Общий форум @ Timus Online Judge

[SSAU_#617]snipious_#1 aka Pimenov Sergey Nikolaevich WA#4 [3] // Задача 1095. Никифор 3 9 янв 2007 15:47

bsu.mmf.team Need optimization [5] // Задача 1734. База эндшпилей 2 ноя 2009 22:44

brainail Accepted SHORT // Задача 1084. Пусти козла в огород 21 янв 2010 17:59

Oracle[Lviv NU] Some tests [1] // Задача 1605. Дьявольская последовательность 3 ноя 2008 22:25

rodge(Vologda ML) WA 1 [5] // Задача 1642. Одномерный лабиринт 18 окт 2009 17:11

var
a : array[-1000..0] of integer;
b : array[0..1000] of integer;
n, i, j, k, l, m, u, x : integer;
c : array[1..100] of integer;
begin
read(n, x);
k := 0;
m := 0;
l := 0;
u := 0;
j := 0;
i := 0;
for i := 1 to n do begin
    read(c[i]);
    if c[i] >= 0 then b[c[i]] := 1 else a[c[i]] := 1;
end;
if b[0] = 1 then u := 1;
if x = 0 then begin
    k := 0;
    m := 0;
end;
if x < 0 then begin
    for i := x to -1 do begin
      if a[i] = 1 then begin
        u := 1;
        break;
      end;
    end;
    if i = 0 then begin
      for j := 0 downto x do begin
        inc(m);
      end;
      m := m - 1;
      repeat
        inc(k);
      until b[k] = 1;
      k := 2 * k + m;
      end;
end;
if x > 0 then begin
      for i := 0 to x do begin
        if(b[i]) = 1 then begin
          u := 1;
          break;
        end;
      end;
      if i = x + 1 then begin
        for j := 0 to x do begin
          inc(k);
        end;
        k := k - 1;
        repeat
          inc(m);
          dec(l);
        until a[l] = 1;
        m := 2 * m + k
      end;
    end;
    if u = 1 then writeln('Impossible') else
    writeln(k,' ', m);
    readln;
    readln;
end.
my code it is work for different numbers and tests (my tests( but WA 1) plese, who can help me?

Oleg Strekalovsky aka OSt [Vologda SPU] Re: WA 1 [4] // Задача 1642. Одномерный лабиринт 18 окт 2009 18:14

I solved this problem by emulation.
I have WA 1 too. Problem was with calculation distance. They some times became negative. When i add function abs() for every places, where was calculation distances - i got AC

Edited by author 18.10.2009 18:20

rodge(Vologda ML) Re: WA 1 [3] // Задача 1642. Одномерный лабиринт 8 ноя 2009 13:51

var
a : array[-1000..0] of integer;
b : array[0..1000] of integer;
n, i, j, k, l, m, u, x : integer;
c : array[1..100] of integer;
begin
read(n, x);
k := 0;
m := 0;
l := 0;
u := 0;
j := 0;
i := 0;
for i := 1 to n do begin
    read(c[i]);
    if c[i] > 0 then b[c[i]] := 1 else a[c[i]] := 1;
end;
if x < 0 then begin
    for i := x to -1 do begin
      if a[i] = 1 then begin
        u := 1;
        break;
      end;
    end;
    if i = 0 then begin
      j := 0;
      while (k>x) do begin
        dec(k);
      end;
      k := abs(k);
      while (b[j]<>1) and (abs(j)<1000) do begin
        inc(m);
        inc(j);
      end;
      m := m * 2 + k;
    end;
end;
if x > 0 then begin
    for i := 0 to x do begin
      if(b[i]) = 1 then begin
        u := 1;
        break;
      end;
    end;
    if i = x + 1 then begin
      j := 0;
      while m < x do begin
        inc(m);
      end;
      while (a[j]<>1) and (abs(j)<1000) do begin
        inc(k);
        dec(j);
      end;
      k := k * 2 + m;
    end;
end;
if u = 1 then writeln('Impossible') else begin
    write(m,' ',k);
end;
readln;readln;
end.
correct my solution but WA1 it's very bad ((( who knows test 1?

Edited by author 08.11.2009 14:04

rodge(Vologda ML) Re: WA 1 // Задача 1642. Одномерный лабиринт 8 ноя 2009 14:05

all tests is right may be I wrong in output? can somebody help me and sorry for my bad english

unlucky [Vologda SPU] Re: WA 1 [1] // Задача 1642. Одномерный лабиринт 8 ноя 2009 15:54

rodge(Vologda ML) писал(a) 8 ноября 2009 13:51

var
a : array[-1000..0] of integer;
b : array[0..1000] of integer;
n, i, j, k, l, m, u, x : integer;
c : array[1..100] of integer;
begin
read(n, x);
k := 0;
m := 0;
l := 0;
u := 0;
j := 0;
i := 0;
for i := 1 to n do begin
    read(c[i]);
    if c[i] > 0 then b[c[i]] := 1 else a[c[i]] := 1;
end;
if x < 0 then begin
    for i := x to -1 do begin
      if a[i] = 1 then begin
        u := 1;
        break;
      end;
    end;
    if i = 0 then begin
      j := 0;
      while (k>x) do begin
        dec(k);
      end;
      k := abs(k);
      while (b[j]<>1) and (abs(j)<1000) do begin
        inc(m);
        inc(j);
      end;
      m := m * 2 + k;
    end;
end;
if x > 0 then begin
    for i := 0 to x do begin
      if(b[i]) = 1 then begin
        u := 1;
        break;
      end;
    end;
    if i = x + 1 then begin
      j := 0;
      while m < x do begin
        inc(m);
      end;
      while (a[j]<>1) and (abs(j)<1000) do begin
        inc(k);
        dec(j);
      end;
      k := k * 2 + m;
    end;
end;
if u = 1 then writeln('Impossible') else begin
    write(m,' ',k);
end;
readln;readln;
end.
correct my solution but WA1 it's very bad ((( who knows test 1?

Edited by author 08.11.2009 14:04

Your code is very crazy :)
1. He get wrong answer for demo test
2.
if x < 0 then begin
    for i := x to -1 do begin (*)
      if a[i] = 1 then begin
        u := 1;
        break;
      end;
    end;
    if i = 0 then begin (**)
How do you think - it is possible to go get TRUE in condition (**) if cycle condition (**) is that?

And the same bug in

    for i := 0 to x do begin (*)
      if(b[i]) = 1 then begin
        u := 1;
        break;
      end;
    end;
    if i = x + 1 then begin (**)

More help only via e-mail.

Edited by author 08.11.2009 15:55

rodge(Vologda ML) Re: WA 1 // Задача 1642. Одномерный лабиринт 20 янв 2010 22:13

Thank you )))
I am thinking and rewriting me programm for 10 minutes now )))
and got AC it's amazing )))

