Fişierul intrare/ieşire:fatkins.in, fatkins.outSursăad-hoc
AutorAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.150 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Fatkins

Ion s-a apucat să ţină dieta Fatkins, o dietă miraculoasă bazată pe bomboane. În fiecare zi timp de Q zile, Ion primeşte la uşă câte o cutie cu bomboane. În fiecare cutie se află N bomboane şi fiecare bomboană este etichetată cu numărul de calorii pe care îl conţine. Toate cutiile conţin acelaşi set de bomboane. Dar Ion nu are voie să mănânce toate bomboanele! În ziua i, Ion primeşte un număr Ki. Considerând toate cele 2N submulţimi de bomboane, ordonate după conţinutul caloric, Ion trebuie să mănânce submulţimea cu numărul de ordine Ki.

Dându-se N, Q, conţinutul caloric al celor N bomboane şi valorile pentru Ki, determinaţi câte calorii mănâncă Ion în fiecare zi.

Date de intrare

Fişierul de intrare fatkins.in conţine

  • pe prima linie numerele N şi Q;
  • pe a doua linie apar numerele naturale pozitive C1, C2, ..., CN, reprezentând numărul de calorii din fiecare bomboană;
  • pe următoarele Q linii numerele naturale K1, K2, ..., KQ, câte unul pe linie.

Date de ieşire

În fişierul de ieşire fatkins.out se vor tipări Q numere, câte unul pe linie, reprezentând caloriile consumate de Ion în fiecare zi. Răspunsurile vor avea aceeaşi ordine cu întrebările.

Restricţii

  • 1 ≤ N ≤ 100
  • 1 ≤ Q ≤ 1.000
  • 1 ≤ Ki ≤ min(2N, 100.000) pentru 1 ≤ i ≤ Q
  • 1 ≤ Ci pentru 1 ≤ i ≤ N
  • C1 + C2 + ... + CN ≤ 1.000.000.000
  • Pentru 20% din teste, 1 ≤ N ≤ 16 şi 1 ≤ Ki ≤ 10.000
  • Pentru alte 30% din teste, 1 ≤ N ≤ 30 şi 1 ≤ Ki ≤ 20.000

Exemplu

fatkins.infatkins.out
4 3
7 2 6 4
6
1
15
7
0
17

Explicaţie

Cele 16 submulţimi sunt, în ordine:

numărbomboanetotal calorii
1niciuna0
222
344
466
52, 46
677
72, 68
82, 79
94, 610
104, 711
112, 4, 612
122, 4, 713
136, 713
142, 6, 715
154, 6, 717
162, 4, 6, 719
Trebuie sa te autentifici pentru a trimite solutii. Click aici