Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
英小文字と . のみからなる文字列 S が与えられます。
S を . で分割したときの末尾の文字列を出力してください。
すなわち、. を含まない S の接尾辞のうち最長のものを出力してください。
制約
- S は英小文字と
.からなる、長さ 2 以上 100 以下の文字列 - S には
.が 1 つ以上含まれる - S の末尾は
.ではない
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
atcoder.jp
出力例 1
jp
atcoder.jp の、 . を含まない最長の接尾辞は jp です。
入力例 2
translate.google.com
出力例 2
com
S に . が複数含まれることもあります。
入力例 3
.z
出力例 3
z
S が . から始まることもあります。
入力例 4
..........txt
出力例 4
txt
S 中で . が連続することもあります。
Score: 100 points
Problem Statement
You are given a string S consisting of lowercase English letters and the character ..
Print the last substring when S is split by .s.
In other words, print the longest suffix of S that does not contain ..
Constraints
- S is a string of length between 2 and 100, inclusive, consisting of lowercase English letters and
.. - S contains at least one
.. - S does not end with
..
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
atcoder.jp
Sample Output 1
jp
The longest suffix of atcoder.jp that does not contain . is jp.
Sample Input 2
translate.google.com
Sample Output 2
com
S may contain multiple .s.
Sample Input 3
.z
Sample Output 3
z
S may start with ..
Sample Input 4
..........txt
Sample Output 4
txt
S may contain consecutive .s.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
長さ N の英小文字からなる文字列 S が与えられます。
S の i 文字目を S_i と記します。
S_1,S_1,S_2,S_2,\dots,S_N,S_N をこの順に連結した長さ 2N の文字列を出力してください。
例えば、 S が beginner のときは bbeeggiinnnneerr と出力してください。
制約
- N は 1 \le N \le 50 を満たす整数
- S は長さ N の英小文字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
答えを出力せよ。
入力例 1
8 beginner
出力例 1
bbeeggiinnnneerr
問題文中の例と同じです。
入力例 2
3 aaa
出力例 2
aaaaaa
Score : 100 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters.
We denote the i-th character of S by S_i.
Print the string of length 2N obtained by concatenating S_1,S_1,S_2,S_2,\dots,S_N, and S_N in this order.
For example, if S is beginner, print bbeeggiinnnneerr.
Constraints
- N is an integer such that 1 \le N \le 50.
- S is a string of length N consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N S
Output
Print the answer.
Sample Input 1
8 beginner
Sample Output 1
bbeeggiinnnneerr
It is the same as the example described in the problem statement.
Sample Input 2
3 aaa
Sample Output 2
aaaaaa
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
AtCoder 商店には N 個の商品があります。 i\ (1\leq i\leq N) 番目の商品の価格は P _ i です。 i\ (1\leq i\leq N) 番目の商品は C _ i 個の機能をもち、i\ (1\leq i\leq N) 番目の商品の j\ (1\leq j\leq C _ i) 番目の機能は 1 以上 M 以下の整数 F _ {i,j} として表されます。
高橋くんは、AtCoder 商店の商品で一方が一方の上位互換であるものがないか気になりました。
i 番目の商品と j 番目の商品 (1\leq i,j\leq N) であって、次の条件をすべて満たすものがあるとき Yes と、ないとき No と出力してください。
- P _ i\geq P _ j である。
- j 番目の製品は i 番目の製品がもつ機能をすべてもつ。
- P _ i\gt P _ j であるか、j 番目の製品は i 番目の製品にない機能を 1 つ以上もつ。
制約
- 2\leq N\leq100
- 1\leq M\leq100
- 1\leq P _ i\leq10^5\ (1\leq i\leq N)
- 1\leq C _ i\leq M\ (1\leq i\leq N)
- 1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
P _ 1 C _ 1 F _ {1,1} F _ {1,2} \ldots F _ {1,C _ 1}
P _ 2 C _ 2 F _ {2,1} F _ {2,2} \ldots F _ {2,C _ 2}
\vdots
P _ N C _ N F _ {N,1} F _ {N,2} \ldots F _ {N,C _ N}
出力
答えを 1 行で出力せよ。
入力例 1
5 6 10000 2 1 3 15000 3 1 2 4 30000 3 1 3 5 35000 2 1 5 100000 6 1 2 3 4 5 6
出力例 1
Yes
(i,j)=(4,3) とすると、条件を全て満たします。
他の組は条件を満たしません。例えば (i,j)=(4,5) とすると j 番目の商品は i 番目の商品の機能をすべてもっていますが、P _ i\lt P _ j なので上位互換ではありません。
入力例 2
4 4 3 1 1 3 1 2 3 1 2 4 2 2 3
出力例 2
No
まったく同じ価格と機能をもった商品がある場合もあります。
入力例 3
20 10 72036 3 3 4 9 7716 4 1 2 3 6 54093 5 1 6 7 8 10 25517 7 3 4 5 6 7 9 10 96930 8 2 3 4 6 7 8 9 10 47774 6 2 4 5 6 7 9 36959 5 1 3 4 5 8 46622 7 1 2 3 5 6 8 10 34315 9 1 3 4 5 6 7 8 9 10 54129 7 1 3 4 6 7 8 9 4274 5 2 4 7 9 10 16578 5 2 3 6 7 9 61809 4 1 2 4 5 1659 5 3 5 6 9 10 59183 5 1 2 3 4 9 22186 4 3 5 6 8 98282 4 1 4 7 10 72865 8 1 2 3 4 6 8 9 10 33796 6 1 3 5 7 9 10 74670 4 1 2 6 8
出力例 3
Yes
Score : 200 points
Problem Statement
AtCoder Shop has N products. The price of the i-th product (1\leq i\leq N) is P _ i. The i-th product (1\leq i\leq N) has C_i functions. The j-th function (1\leq j\leq C _ i) of the i-th product (1\leq i\leq N) is represented as an integer F _ {i,j} between 1 and M, inclusive.
Takahashi wonders whether there is a product that is strictly superior to another.
If there are i and j (1\leq i,j\leq N) such that the i-th and j-th products satisfy all of the following conditions, print Yes; otherwise, print No.
- P _ i\geq P _ j.
- The j-th product has all functions of the i-th product.
- P _ i\gt P _ j, or the j-th product has one or more functions that the i-th product lacks.
Constraints
- 2\leq N\leq100
- 1\leq M\leq100
- 1\leq P _ i\leq10^5\ (1\leq i\leq N)
- 1\leq C _ i\leq M\ (1\leq i\leq N)
- 1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
P _ 1 C _ 1 F _ {1,1} F _ {1,2} \ldots F _ {1,C _ 1}
P _ 2 C _ 2 F _ {2,1} F _ {2,2} \ldots F _ {2,C _ 2}
\vdots
P _ N C _ N F _ {N,1} F _ {N,2} \ldots F _ {N,C _ N}
Output
Print the answer in a single line.
Sample Input 1
5 6 10000 2 1 3 15000 3 1 2 4 30000 3 1 3 5 35000 2 1 5 100000 6 1 2 3 4 5 6
Sample Output 1
Yes
(i,j)=(4,3) satisfies all of the conditions.
No other pair satisfies them. For instance, for (i,j)=(4,5), the j-th product has all functions of the i-th one, but P _ i\lt P _ j, so it is not strictly superior.
Sample Input 2
4 4 3 1 1 3 1 2 3 1 2 4 2 2 3
Sample Output 2
No
Multiple products may have the same price and functions.
Sample Input 3
20 10 72036 3 3 4 9 7716 4 1 2 3 6 54093 5 1 6 7 8 10 25517 7 3 4 5 6 7 9 10 96930 8 2 3 4 6 7 8 9 10 47774 6 2 4 5 6 7 9 36959 5 1 3 4 5 8 46622 7 1 2 3 5 6 8 10 34315 9 1 3 4 5 6 7 8 9 10 54129 7 1 3 4 6 7 8 9 4274 5 2 4 7 9 10 16578 5 2 3 6 7 9 61809 4 1 2 4 5 1659 5 3 5 6 9 10 59183 5 1 2 3 4 9 22186 4 3 5 6 8 98282 4 1 4 7 10 72865 8 1 2 3 4 6 8 9 10 33796 6 1 3 5 7 9 10 74670 4 1 2 6 8
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
1 以上 26 以下の整数からなる長さ 26 の数列 P=(P_1,P_2, \ldots ,P_{26}) が与えられます。ここで、P の要素は相異なることが保証されます。
以下の条件を満たす長さ 26 の文字列 S を出力してください。
- 任意の i\, (1 \leq i \leq 26) について、S の i 文字目は辞書順で小さい方から P_i 番目の英小文字である。
制約
- 1 \leq P_i \leq 26
- P_i \neq P_j (i \neq j)
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
P_1 P_2 \ldots P_{26}
出力
文字列 S を出力せよ。
入力例 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
出力例 1
abcdefghijklmnopqrstuvwxyz
入力例 2
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
出力例 2
bacdefghijklmnopqrstuvwxyz
入力例 3
5 11 12 16 25 17 18 1 7 10 4 23 20 3 2 24 26 19 14 9 6 22 8 13 15 21
出力例 3
eklpyqragjdwtcbxzsnifvhmou
Score : 200 points
Problem Statement
You are given a sequence of 26 integers P=(P_1,P_2, \ldots ,P_{26}) consisting of integers from 1 through 26. It is guaranteed that all elements in P are distinct.
Print a string S of length 26 that satisfies the following condition.
- For every i (1 \leq i \leq 26), the i-th character of S is the lowercase English letter that comes P_i-th in alphabetical order.
Constraints
- 1 \leq P_i \leq 26
- P_i \neq P_j (i \neq j)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
P_1 P_2 \ldots P_{26}
Output
Print the string S.
Sample Input 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Sample Output 1
abcdefghijklmnopqrstuvwxyz
Sample Input 2
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Sample Output 2
bacdefghijklmnopqrstuvwxyz
Sample Input 3
5 11 12 16 25 17 18 1 7 10 4 23 20 3 2 24 26 19 14 9 6 22 8 13 15 21
Sample Output 3
eklpyqragjdwtcbxzsnifvhmou
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