Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
次の長さ 32 の数列の K 番目の項を出力してください。
1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
制約
- 1 \leq K \leq 32
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
K
出力
K 番目の項を出力せよ。
入力例 1
6
出力例 1
2
6 番目の項は 2 です。
入力例 2
27
出力例 2
5
27 番目の項は 5 です。
Score : 100 points
Problem Statement
Print the K-th element of the following sequence of length 32:
1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
Constraints
- 1 \leq K \leq 32
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
K
Output
Print the K-th element.
Sample Input 1
6
Sample Output 1
2
The 6-th element is 2.
Sample Input 2
27
Sample Output 2
5
The 27-th element is 5.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
縦 H マス、横 W マスの盤面があります。 この盤面の左上隅のマスに角行の駒が置かれています。 駒が 0 回以上の好きな回数の移動を繰り返して到達できるマス目は何個あるでしょうか?
ただし、角行の駒は斜めに動くものとします。 より厳密には、駒が上から r_1 番目、左から c_1 番目のマスから上から r_2 番目、左から c_2 番目のマス目に動ける条件は
- r_1 + c_1 = r_2 + c_2
- r_1 - c_1 = r_2 - c_2
のうちちょうど一方が成立することです。たとえば、駒が図の位置にあるとき、一回で移動できる場所は赤くなっているマスです。
制約
- 1 \leq H, W \leq 10^9
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
H \ W
出力
駒が到達できるマス目の個数を出力せよ。
入力例 1
4 5
出力例 1
10
下図の水色のマスに到達可能です。
入力例 2
7 3
出力例 2
11
下図の水色のマスに到達可能です。
入力例 3
1000000000 1000000000
出力例 3
500000000000000000
Score : 200 points
Problem Statement
We have a board with H horizontal rows and W vertical columns of squares. There is a bishop at the top-left square on this board. How many squares can this bishop reach by zero or more movements?
Here the bishop can only move diagonally. More formally, the bishop can move from the square at the r_1-th row (from the top) and the c_1-th column (from the left) to the square at the r_2-th row and the c_2-th column if and only if exactly one of the following holds:
- r_1 + c_1 = r_2 + c_2
- r_1 - c_1 = r_2 - c_2
For example, in the following figure, the bishop can move to any of the red squares in one move:
Constraints
- 1 \leq H, W \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H \ W
Output
Print the number of squares the bishop can reach.
Sample Input 1
4 5
Sample Output 1
10
The bishop can reach the cyan squares in the following figure:
Sample Input 2
7 3
Sample Output 2
11
The bishop can reach the cyan squares in the following figure:
Sample Input 3
1000000000 1000000000
Sample Output 3
500000000000000000
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
\sqrt{a} + \sqrt{b} < \sqrt{c} ですか?
制約
- 1 \leq a, b, c \leq 10^9
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
a \ b \ c
出力
\sqrt{a} + \sqrt{b} < \sqrt{c} ならば Yes
、そうでないならば No
と出力せよ。
入力例 1
2 3 9
出力例 1
No
\sqrt{2} + \sqrt{3} < \sqrt{9} ではありません。
入力例 2
2 3 10
出力例 2
Yes
\sqrt{2} + \sqrt{3} < \sqrt{10} です。
Score : 300 points
Problem Statement
Does \sqrt{a} + \sqrt{b} < \sqrt{c} hold?
Constraints
- 1 \leq a, b, c \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
a \ b \ c
Output
If \sqrt{a} + \sqrt{b} < \sqrt{c}, print Yes
; otherwise, print No
.
Sample Input 1
2 3 9
Sample Output 1
No
\sqrt{2} + \sqrt{3} < \sqrt{9} does not hold.
Sample Input 2
2 3 10
Sample Output 2
Yes
\sqrt{2} + \sqrt{3} < \sqrt{10} holds.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
この問題では、英小文字からなる文字列のみを考えます。
文字列 s, t は以下の条件を満たすとき 同型 であるといいます。
- |s| = |t| である。
- 任意の i, j に対し次のいずれかが成立する。
- s_i = s_j かつ t_i = t_j
- s_i \neq s_j かつ t_i \neq t_j
たとえば、abcac
と zyxzx
は同型ですが、abcac
と ppppp
は同型ではありません。
文字列 s は以下の条件を満たすとき 標準形 であるといいます。
- 任意の s と同型な文字列 t に対し、s \leq t が成立する。ただしここで \leq は辞書順での比較を表す。
たとえば、abcac
は標準形ですが、zyxzx
はそれより辞書順で小さい abcac
と同型のため標準形ではありません。
整数 N が与えられます。 長さ N の標準形の文字列を全て、辞書順で昇順で出力してください。
制約
- 1 \leq N \leq 10
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
長さ N の標準形の文字列が K 個あり、辞書順で w_1, \ldots, w_K であるとする。 このとき以下の形式で出力せよ。
w_1 : w_K
入力例 1
1
出力例 1
a
入力例 2
2
出力例 2
aa ab
Score : 400 points
Problem Statement
In this problem, we only consider strings consisting of lowercase English letters.
Strings s and t are said to be isomorphic when the following conditions are satisfied:
- |s| = |t| holds.
- For every pair i, j, one of the following holds:
- s_i = s_j and t_i = t_j.
- s_i \neq s_j and t_i \neq t_j.
For example, abcac
and zyxzx
are isomorphic, while abcac
and ppppp
are not.
A string s is said to be in normal form when the following condition is satisfied:
- For every string t that is isomorphic to s, s \leq t holds. Here \leq denotes lexicographic comparison.
For example, abcac
is in normal form, but zyxzx
is not since it is isomorphic to abcac
, which is lexicographically smaller than zyxzx
.
You are given an integer N. Print all strings of length N that are in normal form, in lexicographically ascending order.
Constraints
- 1 \leq N \leq 10
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Output
Assume that there are K strings of length N that are in normal form: w_1, \ldots, w_K in lexicographical order. Output should be in the following format:
w_1 : w_K
Sample Input 1
1
Sample Output 1
a
Sample Input 2
2
Sample Output 2
aa ab
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
すぬけ君は、文字列 s を持っています。 あぬけ君、ぶぬけ君、くぬけ君は次のような方法でそれぞれ文字列 a, b, c を得ました。
- s の空でない (s 全体であってもよい) 連続な部分文字列を一つ選ぶ。その部分文字列のうちいくつかの文字 (0 個や全部であってもよい) を
?
で置き換える。
たとえば、s が mississippi
であるとき、部分文字列として ssissip
を選び、その 1, 3 文字目を ?
で置き換えることで ?s?ssip
を得ることができます。
文字列 a, b, c が与えられます。 s の長さとして考えられる最小値を求めてください。
制約
- 1 \leq |a|, |b|, |c| \leq 2000
- a, b, c は英小文字と
?
からなる。
入力
入力は以下の形式で標準入力から与えられる。
a b c
出力
s の長さとして考えられる最小値を出力せよ。
入力例 1
a?c der cod
出力例 1
7
たとえば、s が atcoder
のとき条件を満たします。
入力例 2
atcoder atcoder ???????
出力例 2
7
a, b, c は相異なるとは限りません。
Score : 500 points
Problem Statement
Snuke has a string s. From this string, Anuke, Bnuke, and Cnuke obtained strings a, b, and c, respectively, as follows:
- Choose a non-empty (contiguous) substring of s (possibly s itself). Then, replace some characters (possibly all or none) in it with
?
s.
For example, if s is mississippi
, we can choose the substring ssissip
and replace its 1-st and 3-rd characters with ?
to obtain ?s?ssip
.
You are given the strings a, b, and c. Find the minimum possible length of s.
Constraints
- 1 \leq |a|, |b|, |c| \leq 2000
- a, b, and c consists of lowercase English letters and
?
s.
Input
Input is given from Standard Input in the following format:
a b c
Output
Print the minimum possible length of s.
Sample Input 1
a?c der cod
Sample Output 1
7
For example, s could be atcoder
.
Sample Input 2
atcoder atcoder ???????
Sample Output 2
7
a, b, and c may not be distinct.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
非負整数 K に対し、以下のようにレベル K のフラクタルを定義します。
- レベル 0 のフラクタルとは、白いマス一個のみからなるグリッドである。
- K > 0 のとき、レベル K のフラクタルは 3^K \times 3^K のグリッドである。このグリッドを 3^{K-1} \times 3^{K-1} のブロック 9 個に分割したとき、
- 中央のブロックは全て黒マスからなる。
- 他の 8 個のブロックは、レベル K-1 のフラクタルになっている。
たとえば、レベル 2 のフラクタルは下図の通りです。
レベル 30 のフラクタルにおいて、上から r 番目、左から c 番目のマスを (r, c) と書きます。
Q 個の整数組 (a_i, b_i, c_i, d_i) が与えられます。 それぞれの組について、(a_i, b_i) から (c_i, d_i) への距離を求めてください。
ただし、(a, b) から (c, d) への距離とは、以下の条件を満たすような最小の n とします。
- ある白マスの列 (x_0, y_0), \ldots, (x_n, y_n) が存在して、以下の条件を満たす。
- (x_0, y_0) = (a, b)
- (x_n, y_n) = (c, d)
- 任意の i (0 \leq i \leq n-1) に対し、マス (x_i, y_i) と (x_{i+1}, y_{i+1}) は辺で接する。
制約
- 1 \leq Q \leq 10000
- 1 \leq a_i, b_i, c_i, d_i \leq 3^{30}
- (a_i, b_i) \neq (c_i, d_i)
- (a_i, b_i), (c_i, d_i) は白マスである。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
Q a_1 \ b_1 \ c_1 \ d_1 : a_Q \ b_Q \ c_Q \ d_Q
出力
Q 行出力せよ。 i 行目には、(a_i, b_i) から (c_i, d_i) への距離を出力せよ。
入力例 1
2 4 2 7 4 9 9 1 9
出力例 1
5 8
Score : 600 points
Problem Statement
For a non-negative integer K, we define a fractal of level K as follows:
- A fractal of level 0 is a grid with just one white square.
- When K > 0, a fractal of level K is a 3^K \times 3^K grid. If we divide this grid into nine 3^{K-1} \times 3^{K-1} subgrids:
- The central subgrid consists of only black squares.
- Each of the other eight subgrids is a fractal of level K-1.
For example, a fractal of level 2 is as follows:
In a fractal of level 30, let (r, c) denote the square at the r-th row from the top and the c-th column from the left.
You are given Q quadruples of integers (a_i, b_i, c_i, d_i). For each quadruple, find the distance from (a_i, b_i) to (c_i, d_i).
Here the distance from (a, b) to (c, d) is the minimum integer n that satisfies the following condition:
- There exists a sequence of white squares (x_0, y_0), \ldots, (x_n, y_n) satisfying the following conditions:
- (x_0, y_0) = (a, b)
- (x_n, y_n) = (c, d)
- For every i (0 \leq i \leq n-1), (x_i, y_i) and (x_{i+1}, y_{i+1}) share a side.
Constraints
- 1 \leq Q \leq 10000
- 1 \leq a_i, b_i, c_i, d_i \leq 3^{30}
- (a_i, b_i) \neq (c_i, d_i)
- (a_i, b_i) and (c_i, d_i) are white squares.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Q a_1 \ b_1 \ c_1 \ d_1 : a_Q \ b_Q \ c_Q \ d_Q
Output
Print Q lines. The i-th line should contain the distance from (a_i, b_i) to (c_i, d_i).
Sample Input 1
2 4 2 7 4 9 9 1 9
Sample Output 1
5 8