UVa - 147 - Dollars

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم  #####*******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define sc(n) scanf("%d", &n)
8. #define S 30003
9. using namespace std;
10. typedef long long LL;
11.  
12. LL N, dp[15][S];
13. LL coins[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};
14. LL Dollars(int ind, LL tot){
15.     if(tot == 0LL)return 1LL;
16.     if(tot < 0)return 0LL;
17.     if(ind >= 11)return 0LL;
18.     if(dp[ind][tot] != -1LL)return dp[ind][tot];
19.     dp[ind][tot] = (Dollars(ind, tot-coins[ind])+Dollars(ind+1, tot));
20.     return dp[ind][tot];
21. }
22.  
23. void Do(){
24.     char n[10];
25.     memset(dp, -1LL, sizeof(dp));
26.     while(scanf("%s", n) == 1){
27.         N = 0LL;
28.         for(int i = 0; n[i]; i++){
29.             if(n[i] >= '0' && n[i] <= '9')
30.                 N = (N*10LL)+(n[i]-'0');
31.         }
32.         if(N == 0LL)break;
33.         printf("%6s%17lld\n", n, Dollars(0, N));
34.     }
35. }
36.  
37. int main(){
38.     ios_base::sync_with_stdio(0); cin.tie(0);
39.     #ifndef ONLINE_JUDGE
40.     ///freopen("inp","r",stdout);
41.     ///freopen("contest.txt","w",stdout);
42.     #endif
43.     Do();
44.     return 0;
45. }

UVa - 11517 - Exact Change

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم  #####*******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define sc(n) scanf("%d", &n)
8. #define S 103
9. using namespace std;
10. typedef long long LL;
11.  
12. int p, n, mn, ans;
13. int arr[S], dp[S][S*100];
14.  
15. int Exchange(int ind, int tot, int coin){
16.     if(tot >= p)return tot;
17.     if(ind >= n)return INT_MAX;
18.     if(dp[ind][tot] != -1)return dp[ind][tot];
19.     dp[ind][tot] = 0;
20.     dp[ind][tot] += Exchange(ind+1, tot+arr[ind], coin+1);
21.     mn = min(mn, dp[ind][tot]);
22.     Exchange(ind+1, tot, coin);
23.     return mn;
24. }
25.  
26. int Coins(int ind, int coin, int tot){
27.     if(tot == ans)return coin;
28.     if(tot > ans)return INT_MAX;
29.     if(ind >= n)return INT_MAX;
30.     if(dp[ind][tot] != -1)return dp[ind][tot];
31.     dp[ind][tot] = 0;
32.     dp[ind][tot] += Coins(ind+1, coin+1, tot+arr[ind]);
33.     mn = min(mn, dp[ind][tot]);
34.     Coins(ind+1, coin, tot);
35.     return mn;
36. }
37.  
38. void Do(){
39.     int t;
40.     sc(t);
41.     while(t--){
42.         sc(p);
43.         sc(n);
44.         memset(dp, -1, sizeof(dp));
45.         for(int i = 0; i < n; i++)sc(arr[i]);
46.         sort(arr, arr+n);
47.         reverse(arr, arr+n);
48.         mn = INT_MAX;
49.         ans = Exchange(0, 0, 0);
50.         cout << ans << " ";
51.         memset(dp, -1, sizeof(dp));
52.         mn = INT_MAX;
53.         cout << Coins(0, 0, 0) << endl;
54.     }
55. }
56.  
57. int main(){
58.     ios_base::sync_with_stdio(0); cin.tie(0);
59.     #ifndef ONLINE_JUDGE
60.     ///freopen("inp","r",stdout);
61.     ///freopen("contest.txt","w",stdout);
62.     #endif
63.     Do();
64.     return 0;
65. }

