A - 元気にお使い！高橋君

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

ある日高橋君はお母さんに近くのスーパーまでおつかいを頼まれました。
お母さんに手渡されたおつかいメモには、買ってきて欲しい商品の値段と個数がそれぞれ書かれています。
ただしメモに書かれている値段には消費税が含まれていませんが、全ての商品には消費税が 5\% かかります。
高橋君のおつかいに必要な金額を答えなさい。
なお、消費税は 1 円未満は切り捨てます。

入力

入力は以下の形式で標準入力から与えられる。 
N
a_0 b_0
a_1 b_1
:
:
a_{N-1} b_{N-1}
  • 入力は N+1 行ある。
  • 1 行目には、購入する商品の品数を表す整数 N(1≦N≦10) が与えられる。
  • 2 行目から N 行の i+2 行目にはある商品の購入したい個数を表す整数 a_i(1≦a_i≦10) とその単価を表す整数 b_i(1≦b_i≦1,000) が空白区切りで与えられる。

出力

高橋君のおつかいに必要な金額を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

2
4 120
2 130

出力例 1

777
  • 120×4+130×2=740 円に消費税を加えると 740×1.05=777 円になります。

入力例 2

1
1 100

出力例 2

105
  • 100×1×1.05=105 円になります。

入力例 3

4
3 510
1 835
2 140
6 205

出力例 3

4068
  • 合計金額 3875 円に消費税を加えると 4068.75 円になります。
  • 1 円未満は切り捨てるので 4068 円が答えになります。

入力例 4

10
8 10
7 189
4 545
1 596
3 209
10 850
9 943
6 921
8 984
10 702

出力例 4

44321

Source Name

ARC 009
B - おとぎの国の高橋君

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋君の住むAtCoder国では、私達が普段使用する数字と同様に 10 個のアラビア数字 (0-9) の 10 進数が使われています。
しかし、私達が普段使用する数字は大小関係が 0<1<2<3<4<5<6<7<8<9 の順になっているのに対して、 AtCoder国の数字ではその大小関係が異なっています。
例えば、AtCoder国の数字では 0<9<8<7<6<5<4<3<2<1 の順になっている場合、AtCoder国では 9 よりも 8 の方が大きいことになります。また、97 よりも 72 の方が大きいことになります。

AtCoder国の数字の大小関係といくつかの数が与えられるので、AtCoder国の数字の大小関係で昇順に並び替えてください。
なお、私達が普段使用する数字同様、AtCoder国で最も小さい数字は 0 であることは決まっています。

入力

入力は以下の形式で標準入力から与えられる。 
b_0 b_1 ‥‥ b_9
N
a_0
a_1
:
:
a_{N-1}
  • 入力は N+2 行ある。
  • 1 行目には、AtCoder国での 1 桁の数字の大小関係が与えられる。
    • AtCoder国では b_0 < b_1 < ... < b_9 であることを表している。
    • b_0 は必ず 0 である。
    • 重複する数字は存在せず、0 から 9 までの数字が 1 度ずつ現れる。
  • 2 行目には並び替える数の個数を表す整数 N(1≦N≦777) が与えられる。
  • 3 行目からの N 行には、j+3 行目に並び替える数を表す整数 a_j(1≦a_j≦777,777,777) が与えられる。

出力

与えられた数をAtCoder国の数字の大小関係にあわせて昇順に並び替え、標準出力に 1 行に 1 つの数字ずつ出力せよ。
なお、最後には改行を出力せよ。

入力例 1

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

出力例 1

8
1
3
5
4
9
7
6
2
10
  • AtCoder国ではこの大小関係の場合、0, 8, 1, 3, 5, 4, 9, 7, 6, 2, 80, 88, 81, 83, ..., 86, 82, 10, 18, 11, ... の順に大きくなるので、答えは上記の順になります。

入力例 2

0 9 8 7 6 5 4 3 2 1
3
13467932
98738462
74392

出力例 2

74392
98738462
13467932
  • 5 桁の数は 8 桁の数よりも小さいので、1 番は 74392 になります。
  • 98738462 と 13467932 では最上位の 9 は1 より小さいので、98738462 が 2 番目、13467932 が 3 番目になります。

入力例 3

0 1 2 3 4 5 6 7 8 9
4
643
1234
43
909

出力例 3

43
643
909
1234
  • 私達の普段使用する数と同じ大小関係に昇順に並べます。

入力例 4

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

出力例 4

333
333

入力例 5

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

出力例 5

10

Source Name

ARC 009
C - 高橋君、24歳

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

　高橋君は10月20日が誕生日なので、友達を誕生会に呼ぼうと考えています。
　そこで恥ずかしがり屋な彼は、みんなに招待状を送ることにしました。

　高橋君はなかなか手紙の良い文面が思いつかなかったので、全員分の手紙を書き終えたのは誕生日の前日でした。
　慌てて友達 N 人の家のポストに 1 つずつ手紙を入れていったのですが、誤ってそのうち K 人の手紙を、別の友達のポストに入れてしまいました。

　帰った後にそのことに気づいた高橋君はとても焦っています。
　彼を少しでも元気づけるために、ポストと入れられた手紙の考えられる組み合わせの数を 1,777,777,777 (素数) で割った余りを教えてあげてください。

入力

入力は以下の形式で標準入力から与えられる。 
N K
  • 入力は 1 行ある。
  • 1 行目には、高橋君の友達の人数を表す整数 N と高橋君が間違った手紙を入れてしまった友達の人数を表す整数 K が空白区切りで与えられる。
    • K は N を超えることはない。
  • 友達は過不足無く 1 人 1 枚の手紙を受け取った。
  • K 人は別の友達の手紙を受け取り、N-K 人は自分宛に書かれた手紙を受け取った。

