10430 - Dear GOD

[cytse]

Can anyone tell me why the following code gets TLE instead of WA?
[cpp]
#include <iostream>
using namespace std;

int main() {
for (;;) {
int a,b;
cin >> a >> b;
if (a<0 && b<0) break;
}
return 0;
}
[/cpp]

[Adrian Kuegel]

In fact the input is ending with EOF (there is no negative integer in the input, I just checked it).

[cytse]

Thanks, Adrian. That means the input specification is wrong...

[RuiFerreira]

Hi!

I've noted that X can go until 9^99, so i've got to use big ints?

what about t==1? what shoud be k?

shoud I make shure that gdc( t^n , (1-t^n)/(1-t) ) == 1?

please help me!!

[cytse]

Yes, BigInt is needed.

[Farid Ahmadov]

Hello.

I get WA.
I think my program is correct. I use Big Ints. I have tested it on many test cases and I always got right answers.
Please give me some hints if there is any trick here. I didn't find anything here.

[pascal]program Dear_GOD_Pardom_Me;

type
Int = record
l: Integer;
n: array[1..110] of Byte;
end;

var
T,N,i: Integer;
X,K,A,B: Int;

procedure mult(A: Int; k: Integer; var B: Int);
var
p,i: Integer;
begin
p:=0;
for i:=1 to A.l do
begin
B.n:=(A.n*k+p) mod 10;
p:=(A.n*k+p) div 10;
end;
B.l:=A.l;
while p>0 do
begin
inc(B.l); B.n[B.l]:=p mod 10;
p:=p div 10;
end;
end;

procedure add(A,B: Int; var C: Int);
var
l,i,p: Integer;
begin
if A.l>B.l then l:=A.l else l:=B.l;
p:=0;
for i:=1 to l do
begin
C.n:=(A.n+B.n+p) mod 10;
p:=(A.n+B.n+p) div 10;
end;
C.l:=l;
if p>0 then
begin
inc(C.l); C.n[C.l]:=p;
end;
end;

begin
{ assign(input,'10430.in'); reset(input);
assign(output,'10430.out'); rewrite(output); }
writeln('Dear GOD, Pardon Me');
fillchar(A,sizeof(A),0);
A.l:=1; A.n[1]:=1;
while not eof do
begin
readln(T,N);
X:=A; K:=A;
for i:=1 to N-1 do
begin
mult(K,T,B); K:=B;
add(X,K,B); X:=B;
end;
mult(K,T,B); K:=B;
write('X = ');
for i:=X.l downto 1 do write(X.n);
writeln;
write('K = ');
for i:=K.l downto 1 do write(K.n);
writeln;
while (eoln)and(not eof) do readln;
if not eof then writeln;
end;
{ close(input); close(output); }
end.[/pascal]

If you look here then you know something about this problem or you have got AC. Then please help. Give some inputs or anything else.

Thank you.

[Farid Ahmadov]

Help. Give some I/O or other.

[little joey]

Your answer for '1 99' is wrong (and for '1 98', '1 97', etc.).
Read the problem description, and you'll know why.
Tip: always check the borderline cases and make sure your answers make sense

[htl]

Is there any critical test case? And are both of T and N positive integers?
I still can find out what's wrong.

[htl]

How about the in/output below?

in:
1 99
2 99
3 99
4 99
5 99
6 99
7 99
8 99
9 99

out:
Dear GOD, Pardon Me
X = 99
K = 1

X = 633825300114114700748351602687
K = 633825300114114700748351602688

X = 85896253455335221839410188294270212117017920333
K = 171792506910670443678820376588540424234035840667

X = 133911503688249189628496841028430216876850249481899402941781
K = 401734511064747568885490523085290650630550748445698208825344

X = 394430452610505902705864282641393114836603217554511502385139465332031
K = 1577721810442023610823457130565572459346412870218046009540557861328125

X = 21777287450002363536556342238601927351238123682431829051435732212316571382579
K = 108886437250011817682781711193009636756190618412159145257178661061582856912896

X = 77011345467256142651063042121433733591838171402491080974616555509325987134212572857
K = 462068072803536855906378252728602401551029028414946485847699333055955922805275437143

X = 6375642434544394397650815864453181447347649886891718761359650881328237495773869753274953
K = 4629497041810760783555711051172270131433549208242031329517556169297662470417088272924672

X = 3178831594018594185028274717039294909064630479110757985579709617929184752541588676375611
K = 5430652752148753480226197736314359272517043832886063884637676943433478020332709411004889

[zac.friggstad]

This might be old-hat since your post was some time ago but it appears that you are not allocating enough space to store all of the digits for the larger cases. For example, my answer for your last test case is:

X = 3689083178831594018594185028274717039294909064630479110757985579709617929184752541588676375611

K = 29512665430652752148753480226197736314359272517043832886063884637676943433478020332709411004889

[zac.friggstad]

In regards to the gcd question, reducing via the gcd is useless. Since t^n and t^n - 1 are relatively prime then t^n and (t^n - 1) / (t - 1) must be as well.

[Robert Gerbicz]

What is the output for:

Code: Select all

1 1
1 2
1 3
1 4
1 10
1 98
1 99

Thanks in advance!