Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
4 桁の暗証番号 X_1X_2X_3X_4 が与えられます。 番号は先頭の桁が 0 であることもあり得ます。 暗証番号は以下のいずれかの条件をみたすとき弱い暗証番号と呼ばれます。
- 4 桁とも同じ数字である。
- 1\leq i\leq 3 をみたす任意の整数 i について、 X_{i+1} が、 X_i の次の数字である。 ただし、 0\leq j\leq 8 について j の次の数字は j+1 であり、 9 の次の数字は 0 である。
与えられた暗証番号が弱い暗証番号ならば Weak を、そうでないならば Strong を出力してください。
制約
- 0 \leq X_1, X_2, X_3, X_4 \leq 9
- X_1, X_2, X_3, X_4 は整数である。
入力
入力は以下の形式で標準入力から与えられる。
X_1X_2X_3X_4
出力
与えられた暗証番号が弱い暗証番号ならば Weak を、そうでないならば Strong を出力せよ。
入力例 1
7777
出力例 1
Weak
4 桁ともすべて 7 であるため、 1 つめの条件をみたしており、弱い暗証番号です。
入力例 2
0112
出力例 2
Strong
1 桁目と 2 桁目が異なっており、 3 桁目は 2 桁目の次の数字ではないため、どちらの条件もみたしていません。
入力例 3
9012
出力例 3
Weak
9 の次の数字が 0 であることに注意してください。
Score : 200 points
Problem Statement
You are given a 4-digit PIN: X_1X_2X_3X_4, which may begin with a 0. The PIN is said to be weak when it satisfies one of the following conditions:
- All of the four digits are the same.
- For each integer i such that 1\leq i\leq 3, X_{i+1} follows X_i. Here, j+1 follows j for each 0\leq j\leq 8, and 0 follows 9.
If the given PIN is weak, print Weak; otherwise, print Strong.
Constraints
- 0 \leq X_1, X_2, X_3, X_4 \leq 9
- X_1, X_2, X_3, and X_4 are integers.
Input
Input is given from Standard Input in the following format:
X_1X_2X_3X_4
Output
If the given PIN is weak, print Weak; otherwise, print Strong.
Sample Input 1
7777
Sample Output 1
Weak
All four digits are 7, satisfying the first condition, so this PIN is weak.
Sample Input 2
0112
Sample Output 2
Strong
The first and second digits differ, and the third digit does not follow the second digit, so neither condition is satisfied.
Sample Input 3
9012
Sample Output 3
Weak
Note that 0 follows 9.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
おもり 1, おもり 2, \dots, おもり N の N 個のおもりがあります。おもり i の重さは A_i です。
以下の条件を満たす正整数 n を 良い整数 と呼びます。
- \bf{3} 個以下 の異なるおもりを自由に選んで、選んだおもりの重さの和を n にすることができる。
W 以下の正整数のうち、良い整数は何個ありますか？
制約
- 1 \leq N \leq 300
- 1 \leq W \leq 10^6
- 1 \leq A_i \leq 10^6
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N W A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
2 10 1 3
出力例 1
3
おもり 1 のみを選ぶと重さの和は 1 になります。よって 1 は良い整数です。
おもり 2 のみを選ぶと重さの和は 3 になります。よって 3 は良い整数です。
おもり 1 とおもり 2 を選ぶと重さの和は 4 になります。よって 4 は良い整数です。
これら以外に良い整数は存在しません。また、1,3,4 のいずれも W 以下の整数です。よって答えは 3 個になります。
入力例 2
2 1 2 3
出力例 2
0
W 以下の良い整数は存在しません。
入力例 3
4 12 3 3 3 3
出力例 3
3
良い整数は 3,6,9 の 3 個です。
たとえばおもり 1, おもり 2, おもり 3 を選ぶと重さの和は 9 になるので、9 は良い整数です。
12 は良い整数 ではない ことに注意してください。
入力例 4
7 251 202 20 5 1 4 2 100
出力例 4
48
Score : 200 points
Problem Statement
There are N weights called Weight 1, Weight 2, \dots, Weight N. Weight i has a mass of A_i.
Let us say a positive integer n is a good integer if the following condition is satisfied:
- We can choose at most 3 different weights so that they have a total mass of n.
How many positive integers less than or equal to W are good integers?
Constraints
- 1 \leq N \leq 300
- 1 \leq W \leq 10^6
- 1 \leq A_i \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N W A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
2 10 1 3
Sample Output 1
3
If we choose only Weight 1, it has a total mass of 1, so 1 is a good integer.
If we choose only Weight 2, it has a total mass of 3, so 3 is a good integer.
If we choose Weights 1 and 2, they have a total mass of 4, so 4 is a good integer.
No other integer is a good integer. Also, all of 1, 3, and 4 are integers less than or equal to W. Therefore, the answer is 3.
Sample Input 2
2 1 2 3
Sample Output 2
0
There are no good integers less than or equal to W.
Sample Input 3
4 12 3 3 3 3
Sample Output 3
3
There are 3 good integers: 3, 6, and 9.
For example, if we choose Weights 1, 2, and 3, they have a total mass of 9, so 9 is a good integer.
Note that 12 is not a good integer.
Sample Input 4
7 251 202 20 5 1 4 2 100
Sample Output 4
48
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君と青木君は、それぞれ N 個のボールに M 本のひもを取り付けたおもちゃを持っています。
高橋君のおもちゃにおいて、ボールには 1, \dots, N と番号が付けられており、i \, (1 \leq i \leq M) 本目のひもはボール A_i とボール B_i を結んでいます。
青木君のおもちゃにおいても同様に、ボールには 1, \dots, N と番号が付けられており、i \, (1 \leq i \leq M) 本目のひもはボール C_i とボール D_i を結んでいます。
それぞれのおもちゃにおいて、同一のボールを結ぶようなひもは存在せず、2 つのボールを 2 本以上の異なるひもが結んでいることはありません。
すぬけ君は、2 人のおもちゃが同じ形であるかどうか気になっています。
ここで、2 人のおもちゃが同じ形であるとは、以下の条件を満たす数列 P が存在することをいいます。
- P は (1, \dots, N) を並べ替えて得られる。
- 任意の 1 以上 N 以下の整数 i, j に対し、以下が成り立つ。
- 高橋君のおもちゃにおいてボール i, j がひもで繋がれていることと、青木君のおもちゃにおいてボール P_i, P_j がひもで繋がれていることは同値である。
2 人のおもちゃが同じ形であるなら Yes、そうでないなら No と出力してください。
制約
- 1 \leq N \leq 8
- 0 \leq M \leq \frac{N(N - 1)}{2}
- 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
- (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
- 1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
- (C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 \vdots A_M B_M C_1 D_1 \vdots C_M D_M
出力
2 人のおもちゃが同じ形であるなら Yes、そうでないなら No と出力せよ。
入力例 1
4 4 1 2 1 3 1 4 3 4 1 3 1 4 2 3 3 4
出力例 1
Yes
高橋君のおもちゃは下図の左側のような形をしており、青木君のおもちゃは下図の右側のような形をしています。
次の図から、2 人のおもちゃが同じ形であることがわかります。例えば P = (3, 2, 1, 4) とすると問題文中の条件を満たします。
入力例 2
5 6 1 2 1 3 1 4 3 4 3 5 4 5 1 2 1 3 1 4 1 5 3 5 4 5
出力例 2
No
2 人のおもちゃは同じ形ではありません。
入力例 3
8 0
出力例 3
Yes
Score : 300 points
Problem Statement
Takahashi and Aoki each have a toy made by attaching M cords to N balls.
In Takahashi's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball A_i and B_i.
Similarly, in Aoki's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball C_i and D_i.
In each toy, no cord ties a ball to itself, and no two balls are tied by two or more different cords.
Snuke is wondering whether the two toys have the same shape.
Here, they are said to have the same shape when there is a sequence P that satisfies the conditions below.
- P is a permutation of (1, \dots, N).
- For every pair of integers i, j between 1 and N (inclusive), the following holds.
- Balls i and j in Takahashi's toy are tied by a cord if and only if Balls P_i and P_j in Aoki's toy are tied by a cord.
If the two toys have the same shape, print Yes; otherwise, print No.
Constraints
- 1 \leq N \leq 8
- 0 \leq M \leq \frac{N(N - 1)}{2}
- 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
- (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
- 1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
- (C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 \vdots A_M B_M C_1 D_1 \vdots C_M D_M
Output
If the two toys have the same shape, print Yes; otherwise, print No.
Sample Input 1
4 4 1 2 1 3 1 4 3 4 1 3 1 4 2 3 3 4
Sample Output 1
Yes
Takahashi's toy is illustrated on the left in the figure below, and Aoki's is illustrated on the right.
The following figure shows that the two toys have the same shape. The condition in the statement is satisfied when P = (3, 2, 1, 4), for example.
Sample Input 2
5 6 1 2 1 3 1 4 3 4 3 5 4 5 1 2 1 3 1 4 1 5 3 5 4 5
Sample Output 2
No
The two toys do not have the same shape.
Sample Input 3
8 0
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の文字列 S が与えられます。S_i\ (1\leq i \leq N) を S の左から i 番目の文字とします。
あなたは以下の 2 種類の操作を好きな順番で 0 回以上好きな回数行うことができます。
-
A 円払う。 S の左端の文字を右端に移動する。すなわち、S_1S_2\ldots S_N を S_2\ldots S_NS_1 に変える。
-
B 円払う。 1 以上 N 以下の整数 i を選び、 S_i を好きな英小文字で置き換える。
S を回文にするためには最低で何円必要ですか？
回文とは
ある文字列 T について、 T の長さを |T| として、全ての整数 i (1 \le i \le |T|) について、 T の前から i 文字目と後ろから i 文字目が同じであるとき、またそのときに限って、 T は回文です。制約
- 1\leq N \leq 5000
- 1\leq A,B\leq 10^9
- S は英小文字からなる長さ N の文字列
- S 以外の入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A B S
出力
答えを整数として出力せよ。
入力例 1
5 1 2 rrefa
出力例 1
3
最初に 2 番目の操作を 1 回行います。2 円払い、i=5 として S_5 を e で置き換えます。 S は rrefe となります。
次に 1 番目の操作を 1 回行います。1 円払い、S は refer となります。これは回文です。
よって 3 円払うことで S を回文にすることができました。 2 円以下払うことで S を回文にすることは不可能なので、これが答えです。
入力例 2
8 1000000000 1000000000 bcdfcgaa
出力例 2
4000000000
答えは 32 bit 整数に収まらない場合があることに注意してください。
Score : 300 points
Problem Statement
You are given a string S of length N. Let S_i\ (1\leq i \leq N) be the i-th character of S from the left.
You may perform the following two kinds of operations zero or more times in any order:
-
Pay A yen (the currency in Japan). Move the leftmost character of S to the right end. In other words, change S_1S_2\ldots S_N to S_2\ldots S_NS_1.
-
Pay B yen. Choose an integer i between 1 and N, and replace S_i with any lowercase English letter.
How many yen do you need to pay to make S a palindrome?
What is a palindrome?
A string T is a palindrome if and only if the i-th character from the left and the i-th character from the right are the same for all integers i (1 \le i \le |T|), where |T| is the length of T.Constraints
- 1\leq N \leq 5000
- 1\leq A,B\leq 10^9
- S is a string of length N consisting of lowercase English letters.
- All values in the input except for S are integers.
Input
The input is given from Standard Input in the following format:
N A B S
Output
Print the answer as an integer.
Sample Input 1
5 1 2 rrefa
Sample Output 1
3
First, pay 2 yen to perform the operation of the second kind once: let i=5 to replace S_5 with e. S is now rrefe.
Then, pay 1 yen to perform the operation of the first kind once. S is now refer, which is a palindrome.
Thus, you can make S a palindrome for 3 yen. Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.
Sample Input 2
8 1000000000 1000000000 bcdfcgaa
Sample Output 2
4000000000
Note that the answer may not fit into a 32-bit integer type.
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
1 から N までの番号が付けられた N 個の商品がベルトコンベア上を流れています。 ベルトコンベアには印字機が取り付けられており、商品 i は今から T_i [μs] 後に印字機の範囲に入り、その D_i [μs] 後に印字機の範囲から出ます。
キーエンスの印字機は、印字機の範囲内にある商品 1 つに一瞬で印字することができます（特に、商品が印字機の範囲に入る瞬間や範囲から出る瞬間に印字することも可能です）。 ただし、1 度印字すると、次に印字するまでに 1 [μs] のチャージ時間が必要です。 印字機が印字をする商品とタイミングをうまく選んだとき、最大で何個の商品に印字することができますか？
制約
- 1\leq N \leq 2\times 10^5
- 1\leq T_i,D_i \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N T_1 D_1 T_2 D_2 \vdots T_N D_N
出力
印字機が印字することのできる商品の数の最大値を出力せよ。
入力例 1
5 1 1 1 1 2 1 1 2 1 4
出力例 1
4
以下、今から t [μs] 後のことを単に時刻 t とよびます。
例えば、次のようにして 4 個の商品に印字することができます。
- 時刻 1 : 商品 1,2,4,5 が印字機の範囲に入る。商品 4 に印字する。
- 時刻 2 : 商品 3 が印字機の範囲に入り、商品 1,2 が印字機の範囲から出る。商品 1 に印字する。
- 時刻 3 : 商品 3,4 が印字機の範囲から出る。商品 3 に印字する。
- 時刻 4.5 : 商品 5 に印字する。
- 時刻 5 : 商品 5 が印字機の範囲から出る。
5 個の商品すべてに印字することはできないため、答えは 4 です。
入力例 2
2 1 1 1000000000000000000 1000000000000000000
出力例 2
2
入力例 3
10 4 1 1 2 1 4 3 2 5 1 5 1 4 1 2 1 4 1 2 4
出力例 3
6
Score : 450 points
Problem Statement
There are N products labeled 1 to N flowing on a conveyor belt. A Keyence printer is attached to the conveyor belt, and product i enters the range of the printer T_i microseconds from now and leaves it D_i microseconds later.
The Keyence printer can instantly print on one product within the range of the printer (in particular, it is possible to print at the moment the product enters or leaves the range of the printer). However, after printing once, it requires a charge time of 1 microseconds before it can print again. What is the maximum number of products the printer can print on when the product and timing for the printer to print are chosen optimally?
Constraints
- 1\leq N \leq 2\times 10^5
- 1\leq T_i,D_i \leq 10^{18}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N T_1 D_1 T_2 D_2 \vdots T_N D_N
Output
Print the maximum number of products the printer can print on.
Sample Input 1
5 1 1 1 1 2 1 1 2 1 4
Sample Output 1
4
Below, we will simply call the moment t microseconds from now time t.
For example, you can print on four products as follows:
- Time 1 : Products 1,2,4,5 enter the range of the printer. Print on product 4.
- Time 2 : Product 3 enters the range of the printer, and products 1,2 leave the range of the printer. Print on product 1.
- Time 3 : Products 3,4 leave the range of the printer. Print on product 3.
- Time 4.5 : Print on product 5.
- Time 5 : Product 5 leaves the range of the printer.
It is impossible to print on all five products, so the answer is 4.
Sample Input 2
2 1 1 1000000000000000000 1000000000000000000
Sample Output 2
2
Sample Input 3
10 4 1 1 2 1 4 3 2 5 1 5 1 4 1 2 1 4 1 2 4
Sample Output 3
6