A - プロコン

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君はプロコン(ここでいうプロコンとは、グラフ上に適切にプロットする力を問うコンテストである)に参加している。

高橋君は 3 つの課題に取り組んだ。

課題ごとに配点が定められており、各課題ごとに 1 以上 10 以下の整数による評価が付けられる。評価の数字が X であるとき、その課題においては配点の X 割の得点が与えられる。

3 つの課題の配点と評価が与えられるので、高橋君が合計で何点獲得したのかを求めてほしい。

入力

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

s_1 e_1
s_2 e_2
s_3 e_3
  • 1 行目には、1 つめの課題の情報を表す 2 つの整数 s_1 (10 ≦ s_1 ≦ 990) と e_1 (1 ≦ e_1 ≦ 10) が与えられる。これは、1 つめの課題の配点が s_1 点で、評価が e_1 だったことを表す。
  • 2 行目には、2 つめの課題の情報を表す 2 つの整数 s_2 (10 ≦ s_2 ≦ 990) と e_2 (1 ≦ e_2 ≦ 10) が与えられる。これは、2 つめの課題の配点が s_2 点で、評価が e_2 だったことを表す。
  • 3 行目には、3 つめの課題の情報を表す 2 つの整数 s_3 (10 ≦ s_3 ≦ 990) と e_3 (1 ≦ e_3 ≦ 10) が与えられる。これは、3 つめの課題の配点が s_3 点で、評価が e_3 だったことを表す。
  • s_1 と s_2 と s_3 のいずれも 10 の倍数であることが保証されている。そのため、合計得点は整数値となる。

出力

合計得点を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

50 7
40 8
30 9

出力例1

94

課題 1 では配点 50 点のうち 7 割の得点を得るので、50 × 0.7 = 35 点を獲得する。

課題 2 では配点 40 点のうち 8 割の得点を得るので、40 × 0.8 = 32 点を獲得する。

課題 3 では配点 30 点のうち 9 割の得点を得るので、30 × 0.9 = 27 点を獲得する。

3 つの課題の合計得点は、35 + 32 + 27 = 94 点となる。

入力例2

990 10
990 10
990 10

出力例2

2970

配点がそのまま得点となる場合もある。

B - choku語

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は、ある日不思議な生物を見た。

その生物は choku 語という言語を用いていることがわかった。

文字列 S が以下の条件を満たしているときに S は choku 語であると定義する。

  • 文字列 S が空文字列であるとき。
  • 文字列 S が、choku 語である文字列 T の末尾に ch をつけた文字列であるとき。
  • 文字列 S が、choku 語である文字列 T の末尾に o をつけた文字列であるとき。
  • 文字列 S が、choku 語である文字列 T の末尾に k をつけた文字列であるとき。
  • 文字列 S が、choku 語である文字列 T の末尾に u をつけた文字列であるとき。

choku 語の理解を深めるため、与えられた文字列が choku 語であるかを判定するプログラムを作成することにした。

入力

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

X
  • 1 行目には、choku 語か判定したい文字列 X (1 ≦ |X| ≦ 50) が与えられる。
  • X は半角小文字アルファベットのみで構成されている。

出力

X が choku 語なら文字列 YES を、そうでないなら文字列 NO を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

chokuou

出力例1

YES

文字列 chokuou は choku 語である。

入力例2

kuccho

出力例2

NO

文字列 kuccho は choku 語ではない。

入力例3

atcoder

出力例3

NO
C - ハイスコア

Time Limit: 6 sec / Memory Limit: 256 MB

問題文

高橋君はあるゲームが大好きである。

このゲームには N 個の遺跡があり、好きな順番に探索することができる。遺跡には 1 から N までの番号が付けられている。

ゲーム中に宝石を獲得することがある。宝石は M 種類あり、1 から M まで番号が付けられている。

遺跡を探索することで報酬として得点といくつかの宝石を入手することができる。遺跡 i (1 ≦ i ≦ N) を探索することで、得点 s_i 点を獲得し、番号が l_i 以上 r_i 以下のすべての宝石を 1 つずつ獲得する。同じ遺跡を複数回探索することはできない。

獲得した宝石は捨てることができず、またすべての種類の宝石を 1 つ以上獲得してしまうと、魔王が復活するイベントが進行する。魔王が復活する際に探索していた遺跡で得られるはずの得点は消滅してしまう。

高橋君はスコアをできるだけ高くすることを目標としており、うまく探索する遺跡を選ぶことで、魔王が復活しない状態で得られる得点の合計値を最大化したい。

考えられる最大値はいくらか。

入力

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

