Rday5

Rday5

练习

2048 Game

You are playing a variation of game 2048. Initially you have a multiset s of n integers. Every integer in this multiset is a power of two.

You may perform any number (possibly, zero) operations with this multiset.

During each operation you choose two equal integers from s, remove them from s and insert the number equal to their sum into s.

For example, if s={1,2,1,1,4,2,2} and you choose integers 2 and 2, then the multiset becomes {1,1,1,4,4,2}.

You win if the number 2048 belongs to your multiset. For example, if s={1024,512,512,4} you can win as follows: choose 512 and 512, your multiset turns into {1024,1024,4}. Then choose 1024 and 1024, your multiset turns into {2048,4} and you win.

You have to determine if you can win this game.

You have to answer q independent queries.

Input
The first line contains one integer q (1≤q≤100) – the number of queries.

The first line of each query contains one integer n (1≤n≤100) — the number of elements in multiset.

The second line of each query contains n integers s1,s2,…,sn (1≤si≤229) — the description of the multiset. It is guaranteed that all elements of the multiset are powers of two.

Output
For each query print YES if it is possible to obtain the number 2048 in your multiset, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

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
Example
Input
6
4
1024 512 64 512
1
2048
3
64 512 2
2
4096 4
7
2048 2 2048 2048 2048 2048 2048
2
2048 4096
Output
YES
YES
NO
NO
YES
YES

Note
In the first query you can win as follows: choose 512 and 512, and s turns into {1024,64,1024}. Then choose 1024 and 1024, and s turns into {2048,64} and you win.

In the second query s contains 2048 initially.

题意
根据所给的数字集合,判断里面的数字相加是否是2048就可以了
可以先排一下序,因为都是2的幂数,所以可以放心的直接相加就行了

code:

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxx = 1e5;

bool cmp(int x, int y)
{
return x > y;
}
int a[maxx];

int main()
{
int t;
int n;
cin >> t;
while(t --)
{
cin >> n;
int x;
int flag = 0, sum = 0;
for(int i = 0; i < n; i ++) cin >> a[i];
sort(a, a + n, cmp);
for(int i = 0; i < n; i ++)
{
if(a[i] > 2048) continue;
else
{
sum += a[i];
}
if(sum == 2048 || a[i] == 2048)
{
flag = 1;
break;
}

}
if(flag == 1) puts("YES");
else puts("NO");
}

return 0;
}

Perfect Team

You may have already known that a standard ICPC team consists of exactly three members. The perfect team however has more restrictions. A student can have some specialization: coder or mathematician. She/he can have no specialization, but can’t have both at the same time.

So the team is considered perfect if it includes at least one coder, at least one mathematician and it consists of exactly three members.

You are a coach at a very large university and you know that c of your students are coders, m are mathematicians and x have no specialization.

What is the maximum number of full perfect teams you can distribute them into?

Note that some students can be left without a team and each student can be a part of no more than one team.

You are also asked to answer q independent queries.

Input
The first line contains a single integer q (1≤q≤104) — the number of queries.

Each of the next q lines contains three integers c, m and x (0≤c,m,x≤108) — the number of coders, mathematicians and students without any specialization in the university, respectively.

Note that the no student is both coder and mathematician at the same time.

Output
Print q integers — the i-th of them should be the answer to the i query in the order they are given in the input. The answer is the maximum number of full perfect teams you can distribute your students into.

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
Example
Input
6
1 1 1
3 6 0
0 0 0
0 1 1
10 1 10
4 4 1
Output
1
3
0
0
1
3
Note
In the first example here are how teams are formed:

the only team of 1 coder, 1 mathematician and 1 without specialization;
all three teams consist of 1 coder and 2 mathematicians;
no teams can be formed;
no teams can be formed;
one team consists of 1 coder, 1 mathematician and 1 without specialization, the rest aren't able to form any team;
one team consists of 1 coder, 1 mathematician and 1 without specialization, one consists of 2 coders and 1 mathematician and one consists of 1 coder and 2 mathematicians.

题解
这道题重点是判断一下数学家和编译员的人数,如果为0,是肯定组不成的
不为0的话,要判断数学家和编译员的人数之中最小的值和最小能够组成完美队伍的值之间,取最小值

code:

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxx = 1e5;

int main()
{
int c, m, x;//c是程序员,m是数学家,x是无专业人
int t;
cin >> t;
while(t --)
{
cin >> c >> m >> x;
int ans = 0;
if(c == 0 || m == 0)
{
puts("0");
continue;
}
int minx = min(c, m);
int len = (c + m + x) / 3;
ans = min(minx, len);
cout << ans << '\n';
}
return 0;
}

---------------- The End ----------------
0%