
ZOJ Problem Set  4047
DreamGrid is playing the music game Live Love. He has just finished a song consisting of $n$ notes and got a result sequence $A_1, A_2, \dots, A_n$ ($A_i \in$ {PERFECT, NONPERFECT}). The score of the song is equal to the \textit{maxcombo} of the result sequence, which is defined as the maximum number of continuous PERFECTs in the sequence. Formally speaking, $\text{maxcombo}(A) = \max$ {$k$  $k$ is an integer and there exists an integer $i$ ($1 \le i \le nk+1$) such that $A_i = A_{i+1} = A_{i+2} = \dots = A_{i+k1} = $ PERFECT}. For completeness, we define max($\emptyset$) = 0. As DreamGrid is forgetful, he forgets the result sequence immediately after finishing the song. All he knows is the sequence length $n$ and the total number of PERFECTs in the sequence, indicated by $m$. Any possible score $s$ he may get must satisfy that there exists a sequence $A'$ of length $n$ containing exactly $m$ PERFECTs and $(nm)$ NONPERFECTs and $\text{maxcombo}(A') = s$. Now he needs your help to find the maximum and minimum $s$ among all possible scores. InputThere are multiple test cases. The first line of the input contains an integer $T$($1 \le T \le 100$), indicating the number of test cases. For each test case: The only line contains two integers $n$ and $m$ ($1 \le n \le 10^3$, $0 \le m \le 10^3$, $m \le n$), indicating the sequence length and the number of PERFECTs DreamGrid gets. OutputFor each test case output one line containing two integers $s_{max}$ and $s_{min}$, indicating the maximum and minimum possible score. Sample Input5 5 4 100 50 252 52 3 0 10 10 Sample Output4 2 50 1 52 1 0 0 10 10 HintLet's indicate a PERFECT as $P$ and a NONPERFECT as $N$. For the first sample test case, the sequence $(P,P,P,P,N)$ leads to the maximum score and the sequence $(P,P,N,P,P)$ leads to the minimum score. Author: CHEN, Shihan Source: The 2018 ACMICPC Asia Qingdao Regional Contest, Online 