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

guest1 написав:

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

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).

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

как помне это неправильно, сто первая что вторая,
первая: оно будет работать правильно но ОЧЕНЬ ДОЛГО -         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 случай когда число берем другой когда не берем и все) и делаем большое дерево, - так мы узнаем можноли азложить какоето число на какието другие + пишим еше цыкл для проверки

Задача 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.

sonner написав:

guest1 написав:

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

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

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

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 ?

Попробую выложить свои идеи по поводу этих всех задач.
Я конечно не считаю себя сильно крутым по поводу создания алгоритмов, но к сожалению я пока согласен только с решениями задач 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-эта сумма" - минимальная, которую нельзя заплатить объединив купюры продавца и покупателя. Алгоритм нахождения этой суммы - известная задача(правда я ее не нашел )
Задача 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)
Это конечно не простая формулка, но пораскинув мозгами, исходя из теории чисел можно догадатся.

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 ?

бывает...))

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

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

pro написав:

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

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

pro написав:

redman17 написав:

pro написав:

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

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

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

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

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.

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

summa(long ver )

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)

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

if m=n then write(0)

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

MAXXX написав:

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

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