2091D.md (2103B)
1 Source: https://codeforces.com/problemset/problem/2091/D 2 3 D. Place of the Olympiad 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 For the final of the first Olympiad by IT Campus "NEIMARK", a rectangular venue was prepared. You may assume that the venue is divided into $n$ rows, each containing $m$ spots for participants' desks. A total of $k$ participants have registered for the final, and each participant will sit at an individual desk. Now, the organizing committee must choose the locations for the desks in the venue. 22 23 Each desk occupies one of the $m$ spots in a row. Moreover, if several desks occupy consecutive spots in the same row, we call such a group of desks a bench, and the number of desks in the group is the bench's length. For example, seating $7$ participants on a $3 \times 4$ venue (with $n = 3, m = 4$) can be arranged as follows: 24 25  26 27 In the figure above, the first row has one bench of length $3$, the second row has one bench of length $2$, and the third row has two benches of length $1$. 28 29 The organizing committee wants to choose the locations so that the length of the longest bench is as small as possible. In particular, the same $7$ desks can be arranged in a more optimal way, so that the lengths of all benches do not exceed $2$: 30 31  32 33 Given the integers $n$, $m$, and $k$, determine the minimum possible length of the longest bench. 34 35 Input 36 37 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). The description of the test cases follows. 38 39 A single line of each test case contains three positive integers — $n$, $m$, $k$ ($1 \leq n, m, k \leq 10^9$, $k \leq n\cdot m$). 40 41 Output 42 43 For each test case, output a single number — the minimum possible length of the longest bench. 44 45 Example 46 47 Input 48 49 ``` 50 5 51 52 3 4 7 53 54 5 5 5 55 56 1 13 2 57 58 2 4 7 59 60 1 5 4 61 ``` 62 63 Output 64 65 ``` 66 2 67 1 68 1 69 4 70 2 71 ```