A - Binarize It

算法标签

思维

题目描述

Professor Boolando can only think in binary, or more specifically, in powers of 2. He converts any number you give him to the smallest power of 2 that is equal to or greater than your number. For example, if you give him 5, he converts it to 8; if you give him 100, he converts it to 128; if you give him 512, he converts it to 512.

The Problem:

Given an integer, your program should binarize it.

输入

The first input line contains a positive integer,n, indicating the numberof values to binarize. The values are on the following n input lines, one per line. Each input will contain an integer between 2 and 100,000 (inclusive).

输出

At the beginning of each testcase, output “Inputvalue:v” where v is the input value. Then,on the next output line, print the binarized version. Leave a blank line after the output for each test case.

样例

Input

1
2
3
4
3
900
16
4000

Output

1
2
3
4
5
6
7
8
Input value: 900
1024

Input value: 16
16

Input value: 4000
4096

解题思路

题目很简单，签到题，注意输出格式。

给你一个数字，转换成以2为底的幂，得到的答案大于等于这个数字。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

using namespace std;

int main()
{
	int T;
	int n;

	cin >> T;
	while (T--)
	{
		cin >> n;

		int ans = 2;

		while (ans < n)	ans *= 2;

		cout << "Input value: " << n << endl;
		cout << ans << endl << endl;
	}

	return 0;
}

English单词积累

无

B - g2g c u l8r

算法标签

模拟

题目描述

According to the national statistics, a teenager sends/receives 100+ text messages a day. Dr. Orooji’s teenage children are no exception but the problem is Dr. O (an old-fashioned, face-to- face communicator) has difficulty reading text messages full of abbreviations (short-hands) sent to him by his children. Dr. O needs your help reading these text messages.

The Problem:

Given the list of abbreviations and a paragraph, you are to expand the text (paragraph) so that Dr. O can read it easily.

输入

The first input line contains an integer,n (1 ≤ n ≤ 20),indicating the number of abbreviations. These abbreviations are on the following n input lines, one per line. Each input line starts in column 1 and contains an abbreviation (1-5 characters, consisting of only lowercase letters and/or digits). The abbreviation is followed by exactly one space, and this is followed by the expanded version ofthe abbreviation (1-50 characters, consisting of only lowercase letters and spaces; assume the expanded version does not start or end with a space and contains no multiple consecutive spaces between words).Assume that all abbreviations are distinct, i.e. no duplicates.

The list of abbreviations is followed by a positive integer,p,indicating the number of input lines containing the paragraph to be expanded. The paragraph is on the following p input lines. Assume these input lines do not exceed column 50, do not start or end with a space, and each line contains at least one word. The paragraph will contain only lowercase letters, digits, and spaces. Assume that there will not be multiple consecutive spaces in the input paragraph.

A word is defined as a consecutive sequence of letters/digits. Assume that a word will be entirely on one input line, i.e. a word is not broken over two or more lines.

输出

Each line of the input paragraph must be on one line of output. The input line must be printed in the output exactly the same (spacing). The only exception is that each abbreviation must be replaced by its expanded version, i.e., when an abbreviation is found in the input, its expanded version must be output.

Note that an abbreviation must match a word completely and not just part of a word. For example,if u is an abbreviation for “you”, then u must appear as a word by itself in the paragraph

in order to be replaced,i.e., if the abbreviation is part of a word in the paragraph (e.g.,the paragraph contains the word buy or ugly or you),the u in these words should not be replaced.

样例

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
8
g2g got to go
g good
c see
l8 late
l8r later
d i am done
u you
r are
6
hi
how r u
you tell me
you are l8
d
c u l8r

Output

1
2
3
4
5
6
hi
how are you
you tell me
you are late
i am done
see you later

解题思路

题意很简单，给出缩写对应的完整语句。

然后给出一段文字，将文字中的缩写替换。

可以使用map保存缩写，然后使用stringstream分割文字替换即可。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <sstream>
#include <map>

using namespace std;

int main()
{
	int n;
	stringstream ss;
	map<string, string> str;

	cin >> n;
	getchar();
	while (n--)
	{
		string a;
		string b;

		cin >> a;
		getchar();
		getline(cin, b);

		str[a] = b;
	}

	cin >> n;
	getchar();
	while (n--)
	{
		string tmp;
		string ans;

		getline(cin, tmp);
		ss.str("");
		ss.clear();
		ss.str(tmp);

		int flag = 1;
		while (ss >> tmp)
		{
			if (flag == 0)	ans += ' ';

			if (str.find(tmp) != str.end())
			{
				ans += str[tmp];
			}
			else
			{
				ans += tmp;
			}

			flag = 0;
		}

		cout << ans << endl;
	}

	return 0;
}

