実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
与えられる 5 つの整数 A, B, C, D, E の中に何種類の整数があるかを出力してください。
制約
- 0 \leq A, B, C, D, E \leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
A B C D E
出力
答えを出力せよ。
入力例 1
31 9 24 31 24
出力例 1
3
与えられる 5 つの整数 31, 9, 24, 31, 24 の中には、9, 24, 31 という 3 種類の整数があります。 よって、3 を出力します。
入力例 2
0 0 0 0 0
出力例 2
1
Score : 100 points
Problem Statement
Print how many distinct integers there are in given five integers A, B, C, D, and E.
Constraints
- 0 \leq A, B, C, D, E \leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B C D E
Output
Print the answer.
Sample Input 1
31 9 24 31 24
Sample Output 1
3
In the given five integers 31, 9, 24, 31, and 24, there are three distinct integers 9, 24, and 31. Thus, 3 should be printed.
Sample Input 2
0 0 0 0 0
Sample Output 2
1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
現在 AtCoder で開催されている AtCoder Regular Contest (ARC) には、Div. 1 と Div. 2 の 2 種類が存在します。 ARC Div. 1 では レーティング が 1600 以上 2999 以下の人が、ARC Div. 2 ではレーティングが 1200 以上 2399 以下の人がそれぞれ Rated 対象 となります。
正整数 R, X が与えられます。
レーティングが R の人は ARC Div. X において Rated 対象ですか?
制約
- 1\leq R \leq 4229
- 1\leq X \leq 2
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
R X
出力
レーティングが R の人が ARC Div. X において Rated 対象ならば Yes を、そうでないならば No を出力せよ。
入力例 1
2000 1
出力例 1
Yes
2000 は 1600 以上 2999 以下であるため、レーティングが 2000 の人は ARC Div. 1 において Rated 対象です。
入力例 2
1000 1
出力例 2
No
1000 は 1600 未満であるため、レーティングが 1000 の人は ARC Div. 1 において Rated 対象ではありません。
入力例 3
1500 2
出力例 3
Yes
1500 は 1200 以上 2399 以下であるため、レーティングが 1500 の人は ARC Div. 2 において Rated 対象です。
入力例 4
2800 2
出力例 4
No
2800 は 2399 より大きいため、レーティングが 2800 の人は ARC Div. 2 において Rated 対象ではありません。
Score : 100 points
Problem Statement
AtCoder Regular Contest (ARC) currently has two divisions: Div. 1 and Div. 2. In ARC Div. 1, participants whose rating is between 1600 and 2999, inclusive, are rated. In ARC Div. 2, participants whose rating is between 1200 and 2399, inclusive, are rated.
You are given positive integers R and X.
Determine whether a person with rating R is rated in ARC Div. X.
Constraints
- 1 \le R \le 4229
- 1 \le X \le 2
- All input values are integers.
Input
The input is given from Standard Input in the following format:
R X
Output
If a person with rating R is rated in ARC Div. X, output Yes; otherwise, output No.
Sample Input 1
2000 1
Sample Output 1
Yes
Because 2000 lies between 1600 and 2999, a person with rating 2000 is rated in ARC Div. 1.
Sample Input 2
1000 1
Sample Output 2
No
Because 1000 is less than 1600, a person with rating 1000 is not rated in ARC Div. 1.
Sample Input 3
1500 2
Sample Output 3
Yes
Because 1500 lies between 1200 and 2399, a person with rating 1500 is rated in ARC Div. 2.
Sample Input 4
2800 2
Sample Output 4
No
Because 2800 exceeds 2399, a person with rating 2800 is not rated in ARC Div. 2.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N + 1 個の部屋が一列に並んでおり、順に 0, 1, \ldots, N の番号が付けられています。
部屋の間には N 個のドアがあり、1, 2, \ldots, N の番号が付けられています。ドア i は部屋 i - 1 と部屋 i の間にあります。
各ドアについて鍵の状態を表す値 L_i が与えられ、L_i = 0 のときドア i の鍵は開いており、L_i = 1 のときドア i の鍵は閉まっています。
2 人の人がおり、1 人は部屋 0 に、もう 1 人は部屋 N にいます。それぞれの人は、ドア i の鍵が開いているときに限り、部屋 i - 1 と部屋 i の間を移動することができます。
このとき、2 人のいずれも到達できない部屋の個数を求めてください。
制約
- 2 \leq N \leq 100
- L_i \in \lbrace 0, 1 \rbrace
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N L_1 L_2 \ldots L_N
出力
答えを出力せよ。
入力例 1
5 0 1 0 0 1
出力例 1
3
2 人のいずれも到達できない部屋は部屋 2, 3, 4 の 3 つです。
入力例 2
3 1 0 1
出力例 2
2
入力例 3
8 0 0 1 1 0 1 0 0
出力例 3
3
Score : 200 points
Problem Statement
There are N + 1 rooms arranged in a line, numbered 0, 1, \ldots, N in order.
Between the rooms, there are N doors numbered 1, 2, \ldots, N. Door i is between rooms i - 1 and i.
For each door, a value L_i representing the lock state is given. When L_i = 0, door i is unlocked, and when L_i = 1, door i is locked.
There are two people, one in room 0 and the other in room N. Each person can move between rooms i - 1 and i only when door i is unlocked.
Find the number of rooms that neither of the two people can reach.
Constraints
- 2 \leq N \leq 100
- L_i \in \lbrace 0, 1 \rbrace
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N L_1 L_2 \ldots L_N
Output
Output the answer.
Sample Input 1
5 0 1 0 0 1
Sample Output 1
3
The rooms that neither of the two people can reach are rooms 2, 3, 4, which is 3 rooms.
Sample Input 2
3 1 0 1
Sample Output 2
2
Sample Input 3
8 0 0 1 1 0 1 0 0
Sample Output 3
3
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
AtCoder では現在、 ABC , ARC , AGC , AHC の 4 つのコンテストが定期的に開催されています。
AtCoder で現在定期的に開催されているコンテストは S_1 , S_2 , S_3 とあと 1 つは何ですか?
制約
- S_1 , S_2 , S_3 はそれぞれ、
ABC,ARC,AGC,AHCのいずれかである。 - S_1 , S_2 , S_3 は相異なる。
入力
入力は以下の形式で標準入力から与えられる。
S_1 S_2 S_3
出力
答えを出力せよ。
入力例 1
ARC AGC AHC
出力例 1
ABC
ARC , AGC , AHC の 3つが入力として与えられているので、
残りの 1 つはABC です。
入力例 2
AGC ABC ARC
出力例 2
AHC
Score : 200 points
Problem Statement
AtCoder currently holds four series of regular contests: ABC, ARC, AGC, and AHC.
What is the series of regular contests currently held by AtCoder in addition to S_1, S_2, and S_3?
Constraints
- Each of S_1, S_2, and S_3 is
ABC,ARC,AGC, orAHC. - S_1, S_2, and S_3 are pairwise different.
Input
Input is given from Standard Input in the following format:
S_1 S_2 S_3
Output
Print the answer.
Sample Input 1
ARC AGC AHC
Sample Output 1
ABC
Given in input are ARC, AGC, and AHC. The rest is ABC.
Sample Input 2
AGC ABC ARC
Sample Output 2
AHC
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) および正整数 K が与えられます。
1 以上 K 以下の整数のうち、A の中に一度も現れないものの総和を求めてください。
制約
- 1\leq N \leq 2\times 10^5
- 1\leq K \leq 2\times 10^9
- 1\leq A_i \leq 2\times 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
4 5 1 6 3 1
出力例 1
11
1 以上 5 以下の整数のうち、A の中に一度も現れないものは 2,4,5 の 3 つです。
よって、それらの総和である 2+4+5=11 を出力します。
入力例 2
1 3 346
出力例 2
6
入力例 3
10 158260522 877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739
出力例 3
12523196466007058
Score: 250 points
Problem Statement
You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a positive integer K.
Find the sum of the integers between 1 and K, inclusive, that do not appear in the sequence A.
Constraints
- 1\leq N \leq 2\times 10^5
- 1\leq K \leq 2\times 10^9
- 1\leq A_i \leq 2\times 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
4 5 1 6 3 1
Sample Output 1
11
Among the integers between 1 and 5, three numbers, 2, 4, and 5, do not appear in A.
Thus, print their sum: 2+4+5=11.
Sample Input 2
1 3 346
Sample Output 2
6
Sample Input 3
10 158260522 877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739
Sample Output 3
12523196466007058
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
数字からなる文字列 S が与えられます。
以下の条件を全て満たす文字列 T を 1122文字列 と呼びます。(定義は F 問題と同じです。)
- T は数字からなる空でない文字列
- |T| は偶数。ここで、 |T| は文字列 T の長さを表す
- T の 1 文字目から \frac{|T|}2 文字目までは全て同じ数字である
- T の \frac{|T|}2+1 文字目から |T| 文字目までは全て同じ数字である
- T の 1 文字目の数字に 1 を足すと |T| 文字目の数字になる
例えば 1122 や 01 、 444555 などは 1122文字列 ですが、 1222 や 90 は 1122文字列 ではありません。
S の 部分文字列 であって 1122文字列 であるものの個数を求めてください。
ただし、ある二つの部分文字列が文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えるものとします。
制約
- S は長さ 1 以上 10^6 以下の数字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の空でない部分文字列であって 1122文字列 であるものの個数を出力せよ。
入力例 1
1122
出力例 1
2
以下の 2 つの部分文字列が条件を満たします。
- S の 2 文字目から 3 文字目を取り出した
12 - S の 1 文字目から 4 文字目を取り出した
1122
したがって、 2 を出力してください。
入力例 2
7788788
出力例 2
3
文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えることに注意してください。
入力例 3
2025
出力例 3
0
1122文字列 となる部分文字列が存在しない場合もあります。
入力例 4
1112222334445556555
出力例 4
11
Score : 300 points
Problem Statement
You are given a string S consisting of digits.
A string T is called a 1122-string if it satisfies all of the following conditions. (The definition is the same as in Problem F.)
- T is a non-empty string consisting of digits.
- |T| is even, where |T| denotes the length of string T.
- All characters from the 1-st through the \frac{|T|}2-th character of T are the same digit.
- All characters from the (\frac{|T|}2+1)-th through the |T|-th character of T are the same digit.
- Adding 1 to the digit of the 1-st character of T gives the digit of the |T|-th character.
For example, 1122, 01, and 444555 are 1122-strings, but 1222 and 90 are not 1122-strings.
Find the number of substrings of S that are 1122-strings.
Two substrings are counted separately if they are extracted from different positions, even if they are identical as strings.
Constraints
- S is a string consisting of digits with length between 1 and 10^6, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Output the number of non-empty substrings of S that are 1122-strings.
Sample Input 1
1122
Sample Output 1
2
The following two substrings satisfy the condition.
12extracted from the 2-nd through 3-rd characters of S1122extracted from the 1-st through 4-th characters of S
Thus, output 2.
Sample Input 2
7788788
Sample Output 2
3
Note that two substrings are counted separately if they are extracted from different positions, even if they are identical as strings.
Sample Input 3
2025
Sample Output 3
0
There may be no substring that is a 1122-string.
Sample Input 4
1112222334445556555
Sample Output 4
11
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
頂点 1,2,\dots,N の N 頂点からなる木が与えられます。この木の辺のうち i 本目は頂点 U_i と頂点 V_i を結びます。
頂点 i には整数 A_i が書かれています。
全ての k=1,2,\dots,N について以下の問題に答えてください。
- 問題: 頂点 1 から頂点 k への単純なパス (同じ頂点を複数回通らないパス) に含まれる頂点について、同じ整数の書かれた異なる 2 頂点の組が存在すれば
Yes、そうでないならNoと答えよ。- なお、木上の 2 つの頂点を結ぶ単純なパスが一意に定まることは証明できる。
制約
- 入力は全て整数
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 1 \le U_i, V_i \le N
- 与えられるグラフは木
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \dots A_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
出力
N 行出力せよ。
そのうち i 行目には、 k=i である場合の問題の答えを出力せよ。
入力例 1
5 1 3 2 1 2 1 2 1 3 3 4 3 5
出力例 1
No No No Yes Yes
- k=1 について、頂点 1 から頂点 1 へのパスに含まれるのは頂点 1 です。パスが 1 頂点のみで構成されるので、答えは
Noとなります。 - k=2 について、頂点 1 から頂点 2 へのパスに含まれるのは頂点 1,2 で、それぞれに書かれた整数は 1,3 です。よって、答えは
Noです。 - k=3 について、頂点 1 から頂点 3 へのパスに含まれるのは頂点 1,3 で、それぞれに書かれた整数は 1,2 です。よって、答えは
Noです。 - k=4 について、頂点 1 から頂点 4 へのパスに含まれるのは頂点 1,3,4 で、それぞれに書かれた整数は 1,2,1 です。パス内の頂点 1,4 に同じ整数 1 が書かれているので、答えは
Yesです。 - k=5 について、頂点 1 から頂点 5 へのパスに含まれるのは頂点 1,3,5 で、それぞれに書かれた整数は 1,2,2 です。パス内の頂点 3,5 に同じ整数 2 が書かれているので、答えは
Yesです。
入力例 2
2 1000000000 1000000000 2 1
出力例 2
No Yes
入力例 3
10 10 7 3 9 1 3 8 5 7 10 3 6 8 6 6 1 9 7 7 10 5 4 4 2 10 2 1 9
出力例 3
No Yes Yes Yes Yes No No No No Yes
Score : 400 points
Problem Statement
You are given a tree with N vertices numbered 1,2,\dots,N. The i-th edge connects vertices U_i and V_i.
Each vertex i has an integer A_i written on it.
Answer the following problem for all k=1,2,\dots,N.
- Problem: Among the vertices on the simple path (a path that does not visit the same vertex more than once) from vertex 1 to vertex k, if there exist two distinct vertices with the same integer written on them, output
Yes; otherwise, outputNo.- It can be proved that the simple path connecting two vertices on a tree is unique.
Constraints
- All input values are integers.
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 1 \le U_i, V_i \le N
- The given graph is a tree.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \dots A_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
Output
Output N lines.
The i-th line should contain the answer to the problem for k=i.
Sample Input 1
5 1 3 2 1 2 1 2 1 3 3 4 3 5
Sample Output 1
No No No Yes Yes
- For k=1: the path from vertex 1 to vertex 1 contains only vertex 1. Since the path consists of only one vertex, the answer is
No. - For k=2: the path from vertex 1 to vertex 2 contains vertices 1,2, with integers 1,3 written on them respectively. Thus, the answer is
No. - For k=3: the path from vertex 1 to vertex 3 contains vertices 1,3, with integers 1,2 written on them respectively. Thus, the answer is
No. - For k=4: the path from vertex 1 to vertex 4 contains vertices 1,3,4, with integers 1,2,1 written on them respectively. Since vertices 1 and 4 on the path have the same integer 1 written on them, the answer is
Yes. - For k=5: the path from vertex 1 to vertex 5 contains vertices 1,3,5, with integers 1,2,2 written on them respectively. Since vertices 3 and 5 on the path have the same integer 2 written on them, the answer is
Yes.
Sample Input 2
2 1000000000 1000000000 2 1
Sample Output 2
No Yes
Sample Input 3
10 10 7 3 9 1 3 8 5 7 10 3 6 8 6 6 1 9 7 7 10 5 4 4 2 10 2 1 9
Sample Output 3
No Yes Yes Yes Yes No No No No Yes
実行時間制限: 4 sec / メモリ制限: 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.
実行時間制限: 2 sec / メモリ制限: 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