Codeforces Beta Round #2 A. Winner The winner of the card game popular in Berland "Berlogging" is determined according to the following rules. If at the end of the game there is only one player with the maximum number of points, he is the winner. The situation becomes more difficult if the number of such players is more than one. During each round a player gains or loses a particular number of points. In the course of the game the number of points is registered in the line "name score", where name is a player's name, and score is the number of points gained in this round, which is an integer number. If score is negative, this means that the player has lost in the round. So, if two or more players have the maximum number of points (say, it equals to m) at the end of the game, than wins the one of them who scored at least m points first. Initially each player has 0 points. It's guaranteed that at the end of the game at least one player has a positive number of points. Input
The first line contains an integer number n (1??≤??n??≤??1000), n is the number of rounds played. Then follow n lines, containing the information about the rounds in "name score" format in chronological order, where name is a string of lower-case Latin letters with the length from 1 to 32, and score is an integer number between -1000 and 1000, inclusive.
OutputPrint the name of the winner.
Examples input3output
mike 3
andrew 5
mike 2
andrewinput
3output
andrew 3
andrew 2
mike 5
andrew
題意：大概意思就是給你一些人玩游戲的程序，問你游戲結束時，誰的總分最高，要注意的就是如果最后總分有一樣的，那就是先得到最高分的人獲勝，
代碼奉上：
#include <bits/stdc++.h> using namespace std; string s[10002],a; int n,i,o[100032],m=-0x3f3f3f,temp; map<string,int>p,t; main() { scanf("%d",&n); for(i=0; i<n; i++) { cin>>s[i]>>o[i]; p[s[i]]+=o[i]; } for(i=0; i<n; i++) if(p[s[i]]>m) m=p[s[i]]; for(i=0; i<n; i++) { if((t[s[i]]+=o[i])>=m&&p[s[i]]>=m) { cout<<s[i]<<endl; break; } } return 0; }B. The least round way
There is a square matrix n?×?n, consisting of non-negative integer numbers. You should find such a way on it that
- starts in the upper left cell of the matrix;
- each following cell is to the right or down from the current cell;
- the way ends in the bottom right cell.
Moreover, if we multiply together all the numbers along the way, the result should be the least "round". In other words, it should end in the least possible number of zeros.
InputThe first line contains an integer number n (2?≤?n?≤?1000), n is the size of the matrix. Then follow n lines containing the matrix elements (non-negative integer numbers not exceeding 109).
OutputIn the first line print the least number of trailing zeros. In the second line print the correspondent way itself.
Examples input3output
1 2 3
4 5 6
7 8 9
0
DDRR
題意：這個題就是給你一個n*n的矩陣，然后讓你從左上角走到右下角，問走過的路線每個數都乘起來，然后找出結果中末尾0的個數最少的以及這條路線是如何走的，只能向右或向下，
代碼如下：
#include <bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; int f[1001][1001][2],n,x,k; char g[1001][1001][2]; void gao(int x,int y) { if(x==1&&y==1)//如果是起點，回傳 return; if(g[x][y][k])//判斷g的，1記錄的向下,0記錄的向右 gao(x-1,y),putchar('D'); else gao(x,y-1),putchar('R'); } int main() { scanf("%d",&n); memset(f,0,sizeof(f)); for(int i=2; i<=n; ++i) f[0][i][0]=f[0][i][1]=f[i][0][0]=f[i][0][1]=inf;//讓第一行的上一行和第一列的前一列 for(int i=1; i<=n; ++i) { for(int j=1; j<=n; ++j) { scanf("%d",&k); if(!k)//當前值為零 x=i;//標記一下，記錄第幾行存在0 else { while(k%2==0) ++f[i][j][0],k/=2;//如果當前位置的值為2的倍數，則記錄進0中，存進數值除以2的值 while(k%5==0) ++f[i][j][1],k/=5;//如果當前數值是5的倍數，測記錄進1中，存進數值除以5的值 } for(int k=0; k<2; k++)//統計行程序序中2的倍數和5的倍數 { if(g[i][j][k]=f[i-1][j][k]<f[i][j-1][k])//判斷此行的上一行的2的倍數個數小于此列的上一列的2的倍數的個數,也就是當前位置的上一個位置，左邊和上邊，那個方向的2更少，g為一的時候，則是向下走 f[i][j][k]+=f[i-1][j][k];//則進行此位置加上上一行的2或5的倍數的個數，就把那個方向的數加上 else//否則則是另一個方向，向右走的 f[i][j][k]+=f[i][j-1][k];//否則就是此位置加上上一列2或5的倍數的個數 } } } k=f[n][n][1]<f[n][n][0];//最后一個位置的2和5個數那個比較多 if(x&&f[n][n][k]>1)//說明前面至少有一對2和5，也就是至少有一個零，同時如果程序中有為零的，也就是x被標記過，那就是只存在一個零，相當于就一個10， { cout<<"1\n";//接下來就是輸出程序中以x這個點為十字路口，前面一個方向，后面一個方向 for(int i=2; i<=x; i++) putchar('D'); for(int i=2; i<=n; i++) putchar('R'); for(int i=x+1; i<=n; i++) putchar('D'); } else printf("%d\n",f[n][n][k]),gao(n,n);//先輸出最少的對數，因為一個是記數2的，一個是記數5的 return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/89825.html
標籤：C++