Kickstart Practice Round 2017

Chong Wang Lv6
  2017-03-03 14:25:28 2017-03-03 14:25:28 Created   2026-10-09 09:08:18 2026-10-09 09:08:18 Updated  

It has been a long time since I last wrote a blog post. I am doing Kick Start this weekend, so I used a Practice Round to warm up. These three problems were fairly simple. I mainly wanted to record Problem B, Vote: it uses the same idea as SPOJ’s INS14G - Kill Them All. I struggled to understand it before, then partly forgot it when solving it again.

I am so tired. Year after year, I have not become who I wanted to be or gone where I wanted to go.

I hope to make my dreams real this year.

A.Country Leader

Problem

The Constitution of a certain country states that the leader is the person with the name containing the greatest number of different alphabet letters. (The country uses the uppercase English alphabet from A through Z.) For example, the name GOOGLE has four different alphabet letters: E, G, L, and O. The name APAC CODE JAM has eight different letters. If the country only consists of these 2 persons, APAC CODE JAM would be the leader.

If there is a tie, the person whose name comes earliest in alphabetical order is the leader.

Given a list of names of the citizens of the country, can you determine who the leader is?
Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line with an interger N, the number of people in the country. Then N lines follow. The i-th line represents the name of the i-th person. Each name contains at most 20 characters and contains at least one alphabet letter.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the name of the leader.
Limits

1 ≤ T ≤ 100.
1 ≤ N ≤ 100.
Small dataset

Each name consists of at most 20 characters and only consists of the uppercase English letters A through Z.

Large dataset

Each name consists of at most 20 characters and only consists of the uppercase English letters A through Z and ‘ ‘(space).
All names start and end with alphabet letters.
Sample

Input
2
3
ADAM
BOB
JOHNSON
2
A AB C
DEF

Output

Case #1: JOHNSON
Case #2: A AB C

In sample case #1, JOHNSON contains 5 different alphabet letters(‘H’, ‘J’, ‘N’, ‘O’, ‘S’), so he is the leader.

Sample case #2 would only appear in Large data set. The name DEF contains 3 different alphabet letters, the name A AB C also contains 3 different alphabet letters. A AB C comes alphabetically earlier so he is the leader.

Find the character that occurs most often in a string. If several tie, choose the lexicographically smallest.

A direct simulation is enough; the main point is to use getline(cin, t).

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
void solve()
{
	int n;
	sa(n);
	string res = "";
	string res_nxt = "";
	int cnt = 0;
	char tmp;
	scanf("%c", &tmp);
	repp(i, 1, n)
	{
		string t;
		getline(cin, t);
		map<char, int>hax;
		string nxt;
		rep(i, 0, t.length())
		{
			if (t[i] == ' ')continue;
			hax[t[i]]++;
			nxt.push_back(t[i]);
		}
		if (hax.size() > cnt)
		{
			cnt = hax.size();
			res = t;
			res_nxt = nxt;
		}
		else if (hax.size() == cnt)
		{
			res = min(res, t);
		}
	}
	cout << res << endl;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("i.txt", "r", stdin);
	freopen("o.txt", "w", stdout);
#endif
	int t;
	sa(t);
	repp(i, 1, t)
	{
		printf("Case #%d: ", i);
		solve();
	}//system("pause");
	return 0;
}

B.Vote

Problem

A and B are the only two candidates competing in a certain election. We know from polls that exactly N voters support A, and exactly M voters support B. We also know that N is greater than M, so A will win.

Voters will show up at the polling place one at a time, in an order chosen uniformly at random from all possible (N + M)! orders. After each voter casts their vote, the polling place worker will update the results and note which candidate (if any) is winning so far. (If the votes are tied, neither candidate is considered to be winning.)

What is the probability that A stays in the lead the entire time – that is, that A will always be winning after every vote?

Input

The input starts with one line containing one integer T, which is the number of test cases. Each test case consists of one line with two integers N and M: the numbers of voters supporting A and B, respectively.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the probability that A will always be winning after every vote.

y will be considered correct if y is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

Limits

1 ≤ T ≤ 100.
Small dataset

0 ≤ M < N ≤ 10.
Large dataset

0 ≤ M < N ≤ 2000.
Sample

Input

2
2 1
1 0

Output

Case #1: 0.33333333
Case #2: 1.00000000

