e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Olympiad in Informatics, II Stage, II Round

I. Козак Вус та скарби

Козак Вус вирішив придбати подарунки своїм друзям. Під час подорожі по магазинах він натрапив на дивну акцію: розв'яжи задачу та отримай безкоштовно будь-який товар. Є $n$ коробок пронумерованих від $1$ до $n$. Вони розташовані по колу, так що коробки $i$ та $i+1$ сусідні для $1 \le i < n$. Також коробки $1$ та $n$ сусідні. У деяких коробках сховані скарби! Також є запити, які можна робити будь-яку кількість разів. Опис запиту: \begin{enumerate} \item Дізнатися парність сумарної кількості скарбів у трьох \textbf{будь-яких різних} коробках; \item Дізнатися парність сумарної кількості скарбів у трьох \textbf{послідовних} коробках. \end{enumerate} Козаку Вусу треба знайти наступне: \begin{enumerate} \item За яку \textbf{мінімальну} кількість запитів типу (1) можна гарантовано дізнатися, чи кількість скарбів парна чи непарна; \item За яку \textbf{мінімальну} кількість запитів типу (2) можна гарантовано дізнатися, чи кількість скарбів парна чи непарна. \end{enumerate} Допоможіть Козаку Вусу якнайшвидше розв'язати цю задачу, бо з кожною хвилиною товарів стає все менше! \InputFile У вхідних даних знаходяться кілька (не менш одного) тестових випадків. Перший рядок містить одне ціле число $T$ ($ 1 \le T \le 10^5 $) --- кількість тестових випадків. Кожен з наступних $T$ рядків містить два цілих числа $n$ та $t$ ($3 \le n \le 10^9, 1 \le t \le 2$). \OutputFile Виведіть $T$ рядків. $i$-ий рядок повинен містити одне ціле число $ans$, де $ans$ --- це відповідь на питання під номером $t$ $i$-го тестового випадку відповідно. \Note У другому тестовому випадку достатньо зробити наступні запити: $\{1, 2, 3\}$, $\{2, 3, 4\}$, $\{3, 4, 1\}$ та $\{4, 1, 2\}$. У третьому тестовому випадку треба зробити такі запити: $\{1, 3, 5\}$, $\{3, 5, 4\}$, $\{3, 5, 2\}$. \Scoring Якщо рішення працює правильно лише при $n=3 \cdot k$, де $k$ --- ціле додатне число, то воно буде оцінюватися у $25$ балів. Якщо рішення працює правильно лише при $t=1$, то воно буде оцінюватися у $25$ балів. Якщо рішення працює правильно лише при $t=2$, то воно буде оцінюватися у $25$ балів.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
5
3 1
4 2
5 1
6 2
8 1
Output example #1
1
4
3
2
4
Author Kostya Denisov