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


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

Ви не зайшли.

#1 2007-11-07 14:37:27

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Тур наконец-то закончен и резалты тож есть

Предлагаю выкладывать интересные чем то решения. Например самые короткие решения. Естественно решения должны быть АС
PS: Задачи легкие так что давайте у кого так сказать короче )) или лаконичнее.

Відредаговано necro (2007-11-07 16:30:22)


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#2 2007-11-07 14:47:13

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Тур наконец-то закончен и резалты тож есть

Начну сам ) :
_____________________________________________________
Snake :
var
   x, y : longint;
begin
   readln(x, y);
   writeln(abs(2 * (ord(abs(x) <= abs(y)) * x + ord(abs(x) > abs(y)) * y)) + 2 * abs(abs(x) - abs(y)) - ord(odd(abs(x - y))));
end.

_____________________________________________________


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#3 2007-11-07 17:39:39

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

Re: Тур наконец-то закончен и резалты тож есть

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.

Поза форумом

 

#4 2007-11-07 17:43:05

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Тур наконец-то закончен и резалты тож есть

Cris написав:

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.

Не спорю что куда лаконичнее но я написал в две строки и этим я хотел зарулить )).
У когото есть более коротике решения типа readln-writeln?


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#5 2007-11-07 17:43:57

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

Re: Тур наконец-то закончен и резалты тож есть

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

Поза форумом

 

#6 2007-11-07 17:44:55

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Тур наконец-то закончен и резалты тож есть

Gears :

var
   a : array [1..10000] of boolean;
   ans, i, n, k : longint;
begin
   read(n);
   ans := -2;
   for i := 1 to n do begin
      read(k);
      ans := ans + 1 + ord(not a[k]);
      a[k] := true;
   end;
   writeln(ans);
end.


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#7 2007-11-07 17:45:30

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

Re: Тур наконец-то закончен и резалты тож есть

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

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

Поза форумом

 

#8 2007-11-07 17:48:32

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Тур наконец-то закончен и резалты тож есть

Cris написав:

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

Ну по сути идея у тебя верная : упорядочиваем массив, так как если колеса одного радиуса рядом, то нужна одна шестеранка иначе - две. Я использовал линейную сортировку (точнее ее идею) так как тип входных данных меньше интежера.


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#9 2007-11-07 17:49:41

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

Re: Тур наконец-то закончен и резалты тож есть

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.

Поза форумом

 

#10 2007-11-07 17:49:55

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Тур наконец-то закончен и резалты тож есть

Cris написав:

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

полный бал. Неполные решения непубикуют обычно - разве что чтото хитрое.


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#11 2007-11-07 17:51:58

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Тур наконец-то закончен и резалты тож есть

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 взял бы. А так сколько?


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#12 2007-11-07 17:52:59

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Тур наконец-то закончен и резалты тож есть

Более подробно мое решение пояснить или все ясно уже?


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#13 2007-11-07 18:06:25

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

Re: Тур наконец-то закончен и резалты тож есть

обьясни
и вот мой кайф:
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.

Поза форумом

 

#14 2007-11-07 18:07:55

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

Re: Тур наконец-то закончен и резалты тож есть

разкажи как ты делал милитари, ато я делал самым простым и тупым способом проходил масив и менял де надо > на < и< на>

Поза форумом

 

#15 2007-11-07 18:09:11

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

Re: Тур наконец-то закончен и резалты тож есть

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

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

Поза форумом

 

#16 2007-11-07 18:23:00

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

Re: Тур наконец-то закончен и резалты тож есть

кста а нельзя ли получить какие были тесты??
на разные задачи или же авторские прогрыма?

Поза форумом

 

#17 2007-11-07 18:46:08

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Тур наконец-то закончен и резалты тож есть

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)


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#18 2007-11-07 18:51:23

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Тур наконец-то закончен и резалты тож есть

Cris написав:

кста а нельзя ли получить какие были тесты??
на разные задачи или же авторские прогрыма?

Пожжей - после олимпы (всех 4 туров) обычно вывешивают архив олимпы. А пока что можеш писать решения и сдавать в онлайне уже на полном наборе тестов.


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#19 2007-11-07 19:00:28

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Тур наконец-то закончен и резалты тож есть

Cris написав:

обьясни

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

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


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#20 2007-11-07 19:06:11

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Тур наконец-то закончен и резалты тож есть

Cris написав:

обьясни
и вот мой кайф:
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.

Мой кайф по легче но задумка то проста остальное дело техники:
var
   s : string;
   ch : char;
   q, i, j, k, p : longint;
begin
   read(p);
   readln(ch, s);

   q := length(s) - p;
   k := 1;

   for i := 1 to length(s) - p do begin
      for j := k to length(s) - q + 1 do if (s[k] < s[j]) then k := j;
      write(s[k]);
      dec(q); inc(k);
   end;
end.


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#21 2007-11-07 19:26:51

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

Re: Тур наконец-то закончен и резалты тож есть

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

Поза форумом

 

#22 2007-11-07 20:58:38

Nicky Nick
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-25
Повідомлень: 48
Вебсайт

Re: Тур наконец-то закончен и резалты тож есть

Military:

Код:

#include <stdio.h>

int sum,max;

void ReadNSolve ()
{
    sum = max = 0;

    int i = 0;
    int curleft = 0;
    int delay = 0;
    int moves;

    char c;
    scanf ("%c",&c);
    while ((c == '>') || (c == '<'))
    {
        if (c == '<')
        {
            moves = (i-curleft);
            sum += moves;

            if (moves > 0)
            {
                if (moves + delay > max)
                    max = moves + delay;
                delay++;
            }

            curleft++;
        }
        else
        {
            if (delay > 0)
                delay--;
        }

        i++;
        scanf ("%c",&c);
    }
}

void WriteData ()
{
    printf ("%d %d\n",max,sum);
}

int main ()
{
//    freopen ("military4.dat","r",stdin);
//    freopen ("military4.sol","w",stdout);

    ReadNSolve ();
    WriteData ();

    return 0;
}

Надеюсь, алгоритм будет несложно понять - старался писать чисто.

Поза форумом

 

#23 2007-11-07 22:53:35

Skiminok
Новий користувач
Звідки: Киев, Украина
Зареєстрований: 2006-01-19
Повідомлень: 144
Вебсайт

Re: Тур наконец-то закончен и резалты тож есть

Думаю, интересными здесь покажутся 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)


Если вы с первого раза сумели написать программу, в которой транслятор не обнаружил ни одной ошибки, сообщите об этом системному программисту. Он исправит ошибки в трансляторе.
http://wwp.icq.com/scripts/online.dll?icq=282667777&amp;img=5ICQ 282667777

Поза форумом

 

#24 2007-11-07 23:54:19

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Тур наконец-то закончен и резалты тож есть

Почему же Снейк елементарная. Простая - да но реализация то разной длинны бывает вот мой Readln Writeln я уже выкладывал, но может кто по короче смог? Понятно что за чудоалогритмами тут фактически нечего гнатся.

ПС : Имхо мой Гиарс покруче ))

Код:

var
   a : array [1..10000] of boolean;
   ans, i, n, k : longint;
begin
   read(n);
   ans := -2;
   for i := 1 to n do begin
      read(k);
      ans := ans + 1 + ord(not a[k]);
      a[k] := true;
   end;
   writeln(ans);
end.

Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#25 2007-11-11 22:50:08

Брэнд
Новий користувач
Звідки: Днепропетровск
Зареєстрований: 2007-09-30
Повідомлень: 44

Re: Тур наконец-то закончен и резалты тож есть

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

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt