A - Shampoo

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君の家には、高橋君、高橋君の父、高橋君の母の 3 人が住んでおり、全員が毎晩風呂で髪を洗います。
風呂には、高橋君の父、高橋君の母、高橋君の順に入り、それぞれシャンプーを A,B,C ミリリットル使います。

今朝の時点で、ボトルには V ミリリットルのシャンプーが残っていました。このまま補充しない時、初めてシャンプーが不足するのは誰が使おうとした時ですか？

制約

  • 1 \leq V,A,B,C \leq 10^5
  • 入力に含まれる値は全て整数である

入力

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

V A B C

出力

初めてシャンプーが不足するのが、高橋君の父が使おうとしたときならば F、高橋君の母が使おうとしたときならば M、高橋君が使おうとしたときならば T を出力せよ。

入力例 1

25 10 11 12

出力例 1

T

シャンプーは 25 ミリリットル残っています。

  • まず高橋君の父が 10 ミリリットル使い、残りは 15 ミリリットルになります。
  • 次に高橋君の母が 11 ミリリットル使い、残りは 4 ミリリットルになります。
  • 最後に高橋君が 12 ミリリットル使おうとしますが、4 ミリリットルしか残っておらず、不足しています。

入力例 2

30 10 10 10

出力例 2

F

シャンプーは 30 ミリリットル残っています。

  • まず高橋君の父が 10 ミリリットル使い、残りは 20 ミリリットルになります。
  • 次に高橋君の母が 10 ミリリットル使い、残りは 10 ミリリットルになります。
  • 続いて高橋君が 10 ミリリットル使い、残りは 0 ミリリットルになります。
  • 翌日、高橋君の父が 10 ミリリットル使おうとしますが、0 ミリリットルしか残っておらず、不足しています。

入力例 3

100000 1 1 1

出力例 3

M

Score : 100 points

Problem Statement

Three people live in Takahashi's house: Takahashi, his father, and his mother. All of them wash their hair in the bathroom each night.
His father, his mother, and Takahashi take a bath in this order and use A, B, and C milliliters of shampoo, respectively.

This morning, the bottle contained V milliliters of shampoo. Without refilling, who will be the first to run short of shampoo to wash their hair?

Constraints

  • 1 \leq V,A,B,C \leq 10^5
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

V A B C

Output

If the first person to run short of shampoo to wash their hair is Takahashi's father, print F; if it is Takahashi's mother, print M; if it is Takahashi, print T.

Sample Input 1

25 10 11 12

Sample Output 1

T

Now, they have 25 milliliters of shampoo.

  • First, Takahashi's father uses 10 milliliters, leaving 15.
  • Next, Takahashi's mother uses 11 milliliters, leaving 4.
  • Finally, Takahashi tries to use 12 milliliters and runs short of shampoo since only 4 is remaining.

Sample Input 2

30 10 10 10

Sample Output 2

F

Now, they have 30 milliliters of shampoo.

  • First, Takahashi's father uses 10 milliliters, leaving 20.
  • Next, Takahashi's mother uses 10 milliliters, leaving 10.
  • Then, Takahashi uses 10 milliliters, leaving 0.
  • Next day, Takahashi's father tries to use 10 milliliters and runs short of shampoo since only 0 is remaining.

Sample Input 3

100000 1 1 1

Sample Output 3

M
B - ^{-1}

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

(1,2,…,N) を並び替えた数列 P と整数 X が与えられます。 数列 P の i 番目の項の値は P_i です。 P_k = X を満たす k を出力してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq X \leq N
  • P は (1,2,…,N) を並び替えてできる数列
  • 入力はすべて整数

入力

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

N X
P_1 P_2 \ldots P_N

出力

答えを出力せよ。

入力例 1

4 3
2 3 1 4

出力例 1

2

P = (2,3,1,4) なので、P_2 = 3 です。したがって、2 を出力します。

入力例 2

5 2
3 5 1 4 2

出力例 2

5

入力例 3

6 6
1 2 3 4 5 6

出力例 3

6

Score : 100 points

Problem Statement

You are given a sequence P that is a permutation of (1,2,…,N), and an integer X. The i-th term of P has a value of P_i. Print k such that P_k = X.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq X \leq N
  • P is a permutation of (1,2,…,N).
  • All values in the input are integers.

Input

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

N X
P_1 P_2 \ldots P_N

Output

Print the answer.

Sample Input 1

4 3
2 3 1 4

Sample Output 1

2

We have P = (2,3,1,4), so P_2 = 3. Thus, you should print 2.

Sample Input 2

5 2
3 5 1 4 2

Sample Output 2

5

Sample Input 3

6 6
1 2 3 4 5 6

Sample Output 3

6
C - Qualification Contest

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の人があるコンテストに参加し、i 位の人のハンドルネームは S_i でした。
上位 K 人のハンドルネームを辞書順に出力してください。

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。

以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

  1. S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
  2. S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
  3. S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

  • 1 \leq K \leq N \leq 100
  • K, N は整数
  • S_i は英小文字からなる長さ 10 以下の文字列
  • i \neq j ならば S_i \neq S_j

入力

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

N K
S_1
S_2
\vdots
S_N

出力

答えを改行区切りで出力せよ。

入力例 1

5 3
abc
aaaaa
xyz
a
def

出力例 1

aaaaa
abc
xyz

このコンテストには 5 人が参加し、1 位の人のハンドルネームは abc 、2 位の人のハンドルネームは aaaaa 、3 位の人のハンドルネームは xyz 、4 位の人のハンドルネームは a 、5 位の人のハンドルネームは def でした。

