東京大学プログラミングコンテスト2012

F - Uinny


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

Uinny は言わずと知れた自作ポエムを共有するツールである。 このソフトウェアを使ってポエムを共有するためには、まずポエムを Uinny に登録し、そのポエムから計算することができるハッシュと呼ばれる文字列を、有名な掲示板に投稿する必要がある(ここまでの作業を放流と呼ぶ)。ポエムを読みたいと思った人は、そのハッシュを Uinny に打ち込むことにより、自動的にポエムがダウンロードされるという仕組みになっている。 あなたは HAIKU と呼ばれる一種のポエムを創作するのが趣味である。 HAIKU とは小文字アルファベットを50文字以下で繋げた短い並びに、自然の美しさ、恋の辛さ、人生の儚さ、などの思いを託した芸術作品である。 あなたは素晴らしい HAIKU を幾度も放流した実績により、掲示板では神と呼ばれるほどの名声を確立していた。 ところがある日、公開した HAIKU の評判をみようと掲示板を開くと、自分に対する罵詈雑言が大量に投稿されている事に気づいた。 どうやら自分が公開したハッシュが他の有名な作品のハッシュと同じものとなってしまい、自分が盗作、著作権法違反をしたかのような扱いとなっているのだ。 たまたま同じハッシュが生成されただけで、自分の本当の作品は別にあると主張したが、掲示板の匿名ユーザーは聞く耳を持ってくれない。 そこであなたは同じハッシュを持つ複数の HAIKU を生成することで、このような現象は起こりうるのだと立証することにした。 Uinny の技術という本によると、ある HAIKU s のハッシュ h は、

h = 0
for i=0,...|s|-1
    h = (h * a + (s[i] - 'a' + 1)) % b

として計算されるようだ、 ただしここで、 s[i] は si番目の文字を表し、(s[i] - a + 1) は、s[i]=aならば 1 であり、s[i]=z ならば 26 となる式である。

a と b の値はプログラムを解析すると簡単にわかるらしい。 さあ、同じハッシュを持つ HAIKU を大量に生成して、自分の容疑が冤罪であると立証するのだ!


入力

1 行に数値a bが空白区切りで与えられる。

出力

ハッシュが同じ,すべて小文字アルファベットの,互いに異なる文字列(長さは50まで) を最大 100 個、それぞれ 1 行に 1 個ずつ出力せよ.

制約

部分点

出力できた文字列の個数をnとしたとき,各テストケースごとに,n% の点が入る. すなわち,以下のようにしてこの問題の点数は計算される.

テストケース数を N とする. i番目のテストケースのスコアs_i を,出力した文字列の個数として定める. ただし,誤答の場合や,100より多くの文字列を出力した場合は, s_i = 0 となる. すべてのs_iの総和をSとしたとき, この問題の点数として,2S/N 点が与えられる.


入力例 1

26 52

入力例 1 に対する出力例

aaz
baz
caz
daz
eaz
faz
gaz
haz
iaz
jaz
kaz
laz
maz
naz
oaz
paz
qaz
raz
saz
taz
uaz
vaz
waz
xaz
yaz
zaz
aaaz
abaz
acaz
adaz
aeaz
afaz
agaz
ahaz
aiaz
ajaz
akaz
alaz
amaz
anaz
aoaz
apaz
aqaz
araz
asaz
ataz
auaz
avaz
awaz
axaz
ayaz
azaz
baaz
bbaz
bcaz
bdaz
beaz
bfaz
bgaz
bhaz
biaz
bjaz
bkaz
blaz
bmaz
bnaz
boaz
bpaz
bqaz
braz
bsaz
btaz
buaz
bvaz
bwaz
bxaz
byaz
bzaz
caaz
cbaz
ccaz
cdaz
ceaz
cfaz
cgaz
chaz
ciaz
cjaz
ckaz
claz
cmaz
cnaz
coaz
cpaz
cqaz
craz
csaz
ctaz
cuaz
cvaz

Submit提出する