Panasonic Programming Contest (AtCoder Beginner Contest 195)

A - Health M Death

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

魔法使いの高橋君がモンスターと戦っています。

高橋君が魔法を使うと、体力が M の倍数であるモンスターを倒すことができます。体力が M の倍数でないモンスターに対しては何の効果もありません。

高橋君の魔法によって、体力が H のモンスターを倒すことができるでしょうか？

制約

1 \leq M \leq 1000
1 \leq H \leq 1000
M 及び H は整数

入力

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

M H

出力

魔法でモンスターを倒すことができるなら Yes を、できないなら No を出力せよ。

入力例 1

10 120

出力例 1

Yes

高橋君の魔法は、体力が 10 の倍数であるモンスターを倒すことができます。

120 は 10 の倍数なので、体力が 120 のモンスターは倒すことができます。

入力例 2

10 125

出力例 2

No

125 は 10 の倍数ではないので、体力が 125 のモンスターは倒すことはできません。

Score : 100 points

Problem Statement

Takahashi, the magician, is fighting with a monster.

His magic can defeat a monster whose health is a multiple of M. It has no effect on a monster whose health is not a multiple of M.

Can his magic defeat a monster whose health is H?

Constraints

1 \leq M \leq 1000
1 \leq H \leq 1000
M and H are integers.

Input

Input is given from Standard Input in the following format:

M H

Output

If Takahashi's magic can defeat the monster, print Yes; otherwise, print No.

Sample Input 1

10 120

Sample Output 1

Yes

Takahashi's magic can defeat a monster whose health is a multiple of 10.

120 is a multiple of 10, so his magic can defeat the monster with health 120.

Sample Input 2

10 125

Sample Output 2

No

125 is not a multiple of 10, so his magic cannot defeat the monster with health 125.

B - Many Oranges

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

みかんがたくさんあります。どのみかんの重さも A グラム以上 B グラム以下であることがわかっています。（みかんの重さは整数とは限りません。）

この中からいくつかのみかんを選んだところ、選んだみかんの重さの合計がちょうど W キログラムになりました。

選んだみかんの個数として考えられる最小値と最大値を求めてください。ただし、このようなことが起こり得ないなら、かわりにそのことを報告してください。

制約

1 \leq A \leq B \leq 1000
1 \leq W \leq 1000
入力は全て整数

入力

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

A B W

出力

選んだみかんの個数としてありえる最小値と最大値を空白区切りでこの順に出力せよ。ただし、与えられた条件に合うような個数が存在しない場合、かわりに UNSATISFIABLE と出力せよ。

入力例 1

100 200 2

出力例 1

10 20

みかん 1 個の重さは 100 グラム以上 200 グラム以下です。

200 グラムのみかんを 10 個選んだとき、重さの合計はちょうど 2 キログラムになります
100 グラムのみかんを 20 個選んだとき、重さの合計はちょうど 2 キログラムになります

9 個以下または 21 個以上でちょうど 2 キログラムになることはないので、10 個と 20 個がそれぞれ最小値と最大値になります。

入力例 2

120 150 2

出力例 2

14 16

みかん 1 個の重さは 120 グラム以上 150 グラム以下です。

例えば 140 グラムのみかん 10 個と、150 グラムのみかん 4 個を選んだとき、重さの合計はちょうど 2 キログラムになります
例えば 120 グラムのみかん 8 個と、130 グラムのみかん 8 個を選んだとき、重さの合計はちょうど 2 キログラムになります

13 個以下または 17 個以上でちょうど 2 キログラムになることはないので、14 個と 16 個がそれぞれ最小値と最大値になります。

入力例 3

300 333 1

出力例 3

UNSATISFIABLE

みかん 1 個の重さは 300 グラム以上 333 グラム以下です。

このようなみかんいくつかの重さの合計がちょうど 1 キログラムになることはありえません。

Score : 200 points

Problem Statement

We have many oranges. It is known that every orange weighs between A and B grams, inclusive. (An orange can have a non-integer weight.)

We chose some of those oranges, and their total weight was exactly W kilograms.

