情画プロコン 問題 （2014/12/14実施）

1. サービス券
2. フィルタ
3. 整理整頓
4. 部分回文

リソース制約（全問共通）

Lv1. サービス券

問題文

K君はサービス券を$N$ 枚持っている。
このサービス券は$M$ 枚集めるとあるイベントに無料で参加でき、1回イベントに参加するとサービス券を1枚もらうことができる。
K君が無料でイベントに参加できる最大回数は何回か？

入力

2つの整数$N$ , $M$ の1行からなる。

N M

$N$ は初期状態で持っているサービス券の数、$M$ は1回のイベントの無料参加に必要なサービス券の数を表す。

出力

K君が無料でイベントに参加できる最大回数を出力せよ。 末尾に改行文字を入れること。

制約

• $0≦N≦1000$
• $2≦M≦1000$

サンプル

入力1

5 5

出力1

1

K君は最初5枚のサービス券を持っています。
1回イベントに参加するのに必要な枚数は5枚なので、1回だけイベントに参加することができます。
参加した後、サービス券が1枚もらえますが、5枚に満たないので次のイベントに参加することはできません。
よって、1を出力します。

入力2

25 5

出力2

6

K君は最初25枚のサービス券を持っています。
1回イベントに参加するのに必要な枚数は5枚なので、5回イベントに参加することができます。
参加した後、サービス券が合計5枚もらえます。もらった5枚でさらにイベントに1回参加することができます。
よって、5 + 1 = 6を出力します。

入力3

0 5

出力3

0

K君は1枚もサービス券を持っていません。
1回もイベントに参加できないので、0を出力します。

入力4

1000 3

出力4

499

Lv2. フィルタ

問題文

$N$個の整数からなる数列$A$（$0≦A_i≦255$, $1≦i≦N$）が与えられる。
この数列に以下の処理を施して、新たな数列$B$ を作る。

• すべての$i(1≦i≦N)$について
• $A_{i-1}$, $A_i$, $A_{i+1}$ の中央値を $m$ とする。
  • このとき、$i=1$ については、中央値 $m$ は$A_1$ と$A_2$ の平均である。
  • $i=N$ については、中央値 $m$ は$A_{N-1}$ と$A_N$ の平均である。
  • $m$ が小数となる場合は、$m$ の小数点以下を切り捨てする。
• $B_i = m$

このようにして作られる新たな数列$B$を出力せよ。

入力

1行目は1つの整数$N$からなる。 2行目は、$N$個の整数$A_i$が空白区切りで記述されている。

N
A1 A2 A3 … AN

$N$は数列の要素数、$A_i$は数列の内容を表す。 $N$, $A_i$は整数である。

出力

処理を施して得られる配列$B$を半角スペースで区切って1行に出力せよ。
末尾に改行を出力すること。

制約

• $3≦N≦1000$
• $0≦A_i≦255$

サンプル

入力1

3
1 2 3

出力1

1 2 2 

• $B_1$ = ($A_1$ + $A_2$) / 2 = 3 / 2 = 1 (小数点以下切り捨て)
• $B_2$ = ($A_1$と$A_2$と$A_3$の中央値) = 2
• $B_3$ = ($A_2$ + $A_3$) / 2 = 5 / 2 = 2 (小数点以下切り捨て)
  となるので、「1 2 2」を出力します。

入力2

4
10 20 30 40

出力2

15 20 30 35 

• $B_1$ = ($A_1$ + $A_2$) / 2 = 30 / 2 = 15
• $B_2$ = ($A_1$と$A_2$と$A_3$の中央値) = 20
• $B_3$ = ($A_2$と$A_3$と$A_4$の中央値) = 30
• $B_4$ = ($A_3$ + $A_4$) / 2 = 70 / 2 = 35
  となるので、「15 20 30 35」を出力します。

入力3

12
10 20 30 255 50 60 70 80 90 255 110 120

出力3

15 20 30 50 60 60 70 80 90 110 120 115 

Lv3. 整理整頓

問題文

縦2[m], 横$X$ [m]の長方形の箱がある。
この箱に、縦1[m], 横$L_i$ [m]のブロック$N$ 個を詰める。
ただし、$L_i$ は$i$ 個目（$1≦i≦N$） のブロックの横の長さで、整数である。

箱の中央に図のように仕切りがあり、領域が分かれているので、ブロックは回転して箱に入れることはできない。

