A logistics coordinator runs two parallel assembly lines that both feed into the same shipment quota. Line X produces exactly A crates every shift it runs, and line Y produces exactly B crates every shift it runs. For a target shipment quota Z, the coordinator wants to know every way to schedule a whole number of shifts x for line X and a whole number of shifts y for line Y — each between 1 and 1000 shifts, inclusive — so that the two lines' combined output lands exactly on Z crates.
Given A, B, and Z, find every pair of integers (x, y) with 1 <= x, y <= 1000 such that A * x + B * y = Z, and report them.
A single line containing three integers A, B, and Z, separated by spaces.
Print an integer k — the number of valid shift-count pairs. Then print k additional lines, each containing two integers x and y (space-separated) describing one valid pair, sorted in strictly increasing order of x. If no valid pair exists, print only the single line 0.
Example 1
Input
1 1 5
Expected
4 1 4 2 3 3 2 4 1
Explanation
Line X and line Y each produce 1 crate per shift, and the quota is 5 crates. Every pair of positive shift counts summing to 5 works, provided both stay within 1..1000: (1,4), (2,3), (3,2), and (4,1). Sorted by increasing x, that gives 4 pairs.
Example 2
Input
3 5 1
Expected
0
Explanation
Even the smallest possible schedule — one shift on each line — already produces 3*1 + 5*1 = 8 crates, which overshoots the target of 1, and no smaller output is possible since both shift counts must be at least 1. So no valid pair exists and the output is just 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →