お誕生日コンテスト

X - この問題はほんとうにひどい問題であるため,できれば先に他の問題のほうをお楽しみいただければと思っておりまして,ですので他の問題を通し終えて暇になり,かつその暇を


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

このコンテストで潰そうという気になってくれた方に挑戦していただければと思います.コンテスト準備をしている段階から,本当にこんな問題を出題するのが許されるのかと大いに悩んでおりましたが,せっかくのネタ性に溢れるコンテストなので思い切って出題してみた次第です.お楽しみ頂ければ幸いです.

問題文

くぅ〜疲れましたw これにてコンテスト準備終了です!
実は、ネタ問題を考えたらコンテストの話を持ちかけられたのが始まりでした
本当はボス問題のネタなかったのですが←
ご厚意を無駄にするわけには行かないので一発ネタで挑んでみた所存ですw
以下、writer達のみんなへのメッセジをどぞ

きゅうり「みんな、解いてくれてありがとう
ちょっとクソ問なところも見えちゃったけど・・・気にしないでね!」

JAPLJ「いやーありがと!
問題の面白さは二十分に伝わったかな?」

KyuR1「解いてくれたのは嬉しいけどちょっとペナルティが多いね・・・」

じゃっぷる「解いてくれてありがとな!
正直、問題文はほとんどがコピペ改変だよ!」

kyuridenamida「・・・ありがと」キュリ

では、

きゅうり、JAPLJ、KyuR1、じゃっぷる、kyuridenamida、高橋「皆さんありがとうございました!」

きゅうり、JAPLJ、KyuR1、じゃっぷる、kyuridenamida「って、なんで高橋くんが!?
改めまして、ありがとうございました!」

本当の本当に終わり


課題

1 桁の整数,括弧,四則演算(加算・減算・乗算・除算)のみからなる式が与えられるので,その計算結果を出力せよ.


入力

t
W H
B_1
B_2B_H

t は非負整数であり,0 番から順につけられているテストケースの番号を表す.

W, H はいずれも正の整数で入力の画像の横の大きさと縦の大きさを表す.

1 \leq i \leq H に対し B_i.# のみからなる W 文字の文字列であり,その j 文字目 (1 \leq j \leq W) は画像の上から i 行目,左から j 列目の画素を表す.対応する文字が . のときその画素は白で,# のときその画素は黒である.

出力

A

A は入力の画像の黒い画素によって表される式の計算結果である.


制限

  • 全ての入力データで,H = 65かつ 1 \leq W \leq 9,000を満たす.

すべての入力データは以下のプロセスによって生成される.

  • はじめに 1 桁の整数,括弧,四則演算のみからなる L 文字以下の式で,計算結果も計算途中に現れる値も 32 ビット符号付き整数型に収まるようなものを用意する(これはランダムに生成されるとは限らない).
    また,割り算は整数除算で行われる.整数除算で得られる値は,代数的な商から小数部を切り捨てた値とする(たとえば, -7/3 = -2 である).
    なお,-5 といった負数のリテラルや -(2+3)+1 といった単項演算子を含む式は存在しない.
  • 式に含まれる各文字に対応する画像を次のようにして生成する.
    • フォント Courier Prime を用い,フォントサイズ64,太字で文字を描画した 2 値画像を作成する.
      このようにして生成した画像と,それを .# からなるテキストに変換したものをページ下部のヒントからダウンロード可能である.
    • 倍率 M (M \leq 1) を生成し,画像全体を M 倍に拡大(実質的に縮小)する.
    • 縦方向の倍率 M_h (M_h \leq 1) と横方向の倍率 M_w (M_w \leq 1) を生成し,画像全体を縦方向に M_h 倍,横方向に M_w 倍に拡大する.
    • 角度 R を生成し,画像全体を R 度回転させる.
    • 2つのパラメタ S_x, S_y を生成し,このパラメタに基いて画像を歪める.具体的には座標 (x,\, y) にある画素を (x + S_{y}y,\, S_{x}x + y) へと移す変換を行う.
  • 各文字に対応する画像を横に連結してひとつの画像を得る.このとき
    • 横方向の位置については,隣り合う文字どうしがくっついてしまわないように,文字と文字の間には 10 画素ぶんの余白を設ける.
    • 縦方向の位置については,画像全体の縦幅は拡大縮小・回転・歪みなどの操作を加える前のフォントの縦の大きさぶん用意し,そこにおさまる範囲でランダムに決められる.
  • 最後に確率 P によって,画像の各画素について確率 P でその白黒を反転させる(ノイズを生成する).

