A - Calendar

Time Limit: 1 sec / Memory Limit: 256 MB

Max Score: $250$ Points

Problem Statement

Snuke has a very long calendar. It has a grid with $n$ rows and $7$ columns. One day, he noticed that calendar has a following regularity.
  • The cell at the $i$-th row and $j$-th column contains the integer $7i+j-7$.
A good sub-grid is a $3 \times 3$ sub-grid and the sum of integers in this sub-grid mod $11$ is $k$.
How many good sub-grid are there? Write a program and help him.

Input

The input is given from standard input in the following format.

$n \quad k$

Output

  • Print the number of good sub-grid. If there are no solution exists, print 0.

Constraints

  • $1 \le n \le 10^9$
  • $0 \le k \le 10$

Subtasks

Subtask 1 [ $150$ points ]

  • The testcase in the subtask satisfies $1 \le n \le 100$.

Subtask 2 [ $100$ points ]

  • There are no additional constraints.

Sample Input 1

7 7

Sample Output 1

2
In this case, the calendar likes this matrix.
Sun. Mon. Tue. Wed. Thu. Fri. Sat.
Week 1 1 2 3 4 5 6 7
Week 2 8 9 10 11 12 13 14
Week 3 15 16 17 18 19 20 21
Week 4 22 23 24 25 26 27 28
Week 5 29 30 31 32 33 34 35
Week 6 36 37 38 39 40 41 42
Week 7 43 44 45 46 47 48 49

The cell at $i$-th row and $j$-th column is denoted $(i, j)$.
  • If upper-left is $(1, 5)$, the sum of integers is $5+6+7+12+13+14+19+20+21=117$.
  • If upper-left is $(3, 2)$, the sum of integers is $16+17+18+23+24+25+30+31+32=216$.
Therefore, there are 2 good sub-grids.

Sample Input 2

6 0

Sample Output 2

2
If upper-left is $(1, 3)$ or $(4, 4)$, it is a good sub-grid.

Sample Input 3

18 10

Sample Output 3

7

Sample Input 4

100 8

Sample Output 4

45

Writer：square1001
配点： $250$ 点

問題文

E869120は, 縦に長いカレンダーらしいものを持っていた。
ある日, E869120はそのカレンダーに以下の規則性があることを発見した。
  • 上から $i$ 番目, 左から $j$ 番目に書かれている整数は $7i+j-7$ である。
また, E869120は $3 \times 3$ の正方形の枠を持っていた。
そこで、以下の条件を満たす正方形の置き方を数え上げしてみることにした。
  • 正方形の枠内に入っている $9$ 個の数字の和を $11$ で割った余りは $k$ である。
そのとき, 条件を満たす枠の置き方は何通りあるでしょうか?

入力

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

$n \quad k$
  • 1行目には、カレンダーの段数 $n$ と, 正方形を置く時の条件となる数 $k$ が空白区切りで与えられる。

出力

  • 条件を満たす $3 \times 3$ の正方形の置き方の通り数を1行に出力しなさい。
  • ただし, 1つも条件を満たすような置き方ができない場合, $0$ と出力しなさい。

制約

  • $1 \le n \le 10^9$
  • $0 \le k \le 10$

小課題

小課題1 [ $150$点 ]

  • $1 \le n \le 100$ を満たす。

小課題2 [ $100$ 点 ]

  • 追加の制約はない。

入力例1

7 7

出力例1

2
この場合、以下の表のようなカレンダーになっている。
1列目 2列目 3列目 4列目 5列目 6列目 7列目
1行目 1 2 3 4 5 67
2行目 8 9 10 11 12 13 14
3行目 15 16 17 18 19 20 21
4行目 22 23 24 25 26 27 28
5行目 29 30 31 32 33 34 35
6行目 36 37 38 39 40 41 42
7行目 43 44 45 46 47 48 49

ここでは, $(i, j)$ を上から $i$ 番目, 左から $j$ 番目のマスとする。
  • 左上が $(1, 5)$ のとき, $5+6+7+12+13+14+19+20+21=117$ となり, $11$ で割った余りは $7$ となる。
  • 左上が $(3, 2)$ のとき, $16+17+18+23+24+25+30+31+32=216$ となり, $11$ で割った余りは $7$ となる。
条件を満たすのはこの2つのみである。

入力例2

6 0

出力例2

2
左上が $(1, 3)$ または $(4, 4)$ のときのみ条件を満たす。

入力例3

18 10

出力例3

7
左上のマスが $(2,2), (5,3), (8,4), (10,1), (11,5), (13,2), (16,3)$ のとき, 条件を満たす。

入力例4

100 8

出力例4

45
この入力例は小課題1を満たす。

問題文担当者：square1001
B - Falling Stone Game

Time Limit: 1 sec / Memory Limit: 256 MB

Max Score: $300$ Points

Problem Statement

We are playing a puzzle. An upright board with $H$ rows by $W$ columns of cells, is used in this puzzle.
A stone in $i$-th row and $j$-th column engraved with a digit, one of 1 through 9, is placed in each of the cells.
You can erase 1 cell in the board.

