E - Product Simulation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1800 点

問題文

これは output-only 問題です。入力は与えられません。

簡潔に述べると、整数の掛け算を、比較 (x < y) と加算 (x + y) のみを用いてシミュレートする問題です。 入力はありません。操作列の出力のみを行ってください。

長さ N の長大な配列 a[0], a[1], ..., a[N-1] があるとします。 先頭の二要素の初期値は非負整数 A, B であり (あなたには知らされません)、残りの要素の初期値は 0 です。 あなたの目的は、最終的に a[2] を積 A \cdot B とすることです。

あなたが行えるのは、以下の形式の二種類の操作です (ここで、0 \leq i, j, k < N です)。

  • + i j k: a[k] = a[i] + a[j] とする。
  • < i j k: a[k] = a[i] < a[j] とする。すなわち、a[i] < a[j] であれば a[k] は 1 となり、そうでなければ a[k] は 0 となる。

操作を行える回数は最大で Q 回であり、操作中に a の要素が V より大きくなってはなりません。 ただし、一回の操作で指定する添字 (i, j, k) に重複があっても構わず、(先頭二要素を含む) 配列のどの要素も書き換えて構いません。 なお、この問題の正誤判定機は、単一テストケースにおいて実際には複数のペア (A, B) について操作列を実行します。 各回について、判定機は値 A, B を選んで配列 a = [A, B, 0, 0, \ldots, 0] を生成し、提出された操作列を適用して最終的に a[2] = A \cdot B となるかを検証します。

制約

  • 0 \leq A, B \leq 10^9
  • N = Q = 200\,000
  • V = 10^{19} = 10\,000\,000\,000\,000\,000\,000

部分点

  • A, B \leq 10 を満たすテストケースを通過すると、800 点が与えられる。
  • すべてのテストケースを通過すると、さらに 1000 点が与えられる。

入力

標準入力から与えられる入力は空である。

出力

1 行目に、操作を行う回数を出力せよ。 続けて、行う操作をそれぞれ + i j k または < i j k という形式で一行に出力せよ。

Sample Input 1













Sample Output 1
4
< 0 1 8
+ 0 1 2
+ 2 8 2
+ 0 0 0



入力例 1 では、正誤判定機はペア (A, B) = (2, 3) についてのみ提出された操作列を検証します。
上記の出力は、このテストケースを通過します。その過程は次の通りです。


    

  • はじめ、a[0] = 2, a[1] = 3, a[2] = a[3] = \ldots = a[N-1] = 0 である。
    • 

  • < 0 1 8 により、a[0] < a[1] であるため a[8] = 1 となる。
    • 

  • + 0 1 2 により、a[2] = a[0] + a[1] = 5 となる。
    • 

  • + 2 8 2 により、a[2] = a[2] + a[8] = 6 となる。
    • 

  • + 0 0 0 により、a[0] = a[0] + a[0] = 4 となる。
    • 

  • 要求された通り、最終的に a[2] = 6 = A \cdot B となっている。
    • 







Score : 1800 points







Problem Statement
This is an output-only problem. You shouldn't read anything from the input.


In short, your task is to simulate multiplication by using only comparison (x < y) and addition (x + y).
There is no input in this problem, you just print a sequence of operations.


Imagine that there is a big array a[0], a[1], ..., a[N-1] of length N.
The first two values are initially two non-negative integers A and B (which are unknown to you),
    the other elements are zeros.
Your goal is to get the product A \cdot B in a[2] at the end.


You are allowed operations of two types, with the following format (where 0 \leq i, j, k < N):


    

  • + i j k — applies operation a[k] = a[i] + a[j].
    • 

  • < i j k — applies operation a[k] = a[i] < a[j].
    That is, if a[i] < a[j] then a[k] becomes 1, otherwise it becomes 0.
    • 



You can use at most Q operations.
Elements of a can't exceed V.
Indices (i, j, k) don't have to be distinct.
It's allowed to modify any element of the array (including the first two).
The actual checker simulates the process for multiple pairs (A, B) within a single test.
Each time, the checker chooses values A and B, creates the array a = [A, B, 0, 0, \ldots, 0],
    applies all your operations and ensures that a[2] = A \cdot B.











Constraints
    

  • 0 \leq A, B \leq 10^9
    • 

  • N = Q = 200\,000
    • 

  • V = 10^{19} = 10\,000\,000\,000\,000\,000\,000
    • 












Partial Score
    

  • 800 points will be awarded for passing tests that satisfy A, B \leq 10.
    • 

  • Another 1000 points will be awarded for passing all tests.
    • 

















Input
The Standard Input is empty.











Output
In the first line, print the number of operations.
Each operation should then be printed in a single line of format + i j k or < i j k.
















Sample Input 1












Sample Output 1
4
< 0 1 8
+ 0 1 2
+ 2 8 2
+ 0 0 0



In the first sample test, the checker checks your sequence only for a pair (A, B) = (2, 3).
The provided output is correct for this test:


    

  • Initially, a[0] = 2, a[1] = 3, a[2] = a[3] = \ldots = a[N-1] = 0.
    • 

  • < 0 1 8 applies a[8] = 1 because a[0] < a[1].
    • 

  • + 0 1 2 applies a[2] = a[0] + a[1] = 5.
    • 

  • + 2 8 2 applies a[2] = a[2] + a[8] = 6.
    • 

  • + 0 0 0 applies a[0] = a[0] + a[0] = 4.
    • 

  • As required, at the end we have a[2] = 6 = A \cdot B.
    •