E - 321-like Searcher

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

以下の条件を満たす正整数 x を 321-like Number と呼びます。 この定義は A 問題と同様です。

  • x の各桁を上から見ると狭義単調減少になっている。
  • すなわち、x が d 桁の整数だとすると、 1 \le i < d を満たす全ての整数 i について以下の条件を満たす。
    • ( x の上から i 桁目 ) > ( x の上から i+1 桁目 )

なお、 1 桁の正整数は必ず 321-like Number であることに注意してください。

例えば、 321,96410,1 は 321-like Number ですが、 123,2109,86411 は 321-like Number ではありません。

K 番目に小さい 321-like Number を求めてください。

制約

  • 入力は全て整数
  • 1 \le K
  • 321-like Number は K 個以上存在する

入力

入力は以下の形式で標準入力から与えられる。

K

出力

K 番目に小さい 321-like Number を整数として出力せよ。


入力例 1

15

出力例 1

32

321-like Number は小さいものから順に (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) です。
このうち 15 番目に小さいものは 32 です。


入力例 2

321

出力例 2

9610

入力例 3

777

出力例 3

983210

Score : 300 points

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

  • The digits of x are strictly decreasing from top to bottom.
  • In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
    • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

  • All input values are integers.
  • 1 \le K
  • At least K 321-like Numbers exist.

Input

The input is given from Standard Input in the following format:

K

Output

Print the K-th smallest 321-like Number as an integer.


Sample Input 1

15

Sample Output 1

32

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.


Sample Input 2

321

Sample Output 2

9610

Sample Input 3

777

Sample Output 3

983210
F - Humidifier 3

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

AtCoder社のオフィスは H 行 W 列のマス目で表されます。上から i 行目、左から j 列目のマスを (i, j) と表します。

各マスの状態は文字 S_{i,j} で表され、 S_{i,j} が # のときそのマスは壁、. のときそのマスは床、H のときそのマスは加湿器が置かれた床です。

あるマスは、ある加湿器から壁を通らず上下左右に D 回以下の移動で辿り着ける場合加湿されます。ここで、加湿器が置かれた床のマスは必ず加湿されていることに注意してください。

加湿されている床のマスの個数を求めてください。

制約

  • 1 \leq H \leq 1000
  • 1 \leq W \leq 1000
  • 0 \leq D \leq H\times W
  • S_{i,j} は # または . または H である (1 \leq i \leq H, 1 \leq j \leq W)
  • 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}

出力

答えを出力せよ。


入力例 1

3 4 1
H...
#..H
.#.#

出力例 1

5

マス (1,1),(1,2),(1,4),(2,3),(2,4) の 5 つのマスが加湿されています。


入力例 2

5 6 2
##...H
H.....
..H.#.
.HH...
.###..

出力例 2

21

入力例 3

1 6 3
...#..

出力例 3

0

加湿されるマスが存在しない場合もあります。

Score : 350 points

Problem Statement

The AtCoder company office is represented as a grid of H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

The state of each cell is represented by a character S_{i,j}. If S_{i,j} is #, that cell has a wall; if S_{i,j} is ., that cell is a floor; if S_{i,j} is H, that cell has a humidifier placed on a floor cell.

A certain cell is considered humidified if it can be reached from at least one humidifier cell by at most D moves up, down, left, or right without passing through a wall. Note that any cell with a humidifier is always humidified.

Find the number of humidified floor cells.

Constraints

  • 1 \leq H \leq 1000
  • 1 \leq W \leq 1000
  • 0 \leq D \leq H\times W
  • S_{i,j} is #, ., or H. (1 \leq i \leq H, 1 \leq j \leq W)
  • All input numbers are integers.

Input

The input is given from Standard Input in the following format:

H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}

Output

Print the answer.


Sample Input 1

3 4 1
H...
#..H
.#.#

Sample Output 1

5

Five cells (1,1), (1,2), (1,4), (2,3), (2,4) are humidified.


Sample Input 2

5 6 2
##...H
H.....
..H.#.
.HH...
.###..

