問題一覧 > 通常問題

No.3159 Just Answer 10 Integers!

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 82
作問者 : butsurizuki / テスター : みうね kencho kmmtkm fluorine jastaway tatesoto TKTYI
ProblemId : 12233 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-05-23 19:01:29

問題文

大きさ $N$ ( $2 \le N \le 10$ ) の相異なる正整数からなる集合 $S = \{S_1,S_2,...S_N\}$ に対し、次の通りにスコアを定めます。

直感的には、 $S$ のスコアは ${\rm lcm}(S_i,S_j)$ ( $1 \le i < j \le N$ ) の取りうる値の種類数です。
厳密な定義は次の通りです。

  • $S$ のスコアを、次の条件を満たす整数 $m$ の個数とする。
    • ある整数 $i,j$ ( $1 \le i < j \le N$ ) が存在して、 $m = {\rm lcm}(S_i,S_j)$ である。
    • ただし、 ${\rm lcm}(x,y)$ は $x$ と $y$ の最小公倍数を表します。
集合 $S$ として考えられるもののうち、スコアが 最小 になるものを1つ答えてください。
ただし、出力は以下の制約を満たす必要があります。
  • $1 \le S_i \le 10^9$
  • $S_i \neq S_j$ ( $1 \le i < j \le N$ )
なお、スコアが最小となる集合 $S$ であって、上記の制約を満たすものが存在することが証明できます。

入力

$N$

$N$ は $2$ 以上 $10$ 以下の整数である。

出力

集合 $S$ を次の形式で出力せよ。 

$S_1$ $S_2$ $\dots$ $S_N$
なお、正答が複数考えられる場合、どれを出力しても正解とみなされる。

サンプル

サンプル1
入力
3
出力
2 6 3

$S = \{2,6,3\}$ について、以下が成り立ちます。

  • ${\rm lcm}(S_1,S_2) = {\rm lcm}(2,6) = 6$
  • ${\rm lcm}(S_1,S_3) = {\rm lcm}(2,3) = 6$
  • ${\rm lcm}(S_2,S_3) = {\rm lcm}(3,6) = 6$
このとき $S$ のスコアは $1$ であり、これが達成可能な最小です。
他にも、 1500 300 500 といった出力も正解とみなされます。

一方で、 $S = \{2,4,8\}$ については、以下が成り立ちます。
  • ${\rm lcm}(S_1,S_2) = {\rm lcm}(2,4) = 4$
  • ${\rm lcm}(S_1,S_3) = {\rm lcm}(2,8) = 8$
  • ${\rm lcm}(S_2,S_3) = {\rm lcm}(4,8) = 8$
このとき $S$ のスコアは $2$ であり、これは達成可能な最小ではないので、 2 4 8 という出力は不正解とみなされます。

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