In sample case #1, there are 3 voters. Two of them support A – we will call them A1 and A2 – and one of them supports B. They can come to vote in six possible orders: A1 A2 B, A2 A1 B, A1 B A2, A2 B A1, B A1 A2, B A2 A1. Only the first two of those orders guarantee that Candidate A is winning after every vote. (For example, if the order is A1 B A2, then Candidate A is winning after the first vote but tied after the second vote.) So the answer is 2/6 = 0.333333…

In sample case #2, there is only 1 voter, and that voter supports A. There is only one possible order of arrival, and A will be winning after the one and only vote.

Given $n$ ones and $m$ zeroes, count strings in which every prefix $[1..x]$ has more ones than zeroes.

Use the same idea as the daily problem. Imagine walking from $[1,1]$ to $[n+m,n-m]$, going up $n-1$ times and down $m$ times without touching the x-axis. The total number of paths is
$$
C\begin{pmatrix}
n+m-1\
n-1
\end{pmatrix}
$$
Then subtract invalid paths. If a path touches the x-axis, reflect the part before that touch across the axis. The invalid paths correspond to paths from $[1,-1]$ to $[n+m,n-m]$, whose count is
$$
C\begin{pmatrix}
n+m-1\
n
\end{pmatrix}
$$
Then multiply by $m! * n! / (m+n)!$.

The result is
$$
\frac{n-m}{n+m}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int m, n;
void solve()
{
	sa(n), sa(m);
	printf("%.7lf\n", (1.0*n - m) / (n + m));
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("i.txt", "r", stdin);
	freopen("o.txt", "w", stdout);
#endif
	int t;
	sa(t);
	repp(i, 1, t)
	{
		printf("Case #%d: ", i);
		solve();
	}//system("pause");
	return 0;
}

C. Sherlock and Parentheses

Problem

Sherlock and Watson have recently enrolled in a computer programming course. Today, the tutor taught them about the balanced parentheses problem. A string S consisting only of characters ( and/or ) is balanced if:
It is the empty string, or:
It has the form (S), where S is a balanced string, or:
It has the form S1S2, where S1 is a balanced string and S2 is a balanced string.

Sherlock coded up the solution very quickly and started bragging about how good he is, so Watson gave him a problem to test his knowledge. He asked Sherlock to generate a string S of L + R characters, in which there are a total of L left parentheses ( and a total of R right parentheses ). Moreover, the string must have as many different balanced non-empty substrings as possible. (Two substrings are considered different as long as they start or end at different indexes of the string, even if their content happens to be the same). Note that S itself does not have to be balanced.

Sherlock is sure that once he knows the maximum possible number of balanced non-empty substrings, he will be able to solve the problem. Can you help him find that maximum number?
Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line with two integers: L and R.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the answer, as described above.

Limits

1 ≤ T ≤ 100.
Small dataset

0 ≤ L ≤ 20.
0 ≤ R ≤ 20.
1 ≤ L + R ≤ 20.
Large dataset

0 ≤ L ≤ 105.
0 ≤ R ≤ 105.
1 ≤ L + R ≤ 105.
Sample

Input
3
1 0
1 1
3 2
Output

Case #1: 0
Case #2: 1
Case #3: 3

In Case 1, the only possible string is (. There are no balanced non-empty substrings.
In Case 2, the optimal string is (). There is only one balanced non-empty substring: the entire string itself.
In Case 3, both strings ()()( and (()() give the same optimal answer.
For the case ()()(, for example, the three balanced substrings are () from indexes 1 to 2, () from indexes 3 to 4, and ()() from indexes 1 to 4.

Given the number of left and right parentheses, find the maximum number of valid parentheses substrings that can be formed.

Let $n$ be the number of matched left and right parentheses. The optimal form is ()()()…, so the answer is
$$
\frac{n*(n+1)}{2}
$$

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
ll m, n;
void solve()
{
	cin >> n >> m;
	ll minn = min(n, m);
	ll res = (minn + 1)*minn / 2;
	cout << res << endl;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("i.txt", "r", stdin);
	freopen("o.txt", "w", stdout);
#endif
	int t;
	sa(t);
	repp(i, 1, t)
	{
		printf("Case #%d: ", i);
		solve();
	}
  	//system("pause");
	return 0;
}
On this page
Kickstart Practice Round 2017
  1. A.Country Leader
  2. B.Vote
  3. C. Sherlock and Parentheses