AtCoder Beginner Contest 055

A - Restaurant

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

すぬけくんはレストランに通うのが好きです。

すぬけくん行きつけのレストランは何を食べても 1 食 800 円で、15 食食べる毎にその場で 200 円もらえます。

すぬけくんは今までで合計 N 食食べました。今までに払った金額を x 円、レストランからもらった金額を y 円として、x-y を求めなさい。

制約

1 ≦ N ≦ 100

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

すぬけくんは今までに 16000 円払っており、200 円もらっているので、答えは 15800 となります。

入力例 2

出力例 2

すぬけくんは 60 食食べたので、48000 円払って 800 円もらいました。

Score : 100 points

Problem Statement

Snuke has a favorite restaurant.

The price of any meal served at the restaurant is 800 yen (the currency of Japan), and each time a customer orders 15 meals, the restaurant pays 200 yen back to the customer.

So far, Snuke has ordered N meals at the restaurant. Let the amount of money Snuke has paid to the restaurant be x yen, and let the amount of money the restaurant has paid back to Snuke be y yen. Find x-y.

Constraints

1 ≤ N ≤ 100

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

So far, Snuke has paid 16000 yen, and the restaurant has paid back 200 yen. Thus, the answer is 15800.

Sample Input 2

Sample Output 2

Snuke has paid 48000 yen for 60 meals, and the restaurant has paid back 800 yen.

B - Training Camp

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

すぬけくんはトレーニングが好きなので N 回だけトレーニングすることにしました。

すぬけくんのトレーニング開始前のパワーは 1 です。すぬけくんが i 回目のトレーニングを終えるとパワーが i 倍されます。

すぬけくんが N 回トレーニングをしたあとのパワーを求めなさい。ただし、答えの値は非常に大きな値になることがあるので 10^{9}+7 で割ったあまりを出力してください。

制約

1 ≦ N ≦ 10^{5}

入力

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

出力

答えを 10^{9}+7 で割ったあまりを出力せよ。

入力例 1

出力例 1

1 回目のトレーニングを終えると、パワーは 1 倍され 1 になります
2 回目のトレーニングを終えると、パワーは 2 倍され 2 になります
3 回目のトレーニングを終えると、パワーは 3 倍され 6 になります

入力例 2

出力例 2

入力例 3

出力例 3

457992974

答えを 10^{9}+7 で割ったあまりを出力してください。

Score : 200 points

Problem Statement

Snuke loves working out. He is now exercising N times.

Before he starts exercising, his power is 1. After he exercises for the i-th time, his power gets multiplied by i.

Find Snuke's power after he exercises N times. Since the answer can be extremely large, print the answer modulo 10^{9}+7.

Constraints

1 ≤ N ≤ 10^{5}

Input

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

Output

Print the answer modulo 10^{9}+7.

Sample Input 1

Sample Output 1

After Snuke exercises for the first time, his power gets multiplied by 1 and becomes 1.
After Snuke exercises for the second time, his power gets multiplied by 2 and becomes 2.
After Snuke exercises for the third time, his power gets multiplied by 3 and becomes 6.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

457992974

Print the answer modulo 10^{9}+7.

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