LightOJ - 1007 - Mathematically Hard

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define S 5000003
8. using namespace std;
9.  
10. bool prime[S];
11. __int64 primeD[S];
12.  
13. void seive(){
14.     int last;
15.     for(int i = 2; i <= S; i++){
16.         if(prime[i]){
17.             primeD[i] = i-1;
18.             for(int j = i+i; j <= S; j+=i){
19.                 prime[j] = false;
20.                 if(!primeD[j])primeD[j] = (__int64)j - (j/i);
21.                 else primeD[j] -= (primeD[j]/i);
22.             }
23.         }
24.     }
25.     for(int i = 2; i <= S; i++)primeD[i] *= primeD[i];
26. }
27.  
28. void cumulative_sum(){
29.     for(int i = 3; i <= S; i++){
30.         primeD[i] = primeD[i-1]+primeD[i];
31.     }
32. }
33.  
34. int main(){
35.     memset(prime, true, sizeof(prime));
36.     seive();
37.     cumulative_sum();
38.     int t, a, b, cs = 0;
39.     scanf("%d", &t);
40.     while(t--){
41.         scanf("%d %d", &a, &b);
42.         printf("Case %d: %llu\n", ++cs, primeD[b]-primeD[a-1]);
43.     }
44.     return 0;
45. }

UVa - 524 - Prime Ring Problem

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define S 100
8. using namespace std;
9.  
10. int n;
11. bool check[23];
12. int all[23];
13.  
14. bool prime[S];
15.  
16. void primeCheck(){
17.     int lim = sqrt(S);
18.     for(int i = 2; i <= lim; i++){
19.         if(prime[i]){
20.             for(int j = i*2; j <= S; j+=i){
21.                 prime[j] = false;
22.             }
23.         }
24.     }
25. }
26.  
27. bool sum(int a, int b){
28.     int c = a+b;
29.     return prime[c];
30. }
31.  
32. void PrimeRing(int ind){
33.     int p = all[ind-1]+all[ind-2];
34.     if(p > 1 && !prime[p])return;
35.     if(n == ind){
36.         if(sum(all[0], all[n-1])){
37.             for(int i = 0; i < n; i++){
38.                 printf("%d", all[i]);
39.                 if(i != n-1)printf(" ");
40.             }
41.             puts("");
42.         }
43.         return;
44.     }
45.     for(int i = 1; i < n; i++){
46.         if(!check[i]){
47.             all[ind] = i+1;
48.             check[i] = true;
49.             PrimeRing(ind+1);
50.             check[i] = false;
51.         }
52.     }
53. }
54.  
55. int main(){
56.     int cs = 0;
57.     memset(prime, true, sizeof(prime));
58.     primeCheck();
59.     while(scanf("%d", &n) == true){
60.         if(cs)puts("");
61.         memset(check, false, sizeof(check));
62.         memset(all, 0, sizeof(all));
63.         printf("Case %d:\n", ++cs);
64.         all[0] = 1;
65.         PrimeRing(1);
66.     }
67.     return 0;
68. }

LightOJ - 1023 - Discovering Permutations

1. 1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
   2. __________________________________________________________________________
   3. ######################  Ya-Seen Arafat(ACWizard) #########################
   4. ######################        UAP-CSE-33B        #########################
   5. *************************************************************************/
   6. #include <bits/stdc++.h>
   7. using namespace std;
   8.  
   9. int n, m, cn;
   10. bool check[30];
   11. char all[30];
   12.  
   13. void DisPer(int ind){
   14.     if(n == ind){
   15.         for(int i = 0; i < n; i++){
   16.             printf("%c", all[i]);
   17.         }
   18.         puts("");
   19.         cn++;
   20.  
   21.         return;
   22.     }
   23.     if(cn >= m)return;
   24.     for(int i = 0; i < n; i++){
   25.         if(!check[i]){
   26.             all[ind] = i+'A';
   27.             check[i] = true;
   28.             DisPer(ind+1);
   29.             check[i] = false;
   30.         }
   31.     }
   32. }
   33.  
   34. int main(){
   35.     int t, cs = 0;
   36.     scanf("%d", &t);
   37.     while(t--){
   38.         cn = 0;
   39.         scanf("%d %d", &n, &m);
   40.         memset(check, false, sizeof(check));
   41.         memset(all, 0, sizeof(all));
   42.         printf("Case %d:\n", ++cs);
   43.         DisPer(0);
   44.     }
   45.     return 0;
   46. }

