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


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

Ви не зайшли.

#76 2005-11-19 17:22:54

Angry Coder
Олімпієць
Зареєстрований: 2005-11-03
Повідомлень: 42

Re: У кого какое решение?

а еще у Злого Кодера не пройдет задача Piece. потому что он любит сдавать не тестируя. но это не большая потеряsmile

Поза форумом

 

#77 2005-11-19 17:29:10

Angry Coder
Олімпієць
Зареєстрований: 2005-11-03
Повідомлень: 42

Re: У кого какое решение?

2jack_spektor

(1 24) (1 50) (2 54) (2 83) (3 33) (4 70) (5 21) (6 68) (7 43) (8 59) (9 80) (10 48) (11 62) (12 25) (12 74) (13 60) (13 71) (14 46) (15 22) (15 85) (16 11) (17 82) (18 87) (20 3) (20 36) (21 89) (22 60) (23 63) (24 7) (25 64) (26 48) (27 17) (27 61) (28 52) (28 77) (29 54) (29 78) (30 80) (31 18) (34 16) (34 67) (35 47) (37 32) (37 62) (38 9) (3898) (39 14) (40 57) (40 90) (41 30) (41 58) (42 61) (42 81) (44 91) (44 93) (45 81) (46 100) (49 52) (49 95) (51 98) (53 19) (53 75) (55 8) (55 39) (56 73) (56 84) (57 78) (59 92) (63 45) (64 51) (65 79) (65 82) (69 23) (69 35) (70 33) (71 95) (72 50) (72 79) (73 67) (74 68) (75 93) (76 19) (76 88) (77 6) (83 96) (84 88) (85 31) (86 43) (86 66) (87 58) (89 4) (90 26)(91 32) (92 36) (94 47) (96 94) (97 5) (99 10) (99 97) (100 66)

вот что выводит твоя программа если сделать show(cards,n) в конце. очевидно, карты лежат неправильно. так что не 27. sad

Поза форумом

 

#78 2005-11-19 17:30:14

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: У кого какое решение?

Интересно,а у Енди есть аналогичные тесты для Бляма или Piece.


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#79 2005-11-19 17:30:20

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

Re: У кого какое решение?

jack_блин_inspector написав:

И вообще Кодер вовсем не злой.Он аг-р-р-есивный... :-)
angry - сердитый,аггресивный (англ.)

Я знаю...

2"Агрессивный кодер"

А че заглючила piece????


Не бывает сложных задач бывают тупые решатели!!!! smile

Поза форумом

 

#80 2005-11-19 17:31:58

Angry Coder
Олімпієць
Зареєстрований: 2005-11-03
Повідомлень: 42

Re: У кого какое решение?

в формулах ошибся. и не потестировал. на афтарском прошло - круто. здавать smile

Поза форумом

 

#81 2005-11-19 17:37:45

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: У кого какое решение?

Angry Coder написав:

2jack_spektor

(1 24) (1 50) (2 54) (2 83) (3 33) (4 70) (5 21) (6 68) (7 43) (8 59) (9 80) (10 48) (11 62) (12 25) (12 74) (13 60) (13 71) (14 46) (15 22) (15 85) (16 11) (17 82) (18 87) (20 3) (20 36) (21 89) (22 60) (23 63) (24 7) (25 64) (26 48) (27 17) (27 61) (28 52) (28 77) (29 54) (29 78) (30 80) (31 18) (34 16) (34 67) (35 47) (37 32) (37 62) (38 9) (3898) (39 14) (40 57) (40 90) (41 30) (41 58) (42 61) (42 81) (44 91) (44 93) (45 81) (46 100) (49 52) (49 95) (51 98) (53 19) (53 75) (55 8) (55 39) (56 73) (56 84) (57 78) (59 92) (63 45) (64 51) (65 79) (65 82) (69 23) (69 35) (70 33) (71 95) (72 50) (72 79) (73 67) (74 68) (75 93) (76 19) (76 88) (77 6) (83 96) (84 88) (85 31) (86 43) (86 66) (87 58) (89 4) (90 26)(91 32) (92 36) (94 47) (96 94) (97 5) (99 10) (99 97) (100 66)

вот что выводит твоя программа если сделать show(cards,n) в конце. очевидно, карты лежат неправильно. так что не 27. sad

Облом...Капут...
Ну,звиняюсь,здаюсь...Ваша взяла...

