AtCoder Beginner Contest 089

A - Grouping 2

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

ある学校には、N 人の生徒がいます。

生徒たちをいくつかのグループに分け、グループごとにあるテーマについて話し合ってもらうこととなりました。

あなたは、2 人以下のグループだと効果的な話し合いが出来ないと考えており、なるだけ多くのグループを 3 人以上にしたいです。

生徒たちを上手く分けて、3 人以上のグループの数を最大化してください。

制約

1 \leq N \leq 1000
入力は全て整数

入力

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

出力

3 人以上のグループを最大で x 個作れるとき、x を出力せよ。

入力例 1

出力例 1

例えば、3 人のグループと 5 人のグループに分けるとよいです。

入力例 2

出力例 2

どのように生徒たちを分けても 3 人以上のグループを作れない場合もあります。

入力例 3

出力例 3

Score : 100 points

Problem Statement

There are N students in a school.

We will divide these students into some groups, and in each group they will discuss some themes.

You think that groups consisting of two or less students cannot have an effective discussion, so you want to have as many groups consisting of three or more students as possible.

Divide the students so that the number of groups consisting of three or more students is maximized.

Constraints

1 \leq N \leq 1000
All input values are integers.

Input

Input is given from Standard Input in the following format:

Output

If you can form at most x groups consisting of three or more students, print x.

Sample Input 1

Sample Output 1

For example, you can form a group of three students and another of five students.

Sample Input 2

Sample Output 2

Sometimes you cannot form any group consisting of three or more students, regardless of how you divide the students.

Sample Input 3

Sample Output 3

B - Hina Arare

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

日本では、3 月 3 日にひなあられという、色のついたお菓子をお供えする習慣があります。

1 つの袋があり、ひなあられが N 個入っています。

この袋には、桃色、白色、緑色の 3 種類か、桃色、白色、緑色、黄色の 4 種類のひなあられが入っていることが分かっています。

桃色を P、白色を W、緑色を G、黄色を Y と表したとき、袋からひなあられを 1 粒ずつ取り出していったところ、i 番目に取り出したひなあられの色は S_i でした。

この袋に 3 種類のひなあられが入っていた場合は Three、4 種類のひなあられが入っていた場合は Four と出力してください。

制約

1 \leq N \leq 100
S_i は P か W か G か Y
S_i=P、S_j=W、S_k=G を満たす i,j,k が必ず存在する

入力

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

N
S_1 S_2 ... S_N

出力

袋に 3 種類のひなあられが入っていた場合は Three、4 種類のひなあられが入っていた場合は Four と出力せよ。

入力例 1

6
G W Y P Y W

出力例 1

Four

袋に 4 種類のひなあられが入っていたので Four と出力するとよいです。

入力例 2

9
G W W G P W P G G

出力例 2

Three

袋に 3 種類のひなあられが入っていたので Three と出力するとよいです。

入力例 3

8
P Y W G Y W Y Y

出力例 3

Four

Score : 200 points

Problem Statement

In Japan, people make offerings called hina arare, colorful crackers, on March 3.

We have a bag that contains N hina arare. (From here, we call them arare.)

It is known that the bag either contains arare in three colors: pink, white and green, or contains arare in four colors: pink, white, green and yellow.

We have taken out the arare in the bag one by one, and the color of the i-th arare was S_i, where colors are represented as follows - pink: P, white: W, green: G, yellow: Y.

If the number of colors of the arare in the bag was three, print Three; if the number of colors was four, print Four.

Constraints

1 \leq N \leq 100
S_i is P, W, G or Y.
There always exist i, j and k such that S_i=P, S_j=W and S_k=G.

Input

Input is given from Standard Input in the following format:

N
S_1 S_2 ... S_N

Output

If the number of colors of the arare in the bag was three, print Three; if the number of colors was four, print Four.

Sample Input 1

6
G W Y P Y W

Sample Output 1

Four

The bag contained arare in four colors, so you should print Four.

Sample Input 2

9
G W W G P W P G G

Sample Output 2

Three

The bag contained arare in three colors, so you should print Three.

Sample Input 3

8
P Y W G Y W Y Y

Sample Output 3

Four

C - March

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

N 人の人がいて、i 番目の人の名前は S_i です。

この中から、以下の条件を満たすように 3 人を選びたいです。

全ての人の名前が M,A,R,C,H のどれかから始まっている
同じ文字から始まる名前を持つ人が複数いない

これらの条件を満たすように 3 人を選ぶ方法が何通りあるか、求めてください。ただし、選ぶ順番は考えません。

答えが 32 bit整数型に収まらない場合に注意してください。

制約

1 \leq N \leq 10^5
S_i は英大文字からなる
1 \leq |S_i| \leq 10
S_i \neq S_j (i \neq j)

入力

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

N
S_1
:
S_N

出力

与えられた条件を満たすように 3 人を選ぶ方法が x 通りのとき、x を出力せよ。

入力例 1

5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI

出力例 1

次のような名前の 3 人を選ぶと良いです。

MASHIKE,RUMOI,HABORO
MASHIKE,RUMOI,HOROKANAI

よって、2 通りとなります。

入力例 2

4
ZZ
ZZZ
Z
ZZZZZZZZZZ

出力例 2