Find the minimum and maximum possible numbers of oranges chosen. If no set of oranges can weigh exactly W kilograms in total, report that fact.

Constraints

1 \leq A \leq B \leq 1000
1 \leq W \leq 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B W

Output

Print the minimum and maximum possible numbers of oranges chosen, in this order, with space in between. If there is no number of oranges that can have the specified total weight, print UNSATISFIABLE instead.

Sample Input 1

100 200 2

Sample Output 1

10 20

Here, one range weighs between 100 and 200 grams (inclusive).

If we choose 10 200-gram oranges, their total weight will be exactly 2 kilograms.
If we choose 20 100-gram oranges, their total weight will be exactly 2 kilograms.

With less than 10 oranges or more than 20 oranges, the total weight will never be exactly 2 kilograms, so the minimum and maximum possible numbers of oranges chosen are 10 and 20, respectively.

Sample Input 2

120 150 2

Sample Output 2

14 16

Here, one range weighs between 120 and 150 grams (inclusive).

If we choose 10 140-gram oranges and 4 150-gram oranges, for example, their total weight will be exactly 2 kilograms.
If we choose 8 120-gram oranges and 8 130-gram oranges, for example, their total weight will be exactly 2 kilograms.

With less than 14 oranges or more than 16 oranges, the total weight will never be exactly 2 kilograms, so the minimum and maximum possible numbers of oranges chosen are 14 and 16, respectively.

Sample Input 3

300 333 1

Sample Output 3

UNSATISFIABLE

Here, one range weighs between 300 and 333 grams (inclusive).

No set of oranges of this kind can weigh exactly 1 kilograms in total.

C - Comma

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

高橋君は整数を書くとき、下から 3 桁ごとにコンマで区切って書きます。例えば 1234567 であれば 1,234,567、777 であれば 777 と書きます。

高橋君が 1 以上 N 以下の整数を 1 度ずつ書くとき、コンマは合計で何回書かれますか？

制約

1 \leq N \leq 10^{15}
N は整数

入力

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

出力

コンマが書かれる回数の合計を出力せよ。

入力例 1

出力例 1

999 以下の数を書くときにはコンマは書かれません。1000 以上 1010 以下の数を書くときには、それぞれ 1 回ずつコンマが書かれます。

よって、コンマは全部で 11 回書かれます。

入力例 2

27182818284590

出力例 2

107730272137364

Score : 300 points

Problem Statement

When Takahashi writes an integer, he uses a comma every third digit from the right. For example, 1234567 is written as 1,234,567, and 777 is written as 777.

How many commas will be used in total when he writes each integer from 1 through N once?

Constraints

1 \leq N \leq 10^{15}
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the total number of commas.

Sample Input 1

Sample Output 1

No comma is used in writing 999 or smaller numbers. One comma is used in writing each of the numbers from 1000 through 1010.

Thus, 11 commas are used in total.

Sample Input 2

27182818284590

Sample Output 2

107730272137364

D - Shipping Center

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

1 から N の番号がついた N 個の荷物と、1 から M の番号がついた M 個の箱があります。

荷物 i の大きさは W_i で、価値は V_i です。

箱 i には大きさが X_i 以下の荷物を入れることができます。1 つの箱に 2 つ以上の荷物を入れることはできません。

Q 個のクエリが与えられます。各クエリでは 2 つの整数 L,R が与えられるので、次の問題を解いてください。

問題：M 個の箱のうち、箱 L,L+1,\ldots,R の R-L+1 個の箱が使えなくなってしまいました。残りの箱の中に同時に入れることができる荷物の価値の合計の最大値を求めてください。

制約

1 \leq N \leq 50
1 \leq M \leq 50
1 \leq Q \leq 50
1 \leq W_i \leq 10^6
1 \leq V_i \leq 10^6
1 \leq X_i \leq 10^6
1 \leq L \leq R \leq M
入力は全て整数

入力

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

N M Q
W_1 V_1
\vdots
W_N V_N
X_1 \ldots X_M
\mathrm{Query}_1
\vdots
\mathrm{Query}_Q

各クエリは以下の形式で与えられる。

L R