Sample Output 2

21

Sample Input 3

1 6 3
...#..

Sample Output 3

0

It is possible that no cells are humidified.

G - Range Add Query

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

長さ N の整数列 A = (A_1, A_2, \ldots, A_N) と正整数 K が与えられます。

各 i = 1, 2, \ldots, Q について、A の連続部分列 (A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}) が良い数列かどうかを判定してください。

ここで、長さ n の数列 X = (X_1, X_2, \ldots, X_n) は、下記の操作を好きな回数( 0 回でも良い)だけ行うことによって、X のすべての要素を 0 にすることができるとき、かつ、そのときに限り良い数列です。

1 \leq i \leq n-K+1 を満たす整数 i および、整数 c (負の数でも良い)を選び、K 個の要素 X_{i}, X_{i+1}, \ldots, X_{i+K-1} のそれぞれに c を加算する。

なお、すべての i = 1, 2, \ldots, Q について、r_i - l_i + 1 \geq K が保証されます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq \min\lbrace 10, N \rbrace
  • -10^9 \leq A_i \leq 10^9
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq l_i, r_i \leq N
  • r_i-l_i+1 \geq K
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \ldots A_N
Q
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

出力

Q 行出力せよ。 i = 1, 2, \ldots, Q について、i 行目には数列 (A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}) が良い数列である場合は Yes を、 そうでない場合は No を出力せよ。


入力例 1

7 3
3 -1 1 -2 2 0 5
2
1 6
2 7

出力例 1

Yes
No

数列 X \coloneqq (A_1, A_2, A_3, A_4, A_5, A_6) = (3, -1, 1, -2, 2, 0) は良い数列です。 実際、下記の手順で操作を行うことで、すべての要素を 0 にすることができます。

  • まず、i = 2, c = 4 として操作を行う。その結果、X = (3, 3, 5, 2, 2, 0) となる。
  • 次に、i = 3, c = -2 として操作を行う。その結果、X = (3, 3, 3, 0, 0, 0) となる。
  • 最後に、i = 1, c = -3 として操作を行う。その結果、X = (0, 0, 0, 0, 0, 0) となる。

よって、1 行目には Yes を出力します。

一方、数列 (A_2, A_3, A_4, A_5, A_6, A_7) = (-1, 1, -2, 2, 0, 5) は、 どのような手順で操作を行ってもすべての要素を 0 にすることはできないため、良い数列ではありません。 よって、2 行目には No を出力します。


入力例 2

20 4
-19 -66 -99 16 18 33 32 28 26 11 12 0 -16 4 21 21 37 17 55 -19
5
13 16
4 11
3 12
13 18
4 10

出力例 2

No
Yes
No
Yes
No

Score : 400 points

Problem Statement

You are given an integer sequence of length N, A = (A_1, A_2, \ldots, A_N), and a positive integer K.

For each i = 1, 2, \ldots, Q, determine whether a contiguous subsequence of A, (A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}), is a good sequence.

Here, a sequence of length n, X = (X_1, X_2, \ldots, X_n), is good if and only if there is a way to perform the operation below some number of times (possibly zero) to make all elements of X equal 0.

Choose an integer i such that 1 \leq i \leq n-K+1 and an integer c (possibly negative). Add c to each of the K elements X_{i}, X_{i+1}, \ldots, X_{i+K-1}.

It is guaranteed that r_i - l_i + 1 \geq K for every i = 1, 2, \ldots, Q.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq \min\lbrace 10, N \rbrace
  • -10^9 \leq A_i \leq 10^9
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq l_i, r_i \leq N
  • r_i-l_i+1 \geq K
  • 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 \ldots A_N
Q
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

Output

Print Q lines. For each i = 1, 2, \ldots, Q, the i-th line should contain Yes if the sequence (A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}) is good, and No otherwise.


Sample Input 1

7 3
3 -1 1 -2 2 0 5
2
1 6
2 7

Sample Output 1

Yes
No

