Fewest Moves Challenge

큐브를 하면 머리가 좋아진다는데, 실제로 큐브를 맞춰 보신 분들은 공식만 잔뜩 외우고 연습만 열심히 해서 큐브를 어떻게든 더 빨리 맞추려는 스피드큐빙 커뮤니티에 어쩌면 실망하셨을지도 모르겠습니다. 여러분들을 위해 333 최소 회전 풀이 분야를 소개드립니다.

333 최소 회전 풀이(333 Fewest Moves Solution)는 333 큐브를 최소한의 이동(move)을 사용해서 맞추는 풀이를 찾는 분야입니다. 다양한 상황을 만날 수 있고, 정말로 머리를 써야 하는 분야입니다. 예를 들어, 이 분야에서 상황에 맞는 공식을 창조하는 것은 기본 중의 기본입니다! 이 분야도 공식 대회가 열립니다. 공식 대회의 규칙은 이곳에서 보실 수 있으며, 별도로 명시되지 않은 경우 이 문제 역시 이 규칙을 따릅니다. 노트 란에 번역본 및 바뀐 규칙을 표시해 두었습니다.

키파는 컴퓨터가 333 최소 회전에 도전(Fewest Moves Challenge)하는 것은 딥 러닝의 시대에 매우 적합하다고 판단했고, 이에 맞는 규칙을 만들기 시작했습니다.

우선 컴퓨터는 연산을 1초에 1억 번 할 수 있다는 암묵의 규칙을 떠올렸습니다. 사람이 1초에 한 번 연산을 할 수 있는 건 아니지만, 1초에 한 번 연산할 수 있다고 가정하고 36억 ㎲에 한 개의 큐브의 해법을 얻는다면, 컴퓨터는 36㎲에 한 개의 큐브의 해법을 얻어야 합니다. 36㎲는 너무 작은 시간이므로 대신 3만 개의 큐브를 1.08초에 해결하는 것으로 바꾸었습니다.

다음으로 사람은 큐브의 상태를 보고 섞기 수열을 얻어낼 수 없기 때문에, 섞기 수열을 제공하고 대신 풀이가 섞기 수열과 관련이 있으면 안 된다는 조항을 넣어서 해결합니다. 섞기 수열이 제공되기 때문에 NISS 등의 방법을 사용할 수 있습니다. 컴퓨터는 큐브를 평범한 해법으로 맞춘 다음 섞기 수열을 만들어낼 수 있으므로, 섞기 수열이 필요 없습니다. 대신 큐브의 상태를 직접 주는 것으로 바꾸었습니다.

이런 귀찮은 일을 하고 있자니 키파는 에너지가 떨어져서, 이 "컴퓨터 FMC" 대회를 대신 구데기컵에 열기로 했습니다. 여러분은 프로그램을 작성해서, 이 프로그램을 컴퓨터 FMC 대회에 참가시켜야 합니다.

웬만큼 잘하는 사람이 평균 35회전을 한다고 하니 이것보다는 잘해야겠죠...!

첫째 줄에 333 큐브의 개수 N이 주어집니다. N은 1 혹은 30 000이며, N = 1인 데이터는 예제밖에 없습니다.

둘째 줄부터 9N개의 줄에 N개의 큐브가 주어집니다. 큐브 하나가 총 9줄에 걸쳐 주어지며, 333 큐브를 나타내는 54개의 정수가 예제 입력과 비슷한 형식으로 주어집니다. 큐브 조각의 색을 나타내는 정수는 1 이상 6 이하입니다. 각 면의 중앙 색은 예제 입력과 항상 같습니다.

입력으로 주어지는 모든 큐브는 면 회전만으로 맞출 수 있습니다.

N개의 줄에 풀이를 노트 란의 규정을 참고해서 출력합니다. 중앙 색이 1인 면이 위쪽 면(U 회전의 면), 2인 면이 앞쪽 면(F 회전의 면)입니다.

점수 계산 방식

한 테스트 케이스에 대해서 점수는 다음과 같이 계산됩니다: 노트 란의 규정에 따라 계산된 무브 수의 총합을 N으로 나눈 값(평균)을 v라 합시다.

• v ≤ 65이면, S := 222 222 · 2(35-v)/5로 둡니다.
• v > 65이면, S := 231.48125 · (80 - v)로 둡니다.

S가 222 222 이상이면 222 222점을 받습니다. 이외의 경우 테스트 케이스의 점수는 S와 최대 0.02까지 차이날 수 있습니다.

예제 이외의 테스트 케이스는 총 10개이며, 최종적으로 받게 되는 점수는 모든 테스트 케이스 점수의 최솟값입니다.

FMC를 처음 시작하시는 경우 위의 예시 풀이가 큰 도움이 될 수도 있습니다.

스피드큐빙을 이미 어느 정도 즐겨 보신 분의 경우, 추천하는 FMC 튜토리얼은 이쪽(영어)입니다. 루빅스 큐브가 완전히 처음이시라면 이쪽(대부분 영어)을 추천드립니다.

큐브 매니아의 FMC 튜토리얼은 초심자들에게도 굉장히 친절하게 쓰여 있지만, 안타깝게도 카페 가입을 해야 볼 수 있습니다.

노트

아래는 "E. 최소 회전 풀이"의 번역본이며, 아래에 문제에서 변경된 사항을 적어 두었습니다. 사라진 사항은 취소선으로, 추가된 사항은 굵은 글씨로 표시해 두었습니다.

