CF1472B - Fair Division

题目描述

Alice and Bob received n candies from their parents. Each candy weighs either 1 gram or 2 grams. Now they want to divide all candies among themselves fairly so that the total weight of Alice’s candies is equal to the total weight of Bob’s candies.

Check if they can do that.

Note that candies are not allowed to be cut in half.

输入

The first line contains one integer t (1≤t≤10^4^) — the number of test cases. Then t test cases follow.

The first line of each test case contains an integer n (1≤n≤100) — the number of candies that Alice and Bob received.

The next line contains n integers a1,a2,…,an — the weights of the candies. The weight of each candy is either 1 or 2.

It is guaranteed that the sum of n over all test cases does not exceed 10^5^.

输出

For each test case, output on a separate line:

“YES”, if all candies can be divided into two sets with the same weight;
“NO” otherwise.
You can output “YES” and “NO” in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

样例

Input

1
2
3
4
5
6
7
8
9
10
11
5
2
1 1
2
1 2
4
1 2 1 2
3
2 2 2
3
2 1 2

Output

1
2
3
4
5
YES
NO
YES
NO
NO

注意

In the first test case, Alice and Bob can each take one candy, then both will have a total weight of 1.

In the second test case, any division will be unfair.

In the third test case, both Alice and Bob can take two candies, one of weight 1 and one of weight 2.

In the fourth test case, it is impossible to divide three identical candies between two people.

In the fifth test case, any division will also be unfair.

解题思路

题目大意:有n个糖果,两个人平分,糖果的重量为1或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
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

int main()
{
int T;

cin >> T;
while (T--)
{
int n;
int sum1 = 0, sum2 = 0, sum = 0; //1克糖果数量 2克糖果数量 糖果总数量

cin >> n;

for (int i = 0; i < n; i++)
{
int temp;

cin >> temp;
sum += temp;

if (temp == 1) sum1++;
else sum2++;
}

if (sum1 % 2 == 0 && sum2 == 0 || sum1 == 0 && sum2 % 2 == 0) //只有一种糖果,直接平分
{
cout << "YES" << endl;
}
else if(sum % 2 == 0) //先判断总数能否平分
{
int a, b; //a拥有的糖果、b拥有的糖果
a = sum2 / 2;
b = sum2 - sum2 / 2;

if(sum - a * 2 - b * 2 == sum1 && sum1 != 0)
cout << "YES" << endl;
else
{
cout << "NO" << endl;
}
}
else
{
cout << "NO" << endl;
}

}

return 0;
}

English单词积累

CF1166A - Silent Classroom

题目描述

There are n students in the first grade of Nlogonia high school. The principal wishes to split the students into two classrooms (each student must be in exactly one of the classrooms). Two distinct students whose name starts with the same letter will be chatty if they are put in the same classroom (because they must have a lot in common). Let x be the number of such pairs of students in a split. Pairs (a,b) and (b,a) are the same and counted only once.

For example, if there are 6 students: “olivia”, “jacob”, “tanya”, “jack”, “oliver” and “jessica”, then:

  • splitting into two classrooms (“jack”, “jacob”, “jessica”, “tanya”) and (“olivia”, “oliver”) will give x=4 (3 chatting pairs in the first classroom, 1 chatting pair in the second classroom),
  • splitting into two classrooms (“jack”, “tanya”, “olivia”) and (“jessica”, “oliver”, “jacob”) will give x=1 (0 chatting pairs in the first classroom, 1 chatting pair in the second classroom).

You are given the list of the n names. What is the minimum x we can obtain by splitting the students into classrooms?

Note that it is valid to place all of the students in one of the classrooms, leaving the other one empty.

输入

The first line contains a single integer n (1≤n≤100) — the number of students.

After this n lines follow.

The i-th line contains the name of the i-th student.

It is guaranteed each name is a string of lowercase English letters of length at most 20. Note that multiple students may share the same name.

输出

The output must consist of a single integer x — the minimum possible number of chatty pairs.

样例

Input

1
2
3
4
5
4
jorge
jose
oscar
jerry

Output

1
1

Input

1
2
3
4
5
6
7
8
7
kambei
gorobei
shichiroji
kyuzo
heihachi
katsushiro
kikuchiyo

Output

1
2

Input

1
2
3
4
5
6
5
mike
mike
mike
mike
mike

Output

1
4

注意

In the first sample the minimum number of pairs is 1. This can be achieved, for example, by putting everyone except jose in one classroom, and jose in the other, so jorge and jerry form the only chatty pair.

