| Fişierul intrare/ieşire: | mins.in, mins.out | Sursă | Lot Juniori 2009 - Baraj 1 |
| Autor | Carmen Minca, Stelian Ciurea | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mins
În planul xOy se desenează un dreptunghi cu laturile paralele cu axele de coordonate. Coordonatele vârfurilor stânga-jos şi dreapta-sus ale dreptunghiului sunt: (0,0) şi (c,d). Fie P mulţimea punctelor situate în interiorul dreptunghiului, ale căror coordonate sunt numere naturale. Prin desenarea unui număr minim m de segmente de dreaptă, se uneşte vârful de coordonate (0,0) cu fiecare punct din mulţimea P. Astfel, fiecare punct din P va aparţine interiorului unui segment din cele m sau va fi o extremitate a unui segment din cele m.
Cerinţă
Scrieţi un program care să citească numerele naturale c şi d, şi care să determine numărul minim m de segmente de dreaptă desenate.
Date de intrare
Fişierul de intrare mins.in conţine o singură linie pe care sunt scrise două numere naturale c şi d, separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire mins.out va conţine o singură linie pe care se va scrie un număr natural reprezentând numărul minim m de segmente de dreaptă desenate.
Restricţii şi precizări
- c, d sunt numere naturale nenule.
- 1 ≤ c, d ≤ 1 000 000
- Pentru 50% dintre teste, c, d ≤ 5000.
- Pentru 80% dintre teste, c, d ≤ 200 000.
Exemplu
| mins.in | mins.out |
|---|---|
| 4 3 | 5 |
Explicaţie
Pentru c=4, d=3, mulţimea P a punctelor de coordonate naturale, situate în interiorul dreptunghiului, este formată din 6 puncte: {P1,P2,P3,P4,P5,P6}. Pentru a uni vârful stanga-jos al dreptunghiului, (0, 0) cu cele 6 puncte sunt suficiente 5 segmente.
