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

Angry Coder · 2005-11-19 17:22:54

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

Angry Coder · 2005-11-19 17:29:10

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.

jack_spektor · 2005-11-19 17:30:14

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

respect · 2005-11-19 17:30:20

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

Я знаю...

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

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

Angry Coder · 2005-11-19 17:31:58

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

jack_spektor · 2005-11-19 17:37:45

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.

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

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

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

Andy · 2005-11-19 17:42:27

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

Джулгаков Дмитрий · 2005-11-19 18:42:38

Ответ действительно 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.

Sharp · 2005-11-19 19:00:23

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;
}

jack_spektor · 2005-11-19 19:08:42

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

Fokysnik · 2005-11-20 11:11:46

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);}

Fokysnik · 2005-11-20 11:15:03

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);}

Fokysnik · 2005-11-20 11:18:58

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 це кут між діагоналями карти.

Art[ASoft] · 2005-11-20 12:06:47

недобрал балы только из-за того что поставил 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)

Art[ASoft] · 2005-11-20 12:09:44

а в 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.

Art[ASoft] · 2005-11-20 12:12:04

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

jack_spektor · 2005-11-20 13:07:41

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

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

Fokysnik · 2005-11-20 17:06:04

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

Fokysnik · 2005-11-20 17:10:21

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

Джулгаков Дмитрий · 2005-11-20 18:01:50

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.

Удачи!

Fokysnik · 2005-11-20 21:07:15

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Angry Coder написав:

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

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

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

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

Код:

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

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

Код:

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

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

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

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

Код:

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

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

Код:

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

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

Код:

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

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

Код:

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

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

Код:

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

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

Код:

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

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

Fokysnik написав:

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

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

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

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

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

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

Fokysnik написав:

Код:

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

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

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