AtCoder Beginner Contest 043

A - Children and Candies (ABC Edit)

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

競プロ幼稚園にはN人の子供がいます。えび先生は、子供たちを一列に並べ、一人目にはキャンディーを1個,二人目には2個,...,N人目にはN個あげることにしました。必要なキャンディーの個数の合計は何個でしょう?

制約

1≦N≦100

入力

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

出力

必要なキャンディーの個数の合計を出力せよ。

入力例 1

出力例 1

1+2+3=6が答えになります。

入力例 2

出力例 2

1から10までの和は55です。

入力例 3

出力例 3

子供は一人しかいません。この時答えは1になります。

Score : 100 points

Problem Statement

There are N children in AtCoder Kindergarten. Mr. Evi will arrange the children in a line, then give 1 candy to the first child in the line, 2 candies to the second child, ..., N candies to the N-th child. How many candies will be necessary in total?

Constraints

1≦N≦100

Input

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

Output

Print the necessary number of candies in total.

Sample Input 1

Sample Output 1

The answer is 1+2+3=6.

Sample Input 2

Sample Output 2

The sum of the integers from 1 to 10 is 55.

Sample Input 3

Sample Output 3

Only one child. The answer is 1 in this case.

B - Unhappy Hacking (ABC Edit)

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

しぐはキーボードを製作しました。シンプルさを極限まで追求したこのキーボードには、0 キー、1 キー、バックスペースキーの 3 つしかキーがありません。

手始めに、しぐはこのキーボードで簡単なテキストエディタを操作してみることにしました。このエディタには常に一つの文字列が表示されます（文字列が空のこともあります）。エディタを起動した直後では、文字列は空です。キーボードの各キーを押すと、文字列が次のように変化します。

0 キー: 文字列の右端に文字 0 が挿入される。
1 キー: 文字列の右端に文字 1 が挿入される。
バックスペースキー: 文字列が空なら、何も起こらない。そうでなければ、文字列の右端の 1 文字が削除される。

しぐはエディタを起動し、これらのキーを何回か押しました。しぐが押したキーを順番に記録した文字列 s が与えられます。s の中の文字 0 は 0 キー、文字 1 は 1 キー、文字 B はバックスペースキーを表します。いま、エディタの画面にはどのような文字列が表示されているでしょうか？

制約

1 ≦ |s| ≦ 10 (|s| は s の長さを表す)
s は文字 0, 1, B のみからなる。
正解は空文字列ではない。

入力

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

出力

最終的にエディタに表示されている文字列を出力せよ。（「制約」セクションで述べたように、この文字列が空になるような入力は与えられない）

入力例 1

01B0

出力例 1

キーが押されるたびに、エディタの文字列は 0, 01, 0, 00 と変化します。

入力例 2

0BB1

出力例 2

キーが押されるたびに、エディタの文字列は 0, (空文字列), (空文字列), 1 と変化します。

Score : 200 points

Problem Statement

Sig has built his own keyboard. Designed for ultimate simplicity, this keyboard only has 3 keys on it: the 0 key, the 1 key and the backspace key.

To begin with, he is using a plain text editor with this keyboard. This editor always displays one string (possibly empty). Just after the editor is launched, this string is empty. When each key on the keyboard is pressed, the following changes occur to the string:

The 0 key: a letter 0 will be inserted to the right of the string.
The 1 key: a letter 1 will be inserted to the right of the string.
The backspace key: if the string is empty, nothing happens. Otherwise, the rightmost letter of the string is deleted.

Sig has launched the editor, and pressed these keys several times. You are given a string s, which is a record of his keystrokes in order. In this string, the letter 0 stands for the 0 key, the letter 1 stands for the 1 key and the letter B stands for the backspace key. What string is displayed in the editor now?

Constraints

1 ≦ |s| ≦ 10 (|s| denotes the length of s)
s consists of the letters 0, 1 and B.
The correct answer is not an empty string.

Input

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

Output

Print the string displayed in the editor in the end.

Sample Input 1

01B0

Sample Output 1

Each time the key is pressed, the string in the editor will change as follows: 0, 01, 0, 00.

Sample Input 2

0BB1

Sample Output 2

Each time the key is pressed, the string in the editor will change as follows: 0, (empty), (empty), 1.

C - Be Together

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

N 個の整数 a_1,a_2,..,a_N が与えられます。えび君はこれらを書き換えて全て同じ整数にしようとしています。各a_i (1≦i≦N)は高々一回しか書き換えられません(書き換えなくても良い)。整数xを整数yに書き換えるとき、コストが(x-y)^2かかります。仮にa_i=a_j (i≠j)だとしても、ひとつ分のコストで同時に書き換えることは出来ません(入出力例2 を参照)。えび君が目的を達成するのに必要なコストの総和の最小値を求めてください。

制約

1≦N≦100
-100≦a_i≦100

入力

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

N
a_1 a_2 ... a_N

