AtCoder Beginner Contest 073

A - September 9

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

今、日本は 9 月 9 日です。二桁の整数 N が与えられるので、十進法で N に 9 が含まれるか答えてください。

制約

10≦N≦99

入力

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

出力

9 が含まれるとき Yes 、含まれないとき No を出力せよ。

入力例 1

出力例 1

Yes

29 の一の位は 9 です。

入力例 2

出力例 2

No

72 に 9 は含まれません。

入力例 3

出力例 3

Yes

Score : 100 points

Problem Statement

It is September 9 in Japan now.

You are given a two-digit integer N. Answer the question: Is 9 contained in the decimal notation of N?

Constraints

10≤N≤99

Input

Input is given from Standard Input in the following format:

Output

If 9 is contained in the decimal notation of N, print Yes; if not, print No.

Sample Input 1

Sample Output 1

Yes

The one's digit of 29 is 9.

Sample Input 2

Sample Output 2

No

72 does not contain 9.

Sample Input 3

Sample Output 3

Yes

B - Theater

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

joisinoお姉ちゃんは、劇場の受付を担当しています。

この劇場には、席 1 から席 100000 までの、100000 個の席があります。

彼女のメモ書きによると、今までの間に N 組の団体が来て、i 組目の団体は席 l_i から席 r_i までの連続した席に座っています。

今、劇場の席には何人座っているか求めてください。

制約

1≦N≦1000
1≦l_i≦r_i≦100000
同じ席に複数の人が座ることはない。
入力は全て整数である。

入力

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

N
l_1 r_1
:
l_N r_N

出力

劇場の席に座っている人数を出力せよ。

入力例 1

1
24 30

出力例 1

24,25,26,27,28,29,30 番の席に人が座っており、 7 人です。

入力例 2

2
6 8
3 3

出力例 2

Score : 200 points

Problem Statement

Joisino is working as a receptionist at a theater.

The theater has 100000 seats, numbered from 1 to 100000.

According to her memo, N groups of audiences have come so far, and the i-th group occupies the consecutive seats from Seat l_i to Seat r_i (inclusive).

How many people are sitting at the theater now?

Constraints

1≤N≤1000
1≤l_i≤r_i≤100000
No seat is occupied by more than one person.
All input values are integers.

Input

Input is given from Standard Input in the following format:

N
l_1 r_1
:
l_N r_N

Output

Print the number of people sitting at the theater.

Sample Input 1

1
24 30

Sample Output 1

There are 7 people, sitting at Seat 24,25,26,27,28,29 and 30.

Sample Input 2

2
6 8
3 3

Sample Output 2

C - Write and Erase

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

あなたは、joisinoお姉ちゃんと以下のようなゲームをしています。

最初、何も書いていない紙がある。
joisinoお姉ちゃんが一つの数字を言うので、その数字が紙に書いてあれば紙からその数字を消し、書いていなければその数字を紙に書く。これを N 回繰り返す。
その後、紙に書かれている数字がいくつあるかを答える。

joisinoお姉ちゃんが言った数字が、言った順番に A_1, ... ,A_N として与えられるので、ゲーム終了後に紙に書かれている数字がいくつあるか答えてください。

制約

1≦N≦100000
1≦A_i≦1000000000(=10^9)
入力は全て整数である。

入力

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

N
A_1
:
A_N

出力

ゲーム終了後に紙に書かれている数字の個数を出力せよ。

入力例 1

出力例 1

以下の操作を行うこととなります。

紙に 6 は書かれていないので、6 を書く。
紙に 2 は書かれていないので、2 を書く。
紙に 6 は書かれているので、6 を消す。

よって、最後に書いてあるのは 2 だけなので、答えは 1 です。

入力例 2

出力例 2

最後に紙に数字が一つも書かれていない場合もあります。

入力例 3

出力例 3

Score : 300 points

Problem Statement

You are playing the following game with Joisino.

