実行時間制限: 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
配点 : 200 点
問題文
AtCoder 国では、1 年が N か月からなる暦を使っています。 i 月 (1\leq i\leq N) は、i 月 1 日から i 月 D _ i 日までの D _ i 日からなります。
AtCoder 国において、1 年のうち日付がゾロ目になる日が何日あるか求めてください。
ただし、i 月 j 日 (1\leq i\leq N,1\leq j\leq D _ i) の日付がゾロ目になるとは、1 種類の数字だけを用いて i と j を十進法で表すことができることをいいます。
制約
- 1\leq N\leq100
- 1\leq D _ i\leq100\ (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D _ 1 D _ 2 \ldots D _ N
出力
答えを出力せよ。
入力例 1
12 31 29 31 30 31 30 31 31 30 31 30 31
出力例 1
13
AtCoder 国では、 1 月 1 日、1 月 11 日、2 月 2 日、2 月 22 日、3 月 3 日、4 月 4 日、5 月 5 日、6 月 6 日、7 月 7 日、8 月 8 日、9 月 9 日、11 月 1 日、11 月 11 日の合計 13 日の日付がゾロ目になります。
入力例 2
10 10 1 2 3 4 5 6 7 8 100
出力例 2
1
AtCoder 国では、1 月 1 日のみが日付がゾロ目になります。
入力例 3
30 73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32
出力例 3
15
Score : 200 points
Problem Statement
AtCoder Kingdom uses a calendar whose year has N months. Month i (1\leq i\leq N) has D _ i days, from day 1 of month i to day D _ i of month i.
How many days in a year of AtCoder have "repdigits" dates?
Here, day j of month i (1\leq i\leq N,1\leq j\leq D _ i) is said to have a repdigit date if and only if all digits in the decimal notations of i and j are the same.
Constraints
- 1\leq N\leq100
- 1\leq D _ i\leq100\ (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D _ 1 D _ 2 \ldots D _ N
Output
Print the answer.
Sample Input 1
12 31 29 31 30 31 30 31 31 30 31 30 31
Sample Output 1
13
In AtCoder Kingdom, the days that have repdigit dates are January 1, January 11, February 2, February 22, March 3, April 4, May 5, June 6, July 7, August 8, September 9, November 1, and November 11, for a total of 13 days.
Sample Input 2
10 10 1 2 3 4 5 6 7 8 100
Sample Output 2
1
In AtCoder Kingdom, only January 1 has a repdigit date.
Sample Input 3
30 73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32
Sample Output 3
15
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は数直線上の座標 0 の位置にいます。
これから高橋君は N 回のジャンプを行います。i \, (1 \leq i \leq N) 回目のジャンプでは、正の方向に a_i または b_i 移動します。
N 回のジャンプの後に座標 X の位置にいるようにすることはできますか？
制約
- 1 \leq N \leq 100
- 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
- 1 \leq X \leq 10000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X a_1 b_1 \vdots a_N b_N
出力
N 回のジャンプの後に座標 X の位置にいるようにすることができるならば Yes と、そうでないなら No と出力せよ。
入力例 1
2 10 3 6 4 5
出力例 1
Yes
1 回目のジャンプでは b_1 (= 6) 移動し、2 回目のジャンプでは a_2 (= 4) 移動することで、座標 X (= 10) の位置にいるようにすることができます。
入力例 2
2 10 10 100 10 100
出力例 2
No
1 回目のジャンプの後に座標 X (= 10) の位置にいるようにすることはできますが、全てのジャンプの後に座標 X (= 10) の位置にいるようにすることはできません。
入力例 3
4 12 1 8 5 7 3 4 2 6
出力例 3
Yes
Score : 300 points
Problem Statement
Takahashi is standing at the coordinate 0 on a number line.
He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.
Is it possible for him to be at the coordinate X after N jumps?
Constraints
- 1 \leq N \leq 100
- 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
- 1 \leq X \leq 10000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X a_1 b_1 \vdots a_N b_N
Output
If it is possible for Takahashi to be at the coordinate X after N jumps, print Yes; otherwise, print No.
Sample Input 1
2 10 3 6 4 5
Sample Output 1
Yes
By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).
Sample Input 2
2 10 10 100 10 100
Sample Output 2
No
He can be at the coordinate X (= 10) after the first jump, but not after all jumps.
Sample Input 3
4 12 1 8 5 7 3 4 2 6
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君と青木君は 2 人で次の対戦ゲームをします。
高橋君が先手でゲームを始め、ゲームが終了するまでの間、 2 人は交互に 1 以上 2N+1 以下の整数を 1 つずつ宣言します。 どちらかが一度でも宣言した整数は、それ以降どちらも二度と宣言することが出来ません。 先に整数を宣言することが出来なくなった方のプレイヤーの負けとなり、負けなかった方のプレイヤーの勝ちとなります。
このゲームでは必ず高橋君が勝ちます。 高橋君の立場で実際にゲームを行い、ゲームに勝ってください。
制約
- 1 \leq N \leq 1000
- N は整数
入出力
この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。
あなたのプログラムが高橋君の立場で、ジャッジプログラムが青木君の立場でゲームを行います。
まず、あなたのプログラムに標準入力から正の整数 N が与えられます。 その後、ゲームが終了するまで下記の手順を繰り返します。
- あなたのプログラムが、高橋君が宣言する整数として、1 以上 2N+1 以下の整数を標準出力に出力します。（どちらかのプレイヤーによってすでに宣言されている整数を出力することは出来ません。）
- ジャッジプログラムによって、青木君が宣言する整数があなたのプログラムに標準入力から与えられます。（どちらかのプレイヤーによってすでに宣言されている整数が入力されることはありません。） ただし、青木君が宣言できる整数が残っていない場合は、代わりに 0 が与えられ高橋君の勝ちでゲームが終了します。
注意点
- 出力を行うたびに標準出力をflushしてください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
- 高橋君の勝ちでゲームが終了したあと、あなたのプログラムは直ちに終了しなければなりません。そうしなかった場合、ジャッジ結果が AC とならない可能性があります。
- ゲームの途中で不正な出力を行った場合（例えば、すでにどちらかのプレイヤーによって宣言されている整数を出力した場合）は不正解となりますが、そのときのジャッジ結果は不定です。WA になるとは限りません。
入出力例
| 入力 | 出力 | 説明 |
|---|---|---|
| 2 | まず整数 N が与えられます。 | |
| 1 | 高橋君が 1 を宣言します。 | |
| 3 | 青木君が 3 を宣言します。 | |
| 2 | 高橋君が 2 を宣言します。 | |
| 4 | 青木君が 4 を宣言します。 | |
| 5 | 高橋君が 5 を宣言します。 | |
| 0 | 青木君が宣言できる整数が残っていないため、高橋君の勝ちでゲームが終了します。 |
Score : 300 points
Problem Statement
Takahashi and Aoki will play the following game against each other.
Starting from Takahashi, the two alternatingly declare an integer between 1 and 2N+1 (inclusive) until the game ends. Any integer declared by either player cannot be declared by either player again. The player who is no longer able to declare an integer loses; the player who didn't lose wins.
In this game, Takahashi will always win. Your task is to actually play the game on behalf of Takahashi and win the game.
Constraints
- 1 \leq N \leq 1000
- N is an integer.
Input and Output
This task is an interactive task (in which your program and the judge program interact with each other via inputs and outputs).
Your program plays the game on behalf of Takahashi, and the judge program plays the game on behalf of Aoki.
First, your program is given a positive integer N from Standard Input. Then, the following procedures are repeated until the game ends.
- Your program outputs an integer between 1 and 2N+1 (inclusive) to Standard Output, which defines the integer that Takahashi declares. (You cannot output an integer that is already declared by either player.)
- The integer that Aoki declares is given by the judge program to your program from Standard Input. (No integer that is already declared by either player will be given.) If Aoki has no more integer to declare, 0 is given instead, which means that the game ended and Takahashi won.
Notes
- After each output, you must flush Standard Output. Otherwise, you may get TLE.
- After the game ended and Takahashi won, the program must be terminated immediately. Otherwise, the judge does not necessarily give AC.
- If your program outputs something that violates the rules of the game (such as an integer that has already been declared by either player), your answer is considered incorrect. In such case, the verdict is indeterminate. It does not necessarily give WA.
Sample Input and Output
| Input | Output | Description |
|---|---|---|
| 2 | First, an integer N is given. | |
| 1 | Takahashi declares an integer 1. | |
| 3 | Aoki declares an integer 3. | |
| 2 | Takahashi declares an integer 2. | |
| 4 | Aoki declares an integer 4. | |
| 5 | Takahashi declares an integer 5. | |
| 0 | Aoki has no more integer to declare, so Takahashi wins, and the game ends. |
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
正整数 A,B が与えられます。
あなたは、A=B になるまで以下の操作を繰り返します。
- A,B の大小関係に応じて、次の 2 個のうちどちらかの処理を行う。
- A > B ならば、A を A-B で置き換える。
- A < B ならば、B を B-A で置き換える。
A=B になるまで、操作を何回行うか求めてください。ただし、有限回の操作で A=B になることが保証されます。
制約
- 1 \le A,B \le 10^{18}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
入力例 1
3 8
出力例 1
4
始め、A=3,B=8 です。操作は以下のように行われます。
- A<B であるため、B を B-A=5 で置き換える。A=3,B=5 となる。
- A<B であるため、B を B-A=2 で置き換える。A=3,B=2 となる。
- A>B であるため、A を A-B=1 で置き換える。A=1,B=2 となる。
- A<B であるため、B を B-A=1 で置き換える。A=1,B=1 となる。
よって、操作回数は 4 回です。
入力例 2
1234567890 1234567890
出力例 2
0
入力が 32bit 整数型に収まらないことがあることに注意してください。
入力例 3
1597 987
出力例 3
15
Score : 400 points
Problem Statement
You are given positive integers A and B.
You will repeat the following operation until A=B:
- compare A and B to perform one of the following two:
- if A > B, replace A with A-B;
- if A < B, replace B with B-A.
How many times will you repeat it until A=B? It is guaranteed that a finite repetition makes A=B.
Constraints
- 1 \le A,B \le 10^{18}
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print the answer.
Sample Input 1
3 8
Sample Output 1
4
Initially, A=3 and B=8. You repeat the operation as follows:
- A<B, so replace B with B-A=5, making A=3 and B=5.
- A<B, so replace B with B-A=2, making A=3 and B=2.
- A>B, so replace A with A-B=1, making A=1 and B=2.
- A<B, so replace B with B-A=1, making A=1 and B=1.
Thus, you repeat it four times.
Sample Input 2
1234567890 1234567890
Sample Output 2
0
Note that the input may not fit into a 32-bit integer type.
Sample Input 3
1597 987
Sample Output 3
15