部分点

テストデータは以下の 2 種類のテストデータセットのいずれかに含まれており、それぞれのデータセットに含まれているテストデータは以下に示すように与えられる整数 N と K の範囲が異なっている。
あるテストデータセットに含まれているテストデータ全てに対して正しい解を出力できると、それ以外のテストデータセットで不正解を出力しても以下のように部分点が与えられる。
  • small ( 40 点)
    • 2≦N≦8
    • 2≦K≦8
  • large ( 60 点)
    • 2≦N≦777,777,777,777,777,777
    • 2≦K≦777,777

出力

ポストと入れられた手紙の考えられる組み合わせの数を 1,777,777,777 (素数) で割った余りを標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

3 2

出力例 1

3
  • 高橋君の 3 人の友達を A,B,C とすると、次のような組み合わせが考えられます。
    1. A は自分宛の手紙を受け取り、B は C 宛ての手紙を受け取り、C は B 宛ての手紙を受け取った。
    2. B は自分宛の手紙を受け取り、A は C 宛ての手紙を受け取り、C は A 宛ての手紙を受け取った。
    3. C は自分宛の手紙を受け取り、B は A 宛ての手紙を受け取り、A は B 宛ての手紙を受け取った。
  • 条件を満たす組み合わせはこの 3 通りのみなので、答えは 3 になります。

入力例 2

5 3

出力例 2

20

入力例 3

4 4

出力例 3

9

入力例 4

8 4

出力例 4

630

入力例 5

777 77

出力例 5

1084428318

Source Name

ARC 009
D - 覚醒ノ高橋君

Time Limit: 8 sec / Memory Limit: 64 MB

問題文

AtCoder国には、たくさんの町が存在します。
町を管理するために、町の集合である、市が存在します。
市内の町と町は、道で結ばれています。これらの道によって、市内のすべての町に行き来できるようになっています。
ですが、これらの道だけでは他の市にある町に移動することが出来ません。
そこで、AtCoder国では、この問題を解決するためにいくつかの町を複数の市で管理することによって、市同士を繋げ、全ての市を行き来できるようにしています。

複数の市で１つの町を管理するのは非常に面倒なため、共有する数は、出来るだけ少なくなるようにされています。
具体的には、 N 個の市があるとして、 k 個の市で共有している町の個数を S_k とすると、 Σ(S_k×(k-1))=N-1 になります。

高橋君はAtCoder国の国土交通大臣で、各道の整備にかかるコストの総和を出来るだけ小さくしたいです。
ですが、整備計画が 1 つでは不安なので、 k 番目に良いプランまで考えることにしました。

そのプランの内容は以下の通りです。
  • どの町の間を移動する場合にも、同じ町を重複して通らないように移動したとき、経路がちょうど 1 つに定まるように整備したいです。
  • 道を整備するとは、町と町の間の道を減らすことである。
彼はこの条件を満たすプランがたくさんあることに気づきました。
そこで、プランのコストを、各道の整備にかかったコストの総和としました。
コストの値が小さい程、そのプランは良いと言えます。

k 番目に良いプランのコストを出力しなさい。k番目の値が存在しない場合は-1を出力しなさい。

入力

入力は以下の形式で標準入力から与えられる。 制約の追記を行いました 
A T k
N_1
C_{11} C_{12} C_{13} ... C_{1N_1}
:
:
N_A
C_{N1} C_{N2} C_{N3} ... C_{NN_A}
M
city_{11} city_{12} cost_1
:
:
cost_{M1} city_{M2} cost_M
  • 入力は 2×A+M+2 行ある。
  • 1 行目には市の数 A(1≦A≦77) 、町の数 T(1≦T≦A×7) 、非負の整数 k(1≦k≦7,777,777) が与えられる。
  • 2 行目から 2×A+1 行目までの 2×A 行は市に所属する町の情報が与えられる。
    1. N_i(2≦N_i≦7) ... i 番目の市に所属する町の数を表す。
    2. C_{ij}(1≦C_{ij}≦T) ... i 番目の市に所属する j 番目の町を表す。
  • M は道の数を表し、非負の整数である。入力の最後までの M 行は道の情報が与えられる。
    1. city_{i1} と city_{i2} は i 番目の道が繋げている町を表す。つまり、 city_{i1} と city_{i2} は双方向に移動可能で、同じ市に属している。
    2. cost_i(1≦cost_i≦77) は i 番目の道の整備にかかるコストを表す。

出力

k番目に良いプランのコストを出力しなさい。k番目の値が存在しない場合は-1を出力しなさい。

入力例 1

3 7 1
3
1 2 3
3
3 4 5
3
5 6 7
9
1 2 1
1 3 2
2 3 3
3 4 3
3 5 6
4 5 9
5 6 9
5 7 18
6 7 27
図：入力例 1 を図示したもの

出力例 1

13
図：出力例 1 の状態を図示したもの
  • 1 番目に良いプランは、町 1 と 町 2 を繋ぐ道、町 3 と町 4 を繋ぐ道、町 5 と町 6 を繋ぐ道を取り除いたプランです。

入力例 2

2 3 2
2
1 2
2
2 3
2
1 2 1
2 3 1

出力例 2

-1
  • 2 番目に良いプランのコストが存在しないため、 -1 を出力します。

入力例 3

4 9 2
3
1 2 3
3
3 4 5
3
5 6 7
3
5 8 9
12
1 2 1
1 3 1
2 3 1
3 4 3
3 5 3
4 5 3
5 6 6
5 7 3
6 7 9
5 8 9
5 9 18
8 9 27

出力例 3

16
  • 合計コストが16のプランが最小ですが、これと同じコストで出来るプランは9通り存在します。よって、2番目のプランの必要コストも同じく16です。

Source Name

ARC 009