Codeforces Beta Round #2 A,B,C

A. Winner

time limit per test:1 second

memory limit per test:64 megabytes

input:standard input

output:standard output

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

题目链接：http://codeforces.com/problemset/problem/2/A

题意：

给出一些列的名字和分数！正的表示加分，负的表示减分！ 求最终分数最大的人的名字；

如果分数最大的人有多个，输出最先达到最大分数的人！

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 map<string, int> a,b;
 4 string s[1017];
 5 int main()
 6 {
 7     int x[1017];
 8     int n;
 9     cin >> n;
10     for(int i = 1; i <= n; i++)
11     {
12         cin >> s[i] >> x[i];
13         a[s[i]]+=x[i];
14     }
15     int maxx = 0;
16     for(int i = 1; i <= n; i++)
17     {
18         if(a[s[i]] > maxx)
19             maxx = a[s[i]];
20     }
21 
22     for(int i = 1; i <= n; i++)
23     {
24         b[s[i]]+=x[i];
25         if((b[s[i]]>=maxx) && (a[s[i]]>=maxx))//在最终分数是最大的人中，选首先达到最大分数的人
26         {
27             cout << s[i];
28             break;
29         }
30     }
31     return 0;
32 }

B. The least round way

time limit per test：2 seconds

memory limit per test：64 megabytes

input：standard input

output：standard output

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

题目链接：http://codeforces.com/problemset/problem/2/B

题目大意

给定一个N*N的格子，每个格子里有一个非负数，要求你找出从左上角到右下角的一条路径，使得它满足路径上的格子里的数全部乘起来的积尾部0最少 题解

如果要产生0肯定是2*5得出来的，最终的乘积可以表示为2^x*5^y*C,那么零的个数就是min(x,y)。我们可以先对每个格子里的数预处理下，计算出2和5的个数来，然后DP分别求出2和5的最小个数然后选两者中的最小值，输出路径方法没啥说的，很传统~~还有一个要注意的问题就是如果某个格子的数字为0的情况，这个需要特殊判断一下，我们可以把它当做10，如果最后的结果0的个数大于1则直接输出尾部0的个数为1即可

下面给出AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define  MAXN 1005
 4 #define  INF 0x7fffffff
 5 int path[MAXN][MAXN][2];
 6 int dp[MAXN][MAXN][2],a[MAXN][MAXN][2],n;
 7 int zerox,zeroy,x;
 8 string s;
 9 bool flag;
10 int main()
11 {
12     scanf("%d",&n);
13     flag=false;
14     for(int i=0;i<n;i++)
15         for(int j=0;j<n;j++)
16         {
17             scanf("%d",&x);
18             if(!x)
19             {     
20                 a[i][j][0]=a[i][j][1]=1;
21                 zerox=i,zeroy=j,flag=true;
22             }
23             else
24             {
25                 while(x%2==0) {a[i][j][0]++;x/=2;}
26                 while(x%5==0) {a[i][j][1]++,x/=5;}
27             }
28         }
29         for(int k=0;k<2;k++)
30             for(int i=0;i<n;i++)
31                 for(int j=0;j<n;j++)
32                 {
33                     int ans=INF;
34                     if(i==0&&j==0) ans=0;
35                     if(i!=0&&dp[i-1][j][k]<ans) ans=dp[i-1][j][k];
36                     if(j!=0&&dp[i][j-1][k]<ans) ans=dp[i][j-1][k],path[i][j][k]=1;
37                     dp[i][j][k]=ans+a[i][j][k];
38                 }
39                 int k=dp[n-1][n-1][0]<dp[n-1][n-1][1]?0:1;
40                 if(flag&&dp[n-1][n-1][k]>1)
41                 {
42                     for(int i=0;i<zeroy;i++)
43                         s+="R";
44                     for(int i=0;i<zerox;i++)
45                         s+="D";
46                     for(int i=0;i<n-zeroy-1;i++)
47                         s+="R";
48                     for(int i=0;i<n-zerox-1;i++)
49                         s+="D";
50                     cout<<1<<endl<<s<<endl;
51                 }
52                 else
53                 {
54                     int i=n-1,j=n-1;
55                     while(i>0||j>0)
56                     {
57                         if(path[i][j][k]==1)
58                             s+="R",j--;
59                         else
60                             s+="D",i--;
61                     }
62                     reverse(s.begin(),s.end());
63                     cout<<dp[n-1][n-1][k]<<endl<<s<<endl;
64                 }
65                 return 0;
66 }

C. Commentator problem

time limit per test：1 second

memory limit per test：64 megabytes

input：standard input

output：standard output

