Diferențe pentru problema/shopping între reviziile #47 si #54

Diferențe între titluri:

shopping
Shopping

Diferențe între conținut:

== include(page="template/taskheader" task_id="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 si 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 in 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 in 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ă si ce tipuri să cumpere, asa incat la final va avea suma de bani pe care si-o doreste.
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  aibă suma de bani pe care și-o dorește.
Presupunem că există $k$ produse in magazin, care au prețurile $a[~1~],a[~2~], a[~3~],.....,a[~k~]$ leva (moneda Bulgara), respectiv că fata dorește să ramână la final cu exact $n$ leve. Trebuie sa afișați de câte ori ea trebuie sa cumpere sau să vânda fiecare tip de produs (cumpărarea este marcată ca număr negativ si vânzarea ca număr pozitiv ), astfel încât Deni să obțină in final $n$ leva. Programul vostru va rezolva $t$ teste la o rulare. Deoarece numere din output 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 din ele. Dacă nu există soluție, veți printa textul No solutions (fără ghilimele).
Presupunem că există $k$ produse în magazin, care au prețurile $a[~1~], a[~2~], a[~3~], ..., a[~k~]$ 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).
h2. Date de intrare
Fișierul de intrare $shopping.in$ conține pe prima linie este 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 $a[~1~],a[~2~], a[~3~],.....,a[~k~]$ reprezentând prețurile tipurilor de produse din Mall. A treia linie conține numărul natural $n$ -ți leva dorește să obțină Deni la final.
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 $a[~1~], a[~2~], a[~3~], ..., a[~k~]$ reprezentând prețurile tipurilor de produse din Mall în leva. A treia linie conține numărul natural $n$ reprezentândte leve dorește să obțină Deni la final.
h2. 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 num[~1~] * num[~2~] *...* num[~p~])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).
 
Î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 $num[~1~] * num[~2~] * ... * num[~p~]$) 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).
h2. Restricții
* $1 ≤ t ≤ 2$
* $2 ≤ k ≤ 100000$
* $1 ≤ a[~1~],a[~2~], a[~3~],.....,a[~k~]  ≤ 10[^18^]$
* $2 ≤ k ≤ 100 000$
* $1 ≤ a[~1~], a[~2~], a[~3~], ..., a[~k~] ≤ 10[^18^]$
* $1 ≤ n ≤ 10[^18^]$
* $1 ≤ p ≤ 100$
* $-10[^9^] ≤ num[~1~] ≤ 10[^9^]$
* $0 ≤ num[~i~] ≤ 10[^9^]$
* $2 ≤ i ≤ p$
* $0 ≤ num[~i~] ≤ 10[^9^]$ pentru $2 ≤ i ≤ p$
table(example).
|_. Subtask |_. Puncte |_. k |_. Observații|
| 3
| 10
| 4 ≤ k ≤ 1000
| Există printre numerele a[~1~],a[~2~], a[~3~],.....,a[~k~] cel puțin două numere relativ prime (adică singurul întreg pozitiv care le divide pe ambele este 1).
 Pentru fiecare test t = 2.
| Există printre numerele a[~1~], a[~2~], a[~3~], ..., a[~k~]
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
5
11
| 2 1
| Dacă Deni vinde primul tip de produs de două ori și și al doilea produs o dată atunci ea obține 2 ∗ 3 + 5 = 11 leva 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ă.
| 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
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
lev
a
.
Al doilea număr este
9 (
reprezentat
ca
3
*3=9)
și al patrulea num
ăr este
─5
(
reprezentat
ca
─
1
*5=5).
| 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).
|
== include(page="template/taskfooter" task_id="shopping") ==

Nu există diferențe între securitate.