AtCoder Beginner Contest 053

A - ABC/ARC

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

すめけくんは現在のレートが 1200 未満ならば AtCoder Beginner Contest (ABC) に、そうでなければ AtCoder Regular Contest (ARC) に参加することにしました。すめけくんの現在のレート x が与えられます。すめけくんが参加するコンテストが ABC ならば ABC と、そうでなければ ARC と出力してください。

制約

1 ≦ x ≦ 3{,}000
x は整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

ABC

すめけくんの現在のレートは 1200 未満なので ABC と出力してください。

入力例 2

出力例 2

ARC

すめけくんの現在のレートは 1200 以上なので ARC と出力してください。

Score : 100 points

Problem Statement

Smeke has decided to participate in AtCoder Beginner Contest (ABC) if his current rating is less than 1200, and participate in AtCoder Regular Contest (ARC) otherwise.

You are given Smeke's current rating, x. Print ABC if Smeke will participate in ABC, and print ARC otherwise.

Constraints

1 ≦ x ≦ 3{,}000
x is an integer.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

ABC

Smeke's current rating is less than 1200, thus the output should be ABC.

Sample Input 2

Sample Output 2

ARC

Smeke's current rating is not less than 1200, thus the output should be ARC.

B - A to Z String

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

すぬけくんは文字列 s の連続した一部分(部分文字列という)を取り出して先頭が A であり末尾が Z であるような文字列を作ることにしました。すぬけくんが作ることのできる文字列の最大の長さを求めてください。なお，s には先頭が A であり末尾が Z であるような部分文字列が必ず存在することが保証されます。

制約

1 ≦ |s| ≦ 200{,}000
s は英大文字のみからなる
s には先頭が A であり末尾が Z であるような部分文字列が必ず存在する

入力

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

出力

答えを出力せよ。

入力例 1

QWERTYASDFZXCV

出力例 1

7 文字目から 11 文字目までを取り出して ASDFZ を作ると、先頭が A 末尾が Z であるような文字列を得ることが可能です。

入力例 2

ZABCZ

出力例 2

入力例 3

HASFJGHOGAKZZFEGA

出力例 3

Score : 200 points

Problem Statement

Snuke has decided to construct a string that starts with A and ends with Z, by taking out a substring of a string s (that is, a consecutive part of s).

Find the greatest length of the string Snuke can construct. Here, the test set guarantees that there always exists a substring of s that starts with A and ends with Z.

Constraints

1 ≦ |s| ≦ 200{,}000
s consists of uppercase English letters.
There exists a substring of s that starts with A and ends with Z.

Input

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

Output

Print the answer.

Sample Input 1

QWERTYASDFZXCV

Sample Output 1

By taking out the seventh through eleventh characters, it is possible to construct ASDFZ, which starts with A and ends with Z.

Sample Input 2

ZABCZ

Sample Output 2

Sample Input 3

HASFJGHOGAKZZFEGA

Sample Output 3

C - X: Yet Another Die Game

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

すぬけくんは 6 面サイコロで遊ぶことにしました。サイコロは 1 から 6 までの整数がそれぞれの面に書かれており、向かい合う面に書かれた数の和はどれも 7 です。

すぬけくんはサイコロの好きな面が上向きになるように置いたのち何回か以下の操作を行います。

操作：サイコロを手前、奥、左、右のどれかの方向に 90° だけ回転させる。その後、上を向いている面に書かれた数を y として y 点得る。

例えば、図のように 1 と書かれた面が上を向いており、手前側の面に 5 が、右側の面に 4 が書かれている状況を考えます。
図に示されるように右方向に回転させることで 3 と書かれた面が上を向くようにすることが可能です。その他、左方向に回転させた場合は 4 と書かれた面が、手前方向に回転させた場合は 2 と書かれた面が、奥方向に回転させた場合は 5 と書かれた面が上を向くようにすることが可能です。

すぬけくんが合計で x 点以上得るために必要な最小の操作回数を求めなさい。

制約

1 ≦ x ≦ 10^{15}
x は整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

入力例 2

149696127901

出力例 2

27217477801

Score : 300 points

Problem Statement

Snuke has decided to play with a six-sided die. Each of its six sides shows an integer 1 through 6, and two numbers on opposite sides always add up to 7.

Snuke will first put the die on the table with an arbitrary side facing upward, then repeatedly perform the following operation:

Operation: Rotate the die 90° toward one of the following directions: left, right, front (the die will come closer) and back (the die will go farther). Then, obtain y points where y is the number written in the side facing upward.

For example, let us consider the situation where the side showing 1 faces upward, the near side shows 5 and the right side shows 4, as illustrated in the figure. If the die is rotated toward the right as shown in the figure, the side showing 3 will face upward. Besides, the side showing 4 will face upward if the die is rotated toward the left, the side showing 2 will face upward if the die is rotated toward the front, and the side showing 5 will face upward if the die is rotated toward the back.

Find the minimum number of operation Snuke needs to perform in order to score at least x points in total.

Constraints

1 ≦ x ≦ 10^{15}
x is an integer.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

Sample Input 2

149696127901

Sample Output 2

27217477801

D - Card Eater

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

すぬけくんはカードゲームで遊ぶことにしました。 N 枚からなるカードの山があり、上から i 枚目のカードには整数 A_i が書かれています。

すぬけくんはこのカードの山に対し 0 回以上、以下の操作を行い、残ったカードに書かれた値が互いに異なるようにしたいです。最大で何枚のカードを残すことが可能か求めなさい。なお、N は奇数であり、少なくとも 1 枚のカードを残すことが可能であることが保証されます。

操作：カードの山から任意の 3 枚のカードを抜き出す。抜き出したカードのうち書かれた値が最大であるようなカード 1 枚と最小であるようなカード 1 枚の合計 2 枚を選んで食べる。その後残った 1 枚をカードの山に戻す。

制約

3 ≦ N ≦ 10^{5}
N は奇数
1 ≦ A_i ≦ 10^{5}
A_i は整数

入力

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

N
A_1 A_2 A_3 ... A_{N}

出力

答えを出力せよ。

入力例 1

5
1 2 1 3 7

出力例 1

操作を 1 回行って 1,1,2 を取り出すというのが最適な操作手順の 1 つです。最大値である 2 と書かれたカードで最小値である 1 と書かれたカードがそれぞれ 1 枚ずつ食べられ、残った 1 と書かれたカードがカードの山に戻されます。カードの山に残っているカードは 1,3,7 となり、これらは互いに異なります。

入力例 2

15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1

出力例 2

Score : 400 points

Problem Statement

Snuke has decided to play a game using cards. He has a deck consisting of N cards. On the i-th card from the top, an integer A_i is written.

He will perform the operation described below zero or more times, so that the values written on the remaining cards will be pairwise distinct. Find the maximum possible number of remaining cards. Here, N is odd, which guarantees that at least one card can be kept.

Operation: Take out three arbitrary cards from the deck. Among those three cards, eat two: one with the largest value, and another with the smallest value. Then, return the remaining one card to the deck.

Constraints

3 ≦ N ≦ 10^{5}
N is odd.
1 ≦ A_i ≦ 10^{5}
A_i is an integer.

Input

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

N
A_1 A_2 A_3 ... A_{N}

Output

Print the answer.

Sample Input 1

5
1 2 1 3 7

Sample Output 1

One optimal solution is to perform the operation once, taking out two cards with 1 and one card with 2. One card with 1 and another with 2 will be eaten, and the remaining card with 1 will be returned to deck. Then, the values written on the remaining cards in the deck will be pairwise distinct: 1, 3 and 7.

Sample Input 2

15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1