Indeedなう（予選A）

A - 掛け算の筆算

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたは算数を学んでいます。あなたは 2 つの数の掛け算を行いたいと思っています。

あなたが学んでいる掛け算の筆算では、2 つの数の掛け算を行うために、1 桁の数同士の掛け算をちょうど (A の桁数) × (Bの桁数) 回だけ行います。

あなたには正の整数 A と B が与えられます。この 2 つの数の掛け算を筆算で行うとき、1 桁の数同士の掛け算を何回行うか出力してください。

入力

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

A
B

1 行目には、正の整数 A (1≦A≦10^6) が与えられる。
2 行目には、正の整数 B (1≦B≦10^6) が与えられる。

出力

1 行目には、文中で述べられている掛け算の筆算を行ったとき 1 桁の数同士の掛け算を何回行うかを出力せよ。末尾の改行を忘れないこと。

入力例1

123
12

出力例1

123 は 3 桁の数、12 は 2 桁の数です。したがって、答えは 6(=2×3) となります。

入力例2

10
1000

出力例2

入力例3

2
3

出力例3

入力例4

1000000
1000000

出力例4

B - Indeedなう！

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたには、N 個の文字列 {S_1,S_2,...,S_N}が与えられます。それぞれの i (1≦i≦N) について、S_i が indeednow のアナグラムになっているかどうかを判定しなさい。

文字列 A と B について、A に含まれる文字を任意の順番で並び替えて B にできるとき、A を B のアナグラムと呼びます。

入力

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

N
S_1
S_2
:
S_N

1 行目には、与えられる文字列の数 N (1≦N≦100) が与えられる。
2 行目から N 行には、それぞれの文字列が与えられる。そのうち i (1≦i≦N) 行目には、S_i が与えられる。S_i の長さは 1 以上 100 以下であり、半角小文字アルファベット a-z のみからなる。

出力

1 行目から N 行には、それぞれの文字列に対する判定結果を出力せよ。そのうち i (1≦i≦N) 行目には S_i が indeednow のアナグラムになっているならば YES を、そうでないならば NO を出力せよ。末尾の改行を忘れないこと。

入力例1

10
nowindeed
indeedwow
windoneed
indeednow
wondeedni
a
indonow
ddeennoiw
indeednoww
indeow

出力例1

YES
NO
YES
YES
YES
NO
NO
YES
NO
NO

たとえば nowindeed や windoneed に含まれる文字を並び替えると indeednow にすることができます。したがって nowindeed や windoneed は indeednow のアナグラムです。

一方、 indeedwow や a は、並び替えても indeednow にすることはできないため、indeednow のアナグラムではありません。

C - 説明会

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ある企業は、説明会に参加する学生の選抜コンテストを行いました。説明会を行おうとしている会場の最大収容可能人数が決まっているため、コンテスト担当者はボーダーラインを何点にするかを悩んでいます。

選抜方法を説明します。

ボーダーラインが x 点のとき、正の点数を取っている学生のうち x 点以上の得点を得た学生を全て選抜する。
つまり、0 点の学生は会場の最大収容可能人数に関わらず選抜しない。

あなたには、選抜コンテストにおける N 人の学生の点数が与えられます。また、会場の候補が Q 個あります。そして、会場の最大収容可能人数はそれぞれ k_1,k_2,…,k_Q です。ある企業は、説明会をこれらの会場の候補のうちいずれかで開催しようとしています。

あなたの仕事は、それぞれの会場候補で説明会を行う場合について、最小のボーダーラインを出力しなければなりません。具体的には、i (1≦i≦Q) 番目の会場候補で説明会を行うと仮定したとき、上記の方法に基づいて選抜した学生の数が k_i 人以下となるようなボーダーラインのうち 0 以上かつ最小のものを出力してください。

入力

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

N
s_1
s_2
:
s_N
Q
k_1
k_2
:
k_Q

1 行目には、学生の数 N (1≦N≦100,000) が与えられる。
2 行目から N 行には、選抜コンテストにおける各学生の得点情報が与えられる。そのうち i (1≦i≦N) 行目には、i 番目の学生の得点 s_i (0≦s_i≦1,000,000) が与えられる。
2+N 行目には、会場候補の数 Q (1≦Q≦100,000) が与えられる。
3+N 行目から Q 行には、各会場候補の最大収容可能人数が与えられる。そのうち i (1≦i≦Q) 行目には、i 番目の会場の最大収容可能人数 k_i (0≦k_i≦N) が与えられる。

