AtCoder Regular Contest 069

C - Scc Puzzle

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

すぬけくんはパズルが好きです。

今日は S と c の形をしたピースを使ったパズルで遊んでいます。このパズルでは図のように c 型のピースを 2 つ組み合わせて S 型のピースを 1 つ作ることができます。

すぬけくんは S 型のピースを 1 つ、c 型のピースを 2 つ組み合わせて Scc という組を可能な限り多く作ることにしました。

すぬけくんが N 個の S 型のピースと M 個の c 型のピースを持っているとき、Scc という組を最大でいくつ作ることが可能か求めなさい。

制約

1 ≦ N,M ≦ 10^{12}

入力

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

N M

出力

答えを出力せよ。

入力例 1

1 6

出力例 1

以下のような手順でピースを組み合わせることで 2 つの Scc という組を作ることが可能です。

c 型のピース 2 つを組み合わせて S のピースを 1 つ作る
S 型のピース 1 つと c のピース 2 つを組み合わせて Scc という組を 1 つ作る
S 型のピース 1 つと c のピース 2 つを組み合わせて Scc という組を 1 つ作る

入力例 2

12345 678901

出力例 2

Score : 300 points

Problem Statement

Snuke loves puzzles.

Today, he is working on a puzzle using S- and c-shaped pieces. In this puzzle, you can combine two c-shaped pieces into one S-shaped piece, as shown in the figure below:

Snuke decided to create as many Scc groups as possible by putting together one S-shaped piece and two c-shaped pieces.

Find the maximum number of Scc groups that can be created when Snuke has N S-shaped pieces and M c-shaped pieces.

Constraints

1 ≤ N,M ≤ 10^{12}

Input

The input is given from Standard Input in the following format:

N M

Output

Print the answer.

Sample Input 1

1 6

Sample Output 1

Two Scc groups can be created as follows:

Combine two c-shaped pieces into one S-shaped piece
Create two Scc groups, each from one S-shaped piece and two c-shaped pieces

Sample Input 2

12345 678901

Sample Output 2

D - Menagerie

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 500 点

問題文

すぬけくんは動物が好きなので動物園を作りました。

この動物園では 1,2,3, ..., N の番号を割り振られた N 匹の動物が円環状に並べられています。 i (2≦i≦N-1) 番の動物は i-1 番の動物と i+1 番の動物と隣り合っています。また、1 番の動物は N 番の動物と 2 番の動物と隣り合っており、N 番の動物は N-1 番の動物と 1 番の動物と隣り合っています。

動物園には本当のことしか言わない正直者の羊と、嘘しか言わない嘘つきの狼の 2 種類の動物がいます。

すぬけくんには羊と狼の区別がつかないので、それぞれの動物に両隣の動物が同じ種類かどうかを訪ねたところ、i 番目の動物は s_i と答えました。s_i が o ならば両隣の動物が同じ種類であると、x ならば異なる種類であると i 番の動物が言ったことを示します。

より形式的には、羊は両隣の動物がどちらも羊あるいはどちらも狼のとき o と答え、そうでないとき x と答えます。狼は両隣の動物がどちらも羊あるいはどちらも狼のとき x と答え、そうでないとき o と答えます。

これらの回答結果と矛盾しないような各動物の種別の割り当てが存在するか、すぬけくんは気になっています。存在するならば一例を示し、存在しないならば -1 を出力しなさい。

制約

3 ≦ N ≦ 10^{5}
s は o と x のみからなる長さ N の文字列

入力

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

N
s

出力

s と矛盾しないような各動物の種類の割当てが存在しないならば -1 を出力してください。存在するならば以下の形式で文字列 t を出力してください。 t で示される割り当てが s と矛盾しないならば正解となります。

t は長さ N で S と W のみからなる文字列
t_i が S ならば i 番の動物が羊であることを、W ならば狼であることを示す

入力例 1

6
ooxoox

出力例 1

SSSWWS

