Fişierul intrare/ieşire:mins.in, mins.outSursăLot Juniori 2009 - Baraj 1
AutorCarmen Minca, Stelian CiureaAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.15 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inmins.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content