Toy store profits

Question

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

Answer 1

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.

Answer 2

Haskell, 67 bytes

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).

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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)]:[]

Another clone of @CAD97's answer.