MUJIN プログラミングチャレンジ Programming Challenge

A - MUJIN

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたは、QWERTY 配列のキーボードを眺めていると、M，U，J，I，N キーがひと固まりになっていることに気づきました（下図）。

M，U，J，I，N 以外の英大文字が与えられるので、そのキーが M，U，J，I，N キーの左側にあるか、右側にあるかを判定してください。

入力

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

1 行目には、M，U，J，I，N 以外の英大文字 c が与えられる。

出力

c のキーが M，U，J，I，N キーの左側にあれば Left を、右側にあれば Right を出力せよ。出力の末尾には改行を入れること。

入力例1

出力例1

Left

入力例2

出力例2

Right

入力例3

出力例3

Left

Problem

When you were looking at a QWERTY keyboard, you noticed that keys M, U, J, I, and N are close, and they split the remaining keys vertically (see the figure below).

Given an upper-case letter other than M, U，J，I，or N, your task is to determine whether the key is in the left or right part.

Input

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

In the first line, an upper-case letter c is written. c is not M，U，J，I，or N.

Output

If the key c is in the left part, print Left. Otherwise, print Right. Print a newline at the end of the output.

Input Example 1

Output Example 1

Left

Input Example 2

Output Example 2

Right

Input Example 3

Output Example 3

Left

B - Robot Arm

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたはロボットアームを持っています。ロボットアームの構造は、二次元平面上の折れ線 O-A-B-C で表されます（下図）。点 O は原点 (0,\ 0) に固定されています。

ロボットアームは、点 O，A，B で折れ線の角度を自由に変えられますが、線分 OA，AB，BC の長さは変えられません。また、折れ線には自己交差があっても構いません。

線分 OA，AB，BC の長さが与えられるので、点 C が移動できる領域の面積を求めてください。

入力

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

l_{OA} l_{AB} l_{BC}

1 行目には、線分 OA，AB，BC の長さを表す整数 l_{OA}，l_{AB}，l_{BC} (1≦l_{OA},\ l_{AB},\ l_{BC}≦100) が空白区切りで与えられる。

出力

点 C が移動できる領域の面積を出力せよ。絶対誤差または相対誤差が 10^{-6} 以下ならば正解となる。出力の末尾には改行を入れること。

入力例1

1 1 1

出力例1

28.2743338823

点 C が移動できる領域は、図の青い領域です。

入力例2

3 1 1

出力例2

75.3982236862

点 C が移動できる領域は、図の青い領域です。

入力例3

16 2 27

出力例3

6107.2561185786

Problem

Let us think about a robot arm, which is modeled as a polyline O-A-B-C in a two-dimensional space (see the figure below). Point O is fixed at the origin, i.e., O = (0, 0).

You can modify the angles at points O, A, and B; whereas you cannot change the lengths of segments OA, AB, or BC. It is allowed for these segments to cross each other.

Given the lengths of segments OA, AB, and BC, your task is to calculate the area of the region where point C can access.

Input

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

l_{OA} l_{AB} l_{BC}

In the first line, you are given three integers l_{OA}, l_{AB}, and l_{BC} (1≦l_{OA},\ l_{AB},\ l_{BC}≦100), separated by spaces. They indicate the lengths of segments OA, AB, and BC, respectively.

Output

Output the area of the region where point C can access. An answer with a relative or absolute error at most 10^{-6} is considered correct. Put a newline at the end of the output.

Input Example 1

1 1 1

Output Example 1

28.2743338823

The region is illustrated in blue below.

Input Example 2

3 1 1

Output Example 2

75.3982236862

The region is illustrated in blue below.

Input Example 3

16 2 27

Output Example 3

6107.2561185786

C - Orange Graph

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたは、N 頂点 M 辺の無向グラフを持っています。グラフは連結で、自己ループや多重辺はありません。頂点は 1 から N まで番号が振られており、辺は 1 から M まで番号が振られています。