English单词积累

abbreviations—缩写

C - Tip to be Palindrome

算法标签

模拟

题目描述

One of the cool UCF CS alumni is Dr. Greg, The Palindrome Tipper. A palindrome is a string that reads the same forward and backward, e.g., madam, abba, 3, 44, 525.
One cool thing about Dr. Greg is that he leaves at least 20% tip when he eats out, e.g., if the meal is 30, Dr. Greg leaves 30, Dr. Greg leaves 6 (30 * 0.20) for tip. If the tip (20%) is not a whole dollar amount, he rounds up the tip to make it a whole number. For example, if the meal is 12, tip would be (12 * 0.20) but Dr. Greg would leave $3 for tip.
Another cool thing about Dr. Greg is that he is a palindrome guru. If his total bill (meal plus tip) is not a palindrome, he will increase the total (by adding to the tip) to make the total a palindrome. He will, of course, add the minimum needed to make the total a palindrome.
The Problem:

Given Dr. Greg’s meal cost, your program should determine the tip amount for him (according to his rules) and the total bill.

输入

The first input line contains a positive integer, n, indicating the number of times Dr. Greg ate out. The meal costs are on the following n input lines, one per line. Each input will contain an integer between 5 and 10000 (inclusive).

输出

At the beginning of each test case, output “Input cost: c” where c is the input cost. Then, on the next output line, print the tip amount and the total bill, separated by one space. Leave a blank line after the output for each test case.

样例

Input

1
2
3
2
12
84

Output

1
2
3
4
5
Input cost: 12
10 22

Input cost: 84
17 101

解题思路

博士出门吃饭，每次付费20%的小费，如果小费不是整数，向上取整。

此外，要求付费总额必须是一个回文数字，如果不是的话增加小费。

吃饭金额小于等于10000，可以在小费的基础上暴力计算。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

bool IsAns(int ans)
{
	vector<int> v;

	while (ans)
	{
		v.push_back(ans % 10);
		ans /= 10;
	}

	for (int i = 0; i < v.size() / 2; i++)
	{
		if (v[i] != v[v.size() - i - 1])	return false;
	}

	return true;
}

int main()
{
	int T;

	cin >> T;
	while (T--)
	{
		int n;
		int tip;
		int ans;

		cin >> n;
		tip = ceil(n * 0.2);
		ans = n + tip;

		while(!IsAns(ans))
		{
			tip++;
			ans++;
		}

		cout << "Input cost: " << n << endl;
		cout << tip << ' ' << ans << endl << endl;
	}

	return 0;
}

English单词积累

alumni—校友

Palindrome—回文

guru—专家

D - Soccer Standings

算法标签

模拟

题目描述

Soccer fever has gripped the world once again, and millions of people from dozens of countries will be glued to their TV sets for the World Cup. Being an enterprising sort, you’ve started up your own internet World Cup Soccer Channel for streaming matches online. Recently you came up with the idea of filling up the time between matches by having a couple of ‘experts’ offer critical analysis of games. For this purpose, you have devised a unique ranking system for soccer teams, which you must now implement.

The Problem:

Given a list of teams and a list of match scores, you must compute several quantities for each team. These are: the total number of goals scored over all their games, the total number of goals scored against them (goals allowed, for short), the number of wins, draws and losses, and the number of points scored so far. Points are to be computed as follows: winning a match nets a team 3 points, losing gets them nothing. In the event of a tie, both teams get 1 point.

In addition to this, you must order the teams correctly according to your new system. Teams are ordered according to points, from highest to lowest. In the event of a tie in points, the team that has a higher goal difference comes first. The goal difference is defined as the total number of goals scored by the team minus the total number of goals scored against them.
If there is still a tie (i.e., two or more teams have the same points and the same goal differences), the team with higher total goals scored comes first. If even this is tied, the team whose name comes first in alphabetical order goes first.

输入

The first input line contains a positive integer, n, indicating the number of data sets to be processed. The first line of each data set consists of two positive integers T (T ≤ 30) and G (G ≤ 400) – the number of teams in this group and the total number of games played by them. The next line contains T unique names separated by single spaces. Each name is a single uppercase word with no more than 15 characters.
Each of the next G input lines will contain the results of a match. Each line is of the form
. For example, “Greece 2 Nigeria 1” indicates that Greece and Nigeria played a game with score 2-1. All four terms will be separated by single spaces.

