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

WA13
Posted by Milica 22 Dec 2023 16:39
Can someone tell me what is 13.test case? Also, is the only way to solve this problem using long arithmetic?
Re: WA13
Posted by fxubp 9 Jan 2024 04:47
Да очень круто: https://forum.tatysite.net/showthread.php?t=13334 .
Milica wrote 22 December 2023 16:39
Can someone tell me what is 13.test case? Also, is the only way to solve this problem using long arithmetic?
Re: WA13
Posted by Milica 10 Jan 2024 16:06
I got time exceeded error. Can somebody tell what is test case? Or tell me how can I optimize my code? I even found to solutions using dp.

void lemontale(int n,int k,vector<vector<BigInt>> &mem){
    BigInt big_n = BigInt(n);
    BigInt big_k = BigInt(k);
    BigInt dva_big = BigInt(2ull);
    if (mem[n-1][k] == BigInt()){
        if (n<0)
            return ;
        else if (k==0 && n==1){
            mem[n-1][k] = BigInt(1);

            }
        else if (k==0){
            lemontale(n-1,k_start,mem);
            mem[n-1][k] = mem[n-2][k_start];

            }
        else if (n<=k){
            BigInt rez = dva_big^big_n;

            mem[n-1][k] = rez;
            }
        else{

                lemontale(n-1,k_start,mem);
                lemontale(n-1,k-1,mem);
                mem[n-1][k] = mem[n-2][k-1]+mem[n-2][k_start];
            }
    }

}
void lemontale2(int n,int k,BigInt* mem){
    BigInt dva_big = BigInt(2ull);

    if (mem[n-1]==BigInt()){
        if (n<=k)
            mem[n-1] = dva_big^BigInt(n);
        else
            for(int i=0;i<=k;i++){
                if (n-i-1 != 0){
                    lemontale2(n-i-1,k,mem);
                    mem[n-1]+=mem[n-i-2];
                }
                else{
                    mem[n-1]+=1;
                }
            }
    }

}

Edited by author 10.01.2024 16:08

Edited by author 10.01.2024 16:09

Edited by author 10.01.2024 16:09

Edited by author 10.01.2024 16:09