E. Vladik and Entertaining Flags

problem_index: E

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
Partitioning on components for every segment from first test case:
![image](images/cf_811_E/2.png)

source: codeforces

raw_problem:
E. Vladik and Entertaining Flags

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

In his spare time Vladik estimates beauty of the flags.

Every flag could be represented as the matrix n × m which consists of positive integers.

Let's define the beauty of the flag as number of components in its matrix. We call component a set of cells with same numbers and between any pair of cells from that set there exists a path through adjacent cells from same component. Here is the example of the partitioning some flag matrix into components:

But this time he decided to change something in the process. Now he wants to estimate not the entire flag, but some segment. Segment of flag can be described as a submatrix of the flag matrix with opposite corners at (1, l) and (n, r), where conditions 1 ≤ l ≤ r ≤ m are satisfied.

Help Vladik to calculate the beauty for some segments of the given flag.

Input

First line contains three space-separated integers n, m, q (1 ≤ n ≤ 10, 1 ≤ m, q ≤ 105) — dimensions of flag matrix and number of segments respectively.

Each of next n lines contains m space-separated integers — description of flag matrix. All elements of flag matrix is positive integers not exceeding 106.

Each of next q lines contains two space-separated integers l, r (1 ≤ l ≤ r ≤ m) — borders of segment which beauty Vladik wants to know.

Output

For each segment print the result on the corresponding line.

Example

Input

4 5 4
1 1 1 1 1
1 2 2 3 3
1 1 1 2 5
4 4 5 5 5
1 5
2 5
1 2
4 5

Output

6
7
3
4

Note

Partitioning on components for every segment from first test case:

question:
In his spare time Vladik estimates beauty of the flags.
Every flag could be represented as the matrix n × m which consists of positive integers.
Let's define the beauty of the flag as number of components in its matrix. We call component a set of cells with same numbers and between any pair of cells from that set there exists a path through adjacent cells from same component. Here is the example of the partitioning some flag matrix into components:
 ![image](1.png) But this time he decided to change something in the process. Now he wants to estimate not the entire flag, but some segment. Segment of flag can be described as a submatrix of the flag matrix with opposite corners at (1, l) and (n, r), where conditions 1 ≤ l ≤ r ≤ m are satisfied.
Help Vladik to calculate the beauty for some segments of the given flag.

Input
First line contains three space-separated integers n, m, q (1 ≤ n ≤ 10, 1 ≤ m, q ≤ 10^{5}) — dimensions of flag matrix and number of segments respectively.
Each of next n lines contains m space-separated integers — description of flag matrix. All elements of flag matrix is positive integers not exceeding 10^{6}.
Each of next q lines contains two space-separated integers l, r (1 ≤ l ≤ r ≤ m) — borders of segment which beauty Vladik wants to know.

Output
For each segment print the result on the corresponding line.

Example
Input
4 5 4
1 1 1 1 1
1 2 2 3 3
1 1 1 2 5
4 4 5 5 5
1 5
2 5
1 2
4 5

Output
6
7
3
4

Note
Partitioning on components for every segment from first test case:
![image](2.png)

tags: ['Spanning trees', 'Graph algorithms', 'Data structures']

skill_types: ['Data structures']

image_tags: Patterns Patterns

data_split: test


G. Andryusha and Nervous Barriers

problem_index: G

time_limit: 4 seconds

memory_limit: 256 megabytes

note:
In the first sample case, there is a single barrier: if one throws a marble in the second or the third column, two marbles come out, otherwise there is only one. The total answer is 7.
In the second sample case, the numbers of resulting marbles are 2, 2, 4, 4, 4 in order of indexing columns with the initial marble.
In the third sample case, the numbers of resulting marbles are 1, 1, 4, 4, 4. Note that the first barrier evades the marbles falling from the top of the board, but does not evade the marbles falling from the second barrier.
In the fourth sample case, the numbers of resulting marbles are 2, 2, 6, 6, 6, 6, 6, 6, 6, 1, 2, 1, 1, 1, 1. The picture below shows the case when a marble is thrown into the seventh column.
![image](images/cf_780_G/2.png) The result of throwing a marble into the seventh column.

source: codeforces

raw_problem:
G. Andryusha and Nervous Barriers

time limit per test
4 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Andryusha has found a perplexing arcade machine. The machine is a vertically adjusted board divided into square cells. The board has w columns numbered from 1 to w from left to right, and h rows numbered from 1 to h from the bottom to the top.

Further, there are barriers in some of board rows. There are n barriers in total, and i-th of them occupied the cells li through ri of the row ui. Andryusha recollects well that no two barriers share the same row. Furthermore, no row is completely occupied with a barrier, that is, at least one cell in each row is free.

The player can throw a marble to any column of the machine from above. A marble falls downwards until it encounters a barrier, or falls through the bottom of the board. A marble disappears once it encounters a barrier but is replaced by two more marbles immediately to the left and to the right of the same barrier. In a situation when the barrier is at an edge of the board, both marbles appear next to the barrier at the side opposite to the edge. More than one marble can occupy the same place of the board, without obstructing each other's movement. Ultimately, all marbles are bound to fall from the bottom of the machine.
  Examples of marble-barrier interaction.
Peculiarly, sometimes marbles can go through barriers as if they were free cells. That is so because the barriers are in fact alive, and frightened when a marble was coming at them from a very high altitude. More specifically, if a marble falls towards the barrier i from relative height more than si (that is, it started its fall strictly higher than ui + si), then the barrier evades the marble. If a marble is thrown from the top of the board, it is considered to appear at height (h + 1).

Andryusha remembers to have thrown a marble once in each of the columns. Help him find the total number of marbles that came down at the bottom of the machine. Since the answer may be large, print it modulo 109 + 7.

Input

The first line contains three integers h, w, and n (1 ≤ h ≤ 109, 2 ≤ w ≤ 105, 0 ≤ n ≤ 105) — the number of rows, columns, and barriers in the machine respectively.

Next n lines describe barriers. i-th of these lines containts four integers ui, li, ri, and si (1 ≤ ui ≤ h, 1 ≤ li ≤ ri ≤ w, 1 ≤ si ≤ 109) — row index, leftmost and rightmost column index of i-th barrier, and largest relative fall height such that the barrier does not evade a falling marble. It is guaranteed that each row has at least one free cell, and that all ui are distinct.

Output

Print one integer — the answer to the problem modulo 109 + 7.

Examples

Input

10 5 1
3 2 3 10

Output

7

Input

10 5 2
3 1 3 10
5 3 5 10

Output

16

Input

10 5 2
3 1 3 7
5 3 5 10

Output

14

Input

10 15 4
7 3 9 5
6 4 10 1
1 1 4 10
4 11 11 20

Output

53

Note

In the first sample case, there is a single barrier: if one throws a marble in the second or the third column, two marbles come out, otherwise there is only one. The total answer is 7.

In the second sample case, the numbers of resulting marbles are 2, 2, 4, 4, 4 in order of indexing columns with the initial marble.

In the third sample case, the numbers of resulting marbles are 1, 1, 4, 4, 4. Note that the first barrier evades the marbles falling from the top of the board, but does not evade the marbles falling from the second barrier.

In the fourth sample case, the numbers of resulting marbles are 2, 2, 6, 6, 6, 6, 6, 6, 6, 1, 2, 1, 1, 1, 1. The picture below shows the case when a marble is thrown into the seventh column.
  The result of throwing a marble into the seventh column.

question:
Andryusha has found a perplexing arcade machine. The machine is a vertically adjusted board divided into square cells. The board has w columns numbered from 1 to w from left to right, and h rows numbered from 1 to h from the bottom to the top.
Further, there are barriers in some of board rows. There are n barriers in total, and i-th of them occupied the cells l_{i} through r_{i} of the row u_{i}. Andryusha recollects well that no two barriers share the same row. Furthermore, no row is completely occupied with a barrier, that is, at least one cell in each row is free.
The player can throw a marble to any column of the machine from above. A marble falls downwards until it encounters a barrier, or falls through the bottom of the board. A marble disappears once it encounters a barrier but is replaced by two more marbles immediately to the left and to the right of the same barrier. In a situation when the barrier is at an edge of the board, both marbles appear next to the barrier at the side opposite to the edge. More than one marble can occupy the same place of the board, without obstructing each other's movement. Ultimately, all marbles are bound to fall from the bottom of the machine.
 ![image](1.png) Examples of marble-barrier interaction. Peculiarly, sometimes marbles can go through barriers as if they were free cells. That is so because the barriers are in fact alive, and frightened when a marble was coming at them from a very high altitude. More specifically, if a marble falls towards the barrier i from relative height more than s_{i} (that is, it started its fall strictly higher than u_{i} + s_{i}), then the barrier evades the marble. If a marble is thrown from the top of the board, it is considered to appear at height (h + 1).
Andryusha remembers to have thrown a marble once in each of the columns. Help him find the total number of marbles that came down at the bottom of the machine. Since the answer may be large, print it modulo 10^{9} + 7.

Input
The first line contains three integers h, w, and n (1 ≤ h ≤ 10^{9}, 2 ≤ w ≤ 10^{5}, 0 ≤ n ≤ 10^{5}) — the number of rows, columns, and barriers in the machine respectively.
Next n lines describe barriers. i-th of these lines containts four integers u_{i}, l_{i}, r_{i}, and s_{i} (1 ≤ u_{i} ≤ h, 1 ≤ l_{i} ≤ r_{i} ≤ w, 1 ≤ s_{i} ≤ 10^{9}) — row index, leftmost and rightmost column index of i-th barrier, and largest relative fall height such that the barrier does not evade a falling marble. It is guaranteed that each row has at least one free cell, and that all u_{i} are distinct.

Output
Print one integer — the answer to the problem modulo 10^{9} + 7.

Examples
Input
10 5 1
3 2 3 10

Output
7

Input
10 5 2
3 1 3 10
5 3 5 10

Output
16

Input
10 5 2
3 1 3 7
5 3 5 10

Output
14

Input
10 15 4
7 3 9 5
6 4 10 1
1 1 4 10
4 11 11 20

Output
53

Note
In the first sample case, there is a single barrier: if one throws a marble in the second or the third column, two marbles come out, otherwise there is only one. The total answer is 7.
In the second sample case, the numbers of resulting marbles are 2, 2, 4, 4, 4 in order of indexing columns with the initial marble.
In the third sample case, the numbers of resulting marbles are 1, 1, 4, 4, 4. Note that the first barrier evades the marbles falling from the top of the board, but does not evade the marbles falling from the second barrier.
In the fourth sample case, the numbers of resulting marbles are 2, 2, 6, 6, 6, 6, 6, 6, 6, 1, 2, 1, 1, 1, 1. The picture below shows the case when a marble is thrown into the seventh column.
 ![image](2.png) The result of throwing a marble into the seventh column.

tags: ['Dynamic programming', 'Data structures']

image_tags: Map Map

data_split: test


Grid Number

source: Hokkaido University Programming Contest 2019 Day 1, Hokkaido University Competitive Programming Camp 2019

raw_problem:
F: グリッドの番号

問題

えびちゃんは、横 <var>n</var> 列、縦 <var>2</var> 行のグリッドに <var>1</var> から <var>2 \times n</var> までの整数をちょうど <var>1</var> つずつ書き込もうとしています。

グリッドの各マスにはちょうど <var>1</var> つの整数しか書き込めません。

普通に書き込むだけでは面白くないので、以下のようなルールを定めました。

隣り合う <var>2</var> つのマスに書き込まれた整数の、差の絶対値は <var>k</var> 以下である。

あるマスの右にマスが存在する時、あるマスに書き込まれた整数は、右のマスに書き込まれた整数より真に小さい。

あるマスの下にマスが存在する時、あるマスに書き込まれた整数は、下のマスに書き込まれた整数より真に小さい。

ここで、隣り合う <var>2</var> つのマスとは、あるマスと上下左右の辺を共有するマスのことを表します。

このような書き込み方は何通りあるでしょうか?
答えが非常に大きくなる可能性があるので、素数 <var>m</var> で割った余りを出力してください。

補足

上記の <var>2</var> 番目のルールと <var>3</var> 番目のルールは、以下の図のように、不等号に違反しないように整数を書き込むことを要求しています。

入力形式

入力として整数が 3 つ与えられます。

<var>n</var> <var>k</var> <var>m</var>

制約

<var>1 \leq n \leq 100</var>

<var>1 \leq k \leq 10</var>

<var>2 \leq m \leq 10^9+7</var>

 <var>m</var> は素数

出力形式

数字の書き込み方の通り数を一行に出力してください。
また、末尾の改行を忘れないように注意してください。

入力例 1

3 2 7

出力例 1

1

上記の書き込み方が条件を満たし、これ以外に条件を満たす書き込み方は存在しません。

入力例 2

5 10 11

出力例 2

9

<var>m</var> で割った余りを出力してください。

solutions: ["import sys\ninput = lambda : sys.stdin.readline().rstrip()\n\nsys.setrecursionlimit(2*10**5+10)\nwrite = lambda x: sys.stdout.write(x+\"\\n\")\ndebug = lambda x: sys.stderr.write(x+\"\\n\")\nwritef = lambda x: print(\"{:.12f}\".format(x))\n\ndef sub(v,v2,b):\n    for i in range(k+1):\n        if not b>>i&1:\n            return i\n    return k+1\nn,k,M = list(map(int, input().split()))\nd = {} # (v,v2,b) : \u7aef\u304c(v,v2)\u3067\u3001(b>>i)&1 \u306e\u3068\u304d v+i \u304c\u4f7f\u308f\u308c\u3066\u3044\u308b\nfor i in range(2,min(k+1, n+1)+1):\n    d[(1,i,1|(1<<(i-1)))] = 1\n# print(d)\nfor i in range(n-1):\n    nd = {}\n    for (v,v2,b),val in d.items():\n        res = sub(v,v2,b)\n        nv = v + res\n        if nv>v+k:\n            continue\n        for nv2 in range(nv+1, min(nv+k, 2*n)+1):\n            if (b>>(nv2-v))&1 or nv2<v2 or nv2<nv or nv2>v2+k:\n                continue\n            nb = (b|(1<<res)|(1<<(nv2-v)))>>res\n            \n            nd.setdefault((nv,nv2,nb), 0)\n            nd[nv,nv2,nb] += val\n            nd[nv,nv2,nb] %= M\n    d = nd\n#     print(d)\nans = sum(d.values())%M\nprint(ans%M)\n", "from collections import Counter\nN, K, mod = map(int, input().split())\ndp = [Counter() for _ in range(2*N)]\n\ndp[0][(None, (0,))] = 1\nfor i in range(2*N-1):\n    for (left, top), v in dp[i].items():\n        if len(top) > K+1:\n            continue\n        if left == None:\n            if top and i+1 - top[0] <= K:\n                dp[i+1][(i+1, top)] = (dp[i+1][(i+1, top)] + v) % mod \n        elif (i+1 - left <= K) and len(top) > 1 and (i+1 - top[1] <= K):\n            dp[i+1][(i+1, top[1:])] = (dp[i+1][(i+1, top[1:])] + v) % mod\n        if top and (i+1 - top[-1] <= K):\n            top = list(top)\n            top.append(i+1)\n            top = tuple(top)\n            dp[i+1][(left, top)] = (dp[i+1][(left, top)] + v) % mod\n\nres = 0\nfor (left, top), v in dp[2*N-1].items():\n    if len(top) == 1:\n        assert left == 2*N - 1\n        res = (res + v) % mod\nprint(res)\n\n"]

source: aizu

question:
F: Grid Numbering
Problem

Ebi-chan is trying to write integers from $1$ to $2 \times n$ into a grid with $n$ horizontal columns and $2$ vertical rows, with exactly one integer per square.
No more than one integer can be written in each square of the grid.
To make it more interesting than just writing the numbers ordinarily, she defined the following rules:

- The absolute difference between the integers written in two adjacent squares must be at most $k$.
- If there is a square to the right of a certain square, the integer written in that square must be strictly smaller than the integer written in the right square.
- If there is a square below a certain square, the integer written in that square must be strictly smaller than the integer written in the square below it.

Here, two adjacent squares refer to the squares that share an edge either vertically or horizontally.

How many ways are there to write the integers according to these rules?
Since the answer could become very large, please output the remainder when divided by a prime number $m$.

Supplement

The above second and third rules require you to write integers such that they do not violate the inequalities, as shown in the following figure.

![image](1.png)
Input Format

You are given three integers as input.
$n$ $k$ $m$
Constraints

- $1 \leq n \leq 100$
- $1 \leq k \leq 10$
- $2 \leq m \leq 10^9+7$
- $m$ is a prime number

Output Format

Please output the number of ways to write the integers on one line.
Also, be careful not to forget the trailing newline.

Example Input 1

3 2 7
Example Output 1

1

![image](2.png)

- The above way of writing satisfies the conditions, and no other way of writing satisfies the conditions.

Example Input 2

5 10 11
Example Output 2

9

- Please output the remainder after division by $m$.

image_tags: Others Others

data_split: test


Cubic Colonies

source: ACM International Collegiate Programming Contest, Asia Regional 2012, Japan

raw_problem:
Problem J: Cubic Colonies

In AD 3456, the earth is too small for hundreds of billions of people to live in peace. Interstellar Colonization Project with Cubes (ICPC) is a project that tries to move people on the earth to space colonies to ameliorate the problem. ICPC obtained funding from governments and manufactured space colonies very quickly and at low cost using prefabricated cubic blocks.

The largest colony looks like a Rubik's cube. It consists of 3 × 3 × 3 cubic blocks (Figure J.1A). Smaller colonies miss some of the blocks in the largest colony.

When we manufacture a colony with multiple cubic blocks, we begin with a single block. Then we iteratively glue a next block to existing blocks in a way that faces of them match exactly. Every pair of touched faces is glued.

Figure J.1: Example of the largest colony and a smaller colony

However, just before the first launch, we found a design flaw with the colonies. We need to add a cable to connect two points on the surface of each colony, but we cannot change the inside of the prefabricated blocks in a short time. Therefore we decided to attach a cable on the surface of each colony. If a part of the cable is not on the surface, it would be sheared off during the launch, so we have to put the whole cable on the surface. We would like to minimize the lengths of the cables due to budget constraints. The dashed line in Figure J.1B is such an example.

Write a program that, given the shape of a colony and a pair of points on its surface, calculates the length of the shortest possible cable for that colony.

Input

The input contains a series of datasets. Each dataset describes a single colony and the pair of the points for the colony in the following format.

x1 y1 z1 x2 y2 z2

b0,0,0b1,0,0b2,0,0

b0,1,0b1,1,0b2,1,0

b0,2,0b1,2,0b2,2,0

b0,0,1b1,0,1b2,0,1

b0,1,1b1,1,1b2,1,1

b0,2,1b1,2,1b2,2,1

b0,0,2b1,0,2b2,0,2

b0,1,2b1,1,2b2,1,2

b0,2,2b1,2,2b2,2,2

(x1, y1, z1) and (x2, y2, z2) are the two distinct points on the surface of the colony, where x1, x2, y1, y2, z1, z2 are integers that satisfy 0 ≤ x1, x2, y1, y2, z1, z2 ≤ 3. bi,j,k is '#' when there is a cubic block whose two diagonal vertices are (i, j, k) and (i + 1, j + 1, k + 1), and bi,j,k is '.' if there is no block. Figure J.1A corresponds to the first dataset in the sample input, whereas Figure J.1B corresponds to the second. A cable can pass through a zero-width gap between two blocks if they are touching only on their vertices or edges. In Figure J.2A, which is the third dataset in the sample input, the shortest cable goes from the point A (0, 0, 2) to the point B (2, 2, 2), passing through (1, 1, 2), which is shared by six blocks. Similarly, in Figure J.2B (the fourth dataset in the sample input), the shortest cable goes through the gap between two blocks not glued directly. When two blocks share only a single vertex, you can put a cable through the vertex (Figure J.2C; the fifth dataset in the sample input).

You can assume that there is no colony consisting of all 3 × 3 × 3 cubes but the center cube.

Six zeros terminate the input.

Figure J.2: Dashed lines are the shortest cables. Some blocks are shown partially transparent
for illustration.

Output

For each dataset, output a line containing the length of the shortest cable that connects the two given points. We accept errors less than 0.0001. You can assume that given two points can be connected by a cable.

Sample Input

0 0 0 3 3 3
###
###
###
###
###
###
###
###
###
3 3 0 0 0 3
#..
###
###
###
###
###
#.#
###
###
0 0 2 2 2 2
...
...
...
.#.
#..
...
##.
##.
...
0 1 2 2 1 1
...
...
...
.#.
#..
...
##.
##.
...
3 2 0 2 3 2
###
..#
...
..#
...
.#.
..#
..#
.##
0 0 0 0 0 0

Output for the Sample Input

6.70820393249936941515
6.47870866461907457534
2.82842712474619029095
2.23606797749978980505
2.82842712474619029095

source: aizu

question:
Problem J: Cubic Colonies

In AD 3456, the earth is too small for hundreds of billions of people to live in peace. Interstellar Colonization Project with Cubes (ICPC) is a project that tries to move people on the earth to space colonies to ameliorate the problem. ICPC obtained funding from governments and manufactured space colonies very quickly and at low cost using prefabricated cubic blocks.

The largest colony looks like a Rubik's cube. It consists of 3 × 3 × 3 cubic blocks (Figure J.1A). Smaller colonies miss some of the blocks in the largest colony.

When we manufacture a colony with multiple cubic blocks, we begin with a single block. Then we iteratively glue a next block to existing blocks in a way that faces of them match exactly. Every pair of touched faces is glued.

![image](1.png)

Figure J.1: Example of the largest colony and a smaller colony

However, just before the first launch, we found a design flaw with the colonies. We need to add a cable to connect two points on the surface of each colony, but we cannot change the inside of the prefabricated blocks in a short time. Therefore we decided to attach a cable on the surface of each colony. If a part of the cable is not on the surface, it would be sheared off during the launch, so we have to put the whole cable on the surface. We would like to minimize the lengths of the cables due to budget constraints. The dashed line in Figure J.1B is such an example.

Write a program that, given the shape of a colony and a pair of points on its surface, calculates the length of the shortest possible cable for that colony.

Input

The input contains a series of datasets. Each dataset describes a single colony and the pair of the points for the colony in the following format.

x_{1} y_{1} z_{1} x_{2} y_{2} z_{2}
b_{0,0,0}b_{1,0,0}b_{2,0,0}
b_{0,1,0}b_{1,1,0}b_{2,1,0}
b_{0,2,0}b_{1,2,0}b_{2,2,0}
b_{0,0,1}b_{1,0,1}b_{2,0,1}
b_{0,1,1}b_{1,1,1}b_{2,1,1}
b_{0,2,1}b_{1,2,1}b_{2,2,1}
b_{0,0,2}b_{1,0,2}b_{2,0,2}
b_{0,1,2}b_{1,1,2}b_{2,1,2}
b_{0,2,2}b_{1,2,2}b_{2,2,2}

(x_{1}, y_{1}, z_{1}) and (x_{2}, y_{2}, z_{2}) are the two distinct points on the surface of the colony, where x_{1}, x_{2}, y_{1}, y_{2}, z_{1}, z_{2} are integers that satisfy 0 ≤ x_{1}, x_{2}, y_{1}, y_{2}, z_{1}, z_{2} ≤ 3. b_{i,j,k} is '#' when there is a cubic block whose two diagonal vertices are (i, j, k) and (i + 1, j + 1, k + 1), and b_{i,j,k} is '.' if there is no block. Figure J.1A corresponds to the first dataset in the sample input, whereas Figure J.1B corresponds to the second. A cable can pass through a zero-width gap between two blocks if they are touching only on their vertices or edges. In Figure J.2A, which is the third dataset in the sample input, the shortest cable goes from the point A (0, 0, 2) to the point B (2, 2, 2), passing through (1, 1, 2), which is shared by six blocks. Similarly, in Figure J.2B (the fourth dataset in the sample input), the shortest cable goes through the gap between two blocks not glued directly. When two blocks share only a single vertex, you can put a cable through the vertex (Figure J.2C; the fifth dataset in the sample input).

You can assume that there is no colony consisting of all 3 × 3 × 3 cubes but the center cube.

Six zeros terminate the input.

![image](2.png)

Figure J.2: Dashed lines are the shortest cables. Some blocks are shown partially transparent
for illustration.

Output

For each dataset, output a line containing the length of the shortest cable that connects the two given points. We accept errors less than 0.0001. You can assume that given two points can be connected by a cable.

Sample Input

0 0 0 3 3 3
###
###
###
###
###
###
###
###
###
3 3 0 0 0 3
#..
###
###
###
###
###
#.#
###
###
0 0 2 2 2 2
...
...
...
.#.
#..
...
##.
##.
...
0 1 2 2 1 1
...
...
...
.#.
#..
...
##.
##.
...
3 2 0 2 3 2
###
..#
...
..#
...
.#.
..#
..#
.##
0 0 0 0 0 0

Output for the Sample Input

6.70820393249936941515
6.47870866461907457534
2.82842712474619029095
2.23606797749978980505
2.82842712474619029095

image_tags:
3D Geometry
3D Geometry

data_split: test


Triangle Ornaments

difficulty: EASY

source: open kattis

raw_problem:
A company makes triangle-shaped ornaments for the
    upcoming holidays. Each ornament is tied at one of its corners
    to a rod using a string of unknown length. Multiple of these
    ornaments may be attached to the same rod. These ornaments
    should be able to swing (rotate around the axis formed by the
    string) without interfering with each other.

Write a program that computes the minimum required length
    for the rod, given a list of triangles!

Input

The input consists of a single test case. The first line
    contains one integer $N$
    ($0 < N \le 100$),
    denoting the number of triangles. The next $N$ lines each contain three integers
    $A, B, C$ denoting the
    lengths of the three sides of each triangle. The triangle will
    hang from the corner between sides $A$ and $B$. You are guaranteed that
    $A, B, C$ form a triangle
    that has an area that is strictly greater than zero.

Output

Output the required length $L$ such that all triangles can be
    hung from the rod, no matter how long or short each triangle’s
    string is. No triangle should swing beyond the rod’s ends. You
    may ignore the thickness of each ornament, the width of the
    string and you may assume that the string is attached exactly
    to the triangle’s end point.

Your answer should be accurate to within an absolute or
    relative error of $10^{-4}$.

Sample Input 1
Sample Output 1

2
3 3 3
4 4 5

8.0

Sample Input 2
Sample Output 2

2
3 3 3
4 5 4

6.843530573929037

Sample Input 3
Sample Output 3

3
7 20 14
7 14 20
14 20 7

20.721166413503266

question:
![image](1.png)A company makes triangle-shaped ornaments for the upcoming holidays. Each ornament is tied at one of its corners to a rod using a string of unknown length. Multiple of these ornaments may be attached to the same rod. These ornaments should be able to swing (rotate around the axis formed by the string) without interfering with each other.Write a program that computes the minimum required length for the rod, given a list of triangles!

Input
The input consists of a single test case. The first line contains one integer$N$($0 < N \le 100$), denoting the number of triangles. The next$N$lines each contain three integers$A, B, C$denoting the lengths of the three sides of each triangle. The triangle will hang from the corner between sides$A$and$B$. You are guaranteed that$A, B, C$form a triangle that has an area that is strictly greater than zero.

Output
Output the required length$L$such that all triangles can be hung from the rod, no matter how long or short each triangle’s string is. No triangle should swing beyond the rod’s ends. You may ignore the thickness of each ornament, the width of the string and you may assume that the string is attached exactly to the triangle’s end point.
Your answer should be accurate to within an absolute or relative error of$10^{-4}$.
Sample Input 1
2
3 3 3
4 4 5

Sample Output 1
8.0

Sample Input 2
2
3 3 3
4 5 4

Sample Output 2
6.843530573929037

Sample Input 3
3
7 20 14
7 14 20
14 20 7

Sample Output 3
20.721166413503266

data_split: test


Tournament

source: Ritsumeikan University Programming Contest 2017, Ritsumeikan University Competitive Programming Camp 2017

raw_problem:
A: トーナメント

問題

 AOR イカちゃんとあなたは、トーナメント形式の卓球大会シングルスの部に偵察に来た。
全ての試合を録画したい AOR イカちゃんのために、あなたはこの大会で行われる試合数を求めてあげることにした。

この大会には $N$ 人の選手が参加しており、それぞれ $0, \dots , N - 1$ の背番号を持っている。
そのうち、 $M$ 人の選手が棄権し、試合には出場しなかった。

この大会の試合数は、以下のルールに基いて決定される。

シード選手は存在せず、任意の出場者が優勝するために必要な勝利回数は一定である。

対戦相手が不在の場合は試合を行わず、出場した選手が勝利する。試合数にはカウントされない。

優勝者が決まった段階で大会は終了する。

一度試合に負けた人が再び試合をすることはない。つまり敗者復活戦や 3 位決定戦などは行わない。

なお、卓球台が 1 台しか無いため異なる試合が同時に行われることはなく、また各試合では必ず勝者が決まる (引き分けとなることはない)。

なお、トーナメントの定義は次のとおりである。
トーナメントは高さ $L = \log_2 N$ の完全二分木で表され、葉にあたる各頂点には参加者の背番号が書き込まれている。
根の深さを 0 とすると、 $i$ 回戦 ($1 \le i \le L$) では、
深さ $L - i$ の各頂点の子に書かれた番号の選手同士が試合を行い、その勝者の背番号をその頂点に書き込む。

制約

$2 \le N \le 2^8$

$0 \le M \le N - 1$

$0 \le a_i \le N - 1 \ (0 \le i \le M - 1)$

 $N$ は 2 の累乗である。

 $a_i \ (0 \le i \le M - 1)$ は相異なる

入力形式

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

$N \ M$

$a_1$

$\vdots$

$a_M$

1 行目には、参加者を表す整数 $N$ 、参加者のうち棄権した者の人数を表す整数 $M$ が与えられる。

続く $M$ 行には、棄権して出場しなかった選手の番号を表す整数 $a_i$ が与えられる。

出力

この大会が終了するまでに行われる試合数を 1 行で出力せよ。また、末尾に改行も出力せよ。

サンプル

サンプル入力 1

2 0

サンプル出力 1

1

最初の試合で優勝者が決まる。

サンプル入力 2

4 2
2
3

サンプル出力 2

1

