いろはちゃんコンテスト Day3

A - 宇宙人

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 100 点

問題文

ある日、地球の住人であるいろはちゃんは、ダガバジという 1 人の宇宙人に出会いました。

ダガバジやいろはちゃんに関して、以下の情報が与えられています。

〜〜〜〜〜〜〜〜〜〜

ダガバジは、 A 年前に地球にやってきました。

ダガバジは、 B 年前に初めて、地球上で住む家を見つけました。今もダガバジはその家に住んでいます。

ダガバジの家は、いろはちゃんと出会った地点から C\ \mathrm{\small (m)}離れたところにあります。

いろはちゃんの家は、ダガバジの家から D\ \mathrm{\small (m)}離れたところにあります。

今、ダガバジには、腕が E 本と、脚が F 本あります。

ダガバジは、腕を何本でも新しく生やすことができます。しかし、脚の本数は変えることができません。

ダガバジはたこ焼きが大好きで、 3 日前はたこ焼きを G 個、おとといは H 個、昨日は I 個食べました。

今日、ダガバジは、昨日までの 3 日間における、 1 日で食べたたこ焼きの平均の個数よりも多くたこ焼きを食べたいと思っています。

ダガバジには「お気に入りの文字列」というものがあります。

それは、dagabajiという英小文字からなる文字列の、長さ J の(連続とは限らない)部分列のうち、辞書順で最小であるものです。

さらに、ダガバジには「お気に入りの正の整数」というものもあり、しかもそれは 2 つあります。

1 つ目は、 59 で割った余りが K 、 61 で割った余りが L である正の整数のうち、 M 番目に小さいものです。

2 つ目は、 1 つ目の「お気に入りの正の整数」との差の絶対値が N 以上である完全数のうち、最も小さいものです。

また、ダガバジはいろはちゃんに次のお願いをしてきました。

お願い: (O+P+Q)(R+S+T)(U+V+W)(X+Y+Z)を9973 で割った余りを求めてほしい。

しかし、いろはちゃんはこの計算を即座にできませんでした。

〜〜〜〜〜〜〜〜〜〜

それでは、以下の 8 つの文章の空欄に当てはまる整数、または文字列を答えなさい。

ダガバジが地球にやってきてから、地球上で住む家を見つけるまでの期間は[ 1 ]年間でした。
いろはちゃんがダガバジと出会った地点からいろはちゃんの家までの距離として、考えられる最大値は[ 2 ]\ \mathrm{\small (m)}です。
ダガバジの腕の本数が脚の本数よりも多い状態となるために、ダガバジが新しく生やす必要のある腕の本数は[ 3 ]本です。
今日、ダガバジは最低でも[ 4 ]個のたこ焼きを食べようと思っています。
ダガバジの「お気に入りの文字列」は[ 5 ]です。
ダガバジの「お気に入りの正の整数」のうち、小さい方は[ 6 ]です。
ダガバジの「お気に入りの正の整数」のうち、大きい方は[ 7 ]です。
ダガバジがいろはちゃんにお願いしてきた計算の、正しい答えは[ 8 ]です。

制約

入力は全て、 1 以上 1000 以下の整数である。
B < A
J \leq 8
K < 59
L < 61

入力

入力は以下の形式で標準入力から与えられる。

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

出力

8 行出力せよ。 i 行目 (1 \leq i \leq 8) では、上の文章の[ i ]に当てはまる整数、または文字列を出力せよ。

入力例1

25 10 800 250 6 4 15 7 5 5 17 31 334 777 616 88 919 331 270 27 555 555 555 1000 100 10

出力例1

解説

B - ゐろはちゃん

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 100 点

これはインタラクティブな問題です。

問題文

ゐろはちゃんはいろはちゃんの偽者です。いろはちゃんは常に本当のことを言い、ゐろはちゃんはほぼ常に嘘をつきます。

また、二人はある立方体を共有しています。その立方体の各頂点には 0 から 7 までの整数が 1 つずつ割り当てられており、異なる頂点には異なる数が割り当てられています。

あなたはこの二人を見分けるために、二人に何回か質問をすることにしました。

あなたは以下の質問を、二人に同時にすることができます。

