Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
あなたは、室温が 30 度以上のとき、またそのときに限り、冷房の電源を入れます。
今の室温は X 度です。冷房の電源を入れますか？
制約
- -40 \leq X \leq 40
- X は整数である。
入力
入力は以下の形式で標準入力から与えられる。
X
出力
冷房の電源を入れるならば Yes、入れないならば No を出力せよ。
入力例 1
25
出力例 1
No
入力例 2
30
出力例 2
Yes
Score : 100 points
Problem Statement
You will turn on the air conditioner if, and only if, the temperature of the room is 30 degrees Celsius or above.
The current temperature of the room is X degrees Celsius. Will you turn on the air conditioner?
Constraints
- -40 \leq X \leq 40
- X is an integer.
Input
Input is given from Standard Input in the following format:
X
Output
Print Yes if you will turn on the air conditioner; print No otherwise.
Sample Input 1
25
Sample Output 1
No
Sample Input 2
30
Sample Output 2
Yes
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
2 次元平面上に N 個の点があります。 i 個目の点の座標は (X_i,Y_i) です。
これらのうち、原点からの距離が D 以下であるような点は何個ありますか？
なお、座標 (p,q) にある点と原点の距離は \sqrt{p^2+q^2} で表されます。
制約
- 1 \leq N \leq 2\times 10^5
- 0 \leq D \leq 2\times 10^5
- |X_i|,|Y_i| \leq 2\times 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N D X_1 Y_1 \vdots X_N Y_N
出力
原点からの距離が D 以下であるような点の個数を整数で出力せよ。
入力例 1
4 5 0 5 -2 4 3 4 4 -4
出力例 1
3
それぞれの点の原点からの距離は
- \sqrt{0^2+5^2}=5
- \sqrt{(-2)^2+4^2}=4.472\ldots
- \sqrt{3^2+4^2}=5
- \sqrt{4^2+(-4)^2}=5.656\ldots
となります。したがって、原点からの距離が 5 以下であるような点は 3 個です。
入力例 2
12 3 1 1 1 1 1 1 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
出力例 2
7
同じ座標に複数の点があることがあります。
入力例 3
20 100000 14309 -32939 -56855 100340 151364 25430 103789 -113141 147404 -136977 -37006 -30929 188810 -49557 13419 70401 -88280 165170 -196399 137941 -176527 -61904 46659 115261 -153551 114185 98784 -6820 94111 -86268 -30401 61477 -55056 7872 5901 -163796 138819 -185986 -69848 -96669
出力例 3
6
Score : 200 points
Problem Statement
We have N points in the two-dimensional plane. The coordinates of the i-th point are (X_i,Y_i).
Among them, we are looking for the points such that the distance from the origin is at most D. How many such points are there?
We remind you that the distance between the origin and the point (p, q) can be represented as \sqrt{p^2+q^2}.
Constraints
- 1 \leq N \leq 2\times 10^5
- 0 \leq D \leq 2\times 10^5
- |X_i|,|Y_i| \leq 2\times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N D X_1 Y_1 \vdots X_N Y_N
Output
Print an integer representing the number of points such that the distance from the origin is at most D.
Sample Input 1
4 5 0 5 -2 4 3 4 4 -4
Sample Output 1
3
The distance between the origin and each of the given points is as follows:
- \sqrt{0^2+5^2}=5
- \sqrt{(-2)^2+4^2}=4.472\ldots
- \sqrt{3^2+4^2}=5
- \sqrt{4^2+(-4)^2}=5.656\ldots
Thus, we have three points such that the distance from the origin is at most 5.
Sample Input 2
12 3 1 1 1 1 1 1 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
Sample Output 2
7
Multiple points may exist at the same coordinates.
Sample Input 3
20 100000 14309 -32939 -56855 100340 151364 25430 103789 -113141 147404 -136977 -37006 -30929 188810 -49557 13419 70401 -88280 165170 -196399 137941 -176527 -61904 46659 115261 -153551 114185 98784 -6820 94111 -86268 -30401 61477 -55056 7872 5901 -163796 138819 -185986 -69848 -96669
Sample Output 3
6
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
高橋君は K の倍数と 7 が好きです。
7,77,777,\ldots という数列の中に初めて K の倍数が登場するのは何項目ですか？
存在しない場合は代わりに -1 を出力してください。
制約
- 1 \leq K \leq 10^6
- K は整数である。
入力
入力は以下の形式で標準入力から与えられる。
K
出力
答えを整数として出力せよ。
入力例 1
101
出力例 1
4
7,77,777 は 101 の倍数ではありませんが、7777 は 101 の倍数です。
入力例 2
2
出力例 2
-1
数列の値は全て奇数なので、2 の倍数が登場することはありません。
入力例 3
999983
出力例 3
999982
Score : 300 points
Problem Statement
Takahashi loves the number 7 and multiples of K.
Where is the first occurrence of a multiple of K in the sequence 7,77,777,\ldots? (Also see Output and Sample Input/Output below.)
If the sequence contains no multiples of K, print -1 instead.
Constraints
- 1 \leq K \leq 10^6
- K is an integer.
Input
Input is given from Standard Input in the following format:
K
Output
Print an integer representing the position of the first occurrence of a multiple of K. (For example, if the first occurrence is the fourth element of the sequence, print 4.)
Sample Input 1
101
Sample Output 1
4
None of 7, 77, and 777 is a multiple of 101, but 7777 is.
Sample Input 2
2
Sample Output 2
-1
All elements in the sequence are odd numbers; there are no multiples of 2.
Sample Input 3
999983
Sample Output 3
999982
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
祭壇に、左から右へと一列に並ぶ N 個の石が祀られています。左から i 個目 (1 \leq i \leq N) の石の色は文字 c_i として与えられ、c_i が R のとき赤、W のとき白です。
あなたは、以下の二種の操作を任意の順に何度でも行うことができます。
- 石を 2 個選び (隣り合っていなくてもよい)、それらを入れ替える。
- 石を 1 個選び、その石の色を変える (赤なら白に、白なら赤に)。
占い師によると、赤い石の左隣に置かれた白い石は災いを招きます。そのような白い石がない状態に至るには、最小で何回の操作が必要でしょうか。
制約
- 2 \leq N \leq 200000
- c_i は
RまたはW
入力
入力は以下の形式で標準入力から与えられる。
N
c_{1}c_{2}...c_{N}
出力
必要な最小の操作回数を表す整数を出力せよ。
入力例 1
4 WWRR
出力例 1
2
例えば、以下の 2 回の操作で目的を達成できます。
- 左から 1 番目の石と左から 3 番目の石を入れ替え、
RWWRとする。 - 左から 4 番目の石の色を変え、
RWWWとする。
入力例 2
2 RR
出力例 2
0
一度も操作を行う必要がない可能性もあります。
入力例 3
8 WRWWRWRR
出力例 3
3
Score : 400 points
Problem Statement
An altar enshrines N stones arranged in a row from left to right. The color of the i-th stone from the left (1 \leq i \leq N) is given to you as a character c_i; R stands for red and W stands for white.
You can do the following two kinds of operations any number of times in any order:
- Choose two stones (not necessarily adjacent) and swap them.
- Choose one stone and change its color (from red to white and vice versa).
According to a fortune-teller, a white stone placed to the immediate left of a red stone will bring a disaster. At least how many operations are needed to reach a situation without such a white stone?
Constraints
- 2 \leq N \leq 200000
- c_i is
RorW.
Input
Input is given from Standard Input in the following format:
N
c_{1}c_{2}...c_{N}
Output
Print an integer representing the minimum number of operations needed.
Sample Input 1
4 WWRR
Sample Output 1
2
For example, the two operations below will achieve the objective.
- Swap the 1-st and 3-rd stones from the left, resulting in
RWWR. - Change the color of the 4-th stone from the left, resulting in
RWWW.
Sample Input 2
2 RR
Sample Output 2
0
It can be the case that no operation is needed.
Sample Input 3
8 WRWWRWRR
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
丸太が N 本あり、それぞれ長さは A_1,A_2,\cdots,A_N です。
これらの丸太を合計 K 回まで切ることができます。 長さ L の丸太を片端から t (0<t<L) の位置で切ると、長さ t,L-t の丸太に分かれます。
丸太を合計 K 回まで切った後最も長い丸太の長さが最小でいくつになるか求め、小数点以下を切り上げた値を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \cdots A_N
出力
答えとなる整数を出力せよ。
入力例 1
2 3 7 9
出力例 1
4
- まず、長さ 7 の丸太を片端から 3.5 の位置で切り、長さ 3.5 の丸太二本に分けます。
- 次に、長さ 9 の丸太を片端から 3 の位置で切り、長さ 3 と 6 の丸太に分けます。
- 最後に、長さ 6 の丸太を片端から 3.3 の位置で切り、長さ 3.3 と 2.7 の丸太に分けます。
すると、最も長い丸太の長さは 3.5 になります。これが最小なので、小数点以下を切り上げた 4 を出力します。
入力例 2
3 0 3 4 5
出力例 2
5
入力例 3
10 10 158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202
出力例 3
292638192
Score : 500 points
Problem Statement
We have N logs of lengths A_1,A_2,\cdots A_N.
We can cut these logs at most K times in total. When a log of length L is cut at a point whose distance from an end of the log is t (0<t<L), it becomes two logs of lengths t and L-t.
Find the shortest possible length of the longest log after at most K cuts, and print it after rounding up to an integer.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \cdots A_N
Output
Print an integer representing the answer.
Sample Input 1
2 3 7 9
Sample Output 1
4
- First, we will cut the log of length 7 at a point whose distance from an end of the log is 3.5, resulting in two logs of length 3.5 each.
- Next, we will cut the log of length 9 at a point whose distance from an end of the log is 3, resulting in two logs of length 3 and 6.
- Lastly, we will cut the log of length 6 at a point whose distance from an end of the log is 3.3, resulting in two logs of length 3.3 and 2.7.
In this case, the longest length of a log will be 3.5, which is the shortest possible result. After rounding up to an integer, the output should be 4.
Sample Input 2
3 0 3 4 5
Sample Output 2
5
Sample Input 3
10 10 158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202
Sample Output 3
292638192
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 個の色の付いた玉が左右一列に並んでおり、左から i 番目の玉の色は c_i です。
クエリが Q 個与えられます。i 番目のクエリでは、左から l_i 番目から r_i 番目までにある玉の色の種類数を答えてください。
制約
- 1\leq N,Q \leq 5 \times 10^5
- 1\leq c_i \leq N
- 1\leq l_i \leq r_i \leq N
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N Q c_1 c_2 \cdots c_N l_1 r_1 l_2 r_2 : l_Q r_Q
出力
Q 行出力せよ。i 行目には、i 番目のクエリに対する答えを出力せよ。
入力例 1
4 3 1 2 1 3 1 3 2 4 3 3
出力例 1
2 3 1
- 1,2,3 番目の玉の色は 1,2,1 で、色 1,2 の 2 種類があります。
- 2,3,4 番目の玉の色は 2,1,3 で、色 1,2,3 の 3 種類があります。
- 3 番目の玉の色は 1 で、色 1 の 1 種類があります。
入力例 2
10 10 2 5 6 5 2 1 7 9 7 2 5 5 2 4 6 7 2 2 7 8 7 9 1 8 6 9 8 10 6 8
出力例 2
1 2 2 1 2 2 6 3 3 3
Score : 600 points
Problem Statement
We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.
You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?
Constraints
- 1\leq N,Q \leq 5 \times 10^5
- 1\leq c_i \leq N
- 1\leq l_i \leq r_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q c_1 c_2 \cdots c_N l_1 r_1 l_2 r_2 : l_Q r_Q
Output
Print Q lines. The i-th line should contain the response to the i-th query.
Sample Input 1
4 3 1 2 1 3 1 3 2 4 3 3
Sample Output 1
2 3 1
- The 1-st, 2-nd, and 3-rd balls from the left have the colors 1, 2, and 1 - two different colors.
- The 2-st, 3-rd, and 4-th balls from the left have the colors 2, 1, and 3 - three different colors.
- The 3-rd ball from the left has the color 1 - just one color.
Sample Input 2
10 10 2 5 6 5 2 1 7 9 7 2 5 5 2 4 6 7 2 2 7 8 7 9 1 8 6 9 8 10 6 8
Sample Output 2
1 2 2 1 2 2 6 3 3 3