Codeforces Beta Round #2

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.

output

print the name of the winner.

examples

input

3
mike 3
andrew 5
mike 2

output

andrew

input

3
andrew 3
andrew 2
mike 5

output

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.

input

the 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).

output

in the first line print the least number of trailing zeros. in the second line print the correspondent way itself.

examples

input

3
1 2 3
4 5 6
7 8 9

output

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;
}