Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
英大文字からなる文字列 S が与えられます。S の各文字を空白で区切り、その順で 1 文字ずつ出力してください。
制約
- S は長さ 2 以上 100 以下の英大文字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の各文字を空白で区切り、1 文字ずつ出力せよ。
入力例 1
ABC
出力例 1
A B C
A, B, C を空白で区切り、1 文字ずつ出力してください。
C の後ろに空白を出力する必要がないことに注意してください。
入力例 2
ZZZZZZZ
出力例 2
Z Z Z Z Z Z Z
入力例 3
OOXXOO
出力例 3
O O X X O O
Score : 100 points
Problem Statement
You are given a string S consisting of uppercase English letters. Separate each character of S with a space and print them one by one in order.
Constraints
- S is a string consisting of uppercase English letters with a length between 2 and 100, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Separate each character of S with a space and print them one by one.
Sample Input 1
ABC
Sample Output 1
A B C
Separate A, B, and C with spaces and print them one by one.
There is no need to print a space after C.
Sample Input 2
ZZZZZZZ
Sample Output 2
Z Z Z Z Z Z Z
Sample Input 3
OOXXOO
Sample Output 3
O O X X O O
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
ある提案に対し、N 人の人が賛成か反対かを表明しています。なお、N は奇数です。
i \, (i = 1, 2, \dots, N) 番目の人の意見は文字列 S_i で表され、S_i = For のとき賛成しており、S_i = Against のとき反対しています。
過半数の人がこの提案に賛成しているかどうかを判定してください。
制約
- N は 1 以上 99 以下の奇数
- 全ての i = 1, 2, \dots, N に対し、S_i =
Forまたは S_i =Against
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
N 人のうち過半数が提案に賛成しているならば Yes、そうでなければ No と出力せよ。
入力例 1
3 For Against For
出力例 1
Yes
提案に賛成している人数は 2 人であり、これは半数を超えているので Yes と出力します。
入力例 2
5 Against Against For Against For
出力例 2
No
提案に賛成している人数は 2 人であり、これは半数以下なので No と出力します。
入力例 3
1 For
出力例 3
Yes
Score : 100 points
Problem Statement
There are N people. Each of them agrees or disagrees with a proposal. Here, N is an odd number.
The i-th (i = 1, 2, \dots, N) person's opinion is represented by a string S_i: the person agrees if S_i = For and disagrees if S_i = Against.
Determine whether the majority agrees with the proposal.
Constraints
- N is an odd number between 1 and 99, inclusive.
- S_i =
Foror S_i =Against, for all i = 1, 2, \dots, N.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print Yes if the majority of the N people agree with the proposal; print No otherwise.
Sample Input 1
3 For Against For
Sample Output 1
Yes
The proposal is supported by two people, which is the majority, so Yes should be printed.
Sample Input 2
5 Against Against For Against For
Sample Output 2
No
The proposal is supported by two people, which is not the majority, so No should be printed.
Sample Input 3
1 For
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
整数 N が与えられます。
非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを辞書順で小さい方から順に全て出力してください。
非負整数の組の辞書順とは？
非負整数の組 (x,y,z) が (x',y',z') より辞書順で小さいとは、下記のいずれかが成り立つことを言います。
- x < x' である
- x=x' かつ y< y' である
- x=x' かつ y=y' かつ z< z' である
制約
- 0 \leq N \leq 21
- N は整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを、1 行に 1 組ずつ x,y,z を空白区切りで、辞書順で小さい方から順に全て出力せよ。
入力例 1
3
出力例 1
0 0 0 0 0 1 0 0 2 0 0 3 0 1 0 0 1 1 0 1 2 0 2 0 0 2 1 0 3 0 1 0 0 1 0 1 1 0 2 1 1 0 1 1 1 1 2 0 2 0 0 2 0 1 2 1 0 3 0 0
入力例 2
4
出力例 2
0 0 0 0 0 1 0 0 2 0 0 3 0 0 4 0 1 0 0 1 1 0 1 2 0 1 3 0 2 0 0 2 1 0 2 2 0 3 0 0 3 1 0 4 0 1 0 0 1 0 1 1 0 2 1 0 3 1 1 0 1 1 1 1 1 2 1 2 0 1 2 1 1 3 0 2 0 0 2 0 1 2 0 2 2 1 0 2 1 1 2 2 0 3 0 0 3 0 1 3 1 0 4 0 0
Score : 150 points
Problem Statement
You are given an integer N.
Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.
What is lexicographical order for non-negative integer triples?
A triple of non-negative integers (x,y,z) is said to be lexicographically smaller than (x',y',z') if and only if one of the following holds:
- x < x';
- x=x' and y< y';
- x=x' and y=y' and z< z'.
Constraints
- 0 \leq N \leq 21
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order, with x,y,z separated by spaces, one triple per line.
Sample Input 1
3
Sample Output 1
0 0 0 0 0 1 0 0 2 0 0 3 0 1 0 0 1 1 0 1 2 0 2 0 0 2 1 0 3 0 1 0 0 1 0 1 1 0 2 1 1 0 1 1 1 1 2 0 2 0 0 2 0 1 2 1 0 3 0 0
Sample Input 2
4
Sample Output 2
0 0 0 0 0 1 0 0 2 0 0 3 0 0 4 0 1 0 0 1 1 0 1 2 0 1 3 0 2 0 0 2 1 0 2 2 0 3 0 0 3 1 0 4 0 1 0 0 1 0 1 1 0 2 1 0 3 1 1 0 1 1 1 1 1 2 1 2 0 1 2 1 1 3 0 2 0 0 2 0 1 2 0 2 2 1 0 2 1 1 2 2 0 3 0 0 3 0 1 3 1 0 4 0 0
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
配点 : 300 点
問題文
ピザ屋で働く高橋くんは、まかないとして美味しいチーズピザを作ることにしました。
今、高橋くんの目の前に N 種類のチーズがあります。
i 種類目のチーズは 1 [g] あたりのおいしさが A_i で、 B_i [g] あります。
ピザのおいしさは、ピザに乗せたチーズのおいしさの総和で決まります。
但し、チーズを使いすぎると怒られてしまうため、乗せたチーズの重さは合計で W [g] 以下である必要があります。
この条件のもとで、可能なピザのおいしさの最大値を求めてください。
制約
- 入力は全て整数
- 1 \le N \le 3 \times 10^5
- 1 \le W \le 3 \times 10^8
- 1 \le A_i \le 10^9
- 1 \le B_i \le 1000
入力
入力は以下の形式で標準入力から与えられる。
N W A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを整数として出力せよ。
入力例 1
3 5 3 1 4 2 2 3
出力例 1
15
1 種類目のチーズを 1 [g] 、 2 種類目のチーズを 2 [g] 、 3 種類目のチーズを 2 [g] 乗せるのが最適です。
このとき、ピザのおいしさは 15 となります。
入力例 2
4 100 6 2 1 5 3 9 8 7
出力例 2
100
チーズの重量の総和が W [g] に満たないケースもあります。
入力例 3
10 3141 314944731 649 140276783 228 578012421 809 878510647 519 925326537 943 337666726 611 879137070 306 87808915 39 756059990 244 228622672 291
出力例 3
2357689932073
Score : 300 points
Problem Statement
Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is A_i per gram, and B_i grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.
Constraints
- All values in input are integers.
- 1 \le N \le 3 \times 10^5
- 1 \le W \le 3 \times 10^8
- 1 \le A_i \le 10^9
- 1 \le B_i \le 1000
Input
Input is given from Standard Input in the following format:
N W A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print the answer as an integer.
Sample Input 1
3 5 3 1 4 2 2 3
Sample Output 1
15
The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.
Sample Input 2
4 100 6 2 1 5 3 9 8 7
Sample Output 2
100
There may be less than W grams of cheese in total.
Sample Input 3
10 3141 314944731 649 140276783 228 578012421 809 878510647 519 925326537 943 337666726 611 879137070 306 87808915 39 756059990 244 228622672 291
Sample Output 3
2357689932073