例えば 1,2,3,4,5,6 番の動物がそれぞれ羊、羊、羊、狼、狼、羊であるとき発言と矛盾しません。その他、狼、羊、狼、羊、狼、狼であるようなときも矛盾しません。

両隣が同じ種類の動物のとき羊は o と発言し、狼は x と発言すること、両隣が異なる種類の動物のとき羊は x と発言し、狼は o と発言することに注意してください。

入力例 2

3
oox

出力例 2

-1

存在しない場合は -1 を出力してください。

入力例 3

10
oxooxoxoox

出力例 3

SSWWSSSWWS

Score : 500 points

Problem Statement

Snuke, who loves animals, built a zoo.

There are N animals in this zoo. They are conveniently numbered 1 through N, and arranged in a circle. The animal numbered i (2≤i≤N-1) is adjacent to the animals numbered i-1 and i+1. Also, the animal numbered 1 is adjacent to the animals numbered 2 and N, and the animal numbered N is adjacent to the animals numbered N-1 and 1.

There are two kinds of animals in this zoo: honest sheep that only speak the truth, and lying wolves that only tell lies.

Snuke cannot tell the difference between these two species, and asked each animal the following question: "Are your neighbors of the same species?" The animal numbered i answered s_i. Here, if s_i is o, the animal said that the two neighboring animals are of the same species, and if s_i is x, the animal said that the two neighboring animals are of different species.

More formally, a sheep answered o if the two neighboring animals are both sheep or both wolves, and answered x otherwise. Similarly, a wolf answered x if the two neighboring animals are both sheep or both wolves, and answered o otherwise.

Snuke is wondering whether there is a valid assignment of species to the animals that is consistent with these responses. If there is such an assignment, show one such assignment. Otherwise, print -1.

Constraints

3 ≤ N ≤ 10^{5}
s is a string of length N consisting of o and x.

Input

The input is given from Standard Input in the following format:

N
s

Output

If there does not exist an valid assignment that is consistent with s, print -1. Otherwise, print an string t in the following format. The output is considered correct if the assignment described by t is consistent with s.

t is a string of length N consisting of S and W.
If t_i is S, it indicates that the animal numbered i is a sheep. If t_i is W, it indicates that the animal numbered i is a wolf.

Sample Input 1

6
ooxoox

Sample Output 1

SSSWWS

For example, if the animals numbered 1, 2, 3, 4, 5 and 6 are respectively a sheep, sheep, sheep, wolf, wolf, and sheep, it is consistent with their responses. Besides, there is another valid assignment of species: a wolf, sheep, wolf, sheep, wolf and wolf.

Let us remind you: if the neiboring animals are of the same species, a sheep answers o and a wolf answers x. If the neiboring animals are of different species, a sheep answers x and a wolf answers o.

Sample Input 2

3
oox

Sample Output 2

-1

Print -1 if there is no valid assignment of species.

Sample Input 3

10
oxooxoxoox

Sample Output 3

SSWWSSSWWS

E - Frequency

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700 点

問題文

すぬけくんは数列を作るのが好きです。

1 から N までの番号がついた石の山があります。 i 番の石の山は a_i 個の石からなります。

すぬけくんは以下の手順により長さ Σa_i の数列 s を構成することにしました。

石の数が最大である山のうち、最も番号が小さい山の番号を x として、s の末尾に x を追加する
石が 1 個以上存在する山を 1 つ選んで、選んだ山から石を 1 つ取り除く
石が 1 個以上存在する山が存在するなら 1. へ、そうでなければ数列の構成を終了する

s が辞書順で最小の数列となるようにしたとき、s に 1,2,3,...,N という数がそれぞれいくつ含まれるか求めなさい。

制約

1 ≦ N ≦ 10^{5}
1 ≦ a_i ≦ 10^{9}

入力

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

N
a_1 a_2 ... a_{N}

出力

答えを N 行に出力せよ。i 行目では辞書順で最小の s における i の出現回数を出力せよ。

入力例 1

2
1 2

出力例 1

2
1

以下の手順で辞書順最小であるような数列が構成できます。