The sequence X \coloneqq (A_1, A_2, A_3, A_4, A_5, A_6) = (3, -1, 1, -2, 2, 0) is good. Indeed, you can do the following to make all elements equal 0.

  • First, do the operation with i = 2, c = 4, making X = (3, 3, 5, 2, 2, 0).
  • Next, do the operation with i = 3, c = -2, making X = (3, 3, 3, 0, 0, 0).
  • Finally, do the operation with i = 1, c = -3, making X = (0, 0, 0, 0, 0, 0).

Thus, the first line should contain Yes.

On the other hand, for the sequence (A_2, A_3, A_4, A_5, A_6, A_7) = (-1, 1, -2, 2, 0, 5), there is no way to make all elements equal 0, so it is not a good sequence. Thus, the second line should contain No.


Sample Input 2

20 4
-19 -66 -99 16 18 33 32 28 26 11 12 0 -16 4 21 21 37 17 55 -19
5
13 16
4 11
3 12
13 18
4 10

Sample Output 2

No
Yes
No
Yes
No
H - Bishop 2

Time Limit: 6 sec / Memory Limit: 1024 MiB

配点 : 500 点

コンテスト開催当時はメモリ制限が2GBでしたが、ジャッジ環境が異なるため、現在はメモリ制限を1GBに設定しております。なお、このメモリ制限でもAC出来ることは確認しています。

問題文

ここに、 N \times N のチェス盤があります。このチェス盤の上から i 行目、左から j 列目にあるマスをマス (i,j) と呼びます。
チェス盤の情報は N 個の文字列 S_i として与えられます。
文字列 S_i の j 文字目である S_{i,j} には、以下の情報が含まれています。

  • S_{i,j}= . のとき マス (i,j) には何も置かれていない。
  • S_{i,j}= # のとき マス (i,j) には白のポーンが 1 つ置かれている。このポーンを動かしたり取り除いたりすることはできない。

この盤面のマス (A_x,A_y) に、白のビショップを 1 つ置きました。
この白のビショップをチェスのルール (注記参照) に従ってマス (A_x,A_y) からマス (B_x,B_y) に移動させるために必要な最小の手数を求めてください。
ただし、移動できない場合は代わりに -1 を出力してください。

注記

マス (i,j) に置かれている白の ビショップ は、 1 手で以下のルールに従って移動することができます。

  • 各正整数 d について、以下の条件を全て満たせばマス (i+d,j+d) に移動できる。

    • マス (i+d,j+d) が盤内に存在する
    • 全ての正整数 l \le d について、 (i+l,j+l) に白のポーンがない
  • 各正整数 d について、以下の条件を全て満たせばマス (i+d,j-d) に移動できる。

    • マス (i+d,j-d) が盤内に存在する
    • 全ての正整数 l \le d について、 (i+l,j-l) に白のポーンがない
  • 各正整数 d について、以下の条件を全て満たせばマス (i-d,j+d) に移動できる。

    • マス (i-d,j+d) が盤内に存在する
    • 全ての正整数 l \le d について、 (i-l,j+l) に白のポーンがない
  • 各正整数 d について、以下の条件を全て満たせばマス (i-d,j-d) に移動できる。

    • マス (i-d,j-d) が盤内に存在する
    • 全ての正整数 l \le d について、 (i-l,j-l) に白のポーンがない

制約

  • 2 \le N \le 1500
  • 1 \le A_x,A_y \le N
  • 1 \le B_x,B_y \le N
  • (A_x,A_y) \neq (B_x,B_y)
  • S_i は . および # からなる N 文字の文字列
  • S_{A_x,A_y}= .
  • S_{B_x,B_y}= .

入力

入力は以下の形式で標準入力から与えられる。

N
A_x A_y
B_x B_y
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。


入力例 1

5
1 3
3 5
....#
...#.
.....
.#...
#....

出力例 1

3

以下のように移動させることで 3 手でビショップを (1,3) から (3,5) まで移動させることができます。 2 手以内でビショップを (1,3) から (3,5) まで移動させることはできません。

  • (1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)

入力例 2

4
3 2
4 2
....
....
....
....

