A - Not Too Hard

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 問の問題が出題されるプログラミングコンテストがあります。 i = 1, 2, \ldots, N について、i 問目の配点は S_i です。

配点が X 以下である問題すべての配点の合計を出力してください。

制約

  • 入力される値は全て整数
  • 4 \leq N \leq 8
  • 100 \leq S_i \leq 675
  • 100 \leq X \leq 675

入力

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

N X
S_1 S_2 \ldots S_N

出力

答えを出力せよ。


入力例 1

6 200
100 675 201 200 199 328

出力例 1

499

配点が 200 以下である問題は、1, 4, 5 問目の全 3 問であり、それらの配点の合計は S_1 + S_4 + S_5 = 100 + 200 + 199 = 499 です。


入力例 2

8 675
675 675 675 675 675 675 675 675

出力例 2

5400

入力例 3

8 674
675 675 675 675 675 675 675 675

出力例 3

0

Score : 100 points

Problem Statement

There is a programming contest with N problems. For each i = 1, 2, \ldots, N, the score for the i-th problem is S_i.

Print the total score for all problems with a score of X or less.

Constraints

  • All input values are integers.
  • 4 \leq N \leq 8
  • 100 \leq S_i \leq 675
  • 100 \leq X \leq 675

Input

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

N X
S_1 S_2 \ldots S_N

Output

Print the answer.


Sample Input 1

6 200
100 675 201 200 199 328

Sample Output 1

499

Three problems have a score of 200 or less: the first, fourth, and fifth, for a total score of S_1 + S_4 + S_5 = 100 + 200 + 199 = 499.


Sample Input 2

8 675
675 675 675 675 675 675 675 675

Sample Output 2

5400

Sample Input 3

8 674
675 675 675 675 675 675 675 675

Sample Output 3

0
B - Saturday

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある日、学校へ行くのに疲れてしまった高橋くんは、土曜日まであと何日あるかを知りたくなりました。
その日は平日で、曜日を英語で表すと S だったことが分かっています。その日より後の直近の土曜日は何日後かを求めてください。

なお、月曜日、火曜日、水曜日、木曜日、金曜日はそれぞれ英語で Monday, Tuesday, Wednesday, Thursday, Friday です。

制約

  • S は Monday, Tuesday, Wednesday, Thursday, Friday のいずれかである

入力

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

S

出力

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


入力例 1

Wednesday

出力例 1

3

この日は水曜日なので、3 日後に土曜日になります。


入力例 2

Monday

出力例 2

5

Score : 100 points

Problem Statement

One day, tired from going to school, Takahashi wanted to know how many days there were until Saturday.
We know that the day was a weekday, and the name of the day of the week was S in English.
How many days were there until the first Saturday after that day (including Saturday but not the starting day)?

Constraints

  • S is Monday, Tuesday, Wednesday, Thursday, or Friday.

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer as an integer.


Sample Input 1

Wednesday

Sample Output 1

3

It was Wednesday, so there were 3 days until the first Saturday after that day.


Sample Input 2

Monday

Sample Output 2

5
C - Cut .0

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

実数 X が小数点以下第 3 位まで与えられます。

実数 X を以下の条件を満たすように出力してください。

  • 小数点以下の部分について、末尾に 0 を付けない
  • 末尾に過剰な小数点を付けない

制約

  • 0 \le X < 100
  • X は小数点以下第 3 位まで与えられる

入力

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

X

出力

答えを出力せよ。


入力例 1

1.012

出力例 1

1.012

1.012 はそのまま出力しても構いません。


入力例 2

12.340

出力例 2

12.34

12.340 を末尾に 0 を付けずに出力すると 12.34 となります。


入力例 3

99.900

出力例 3

99.9

99.900 を末尾に 0 を付けずに出力すると 99.9 となります。


入力例 4

0.000

出力例 4

0

0.000 を末尾に 0 や過剰な小数点を付けずに出力すると 0 となります。

Score : 150 points

Problem Statement

A real number X is given to the third decimal place.

Print the real number X under the following conditions.

  • The decimal part must not have trailing 0s.
  • There must not be an unnecessary trailing decimal point.

Constraints

  • 0 \le X < 100
  • X is given to the third decimal place.

Input

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

X

Output

Output the answer.


Sample Input 1

1.012

Sample Output 1

1.012

1.012 can be printed as it is.


Sample Input 2

12.340

Sample Output 2

12.34

Printing 12.340 without the trailing 0 results in 12.34.


Sample Input 3

99.900

Sample Output 3

99.9

Printing 99.900 without the trailing 0s results in 99.9.


Sample Input 4

0.000

Sample Output 4

0

Printing 0.000 without trailing 0s or an unnecessary decimal point results in 0.

D - Setsubun

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