Initially, you have a blank sheet of paper.
Joisino announces a number. If that number is written on the sheet, erase the number from the sheet; if not, write the number on the sheet. This process is repeated N times.
Then, you are asked a question: How many numbers are written on the sheet now?

The numbers announced by Joisino are given as A_1, ... ,A_N in the order she announces them. How many numbers will be written on the sheet at the end of the game?

Constraints

1≤N≤100000
1≤A_i≤1000000000(=10^9)
All input values are integers.

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print how many numbers will be written on the sheet at the end of the game.

Sample Input 1

Sample Output 1

The game proceeds as follows:

6 is not written on the sheet, so write 6.
2 is not written on the sheet, so write 2.
6 is written on the sheet, so erase 6.

Thus, the sheet contains only 2 in the end. The answer is 1.

Sample Input 2

Sample Output 2

It is possible that no number is written on the sheet in the end.

Sample Input 3

Sample Output 3

D - joisino's travel

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

Atcoder国には N 個の町があり、M 本の双方向に移動可能な道で結ばれています。

また、 i 本目の道は町 A_i と町 B_i の間を距離 C_i で結んでいます。

joisinoお姉ちゃんは、この国の R 個の町 r_1,r_2..r_R を訪れることとなりました。

最初に訪れる町までの移動と、最後に訪れる町からの移動は空路で行うが、それ以外は道を使わなければなりません。

町を訪れる順番を、道での移動距離が最小となるように決めた時の移動距離を答えてください。

制約

2≦N≦200
1≦M≦N×(N-1)/2
2≦R≦min(8,N) ( min(8,N) は 8 と N のうち小さい方)
r_i≠r_j (i≠j)
1≦A_i,B_i≦N , A_i≠B_i
(A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j)
1≦C_i≦100000
すべての町の間は道のみで移動することができる。
入力は全て整数である。

入力

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

N M R
r_1 ... r_R
A_1 B_1 C_1
:
A_M B_M C_M

出力

町を訪れる順番を、道での移動距離が最小となるように決めた時の移動距離を出力せよ。

入力例 1

出力例 1

例えば、町 1 ,町 2 ,町 3 の順番で訪れると、移動距離が 2 となり、最小となります。

入力例 2

出力例 2

町 1 を訪れたあとに町 3 を訪れても、町 3 を訪れたあとに町 1 を訪れても、町 1 と町 3 の間の最短距離は 4 であるため、どの順番を選んだとしても答えは 4 となります。

入力例 3

出力例 3

Score : 400 points

Problem Statement

There are N towns in the State of Atcoder, connected by M bidirectional roads.

The i-th road connects Town A_i and B_i and has a length of C_i.

Joisino is visiting R towns in the state, r_1,r_2,..,r_R (not necessarily in this order).

She will fly to the first town she visits, and fly back from the last town she visits, but for the rest of the trip she will have to travel by road.

If she visits the towns in the order that minimizes the distance traveled by road, what will that distance be?

Constraints

2≤N≤200
1≤M≤N×(N-1)/2
2≤R≤min(8,N) (min(8,N) is the smaller of 8 and N.)
r_i≠r_j (i≠j)
1≤A_i,B_i≤N, A_i≠B_i
(A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j)
1≤C_i≤100000
Every town can be reached from every town by road.
All input values are integers.

Input

Input is given from Standard Input in the following format:

N M R
r_1 ... r_R
A_1 B_1 C_1
:
A_M B_M C_M

Output

Print the distance traveled by road if Joisino visits the towns in the order that minimizes it.

Sample Input 1

Sample Output 1

For example, if she visits the towns in the order of 1, 2, 3, the distance traveled will be 2, which is the minimum possible.

Sample Input 2

Sample Output 2

The shortest distance between Towns 1 and 3 is 4. Thus, whether she visits Town 1 or 3 first, the distance traveled will be 4.

Sample Input 3