Общий форум| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Crash (access violation) 54. Something strange. | Programmer | 1392. Тяга к звёздам | 23 янв 2010 02:28 | 1 | I can`t find place where it can be crash. | | Hint: if you have WA#13 or WA#14 | bsu.mmf.team | 1666. Про Васю Феррари | 22 янв 2010 20:55 | 1 | If you solve this problem with a help of finding roots of the initial polynom, use long long or __int64 type in this function! This fact costed me about 5 submissions...
This is the part of my code:
long long PolynomValue (vector<int>PolynomCoeffs, int x0)
{
long long value;
...
return value;
}
int FindRoot (vector<int> PolynomCoeffs)
{
...
if (!PolynomValue(PolynomCoeffs,a)) return a;
...
}
If I changed long long to int I would not find a root in several cases.
To understand me more clearly try these tests:
-20000 19998 20000 -19999
(x-1)(x-1)(x+1)(x-19999)
-19998 -20000 20000 -19999
(x-19999)(x3+x2-x+1)
-19999 -19999 -19999 -20000
(x+1)(x-20000)(x2+1)
I guess 13th and 14th tests are something like these ones.
Good luck!
Edited by author 22.01.2010 21:07 | | WA#4 | [SSAU_#617]snipious_#1 aka Pimenov Sergey Nikolaevich | 1095. Никифор 3 | 22 янв 2010 11:07 | 4 | WA#4 [SSAU_#617]snipious_#1 aka Pimenov Sergey Nikolaevich 9 янв 2007 15:47 Please, give me some difficult tests...
Send them please on snipious@mail.ru!!! Re: WA#4 [SSAU_#617]snipious_#1 aka Pimenov Sergey Nikolaevich 11 янв 2007 14:12 Can anyone give some tests??? I have found a mistake in the decision!!!
The test was from a series:
1
10234 a very useful test!
i may make the mistake. | | Need optimization | bsu.mmf.team | 1734. База эндшпилей | 22 янв 2010 01:41 | 6 | Can anybody tell me how to calucate bynomial coefficients with a help of the fastest method? What about C(n,k) = n!/k!*(n-k)! ,where '!' denotes factorial. fastest method С[n][k]=C[n-1][k]+C[n-1][k-1] also:
C(n,k)=(C(n,k-1)*(n-k+1)*Inv(k,p))%p because 100000007 is
prime
PS. And this method helped to Ac.
Edited by author 03.11.2009 15:23 Oh!
Thanks! It's cool formula :)
Edited by author 29.06.2011 22:31 | | Accepted SHORT | brainail | 1084. Пусти козла в огород | 21 янв 2010 17:59 | 1 | uses math;
var len,r:extended;
begin
read(len,r);
if(r<=len/2)then writeln((pi*r*r):0:3) else
if(sqrt(2)*len/2<=r)then writeln((len*len):0:3) else
writeln((pi*r*r-4*arccos(len/r/2)*r*r+2*len*sqrt(r*r-len*len/4)):0:3);
end. | | Some tests | Oracle[Lviv NU] | 1605. Дьявольская последовательность | 21 янв 2010 08:57 | 2 | that is what my AC prog gives on some tests:
n=7, res=1
n=7777, res=2340
n=77777, res=23412
n=99997, res=30101
n=99998, res=30102
n=52251, res=15728
n=55555, res=16723
n=100000, res=30102 6 1
66 19
666 200
6666 2006
66666 20068
666666 200686
6666666 2006866
66666666 20068666
666666666 200686663
Edited by author 16.02.2010 08:43 | | WA 1 | rodge(Vologda ML) | 1642. Одномерный лабиринт | 20 янв 2010 22:13 | 6 | WA 1 rodge(Vologda ML) 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? Re: WA 1 Oleg Strekalovsky aka OSt [Vologda SPU] 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 Re: WA 1 rodge(Vologda ML) 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 Re: WA 1 rodge(Vologda ML) 8 ноя 2009 14:05 all tests is right may be I wrong in output? can somebody help me and sorry for my bad english Re: WA 1 unlucky [Vologda SPU] 8 ноя 2009 15:54 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:55Re: WA 1 rodge(Vologda ML) 20 янв 2010 22:13 Thank you )))
I am thinking and rewriting me programm for 10 minutes now )))
and got AC it's amazing ))) | | WA 13. Any tests? | Programmer | 1489. Точки на параллелепипеде | 20 янв 2010 13:30 | 2 | Try this test:
4 3 2
8 5
2 3
Right answer is:
4.0000000 | | If you have WA#3 | Smilodon_am | 1489. Точки на параллелепипеде | 20 янв 2010 11:32 | 1 | I have had WA#3, but when I have tried following test, I pass Test#3, but have WA#13:
4 3 2
2.0 0.0
2.0 10.0
Right answer:
0.0000000
Now I have AC.
Edited by author 20.01.2010 13:32 | | My Accept Short Solution :D | brainail | 1015. Найдите различия! | 19 янв 2010 01:07 | 1 | #include<iostream>
#include<vector>
using namespace std;
#define forr(i,x,y) for(int i=(int)(x); i<=(int)(y); i++)
int p[24][6]={
{1,2,3,4,5,6},{1,2,6,5,3,4},{1,2,4,3,6,5},{1,2,5,6,4,3},{2,1,4,3,5,6},{2,1,6,5,4,3},{2,1,3,4,6,5},{2,1,5,6,3,4},
{3,4,2,1,5,6},{3,4,6,5,2,1},{3,4,1,2,6,5},{3,4,5,6,1,2},{4,3,6,5,1,2},{4,3,2,1,6,5},{4,3,5,6,2,1},{4,3,1,2,5,6},
{5,6,3,4,2,1},{5,6,1,2,3,4},{5,6,4,3,1,2},{5,6,2,1,4,3},{6,5,3,4,1,2},{6,5,2,1,3,4},{6,5,4,3,2,1},{6,5,1,2,4,3}};
int n,a[7],b[7],id[7][7][7][7][7][7],m=0,x=0;
vector< vector<int> > y(100100);
int main() {
scanf("%d",&n);
forr(i,1,n) {
scanf("%d %d %d %d %d %d",&a[3],&a[4],&a[2],&a[5],&a[1],&a[6]);
forr(q,0,23) if(x=id[a[p[q][0]]][a[p[q][1]]][a[p[q][2]]][a[p[q][3]]][a[p[q][4]]][a[p[q][5]]])break;
if(!x) { y[++m].push_back(i); id[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]]=m; } else y[x].push_back(i);
}
printf("%d\n",m);
forr(i,1,m) { forr(j,0,y[i].size()-1) printf("%d ",y[i][j]); printf("\n"); }
}
| | ADMINS!!!!! Are you sleep??? | Ras Misha [t4ce] | 1005. Куча камней | 18 янв 2010 05:06 | 3 | up Ras Misha [t4ce] 14 янв 2010 23:20 Re: up Ras Misha [t4ce] 18 янв 2010 05:06 | | Clarification | Andre Linhares | 1660. Остров Невезения | 17 янв 2010 21:47 | 3 | "When no more circles can be inscribed, the distance between the first and the last inscribed circles is measured."
What is the definition of the distance between two circles? As usual, min (dist(P1, P2)), where point P1 lies on the 1st circle, and point P2 lies on the 2nd circle i.e. the difference of the distance between centers of these circles and the sum of their radiuses.
D=sqrt((c1.x-c2.x)^2+(c1.y-c2.y)^2) - r1 - r2. | | podvodnii kamni | Light | 1551. Турнир по сумо | 17 янв 2010 18:21 | 6 | kakoi v etoi zada4i moget bit` podvoh?
u menya na 12 teste valitsa A imena rizni concurentiv? why can't you talk in english? I think it's not so hard
others can take it as an OFFENCE
Edited by author 29.10.2007 22:49 I can help with Russian ^ ^ 3
a a
b c
c b
d b
e a
f c
g b
h c
Right answer: 1 | | Problem is very easy, but I got wa#12... Please give me some useful tests | Crash_access_violation | 1551. Турнир по сумо | 17 янв 2010 18:21 | 4 | thanks...
sorry for my bad english
Names of all participants are various? or not? I assumed them various. Although, the names are not important to solve the problem; just the maximum of the number of participants from any place matters. 3
a a
b c
c b
d b
e a
f c
g b
h c
Right answer: 1 | | contacting authors | mirzauzairbaig | | 17 янв 2010 10:25 | 4 | helo!
this is just a suggestion, i believe there should be an option (if they wish) for authors to display their email address to be contacted !
as it will enable and allow for more communications between authors.
my address is, baiguzair@gmail[dot]com Does nobody want to stay in touch!!?? Does nobody want to stay in touch!!?? I think they may also set up a mail function inside timus...
But if you want to show your email, you can set it as your motto. | | my program is correct, please tell me my error WA #4 | mirzauzairbaig | 1020. Ниточка | 17 янв 2010 10:17 | 6 | #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;} 3 1.2
12.24 13.34
0.00 24.75
-33.36 70.12
153.41
your program is too complicated to read 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? 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 Well, I suppose perhaps float is not accurate enough...
Since triangle functions in math.h are all float.
Congratulations anyway. | | Suggestion | VladimirZagorodskih | | 16 янв 2010 17:56 | 2 | Why don't add a button "Random Problem" ?? Random problem from those which have not already solved.
Edited by author 16.01.2010 17:56 | | WTF? | Aleksey [TeXHuK] | 1424. Маршрутка | 16 янв 2010 17:46 | 8 | WTF? Aleksey [TeXHuK] 11 ноя 2006 15:12 Please, show 9 test.
Who make this problem, public your solution, please. Re: WTF? Samsonov Alex [USU] 11 ноя 2006 15:57 Probably you should try to find a bug in your code. It doesn't look like this problem have any troubles with test data. Re: WTF? Aleksey [TeXHuK] 11 ноя 2006 16:17 Without test very hardly found bugz in code :-( Re: WTF? Samsonov Alex [USU] 11 ноя 2006 19:42 But actually you have to obtain this useful skill. I have WA9 too.
try test:
3 1 2 1
1 3
1 2 Re: WTF? AlexF [USTU Frogs] 18 сен 2007 10:16 I don't think that 9 test has smth special) I had a very stupid bug in my code and so had WA#9)
Failed test was
10 1 7 1
1 8
2 3
3 4
4 5
5 6
6 7
7 8
IMHO Cool problem) Re: WTF? Vladimir Mihajlovski 27 май 2008 00:41 I also fall on test 9, but both of these tests work fine. What was the bug you corrected?
Edited by author 27.05.2008 02:28 WA9 Programmer 16 янв 2010 17:46 | | Hint for DFS and Crash #3 !!!!! | tiancaihb | 1471. Расстояние в дереве | 16 янв 2010 12:50 | 3 | I used Tarjan Algo, based on DFS and union-find sets, but got Crash AV #3. I made a extreme data myself, like a chain from Node #0. And it really crashed with DEV-C++. I tried to enlarge the size of stack, but it seemed workless. After debugging for so long, I still can't explain why it got stuck at Node #49xxx (The program works on every "smaller data"). Do I have to make a "stack" myself? No, I came up with an idea--randomize. And with that I ACed with no difficulty.
Here is the thing, maybe you picked Node #0 as the root of the tree, but why not change to a random one? I think data #3 is such a data that will make the first algo crash.
Sorry for my poor English, btw. I had the same problems with this problem but increasing size of the stack helped me. Post here your e-mail and i'll send you my code. I think you understand my code because i made it the same way with you(dfs+disjoint set) tiancaihbATsinaDOTcom
No, forget about it. I must have writen a wrong code
The right one is #pragma comment(linker, "/STACK:16777216").
Well, that's embarrassing because you won't get CE even if it's wrong.
I wrote before: #pragma comment(linker, "/STACK:64777216")
Edited by author 16.01.2010 12:54
Edited by author 16.01.2010 12:55 | | WA#25: can you give me some tests? | fail | 1671. Паутина Ананси | 15 янв 2010 22:13 | 2 | I got AC when i handle multigraphs (multiple edges between pair of vertices are possible) Look my post (he located above your post in that node{ NOT MAIN NODE BUT NODE of the problem 1671}) there you can find test with multi-edges.
Edited by author 15.01.2010 22:18
Edited by author 16.01.2010 13:03 |
|
|