年に 1 度の節分には年齢と同じ数の豆を食べます。高橋君はそれ以外に豆を食べることはありません。
高橋君は、今年 ( 0 年後 ) の節分の時点で N 歳です。

高橋君が今年以降 (今年を含む) で累計 K 個以上の豆を食べたことになるのは、最短で何年後の節分ですか?
なお、高橋君は不死身なので、高橋君が今年以降で累計 K 個以上の豆を食べたという状況は必ず訪れます。

制約

  • 入力は全て整数
  • 1 \le N,K \le 10^8

入力

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

N K

出力

答えを出力せよ。


入力例 1

4 43

出力例 1

6
  • 0 年後の節分に高橋君は 4 個の豆を食べ、今年以降で累計で 4 個の豆を食べます。
  • 1 年後の節分に高橋君は 5 個の豆を食べ、今年以降で累計で 9 個の豆を食べます。
  • 2 年後の節分に高橋君は 6 個の豆を食べ、今年以降で累計で 15 個の豆を食べます。
  • 3 年後の節分に高橋君は 7 個の豆を食べ、今年以降で累計で 22 個の豆を食べます。
  • 4 年後の節分に高橋君は 8 個の豆を食べ、今年以降で累計で 30 個の豆を食べます。
  • 5 年後の節分に高橋君は 9 個の豆を食べ、今年以降で累計で 39 個の豆を食べます。
  • 6 年後の節分に高橋君は 10 個の豆を食べ、今年以降で累計で 49 個の豆を食べます。

6 年後の節分の時点で累計 43 個以上の豆を食べたことになるので、 6 と出力してください。


入力例 2

100000000 100000000

出力例 2

0

今年のみで食べた豆の個数が K 個以上に達することもあります。


入力例 3

1234 12345678

出力例 3

3886

Score : 200 points

Problem Statement

At the annual Setsubun festival, one eats the same number of beans as their age. Takahashi-kun does not eat beans at any other time.
He is N years old at this year's Setsubun (0 years later).

At the earliest, how many years later will he have eaten a total of K or more beans from this year onward (including this year)?
He is immortal, so he will eventually have eaten a total of K or more beans from this year onward.

Constraints

  • All input values are integers.
  • 1 \le N,K \le 10^8

Input

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

N K

Output

Print the answer.


Sample Input 1

4 43

Sample Output 1

6
  • At Setsubun 0 years later, Takahashi-kun eats 4 beans, totaling 4 beans from this year onward.
  • At Setsubun 1 year later, he eats 5 beans, totaling 9 beans from this year onward.
  • At Setsubun 2 years later, he eats 6 beans, totaling 15 beans from this year onward.
  • At Setsubun 3 years later, he eats 7 beans, totaling 22 beans from this year onward.
  • At Setsubun 4 years later, he eats 8 beans, totaling 30 beans from this year onward.
  • At Setsubun 5 years later, he eats 9 beans, totaling 39 beans from this year onward.
  • At Setsubun 6 years later, he eats 10 beans, totaling 49 beans from this year onward.

At Setsubun 6 years later, he will have eaten a total of 43 or more beans, so output 6.


Sample Input 2

100000000 100000000

Sample Output 2

0

The number of beans eaten this year alone may reach K or more.


Sample Input 3

1234 12345678

Sample Output 3

3886
E - Fishbones

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

アーティストの高砂君は、魚の骨をかたどったオブジェを作りました。

オブジェは N 本の肋骨と 1 本の脊椎からなります。 肋骨には 1 から N までの番号が付けられています。

高砂君は、以下の条件をすべて満たすように N+1 本の骨に 1 つずつ文字列を書こうと考えています。

  • 脊椎に書く文字列の長さは N である。
  • 肋骨 i = 1, \dots, N に対して、以下が成り立つ。
    • 肋骨 i に書く文字列の長さは A_i である。
    • 肋骨 i に書く文字列の B_i 文字目は、脊椎に書く文字列の i 文字目に一致する。
  • N+1 本の骨に書く文字列はいずれも、S_1, \cdots, S_M のいずれかである(重複してもよい)。

S_1, \cdots, S_M は英小文字からなる文字列であり、互いに異なります。

j = 1, \cdots, M に対して、以下の質問に答えてください。

  • 条件を満たす書き方のうち、脊椎に書く文字列が S_j であるものは存在しますか?

制約

  • N は整数
  • 1 \leq N \leq 10
  • A_i, B_i は整数 (1 \leq i \leq N)
  • 1 \leq B_i \leq A_i \leq 10 (1 \leq i \leq N)
  • M は整数
  • 1 \leq M \leq 200\,000
  • S_j は英小文字からなる文字列 (1 \leq j \leq M)
  • 1 \leq |S_j| \leq 10 (1 \leq j \leq M)
  • S_1, \cdots, S_M は相異なる

入力

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

N
A_1 B_1
\vdots
A_N B_N
M
S_1
\vdots
S_M

出力

M 行出力せよ。

j 行目 (1 \leq j \leq M) には、条件を満たす書き方のうち脊椎に書く文字列が S_j のものが存在するならば Yes を、存在しないならば No を出力せよ。


入力例 1

5
5 3
5 2
4 1
5 1
3 2
8
retro
chris
itchy
tuna
crab
rock
cod
ash

出力例 1

Yes
Yes
No
No
No
No
No
No

肋骨 1,2,3,4,5 にそれぞれ chris, retro, tuna, retro, cod と書くことで、脊椎に retro を書いたときに条件を満たします。

  • retro の長さは 5 文字。
  • 各肋骨について、以下が成り立つ。
    • 肋骨 1 に書かれる文字列 chris の長さは 5 文字である。その 3 文字目は r であり、retro の 1 文字目に一致する。
    • 肋骨 2 に書かれる文字列 retro の長さは 5 文字である。その 2 文字目は e であり、retro の 2 文字目に一致する。
    • 肋骨 3 に書かれる文字列 tuna の長さは 4 文字である。その 1 文字目は t であり、retro の 3 文字目に一致する。
    • 肋骨 4 に書かれる文字列 retro の長さは 5 文字である。その 1 文字目は r であり、retro の 4 文字目に一致する。
    • 肋骨 5 に書かれる文字列 cod の長さは 3 文字である。その 2 文字目は o であり、retro の 5 文字目に一致する。

肋骨 1,2,3,4,5 にそれぞれ itchy, chris, rock, itchy, ash と書くことで、脊椎に chris を書いたときに条件を満たします。


入力例 2

5
5 1
5 2
5 3
5 4
5 5
8
retro
chris
itchy
tuna
crab
rock
cod
ash

出力例 2

Yes
Yes
Yes
No
No
No
No
No

Score : 300 points

Problem Statement

Artist Takasago has created an object in the shape of a fish skeleton.

The object consists of N ribs and one spine. The ribs are numbered 1 through N.

He wants to write one string on each of the N+1 bones, satisfying all of the following conditions.

  • The length of the string written on the spine is N.
  • For each rib i = 1, \dots, N, the following hold.
    • The length of the string written on rib i is A_i.
    • The B_i-th character of the string written on rib i equals the i-th character of the string written on the spine.
  • Each of the strings written on the N+1 bones is one of S_1, \cdots, S_M (duplicates allowed).

S_1, \cdots, S_M are strings consisting of lowercase English letters, and they are all distinct.

For each j = 1, \cdots, M, answer the following question.

  • Among the ways to write strings satisfying the conditions, is there one where the string written on the spine is S_j?

Constraints

  • N is an integer.
  • 1 \leq N \leq 10
  • A_i and B_i are integers. (1 \leq i \leq N)
  • 1 \leq B_i \leq A_i \leq 10 (1 \leq i \leq N)
  • M is an integer.
  • 1 \leq M \leq 200\,000
  • S_j is a string consisting of lowercase English letters. (1 \leq j \leq M)
  • 1 \leq |S_j| \leq 10 (1 \leq j \leq M)
  • S_1, \cdots, S_M are pairwise distinct.

Input

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

N
A_1 B_1
\vdots
A_N B_N
M
S_1
\vdots
S_M

Output

Output M lines.

The j-th line (1 \leq j \leq M) should contain Yes if there exists a way to write strings satisfying the conditions with S_j written on the spine, and No otherwise.


Sample Input 1

5
5 3
5 2
4 1
5 1
3 2
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 1

Yes
Yes
No
No
No
No
No
No

By writing chris, retro, tuna, retro, cod on ribs 1,2,3,4,5 respectively, the conditions are satisfied with retro written on the spine.

  • The length of retro is 5.
  • For each rib, the following hold.
    • The string written on rib 1 is chris, which has length 5. Its third character is r, which equals the first character of retro.
    • The string written on rib 2 is retro, which has length 5. Its second character is e, which equals the second character of retro.
    • The string written on rib 3 is tuna, which has length 4. Its first character is t, which equals the third character of retro.
    • The string written on rib 4 is retro, which has length 5. Its first character is r, which equals the fourth character of retro.
    • The string written on rib 5 is cod, which has length 3. Its second character is o, which equals the fifth character of retro.

By writing itchy, chris, rock, itchy, ash on ribs 1,2,3,4,5 respectively, the conditions are satisfied with chris written on the spine.


Sample Input 2

5
5 1
5 2
5 3
5 4
5 5
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 2

Yes
Yes
Yes
No
No
No
No
No