Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2008-12-23 00:08:12

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Разбор решений задач.

http://drop.io/olymp2008 — исходники второго тура, кроме market'a.

Відредаговано guest1 (2008-12-23 19:56:29)

Поза форумом

 

#2 2008-12-23 00:43:24

sonner
Новий користувач
Зареєстрований: 2008-11-25
Повідомлень: 8

Re: Разбор решений задач.

guest1 написав:

Market
Для начала обратим внимание, что нам нужна именно максимальная сумма. Поэтому в покупке обязательно будут участвовать все деньги покупателя.

Как по мне, это не совсем так.
2 4 10 2 1 2

Відредаговано sonner (2008-12-23 00:45:16)

Поза форумом

 

#3 2008-12-23 07:32:30

Cris
Новий користувач
Звідки: Сумы
Зареєстрований: 2007-10-02
Повідомлень: 140

Re: Разбор решений задач.

guest1 написав:

Итак, начнём. Пока что выкладываю сами идеи (а также прошу прощения за возможные грамматические ошибки), ибо «обзор» делался в условиях отсутствия света и на чужом ноуте smile

Device
Для начала попробуем смоделировать данную ситуацию в рекурсивной procedure Research(value: longint), где value — количество оставшихся приборов. Итак, если у нас остаётся три прибора, то увеличиваем счётчик вариантов на единицу; если приборов осталось два или один, то не делаем ничего. В остальных случаях мы рассматриваем две новые группы, получающиеся из данной. Если исходная группа имеет чётную длину, то две новые группы имеют одинаковую длину; в противном случае длина одной из групп больше длины другой группы на единицу. Cостав групп нам не важен — они нумеруются автоматически. Получаем такой код, моделирующий ситуацию:
program Device;
var N, R: longint;
procedure Research(value: longint);
begin
    if value < 4 then begin
        if value = 3 then inc(R);
    end else begin
        if value mod 2 = 0 then begin
           Research(value div 2);
           Research(value div 2);
        end else begin
            Research(value div 2);
            Research(value div 2 + 1);
        end;
    end;
end;
begin
    read(N); R:=0;
    Research(N);
    write(N);
end.
Это решение самое очевидное, однако, как нетрудно заметить, время его выполнения будет достаточно большим (~О(2^N)).
Начнём искать пути оптимизации. Для начала выпишем в строку результаты для нескольких первых N, получим строку:
0 0 1 0 1 2 1 0 1 2 3 4 3 2 1 0 ...
Замечаем, что эта строка является последовательностью из чередующихся подъёмов и спадов, причём каждым новым пиком последовательности является новая степень двойки. Разобьём для удобства нашу строку на такие отрезки:
0
0 1
0 1 2 1
0 1 2 3 4 3 2 1
...
N-ая строка имеет длину 2^(N – 1) и пик 2^(N – 2) (исключение — первая строка, пик 0). Для начала найдём, которому отрезку принадлежит N — в этом нам поможет формула 2^0 + 2^1 + 2^2 + ... + 2^(N – 1) = 2^N – 1. Имея все эти данные, можно вычислить ответ.

Market
Для начала обратим внимание, что нам нужна именно максимальная сумма. Поэтому в покупке обязательно будут участвовать все деньги покупателя. Просуммируем их, пусть значение суммы всех денег покупателя будет равно X.
Для купюр продавца же нам необходимо найти наименьшее число, которое нельзя будет получить из суммы некоторых его купюр. Для решения этой подзадачи нам необходимо отсортировать массив купюр по возрастанию. Если в результате сортировки первый элемент не будет равен 1, то мы нашли ответ к этой подзадаче — 1. Иначе, работаем по такому общему алгоритму: если сумма всех предыдущих чисел массива меньше текущего более, чем на единицу, то ответом будет сумма всех предыдущих чисел + 1; иначе прибавляем к сумме всех предыдущих чисел текущее число. Ответ к этой подзадаче обозначим буквой Y.
В итоге, ответом к задаче будет X – Y (но если X – Y < 0, то есть мы можем купить товаров на любую доступную нам сумму, то выводим 0).

--- пока что всё, если нам завтра включат свет, пост будет дополнен smile ---