石の数が最大であるような山は 2 番なので 2 を s に追加する。その後、番号 2 の山から石を 1 つ取り除く。
石の数が最大であるような山は 1 番と 2 番なので、最も番号が小さい 1 を s に追加する。その後、番号 2 の山から石を 1 つ取り除く。
石の数が最大であるような山は 1 番なので 1 を s に追加する。その後、番号 1 の山から石を 1 つ取り除く。

このときできる数列は (2,1,1) となります。1 は 2 つ含まれ、2 は 1 つ含まれます。

入力例 2

10
1 2 1 3 2 4 2 5 8 1

出力例 2

Score : 700 points

Problem Statement

Snuke loves constructing integer sequences.

There are N piles of stones, numbered 1 through N. The pile numbered i consists of a_i stones.

Snuke will construct an integer sequence s of length Σa_i, as follows:

Among the piles with the largest number of stones remaining, let x be the index of the pile with the smallest index. Append x to the end of s.
Select a pile with one or more stones remaining, and remove a stone from that pile.
If there is a pile with one or more stones remaining, go back to step 1. Otherwise, terminate the process.

We are interested in the lexicographically smallest sequence that can be constructed. For each of the integers 1,2,3,...,N, how many times does it occur in the lexicographically smallest sequence?

Constraints

1 ≤ N ≤ 10^{5}
1 ≤ a_i ≤ 10^{9}

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{N}

Output

Print N lines. The i-th line should contain the number of the occurrences of the integer i in the lexicographically smallest sequence that can be constructed.

Sample Input 1

2
1 2

Sample Output 1

2
1

The lexicographically smallest sequence is constructed as follows:

Since the pile with the largest number of stones remaining is pile 2, append 2 to the end of s. Then, remove a stone from pile 2.
Since the piles with the largest number of stones remaining are pile 1 and 2, append 1 to the end of s (we take the smallest index). Then, remove a stone from pile 2.
Since the pile with the largest number of stones remaining is pile 1, append 1 to the end of s. Then, remove a stone from pile 1.

The resulting sequence is (2,1,1). In this sequence, 1 occurs twice, and 2 occurs once.

Sample Input 2

10
1 2 1 3 2 4 2 5 8 1

Sample Output 2

F - Flags

Time Limit: 5 sec / Memory Limit: 256 MB

配点 : 1200 点

問題文

すぬけくんは旗が好きです。

すぬけくんは N 本の旗を一直線上に並べることにしました。

i 番目の旗は座標 x_i か座標 y_i のどちらかに設置することができます。

すぬけくんは、2 つの旗同士の距離の最小値 d が大きいほど、旗の並びの見栄えが良いと考えています。d としてありうる値の最大値を求めなさい。

制約

2 ≦ N ≦ 10^{4}
1 ≦ x_i, y_i ≦ 10^{9}
x_i, y_i は整数

入力

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

N
x_1 y_1
:
x_N y_N

出力

答えを出力せよ。

入力例 1

出力例 1

旗 1 を座標 1 に、旗 2 を座標 5 に、旗 3 を座標 9 に設置するのが最適であり、このとき旗同士の距離の最小値は 4 となります。

入力例 2

出力例 2

旗の位置は重なることもあります。

入力例 3

出力例 3

Score : 1200 points

Problem Statement

Snuke loves flags.

Snuke is placing N flags on a line.

The i-th flag can be placed at either coordinate x_i or coordinate y_i.

Snuke thinks that the flags look nicer when the smallest distance between two of them, d, is larger. Find the maximum possible value of d.

Constraints

2 ≤ N ≤ 10^{4}
1 ≤ x_i, y_i ≤ 10^{9}
x_i and y_i are integers.

Input

The input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the answer.

Sample Input 1

Sample Output 1

The optimal solution is to place the first flag at coordinate 1, the second flag at coordinate 5 and the third flag at coordinate 9. The smallest distance between two of the flags is 4 in this case.

Sample Input 2

Sample Output 2

There can be more than one flag at the same position.

Sample Input 3