質問: 0 以上 7 以下の相異なる 3 個の整数の組 (X, Y, Z) に対し、それらの数が割り当てられている 3 つの頂点を通る平面で立方体を切ったときの切り口の形を聞く。

二人の回答は、Square、Rectangle、Triangleのいずれかです。いろはちゃんは、指定された平面が立方体の 1 つの面と一致する、つまり切り口の形が正方形といえるときはSquare、切り口の形が正方形でない長方形のときはRectangle、正三角形のときはTriangleと回答します。ゐろはちゃんは、最初の質問に対してだけは必ずいろはちゃんと同じ回答を言いますが、 2 回目以降の質問に対しては、必ずいろはちゃんの回答とは異なる回答を言います。例えば、いろはちゃんが、 2 回目以降のある質問に対してRectangleと回答するとき、ゐろはちゃんはSquareとTriangleのうちのどちらか一方を回答します。

あなたは二人に最大 11 回質問することができます。ただし、同じ整数の組み合わせを複数回質問することはできません。例えば、整数の組 (1, 3, 6) について質問をした後、 (1, 3, 6) や (3, 1, 6) 、 (6, 1, 3) などについて質問をすることはできません。

回答者 1 と回答者 2 のどちらがいろはちゃんか判定してください。

入出力

この問題はインタラクティブ形式です。大事なことなので 2 度言いました。

この問題においては、最初に入力は与えられない。最初からクエリを送ることを繰り返す。

質問のクエリは次の形式で標準出力へ出力せよ。行末には改行を出力せよ。

?\ X\ Y\ Z

( X, Y, Z は 0 以上 7 以下の相異なる整数)

これに対するクエリの答えは、次の形式で標準入力から与えられる。

S\ \ T

S は回答者 1 の回答、 T は回答者 2 の回答で、どちらもSquare、Rectangle、Triangleのいずれかである。

解は次の形式で標準出力へ出力せよ。行末には改行を出力せよ。

!\ \ t

回答者 1 がいろはちゃんであるならば t=1、回答者 2 がいろはちゃんであるならば t=2 とせよ。

実装上の注意

出力のあと、標準出力を flush しなければならない。そうでないときはTLEの可能性がある。
答えを出力した後、プログラムをすぐに終了しなければならない。そうでないときの挙動は定義されていない。
質問回数が 11 回を超えた場合、および同じ数の組み合わせについての質問を複数回行った場合、WAとなる。
クエリの形式が正しくない場合の挙動は定義されていない。

解説

C - Not Say "NO"

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 100 点

問題文

まず、以下の問題を読んでください。

1,2,\dots,N の番号のついた N 人の子供がいて、互いに価値の異なるプレゼントが K 個ある。 i 個目のプレゼントの価値は V_i である。全てのプレゼントを子供たちに分けるとき、全ての子供が最終的に合計で同じ価値のプレゼントを得るようにできるだろうか? 可能ならYESと出力し、分け方の一例を示してください。不可能ならNOと出力してください。

制約

1 \le N \le 100

2\times N-1 \le K \le 10^4

1 \le V_i \le 10^{14}(1 \le i \le K)

V_i \neq V_j(1 \le i < j \le K)

N,K が与えられるので、この問題のテストケースを解の一例とともに生成してください。ただし、解がNOとなるケースを生成してはいけません。なお、この問題においてこの制約のもとでどんな入力でも解が存在することが示せます。

入力

入力は以下の形式で標準入力から与えられる。

N\ K

出力

以下の形式で出力せよ。

V_1\ V_2\ \cdots\ V_K
S
R_1\ R_2\ \cdots\ R_K

まず、 1 行目に生成したテストケース V_i を出力してください。

次に、テストケースの解である S を出力してください。 S はYESかNOである必要がありますが、解がNOとなるケースを生成してはいけません。

最後に、 S がYESの場合、分け方の一例を示してください。 R_i=X(1\le X \le N) の場合、 i 番目のプレゼントが R_i 番の子供に渡されたことを表します。

入力例 1

3 6

出力例 1

3 5 2 6 4 1
YES
3 2 2 1 3 1

入力例 2

2 5

出力例 2

100 10 20 30 40
YES
2 1 1 1 1

解説

Not Say "NO" - 解説

D - おにごっこ

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 100 点

これはインタラクティブな問題です。

問題文