The game process is following:
  1. When $K$ or more stones in horizontally adjacent cells are engraved with the same digit, the stones will disappear. Disappearances of all such groups of stones take place simultaneously.
  2. When stones are in the cells above the emptied cells, these stones drop down so that the emptied cells are filled.
  3. After the completion of all stone drops, if one or more groups of stones satisfy the disappearance condition, repeat by returning to the step 1.
  4. Score is $\sum_i 2^i \times \left(\text{Sum of numbers in the stones which disappeared in the $i$-th chain (0-indexed)}\right)$.
Please answer the points if he erased the optimal place.

Input

The input is given from standard input in the following format.
$H \ W \ K$ $c_{1, 1} \ c_{1, 2} \ \cdots \ c_{1, W}$ $c_{2, 1} \ c_{2, 2} \ \cdots \ c_{2, W}$ $\vdots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \vdots$ $c_{H, 1} \ c_{H, 2} \ \cdots \ c_{H, W}$

Output

  • Please output total points if he erase the optimal place.

Constraints

  • $2 \le H, W \le 30$
  • $2 \le K \le 3$
  • $answer \le 1,000,000,000$
  • $c_{i,j} ≠ c_{i,j+1} (1 \le j \le W-1)$

Subtasks

Subtask 1 [ $120$ points ]
  • $H, W \le 10$
  • $W=K$
Subtask 2 [ $180$ points ]
  • There are no additional constraints.

Sample Input 1

4 4 2
3413
4121
1424
2312

Sample Output 1

23
If you erase cell(4,3):

Total score: $7 + 16 = 23$points.
The optimal place to erase is cell(3,2).

Sample Input 2

4 4 2
1212
2121
1212
2121

Sample Output 2

54

Sample Input 3

7 7 2
8989898
9898989
8989898
9898989
8989898
9898989
8989898

Sample Output 3

2520

Sample Input 4

17 17 2
12345678912345678
23456789123456789
34567891234567891
45678912345678912
56789123456789123
67891234567891234
78912345678912345
89123456789123456
91234567891234567
12345678912345678
23456789123456789
34567891234567891
45678912345678912
56789123456789123
67891234567891234
78912345678912345
89123456789123456

Sample Output 4

2354638
writer: E869120
配点： $300$ 点

問題文

square1001氏は、パソコン部に入るために試験を受けました。
この試験の内容は、以下のようなものであります。
  • $H \times W$ の盤面が与えられる。
  • その盤面の各マスは、 $1 \sim 9$ の数字が書かれている。また、1行目が一番上である。
  • あなたは、セルのうち1つのマスを消すことができる。消した上のマスは落ちてくる。
また、そのゲームは以下のようなステップで進行する。
  • 1:$K$ 個以上の水平に隣り合うセルに同じ数字を彫った石があれば，これらの石は消滅する．こうした石群の消滅はすべて同時に起きる。
  • 2:石が消滅したセルの上方のセルに石があれば，空きを埋めるように石が落下する。
  • 3:すべての石の落下完了後に，消滅の条件を満たすようになった石群があれば，ステップ1に戻って繰り返す。
  • 4:スコアは, $2^i \times \left(i \text{回目の消滅で消えた数字の値の和}\right)$ の合計である。ただし、最初の消滅を0回目とする。
そのとき、square1001氏が最適にやって試験に受かるか調べるために、最適にセルを消したときに何点取れるかを計算することにした。
square1001氏を助けるために、最大の点数を出力しなさい。

入力

入力は以下の形式で標準入力から与えられる。
$H \ W \ K$ $c_{1, 1} \ c_{1, 2} \ \cdots \ c_{1, W}$ $c_{2, 1} \ c_{2, 2} \ \cdots \ c_{2, W}$ $\vdots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \vdots$ $c_{H, 1} \ c_{H, 2} \ \cdots \ c_{H, W}$
  • 1行目に, 盤面の縦、横の大きさ$H$, $W$と、何個横に並ぶと消滅するかを表す数 $K$ が与えられる。
  • 2行目から, $H$行にわたって盤面の状況が与えられる。
  • 1～9はそれぞれの数字があることを示す。

出力

出力は以下の形式で標準出力に従うこと。
  • 最大の点数を1行に出力しなさい。

制約

  • $2 \le H, W \le 30$
  • 点数は $1,000,000,000$ 点を超えない
  • 最初の盤面では, すべての横に隣り合うマス同士は同じ数が書かれていることはない。

小課題

小課題1 [ $120$ 点 ]
  • $H, W \le 10$
  • $W=K$
小課題2 [ $180$点 ]
  • 追加の制約はない。

入力例1

4 4 2
3413
4121
1424
2312

出力例1

23
場所 $(4, 3)$ を押すと以下のようになります。
よって, $7+16=23$ 点となる。
また, 場所 $(4,3)$ を消すのが最適である。

入力例2

4 4 2
1212
2121
1212
2121

出力例2

54
この入力例は小課題1の制約を満たさない。

入力例3

7 7 2
8989898
9898989
8989898
9898989
8989898
9898989
8989898

出力例3

2520
この入力例は小課題1の制約を満たさない。

入力例4

17 17 2
12345678912345678
23456789123456789
34567891234567891
45678912345678912
56789123456789123
67891234567891234
78912345678912345
89123456789123456
91234567891234567
12345678912345678
23456789123456789
34567891234567891
45678912345678912
56789123456789123
67891234567891234
78912345678912345
89123456789123456

