Превышения ограничения по времени

Про имена переменных

Begin

Var

Begin

Var

Отступы.

Пример: это кусок моего решения задачи J с заочки 9-10-го года. Без отступов. http://olympiads.ru/zaoch/2009/problems/j.shtml

procedure Main;

i, j, k, ht, l, r, t, q: integer;

z: array [0..31] of integer;

x:= 0;

FillChar(m[1], sizeof(m[1]), 0);

for ht:= 1 to H do begin

pb[0]:= 0;

for i:= 1 to W do pb[i]:= pb[i - 1] + p[ht, i];

FillChar(m[x], sizeof(m[x]), 0);

for k:= 1 to N - H + ht do begin

for l:= 1 to W do begin

z[W + 1]:= 0;

for r:= W downto l do begin

if k >= r - l + 1 then

z[r]:= m[1 - x, k - r + l - 1, l, r] + pb[r] - pb[l - 1]

else z[r]:= 0;

if z[r] < z[r + 1] then z[r]:= z[r + 1];

if z[r] > m[x, k, r, r] then m[x, k, r, r]:= z[r];

end;

end;

for l:= 1 to W - 1 do

for r:= l + 1 to W do begin

t:= m[x, k, l, r - 1];

q:= m[x, k, r, r];

if t > q then m[x, k, l, r]:= t

else m[x, k, l, r]:= q;

end;

end;

x:= 1 - x;

end;

end;

Слабо определить сложность этого алгоритма? И вообще, можно ли как-нибудь понять, что тут написано?

Какому begin-у соответствует пред-предпоследний end?

При каких значениях переменных может произойти присваивание m[x, k, r, r]:= z[r]?

Такой код невозможно не только читать, но и отлаживать.

В оригинале эта процедура выглядит так.

1. procedure Main;

3. i, j, k, ht, l, r, t, q: integer;

4. z: array [0..31] of integer;

6. x:= 0;

7. FillChar(m[1], sizeof(m[1]), 0);

8. for ht:= 1 to H do begin

9. pb[0]:= 0;

10. for i:= 1 to W do pb[i]:= pb[i - 1] + p[ht, i];

11. FillChar(m[x], sizeof(m[x]), 0);

12. for k:= 1 to N - H + ht do begin

13. for l:= 1 to W do begin

14. z[W + 1]:= 0;

15. for r:= W downto l do begin

16. if k >= r - l + 1 then z[r]:= m[1 - x, k - r + l - 1, l, r] + pb[r] - pb[l - 1]

17. else z[r]:= 0;

18. if z[r] < z[r + 1] then z[r]:= z[r + 1];

19. if z[r] > m[x, k, r, r] then m[x, k, r, r]:= z[r];

20. end;

21. end;

22. for l:= 1 to W - 1 do

23. for r:= l + 1 to W do begin

24. t:= m[x, k, l, r - 1];

25. q:= m[x, k, r, r];

26. if t > q then m[x, k, l, r]:= t

27. else m[x, k, l, r]:= q;

28. end;

29. end;

30. x:= 1 - x;

31. end;

32. end;

Тут определить сложность очень просто – она равна O(N*H*W^2), что вполне приемлемо для этой задачи (и, кстати, это решение набрало полный балл). Написать что-то такое, не расставляя отступы, просто невозможно.

Называйте переменные по-нормальному! Используйте хотя бы первые буквы слов, отражающих, по вашему мнению, смысл переменной. Например, сумму цифр числа естественно (хотя и совсем не обязательно) обозначать digsum или DigSum, или просто ds. Координаты лучше обозначать именами x и y. Если нужна еще одна точка, то пусть это будет (x2, y2). Или, например, (xm, ym), если в этой точке достигается какой-нибудь минимум или максимум.

НИКОГДА не называйте переменные именем O(o) или I(i). Потому что операции типа x:= O или I:=1 вводят в замешательство, а выражения типа if O = 0 (if I = 1) и вовсе взрывают мозг.

Не используйте русские слова в именах процедур, функций, переменных и названии программы. Это тупо. Например, некоторые любят писать что-нибудь вроде

function stepen(a, b: integer): integer;

По английски «степень» – «power», а не «stepen». Используйте английские слова.

Вы столкнулись с проблемой небольшого превышения ограничения по времени. Например: на вашем компьютере решение проходит худший тест за 1.5 секунды, а ограничение в задаче - 1c. В таких ситуациях естественно попытаться как-нибудь оптимизировать код. Почти в любом запрограммированном алгоритме есть тонкое место - одна или несколько строк, которые повторяются больше всего раз. Эти места могут существенно повлиять на скорость работы алгоритма, даже если весь остальной код сильно неоптимален. Увидеть их легко благодаря тем самым отступам (они обычно сильнее всего смещены вправо).

Иногда достаточно просто поменять тип параметра функции с long long на long, что избавляет от некоторых лишних (в этом решении) операций.

Оценивайте сложность всех решений, которые пишете. Имейте в виду, что алгоритмы сложности O(N^3) при N ~ 1000 проходят очень редко. Исключение составляет алгоритм Флойда, который довольно часто укладывается в 1-2с.

Программировать можно не только решения задач, но и генераторы тестов, алгоритмы для проверки каких-то гипотез, чекеры (например, когда пишешь банальное решение и на маленьких тестах сверяешь его со своим) и т.д. Это все бывает очень полезно.

Дата добавления: 2015-07-02; Просмотров: 128; Нарушение авторских прав?; Мы поможем в написании вашей работы!