実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
3 文字からなる文字列 S が与えられます。S は、1 以上 9 以下の整数 a, b と文字 x を、axb のように順につなげて得られます。
a と b の積を求めてください。
制約
- S の長さは 3
- S の 1 文字目および 3 文字目は 1 以上 9 以下の整数を表す
- S の 2 文字目は
x
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
3x7
出力例 1
21
3 \times 7 = 21 であるので、これを出力します。
入力例 2
9x9
出力例 2
81
入力例 3
1x1
出力例 3
1
Score : 100 points
Problem Statement
You are given a 3-character string S, which is a concatenation of integers a and b between 1 and 9 (inclusive) and the character x in this order: axb.
Find the product of a and b.
Constraints
- The length of S is 3.
- The 1-st and 3-rd characters are digits between 1 and 9 (inclusive).
- The 2-nd character is
x.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
3x7
Sample Output 1
21
We have 3 \times 7 = 21, which should be printed.
Sample Input 2
9x9
Sample Output 2
81
Sample Input 3
1x1
Sample Output 3
1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 150 点
問題文
この問題における 11/22 文字列の定義は C 問題および E 問題と同じです。
文字列 T が以下の条件を全て満たすとき、T を 11/22 文字列 と呼びます。
- |T| は奇数である。ここで、|T| は T の長さを表す。
- 1 文字目から \frac{|T|+1}{2} - 1 文字目までが
1である。 - \frac{|T|+1}{2} 文字目が
/である。 - \frac{|T|+1}{2} + 1 文字目から |T| 文字目までが
2である。
例えば 11/22, 111/222, / は 11/22 文字列ですが、1122, 1/22, 11/2222, 22/11, //2/2/211 はそうではありません。
1, 2, / からなる長さ N の文字列 S が与えられます。S が 11/22 文字列であるか判定してください。
制約
- 1 \leq N \leq 100
- S は
1,2,/からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
S が 11/22 文字列であれば Yes を、そうでなければ No を出力せよ。
入力例 1
5 11/22
出力例 1
Yes
11/22 は問題文の 11/22 文字列の条件を満たします。
入力例 2
1 /
出力例 2
Yes
/ は問題文の 11/22 文字列の条件を満たします。
入力例 3
4 1/22
出力例 3
No
1/22 は問題文の 11/22 文字列の条件を満たしません。
入力例 4
5 22/11
出力例 4
No
Score : 150 points
Problem Statement
The definition of an 11/22 string in this problem is the same as in Problems C and E.
A string T is called an 11/22 string when it satisfies all of the following conditions:
- |T| is odd. Here, |T| denotes the length of T.
- The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all
1. - The (\frac{|T|+1}{2})-th character is
/. - The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all
2.
For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.
Given a string S of length N consisting of 1, 2, and /, determine whether S is an 11/22 string.
Constraints
- 1 \leq N \leq 100
- S is a string of length N consisting of
1,2, and/.
Input
The input is given from Standard Input in the following format:
N S
Output
If S is an 11/22 string, print Yes; otherwise, print No.
Sample Input 1
5 11/22
Sample Output 1
Yes
11/22 satisfies the conditions for an 11/22 string in the problem statement.
Sample Input 2
1 /
Sample Output 2
Yes
/ satisfies the conditions for an 11/22 string.
Sample Input 3
4 1/22
Sample Output 3
No
1/22 does not satisfy the conditions for an 11/22 string.
Sample Input 4
5 22/11
Sample Output 4
No
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
入学試験の受験者が N 人います。
試験の結果、 i 番の受験生は数学で A_i 点、英語で B_i 点を取りました。
試験の合格者は次のように決められます。
- 数学の点が高い方から X 人を合格とする。
- 次に、この時点でまだ合格となっていない受験者のうち、英語の点が高い方から Y 人を合格とする。
- 次に、この時点でまだ合格となっていない受験者のうち、数学と英語の合計点が高い方から Z 人を合格とする。
- ここまでで合格となっていない受験者は、不合格とする。
ただし、 1. から 3. までのどの段階についても、同点であった場合は受験生の番号の小さい方を優先します。入出力例も参照してください。
以上の手順で合格者を決める時、合格となった受験生の番号を小さい方から順に改行区切りで出力してください。
制約
- 入力は全て整数
- 1 \le N \le 1000
- 0 \le X,Y,Z \le N
- 1 \le X+Y+Z \le N
- 0 \le A_i,B_i \le 100
入力
入力は以下の形式で標準入力から与えられる。
N X Y Z A_1 A_2 \dots A_N B_1 B_2 \dots B_N
出力
合格となった受験生の番号を小さい方から順に改行区切りで出力せよ。
入力例 1
6 1 0 2 80 60 80 60 70 70 40 20 50 90 90 80
出力例 1
1 4 5
- まず、数学の点が高い方から 1 人が合格となります。
- 数学の最高点は 80 点で 1 番の受験生と 3 番の受験生が並んでいますが、受験生の番号が小さい方が優先され 1 番の受験生が合格となります。
- 次に、まだ合格となっていない受験者のうち、英語の点が高い方から 0 人が合格となります。
- 明らかに、ここで合格者が増えることはありません。
- 次に、まだ合格となっていない受験者のうち、数学と英語の合計点が高い方から 2 人が合格となります。
- まず、まだ合格となっていない受験者の中で、合計点が 160 点と最も高い 5 番の受験生が合格となります。
- 次に、まだ合格となっていない受験者の中で、合計点が 150 点の 4 番の受験生と 6 番の受験生が並んでいます。受験生の番号の小さい方が優先され、 4 番の受験生が合格となります。
以上より、合格となる受験生の番号は 1,4,5 なので、小さい方から出力してください。
入力例 2
5 2 1 2 0 100 0 100 0 0 0 100 100 0
出力例 2
1 2 3 4 5
全員が合格となることもあります。
入力例 3
15 4 3 2 30 65 20 95 100 45 70 85 20 35 95 50 40 15 85 0 25 45 35 65 70 80 90 40 55 20 20 45 75 100
出力例 3
2 4 5 6 7 8 11 14 15
Score : 200 points
Problem Statement
N examinees took an entrance exam.
The examinee numbered i scored A_i points in math and B_i points in English.
The admissions are determined as follows.
- X examinees with the highest math scores are admitted.
- Then, among the examinees who are not admitted yet, Y examinees with the highest English scores are admitted.
- Then, among the examinees who are not admitted yet, Z examinees with the highest total scores in math and English are admitted.
- Those examinees who are not admitted yet are rejected.
Here, in each of the steps 1. to 3., ties are broken by examinees' numbers: an examinee with the smaller examinee's number is prioritized. See also Sample Input and Output.
Print the examinees' numbers of the admitted examinees determined by the steps above in ascending order, separated by newlines.
Constraints
- All values in input are integers.
- 1 \le N \le 1000
- 0 \le X,Y,Z \le N
- 1 \le X+Y+Z \le N
- 0 \le A_i,B_i \le 100
Input
Input is given from Standard Input in the following format:
N X Y Z A_1 A_2 \dots A_N B_1 B_2 \dots B_N
Output
Print the examinees' number of the admitted examinees in ascending order, separated by newlines.
Sample Input 1
6 1 0 2 80 60 80 60 70 70 40 20 50 90 90 80
Sample Output 1
1 4 5
- First, 1 examinee with the highest math score is admitted.
- Examinee 1 is tied with Examinee 3, scoring the highest 80 points in math, and the tie is broken by the examinees' numbers, so Examinee 1 is admitted.
- Then, among the examinees who are not admitted yet, 0 examinees with the highest English scores are admitted.
- Obviously, it does not affect the admissions.
- Then, among the examinees who are not admitted yet, 2 examinees with the highest total scores in math and English are admitted.
- First, among the examinees who are not admitted yet, Examinee 5 is admitted, scoring the highest total score of 160 points.
- Next, among the examinees who are not admitted yet, Examinee 4 is tied with Examinee 6, scoring a total score of 150 points. The tie is broken by the examinees' numbers, and Examinee 4 is admitted.
Therefore, the examinees' numbers of the admitted examinees are 1, 4, and 5. Print them in ascending order.
Sample Input 2
5 2 1 2 0 100 0 100 0 0 0 100 100 0
Sample Output 2
1 2 3 4 5
All examinees may be admitted.
Sample Input 3
15 4 3 2 30 65 20 95 100 45 70 85 20 35 95 50 40 15 85 0 25 45 35 65 70 80 90 40 55 20 20 45 75 100
Sample Output 3
2 4 5 6 7 8 11 14 15
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
-10^{18} 以上 10^{18} 以下の整数 X が与えられるので、\left\lceil \dfrac{X}{10} \right\rceil を出力してください。
ここで、\left\lceil a \right\rceil は a 以上の整数のうち最小のものを意味します。
制約
- -10^{18} \leq X \leq 10^{18}
- X は整数
入力
入力は以下の形式で標準入力から与えられる。
X
出力
\left\lceil \dfrac{X}{10} \right\rceil を整数として出力せよ。
入力例 1
27
出力例 1
3
\frac{27}{10} = 2.7 以上の整数は 3, 4, 5, \dots です。この中で一番小さい整数は 3 なので、\left \lceil \frac{27}{10} \right \rceil = 3 となります。
入力例 2
-13
出力例 2
-1
\frac{-13}{10} = -1.3 以上の整数は、全ての正整数および 0, -1 です。この中で一番小さい整数は -1 なので、\left \lceil \frac{-13}{10} \right \rceil = -1 となります。
入力例 3
40
出力例 3
4
\frac{40}{10} = 4 以上の整数で一番小さい整数は 4 自身です。
入力例 4
-20
出力例 4
-2
入力例 5
123456789123456789
出力例 5
12345678912345679
Score: 200 points
Problem Statement
Given an integer X between -10^{18} and 10^{18}, inclusive, print \left\lceil \dfrac{X}{10} \right\rceil.
Here, \left\lceil a \right\rceil denotes the smallest integer not less than a.
Constraints
- -10^{18} \leq X \leq 10^{18}
- X is an integer.
Input
The input is given from Standard Input in the following format:
X
Output
Print \left\lceil \dfrac{X}{10} \right\rceil as an integer.
Sample Input 1
27
Sample Output 1
3
The integers not less than \frac{27}{10} = 2.7 are 3, 4, 5, \dots. Among these, the smallest is 3, so \left \lceil \frac{27}{10} \right \rceil = 3.
Sample Input 2
-13
Sample Output 2
-1
The integers not less than \frac{-13}{10} = -1.3 are all positive integers, 0, and -1. Among these, the smallest is -1, so \left \lceil \frac{-13}{10} \right \rceil = -1.
Sample Input 3
40
Sample Output 3
4
The smallest integer not less than \frac{40}{10} = 4 is 4 itself.
Sample Input 4
-20
Sample Output 4
-2
Sample Input 5
123456789123456789
Sample Output 5
12345678912345679
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 匹の鳩がおり、 1 から N までの番号がつけられています。また、 N 個の巣があり、 1 から N までの番号がつけられています。はじめ、鳩 i は巣 i にいます (1\leq i\leq N)。
Q 個のクエリが与えられるので順に処理してください。 クエリは 2 種類あり、以下のいずれかの形式で与えられます。
1 P H: 鳩 P を巣 H に移動させる。2: 複数の鳩がいる巣の個数を出力する。
制約
- 2\leq N\leq 10^6
- 1\leq Q\leq 3\times 10^5
- 1\leq P,H\leq N
- 1 つ目の形式のクエリについて、鳩 P は移動する前に巣 H にいない
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
各クエリは以下の 2 種類のいずれかの形式で与えられる。
1 P H
2
出力
問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。
入力例 1
4 7 2 1 1 2 2 1 3 2 2 1 3 4 2
出力例 1
0 1 1 2
初め、鳩 1,2,3,4 はそれぞれ巣 1,2,3,4 にいます。
- 1 つ目のクエリについて、巣 1,2,3,4 にはそれぞれ 1,1,1,1 匹います。鳩が複数いる巣は存在しないので 0 を出力します。
- 2 つ目のクエリについて、鳩 1 を巣 2 に移動します。
- 3 つ目のクエリについて、巣 1,2,3,4 にはそれぞれ 0,2,1,1 匹います。鳩が複数いる巣は巣 2 の 1 つなので 1 を出力します。
- 4 つ目のクエリについて、鳩 3 を巣 2 に移動します。
- 5 つ目のクエリについて、巣 1,2,3,4 にはそれぞれ 0,3,0,1 匹います。鳩が複数いる巣は巣 2 の 1 つなので 1 を出力します。
- 6 つ目のクエリについて、鳩 3 を巣 4 に移動します。
- 7 つ目のクエリについて、巣 1,2,3,4 にはそれぞれ 0,2,0,2 匹います。鳩が複数いる巣は巣 2,4 の 2 つなので 2 を出力します。
入力例 2
5 10 2 1 4 3 1 4 5 2 1 3 1 2 1 2 3 1 2 5 1 1 3 2
出力例 2
0 1 2 1
Score : 300 points
Problem Statement
There are N pigeons numbered from 1 to N, and there are N nests numbered from 1 to N. Initially, pigeon i is in nest i for 1\leq i\leq N.
You are given Q queries, which you must process in order. There are two types of queries, each given in one of the following formats:
1 P H: Move pigeon P to nest H.2: Output the number of nests that contain more than one pigeon.
Constraints
- 2 \leq N \leq 10^6
- 1 \leq Q \leq 3\times 10^5
- 1 \leq P, H \leq N
- For a query of the first type, pigeon P is not in nest H before the move.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is given in one of the following two formats:
1 P H
2
Output
Print the answer to each query on a new line according to the instructions in the problem statement.
Sample Input 1
4 7 2 1 1 2 2 1 3 2 2 1 3 4 2
Sample Output 1
0 1 1 2
Initially, pigeons 1,2,3,4 are in nests 1,2,3,4, respectively.
- For the 1st query, the counts of pigeons in nests 1,2,3,4 are 1,1,1,1. No nests contain multiple pigeons, output 0.
- For the 2nd query, move pigeon 1 to nest 2.
- For the 3rd query, the counts become 0,2,1,1, respectively. One nest (nest 2) contains multiple pigeons, so output 1.
- For the 4th query, move pigeon 3 to nest 2.
- For the 5th query, the counts become 0,3,0,1, respectively. One nest (nest 2) contains multiple pigeons, so output 1.
- For the 6th query, move pigeon 3 to nest 4.
- For the 7th query, the counts become 0,2,0,2, respectively. Two nests (nests 2 and 4) contain multiple pigeons, so output 2.
Sample Input 2
5 10 2 1 4 3 1 4 5 2 1 3 1 2 1 2 3 1 2 5 1 1 3 2
Sample Output 2
0 1 2 1