上位 3 人のハンドルネームは abc、aaaaa、xyz であるため、これを辞書順に並べ替えて aaaaa 、abc 、xyz の順に出力します。

入力例 2

4 4
z
zyx
zzz
rbg

出力例 2

rbg
z
zyx
zzz

入力例 3

3 1
abc
arc
agc

出力例 3

abc

Score : 200 points

Problem Statement

There were N participants in a contest. The participant ranked i-th had the nickname S_i.
Print the nicknames of the top K participants in lexicographical order.

What is lexicographical order?

Simply put, the lexicographical order is the order of words in a dictionary. As a formal description, below is an algorithm to order distinct strings S and T.

Let S_i denote the i-th character of a string S. We write S \lt T if S is lexicographically smaller than T, and S \gt T if S is larger.

  1. Let L be the length of the shorter of S and T. For i=1,2,\dots,L, check whether S_i equals T_i.
  2. If there is an i such that S_i \neq T_i, let j be the smallest such i. Compare S_j and T_j. If S_j is alphabetically smaller than T_j, we get S \lt T; if S_j is larger, we get S \gt T.
  3. If there is no i such that S_i \neq T_i, compare the lengths of S and T. If S is shorter than T, we get S \lt T; if S is longer, we get S \gt T.

Constraints

  • 1 \leq K \leq N \leq 100
  • K and N are integers.
  • S_i is a string of length 10 consisting of lowercase English letters.
  • S_i \neq S_j if i \neq j.

Input

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

N K
S_1
S_2
\vdots
S_N

Output

Print the nicknames, separated by newlines.

Sample Input 1

5 3
abc
aaaaa
xyz
a
def

Sample Output 1

aaaaa
abc
xyz

This contest had five participants. The participants ranked first, second, third, fourth, and fifth had the nicknames abc, aaaaa, xyz, a, and def, respectively.

The nicknames of the top three participants were abc, aaaaa, xyz, so print these in lexicographical order: aaaaa, abc, xyz.

Sample Input 2

4 4
z
zyx
zzz
rbg

Sample Output 2

rbg
z
zyx
zzz

Sample Input 3

3 1
abc
arc
agc

Sample Output 3

abc
D - Rotate

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 行 N 列のマス目が与えられます。上から i 行目、左から j 列目のマスには整数 A_{i,j} が書かれています。ここで、A_{i,j} は 0 か 1 であることが保証されます。

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目を出力してください。

ただし外側のマスとは、1 行目、N 行目、1 列目、N 列目のいずれか 1 つ以上に属するマスの集合のことを指します。

制約

  • 2 \le N \le 100
  • 0 \le A_{i,j} \le 1(1 \le i,j \le N)
  • 入力は全て整数

入力

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

出力

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目において、上から i 行目、左から j 列目のマスに書かれている整数を B_{i,j} と置く。このとき、以下の形式で出力せよ。

B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

入力例 1

4
0101
1101
1111
0000

出力例 1

1010
1101
0111
0001

上から i 行目、左から j 列目のマスを (i,j) と呼ぶこととします。

外側のマスは (1,1) から時計回りに列挙すると (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1),(2,1) の 12 個です。

これらのマスに書かれている整数を、時計回りに 1 個ずつ動かすと出力欄のようになります。

入力例 2

2
11
11

出力例 2

11
11

入力例 3

5
01010
01001
10110
00110
01010

出力例 3

00101
11000
00111
00110
10100

Score : 200 points

Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

  • 2 \le N \le 100
  • 0 \le A_{i,j} \le 1(1 \le i,j \le N)
  • All input values are integers.

Input

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

Output

Let B_{i,j} be the integer written on the square at the i-th row from the top and j-th column from the left in the grid resulting from shifting the outer squares clockwise by one square each. Print them in the following format:

B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

Sample Input 1

4
0101
1101
1111
0000

Sample Output 1

1010
1101
0111
0001

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.

Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

5
01010
01001
10110
00110
01010

Sample Output 3

00101
11000
00111
00110
10100
E - abc285_brutmhyhiizp

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

別世界の AtCoder で開催されている AtCoder Big Contest では、 10^{16} 問の問題が一度に出題されます。
問題の ID は 1 問目から順に A, B, ..., Z, AA, AB, ..., ZZ, AAA, ... と付けられています。

つまり、 ID は以下の順番で付けられています。

  • 長さ 1 の英大文字からなる文字列を辞書順に並べたもの
  • 長さ 2 の英大文字からなる文字列を辞書順に並べたもの
  • 長さ 3 の英大文字からなる文字列を辞書順に並べたもの
  • ...

このコンテストに含まれる問題の ID である文字列 S が与えられるので、それが何問目か答えてください。

制約

  • S は AtCoder Big Contest に含まれる問題の ID として正しい

入力

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

S

出力

答えを整数として出力せよ。

入力例 1

AB

出力例 1

28

ID が AB である問題は、 AtCoder Big Contest の 28 問目です。

入力例 2

C

出力例 2

3

ID が C である問題は、 AtCoder Big Contest の 3 問目です。

入力例 3

BRUTMHYHIIZP

出力例 3

10000000000000000

ID が BRUTMHYHIIZP である問題は、 AtCoder Big Contest の 10^{16} 問目、すなわち最終問題です。

Score : 300 points

Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

  • the strings of length 1 consisting of uppercase English letters, in lexicographical order;
  • the strings of length 2 consisting of uppercase English letters, in lexicographical order;
  • the strings of length 3 consisting of uppercase English letters, in lexicographical order;
  • ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

  • S is a valid ID of a problem given in AtCoder Big Contest.

Input

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

S

Output

Print the answer as an integer.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.