21565번 - 논리의 돌 점수

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

돌 조각에서 사용한 신호는 ‘스핀’이라고 불리며, 스핀은 항상 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$의 형태로 출력합니다. 이 표현의 의미는 아래와 같습니다.

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

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