最初、辺はすべて白です。あなたは、「白い辺をひとつ選び、オレンジに塗る」という操作を繰り返し行います。ただし、オレンジの辺のみからなる奇数長の閉路ができてしまうような操作は行えません。

あなたは、可能な操作があるかぎりは操作を行い続けます。あなたが操作を終えた後、最終的な辺の色の組合せとして考えられるものは何通りか求めてください。

入力

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

N M
x_1 y_1
x_2 y_2
:
x_M y_M

1 行目には、グラフの頂点数 N (2≦N≦16) と辺数 M (N-1≦M≦N(N-1)/2) が空白区切りで与えられる。
2 行目からの M 行には、辺の情報が与えられる。このうち i 行目には、i 番目の辺の端点 x_i と y_i (1≦x_i<y_i≦N) が空白区切りで与えられる。
i≠j ならば、x_i≠x_j または y_i≠y_j である。
グラフは連結である。

出力

あなたが操作を終えた後、最終的な辺の色の組合せとして考えられるものは何通りか出力せよ。出力の末尾には改行を入れること。

入力例1

出力例1

図の 3 通りです。

入力例2

出力例2

図の 5 通りです。

入力例3

出力例3

図の 1 通りです。

Problem

You are given an undirected graph with N vertices and M edges. It is connected and has no self-loops nor parallel edges. The vertices are numbered from 1 to N, and the edges are numbered from 1 to M.

Initially, all the edges are white. You repeat the following operation: Choose a white edge and paint it in orange. However, you are not allowed to apply an operation that yields an odd-length cycle that consists only of orange edges.

You repeat the procedure until there is no valid operation. Your task is, given the initial graph, to compute the number of possible outcomes (i.e., the colors of the edges).

Input

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

N M
x_1 y_1
x_2 y_2
:
x_M y_M

In the first line, integers N (2≦N≦16) and M (N-1≦M≦N(N-1)/2) are written, separated by a space. N and M describe the numbers of vertices and edges, respectively.
The subsequent M lines describe the edges. The i-th line among them contains two integers x_i and y_i (1≦x_i<y_i≦N), separated by a space, which indicates the endpoints of edge i.
If i≠j, then x_i≠x_j or y_i≠y_j.
The graph is connected.

Output

Output the number of possible outcomes, i.e., the number of the possible sets of orange edges. Put the newline at the end of the output.

Input Example 1

Output Example 1

There are three possible outcomes as illustrated in the figure below.

Input Example 2

Output Example 2

There are five possible outcomes as illustrated in the figure below.

Input Example 3

Output Example 3

There is one possible outcome as illustrated in the figure below.

D - Parenthesis Sequence

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

正しい括弧列とは、以下で定義される文字列のことです。

空文字列は正しい括弧列である。
文字列 s が正しい括弧列であるとき、(+s+) は正しい括弧列である。
文字列 s，t が正しい括弧列であるとき、s+t は正しい括弧列である。

あなたは、長さ N の文字列 S を持っています。S は (，)，? のみからなります。

S について Q 個の質問に答えてください。i 番目の質問は次のようなものです。

S の l_i 文字目から r_i 文字目までの連続した部分文字列を S_i とする。S_i に含まれるすべての ? をそれぞれ ( または ) へ置き換えることで、S_i を正しい括弧列にできるか？

入力

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

N
S
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q

1 行目には、文字列の長さ N (1≦N≦10^5) が与えられる。
2 行目には、長さ N の文字列 S が与えられる。S は (，)，? のみからなる。
3 行目には、質問の個数 Q (1≦Q≦10^5) が与えられる。
4 行目からの Q 行には、質問の情報が与えられる。このうち i 行目には、整数 l_i と r_i (1≦l_i≦r_i≦N) が空白区切りで与えられる。

出力

Q 行出力せよ。i 行目には、i 番目の質問に対する答えとして Yes または No を出力せよ。

入力例1

出力例1

No
Yes
No
No
No
Yes

入力例2

出力例2

No
Yes
No
No
No
Yes
Yes
No
No
Yes

Problem

We prefer correct parenthesis sequences. Correct parenthesis sequences are defined as follows.