出力例 2

-1

どのようにビショップを動かしても (3,2) から (4,2) に移動させることはできません。


入力例 3

18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

出力例 3

9

Score : 500 points

During the time of the contest, the memory limit was set to 2GB. However, due to a change in the judging environment, the memory limit has now been set to 1GB. Please note that it has been confirmed that solutions can still achieve an Acceptable Completion (AC) within this memory limit.

Problem Statement

We have an N \times N chessboard. Let (i, j) denote the square at the i-th row from the top and j-th column from the left of this board.
The board is described by N strings S_i.
The j-th character of the string S_i, S_{i,j}, means the following.

  • If S_{i,j}= ., the square (i, j) is empty.
  • If S_{i,j}= #, the square (i, j) is occupied by a white pawn, which cannot be moved or removed.

We have put a white bishop on the square (A_x, A_y).
Find the minimum number of moves needed to move this bishop from (A_x, A_y) to (B_x, B_y) according to the rules of chess (see Notes).
If it cannot be moved to (B_x, B_y), report -1 instead.

Notes

A white bishop on the square (i, j) can go to the following positions in one move.

  • For each positive integer d, it can go to (i+d,j+d) if all of the conditions are satisfied.

    • The square (i+d,j+d) exists in the board.
    • For every positive integer l \le d, (i+l,j+l) is not occupied by a white pawn.
  • For each positive integer d, it can go to (i+d,j-d) if all of the conditions are satisfied.

    • The square (i+d,j-d) exists in the board.
    • For every positive integer l \le d, (i+l,j-l) is not occupied by a white pawn.
  • For each positive integer d, it can go to (i-d,j+d) if all of the conditions are satisfied.

    • The square (i-d,j+d) exists in the board.
    • For every positive integer l \le d, (i-l,j+l) is not occupied by a white pawn.
  • For each positive integer d, it can go to (i-d,j-d) if all of the conditions are satisfied.

    • The square (i-d,j-d) exists in the board.
    • For every positive integer l \le d, (i-l,j-l) is not occupied by a white pawn.

Constraints

  • 2 \le N \le 1500
  • 1 \le A_x,A_y \le N
  • 1 \le B_x,B_y \le N
  • (A_x,A_y) \neq (B_x,B_y)
  • S_i is a string of length N consisting of . and #.
  • S_{A_x,A_y}= .
  • S_{B_x,B_y}= .

Input

Input is given from Standard Input in the following format:

N
A_x A_y
B_x B_y
S_1
S_2
\vdots
S_N

Output

Print the answer.


Sample Input 1

5
1 3
3 5
....#
...#.
.....
.#...
#....

Sample Output 1

3

We can move the bishop from (1,3) to (3,5) in three moves as follows, but not in two or fewer moves.

  • (1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)

Sample Input 2

4
3 2
4 2
....
....
....
....

Sample Output 2

-1

There is no way to move the bishop from (3,2) to (4,2).


Sample Input 3

18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

Sample Output 3

9
I - x = a^b

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

1 以上 N 以下の正整数 x であって、ある正整数 a と 2 以上の 正整数 b を用いて x=a^b と表現できるものはいくつありますか?

制約

  • 入力は全て整数
  • 1 \le N \le 10^{18}

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを整数として出力せよ。


入力例 1

99

出力例 1

12

問題文中の条件を満たす整数は 1,4,8,9,16,25,27,32,36,49,64,81 の 12 個です。


入力例 2

1000000000000000000

出力例 2

1001003332

Score : 500 points

Problem Statement

How many integers x between 1 and N, inclusive, can be expressed as x = a^b using some positive integer a and a positive integer b not less than 2?

Constraints

  • All input values are integers.
  • 1 \le N \le 10^{18}

Input

The input is given from Standard Input in the following format:

N

Output

Print the answer as an integer.


Sample Input 1

99

Sample Output 1

12

The integers that satisfy the conditions in the problem statement are 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81: there are 12.


Sample Input 2

1000000000000000000

Sample Output 2

1001003332