Fişierul intrare/ieşire:photo.in, photo.outSursăCEOI 2009
AutorMihai PatrascuAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inphoto.outExplicaţie
6 4
2 1
4 1
5 1
5 4
7 1
6 4
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content