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 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;
Procedure       Readinp;
Begin
        Readln(fi,n,k);
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;
        Readinp;
        Solve;
        CloseFile;
End.