Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
下の画像で示す図において、a 番の点と b 番の点が線で直接結ばれているかを答えてください。
制約
- 1 \leq a \lt b \leq 10
- a, b は整数
入力
入力は以下の形式で標準入力から与えられる。
a b
出力
a 番の点と b 番の点が線で直接結ばれている場合は Yes を出力し、結ばれていない場合は No を出力せよ。
ジャッジは英大文字と英小文字を厳密に区別することに注意せよ。
入力例 1
4 5
出力例 1
Yes
問題文で示した図において、4 番の点と 5 番の点は線で直接結ばれています。
よって、Yes を出力します。
入力例 2
3 5
出力例 2
No
問題文で示した図において、3 番の点と 5 番の点は線で直接結ばれていません。
よって、No を出力します。
入力例 3
1 10
出力例 3
Yes
Score : 100 points
Problem Statement
In the figure shown in the image below, are the points numbered a and b directly connected by a line segment?
Constraints
- 1 \leq a \lt b \leq 10
- a and b are integers.
Input
Input is given from Standard Input in the following format:
a b
Output
If the points numbered a and b are directly connected by a line segment, print Yes; otherwise, print No.
The judge is case-sensitive: be sure to print uppercase and lowercase letters correctly.
Sample Input 1
4 5
Sample Output 1
Yes
In the figure shown in the Problem Statement, the points numbered 4 and 5 are directly connected by a line segment.
Thus, Yes should be printed.
Sample Input 2
3 5
Sample Output 2
No
In the figure shown in the Problem Statement, the points numbered 3 and 5 are not directly connected by a line segment.
Thus, No should be printed.
Sample Input 3
1 10
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
上下左右に広がる H 行 W 列のマス目があり、各マスにはコマが置かれているか、何も置かれていないかのどちらかです。
マス目の状態は H 個の長さ W の文字列 S_1, S_2, \ldots, S_H によって表され、
S_i の j 文字目が # のとき上から i 行目かつ左から j 列目のマスにはコマが置かれていることを、
S_i の j 文字目が . のとき上から i 行目かつ左から j 列目のマスには何も置かれていないことを表しています。
マス目上のマスのうち、コマが置かれているようなものの個数を求めてください。
制約
- 1\leq H,W \leq 10
- H,W は整数
- S_i は
#と.のみからなる長さ W の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H
出力
コマが置かれているマスの個数を整数で出力せよ。
入力例 1
3 5 #.... ..... .##..
出力例 1
3
- 上から 1 行目かつ左から 1 列目のマス
- 上から 3 行目かつ左から 2 列目のマス
- 上から 3 行目かつ左から 3 列目のマス
の計 3 つのマスにコマが置かれているため、3 を出力します。
入力例 2
1 10 ..........
出力例 2
0
どのマスにもコマは置かれていないため、0 を出力します。
入力例 3
6 5 #.#.# ....# ..##. ####. ..#.. #####
出力例 3
16
Score : 100 points
Problem Statement
There is a grid with H rows from top to bottom and W columns from left to right. Each square has a piece placed on it or is empty.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W.
If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left has a piece on it;
if the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is empty.
How many squares in the grid have pieces on them?
Constraints
- 1\leq H,W \leq 10
- H and W are integers.
- S_i is a string of length W consisting of
#and..
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
Print the number of squares with pieces as an integer.
Sample Input 1
3 5 #.... ..... .##..
Sample Output 1
3
The following three squares have pieces on them:
- the square at the 1-st row from the top and 1-st column from the left;
- the square at the 3-rd row from the top and 2-nd column from the left;
- the square at the 3-rd row from the top and 3-rd column from the left.
Thus, 3 should be printed.
Sample Input 2
1 10 ..........
Sample Output 2
0
Since no square has a piece on it, 0 should be printed.
Sample Input 3
6 5 #.#.# ....# ..##. ####. ..#.. #####
Sample Output 3
16
Time Limit: 2 sec / Memory Limit: 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................... ............................................................
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
正整数 N が与えられるので、 2^k \le N となる最大の整数 k を求めてください。
制約
- N は 1 \le N \le 10^{18} を満たす整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
6
出力例 1
2
- k=2 は 2^2=4 \le 6 を満たします。
- k \ge 3 である全ての整数 k について 2^k > 6 となります。
以上より、答えは k=2 となります。
入力例 2
1
出力例 2
0
2^0=1 であることに注意してください。
入力例 3
1000000000000000000
出力例 3
59
入力が 32 bit 整数に収まらない場合があります。
Score : 200 points
Problem Statement
Given a positive integer N, find the maximum integer k such that 2^k \le N.
Constraints
- N is an integer satisfying 1 \le N \le 10^{18}.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
6
Sample Output 1
2
- k=2 satisfies 2^2=4 \le 6.
- For every integer k such that k \ge 3, 2^k > 6 holds.
Therefore, the answer is k=2.
Sample Input 2
1
Sample Output 2
0
Note that 2^0=1.
Sample Input 3
1000000000000000000
Sample Output 3
59
The input value may not fit into a 32-bit integer.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
縦 H マス, 横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と呼びます。
はじめ、グリッド上には、ある 縦横 2 マス以上 の部分長方形の内部にあるマスにクッキーが 1 枚ずつ置かれていて、それ以外のマスにはクッキーが置かれていません。
形式的に説明すると、以下の条件を全て満たす 4 つの整数の組 (a,b,c,d) がただ 1 つ存在します。
- 1 \leq a \lt b \leq H
- 1 \leq c \lt d \leq W
- グリッド上のマスのうち、a \leq i \leq b, c \leq j \leq d を満たす全てのマス (i, j) にはクッキーが 1 枚ずつ置かれていて、それ以外のマスにはクッキーが置かれていない。
ところが、すぬけ君がグリッド上のクッキーのどれか 1 枚を取って食べてしまいました。
すぬけ君がクッキーを取ったマスは、クッキーが置かれていない状態に変わります。
すぬけ君がクッキーを食べた後のグリッドの状態が入力として与えられます。
マス (i, j) の状態は文字 S_{i,j} として与えられて、# はクッキーが置かれているマスを, . はクッキーが置かれていないマスを意味します。
すぬけ君が食べたクッキーが元々置かれていたマスを答えてください。(答えは一意に定まります。)
制約
- 2 \leq H, W \leq 500
- S_{i,j} は
#または.
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1}S_{1,2}\dotsS_{1,W}
S_{2,1}S_{2,2}\dotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\dotsS_{H,W}
出力
すぬけ君が食べたクッキーが元々置かれていたマスを (i, j) とする。i, j をこの順に空白区切りで出力せよ。
入力例 1
5 6 ...... ..#.#. ..###. ..###. ......
出力例 1
2 4
はじめ、クッキーは (2, 3) を左上、(4, 5) を右下とする部分長方形の内部にあるマスに置かれていて、すぬけ君は (2, 4) にあるクッキーを食べたことがわかります。よって (2, 4) を出力します。
入力例 2
3 2 #. ## ##
出力例 2
1 2
はじめ、クッキーは (1, 1) を左上、(3, 2) を右下とする部分長方形の内部にあるマスに置かれていて、すぬけ君は (1, 2) にあるクッキーを食べたことがわかります。
入力例 3
6 6 ..#### ..##.# ..#### ..#### ..#### ......
出力例 3
2 5
Score : 300 points
Problem Statement
There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.
Initially, there was one cookie on each square inside a rectangle whose height and width were at least 2 squares long, and no cookie on the other squares.
Formally, there was exactly one quadruple of integers (a,b,c,d) that satisfied all of the following conditions.
- 1 \leq a \lt b \leq H
- 1 \leq c \lt d \leq W
- There was one cookie on each square (i, j) such that a \leq i \leq b, c \leq j \leq d, and no cookie on the other squares.
However, Snuke took and ate one of the cookies on the grid.
The square that contained that cookie is now empty.
As the input, you are given the state of the grid after Snuke ate the cookie.
The state of the square (i, j) is given as the character S_{i,j}, where # means a square with a cookie, and . means a square without one.
Find the square that contained the cookie eaten by Snuke. (The answer is uniquely determined.)
Constraints
- 2 \leq H, W \leq 500
- S_{i,j} is
#or..
Input
The input is given from Standard Input in the following format:
H W
S_{1,1}S_{1,2}\dotsS_{1,W}
S_{2,1}S_{2,2}\dotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\dotsS_{H,W}
Output
Let (i, j) the square contained the cookie eaten by Snuke. Print i and j in this order, separated by a space.
Sample Input 1
5 6 ...... ..#.#. ..###. ..###. ......
Sample Output 1
2 4
Initially, cookies were on the squares inside the rectangle with (2, 3) as the top-left corner and (4, 5) as the bottom-right corner, and Snuke ate the cookie on (2, 4). Thus, you should print (2, 4).
Sample Input 2
3 2 #. ## ##
Sample Output 2
1 2
Initially, cookies were placed on the squares inside the rectangle with (1, 1) as the top-left corner and (3, 2) as the bottom-right corner, and Snuke ate the cookie at (1, 2).
Sample Input 3
6 6 ..#### ..##.# ..#### ..#### ..#### ......
Sample Output 3
2 5
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: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
あなたは以下の連続する操作をちょうど一度だけ行います。
-
整数 x\ (0\leq x \leq N) を選ぶ。x として 0 を選んだ場合何もしない。 x として 1 以上の整数を選んだ場合、A_1,A_2,\ldots,A_x をそれぞれ L で置き換える。
-
整数 y\ (0\leq y \leq N) を選ぶ。y として 0 を選んだ場合何もしない。 y として 1 以上の整数を選んだ場合、A_{N},A_{N-1},\ldots,A_{N-y+1} をそれぞれ R で置き換える。
操作後の A の要素の総和として考えられる最小値を求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- -10^9 \leq L, R\leq 10^9
- -10^9 \leq A_i\leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L R A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
5 4 3 5 5 0 6 3
出力例 1
14
x=2,y=2 として操作をすると、数列 A = (4,4,0,3,3) となり、要素の総和は 14 になります。
これが達成可能な最小値です。
入力例 2
4 10 10 1 2 3 4
出力例 2
10
x=0,y=0 として操作をすると、数列 A = (1,2,3,4) となり、要素の総和は 10 になります。
これが達成可能な最小値です。
入力例 3
10 -5 -3 9 -6 10 -1 2 10 -1 7 -15 5
出力例 3
-58
L,R,A_i は負であることがあります。
Score : 400 points
Problem Statement
You are given an integer sequence of length N: A=(A_1,A_2,\ldots,A_N).
You will perform the following consecutive operations just once:
-
Choose an integer x (0\leq x \leq N). If x is 0, do nothing. If x is 1 or greater, replace each of A_1,A_2,\ldots,A_x with L.
-
Choose an integer y (0\leq y \leq N). If y is 0, do nothing. If y is 1 or greater, replace each of A_{N},A_{N-1},\ldots,A_{N-y+1} with R.
Print the minimum possible sum of the elements of A after the operations.
Constraints
- 1 \leq N \leq 2\times 10^5
- -10^9 \leq L, R\leq 10^9
- -10^9 \leq A_i\leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N L R A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
5 4 3 5 5 0 6 3
Sample Output 1
14
If you choose x=2 and y=2, you will get A = (4,4,0,3,3), for the sum of 14, which is the minimum sum achievable.
Sample Input 2
4 10 10 1 2 3 4
Sample Output 2
10
If you choose x=0 and y=0, you will get A = (1,2,3,4), for the sum of 10, which is the minimum sum achievable.
Sample Input 3
10 -5 -3 9 -6 10 -1 2 10 -1 7 -15 5
Sample Output 3
-58
L, R, and A_i may be negative.
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
AtCoder 王国では、N 種類のたこ焼きが売られています。i 種類目のたこ焼きの値段は A_i 円です。
高橋君は、合計で 1 個以上のたこ焼きを買います。このとき、同じたこ焼きを複数個買うことも許されます。
高橋君が支払う金額としてあり得るもののうち、安い方から K 番目の金額を求めてください。ただし、同じ金額を支払う方法が複数存在する場合は 1 回だけ数えます。
制約
- 1 \le N \le 10
- 1 \le K \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
4 6 20 25 30 100
出力例 1
50
AtCoder 王国で売られている 4 種類のたこ焼きは、それぞれ 20 円、25 円、30 円、100 円です。
高橋君の支払う金額としてあり得るものは、安い方から 6 個を列挙すると 20 円、25 円、30 円、40 円、45 円、50 円となります。よって、答えは 50 円です。
合計で 1 個以上たこ焼きを買う必要があることに注意してください。
入力例 2
2 10 2 1
出力例 2
10
同じ金額の買い方が何通りかあっても、重複してカウントしないことに注意してください。
入力例 3
10 200000 955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872
出力例 3
5705443819
Score : 500 points
Problem Statement
In AtCoder Kingdom, N kinds of takoyakis (ball-shaped Japanese food) are sold. A takoyaki of the i-th kind is sold for A_i yen.
Takahashi will buy at least one takoyaki in total. He is allowed to buy multiple takoyakis of the same kind.
Find the K-th lowest price that Takahashi may pay. Here, if there are multiple sets of takoyakis that cost the same price, the price is counted only once.
Constraints
- 1 \le N \le 10
- 1 \le K \le 2 \times 10^5
- 1 \le A_i \le 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
4 6 20 25 30 100
Sample Output 1
50
The four kinds of takoyakis sold in AtCoder Kingdom cost 20 yen, 25 yen, 30 yen, and 100 yen.
The six lowest prices that Takahashi may pay are 20 yen, 25 yen, 30 yen, 40 yen, 45 yen, and 50 yen. Thus, the answer is 50.
Note that at least one takoyaki must be bought.
Sample Input 2
2 10 2 1
Sample Output 2
10
Note that a price is not counted more than once even if there are multiple sets of takoyakis costing that price.
Sample Input 3
10 200000 955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872
Sample Output 3
5705443819
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
N 頂点 M 辺からなる単純な有向グラフ G があり、頂点には頂点 1, 頂点 2, \ldots, 頂点 N と番号がついています。 また、i (1\leq i\leq M) 本目の辺は頂点 U_i から頂点 V_i へ張られています。
高橋君がある頂点から始めて、G の上を有向辺に沿って頂点から頂点へ移動することを繰り返します。 G の頂点のうち、高橋君がうまく経路を選ぶことで、その頂点から始めていくらでも移動を繰り返すことができるようなものの個数を求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 0 \leq M \leq \min(N(N-1), 2\times 10^5)
- 1 \leq U_i,V_i\leq N
- U_i\neq V_i
- i\neq j ならば (U_i,V_i)\neq (U_j,V_j)
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
出力
答えを出力せよ。
入力例 1
5 5 1 2 2 3 3 4 4 2 4 5
出力例 1
4
頂点 2 を始点とした場合、頂点 2 \to 頂点 3 \to 頂点 4 \to 頂点 2 \to 頂点 3 \to \cdots
と高橋君はいくらでも移動を繰り返す事ができます。
頂点 3, 頂点 4 を始点とした場合も同様です。
頂点 1 からは最初に頂点 2 に移動して、以下同様にいくらでも行動を繰り返すことができます。
一方、頂点 5 からは一度も移動することができません。
よって、条件を満たすのは頂点 1, 2, 3, 4 の 4 つであるので、 4 を出力します。
入力例 2
3 2 1 2 2 1
出力例 2
2
単純な有向グラフにおいて、2 つの頂点の間を互いに逆向きに結ぶ辺が、ともに存在する事はあり得ることに注意してください。 また、G は連結であるとは限りません。
Score : 500 points
Problem Statement
We have a simple directed graph G with N vertices and M edges. The vertices are labeled as Vertex 1, Vertex 2, \ldots, Vertex N. The i-th edge (1\leq i\leq M) goes from Vertex U_i to Vertex V_i.
Takahashi will start at a vertex and repeatedly travel on G from one vertex to another along a directed edge. How many vertices of G have the following condition: Takahashi can start at that vertex and continue traveling indefinitely by carefully choosing the path?
Constraints
- 1 \leq N \leq 2\times 10^5
- 0 \leq M \leq \min(N(N-1), 2\times 10^5)
- 1 \leq U_i,V_i\leq N
- U_i\neq V_i
- (U_i,V_i)\neq (U_j,V_j) if i\neq j.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
Output
Print the answer.
Sample Input 1
5 5 1 2 2 3 3 4 4 2 4 5
Sample Output 1
4
When starting at Vertex 2, Takahashi can continue traveling indefinitely: 2 \to 3 \to 4 \to 2 \to 3 \to \cdots
The same goes when starting at Vertex 3 or Vertex 4.
From Vertex 1, he can first go to Vertex 2 and then continue traveling indefinitely again.
On the other hand, from Vertex 5, he cannot move at all.
Thus, four vertices ―Vertex 1, 2, 3, and 4― satisfy the conditions, so 4 should be printed.
Sample Input 2
3 2 1 2 2 1
Sample Output 2
2
Note that, in a simple directed graph, there may be two edges in opposite directions between the same pair of vertices. Additionally, G may not be connected.