Time Limit: 2 sec / Memory Limit: 64 MB
問題文
近年、急成長を遂げているソフトウェア会社"天下一株式会社"は他社にはない採用ルールを設けている。
それは、今後の成長を見越し、毎年4月1日に現在の社員数と同数の新入社員を入社させるというものである。
天下一株式会社は人気企業であり、定員割れを起こすことは無く、採用された者は必ず入社する。
この採用以外で入社する者は存在せず、また退職する社員はいないので社員数が減少することもない。
天下一株式会社は 42 人の天下一級なメンバーにより創立された。
上記の採用ルールにより、創立後の最初の4月1日には 42 人の社員を入社させ、社員数は計 84 人となった。
そして20XX年、ついに初めてその社員数が1億3千万人 ( 130000000 人 ) を超えた。
1億3千万人を超えた直後の"天下一株式会社"の社員数を答えよ。
入力
この問題では入力は与えられない。
出力
1億3千万人を超えた直後の"天下一株式会社"の社員数を標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。
Source Name
天下一プログラマーコンテスト2013 予選ATime Limit: 2 sec / Memory Limit: 64 MB
問題文
天下一株式会社の主催するプログラミングコンテストでは、問題の難易度を 5 つの整数値のパラメータ ( 0 以上 20 以下 ) で表現している。
5 つのパラメータはそれぞれ、
- 問題文の複雑さ
- 実装の複雑さ
- 解法の難しさ
- 入力の複雑さ
- テストデータの厳しさ
を意味している。
問題の難易度はそれらのパラメータの総和を S としたとき、以下の通りに決定される。
- 85 \leq S \leq 100 の場合、 難易度E
- 70 \leq S \lt 85 の場合、 難易度D
- 60 \leq S \lt 70 の場合、 難易度C
- 20 \leq S \lt 60 の場合、 難易度B
- 0 \leq S \lt 20 の場合、 難易度A
天下一株式会社の新入社員であるショウヘイ君は用意された N 個の問題の中から、難易度Aの問題の個数を数えることを命じられた。
ショウヘイ君の友人であるあなたはプログラムを書いて彼を助けることにした。
入力
入力は以下の形式で標準入力から与えられる。
N V_1 W_1 X_1 Y_1 Z_1 : : V_N W_N X_N Y_N Z_N
- 1 行目は、問題の数を表す整数 N (1 \leq N \leq 100) が与えられる。
- 2 行目から N 行には、 i ( 1 \leq i \leq N ) 番目の問題の、問題文の複雑さを表す整数 V_i 、実装の複雑さを表す整数 W_i 、解法の難しさを表す整数 X_i 、入力の複雑さを表す整数 Y_i、テストデータの厳しさを表す整数 Z_i ( 0 \leq V_i, W_i, X_i, Y_i, Z_i \leq 20 ) が空白区切りで与えられる。
出力
難易度Aの問題の数を標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。
入力例 1
2 3 3 3 3 3 4 4 4 4 4
出力例 1
1
Source Name
天下一プログラマーコンテスト2013 予選ATime Limit: 2 sec / Memory Limit: 64 MB
問題文
パズル作家のショウヘイ君は、天下一級のプログラマであるあなたに、「あるパズル」を出題して対決することになった。
そのパズルは以下のようなルールを持つものだった。
- M \times N のマス目が用意されており、そのマスすべてに対して 1, 2, 3 のいずれかの数字を以下の条件を満たすように入れていく。
- 同じ行または同じ列にある同じ数字のマスの間には、そのマスの数字以上の個数のマスが存在する。
このパズルでの数字の配置の仕方が何通りあるかを答えよ。
ただし、回転や反転によって同じになる配置も別々のものとして数える。
例えば、3 \times 3 のマス目に対しては以下のような配置ができる。
縦または、横一列に 1 が 2 つ以上存在している場合は以下のように間に 1 マス以上空いていなければならない。
2 を配置する場合は 2 マス以上空いていなければならない。
入力
入力は以下の形式で標準入力から与えられる。
M N
- 横方向のマスの数 M と 縦方向のマスの数 N ( 1 \leq M, N \leq 10^6 ) が空白区切りで 1 行で与えられる。
部分点
- M, N \leq 4 の入力に正解すると、120 点満点に対して部分点として 40 点が与えられる。
- M, N \leq 100 の入力に正解すると、120 点満点に対して部分点として、さらに 20 点が与えられる。
出力
数字の配置の仕方が何通りあるかを標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。
入力例 1
1 1
出力例 1
3
入力例 2
3 1
出力例 2
8
Source Name
天下一プログラマーコンテスト2013 予選ATime Limit: 2 sec / Memory Limit: 64 MB
問題文
あなたは友人のタクヤ君から独自の方式で圧縮された文字列とそれを展開した後に参照すべき部分の位置と長さを受け取ったので、
参照すべき部分の文字列を得るプログラムを作成する必要がある。
圧縮前の文字列は英字のみからなる文字列である。
そして、英字のみからなる部分文字列 x が n 回繰り返す部分を (x)n に置換することで圧縮を行う。
ただし、|x| \geq 1、n \geq 1 とする。 ( |x| は x の文字列長 )
例えば、 ABABABA は (AB)3A に置換することができる。
また、この置換操作は任意の回数行うことができる。
例えば、AAABBAAABB は (AAABB)2 に置換した後、 さらに、((A)3BB)2 、 ((A)3(B)2)2 と置換することができる。
以上より、圧縮後の文字列 ( input ) は以下のEBNFに従う。
input = string,{string} ;
string = alphabet,{alphabet} | "(",input,")",positive_number ;
alphabet = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" |
"N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" |
"a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" |
"n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" ;
positive_number = digit_excluding_zero,{digit} ;
digit_excluding_zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit = "0" | digit_excluding_zero ;
入力
入力は以下の形式で標準入力から与えられる。
B L N S
- 1 行目には、展開後に参照するべき部分の開始位置 B ( -M \leq B \lt M ) 、参照するべき長さ L ( 1 \leq L \leq 10^5 ) 、 圧縮後の文字列の長さ N ( 1 \leq N \leq 10^4 ) が、スペースで区切られて、それぞれ整数で与えられる。 ただし、M は圧縮前の文字列の長さ とする。
- 2 行目には、圧縮後の文字列 S が与えられる。
- B は、非負の場合は先頭を 0 とした先頭からの位置を表し、負の場合は末尾を -1 とした末尾からの位置を表す。
- B の正負に関係なく、開始位置から末尾方向への L 文字が参照すべき文字列であり、この長さの文字列が得られることは保証される。
- 圧縮前の文字列の長さは 10^{15} を超えない。
部分点
- 圧縮前の文字列の長さをMとし、 L, N \leq 100, M \leq 1000 の入力に正解すると、130 点満点に対して部分点として 50 点が与えられる。
- L, N \leq 100 の入力に正解すると、130 点満点に対して部分点として、さらに 50 点が与えられる。
出力
参照するべき文字列を標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。
入力例 1
0 7 6 (AB)3A
出力例 1
ABABABA
入力例 2
-6 5 11 ((A)3(B)2)2
出力例 2
BAAAB
Source Name
天下一プログラマーコンテスト2013 予選ATime Limit: 2 sec / Memory Limit: 64 MB
問題文
天下一プログラマーコンテストのモノクロポスターが、高橋君のいたずらにより、バラバラにされてしまいました。
ポスターは、H*W個の正方形のタイルを、縦H個、横W個の長方形に敷き詰めて構成されていたのですが、高橋君によって、全てタイル４つで構成される、トの字型のピースに分解されてしまっています。
幸運なことに、元のデジタルデータは残っていましたが、残念なことに、印刷するための紙がありません。
仕方がないので、あなたはこのピースから、ポスターを修復しなければいけません。
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 : : S_H N P_1 P_2 : : P_n
- 1 行目には、ポスターの縦の長さ H と横の長さ W ( 4 \leq H,W \leq 12 )が、スペースで区切られて、それぞれ整数で与えられる。
- H, W はそれぞれ 4 で必ず割り切れる。
- 2 行目から H 行は、元のポスターを表す文字列 S_i が与えられる。この文字列は各行とも W 文字である。
- S_i のj文字目は、左上のタイルを (1,1) とした座標 (j,i) における、タイルの色を表す。 '#'が黒いタイル、'.'が白いタイルを表す。
- H + 2 行目には、ピースの数 N が与えられる。
- H + 3 行目から N ( N = H * W / 4)行には、与えられるピースの模様の種類 P_i (1 \leq P_i \leq 16)が与えられる。模様の種類は以下の16種類である。
. # . # . # . # . # . # . # . # .. .. #. #. .# .# ## ## .. .. #. #. .# .# ## ## . . . . . . . . # # # # # # # # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
部分点
- H, W \leq 4 の入力に正解すると、150 点満点に対して部分点として 30 点が与えられる
- H, W \leq 8 の入力に正解すると、150 点満点に対して部分点として追加で 50 点が与えられる
出力
パズルを修復する方法を n 行で出力してください。パズルが復元不可能である場合は、-1と出力してください。
i行目には、P_iの置くべきX座標、Y座標、回転方向の3つの整数をスペース区切りで出力してください。
なお、回転方向は、下図のように時計回りに表し、ポスターの左上の座標を(1, 1)とし、下記の図のAの位置の座標を出力するとします。
A DBA D BC C CB C D A ABD 0 1 2 3なお、行の終端には改行が必要です。答えが複数ある場合は、どれを出力しても構いません。
入力例 1
4 4 #... .#.. ..## ..## 4 9 6 1 8
出力例 1
1 4 3 1 1 0 4 1 1 4 4 2
- 下記の図のように、元のポスターを修復することが可能である。
入力例 2
4 4 #... .#.. ..## ..## 4 1 2 3 4
出力例 2
-1
- 与えられたピースから元のポスターがどうやっても復元できない場合は、-1を出力する。