Programmer WA 13. Any tests? [1] // Задача 1489. Точки на параллелепипеде 27 май 2009 03:20

Smilodon_am If you have WA#3 // Задача 1489. Точки на параллелепипеде 20 янв 2010 11:32

brainail My Accept Short Solution :D // Задача 1015. Найдите различия! 19 янв 2010 01:07

Ras Misha [t4ce] ADMINS!!!!! Are you sleep??? [2] // Задача 1005. Куча камней 9 янв 2010 02:37

Andre Linhares Clarification [2] // Задача 1660. Остров Невезения 20 дек 2008 13:04

Light podvodnii kamni [5] // Задача 1551. Турнир по сумо 21 апр 2007 13:47

Crash_access_violation Problem is very easy, but I got wa#12... Please give me some useful tests [3] // Задача 1551. Турнир по сумо 18 июн 2008 16:08

mirzauzairbaig contacting authors [3] 14 янв 2010 13:36

mirzauzairbaig my program is correct, please tell me my error WA #4 [5] // Задача 1020. Ниточка 15 янв 2010 14:43

#include <iostream>
#include <cmath>
using namespace std;
int main(){
double PI=acos(-1.0);
int N; double r(0), perimeter(0);
cin>>N>>r;
double *pointx, *pointy;
pointx = new double[N+1];
pointy = new double[N+1];
for(int a=0; a<N; a++){
cin>>pointx[a]>>pointy[a];
}
pointy[N]= pointy[0];
pointx[N] = pointx[0];
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);
if(N==1){
perimeter=2*PI*r;
cout<<perimeter;

}
else{
if(N==2){
perimeter=2*(pow((pow((pointx[0]-pointx[1]),2)+pow((pointy[0]-pointy[1]),2)),0.5)) + 2*PI*r;
cout<<perimeter;

}
else{
double angle(0);
for(int a=0; a<N; a++){
perimeter += pow((pow((pointx[a]-pointx[a+1]),2)+pow((pointy[a]-pointy[a+1]),2)),0.5);
}

double p1x, p2x, p3x, p1y, p2y, p3y, m1, m2;

p1x=pointx[N-1]; p2x=pointx[0]; p3x=pointx[1];
p1y=pointy[N-1]; p2y=pointy[0]; p3y=pointy[1];
if(p3x==p2x)
m1=tan(PI/2.0);
if(p2x==p1x)
m2=tan(PI/2.0);
if(p2x!=p3x)
m1=(p3y-p2y)/(p3x-p2x);
if(p2x!=p1x)
m2=(p1y-p2y)/(p1x-p2x);
angle = 2*PI - (PI + fabs(atan(m1)-atan(m2)));
for(int a=1; a<N; a++){
p1x=pointx[a-1]; p2x=pointx[a]; p3x=pointx[a+1];
p1y=pointy[a-1]; p2y=pointy[a]; p3y=pointy[a+1];
if(p3x==p2x)
m1=tan(PI/2.0);
if(p2x==p1x)
m2=tan(PI/2.0);
if(p2x!=p3x)
m1=(p3y-p2y)/(p3x-p2x);
if(p2x!=p1x)
m2=(p1y-p2y)/(p1x-p2x);

angle += ((2*PI) - (PI + fabs(atan(m1)-atan(m2))));
}

perimeter += r*angle;
cout<<perimeter;
}}
delete pointx;
delete pointy;
return 0;}