あなたといろはちゃんは、これから N\times N ( N は奇数)のグリッド上でおにごっこをします。グリッドは上から 1,2,\dots,N 行、左から 1,2,\dots,N 列で、いろはちゃんが鬼です。

グリッドは空き地を意味する.または障害物を意味する#からなり、障害物のマスには 2 人とも立ち入ることはできません。

グリッドの最外辺と、上から奇数行目かつ左から奇数マス目は#であること、上から偶数行目かつ左から偶数マス目は.であることが保証されます。また、このグリッドでは治安維持のため、.には必ず 2 つ以上の.が隣接しています。(すなわち、行き止まりはありません。)

鬼ごっこは 1000 ターンからなり、あなたは (2,2) から、いろはちゃんは (N-1,N-1) からスタートします。 1 ターン毎に 2 人は今いるグリッドと辺で隣接する空き地のグリッドに移動するか、今いるグリッドにとどまるかの行動を同時に起こします。二人が同時に同じマスにいる場合、あなたはいろはちゃんに捕まって敗北してしまいます。

あなたは、いろはちゃんと同じ行または列にいて、 2 人の間に障害物がない場合のみにいろはちゃんの位置を観測できます。しかし、いろはちゃんは天才忍者なので常にあなたの位置情報を把握しているかもしれません。厳密には、あるアルゴリズムのもとで動作しています。

いろはちゃんから 1000 ターン逃げ切ってください。

制約

N は奇数である
5 \leq N \leq 9
|S_i| = N(1 \le i \le N)

入出力

ゲームの最初に以下の形式でグリッドの情報が与えられる。

N
S_1
S_2
\vdots
S_N

まず、各ターンの開始時にあなたは

U(上に 1 マス移動)
D(下に 1 マス移動)
L(左に 1 マス移動)
R(右に 1 マス移動)
-(動かない)

のどれかの行動を出力してください。出力後に必ず改行する必要があります。 この動作においてあなたが#マスに入った場合WAとなります。次に、ジャッジはいろはちゃんの行動を行い、その結果を出力します。ここで、いろはちゃんはあなたの行動を受けて行動しうることに留意してください。

ジャッジからのフィードバックは以下の種類に分けられます。

x\ y\ (xとyは正の整数)

この場合、あなたからいろはちゃんが見えて、いろはちゃんが x 行 y 列にいることを表します。(5/2 13:44追記)

-1 -1

この場合、あなたからいろはちゃんが見えないことを表します。

-2 -2

この場合、あなたがいろはちゃんに捕まった、もしくは出力に不備があったことを表します。この返答を受け取った場合、あなたは直ちにプログラムを終了してください。

-3 -3

この場合、あなたが 1000 ターン逃げ切ったことを表します。この返答はちょうど 1000 ターン目にのみ得られます。この返答を受け取った場合も、あなたは直ちにプログラムを終了してください。

実装上の注意

この問題は インタラクティブ形式 である。
出力のあと、標準出力を flush しなければならない。行わなかった場合TLEの可能性がある。
-2ないし-3を受け取った後、プログラムをすぐに終了しなければならない。そうでないときの挙動は定義されていない。

入力例

グリッドの例

7
#######
#.....#
#.#.#.#
#.....#
#.#.#.#
#.....#
#######

9
#########
#.......#
#.#.###.#
#.....#.#
#.###.#.#
#...#...#
#.#.###.#
#.......#
#########

解説

おにごっこ - 解説

E - 「く」

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 100 点

問題文

いろはちゃんは縦一列に「く」といくつか紙に書きました。
しかし、いろはちゃんはあまりに達筆すぎるので、「く」が全て繋がって一本の線になってしまいました。
後で読むときに不便なので、いろはちゃんがいくつ「く」を書いたか数えてあげましょう。

制約

C_i は/か\
1 \leq N \leq 10^5

入力

入力は以下の形式で与えられる。

N
C_1
C_2
\vdots
C_N

整数 N と、その後 N 行に渡って/か\のどちらかの文字 C_i(1 \leq i \leq N) が与えられます。
C_1 から順番に、文字が/だった場合はいろはちゃんが書いた線が左下に長さ 1 だけのびていて、\だった場合は右下に長さ 1 だけのびていることを表します。右下に伸びている線分の長さと、直前に左下に伸びていた線分の長さが等しい場合、この二つの線分を合わせて「く」とします。 (5/2 13:54 表現の修正)

