A Thickest Burger Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 3026 Accepted Submission(s): 2290
Problem Description ACM ICPC is launching a thick burger. The thickness (or the height) of a piece of club steak is A (1 ≤ A ≤ 100). The thickness (or the height) of a piece of chicken steak is B (1 ≤ B ≤ 100). The chef allows to add just three pieces of meat into the burger and he does not allow to add three pieces of same type of meat. As a customer and a foodie, you want to know the maximum total thickness of a burger which you can get from the chef. Here we ignore the thickness of breads, vegetables and other seasonings.
Input The first line is the number of test cases. For each test case, a line contains two positive integers A and B.
Output For each test case, output a line containing the maximum total thickness of a burger.
Sample Input 10 68 42 1 35 25 70 59 79 65 63 46 6 28 82 92 62 43 96 37 28
Sample Output 178 71 165 217 193 98 192 246 235 102
Hint Consider the first test case, since 68+68+42 is bigger than 68+42+42 the answer should be 68+68+42 = 178. Similarly since 1+35+35 is bigger than 1+1+35, the answer of the second test case should be 1+35+35 = 71.
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> using namespace std; long long t,a,b,s; int main() { cin>>t; while(t--) { cin>>a>>b; if(a>b) s=a*2+b; else s=b*2+a; cout<<s<<endl; } }B Relative atomic mass Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2784 Accepted Submission(s): 2305
Problem Description Relative atomic mass is a dimensionless physical quantity, the ratio of the average mass of atoms of an element (from a single given sample or source) to 12of the mass of an atom of carbon-12 (known as the unified atomic mass unit). You need to calculate the relative atomic mass of a molecule, which consists of one or several atoms. In this problem, you only need to process molecules which contain hydrogen atoms, oxygen atoms, and carbon atoms. These three types of atom are written as ’H’，’O’ and ’C’ repectively. For your information, the relative atomic mass of one hydrogen atom is 1, and the relative atomic mass of one oxygen atom is 16 and the relative atomic mass of one carbon atom is 12. A molecule is demonstrated as a string, of which each letter is for an atom. For example, a molecule ’HOH’ contains two hydrogen atoms and one oxygen atom, therefore its relative atomic mass is 18 = 2 * 1 + 16.
Input The first line of input contains one integer N(N ≤ 10), the number of molecules. In the next N lines, the i-th line contains a string, describing the i-th molecule. The length of each string would not exceed 10.
Output For each molecule, output its relative atomic mass.
Sample Input 5 H C O HOH CHHHCHHOH
Sample Output 1 12 16 18 46
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> using namespace std; long long t,a,b,s; int main() { cin>>t; while(t--) { char x[10001]; s=0; scanf("%s",x); int l=strlen(x); for(int i=0;i<l;i++) { if(x[i]=='H') s+=1; else if(x[i]=='C') s+=12; else if(x[i]=='O') s+=16; } cout<<s<<endl; } }C Recursive sequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 5485 Accepted Submission(s): 2362
Problem Description Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and i4. Now, you need to write a program to calculate the number of the N-th cow in order to check if John’s cows can make it right.
Input The first line of input contains an integer t, the number of test cases. t test cases follow. Each case contains only one line with three numbers N, a and b where N,a,b < 231 as described above.
Output For each test case, output the number of the N-th cow. This number might be very large, so you need to output it modulo 2147493647.
Sample Input 2 3 1 2 4 1 10
Sample Output 85 369 Hint In the first case, the third number is 85 = 21十2十3^4. In the second case, the third number is 93 = 21十1*10十3^4 and the fourth number is 369 = 2 * 10 十 93 十 4^4.
#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <string> using namespace std; typedef long long ll; const int N = 10; ll n, p; const ll mod = 2147493647; ll a, b; struct node { ll g[N + 2][N + 2];//结构体存储矩阵 }f, res, s, rans; //构造单位矩阵 void matrixI(node& x) { for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) { if (i == j)x.g[i][j] = 1LL; else x.g[i][j] = 0LL; } } //矩阵乘法 void matrixMultiple(node& x, node& y, node& z) { memset(z.g, 0, sizeof(z.g)); for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) for (int k = 1; k <= N; ++k) { z.g[i][k] += (x.g[i][j] * y.g[j][k]) % mod; if (z.g[i][k] >= mod)z.g[i][k] %= mod; } } //快速幂 void matrixMuli(ll k) { matrixI(res); node tmp = f, t; while (k) { if (k & 1) { matrixMultiple(res, tmp, t); res = t; } matrixMultiple(tmp, tmp, t); tmp = t; k >>= 1; } } void init() { f.g[1][1] = 1; f.g[1][2] = 2; f.g[1][3] = 1; f.g[2][1] = 1; f.g[3][3] = 1; f.g[3][4] = 4; f.g[3][5] = 6; f.g[3][6] = 4; f.g[3][7] = 1; f.g[4][4] = 1; f.g[4][5] = 3; f.g[4][6] = 3; f.g[4][7] = 1; f.g[5][5] = 1; f.g[5][6] = 2; f.g[5][7] = 1; f.g[6][6] = 1; f.g[6][7] = 1; f.g[7][7] = 1; } ll solve() { ll ans; if (n == 1) ans = a % mod; else if (n == 2) ans = b % mod; else { matrixMuli(n - 2); ans = (s.g[1][1] * res.g[1][1] % mod + s.g[2][1] * res.g[1][2] % mod + s.g[3][1] * res.g[1][3] % mod + s.g[4][1] * res.g[1][4] % mod + s.g[5][1] * res.g[1][5] % mod + s.g[6][1] * res.g[1][6] % mod + s.g[7][1] * res.g[1][7] % mod) % mod; } return ans; } int main() { ll t; scanf("%lld", &t); init(); while (t--) { scanf("%lld%lld%lld", &n, &a, &b); //memset(f.g, 0, sizeof(f.g)); //memset(res.g, 0, sizeof(res.g)); //memset(s.g, 0, sizeof(s.g)); //memset(rans.g, 0, sizeof(rans.g)); s.g[1][1] = b; s.g[2][1] = a; s.g[3][1] = 3 * 3 * 3 * 3; s.g[4][1] = 3 * 3 * 3; s.g[5][1] = 3 * 3; s.g[6][1] = 3; s.g[7][1] = 1; ll ans = solve(); printf("%lld\n", ans); } return 0; }D Winning an Auction Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 393 Accepted Submission(s): 119
Problem Description Alice and Bob play an auction game. Alice has A dollars and Bob has B dollars initially. There are N items on sale. In each round, an item will be sold by the following way. Alice writes down an integer a (0 ≤ a ≤ A) and Bob writes down an integer b (0 ≤ b ≤ B), which are the amount of dollars they want to pay for the item. If a > b, then Alice gets the item and pays a dollars to the seller. If a < b, then Bob gets the item and pays b dollars to the seller. If a = b, then for the 1st, 3rd, 5th, 7th … round, Alice gets the item and pays a dollars; for the 2rd, 4th, 6th, 8th … round, Bob gets the item and pays b dollars. Since all the items have the same value, the goal of the auction game is to get as many items as possible. Both Alice and Bob know the values of N,A and B. Your task is to calculate how many items they will get if both of them play optimally.
Input The first line is the number of test cases. Each test case contains 3 integers N,A and B, which are no larger than 255.
Output For each test case, output the number of items Alice and Bob will get if both of them play optimally.
Sample Input 3 1 1 2 2 4 2 3 3 3
Sample Output Alice 0 Bob 1 Alice 1 Bob 1 Alice 2 Bob 1
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> typedef long long ll; using namespace std; int dp[256][256][256]; int f(int n,int a) { int t=n/2; return t*a+(n-t)*(a+1); } int main() { for(int i=0;i<256;i++) { for(int j=0;j<256;j++) { if(i>=j) dp[1][i][j]=1; else dp[1][i][j]=0; } } for(int i=2;i<256;i++) { for(int a=0;a<256;a++) { int t=min(f(i,a),256); for(int b=0;b<t;b++) { if(a==b) { dp[i][a][b]=(i+1)/2; continue; } int ta=i-dp[i-1][b][a]; int tb=0; int j=1; while(1) { tb=i-1-dp[i-1][b-j][a]; if(b<j||tb>=ta) { dp[i][a][b]=ta; break; } ta=i-dp[i-1][b][a-j]; if(a<j||ta<=tb) { dp[i][a][b]=tb; break; } j++; } } } } int t; scanf("%d",&t); while(t--) { int n,a,b; scanf("%d%d%d",&n,&a,&b); printf("Alice %d Bob %d\n",dp[n][a][b],n-dp[n][a][b]); } return 0; }