Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Give me your answer for this tests. And help me. | Zubyk Taras(Khmelnitsky) | 1153. Суперкомпьютер | 24 янв 2018 22:45 | 4 |
I have WA#1, but my program is correct. Give me some tests And answer for this tests: Input 1 : 120 My answer : 15 Input 2 : 1081 My answer : 46 Input 3 : 1073845 My answer : 1465 Input 4 : 500500 My answer : 1000 Input 5 : 11325 My answer : 150 Input 6 : 17391 My answer : 186 Input 7 : 122750946 My answer : 15668 Input 8 : 906531 My answer : 1346 Input 9 : 154290 My answer : 555 Input 10 : 7620753696 My answer : 123456 Thanks Advanced !!!! check if any char is a digit My AC program gives that answers for your tests 120: 15 1081: 46 1073845: 1465 500500: 1000 11325: 150 17391: 186 122750946: 15668 906531: 1346 154290: 555 7620753696: 123456 Edited by author 24.01.2018 22:46 |
Python big numbers | TwoEightNine Goes #STAG [146110 SSAU] | 1153. Суперкомпьютер | 5 июн 2016 19:43 | 5 |
print(int((((8*int(input())+1)**.5)-1)/2)) why the fuck doesnt it work???? i got wa6, who can help me with tests? Do you know how floating-point numbers work? Hint: use binary search Edited by author 24.10.2014 14:27 10^600 gives "OverflowError: int too large to convert to float" :) You can use Python library "decimal" |
be carefull ... | arrammis | 1153. Суперкомпьютер | 9 июл 2015 18:13 | 1 |
If you use newton's method to find a square root make sure that your division algorithm for 2 big integers is fast enough to handle quickly a lot of divisions that requires newtons method, otherwise you will get TL ... even with O(n*log(BASE)) time complexity division algorithm your going to get TL. Faster division at O(n) is described in Knuth's The Art of Computer Sience 2 edition, page 298 or 299... So in case if yo get TL with newton's method (which has got actually better time complexity than binary search root finding) just use binary search algo for root with BASE = 10^9 for you big integers, it needs only division by 2, *, +, and - operations needed for big integer. If input contains 600 digits you will only need 600 / 9 array elements to store that number ... and with less divisions you will get AC! take care ... Edited by author 09.07.2015 18:17 |
What about company name? | MOPDOBOPOT | 1153. Суперкомпьютер | 8 авг 2012 10:44 | 2 |
Just push all symbols at one position back.. J -> I C -> B N -> ??? Edited by author 30.07.2012 13:46 |
WA 6 | psiml | 1153. Суперкомпьютер | 4 янв 2012 11:29 | 3 |
WA 6 psiml 11 окт 2011 23:58 Hello, I have a problem with test 6 - can you please give me some similar input and right answer? I read this discuss and I found only something about wrong character problem, so I added testing of it (if there are any not number characters, it ignores them). It didn't help. Thanks and sorry for my English. Edited by author 12.10.2011 18:05 I found a mistake, it was that: if you use java, you must use BigInteger, not just long or double. I hope it will help someone. I'm pretty sure that the test case for 6 is really larger value that will fail if you use Math.sqrt function. Provide your own square root function and you will AC for sure :) |
Why I got WA at test 6??? | Tang RZ | 1153. Суперкомпьютер | 24 ноя 2010 11:02 | 10 |
This is my program: {$N+} var n,m:extended; begin read(m); n:=(sqrt(8*m+1)-1)/2; writeln(n:0:0); end. Could you help me?? Oh God! Do you really think that extended holds 600 digits? You should implement that formula on big numbers... But how to calculate "sqrt"? Could you help me? Thank you! You implement sqrt for big nums? if so, post your source. I'll try to debug it... This is my program: {$N+} var flag:boolean; s:string; a,b:array [1..601] of longint; x,temp,last,lasttemp:extended; l,k:longint; code,i,j:integer; procedure pingfanggen; begin if odd(l) then begin inc(l); a[l]:=0; end; for i:=9 downto 1 do if i*i<=a[l]*10+a[l-1] then begin last:=a[l]*10+a[l-1]-i*i; b[1]:=i; k:=1; break; end; lasttemp:=0; for i:=(l-1) div 2 downto 1 do begin x:=a[i*2]*10+a[i*2-1]+last*100; inc(k); temp:=((b[k-1]*2)+lasttemp)*10; for j:=9 downto 0 do if (temp+j)*j<=x then begin temp:=temp+j; break; end; b[k]:=j; last:=x-b[k]*temp; lasttemp:=temp; end; end; begin readln(s); l:=length(s); for i:=l downto 1 do val(s[l-i+1],a[i],code); for i:=1 to l do a[i]:=a[i]*8; a[1]:=a[1]+1; for i:=1 to l+2 do if a[i]>9 then begin a[i+1]:=a[i+1]+a[i] div 10; a[i]:=a[i] mod 10; if i+1>l then l:=i+1; end; pingfanggen; fillchar(a,sizeof(a),0); for i:=1 to k do a[i]:=b[k-i+1]; l:=k; a[1]:=a[1]-1; for i:=1 to l do if a[i]<0 then begin a[i+1]:=a[i+1]-1; a[i]:=a[i]+10; end; for i:=l downto 1 do begin a[i-1]:=a[i-1]+10*(a[i] mod 2); a[i]:=a[i] div 2; end; flag:=true; for i:=l downto 1 do if (flag=false)or(a[i]<>0) then begin write(a[i]); flag:=false; end; writeln; end. Could you help me? Thank you! I debugged your program and got different answers for almost all tests I've tryied... For example: 1543209876540123456790 -> 55555555555 (correct), yours -> 55531491125 and many more... I really don't have any idea how did your program passed 5 tests... long alternative trunc(sqrt(2 * n)) sorry for my english) |
WA at test #5 (Pascal) | Valentina | 1153. Суперкомпьютер | 19 мар 2010 20:04 | 1 |
Does anybody know what can this test contain? I get WA every time I send my solution, can anybody give me some advice? If you need my code, you can connect me on the ICQ (425805594) |
Test 4 (Special Characters) | Varun Sharma | 1153. Суперкомпьютер | 10 фев 2010 23:15 | 2 |
Hi, To those who are reading the input character by character, test 4 contains some Non Digit characters as well like new line or space at the end of input etc. In my program, I just put a condition to ignore those and then it worked fine. Varun Thank you VERY much! :-) Edited by author 10.02.2010 23:16 |
Binary Search also works! | Fu Dong | 1153. Суперкомпьютер | 21 сен 2009 19:55 | 5 |
I solved this problem with Binary search, but I used 0.812s. Can anyone who solved this problem with Binary search tell me how to make it faster? Yes, and I remember sgu has the same problem only this way work... Use the big basis, for example 1000000000 Java BigInteger BS worked in 0.078ms! Fantastic! |
TLE...At #7 help | S▓i.l.e.n.t | 1153. Суперкомпьютер | 28 фев 2009 23:22 | 1 |
I get TLE at #7 I uses binary search to find sqrt root... but why i TLE?? I haved tried many tests Edited by author 28.02.2009 23:59 |
The answer it's easy, implementation is more or less difficult... | Gheorghe Stefan | 1153. Суперкомпьютер | 26 мар 2008 21:55 | 2 |
the formula is N = (sqrt(8 * M + 1) - 1) / 2 * Брэнд 26 мар 2008 21:55 The answer is easier: N = [sqrt(2*M)] |
What is test#7? | nickolas stoudemire | 1153. Суперкомпьютер | 22 авг 2007 20:52 | 2 |
I got Crash (stack overflow) when my solution met it. type ac=array[1..601]of longint; var a,c,mi,lan,ch:ac; b,d,e,f,g,h,i,j,k,l,m,n:longint;t:array[1..601]of char; function times(a,c:ac;n:longint):ac; var i,j,l:longint; begin fillchar(ch,sizeof(ch),0); for i:=n downto 1 do begin l:=0; for j:=n downto 1 do if i+j-n>0 then begin ch[i+j-n]:=ch[i+j-n]+a[i]*c[j]+l; l:=ch[i+j-n] div 10; ch[i+j-n]:=ch[i+j-n] mod 10; end; end; times:=ch; end; function larger(a,c:ac;n:longint):boolean; var i:longint; begin for i:=1to n do if a[i]>c[i] then exit(true) else if a[i]<c[i] then exit(false); exit(false); end; procedure goal(g:longint); var i,j:longint; begin if g=602 then begin for i:=601-m+1 to 601 do write(c[i]); WRITELN; halt; end; fillchar(lan,sizeof(lan),0); if odd(n) then for j:=2to (g-(601-m))*2 do LAN[j]:=a[j+(601-n)-1] else for j:=1to (g-(601-m))*2 do LAN[j]:=a[j+(601-n)]; for i:=1to 10 do begin if i<10 then begin c[g]:=i; fillchar(mi,sizeof(mi),0); for j:=1to g-(601-m) do mi[j+g-(601-m)]:=c[j+(601-m)]; mi:=times(mi,mi,(g-(601-m))*2); end; if i=10 then begin c[g]:=9; goal(g+1); end else if larger(mi,lan,(g-(601-m))*2) then begin c[g]:=i-1; goal(g+1); end; end; end; begin n:=0; repeat inc(n); read(t[n]); until eoln; for i:=1to n do a[601-n+i]:=ord(T[I])-48; h:=0; for i:=601 downto 1 do begin a[i]:=a[i]*2+h; h:=a[i] div 10; a[i]:=a[i] mod 10; end; for i:=1to 601 do if a[i]<>0 then break; n:=602-i; m:=(n+1)div 2; goal(601-m+1); end. I think it's OK. Does anybody know what's wrong with it? |
my "little" solution | Olympic Bear | 1153. Суперкомпьютер | 30 июл 2007 12:46 | 5 |
[censored] Edited by moderator 09.04.2004 20:53 nothing here ;-) Edited by moderator 09.04.2004 20:56 yixnissac@hotmail.com [censored] Edited by moderator 09.04.2004 20:53 |
i use simple algorhit. it works on my test. Why Wa 6? | Alexander Prudaev | 1153. Суперкомпьютер | 10 окт 2006 14:28 | 1 |
I test it on random big integers and it work, but i get WA#6 What's wrong? I am sure, My program always gives right answer. #include <stdio.h> class ML // my long integer .... ML sqrt(ML x) { ML l(1); ML r=x; ML m; ML E(1); while (l+E!=r) { m=(l+r)/2; if (m*m>x) r=m; else l=m; } return l; } int main() { ML a; a.read(); sqrt(a*2).write(); return 0; } |
My God, why do I allways have TLE#8?!?! Several programs don't pass this test. Any trick? Help. Thanks. (-) | Alexey | 1153. Суперкомпьютер | 14 июл 2006 15:14 | 5 |
What algorithm do you use? It is necessary to take square root It is possible to solve this problem using BS. So it looks like some optimization is required... The first program did like this: If c<0 then l:=n; If c=0 then break; If c>0 then r:=n; Where l,n,r:array...; Now I do like If c<0 then swap(no1,no2); If c=0 then break; If c>0 then swap(no2,no3); Where no1,no2,no3:byte; ANW, TLE#8 in both cases. |
Please, give some tests. My prog passed about 50 my own tests but got TLE#8 or Crash#8. Help me. | Alexey | 1153. Суперкомпьютер | 9 май 2006 20:07 | 1 |
Tests or hints will help me, I hope. My prog passes such tests like 50005000 I don't know, what's the problem. Help me. I use binnary search. Thanks. Edited by author 13.05.2006 17:24 |
I finally worked it problem out.In fact,it's very easy. | Huang Yizheng | 1153. Суперкомпьютер | 28 дек 2005 00:42 | 8 |
how Dilyan 20 июл 2004 00:17 Re: how Gheorghe Stefan 20 июл 2004 00:31 you compute sqrt for big nums :) Re: how The Cheater 20 июл 2004 03:44 Sorry , I didn`t understand your explanation well . If you have time can you please write down much description of your algorithm . Thank you from now . Anyone know, where I can read about sqrt for big nums? Some links? Thanks. Give me your email I will send you the article, but in the Ukrainian language. I use Binary search for Answer. |
Please, Help me... TLE#8 Give me some tests or hints. I used Binary Search | Alexey | 1153. Суперкомпьютер | 29 окт 2005 15:46 | 1 |
I know that binary search works, so I decided to write it. But I have such a problem. Please help me... |
Easy Tests | Tratata (barssimfi@mail.ru) | 1153. Суперкомпьютер | 20 авг 2005 16:03 | 2 |
Easy Tests Tratata (barssimfi@mail.ru) 11 май 2004 00:38 Authors! Your tests very easy! Add the test: S=50005000. I sent not absolutely true decision and got AC! Edited by author 11.05.2004 00:39 Thank you for your easy test. Though it's easy enough, but it help me find the reason why I crash. So thanks again |
I got AC used 0.046s and 421KB... ^_^ | marina_ufa | 1153. Суперкомпьютер | 8 июн 2005 09:49 | 6 |
I got ac 0.031 s 217 КБ but I just used an regular square root algorithm. I got AC in 0.015s and 118 KB. But I used very bad algorithm of square root, so it can be solved faster. |