出力

Q 行出力せよ。

i 行目には、\mathrm{Query}_i に対応する問題の答えを出力せよ。

入力例 1

出力例 1

20
0
9

1 番目のクエリでは箱 4 が使えません。箱 1 に荷物 1 を、箱 2 に荷物 3 を、箱 3 に荷物 2 を入れることで、全ての荷物を箱の中に入れることができ、箱の中の荷物の価値の合計を 20 にすることができます。

2 番目のクエリでは全ての箱が使えません。したがって、答えは 0 です。

3 番目のクエリでは、箱 4 だけが使えます。箱 4 に荷物 1 を入れることで、箱の中の荷物の価値の合計は 9 となり、これが最大です。

Score : 400 points

Problem Statement

We have N pieces of baggage called Baggage 1 through N, and M boxes called Box 1 through M.

Baggage i has a size of W_i and a value of V_i.

Box i can contain a piece of baggage whose size of at most X_i. It cannot contain two or more pieces of baggage.

You will be given Q queries. In each query, given two integers L and R, solve the following problem:

Problem: Out of the M boxes, R-L+1 boxes, Box L,L+1,\ldots,R, have become unavailable. Find the maximum possible total value of a set of baggage that we can put into the remaining boxes simultaneously.

Constraints

1 \leq N \leq 50
1 \leq M \leq 50
1 \leq Q \leq 50
1 \leq W_i \leq 10^6
1 \leq V_i \leq 10^6
1 \leq X_i \leq 10^6
1 \leq L \leq R \leq M
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M Q
W_1 V_1
\vdots
W_N V_N
X_1 \ldots X_M
\mathrm{Query}_1
\vdots
\mathrm{Query}_Q

Each Query is in the following format:

L R

Output

Print Q lines.

The i-th line should contain the answer to the problem described by \mathrm{Query}_i.

Sample Input 1

Sample Output 1

20
0
9

In the 1-st query, only Box 4 is unavailable. By putting Baggage 1 into Box 1, Baggage 3 into Box 2, and Baggage 2 into Box 3, we can put all baggage into boxes, making the total value of baggage in boxes 20.

In the 2-nd query, all boxes are unavailable; the answer is 0.

In the 3-rd query, only Box 4 is available. By putting Baggage 1 into Box 4, we can make the total value of baggage in boxes 9, which is the maximum possible result.

E - Lucky 7 Battle

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

0,\ldots,9 からなる長さ N の文字列 S と、A,T からなる長さ N の文字列 X が与えられます。また、空文字列で初期化された文字列 T があります。

高橋君と青木君がこれらを使ってゲームをします。ゲームは N ラウンドからなり、i 回目 (1\leq i \leq N) のラウンドでは次の操作が行われます。

X_i が A なら青木君が、T なら高橋君が以下の操作を行う
操作：T の末尾に S_i か 0 のどちらか一方を加える

N 回の操作が終了したあと、T は 0,\ldots,9 からなる長さ N の文字列となります。 T を (先頭の余計な 0 を取り除いた上で) 10 進法で表された数と解釈したとき、7 の倍数であれば高橋君の勝ちであり、そうでなければ青木君の勝ちです。

2 人が最適に行動する時、どちらが勝つか判定してください。

制約

1 \leq N \leq 2\times 10^5
S,X の長さは N
S は 0,\ldots,9 のみからなる
X は A,T のみからなる

入力

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

N
S
X

出力

2 人が最適に行動する時、高橋君が勝つなら Takahashi、青木君が勝つなら Aoki と出力せよ。

入力例 1

2
35
AT

出力例 1

Takahashi

1 回目のラウンドでは青木君が 3 か 0 を T の末尾に加え、2 回目のラウンドでは高橋君が 5 か 0 を T の末尾に加えます。

青木君が 3 を加えた場合、高橋君が 5 を追加すると T は 35 となり、これは 7 の倍数です。

青木君が 0 を加えた場合、高橋君が 0 を追加すると T は 00 となり、これは 7 の倍数です。

したがって、かならず高橋君が勝ちます。

入力例 2

5
12345
AAAAT

