시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 512 MB 150 29 19 67.857%

문제

키파는 부족한 돈을 벌기 위해 네모 산타의 비밀공장에 취직했습니다. 이 공장의 목표는 곧 있을 크리스마스를 맞아 사람들이 자고 있을 밤에 남의 선물 공장에 들어가서 생산 공정에 있는 선물을 가져와 착한 어린이들에게 나눠주는 것입니다. 선물 공장은 밤중에 N개의 선물을 생산한다고 합니다.

선물의 종류는 박스, 브론즈 선물, 실버 선물, 골드 선물, 다이아몬드 선물이 있는데, 각 선물의 가치는 -100점, 100점, 200점, 300점, 600점이고, 선물의 가치를 더한 값을 인사고과에 반영한다고 합니다.

이곳에는 생산 공정에서 N개의 어떤 선물이 어떤 순서로 나올지를 전부 정확하게 아는 로봇 다오가 있습니다. 로봇 다오는 (로봇이기 때문에) 이 정보를 이용하여 항상 최선의 선택으로 선물을 가져옵니다. 그러나 하나의 선물을 가져와 놓는 데는 시간이 꽤 걸리기 때문에, 그동안 그 다음 선물을 놓치게 됩니다. 이는 키파도 마찬가지입니다.

키파는 로봇 다오의 역할을 다른 공장에서 대신 수행하기로 했습니다. 처음 일해보는 것이기 때문에 키파에게는 눈앞에 있는 선물을 보고 그 선물을 가져올지 말지 선택할 여유밖에 없습니다. 키파의 고용주 네모 산타는 키파를 시험하기 위해 이렇게 말했습니다:

만일 그곳에 로봇 다오가 있었다면 가져왔을 선물 가치의 p% 이상을 획득하면, 네게 첫 급여를 줄 것이야~ 호호호!

키파가 첫 급여를 받을 수 있도록 도와줍시다!

함수 목록 및 정의

제공되는 "solution.h"를 include하셔야 합니다.

다음과 같은 함수를 작성해야 합니다.

  • void init()
    • 프로그램이 실행되고 나서 로봇 다오가 있었을 때 선물의 가치를 계산한 직후 한 번만 호출됩니다. 프로그램 실행 시작부터 init() 함수의 호출까지 걸리는 시간이 10ms 이하임이 보장됩니다.
  • bool pick(int value)
    • 가치 value에 해당하는 선물이 눈앞에 있음을 의미합니다. 반환 값은 이 선물을 가져올 경우 true, 아니면 false입니다. 두 번의 연속된 pick 호출이 모두 true를 반환하면 안 됩니다.

입력

Grader는 다음과 같은 입력을 받습니다. 여러분의 소스 코드는 어떠한 입력도 받으면 안 됩니다.

첫 번째 줄에 양의 정수 p와 N이 공백을 사이에 두고 주어집니다. p는 30 이상 50 이하, N은 318 이상 1204 이하입니다.

두 번째 줄에 N개의 정수 a1, a2, ..., aN이 공백을 사이에 두고 주어집니다. 각 정수는 각 선물의 가치를 의미하며, -100, 100, 200, 300, 600 중 하나입니다.

출력

Sample Grader는 다음과 같은 정보를 출력합니다.

첫째 줄에 만일 여러분이 로봇 다오가 있었다면 가져왔을 선물 가치의 p% 이상을 가져왔다면 1, 아니면 0을 출력합니다.

제공 파일

Sample Grader: sample_grader.zip

서브태스크 1 (30점)

p = 30, ai ≠ 100.

서브태스크 2 (70점)

p = 50이고, ai = -100인 것의 개수는 전체의 40%를 넘지 않습니다.

예제 입력 1

500
200 200 200 ... 200

예제 출력 1

1

예제 입력은 ai = 200이 주어지는 입력입니다.

로봇 다오의 최선은 매 홀수 번째를 모두 가져오든지 매 짝수 번째를 모두 가져오든지 등의 방법으로 5만 점을 획득하는 것입니다.

호출 예시

다음은 위의 입출력 예제에 대해서, Sample Grader와 상호 작용하는 과정을 나타낸 것입니다.

solution.cpp Grader 설명
  p = 30, N = 500 Grader에서 pN의 값을 읽어들입니다.
  tk = 50000 Grader에서 최적의 값을 계산합니다.
  init() 호출 init 함수는 초기에 한 번만 호출됩니다.
  pick(200) 호출  
true 반환    
  pick(200) 호출  
false 반환    
  pick(200) 호출  
false 반환    
... ... 500번 반복합니다. solution.cpp는 true를 두 번 연속 반환하지 않았습니다.
  1 가치를 모두 더한 결과는 16400이었고, 50000의 30%를 넘습니다.

출처

Contest > 키파컵 > 제2회 키파컵 D번

  • 문제를 만든 사람: kipa00

제출할 수 있는 언어

C++14, C++11, C++17

채점

  • 예제는 채점하지 않는다.