CF1047A - Little C Loves 3 I

题目描述

Little C loves number «3» very much. He loves all things about it.

Now he has a positive integer n. He wants to split n into 3 positive integers a,b,c such that a+b+c=n and none of the 3 integers is a multiple of 3. Help him to find a solution.

输入

A single line containing one integer n (3≤n≤10^9^) — the integer Little C has.

输出

Print 3 positive integers a,b,c in a single line, such that a+b+c=n and none of them is a multiple of 3.

It can be proved that there is at least one solution. If there are multiple solutions, print any of them.

样例

Input

1
3

Output

1
1 1 1

Input

1
233

Output

1
77 77 79

注意

解题思路

应该是最简单的A题了,题目很短。

给定一个数字n,将他拆分为3个数字a, b, c,满足a + b + c = n。

并且a、b、c均不为3的倍数,求这三个数。

思路很清晰:如果这个数是3的倍数,只要令a和b都为1,则c一定不是3的倍数。

如果这个数不是3的倍数,这个数减去3依旧不是3的倍数,则令a和b分别为1和3。

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

using namespace std;

int main()
{
int n;
int a, b, c;

cin >> n;

if (n % 3 == 0) //如果是3的倍数
{
a = 1;
b = 1;
c = n - a - b; //a和b均为1,c - 2 一定不是3的倍数
}
else
{
a = 1;
b = 2;
c = n - a - b; //a为1,b为2,c - 3 依旧不是3的倍数
}

cout << a << " " << b << " " << c << endl;

return 0;
}

English单词积累

multiple—倍数;多种多样的

CF1047B - Cover Points

题目描述

There are n points on the plane, (x1,y1),(x2,y2),…,(xn,yn).

You need to place an isosceles triangle with two sides on the coordinate axis to cover all points (a point is covered if it lies inside the triangle or on the side of the triangle). Calculate the minimum length of the shorter side of the triangle.

输入

First line contains one integer n (1≤n≤10^5^).

Each of the next n lines contains two integers xi and yi (1≤xi,yi≤10^9^).

输出

Print the minimum length of the shorter side of the triangle. It can be proved that it’s always an integer.

样例

Input

1
2
3
4
3
1 1
1 2
2 1

Output

1
3

Input

1
2
3
4
5
4
1 1
1 2
2 1
2 2

Output

1
4

注意

解题思路

题目很短, 根据题意,坐标轴上有n个点,并且有一个两条边在坐标轴上的等腰三角形。

我们需要求这个三角形最短边的最小长度,这个三角形必须覆盖所有的点。

这个三角形一定是一个等腰直角三角形。

坐标轴上的点一定过y = -x + b,即b = x + y。

求最短边最小长度即求x + y 的最大值。

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

using namespace std;

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

cin >> n;

while (n--)
{
int x, y;

scanf("%d%d", &x, &y);

ans = x + y > ans ? x + y : ans; //求所有点中x + y的最大值
}

cout << ans << endl;

return 0;
}

English单词积累

plane—飞机;平面

isosceles—等边

CF1047C - Enlarge GCD

题目描述

Mr. F has n positive integers, a1,a2,…,an.

He thinks the greatest common divisor of these integers is too small. So he wants to enlarge it by removing some of the integers.

But this problem is too simple for him, so he does not want to do it by himself. If you help him, he will give you some scores in reward.

Your task is to calculate the minimum number of integers you need to remove so that the greatest common divisor of the remaining integers is bigger than that of all integers.

输入

The first line contains an integer n (2≤n≤3⋅10^5^) — the number of integers Mr. F has.

The second line contains n integers, a1,a2,…,an (1≤ai≤1.5⋅10^7^).

输出

Print an integer — the minimum number of integers you need to remove so that the greatest common divisor of the remaining integers is bigger than that of all integers.

You should not remove all of the integers.

If there is no solution, print «-1» (without quotes).

样例

Input

1
2
3
1 2 4

Output

1
1

Input

1
2
4
6 9 15 30

Output

1
2

Input

1
2
3
1 1 1

Output

1
-1

注意

In the first example, the greatest common divisor is 1 in the beginning. You can remove 1 so that the greatest common divisor is enlarged to 2. The answer is 1.

In the second example, the greatest common divisor is 3 in the beginning. You can remove 6 and 9 so that the greatest common divisor is enlarged to 15. There is no solution which removes only one integer. So the answer is 2.

In the third example, there is no solution to enlarge the greatest common divisor. So the answer is −1.

解题思路

题意很简单,给出n个数,除去其中几个数字,使剩余数字的最大公约数最大。

暴力肯定不行,一定会超时。比赛时也没有想到什么好的优化方法。

AC代码

English单词积累

CF1047D - Little C Loves 3 II

CF1047E - Region Separation