Но на маленьких тестах моя всё равно работает.Так что пару баллов я наверно получу.
Жалко...

Відредаговано jack_spektor (2005-11-19 17:43:41)


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#82 2005-11-19 17:42:27

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

Re: У кого какое решение?

Это был рандомный *корректный* тест для N=100.
Мой ответ тоже 48.

Поза форумом

 

#83 2005-11-19 18:42:38

Джулгаков Дмитрий
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 61

Re: У кого какое решение?

Ответ действительно 48!!!!!!

Решение за время O(n) на Паскале:

Код:

const
  maxN = 65535;
var
  N, KK, KSum, i, j, P, Prev, nnew : longint;
  Side : Byte;
  K : array [1..2] of Integer;
  A : array [1..2, 1..maxN] of Word;
  D : array [1..2, 1..maxN] of Byte;
  First : array [1..10000] of Word;
  t : longint;
begin
  Read(N);
  FillChar(D, SizeOf(D), 0);
  for i := 1 to N do
    Read(First[i]);
  for i := 1 to N do
  begin
    Read(t);
    Inc(D[2, t]);
    Inc(D[1, First[i]]);
    if D[1, First[i]] = 2 then
      A[2, First[i]] := t
    else
      A[1, First[i]] := t;
    if D[2, t] = 2 then
      A[1, t] := First[i]
    else
      A[2, t] := First[i];
  end;

  KSum := 0;
  for i := 1 to N do
  begin
    if D[1, First[i]] <> 2 then
      Continue;
    K[1] := 0;
    K[2] := 0;
    KK := 1;
    P := A[1, first[i]];
    D[1, First[i]] := 3;
    K[1] := 1;
    Side := 2;
    Prev := 0;

    while D[1, P] < 3 do
    begin
      if D[Side, P] = 2 then
      begin
        D[Side, P] := 3;
        if Prev=A[1, P] then
          nnew := A[2, P]
        else
          nnew := A[1, P];
        Prev := P;
        P := nnew;
        Side := 3-Side;
        KK := 3-KK;
        Inc(K[KK]);
      end
      else
      begin
        Prev := P;
        P := A[3-Side, P];
        Inc(K[KK]);
      end;
    end;

    if K[1] > K[2] then
      KSum := KSum+K[2]
    else
      KSum := KSum+K[1];
  end;
  Write(KSum);
end.

Поза форумом

 

#84 2005-11-19 19:00:23

Sharp
Олімпієць
Зареєстрований: 2005-10-17
Повідомлень: 34

Re: У кого какое решение?

48.

Код:

#include <iostream.h>

#define MIN(a,b) ((a)>(b))?(b):(a)

struct card{
    int num[2];
    bool setted;
};

struct entry{
    int c[2];
};

card *a;
entry b[65536];
int n;


int solve(){
    int i, k, t, res = 0, r, cn;
    while(true){
        for(i=0; i<n; i++){
            if(!a[i].setted) break;
        }
        if(i == n) break;
        k = a[i].num[0];
        r = 0; cn = 0;
        while(!a[i].setted){
            cn++;
            if( a[i].num[0] != k ){
                    t = a[i].num[0];
                    a[i].num[0] = a[i].num[1];
                    a[i].num[1] = t;
                    r++;
            }
            a[i].setted = true;
            k = a[i].num[1];
            i = (b[k].c[0] == i)?b[k].c[1]:b[k].c[0];
        }
        res += MIN(r, cn-r);
    }
    return res;
}

int main(){
    int i;
    cin >> n;
    a = new card[n];
    for(i=0; i<n; i++) a[i].setted = false;
    for(i=0; i<65536; i++) b[i].c[0] = -1;
    for(i=0; i<n; i++){
        cin >> a[i].num[0];
        if(b[a[i].num[0]].c[0] == -1){
            b[a[i].num[0]].c[0] = i;
        } else{
            b[a[i].num[0]].c[1] = i;
        }
    }
    for(i=0; i<n; i++){
        cin >> a[i].num[1];
        if(b[a[i].num[1]].c[0] == -1){
            b[a[i].num[1]].c[0] = i;
        } else{
            b[a[i].num[1]].c[1] = i;
        }
    }
    cout << solve();
    delete [] a;
    return 0;
}

Поза форумом

 

