ACM队内Rating赛题解报告（六）

CF1041A - Heist

题目描述

There was an electronic store heist last night.

All keyboards which were in the store yesterday were numbered in ascending order from some integer number x. For example, if x=4 and there were 3 keyboards in the store, then the devices had indices 4, 5 and 6, and if x=10 and there were 7 of them then the keyboards had indices 10, 11, 12, 13, 14, 15 and 16.

After the heist, only n keyboards remain, and they have indices a1,a2,…,an. Calculate the minimum possible number of keyboards that have been stolen. The staff remember neither x nor the number of keyboards in the store before the heist.

输入

The first line contains single integer n (1≤n≤1000) — the number of keyboards in the store that remained after the heist.

The second line contains n distinct integers a1,a2,…,an (1≤ai≤10^9^) — the indices of the remaining keyboards. The integers ai are given in arbitrary order and are pairwise distinct.

输出

Print the minimum possible number of keyboards that have been stolen if the staff remember neither x nor the number of keyboards in the store before the heist.

样例

Input

4
10 13 12 8

Output

2

Input

5
7 5 6 4 8

Output

0

注意

In the first example, if x=8 then minimum number of stolen keyboards is equal to 2. The keyboards with indices 9 and 11 were stolen during the heist.

In the second example, if x=4 then nothing was stolen during the heist.

解题思路

题意很简单，某商店发生盗窃案，序号递增的键盘被偷了一部分。

店员即不知道原来有多少键盘，也不知道哪些键盘被偷了。

我们需要根据剩下的键盘序号，判断被偷了多少键盘。

先排序，然后判断是否顺序，若不是顺序，判断差几个数字，即被偷几个键盘。

AC代码

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
	int n;
	int ans = 0;
	int num[1000] = { 0 };

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

	sort(num, num + n);		//从小到大排序一下

	for (int i = 1; i < n; i++)
	{
		if (num[i] != num[i - 1] + 1) //不是顺序
		{
			ans += num[i] - num[i - 1] - 1;	//统计被偷数量
		}
	}

	cout << ans << endl;

	return 0;
}

English单词积累

heist—盗窃

CF1041B - Buying a TV Set

题目描述

Monocarp has decided to buy a new TV set and hang it on the wall in his flat. The wall has enough free space so Monocarp can buy a TV set with screen width not greater than a and screen height not greater than b. Monocarp is also used to TV sets with a certain aspect ratio: formally, if the width of the screen is w, and the height of the screen is h, then the following condition should be met: w / h=x / y.

There are many different TV sets in the shop. Monocarp is sure that for any pair of positive integers w and h there is a TV set with screen width w and height h in the shop.

Monocarp isn’t ready to choose the exact TV set he is going to buy. Firstly he wants to determine the optimal screen resolution. He has decided to try all possible variants of screen size. But he must count the number of pairs of positive integers w and h, beforehand, such that (w≤a), (h≤b) and (w / h=x / y).

In other words, Monocarp wants to determine the number of TV sets having aspect ratio x / y, screen width not exceeding a, and screen height not exceeding b. Two TV sets are considered different if they have different screen width or different screen height.

输入

The first line contains four integers a, b, x, y (1≤a,b,x,y≤10^18^) — the constraints on the screen width and height, and on the aspect ratio.

输出

Print one integer — the number of different variants to choose TV screen width and screen height so that they meet the aforementioned constraints.

样例

Input

17 15 5 3

Output

3

Input

14 16 7 22

Output

0

Input

4 2 6 4

Output

1

Input

1000000000000000000 1000000000000000000 999999866000004473 999999822000007597

Output

1000000063

注意

In the first example, there are 3 possible variants: (5,3), (10,6), (15,9).

In the second example, there is no TV set meeting the constraints.

In the third example, there is only one variant: (3,2).

解题思路

题意很简单，想买一台电视挂在墙上。

商店里有任意多种宽度和高度为w和h的电视。

要求电视宽度不超过a，高度不超过b。并且满足长宽比：

w / h = x / y

求符合上述条件的电视有多少种。

马上就可以想到，答案应该是取 a / x 和 b / y 中的最小值。

此外，还需要考虑到先把x / y进行约分。即让x和y分别除以它们的最大公约数。

AC代码

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

long long gcd(long long a, long long b)
{
	return a % b != 0 ? gcd(b, a % b) : b;
}

int main()
{
	long long a, b, x, y;
	long long tmp;

	cin >> a >> b >> x >> y;	//最大宽度 最大高度 比例x y

	tmp = gcd(x, y);	//求x和y的最大公约数，用于化简x / y
    
    //化简
	x /= tmp;	
	y /= tmp;

    //分别计算
	a /= x;
	b /= y;

    //取最小值
	cout << (a < b ? a : b) << endl;

	return 0;
}

English单词积累

aspect ratio—纵横比

aforementioned constraints—上述限制条件

CF1041C - Coffee Break

题目描述

Recently Monocarp got a job. His working day lasts exactly m minutes. During work, Monocarp wants to drink coffee at certain moments: there are n minutes a1,a2,…,an, when he is able and willing to take a coffee break (for the sake of simplicity let’s consider that each coffee break lasts exactly one minute).

However, Monocarp’s boss doesn’t like when Monocarp takes his coffee breaks too often. So for the given coffee break that is going to be on minute ai, Monocarp must choose the day in which he will drink coffee during the said minute, so that every day at least d minutes pass between any two coffee breaks. Monocarp also wants to take these n coffee breaks in a minimum possible number of working days (he doesn’t count days when he is not at work, and he doesn’t take coffee breaks on such days). Take into account that more than d minutes pass between the end of any working day and the start of the following working day.

For each of the n given minutes determine the day, during which Monocarp should take a coffee break in this minute. You have to minimize the number of days spent.

输入

The first line contains three integers n, m, d (1≤n≤2⋅10^5^,n≤m≤10^9^,1≤d≤m) — the number of coffee breaks Monocarp wants to have, the length of each working day, and the minimum number of minutes between any two consecutive coffee breaks.

The second line contains n distinct integers a1,a2,…,an (1≤ai≤m), where ai is some minute when Monocarp wants to have a coffee break.

输出

In the first line, write the minimum number of days required to make a coffee break in each of the n given minutes.

In the second line, print n space separated integers. The ii-th of integers should be the index of the day during which Monocarp should have a coffee break at minute ai. Days are numbered from 1. If there are multiple optimal solutions, you may print any of them.

样例

Input

4 5 3
3 5 1 2

Output

3
3 1 1 2 

Input

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

Output

2
2 1 1 2 2 1 2 1 1 2 

注意

In the first example, Monocarp can take two coffee breaks during the first day (during minutes 1 and 5, 3 minutes will pass between these breaks). One break during the second day (at minute 2), and one break during the third day (at minute 3).

In the second example, Monocarp can determine the day of the break as follows: if the minute when he wants to take a break is odd, then this break is on the first day, if it is even, then this break is on the second day.

解题思路

AC代码

English单词积累

CF1041D - Glider

CF1041E - Tree Reconstruction

CF1041F - Ray in the tube