Time Limit: 2 sec / Memory Limit: 64 MB
問題文
整数 A が与えられます。
整数 A が立方数ならYES、そうでないならNOと出力しなさい。
ただし、立方数とは、整数を三乗して作ることが出来る数のことを指します。
入力
入力は以下の形式で標準入力から与えられる。
A
- 1 行目には、1 つの整数 A (1 ≦ A ≦ 1000000) が与えられる。
出力
A が立方数であればYES、そうでないならNOを 1 行で出力せよ。出力の末尾には改行をいれること。
入力例1
8
出力例1
YES
8 は立方数なので、YESと出力します。
入力例2
24
出力例2
NO
24 は立方数ではないので、NOと出力します。
Source Name
Code Formula 2014 予選ATime Limit: 2 sec / Memory Limit: 64 MB
問題文
高橋君は、ボーリングゲームを作っています。 ゲーム中で、倒したピンを表示する必要があるのですが、ピンの番号を羅列しても、あまり見栄えがよくありません。
そこで、高橋君は、 1 投目に倒したピンと、2 投目に倒したピンを、グラフィカルに表示することにしました。 まず、ピンの番号を、以下のように割り当てます。 10 番目のピンは 0 で表されることに注意してください。
7 8 9 0 4 5 6 2 3 1
この番号ごとの位置に対し、以下のような表示を行います。
- そのピンが 1 投目に倒された場合は、
.と表示します。 - そのピンが 2 投目に倒された場合は、
oと表示します。 - そのピンが 2 投目までに倒されなかった場合は、
xと表示します。
例えば、 1 投目に、1, 3, 5 の 3 本のピンが、 2 投目に 7, 0 の 2 本のピンが倒された場合、以下のような表示になります。
o x x o x . x x . .
1 投目、 2 投目に倒されたピンの情報が与えられるので、以上のような出力をしてください。
入力
入力は以下の形式で標準入力から与えられる。
a b p_1 p_2 ... p_a q_1 q_2 ... q_b
- 1 行目には、1 投目に倒した本数を表す整数 a (0 ≦ a ≦ 10) と、2 投目に倒した本数を表す整数 b (0 ≦ b ≦ 10) が、スペース区切りで与えられる。
- 2 行目には、1 投目に倒したピンの番号を表す a 個の整数が、スペース区切りで与えられる。このうち i (1 ≦ i ≦ a) 番目の整数 p_i は、i 番目に倒れたピンを表す。なお、i ≠ jのとき、p_i ≠ p_jであることが保障されている。
- 3 行目には、2 投目に倒したピンの番号を表す b 個の整数が、スペース区切りで与えられる。このうち i (1 ≦ i ≦ b) 番目の整数 q_i は、i 番目に倒れたピンを表す。なお、i ≠ jのとき、q_i ≠ q_jであることが保障されている。
- 任意の i, j に対し、 p_i ≠ q_j であることが保障されている。
出力
倒したピンの情報を、題意に沿って出力しなさい。
出力の末尾にも改行をいれること。
なお、各行の最後の.、o、xの後に、いくつかのスペースを出力しても良い。
入力例1
3 2 1 3 5 7 0
出力例1
o x x o x . x x . .
問題文で説明した入力です。
入力例2
10 0 7 3 4 5 1 2 6 0 9 8
出力例2
. . . . . . . . . .
ストライクの場合は、2 行の後に空行が続きます。
なお、閲覧環境によっては、空行に半角スペースが混ざっていることがありますが、実際の入力では、空行に半角スペースは含まれません。
入力例3
0 10 7 3 4 5 1 2 6 0 9 8
出力例３
o o o o o o o o o o
入力に空行が生じる場合もあることに注意してください。
なお、閲覧環境によっては、空行に半角スペースが混ざっていることがありますが、実際の入力では、空行に半角スペースは含まれません。
Source Name
Code Formula 2014 予選ATime Limit: 2 sec / Memory Limit: 64 MB
問題文
高橋君は、コンテストを開こうと思っています。
コンテストは、 n 回の予選と、 1 回の本選に分かれており、予選の上位 k 人を本選に招待しようと思っています。
本選の出場選手は、以下のように選ばれます。
- 各予選の最高順位が高い人から順番に選ばれる。
- 最高順位が同じ場合は、最高順位を取った予選が開かれた時期が早い方から先に選ばれる。
- k 人が選ばれるまで、この操作を続ける。
高橋君は、招待される選手に出来るだけ早く、本選への招待をしたいです。そこで、予選が終わるたびに、本選への招待が確定した選手に対し、メールを送りたいです。
各予選の結果が与えられるので、予選が終わった際に、誰にメールを送るべきかを求めてください。 なお、本選を辞退する選手はいないものとします。
入力
入力は以下の形式で標準入力から与えられる。
n k
a_{1,1} a_{1,2} ... a_{1,k}
a_{2,1} a_{2,2} ... a_{2,k}
:
a_{n,1} a_{n,2} ... a_{n,k}
- 1 行目には、予選の回数を表す整数 n (1 ≦ n ≦ 50) と、本選への招待人数を表す整数 k (1 ≦ k ≦ 1000) が、スペース区切りで与えられる。
- 2 行目から n 行は、各予選での上位 k 人の選手のIDが与えられる。このうち i (1 ≦ i ≦ n) 行目は、i 回目の予選の結果を表す。結果はスペース区切りの k 個の整数で与えられ、このうち j 個目の整数 a_{i,j} (1 ≦ a_{i,j} ≦ 999999)は、i 回目の予選で j 位だった人のIDを表す。なお、p ≠ qのとき、a_{i,p} ≠ a_{i,q}であることが保障されている。
出力
i (1 ≦ i ≦ n) 回目の予選で、予選通過が確定した人のIDの一覧を、i 行目にスペース区切りで出力せよ。予選通過者が複数人いる場合は、IDが小さい順に出力しなさい。 出力の末尾にも改行をいれること。
入力例1
2 11 1 2 3 4 5 6 7 8 9 10 11 1 2 15 14 13 16 17 18 19 20 21
出力例1
1 2 3 4 5 6 7 13 14 15 16
予選が 2 回あります。
まず、1 回目の予選が行われた直後に、上位 6 人は、その後の予選の結果に拠らず、本選への招待が確定します。
次に、2 回目の予選が行われた際、IDが、1,2 の二人の参加者が重複するため、1 回目の予選の 7 位までと、 2 回目の予選の 6 位までの、本選への招待が確定します。
出力順序は、順位に関係なく、IDが若い順であることに注意してください。
入力例2
4 5 1 2 3 4 5 2 1 3 4 5 1 2 3 4 5 2 1 3 4 5
出力例2
1 2 3 4 5
本選への招待者が確定しない予選があることにも注意してください。
Source Name
Code Formula 2014 予選ATime Limit: 2 sec / Memory Limit: 64 MB
問題文
高橋君は、無刻印キーボードが大好きです。 今日も、アルファベットと数字のみがキートップに書かれていないキーボードで、文章を書こうとしています。
しかし、高橋君は、キーボードのレイアウトを完全に覚えていません。 キーを覚えている文字は、その文字に対応するキーをそのまま叩けば良いですが、覚えていない分は、適当に選んで叩き、間違っていた場合は、バックスペースキーで削除しなくてはなりません。
高橋君は、文章 S を入力しようとしています。この文章を入力するために、キーを叩く回数の期待値を出来るだけ減らしたいです。高橋君は、どのキーを打った時にどの文字が出てきたかを記憶することが可能で、その情報を元に、次にどのキーを叩くか選択することが可能です。
高橋君が、上記目的を達成するために最適な戦略を取った時、キーを叩く回数の期待値を答えなさい。
なお、バックスペースキーの位置や、アルファベットや数字以外のキーは、全て覚えているものとします。
また、矢印キーやマウス操作などの、入力位置を変えるような操作は出来ないものとします。
入力
入力は以下の形式で標準入力から与えられる。
S K
- 1 行目には、入力したい文字列 S (1 ≦ |S| ≦ 50) が、1 行で与えられる。文字列 S は、小文字アルファベットまたは数字のみで構成されていることが保障されてます。
- 2 行目には、高橋君が覚えているキーの種類を表す文字列 K が、1 行で与えられる。文字列 K は、
1234567890abcdefghijklmnopqrstuvwxyzから、1 つの文字を選んで削除する操作を任意の回数行うことで作成可能な文字列であり、先頭文字が1であることが保障されている。
出力
高橋君がキーを叩く必要のある回数の期待値を 1 行で出力せよ。出力の末尾は改行をいれること。
出力は絶対誤差または相対誤差が 10^{-6} 以下であれば許容される。
入力例1
takahashikun 1234567890abcdefghijklmnopqrstuvwxyz
出力例1
12
高橋君は、全てのキーを記憶しています。
よって、キーを叩かなければいけない回数は、takahashikun の文字数と同じ 12 回です。
入力例2
p 1234567890abcdefghijklmnorstuvwxyz
出力例2
2
高橋君は、pおよびqの 2 つのキーの位置がわからなくなってしまっています。
pと打つためには、このわからない 2 つのキーのうち、どちらか 1 つを押す必要があります。
pを押したとき、文章が完成するので、高橋君が押すキーの数の合計は 1 です。qを押したとき、もう 1 つのキーがpであることが解ります。よって、バックスペースキーで 1 文字を消し、もう一度pキーを押すことで、文章が完成します。この時、高橋君がキーを押した回数は 3 回になります。
以上が等確率で選ばれるので、キーを押す回数の期待値は 2 です。