시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 47 10 7 26.923%

문제

폴리매스 문명의 마지막 돌로 알려진 논리의 돌은 아직 그 용도가 확실히 밝혀지지 않았습니다. 대다수의 학자들은 논리의 돌에서 생산해 내는 논리의 돌 조각을 이용해 기초적인 논리 회로를 구성할 수 있었던 것으로 추정하고 있습니다.

돌 조각에서 사용한 신호는 ‘스핀’이라고 불리며, 스핀은 항상 1을 나타내는 ‘업-스핀’또는 0을 나타내는 ‘다운-스핀’ 중 하나의 상태를 가집니다. 논리의 돌 조각은 두 개의 입력 장치를 가지며, 양쪽 모두가 1일 때 1을 반환하는 AND 회로의 형태를 하고 있습니다.

물론 이 구조만 가지고는 논리 회로를 구성할 수 없습니다. 하지만 기록에 따르면 사람들은 놀라운 해결책을 찾아냈는데, 입구에 신호를 위아래로 뒤집어서 주게 되면 신호를 반전시킬 수 있어 논리 회로를 구성할 수 있게 된 것입니다.

논리 회로를 구성하는 방법에 대해 연구하기 위해, 당신은 기초적인 상황에 대한 논리 회로를 직접 구성해 보기로 했습니다. 당신이 풀어야 할 문제는 개의 비트를 오름차순으로 정렬하는 것입니다. 즉, 프로그램의 동작이 끝난 뒤에 모든 ‘1’의 비트는 모든 ‘0’의 비트보다 오른쪽에 있어야 합니다.

초기에 각 비트의 정보는 $1$번 비트부터 $N$번 비트까지에 저장되어 있습니다. 당신은 이를 위해 AND 게이트를 사용할 수 있으며, 사용 방법은 출력 형식을 참조하면 됩니다. 또한 당신은 문제를 풀기 위해 $N$개의 비트 이외에 $K$개의 추가 비트를 사용할 수 있으며, 이들의 번호는 $N+1$부터 $N+K$까지입니다. 다만 추가 비트를 사용하는 것은 다른 연산의 다섯 배의 비용이 들기 때문에, 추가 비트의 사용은 되도록 줄여야 합니다. 사용한 추가 비트의 개수 $K$와 AND 게이트를 사용한 횟수 $Q$, 그리고 추가 비트를 사용하는 연산의 횟수 $Q_1$에 따라서 아래와 같이 점수가 매겨집니다.

$$100 \times min(1, \frac{375}{(Q-Q_1)+5Q_1} ) \times \frac{1}{ max( k, 1 ) }$$

입력

이 문제는 입력이 없습니다.

출력

첫 줄에는 AND 게이트를 사용할 횟수 $Q$를 출력합니다.

다음 줄부터 개의 줄에는 AND 게이트를 사용하는 방법을 $a$ $b$ $c$의 형태로 출력합니다. 이 표현의 의미는 아래와 같습니다.

부호 $b$ $c$ $a$  
(+) $b$번 비트와 $c$번 비트를 AND한 값을 $|a|$번 비트에 대입합니다.
(-) $|b|$번 비트의 반대 비트를 $|c|$번 비트의 반대 비트를 AND한 값의 반대 비트를

 

제한

  • $N=16$
  • $K \le 10$
  • $Q \le 1000$
  • $1 \le |a|, |b|, |c| \le N+K$
  • 추가 비트는 무조건 초기화를 한 뒤에, 즉 값을 대입한 뒤에 사용해야 합니다.
  • $|a|, |b|, |c|$는 서로 같아도 됩니다.

예제 입력 1


						

예제 출력 1

3
-3 -1 -2
4 1 2
1 3 -4

위 프로그램은 1번 스핀과 2번 스핀의 OR 값을 3번 스핀에, 1번 스핀과 2번 스핀의 AND 값을 4번 스핀에 저장하게 됩니다. 또한 3번 스핀과 4번 스핀의 반대를 AND한 값을 1번 스핀에 다시 대입합니다.

위 프로그램은 출력 예시를 보여줄 뿐, 답이 아님에 주의하시기 바랍니다.

노트

채점 프로그램은 가능한 모든 이진 수열에 대해 참가자가 제출한 프로그램으로 정렬을 시도하며, 모든 이진 수열의 정렬에 성공했을 때만 위에 해당하는 점수를 부여합니다. 그렇지 않을 경우, 점수를 받지 못합니다.

채점 및 기타 정보

  • 100점 이상을 획득해야 를 받는다.
  • 예제는 채점하지 않는다.