시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB255420.000%

문제

There are $N$ ($2 \le N \le 1000$) students in line, name them $s_0, s_1, \cdots, s_{N-1}$ by their order.

For each student, you have to check whether he/she did the homework or not, and you can ask:

  • Q1 defined as 0 standing for "Have you finished the homework?" or
  • Q2 defined as 1 standing for "Are you late for the homework?".

However, due to the weird culture in the school, if a student has to answer "no" then he/she will hesitate to answer until the class ends. (Of course, you know that this student expressed "no".)

You prepare the questions $q_0, q_1, \cdots, q_{N-1}$ for the students and they will come to answer in order, and you have to wait for their answers.

  • i.e., if $s_0, s_1, \cdots s_{M-1}$ answer YES and $s_M$ expresses "no", then you will only receive $M$ YES's.
  • so if $s_0, s_1, \cdots s_{N-1}$ answer YES then you will receive $N$ YES's.

Here, for the COVID-19 situation, you write the questions on the computer and upload them online and what you receive is a big YES on the monitor. You can only get the sequence of answers.

However, the online system was broken so the questions get arranged by a pre-chosen order $i_0, i_1, \cdots, i_{N-1}$.

  • i.e., if you input $q_0, q_1, \cdots, q_{N-1}$, then the questions will be asked by the order $q_{i_0}, q_{i_1}, \cdots, q_{i_{N-1}}$.

You can have at most $\lceil N + N\log_2 N \rceil$ classes to ask the questions.

Write a function question:

  • input parameter: a Student object containing the information of the students' state and the order
  • $\cdot$.n() returns the number of students; i.e., $N$
    • $\cdot$.ask(Q) returns the list of 'YES'’s (need not be a length of $N$) based on the question list Q
      • input parameter: a list of length $N$, consisting of Q1 and Q2
      • return value: ['YES' for j in range($M$)] where $M$ is the number of YES's: i.e., $M = \max\{m \le N \,\vert\, j < m \Longrightarrow s_j \textrm{ answers } $YES$\textrm{ on } $Q[$i_j$]$\}$
  • output: the list of input questions $q_0, q_1, \cdots, q_{N-1}$ that gets $N$ YES's and the order $i_0, i_1, \cdots, i_{N-1}$
    • in the order that you need to input to computer, and the order that $q_i$ is asked, respectively.

Assume every student either finished or was late for the homework, and the states do not change as the classes proceed.

Caution: The protected attributes in Student are named differently in the judging code.

첨부

출처

High School > 한국과학영재학교 > 2021 Fall PPS Final Mock Exam 5번

제출할 수 있는 언어

PyPy3

채점 및 기타 정보

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