A - 天下一プログラマーコンテスト1998

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

コウヘイくんは天下一プログラマーコンテスト1998の賞金額を以下の数列とすることを決めました。

a_0=100
a_1=100
a_2=200
a_n=a_{n-1} + a_{n-2} + a_{n-3}

a_0 が最下位の賞金額、 a_1 が最下位から 2 番目の賞金額となっていきます。

しかし、コウヘイくんは計算が苦手です。コウヘイくんのために参加者が 20 人だった場合の 1 位の賞金額を計算してください。

入力

この問題では入力は与えられない。

出力

1 位の賞金額を 1 行に出力せよ。

出力の末尾には改行を入れること。

配点

この問題には部分点は設定されていない。正解した場合は、10 点が与えられる。

B - 天下一リテラル

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

スクリプト言語 hnw には 3 つの型が存在します。整数型、辞書型、集合型です。

整数型のリテラルは、 0 以上 10^6 以下の整数を十進数で表記したものとして表現できます。

辞書型のリテラルは、“key” と “value” を : でつなげたものを { と } の間にカンマ区切りで並べたものとして表現できます。

空でない集合型のリテラルは、要素を{と}の間にカンマ区切りで並べたものとして表現できます。

辞書型の “key” と “value” および集合型の要素は、整数型、辞書型、集合型のいずれかです。

スクリプト言語 hnw のリテラルは上記のものですべてであり、以下のEBNFに従います。
ただし、INTEGER は整数型、SET は集合型、DICT は辞書型を表します。 

DICT = "{" , EXPR , ":" , EXPR , { "," , EXPR , ":" , EXPR } , "}" | "{}" ;
SET  = "{" , EXPR , { "," , EXPR } , "}" ;
EXPR = DICT | SET | INTEGER ;

集合型か辞書型のリテラルが与えられます。型がどちらなのかを判別してください。

入力

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

S

問題文中の EBNF に沿った集合型あるいは辞書型の値を示す文字列 S が 1 行で与えられる。

文字列 S の長さは 50000 以下である。

入力に空白は含まれない。

出力

値が集合型の場合は set を、辞書型の場合は dict を 1 行に出力しなさい。

出力の末尾には改行を入れること。

配点

この問題には部分点が設定されていない。全てのテストケースに正解した場合は、 40 点が与えられる。

入力例1

{1:2}

出力例1

dict

入力例2

{1,2}

出力例2

set

入力例3

{}

出力例3

dict
C - 擬二等辺三角形

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ニシモリ君は下記の 3 つの条件を満たす三角形を“擬二等辺三角形”と呼ぶことにしました。

  • すべての辺の長さが整数である
  • すべての辺の長さが異なる
  • いずれかの二辺の長さの差が 1 となる

三角形の周長が L 以下となる擬二等辺三角形の個数を求め、1000000007 で割った余りを出力して下さい。

入力

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

L
  • 最大の周長 L ( 5 \leq L \leq 10^{12} ) が1行に与えられる。

出力

三角形の周長が L 以下となる擬二等辺三角形の個数を求め、 1000000007 で割った余りを出力せよ。出力の末尾に改行を入れること。

配点

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

  • L\leq 10^6 を満たすテストケース全てに正解した場合は、25 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 75 点が与えられる。

入力例1

10

出力例1

1

(a, b, c) = (2, 3, 4) のみで、それ以外 ( 例: (1,2,3) や(1,2,4) ) は三角形になりません。

入力例2

1100011

出力例2

251098945
D - 天下一電卓英作文

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

ヨシオ君は電卓を使って英作文をするのが大好きですが、イマイチ良い英作文ができません。ヨシオ君に代わって最高の英作文をしましょう。

電卓に表示した数値は、上下逆さまから見たときに英文字列とみなすことができます。例えば次のようなものです。

0.7734

逆からみるとhELLO

ヨシオ君はこのようにして電卓で英作文を楽しんでいます。ちなみに、ヨシオ君が使っている変換表は次のようなものです。

数字 英字
0 O
D
1 I
2 Z
3 E
4 h
5 s
6 q
7 L
8 B
9 G

ヨシオ君によれば、得点が高いほど良い英文字列だそうです。
それぞれの英文字列の得点は、その英文字列を電卓に表示したときに、元の向きから見たときの数値と同じです。
つまり、EGGなら 993 点、ODDEGGなら 993000 点です。