как помне это неправильно, сто первая что вторая,
первая: оно будет работать правильно но ОЧЕНЬ ДОЛГО -         if value mod 2 = 0 then begin
           Research(value div 2);
           Research(value div 2); - ониже одинаковые  - тоесть можно запустить только один раз а в конце при подсчете ответа умножить на 2 и будет работать раз в 15 быстрей

по второй задаче - ты думаеш как мой учитель))) как сказал sonner 2 4 10 2 1 2,  по твоему принцыпу ответ будет 10, а должно быть  6,   эту задачу я делал тупым и хорошым способом и как оказалось потом быстрым - запускаем рекурсию 1 случай когда число берем другой когда не берем и все) и делаем большое дерево, - так мы узнаем можноли азложить какоето число на какието другие + пишим еше цыкл для проверки

Поза форумом

 

#4 2008-12-23 11:25:30

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Разбор решений задач.

В Device приведено лишь моделирование ситуации, сами исходники я ещё не выкладывал, если дома будет свет — выложу позже.

Поза форумом

 

#5 2008-12-23 13:01:40

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

Задача Winner

Простая математика: сначала в банке было N*Z, на i-том этапе снимают (N-i)*T для i от 0 до N-2. Получаем:
S(N)=N*Z-(N*T+(N-1)*T+...+2*T)=N*Z-T*(N+2)*(N-1)/2.
Если взять по этой штуке производную: S'(N)=Z-T*N+T/2.
Тогда максимум нашей функции достигается в Nmax=(2*Z-T)/(2*T).
Так как Nmax не обязательно целое то проверим на максимум S(trunc(Nmax)) и S(Trunc(Nmax)+1) убедившись что не ищем S(1):

Код:

{$I-,Q-,R-,S-}
program winner;
var t,z,n1,n2,s1,s2:int64;
begin
     read(z,t);
     n1:=(2*z-t) div (2*t);
     n2:=n1+1;
     s1:=n1*z-t*(n1+2)*(n1-1) div 2;
     s2:=n2*z-t*(n2+2)*(n2-1) div 2;
     if (s1>=s2) and (n1>1) then write(n1,' ',s1)
                            else write(n2,' ',s2);
end.

WE DIE HARD!!!

Поза форумом

 

#6 2008-12-23 13:06:27

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

Задача Cavalery

Простой поиск в ширину (только не дай бог для каждого коня отдельный!!!) - из целевой точки ищем длину пути во все остальные:

Код:

{$I-,Q-,R-,S-}
program cavalery;
const mn=100;
      mq=10000;
var n,m,sx,sy,q,h,t,i,j,nx,ny,nd,ans:longint;
    mp:array[1..mn,1..mn] of longint;
    x,y:array[1..mq] of longint;
    d:array[1..mn*mn,1..3] of longint;
    get_all:boolean;

    procedure put(x,y,dp:longint);
    begin
         if (x>=1) and (x<=n) and (y>=1) and (y<=m) and (mp[x,y]=-1) then
            begin
                 d[t,1]:=x;
                 d[t,2]:=y;
                 d[t,3]:=dp;
                 t:=t+1;
                 mp[x,y]:=dp;
            end;
    end;

begin
     read(n,m,sx,sy,q);
     for i:=1 to n do for j:=1 to m do mp[i,j]:=-1;
     for i:=1 to q do read(x[i],y[i]);
     h:=1;
     t:=2;
     d[1,1]:=sx;
     d[1,2]:=sy;
     d[1,3]:=0;
     mp[sx,sy]:=0;
     while (t>h) do
       begin
            nx:=d[h,1];
            ny:=d[h,2];
            nd:=d[h,3];
            put(nx+1,ny+2,nd+1);
            put(nx+1,ny-2,nd+1);
            put(nx-1,ny+2,nd+1);
            put(nx-1,ny-2,nd+1);
            put(nx+2,ny+1,nd+1);
            put(nx+2,ny-1,nd+1);
            put(nx-2,ny+1,nd+1);
            put(nx-2,ny-1,nd+1);
            h:=h+1;
       end;
     ans:=0;
     get_all:=true;
     for i:=1 to q do
         if get_all then
            begin
                 if mp[x[i],y[i]]>=0 then ans:=ans+mp[x[i],y[i]]
                                     else begin ans:=1; get_all:=false; end;
            end else ans:=ans+ord(mp[x[i],y[i]]=-1);
     write(ans);
end.

Відредаговано redman17 (2008-12-23 13:06:40)


WE DIE HARD!!!