The Olympic Games in Bercouver are in full swing now. Here everyone has their own objectives: sportsmen compete for medals, and sport commentators compete for more convenient positions to give a running commentary. Today the main sport events take place at three round stadiums, and the commentator's objective is to choose the best point of observation, that is to say the point from where all the three stadiums can be observed. As all the sport competitions are of the same importance, the stadiums should be observed at the same angle. If the number of points meeting the conditions is more than one, the point with the maximum angle of observation is prefered.

Would you, please, help the famous Berland commentator G. Berniev to find the best point of observation. It should be noted, that the stadiums do not hide each other, the commentator can easily see one stadium through the other.

Input

The input data consists of three lines, each of them describes the position of one stadium. The lines have the format x,  y,  r, where (x, y) are the coordinates of the stadium's center ( -  103 ≤ x,  y ≤ 103), and r (1 ≤ r  ≤ 103) is its radius. All the numbers in the input data are integer, stadiums do not have common points, and their centers are not on the same line.

Output

Print the coordinates of the required point with five digits after the decimal point. If there is no answer meeting the conditions, the program shouldn't print anything. The output data should be left blank.

Examples

Input

0 0 10 
60 0 10 
30 30 10

Output

30.00000 0.00000

题目链接：http://codeforces.com/problemset/problem/2/C

题目大意：

有3个圆，求一点a，使点a对三个圆的视角相等（过a做圆的两条切线，此两切线的夹角即为视角）。若有多点视角相等，则取视角最大的点。

设三个圆的半径分别为r1，r2，r3。设点a到三个圆的圆心距离分别为d1，d2，d3。

即目标是2*arcsin(r1/d1) = 2*arcsin(r2/d2) = 2*arcsin(r3/d3)。即r1/d1 = r2/d2 = r3/d3

那么这就是解析几何的问题了，就是列出坐标系，一顿算呗。应该很难算。但是算出公式直接给程序就行了。

看到网上还有一种方法，就是一种随机的算法。

从一个初始的解开始逐步逼近最优解。

当迭代了若干步之后，估值函数的值仍然较大时，则不存在解。

最开始，我取的估值函数cost = fabs(ang1-ang2) + fabs(ang2-ang3) + fabs(ang3-ang1). 其中ang1 ang2 ang3就是用arcsin求出来的。

这样的问题就是可能会带来比较大的误差，因为要计算的arcsin的值可能很小，所以一开始一直都没法AC。

后来我把估值函数cost 取为cost = (d1/r1-d2/r2)^2 + (d2/r2-d3/r3)^2 + (d3/r3-d1/r1)^2，效果就好一些，就AC了。

总而言之呢，这种随机算法的题目就是很蛋疼了。但是在蛋疼的基础上，还是可以采取一些办法去减小误差的。

下面给出AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 struct pt {
 5     double x;
 6     double y;
 7     double r;
 8 };
 9 
10 pt mkp(double x, double y) {
11     pt ret;
12     ret.x = x;
13     ret.y = y;
14     return ret;
15 }
16 
17 double dis(pt a, pt b) {
18     return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
19 }
20 
21 double cost(pt *p, double x, double y) {
22     double ang[3];
23     for (int i = 0; i < 3; i++) ang[i] = dis(p[i], mkp(x, y)) / p[i].r;
24 
25     double diff[3];
26     for (int i = 0; i < 3; i++) diff[i] = ang[i] - ang[(i+1)%3];
27 
28     double ret = 0;
29     for (int i = 0; i < 3; i++) ret += diff[i] * diff[i];
30 
31     return ret;
32 }
33 
34 const int dx[] = {0, 1, -1, 0};
35 const int dy[] = {1, 0, 0, -1};
36 const double err = 1e-6;
37 int main() {
38     pt p[3];
39     for (int i = 0; i < 3; i++) scanf("%lf %lf %lf", &(p[i].x), &(p[i].y), &(p[i].r));
40 
41     pt ans;
42     ans.x = (p[0].x + p[1].x + p[2].x) / 3.0;
43     ans.y = (p[0].y + p[1].y + p[2].y) / 3.0;
44     double ncost = cost(p, ans.x, ans.y);
45 
46     pt tmp;
47     double step = 1.0;
48     bool flag = false;
49     for (int i = 0; i < 300000 && ncost > err; i++) {
50         flag = false;
51         for (int k = 0; k < 4; k++) {
52             tmp.x = ans.x + step * ((double)dx[k]);
53             tmp.y = ans.y + step * ((double)dy[k]);
54 
55             if (ncost > cost(p, tmp.x, tmp.y)) {
56                 ncost = cost(p, tmp.x, tmp.y);
57                 ans = tmp;
58                 flag = true;
59             }
60         }
61         if (!flag) step *= 0.5;
62     }
63 
64     if (cost(p, ans.x, ans.y) <= err) printf("%.5lf %.5lf\n", ans.x, ans.y);
65     return 0;
66 }

Codeforce