Rubber Duck Lovers Club
InterviewTime limit1sMemory limit512 MB
Pick exactly P of N members and assign each a value in [xi, yi] so the P values sum to E, or report that this is impossible.
- Level
Medium6 of 10
- Topics
- Greedy, Backtracking, Implementation, Math
- Solved
- No attempts yet
Problem
Dayoung recently joined the Rubber Duck Lovers Club (hereafter the Club). Dayoung has E rubber duck dolls, and to celebrate joining, she wants to give rubber duck dolls to the Club members.
After asking the Club president to investigate, Dayoung learned that, excluding Dayoung herself, there are N Club members, and each Club member i accepts only between xi and yi dolls inclusive. Dayoung finds it cheeky that the Club members attach conditions to receiving rubber duck dolls, so she will give dolls only if she gives to exactly P members and the total number of rubber duck dolls she gives them is E. Can Dayoung give out the dolls?
Input
The first line gives the integers N, P, and E, separated by spaces. (1 ≤ N, P ≤ 20, 1 ≤ E ≤ 1,000,000)
From the next line, N lines follow, giving xi and yi for members 1 through N in order, separated by spaces. (1 ≤ xi ≤ yi ≤ 1,000,000)
Output
If Dayoung can give out the dolls, print on the first line the number of dolls she gives to each member i, for members 1 through N in order, separated by spaces. If there are multiple valid ways, print any one of them.
If she cannot give out the dolls under any circumstances, print -1.