Historia

„2016? W porządku…” - narzekał sprzedawca zabawek Hilbert. Otworzył oczy, wytarł z ucha ściekający sos sałatkowy i zjadł cremeschnitte rano. Przykładowe wakacje. Teraz jednak musi iść do pracy i dokończyć księgowość roku.

Boże Narodzenie to bardzo owocny okres roku, szczególnie ze względu na sprzedaż. Hilbert wie dokładnie, jak to działa: osoba wchodzi do sklepu i kupuje jej pierwszy prezent. Płacą za to i uciekają do innego sklepu. W praktyce to, czym tak naprawdę jest prezent, tak naprawdę nie robi różnicy. Cena jest również nieistotna, pod warunkiem że nie jest zbyt wysoka. Wszystko zależy od czasu pozostałego do Bożego Narodzenia - im krótszy czas, tym większe wyrzuty sumienia klientów, tym wyższa cena, jaką są skłonni zapłacić.

Wystarczy spojrzeć na zegarek - Hilbert i od razu wie, ile mogą wydać jego klienci. Może z łatwością skorzystać z tego faktu: po prostu znajduje najdroższy prezent, który może sprzedać danemu klientowi i mu go zaoferować. Dopiero teraz zdał sobie sprawę, że w ubiegłym roku zapomniał zastosować tę przebiegłą strategię. To się jednak zmieni!

Niemniej jednak Hilbert chciałby wiedzieć, jak bardzo rozkwitłby jego interes, gdyby rzeczywiście wykorzystał swój wielki plan. Udało mu się zebrać listę osób, które przyszły do ​​jego sklepu, jednak nie jest pewien, ile pieniędzy mógł na nich zarobić.

Twoje zadanie (TL; DR)

Wejście składa się z rosnąco listę cen dostępnych prezentów oraz listę budżetów klientów. Lista budżetów jest w tej samej kolejności, w jakiej klienci przybyli do sklepu - pod warunkiem, że każdy klient jest skłonny zapłacić co najmniej tyle, co poprzedni, co oznacza, że ​​również rośnie.

Dla każdego klienta znajdź najdroższy prezent, za który jest gotów zapłacić, i wydrukuj jego cenę. Jeśli żadne prezenty w ramach budżetu nie są dostępne, należy wyprowadzić wynik 0.

Otrzymasz -40%premię dla postaci, jeśli asymptotyczna złożoność czasowa twojego algorytmu jest O(n+m)(a nie trywialna O(n*m)) _{Gdzie n, msą długości list wejściowych.}

To jest golf golfowy , wygrywa najkrótsza bajt. Standardowe luki są zabronione.

Przykład

Wejście:

1 2 2 2 5 7 10 20
1 1 2 3 6 6 15 21 21 22

Wynik:

1 0 2 2 5 2 10 20 7 0

_{To zadanie zostało wzięte z lokalnego konkursu programistycznego i przetłumaczone przeze mnie na język angielski. Oto oryginalne zadanie: https://www.ksp.sk/ulohy/zadania/1131/}

Pyth, 17 16 bajtów

1 bajt dzięki Pietu1998

VE=.-Q]
e|fgNTQ0

Demonstracja

Wyjaśnienie:

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.

Haskell, 67 bajtów

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

Przykład użycia: [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].

Podziel ceny na dwie części: (h,t)gdzie hwszystkie ceny <= budżet następnego klienta i twszystkie pozostałe. Weź ostatnią cenę hi kontynuuj rekurencyjnie ze wszystkimi oprócz ostatniego hplusa ti pozostałych budżetów. last(0:h)ocenia, 0czy hjest pusty. Podobne: init (h++[0|h==[]]) ++ tdodaje element fikcyjny 0do hif hjest pusty, więc initma coś do upuszczenia ( initnie działa na pustej liście).

Java, 154 * 0,6 = 92,4 bajtów

-13 bajtów, ponieważ lambda może faktycznie użyć int[], nie Integer[](dzięki BunjiquoBianco )

Powinno to zająć czas O (n + m) i dodatkową przestrzeń O (n + m) _{^{(zakładając, że rozumiem dużą notację O)}} .

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

Wcięte: ( Wypróbuj 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})
        ));
}

_{^{Pokazuję tutaj rozszerzenie inne niż lambda, ponieważ deklaracja typu jest czystsza i ma dokładnie taką samą logikę. Lambda jest obecna na łączu ideonu.}}

Wyjaśnienie:

Zastosowane zmienne:

• gto lista cen prezentów, bto lista budżetów.
• gljest długością gi bljest długością b.
• ato stos niedrogich prezentów, sto tablica wyników sprzedanych prezentów.
• gp, bpI apsą wskaźnikami dla g, bi aodpowiednio. bpjest również wskaźnikiem dla s.

Algorytm:

• Dla każdego budżetu w długości budżetów
  • Podczas gdy ten budżet można kupić prezent na g[gp]
    • Wepchnij budżet na stos ai zwiększajgp
  • Wciśnij górną część, jeśli istnieje, aw przeciwnym s[bp]razie 0.

Haskell, 87 * 0,6 = 52,2 bajtów

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

Zupełnie różni się od mojej innej odpowiedzi , ponieważ idę po premię.

Ostatni wiersz (-> g[]) nie jest częścią definicji, ale wywołuje narzut. Przykład użycia: 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].

Działa w zasadzie w taki sam sposób, jak odpowiedź @ CAD97 , tzn. Używa (początkowo pustego) stosu pomocników do śledzenia przedmiotów do kupienia. Szczegółowo: sprawdź w kolejności:

• jeśli pierwsza cena jest mniejsza lub równa od pierwszego budżetu, przenieś cenę na stos. Zadzwoń ponownie.
• jeśli stos jest pusty, zwróć 0, a następnie wywołanie rekurencyjne z obniżonym budżetem.
• jeśli zarówno stos, jak i lista budżetu nie są puste, zwróć górę stosu, a następnie wywołanie rekurencyjne z wyskakującym stosem i budżetem.
• w przeciwnym razie zwróci pustą listę.

Działa to w m+nczasie, ponieważ a) operacje na stosie pomocniczym używają stałego czasu ib) w każdym z wywołań rekurencyjnych jedna z list jest skracana o jeden element.

Galaretka , 15 bajtów

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

Wypróbuj online!

Jak to działa

ṀṄ;©®œ^  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 bajtów

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

Kolejny klon odpowiedzi @ CAD97.