mirzauzairbaig Re: my program is correct, please tell me my error WA #4 [4] // Задача 1020. Ниточка 15 янв 2010 22:35

Please reply !!

tiancaihb Re: my program is correct, please tell me my error WA #4 [3] // Задача 1020. Ниточка 16 янв 2010 12:48

3 1.2
12.24 13.34
0.00 24.75
-33.36 70.12

153.41

your program is too complicated to read

mirzauzairbaig Re: my program is correct, please tell me my error WA #4 [2] // Задача 1020. Ниточка 16 янв 2010 13:51

I will tell you about my program. I am first calculating the distance between each point and summing it (perimeter). Then I am calculating the angle; of rope wound around each nail. I am adding the angles and then finding the total length by; perimeter + radius*angle. As my angle is in radians. Now, my answer is slightly above your answer in this test case; as I can see. But, if I change my angle to be always just 2 * PI * r, then I get it right !!

Now, first I can see the intuition for always setting angle to be 2*PI*r, but I cannot find any proof of why this will be always true. So, I am calculating it always for each nail. ( I think maybe, my calculation algorithm either gives a rounding error; or I am making a mistake)!!

Please do reply, and tell me why?

mirzauzairbaig Re: my program is correct, please tell me my error WA #4 // Задача 1020. Ниточка 17 янв 2010 03:46

Okay, I found my mistake. And the proof;(the reason) is got to do with exterior angles of a polygon sum up to 360 degrees! :)
thank you tianchb

tiancaihb Re: my program is correct, please tell me my error WA #4 // Задача 1020. Ниточка 17 янв 2010 10:17

Well, I suppose perhaps float is not accurate enough...
Since triangle functions in math.h are all float.
Congratulations anyway.

VladimirZagorodskih Suggestion [1] 16 янв 2010 16:15

Aleksey [TeXHuK] WTF? [7] // Задача 1424. Маршрутка 11 ноя 2006 15:12

tiancaihb Hint for DFS and Crash #3 !!!!! [2] // Задача 1471. Расстояние в дереве 13 янв 2010 13:33

fail WA#25: can you give me some tests? [1] // Задача 1671. Паутина Ананси 12 авг 2009 15:02

Khramov Egor(9 class) Why WA#3. I don't know where my mistake. [1] // Задача 1233. Amusing Numbers 7 июн 2005 01:04

RR42 Crash on Test 1; c++; Падение на тесте 1. Что за тест? (РЕШЕНО! g++ vs. icl) [1] // Задача 1001. Обратный корень 31 дек 2009 02:22