Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
長さ 3 の英大文字からなる文字列 S が与えられます。
S の各文字を並び替えることで S を文字列 ABC と一致させることができるか判定してください。
制約
- S は英大文字からなる長さ 3 の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の各文字を並び替えることで文字列 ABC と一致させることができるなら Yes を、そうでないなら No を出力せよ。
入力例 1
BAC
出力例 1
Yes
S の 1 文字目と S の 2 文字目を入れ替えることで ABC と一致させることができます。
入力例 2
AAC
出力例 2
No
どのように並び替えても S を ABC と一致させることはできません。
入力例 3
ABC
出力例 3
Yes
入力例 4
ARC
出力例 4
No
Score : 100 points
Problem Statement
You are given a string S of length 3 consisting of uppercase English letters.
Determine whether it is possible to rearrange the characters in S to make it match the string ABC.
Constraints
- S is a string of length 3 consisting of uppercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Print Yes if it is possible to rearrange the characters in S to make it match the string ABC, and No otherwise.
Sample Input 1
BAC
Sample Output 1
Yes
You can make S match ABC by swapping the first and second characters of S.
Sample Input 2
AAC
Sample Output 2
No
You cannot make S match ABC no matter how you rearrange the characters.
Sample Input 3
ABC
Sample Output 3
Yes
Sample Input 4
ARC
Sample Output 4
No
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
縦 H 行、横 W 列のマス目があり、このうち上から i 個目、左から j 個目のマスを (i,j) と呼びます。
このとき、マス (R,C) に辺で隣接するマスの個数を求めてください。
ただし、ある 2 つのマス (a,b),(c,d) が辺で隣接するとは、 |a-c|+|b-d|=1 (|x| を x の絶対値とする) であることを言います。
制約
- 入力は全て整数
- 1 \le R \le H \le 10
- 1 \le C \le W \le 10
入力
入力は以下の形式で標準入力から与えられる。
H W R C
出力
答えを整数として出力せよ。
入力例 1
3 4 2 2
出力例 1
4
入出力例 1,2,3 に対する説明は、出力例 3 の下にまとめて示します。
入力例 2
3 4 1 3
出力例 2
3
入力例 3
3 4 3 4
出力例 3
2
H=3,W=4 のとき、マス目は以下のようになります。
- 入力例 1 について、マス (2,2) に隣接するマスは 4 つです。
- 入力例 2 について、マス (1,3) に隣接するマスは 3 つです。
- 入力例 3 について、マス (3,4) に隣接するマスは 2 つです。
入力例 4
1 10 1 5
出力例 4
2
入力例 5
8 1 8 1
出力例 5
1
入力例 6
1 1 1 1
出力例 6
0
Score : 100 points
Problem Statement
There is a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.
Find the number of squares that share a side with Square (R, C).
Here, two squares (a,b) and (c,d) are said to share a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).
Constraints
- All values in input are integers.
- 1 \le R \le H \le 10
- 1 \le C \le W \le 10
Input
Input is given from Standard Input in the following format:
H W R C
Output
Print the answer as an integer.
Sample Input 1
3 4 2 2
Sample Output 1
4
We will describe Sample Inputs/Outputs 1,2, and 3 at once below Sample Output 3.
Sample Input 2
3 4 1 3
Sample Output 2
3
Sample Input 3
3 4 3 4
Sample Output 3
2
When H=3 and W=4, the grid looks as follows.
- For Sample Input 1, there are 4 squares adjacent to Square (2,2).
- For Sample Input 2, there are 3 squares adjacent to Square (1,3).
- For Sample Input 3, there are 2 squares adjacent to Square (3,4).
Sample Input 4
1 10 1 5
Sample Output 4
2
Sample Input 5
8 1 8 1
Sample Output 5
1
Sample Input 6
1 1 1 1
Sample Output 6
0
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 点
問題文
数直線の原点に高橋君がいます。高橋君は座標 X にあるゴールに移動しようとしています。
座標 Y には壁があり、最初、高橋君は壁を超えて移動することができません。
座標 Z にあるハンマーを拾った後でなら、壁を破壊して通過できるようになります。
高橋君がゴールに到達することが可能か判定し、可能であれば移動距離の最小値を求めてください。
制約
- -1000 \leq X,Y,Z \leq 1000
- X,Y,Z は相異なり、いずれも 0 でない
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
X Y Z
出力
高橋君がゴールに到達することが可能であれば、移動距離の最小値を出力せよ。不可能であれば、かわりに -1 と出力せよ。
入力例 1
10 -10 1
出力例 1
10
高橋君はまっすぐゴールに向かうことができます。
入力例 2
20 10 -10
出力例 2
40
ゴールは壁の向こう側にあります。まずハンマーを拾い、壁を壊すことでゴールに到達することができます。
入力例 3
100 1 1000
出力例 3
-1
Score : 200 points
Problem Statement
Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.
There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.
Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.
Constraints
- -1000 \leq X,Y,Z \leq 1000
- X, Y, and Z are distinct, and none of them is 0.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
X Y Z
Output
If Takahashi can reach the goal, print the minimum total distance he needs to travel to do so. If he cannot, print -1 instead.
Sample Input 1
10 -10 1
Sample Output 1
10
Takahashi can go straight to the goal.
Sample Input 2
20 10 -10
Sample Output 2
40
The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.
Sample Input 3
100 1 1000
Sample Output 3
-1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
AtCoder 王国を治める高橋君は、英小文字のアルファベット順を変更することにしました。
新たなアルファベット順はa , b , \ldots, z を並べ替えて得られる文字列 X を用いて表されます。X の i \, (1 \leq i \leq 26) 文字目は、新たな順番において i 番目に小さい英小文字を表します。
AtCoder 王国には N 人の国民がおり、それぞれの国民の名前は S_1, S_2, \dots, S_N です。ここで、S_i \, (1 \leq i \leq N) は英小文字からなります。
これらの名前を、高橋君の定めたアルファベット順に基づく辞書順に従って並べ替えてください。
辞書順とは？
辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 S, T の大小を判定するアルゴリズムを以下に説明します。
以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。
- S, T のうち長さが大きくない方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、S_j が T_j よりアルファベット順で小さい場合は S \lt T 、そうでない場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。
制約
- X は
a,b, \ldots,zを並べ替えて得られる - 2 \leq N \leq 50000
- N は整数
- 1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)
- S_i は英小文字からなる (1 \leq i \leq N)
- S_i \neq S_j (1 \leq i \lt j \leq N)
入力
入力は以下の形式で標準入力から与えられる。
X N S_1 S_2 \vdots S_N
出力
N 行出力せよ。i \, (1 \leq i \leq N) 行目には、高橋君の定めたアルファベット順に基づく辞書順に従って国民の名前を並べ替えたとき、i 番目に小さいものを出力すること。
入力例 1
bacdefghijklmnopqrstuvwxzy 4 abx bzz bzy caa
出力例 1
bzz bzy abx caa
高橋君が新たに設定したアルファベット順において、b は a より小さく、z は y より小さいです。そのため、国民の名前を辞書順に並べ替えると、小さい順に bzz , bzy , abx , caa となります。
入力例 2
zyxwvutsrqponmlkjihgfedcba 5 a ab abc ac b
出力例 2
b a ac ab abc
Score : 300 points
Problem Statement
Takahashi, who governs the Kingdom of AtCoder, has decided to change the alphabetical order of English lowercase letters.
The new alphabetical order is represented by a string X, which is a permutation of a, b, \ldots, z. The i-th character of X (1 \leq i \leq 26) would be the i-th smallest English lowercase letter in the new order.
The kingdom has N citizens, whose names are S_1, S_2, \dots, S_N, where each S_i (1 \leq i \leq N) consists of lowercase English letters.
Sort these names lexicographically according to the alphabetical order decided by Takahashi.
What is the lexicographical order?
Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.
Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.
- Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
- If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
- If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.
Constraints
- X is a permutation of
a,b, \ldots,z. - 2 \leq N \leq 50000
- N is an integer.
- 1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)
- S_i consists of lowercase English letters. (1 \leq i \leq N)
- S_i \neq S_j (1 \leq i \lt j \leq N)
Input
Input is given from Standard Input in the following format:
X N S_1 S_2 \vdots S_N
Output
Print N lines. The i-th line (1 \leq i \leq N) should contain the i-th smallest name when the citizens' names are sorted according to the alphabetical order decided by Takahashi.
Sample Input 1
bacdefghijklmnopqrstuvwxzy 4 abx bzz bzy caa
Sample Output 1
bzz bzy abx caa
In the new alphabetical order set by Takahashi, b is smaller than a and z is smaller than y. Thus, sorting the citizens' names lexicographically would result in bzz, bzy, abx, caa in ascending order.
Sample Input 2
zyxwvutsrqponmlkjihgfedcba 5 a ab abc ac b
Sample Output 2
b a ac ab abc