ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1513. Lemon Tale

WA#11
Posted by khanh45a3kct 22 Feb 2007 06:11
Give me this test plz
Re: WA#11
Posted by [SPbSU ITMO] MAKAPOB 23 Feb 2007 13:48
It is first test, where result exceeded int:
30 30 - this can be
Re: WA#11
Posted by Bespaly Evgeny 29 Aug 2007 23:15
I have probelm with this test too.
If n=30, k=30, result 1073741824?

Edited by author 29.08.2007 23:15
Re: WA#11
Posted by Shyrik 26 Sep 2007 19:35
YES
BUT YOU MUST WRITE LONG ARITHMETIC (MINUS AND SUM IN MY SOLVE)
I'am wa # 11, too ! what wrong with this code?
Posted by Nguyễn Cảnh Toàn 19 Jan 2010 14:38
Shyrik wrote 26 September 2007 19:35
Uses    Math;
Const   Finp    ='';
Fout    ='';
Maxn    =10001;
Base    =Trunc(1E16);
Type    Bignum  =Record
d:Integer;
A:Array[1..200] of Int64;
End;
Var     fi,fo   :Text;
n,k     :Integer;
A,B,T   :Array[0..maxn] of Bignum;
Res,Z   :Bignum;
Procedure       OpenFile;
begin
Assign(fi,finp); Reset(fi);
Assign(fo,fout); Rewrite(fo);
End;
Procedure       CloseFile;
Begin
Close(fi); Close(fo);
End;
Begin
End;
Function        Tong(x,y:Bignum):Bignum;
Var
i,d:Integer;
Nho:Int64;
Begin
Fillchar(z,sizeof(z),0);
d:=Max(x.d,y.d); Nho:=0;
For i:=1 to d do
Begin
Nho:= Nho + x.a[i] + y.a[i];
z.a[i]:= nho mod Base;
Nho:= Nho div Base;
End;
If Nho > 0 Then
begin
Inc(d); z.a[d]:=Nho;
End;
z.d:=d;
Exit(z);
End;
Function        Hieu(x,y:Bignum):Bignum;
Var
i,d:Integer;
Nho:Int64;
Begin
Fillchar(z,sizeof(z),0);
Nho:=0; d:=Max(x.d,y.d);
For i:=1 to d do
Begin
Nho:= x.a[i] - nho - y.a[i];
If Nho < 0 Then
Begin
z.a[i]:= Nho+10;
Nho:=1;
End
Else
begin
z.a[i]:=Nho;
Nho:=0;
End;
End;
While (z.a[d]=0) and (d=1) do dec(d);
z.d:=d;
Exit(z);
End;
Procedure       Viet(x:Bignum);
Var     i,j,d:Integer;
S:String;
Begin
d:=x.d;
If d=0 Then Exit;
Write(fo,x.a[d]);
For i:=d-1 downto 1 do
Begin
Str(x.a[i],S);
For j:=1 to 16- Length(s) do Write(fo,0);
Write(fo,S);
End;
Writeln(fo);
End;
Procedure       Solve;
Var     i,x:Integer;
Begin
If k=0 Then
begin
Writeln(fo,1);
Exit;
End;
A[1].d:=1; A[1].A[1]:=1;
B[1].d:=1; B[1].A[1]:=1;
T[1]:=A[1];
For i:=2 to n do
Begin
x:=Max(i-k-1,0);
B[i]:=Tong(A[i-1],B[i-1]);
A[i]:=Hieu(T[i-1],T[x]);
If i<=k Then A[i]:=Tong(A[i],A[1]);
T[i]:=Tong(T[i-1],B[i]);
End;
Res:=Tong(A[n],b[n]);
Viet(Res);
End;
Begin
OpenFile;