Time Limit: 2 sec / Memory Limit: 64 MB
Description
今学期あなたは，k単位以上取得できなければ，留年してしまうことが分かった．なんとしてもそれは避けたいので，n個の講義の中からいくつか選んで，k単位を取得したいと思う．
事前の調査によって，各講義で単位を取得するために最低限必要な出席回数が分かった．学校などできるだけ行きたくないので，k単位以上取得するために必要な最小の出席回数を求めよう．
Input
入力は複数のテストケースからなる．入力の終わりは2つの0のみを含んだ行で示される．各テストケースは以下の形式で与えられる．
n k x_1 … x_n
- 1 ≦ n ≦ 100
- 1 ≦ k ≦ n
- 0 ≦ x_i ≦ 100
テストケースの1行目には，2つの整数n, kが書かれている．nは講義の数を表し，kは必要な単位の数を表す．
テストケースの2行目には，n個の整数x_iが書かれている．x_iはi番目の授業の単位を修得するのに必要な出席回数を表す．
各講義で取得できる単位数は，すべて1単位である．テストケースの数は1つのファイルにつき1,000個以下であることが保証されている．
Output
各テストケースに対して，最低限出席しなければならない回数を1行で出力せよ．
Sample Input
5 1 4 6 1 3 6 5 3 4 6 1 3 6 10 10 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output
1 8 0
Source Name
ふか杯 5th ContestTime Limit: 2 sec / Memory Limit: 64 MB
Description
O氏は長い間ずっと大学に閉じ込められていたが，自分の後継となる者Fを見つけ後の事を全てそのFにたくし，n年の時を経て外の世界に旅立つことにした．(0は自然数)
大学から外の世界に出るためには，まず大学を卒業しなければならない．なんと，O氏はこの事を事前に想定し，一定時間がたつと自動的にO氏が卒業したことにするプログラムを大学のコンピュータに埋め込んでいたのだ．しかし，仕込んだ日時は記録しているのだがプログラムを仕込んだのがずいぶん昔なため卒業する正確な時刻を忘れてしまった．仕込んだプログラムを見てみると，仕込んだ時刻から2進数で111....11秒後に発動する設定になっていた．
O氏は周りの人に不審に思われないように卒業するために，仕込んだプログラムが発動する時刻を計算することにした．
(この問題では，閏秒はないものとして考えること)
Input
入力は複数のテストケースからなる．入力の終わりは1つの0のみを含んだ行で示される． 各テストケースは以下の形式で与えられる．
year/month/day hh:mm:ss time
- 1900 ≦ year ≦ 20012
- 01 ≦ month ≦ 12
- 01 ≦ day ≦ 31
- 00 ≦ hh ≦ 23
- 00 ≦ mm,ss ≦ 59
テストケースの1行目には，年，月，日，時間，分，秒が書かれている．これらはO氏がプログラムを仕込んだ時刻を表している．月，日，時間，分，秒は必ず2桁で与えられる．(値が10未満の場合，10の位は0埋めされる)
テストケースの2行目には，1のみから成る文字列timeが書かれている．これはプログラムが発動するまでの時間を2進数で表したものである．timeの長さは1文字以上30文字以下である．
存在しない日付は与えられないことが保証されている．テストケースの数は1つのファイルにつき5,000個以下であることが保証されている．
Output
各テストケースに対して，プログラムが発動する時刻を入力と同じ形式で1行に出力せよ．
Sample Input
2012/04/14 17:45:00 1 2012/02/29 17:45:00 111 2012/02/02 00:00:00 11111111 2012/04/14 20:16:15 1111111111111111 2002/09/28 02:35:44 1111111111111111111111111111 2005/12/11 12:00:00 111111111111 2009/12/20 15:00:00 11111111111111 2006/11/18 05:11:29 11111111111111111111111111111 20012/12/31 23:59:59 111111111111111111111111111111 0
Sample Output
2012/04/14 17:45:01 2012/02/29 17:45:07 2012/02/02 00:04:15 2012/04/15 14:28:30 2011/03/31 23:59:59 2005/12/11 13:08:15 2009/12/20 19:33:03 2023/11/23 00:00:00 20047/01/10 13:37:02
Hint
各月はそれぞれ以下の日数分ある．
- 1月：31日
- 2月：28日
- 3月：31日
- 4月：30日
- 5月：31日
- 6月：30日
- 7月：31日
- 8月：31日
- 9月：30日
- 10月：31日
- 11月：30日
- 12月：31日
ただし，年が400の倍数で割り切れるか，100の倍数で割り切れず4の倍数で割り切れる閏年の時には2月は29日分存在する．
Source Name
ふか杯 5th ContestTime Limit: 2 sec / Memory Limit: 64 MB
Description
w*hのグリッドがある．
グリッド上のおのおののマスには，高さが設定されている．
今，いくつかのマスの上から液体を注ぐ．
あるマスの上に液体が存在し，そのマスの高さよりもそこから隣接するマスの高さの方が低いとき，液体は隣接するマスへ広がっていく．ただし，グリッド上の2つのマスは辺を共有するときに隣接していると見なす．
液体が広がるマスの個数を求めよ．
Input
入力は複数のテストケースからなる． 入力の終わりは，3つの0のみを含んだ行で示される． 各テストケースは，以下の形式で与えられる．
w h p
z_{00} z_{01} … z_{0(w-1)}
z_{10} z_{11} … z_{1(w-1)}
…
z_{(h-1)0} z_{(h-1)1} … z_{(h-1)(w-1)}
x_1 y_1
…
x_p y_p
- 1 ≦ w，h ≦ 20
- 0 ≦ p ≦ wh
- 0 ≦ z_{ij} ≦ 100
- 0 ≦ x_i < w
- 0 ≦ y_i < h
テストケースの1行目には，3つの整数w，h，pが書かれている． w，hはそれぞれグリッドの横幅と縦幅を表し，pは液体を注ぐ回数を表す．
続くh行には，それぞれw個の整数z_{ij}が書かれている． z_{ij}は(j，i)のマスの高さを表す．
続くp行にはそれぞれ2個の整数x_i，y_iが書かれている． x_i，y_iは(x_i，y_i)のマスに液体を注ぐことを示す．
ただしすでに液体を注いだマスにもう一度液体を注ぐこともある．
テストケースの数は1つのファイルにつき20個以下であることが保証されている．
Output
各テストケースに対して，液体が広がるマスの個数を1行に出力せよ．
Sample Input
2 2 1 1 0 0 1 1 0 2 2 1 1 0 0 1 1 1 1 1 0 100 5 5 2 5 4 5 5 5 5 3 5 1 5 5 2 1 2 5 5 3 5 3 5 5 5 5 5 5 0 0 2 2 0 0 0
Sample Output
1 3 0 5
Source Name
ふか杯 5th ContestTime Limit: 5 sec / Memory Limit: 64 MB
Description
1つの数字が書かれた節点がn個ある．このn個の節点をすべて使って2分木を作る．2分木の定義については，例えば Wikipedia のページなどを参照すること．
木の重さを，その木に含まれる数字の和で定義する．木が空集合の場合，その重さは0であるとする．
次のことが成り立つとき，木は安定であると呼ぶ : 葉を除くすべての節点について左部分木と右部分木の重さの差の絶対値がa以上b以下となる．ここで，左の子を根とする部分木(左の子が存在しない場合は空集合)を左部分木と呼び，同様に右の子を根とする部分木を右部分木と呼ぶことにする．
n個の節点の値とa，bが与えられたとき，安定な2分木の個数を出力せよ．ただし，2分木の数を数える際は，n個の節点を全て区別する．また，子節点の順序が異なったり，節点の親子関係が異なる場合も区別して数える．
Input
入力は複数のテストケースからなる．入力の終わりは3つの0のみを含んだ行で示される．各テストケースは以下の形式で与えられる．
n a b x_1…x_n
- 1 ≦ n ≦ 13
- 0 ≦ a,b ≦ 2000
- 1 ≦ x_i ≦ 100
テストケースの1行目には3つの整数n，a，bが書かれている．
テストケースの2行目にはn個の整数x_iが書かれている．x_iはi番目の点に書かれている数字を表す．
テストケースの数は1つのファイルにつき20個以下であることが保証されている．
Output
各テストケースに対して，条件を満たす2分木の個数を1行で出力せよ．
Sample Input
1 0 100 1 2 3 3 1 2 3 0 2 1 2 3 10 0 10 1 2 3 4 5 6 7 8 9 10 13 0 10 1 2 3 4 5 6 7 8 9 10 11 12 13 0 0 0
Sample Output
1 0 6 164650496 213181735360
Source Name
ふか杯 5th ContestTime Limit: 5 sec / Memory Limit: 128 MB
Description
Fは6面ダイスを1個使って進むすごろくに一人で挑戦しようとしている．
すごろくのマスの中には「○マス進む」と「振り出しに戻る」が存在し，そこに止まってしまうと，必ず指示された通りに移動しなければならない．マスの効果で移動した結果，再び効果のあるマスに止まった場合は，続けて指示通りに移動する．
Fはものぐさなので，実際にすごろくを遊ぶのはめんどくさくなってしまった．そこで，ゴールまでのダイスを振る回数の期待値を求めることにした．
Input
入力は複数のテストケースからなる．入力の終わりは1つの0のみを含んだ行で示される．各テストケースは以下の形式で与えられる．
n x_1 x_2 … x_n
- 1≦n≦500,000
- -1≦x_i≦n-i
- x_1,x_n=0
テストケースの1行目には，すごろくのマスの数nが書かれている．マスには1番からn番までの番号がふられている．スタートのマスが1番で，それからスタートに近い順に2番，3番，…，n-1番と続き，ゴールのマスがn番である．i番のマスでサイコロを振ってjの目が出たら，i+j番のマスへ移動する．もしもi+jがn以上である場合，ゴールしたとみなされる．
テストケースの2行目には，n個の整数x_iが書かれている．x_iはi番目のマスに書かれている指示を表す．x_i = -1 ならば「振り出しに戻る」，0 < x_i ≦ n-i ならば「x_iマス進む」，x_i = 0 ならそのマスには何の効果もない．
x_1, x_n は0であることが保証されている．与えられるすごろくはゴール可能であり，ダイスを振る回数の期待値は10^7以上にならないことが保証されている．テストケースの数は1つのファイルにつき300個以下であることが保証されている．また，1つのファイルにつきnの合計は500,000以下であることが保証されている．
Output
各テストケースに対して，ダイスを振る回数の期待値を1行に出力せよ．誤差は，絶対誤差もしくは相対誤差で10^{-7}まで許容される．
Sample Input
2 0 0 7 0 -1 -1 -1 -1 -1 0 7 0 0 0 0 0 0 0 7 0 5 4 3 2 1 0 8 0 -1 -1 -1 0 -1 -1 0 0
Sample Output
1.00000000 6.00000000 2.16139403 1.00000000 10.50000000
Source Name
ふか杯 5th ContestTime Limit: 2 sec / Memory Limit: 128 MB
Description
2次元平面上にマラカス(点)がn個ある． バスターでマラカスをなるべくたくさん撃ち抜きたい． バスターは幅2w，長さ無限大の矩形の大きさを持ち，矩形の幅の中心を原点が通るように原点から発射される． 適切にバスターを打ち出す角度を決めたとき最大何個のマラカスを撃ち抜けるか答えよ．
Input
入力は複数のテストケースからなる．入力の終わりは2つの0のみを含んだ行で示される． 各テストケースは以下の形式で与えられる．
n w x_1 y_1 … x_n y_n
- 1≦n≦100,000
- 1≦w≦1,000
- 0≦x_i，y_i≦100,000
テストケースの1行目には2つの整数n，wが書かれている． nはマラカスの数を表し，wはバスターの半径を表す．
続くn行にはそれぞれ2つの整数x_i，y_iが書かれている． x_i，y_iはi番目のマラカスの座標を表す．
2つのテストケースの間には空行がひとつ入る．
wを±10^{-6}変更しても答えは変わらないことが保証されている． テストケースの数は1つのファイルにつき1,000個以下であることが保証されている． また，1つのファイルにつきnの合計は300,000以下であることが保証されている．
Output
各テストケースに対して，撃ち抜けるマラカスの最大個数を1行に出力せよ．
Sample Input
1 1 2 2 4 1 3 3 4 4 5 5 6 6 3 2 1 1 2 1 3 1 7 3 10 3 10 5 10 7 10 9 10 11 10 13 10 15 2 1000 10 10 10 10 5 10 100 20 110 21 48 9 4 240 5 2012 0 0
Sample Output
1 4 3 5 2 3
Hint
サンプルの4つ目のテストケースは以下の様にすれば5個のマラカスを撃ち抜ける．
Source Name
ふか杯 5th ContestTime Limit: 5 sec / Memory Limit: 256 MB
Description
w*hの二値画像がある．この画像上に絵を描いていたのだが誰かがいたずらで部分的に白と黒の画素の値を入れ替えてしまった．元の画像を復元するために色々文献をあさって調べた結果以下の手法を用いることにした．
- ノイズ（いたずらされた画素）は十分少ないとみなす．
- いたずらされた画像の(x,y)の画素の値をY(x,y)とする．
- 復元後の画像の(x,y)の画素の値をX(x,y)とする．
- (x,y)の4近傍(上下左右)をd(x,y)とする．
- 式
![E=\sum_{(x,y)\in\{W\times H\}}\lambda|X(x,y)-Y(x,y)| +
\sum_{(x,y)\in\{w\times h\}}\sum_{(nx,ny)\in d(x,y)}\frac{\kappa}{2}|X(x,y) - X(nx, ny)|]]( http://fuka5.contest.atcoder.jp/img/other/fuka5/Equ.png)
を考える． - Eを最小にするような復元後の画像を選ぶのがもっとも良い．
- ちなみに，式の前半は画像をあまり変えないように働き，後半部分は色が激しく変化させないように働く．
方法が決まったので，プログラムを書いて絵を復元することにした．
Input
入力は複数のテストケースからなる．入力の終わりは4つの0のみを含んだ行で示される． 各テストケースは以下の形式で与えられる．h w λ κ Y(1,1)Y(2,1)...Y(w,1) Y(1,2)Y(2,2)...Y(w,2) ... Y(1,h)Y(2,h)...Y(w,h)
- 1<=h,w<=50
- 0.000<λ,κ<=1.000
λ,κは0.001刻みで与えられる．
テストケースの1行目には2つの整数h，wと2つの実数λ，κが書かれている． w，hはそれぞれ画像の横幅と縦幅を表し，λ，κは最小化する目的の式Eのパラメータを表す．
続くh行にはそれぞれ.と#で構成される長さwの文字列が書かれている．
Y(x,y)はいたずらされた後の画像の(x,y)の画素の値であり,.が0を表し，#が1を表す．
テストケースの数は1つのファイルにつき300個以下であることが保証されている． また,1つのファイルにつきw*hの合計は8,000以下であることが保証されている．
Output
各テストケースに対して，最小値を与えるEを一行に出力し,次のh行にその最小値を与える画素の割り当てを入力と同じ形式で出力せよ． 誤差は，絶対誤差もしくは相対誤差で10^{-6}まで許容される． 最小値を与える割り当てが複数ある場合はどれを出力しても良い．
Sample Input
10 10 0.4000 0.20 .##...###. .##.####.. .######... .#.#.####. ######.... ##.##..... ....#..... ..####.#.. .#####.##. .#####.##. 25 38 0.5 0.24 ...........#...............#.......... ...........###..........####.......... ....##.....#####.......####........... .....##.....###############.....##.... ............#####.###.#####......#.... ............#########.####............ .....##......#########.###............ ....##......#####.#########........#.. ....#......##.##..####..####.......... .......#...###########.#####...#...... .......##.##################..##...... ........#####.####.##.######.##....... ..........####################........ .........##.##..########..#####....... .......######....##..#....###.##...... ......###.####...##.##..#####.##.#.... ....###..##..#...#####..#..########... ..####..###.....#######......#######.. ...#######......#######........###.... ..####.........##.######........###... ...............###...###.............. ..............#######..#...#...##..... .........#....##########...#....#..... ..#.....##.....########............... ...............########............... 0 0 0 0
Sample Output
11.200000 .##...###. .##.####.. .######... .######... ######.... ##.##..... ....#..... ..####.... .#####.##. .#####.##. 73.540000 ...........#...............#.......... ...........###..........####.......... ...........#####.......####........... ............###############........... ............###############........... ............##############............ .............#############............ ............###############........... ...........#################.......... .......#...#################...#...... .......##.##################..##...... ........####################.##....... ..........####################........ .........#####..########..#####....... .......######....#####....######...... ......########...#####..########.#.... ....#######..#...#####..#..########... ..#########.....#######......#######.. ...#######......#######........###.... ..####.........#########........###... ...............#########.............. ..............##########.............. ..............##########.............. ...............########............... ...............########...............