AtCoder Beginner Contest 080

A - Parking

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

駐車場があり、以下の二種類のプランのどちらかを選んで駐車できます。

プラン 1 : T 時間駐車した場合、A×T 円が駐車料金となる。
プラン 2 : 駐車した時間に関わらず B 円が駐車料金となる。

N 時間駐車するとき、駐車料金は最小でいくらになるか求めてください。

制約

1≦N≦20
1≦A≦100
1≦B≦2000
入力は全て整数

入力

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

N A B

出力

駐車料金が最小で x 円のとき、x を出力せよ。

入力例 1

7 17 120

出力例 1

プラン 1 を選んだ場合、駐車料金は 7×17=119 円になります、
プラン 2 を選んだ場合、駐車料金は 120 円になります。

よって、駐車料金は最小で 119 円です。

入力例 2

5 20 100

出力例 2

どちらのプランを選んでも駐車料金が変わらない場合もあります。

入力例 3

6 18 100

出力例 3

Score : 100 points

Problem Statement

You are parking at a parking lot. You can choose from the following two fee plans:

Plan 1: The fee will be A×T yen (the currency of Japan) when you park for T hours.
Plan 2: The fee will be B yen, regardless of the duration.

Find the minimum fee when you park for N hours.

Constraints

1≤N≤20
1≤A≤100
1≤B≤2000
All input values are integers.

Input

Input is given from Standard Input in the following format:

N A B

Output

When the minimum fee is x yen, print the value of x.

Sample Input 1

7 17 120

Sample Output 1

If you choose Plan 1, the fee will be 7×17=119 yen.
If you choose Plan 2, the fee will be 120 yen.

Thus, the minimum fee is 119 yen.

Sample Input 2

5 20 100

Sample Output 2

The fee might be the same in the two plans.

Sample Input 3

6 18 100

Sample Output 3

B - Harshad Number

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

整数 X を十進法で表したときの各桁の数字の和を f(X) としたとき、X が f(X) で割り切れる場合、X はハーシャッド数です。

整数 N が与えられるので、ハーシャッド数かどうか判定してください。

制約

1≦N≦10^8
入力は全て整数

入力

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

出力

N がハージャッド数ならば Yes を、そうでなければ No を出力せよ。

入力例 1

出力例 1

Yes

f(12)=1+2=3 より、12 は 3 で割り切れるので 12 はハーシャッド数です。

入力例 2

出力例 2

No

f(57)=5+7=12 より、57 は 12 で割り切れないので 57 はハーシャッド数ではありません。

入力例 3

出力例 3

No

Score : 200 points

Problem Statement

An integer X is called a Harshad number if X is divisible by f(X), where f(X) is the sum of the digits in X when written in base 10.

Given an integer N, determine whether it is a Harshad number.

Constraints

1?N?10^8
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print Yes if N is a Harshad number; print No otherwise.

Sample Input 1

Sample Output 1

Yes

f(12)=1+2=3. Since 12 is divisible by 3, 12 is a Harshad number.

Sample Input 2

Sample Output 2

No

f(57)=5+7=12. Since 57 is not divisible by 12, 12 is not a Harshad number.

Sample Input 3

Sample Output 3

No

C - Shopping Street

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

joisinoお姉ちゃんは、ある商店街に店を開こうとしています。

その商店街の店は、月曜日から金曜日の 5 つの曜日を午前と午後の 2 つの時間帯に分けて、これら 10 個の時間帯それぞれについて店を営業するか否かを決めることとなっています。ただし、1 つ以上の時間帯で店を営業しなければなりません。

商店街には既に N 個の店があり、1 から N までの番号がついています。

これらの店の営業時間の情報として F_{i,j,k} が与えられ、月曜日 = 曜日 1、火曜日 = 曜日 2、水曜日 = 曜日 3、木曜日 = 曜日 4、金曜日 = 曜日 5、午前 = 時間帯 1、午後 = 時間帯 2 と対応させたとき、F_{i,j,k}=1 なら曜日 j の時間帯 k に店 i が営業しており、F_{i,j,k}=0 なら営業していないことを意味します。

店 i とjoisinoお姉ちゃんの開く店の両方が営業している時間帯の個数を c_i としたとき、joisinoお姉ちゃんの店の利益は P_{1,c_1}+P_{2,c_2}+...+P_{N,c_N} となります。ただし、利益は負にもなりうることに注意してください。

1 つ以上の時間帯で店を営業しなければならないことに注意しつつ、10 個の時間帯それぞれについて店を営業するか否かを決めるとき、joisinoお姉ちゃんの店の利益のあり得る最大値を求めてください。

制約

1≦N≦100
0≦F_{i,j,k}≦1
1≦i≦N を満たす全ての整数 i に対して、F_{i,j,k}=1 を満たす (j,k) が必ず 1 つ以上存在する
-10^7≦P_{i,j}≦10^7
入力は全て整数

入力

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

N
F_{1,1,1} F_{1,1,2} ... F_{1,5,1} F_{1,5,2}
:
F_{N,1,1} F_{N,1,2} ... F_{N,5,1} F_{N,5,2}
P_{1,0} ... P_{1,10}
:
P_{N,0} ... P_{N,10}

出力

joisinoお姉ちゃんの店の利益のあり得る最大値が x のとき、x を出力せよ。

入力例 1

1
1 1 0 1 0 0 0 1 0 1
3 4 5 6 7 8 9 -2 -3 4 -2

出力例 1

店 1 が営業している時間帯のみに店を営業すると、利益 8 を得ることができ、利益が最大となります。

入力例 2

2
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1
0 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1
0 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1

出力例 2

-2

1 つ以上の時間帯で店を営業しなければならないことや、利益が負となる場合があることに注意してください。

入力例 3

3
1 1 1 1 1 1 0 0 1 1
0 1 0 1 1 1 1 0 1 0
1 0 1 1 0 1 0 1 0 1
-8 6 -2 -8 -8 4 8 7 -6 2 2
-9 2 0 1 7 -5 0 -2 -6 5 5
6 -6 7 -9 6 -5 8 0 -9 -7 -7

出力例 3

Score : 300 points

Problem Statement

Joisino is planning to open a shop in a shopping street.

Each of the five weekdays is divided into two periods, the morning and the evening. For each of those ten periods, a shop must be either open during the whole period, or closed during the whole period. Naturally, a shop must be open during at least one of those periods.

There are already N stores in the street, numbered 1 through N.

You are given information of the business hours of those shops, F_{i,j,k}. If F_{i,j,k}=1, Shop i is open during Period k on Day j (this notation is explained below); if F_{i,j,k}=0, Shop i is closed during that period. Here, the days of the week are denoted as follows. Monday: Day 1, Tuesday: Day 2, Wednesday: Day 3, Thursday: Day 4, Friday: Day 5. Also, the morning is denoted as Period 1, and the afternoon is denoted as Period 2.

Let c_i be the number of periods during which both Shop i and Joisino's shop are open. Then, the profit of Joisino's shop will be P_{1,c_1}+P_{2,c_2}+...+P_{N,c_N}.

Find the maximum possible profit of Joisino's shop when she decides whether her shop is open during each period, making sure that it is open during at least one period.

Constraints

1≤N≤100
0≤F_{i,j,k}≤1
For every integer i such that 1≤i≤N, there exists at least one pair (j,k) such that F_{i,j,k}=1.
-10^7≤P_{i,j}≤10^7
All input values are integers.

Input

Input is given from Standard Input in the following format:

N
F_{1,1,1} F_{1,1,2} ... F_{1,5,1} F_{1,5,2}
:
F_{N,1,1} F_{N,1,2} ... F_{N,5,1} F_{N,5,2}
P_{1,0} ... P_{1,10}
:
P_{N,0} ... P_{N,10}

Output

Print the maximum possible profit of Joisino's shop.

Sample Input 1

1
1 1 0 1 0 0 0 1 0 1
3 4 5 6 7 8 9 -2 -3 4 -2

Sample Output 1

If her shop is open only during the periods when Shop 1 is opened, the profit will be 8, which is the maximum possible profit.

Sample Input 2

