논리의 돌

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

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

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

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

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

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

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

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

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

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