与えられた条件を満たすように 3 人を選ぶ方法が存在しない場合に注意してください。

入力例 3

5
CHOKUDAI
RNG
MAKOTO
AOKI
RINGO

出力例 3

Score : 300 points

Problem Statement

There are N people. The name of the i-th person is S_i.

We would like to choose three people so that the following conditions are met:

The name of every chosen person begins with M, A, R, C or H.
There are no multiple people whose names begin with the same letter.

How many such ways are there to choose three people, disregarding order?

Note that the answer may not fit into a 32-bit integer type.

Constraints

1 \leq N \leq 10^5
S_i consists of uppercase English letters.
1 \leq |S_i| \leq 10
S_i \neq S_j (i \neq j)

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

If there are x ways to choose three people so that the given conditions are met, print x.

Sample Input 1

5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI

Sample Output 1

We can choose three people with the following names:

MASHIKE, RUMOI, HABORO
MASHIKE, RUMOI, HOROKANAI

Thus, we have two ways.

Sample Input 2

4
ZZ
ZZZ
Z
ZZZZZZZZZZ

Sample Output 2

Note that there may be no ways to choose three people so that the given conditions are met.

Sample Input 3

5
CHOKUDAI
RNG
MAKOTO
AOKI
RINGO

Sample Output 3

D - Practical Skill Test

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

H 行 W 列のマス目があり、i 行目の j 列目のマスをマス (i,j) と呼びます。

このマス目には 1 から H×W までの整数が重複なく書かれており、マス (i,j) に書かれている整数は A_{i,j} です。

魔法少女であるあなたは、魔力 |x-i|+|y-j| を消費することでマス (i,j) に置かれた駒をマス (x,y) に瞬間移動させることができます。

あなたは、魔法少女としての能力を計るために、Q 回の実技試験を受けなければなりません。

i 回目の実技試験は、以下の手順で行われます。

初めに、駒が整数 L_i の書かれているマスに置かれている。
駒の置かれているマスに書かれている整数を x とする。x が R_i でない限り、駒を x+D の書かれているマスに移動することを繰り返す。x=R_i となったら終了する。
ただし、R_i-L_i が D の倍数であることは保証される。

それぞれの実技試験に対し、あなたの消費する魔力の総和を求めてください。

制約

1 \leq H,W \leq 300
1 \leq D \leq H×W
1 \leq A_{i,j} \leq H×W
A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))
1 \leq Q \leq 10^5
1 \leq L_i \leq R_i \leq H×W
(R_i-L_i) は D の倍数

入力

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

H W D
A_{1,1} A_{1,2} ... A_{1,W}
:
A_{H,1} A_{H,2} ... A_{H,W}
Q
L_1 R_1
:
L_Q R_Q

出力

それぞれの実技試験に対し、あなたの消費する魔力の総和を出力せよ。

ただし、出力する順番は実技試験の行われる順とすること。

入力例 1

出力例 1

4 が書かれたマスは、マス (1,2) です。
6 が書かれたマスは、マス (3,3) です。
8 が書かれたマスは、マス (3,1) です。

よって、1 回目の実技試験であなたの消費する魔力の総和は、(|3-1|+|3-2|)+(|3-3|+|1-3|)=5 です。

入力例 2

出力例 2

0
0

駒を全く移動しない実技試験が存在する場合や、複数の実技試験の内容が同じ場合に注意してください。

入力例 3

5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13

出力例 3

0
5
0

Score : 400 points

Problem Statement

We have a grid with H rows and W columns. The square at the i-th row and the j-th column will be called Square (i,j).

The integers from 1 through H×W are written throughout the grid, and the integer written in Square (i,j) is A_{i,j}.

You, a magical girl, can teleport a piece placed on Square (i,j) to Square (x,y) by consuming |x-i|+|y-j| magic points.

You now have to take Q practical tests of your ability as a magical girl.

The i-th test will be conducted as follows:

Initially, a piece is placed on the square where the integer L_i is written.
Let x be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer x+D is written, as long as x is not R_i. The test ends when x=R_i.
Here, it is guaranteed that R_i-L_i is a multiple of D.

For each test, find the sum of magic points consumed during that test.

Constraints

1 \leq H,W \leq 300
1 \leq D \leq H×W
1 \leq A_{i,j} \leq H×W
A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))
1 \leq Q \leq 10^5
1 \leq L_i \leq R_i \leq H×W
(R_i-L_i) is a multiple of D.

Input

Input is given from Standard Input in the following format:

H W D
A_{1,1} A_{1,2} ... A_{1,W}
:
A_{H,1} A_{H,2} ... A_{H,W}
Q
L_1 R_1
:
L_Q R_Q

Output

For each test, print the sum of magic points consumed during that test.

Output should be in the order the tests are conducted.

Sample Input 1

Sample Output 1

4 is written in Square (1,2).
6 is written in Square (3,3).
8 is written in Square (3,1).

Thus, the sum of magic points consumed during the first test is (|3-1|+|3-2|)+(|3-3|+|1-3|)=5.

Sample Input 2

Sample Output 2

0
0

Note that there may be a test where the piece is not moved at all, and there may be multiple identical tests.

Sample Input 3

5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13

Sample Output 3

0
5
0