Поза форумом

 

#7 2008-12-23 13:07:30

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Разбор решений задач.

sonner написав:

guest1 написав:

Market
Для начала обратим внимание, что нам нужна именно максимальная сумма. Поэтому в покупке обязательно будут участвовать все деньги покупателя.

Как по мне, это не совсем так.
2 4 10 2 1 2

Действительно. Спасибо.

Поза форумом

 

#8 2008-12-23 13:09:30

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

Задача Device

guest1 написав:

В Device приведено лишь моделирование ситуации, сами исходники я ещё не выкладывал, если дома будет свет — выложу позже.

Если кто-то ждет не дождется этого уникального кода:

Код:

{$I-,Q-,R-,S-}
program device;
var i,n2,n,ans:int64;
begin
     read(n);
     i:=0;
     n2:=1;
     while 2*n2<=n do begin i:=i+1; n2:=n2*2; end;
     if n<3*n2 div 2 then ans:=n-n2
                     else ans:=2*n2-n;
     if n<3 then ans:=0;
     write(ans);
end.

Відредаговано redman17 (2008-12-23 13:09:53)


WE DIE HARD!!!

Поза форумом

 

#9 2008-12-23 17:34:59

Funeral Violator
Новий користувач
Звідки: Подалі від УФМЛ
Зареєстрований: 2008-11-29
Повідомлень: 1

Re: Разбор решений задач.

redman17 написав:

Задача Device

guest1 написав:

В Device приведено лишь моделирование ситуации, сами исходники я ещё не выкладывал, если дома будет свет — выложу позже.

Если кто-то ждет не дождется этого уникального кода:

Код:

{$I-,Q-,R-,S-}
program device;
var i,n2,n,ans:int64;
begin
     read(n);
     i:=0;
     n2:=1;
     while 2*n2<=n do begin i:=i+1; n2:=n2*2; end;
     if n<3*n2 div 2 then ans:=n-n2
                     else ans:=2*n2-n;
     if n<3 then ans:=0;
     write(ans);
end.

в этом коде непонятно только одно... какую роль играет переменная I ? smile

Поза форумом

 

#10 2008-12-23 17:58:17

Cris
Новий користувач
Звідки: Сумы
Зареєстрований: 2007-10-02
Повідомлень: 140

Re: Разбор решений задач.

Funeral Violator написав:

redman17 написав:

Задача Device

guest1 написав:

В Device приведено лишь моделирование ситуации, сами исходники я ещё не выкладывал, если дома будет свет — выложу позже.

Если кто-то ждет не дождется этого уникального кода:

Код:

{$I-,Q-,R-,S-}
program device;
var i,n2,n,ans:int64;
begin
     read(n);
     i:=0;
     n2:=1;
     while 2*n2<=n do begin i:=i+1; n2:=n2*2; end;
     if n<3*n2 div 2 then ans:=n-n2
                     else ans:=2*n2-n;
     if n<3 then ans:=0;
     write(ans);
end.

в этом коде непонятно только одно... какую роль играет переменная I ? smile

то он попривычке цыкл описывал и увеличивал счетчик)

Поза форумом

 

#11 2008-12-23 19:01:11

pro
Новий користувач
Звідки: Черкаси
Зареєстрований: 2007-11-14
Повідомлень: 33

Re: Разбор решений задач.

Попробую выложить свои идеи по поводу этих всех задач.
Я конечно не считаю себя сильно крутым по поводу создания алгоритмов, но к сожалению sad я пока согласен только с решениями задач Winner и Cavalery.
Начну с задачи Device:

Код:

function res(n:longint):qword;
begin
   if n=3 then begin res:=1; exit; end;
   if n<3 then begin res:=0; exit; end;
   if n mod 2<>0 then
      res:=res(n div 2)+res(n div 2+n mod 2) 
   else
      res:=2*res(n div 2);
end;

