Fişierul intrare/ieşire:carti2.in, carti2.outSursăGrigore Moisil 2011, Clasele 11-12
AutorPerticas CatalinAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Carti2

Mitruţ, motanul încălţat, vrea să-şi restructureze biblioteca în aşa fel încât să-i încapă cât mai multe cărţi din cele N pe care le are. Fiindcă îi place aşa de mult să doarmă, s-a gândit să-ţi dea ţie această sarcină şi promite să te recompenseze cu 100 puncte dacă îl ajuţi. Ştii că biblioteca are înălţimea H şi lăţimea L, iar grosimea fiecărui raft este G. Între oricare două rânduri adiacente de cărţi pe care le pui în bibliotecă trebuie plasat un raft. De asemenea, trebuie plasat un raft la baza bibliotecii. Cărţile pe care le deţine Mitruţ pot avea dimensiuni diferite, unele sunt mai late, altele mai înalte. Înălţimea cărţii i este Ai, iar lăţimea ei este Bi.

Cerinţă

Determinaţi numărul maxim de cărţi care încap în biblioteca lui Mitruţ şi afişaţi cărţile pe care le puneţi în bibliotecă. Dacă sunt mai multe soluţii, afişaţi soluţia minim lexicografică. Ordinea cărţilor pe rafturi nu contează.

Date de intrare

Pe prima linie a fişierului de intrare carti2.in se află un număr natural T care reprezintă numărul de teste pe care trebuie să le evaluaţi. În continuare, vor fi descrise fiecare din cele T teste. Pe prima linie a fiecărui test se află numerele naturale N, H, L şi G cu semnificaţia din enunţ. Pe fiecare din următoarele N linii se află câte două numere naturale Ai şi Bi. Pe linia i + 1 a fiecărui test se află descrierea cărţii i.

Date de ieşire

În fişierul de ieşire carti2.out veţi afişa răspunsul pentru fiecare test. Pe o linie va fi numărul maxim Nmax de cărţi care încap în bibliotecă, iar pe alta descrierea soluţiei optime, adică Nmax numere sortate crescător după numărul de ordine al cărţilor pe care le alegeţi. 

Restricţii

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 12
  • 1 ≤ H, L, G, Ai, Bi ≤ 1 000 000
  • Pentru 50% din teste N ≤ 9.
  • Un şir x1, x2,..., xs este mai mic lexicografic decât un alt şir y1, y2,..., yt dacă există i ≤ min(s, t) astfel încât x1 = y1, x2 = y2,..., x{i-1} = y{i-1} şi xi < yi.

Exemplu

carti2.incarti2.out
2
8 9 7 1
3 2
6 3
7 2
3 4
2 6
4 3
1 5
5 1
8 12 13 2
6 2
3 5
7 8
2 4
9 5
3 5
2 7
6 3
4
1 2 7 8
5
1 2 4 6 7

Explicaţie

Pentru primul test putem împărţi cele 4 cărţi (1, 2, 7 şi 8) în următorul fel: 1, 2 şi 8 le punem pe primul raft, iar 7 pe ultimul raft.

Pentru al doilea test putem să punem cărţile 1, 2 şi 6 pe primul raft, iar pe 4 şi 7 pe al doilea raft.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content