Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
あなたは3Dゲームの当たり判定を実装しようとしています。
3 次元空間内の直方体であって、2 点 (a,b,c),(d,e,f) を結ぶ線分を対角線とし、全ての面が xy 平面、yz 平面、zx 平面のいずれかに平行なものを C(a,b,c,d,e,f) と表します。
(この定義により C(a,b,c,d,e,f) は一意に定まります)
2 つの直方体 C(a,b,c,d,e,f) と C(g,h,i,j,k,l) が与えられるので、これらの共通部分の体積が正かどうか判定してください。
制約
- 0 \leq a < d \leq 1000
- 0 \leq b < e \leq 1000
- 0 \leq c < f \leq 1000
- 0 \leq g < j \leq 1000
- 0 \leq h < k \leq 1000
- 0 \leq i < l \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
a b c d e f g h i j k l
出力
2 つの直方体の共通部分の体積が正なら Yes、そうでなければ No を出力せよ。
入力例 1
0 0 0 4 5 6 2 3 4 5 6 7
出力例 1
Yes
2 つの直方体の位置関係は下図のようになっており、共通部分の体積は 8 です。

入力例 2
0 0 0 2 2 2 0 0 2 2 2 4
出力例 2
No
2 つの直方体は面で接していますが、共通部分の体積は 0 です。
入力例 3
0 0 0 1000 1000 1000 10 10 10 100 100 100
出力例 3
Yes
Score : 250 points
Problem Statement
You are trying to implement collision detection in a 3D game.
In a 3-dimensional space, let C(a,b,c,d,e,f) denote the cuboid with a diagonal connecting (a,b,c) and (d,e,f), and with all faces parallel to the xy-plane, yz-plane, or zx-plane.
(This definition uniquely determines C(a,b,c,d,e,f).)
Given two cuboids C(a,b,c,d,e,f) and C(g,h,i,j,k,l), determine whether their intersection has a positive volume.
Constraints
- 0 \leq a < d \leq 1000
- 0 \leq b < e \leq 1000
- 0 \leq c < f \leq 1000
- 0 \leq g < j \leq 1000
- 0 \leq h < k \leq 1000
- 0 \leq i < l \leq 1000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
a b c d e f g h i j k l
Output
Print Yes if the intersection of the two cuboids has a positive volume, and No otherwise.
Sample Input 1
0 0 0 4 5 6 2 3 4 5 6 7
Sample Output 1
Yes
The positional relationship of the two cuboids is shown in the figure below, and their intersection has a volume of 8.