出力例4

2354638
連鎖数が非常に大きくなることもある。
問題作成者:E869120
C - Solving XOR-Puzzles

Time Limit: 1 sec / Memory Limit: 256 MB

Max Score: $400$ Points

Problem Statement

Sample testcase 3 has a mistake, so we erased this case and rejudged all solutions of this problem. (21:01)

Snuke got a sequence $a$ of length $n$ from AtCoder company. All elements in $a$ are distinct.
He made a sequence $b$, but actually, he is not remembered it.
However, he is remembered a few things about sequence $b$.
  • All elements in $b$ are distinct.
  • All elements in $b$ is in $a$.
  • $b_1 \oplus b_2 \oplus \cdots \oplus b_r = k$. ($r$ is length of sequence $b$) [$\oplus$ means XOR]

For example, if $a = { 1, 2, 3 }$ and $k = 1$, he can make $b = { 1 }, { 2, 3 }, { 3, 2 }$.
He wants to restore sequence $b$, but he says that there are too many ways and he can't restore it. Please calculate the ways to make $b$ and help him.
Since the answer can be large, print the answer modulo $1,000,000,007$.

Input

The input is given from Standard Input in the following format:
$n \ k$ $a_1 \ a_2 \ \cdots \ a_n$

Output

  • Print the number of ways to make sequence $b$.
  • Print the answer modulo $1,000,000,007$.

Constraints

  • $1 \le n \le 100$
  • $1 \le a_i, k \le 255$
  • $i \neq j \Rightarrow a_i \neq a_j$

Subtasks

Subtask 1 [ $50$ points ]
  • $1 \le n \le 4$
Subtask 2 [ $170$ points ]
  • $1 \le n \le 20$
Subtask 3 [ $180$ points ]
  • There are no additional constraints.

Sample Input 1

3 1
1 2 3

Sample Output 1

3
You can make 3 patterns: $b = \{ 1 \}, \{ 2, 3 \}, \{ 3, 2 \}$

Sample Input 2

3 10
8 7 5

Sample Output 2

6
You can make 6 patterns: $b = \{ 5, 7, 8 \}, \{ 5, 8, 7 \}, \{ 7, 5, 8 \}, \{ 7, 8, 5 \}, \{ 8, 5, 7 \}, \{ 8, 7, 5 \}$.

Sample Input 4

25 127
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125

Sample Output 4

235924722

Please output answer mod $1,000,000,007$.

writer: E869120
配点： $400$ 点

問題文

サンプルケース3に不備があったので、リジャッジをしました。申し訳ございません。(21:01)

square1001は, Atcoder社から長さ $n$ の数列 $a$ をもらいました。$a$ の要素はすべて異なります。
彼は, 数列 $b$ を作りましたが, この数列を覚えていません。しかし, 次のことは覚えています。
  • $b$ の要素はすべて異なる。
  • $b$ の要素はすべて $a$ にも入っている。
  • square'1001' は, 2進数が好きなため, $b_1 \oplus b_2 \oplus \cdots \oplus b_r = k$ ($r$ は数列 $b$ の長さ) であることも覚えている。[$\oplus$ は XOR]
square1001は, 数列 $b$ として考えられるものが何通りあるのか考えることにしました。
しかし, 彼は全探索をしようとしていて, これに気付いたあなたは, 彼の代わりに求めてあげようとしました。
そのとき, square'1001'が作った数列 $b$ として考えられるものは, 何通りあるでしょうか?
ただし, 答えが非常に大きくなることがあるので, $1,000,000,007$で割った余りを求めてください。

入力

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

$n \ k$ $a_1 \ a_2 \ \cdots \ a_n$
  • 1 行目には、数列aの長さnと、数列bのXORした値kが空白区切りで与えられる。
  • 2 行目には、数列aの要素が空白区切りで与えられる。

出力

出力は以下の形式で標準出力に従うこと。

  • square'1001'が作った数列として考えられるものの通り数を1行に出力せよ。
  • ただし, $1,000,000,007$ で割った余りを出力すること。

制約

  • $1 \le n \le 100$
  • $1 \le a_i, k \le 255$
  • $i \neq j \Rightarrow a_i \neq a_j$

小課題

小課題1 [ $50$ 点 ]
  • $1 \le n \le 4$ を満たす。
小課題2 [ $170$ 点 ]
  • $1 \le n \le 20$ を満たす。
小課題3 [ $180$ 点 ]
  • $1 \le n \le 100$ を満たす。

入力例1

3 1
1 2 3

出力例1

3
数列 $b$ として考えられるのは, $b = \{ 1 \}, \{ 2, 3 \}, \{ 3, 2 \}$ の3つである。

入力例2

3 10
8 7 5

出力例2

6
数列 $b$ として考えられるのは, $b = \{ 5, 7, 8 \}, \{ 5, 8, 7 \}, \{ 7, 5, 8 \}, \{ 7, 8, 5 \}, \{ 8, 5, 7 \}, \{ 8, 7, 5 \}$ の6つである。

入力例4

25 127
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125

出力例4

235924722

$1,000,000,007$ で割った余りを求めること。

問題作成者:E869120
D - Souvenirs

Time Limit: 2 sec / Memory Limit: 256 MB

