| Fişierul intrare/ieşire: | photo.in, photo.out | Sursă | CEOI 2009 |
| Autor | Mihai Patrascu | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Photo
Vi se oferă o fotografie a liniei de orizont a oraşului Târgu-Mureş realizată în timpul nopţii. Unele camere încă mai au lumina aprinsă. Se ştie că toate clădirile se modelează cu dreptunghiuri de arie cel mult A. Găsiţi numărul minim de clădiri ce reconstituie fotografia.
Mai exact, se dă un număr întreg A şi N puncte la coordonate numere întregi (x, y). Cerinţa constă în a găsi un număr minim de dreptunghiuri, cu una din laturi pe axa Ox iar aria cel mult egală cu A, care acoperă toate punctele. Dreptunghiurile se pot suprapune.
Date de intrare
Prima linie a fişierului de intrare photo.in conţine două numere întregi N şi A, separate printr-un singur spaţiu. Următoarele N linii conţin două numere întregi x şi y, reprezentând coordonatele fiecărui punct.
Date de ieşire
Fişierul de ieşire photo.out conţine o singură linie cu numărul minim de dreptunghiuri.
Restricţii
- 1 ≤ N ≤ 100
- 1 ≤ A ≤ 200 000
- Fiecare punct are 0 ≤ x ≤ 3 000 000 şi 1 ≤ y ≤ A.
- Pentru 30% din teste 1 ≤ N ≤ 18.
Exemplu
| photo.in | photo.out | Explicaţie |
|---|---|---|
| 6 4 2 1 4 1 5 1 5 4 7 1 6 4 | 3 | 
|