Sample Input 2
0 0 0 2 2 2 0 0 2 2 2 4
Sample Output 2
No
The two cuboids touch at a face, where the volume of the intersection is 0.
Sample Input 3
0 0 0 1000 1000 1000 10 10 10 100 100 100
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
チェス盤のどこにコマが置かれているか答えてください。
縦 8 マス、横 8 マスのグリッドがあります。グリッドの各マスには、次のルールで定められる長さ 2 の文字列の名前がついています。
- 左から 1 列目にあるマスの名前の 1 文字目は
aである。同様に、左から 2,3,\ldots,8 列目にあるマスの名前の 1 文字目はb,c,d,e,f,g,hである。 - 下から 1 行目にあるマスの名前の 2 文字目は
1である。同様に、下から 2,3,\ldots,8 行目にあるマスの名前の 2 文字目は2,3,4,5,6,7,8である。
例えば、グリッドの左下のマスの名前は a1、右下のマスの名前は h1、右上のマスの名前は h8 です。
グリッドの状態を表す長さ 8 の 8 つの文字列 S_1,\ldots,S_8 が与えられます。
S_i の j 文字目は、グリッドの上から i 行目 左から j 列目のマスにコマが置かれているとき *、置かれていないとき . であり、S_1,\ldots,S_8 の中に文字 * はちょうど 1 つ存在します。
コマが置かれているマスの名前を求めてください。
制約
- S_i は
.および*のみからなる長さ 8 の文字列である - S_1,\ldots,S_8 の中に文字
*はちょうど 1 つ存在する。
入力
入力は以下の形式で標準入力から与えられる。
S_1 S_2 S_3 S_4 S_5 S_6 S_7 S_8
出力
答えを出力せよ。
入力例 1
........ ........ ........ ........ ........ ........ ........ *.......
出力例 1
a1
問題文中で説明したとおり、グリッドの左下のマスの名前は a1 です。
入力例 2
........ ........ ........ ........ ........ .*...... ........ ........
出力例 2
b3
Score : 200 points
Problem Statement
Locate a piece on a chessboard.
We have a grid with 8 rows and 8 columns of squares. Each of the squares has a 2-character name determined as follows.
- The first character of the name of a square in the 1-st column from the left is
a. Similarly, the first character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th column from the left isb,c,d,e,f,g,h, respectively. - The second character of the name of a square in the 1-st row from the bottom is
1. Similarly, the second character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th row from the bottom is2,3,4,5,6,7,8, respectively.
For instance, the bottom-left square is named a1, the bottom-right square is named h1, and the top-right square is named h8.
You are given 8 strings S_1,\ldots,S_8, each of length 8, representing the state of the grid.
The j-th character of S_i is * if the square at the i-th row from the top and j-th column from the left has a piece on it, and . otherwise.
The character * occurs exactly once among S_1,\ldots,S_8.
Find the name of the square that has a piece on it.
Constraints
- S_i is a string of length 8 consisting of
.and*. - The character
*occurs exactly once among S_1,\ldots,S_8.
Input
The input is given from Standard Input in the following format:
S_1 S_2 S_3 S_4 S_5 S_6 S_7 S_8
Output
Print the answer.
Sample Input 1
........ ........ ........ ........ ........ ........ ........ *.......
Sample Output 1
a1
As explained in the problem statement, the bottom-left square is named a1.
Sample Input 2
........ ........ ........ ........ ........ .*...... ........ ........
Sample Output 2
b3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は N 日間の鉄道旅行を計画しています。
高橋君はそれぞれの日について、運賃の通常料金を払うか、1 日周遊パスを 1 枚使用するか選ぶことができます。
ここで、1\leq i\leq N について、i 日目の旅行にかかる運賃の通常料金は F_i 円です。
一方、1 日周遊パスは D 枚セットで P 円で発売されており、何セットでも購入することが可能ですが、D 枚単位でしか購入することができません。
また、購入したパスは 1 枚ずつ好きな日に使うことができ、旅行が終了した時点で余っていても構いません。
N 日間の旅行でかかる金額、すなわち 1 日周遊パスの購入にかかった代金と、1 日周遊パスを利用しなかった日における運賃の通常料金の合計金額の和としてあり得る最小値を求めてください。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq D\leq 2\times 10^5
- 1\leq P\leq 10^9
- 1\leq F_i\leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D P F_1 F_2 \ldots F_N
出力
N 日間の旅行でかかる金額としてあり得る最小値を出力せよ。
入力例 1
5 2 10 7 1 6 3 6
出力例 1
20
1 日周遊パスを 1 セットだけ購入し、1 日目と 3 日目に使用すると、合計金額は (10\times 1)+(0+1+0+3+6)=20 となり、このときかかる金額が最小となります。
よって、20 を出力します。
入力例 2
3 1 10 1 2 3
出力例 2
6
3 日間すべてにおいて運賃の通常料金を支払ったときに最小となります。
入力例 3
8 3 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
3000000000
1 日周遊パスを 3 セット購入し、8 日間すべてにおいて 1 日周遊パスを利用したときに最小となります。
答えが 32 bit 整数型に収まらないことがあることに注意してください。
Score : 300 points
Problem Statement
Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.
Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.
Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq D\leq 2\times 10^5
- 1\leq P\leq 10^9
- 1\leq F_i\leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D P F_1 F_2 \ldots F_N
Output
Print the minimum possible total cost for the N-day trip.
Sample Input 1
5 2 10 7 1 6 3 6
Sample Output 1
20
If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.
Sample Input 2
3 1 10 1 2 3
Sample Output 2
6
The minimum cost is achieved by paying the regular fare for all three days.
Sample Input 3
8 3 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
3000000000
The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
414 の十進法での表記は 414 であり、これは回文です。
また、414 の八進法での表記は 636 であり、これも回文です。
これを踏まえて、以下の問題を解いてください。
正の整数 A, N が与えられます。 1 以上 N 以下の整数のうち、十進法での表記も A 進法での表記も回文であるようなものの総和を求めてください。
なお、この問題の制約下で答えは 2^{63} 未満であることが証明できます。
制約
- 2 \leq A \leq 9
- 1 \leq N \le 10^{12}
- 入力される数値は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
A N
出力
答えを 1 行で出力せよ。
入力例 1
8 1000
出力例 1
2155
条件を満たす整数は 1,2,3,4,5,6,7,9,121,292,333,373,414,585 の 14 個であり、その総和は 2155 です。
入力例 2
8 999999999999
出力例 2
914703021014
入力例 3
6 999999999999
出力例 3
283958331810
Score : 350 points
Problem Statement
The decimal representation of 414 is 414, which is a palindrome.
Also, the octal representation of 414 is 636, which is also a palindrome.
Based on this, solve the following problem.
You are given positive integers A and N. Find the sum of all integers between 1 and N, inclusive, whose decimal representation and base-A representation are both palindromes.
Under the constraints of this problem, it can be proved that the answer is less than 2^{63}.
Constraints
- 2 \leq A \leq 9
- 1 \leq N \le 10^{12}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A N
Output
Output the answer in one line.
Sample Input 1
8 1000
Sample Output 1
2155
The integers satisfying the condition are 1,2,3,4,5,6,7,9,121,292,333,373,414,585 (14 integers), and their sum is 2155.
Sample Input 2
8 999999999999
Sample Output 2
914703021014
Sample Input 3
6 999999999999
Sample Output 3
283958331810
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
頂点に 1 から N の、辺に 1 から M の番号がついたN 頂点 M 辺の有向グラフがあります。辺 i は頂点 A_i から頂点 B_i への重み W_i の有向辺です。
頂点 1 から頂点 N への walk のうち、walk に含まれる辺の重みのビット単位 \mathrm{XOR} の最小値を求めてください。
頂点 1 から頂点 N への walk とは
直感的には、「頂点 1 から頂点 N への経路であって、同じ頂点や同じ辺を複数回通っても良いもの」です。 正確には、辺の列 (e_1,\ldots,e_k) であって、以下の条件を全て満たすものです。
- e_1 は頂点 1 を始点とする。
- 全ての 1 \leq i < k について、e_i の終点と e_{i+1} の始点は一致する。
- e_k は頂点 N を終点とする。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A\ \mathrm{XOR}\ B は、以下のように定義されます。
- A\ \mathrm{XOR}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
制約
- 2 \leq N \leq 1000
- 0 \leq M \leq 1000
- 1 \leq A_i,B_i \leq N
- 0 \leq W_i < 2^{10}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 W_1 A_2 B_2 W_2 \vdots A_M B_M W_M
出力
頂点 1 から頂点 N への walk が存在しない場合、-1 と出力せよ。
頂点 1 から頂点 N への walk が存在する場合、そのうち、walk に含まれる辺の重みのビット単位 \mathrm{XOR} の最小値を出力せよ。
入力例 1
3 3 1 2 4 2 3 5 1 3 2
出力例 1
1
(辺 1, 辺 2) という walk に含まれる辺の重みのビット単位 \mathrm{XOR} は 1 となります。
入力例 2
4 4 1 4 7 4 2 2 2 3 4 3 4 1
出力例 2
0
(辺 1, 辺 2, 辺 3, 辺 4) という walk に含まれる辺の重みのビット単位 \mathrm{XOR} は 0 となります。
途中に頂点 N を含んでも良いことに注意してください。
入力例 3
999 4 1 2 9 2 1 8 1 2 7 1 1 6
出力例 3
-1
頂点 1 から頂点 N への walk が存在しない場合、-1 と出力してください。
Score : 400 points
Problem Statement
There is a directed graph with N vertices and M edges, where vertices are numbered from 1 to N and edges are numbered from 1 to M. Edge i is a directed edge from vertex A_i to vertex B_i with weight W_i.
Find the minimum value of the bitwise \mathrm{XOR} of the weights of edges included in a walk from vertex 1 to vertex N.
What is a walk from vertex 1 to vertex N?
Intuitively, it is "a path from vertex 1 to vertex N that may visit the same vertex or edge multiple times." Formally, it is a sequence of edges (e_1,\ldots,e_k) that satisfies all of the following conditions:
- e_1 starts at vertex 1.
- For all 1 \leq i < k, the endpoint of e_i and the starting point of e_{i+1} are the same.
- e_k ends at vertex N.
What is the bitwise \mathrm{XOR} operation?
The bitwise \mathrm{XOR} of non-negative integers A and B, denoted A\ \mathrm{XOR}\ B, is defined as follows:
- When A\ \mathrm{XOR}\ B is written in binary, the digit at the 2^k place (k \geq 0) is 1 if exactly one of the digits at the 2^k place of A and B in binary is 1, and 0 otherwise.
In general, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k), and it can be proved that this does not depend on the order of p_1, p_2, p_3, \dots p_k.
Constraints
- 2 \leq N \leq 1000
- 0 \leq M \leq 1000
- 1 \leq A_i,B_i \leq N
- 0 \leq W_i < 2^{10}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 W_1 A_2 B_2 W_2 \vdots A_M B_M W_M
Output
If there is no walk from vertex 1 to vertex N, output -1.
If there is a walk from vertex 1 to vertex N, output the minimum value of the bitwise \mathrm{XOR} of the weights of edges included in such a walk.
Sample Input 1
3 3 1 2 4 2 3 5 1 3 2
Sample Output 1
1
The bitwise \mathrm{XOR} of the weights of edges included in the walk (edge 1, edge 2) is 1.
Sample Input 2
4 4 1 4 7 4 2 2 2 3 4 3 4 1
Sample Output 2
0
The bitwise \mathrm{XOR} of the weights of edges included in the walk (edge 1, edge 2, edge 3, edge 4) is 0.
Note that the walk may include vertex N in the middle.
Sample Input 3
999 4 1 2 9 2 1 8 1 2 7 1 1 6
Sample Output 3
-1
If there is no walk from vertex 1 to vertex N, output -1.