LightOJ - 1004 - Monkey Banana Problem

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 scD(n) scanf("%lf", &n)
9. #define scS(n) scanf("%s", &n)
10. #define S 103
11. using namespace std;
13. int n, ar[S*3][S];
14. int dp[S*3][S], sz[S*3];
16. int MB(int row, int ind, int jump){
17.     if(row > (n+n-1) || ind < 0 || ind > sz[jump])return 0;
18.     if(dp[jump][ind] != -1)return dp[jump][ind];
19.     if(row < n)dp[jump][ind] = (ar[jump][ind] + max(MB(row+1, ind, jump+1), MB(row+1, ind+1, jump+1)));
20.     else dp[jump][ind] = (ar[jump][ind] + max(MB(row+1, ind-1, jump+1), MB(row+1, ind, jump+1)));
21.     return dp[jump][ind];
22. }
24. int main(){
25.     int t, cs = 0;
26.     scanf("%d", &t);
27.     while(t--){
28.         memset(dp, -1, sizeof(dp));
29.         memset(ar, 0, sizeof(ar));
30.         scanf("%d", &n);
31.         int z;
32.         for(int i = 0; i < n; i++){
33.             for(int j = 0; j <= i; j++){
34.                 scanf("%d", &ar[i][j]);
35.             }
36.             sz[i] = i;
37.             z = i;
38.         }
39.         int jj = n-1;
40.         for(int i = z+1; i < (n+n-1); i++){
41.             for(int j = 0; j < jj; j++){
42.                 scanf("%d", &ar[i][j]);
43.             }
44.             sz[i] = jj-1;
45.             jj--;
46.         }
47.         int ans = MB(1, 0, 0);
48.         cout << "Case " << ++cs << ": " << ans << endl;
49.     }
50.     return 0;
51. }

LightOJ - 1009 - Back to Underworld --- using BFS

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 scD(n) scanf("%lf", &n)
9. #define scS(n) scanf("%s", &n)
10. #define S 20003
11. #define SS 100003
12. using namespace std;
13. typedef long long LL;
14.  
15. vector <int> race[S], edge;
16. int ans[S], check[S];
17.  
18. int BFS(int src){
19.     int anss = 0;
20.     queue <int> Q;
21.     Q.push(src);
22.     int sz = edge.size();
23.     ans[src] = 1;
24.     while(!Q.empty()){
25.         int x, y;
26.         x = Q.front();
27.         check[x]++;
28.         Q.pop();
29.         y = race[x].size();
30.         for(int i = 0; i < y; i++){
31.             if(!ans[race[x][i]]){
32.                 Q.push(race[x][i]);
33.                 if(ans[x] == 1)ans[race[x][i]] = 2;
34.                 if(ans[x] == 2)ans[race[x][i]] = 1;
35.             }
36.         }
37.         if(Q.empty()){
38.             int vamp = 0, lyk = 0;
39.             for(int i = 0; i < S; i++){
40.                     if(ans[i] == 1)vamp++;
41.                     if(ans[i] == 2)lyk++;
42.                     ans[i] = 0;
43.             }
44.             anss += max(vamp, lyk);
45.             for(int i = 0; i < sz; i++){
46.                 if(check[edge[i]] == 1){
47.                     Q.push(edge[i]);
48.                     ans[edge[i]] = 1;
49.                     break;
50.                 }
51.             }
52.         }
53.     }
54.     return anss;
55. }
56.  
57. void Do(){
58.     int t, n, u, v, cs = 0;
59.     sc(t);
60.     while(t--){
61.         sc(n);
62.         memset(ans, 0, sizeof(ans));
63.         memset(check, 0, sizeof(check));
64.         for(int i = 0; i < S; i++)race[i].clear();
65.         edge.clear();
66.         while(n--){
67.             sc(u);
68.             sc(v);
69.             if(!check[u])check[u] = 1, edge.push_back(u);
70.             if(!check[v])check[v] = 1, edge.push_back(v);
71.             race[u].push_back(v);
72.             race[v].push_back(u);
73.         }
74.         int members = BFS(u);
75.         printf("Case %d: %d\n", ++cs, members);
76.     }
77. }
78.  
79. int main(){
80.     ios_base::sync_with_stdio(0); cin.tie(0);
81.     #ifndef ONLINE_JUDGE
82.     ///freopen("contest.txt","w",stdout);
83.     #endif
84.     Do();
85.     return 0;
86. }