このとき、ブロック$N$ 個を箱に詰めることができるかどうかを判定せよ。

入力

1行目は2つの整数$N$, $X$ からなる。 2行目は、$N$ 個の整数$L_i$が空白区切りで記述されている。

N X
L1 L2 L3 … LN

$N$ はブロックの数、$X$ は箱の横の長さ、$L_i$ は$i$ 番目のブロックの横の長さを表す。
$N$, $X$, $L_i$ は整数である。

出力

縦2[m], 横$X$[m]の長方形の箱にすべてのブロックを詰めることができる場合は、

possible

そうでない場合は

impossible

と出力せよ。末尾に改行を出力すること。

制約

• $1≦N≦16$
• $1≦X≦1000$
• $1≦L_i≦100$

サンプル

入力1

3 30
10 20 30

出力1

possible

わかりやすいように、縦2[m], 横$X$[m]の箱の上半分を領域A、下半分を領域Bとします。

横の長さが10m, 20m, 30mのブロックがあります。

領域Aに横の長さが10mと20mのブロック、領域Bに30mのブロックを入れることでぎりぎり箱(横の長さが30m)に入れることができます。

よって出力は"possible"になります。

入力2

3 30
20 20 20

出力2

impossible

どのように入れても箱をはみ出してしまいます。よって"impossible"を出力します。

入力3

2 10
3 3

出力3

possible

どのように入れても箱に入れることができます。よって"possible"を出力します。

入力4

16 68
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

出力4

possible

領域Aに10m,13m,14m,15m,16m、
領域Bに1m,2m,3m,4m,5m,6m,7m,8m,9m,11m,12mのブロックを入れることで
箱にぴったり入れることができます。よって"possible"を出力します。

Lv4. 部分回文

問題文

1～9の数字からなる文字列$S$ について考える。
$S$ のある部分文字列について、回文となるものがあるとき、$S$ は「部分回文」であると定義する。
ただし、部分文字列とは、$S$ の中で2文字以上連続する文字列とする（$S$ 自身も含む）。
また、回文とは、前から読んでも後ろから読んでも同じ文字列である。

例えば、$S$ = "124341" の場合、
部分文字列 "434" が回文となるので、$S$ は部分回文である。

さて、K君は未完成の文字列$S'$ を与えられた。
$S'$ は文字*と1～9の数字から構成される。
K君は$S'$ の*となっている部分に1～9の数字どれかを入れて「部分回文でない」文字列を作る。
このような文字列は何通り考えられるか。答えを1000000007で割った余りを求めよ。

入力

1つの文字列$S'$からなる。

S'

$S'$はK君に与えられた未完成の文字列である。
$S'$は文字*と1～9の数字のうちどれかで構成されている。
$S'$の長さ$|S'|$について、$2≦|S'|≦1000$を満たす。

出力

K君が作ることのできる「部分回文でない」文字列の個数を1000000007で割った余りを出力せよ。
末尾に改行を出力すること。

制約

• $2≦|S'|≦1000$

部分点制約

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

• 採点用入出力データのうち、50%は「$2≦|S'|≦5$」を満たす。
• 採点用入出力データのうち、70%は「$2≦|S'|≦50$かつ、$|S'|$の中の文字*の数が5個以下」を満たす。

例えば、「$2≦|S'|≦5$」を満たす入力に対して、リソース制限を満たし正しい答えを出力するプログラムを提出すれば、
50%分の得点（つまり150点）が保証される。

サンプル

入力1

*1

出力1

8

K君は1つの*に1～9の数字を入れます。
入れる数字が1でなければ「部分回文でない」文字列が作れます。
("21", "31", "41", "51", "61", "71", "81", "91")　の8通り作れます。

入力2

**

出力2

72

K君は2つの*に1～9の数字を入れます。
この2つの数字が異なれば、「部分回文でない」文字列が作れます。
よって、そのような並べ方は　9 * 8 = 72　通りとなります。

入力3

1**

出力3

56

2つの*には1を入れてはいけません。
さらに、2つの*は異なる数字である必要があります。
よって、 8 * 7 = 56 を出力します。

入力4

1*1

出力4

0

*にどんな数字を入れても部分回文になります。
よって0を出力します。

入力5

123

出力5

1

既に、「部分回文でない」文字列ができています。
この文字列自身の1通り作れます。

入力6

********************

出力6

228831882

1000000007で割った余りを出力するのに注意してください。