ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1153. Supercomputer

Tang RZ Why I got WA at test 6??? [9] // Problem 1153. Supercomputer 18 Aug 2004 11:03
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??
Gheorghe Stefan Re: Why I got WA at test 6??? [8] // Problem 1153. Supercomputer 18 Aug 2004 21:26
Oh God!
Do you really think that extended holds 600 digits?
You should implement that formula on big numbers...
Tang RZ Re: Why I got WA at test 6??? [7] // Problem 1153. Supercomputer 19 Aug 2004 11:53
But how to calculate "sqrt"? Could you help me? Thank you!
Danica Porobic Re: Why I got WA at test 6??? [6] // Problem 1153. Supercomputer 19 Aug 2004 13:05
Hi!

Here is a link to explanation of one very interesting and simple sqrt algorithm http://www.homeschoolmath.net/other_topics/square-root-algorithm-example.php
I got AC using it, so if you have any questions about the implementation email me: dporobic@eunet.yu
Tang RZ Re: Why I got WA at test 6??? [5] // Problem 1153. Supercomputer 20 Aug 2004 12:36
Still WA!!! Why?
Gheorghe Stefan Re: Why I got WA at test 6??? [4] // Problem 1153. Supercomputer 20 Aug 2004 12:50
You implement sqrt for big nums? if so, post your source. I'll      try to debug it...
Tang RZ Re: Why I got WA at test 6??? [3] // Problem 1153. Supercomputer 20 Aug 2004 15:36
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!
Gheorghe Stefan Re: Why I got WA at test 6??? [2] // Problem 1153. Supercomputer 21 Aug 2004 16:26
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...
Edric Mao Re: Why I got WA at test 6??? [1] // Problem 1153. Supercomputer 22 Sep 2010 14:05
thanks
Yuri.Pechatnov Re: Why I got WA at test 6??? // Problem 1153. Supercomputer 24 Nov 2010 11:02
long alternative trunc(sqrt(2 * n))
sorry for my english)