出力

1 行目から Q 行には、各会場候補で説明会を行う場合のボーダーラインを出力せよ。そのうち i (1≦i≦Q) 行目には、i 番目の会場で説明会を行う場合のボーダーラインを出力せよ。

入力例1

出力例1

11
7
0

とんでもないケースですが、1 番目の会場の最大収容可能人数は 0 なので、誰も通過させたくありません。それを達成するボーダーラインで最小のものは 11 点です。

2 番目の会場の最大収容可能人数は 4 人なので、選抜する人数がそれ以下になるようなボーダーラインを設定しなければなりません。もしボーダーラインを 6 点に設定した場合、6 人通過してしまい会場の最大収容可能人数をオーバーしてしまいます。7 点に設定した場合は 3 人のみ通過し、会場に収容可能でき、これが最小のボーダーラインです。

3 番目の会場の最大収容可能人数は 12 人ですが、ボーダーラインは 0 点にします。なぜならば、選抜方法より 0 点の学生は通過できないので、正の点数を取った 12 人のみが通過するからです。

入力例2

出力例2

入力例3

出力例3

全員が 0 点のケースもありえます。この場合は、どんなボーダーラインに設定しても誰も通過しないので、会場の最大収容可能人数に関わらずボーダーラインは 0 点にします。

D - パズル

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

あなたには、以下のような縦 Hマス、横 W マスのスライドパズルの盤面が与えられます(図1)。

図1. スライドパズル盤面

各マスには、相異なる 1 から H×W-1 までの番号が割り振られており、さらにある 1 つのマスは空きマスとなっています。

このスライドパズルでは、空白マスを左右上下のマスのいずれかと入れ替える操作が許されています。ただし、入れ替えたい方向にマスが存在しない場合は入れ替えることができません。

この盤面に入れ替え操作を任意の回数行い、完成の状態にしたいと思っています。ここで、完成の状態とは、左上のマスから順番に番号付けされており右下が空白マスであるような状態にしたいと思っています(図2)。

図2. 完成盤面

つまり、完成盤面とは、

番号 i (1≦i≦H×W-1) のマスは (1+[(i-1)÷W],1+(i-1)%W) にある
さらに、空きマスが (H,W) にある

という状態を指します。[a÷b] は a を b で割った値の小数点以下を切り捨てたもの、a%b は a を b で割った余りを指します。

最小操作数が 24 回以内ということが保障されているとき、パズルを解くのに必要な最小操作数を出力しなさい。

入力

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

H W
c_{1,1} c_{1,2} … c_{1,W}
c_{2,1} c_{2,2} … c_{2,W}
:
c_{H,1} c_{H,2} … c_{H,W}

1 行目には、パズルの盤面の縦方向の長さを表す整数 H (2≦H≦6) と横方向の長さを表す整数 W (2≦W≦6) がスペース区切りで与えられる。
2 行目から H 行には、パズルの盤面の情報が与えられる。そのうち i (1≦i≦H) 行目には、スライドパズルの座標 (i,1),(i,2),...,(i,W) のマスに書かれている数字を表す整数 c_{i,1},c_{i,2},...,c_{i,W} がスペース区切りで与えられる。ただし、c_{i,j}=0のときは特別に、そのマスが空マスであることを表す。
パズルの盤面には、1 から H×W-1 までの整数が1つと、空マスを表す整数 0 がちょうど 1 つずつ現れることが保障されている。
パズルを解く最小操作数が 24 回以内ということが保障されている。

出力

1 行目に、パズルを解く最小操作数を出力せよ。末尾の改行を忘れないこと。

入力例1

出力例1

最初、空きマスは (1,2) にあります。この空きマスを「右→下→下」と動かすことで完成の状態にすることができ、そのとき最小操作回数を達成します。

入力例2

3 5
6 1 2 8 5
7 0 4 3 10
11 12 13 9 14

出力例2

入力例3

2 2
1 2
3 0

出力例3

入力例4

出力例4

パズルが元から完成している場合もあります。

入力例5

6 6
1 2 3 4 5 6
14 15 10 16 11 12
8 9 19 17 0 18
7 13 20 22 23 24
25 26 21 28 29 30
31 32 27 33 34 35

出力例5

出力する答えが最大となるケースです。