#ijpcprimehazard. [ijpc_primehazard]合成数を倒せ (Prime Hazard)
[ijpc_primehazard]合成数を倒せ (Prime Hazard)
きつねの太郎と次郎はPrime Hazardというコンピューターゲームで遊んでいる。
Prime Hazardに登場するキャラクターには2以上の整数が書かれていて、素数が書かれたキャラクターはプレイヤーの仲間であり、合成数が書かれたキャラクターはプレイヤーの敵である。
プレイヤーはキャラクターに書かれた数字を見て、瞬時に敵か仲間かを判断し敵だけを攻撃しなくてはならない。敵は書かれている数字の最小の素因数を入力することで倒すことができる。
太郎と次郎はこのゲームをプレイする際に次のような役割分担をすることにした。
- 太郎は敵の数字を読んでその情報を次郎に伝える。
- 次郎は太郎からの情報を元に、キャラクターが敵かどうか、敵であれば最小の素因数は何かを判断する。
一度に大量のキャラクターについて処理しなくてはならないため、情報の伝達はできるだけ簡単にしたい。太郎は次郎に0か1の数字をいくつか伝えることにした。
課題
2以上の正整数Nが与えられる。Nが素数か判定せよ。合成数の場合は最小の素因数を求めよ。
次のプロシージャを実装せよ:
-
次のパラメータを持つプロシージャ taro(N):
- N -- 与えられた正整数。
このプロシージャ中で send(b) を繰り返し呼び出すことで次郎にデータを送信することが可能である。ただし b は 0 または 1 でなければならない。このプロシージャは jiro(S, X) よりも先に1度だけ呼び出され、戻り値を持たない。
-
次のパラメータを持つプロシージャ jiro(S, X):
- S -- 太郎から送られてきたデータの長さ(ビット数)。
- X -- S 個の整数からなる1次元配列。0 ≦ i ＜ S に対して X[i] は taro(N) 中で send(b) が i+1 回目に呼び出された際の b の値に等しい。
このプロシージャは taro(N) が呼び出された後に1度だけ呼び出される。このプロシージャはNが素数である場合は -1, 合成数の場合は最小の素因数を戻り値として返す必要がある。
例
例1
N = 7
の場合を考える。
taro 中で send が次のように呼び出されたとする。
send(1)
send(1)
send(0)
send(1)
このとき jiro 呼び出しにおいて S = 4 であり、
X =
1
1
0
1
となる。
この場合、7 は素数であるので、jiro は -1 を返さなければならない。
例2
N = 6
の場合を考える。
この場合、6 は合成数であり、最小の素因数は 2 であるので、 jiro は 2 を返さなければならない。
小課題
小課題 1 (50 点)
- 2 ≦ N ≦ 1 000
- 太郎が次郎に送るデータの大きさ(S)は 12 以下でなければならない。
小課題 2 (50 点)
- 2 ≦ N ≦ 1 000 000 000
- 太郎が次郎に送るデータの大きさ(S)は 12 以下でなければならない。
実装の詳細
制限
- CPU 時間制限: 1 秒
- メモリ制限: 64 MB
注意: スタックのサイズには決められた制限はない。スタックとして使用されたメモリは、メモリ総使用量に含まれる。
インターフェース (API)
- 実装フォルダ: primehazard/ (プロトタイプ: primehazard.zip)
- 競技者が実装するファイル:primehazard.cpp
注意: 提出されたファイルからは1つの実行ファイルが生成されるが、ジャッジサーバーでは2つの実行インスタンスが起動されることに注意せよ。特に、グローバル変数や静的変数を使用している場合には、taroとjiroでそれらの変数を共有できないことに注意せよ。 - 提出ファイルのインターフェース: primehazard.h
- 採点プログラムのインターフェース: grader.h
- 採点プログラムのサンプル: grader.cpp
- 採点プログラムの入力のサンプル: grader.in.1, grader.in.2, ...
**注意:**採点プログラムのサンプルは次の書式の入力を読み込む。- 1 行目: 整数 N が書かれている。N は与えられた正整数を表す。
- 採点プログラムの入力のサンプルに対して期待される出力: grader.expect.1, grader.expect.2, ...
**注意:**採点プログラムのサンプルは次の書式の出力を書き出す。- 1 行目: プロシージャ jiro が返すべき値が書かれている。
- Problem Proposal: qnighy
- Problem Statement: utatakiyoshi