2
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1
0 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1
0 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1

Sample Output 2

-2

Note that a shop must be open during at least one period, and the profit may be negative.

Sample Input 3

3
1 1 1 1 1 1 0 0 1 1
0 1 0 1 1 1 1 0 1 0
1 0 1 1 0 1 0 1 0 1
-8 6 -2 -8 -8 4 8 7 -6 2 2
-9 2 0 1 7 -5 0 -2 -6 5 5
6 -6 7 -9 6 -5 8 0 -9 -7 -7

Sample Output 3

D - Recording

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

joisinoお姉ちゃんは、録画機を用いて N 個のテレビ番組を録画しようとしています。

テレビが受信できるチャンネルは C 個あり、1 から C までの番号がついています。

joisinoお姉ちゃんの録画したいテレビ番組のうち、i 個目のテレビ番組は、時刻 s_i から時刻 t_i まで、チャンネル c_i で放送されます。(ただし時刻 s_i を含み、時刻 t_i を除く)

ただし、同じチャンネルで複数のテレビ番組が同時に放送されることはありません。

また、録画機は、あるチャンネルの時刻 S から時刻 T までを録画するとき、時刻 S-0.5 から時刻 T までの間、他のチャンネルの録画に使うことができません。(ただし時刻 S-0.5を含み、時刻 T を除く)

N 個のテレビ番組の全ての放送内容が含まれるように録画するとき、必要な録画機の最小個数を求めてください。

制約

1≦N≦10^5
1≦C≦30
1≦s_i<t_i≦10^5
1≦c_i≦C
c_i=c_j かつ i≠j ならば t_i≦s_j か s_i≧t_j が成り立つ
入力は全て整数

入力

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

N C
s_1 t_1 c_1
:
s_N t_N c_N

出力

必要な録画機の最小個数が x 個のとき、 x を出力せよ。

入力例 1

出力例 1

例えば、録画機 2 個を用いて、以下のように録画することができます。

1 個目の録画機を用いて、時刻 1 から時刻 7 までチャンネル 2 を録画します。このとき、1 個目のテレビ番組が録画されます。また、時刻 0.5 から時刻 7 まではこの録画機を他のチャンネルの録画に使えないことに注意してください。
2 個目の録画機を用いて、時刻 7 から時刻 12 までチャンネル 1 を録画します。このとき、 2 個目と 3 個目のテレビ番組が録画されます。また、時刻 6.5 から時刻 12 まではこの録画機を他のチャンネルの録画に使えないことに注意してください。

入力例 2

出力例 2

録画するテレビ番組がないチャンネルがある場合もあります。

入力例 3

出力例 3

Score : 400 points

Problem Statement

Joisino is planning to record N TV programs with recorders.

The TV can receive C channels numbered 1 through C.

The i-th program that she wants to record will be broadcast from time s_i to time t_i (including time s_i but not t_i) on Channel c_i.

Here, there will never be more than one program that are broadcast on the same channel at the same time.

When the recorder is recording a channel from time S to time T (including time S but not T), it cannot record other channels from time S-0.5 to time T (including time S-0.5 but not T).

Find the minimum number of recorders required to record the channels so that all the N programs are completely recorded.

Constraints

1≤N≤10^5
1≤C≤30
1≤s_i<t_i≤10^5
1≤c_i≤C
If c_i=c_j and i≠j, either t_i≤s_j or s_i≥t_j.
All input values are integers.

Input

Input is given from Standard Input in the following format:

N C
s_1 t_1 c_1
:
s_N t_N c_N

Output

When the minimum required number of recorders is x, print the value of x.

Sample Input 1

Sample Output 1

Two recorders can record all the programs, for example, as follows:

With the first recorder, record Channel 2 from time 1 to time 7. The first program will be recorded. Note that this recorder will be unable to record other channels from time 0.5 to time 7.
With the second recorder, record Channel 1 from time 7 to time 12. The second and third programs will be recorded. Note that this recorder will be unable to record other channels from time 6.5 to time 12.

Sample Input 2

Sample Output 2

There may be a channel where there is no program to record.

Sample Input 3