시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 (추가 시간 없음) | 128 MB | 230 | 116 | 67 | 48.201% |
CS-House에서는 매주 목요일에 연세대학교 컴퓨터과학과에 대한 여러 이야기를 팟캐스트 형식으로 다룬다. 2021년 3월 18일에 진행한 CS-House에서는 ICPC World Final에 진출한 윤인섭 선배가 게스트로 나와서 알고리즘 및 Competitive Programming에 대해서 이야기를 했다. 이야기 도중에 시청자들과 함께 재미있는 문제들을 풀어보는 시간을 가졌는데, 그 문제 중 하나를 변형해서 연세대학교 신입생 프로그래밍 경진대회에 내기로 했다. 다음과 같은 문제를 생각해보자.
그림과 같이 $N$명의 사람이 앞을 보고 일렬로 서있다. 각 사람은 맨 뒷사람을 제외하고 $0$ 이상 $63$ 이하의 정수가 적힌 모자를 쓰고 있다.
각 사람은 자신보다 앞에 있는 사람의 모자에 적힌 수를 모두 볼 수 있지만, 자신을 포함해서 뒤에 있는 사람의 모자에 적힌 수는 볼 수 없다.
게임이 시작되면 맨 뒷 사람부터 순서대로 $0$ 이상 $63$ 이하의 정수 중 하나를 말한다.
게임을 시작하기 전 $N$명의 사람들이 모여 작전을 세우려고 한다. 자신이 말한 수와 자신의 모자에 적힌 수가 동일한 사람이 최대한 많아지도록 작전을 세워보자.
이 문제를 풀기 위해서는 hat.cpp 파일을 제출해야 한다. hat.cpp 파일에 포함되어야 하는 함수는 다음과 같다..
void init(int N);
N
은 일렬로 서있는 사람의 수를 의미한다.int call(vector<int> F, vector<int> B, int num);
(num+1)
번째에 서있는 사람이 말해야 하는 수를 return
한다. num
은 $0$ 이상 $N-1$ 이하의 정수다.F
는 앞에 있는 사람들이 쓴 모자의 수를 저장한 길이 $N$의 정수 배열이다. F[i]
에는 i+1
번째 사람이 쓴 모자의 수가 저장되어 있다. 만약 num+1
번째 사람이 i+1
번째 사람이 쓴 모자의 수를 볼 수 없다면 해당 배열 값은 $0$이다.B
는 뒤에 있는 사람들이 말한 수를 저장한 길이 $N$의 정수 배열이다. B[i]
에는 i+1
번째 사람이 말한 수가 저장되어 있다. 만약 num+1
번째 사람이 말하기 전에 i+1
번째 사람이 말하는 차례가 오지 않았다면 해당 배열 값은 $0$이다.call
은 총 $N$번 호출된다. call
이 호출될 때 마다 num
에는 $N-1$부터 $0$까지 수가 순서대로 들어간다.총 $T$번의 모자 게임이 동시에 진행되며, 각 게임별로 $N-1$명이 자신이 쓴 모자에 적힌 수와 동일한 수를 말해야 맞았습니다!!를 받을 수 있다. Grader가 실행 도중 틀렸습니다라고 판정한 경우, 그 즉시 프로그램이 종료된다.
University > 연세대학교 > 2021 연세대학교 신입생 프로그래밍 경진대회 I번
C++17, C++11, C++14, C++20