• E2) 3x3x3 최소 회전의 절차:

  • E2a) 심판이 섞기 수열30,000개의 큐브 상태와 종이1024MB의 메모리를 모든 선수에게 나누어 줍니다. 그러고 나서 스톱워치를 시작하고 "GO"를 외칩니다선수를 실행합니다. 섞기 수열은 나누어드리지 않으므로, 섞기 수열이 필요하면 큐브를 맞춘 뒤 수열의 역순을 사용하세요.

    • E2a1) 시도가 시작하기 전에, 참가자는 어떠한 것도 종이메모리에 작성해서는 안 됩니다. 예외: 참가자는 이 시도를 식별할 수 있는 정보를 남길 수 있습니다(규정 E2c1 참조). 만일 섞기 수열이 적힌 종이에 이 정보를 적는다면, 이 정보는 반드시 섞기 수열이 없는 면에 적어야 합니다. 이 시도를 식별할 수 있는 정보 이외의 것을 적는 것에 대한 처벌: 시도의 실격(DNF).

  • E2b) 참가자가 섞기 수열 하나30,000개의 큐브 상태에 대한 풀이를 순서대로 적을 시간은 총 60분1.08초입니다.

    • E2b1) 심판은 55분째에 "5 MINUTES REMAINING"을 외칠 필요가 있고, 60분에는 "STOP"을 외쳐야 합니다.심판은 1.08초 이후 참가자를 강제 종료할 수 있습니다. 프로그램이 강제 종료되었고 타이머가 1.08초를 넘은 것에 대한 처벌: 시도의 시간 초과(TLE).

  • E2c) 60분째에1.08초째까지 각 선수는 해결 방법과 시도를 식별할 수 있는 정보가 적힌 종이 한 장을 심판에게 제출표준 출력(stdout)에 출력해야 합니다.

    • E2c1) 시도를 식별하기 위한 정보는 선수의 이름, WCA ID, 대회 등록자 ID 중 최소 하나(여러 개도 가능)이며, 추가로 대회 이름, 라운드, 시도 번호를 기재할 수 있습니다. 이름, WCA ID, 또는 대회 등록자 ID가 없는 제출된 풀이에 대한 처벌: 시도의 실격(DNF).
    • E2c2) 풀이는 각 개별 이동이 순차적인 순서로 작성된 하나의30,000개의 명확한 이동 수열이어야 합니다. 모호한 풀이에 대한 처벌: 시도의 실격(DNF)틀렸습니다(WA).
      • E2c2') 하나의 이동은 공백 없이 출력해야 하며, 이동과 이동 사이에는 공백이 정확히 하나 있어야 합니다. 하나의 풀이 끝에는 줄바꿈(line feed)이 있어야 합니다.
    • E2c3) 선수는 종이에 적힌 움직임 중 풀이의 일부로 의도하지 않은 것을 명확하게 까맣게 칠하기 혹은 두 줄 긋기 해야 합니다움직임을 표준 출력(stdout)에 출력해서는 안 됩니다. 예외: 줄 마지막의 공백은 0개 혹은 1개 허용됩니다. 처벌: 시도의 틀렸습니다(WA).
    • E2c4) 선수의 풀이는 규정 12a12a1의 3x3x3 큐브 표기법으로 정확히 정의된 동작만 사용해야 하며, 규정 12a12a1에 구체적으로 정의되지 않은 기호 또는 기호 조합을 사용해서는 안 됩니다. 처벌: 시도의 실격(DNF)틀렸습니다(WA).
    • E2c5) 해결된 퍼즐로 시작하여 섞기 수열을 적용한 후주어진 큐브 상태에서 시작하여 풀이가 큐브를 맞추면 올바른 것으로 간주됩니다. 잘못된 풀이에 대한 처벌: 시도의 실격(DNF)그 큐브 상태에 대해 80 이동(EM).

  • E2d) 선수의 결과는 외부 블록 회전 기준(규정 12a5 참조)을 사용하여 계산된 풀이의 이동 횟수입니다.

    • E2d1) 선수의 풀이는 실행 회전 기준외부 블록 회전 기준을 사용하여 계산할 때 80 이동(회전 포함)을 초과해서는 안 됩니다(규정 12a612a5 참조). 처벌: 시도의 실격(DNF)틀렸습니다(WA).

  • E2e) 선수의 풀이는 섞기 수열의 어떤 부분에서도 직접 파생되어서는 안 됩니다. 벌칙: WCA 대표의 재량에 따라 시도의 실격(DNF).

    • E2e1) WCA 대표는 섞기 수열과 상관없이 참가자에게 풀이에서 각 움직임의 목적을 설명하도록 요청할 수 있습니다. 선수가 유효한 설명을 할 수 없는 경우, 그 시도는 실격 처리됩니다(DNF).

• E3) 선수는 시도 중에 다음과 같은 물건을 사용할 수 있습니다. 승인되지 않은 물건 사용에 대한 벌칙: 시도의 실격(DNF)컴파일 에러(CE).

  • E3a) 종이메모리(심판 제공) 및 펜/연필 또는 이와 유사한 것(심판 제공, 자급할 수 있음).
  • E3b) 3조에 설명된 대로 3x3x3 큐브(최대 3개, 자급).
  • E3c) 스티커(자급).
  • E3d) WCA 대표가 승인한 경우 경과 시간을 확인하기 위한 스톱워치 또는 시계clock() 등의 시간을 알 수 있는 C/C++ 헤더(자급).
  • E3e) WCA 대표의 재량에 따라 불공정한 이점을 제공하지 않는 기타 비전자적 지원(규정 2i1 참조)선수가 사용하는 프로그래밍 언어에 내장된 기타 기능 (심판 제공).
  • E3f) 수정액, 수정 테이프 또는 지우개와 같은 표시를 제거하는 도구(자급).

• E4) WCA 대표는 풀이(예: 점수 시트의 사진 또는 풀이 전사)를 게시하도록 선택할 수 있습니다.