| Fişierul intrare/ieşire: | shopping.in, shopping.out | Sursă | Concurs Shumen juniori 2017 |
| Autor | Autor Necunoscut | Adăugată de |  Spatarel Dan-Constantin •spatarel |
| Timp execuţie pe test | 3 sec | Limită de memorie | 32768 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Shopping
Ieri a fost ziua de naştere a lui Deni şi a primit o mulţime de cadouri de la mai mulţi prieteni. Se poate considera că datorită cadourilor ea are un număr nelimitat de produse care sunt de asemenea disponibile şi la Mall. Deni decide să vândă o parte dintre ele pentru a obţine bani. Cu aceşti bani ea va merge la cumpărături în Mall cu prietenii dar va cumpăra numai produse diferite de cele pe care le-a vândut. Deni vrea sa obţină o anumită sumă de bani în final. Dacă aceasta se poate realiza doar vânzând o parte dintre cadouri, atunci ea va amâna cumpărăturile pentru altă dată. Deoarece are o mulţime de produse de diferite preţuri, îi este greu sa decidă ce tipuri de produse să vândă şi ce tipuri să cumpere, asa încât la final să aibă suma de bani pe care şi-o doreşte.
Presupunem că există k produse în magazin, care au preţurile a1, a2, a3, ..., ak leve (moneda naţională a Bulgariei) şi că fata doreşte să ramână la final cu exact n leve. Trebuie să afişaţi de câte ori ea trebuie să cumpere sau să vândă fiecare tip de produs (cumpărarea este marcată ca număr negativ şi vânzarea ca număr pozitiv) astfel încât Deni să obţină în final n leve. Programul vostru va rezolva t teste la o rulare. Deoarece numere din fişierul de ieşire pot fi foarte mari, fiecare număr va fi afişat ca produs a cel mult 100 de numere. Dacă există mai multe soluţii, veţi afişa oricare dintre ele. Dacă nu există soluţie, veţi afişa textul "No solutions" (fără ghilimele).
Date de intrare
Fişierul de intrare shopping.in conţine pe prima linie un singur număr t care reprezintă numărul de teste pe care îl va procesa programul. Fiecare test este descris pe 3 linii. Prima linie va conţine numărul natural k, a doua linie va conţine numere naturale a1, a2, a3, ..., ak reprezentând preţurile tipurilor de produse din Mall în leva. A treia linie conţine numărul natural n reprezentând câte leve doreşte să obţină Deni la final.
Date de ieşire
În fişierul de ieşire shopping.out se va afişa texul "No solutions" (fără ghilimele) dacă problema nu are soluţie sau, în cazul în care problema are soluţie, k numere întregi (fiecare dintre acestea trebuie să fie afişate sub forma num1 * num2 * ... * nump) care descriu de câte ori Dani a cumpărat sau a vândut un produs (dacă numărul este negativ atunci ea a cumpărat acel tip de produs iar dacă este pozitiv atunci l-a vândut).
Restricţii
- 1 ≤ t ≤ 2
- 2 ≤ k ≤ 100 000
- 1 ≤ a1, a2, a3, ..., ak ≤ 1018
- 1 ≤ n ≤ 1018
- 1 ≤ p ≤ 100
- -109 ≤ num1 ≤ 109
- 0 ≤ numi ≤ 109 pentru 2 ≤ i ≤ p
| Subtask | Puncte | k | Observaţii |
|---|---|---|---|
| 1 | 10 | k = 2 | Petru fiecare test t = 1. |
| 2 | 20 | k = 3 | Pentru fiecare test t = 1. |
| 3 | 10 | 4 ≤ k ≤ 1000 | Există printre numerele a1, a2, a3, ..., ak cel puţin două numere relativ prime (adică singurul întreg pozitiv care le divide pe ambele este 1). Pentru fiecare test t = 2. |
| 4 | 60 | 4 ≤ k ≤ 105 | Pentru fiecare test t = 2. |
Exemple
| shopping.in | shopping.out | Explicaţii |
|---|---|---|
| 1 2 3 5 11 | 2 1 | Dacă Deni vinde primul tip de produs de două ori şi al doilea produs o dată atunci ea obţine 2 ∗ 3 + 1 * 5 = 11 leve, care este exact suma dorită. Observaţi că ar fi putut deasemenea să vândă de 7 ori produsul de tip 1 şi sa cumpere de două ori produsul de tip 2 obţinând deasemenea o soluţie validă. |
| 1 4 30 42 70 105 413 | 7 -3 * 3 5 -1 * 5 | În acest exemplu (există de asemenea şi alte posibilităţi) suma obţinută de Deni va fi: 7 ∗ 30 + 9 ∗ 42 + 5 ∗ 70 - 5 ∗ 105 = = 210 + 378 + 350 - 525 = 413 leve. Al doilea număr este 9 (reprezentat ca 3 * 3 = 9) şi al patrulea număr este -5 (reprezentat ca -1 * 5 = 5). |
