It's interesting that answer approaches to pi number without decimal point. If you'll increase r, answer becomes more and more precisely. For example: answer for r = 1e5 is 31416325412, but for r = 1e9 (although r < 1e5) is 3141592657589764752, when pi equals to 3.141592653 Anybody knows why it's happens? Edited by author 28.12.2017 02:31 Edited by author 28.12.2017 02:31 Square of cirlce is Pi*r*r. Also it tends to some amount of little squares, because big cirlce is more bigger than one little square. Actually we have then amount of squares = pi*r*r on the big r. If r=10^k then pi*r*r=pi*10^2k=amount of squares Sorry for bad english=) Edited by author 03.04.2018 15:12 Edited by author 03.04.2018 15:12 How to compactly encode this sequence (or delta with ceil(round(x)))? Give me some test. Or give me test 10! Edited by author 14.02.2007 18:59 1. Use __int64 2. Here is some fragment of my code(and the most significant): for(x=0;x<r;x++) k+=ceil(sqrt((double)(r-x)*(r+x))); <----- be careful!! use binary search and the following relation: x^2+y^2=R^2 this staff is nice. that let me deal problem. looks like sqrt can't handle 100000*100000 also (r-x)(r+x) == r*r - x*x, but first can be handled with sqrt but second not finally, thanks at all sorry for bad english I cannot pass test10 and i cannot find any mistakes. Is my algo wrong? my code: program p1490; var r,n:int64; i:longint; x:real; begin readln(r); for i:=r-1 downto 0 do begin x:=sqrt(sqr(r)-sqr(i)); if x-trunc(x)<1e-10 then inc(n,r-trunc(x)) else inc(n,r-trunc(x)-1); end; writeln(4*(r*r-n)); end. I have got AC! I changed "sqr(r)-sqr(i)" into "(r+i)*(r-i)". Then I don't WA#10 any more, but I don't know why. Could anyone tell me? Sorry for my poor English... Overflow of type. Edited by author 30.07.2012 20:16 Edited by author 30.07.2012 20:17 Ignore statement about 1'000'000 square kilometers or you will get WA9 This statement is unnecessary. The size of the room is 1000 km, half of it is 500 km, but max radius is only 100 km. What's wrong with the test 10? #include<stdio.h> int main(){ long unsigned int x,y=0,z=0,q,p,r; scanf("%lu",&r); x=r; q=r*r; do{ p=q-y*y; while( x*x >= p && x >= 0 )x--; z+=(x+1); y++; }while(y<r); z*=4; printf("%lu\n",z); return 0; } Используй long long и/или long double Сабж. Условие не соответствует решению ну вы и казлыыыыыыыыыыыы WTF??? And who'll return my 10 submits and lost time??? And still what's the problem with test case 10, when we assume that the board is infinite? i got WA on test 10 anyway, where is the catch? may be answer more than 2^31 ... Well, I don't think this is the problem, because I used long long, and printed it with %lld. Is there a problem with this here in timus? Edited by author 14.10.2006 19:09 r=100000 r=43653 r=2666 Can you please tell the answer? Answers are: 31416325412 (surely more than 2^31) 5986743704 22339576 respectively Thank you very much. My program gives the right answer only for the 3rd test of these 3 but it passed 9 tests :) long long for here is %I64d , and also for some gcc compilers. Please read the FAQ. (However, it's %lld for some) /!!!!\ Result = REAL!!!!! Используйте для подсчёта тип Real.... Я integer использовал и час думал что же у меня не правильно.... Спасибо человеку, который задал вопрос про результаты при больших рабиусах!!! Can you delete it from statement? Вот и мне так кажется. Когда считаю все клетки пападающие в круг и не учитываю ограничение по площади проходит 9 тест но не хватает времени на 10, иначе проходит Wrong Answer на 9. Что это значит??? I haven't crash on my computer on all tests but have crash floating-point 10... Also my answers r<20000 is right if my brute force is right. sorry for my bad English Do you use int? Maybe you use something sqrt(sqr(int)+sqr(int)), and sqr(10^5)=10^10 makes overflow in int, and you get sqrt from negative number? r is <=100000. I don't understand why WA#4 here is my code(maybe I use uncorrect algo?): #include<iostream> #include<cmath> #include<stdio.h> using namespace std; int main() { unsigned __int64 k=0; long r; cin>>r; if(r==1) { cout<<4<<endl; return 0; } if(r==2) { cout<<16<<endl; return 0; } k=(r-1)*8; k=k+(r-1+r-1)*(r-1+r-1); printf("%I64u\n",k); return 0; } Wrong algo :] For example: r = 5 correct_answer = 88 Your formula: a = 8*(5-1) = 8*4 = 32 b = (r-1+r-1)*(r-1+r-1) = (2r-2)^2 = 8^2 = 64 res = a+b = 32 + 64 = 96 correct_answer != res -> Wrong algo :] Edited by author 12.06.2009 01:14 var n,x,r:integer; y2,y,s:int64; BEGIN s:=0; read (n); r:=n; for x:=0 to n-1 do begin y:=trunc(sqrt(r-x)*sqrt(r+x)); if y*y<>(r-x)*(r+x) then y:=y+1; s:=s+y; end; writeln (s*4); END. r = 99999 result = 31415696920 10 344 6 132 666 1396052 100000 31416325412 99999 31415696920 i dont know why i ahve got WA7 Here is my code(pls help me :D) #include<stdio.h> #include<math.h> long i, j, r; unsigned long nr; int main() { scanf("%ld", &r); for(i = 1; i <= r; i++) for(j = 1; j <= r; j++) if((double)(sqrt(i * i + j * j) - r) >= sqrt(2)) nr++; nr = r * r * 4 - nr * 4; printf("%ld\n", nr); return 0; } Edited by author 25.09.2008 14:42 Help me! Program Contest_B; Var I, R : LongInt; Ans : Int64; Tmp : Extended; Begin ReadLn(R); If R = 1 Then Ans := 4 Else Begin Ans := 0; For I := R - 1 Downto 0 Do Begin Tmp := Sqrt(Sqr(R) - Sqr(I)); If Tmp - Trunc(Tmp) <= 1E-9 Then Inc(Ans, Trunc(Tmp)) Else Inc(Ans, Trunc(Tmp) + 1); End; Ans := Ans * 4; End; WriteLn(Ans); End. >Tmp := Sqrt(Sqr(R) - Sqr(I)); Overflow of longint type for r>32768. And according to the statement r<=100000. Дело не в этом longint ограничен 2^31-1>2000000000 а вот inc не работает с типом int64 Why i get WA on test 5? This is my solution: var r,sum,n:extended; begin readln(input,r); sum:=4*sqr(r); n:=int((sqrt(2)-1)*r/sqrt(2)); write(output,(sum-2*n*(n+1)):0:0); end. Edited by author 24.05.2007 21:21 [sorry man] Edited by author 04.11.2007 00:27 Edited by author 04.11.2007 00:27 Buy Iphone! You are TEAPOT!!!!!!!!!!!!!!!!!!!!!! I pass all tests that were mentioned in this thread but I get WA 5, can someone who has fixed such bug tell me what's special in this test ? Btw, just to add I use bruteforce in order to precalc, but I had mistaken the data type and used long instead of unsigned long long , so I've already fixed this bug :) Edited by author 31.10.2006 17:37 Если площадь квадрата ограничена 1000000, то максимальная площадь поражения и будет 1000000, сторона зала - не более 1000 метров, круг обрезается по четырём сторонам, если радиус превышает 500. Полностью согласен! Вообще, мне непонятно, как можно придумать такое глючное условие. При чем здесь вообще 1000000 клеток? Когда проходит решение вообще это никак не учитывается. Из-за этой задачи наша команда(3DURAKA) завалила весь контест и очень расстроилась:) Нехорошо! Могу вас успокоить, наша команда была на 6 позиций ниже вашей по окочании контеста :). Я только надеюсь, что на XI чемпионате Урала по программированию не будет таких лажовых условий. Ошибка была допущена только в Интернет-версии. На очном соревновании все прошло без единой ошибки. Edited by author 16.10.2006 20:12 В условии написано площадь зала 1000000 КИЛОМЕТРОВ => Ширина и высота =1000 КИЛОМЕТРОВ Растояние до стенки =500 КИЛОМЕТРОВ = 500000 МЕТРОВ 500000>100000 Круг не будет обрезаться. Я всё правильно понял? Во время соревнования в условии было по ошибке написано "1000000 МЕТРОВ". |
|