実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
二つの文字 x と y は以下の 3 つの条件のうちどれか 1 つを満たすとき、似た文字と呼ばれます。
- x と y は同じ文字
- x と y の片方が
1で、もう片方がl - x と y の片方が
0で、もう片方がo
また、長さ N の文字列 S と T は以下の条件を満たすとき、似た文字列と呼ばれます。
- 任意の i\ (1\leq i\leq N) について、 S の i 番目の文字と T の i 番目の文字は似た文字
英小文字及び数字からなる長さ N の文字列 S,T が与えられます。 S と T が似た文字列か判定してください。
制約
- N は 1 以上 100 以下の整数
- S,T は英小文字及び数字からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S T
出力
S と T が似た文字列の場合 Yes を、そうでない場合 No を出力せよ。
入力例 1
3 l0w 1ow
出力例 1
Yes
S の 1 文字目は lで、T の 1 文字目は 1です。これらは似た文字です。
S の 2 文字目は 0で、T の 2 文字目は oです。これらは似た文字です。
S の 3 文字目は wで、T の 3 文字目は wです。これらは似た文字です。
よって S と T は似た文字列です。
入力例 2
3 abc arc
出力例 2
No
S の 2 文字目は bで、T の 2 文字目は rです。これらは似た文字ではありません。
よって S と T は似た文字列ではありません。
入力例 3
4 nok0 n0ko
出力例 3
Yes
Score : 100 points
Problem Statement
Two characters x and y are called similar characters if and only if one of the following conditions is satisfied:
- x and y are the same character.
- One of x and y is
1and the other isl. - One of x and y is
0and the other iso.
Two strings S and T, each of length N, are called similar strings if and only if:
- for all i\ (1\leq i\leq N), the i-th character of S and the i-th character of T are similar characters.
Given two length-N strings S and T consisting of lowercase English letters and digits, determine if S and T are similar strings.
Constraints
- N is an integer between 1 and 100.
- Each of S and T is a string of length N consisting of lowercase English letters and digits.
Input
The input is given from Standard Input in the following format:
N S T
Output
Print Yes if S and T are similar strings, and No otherwise.
Sample Input 1
3 l0w 1ow
Sample Output 1
Yes
The 1-st character of S is l, and the 1-st character of T is 1. These are similar characters.
The 2-nd character of S is 0, and the 2-nd character of T is o. These are similar characters.
The 3-rd character of S is w, and the 3-rd character of T is w. These are similar characters.
Thus, S and T are similar strings.
Sample Input 2
3 abc arc
Sample Output 2
No
The 2-nd character of S is b, and the 2-nd character of T is r. These are not similar characters.
Thus, S and T are not similar strings.
Sample Input 3
4 nok0 n0ko
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
明日からの 7 日間の天気予報を表す文字列 S が与えられます。
i 日後の予報は S の i 文字目が o であるとき晴れ、x であるとき雨です。
N 日後の天気予報が晴れかどうかを教えてください。
制約
- N は 1 以上 7 以下の整数
- S は長さ 7 の文字列であり、
oとxのみからなる
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
N 日後の天気予報が晴れであるとき Yes を、雨であるとき No を出力せよ。
入力例 1
4 oooxoox
出力例 1
No
明日からの 7 日間の天気予報は順に、晴れ、晴れ、晴れ、雨、晴れ、晴れ、雨です。
特に、今日から 4 日後の天気予報は雨です。
入力例 2
7 ooooooo
出力例 2
Yes
Score : 100 points
Problem Statement
You are given a string S, which represents a weather forecast for the seven days starting tomorrow.
The i-th of those seven days is forecast to be sunny if the i-th character of S is o, and rainy if that character is x.
Tell us whether the N-th day is forecast to be sunny.
Constraints
- N is an integer between 1 and 7 (inclusive).
- S is a string of length 7 consisting of
oandx.
Input
Input is given from Standard Input in the following format:
N S
Output
Print Yes if the N-th of the seven days starting tomorrow is forecast to be sunny, and No if that day is forecast to be rainy.
Sample Input 1
4 oooxoox
Sample Output 1
No
The forecast for each of the seven days starting tomorrow is as follows: sunny, sunny, sunny, rainy, sunny, sunny, rainy.
In particular, the fourth day is forecast to be rainy.
Sample Input 2
7 ooooooo
Sample Output 2
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
正の整数 N が与えられます。
N=2^x3^y を満たす整数 x,y が存在するなら Yes 、そうでなければ No と出力してください。
制約
- 1\leq N\leq10^{18}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
条件を満たす整数 x,y が存在するなら Yes 、そうでなければ No と 1 行に出力せよ。
入力例 1
324
出力例 1
Yes
x=2,y=4 とすると、2^x3^y=2^23^4=4\times81=324 となるため条件を満たします。
よって、Yes と出力してください。
入力例 2
5
出力例 2
No
どのような整数 x,y をとっても 2^x3^y=5 とすることはできません。
よって、No と出力してください。
入力例 3
32
出力例 3
Yes
x=5,y=0 とすると、2^x3^y=32\times1=32 となるため、Yes と出力してください。
入力例 4
37748736
出力例 4
Yes
Score : 200 points
Problem Statement
You are given a positive integer N.
If there are integers x and y such that N=2^x3^y, print Yes; otherwise, print No.
Constraints
- 1\leq N\leq10^{18}
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print a single line containing Yes if there are integers x and y that satisfy the condition, and No otherwise.
Sample Input 1
324
Sample Output 1
Yes
For x=2,y=4, we have 2^x3^y=2^23^4=4\times81=324, so the condition is satisfied.
Thus, you should print Yes.
Sample Input 2
5
Sample Output 2
No
There are no integers x and y such that 2^x3^y=5.
Thus, you should print No.
Sample Input 3
32
Sample Output 3
Yes
For x=5,y=0, we have 2^x3^y=32\times1=32, so you should print Yes.
Sample Input 4
37748736
Sample Output 4
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
0 以上 26 以下の整数からなる H 行 W 列の行列 A が与えられます。A の上から i 行目、左から j 列目の要素は A_{i,j} です。
H 個の長さ W の文字列 S_1, S_2, \dots, S_H を次の条件を満たすように定めます。
- S_i の j 文字目は、 A_{i,j} が 0 ならばピリオド (
.)、そうでなければ A_{i,j} 番目の大文字アルファベットである。
S_1, S_2, \dots, S_H を順に出力してください。
制約
- 1 \leq H \leq 100
- 1 \leq W \leq 100
- 0 \leq A_{i,j} \leq 26
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1,1} A_{1,2} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}
出力
H 行出力せよ。i 行目には S_i を出力せよ。
入力例 1
2 3 0 1 2 0 0 3
出力例 1
.AB ..C
S_1 = .AB、S_2 = ..C です。この 2 つを順に出力します。
入力例 2
3 3 24 0 0 0 25 0 0 0 26
出力例 2
X.. .Y. ..Z
入力例 3
3 1 2 9 4
出力例 3
B I D
入力例 4
24 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0 0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0 0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0 0 0 22 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0 0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力例 4
................................B........................... ...................MMN...J.....OXN.......................... .................MWGYXMJ.JL....SIW....JJN...JN.............. ...............IME..WKNN..LIAUS..ILJYCJF..IMWXN............. ..............MNF...JEYM..Y..........JP..MUMMNWN............ .............MHB.....MKMS..ABEILLEIITF.NNNI...NNR........... ..........JWMMMMMMNNNMNNMG............MMMB....MKMP.......... ........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP......... ......MI...............................TTTMMGTZMHFN......... .....E.......ABTTWMBGBJL.......................TTWM......... ....M........A...MLINMMIITL...........AIIIIL.......T........ ...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM...... ..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG.... ..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP... ..VM.................................TMMMBINBTN.........B... ...EM...BGMMMMMMMBI....................ITTI.............S... ....TML..................UNGBTX........................IF... ......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E.... ........TMN........MI........MK.......NI...TYNG....IANG..... ..........IMMT.....IL.......NMN.......F........IITNNDN...... ..............TBI....IITUGMT..TWGGBLGF............EE........ .................TTIITXJLJ........TT.....TGGMVBEIB.......... .........................ITETEBEGTENNEKEB................... ............................................................
Score : 200 points
Problem Statement
You are given an H-by-W matrix A consisting of integers between 0 and 26. The element at the i-th row from the top and j-th column from the left is A_{i,j}.
Let S_1, S_2, \dots, S_H be H strings of length W that satisfy the following.
- The j-th character of S_i is a period (
.) if A_{i,j} is 0, and the A_{i,j}-th uppercase English letter otherwise. (For instance, the 4-th letter isD.)
Print S_1, S_2, \dots, S_H in order.
Constraints
- 1 \leq H \leq 100
- 1 \leq W \leq 100
- 0 \leq A_{i,j} \leq 26
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
H W
A_{1,1} A_{1,2} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}
Output
Print H lines. The i-th line should contain S_i.
Sample Input 1
2 3 0 1 2 0 0 3
Sample Output 1
.AB ..C
We have S_1 = .AB and S_2 = ..C. Print these in order.
Sample Input 2
3 3 24 0 0 0 25 0 0 0 26
Sample Output 2
X.. .Y. ..Z
Sample Input 3
3 1 2 9 4
Sample Output 3
B I D
Sample Input 4
24 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0 0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0 0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0 0 0 22 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0 0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output 4
................................B........................... ...................MMN...J.....OXN.......................... .................MWGYXMJ.JL....SIW....JJN...JN.............. ...............IME..WKNN..LIAUS..ILJYCJF..IMWXN............. ..............MNF...JEYM..Y..........JP..MUMMNWN............ .............MHB.....MKMS..ABEILLEIITF.NNNI...NNR........... ..........JWMMMMMMNNNMNNMG............MMMB....MKMP.......... ........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP......... ......MI...............................TTTMMGTZMHFN......... .....E.......ABTTWMBGBJL.......................TTWM......... ....M........A...MLINMMIITL...........AIIIIL.......T........ ...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM...... ..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG.... ..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP... ..VM.................................TMMMBINBTN.........B... ...EM...BGMMMMMMMBI....................ITTI.............S... ....TML..................UNGBTX........................IF... ......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E.... ........TMN........MI........MK.......NI...TYNG....IANG..... ..........IMMT.....IL.......NMN.......F........IITNNDN...... ..............TBI....IITUGMT..TWGGBLGF............EE........ .................TTIITXJLJ........TT.....TGGMVBEIB.......... .........................ITETEBEGTENNEKEB................... ............................................................
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
それぞれ N 個、M 個の正整数からなる 2 つの数列 A=(A_1,A_2, \ldots ,A_N) と B=(B_1, \ldots ,B_M) が与えられます。
それぞれの数列から 1 つずつ要素を選んだときの 2 つの値の差の最小値、すなわち、 \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert を求めてください。
制約
- 1 \leq N,M \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
出力
答えを出力せよ。
入力例 1
2 2 1 6 4 9
出力例 1
2
それぞれの数列から 1 つずつ要素を選んだときの 2 つの値の差としてあり得るのは、 \lvert 1-4\rvert=3 、 \lvert 1-9\rvert=8 、 \lvert 6-4\rvert=2 、 \lvert 6-9\rvert=3 の 4 つです。 この中で最小である 2 を出力します。
入力例 2
1 1 10 10
出力例 2
0
入力例 3
6 8 82 76 82 82 71 70 17 39 67 2 45 35 22 24
出力例 3
3
Score : 300 points
Problem Statement
You are given two sequences: A=(A_1,A_2, \ldots ,A_N) consisting of N positive integers, and B=(B_1, \ldots ,B_M) consisting of M positive integers.
Find the minimum difference of an element of A and an element of B, that is, \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert.
Constraints
- 1 \leq N,M \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
Output
Print the answer.
Sample Input 1
2 2 1 6 4 9
Sample Output 1
2
Here is the difference for each of the four pair of an element of A and an element of B: \lvert 1-4\rvert=3, \lvert 1-9\rvert=8, \lvert 6-4\rvert=2, and \lvert 6-9\rvert=3. We should print the minimum of these values, or 2.
Sample Input 2
1 1 10 10
Sample Output 2
0
Sample Input 3
6 8 82 76 82 82 71 70 17 39 67 2 45 35 22 24
Sample Output 3
3
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
ポエムオンラインジャッジ (Poem Online Judge, 以下 POJ と表記) は提出された文字列に得点をつけるオンラインジャッジです。
POJ に N 回の提出がありました。早い方から i 番目の提出では文字列 S_i が提出されて、得点は T_i でした。(同じ文字列が複数回提出される場合もあります)
ただし、POJ では 同じ文字列を提出しても得点が等しいとは限らない のに注意してください。
N 回の提出のうち、その提出よりも早い提出であって文字列が一致するものが存在しないような提出を オリジナル であると呼びます。
また、オリジナルな提出の中で最も得点が高いものを 最優秀賞 と呼びます。ただし、そのような提出が複数ある場合は、最も提出が早いものを最優秀賞とします。
最優秀賞は早い方から何番目の提出ですか？
制約
- 1 \leq N \leq 10^5
- S_i は英小文字からなる文字列
- S_i の長さは 1 以上 10 以下
- 0 \leq T_i \leq 10^9
- N, T_i は整数
入力
入力は以下の形式で標準入力から与えられる。
N S_1 T_1 S_2 T_2 \vdots S_N T_N
出力
答えを出力せよ。
入力例 1
3 aaa 10 bbb 20 aaa 30
出力例 1
2
以下では早い方から i 番目の提出を提出 i と呼びます。
オリジナルな提出は提出 1 と 提出 2 です。提出 3 は提出 1 と文字列が一致しているためオリジナルではありません。
オリジナルな提出のうち最も得点が高い提出は提出 2 です。よってこれが最優秀賞になります。
入力例 2
5 aaa 9 bbb 10 ccc 10 ddd 10 bbb 11
出力例 2
2
オリジナルな提出は提出 1・提出 2・提出 3・提出 4 です。
その中で最も得点が高い提出は提出 2・提出 3・提出 4 です。この場合はこの中でもっとも提出の早い提出 2 を最優秀賞とします。
このように、オリジナルな提出の中で最も得点が高い提出が複数ある場合は、さらにその中で最も提出が早いものを最優秀賞とするのに注意してください。
入力例 3
10 bb 3 ba 1 aa 4 bb 1 ba 5 aa 9 aa 2 ab 6 bb 5 ab 3
出力例 3
8
Score : 300 points
Problem Statement
Poem Online Judge (POJ) is an online judge that gives scores to submitted strings.
There were N submissions to POJ. In the i-th earliest submission, string S_i was submitted, and a score of T_i was given. (The same string may have been submitted multiple times.)
Note that POJ may not necessarily give the same score to submissions with the same string.
A submission is said to be an original submission if the string in the submission is never submitted in any earlier submission.
A submission is said to be the best submission if it is an original submission with the highest score. If there are multiple such submissions, only the earliest one is considered the best submission.
Find the index of the best submission.
Constraints
- 1 \leq N \leq 10^5
- S_i is a string consisting of lowercase English characters.
- S_i has a length between 1 and 10, inclusive.
- 0 \leq T_i \leq 10^9
- N and T_i are integers.
Input
Input is given from Standard Input in the following format:
N S_1 T_1 S_2 T_2 \vdots S_N T_N
Output
Print the answer.
Sample Input 1
3 aaa 10 bbb 20 aaa 30
Sample Output 1
2
We will refer to the i-th earliest submission as Submission i.
Original submissions are Submissions 1 and 2. Submission 3 is not original because it has the same string as that in Submission 1.
Among the original submissions, Submission 2 has the highest score. Therefore, this is the best submission.
Sample Input 2
5 aaa 9 bbb 10 ccc 10 ddd 10 bbb 11
Sample Output 2
2
Original submissions are Submissions 1, 2, 3, and 4.
Among them, Submissions 2, 3, and 4 have the highest scores. In this case, the earliest submission among them, Submission 2, is the best.
As in this sample, beware that if multiple original submissions have the highest scores, only the one with the earliest among them is considered the best submission.
Sample Input 3
10 bb 3 ba 1 aa 4 bb 1 ba 5 aa 9 aa 2 ab 6 bb 5 ab 3
Sample Output 3
8
実行時間制限: 4 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
N = 2^{20} 項からなる数列 A = (A_0, A_1, \dots, A_{N - 1}) があります。はじめ、全ての要素は -1 です。
Q 個のクエリを順番に処理してください。i \, (1 \leq i \leq Q) 個目のクエリは t_i = 1 または t_i = 2 を満たす整数 t_i および整数 x_i で表され、内容は以下の通りです。
- t_i = 1 のとき、以下の処理を順番に行う。
- 整数 h を h = x_i で定める。
- A_{h \bmod N} \neq -1 である間、h の値を 1 増やすことを繰り返す。この問題の制約下でこの操作が有限回で終了することは証明できる。
- A_{h \bmod N} の値を x_i で書き換える。
- t_i = 2 のとき、その時点での A_{x_i \bmod N} の値を出力する。
なお、整数 a, b に対し、a を b で割った余りを a \bmod b と表します。
制約
- 1 \leq Q \leq 2 \times 10^5
- t_i \in \{ 1, 2 \} \, (1 \leq i \leq Q)
- 0 \leq x_i \leq 10^{18} \, (1 \leq i \leq Q)
- t_i = 2 であるような i \, (1 \leq i \leq Q) が 1 つ以上存在する。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
Q
t_1 x_1
\vdots
t_{Q} x_{Q}
出力
t_i = 2 であるようなクエリに対し、それぞれ答えを 1 行に出力せよ。そのようなクエリが 1 つ以上存在することは保証される。
入力例 1
4 1 1048577 1 1 2 2097153 2 3
出力例 1
1048577 -1
x_1 \bmod N = 1 であるので、1 番目のクエリによって A_1 = 1048577 となります。
2 番目のクエリにおいて、はじめ h = x_2 ですが、A_{h \bmod N} = A_{1} \neq -1 であるので h の値を 1 増やします。すると A_{h \bmod N} = A_{2} = -1 となるので、このクエリによって A_2 = 1 となります。
3 番目のクエリにおいて、A_{x_3 \bmod N} = A_{1} = 1048577 を出力します。
4 番目のクエリにおいて、A_{x_4 \bmod N} = A_{3} = -1 を出力します。
この問題において N = 2^{20} = 1048576 は定数であり、入力では与えられないことに注意してください。
Score : 400 points
Problem Statement
There is a sequence A = (A_0, A_1, \dots, A_{N - 1}) with N = 2^{20} terms. Initially, every term is -1.
Process Q queries in order. The i-th query (1 \leq i \leq Q) is described by an integer t_i such that t_i = 1 or t_i = 2, and another integer x_i, as follows.
- If t_i = 1, do the following in order.
- Define an integer h as h = x_i.
- While A_{h \bmod N} \neq -1, keep adding 1 to h. We can prove that this process ends after finite iterations under the Constraints of this problem.
- Replace the value of A_{h \bmod N} with x_i.
- If t_i = 2, print the value of A_{x_i \bmod N} at that time.
Here, for integers a and b, a \bmod b denotes the remainder when a is divided by b.
Constraints
- 1 \leq Q \leq 2 \times 10^5
- t_i \in \{ 1, 2 \} \, (1 \leq i \leq Q)
- 0 \leq x_i \leq 10^{18} \, (1 \leq i \leq Q)
- There is at least one i (1 \leq i \leq Q) such that t_i = 2.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Q
t_1 x_1
\vdots
t_{Q} x_{Q}
Output
For each query with t_i = 2, print the response in one line. It is guaranteed that there is at least one such query.
Sample Input 1
4 1 1048577 1 1 2 2097153 2 3
Sample Output 1
1048577 -1
We have x_1 \bmod N = 1, so the first query sets A_1 = 1048577.
In the second query, initially we have h = x_2, for which A_{h \bmod N} = A_{1} \neq -1, so we add 1 to h. Now we have A_{h \bmod N} = A_{2} = -1, so this query sets A_2 = 1.
In the third query, we print A_{x_3 \bmod N} = A_{1} = 1048577.
In the fourth query, we print A_{x_4 \bmod N} = A_{3} = -1.
Note that, in this problem, N = 2^{20} = 1048576 is a constant and not given in input.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 425 点
問題文
人 1、人 2、\ldots、人 N からなる家系があります。i\geq 2 に対し、人 i の親は人 p_i です。
この家系の人たちは M 回保険に加入しました。i=1,2,\ldots,M に対し、i 番目の保険の加入者は人 x_i で、本人及びその y_i 代先までの子たちが補償対象者です。
1 個以上の保険の補償対象者になっている人が何人いるかを求めてください。
制約
- 2 \leq N \leq 3 \times 10^5
- 1 \leq M \leq 3 \times 10^5
- 1 \leq p_i \leq i-1
- 1 \leq x_i \leq N
- 1 \leq y_i \leq 3 \times 10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M p_2 \ldots p_N x_1 y_1 \vdots x_M y_M
出力
答えを出力せよ。
入力例 1
7 3 1 2 1 3 3 3 1 1 1 2 4 3
出力例 1
4
1 番目の保険について、人 1 の 1 代先の子たちは人 2 と人 4 なので人 1,2,4 が補償対象者です。
2 番目の保険について、人 1 の 1 代先の子たちは人 2 と人 4、2 代先の子は人 3 なので人 1,2,3,4 が補償対象者です。
3 番目の保険について、人 4 の 1,2,3 代先の子は存在しないので人 4 が補償対象者です。
以上より、1 個以上の保険の補償対象者になっている人は人 1,2,3,4 の 4 人です。
入力例 2
10 10 1 1 3 1 2 3 3 5 7 2 1 5 1 4 3 6 3 2 1 7 3 9 2 1 2 6 2 8 1
出力例 2
10
Score : 425 points
Problem Statement
There is a family consisting of person 1, person 2, \ldots, and person N. For i\geq 2, person i's parent is person p_i.
They bought insurance M times. For i=1,2,\ldots,M, person x_i bought the i-th insurance, which covers that person and their descendants in the next y_i generations.
How many people are covered by at least one insurance?
Constraints
- 2 \leq N \leq 3 \times 10^5
- 1 \leq M \leq 3 \times 10^5
- 1 \leq p_i \leq i-1
- 1 \leq x_i \leq N
- 1 \leq y_i \leq 3 \times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M p_2 \ldots p_N x_1 y_1 \vdots x_M y_M
Output
Print the answer.
Sample Input 1
7 3 1 2 1 3 3 3 1 1 1 2 4 3
Sample Output 1
4
The 1-st insurance covers people 1, 2, and 4, because person 1's 1-st generation descendants are people 2 and 4.
The 2-nd insurance covers people 1, 2, 3, and 4, because person 1's 1-st generation descendants are people 2 and 4, and person 1's 2-nd generation descendant is person 3.
The 3-rd insurance covers person 4, because person 4 has no 1-st, 2-nd, or 3-rd descendants.
Therefore, four people, people 1, 2, 3, and 4, are covered by at least one insurance.
Sample Input 2
10 10 1 1 3 1 2 3 3 5 7 2 1 5 1 4 3 6 3 2 1 7 3 9 2 1 2 6 2 8 1
Sample Output 2
10
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
文字列 S が与えられます。高橋君はこの文字列から以下の手順にしたがって新しい文字列 T を作ります。
- まず、S の文字のうちの一つ以上に印をつける。ただし、印をつけた文字どうしが隣り合ってはならない。
- 次に、印がついていない文字を全て削除する。
- 最後に、残った文字列を T とする。ただし、この時に文字を並び替えてはならない。
T としてありうる文字列は何種類ありますか？ (10^9 + 7) で割ったあまりを求めてください。
制約
- S は英小文字のみからなる長さ 1 以上 2 \times 10^5 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
T としてありうる文字列の種類数を (10^9 + 7) で割ったあまりを出力せよ。
入力例 1
abc
出力例 1
4
T としてありうるものは a、 b、 c、 ac の 4 つです。
S の 1 文字目のみに印をつけたとき T は a、
S の 2 文字目のみに印をつけたとき T は b、
S の 3 文字目のみに印をつけたとき T は c、
S の 1 文字目と 3 文字目のみに印をつけたとき T は ac、
となります。例えば 1 文字目と 2 文字目の両方に印をつけることはできないことに注意してください。
入力例 2
aa
出力例 2
1
T としてありうるものは a のみです。
印をつけた位置が異なっていても T が同じ文字列となる可能性があることに注意してください。
入力例 3
acba
出力例 3
6
T としてありうるものは a、 b、 c、 aa、 ab、 ca の 6 つです。
入力例 4
chokudai
出力例 4
54
Score : 500 points
Problem Statement
Given is a string S. From this string, Takahashi will make a new string T as follows.
- First, mark one or more characters in S. Here, no two marked characters should be adjacent.
- Next, delete all unmarked characters.
- Finally, let T be the remaining string. Here, it is forbidden to change the order of the characters.
How many strings are there that can be obtained as T? Find the count modulo (10^9 + 7).
Constraints
- S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the number of different strings that can be obtained as T, modulo (10^9 + 7).
Sample Input 1
abc
Sample Output 1
4
There are four strings that can be obtained as T: a, b, c, and ac.
Marking the first character of S yields a;
marking the second character of S yields b;
marking the third character of S yields c;
marking the first and third characters of S yields ac.
Note that it is forbidden to, for example, mark both the first and second characters.
Sample Input 2
aa
Sample Output 2
1
There is just one string that can be obtained as T, which is a.
Note that marking different positions may result in the same string.
Sample Input 3
acba
Sample Output 3
6
There are six strings that can be obtained as T: a, b, c, aa, ab, and ca.
Sample Input 4
chokudai
Sample Output 4
54