The story
"2016? Al..right," grumbled toy seller Hilbert. He opened his eyes, wiped salad dressing trickling out of his ear and ate a morning kick-start cremeschnitte. Exemplar holidays. He needs to go to work now though, and finish the year's accounting.
Christmas is a very yielding period of the year, especially for his sales. Hilbert knows exactly how it works: A person comes into a shop and buys the first gift they are offered. They pay for it and run off to another shop. In practice, what the gift actually is doesn't really make a difference. The price is also irrelevant, provided it is not too high. It all depends on the time remaining until Christmas -- the shorter the time, the greater the remorse of the customers, the greater the price they are willing to pay.
All it takes for Hilbert is to look at his watch -- and he knows right away how much his customers can spend. He can easily take advantage of this fact: He just finds the most expensive gift he can sell to a given customer, and offer it to them. Only now has he realized that he forgot to employ this cunning strategy last year. That's gonna change though!
Nevertheless, Hilbert would like to know how much his business would have flourished, if he had actually used his grand scheme. He's managed to put together a list of people who came to his store, he is however not sure how much money he could have made on them.
Your task (TL;DR)
The input consists of an ascending list of prices of available gifts, and a list of customers' budgets. The list of budgets is in the same order as the customers arrived to the shop -- with a condition that every customer is willing to pay at least as much as the previous one, meaning it is also ascending.
For each customer, find the most expensive gift they are willing to pay for, and output it's price. If no gifts within the budget are available, output a 0
.
You get a -40%
characters bonus, if the asymptotic time complexity of your algorithm is O(n+m)
(rather than the trivial O(n*m)
) Where n, m
are the lengths of the input lists.
This is code-golf, shortest bytes wins. Standard loopholes are prohibited.
Example
Input:
1 2 2 2 5 7 10 20
1 1 2 3 6 6 15 21 21 22
Output:
1 0 2 2 5 2 10 20 7 0
This task was taken from a local programming competition, and translated to English by me. Here is the original assignment: https://www.ksp.sk/ulohy/zadania/1131/