UVa - 562 - Dividing coins

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int dp[103][503], N, Mid;
vector <int> Coin;

int evaluate(int I, int C){
    int gain1, gain2;
    if(I == N)return 0;
    if(dp[I][C] != -1)return dp[I][C];
    if(C+Coin[I] <= Mid)gain1 = Coin[I] + evaluate(I+1, C+Coin[I]);
    else gain1 = 0;
    gain2 = evaluate(I+1, C);
    return dp[I][C] = max(gain1, gain2);
}

int main(){
    int T, C;
    cin >> T;
    while(T--){
        cin >> N;
        int Sum = 0;
        for(int i = 1; i <= N; i++)cin >> C, Sum += C, Coin.push_back(C);
        Mid = Sum / 2;
        memset(dp, -1, sizeof(dp));
        int ans = evaluate(0, 0);
        ans *= 2;
        int real = Sum - ans;
        cout << real << endl;
        Coin.clear();
    }
    return 0;
}

UVa - 414 - Machined Surfaces

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

int main(){
    int n;
    string input;
    while(cin >> n){
        if(n == 0)break;
        int cnt[n], mn = 25;
        memset(cnt, 0, sizeof(cnt));
        getchar();
        for(int i = 0; i < n; i++){
            getline(cin, input);
            for(int j = 0; j < 25; j++)if(input[j] == 32)cnt[i]++;
            mn = min(mn, cnt[i]);
        }
        int sum = 0, temp;
        for(int i = 0; i < n; i++)temp = (cnt[i]-mn), sum += temp;
        cout << sum << endl;
    }
    return 0;
}

UVa - 400 - Unix ls

1. #include <iostream>
2. #include <vector>
3. #include <cmath>
4. #include <algorithm>
5. using namespace std;
6.  
7. int main(){
8.     int n, mx, sz;
9.     string file;
10.     vector <string> srt;
11.     while(cin >> n){
12.         mx = 0;
13.         for(int i = 1; i <= n; i++){
14.             cin >> file, srt.push_back(file);
15.             sz = file.size();
16.             if(sz > mx)mx = sz;
17.         }
18.         sort(srt.begin(), srt.end());
19.         int row, col, temp;
20.         col = 62 / (mx+2);
21.         row = ceil(n/(double)col);
22.         for(int i = 1; i <= 60; i++)cout << "-";
23.         cout << endl;
24.         for(int i = 0; i < row; i++){
25.             for(int k = i; k < n; k += row){
26.                 cout << srt[k];
27.                 for(int m = 1; m <= (mx-(srt[k].size()))+2; m++)cout << " ";
28.             }
29.             cout << endl;
30.         }
31.         srt.clear();
32.     }
33.     return 0;
34. }

UVa - 357 - Let Me Count The Ways

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int Coin[] = {1, 5, 10, 25, 50};
long long dp[7][30003];
long long N;

long long makeCoin(long long I, long long H){
    if(I >= 5){
        if(H == 0)return 1;
        else return 0;
    }
    if(dp[I][H] != -1)return dp[I][H];
    long long Way1 = 0, Way2 = 0;
    if(H-Coin[I] >= 0)Way1 = makeCoin(I, H-Coin[I]);
    Way2 = makeCoin(I+1, H);
    return dp[I][H] = Way1+Way2;
}

int main(){
    memset(dp, -1, sizeof(dp));
    while(cin >> N){
        long long ans = makeCoin(0, N);
        if(ans == 1)cout << "There is only 1 way to produce " << N << " cents change." << endl;
        else cout << "There are " << ans << " ways to produce " << N << " cents change." << endl;
    }
    return 0;
}

