루미 알고리즘

#1615다이아Neural Bakework

PO 2025 장기 대회코딩출제 Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Arvid is preparing for the AI Olympiad final. There's much to do: arranging accommodations, organizing food, preparing problems, and setting up snacks for everyone. Stressed out, Arvid accidentally mixes up the last two tasks. As a participant in the AI Olympiad, you must solve the strange problem that arose.

A neural bakework is a directed graph with N nodes, designed to bake cookies. Initially, X units of ingredients are placed on node 1, while all other nodes start with zero ingredients. Every second, the following occurs simultaneously for all nodes:

  • Let a_v be the number of ingredients on node v, and d_v be its out-degree.
  • If d_v = 0, nothing happens. Otherwise, let a_v = d_v · q + r where 0 ≤ r < d_v. Afterwards send q units of ingredients to each node pointed to by v, and keep the remainder r.

In other words, each node splits its ingredients as evenly as possible and forwards the result. All updates happen simultaneously across all nodes each second, so the processing order of nodes does not matter.

The ingredients reaching node N become finished cookies. For the neural bakework to be valid, no node may point to itself, and no node may have multiple edges to the same target.

Given integers X and Y, your task is to construct a neural bakework that produces exactly Y cookies when X units of ingredients are used. Specifically, the bakework will run for 10^4 seconds, and if node N ends up with Y cookies, the test case is solved. Your score depends on minimizing N.

Input

The input consists of a single line with two integers X and Y (1 ≤ X, Y ≤ 10^18).

Output

If no valid neural bakework can produce Y cookies from X ingredients, output -1.

Otherwise, output first a line with two integers N and M, the number of nodes and edges in your network. Then output M lines, each containing two integers u_i, v_i (1 ≤ u_i, v_i ≤ N), representing an edge from node u_i to v_i.

Scoring

There are two test groups that scores independently. Each test group contains a set of test cases.

Let N_max be the maximum value of N in your solution across all test cases in a group. If N_max ≤ 30 then you get full points for the group, otherwise, points are calculated as:

(20 · g)/(N_max - 10)

where g is the group's total points (20 or 80).

If N_max ≥ 200 or your answer is incorrect for any test case, you get 0 points for the group.

GroupPointsConstraints
120X, Y ≤ 20
280No additional constraints.

예제

예제 1

입력
15 4
출력
8 10
1 2
2 3
3 4
4 2
1 4
1 5
5 6
5 7
6 8
7 8

예제 2

입력
1 2
출력
-1

출처 표기

출처: Programmeringsolympiaden 2025년 장기 대회 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.