実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
正整数 N,K 及び長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A に含まれる要素のうち、K の倍数であるもののみを全て取り出し、それらを K で割って出力してください。
制約
- 1\leq N,K\leq 100
- 1\leq A_1 < A_2 < \ldots < A_N \leq 100
- A には K の倍数が 1 個以上含まれる
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
A に含まれる要素のうち、K の倍数であるもの全てを K で割った値を、空白区切りで昇順に出力せよ。
入力例 1
5 2 2 5 6 7 10
出力例 1
1 3 5
A に含まれる要素のうち、2 の倍数は 2,6,10 です。それらを 2 で割って得られる 1,3,5 を空白区切りで昇順に出力してください。
入力例 2
3 1 3 4 7
出力例 2
3 4 7
入力例 3
5 10 50 51 54 60 65
出力例 3
5 6
Score: 100 points
Problem Statement
You are given positive integers N and K, and a sequence of length N, A=(A_1,A_2,\ldots,A_N).
Extract all elements of A that are multiples of K, divide them by K, and print the quotients.
Constraints
- 1\leq N,K\leq 100
- 1\leq A_1 < A_2 < \ldots < A_N \leq 100
- A has at least one multiple of K.
- All given numbers are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Divide all elements of A that are multiples of K and print the quotients in ascending order with spaces in between.
Sample Input 1
5 2 2 5 6 7 10
Sample Output 1
1 3 5
The multiples of 2 among the elements in A are 2, 6, and 10. Divide them by 2 to get 1, 3, and 5, and print them in ascending order with spaces in between.
Sample Input 2
3 1 3 4 7
Sample Output 2
3 4 7
Sample Input 3
5 10 50 51 54 60 65
Sample Output 3
5 6
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英小文字からなる文字列 S が与えられます。
S に a が現れるならば最後に現れるのが何文字目かを出力し、現れないならば -1 を出力してください。
制約
- S は英小文字からなる長さ 1 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
abcdaxayz
出力例 1
7
S に a は 3 回現れますが、最後に現れるのは 7 文字目なので、7 を出力します。
入力例 2
bcbbbz
出力例 2
-1
S に a は現れないので、-1 を出力します。
入力例 3
aaaaa
出力例 3
5
Score : 100 points
Problem Statement
You are given a string S consisting of lowercase English letters.
If a appears in S, print the last index at which it appears; otherwise, print -1. (The index starts at 1.)
Constraints
- S is a string of length between 1 and 100 (inclusive) consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
abcdaxayz
Sample Output 1
7
a appears three times in S. The last occurrence is at index 7, so you should print 7.
Sample Input 2
bcbbbz
Sample Output 2
-1
a does not appear in S, so you should print -1.
Sample Input 3
aaaaa
Sample Output 3
5
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 150 点
問題文
2 以上の整数 X が与えられます。
N!=X を満たすような正の整数 N を求めてください。
ただし、N! は N の階乗を表し、そのような N がただ一つ存在することは保証されています。
制約
- 2 \leq X \leq 3 \times 10^{18}
- N!=X を満たすような正の整数 N がただ一つ存在する
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
X
出力
答えを出力せよ。
入力例 1
6
出力例 1
3
3!=3\times2\times1=6 より、3 を出力します。
入力例 2
2432902008176640000
出力例 2
20
20!=2432902008176640000 より、20 を出力します。
Score : 150 points
Problem Statement
You are given an integer X not less than 2.
Find the positive integer N such that N! = X.
Here, N! denotes the factorial of N, and it is guaranteed that there is exactly one such N.
Constraints
- 2 \leq X \leq 3 \times 10^{18}
- There is exactly one positive integer N such that N!=X.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
X
Output
Print the answer.
Sample Input 1
6
Sample Output 1
3
From 3!=3\times2\times1=6, print 3.
Sample Input 2
2432902008176640000
Sample Output 2
20
From 20!=2432902008176640000, print 20.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
H 行 W 列からなるグリッドがあります。各マスには整数が 1 つずつ書かれており、これらの整数は相異なります。グリッドの上から i 行目・左から j 行目のマスには整数 A_{i,j} が書かれています。
いま、司会が N 個の相異なる整数 B_1, \dots, B_N を叫びました。
それぞれの行に対して、司会の叫んだ整数がその行に何個含まれるかを求めたとき、それらの最大値はいくつになりますか？
制約
- 1 \leq H \leq 3
- 1 \leq W \leq 5
- 1 \leq N \leq 90
- 1 \leq A_{i,j} \leq 90
- A_{i,j} は相異なる
- 1 \leq B_i \leq 90
- B_i は相異なる
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W N
A_{1,1} \cdots A_{1,W}
\vdots
A_{H,1} \cdots A_{H,W}
B_1
\vdots
B_N
出力
答えを 1 行に出力せよ。
入力例 1
3 4 5 12 3 5 7 6 10 11 9 1 2 4 8 2 4 9 6 11
出力例 1
3
- 上から 1 行目にある整数のうち、司会の叫んだ整数は 0 個です。
- 上から 2 行目にある整数のうち、司会の叫んだ整数は 6,11,9 の 3 個です。
- 上から 3 行目にある整数のうち、司会の叫んだ整数は 2,4 の 2 個です。
以上より、0,3,2 のうちの最大値である 3 が答えです。
入力例 2
3 5 2 81 63 31 16 15 30 3 6 54 24 26 41 48 64 66 44 79
出力例 2
0
入力例 3
3 5 12 78 19 70 58 83 12 30 80 20 27 48 71 8 43 82 82 30 43 8 80 70 20 78 12 71 19 48
出力例 3
5
Score : 200 points
Problem Statement
There is a grid with H rows and W columns. Each square has one integer written on it, and these integers are distinct. The square at the i-th row from the top and j-th column from the left has the integer A_{i,j} written on it.
Now, the host called out N distinct integers B_1, \dots, B_N.
If you find, for each row, how many of the integers called out by the host are contained in that row, what is the maximum value among these?
Constraints
- 1 \leq H \leq 3
- 1 \leq W \leq 5
- 1 \leq N \leq 90
- 1 \leq A_{i,j} \leq 90
- A_{i,j} are distinct.
- 1 \leq B_i \leq 90
- B_i are distinct.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H W N
A_{1,1} \cdots A_{1,W}
\vdots
A_{H,1} \cdots A_{H,W}
B_1
\vdots
B_N
Output
Output the answer in one line.
Sample Input 1
3 4 5 12 3 5 7 6 10 11 9 1 2 4 8 2 4 9 6 11
Sample Output 1
3
- Among the integers in the 1-st row from the top, 0 integers were called out by the host.
- Among the integers in the 2-nd row from the top, 3 integers 6,11,9 were called out by the host.
- Among the integers in the 3-rd row from the top, 2 integers 2,4 were called out by the host.
Thus, the answer is the maximum value among 0,3,2, which is 3.
Sample Input 2
3 5 2 81 63 31 16 15 30 3 6 54 24 26 41 48 64 66 44 79
Sample Output 2
0
Sample Input 3
3 5 12 78 19 70 58 83 12 30 80 20 27 48 71 8 43 82 82 30 43 8 80 70 20 78 12 71 19 48
Sample Output 3
5
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
空の箱があります。
髙橋君は以下の 2 種類の魔法を好きな順番で好きな回数使えます。
- 魔法 A ：箱の中にボールを 1 つ増やす
- 魔法 B ：箱の中のボールの数を 2 倍にする
合計 \mathbf{120} 回以内の魔法で、箱の中のボールの数をちょうど N 個にする方法を 1 つ教えてください。
なお、与えられた制約のもとで条件を満たす方法が必ず存在することが示せます。
魔法以外の方法でボールの数を変化させることはできません。
制約
- 1 \leq N \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
A , B のみからなる文字列 S を出力せよ。
S の i 文字目が A ならば、髙橋君が i 回目に使う魔法が魔法 A であることを表し、B ならば魔法 B であることを表す。
S の長さは \mathbf{120} 以下でなければならない。
入力例 1
5
出力例 1
AABA
ボールの数は、0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5 と変化します。
AAAAA などの答えも正解になります。
入力例 2
14
出力例 2
BBABBAAAB
ボールの数は、0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14 と変化します。
S の長さを最小化する必要はありません。
Score : 300 points
Problem Statement
We have an empty box.
Takahashi can cast the following two spells any number of times in any order.
- Spell A: puts one new ball into the box.
- Spell B: doubles the number of balls in the box.
Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.
There is no way other than spells to alter the number of balls in the box.
Constraints
- 1 \leq N \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Output
Print a string S consisting of A and B.
The i-th character of S should represent the spell for the i-th cast.
S must have at most \mathbf{120} characters.
Sample Input 1
5
Sample Output 1
AABA
This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.
Sample Input 2
14
Sample Output 2
BBABBAAAB
This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.