Max Score: $600$ Points

Problem Statement

Sigma and his brother Sugim are in the $H \times W$ grid. They wants to buy some souvenirs.
Their start position is upper-left cell, and the goal position is lower-right cell.
Some cells has a souvenir shop. At $i$-th row and $j$-th column, there is $a_{i, j}$ souvenirs.
In one move, they can go left, right, down, and up cell.
But they have little time, so they can move only $H+W-2$ times.
They wanted to buy souvenirs as many as possible, but they had no computer, so they couldn't get the maximal numbers of souvenirs.
Write a program and calculate the maximum souvenirs they can get, and help them.

Input

The input is given from standard input in the following format.
$H \ W$ $a_{1, 1} \ a_{1, 2} \ \cdots \ a_{1, W}$ $a_{2, 1} \ a_{2, 2} \ \cdots \ a_{2, W}$ $\vdots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \vdots$ $a_{H, 1} \ a_{H, 2} \ \cdots \ a_{H, W}$

Output

  • Print the maximum number of souvenirs they can get.

Constraints

  • $1 \le H, W \le 200$
  • $0 \le a_{i, j} \le 10^5$

Subtasks

Subtask 1 [ 50 points ]
  • The testcase in the subtask satisfies $1 \le H \le 2$.
Subtask 2 [ 80 points ]
  • The testcase in the subtask satisfies $1 \le H \le 3$.
Subtask 3 [ 120 points ]
  • The testcase in the subtask satisfies $1 \le H, W \le 7$.
Subtask 4 [ 150 points ]
  • The testcase in the subtask satisfies $1 \le H, W \le 30$.
Subtask 5 [ 200 points ]
  • There are no additional constraints.

Sample Input 1

3 3
1 0 5
2 2 3
4 2 4

Sample Output 1

21
The cell at $i$-th row and $j$-th column is denoted $(i, j)$.
In this case, one of the optimal solution is this:
  • Sigma moves $(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)$.
  • Sugim moves $(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)$.
Then, they can get $21$ souvernirs.

Sample Input 2

6 6
1 2 3 4 5 6
8 6 9 1 2 0
3 1 4 1 5 9
2 6 5 3 5 8
1 4 1 4 2 1
2 7 1 8 2 8

Sample Output 2

97
Writer : square1001
配点： $600$ 点

問題文

E869120とsquare1001は, $H \times W$ のマス目を移動して, お土産を買うことにしました。
左上のマスがスタート地点, 右下のマスがゴール地点です。
上から$i$番目, 左から$j$番目には, $a_{i, j}$ 個のお土産が売られています。
そこで, 2人で協力してお土産をできるだけ多く集めることにしました。
しかし, 2人は最短経路で行かなければなりません。そうしないとTLEします。
そのとき, 買うことができるお土産の個数の最大値を求めなさい。

入力

入力は以下の形式で標準入力から与えられる。
$H \ W$ $a_{1, 1} \ a_{1, 2} \ \cdots \ a_{1, W}$ $a_{2, 1} \ a_{2, 2} \ \cdots \ a_{2, W}$ $\vdots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \vdots$ $a_{H, 1} \ a_{H, 2} \ \cdots \ a_{H, W}$
  • $1$行目に, 整数$H$と$W$が与えられる。
  • $2$行目から$H+1$行目には, $W$個の整数が空白区切りで与えられる。

出力

出力は以下の形式で標準出力に従うこと。

  • 買うことのできるお土産の個数の最大値を1行に出力しなさい。

制約

  • $1 \le H, W \le 200$
  • $0 \le a_{i, j} \le 10^5$

小課題

小課題1 [50点]
  • $1 \le H \le 2$ を満たす。
小課題2 [80点]
  • $1 \le H \le 3$ を満たす。
小課題3 [120点]
  • $1 \le H, W \le 7$ を満たす。
小課題4 [150点]
  • $1 \le H, W \le 30$ を満たす。
小課題5 [200点]
  • 追加の制約はない。

入力例1

3 3
1 0 5
2 2 3
4 2 4

出力例1

21
ここでは, 上から $i$ 番目, 左から $j$ 番目を $(i, j)$ とします。
そのとき, 次のような進み方が最適です。
  • E869120は, $(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)$ と進む。
  • square1001は, $(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)$ と進む。
また, 2人は合計で21個のお土産を買うことができます。

入力例2

6 6
1 2 3 4 5 6
8 6 9 1 2 0
3 1 4 1 5 9
2 6 5 3 5 8
1 4 1 4 2 1
2 7 1 8 2 8

出力例2

97
問題文担当者:square1001
E - Circle and Many Triangles

Time Limit: 2 sec / Memory Limit: 256 MB

Max Score: $850$ Points

Problem statement

There is a circle which radius is 1.
There are $N$ vertices on the circle's circumference.
The vertices divides into $N$ equal parts over the circumference.

You can choose $3$ distinct vertices, and you can make a triangle.
There are $\frac{N(N - 1)(N - 2)}{6}$ ways choosing vertices. The question is: Calculate the area of $K$-th smallest triangle in $\frac{N(N-1)(N-2)}{6}$ triangles.
If the area is same, you can order in any order.

