F - おいらの素数生成式 Editorial /

Time Limit: 1 sec / Memory Limit: 256 MB

問題文

素数列に関する研究は,古来より多くの人々が取り組み,挫折してきたことで有名だ. おいらもその一人だ. おいらは今窮地に立たされている.

先日,素数だけを含む数列の一般項(生成式)を発見したという大口をたたいたものの,冷静に考えてみると全然そんなことはなく,気づいた時には後の祭り,公の場で発表することになってしまっていた!

正直,「穴があったら入りたい」という気持ちでいっぱいなんだけど,どうにか耐え凌がなければ未来はなさそうだ. そこでおいらは次のような作戦を考えた!

  1. 素数列は商業的にも非常に価値があるので,ただちにその生成式を公開することはできない.
  2. その数列の第 1 項目から第 100 項目までを公開する.
  3. すかさず,素数に関する奇妙な歌を歌って話を逸らし,質問はさせない.

うん!これなら世間様を納得させることができて,おいらの地位もますます向上するに違いない.


課題

f(1),\, f(2),\, …,\, f(100) の 100 個の値ができるだけ多くの異なる素数になるような一変数関数 f(n) を求めよ.

ただし,f の計算は 32 ビット符号付き整数型演算を行うことができるコンピューターが行うことから,f は以下の制約を満たさなければならない.

  • 式は 変数 n, 定数, 加減乗除(+, -, *, /), 剰余(%),単項の + および - のみの要素からなる.
  • 定数は 32 ビット符号付き整数に収まっている必要があり,n = 1,\, 2,\, …,\, 100 に対して f(n) の計算中に出てくるすべての値も32 ビット符号付き整数に収まっている必要がある.
    注意: -5 は定数ではなく,単項演算子 - に定数 5 を適用した形として解釈される.したがって定数はすべて非負であり,その値はすべて 2147483647 以下でなければならない.すなわち,-2147483648 は不正な式である.
  • 式の評価順序は左結合で単項演算子が最も優先され,乗除と剰余がその次,加減が最後で,括弧があればそれが優先される.
  • 割り算は整数除算で行われる.整数除算で得られる値は,代数的な商から小数部を切り捨てた値とする(たとえば, -7/3 = -2 である).
  • 剰余については (x / y) * y + x % y の値が x の値と等しくなるように x % y の値を定める(たとえば -7%3 = -1 である).
  • ゼロ除算が生じてはならない.
  • 出力すべき数式は以下のBNF表記の <expr> シンボルから導出されるものでなければならず,余計なスペース等を含んではならない.
<expr> ::= <term> "+" <expr>
         | <term> "-" <expr>

<term> ::= <fact> "*" <term>
         | <fact> "/" <term>
         | <fact> "%" <term>

<fact> ::= "+" <fact>
         | "-" <fact>
         | "(" <expr> ")"
         | <number>
         | "n"

<number> ::= <digit>
           | <digit> <number>

<digit> ::= "0" | "1" | "2" | "3" | "4"
          | "5" | "6" | "7" | "8" | "9"

入力

この問題には入力はない.

出力

課題の制約を満たす f(n) の式を一行に出力せよ.


採点基準

出力された f に対し f(1),\, f(2),\, …,\, f(100) を計算し,含まれる相異なる素数の個数(これを P とする)と,その数式の長さ(これを L とする)によって得点が与えられる.ただし数式の長さとは出力文字列の文字数とする.

出力された f が課題の制約を満たしていないか,L > 2000 のときは得点は 0 点である.そうでない場合,以下に示した条件それぞれを満たすたびに対応した得点を与える.

  • P \geq 87 (4点)
  • P = 100 かつ L \leq 600 (5点)
  • P = 100 かつ L \leq 300 (5点)
  • P = 100 かつ L \leq 250 (6点)
  • P = 100 かつ L \leq A (15点)
  • P = 100 かつ L \leq B (15点)
  • P = 100 かつ L \leq C (20点)
  • P = 100 かつ L \leq D (230点)
  • P = 100 かつ L \leq X (1点と賛辞)
  • P = 100 かつ L < X (1点と名誉)
    ただし X は JAPLJ と kyuridenamida が用意した解のうち最も短いものの長さ,A,\, B,\, C,\, D は秘密の定数で,次の式を満たす.
    • X < D < C < B < A < 250
    • 250 - A \geq A - B = B - C > C - D > D - X

注意: この問題では「出力された f が課題の制約を満たしており,かつ L \leq 2000 の場合」を「Accepted」として扱います.従って,提出した結果がACであっても満点でない可能性があります.すなわち,特に次のような結果が返ってきた場合は以下のようなことがわかります:

  • 提出した結果がWAのとき,出力された式 f が課題の制約に反するか,L > 2000
  • 提出した結果がACで,点数が 0 点のとき, f は課題の制約を満たし,かつ L \leq 2000 であるが P < 87

出力例1

57

グロタンディーク素数は素数ではない.そもそもこの式を n = 1, 2, …, 100 で評価しても 57 しか出てこないので無慈悲な 0 点である.


出力例2

2*n+1

3 は素数,5 は素数,7 も素数,…….よって奇数はすべて素数である.

そんなわけがなくてこの式は素数を 45 個しか生成しないので同じく無慈悲な 0 点である.


出力例3

-(n%2)

これもうわかんねえな


出力例4

123-45-67+89

ここで小町算をするのはやめろ


writer: kyuridenamida
statement: kyuridenamida