#85 2005-11-19 19:08:42

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: У кого какое решение?

Люди!
Тут даже я уже согласился что там 48!
Предлагаю сверятся ответами на других задачах.
Например на Piece или BlamBlam...


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#86 2005-11-20 11:11:46

Fokysnik
Олімпієць
Звідки: Львів
Зареєстрований: 2005-10-05
Повідомлень: 51

Re: У кого какое решение?

Bear - елементарно навіть пояснювати нема що:

Код:

#include<stdio.h>
int main()
{unsigned long m,k;
scanf("%li %li",&m,&k);
if (m==0) {printf("0\n"); return(0);}
unsigned long i,c;
if ((k%2)==0)
   c=0; else c=1;
printf("%li",c*m);
for (i=c+2; i<=k; i=i+2)
    printf(" %li",i*m);
printf("\n");
return(0);}

all software must be free
ICQ: 233-537-226

Поза форумом

 

#87 2005-11-20 11:15:03

Fokysnik
Олімпієць
Звідки: Львів
Зареєстрований: 2005-10-05
Повідомлень: 51

Re: У кого какое решение?

Piece - простенька геометрична задачка - рішити квадратне рівняння.
Малюєм на листочку записуєм рівнння кола і прямої...

Код:

#include<stdio.h>
#include<math.h>
int main()
{int R,x,y,x1,y1,x2,y2;
scanf("%i %i %i %i %i %i %i",&R,&x,&y,&x1,&y1,&x2,&y2);
double k;
if ((y2-y1)==0)
   {int z;
   z=x; x=y; y=z;
   z=x1; x1=y1; y1=z;
   z=x2; x2=y2; y2=z;
   }
k=((double)x2-x1)/(y2-y1);
double a,b,c;
a=k*k+1.0;
b=2.0*(k*(x1-k*y1-x)-y);
c=k*y1*(k*y1+2.0*(x-x1))+x1*(x1-2.0*x)+x*x+y*y-R*R;
double D;
D=b*b-4.0*a*c;
if (D<0) {printf("-1\n"); return(0);}
if (D==0) {printf("0\n"); return(0);}
double yt1,yt2,xt1,xt2;
yt1=(-b+sqrt(D))/(2.0*a);
yt2=(-b-sqrt(D))/(2.0*a);
xt1=(yt1-y1)*k+x2;
xt2=(yt2-y1)*k+x2;
double rez;
rez=(xt2-xt1)*(xt2-xt1)+(yt2-yt1)*(yt2-yt1);
rez=sqrt(rez);
printf("%-30.16E\n",rez);
return(0);}

all software must be free
ICQ: 233-537-226

Поза форумом

 

#88 2005-11-20 11:18:58

Fokysnik
Олімпієць
Звідки: Львів
Зареєстрований: 2005-10-05
Повідомлень: 51

Re: У кого какое решение?

Blamblam - знаходим на який максимальний кут треба повернути карту, щоб вона влізла по вертикалі, на який мінімальний, щоб влізла по горизонталі, і звіряєм ці кути.

Код:

#include<stdio.h>
#include<math.h>
int provirka(int x,int y,int a,int b)
{if ((x*y)>(a*b)) return(0);
int z;
if (b>a) {z=a; a=b; b=z;}
if (y>x) {z=x; x=y; y=z;}
if ((x<=a)&&(y<=b)) return(1);
float d,fi,lo,hi;
d=sqrt(x*x+y*y);
fi=2.0*asin(y/d);
lo=acos(a/d)+fi;
hi=asin(b/d);
if (lo<=hi) return(1); else return(0);}

int main(void)
{int n,i,x,y,a,b;
scanf("%i ",&n);
int rez[11];
for (i=1; i<=n; i++)
    {scanf("%i %i %i %i",&x,&y,&a,&b);
     rez[i]=provirka(x,y,a,b);
    }
for (i=1; i<=n; i++)
    printf("%i",rez[i]);
printf("\n");
return(0);}

Кут fi це кут між діагоналями карти.


all software must be free
ICQ: 233-537-226

Поза форумом

 

#89 2005-11-20 12:06:47

Art[ASoft]
Олімпієць
Звідки: Alexandriya
Зареєстрований: 2005-11-13
Повідомлень: 19
Вебсайт

Re: У кого какое решение?

недобрал балы только из-за того что поставил Extended вместо Real...
здесь:

Код:

(*{$N+,E+}*)
{Type
    Real=Extended;}
Var
    R,x,y,x1,y1,x2,y2,tmp,yp1,yp2,xp1,xp2,k,b:Real;

function Dist(x1,y1,x2,y2:Real):Real;
Begin
    Dist:=Sqrt(Sqr(x2-x1)+Sqr(y2-y1));
End;

Procedure glVertex3f;
Begin
    k:=(y2-y1)/(x2-x1);
    b:=y2-k*x2;
    tmp:=(b*b*k*k-(b*b-R*R)*(1+k*k));
    if tmp < 0 then WriteLn(-1)
    else begin
      tmp:=Sqrt(tmp);
      xp1:=(-b*k+tmp)/(1+sqr(k));
      xp2:=(-b*k-tmp)/(1+sqr(k));
      yp1:=k*xp1+b;
      yp2:=k*xp2+b;
      WriteLn(Dist(xp1,yp1,xp2,yp2));
    end;
End;

Begin
    Read(R,x,y,x1,y1,x2,y2);
    x1:=x1-x;x2:=x2-x;x:=0.0;
    y1:=y1-y;y2:=y2-y;y:=0.0;

    if x1=x2 then begin
      tmp:=Sqr(R)-Sqr(x1);
      if tmp < 0 then WriteLn(-1)
      else if abs(tmp) < 1e-10 then WriteLn(0)
      else WriteLn(sqrt(tmp)*2);
    end
    else if y1=y2 then begin
      tmp:=Sqr(R)-Sqr(y1);
      if tmp < 0 then WriteLn(-1)
      else if abs(tmp) < 1e-10 then WriteLn(0)
      else WriteLn(sqrt(tmp)*2);
    end
    else glVertex3f;
End.

Відредаговано Art[ASoft] (2005-11-20 12:08:12)


Good lamer - dead lamer!
FOS for ever!

Поза форумом

 

#90 2005-11-20 12:09:44

Art[ASoft]
Олімпієць
Звідки: Alexandriya
Зареєстрований: 2005-11-13
Повідомлень: 19
Вебсайт

Re: У кого какое решение?

а в Blamblam такая весчь не катит...

Код:

{ 10.11.05 }
{ PF(R.W.) - the best!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! }
Type
    Real=Extended;
Var
    i,N:Integer;
    tmp,x,y,a,b,sina,cosa:Real;

function Prov:boolean;
Begin
    tmp:=sqr(b*x)-(x*x+y*y)*(b*b-y*y);
    cosa:=(b*x-sqrt(tmp))/(x*x+y*y);
    sina:=sqrt(1-cosa*cosa);
    if trunc(sina*x+cosa*y) < A then Prov:=true
    else Prov:=false;
End;

Begin
    Read(N);
    for i:=1 to N do begin
       Read(X,Y,A,B);
       if x<y then begin tmp:=x; x:=y; y:=tmp end;
       if a<b then begin tmp:=a; a:=b; b:=tmp end;
       if ((X<=A)and(Y<=B))or((X<=B)and(Y<=A))or((x*y < a*b)and Prov) then Write('1')
       else Write('0');
    end;
    WriteLn;
End.

Good lamer - dead lamer!
FOS for ever!

Поза форумом

 

#91 2005-11-20 12:12:04

Art[ASoft]
Олімпієць
Звідки: Alexandriya
Зареєстрований: 2005-11-13
Повідомлень: 19
Вебсайт

Re: У кого какое решение?

Circuit вообче лажа

Код:

Var
    A:Array[1..40000] of Longint;
    N,i,Sum,nc1,nc2,kc1,kc2,nd2:Longint;
Begin
    Read(N);
    for i:=1 to N do Read(A[i]);
    nd2:=N div 2;
    for i:=1 to nd2 do Inc(Sum,A[i]);
    for i:=nd2+1 to N do begin
       if Sum = N div 4 then begin nc1:=i-nd2-1;nc2:=i-nd2;kc1:=i-1;kc2:=i;break end;
       Inc(Sum,A[i]);Dec(Sum,A[i-nd2]);
    end;
    if nc1=0 then WriteLn('1 ',kc1,' ',kc2)
    else WriteLn('2 ',nc1,' ',nc2,' ',kc1,' ',kc2);
End.

20 из 20


Good lamer - dead lamer!
FOS for ever!