N M
l_1 r_1 s_1
l_2 r_2 s_2
:
l_N r_N s_N
  • 1 行目には、2 つの整数 N (1 ≦ N ≦ 100,000) と M (1 ≦ M ≦ 100,000) が空白区切りで書かれている。これは、遺跡が N 個、宝石が M 種類あることを表す。
  • 2 行目から N 行には、遺跡に関する情報を表す 3 つの整数 l_i, r_i (1 ≦ l_i ≦ r_i ≦ M), s_i (1 ≦ s_i ≦ 5,000) が与えられる。これは、遺跡 i (1 ≦ i ≦ N) を探索することで、得点 s_i 点を獲得し、番号が l_i 以上 r_i 以下のすべての宝石を 1 つずつ獲得することを表す。

配点と部分点

この問題は 101 点満点で、部分点が設定されている。

  • N ≦ 8 かつ M ≦ 8 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
  • N ≦ 5,000 かつ M ≦ 5,000 を満たすデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。
  • 追加制約のないデータセット 3 に正解した場合は、上記とは別に 1 点が与えられる。

出力

魔王が復活しないような探索方法として考えられるものの中で得られる得点の最大値を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

4 6
1 3 30
2 3 40
3 6 25
6 6 10

出力例1

80

例えば、以下の順番に 3 つの遺跡を探索します。

  • 遺跡 1 を探索する。得点は 30 点で、宝石 1 と宝石 2 と宝石 3 を獲得する。
  • 遺跡 2 を探索する。得点は 40 点で、宝石 2 と宝石 3 を獲得する。
  • 遺跡 4 を探索する。得点は 10 点で、宝石 6 を獲得する。

最終的に獲得している宝石の種類は宝石 1 と宝石 2 と宝石 3 と宝石 6 の 4 種類なので、魔王は復活しません。合計得点は 80 点となり、これが最大値です。

入力例2

2 7
1 3 90
5 7 90

出力例2

180

すべての遺跡を探索しても魔王は復活しません。

入力例3

1 4
1 4 70

出力例3

0

魔王が復活しないように遺跡を探索することができません。

D - サプリメント

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

健康志向の高橋君は通販で購入したサプリメントを摂取することにした。

サプリメントは N 個あり、1 から N まで番号が付けられている。

また、サプリメントの味は M 種類あり、1 から M まで番号が付けられている。サプリメント i (1 ≦ i ≦ N) の味は f_i (1 ≦ f_i ≦ M) である。

高橋君はサプリメントを番号順に複数日かけて摂取する予定である。高橋君はサボらないように、サプリメントが 1 つ以上残っている場合はその日中に必ず 1 つ以上サプリメントを摂取しなければならないという規則を定めた。

高橋君は強靭な肉体を持っているため、1 日にどれだけサプリメントを摂取しても大丈夫だが、同じ味には飽きてしまうので、同じ日に同じ味のサプリメントを 2 つ以上摂取することはできない。

高橋君は、サプリメントの摂取方法の是非について吟味するため、このような条件下で全部で何通りの摂取方法があるかを知りたい。

ここで 2 つの摂取方法についてそれらが違うというのは、ある日について摂取したサプリメントの番号の組み合わせが異なることを定義する。

入力

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

N M
f_1
f_2
:
f_N
  • 1 行目には、2 つの整数 N (1 ≦ N ≦ 100,000) と M (1 ≦ M ≦ 100,000) が空白区切りで書かれている。これはサプリメントが N 個あり、味の種類が M 種類あることを表す。
  • 2 行目から N 行には、サプリメントの味に関する情報が与えられる。これら N 行のうち上から i (1 ≦ i ≦ N) 行目には整数 f_i (1 ≦ f_i ≦ M) が書かれている。これは、サプリメント i の味が f_i であることを表す。

部分点

この問題には部分点が設定されている。

  • N ≦ 5,000 かつ M ≦ 5,000 を満たすデータセット 1 に正解した場合は、上記とは別に 30 点が与えられる。
  • 追加制約のないデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。

出力

摂取方法の総数を 1,000,000,007 (= 1000000007) で割ったあまりを 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

5 2
1
2
1
2
2

出力例1

5

以下の 5 通りが考えられます。

1 日目 2 日目 3 日目 4 日目 5 日目
サプリメント 1 サプリメント 2 サプリメント 3 サプリメント 4 サプリメント 5
サプリメント 1 サプリメント 2 サプリメント 3,4 サプリメント 5 なし
サプリメント 1 サプリメント 2,3 サプリメント 4 サプリメント 5 なし
サプリメント 1,2 サプリメント 3 サプリメント 4 サプリメント 5 なし
サプリメント 1,2 サプリメント 3,4 サプリメント 5 なし なし

入力例2

6 6
1
2
3
4
5
6

出力例2

32

どのように食べても飽きません。