Au mulți băieți și fete în China. Încă ceva băieți. Și chiar mai mult orez.
Recent, însă, sunt din ce în ce mai mulți copii plângători și nefericiți în grădinițele lor. Au început să învețe matematica. În special, până acum au învățat să numere în număr mare și, de asemenea, să se înmulțească și să împartă la doi.
S-ar putea să credeți că au multe teme sau că nu le place matematica. Cu toate acestea, opusul este adevărat. Odată ce au dobândit această nouă superputere, o folosesc în fiecare zi. Mai ales la prânz. Înainte de a începe să mănânce, fiecare își numără boabele de orez. 1
Când toată lumea și-a numărat orezul, începe a doua fază a prânzului. Comparaţie. Dacă cineva află că are de două ori mai multe cereale decât un coleg de clasă, are dreptul să fie promovat și ridiculizat. Apoi urmează plânsul sau un băiat sau o fată rănită găsește pe cineva care are de două ori mai mult orez. Copiii sunt uneori cruzi.
Educatorii sunt fără idei. Nu au experimentat niciodată atâtea plângeri și înjurături creative, cât au auzit în ultima perioadă. Desigur, procesul de predare sa oprit rapid, dar copiii nu pot fi învățați din ceea ce știu deja.
Prin urmare, ca alternativă, ar dori să ia niște orez copiilor și să le dea tofu. Orezul trebuie luat de la copii, astfel încât să nu existe două creșe \ (x \) și \ (2x \) să aibă boabe de orez. Educatorii își dau seama că nimănui nu îi place tofu 2, așa că ar dori să-l dea cat de putin posibil copii. De asemenea, ar fi interesați de câți copii pot lua cel mai mic număr de farfurii de orez și să distribuie tofu.
Sarcina
\ (N \) porții de orez sunt pregătite pentru prânz. Veți învăța un număr despre fiecare porție - numărul de boabe de orez. Aceste numere sunt aranjate în ordine crescătoare la intrare. Trebuie să luați câteva porții, astfel încât nimeni să nu primească de două ori mai mult orez decât oricine altcineva. Cu alte cuvinte, nu ar trebui să rămână două porțiuni care să aibă boabe \ (x \) și \ (2x \). Încercați să eliminați cât mai puține porțiuni posibil.
Aflați, de asemenea, câte porțiuni pot fi eliminate pentru a îndeplini cerințele anterioare. Cele două moduri sunt diferite dacă există cel puțin o porțiune pe care am lăsat-o într-un fel și nu în celălalt. Deoarece aceste metode pot fi foarte multe, scrieți doar restul după împărțirea la numărul prim \ (1 \, 000 \, 000 \, 009 \) .
formatul de intrare
Pe prima linie de intrare, există un număr întreg pozitiv \ (n \) care nu depășește \ (1 \, 000 \, 000 \) care indică numărul de porțiuni. Următoarea linie este urmată de \ (n \) numere \ (r_i \) separate prin spații, cu \ (0 pentru fiecare dintre ele. Numerele \ (r_i \) sunt aranjate de la cel mai mic la cel mai mare.
Format de iesire
Scrieți două numere întregi separate printr-un spațiu: cel mai mare număr posibil de porțiuni care vor rămâne remodulate \ (1 \, 000 \, 000 \, 009 \) după îndepărtarea plăcilor necesare și numărul de modalități de selectare a acestora. Încheiați ieșirea cu un caracter newline.
Exemplu
Intrare:
Ieșire:
Fără promovare și cât mai puțin tofu posibil, lăsând copiii cu următoarele porțiuni: 1 3 4 5 5, 1 4 5 5 6, 2 2 3 5 5, 2 2 5 5 6
Datorită acestei distracții, ei prânz și câteva ore, așa că nu trebuie să se culce după-amiaza
Și tot orezul acela trebuie mâncat și de cineva
Încărcare
Trebuie să fiți conectat pentru a încărca
Întrebări și discuții
La sfârșitul rundei, veți avea ocazia să discutați soluții într-o discuție sub o soluție model.