出力

いろはちゃんが書いた線の中にある「く」の数を出力してください。

入力例 1

5
/
\
/
/
\

出力例 1

入力例 2

6
/
\
/
/
\
\

出力例 2

入力例 3

13
\
/
/
\
\
/
\
/
\
\
\
/
\

出力例 3

解説

F - 闇のカードゲーム

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 100 点

問題文

テーブルの上に、 N 枚のカードが横一列に並べられています(ただし、 N は奇数)。それぞれのカードには正の整数が 1 つずつ書かれており、左から i 番目 (1 \leq i \leq N) のカードに書かれている整数は a_i です。異なるカードに同じ整数が書かれていることはありません。また、カードは、書かれている整数の小さい順に左から並べられています。

すぬけ君といろはちゃんは、テーブルに置かれているカードが 2 枚になるまで、すぬけ君を先手として次の操作を交互に行います。

操作: その時点でテーブルに置かれているカードの中からカードを 1 枚選んで手に取り、その存在を完全に消去する。

操作が全て終了したとき、まだ存在している 2 枚のカードに書かれている整数の差の絶対値を、このゲームのスコアとします。

このゲームには先手・後手ともに追加規則が存在します。

先手のすぬけ君は、常に、手番が回ってきた時点で真ん中に置かれているカードを選ばなければなりません。つまり、その時点で残っているカードの枚数を r 枚として、左から (r+1)/2 番目のカードの存在を抹消しなければなりません。
後手のいろはちゃんは、手番が回ってきた時点で残っているカードのうち、最も左にあるものか、最も右にあるものを選ばなければなりません。

いろはちゃんが、このゲームのスコアを最小化するように最適に行動するとき、このゲームのスコアがいくつになるかを求めなさい。

制約

N は奇数、a_i \ (1 \leq i \leq N) は整数
3 \leq N \leq 10^{5}
1 \leq a_i \leq 10^{9} \ (1 \leq i \leq N)
a_i < a_j \ (1 \leq i < j \leq N)

入力

入力は以下の形式で標準入力から与えられる。

N
a_1\ a_2\ \cdots\ a_N

出力

ゲームのスコアを1行で出力せよ。

入力例1

3
1 5 100

出力例1

すぬけ君が、左から 2 番目のカードを消して、ゲームが終了します。

入力例2

9
3 14 15 20 33 51 59 62 68

出力例2

解説

3ページ目の本文2行目の「最大値」は「最小値」の誤りです。申し訳ございません。

(5/13 21:40 追記)

G - ますまてぃくす・おりんぴっく！

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : \(100\) 点

問題文

いろはちゃんは競技数学に興味を持ったので、手元にあった問題を試しに解いてみることにしました。以下に 6 問の問題セットがあるので、それぞれの問題番号に対応した正解を返すプログラムを作ってください。

Q0

1+4=[0]

Q1

\bf P を素数全体の集合とする。「 k 未満の任意の正整数 a に関して、 a \in {\bf P} \Leftrightarrow (k-a) \in {\bf P} 」を満たす最大の正の整数 k は[1]である。

Q2

10^4 未満の非負整数の組 (a, b, c) であって、次の条件を満たすものの個数は[2]である。

条件:

三次関数 f(x), g(x) をそれぞれ f(x)=x^3+2019, g(x)=x^3+ax^2+bx+c と定めるとき、 f(x)=g(x) を満たす実数 x の値の個数が高々 2 個である。

Q3

ある実数 x を用いて y=floor(x)^2+ceil(x)^2 として表せる整数 y は 1 以上 5000 兆 (=5\times10^{15}) 以下の範囲に[3]個ある。ただし、 floor(x) は x 以下の最大の整数、 ceil(x) は x 以上の最小の整数と定義される。

Q4

平行四辺形 \rm ABCD があり、 {\rm AB}=4 である。辺 \rm BC 上に {\rm BP}=1 なる点 \rm P をとったところ、 \rm AP\perp BC かつ \rm \angle ADP=\angle CDP を満たした。辺 \rm BC 上に点 \rm Q を、 \rm AQ\perp DP となるようにとるとき、 \rm CQ= [4]
ただし、 \rm XY で線分 \rm XY の長さを表すものとする。