Не буду делать оценок, но на максимальном значении, эта штука работает незаметно для глаза.
Задача Market:
Расположим все суммы которые может оплатить покупатель своими деньгами в порядке возрастания. Если есть сумма X<S_max div 2, то если считать с конца, не учитывая максимальной суммы(S_max), то сумма, такая же по номеру, как и X равна S_max-X!!! Пускай мы нашли искомую сумму. Она равна: ai1+ai2+...+aik+bi1+bi2+...+bit, где a - множество купюр покупателя, а b - продавца. Если искомая сумма - максимальная искомая, то "S_max-эта сумма" - минимальная, которую нельзя заплатить объединив купюры продавца и покупателя. Алгоритм нахождения этой суммы - известная задача(правда я ее не нашел smile )
Задача Summa
Введем ф-цыю, которая находит сумму цифр чисел от 1 до N - T(N). Тогда "искомая сумма=T(N2)-T(N1-1)". Ну а если N=a1 a2 a3 a4 ... an(цифры)
T(a1 a2 ... an)=T(a2 a3...an)+a1*(a2 a3..an)+T(a1 0 0 0 0...(N-1 раз))=T(a2 a3 ... an)+a1*(a2 a3 ... an)+a1+(a1 + 1)*T(9 9 ...(N-1 раз))+T(a1-1)*10^(N-1)
Это конечно не простая формулка, но пораскинув мозгами, исходя из теории чисел можно догадатся.


"Никакие украшения не являются постоянными, будь то картина или цветы в нише. Перемены — да. Но суть всегда остается неизменной." Перл Бак.

Поза форумом

 

#12 2008-12-23 19:19:35

pro
Новий користувач
Звідки: Черкаси
Зареєстрований: 2007-11-14
Повідомлень: 33

Re: Разбор решений задач.

http://depositfiles.com/ru/files/s9nrpprad - скомпиленая Device, если кто не верит


"Никакие украшения не являются постоянными, будь то картина или цветы в нише. Перемены — да. Но суть всегда остается неизменной." Перл Бак.

Поза форумом

 

#13 2008-12-23 19:30:05

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

Funeral Violator написав:

redman17 написав:

Задача Device

guest1 написав:

В Device приведено лишь моделирование ситуации, сами исходники я ещё не выкладывал, если дома будет свет — выложу позже.

Если кто-то ждет не дождется этого уникального кода:

Код:

{$I-,Q-,R-,S-}
program device;
var i,n2,n,ans:int64;
begin
     read(n);
     i:=0;
     n2:=1;
     while 2*n2<=n do begin i:=i+1; n2:=n2*2; end;
     if n<3*n2 div 2 then ans:=n-n2
                     else ans:=2*n2-n;
     if n<3 then ans:=0;
   write(ans);
end.

в этом коде непонятно только одно... какую роль играет переменная I ? smile

бывает...))

стоит ли дискутировать о роле буквы i в слове "паровоз"(с)?)))

Відредаговано redman17 (2008-12-23 19:41:53)


WE DIE HARD!!!

Поза форумом

 

#14 2008-12-23 19:31:49

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

pro написав:

Я конечно не считаю себя сильно крутым по поводу создания алгоритмов, но к сожалению sad я пока согласен только с решениями задач Winner и Cavalery.

С чем именно? (не согласен)


WE DIE HARD!!!

Поза форумом

 

#15 2008-12-23 19:45:45

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Разбор решений задач.

pro написав:

http://depositfiles.com/ru/files/s9nrpprad - скомпиленая Device, если кто не верит

Та верю, верю smile
Извиняюсь, были глюки машины.

Поза форумом

 

#16 2008-12-23 19:57:32

pro
Новий користувач
Звідки: Черкаси
Зареєстрований: 2007-11-14
Повідомлень: 33

Re: Разбор решений задач.

redman17 написав:

pro написав:

Я конечно не считаю себя сильно крутым по поводу создания алгоритмов, но к сожалению sad я пока согласен только с решениями задач Winner и Cavalery.

С чем именно? (не согласен)

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


"Никакие украшения не являются постоянными, будь то картина или цветы в нише. Перемены — да. Но суть всегда остается неизменной." Перл Бак.

Поза форумом

 

#17 2008-12-23 20:04:54

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

pro написав:

redman17 написав:

pro написав:

Я конечно не считаю себя сильно крутым по поводу создания алгоритмов, но к сожалению sad я пока согласен только с решениями задач Winner и Cavalery.

С чем именно? (не согласен)

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

скорее с сочетанием скорость - сложность обнаружения решения smile


WE DIE HARD!!!

Поза форумом

 

#18 2008-12-23 20:09:58

astor
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 48

Re: Разбор решений задач.

device

Код:

var
t,n:int64;
begin
read(n);
t:=2;
if n<3 then writeln('0') else
begin
 while t<n do
  t:=t*2;
 if t-n<n-round(t/2) then writeln(t-n) else writeln(n-round(t/2));
