問題一覧 > 通常問題

No.382 シャイな人たち (2)

レベル : / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 22
作問者 : LayCurseLayCurse
0 ProblemId : 867 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-06-18 00:59:21

問題文

競技プログラミング勢はシャイであることはすでに述べました
ところで,あるコンテストでは,一つの企画としてオンサイトまで勝ち残った競技プログラミング勢から何人か選びチームを作りリレー競技みたいなことをしようと考えています.
しかし,競技プログラミング勢はシャイなので,下手なチーム分けをしてしまうと,会話が全くなくなる可能性があります.

それを避けるために念入りに調査を行いました.
オンサイトに参加している競技プログラミング勢は $N$ 人いて,$i$ 番目の人と $j$ 番目の人との親しさを表す非負整数 $F_{ij}=F_{ji}$ を計算しました.
親しさがある閾値 $P$ 未満である場合は,その両者間で会話がない可能性があります.
また,チームの中に $1$ 組でも,親しさが $P$ 以上となる組があれば,そこから話しやすいムードが広がると考えられます.

チーム決めの際は,公平を期すためランダムに決めます.
よって,どのように $k$ 人($2 \leq k \leq N$)のチームを作ろうとも,必ず,親しさが $P$ 以上となるような競技プログラミング勢の組が存在するような最小の $k$ を求めたいです.
そのような最小の $k$ を求めるプログラムを書いてください.
(全員参加のイベントではなく,必ずしも競う必要もないので,$k$ の値によっては,$1$ チームしか作れなかったり,余りの人が出たとしても問題はありません)

この問題は,必要な情報は乱数で生成され,入力ではその乱数の種 $S$ のみが与えられます.
乱数の種 $S$ が与えられたら,以下の擬似コードによって,情報が生成されます.

    $S$ is given
    $S = (S \times 12345)\ {\rm mod}\ 1000003$
    $N = (S\ {\rm mod}\ 120) + 2$
    $S = (S \times 12345)\ {\rm mod}\ 1000003$
    $P = S$
    for($i$=1; $i$<=$N$; $i$++){
        for($j$=$i$+1; $j$<=$N$; $j$++){
            $S = (S \times 12345)\ {\rm mod}\ 1000003$
            $F_{ij} = F_{ji} = S$
        }
    }

入力

$S$

$1 \leq S < 1000003$,$S \in \mathbb{Z}$

出力

条件を満たす最小の $k$ を $1$ 行で出力してください.
そのような $k$ が存在しない場合は,代わりに $\verb|-1|$ を出力してください.
また,存在する場合は,念の為に,確認として,次の行には,$k-1$ 人からなるチームで,全ての人の間での親しさが $P$ 未満となるようなチームのメンバーの番号を半角スペース区切りで $1$ 行で出力してください.
そのようなチームは複数存在する可能性がありますが,その場合はどれか $1$ つを出力してください.

この問題はスペシャルジャッジのため,余分な空白を出力してしまうなど,少しのフォーマットの違いでもWAになる可能性があります.

サンプル

サンプル1
入力
657
出力
3
1 3

問題文の通りに乱数で情報を作ると,
 $N = 3, P = 859050$
 $F_{1,2}=F_{2,1} = 940438$
 $F_{1,3}=F_{3,1} = 672283$
 $F_{2,3}=F_{2,3} = 308738$
となり,親しさが $P$ 以上の組は,$F_{1,2}$ しかないので,$1$ 人目と $2$ 人目の両方をチームに含める必要があります.
よって,そのような最小のチーム数 $k=3$ で,$2$ 人チームの時,その $2$ 人を含まないチームとして $1,3$ 人目からなるチームや $2,3$ 人目からなるチームが考えられます.

サンプル2
入力
58
出力
5
87 86 12 44
サンプル3
入力
31884
出力
37
7 36 70 79 6 35 14 78 15 59 68 56 16 46 69 28 54 81 83 8 34 53 1 24 32 13 17 66 19 38 12 18 23 41 73 40

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。