UVa - 294 - Divisors

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
    int t, l, u, ans, mx, cnt;
    cin >> t;
    while(t--){
        cin >> l >> u;
        mx = -1;
        for(int i = l; i <= u; i++){
            cnt = 0;
            for(int j = 1; j <= sqrt(i); j++){
                if(i%j == 0){
                    cnt++;
                    if(i/j != j)cnt++;
                }
            }
            if(cnt > mx){
                mx = cnt;
                ans = i;
            }
        }
        cout << "Between " << l << " and " << u << ", " << ans << " has a maximum of " << mx << " divisors." << endl;
    }
    return 0;
}

UVa - 336 - A Node Too Far!

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define M 100003
using namespace std;

vector <int> node[M];
int cs = 1, mx, cnt;

void bfs(int src, int TTL, int cnt){
    queue <int> container;
    int visited[M] = {0}, ans = 1, power[M] = {0};
    visited[src] = 1;
    container.push(src);
    while(!container.empty()){
        int u = container.front();
        int sz = node[u].size();
        for(int i = 0; i < sz; i++){
            int v = node[u][i];
            if(!visited[v]){
                visited[v] = 1;
                power[v] = power[u]+1;
                if(power[v] <= TTL)ans++;
                container.push(v);
            }
        }
        container.pop();
    }
    cout << "Case " << cs << ": " << (cnt - ans) << " nodes not reachable from node " << src << " with TTL = " << TTL << "." << endl;
}

int main(){
    int N, E, x, y, src, TTL, m, num[M] = {0};
    while(cin >> N ){
        mx = 0, cnt = 0;
        if(!N)break;
        for(int i = 0; i < N; i++){
            cin >> x >> y,node[x].push_back(y), node[y].push_back(x);
            m = max(x, y);
            mx = max(mx, m);
        }
        for(int i = 0; i < mx+1; i++){
            int sz = node[i].size();
            if(sz > 0)cnt++;
        }
        while(cin >> src >> TTL){
            if(!src && !TTL)break;
            bfs(src, TTL, cnt);
            cs++;
        }
        for(int i = 0; i <= M; i++)node[i].clear();
    }
    return 0;
}

UVa - 146 - ID Codes

1. #include <iostream>
2. #include <cstdio>
3. #include <string>
4. #include <cstring>
5. #include <algorithm>
6. using namespace std;
7.  
8. int main(){
9.     string code;
10.     while(cin >> code){
11.         if(code == "#")break;
12.         if(next_permutation(code.begin(), code.end()))cout << code << endl;
13.         else cout << "No Successor" << endl;
14.     }
15.     return 0;
16. }

UVa - 119 - Greedy Gift Givers

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <map>
using namespace std;

int main(){
    int money, tk, x, n, sum[10], bl = 0;
    string name[10], temp;
    while(cin >> n){
        if(bl == 1)cout << endl;
        for(int i = 0; i < n; i++)cin >> name[i];
        memset(sum, 0, sizeof(sum));
        for(int k = 0; k < n; k++){
            cin >> temp >> money >> x;
            for(int z = 0; z < n; z++)if(x != 0 && (temp == name[z]))sum[z] -= ((money / x) * x);
            if(x != 0)tk = (money / x);
            for(int i = 0; i < x; i++){
                cin >> temp;
                for(int j = 0; j < n; j++)if(temp == name[j])sum[j] += tk;
            }
        }
        for(int i = 0; i < n; i++)cout << name[i] << " " << sum[i] << endl;bl = 1;
    }
    return 0;
}

UVa - 113 - Power of Cryptography

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
    int n, mod, get, root, temp, m;
    vector <int> ans;
    string pran;
    while(cin >> n >> pran){
        get = n*n, mod = 0, m = 0;
        int l = pran.size();
        for(int i = 0; i < l; i++){
            temp = (mod * 10) + (pran[i]-48);
            mod = ((mod * 10) + (pran[i]-48)) % n;
            if(m == 1 && temp < get)ans.push_back(0);
            if(temp >= get){
                root = temp / get;ans.push_back(root);
                m = 1;
            }
        }
        for(int i = 0; i < ans.size(); i++)cout << ans[i];cout << endl;
        ans.clear();
    }
    return 0;
}