codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1877C.md (2368B)


      1 Source: https://codeforces.com/problemset/problem/1877/C
      2 
      3 C. Joyboard
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Chaneka, a gamer kid, invented a new gaming controller called joyboard. Interestingly, the joyboard she invented can only be used to play one game.
     22 
     23 The joyboard has a screen containing $n+1$ slots numbered from $1$ to $n+1$ from left to right. The $n+1$ slots are going to be filled with an array of non-negative integers $[a_1,a_2,a_3,\ldots,a_{n+1}]$. Chaneka, as the player, must assign $a_{n+1}$ with an integer between $0$ and $m$ inclusive. Then, for each $i$ from $n$ to $1$, the value of $a_i$ will be equal to the remainder of dividing $a_{i+1}$ (the adjacent value to the right) by $i$. In other words, $a_i = a_{i + 1} \bmod i$.
     24 
     25 Chaneka wants it such that after every slot is assigned with an integer, there are exactly $k$ distinct values in the entire screen (among all $n+1$ slots). How many valid ways are there for assigning a non-negative integer into slot $n+1$?
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 2\cdot10^4$) — the number of test cases. The following lines contain the description of each test case.
     30 
     31 The only line of each test case contains three integers $n$, $m$, and $k$ ($1 \leq n \leq 10^9$; $0 \leq m \leq 10^9$; $1 \leq k \leq n+1$) — there are $n+1$ slots, the integer assigned in slot $n+1$ must not be bigger than $m$, and there should be exactly $k$ distinct values.
     32 
     33 Output
     34 
     35 For each test case, output a line containing an integer representing the number of valid ways for assigning a non-negative integer into slot $n+1$.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 4
     43 
     44 4 6 3
     45 
     46 2 0 1
     47 
     48 265 265 265
     49 
     50 3 10 2
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 2
     57 1
     58 0
     59 5
     60 ```
     61 
     62 Note
     63 
     64 In the first test case, one of the $2$ possible ways for Chaneka is to choose $a_{n+1}=6$. If she does that, then:
     65 
     66 * $a_4=a_5\bmod 4=6\bmod 4=2$
     67 * $a_3=a_4\bmod 3=2\bmod 3=2$
     68 * $a_2=a_3\bmod 2=2\bmod 2=0$
     69 * $a_1=a_2\bmod 1=0\bmod 1=0$
     70 * $a = [0, 0, 2, 2, 6]$
     71 * There are $3$ distinct values.
     72 
     73 In the second test case, the $1$ possible way for Chaneka is to choose $a_{n+1}=0$. If she does that, then $a = [0, 0, 0]$. There is only $1$ distinct value.
     74 
     75 In the third test case, there is no possible way for assigning a non-negative integer into slot $n+1$.