Solution UVA: 10943 - How do you add?

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10943 - How do you add?	Accepted	Python	0.160	0.000	4199	35 secs ago

Suggest:

- This problem similar with problem 10721 - Bar Codes

We have fomular f(n, k) = f(n-i, k-1) | i = 0 -> n

- Example: 

f(2,2) = f(2,1) + f(1, 1) + f(0, 1) 

f(0, 1) = 0

f(1, 1) = f(1, 0) + f(0, 0) = 0 + 1 = 1

f(2, 1) = f(2, 0) + f(1, 0) + f(0, 0) = 0 + 1 + 1 = 2

=> f(2, 2) = 0 + 1 + 2 = 3 

from functools import cache

@cache

def f(n, k, m):

    if n < 0 or k < 0:

        return 0

    if n == 0 and k == 0:

        return 1

   

    r = 0

    for i in range(0, n+1):

        r = (r + f(n-i, k-1, m) % m) % m

    return r

while True:

    n, k = map(int, input().split())

    if n==0 and k==0:

        break

    print(f(n, k, 1000000))

Solution UVA: 10819 - Trouble of 13-Dots

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10819 - Trouble of 13-Dots	Accepted	C++11	0.040	0.000	415	1 mins ago

Suggest:

- DP knapsack range m+200

- Get result with 3 case:

+ m <= 1800

+ 1801 <= m <= 2000

+ m >= 2001

Code implenment by suggest:

#include<bits/stdc++.h>

using namespace std;

int n, m;

int a[1000111];

int b[1000111];

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    while(cin >> m >> n){

        for(int i=1; i<=n; i++) cin >> a[i] >> b[i];

       

        vector<int> f(m+201, 0);

           

        for(int i=1; i<=n; i++)

            for(int j=m+200; j>=a[i]; j--)

                if (f[j - a[i]] > 0 || j == a[i])

                        f[j] = max(f[j], f[j - a[i]] + b[i]);

       

        int res = 0;

        for(int i=0; i<=m; i++)

            res = max(res, f[i]);

   

        if (1801 <= m <= 2000){

            for(int i=2001; i<=m+200; i++)

                res = max(res, f[i]);

        }

           

        if (m >= 2001){

            for(int i=0; i<=m+200; i++)

                res = max(res, f[i]);

        }

                           

        cout<<res<<"\n";

    }

}