If $N = 4, K = 3$, the result is following:
  • If you select vertices $1$, $2$, and $3$, the area of triangle $= 1$.
  • If you select vertices $1$, $2$, and $4$, the area of triangle $= 1$.
  • If you select vertices $1$, $3$, and $4$, the area of triangle $= 1$.
  • If you select vertices $2$, $3$, and $4$, the area of triangle $= 1$.
As a result, the 3rd smallest triangle's area $= 1$.

Input

The input is given from Standard Input in the following format:
$N \ K$

Output

  • Please output the $K$-th triangle area.
  • Print a floating number denoting the answer. The relative or absolute error of your answer should not be higher than $10^{−9}$.

Constraints

  • $3 \le N \le 200,000$
  • $1 \le K \le \frac{N(N-1)(N-2)}{6}$

Subtasks

Subtask 1 [ $160$ points ]
  • $N \le 100$
Subtask 2 [ $240$ points ]
  • $N \le 1000$
Subtask 3 [ $450$ points ]
  • $N \le 200,000$

Sample Input 1

4 3

Sample Output 1

1.0000000000000
This example is already explained in the problem statement.

Sample Input 2

6 9

Sample Output 2

0.86602540378
There are $6$ ways to choose a triangle which area is $\frac{\sqrt{3}}{4}$.
There are $10$ ways to choose a triangle which area is $\frac{\sqrt{3}}{2}$.
There are $2$ ways to choose a triangle which area is $\frac{3 \sqrt{3}}{4}$.
Therefore, the 9th smallest triangle's area is $\frac{\sqrt{3}}{2}$.

Sample Input 3

12 220

Sample Output 3

1.29903810568
Writer: E869120
配点： $850$ 点

問題文

半径が $1$ の円があり、頂点 $1$ ～ $N$ が時計回りに並んでいます。
頂点は, 円周を $N$ 等分しています。
square1001は, $3$ つの頂点を選んで三角形を作ろうとしています。

$\frac{N(N-1)(N-2)}{6}$ 通りの作り方のうち, 面積が小さい順に数えて $K$ 番目となる三角形の面積を出力してください。
ただし, 面積が同じ場合は、面積だけを出力すればいいので順番は適当で構いません。

例えば, $N = 4, K = 3$ のとき, 次のようになります。
  • 3頂点の番号が $(1,2,3)$ のとき, 面積 $= 1$
  • 3頂点の番号が $(1,2,4)$ のとき, 面積 $= 1$
  • 3頂点の番号が $(1,3,4)$ のとき, 面積 $= 1$
  • 3頂点の番号が $(2,3,4)$ のとき, 面積 $= 1$
よって, 3番目の三角形の面積 $= 1.0$ となります。

入力

入力は以下の形式で標準入力から与えられる。
$N \ K$
  • 1行目に, 円周上にある点の数 $N$ と, 何番目の三角形かを表す整数 $K$ が, 空白区切りで与えられる。

出力

  • 面積が小さい順から数えて $K$ 番目となる三角形の面積を出力しなさい。
  • ただし, 絶対誤差または相対誤差が $10^{-9}$ 以下であれば正解とみなされる。

制約

  • $3 \le N \le 200,000$
  • $1 \le K \le \frac{N(N - 1)(N - 2)}{6}$

小課題

小課題1 [ $160$ 点 ]
  • $N \le 100$
小課題2 [ $240$点 ]
  • $N \le 1000$
小課題3 [ $450$点 ]
  • 追加の制約はない。

入力例1

4 3

出力例1

1.000000000000000000
この入力例は問題文で説明したとおりです。

入力例2

6 9

出力例2

0.86602540378
$N = 6$ のとき, 面積が $\frac{\sqrt{3}}{4}$ となるような頂点の選び方は $6$ 通り, 面積が $\frac{\sqrt{3}}{2}$ となるような頂点の選び方は $12$ 通り, 面積が $\frac{3 \sqrt{3}}{4}$ となるような頂点の選び方は $2$ 通りあります。
よって, $K = 9$ 番目の三角形の面積は $\frac{\sqrt{3}}{2}$ となります。

入力例3

12 220

出力例3

1.29903810568
$N = 12$ のとき, 三角形の作り方は $\frac{12 \times 11 \times 10}{6} = 220$ 通りあります。
この中で面積が一番大きいのは正三角形となるときなので, $K = 220$ 番目の三角形の面積は $\frac{3 \sqrt{3}}{4}$ となります。
問題作成者：E869120
F - Sushi

Time Limit: 3 sec / Memory Limit: 256 MB

Max Score: $1200$ Points

Problem statement

There are $N$ customers in a restaurant. Each customer is numbered $1$ through $N$.
A sushi chef carried out $Q$ operations for customers.

The $i$-th operation is follows:
  1. The sushi chef chooses a customer whose number of dishes of sushi eaten is minimum, in customer $1, 2, 3, \dots, a_i$. If there are multiple customers who are minimum numbers of dishes, he selects the minimum-numbered customers.
  2. He puts a dish of sushi on the selected seats.
  3. A customer who have selected for professional eats this sushi.
  4. Repeat 1-3, $b_i$ times.

Please calculate the number of dishes of sushi that have been eaten by each customer.

Input

The input is given from Standard Input in the following format:
$N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $ ： \ ： $ $a_Q \ b_Q$

Output

  • You have to print $N$ lines.
  • The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.

Constraints

  • $3 \le N, Q \le 100,000$
  • $1 \le a_i \le N$
  • $1 \le b_i \le 10^{12}$
  • Any final results do not exceed $2 \times 10^{13}$.

Subtasks

Subtask 1 [ $60$ points ]
  • $N, Q \le 100$
  • $b_i = 1$
Subtask 2 [ $400$ points ]
  • $N, Q \le 100$
  • $b_i \le 10^{12}$
Subtask 3 [ $240$ points ]
  • $N, Q \le 100,000$
  • $b_i = 1$
Subtask 4 [ $500$ points ]
  • There are no additional constraints.

Sample Input 1

9 3
5 11
8 4
4 7

Sample Output 1

4
4
4
4
2
2
1
1
0
The change of the number of dishes of sushi have eaten is following:

Customer 1 Customer 2 Customer 3 Customer 4 Customer 5 Customer 6 Customer 7 Customer 8 Customer 9
1st Operation 3 2 2 2 2 0 0 0 0
2nd Operation 3 2 2 2 2 2 1 1 0
3rd Operation 4 4 4 4 2 2 1 1 0

Sample Input 2

6 6
3 5
6 11
1 6
4 7
5 2
2 5

Sample Output 2

10
10
5
5
4
2

Sample Input 3

5 6
1 1
2 1
3 1
1 1
5 1
3 1

Sample Output 3

2
2
1
1
0

Sample Input 4

10 10
10 10
9 20
8 30
7 40
6 50
5 60
4 70
3 80
2 90
1 100

Sample Output 4

223
123
77
50
33
21
12
7
3
1
Writer: E869120
配点： $1200$ 点

問題文

$N$人の客が寿司屋にいます。それぞれの客には番号が付けられており, $1,2,3,…,N$ となっています。
板前は, 次の操作を $Q$ 回します。

$i$ 回目の操作では, 次のことをします。
  1. 板前は, 客 $1, 2, 3, \dots, a_i$ の中で食べた寿司の皿数が最も少ない人を選びます。そのような人が複数いる場合は, その中で番号が最も少ない人を選びます。
  2. 板前が選んだ人に寿司を渡します。
  3. 2. で選ばれた人は, 寿司を食べます。
  4. 1. ～ 3. のを $b_i$ 回繰り返します。

$Q$ 回すべての操作が終わったあと, それぞれの人が食べた寿司の皿数を計算してください。

入力

入力は以下の形式で標準入力から与えられる。
$N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $ ： \ ： $ $a_Q \ b_Q$
  • 1行目に, 客の数 $N$ と, 操作の回数 $Q$ が空白区切りで与えられる。
  • 2行目から $N$ 行にわたって, 整数 $a_i$, $b_i$ が空白区切りで与えられる。

出力

出力は以下の形式で標準出力に従うこと。
  • $N$ 行にわたって出力する。
  • $i$ 行目には, 客 $i$ が食べた寿司の皿数を出力しなさい。

制約

  • $3 \le N, Q \le 100,000$
  • $1 \le a_i \le N$
  • $1 \le b_i \le 10^{12}$
  • 最終的な値は, どれも $2 \times 10^{13}$ を超えない。

小課題

小課題1 [ $60$ 点 ]
  • $N, Q \le 100$
  • $b_i = 1$
小課題2 [ $400$ 点 ]
  • $N, Q \le 100$
  • $b_i \le 10^{12}$
小課題3 [ $240$ 点 ]
  • $N, Q \le 100,000$
  • $b_i = 1$
小課題4 [ $500$ 点 ]
  • 追加の制約はない。

入力例1

9 3
5 11
8 4
4 7

出力例1

4
4
4
4
2
2
1
1
0
客が食べた寿司の皿数の変化は以下の通りです。

客1 客2 客3 客4 客5 客6 客7 客8 客9
1回目の操作 3 2 2 2 2 0 0 0 0
2回目の操作 3 2 2 2 2 2 1 1 0
3回目の操作 4 4 4 4 2 2 1 1 0

入力例2

6 6
3 5
6 11
1 6
4 7
5 2
2 5

出力例2

10
10
5
5
4
2

入力例3

5 6
1 1
2 1
3 1
1 1
5 1
3 1

出力例3

2
2
1
1
0

入力例4

10 10
10 10
9 20
8 30
7 40
6 50
5 60
4 70
3 80
2 90
1 100

出力例4

223
123
77
50
33
21
12
7
3
1
問題作成者 : E869120
G - Sum of Fibonacci Sequence

Time Limit: 2 sec / Memory Limit: 256 MB

Max Score: $1400$ Points

Problem Statement

E869120 defined a sequence $a$ like this:
  • $a_1=a_2=1$, $a_{k+2}=a_{k+1}+a_k \ (k \ge 1)$

He also defined sequences $d_1, d_2, d_3, \dots , d_n$, as the following recurrence relation :
  • $d_{1, j} = a_j$
  • $d_{i, j} = \sum_{k = 1}^j d_{i - 1, k} \ (i \ge 2)$

You are given integers $n$ and $m$. Please calculate the value of $d_{n, m}$.
Since the answer can be large number, print the answer modulo $998,244,353$.
Can you solve this problem???

Input

The input is given from standard input in the following format.

$n \quad m$

Output

  • Print $d_{n, m}$ modulo $998,244,353$.

Constraints

  • $1 \le n \le 200,000$
  • $1 \le m \le 10^{18}$

Subtasks

Subtask 1 [ $100$ points ]
  • The testcase in this subtask satisfies $1 \le n, m \le 3,000$.
Subtask 2 [ $170$ points ]
  • The testcase in this subtask satisfies $1 \le m \le 200,000$.
Subtask 3 [ $230$ points ]
  • The testcase in this subtask satisfies $1 \le n \le 3$.
Subtask 4 [ $420$ points ]
  • The testcase in this subtask satisfies $1 \le n \le 1000$.
Subtask 5 [ $480$ points ]
  • There are no additional constraints.

Sample Input 1

4 7

Sample Output 1

176
The sequence is following:
$d_{i, 1}$ $d_{i, 2}$ $d_{i, 3}$ $d_{i, 4}$ $d_{i, 5}$ $d_{i, 6}$ $d_{i, 7}$
$d_1$ 1 1 2 3 5 8 13
$d_2$ 1 2 4 7 12 20 33
$d_3$ 1 3 7 14 26 46 79
$d_4$ 1 4 11 25 51 97 176

As a result, the answer is $d_{4, 7} = 176$.

Sample Input 2

12 20

Sample Output 2

174174144
Interesting number. It only contains $1$, $4$ and $7$.

Sample Input 3

16 30

Sample Output 3

102292850
You can calculate that $d_{16, 30} = 1,193,004,294,685$.
Please don't forget printing the answer mod $998,244,353$.
Writer：square1001
配点： $1400$ 点

問題文

次のような数列があります。
  • $a_1=a_2=1$, $a_{k+2}=a_{k+1}+a_k \ (k \ge 1)$

E869120は, この数列を使って次のように数列 $d_1, d_2, d_3, \dots , d_n$ を定義することにしました。
  • $d_{1, j} = a_j$
  • $d_{i, j} = \sum_{k = 1}^j d_{i - 1, k} \ (i \ge 2)$

整数 $n, m$ が与えられます。そのとき, $d_{n, m}$ の値を求めてください。
ただし, 答えが非常に大きくなることがあるので, $998,244,353$ で割った余りを求めてください。
あなたはこの問題が解けますか???

入力

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

$n \quad m$
  • 1行目には, 整数 $n, m$ が空白区切りで与えられる。

出力

  • $d_{n, m}$ を $998,244,353$ で割った余りを求めなさい。

制約

  • $1 \le n \le 200,000$
  • $1 \le m \le 10^{18}$

小課題

小課題1 [ $100$ 点 ]
  • $1 \le n, m \le 3,000$ を満たす。
小課題2 [ $170$ 点 ]
  • $1 \le m \le 200,000$ を満たす。
小課題3 [ $230$ 点 ]
  • $1 \le n \le 3$ を満たす。
小課題4 [ $420$ 点 ]
  • $1 \le n \le 1000$ を満たす。
小課題5 [ $480$ 点 ]
  • 追加の制約はない。

入力例1

4 7

出力例1

176
以下のような数列になっています。
$d_{i, 1}$ $d_{i, 2}$ $d_{i, 3}$ $d_{i, 4}$ $d_{i, 5}$ $d_{i, 6}$ $d_{i, 7}$
$d_1$ 1 1 2 3 5 8 13
$d_2$ 1 2 4 7 12 20 33
$d_3$ 1 3 7 14 26 46 79
$d_4$ 1 4 11 25 51 97 176

よって, $d_{4, 7} = 176$ となり, これが答えとなります。

入力例2

12 20

出力例2

174174144

入力例3

16 30

出力例3

102292850
$d_{16, 30} = 1,193,004,294,685$ なので, これを $998,244,353$ で割った余りは $102,292,850$ です。
問題文担当者：square1001
H - Bombs Searching Game

Time Limit: 1 sec / Memory Limit: 256 MB

Max Score: $1500$ Points

Problem Statement

There is a $50 \times 50$ field. The cell at $i$-th row and $j$-th column is denoted $(i, j)$ (0-indexed).
One day, square1001 puts $250$ bombs in this field. In each cell, there is 1 or 0 bomb.
You want to know where the bombs are by asking some questions.

You can ask this question many times.
  • You can ask the number of bombs in the rectangular area in which upper-left cell is $(a, b)$ and lower-right cell is $(c, d)$.

Please find all bombs' positions asking as few questions as possible.

Note: This problem Input/Output type is special. Please read Input/Output. If you want to use scanf/printf, you have to write fflush(stdout).

Input and output

The first line input is following this format:
$H \ W \ N \ K$
  • $H, W$ is field size. In this problem, $H = 50$ and $W = 50$.
  • $N$ is the number of bombs in the field. In this problem, $N = 250$.
  • $K$ is modulo. This integer uses to answer the state of the field.

After this input, You can ask some questions, following this output format:
$? \ a \ b \ c \ d$
It means that you want to ask the number of bombs in the rectangular area which upper-left cell is $(a, b)$ and lower-right cell is $(c, d)$.