出力

えび君が全てを同じ整数に書き換えるのに必要なコストの総和の最小値を出力せよ。

入力例 1

2
4 8

出力例 1

全てを6に書き換えると、コストの総和は(4-6)^2+(8-6)^2=8となり、これが最小です。

入力例 2

3
1 1 3

出力例 2

全てを2に書き換えると(1-2)^2+(1-2)^2+(3-2)^2=3となります。各a_iごとに書き換えるので、二つの1を一度にコスト(1-2)^2で書き換えられるわけではないことに注意してください。

入力例 3

3
4 2 5

出力例 3

4は書き換えずに、2と5を共に4に書き換えることで(2-4)^2+(5-4)^2=5が達成できて、これが最小です。

入力例 4

4
-100 -100 -100 -100

出力例 4

何も書き換えなくともえび君は目的を達成しています。よってこの場合コストは0です。

Score : 200 points

Problem Statement

Evi has N integers a_1,a_2,..,a_N. His objective is to have N equal integers by transforming some of them.

He may transform each integer at most once. Transforming an integer x into another integer y costs him (x-y)^2 dollars. Even if a_i=a_j (i≠j), he has to pay the cost separately for transforming each of them (See Sample 2).

Find the minimum total cost to achieve his objective.

Constraints

1≦N≦100
-100≦a_i≦100

Input

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

N
a_1 a_2 ... a_N

Output

Print the minimum total cost to achieve Evi's objective.

Sample Input 1

2
4 8

Sample Output 1

Transforming the both into 6s will cost (4-6)^2+(8-6)^2=8 dollars, which is the minimum.

Sample Input 2

3
1 1 3

Sample Output 2

Transforming the all into 2s will cost (1-2)^2+(1-2)^2+(3-2)^2=3 dollars. Note that Evi has to pay (1-2)^2 dollar separately for transforming each of the two 1s.

Sample Input 3

3
4 2 5

Sample Output 3

Leaving the 4 as it is and transforming the 2 and the 5 into 4s will achieve the total cost of (2-4)^2+(5-4)^2=5 dollars, which is the minimum.

Sample Input 4

4
-100 -100 -100 -100

Sample Output 4

Without transforming anything, Evi's objective is already achieved. Thus, the necessary cost is 0.

D - Unbalanced

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

文字列 t について、t の長さが 2 以上であり、かつ t の中の文字のうち過半数が同じ文字であるとき、t をアンバランスであると呼ぶことにします。例えば、voodoo や melee はアンバランスであり、noon や a はアンバランスではありません。

小文字のアルファベットからなる文字列 s が与えられます。s にアンバランスな (連続する) 部分文字列が存在するか判定してください。存在する場合は、s の中でそのような部分文字列が存在する位置を一つ示してください。

制約

2 ≦ |s| ≦ 10^5
s は小文字のアルファベットのみからなる。

部分点

2 ≦ |s| ≦ 100 を満たすデータセットに正解した場合は、200 点が与えられる。

入力

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

出力

s にアンバランスな部分文字列が存在しない場合は、-1 -1 と出力せよ。

s にアンバランスな部分文字列が存在する場合は、そのような部分文字列の一つを s_a s_{a+1} ... s_{b} (1 ≦ a < b ≦ |s|) として、a b と出力せよ。そのような部分文字列が複数存在する場合は、いずれも正解とみなされる。

入力例 1

needed

出力例 1

2 5

文字列 s_2 s_3 s_4 s_5 = eede はアンバランスな文字列です。他にもアンバランスな部分文字列は存在し、例えば 2 6 と出力しても正解となります。

入力例 2

atcoder

出力例 2

-1 -1

文字列 atcoder はアンバランスな部分文字列を持ちません。

Score : 400 points

Problem Statement

Given a string t, we will call it unbalanced if and only if the length of t is at least 2, and more than half of the letters in t are the same. For example, both voodoo and melee are unbalanced, while neither noon nor a is.

You are given a string s consisting of lowercase letters. Determine if there exists a (contiguous) substring of s that is unbalanced. If the answer is positive, show a position where such a substring occurs in s.

Constraints

2 ≦ |s| ≦ 10^5
s consists of lowercase letters.

Partial Score

200 points will be awarded for passing the test set satisfying 2 ≦ N ≦ 100.

Input

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

Output

If there exists no unbalanced substring of s, print -1 -1.

If there exists an unbalanced substring of s, let one such substring be s_a s_{a+1} ... s_{b} (1 ≦ a < b ≦ |s|), and print a b. If there exists more than one such substring, any of them will be accepted.

Sample Input 1

needed

Sample Output 1

2 5

The string s_2 s_3 s_4 s_5 = eede is unbalanced. There are also other unbalanced substrings. For example, the output 2 6 will also be accepted.

Sample Input 2

atcoder

Sample Output 2

-1 -1

The string atcoder contains no unbalanced substring.