UVa - 386 - Perfect Cubes

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم  #####*******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define sc(n) scanf("%d", &n)
8. #define S 10000003
9. using namespace std;
10. typedef long long LL;
12. struct data{
13.     int Num;
14.     vector <int> Qube;
15. }arr[S];
17. int qube[S];
19. int cmp(data p, data q){
20.     if(p.Num == q.Num)return p.Qube < q.Qube;
21.     return p.Num < q.Num;
22. }
24. void asgn_qube(){
25.     for(int i = 2; i <= 200; i++)qube[i*i*i] = i;
26. }
28. int prfct_qube(int z){
29.     int w, x, y;
30.     for(int i = 2; i <= 200; i++){
31.         w = i*i*i;
32.         for(int j = i+1; j <= 200; j++){
33.             x = j*j*j;
34.             for(int k = j+1; k <= 200; k++){
35.                 y = k*k*k;
36.                 if(w+x+y < S && qube[w+x+y]){
37.                     arr[z].Num = qube[w+x+y];
38.                     arr[z].Qube.push_back(i);
39.                     arr[z].Qube.push_back(j);
40.                     arr[z].Qube.push_back(k);
41.                     z++;
42.                 }
43.             }
44.         }
45.     }
46.     sort(arr, arr+z, cmp);
47.     return z;
48. }
50. void Do(){
51.     asgn_qube();
52.     int lim = prfct_qube(0);
53.     int l = 0;
54.     for(int i = 0; i < lim; i++){
55.         int sz = arr[i].Qube.size();
56.         cout << "Cube = " << arr[i].Num << ", ";
57.         for(int j = 0; j < 3; j++){
58.             if(!j)cout << "Triple = (";
59.             if(j == 2)cout << arr[i].Qube[j] << ")" << endl;
60.             else cout << arr[i].Qube[j] << ",";
61.         }
62.     }
63. }
65. int main(){
66.     ios_base::sync_with_stdio(0); cin.tie(0);
67.     #ifndef ONLINE_JUDGE
68.     ///freopen("inp","r",stdout);
69.     ///freopen("contest.txt","w",stdout);
70.     #endif
71.     Do();
72.     return 0;
73. }

UVa - 729 - The Hamming Distance Problem

1. #include <bits/stdc++.h>
2. using namespace std;
3.  
4. vector <int> Ham;
5. int n;
6.  
7. int main(){
8.     int t, p, f = 0, bl = 0;
9.     scanf("%d", &t);
10.     while(t--){
11.         scanf("%d %d", &n, &p);
12.         int b = n-p;
13.         while(p--)Ham.push_back(1);
14.         while(b--)Ham.push_back(0);
15.         reverse(Ham.begin(), Ham.end());
16.         if(bl)puts(""); bl = 1;
17.         for(int i = 0; i < n; i++)cout << Ham[i];
18.         puts("");
19.         while(next_permutation(Ham.begin(), Ham.end())){
20.             for(int i = 0; i < n; i++)cout << Ham[i];
21.             puts("");
22.         }
23.         Ham.clear();
24.     }
25.     return 0;
26. }

LightOJ - 1225 - Palindromic Numbers (II)

1. #include <bits/stdc++.h>
2. using namespace std;
3.  
4. int main(){
5.     int t, cs = 0, f;
6.     char n[13], p[13];
7.     scanf("%d", &t);
8.     while(t--){
9.         scanf("%s", n);
10.         int sz = strlen(n);
11.         strcpy(p, n);
12.         reverse(n, n+sz);
13.         printf("Case %d: ", ++cs);
14.         puts((strcmp(n, p) == 0)?"Yes":"No");
15.     }
16.     return 0;
17. }

LightOJ - 1182 - Parity

1. #include <bits/stdc++.h>
2. using namespace std;
3.  
4. int main(){
5.     int t, n, cs = 0;
6.     cin >> t;
7.     while(t--){
8.         int m = 0;
9.         cin >> n;
10.         while(n){
11.             if(n%2)m++;
12.             n /= 2;
13.         }
14.         cout << "Case " << ++cs << ": ";
15.         puts((m%2)?"odd":"even");
16.     }
17.     return 0;
18. }