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.

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 , 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/

• Bonuses are one thing to avoid when writing challenges. However, I think it might be fine here. If you want to keep it, I recommend changing it to a percentace based bonus. A 20 character bonus doesn't mean anything to a Java submission, but is basically mandatory for solutions in a golfing language. Commented Mar 28, 2016 at 21:16
• Can I award a bounty to OP for the backstory alone? Honestly, that made me smile; every challenge needs one of those.
– cat
Commented Mar 29, 2016 at 1:53
• @tac Thanks, but as is noted in the small text at the bottom, I didn't actually make up the backstory - I only translated it. Commented Mar 29, 2016 at 6:59
• @sammko yes, I saw that, but my above comment still holds :)
– cat
Commented Mar 29, 2016 at 13:03

Pyth, 17 16 bytes

1 byte thanks to Pietu1998

VE=.-Q]
e|fgNTQ0


Demonstration

Explanation:

VE=.-Q]<\n>e|fgNTQ0
Implicit: Q is the list of prices.
VE                      For N in the list of budgets
f   Q      Filter the list of prices
gNT       On the current person's budget being >= that price
|     0     If there aren't any, use 0 instead.
e             Take the last (most expensive) value.
<\n>              Print it out.
=.-Q                  Remove it from the list of prices.

• I think you can save 1 byte with VE=.-Q]\ne|fgNTQ0. Basically the same thing but with a loop. Commented Mar 30, 2016 at 8:57

a#(b:c)|(h,t)<-span(<=b)a=last(0:h):(init(h++[0|h==[]])++t)#c
_#x=x


Usage example: [1,2,2,2,5,7,10,20] # [1,1,2,3,6,6,15,21,21,22] -> [1,0,2,2,5,2,10,20,7,0].

Split the prices in two parts: (h,t) where h are all prices <= the budget of the next customer and t are all the others. Take the last price of h and continue recursively with all but the last of h plus t and the remaining budgets. last(0:h) evaluates to 0 if h is empty. Similar: init (h++[0|h==[]]) ++ t adds a dummy element 0 to h if h is empty, so that init has something to drop (init fails on the empty list).

Java, 154 * 0.6 = 92.4 bytes

-13 bytes because the lambda can actually use int[], not Integer[] (thanks BunjiquoBianco)

This should take O(n+m) time and O(n+m) additional space (assuming I understand big O notation).

g->b->{int l=g.length,L=b.length,G=0,B=0,A=0;int[]a=new int[l],s=new int[L];for(;B<L;){while(G<l&&g[G]<=b[B])a[A++]=g[G++];s[B++]=A>0?a[--A]:0;}return s;}


Indented: (Try it online!)

static int[] toyStore(int[]g,int[]b) {
int gl=g.length,bl=b.length,gp=0,bp=0,ap=0;
int[] a=new int[gl],s=new int[bl];
for (;bp<bl;) {
while(gp<gl&&g[gp]<=b[bp])a[ap++]=g[gp++];
s[bp++]=ap>0?a[--ap]:0;
}
return s;
}

public static void main(String[] args)
{
System.out.println(Arrays.toString(
toyStore(new int[] {1,2,2,2,5,7,10,20},
new int[] {1,1,2,3,6,6,15,21,21,22})
));
}


I show the non-lambda expansion here because the type declaration is cleaner and it's the exact same logic. The lambda is present at the ideone link.

Explanation:

Variables used:

• g is the list of gift prices, b is the list of budgets.
• gl is the length of g and bl is the length of b.
• a is a Stack for affordable gifts, s is the output array of sold gifts.
• gp, bp, and ap are pointers for g, b, and a respectively. bp is also the pointer for s.

Algorithm:

• For each budget in the length of budgets
• While this budget can buy the gift at g[gp]
• Push the budget onto the Stack a and increment gp
• Pop the top of a into s[bp] if it exists, else put 0.
• Can't you curry the lambda? (i.e. (g,b)-> to g->b->? Commented Mar 28, 2016 at 23:35
• @somebody apparently, yes. For some reason it's never worked for me before but now it will. 0.o (You saved 0.6 bytes after the bonus.) Commented Mar 28, 2016 at 23:38
• You can save some bytes by using longs if the input is assumed to be long[] (takes you to 158bytes) - ideone.com/invHlc Commented Mar 29, 2016 at 8:55
• @BunjiquoBianco in fact I can just use int[]. For some reason I was under the impression that since the type arguments take reference types (thus not the value-typed primitives like int) that I needed to use a array of reference types. But I can use an array of int just fine. I'll update once I get a chance. Commented Mar 29, 2016 at 14:32
• @CAD97 Ha! Can't believe I didn't make that link... Commented Mar 29, 2016 at 16:09

Haskell, 87 * 0.6 = 52.2 bytes

g s(p:q)d@(b:c)|p<=b=g(p:s)q d
g[]p(b:c)=0:g[]p c
g(s:t)p(b:c)=s:g t p c
g _ _ _=[]
g[]


Completely different from my other answer, because I'm going for the bonus.

The last line (-> g[]) is not part of the definition, but calling overhead. Usage example: g [] [1,2,2,2,5,7,10,20] [1,1,2,3,6,6,15,21,21,22] -> [1,0,2,2,5,2,10,20,7,0].

Works basically in the same way as @CAD97's answer, i.e. uses a (initially empty) helper stack to keep track of the buyable items. In detail: check in order:

• if the first price is less or equal than the first budget, move the price to the stack. Call again.
• if the stack is empty, return a 0 followed by a recursive call with the budget dropped.
• if both stack and budget list are not empty, return the top of stack followed by a recursive call with stack & budget popped.
• else return the empty list.

This works in m+n time, because a) operations on the helper stack use constant time and b) in each of the recursive calls one of the lists is shortened by one element.

Jelly, 15 bytes

ṀṄ;©®œ^
Rf@€ç/Ṁ


Try it online!

How it works

ṀṄ;©®œ^  Helper link. Arguments: G, H (lists of affordable gifts)

Ṁ        Compute the maximum of G (0 if the list is empty).
Ṅ       Print it.
; ®    Concatenate it with the register (initially 0).
©     Save the result in the register.
œ^  Compute the multiset symmetric difference of the updated register and H.

Rf@€ç/Ṁ  Main link. Arguments: B (budgets), P (prices)

R        Range; replace each t in B with [1, ..., t].
f@€     Intersect the list of prices with each budget range, obtaining, for each
customer, the list of all gifts he's willing to pay for.
ç/   Reduce the array of lists by the helper link.
In each iteration, this computes and prints the most expensive gift for
a customer, than removes the selected gift (and all previously
selected gifts) from the next list.
Ṁ  Compute the maximum of the resulting list, which corresponds to the last
customer.


JavaScript, 85 * 0.6 = 51 bytes

f=(a,b,s=[],[t,...u]=a,[v,...w]=b)=>v?t<=v?f(u,b,[...s,t]):[s.pop()|0,...f(a),w,s)]:[]