== include(page="template/taskheader" task_id="lego") ==
Poveste și cerință...
Compania Lego a început să vândă un nou set de piese, având piese de mai multe lungimi numere naturale:
* O singură piesă cu lungimea *L*, fiind cea mai mare piesă din set.
* Restul pieselor din set au lungimi strict mai mici decât *L*, dar mai mari ca 1.
* Piesele mai mici decât *L* au lungimi submultipli ai lui *L*.
* În set nu există două piese de aceeași lungime.
De exemplu, pentru setul cu piesa cea mai mare *L* = 32, acesta are în componență alte 4 tipuri diferite de piese, submultipli ai lui *L*: piese de lungimi 2, 4, 8, și 16.
Fiecare fabrică Lego are o matriță ce poate produce piese de dimensiune maximă *L*. Deși matrița poate produce piese de lungime 1, pentru siguranța copiilor, Lego nu pune niciodată piese de dimensiunea 1 în seturile sale, de teamă ca acestea să nu fie înghițite accidental.
h2. Cerință
Pentru că vrea să își pregătească fabricile pentru producția noului set de Lego, compania vrea să știe care este dimensiunea cea mai mică a unei piese *D* ≤ *L* pe care o poate produce o fabrică astfel încât noul set să aibă cât mai multe piese de lungimi diferite. De exemplu, pentru *L* = 32 vom alege D = 24, deoarece în setul cu piesa cea mai mare de lungime 24 vom avea alte 6 piese, de lungimi 2, 3, 4, 6, 8 și 12.
h2. Date de intrare
Fișierul de intrare $lego.in$ ...
Fișierul de intrare $lego.in$ conține pe prima linie un număr natural *L*, reprezentând lungimea maximă a unei piese pe care o poate produce fabrica Lego.
h2. Date de ieșire
În fișierul de ieșire $lego.out$ ...
Fișierul de ieșire $lego.out$ conține pe o singură linie *D*, lungimea cea mai mică determinată care are număr maxim de tipuri de piese de dimensiuni diferite în set.
h2. Restricții
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. lego.in |_. lego.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* 1 ≤ *L* ≤ 1 000 000
h3. Explicație
h2. Exemple
...
table(example).
|_. lego.in |_. lego.out |_. Explicații |
| 32
| 24
| Pentru *D* = 24, setul are 6 tipuri de piese de lungimi diferite
(piese de 2, 3, 4, 6, 8 și 12). De asemenea, este cel mai mic număr
care se poate combina cu 6 tipuri de piese de dimensiuni
diferite din intervalul configurare a matriței [1, 32].
|
| 22
| 12
| Pentru D = 12, setul are 4 tipuri de piese de lungimi diferite
(piese de 2, 3, 4 și 6). Deși putem alege și lungimile 18 sau 20
care ar avea tot 4 tipuri de piese, 12 este cea mai mică lungime
care se combină în set cu 4 tipuri de piese de dimensiuni diferite
din intervalul de configurare a matriței [1, 22].
|
== include(page="template/taskfooter" task_id="lego") ==