输出

At the beginning of output for each data set, output “Group g:” where g is the data set number, starting from 1. Next you should print a single line for each team, ordering teams as mentioned above. For each team, the line you print should be of the form “ ”. These items should be separated by single spaces. Leave a blank line after the output for each data set.

样例

Input

1
2
3
4
5
6
7
8
9
10
11
12
2
2 1
KASNIA LATVERIA
KASNIA 0 LATVERIA 1
4 6
ENGLAND USA ALGERIA SLOVENIA
ENGLAND 1 USA 1
ALGERIA 0 SLOVENIA 1
SLOVENIA 2 USA 2
ENGLAND 0 ALGERIA 0
SLOVENIA 0 ENGLAND 1
USA 1 ALGERIA 0

Output

1
2
3
4
5
6
7
8
9
Group 1:
LATVERIA 3 1 0 0 1 0
KASNIA 0 0 1 0 0 1

Group 2:
USA 5 1 0 2 4 3
ENGLAND 5 1 0 2 2 1
SLOVENIA 4 1 1 1 3 3
ALGERIA 1 0 2 1 0 2

解题思路

题目难点在于计分规则，需要认真阅读题目。

统计每个队伍的 队名 得分 赢 输 平 进球数 失球数。

最后按照得分排名，得分相同按照球差排名，球差排名按照进球数排名，最后按照队名排名。

球差 = 进球数 - 对手进球数

涉及到的变量有点多，仔细模拟就行。记得清空数组。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

struct Team
{
	string name;

	int point;

	int win;
	int loss;
	int draw;

	int score;
	int allow;
};

int T;
Team team[30];
int n, m;

int find(Team team[], string& name)
{
	for (int i = 0; i < n; i++)	if (team[i].name == name)	return i;

	return -1;
}

bool cmp(Team a, Team b)
{
	if (a.point != b.point)	return a.point > b.point;
	else if (a.score - a.allow != b.score - b.allow)	return a.score - a.allow > b.score - b.allow;
	else if (a.score != b.score)	return a.score > b.score;
	else return a.name < b.name;
}

void init()
{
	for (int i = 0; i < 30; i++)
	{
		team[i].point = 0;
		team[i].win = 0;
		team[i].loss = 0;
		team[i].draw = 0;
		team[i].score = 0;
		team[i].allow = 0;
	}
}
int main()
{
	int cnt = 0;

	cin >> T;
	while (T--)
	{
		init();

		cnt++;
		cin >> n >> m;

		for (int i = 0; i < n; i++)	cin >> team[i].name;

		for (int i = 0; i < m; i++)
		{
			string name1, name2;
			int score1, score2;
			int index1, index2;

			cin >> name1 >> score1 >> name2 >> score2;

			index1 = find(team, name1);
			index2 = find(team, name2);

			team[index1].score += score1;
			team[index2].score += score2;

			team[index1].allow += score2;
			team[index2].allow += score1;
			if (score1 == score2)
			{
				team[index1].draw++;
				team[index2].draw++;

				team[index1].point += 1;
				team[index2].point += 1;
			}
			else if (score1 > score2)
			{
				team[index1].win++;
				team[index2].loss++;

				team[index1].point += 3;
			}
			else
			{
				team[index1].loss++;
				team[index2].win++;

				team[index2].point += 3;
			}
		}

		sort(team, team + n, cmp);

		printf("Group %d:\n", cnt);
		for (int i = 0; i < n; i++)
		{
			printf("%s %d %d %d %d %d %d\n", team[i].name.c_str(), team[i].point, team[i].win, team[i].loss, team[i].draw,
										   team[i].score, team[i].allow);
		}
		cout << endl;
	}

	return 0;
}

English单词积累

enterprising sort—有进取心的人

devise—发明

implement—实现

E - NIH Budget（未做）

算法标签

分组背包

F - Interstellar Love（未做）

算法标签

并查集求无向图连通分量和闭环数

G - Plate Spinning（未做）

算法标签

H - The Eternal Quest for Caffeine（未做）

算法标签

模拟

I - Pegasus Circle Shortcut（未做）

算法标签

计算几何

J - Lowest Common Ancestor（未做）

算法标签

LCA最近公共祖先