루미 알고리즘

#1638플래티넘Mushrooms

PO 2026 결선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

(그림은 원문 저장소에서 볼 수 있습니다)

To be able to run your new AI startup, you need to perform large-scale parallel computations. A strong candidate for this turns out to be mushrooms! To compute things, you have a cluster of N mushrooms numbered from 1 to N. You now want to load the weights of a neural network into the mushrooms. Each mushroom stores a number, which initially is 0.

To change the values stored in the mushrooms, you can perform a round. In each round, you give one instruction to each mushroom. All these instructions are then executed simultaneously. Let P[i] denote the value of mushroom i before the round, and A[i] the value of mushroom i after the round. The available operations for mushroom i are:

Instruction — Operation — Description

  • p — A[i] = P[i] — keep the previous value
  • < j — A[i] = P[j] << 1 — where << denotes bitwise left shift
  • > j — A[i] = P[j] >> 1 — where >> denotes bitwise right shift
  • + j — A[i] = P[j] + 1 — where + denotes addition
  • ^ j — A[i] = P[i] ^ P[j] — where ^ denotes bitwise XOR
  • & j — A[i] = P[i] & P[j] — where & denotes bitwise AND
  • | j — A[i] = P[i] | P[j] — where | denotes bitwise OR

Be sure to read the descriptions of the operations carefully. You can find definitions of all bitwise operations here (https://en.wikipedia.org/wiki/Bitwise_operations_in_C#Bitwise_operators). The mushrooms can store arbitrarily large numbers. This means that bitwise left shift and addition always cause the value to increase.

You are now given N weights w_1, w_2, …, w_N and need to find a sequence of rounds such that A[i] = w_i for all i.

The fewer rounds you use, the more points you get. In the test data, N is always 512.

Input

The first line of input contains the integer N (N = 512), the number of mushrooms. The reason this is part of the input is to make it easier to test your solution on smaller values of N.

The second line contains the integers w_1, w_2, …, w_N (0 ≤ w_i ≤ 255), the weights of the neural network.

Output

First, print the integer r, the number of rounds your solution uses.

Then print r lines, where each line describes one round. For each round, print the N operations, separated by spaces. The first operation is the one that mushroom 1 should execute, the second that mushroom 2 should execute, and so on. Each operation should be printed in the same format as in the table above, where j (1 ≤ j ≤ N) is the index of a mushroom. Two examples of how valid single operations could look like are “p” and “< 10”.

Scoring

Your solution will be tested on a number of test cases. If it ever prints a sequence of rounds that is invalid or does not produce the correct weights, you get zero points.

Otherwise, let R_max denote the largest number of rounds you use over all test cases. You then get points according to the following piecewise linear function.

(그림은 원문 저장소에서 볼 수 있습니다)

The number of points you get for a given R_max. Note that the x-axis is not linear.

If R_max ≤ 9, you get 100 points. The score values for 9 ≤ R_max ≤ 20 are also given in the table below.

R_max91011121314151617181920
Points1007060504847464544434241

Sample Judge

To make it easier to test your program, a sample judge is provided in the attachments at the bottom. This is not the same judge code that is used on Kattis. A description of how to run the code is given in the comment at the beginning of the code.

Explanation of Sample

Note: the following sample case will not be run against your submission since N ≠ 512. It exists only to demonstrate the input and output format; all input that your solution is tested on has N = 512.

Initially, all mushrooms have the value 0. Below, the mushrooms' values before and after each operation are shown.

0 0 0 0
0 1 0 1
0 1 2 2

출처 표기

출처: Programmeringsolympiaden 2026년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.