出力例 2

Aoki

入力例 3

5
67890
TTTTA

出力例 3

Takahashi

入力例 4

5
12345
ATATA

出力例 4

Aoki

Score : 500 points

Problem Statement

We have a string S of length N consisting of 0, \ldots, 9, and a string X of length N consisting of A and T. Additionally, there is a string T, which is initialized to an empty string.

Takahashi and Aoki will play a game using these. The game consists of N rounds. In the i-th round (1\leq i \leq N), the following happens:

If X_i is A, Aoki does the operation below; if X_i is T, Takahashi does it.
Operation: append S_i or 0 at the end of T.

After N operations, T will be a string of length N consisting of 0, \ldots, 9. If T is a multiple of 7 as a base-ten number (after removing leading zeros), Takahashi wins; otherwise, Aoki wins.

Determine the winner of the game when the two players play optimally.

Constraints

1 \leq N \leq 2\times 10^5
S and X have a length of N each.
S consists of 0, \ldots, 9.
X consists of A and T.

Input

Input is given from Standard Input in the following format:

N
S
X

Output

If Takahashi wins when the two players play optimally, print Takahashi; if Aoki wins, print Aoki.

Sample Input 1

2
35
AT

Sample Output 1

Takahashi

In the 1-st round, Aoki appends 3 or 0 at the end of T. In the 2-nd round, Takahashi appends 5 or 0 at the end of T.

If Aoki appends 3, Takahashi can append 5 to make T 35, a multiple of 7.

If Aoki appends 0, Takahashi can append 0 to make T 00, a multiple of 7.

Thus, Takahashi can always win.

Sample Input 2

5
12345
AAAAT

Sample Output 2

Aoki

Sample Input 3

5
67890
TTTTA

Sample Output 3

Takahashi

Sample Input 4

5
12345
ATATA

Sample Output 4

Aoki

F - Coprime Present

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

あなたは A 以上 B 以下の整数が書かれたカードを各 1 枚、合計 B-A+1 枚持っています。この中から何枚かを選んで (0 枚でもよい) ペットのすぬけ君にプレゼントしようと考えています。

すぬけ君は、プレゼントされたカードたちについて、どの相異なる 2 枚に書かれた数も互いに素であるときに喜び、そうでないとき悲しみます。

すぬけ君が喜ぶようなカードの組合せは何通りありますか？

制約

1 \leq A \leq B \leq 10^{18}
B-A \leq 72
入力は全て整数

入力

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

A B

出力

すぬけ君が喜ぶようなカードの組合せは何通りあるか出力せよ。 なお、制約の条件下で答えは 2^{63} 未満になることが証明される。

入力例 1

2 4

出力例 1

あなたは 2,3,4 が書かれたカードを 1 枚ずつ持っています。すぬけ君が喜ぶようなカードの組合せは

\{\}
\{2\}
\{3\}
\{4\}
\{2,3\}
\{3,4\}

の 6 通りです。

入力例 2

1 1

出力例 2

すぬけ君が喜ぶようなカードの組合せは

\{\}
\{1\}

の 2 通りです。

入力例 3

123456789000 123456789050

出力例 3

Score : 600 points

Problem Statement

You have B-A+1 cards: for each integer from A through B, you have one card with that integer written on it. You will give some of them (possibly none) to your pet, Snuke.

Snuke will be happy if, for every pair of different cards, the numbers written on them are pairwise coprime; otherwise, he will be sad.

How many sets of cards will make Snuke happy?

Constraints

1 \leq A \leq B \leq 10^{18}
B-A \leq 72
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B

Output

Print the number of sets of cards that will make Snuke happy. The constraints guarantee that the answer is less than 2^{63}.

Sample Input 1

2 4

Sample Output 1

You have three cards with 2, 3, and 4 written on them. The following six sets of cards will make Snuke happy:

\{\}
\{2\}
\{3\}
\{4\}
\{2,3\}
\{3,4\}

Sample Input 2

1 1

Sample Output 2

The following two sets of cards will make Snuke happy:

\{\}
\{1\}

Sample Input 3

123456789000 123456789050