end;
end.

Поза форумом

 

#19 2008-12-23 20:12:41

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

astor написав:

device

Код:

var
t,n:int64;
begin
read(n);
t:=2;
if n<3 then writeln('0') else
begin
 while t<n do
  t:=t*2;
 if t-n<n-round(t/2) then writeln(t-n) else writeln(n-round(t/2));
end;
end.

давайте не наполнять тему похожими решениями


WE DIE HARD!!!

Поза форумом

 

#20 2008-12-23 20:15:22

astor
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 48

Re: Разбор решений задач.

давайте не наполнять тему похожими решениями

сорі, по ходу я запіздав... smile

Поза форумом

 

#21 2008-12-23 20:19:49

astor
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 48

Re: Разбор решений задач.

summa(long ver big_smile)

Код:

const
nc:array[1..9] of int64 = (46,901,13501,180001,2250001,27000001,315000001,3600000001,40500000001);
function step10(n:integer):int64;
var i:byte;
    x:int64;
begin
x:=1;
for i:=1 to n do
 x:=x*10;
step10:=x;
end;

function sum1(n:int64):int64;
var
m,s:int64;
begin
 m:=n;
 s:=0;
 if n=0 then s:=0 else
 while m>0 do
  begin
   s:=s+(m mod 10);
   m:=m div 10;
  end;
 sum1:=s;
end;

function sum(n:int64):int64;
var
i,s:integer;
begin
s:=0;
for i:=1 to n do
 s:=s+i;
sum:=s;
end;

function solve{yahooeu!!11}(n:int64):int64;
var
sn:string;
ln,ls:byte;
v,c:integer;
sumn,s:int64;
begin
  sumn:=0;
  str(n,sn);
  ln:=length(sn);
  ls:=1;
  s:=0;
  while ls<ln do
   begin
    val(sn[ls],v,c);
    sumn:=sumn+v*nc[ln-ls]+step10(ln-ls)*(sum1(s)*v+sum(v-1));
    s:=n div step10(ln-ls);
    inc(ls);
   end;
  solve:=sumn+sum(n mod 10)+sum1(n div 10)*(n mod 10);
end;

var
m,n:int64;
begin
 read(m,n);
 if m=n then
 write(0) else
 begin
  write(solve(n)-solve(m-1));
 end;
 writeln;
end.

market

Код:

{$APPTYPE CONSOLE}
type
tmas=array [0..20100] of word;
procedure quicksort(var a: tmas; Lo,Hi: word);
  procedure sort(l,r: integer);
  var
    i,j,x,y: integer;
  begin
    i:=l; j:=r;
    x := a[(r+l) div 2];
    repeat
      while a[i]<x do i:=i+1;
      while x<a[j] do j:=j-1;
      if i<=j then
      begin
        if a[i] > a[j] then
        begin
          y:=a[i]; a[i]:=a[j]; a[j]:=y
        end;
        i:=i+1; j:=j-1
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r)
  end;
begin
  sort(Lo,Hi)
end;

var
a,b:tmas;
m,n,i:word;
s,p:int64;
flag:boolean;
begin
 s:=0;
 read(n);
 for i:=1 to n do
 begin
  read(a[i]);
  s:=s+a[i];
 end;
 read(m);
 for i:=n+1 to m+n do
  read(a[i]);
 Quicksort(a,1,m+n);
 i:=0;
 p:=0;
 b[0]:=0;
 flag:=true;
 while flag and (i<=m+n) do
  begin
   if b[i]+1<a[i+1] then
    begin
     p:=b[i]+1;
     flag:=false;
    end
    else
    begin
     inc(i);
     b[i]:=a[i]+b[i-1];
    end;
  end;
 if not flag then writeln(s-p)
 else writeln(0);
end.

winner

Код:

{$APPTYPE CONSOLE}
var
 n1,n2,z,t:int64;
begin
 read(z,t);
 n1:=(2*z-t) div (2*t);
 n2:=(2*z-t) div (2*t)+1;
 if round(z*n1-t*(n1+2)*(n1-1)/2)>round(z*n2-t*(n2+2)*(n2-1)/2) then
 writeln(n1,' ',round(z*n1-t*(n1+2)*(n1-1)/2)) else writeln(n2,' ',round(z*n2-t*(n2+2)*(n2-1)/2));
