만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

문어 게임

시간 제한1초메모리 제한512 MB

요약
두 카드의 초기 값이 주어질 때, 한 카드에 0이 쓰이도록 다른 카드의 배수를 더하는 동작을 50회 이하로 출력하고, 모든 중간 값의 절댓값이 10^18 이하가 되게 한다.
난이도

보통10점 중 7점

유형
정수론, 수학, 구현
정답자
아직 제출이 없습니다

문제

어느 나라에서 문어 게임이라는 대회가 열린다.

이번 라운드에서 참가자는 수학 퍼즐을 푼다. 각 플레이어는 카드 두 장을 가지고 시작하며, 처음에 첫 번째 카드에는 a0a_0, 두 번째 카드에는 b0b_0가 적혀 있다.

플레이어는 자신의 카드로 행동을 한다. 카드에 적힌 정수를 각각 aa, bb라고 하자. 플레이어는 먼저 정수 kk를 고른 뒤 다음 연산 중 하나를 수행한다.

  1. 첫 번째 카드의 정수를 a+kba + kb로 바꾼다.
  2. 두 번째 카드의 정수를 b+kab + ka로 바꾼다.

게임 중 카드에 적힌 정수의 절댓값은 101810^{18}을 넘어서는 안 된다. 그렇지 않으면 좋지 않은 일이 일어날 수 있다. 최대 50번의 행동을 수행한 뒤 카드 중 하나에 0이 적혀 있으면 그 플레이어가 이번 라운드에서 이긴다.

여러분은 이 게임을 하게 된다. 물론 이기고 싶을 것이다.

입력

입력의 유일한 줄에 카드에 처음 적힌 두 정수 a0a_0와 b0b_0가 주어진다 (−1018≤a0,b0≤1018-10^{18} \le a_0, b_0 \le 10^{18}).

출력

첫 줄에는 카드 중 하나에 0이 적히게 하려고 플레이어가 수행하려는 행동의 수 nn을 출력한다 (0≤n≤500 \le n \le 50). 행동 수를 최소화할 필요는 없지만 50을 넘어서는 안 된다.

다음 nn개의 줄에는 각각 공백으로 구분된 두 정수 tit_i, kik_i를 출력한다. tit_i는 해당 행동의 종류, kik_i는 해당 행동에서 고른 정수 kk이다.

유효한 답이 여러 개면 아무거나 출력해도 된다. 단, 게임 중 카드에 적힌 정수의 절댓값은 101810^{18}을 넘어서는 안 된다.

힌트

첫 번째 테스트에서는 행동 한 번이면 충분하다. 첫 번째 카드의 정수에 3을 곱한 값을 두 번째 카드의 정수에 더하면 된다.

두 번째 테스트에서는 첫 번째 행동 후 카드에 각각 −27-27과 33이 적혀 있고, 두 번째 행동 후에는 00과 33이 적혀 있다.

세 번째 테스트에서 카드의 정수는 차례로 5656과 1515, 2626과 1515, 1111과 1515, 1111과 −7-7, 44와 −7-7, 44와 11, 00과 11이다.

예제3

  1. 예제 1

    입력
    -3 9
    
    예상 출력
    1
    2 3
    
  2. 예제 2

    입력
    -27 57
    
    예상 출력
    2
    2 2
    1 9
    
  3. 예제 3

    입력
    56 15
    
    예상 출력
    6
    1 -2
    1 -1
    2 -2
    1 1
    2 2
    1 -4