|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 14 Dec 2001 15:52:32
To : Marat Shamshutdinov
Subject : Re: Задача с олимпиады по информатике
--------------------------------------------------------------------------------
Привет! "Marat Shamshutdinov"
<Marat.Shamshutdinov@p40.f10.n5052.z2.fidonet.org> сообщил(а) нам:
> AE> Максимальное кол-во комбинаций - 59132290782430712. Для 10 секунд это
> AE> слишком много.
> О чем я и говорю. Посмотри решение Сергея Политова.
Красиво. Только СП немного перемудрил:
b[j,g]:= a[j,g];
if o<=g then b[j,g]:= b[j,g]+a[j-1,g-o] else
b[j,g]:= b[j,g]+a[j-1,k+g-o];
Эквивалентно
b[j,g]:=a[j,g]+a[j-1, ((k-o)+g) mod k];
что куда понятнее.
А если во внешнем цикле заменить o:=trunc(tmp) на o:=k-trunc(tmp), то
выражение сокращается до:
b[j,g]:=a[j,g]+a[j-1, (o+g) mod k];
Аналогично в конце процедуры вместо
o:= trunc(tmp); q:= q*2;
if o<>0 then s:= a[m-1,k-o] else s:= a[m-1,0];
можно записать
s:=a[m-1, (k-trunc(tmp)) mod k];
Понятно, что mod - не самая быстрая операция, но получившийся текст куда
понятнее, а в 10 секунд более чем укладывается.
С уважением, Андрей.
--- ifmail v.2.15dev5
* Origin: COMSTAR Telecommunications (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
