올림픽 피자 Batch Compilation commands

원문 링크

피자는 널리 알려진 전통 이탈리아 음식으로, 오븐에 구운 납작한 빵에 토마토소스와 녹인 모차렐라 치즈, 그 외 여러 선택적인 토핑이 덮인 음식이다. 피자는 그 모양(둥근 피자, 직사각형 피자, 정사각형 피자), 두께(몇 밀리미터부터 몇 센티미터까지), 그리고 가장 중요한 토핑 (치즈, 햄, 살라미, 소시지, 튀김, 버섯, 올리브 등, 그리고 이들의 모든 조합) 등에 따라 구분되어 정말 많은 종류가 있다. 이것이 몇몇 피자 전문점(피자리아)들이 그렇게 다양한 종류의 피자를 제공할 수 있는 이유다!

올림픽 피자

붐비는 IOI의 피자리아는 주문을 관리하고, 그 유명한 피자를 만들기 위해 당신의 도움이 필요하다. 이 곳의 비밀은 매우 신선한 재료를 사용하는 것이며, 이를 위해선 새로운 재료를 자주 배송받아야 한다. 이탈리아의 빈번한 교통 체증 때문에, 많은 재료들이 늦게 배송되고, 따라서 몇몇 순간에는 일부 재료를 사용할 수 없다. 만약 어떤 재료를 사용할 수 없다면, 이 피자리아는 해당 재료를 사용하는 모든 피자를 만들 수 없다.

당신이 해야 할 일은 새 피자 주문과 새 재료 배송에 대한 정보를 받는 프로그램을 작성하는 것이다. 또한, 이 프로그램은 피자 요리사에게 (일부 재료를 사용할 수 없지 않는 한 바로)피자를 만들 수 있는지 알려줘야 한다.

문제

당신은 위에 서술된 것과 같이 주문과 배송을 받고, 피자 요리사에게 언제 피자를 만들 수 있는지 알려주는 프로그램을 작성해야 한다. 구체적으로, 피자에 토핑될 수 있는 재료는 정확히 8가지로, 0부터 7까지의 정수로 표현된다. 주문된 피자의 번호 또한 0 (첫 번째 주문)에서 시작해서 순서대로 표현된다. 당신은 프로그램에 다음과 같은 함수들을 작성해야 한다.

• Init(): 프로그램이 실행될 때 최초로 (다른 어떤 함수도 호출되기 전) 호출되어 피자 전문점이 주문과 배송을 받기 시작할 수 있다는 것을 나타낸다.

• Order(N, A): 자연수 $N\le8$과 $N$개의 정수로 이루어진 배열 $A$(각 정수는 $0$이상 $7$이하로 중복은 없다)가 주어져서, $A$로 표현된 $N$개의 재료(임의의 순서)로 이루어진 피자가 주문되었다는 것을 나타낸다.

• Delivery(I): $0$이상 $7$이하의 정수 $I$가 주어져서, 한 번 분량(하나의 피자에 사용 가능)의 재료 $I$가 배송되었 다는 것을 나타낸다.

당신의 프로그램은 피자 요리사에게 피자를 구우라는 것을 알려주기 위해, 시스템에 구현된 다음 함수를 호출해야 한다.

• Bake(K): 정수 $K\ge0$가 주어져서, $K$번 주문에 해당하는 피자를 구워야 한다는 것을 나타낸다.

당신은 재료들이 준비되자마자 Bake를 호출해야 한다. 만약 여러 개의 피자를 만들 수 있다면, 더 빨리 주문된 피자를 선택해야 한다. 주문된 피자들 중 일부는 재료 부족으로 절대 만들 수 없을 수도 있다.

예제

다음 예제에서 왼쪽 열은 채점 프로그램이 호출하는 당신이 구현한 함수를 의미하고, 오른쪽 열은 당신이 구현한 함수가 호출해야 할 함수를 의미한다.

Your routines	System routine
Init()
Delivery(1)
Delivery(1)
Delivery(1)
Delivery(2)
Delivery(2)
Order(3,[1,2,3])
Delivery(4)
Delivery(4)
Order(3,[1,2,4])	Bake(1)
Delivery(3)	Bake(0)
Order(4,[1,2,3,4])
Delivery(2)

서브태스크

서브태스크 1 (25점)

• Order와 Delivery 함수는 합쳐서 많아야 100번 호출된다.

서브태스크 2 (25점)

• Order와 Delivery 함수는 합쳐서 많아야 5 000번 호출된다.

서브태스크 3 (20점)

• Order와 Delivery 함수는 합쳐서 많아야 100 000번 호출된다. 또한, Delivery 함수가 모두 호출된 후에야 Order 함수가 호출된다.

서브태스크 4 (30점)

• Order와 Delivery 함수는 합쳐서 많아야 100 000번 호출된다.

구현 시 유의사항

인터페이스

문제에 제시된 첨부파일 grader.zip에서 개발에 필요한 인터페이스가 제공됩니다. (IOI에서 제공한 인터페이스에서 편의를 위해 약간 변경했습니다.) 아래에 그 설명이 있습니다.

• 작성해야 할 파일: pizza.c 또는 pizza.cpp
• 채점 프로그램 인터페이스: pizza.h
• 견본 채점 프로그램: grader.c 또는 grader.cpp
• 컴파일 쉘(gcc): compile_c.sh 또는 compile_cpp.sh
• 입력 예제: example.in, example.out

이 문제에서 주어지는 견본 채점 프로그램은 표준 입출력(stdin, stdout)으로 입출력을 수행합니다.

견본 채점 프로그램의 입력 형식은 아래와 같습니다.

• 첫 번째 줄: Order와 Delivery의 총 호출 횟수 M
• 2 ~ (M + 1)번째 줄
  • o N A[0] A[1] .. A[N - 1]: Order(N, A)를 호출합니다.
  • d I: Delivery(I)를 호출합니다.