10430 - Dear GOD

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

10430 - Dear GOD

Post by 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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse »

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

RuiFerreira
New poster
Posts: 23
Joined: Mon Dec 16, 2002 8:01 pm
Location: Portugal
Contact:

Help!

Post by 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!!
Please visit my webpage!! I've got a lot of UVA statistics scripts
http://www.fe.up.pt/~ei01081/scripts/

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse »

Yes, BigInt is needed.

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

10430 WA. Big INTS

Post by Farid Ahmadov »

Hello.

I get WA. :cry:
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.
_____________
NO sigNature

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov »

Help. Give some I/O or other.
_____________
NO sigNature

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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 :wink:

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

10430

Post by 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
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by 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
New poster
Posts: 5
Joined: Tue Jun 14, 2005 7:12 pm

Post by 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
New poster
Posts: 5
Joined: Tue Jun 14, 2005 7:12 pm

Post by 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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 10430 - Dear GOD, Pardon Me

Post by 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!

Post Reply

Return to “Volume 104 (10400-10499)”