An empty string is a correct parenthesis sequence.
If string s is a correct parenthesis sequence, (+s+) is also a correct parenthesis sequence.
If string s and t are correct parenthesis sequences, s + t is also a correct parenthesis sequence.

You have a string S with length N. S consists only of (, ), and ?.

Your task is to answer Q questions about string S. The i-th question is as follows:

Let S_i be the substring of S from the l_i-th character to the r_i-th character, inclusive. Is it possible to make S_i a correct parenthesis sequence by replacing every occurrence of ? with ( or )?

Input

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

N
S
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q

In the first line, integer N (1≦N≦10^5) is written, which indicates the length of string S.
In the second line, string S is written. S consists only of (, ), and ?.
In the third line, integer Q (1≦Q≦10^5) is written, which indicates the number of questions.
The subsequent Q lines describe the questions. The i-th line among them contains two integers l_i and r_i (1≦l_i≦r_i≦N), separated by a space.

Output

Output Q lines. In the i-th line, print Yes or No, according to the answer to the i-th question.

Input Example 1

Output Example 1

No
Yes
No
No
No
Yes

Input Example 2

Output Example 2

No
Yes
No
No
No
Yes
Yes
No
No
Yes

E - Hexagon

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

地面に直方体のブロックを埋めたところ、凸六角形の穴が開きました。穴の形が与えられたときブロックの体積として考えられる最小値を求めてください。

ブロックを xyz 空間内の直方体とします。また、地面を平面 z = 0 とします。このとき、穴は直方体と平面 z = 0 の共通部分として表されます。穴が凸六角形であり、その頂点の座標が反時計回りに (x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4), (x_5, y_5), (x_6, y_6) であるとき、直方体の体積として考えられる最小値を求めてください。ただし、そのような直方体が存在しない場合は、-1 と出力してください。

入力

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

x_1 y_1
x_2 y_2
x_3 y_3
x_4 y_4
x_5 y_5
x_6 y_6

入力はすべて整数である。
0 ≤ x_i, y_i ≤ 1000 をみたす。
六点 (x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4), (x_5, y_5), (x_6, y_6) は反時計回りに並んでいる。とくに、入力中の三点が同一直線上に並んでいることはない。
入力される六角形は凸である。

出力

ブロックの体積として考えられる最小値を出力せよ。ただし、条件を満たす直方体が存在しない場合は -1 と出力せよ。絶対誤差または相対誤差が 10^{-6} 以下ならば正解となる。出力の末尾には改行を入れること。

入力例1

出力例1

43.301270189

入力例2

出力例2

-1

Problem

We made a convex-hexagonal hole on the ground by burying a hyperrectangular block into the ground. You will be given the shape of the hole. Compute the minimum possible volume of the block.

Formally, the problem statement is as follows. Let the block be a hyperrectangle in a three-dimensional xyz-space. Let z = 0 be the surface of the ground. Then, the hole can be represented as the intersection between the hyperrectangle and the plane z = 0. When the hole is a convex hexagon and its vertices are (x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4), (x_5, y_5), (x_6, y_6) (in counter-clockwise order), compute the minimum possible volume of the hyperrectangle. If there is no such hyperrectangle, print -1 instead.

Input

The input will be given in the following format from the standard input:

x_1 y_1
x_2 y_2
x_3 y_3
x_4 y_4
x_5 y_5
x_6 y_6

All numbers in the input will be integers.
The coordinates will satisfy 0 ≤ x_i, y_i ≤ 1000.
The six points (x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4), (x_5, y_5), (x_6, y_6) will be arranged in the counter-clockwise order. In particular, no three points will be on the same line.
The hexagon will be convex.

Output

Print the minimum possible volume of the hyperrectangle. In case there is no such hyperrectangle, print -1 instead. The output will be considered correct if its absolute error or relative error is at most 10^{-6}. Print a newline at the end of the output.

Input Example 1

Output Example 1

43.301270189

Input Example 2

Output Example 2

-1