Поза форумом

 

#92 2005-11-20 13:07:41

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: У кого какое решение?

Fokysnik написав:

Piece - простенька геометрична задачка - рішити квадратне рівняння.
Малюєм на листочку записуєм рівнння кола і прямої...

Ты в своём решении переносил паралельным переносом круг в начало координат?
Я перенёс,чтобы легче было решать...
Наверное там и был глюк...(3 из 20)
Главное идея была таже...


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#93 2005-11-20 17:06:04

Fokysnik
Олімпієць
Звідки: Львів
Зареєстрований: 2005-10-05
Повідомлень: 51

Re: У кого какое решение?

не нічо я не переносив - так рішав smile
Напевно там в тебе і глюк smile


all software must be free
ICQ: 233-537-226

Поза форумом

 

#94 2005-11-20 17:10:21

Fokysnik
Олімпієць
Звідки: Львів
Зареєстрований: 2005-10-05
Повідомлень: 51

Re: У кого какое решение?

В когось є Newpatience на 20 балів?


all software must be free
ICQ: 233-537-226

Поза форумом

 

#95 2005-11-20 18:01:50

Джулгаков Дмитрий
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 61

Re: У кого какое решение?

Fokysnik написав:

В когось є Newpatience на 20 балів?

У многих - посмотри результаты. Например, у меня.

Алгоритм уже много раз обсуждался:
1. Берем первую карточку, у которой одно из чисел т.н. плозое (т.е. второе это число встречается на той же стороне).
2. Далбше смотрим случаи: переворачиваем карточку или нет.
3. Потом для все "хороших" карточек делаем цепное переворачивание, пока цикл не замкнется.
4. А теперь смотрим меньшее из двух чисел: Если первая карточка была перевернута или если нет.
5. Собираем все это в одну переменную.

Сам алгоритм неоднократно описывался - смотри другие темы. Основной прикол задачи - реализовать линейный алгоритм. Т.е. заводим массив 2х65535, в котором пишем для каждого числа число на другой стороне карточки. В результате сложность о(n). Алгоритм с O(n^2) набирал 10-12 балов. Вот так-то.

Привожу свое решение (FP, нужно около 415К памяти):

Код:

const
  maxN = 65535;
var
  N, KK, KSum, i, j, P, Prev, nnew : longint;
  Side : Byte;
  K : array [1..2] of Integer;
  A : array [1..2, 1..maxN] of Word;
  D : array [1..2, 1..maxN] of Byte;
  First : array [1..10000] of Word;
  t : longint;
begin
  Read(N);
  FillChar(D, SizeOf(D), 0);
  for i := 1 to N do
    Read(First[i]);
  for i := 1 to N do
  begin
    Read(t);
    Inc(D[2, t]);
    Inc(D[1, First[i]]);
    if D[1, First[i]] = 2 then
      A[2, First[i]] := t
    else
      A[1, First[i]] := t;
    if D[2, t] = 2 then
      A[1, t] := First[i]
    else
      A[2, t] := First[i];
  end;

  KSum := 0;
  for i := 1 to N do
  begin
    if D[1, First[i]] <> 2 then
      Continue;
    K[1] := 0;
    K[2] := 0;
    KK := 1;
    P := A[1, first[i]];
    D[1, First[i]] := 3;
    K[1] := 1;
    Side := 2;
    Prev := 0;

    while D[1, P] < 3 do
    begin
      if D[Side, P] = 2 then
      begin
        D[Side, P] := 3;
        if Prev=A[1, P] then
          nnew := A[2, P]
        else
          nnew := A[1, P];
        Prev := P;
        P := nnew;
        Side := 3-Side;
        KK := 3-KK;
        Inc(K[KK]);
      end
      else
      begin
        Prev := P;
        P := A[3-Side, P];
        Inc(K[KK]);
      end;
    end;

    if K[1] > K[2] then
      KSum := KSum+K[2]
    else
      KSum := KSum+K[1];
  end;
  Write(KSum);
end.

Удачи!

Поза форумом

 

#96 2005-11-20 21:07:15

Fokysnik
Олімпієць
Звідки: Львів
Зареєстрований: 2005-10-05
Повідомлень: 51

Re: У кого какое решение?

thanks!
Просто понафлудили... попробуй шось найти smile


all software must be free
ICQ: 233-537-226

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt