Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
整数 a, b, c, d が与えられるので、以下の指示に従って 2 行出力してください。
1 行目は (a + b) \times (c - d) の計算結果を整数として出力してください。
2 行目は入力にかかわらず Takahashi と出力してください。
制約
- -100 \leq a, b, c, d \leq 100
- a,b,c,d は整数
入力
入力は以下の形式で標準入力から与えられる。
a b c d
出力
問題文の指示に従って 2 行出力せよ。
入力例 1
1 2 5 3
出力例 1
6 Takahashi
(1 + 2) \times(5 - 3) = 3 \times 2 = 6 です。よって 1 行目は 6 を出力します。
2 行目は Takahashi を出力します。1 文字目を小文字にしたりスペルを誤ったりすると誤答となるので注意してください。
入力例 2
10 -20 30 -40
出力例 2
-700 Takahashi
入出力に負の数が含まれる場合もあります。
入力例 3
100 100 100 -100
出力例 3
40000 Takahashi
Score : 100 points
Problem Statement
You are given integers a, b, c, and d. Print two lines as follows.
The first line should contain the result of calculating (a + b) \times (c - d) as an integer.
The second line should contain Takahashi, regardless of the input.
Constraints
- -100 \leq a, b, c, d \leq 100
- a, b, c, and d are integers.
Input
The input is given from Standard Input in the following format:
a b c d
Output
Print two lines according to the Problem Statement.
Sample Input 1
1 2 5 3
Sample Output 1
6 Takahashi
We have (1 + 2) \times(5 - 3) = 3 \times 2 = 6, so the first line should contain 6.
The second line should contain Takahashi. Lowercasing the first character or incorrect spelling will not be accepted, so be careful.
Sample Input 2
10 -20 30 -40
Sample Output 2
-700 Takahashi
The input or output may contain negative numbers.
Sample Input 3
100 100 100 -100
Sample Output 3
40000 Takahashi
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
高橋君は、毎日 S 時 0 分に部屋の電気をつけ、毎日 T 時 0 分に消します。
電気をつけている間に日付が変わることもあります。
X 時 30 分に部屋の電気がついているかどうか判定してください。
制約
- 0 \leq S, T, X \leq 23
- S \neq T
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
S T X
出力
X 時 30 分に部屋の電気がついているならば Yes と、そうでなければ No と出力せよ。
入力例 1
7 20 12
出力例 1
Yes
部屋の電気がついているのは 7 時 0 分から 20 時 0 分までの間です。12 時 30 分には電気がついているので、Yes と出力します。
入力例 2
20 7 12
出力例 2
No
部屋の電気がついているのは 0 時 0 分から 7 時 0 分までの間と、20 時 0 分から（次の日の）0 時 0 分までの間です。
12 時 30 分には電気がついていないので、No と出力します。
入力例 3
23 0 23
出力例 3
Yes
Score : 100 points
Problem Statement
Takahashi turns on the light of his room at S o'clock (on the 24-hour clock) every day and turns it off at T o'clock every day.
The date may change while the light is on.
Determine whether the light is on at 30 minutes past X o'clock.
Constraints
- 0 \leq S, T, X \leq 23
- S \neq T
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
S T X
Output
If the light is on at 30 minutes past X o'clock, print Yes; otherwise, print No.
Sample Input 1
7 20 12
Sample Output 1
Yes
The light is on between 7 o'clock and 20 o'clock. At 30 minutes past 12 o'clock, it is on, so we print Yes.
Sample Input 2
20 7 12
Sample Output 2
No
The light is on between 0 o'clock and 7 o'clock, and between 20 o'clock and 0 o'clock (on the next day). At 30 minutes past 12 o'clock, it is off, so we print No.
Sample Input 3
23 0 23
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
長さ N の正整数列 a = (a_1, a_2, \dots, a_N) には何種類の整数が現れますか？
制約
- 1 \leq N \leq 1000
- 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N
出力
答えを出力せよ。
入力例 1
6 1 4 1 2 2 1
出力例 1
3
1, 2, 4 の 3 種類の整数が現れます。
入力例 2
1 1
出力例 2
1
入力例 3
11 3 1 4 1 5 9 2 6 5 3 5
出力例 3
7
Score : 200 points
Problem Statement
In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?
Constraints
- 1 \leq N \leq 1000
- 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 \ldots a_N
Output
Print the answer.
Sample Input 1
6 1 4 1 2 2 1
Sample Output 1
3
There are three different integers: 1, 2, 4.
Sample Input 2
1 1
Sample Output 2
1
Sample Input 3
11 3 1 4 1 5 9 2 6 5 3 5
Sample Output 3
7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
東西に無限に伸びる道路があり、この道路上のある基準となる地点から東に x\mathrm{\,m} のところにある地点の座標は x と定められています。 特に、基準となる地点から西に x\mathrm{\,m} のところにある地点の座標は -x です。
すぬけ君は今から、座標が A である地点を基点にして M\mathrm{\,m} おきにクリスマスツリーを立てます。 すなわち、座標がある整数 k を用いて A+kM と表されるような地点それぞれにクリスマスツリーを立てます。
高橋君と青木君はそれぞれ座標が L,R\ (L\leq R) である地点に立っています。 高橋君と青木君の間（高橋君と青木君が立っている地点を含む）に立てられるクリスマスツリーの本数を求めてください。
制約
- -10^{18}\leq A \leq 10^{18}
- 1\leq M \leq 10^9
- -10^{18}\leq L\leq R \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A M L R
出力
高橋君と青木君の間（高橋君と青木君が立っている地点を含む）に立てられるクリスマスツリーの本数を出力せよ。
入力例 1
5 3 -1 6
出力例 1
3
すぬけ君は、座標が \dots,-4,-1,2,5,8,11,14\dots である地点にクリスマスツリーを立てます。 これらのうち高橋君と青木君の間にあるのは、座標が -1,2,5 である地点に立てられる 3 本です。
入力例 2
-2 2 1 1
出力例 2
0
高橋君と青木君が同じ地点に立っていることもあります。
入力例 3
-177018739841739480 2436426 -80154573737296504 585335723211047198
出力例 3
273142010859
Score : 250 points
Problem Statement
There is a road that stretches infinitely to the east and west, and the coordinate of a point located x meters to the east from a certain reference point on this road is defined as x. In particular, the coordinate of a point located x meters to the west from the reference point is -x.
Snuke will set up Christmas trees at points on the road at intervals of M meters, starting from a point with coordinate A. In other words, he will set up a Christmas tree at each point that can be expressed as A+kM using some integer k.
Takahashi and Aoki are standing at points with coordinates L and R (L\leq R), respectively. Find the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).
Constraints
- -10^{18}\leq A \leq 10^{18}
- 1\leq M \leq 10^9
- -10^{18}\leq L\leq R \leq 10^{18}
- All input values are integers.
Input
Input is given from Standard Input in the following format:
A M L R
Output
Print the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).
Sample Input 1
5 3 -1 6
Sample Output 1
3
Snuke will set up Christmas trees at points with coordinates \dots,-4,-1,2,5,8,11,14\dots. Three of them at coordinates -1, 2, and 5 are between Takahashi and Aoki.
Sample Input 2
-2 2 1 1
Sample Output 2
0
Sometimes, Takahashi and Aoki are standing at the same point.
Sample Input 3
-177018739841739480 2436426 -80154573737296504 585335723211047198
Sample Output 3
273142010859
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
英大文字からなる長さ 3 の文字列 T が、英小文字からなる文字列 S の 空港コード であるとは、 T が S から次のいずれかの方法により得られることとします。
- S の長さ 3 の（連続とは限らない）部分列をとり、それを英大文字に変換したものを T とする
- S の長さ 2 の（連続とは限らない）部分列をとり、それを英大文字に変換したものの末尾に
Xを追加したものを T とする
文字列 S, T が与えられるので、 T が S の空港コードであるか判定してください。
制約
- S は英小文字からなる長さ 3 以上 10^5 以下の文字列
- T は英大文字からなる長さ 3 の文字列
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
T が S の空港コードであるならば Yes を、そうでないならば No を出力せよ。
入力例 1
narita NRT
出力例 1
Yes
narita の部分列 nrt を英大文字に変換した文字列 NRT は、 narita の空港コードです。
入力例 2
losangeles LAX
出力例 2
Yes
losangeles の部分列 la を英大文字に変換した文字列 LA の末尾に X を追加したもの LAX は、 losangeles の空港コードです。
入力例 3
snuke RNG
出力例 3
No
Score: 300 points
Problem Statement
A string T of length 3 consisting of uppercase English letters is an airport code for a string S of lowercase English letters if and only if T can be derived from S by one of the following methods:
- Take a subsequence of length 3 from S (not necessarily contiguous) and convert it to uppercase letters to form T.
- Take a subsequence of length 2 from S (not necessarily contiguous), convert it to uppercase letters, and append
Xto the end to form T.
Given strings S and T, determine if T is an airport code for S.
Constraints
- S is a string of lowercase English letters with a length between 3 and 10^5, inclusive.
- T is a string of uppercase English letters with a length of 3.
Input
The input is given from Standard Input in the following format:
S T
Output
Print Yes if T is an airport code for S, and No otherwise.
Sample Input 1
narita NRT
Sample Output 1
Yes
The subsequence nrt of narita, when converted to uppercase, forms the string NRT, which is an airport code for narita.
Sample Input 2
losangeles LAX
Sample Output 2
Yes
The subsequence la of losangeles, when converted to uppercase and appended with X, forms the string LAX, which is an airport code for losangeles.
Sample Input 3
snuke RNG
Sample Output 3
No
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
N 行 N 列のグリッドが与えられます。ここで、N は偶数です。グリッドの上から i 行目、左から j 列目のマスをマス (i, j) と表記します。
グリッドの各マスは黒か白のいずれかで塗られており、A_{i, j} = # のときマス (i, j) は黒、A_{i, j} = . のときマス (i, j) は白で塗られています。
i = 1, 2, \ldots, \frac{N}{2} の順に以下の操作を行った後のグリッドの各マスの色を求めてください。
- i 以上 N + 1 - i 以下の整数 x, y について、マス (y, N + 1 - x) の色をマス (x, y) の色で置き換える。この置き換えは条件を満たすすべての整数 x, y について同時に行う。
制約
- N は 2 以上 3000 以下の偶数
- A_{i, j} は
#または.
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1, 1}A_{1, 2}\ldotsA_{1, N}
A_{2, 1}A_{2, 2}\ldotsA_{2, N}
\vdots
A_{N, 1}A_{N, 2}\ldotsA_{N, N}
出力
すべての操作を終えた後、マス (i, j) の色が黒であるとき B_{i, j} = #、マス (i, j) の色が白であるとき B_{i, j} = . として以下の形式で出力せよ。
B_{1, 1}B_{1, 2}\ldotsB_{1, N}
B_{2, 1}B_{2, 2}\ldotsB_{2, N}
\vdots
B_{N, 1}B_{N, 2}\ldotsB_{N, N}
入力例 1
8 .......# .......# .####..# .####..# .##....# .##....# .####### .#######
出力例 1
........ #######. #.....#. #.###.#. #.#...#. #.#####. #....... ########
操作によってグリッドの各マスの色は以下のように変化します。
.......# ........ ........ ........ ........ .......# ######.. #######. #######. #######. .####..# ######.. #....##. #.....#. #.....#. .####..# → ##..##.. → #....##. → #.##..#. → #.###.#. .##....# ##..##.. #..####. #.##..#. #.#...#. .##....# ##...... #..####. #.#####. #.#####. .####### ##...... #....... #....... #....... .####### ######## ######## ######## ########
入力例 2
6 .#.#.# ##.#.. ...### ###... ..#.## #.#.#.
出力例 2
#.#.#. .#.#.# #.#.#. .#.#.# #.#.#. .#.#.#
入力例 3
12 .......#.### #...#...#..# ###.#..##### ..#.#.#.#... .#.....#.### .......#.#.. #...#..#.... #####....... ...#...#.#.# ..###..#..## #..#.#.#.#.# .####.......
出力例 3
.#..##...##. #.#.#.#.#... ###.##..#... #.#.#.#.#... #.#.##...##. ............ ............ .###.###.### ...#...#.#.. .###...#.### ...#...#...# .###...#.###
Score : 400 points
Problem Statement
You are given a grid with N rows and N columns, where N is an even number. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
Each cell is painted black or white. If A_{i, j} = #, cell (i, j) is black; if A_{i, j} = ., it is white.
Find the color of each cell after performing the following operation for i = 1, 2, \ldots, \frac{N}{2} in this order.
- For all pairs of integers x, y between i and N + 1 - i, inclusive, replace the color of cell (y, N + 1 - x) with the color of cell (x, y). Perform these replacements simultaneously for all such pairs x, y.
Constraints
- N is an even number between 2 and 3000, inclusive.
- Each A_{i, j} is
#or..
Input
The input is given from Standard Input in the following format:
N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}
Output
After all operations, let B_{i, j} = # if cell (i, j) is black, and B_{i, j} = . if it is white. Print the grid in the following format:
B_{1,1}B_{1,2}\ldots B_{1,N}
B_{2,1}B_{2,2}\ldots B_{2,N}
\vdots
B_{N,1}B_{N,2}\ldots B_{N,N}
Sample Input 1
8 .......# .......# .####..# .####..# .##....# .##....# .####### .#######
Sample Output 1
........ #######. #.....#. #.###.#. #.#...#. #.#####. #....... ########
The operations change the colors of the grid cells as follows:
.......# ........ ........ ........ ........ .......# ######.. #######. #######. #######. .####..# ######.. #....##. #.....#. #.....#. .####..# → ##..##.. → #....##. → #.##..#. → #.###.#. .##....# ##..##.. #..####. #.##..#. #.#...#. .##....# ##...... #..####. #.#####. #.#####. .####### ##...... #....... #....... #....... .####### ######## ######## ######## ########
Sample Input 2
6 .#.#.# ##.#.. ...### ###... ..#.## #.#.#.
Sample Output 2
#.#.#. .#.#.# #.#.#. .#.#.# #.#.#. .#.#.#
Sample Input 3
12 .......#.### #...#...#..# ###.#..##### ..#.#.#.#... .#.....#.### .......#.#.. #...#..#.... #####....... ...#...#.#.# ..###..#..## #..#.#.#.#.# .####.......
Sample Output 3
.#..##...##. #.#.#.#.#... ###.##..#... #.#.#.#.#... #.#.##...##. ............ ............ .###.###.### ...#...#.#.. .###...#.### ...#...#...# .###...#.###
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
正整数 N に対して、N を N 個つなげた整数を V_N とします。
より厳密には、N を文字列とみなしたものを N 個連結し、
それを再度整数とみなしたものを V_N とします。
例えば、V_3=333, V_{10}=10101010101010101010 です。
V_N を 998244353 で割った余りを求めてください。
制約
- 1\leq N\leq 10^{18}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
V_N を 998244353 で割った余りを出力せよ。
入力例 1
5
出力例 1
55555
V_5=55555 を 998244353 で割った余りは 55555 です。
入力例 2
9
出力例 2
1755646
V_9=999999999 を 998244353 で割った余りは 1755646 です。
入力例 3
10000000000
出力例 3
468086693
入力が 32 bit 整数型に収まらない可能性があることに注意してください。
Score : 350 points
Problem Statement
For a positive integer N, let V_N be the integer formed by concatenating N exactly N times.
More precisely, consider N as a string, concatenate N copies of it, and treat the result as an integer to get V_N.
For example, V_3=333 and V_{10}=10101010101010101010.
Find the remainder when V_N is divided by 998244353.
Constraints
- 1 \leq N \leq 10^{18}
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the remainder when V_N is divided by 998244353.
Sample Input 1
5
Sample Output 1
55555
The remainder when V_5=55555 is divided by 998244353 is 55555.
Sample Input 2
9
Sample Output 2
1755646
The remainder when V_9=999999999 is divided by 998244353 is 1755646.
Sample Input 3
10000000000
Sample Output 3
468086693
Note that the input may not fit into a 32-bit integer type.
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
N 個の島と、2 つの島の間を双方向に結ぶ M 本の橋があり、
それぞれ島 1, 島 2, \ldots, 島 N および 橋 1, 橋 2, \ldots, 橋 M と番号づけられています。
橋 i は島 U_i と島 V_i を相互に結んでおり、どちらの方向に移動するにも T_i だけ時間がかかります。
ここで、橋の両端が同一の島であるような橋は存在しませんが、ある 2 つの島の間が 2 本以上の橋で直接繋がれている可能性はあります。
また、どの 2 つの島の間もいくつかの橋をわたって移動することができます。
Q 個の問題が与えられるので、各問題に対する答えを求めてください。i 番目の問題は次のようなものです。
相異なる K_i 本の橋、橋 B_{i,1}, 橋 B_{i,2}, \ldots, 橋 B_{i,K_i} が与えられます。
これらの橋をすべて 1 回以上わたり、島 1 から島 N まで移動するために必要な時間の最小値を求めてください。
ただし、島 1 から島 N までの移動において、橋をわたって島の間を移動するのにかかる時間以外は無視できるものとします。
また、与えられた橋はどの順で、またどの向きにわたってもかまいません。
制約
- 2\leq N \leq 400
- N-1\leq M \leq 2\times 10^5
- 1\leq U_i<V_i\leq N
- 1\leq T_i\leq 10^9
- 1\leq Q\leq 3000
- 1\leq K_i\leq 5
- 1\leq B_{i,1}<B_{i,2}<\cdots<B_{i,K_i}\leq M
- 入力はすべて整数
- どの 2 つの島の間もいくつかの橋をわたって移動することができる。
入力
入力は以下の形式で標準入力から与えられる。
N M
U_1 V_1 T_1
U_2 V_2 T_2
\vdots
U_M V_M T_M
Q
K_1
B_{1,1} B_{1,2} \cdots B_{1,{K_1}}
K_2
B_{2,1} B_{2,2} \cdots B_{2,{K_2}}
\vdots
K_Q
B_{Q,1} B_{Q,2} \cdots B_{Q,{K_Q}}
出力
Q 行出力せよ。i 行目（1\leq i\leq Q）には i 番目の問題に対する答えを整数で出力せよ。
入力例 1
3 5 1 2 10 1 3 20 1 3 30 2 3 15 2 3 25 2 1 1 2 3 5
出力例 1
25 70
1 番目の問題では橋 1 をわたった上で島 1 から島 3 へ移動するために必要な時間の最小値を求める必要があります。
橋 1 を使って島 1 から島 2 に移動した後に橋 4 を使って島 2 から島 3 に移動したとき時間は 10+15=25 だけかかり、このときが最小です。
よって、1 行目には 25 を出力します。
2 番目の問題では橋 3 および橋 5 をわたった上で島 1 から島 3 へ移動するために必要な時間の最小値を求める必要があります。
橋 3 を通って島 1 から島 3 に移動した後に橋 5 を使って島 2 へ移動し、橋 4 を使用して島 3 に移動したとき時間は 30+25+15=70 だけかかり、このときが最小です。よって、2 行目には 70 を出力します。
入力例 2
6 6 1 5 1 2 5 1 2 4 1 3 4 1 3 6 1 1 6 1 2 5 1 2 3 4 5 1 5
出力例 2
5 3
各問題において指定された橋をわたる際、わたる方向はどちらでも問題ありません。
入力例 3
5 5 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 1 5 1000000000 1 1 3
出力例 3
4000000000
答えが 32bit 整数型に収まらない可能性があることに注意してください。
Score : 450 points
Problem Statement
There are N islands and M bidirectional bridges connecting two islands. The islands and bridges are numbered 1, 2, \ldots, N and 1, 2, \ldots, M, respectively.
Bridge i connects islands U_i and V_i, and the time it takes to cross it in either direction is T_i.
No bridge connects an island to itself, but it is possible for two islands to be directly connected by more than one bridge.
One can travel between any two islands using some bridges.
You are given Q queries, so answer each of them. The i-th query is as follows:
You are given K_i distinct bridges: bridges B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}.
Find the minimum time required to travel from island 1 to island N using each of these bridges at least once.
Only consider the time spent crossing bridges.
You can cross the given bridges in any order and in any direction.
Constraints
- 2 \leq N \leq 400
- N-1 \leq M \leq 2 \times 10^5
- 1 \leq U_i < V_i \leq N
- 1 \leq T_i \leq 10^9
- 1 \leq Q \leq 3000
- 1 \leq K_i \leq 5
- 1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M
- All input values are integers.
- It is possible to travel between any two islands using some bridges.
Input
The input is given from Standard Input in the following format:
N M
U_1 V_1 T_1
U_2 V_2 T_2
\vdots
U_M V_M T_M
Q
K_1
B_{1,1} B_{1,2} \cdots B_{1,{K_1}}
K_2
B_{2,1} B_{2,2} \cdots B_{2,{K_2}}
\vdots
K_Q
B_{Q,1} B_{Q,2} \cdots B_{Q,{K_Q}}
Output
Print Q lines. The i-th line (1 \leq i \leq Q) should contain the answer to the i-th query as an integer.
Sample Input 1
3 5 1 2 10 1 3 20 1 3 30 2 3 15 2 3 25 2 1 1 2 3 5
Sample Output 1
25 70
For the first query, we need to find the minimum time to travel from island 1 to island 3 while using bridge 1. The minimum time is achieved by using bridge 1 to move from island 1 to island 2, then using bridge 4 to move from island 2 to island 3. The time taken is 10 + 15 = 25. Hence, print 25 on the first line.
For the second query, we need to find the minimum time to travel from island 1 to island 3 while using both bridges 3 and 5. The minimum time is achieved by using bridge 3 to move from island 1 to island 3, then using bridge 5 to move to island 2, and finally using bridge 4 to return to island 3. The time taken is 30 + 25 + 15 = 70. Hence, print 70 on the second line.
Sample Input 2
6 6 1 5 1 2 5 1 2 4 1 3 4 1 3 6 1 1 6 1 2 5 1 2 3 4 5 1 5
Sample Output 2
5 3
For each query, you can cross the specified bridges in either direction.
Sample Input 3
5 5 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 1 5 1000000000 1 1 3
Sample Output 3
4000000000
Beware that the answer may not fit in a 32-bit integer.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
スパイス屋には、スパイス 1 、スパイス 2、\ldots 、スパイス 2^N-1 の 2^N-1 種類のスパイスがそれぞれ 1 個ずつ売られています。 i = 1, 2, \ldots, 2^N-1 について、スパイス i の値段は c_i 円です。 高橋君はそれらを好きなだけ買うことができます。
高橋君は帰宅後、買ったスパイスのうち 1 つ以上を選び、それらを組み合わせてカレーを作る予定です。
高橋君がスパイス A_1 、スパイス A_2 、\ldots、スパイス A_k の k 個のスパイスを組み合わせると、完成するカレーの辛さは A_1 \oplus A_2 \oplus \cdots \oplus A_k になります。
ここで、\oplus はビットごとの排他的論理和を表します。
高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず 1 以上 2^N-1 以下の任意の整数の辛さのカレーを作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してください。
制約
- 2 \leq N \leq 16
- 1 \leq c_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
c_1 c_2 \ldots c_{2^N-1}
出力
高橋君が支払う金額としてあり得る最小値を出力せよ。
入力例 1
2 4 5 3
出力例 1
7
高橋君がスパイス 1 とスパイス 3 を買うと、下記の通り、1 以上 3 以下の任意の整数の辛さのカレーを作ることができます。
- 辛さ 1 のカレーを作るには、スパイス 1 のみを使い、
- 辛さ 2 のカレーを作るには、スパイス 1 とスパイス 3 を組み合わせ、
- 辛さ 3 のカレーを作るには、スパイス 3 のみを使えば良いです。
このとき高橋君が支払う金額は c_1 + c_3 = 4 + 3 = 7 円であり、これが高橋君が支払う金額としてあり得る最小値です。
入力例 2
4 9 7 9 7 10 4 3 9 4 8 10 5 6 3 8
出力例 2
15
Score : 500 points
Problem Statement
The shop supaisu-ya sells 2^N-1 kinds of spices: Spice 1, Spice 2, \ldots, Spice 2^N-1. One pack of each spice is in stock. For each i = 1, 2, \ldots, 2^N-1, Spice i costs c_i yen. Takahashi can buy any of these spices.
He plans to make curry after getting home by choosing one or more of the bought spices and mixing them.
If k spices, Spice A_1, Spice A_2, \ldots, Spice A_k, are mixed, the hotness of the resulting curry is A_1 \oplus A_2 \oplus \cdots \oplus A_k, where \oplus denotes the bitwise XOR.
Takahashi wants to decide the hotness of the curry based on his feeling after getting home. For now, he will buy a set of spices that allows him to make curry of any hotness from 1 through 2^N-1. Print the minimum possible amount of money Takahashi pays.
Constraints
- 2 \leq N \leq 16
- 1 \leq c_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
c_1 c_2 \ldots c_{2^N-1}
Output
Print the minimum possible amount of money Takahashi pays.
Sample Input 1
2 4 5 3
Sample Output 1
7
If Takahashi buys Spice 1 and 3, he can make curry of any hotness from 1 through 3, as follows.
- To make curry of hotness 1, use just Spice 1.
- To make curry of hotness 2, mix Spice 1 and Spice 3.
- To make curry of hotness 3, use just Spice 3.
Here, Takahashi pays c_1 + c_3 = 4 + 3 = 7 yen, which is the minimum possible amount he pays.
Sample Input 2
4 9 7 9 7 10 4 3 9 4 8 10 5 6 3 8
Sample Output 2
15