CF991A - If at first you don’t succeed…

题目描述

Each student eagerly awaits the day he would pass the exams successfully. Thus, Vasya was ready to celebrate, but, alas, he didn’t pass it. However, many of Vasya’s fellow students from the same group were more successful and celebrated after the exam.

Some of them celebrated in the BugDonalds restaurant, some of them — in the BeaverKing restaurant, the most successful ones were fast enough to celebrate in both of restaurants. Students which didn’t pass the exam didn’t celebrate in any of those restaurants and elected to stay home to prepare for their reexamination. However, this quickly bored Vasya and he started checking celebration photos on the Kilogramm. He found out that, in total, BugDonalds was visited by A students, BeaverKing — by B students and C students visited both restaurants. Vasya also knows that there are N students in his group.

Based on this info, Vasya wants to determine either if his data contradicts itself or, if it doesn’t, how many students in his group didn’t pass the exam. Can you help him so he won’t waste his valuable preparation time?

输入

The first line contains four integers — A, B, C and N (0≤A,B,C,N≤100).

输出

If a distribution of N students exists in which A students visited BugDonalds, B — BeaverKing, C — both of the restaurants and at least one student is left home (it is known that Vasya didn’t pass the exam and stayed at home), output one integer — amount of students (including Vasya) who did not pass the exam.

If such a distribution does not exist and Vasya made a mistake while determining the numbers A, B, C or N (as in samples 2 and 3), output −1.

样例

Input

1
10 10 5 20

Output

1
5

Input

1
2 2 0 4

Output

1
-1

Input

1
2 2 2 1

Output

1
-1

注意

The first sample describes following situation: 5 only visited BugDonalds, 5 students only visited BeaverKing, 5 visited both of them and 5 students (including Vasya) didn’t pass the exam.

In the second sample 2 students only visited BugDonalds and 2 only visited BeaverKing, but that means all 4 students in group passed the exam which contradicts the fact that Vasya didn’t pass meaning that this situation is impossible.

The third sample describes a situation where 2 students visited BugDonalds but the group has only 1 which makes it clearly impossible.

解题思路

题目很长,但是只要理解题意后就会发现题目很简单。

共有N个人,有A个人被邀请去BugDonalds餐厅,有B个人被邀请去BeaverKing餐厅,其中同时被邀请去两个餐厅的人数是C。

1

题目让判断A、B、C、N是否矛盾,如果矛盾输出-1,否则输出不及格的人数(没去任何一个餐馆的人数)。

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()
{
//不存在输入-1 存在输入多少不及格的
int A, B, C, n; //共n人,A人去一个餐馆,B人去另一个餐馆,其中C人两个餐馆都去

cin >> A >> B >> C >> n;

//根据图可知:(A + B - C)人去了餐馆
//记得判断C应该小于A和B(这里刚开始忽略了 WA了2次)
if (n - (A + B - C) < 1 || C > A || C > B)
{
cout << -1;
}
else
{
cout << n - (A + B - C) << endl; //输出没去餐馆的人数,即不及格的人数
}

return 0;
}

English单词积累

awaits—等待

contradicts—相矛盾

CF991B - Getting an A

题目描述

Translator’s note: in Russia’s most widespread grading system, there are four grades: 5, 4, 3, 2, the higher the better, roughly corresponding to A, B, C and F respectively in American grading system.

The term is coming to an end and students start thinking about their grades. Today, a professor told his students that the grades for his course would be given out automatically — he would calculate the simple average (arithmetic mean) of all grades given out for lab works this term and round to the nearest integer. The rounding would be done in favour of the student — 4.5 would be rounded up to 5 (as in example 3), but 4.4 would be rounded down to 4.

This does not bode well for Vasya who didn’t think those lab works would influence anything, so he may receive a grade worse than 5 (maybe even the dreaded 2). However, the professor allowed him to redo some of his works of Vasya’s choosing to increase his average grade. Vasya wants to redo as few lab works as possible in order to get 5 for the course. Of course, Vasya will get 5 for the lab works he chooses to redo.

Help Vasya — calculate the minimum amount of lab works Vasya has to redo.

输入

The first line contains a single integer n — the number of Vasya’s grades (1≤n≤100).

The second line contains n integers from 2 to 5 — Vasya’s grades for his lab works.

输出

Output a single integer — the minimum amount of lab works that Vasya has to redo. It can be shown that Vasya can always redo enough lab works to get a 5.

样例

Input

1
2
3
4 4 4

Output

1
2

Input

1
2
4
5 4 5 5

Output

1
0

Input

1
2
4
5 3 3 5

Output

1
1

注意

In the first sample, it is enough to redo two lab works to make two 4s into 5s.

In the second sample, Vasya’s average is already 4.75 so he doesn’t have to redo anything to get a 5.

In the second sample Vasya has to redo one lab work to get rid of one of the 3s, that will make the average exactly 4.5 so the final grade would be 5.

解题思路

这道题目很简单,有n门课程评分范围在3-5。

重做的课程可以达到5分,求最少重做多少门课程后平均分可以达到5。

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
#include <iostream>

using namespace std;

int main()
{
int n;
int cnt = 0; //需要重做的课程
double sum = 0;
int grade[100] = { 0 };

cin >> n;

for (int i = 0; i < n; i++)
{
cin >> grade[i];
sum += grade[i];
}

if (int(sum / n + 0.5) == 5) //已经满足要求,无需重做
{
cout << cnt;
}
else
{
sort(grade, grade + n); //排序,默认重做分数最低的。
for (int i = 0; i < n; i++) //遍历所有课程,中途满足条件就结束
{
sum = 0;
grade[i] = 5;
cnt++;
for (int j = 0; j < n; j++) //每次重做一门课程后计算是否满足要求
{
sum += grade[j];
}

if (int(sum / n + 0.5) == 5) //满足要求,输出答案,结束。
{
cout << cnt;
return 0;
}
}
}

return 0;
}

English单词积累

grading system—评分系统

arithmetic mean—算术平均数

bode—预示

dreaded—可怕的

CF991C - Candies

题目描述

After passing a test, Vasya got himself a box of n candies. He decided to eat an equal amount of candies each morning until there are no more candies. However, Petya also noticed the box and decided to get some candies for himself.

This means the process of eating candies is the following: in the beginning Vasya chooses a single integer k, same for all days. After that, in the morning he eats k candies from the box (if there are less than k candies in the box, he eats them all), then in the evening Petya eats 10% of the candies remaining in the box. If there are still candies left in the box, the process repeats — next day Vasya eats k candies again, and Petya — 10% of the candies left in a box, and so on.

If the amount of candies in the box is not divisible by 10, Petya rounds the amount he takes from the box down. For example, if there were 97 candies in the box, Petya would eat only 9 of them. In particular, if there are less than 10 candies in a box, Petya won’t eat any at all.

Your task is to find out the minimal amount of k that can be chosen by Vasya so that he would eat at least half of the n candies he initially got. Note that the number k must be integer.

输入

The first line contains a single integer n (1≤n≤10^18^) — the initial amount of candies in the box.

输出

Output a single integer — the minimal amount of k that would allow Vasya to eat at least half of candies he got.

样例

Input

1
68

Output

1
3

注意

In the sample, the amount of candies, with k=3, would change in the following way (Vasya eats first):

68→65→59→56→51→48→44→41→37→34→31→28→26→23→21→18→17→14→13→10→9→6→6→3→3→068→65→59→56→51→48→44→41→37→34→31→28→26→23→21→18→17→14→13→10→9→6→6→3→3→0.

In total, Vasya would eat 39 candies, while Petya — 29.

解题思路

A每天早上吃k个(不足k全吃)糖果,B每天晚上吃10%(舍弃小数 少于10个不吃)个糖果。

共有n个糖果。求最小的k,满足A至少吃一半的糖果。

数字范围很大,暴力模拟肯定会超时。只能通过二分答案解决。

在可能的范围内寻找最优解,一般使用二分查找或二分答案。

二分区间即答案区间:1-n,简单的套路题。

写标准的二分操作+题意模拟就可以AC。

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
#include <iostream>

using namespace std;

long long calc(long long n, long long k); //按照题目模拟计算吃多少糖

int main()
{
long long n;
long long l, r, mid;

cin >> n;

//确定二分答案的区间
l = 1;
r = n;

while (l < r)
{
mid = (l + r) / 2;

if (calc(n, mid) >= (n + 1) / 2) //满足题意,右区间缩小继续找更小的答案
{
r = mid;
}
else
{
l = mid + 1; //不满足题意,左区间缩小,继续向右找答案
}
}

cout << l << endl;

return 0;
}


long long calc(long long n, long long k)
{
long long now = n;
long long sum = 0;

while (now)
{
if (now <= k) //剩余的糖小于k
{
sum += now; //全部吃掉,循环结束
break;
}

now -= k; //早上吃k
sum += k;
now -= now / 10; //晚上吃10%
}

return sum;
}

English单词积累

CF991D - Bishwock

CF991E - Bus Number

CF991F - Concise and clear