Loading...
Loading...
Loading...
Three colleagues at an online store have exactly B rupees in total, and each wants one item from the catalogue. The three items must be three different catalogue entries, but two entries may have the same price. Print every different set of three prices whose total is exactly B. Each set must appear once, even if several menu entries give the same prices.
a b c with a ≤ b ≤ c. Order the lines by a, then by b. If no set exists, print NONE.Example 1
Input
6 100 20 50 30 10 40 60
Output
10 30 60 10 40 50 20 30 50
10 + 30 + 60, 10 + 40 + 50 and 20 + 30 + 50 all make 100.
Example 2
Input
5 50 10 10 10 20 20
Output
10 20 20
Several choices of items give 10, 20 and 20, but the set is printed once.
Try the problem first. Open one hint at a time.
Sort the prices first. Then fix the smallest price of the set, a[i], and look for two more prices to its right.
For a fixed i, put one index just after i and one at the end. If the total is too small, move the left one right. If it is too big, move the right one left.
When the total is exactly B, record the set and move both indexes, skipping prices equal to the ones just used.
Also skip an i whose price equals the previous a[i], otherwise the same sets are found again.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor