Блог пользователя danpol

Автор danpol, 12 лет назад, По-русски

Мало кто знает о том, что возможности языка C постепенно внедряются в... Delphi!

Давайте взглянем на основные нововведения:

1) [BDS 2006 +]появление возможности перегрузки операторов (хотя это и реализовано никудышно): подробнее здесь

2) [Delphi 2009 +] появление такой вещи как generics — аналог шаблонов C: подробнее здесь

Пример использования дженериков:

type
  TPoint<T> = record
    X: T;
    Y: T;
  end;

Ничего не напоминает?

3) На основе дженериков написан аналог STL — Generics.Collections, в котором реализованы полезные структуры данных, например LIFO (стек), queue, TDictionary (аналог set)... Реализованы сортировка, бинпоиск и многое другое.

program Generics;

{$APPTYPE CONSOLE}

uses
  SysUtils, Generics.Collections;

var
  dictionary: TDictionary<string, integer>;
  s: string;
  i: integer;
  n, m: integer;
begin
  dictionary := TDictionary<string, integer>.create;
  readln(n);
  for i := 1 to n do
  begin
    readln(s);
    dictionary.Add(s, i);
  end;
  readln(m);
  for i := 1 to m do
  begin
    readln(s);
    writeln(dictionary.ContainsKey(s));
  end;
end.

Такие нововведения ставят Delphi на новую ступень развития. А, прибавляя ко всему прочему простоту разработки, отладки и т.д., можно назвать этот язык достойным звания одного из лучших.

Но вот так не задача... Во всех проверяющих системах стоит Delphi 7 (а то и хуже)! Я думаю, что все паскалисты были бы рады обновлению Delphi хотя бы до версии 2009.

От себя хочу еще добавить, что я возлагаю большие надежды на CodeForces и надеюсь, что (если это возможно) мы в скором времени увидим в разделе выбора языка надпись "Delphi 2009".

Полный текст и комментарии »

  • Проголосовать: нравится
  • -26
  • Проголосовать: не нравится

Автор danpol, 12 лет назад, По-русски

Кто где какие пасхалки встречал? В гугле, в играх...)

Полный текст и комментарии »

  • Проголосовать: нравится
  • -37
  • Проголосовать: не нравится

Автор danpol, 12 лет назад, По-русски

Предисловие:

1) На одном из раундов CF я получил TL на халявной задаче и не смог его отладить, несмотря на то что асимптотика решения была O(NlogN), что влезало в LT

2) На одном из туров в ЛКШ у меня не прошла задача на тупое построение выпуклой оболочки за O(NlogN), что влезало в TL.

Итак, я был зол...

В первой задаче в итоге мне хватило только random-а в QSort-е. Но со второй не так-то уж все и просто оказалось.

Что же я сделал?

о1) Будем передавать все параметры по ссылке, а не по значению. (var или const)

о2) Будем делать рандомизтрованный QSort

о3) Магия: вместо свопанья структурок будем свопать отдельные поля! (Если убрать остальные оптимайзы, и оставить только о3 все проходит!

о4) Т.к. TL критичен, избавимся от лишних вызовов "быстрых" {O(1)} функций.

o5) функции "в одну строчку" типа подсчета скалярного произведения выкиним вообще и будем каждый раз вычислять в длинных формулах.

Вот так с 1.006 секунд на тесте, на котором я получал TL, я получил 0.010 секунд на нем же и сдал задачу.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -13
  • Проголосовать: не нравится