Magic Trick

시간 제한2초메모리 제한2048 MB

요약
한 사람이 순열에서 K장의 카드를 뒤집어 숨기면 다른 사람이 숨긴 값을 모두 알아내는 전략을 설계하고 K를 최대화한다.
난이도

어려움10점 중 8점

유형
조합론, 수학, 구현
정답자
아직 제출이 없습니다

문제

Alicia and Beatriz are preparing a magic trick for the IOI Talent Show. The trick works as follows:

  • A volunteer selects a permutation PP of length NN and places NN cards on the table. The cards are numbered from 00 to N−1N − 1, with card ii displaying the value P\[i]P\[i].
  • Alicia enters the room, observes the cards, and selects KK of them to flip face down, hiding their values.
  • Beatriz then enters the room, sees the current arrangement of the cards (including which ones are face down), and magically determines the values of all KK hidden cards!

Your task is to devise and implement a strategy for Alicia and Beatriz. The more impressive the trick, the better your score: the objective is to maximize KK, the number of hidden cards Beatriz can correctly reveal.

제한

  • N=256N = 256
  • 1≤P\[i]≤N1 ≤ P\[i] ≤ N for each ii such that 0≤i<N0 ≤ i < N.
  • All values in PP are distinct.

예제

이 문제는 공개된 예제가 없습니다.