Q5

\displaystyle\sum_{i=0}^{2\times10^6}\sum_{j=0}^{2\times10^6}\binom{i+j}{i} を 10^9+7 で割った余りは[5]である（ \binom{n}{m} は二項係数）。

制約

n は 0 以上 5 以下の整数

部分点

Q0に正解した場合、 0 点を得られる。
Q1に正解した場合、 10 点を得られる。
Q2に正解した場合、 20 点を得られる。
Q3に正解した場合、 15 点を得られる。
Q4に正解した場合、 25 点を得られる。
Q5に正解した場合、 30 点を得られる。

入力

入力は以下の形式で標準入力から与えられる.

出力

入力された n に対して、上記の[n]に当てはまる整数を 1 行で出力せよ。出力の最後に改行を忘れないこと。

入力例1

出力例1

解説

H - 〔経験値〕

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 100 点

問題文

ある英小文字 C について、英小文字からなる空でない文字列 S の C -経験値を、次のように定義します。

C 以外のある文字が S に重複して現れる場合、 0
そうでない場合、 S に C が現れる回数を N 回として、 (|S|-N) \cdot 2^{N}

例えば、irohachanの a -経験値は 0 、chokudaiの z -経験値は 8 、experienceの e -経験値は 96 です。

いろはちゃんは、あなたに Q 個の質問をしてきました。 i \ (1 \leq i \leq Q) 番目の質問は以下の通りです。

質問: C_i -経験値がちょうど E_i である、英小文字からなる空でない文字列は存在するか？存在するのであれば、そのうち辞書順で最小のものは何か？

これら Q 個の質問に順に答えてください。

制約

Q, E_i \ (1 \leq i \leq Q) は整数
C_i \ (1 \leq i \leq Q) は英小文字
1 \leq Q \leq 10^{5}
0 \leq E_i \leq 10^{18} \ (1 \leq i \leq Q)

入力

入力は以下の形式で与えられる。

Q
C_1 \ E_1
C_2 \ E_2
\vdots
C_Q \ E_Q

出力

Q 行出力せよ。 i \ (1 \leq i \leq Q) 行目には、 i 番目の質問の答えを、以下に従って出力せよ。

C_i -経験値が E_i である、英小文字からなる空でない文字列が存在しない場合は-1を、存在する場合は、そのような文字列のうち辞書順で最小のものを出力せよ。

この問題において、条件を満たす文字列が存在する場合、その中で辞書順最小のものは一意に定まることが保証される。

入力例1

出力例1

aaaabcd
-1
abcdefghijklmnop
a
-1
abcdeeefghijkl
abcdefghijklmnopqrrrrrstuvwxyz

解説

I - Prime or Not

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 2\times\max_{9\times10^{15}\leq x \leq 10^{16}-2018}\#(\{p \in {\bf P}\ |\ x \leq p < x+2019\}) 点

問題文

9\times10^{15} から 10^{16} までの正整数のうち連続する 2019 個を、素数がなるべく多く含まれるように選んでください。

入力

この問題では入力は与えられない。

出力

以下の形式で 1 行に出力してください。

A B

選んだ 2019 個のうち最小の整数 A と最大の整数 B を、この順に 1 行に空白区切りで出力してください。

制約

出力は以下の条件をすべて満たさなければならない。

9\times10^{15} \le A,\ B \le 10^{16}
B-A = 2018

採点方法

閉区間 [A,\ B] に素数が 1 つ含まれるごとに 2 点が与えられる。

解説

Prime or Not - 解説

J - Go to Heaven

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 100 点

問題文

この問題はあなたが普段いかに徳を積んできたかを確かめる問題です。

1 行にJudgementとだけ出力し、最後に改行してください。すると、 1/2 の確率でACが得られます。(この抽選は提出ごとに独立に行われます。)

なお、この問題でリジャッジが行われないことが保証されます。

入力

この問題では入力は与えられない。

出力

指示通り出力して下さい。偉大なる神はあなたの行いを全てご覧になり、その結果を業という形であなたに授けることに注意してください。

解説

K - えそらんぐ

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 100 点

問題文

