| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Страница 2 |
| 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 |
| 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" |
| 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 :) |
| 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 |
| 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 |
| 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? |
| 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. |
| 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 |
| 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 |
| 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... |
| 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! |
| Страница 1 |
| 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) |
| 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. |
| 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 |
| 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)] |
| 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 got AC in first try in 0.06... to heller and other | Locomotive | 1153. Суперкомпьютер | 11 май 2004 00:44 | 4 |
Use a sqrt algorithm as it is I use the same algorithm but i get wrong aswer and i cant find the
darn problem.
[source was deleted]
Edited by moderator 11.05.2004 03:03 Ok
I Cant understand your C code...
mail me at aidin_n7@hotmail.com if u want i sent u my pascal code...
With best wishes
Aidin_n7 It is Right solution!!! It has AC |