You can know the value of the question, from input in this format:
$p$
$p$ is the result of your question.

Finally, you have to output the answer following this format:
$! \ ans$
The value of $ans$ is $\sum_{i=0}^{H-1} \sum_{j=0}^{W-1} r_{i, j} 2^{iW + j}$ mod $K$. Note: $r_{i, j}$ is the number of bombs in cell $(i, j)$.

Constraints

  • $H, W = 50$
  • $N = 250$
  • $1,000,000,000 \le K \le 1,000,010,000$ ($K$ is random)

Score

There are 5 testcases in the judge.
The $score$ in each testcase is defined by following formula:
  • $Q$ is the number of questions.
  • If $Q > 2500$, $score = 0$ (Wrong Answer).
  • If $930 \le Q \le 2500$, $score = max(\lfloor 125 - 3.2\sqrt{Q - 920} \rfloor, 40)$.
  • If $880 \le Q < 930$, $score = \lfloor 288 - 22\sqrt{Q - 870} \rfloor$.
  • If $Q < 880$, $score = min(2860 - 3Q, 300)$.

Sample Input・Output

In the case of the following arrangement, this input / output is conceivable.
This case is $H,W=4$, so this example is not include in testcases.
H=4, W=4, N=4
1001
0000
0010
0100
Example of Input・Output
Input from program Output
4 4 4 1000000007
? 0 0 0 1
1
? 0 1 0 2
0
? 0 3 1 3
1
? 2 1 3 2
2
? 2 2 2 2
1
! 9225
These question is not always meaningful.
Writer: E869120
配点： $1500$ 点

問題文

さて, このsquare869120Contest #3も, 最終問題となってしまった。
square1001氏は, 最終兵器として, あるダンジョンに爆弾を仕掛けた。
そのダンジョンは, 左上のマスが $(0,0)$, 右下のマスが $(49,49)$ の $50 \times 50$ の大きさである。

その中には, 250個の爆弾が仕掛けられている。位置はすべて違うマスである。
あなたは, 全ての爆弾の位置を知ることで, そのダンジョンから脱出できる。
「そんなん、どうやって知ればいいんだよ！　全く分かんねぇじゃないか！助けてぇぇぇぇぇ！」

しかし、あなたは以下の質問を何回かできる。
  • 左上のマス $(a, b)$, 右下のマス $(c, d)$ の区間に何個爆弾があるかを聞くことができる。

しかし, 質問回数が多くなればなるほど, 爆弾の爆発する確率が高くなり, すなわち生存確率が下がる。
そのため, できるだけ少ない質問回数で爆弾250個の配置を当ててほしい。(その方が得点が高い)
あなたの挑戦を待っている。

入出力

最初, 以下のように入力される。
$H \ W \ N \ K$
  • $H, W$ はダンジョンの大きさである。この問題では, $H, W = 50$ である。
  • $N$ はダンジョンの中に含まれる爆弾の数である。この問題では, $N = 250$ である。
  • $K$ は最終的な盤面の状態を出力するために使う整数である。
次に, 次のような質問を何回かすることができる。
質問は以下のような形式で出力することによってできる。
$? \ a \ b \ c \ d$
これは, 左上のマス $(a, b)$, 右下のマス $(c, d)$ の区間に存在する爆弾の数を聞くことである。

また, 質問の返答は, 以下のような出力で行われる。
$p$
$p$ は, 質問で聞いた区間に存在する爆弾の総数である。

また, 答えが分かった時に, 以下のような出力をしなければならない。
$! \ ans$
ただし, $ans$ は以下の値であり, $r_{i, j}$ は, マス $(i, j)$ にある爆弾の個数である。
  • $ans = \sum_{i=0}^{H-1} \sum_{j=0}^{W-1} r_{i, j} 2^{iW + j}$ mod $K$

制約

  • $H, W = 50$
  • $N = 250$
  • $1,000,000,000 \le K \le 1,000,01,000$ ($K$はランダムに与えられる)

得点

5つのテストケースがある。各テストケースに対する得点は, 以下のように計算される。
  • 質問回数を $Q$ とする。
  • $Q > 2500$ のとき, $0$ 点 (Wrong Answer) となる。
  • $930 \le Q \le 2500$ のとき, $score = max(\lfloor 125 - 3.2\sqrt{Q - 920} \rfloor, 40)$ となる。
  • $880 \le Q < 930$ のとき, $score = \lfloor 288 - 22\sqrt{Q - 870} \rfloor$ となる。
  • $Q < 880$ のとき, $score = min(2860 - 3Q, 300)$ となる。

入出力例1

例えば, 以下のような配置の場合、以下のような入出力が考えられる。
ただし, この場合 $H = W = 4, N = 4$ なので, 実際のテストケースには存在しない。
H=4, W=4, N=4
1001
0000
0010
0100
入出力として考えられる例
プログラムへの入力 プログラムの出力
4 4 4 1000000007
? 0 0 0 1
1
? 0 1 0 2
0
? 0 3 1 3
1
? 2 1 3 2
2
? 2 2 2 2
1
! 9225
ただし, 必ずしも意味のある質問をしているとは限りません。
また, これらの情報で必ずしも盤面が把握できるとは限らず, エスパーをすることも許されはします。
問題作成者: E869120