また、通常の電卓と同じく、最上位桁が 0 になるような整数は作れません。
最後の文字がOかDであるような英文字列を作りたい場合は小数点を利用する必要があります。
つまり、上の写真の例の通り、hELLOの得点は 0.7734 点となります。
一方hELLOEGGであれば 99307734 点です。
ただし、電卓の表示としては、末尾の 0 は付けても良いものとします。
つまり、OLDという表示は可能であり、その得点は 0.7 点となります。

ヨシオ君は最大表示桁数 D の電卓と N 個の単語が載っている単語帳を持っています。
この電卓に表示できる、単語帳に載っている単語を並べた英文字列の最高得点はいくらでしょうか？
単語帳に含まれる単語 W_1, W_2, ..., W_N から 1 個以上の単語を選び任意の順序で連結した英文字列のうち、文字列長 D 以下になるものの中での最高得点を求めてください。
ただし、単語帳に含まれる単語から、同じ単語を複数回選ぶことはできません。

入力

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

D
N
W_1
W_2
:
W_N
  • 1 行目には、電卓の最大表示桁数を表す整数 D ( 1 \leq D \leq 200 ) が与えられる。
  • 2 行目には、単語帳に含まれる単語数を表す整数 N ( 1 \leq N \leq 10000 ) が与えられる。
  • 3 行目からの N 行には、単語帳に含まれる単語 W_i ( 1 \leq |W_i| \leq {\rm min}(32, D) ) が与えられる。
    これらの単語は、1 行につき1単語の形式で与えられる。
    W_i は 変換表に含まれる文字「O,D,I,Z,E,h,s,q,L,B,G」だけで構成されており、それ以外の文字を含まない。
  • i \neq j ならば W_i \neq W_j である。

出力

最高得点を 1 行で出力せよ。

答えが小数になる場合、末尾の 0 は取り除いて出力すること。また、小数点以下が全て 0 の場合は整数として出力すること。

出力の末尾には改行を入れること。

配点

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

  • N \leq 8 を満たすテストケース全てに正解した場合は、45 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 75 点が与えられる。

入力例1

9
4
hELLO
hELL
EGG
ODD

出力例1

773407734

最高得点となる英文字列はhELLOhELLです。

入力例2

5
3
ZO
OIO
IOIO

出力例2

0.201

最高得点となる英文字列はOIOZOです。

入力例3

25
10
BED
BEL
BIG
DIE
DIG
DOG
OLD
shE
qED
ZOO

出力例3

918910900738345310070038

最高得点となる英文字列はBEDOLDDIEshEBELDOGDIGBIGです。

入力例4

5
1
hELLO

出力例4

0.7734

上の写真の通り小数点は電卓の表示桁数を消費しないので、桁数 D=5 の電卓で表示可能です。

E - 天下一演算

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

あなたは天下一演算というゲームで遊んでいます。天下一演算は以下のように定義されます。

  • 1 以上 10^5 以下の整数 M、N と、0 以上 M 未満の整数 N 個からなる配列 A が与えられる。
  • 配列の全ての要素に 10 を掛ける操作を何回か行う。
  • その後、配列のある 1 つの要素に 1 を足す操作を何回か行う。
  • 全ての要素が M の倍数になるとクリアとなる。

例えば、M = 7、N = 4、A = \[0, 1, 2, 3\] のとき、全ての要素に 3 回 10 を掛けた後、2 番目の要素に 1 回 1 を足し、3 番目の要素に 2 回 1 を足し、4 番目の要素に 3 回 1 を足すと、A = \[0, 1001, 2002, 3003\] となり、合計 9 回の操作で全ての要素が M の倍数になります。

天下一演算をできるだけ少ない回数の操作でクリアしたときの、合計の操作回数を求めてください。

入力

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

M N
A_1
A_2
:
A_N
  • 1 行目には、2 つの整数 M (1 ≦ M ≦ 10^5)、N (1 ≦ N ≦ 10^5) が空白区切りで与えられる。
  • 2 行目からの N 行に、配列 A のそれぞれの要素 A_i (0 ≦ A_i < M) が与えられる。

出力

天下一演算をできるだけ少ない回数の操作でクリアしたときの、合計の操作回数を出力せよ。出力の末尾に改行を入れること。

配点

この問題には部分点は設定されていない。正解した場合は、130 点が与えられる。

入力例1

7 4
0
1
2
3

出力例1

9

問題文中で説明したケースです。

入力例2

1001 1
1

出力例2

4

3 回 10 を掛けた後、1 回 1 を足すと、M の倍数になります。

入力例3

1 2
0
0

出力例3

0

はじめから M の倍数です。

入力例4

12345 5
12
34
56
78
90

出力例4

1884