킬 스위치 (어려움)

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

요약

주어진 잘못된 정렬 함수가 제대로 정렬하지 못하는 가장 짧은 32비트 부호 없는 정수 배열을 찾습니다.

난이도: 어려움10점 중 9점
유형: 구현, 완전 탐색, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

킬 스위치는 비상 상황에서 기기를 끄는 데 쓰는 장치다.

제레미는 수상한 소프트웨어 회사와 계약직으로 일했다. 작업을 마치자 회사는 계약서의 허점을 근거로 그의 작업에 대한 대가를 전혀 지급하지 않았다. 회사는 제레미가 부정한 낌새를 눈치채고 코드에 킬 스위치를 숨겨 두었다는 것을 꿈에도 모른다.

32비트 부호 없는 정수 배열을 비내림차순으로 정렬하는 척하는 함수의 구현이 주어진다. 이 함수가 제대로 정렬하지 못하는 가장 짧은 입력을 찾아라.

입력

각 서브태스크에는 입력 파일이 두 개 있다. 하나는 C++ 구현이고, 다른 하나는 같은 함수를 구현한 Python 파일이다.

(답이 $n$ 이면, 두 프로그램은 적어도 크기가 $n + 47$ 이하인 모든 올바른 입력에 대해 같은 방식으로 동작한다고 가정해도 된다. 주의할 점으로, 입력이 매우 크면 C++ 구현에서 정수 오버플로가 생길 수 있다. 그런 입력은 이 문제에 포함되지 않으므로 무시해도 된다.)

출력

출력 파일에는 두 줄이 있어야 한다. 첫 줄에는 제대로 정렬되지 않는 배열의 가능한 최소 길이 $n$ 을 음이 아닌 정수로 쓴다. 둘째 줄에는 그 배열의 초기 내용 중 하나를 $A[0], \ldots, A[n-1]$ 형태로 쓴다. 이 값들은 $0 \le A[i] < 2^{32}$ 을 만족해야 한다.

예제1

예제 1

입력

void example_sort(vector<unsigned> &A) {
    int N = A.size();
    if (N >= 2 && A[0] > A[1])
        swap( A[0], A[1] );
    if (N >= 3 && A[0] > A[2])
        swap( A[0], A[2] );
    if (N >= 3 && A[0] > A[1])
        swap( A[0], A[1] );
}
-----------------------------------------
def example_sort(A):
    N = len(A)
    if N >= 2 and A[0] > A[1]:
        A[0], A[1] = A[1], A[0]
    if N >= 3 and A[0] > A[2]:
        A[0], A[2] = A[2], A[0]
    if N >= 3 and A[0] > A[1]:
        A[0], A[1] = A[1], A[0]

예상 출력

3
42 47 1