3 posts tagged with "Binary Search"

Question description​

There are $N$ classes in the ABC competitive programming school, and class number $i$ ($1 \leq i \leq N$) targets students with a rating of $A_i$.

Now, $Q$ students are about to join this school. The rating of student number $j$ ($1 \leq j \leq Q$) is $B_j$. Each student will be dissatisfied if they go to a class that does not match their level. The dissatisfaction for each student is defined as follows:

The absolute difference between the target rating $a$ and their own rating $b$, that is, $|a - b|$.

For $j = 1, 2, 3, \dots, Q$, find the minimum dissatisfaction that can be considered for student number $j$. It is allowed to have classes with no students or classes with multiple students.

Question description​

Output all correct bracket sequences of length $N$ in lexicographic order.

A correct bracket sequence is defined as follows:

• () is a correct bracket sequence.
• When $S$ is a correct bracket sequence, the string ( + $S$ + ) is a correct bracket sequence.
• When $S$ and $T$ are correct bracket sequences, the string $S$ + $T$ is a correct bracket sequence.
• All other strings are not correct bracket sequences.

Problem description​

There is a Yokan of length $L$ [cm]. There are $N$ cutting points, and the $i$-th cutting point from the left is at position $A_i$ [cm] from the left.

You want to choose $K$ of the $N$ cutting points and divide the Yokan into $K+1$ pieces. Then, the following value is used as the score:

• The length of the shortest piece among the $K+1$ pieces

Find the score that can be obtained when dividing the Yokan to maximize the score.