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

program snake;
var x,y:integer;
begin
read(x,y);
x:=abs(x);
y:=abs(y);
if x>y
then writeln(2*x-((x-y) mod 2))
else writeln(2*y-((y-x) mod 2))
end.

можете разказать слгоритм Gears я так понял что бы найти минимальное количество синих шустеренок
то я упорядочивал масив состоящий из радиусов красных колес и потом проходил масив проверяя:
если они одного размера то надо 1 колесо еси разных размеров то 2
но увы почемуто оно тест непрошло полностью

а разказать?
и сколько эта задача набрала балов?

Відредаговано Cris (2007-11-07 17:47:07)

program gears;
var k,a,i,c,s:longint;
    b:array[1..10000] of integer;
begin
read(a);
for i:=1 to a do
read(b[i]);

while k=0 do
begin
k:=1;
for i:=1 to a-1 do
  if b[i]>b[i+1]
   then begin
         c:=b[i];
         b[i]:=b[i+1];
         b[i+1]:=c;
         k:=0;
        end;
end;

for i:=1 to a-1 do
if b[i]=b[i+1]
  then inc(s)
  else inc(s,2);
write(s);
end.

Cris написав:

program gears;
var k,a,i,c,s:longint;
    b:array[1..10000] of integer;
begin
read(a);
for i:=1 to a do
read(b[i]);

while k=0 do
begin
k:=1;
for i:=1 to a-1 do
  if b[i]>b[i+1]
   then begin
         c:=b[i];
         b[i]:=b[i+1];
         b[i+1]:=c;
         k:=0;
        end;
end;

for i:=1 to a-1 do
if b[i]=b[i+1]
  then inc(s)
  else inc(s,2);
write(s);
end.

Это слишком сложно по времени. Нужно было сортировать хотябы квиксортом тогда 20 из 20 взял бы. А так сколько?

обьясни
и вот мой кайф:
program kife;
var n,i,j:byte;
    g:char;
    l,max,ls:string;
begin
readln(n,g,l);
ls:=l;
for j:=1 to n do
  begin
   max:='';
   for i:=1 to length(l) do
    begin
     delete(l,i,1);
     if max<l
      then max:=l;
     l:=ls;
    end;
  l:=max;
  ls:=l;
end;
write(max);
end.

еси у тя сегмент весь полностью пашет то выложи его код хочю посотреть

и еше про милитари: ты нашол такую комбинацию при какой марш начать невозможно?

Cris написав:

еси у тя сегмент весь полностью пашет то выложи его код хочю посотреть

и еше про милитари: ты нашол такую комбинацию при какой марш начать невозможно?

Segment :
{$APPTYPE CONSOLE}
var
   i, n, pk, k, l, al, ar, ans, sum : longint;
begin
   read(n);

   l := 1; sum := 0; ans := -maxlongint; pk := -maxlongint;

   for i := 1 to n do begin
      read(k);

      if (k = pk + 1) and (k > 0) then sum := sum + k
                                  else begin sum := k; l := i; end;
     
      if ((sum > ans) and (sum <> 0)) then begin
         ans := sum; al := l; ar := i;
      end;

      pk := k;
   end;

   writeln(al, ' ', ar, ' ', ans);
end.

Military : Алогритм придумвал сам и вывел что марш можно закончить всегда. Основная придумка такая что солдаты поворачиваясь просто меняются местами - проходят друг сквозь друга.
Количетво общее шагов считал так : для кажого солдата смотрящего вправо считаем сколько справа от него тех кто смотрит влево и по всем солдатам это сумируем (так как через каждого такого солдата ему надо будет пройти). А про время там долго обьяснять придумай уж сам - там по тому же принципу.

Відредаговано necro (2007-11-07 18:50:10)

Cris написав:

обьясни

По задаче Геарс :
Смотри ответ будет состоять из сумы двух частей :
1. N-1 - между каждой парой соседних колес.
2. +1 на каждый переход между колесами разного радиуса.
По сути мы можем минимизировать только вторую часть минимальное количество соседних колес с разными радиусами будет тогда когда их сгрупировать по радиусам (все с одинаковыми радиусами ставить рядом) - в часности это дает сортировка. То есть вторая часть равна количесву разных радиусов минус один.
И так мой масив булеанов :
a[i] boolean - определяет встречался ли нам уже такой радиус в цикле идем (в моей проге) если не встречался то +1 к счетчику. и Заночим в a[i] = true;
Изначально а[i] = false для всех i

Відредаговано necro (2007-11-07 19:06:43)

спс, все понял

Думаю, интересными здесь покажутся 2 решения - Геарс и Милитари. Снейк не выкладываю - это банально, Сегмент такой же, как и у всех (да и алгоритм красивым не назвать по виду, впрочем, какая разница - всё равно AС), а Кайф - единственный из всех задач - недобрал 5 баллов.
Military4

program Military4;

{$APPTYPE CONSOLE}
type integer=longint;

var
  pc, c: char;
  qr, time, quan: Integer;

function max(a,b: integer): Integer;
begin if a>b  then max:=a else max:=b end;

begin
  repeat Read(c) until (c='>') or eoln;
  qr:=1; time:=0; quan:=0;
  pc:=c;
  while not eoln do
  begin
    Read(c);
    if c='>'
      then Inc(qr)
      else begin
        Inc(quan,qr);
        if pc='>'
          then time:=max(qr,time+1)
          else inc(time)
      end;
    pc:=c;
  end;
  Writeln(time,' ',quan);
end.

Gears

program Gears;

{$APPTYPE CONSOLE}
var count:array [1..10000] of integer;
    N,i,K,max:integer;

begin
  Read(N);
  max:=0;
  for i := 1 to N do
  begin
    read(k);
    inc(count[k]);
    if k>max then max:=k;
  end;
  i:=1; while (i<=max) and (count[i]=0) do inc(i);
  K:=count[i]-1;
  inc(i);
  while i<=max do
  begin
    if count[i]>0 then inc(K,count[i]+1);
    inc(i);
  end;
  Writeln(K);   
end.

Відредаговано Skiminok (2007-11-07 22:54:20)

Интересно, а есть ли у кого-нибудь безмассивный Кайф?