世の中にはC/C++、Java、Pythonといった、便利で書きやすいプログラミング言語がたくさんあります。これらの言語の登場により、わかりにくいアセンブリと比べてコンピュータのハードルがぐっと下がりました。

これらとは対照的な存在が、BrainfuckやLazy K、Pietといった、いわゆる「難解プログラミング言語(Esolang)」です。これらの言語の特徴は、名前通り「非常に難解」ということです。例えば、例に上げたBrainfuckで

Hello, World!

を出力するプログラムは、以下のようになります（一例）。

+++++++++[>++++++++<-]>.<+++++++++[>+++<-]>++.+++++++..+++.<+++++++++[>-------<-]>----.<+++++++++[>-<-]>---.<+++++++++[>++++++<-]>+.<+++++++++[>++<-]>++++++.+++.------.--------.<+++++++++[>-------<-]>----.

このように、何を書いてあるかさっぱり分かりません。

Brainfuckのプログラムは 8 種類の記号のみで構成され、単一のメモリ（配列）にデータを出し入れすることで処理を進めます。メモリの参照先は「ポインタ」という変数で保持されます。 8 種類の記号それぞれの意味する処理は以下のとおりです。

>：ポインタを 1 増やす
<：ポインタを 1 減らす
+：ポインタが指すメモリの値を 1 増やす
-：ポインタが指すメモリの値を 1 減らす
.：ポインタが指すメモリの値に対応するASCII文字を出力する
,：入力から 1 文字読み込み、ポインタが指す先にASCIIコードを代入する
[：ポインタが指すメモリの値が 0 のとき、対応する]の直後へジャンプする
]：ポインタの指すメモリの値が 0 でないとき、対応する[の直後へジャンプする

文字の意味が分かると、さっきのプログラムもなんとなくわかった気になりませんか？私はなりません。

このBrainfuckを使って、 3 桁の正整数 A,\ B の和を求めるプログラムを書いてください。

ジャッジで使用されるBrainfuckインタプリタの仕様

メモリの要素数は 1024 で、ポインタは 0 以上 1024 未満の整数値を取る。
メモリの各要素は -128 以上 128 未満の整数値を取る。
はじめ、メモリの各要素の値やポインタは 0 である。
ポインタやメモリの値が下限のときに 1 減らすと、上限の値に置き換えられる。上限を超えた場合も同様である。
対応する移動先の]や[が見つからなかった場合、エラーを出力して終了する。
,の処理を行ったときに入力文字が存在しなかった場合、エラーを出力して終了する。
8 種類の各処理を行った合計回数が 2^{20} 回を超えた場合、エラーを出力して終了する。

解答に必要な文字のASCIIコード一覧

'0' … 48
'1' … 49
'2' … 50
'3' … 51
'4' … 52
'5' … 53
'6' … 54
'7' … 55
'8' … 56
'9' … 57

制約

A,\ B は 1000 未満の正整数
A,\ B はテストケースごとにランダムに生成される

入力

この問題では直接入力は与えられないが、出力されたBrainfuckのプログラムに以下の形式で A,\ B が与えられる。

A\ B

これらが 3 桁に満たない場合は先頭に0が追加される。例えば、48は048、7は007と入力される。また、 A と B の間のスペースは半角 1 文字である。

出力

A と B の和を出力するBrainfuckソースコードを 1 行で出力せよ。末尾以外に改行や空白を含めてはならない。また、Brainfuckのプログラムが出力する内容は、先頭に 0 があってもよいが、ひとつながりで合計 4 文字以内でなければならない。

解説

L - デクレッシェンド

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: \(100\) 点

問題文

次の条件を満たす非負整数列 \(A_1, A_2, \cdots, A_{1000}\) を構築してください。

\(A_i\) は \(i\) の倍数
\(10^{500} > A_1 > A_2 > \cdots > A_{1000}\)

解の「良さ」を \(\sum_{i=1}^{1000} (\sum_{j=1}^{1000} (A_i - A_j))^2\) の値とし、得点は \(\lfloor 100 \times (\frac{想定解の良さ}{提出された解の良さ})^{100} \rfloor\) で与えられます。なお、得点が 0 となる提出は WA と判定されます。(2019/05/02 13:21 追記)

入力

この問題では入力は与えられません。

出力

\(1000\) 行出力してください。\(i\) 行目には \(A_i\) を出力してください。