solutions: ["# AOJ 2805: Tournament\n# Python3 2018.7.11 bal4u\n\nN, M = map(int, input().split())\nprint(N-1-M)\n\n", "def main():\n    N,M=map(int,input().split())\n    a = [ int(input()) for _ in [0]*M ]\n    print(N-len(a)-1)\n\nif __name__ == \"__main__\":\n    main()\n", "n, m = map(int, input().split())\nP = [True for _ in range(n)]\nfor _ in range(m):\n    a = int(input())\n    P[a] = False\nans = 0\nwhile n > 1:\n    nn = n // 2\n    NP = [True for _ in range(nn)]\n    for i in range(0, n, 2):\n        if P[i] and P[i + 1]:\n            ans += 1\n            NP[i // 2] = True\n        elif P[i] or P[i + 1]:\n            NP[i // 2] = True\n        else:\n            NP[i // 2] = False\n    n = nn\n    P = NP[:]\nprint(ans)\n\n", "n,m=map(int,input().split())\nprint(n-m-1)\n", "n, m = map(int, input().split())\n[input() for _ in range(m)]\nprint(n - m - 1)\n", "n,m = map(int, input().split())\nprint (n - m - 1)\nfor i in range(m):\n a = input()\n", "N, M = map(int, input().split())\na = []\nfor i in range(M):\n    a.append(int(input()))\nnum = N - M\nans = 0\nwhile(num):\n    ans += 1\n    num -= 1\nprint(ans - 1)\n", "n,m=map(int,input().split())\nfor _ in [0]*m:input()\nprint(n-m-1)\n", "import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time\n\nsys.setrecursionlimit(10**7)\ninf = 10**20\nmod = 10**9 + 7\n\ndef LI(): return list(map(int, input().split()))\ndef LF(): return list(map(float, input().split()))\ndef II(): return int(input())\ndef LS(): return input().split()\ndef S(): return input()\n\n\ndef main():\n    n,m = LI()\n    return n-m-1\n\nprint(main())\n", "n,m=map(int,input().split())\nprint(n-m-1)\n", "n, m = map(int, input().split())\nfor _ in range(m):\n    tmp = input()\n\nprint(n-m-1)\n\n", "N,M = map(int,input().split())\nprint(N-1-M)\n", "N, M = map(int, input().split())\nprint(N - M - 1)\n", "n, m = map(int, input().split())\nans = n - m - 1\nprint(ans)\n", "n, m = map(int, input().split())\nfor i in range(m):\n    input()\nprint(n-1-m)\n", "n, m = map(int, input().split(' '))\n\nns = [i for i in range(n)]\n\nfor i in range(m):\n  ha = int(input())\n  ns[ha] = None\n\n#print(n, m)\n#print(ns)\n\ncount = 0\nwhile True:\n  size = len(ns)\n  ns2 = []\n  for j in range(0, size, 2):\n    flag = ns[j] is not None and ns[j+1] is not None\n    if flag:\n      ns2.append( 0 )\n      count += 1\n    elif ns[j] is not None or ns[j+1] is not None:\n      ns2.append( 0 )\n    else:\n      ns2.append( None)\n  #print(ns2)\n  ns = ns2\n  if len(ns) == 1:\n    break\nprint(count)\n", "a = input().split(' ')\ntour = int(a[0])-1\nno_vs = 0\n\nif int(a[1]) != 0:\n    absent = []\n    for _ in range(int(a[1])):\n        absent.append(int(input()))\n    num = int(int(a[0])/2)\n    while absent != []:\n        next_absent = []\n        for n in range(num):\n            if 2*n in absent or 2*n+1 in absent:\n                no_vs+=1\n                if 2*n in absent and 2*n+1 in absent:\n                    next_absent.append(n)\n        absent = next_absent\n        num = int(num/2)\n            \nprint(tour-no_vs)\n        \n", "N,M = map(int, input().split())\nl = []\nfor i in range(M):\n    l.append(int(input()))\n\ncount = N - 1 - M\nprint(count)\n"]

source: aizu

question:
A: Tournament
Problem

AOR Ika-chan and you have come to scout a singles tournament-style table tennis championship.
To help AOR Ika-chan, who wants to record all the matches, you decided to calculate the number of matches that will be held in this tournament.

There are $N$ players participating in this tournament, each with a number from $0, \dots, N - 1$.
Out of them, $M$ players have withdrawn and did not participate in the matches.

The number of matches in this tournament is determined based on the following rules:

- There are no seeded players, and the number of wins required for any contestant to be victorious is constant.
- If an opponent is absent, no match is played, and the attending player is declared the winner. These are not counted in the number of matches.
- The tournament ends once the winner is decided.
- A player who loses a match does not play again. There are no revival matches nor matches to determine third place, etc.
- Furthermore, since there is only one table tennis table, different matches do not occur simultaneously, and each match always results in a winner (there are no ties).

Additionally, the definition of the tournament is as follows:
The tournament is represented by a perfect binary tree of height $L = \log_2 N$, with the participant numbers written at each vertex corresponding to the leaves.
If we consider the root to have a depth of 0, in the $i$th round ($1 \le i \le L$),
players with numbers written on a vertex’s children at depth $L - i$ compete, and the winner’s number is written on that vertex.

![image](1.png)
Constraints

- $2 \le N \le 2^8$
- $0 \le M \le N - 1$
- $0 \le a_i \le N - 1 \ (0 \le i \le M - 1)$
- $N$ is a power of 2.
- $a_i \ (0 \le i \le M - 1)$ are all distinct

Input Format

The input is given in the following format.

$N \ M$
$a_1$
$\vdots$
$a_M$

- On the first line, integers $N$ representing the participants and integer $M$ representing the number of participants who have withdrawn are given.
- The following $M$ lines contain integer $a_i$ representing the numbers of the players who withdrew and did not participate.

Output

Print the number of matches that will be held until the tournament ends on one line. Also, output a newline at the end.

Sample
Sample Input 1

2 0

Sample Output 1

1

The winner is decided in the first match.

Sample Input 2

4 2
2
3

Sample Output 2

1

data_split: test