Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
体力が A の敵がいます。あなたは、1 回攻撃をすることで敵の体力を B 減らすことが出来ます。
敵の体力を 0 以下にするためには、最小で何回攻撃をする必要があるでしょうか？
制約
- 1 \le A,B \le 10^{18}
- A, B は整数である。
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
入力例 1
7 3
出力例 1
3
3 回攻撃すると敵の体力が -2 となります。
2 回攻撃しただけでは敵の体力は 1 であるため、3 回攻撃する必要があります。
入力例 2
123456789123456789 987654321
出力例 2
124999999
入力例 3
999999999999999998 2
出力例 3
499999999999999999
Score : 100 points
Problem Statement
There is an enemy with stamina A. Every time you attack the enemy, its stamina reduces by B.
At least how many times do you need to attack the enemy to make its stamina 0 or less?
Constraints
- 1 \le A,B \le 10^{18}
- A and B are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print the answer.
Sample Input 1
7 3
Sample Output 1
3
Attacking three times make the enemy's stamina -2.
Attacking only twice makes the stamina 1, so you need to attack it three times.
Sample Input 2
123456789123456789 987654321
Sample Output 2
124999999
Sample Input 3
999999999999999998 2
Sample Output 3
499999999999999999
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
8 個の整数 S_1,S_2,\dots,S_8 が与えられます。
以下の 3 つの条件が全て満たされるならば Yes を、そうでないならば No を出力してください。
- 数列 (S_1,S_2,\dots,S_8) は広義単調増加である。すなわち、S_1 \leq S_2 \leq \dots \leq S_8 である。
- S_1,S_2,\dots,S_8 は全て 100 以上 675 以下である。
- S_1,S_2,\dots,S_8 は全て 25 の倍数である。
制約
- 0\leq S_i \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
S_1 S_2 \dots S_8
出力
答えを出力せよ。
入力例 1
125 175 250 300 400 525 600 650
出力例 1
Yes
3 つの条件を全て満たしています。
入力例 2
100 250 300 400 325 575 625 675
出力例 2
No
S_4 > S_5 であるため、1 つ目の条件を満たしていません。
入力例 3
0 23 24 145 301 413 631 632
出力例 3
No
2 つ目の条件と 3 つ目の条件を満たしていません。
Score : 100 points
Problem Statement
Given eight integers S_1,S_2,\dots, and S_8,
print Yes if they satisfy all of the following three conditions, and No otherwise.
- The sequence (S_1,S_2,\dots,S_8) is monotonically non-decreasing. In other words, S_1 \leq S_2 \leq \dots \leq S_8.
- S_1,S_2,\dots, and S_8 are all between 100 and 675, inclusive.
- S_1,S_2,\dots, and S_8 are all multiples of 25.
Constraints
- 0\leq S_i \leq 1000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
S_1 S_2 \dots S_8
Output
Print the answer.
Sample Input 1
125 175 250 300 400 525 600 650
Sample Output 1
Yes
They satisfy all of the three conditions.
Sample Input 2
100 250 300 400 325 575 625 675
Sample Output 2
No
They violate the first condition because S_4 > S_5.
Sample Input 3
0 23 24 145 301 413 631 632
Sample Output 3
No
They violate the second and third conditions.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
2N 人の人が横一列に並んでおり、左から i 番目の人は色 A_i の服を着ています。ここで、服の色は 1 から N の N 色であり、それぞれの色についてちょうど 2 人の人がその色の服を着ています。
i=1,2,\ldots,N のうち、以下の条件を満たすものは何通りあるか求めてください。
- 色 i の服を着た二人の人の間にはちょうど一人いる。
制約
- 2\leq N\leq 100
- 1\leq A_i \leq N
- A には 1 以上 N 以下の整数全てがそれぞれ 2 個ずつ含まれる
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \ldots A_{2N}
出力
答えを出力せよ。
入力例 1
3 1 2 1 3 2 3
出力例 1
2
条件を満たす i は 1 と 3 の 2 個です。
実際、色 1 の服を着ているのは左から 1 番目の人と左から 3 番目の人で、間にちょうど一人います。
入力例 2
2 1 1 2 2
出力例 2
0
条件を満たす i が存在しない場合もあります。
入力例 3
4 4 3 2 3 2 1 4 1
出力例 3
3
Score : 150 points
Problem Statement
There are 2N people standing in a row, and the person at the i-th position from the left is wearing clothes of color A_i. Here, the clothes have N colors from 1 to N, and exactly two people are wearing clothes of each color.
Find how many of the integers i=1,2,\ldots,N satisfy the following condition:
- There is exactly one person between the two people wearing clothes of color i.
Constraints
- 2 \leq N \leq 100
- 1 \leq A_i \leq N
- Each integer from 1 through N appears exactly twice in A.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_{2N}
Output
Print the answer.
Sample Input 1
3 1 2 1 3 2 3
Sample Output 1
2
There are two values of i that satisfy the condition: 1 and 3.
In fact, the people wearing clothes of color 1 are at the 1st and 3rd positions from the left, with exactly one person in between.
Sample Input 2
2 1 1 2 2
Sample Output 2
0
There may be no i that satisfies the condition.
Sample Input 3
4 4 3 2 3 2 1 4 1
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君は電卓を持っています。電卓には最初 1 が表示されています。
高橋君は電卓に対して N 回操作を行います。
i 回目 (1\leq i\leq N) の操作では、その時点で画面に表示されている数に正の整数 A_i をかけます。
しかし、電卓には K 桁までしか表示できないため、計算結果が (K+1) 桁以上になる場合、代わりに 1 が画面に表示されます。
そうでない場合は正しく計算結果が表示されます。
N 回の操作の後に電卓に表示されている数を求めてください。
制約
- 1 \leq N \leq 100
- 1 \leq K \leq 18
- 1 \leq A_i < 10^K
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
N 回の操作の後に電卓に表示されている数を出力せよ。
入力例 1
5 2 7 13 3 2 5
出力例 1
10
今回電卓は 2 桁まで表示することができ、最初 1 が表示されています。これに対して、次のように高橋君は操作を行います。
- 1 回目の操作で、7 をかけます。1\times 7=7 であり、電卓には 7 が表示されます。
- 2 回目の操作で、13 をかけます。7\times 13=91 であり、電卓には 91 が表示されます。
- 3 回目の操作で、3 をかけます。91\times 3=273 であり、3 桁になってしまうため、電卓には 1 が表示されます。
- 4 回目の操作で、2 をかけます。1\times 2=2 であり、電卓には 2 が表示されます。
- 5 回目の操作で、5 をかけます。2\times 5=10 であり、電卓には 10 が表示されます。
入力例 2
2 1 2 5
出力例 2
1
Score : 200 points
Problem Statement
Takahashi has a calculator that initially displays 1.
He will perform N operations on the calculator.
In the i-th operation (1 \leq i \leq N), he multiplies the currently displayed number by a positive integer A_i.
However, the calculator can display at most K digits.
If the result of the multiplication has (K+1) or more digits, the display shows 1 instead; otherwise, the result is shown correctly.
Find the number showing on the calculator after the N operations.
Constraints
- 1 \leq N \leq 100
- 1 \leq K \leq 18
- 1 \leq A_i < 10^K
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Output the number shown on the calculator after the N operations.
Sample Input 1
5 2 7 13 3 2 5
Sample Output 1
10
This calculator can display at most two digits and initially shows 1. Takahashi operates as follows:
- The 1st operation multiplies by 7. Since 1 \times 7 = 7, the calculator shows 7.
- The 2nd operation multiplies by 13. Since 7 \times 13 = 91, the calculator shows 91.
- The 3rd operation multiplies by 3. Since 91\times 3=273, which has three digits, the calculator shows 1.
- The 4th operation multiplies by 2. Since 1\times 2=2, the calculator shows 2.
- The 5th operation multiplies by 5. Since 2\times 5=10, the calculator shows 10.
Sample Input 2
2 1 2 5
Sample Output 2
1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
ヘビの待ち行列があります。最初、列は空です。
クエリが Q 個与えられるので、与えられた順に処理してください。クエリは以下の 3 種類です。
- タイプ 1 :
1 lの形式で与えられる。長さ l のヘビが列の末尾に追加される。このとき追加するヘビの頭の位置は、元の列が空の場合は座標 0、そうでない場合は最後尾のヘビの頭の座標に最後尾のヘビの長さを加えた座標となる。 - タイプ 2 :
2の形式で与えられる。列の先頭にいるヘビが列から抜ける。このとき、列が空でないことは保証される。抜けたヘビの長さを m として、列に残っている全てのヘビの頭の座標が m だけ減少する。 - タイプ 3 :
3 kの形式で与えられる。列の先頭から数えて k 番目にいるヘビの頭の座標を出力せよ。このとき、列には少なくとも k 匹のヘビがいることが保証される。
制約
- 1 \leq Q \leq 3 \times 10^{5}
- タイプ 1 のクエリにおいて、1 \leq l \leq 10^{9}
- タイプ 2 のクエリにおいて、列が空でないことが保証される
- タイプ 3 のクエリにおいて、列にいるヘビの数を n として、1 \leq k \leq n
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
ただし、\text{query}_i は i 個目のクエリを表し、以下のいずれかの形式である。
1 l
2
3 k
出力
タイプ 3 のクエリの個数を q として、q 行出力せよ。i 行目には、i 個目のタイプ 3 のクエリに対する答えを出力せよ。
入力例 1
7 1 5 1 7 3 2 1 3 1 4 2 3 3
出力例 1
5 10
- 1 個目のクエリ : 長さ 5 のヘビが列に追加される。列にヘビはいないため、追加されたヘビの頭の座標は 0 となる。
- 2 個目のクエリ : 長さ 7 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 0 で長さが 5 のため、追加されたヘビの頭の座標は 5 となる。
- 3 個目のクエリ : 前から 2 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に 0, 5 であるため、5 を出力する。
- 4 個目のクエリ : 長さ 3 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 5 で長さが 7 のため、追加されたヘビの頭の座標は 12 となる。
- 5 個目のクエリ : 長さ 4 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 12 で長さが 3 のため、追加されたヘビの頭の座標は 15 となる。
- 6 個目のクエリ : 先頭のヘビが列から抜ける。抜けたヘビの長さが 5 であるため、列にいるヘビの頭の座標は 5 だけ減少する。列に残っているヘビの頭の座標は先頭から順に 0,7,10 となる。
- 7 個目のクエリ : 前から 3 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に 0, 7, 10 であるため、10 を出力する。
入力例 2
3 1 1 2 1 3
出力例 2
タイプ 3 のクエリが 1 つもない場合もあります。
入力例 3
10 1 15 1 10 1 5 2 1 5 1 10 1 15 2 3 4 3 2
出力例 3
20 5
Score : 300 points
Problem Statement
There is a queue of snakes. Initially, the queue is empty.
You are given Q queries, which should be processed in the order they are given. There are three types of queries:
- Type 1: Given in the form
1 l. A snake of length l is added to the end of the queue. If the queue was empty before adding, the head position of the newly added snake is 0; otherwise, it is the sum of the head coordinate of the last snake in the queue and the last snake’s length. - Type 2: Given in the form
2. The snake at the front of the queue leaves the queue. It is guaranteed that the queue is not empty at this time. Let m be the length of the snake that left, then the head coordinate of every snake remaining in the queue decreases by m. - Type 3: Given in the form
3 k. Output the head coordinate of the snake that is k-th from the front of the queue. It is guaranteed that there are at least k snakes in the queue at this time.
Constraints
- 1 \leq Q \leq 3 \times 10^{5}
- For a query of type 1, 1 \leq l \leq 10^{9}
- For a query of type 2, it is guaranteed that the queue is not empty.
- For a query of type 3, let n be the number of snakes in the queue, then 1 \leq k \leq n.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
Here, \text{query}_i is the i-th query in one of the following forms:
1 l
2
3 k
Output
Let q be the number of queries of type 3. Print q lines. The i-th line should contain the answer to the i-th type 3 query.
Sample Input 1
7 1 5 1 7 3 2 1 3 1 4 2 3 3
Sample Output 1
5 10
- 1st query: A snake of length 5 is added to the queue. Since the queue was empty, the head coordinate of this snake is 0.
- 2nd query: A snake of length 7 is added to the queue. Before adding, the last snake has head coordinate 0 and length 5, so the newly added snake’s head coordinate is 5.
- 3rd query: Output the head coordinate of the snake that is 2nd from the front. Currently, the head coordinates of the snakes in order are 0, 5, so output 5.
- 4th query: A snake of length 3 is added to the queue. Before adding, the last snake has head coordinate 5 and length 7, so the new snake’s head coordinate is 12.
- 5th query: A snake of length 4 is added to the queue. Before adding, the last snake has head coordinate 12 and length 3, so the new snake’s head coordinate is 15.
- 6th query: The snake at the front leaves the queue. The length of the snake that left is 5, so the head coordinate of each remaining snake decreases by 5. The remaining snake’s head coordinate becomes 0, 7, 10.
- 7th query: Output the head coordinate of the snake that is 3rd from the front. Currently, the head coordinates of the snakes in order are 0, 7, 10, so output 10.
Sample Input 2
3 1 1 2 1 3
Sample Output 2
It is possible that there are no queries of type 3.
Sample Input 3
10 1 15 1 10 1 5 2 1 5 1 10 1 15 2 3 4 3 2
Sample Output 3
20 5