In the second sample the minimum number of pairs is 2. This can be achieved, for example, by putting kambei, gorobei, shichiroji and kyuzo in one room and putting heihachi, katsushiro and kikuchiyo in the other room. In this case the two pairs are kambei and kyuzo, and katsushiro and kikuchiyo.

In the third sample the minimum number of pairs is 4. This can be achieved by placing three of the students named mike in one classroom and the other two students in another classroom. Thus there will be three chatty pairs in one classroom and one chatty pair in the other classroom.

解题思路

题目给出n个人的姓名,要求尽量把首字母相同的人分开到两个教室。

每两个姓名首字母相同的人组成一对,求最少组成多少对(握手问题)。

公式:n * (n - 1) / 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
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

int main()
{
int n;
int ans = 0 ;

int num[26] = { 0 };

cin >> n;

for (int i = 0; i < n; i++)
{
string name;
cin >> name;
num[name[0] - 'a']++;
}

for (int i = 0; i < 26; i++)
{
int a, b;
a = num[i] / 2;
b = num[i] - a;

ans += a * (a - 1) / 2;
ans += b * (b - 1) / 2;
}

cout << ans << endl;

return 0;
}

English单词积累

CF1166B - All the Vowels Please

题目描述

Tom loves vowels, and he likes long words with many vowels. His favorite words are vowelly words. We say a word of length k is vowelly if there are positive integers n and mm such that n⋅m=k and when the word is written by using n rows and mm columns (the first row is filled first, then the second and so on, with each row filled from left to right), every vowel of the English alphabet appears at least once in every row and every column.

You are given an integer k and you must either print a vowelly word of length k or print −1 if no such word exists.

In this problem the vowels of the English alphabet are ‘a’, ‘e’, ‘i’, ‘o’ ,’u’.

输入

Input consists of a single line containing the integer k (1≤k≤10^4^) — the required length.

输出

The output must consist of a single line, consisting of a vowelly word of length k consisting of lowercase English letters if it exists or −1 if it does not.

If there are multiple possible words, you may output any of them.

样例

Input

1
7

Output

1
-1

Input

1
36

Output

1
agoeuioaeiruuimaeoieauoweouoiaouimae

注意

In the second example, the word “agoeuioaeiruuimaeoieauoweouoiaouimae” can be arranged into the following 6×6 grid:

1

It is easy to verify that every row and every column contain all the vowels.

解题思路

题目要求给出一个整数k,并且整数n和m满足n * m = k。

问是否存在n行m列的表格,表格中每一行和每一列都至少包含一次元音字母a、e、i、o、u。

首先考虑临界问题,即每行每列恰好出现一次,即k = 25 ,5 * 5 = 25。

对五行中的五个字符进行逆序数为1的全排序(可以使用next_permutation函数)。

恰好错开排放,满足每行每列均有这五个元音字母。

如果k < 25,一定不满足条件。

如果k > 25,只要以 5 * 5 的表格为基础,向下或向右循环拓展即可。

也就是说,n 和 m必须同时大于等于5,才能得到满足条件的k。

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
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

int num1, num2;

bool what(int);

int main()
{
int k;
int temp;

cin >> k;

temp = k % 5;

if (what(k) == false) cout << -1 << endl;
else
{
char ch1[5] = { 'a', 'e', 'i', 'o', 'u' };
char ch2[5] = { 'e', 'i', 'o', 'u', 'a' };
char ch3[5] = { 'i', 'o', 'u', 'a', 'e' };
char ch4[5] = { 'o', 'u', 'a', 'e', 'i' };
char ch5[5] = { 'u', 'a', 'e', 'i', 'o' };

for (int i = 0; i < num1; i++)
{
int now = 0;

for (int j = 0; j < num2; j++)
{
if (i % 5 == 0)
{
cout << ch1[now];
}
else if(i % 5 == 1)
{
cout << ch2[now];
}
else if (i % 5 == 2)
{
cout << ch3[now];
}
else if (i % 5 == 3)
{
cout << ch4[now];
}
else if (i % 5 == 4)
{
cout << ch5[now];
}

now++;

if (now > 4) now = 0;
}


}
}

return 0;
}

bool what(int num)
{
for (int i = 5; i <= sqrt(num); i++)
{
if (num % i == 0)
{
num1 = i;
num2 = num / i;
return true;
}

}

return false;
}

English单词积累