end.

cavalery

Код:

{$APPTYPE CONSOLE}
var
sum,m,n,s,t,i,j,head,tail,q:longint;
p:array [-1..102,-1..102] of integer;
k,mas:array [1..11000,1..2] of integer;
procedure move(x1,y1:integer);
begin
    if p[mas[tail,1]+x1,mas[tail,2]+y1]=0 then
     begin
      p[mas[tail,1]+x1,mas[tail,2]+y1]:=p[mas[tail,1],mas[tail,2]]+1;
      mas[head,1]:=mas[tail,1]+x1;
      mas[head,2]:=mas[tail,2]+y1;
      inc(head);
     end;
end;

begin
read(n,m,s,t,q);
for i:=1 to q do
 read(k[i,1],k[i,2]);
sum:=0;
for i:=1 to n do
 for j:=1 to m do
  p[i,j]:=0;
for i:=-1 to n+2 do
 for j:=-1 to 0 do
  p[i,j]:=-1;
for i:=-1 to 0 do
 for j:=1 to m+2 do
  p[i,j]:=-1;
for i:=n+1 to n+2 do
 for j:=1 to m+2 do
  p[i,j]:=-1;
for i:=1 to n do
 for j:=m+1 to m+2 do
  p[i,j]:=-1;
tail:=1;
mas[1,1]:=t;
mas[1,2]:=s;
head:=2;
while head>tail do
 begin
  if p[mas[tail,1],mas[tail,2]]<>-1 then
   begin
    move(-2,-1);
    move(-2,1);
    move(-1,-2);
    move(-1,2);
    move(1,-2);
    move(1,2);
    move(2,-1);
    move(2,1);
   end;
   inc(tail);
 end;
p[t,s]:=0;
for i:=1 to q do
 sum:=sum+p[k[i,1],k[i,2]];
writeln(sum); 
end.

Відредаговано astor (2008-12-23 20:22:07)

Поза форумом

 

#22 2008-12-23 20:28:43

sonner
Новий користувач
Зареєстрований: 2008-11-25
Повідомлень: 8

Re: Разбор решений задач.

А еще давайте не цитировать сообщения полностью (особенно страничные). Это излишне и форум разрастается.

Поза форумом

 

#23 2008-12-23 20:29:37

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

astor's summa написав:

if m=n then write(0)

это не понятно...


WE DIE HARD!!!

Поза форумом

 

#24 2008-12-23 20:31:47

MAXXX
Новий користувач
Звідки: м. Київ
Зареєстрований: 2006-10-17
Повідомлень: 132

Re: Разбор решений задач.

У меня вроде сумма чуть поменьше...

Код:

#include <cmath>
#include <iostream>
#include <sstream>
#include <string> 
using namespace std;
#define L(s) (int)((s).end()-(s).begin())
long long p[15],n,v,S,R,r,h,q;
int i;
void solve()
{
    ostringstream ofs;
    ofs<<v;
    string s=ofs.str();
    S=0;R=0;
    for(i=0;i<L(s);++i)
    {
        h=(s[i]-'0');
        q=L(s)-i-1;
        r=(long long)pow(10.,(int)q);
        R+=S*h*r+r*(h*(h-1))/2+p[q]*h+h;
        S+=h;
    }
}
int main()
{
    p[0]=0;
    n=1;
    for(i=1;i<=15;i++)
    {
        p[i]=10*p[i-1]+n*45;
        n*=10;
    }
    cin>>v;--v;solve();n=R;
    cin>>v;solve();cout<<R-n<<'\n';
    return 0;
}

правда на понятность кода я не претендую=)
А вот мой вариант девайса

Код:

#include <iostream>
using namespace std;
long long n,i,s;
int main()
{
    cin>>n;i=s=1;
    while(n>=s+i)
    {
        s+=i;
        i<<=1;
    }
    i>>=1;
    if (n<=s+i)
        cout<<n-s;
    else
        cout<<i-(n-s-i);
    cout<<endl;
    return 0;
}

Відредаговано MAXXX (2008-12-23 20:33:54)


ICQ 426287475

Поза форумом

 

#25 2008-12-23 20:35:54

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

MAXXX написав:

правда на понятность кода я не претендую=)

тогда неплохо бы объяснить


WE DIE HARD!!!

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt