Telejump
Time limit1sMemory limit128 MB
Given a type-1 jumps, b type-2 jumps, and c type-3 jumps with n = a+b+c+1, output a route visiting planets 0 through n-1 exactly once using every ticket exactly once.
- Level
Medium6 of 10
- Topics
- Greedy, Implementation, Math
- Solved
- No attempts yet
Problem
Hongjun and friends plan to visit planets numbered through . They teleport with the Telejump system co-developed by Sasung and Boogle, starting at planet and ending anywhere.
Three ticket types are available.
- Type 1: move from to or when inside the range
- Type 2: move from to or when inside the range
- Type 3: move from to or when inside the range
They hold type-1 tickets, type-2 tickets, and type-3 tickets, with . Each count is at least , so .
Output a visit order that uses every planet exactly once and every ticket exactly once.
Input
The first line contains (), the number of test cases.
Each test case is one line with three integers , , and (). For that case, .
Output
For each test case, print one line with planet numbers separated by spaces. The route must start at planet .
If multiple routes are valid, print any of them. Every input is guaranteed to be solvable.
Hint
Use length-3 jumps to cover large gaps, then spend the remaining type-1 and type-2 tickets on unvisited planets. When , a repeating three-ticket pattern visits the whole line in order.