Ticket Line
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
n people stand in a line at a ticket booth; person 0 is at the front and person i wants tickets[i] tickets. Every
second the booth sells one ticket to the person at the front. That person then goes to the back of the line if they
still need more, or leaves otherwise (moving takes no time). Return how many seconds pass until person k has bought all
of their tickets.
Examples
| tickets | k | result |
|---|---|---|
[2, 3, 2] | 2 | 6 |
[5, 1, 1, 1] | 0 | 8 |
[1] | 0 | 1 |
Example 2 — person 0 buys one ticket, the other three buy one each and leave, then person 0 buys the remaining four: 8 seconds.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(tickets: int[], k: int) → long
Constraints
-
tickets.length -
tickets[i] -
ktickets.length - The answer may exceed the 32-bit range.
Expected complexity
- Time
- O(N)
- Space
- O(1)
Examples
| tickets | k | Expected |
|---|---|---|
[2,3,2] | 2 | 6 |
[5,1,1,1] | 0 | 8 |
[1] | 0 | 1 |
Hint
Hint
The line moves in rounds, and person k finishes in round tickets[k]. Up to then, everyone at or before k buys
min(tickets[i], tickets[k]) tickets and everyone after k buys min(tickets[i], tickets[k] - 1), one second per ticket;
the sum is the answer, in . Simulating second by second takes as many steps as the answer (up to about ) and
exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 3 | verdict only |