ここで式の長さの上限 L およびノイズの確率 P は入力データごとに独立な値,さらに倍率 M,\, M_h,\, M_w, 角度 R, 歪みのパラメタ S_x,\, S_y は同じテストケース中でもそれぞれの文字によって独立に生成されることに注意せよ.


採点基準

この問題の入力データは 140 個あり,0 から始まる番号が各入力データにつけられている.これは入力セクションにおける t の値に対応する.また,以下では x \in [a,\, b] という記法を「xa 以上 b 以下の実数の一様乱数によって生成する」の意味で用いる.

  • 0 \leq t < 30 を満たす入力データの生成プロセスでは
    • L = 3
    • M \in [0.9,\, 1]
    • M_h \in [0.9,\, 1],\, M_w \in [0.9,\, 1]
    • R \in [-2,\, 2]
    • S_x = 0,\, S_y = 0
    • P = 0
  • 30 \leq t < 90 を満たす入力データの生成プロセスでは
    • L = 50
    • M \in [0.9,\, 1]
    • M_h \in [0.9,\, 1],\, M_w \in [0.9,\, 1]
    • R \in [-10,\, 10]
    • S_x \in [-0.1,\, 0.1],\, S_y \in [-0.1,\, 0.1]
    • P = 0.05
  • 90 \leq t < 140 を満たす入力データの生成プロセスでは
    • L = 200
    • M \in [0.9,\, 1]
    • M_h \in [0.9,\, 1],\, M_w \in [0.9,\, 1]
    • R \in [-15,\, 15]
    • S_x \in [-0.1,\, 0.1],\, S_y \in [-0.1,\, 0.1]
    • P = 0.05

得点は次のようにして決まる.

  • 0 \leq t < 30 を満たす入力データ 1 つに正解するごとに 2 点を与える.
  • 30 \leq t < 55 を満たす入力データ 1 つに正解するごとに 2 点を与える.
  • 55 \leq t < 90 を満たす入力データ 1 つに正解するごとに 4 点を与える.
  • 90 \leq t < 140 を満たす入力データ 1 つに正解するごとに 5 点を与える.

なお,30 \leq t < 55 を満たす入力データについては,その入力ファイルおよびそれぞれを可視化した PNG フォーマットの画像をダウンロード可能である: ここだよ


入出力例

例として,次のような画像が入力される場合を考える.

この画像に対応する入力データを示す(サイズが大きいのでリンク先のファイルを参照,等幅フォントでフォントサイズを小さくすると分かりやすい).このデータのテストケース番号 999 はダミーである.

これに対しては 3 \times 3 - 4 を計算して

5

出力すればよい.


ヒント

フォントデータ

0123456789()+-*/ の 16 文字ぶんの 画像とテキスト形式のフォントデータをまとめた zip がリンクからダウンロード可能である.この zip ファイルを展開すると txt/png/ という 2 つのディレクトリがあり,それぞれ中にテキスト形式と画像(PNG形式)のフォントデータが入っている.

テキスト形式のフォントデータのフォーマットについては,本課題の入力フォーマットからテストケース番号 t を省いた形になっている.

埋め込み支援用テキスト

上記フォントデータをプログラム中に埋め込む際に使えるテキストがリンクからダウンロード可能である.適宜必要な加工をして埋め込みに用いるとよい.

注意: この埋め込みデータは約 44,000 バイトある.AtCoder で送信できるソースコードは UTF-8 で 60,000 文字以下なので,文字数制限に注意してプログラムを書くこと.

われわれの努力について

採点用に用いられるデータに対する特別な対応を行っていないプログラムで,採点用の 140 個のデータおよび同様の方法でランダム生成された 200 個ぐらいのデータに対してすべて正答するようなものが存在する(がんばりました).


writer: JAPLJ
statement: JAPLJ

Submit提出する