Fişierul intrare/ieşire:patrate4.in, patrate4.outSursăLot Suceava 2007
AutorStelian CiureaAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.3 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Patrate4

Pe o foaie de matematica sunt 5000 × 5000 de patratele cu latura egala cu 1 cm. Patratelele sunt evident organizate in 5000 de linii (numerotate de sus in jos de la 1 la 5000) si 5000 de coloane (numerotate de la stanga la dreapta de la 1 la 5000).

Pozitia fiecarui patratel de pe foaie este caracterizata prin numarul liniei si numarul coloanei pe care se afla patratelul. Pe foaie sunt innegrite N patratele.

Trebuie sa desenam pe foaia de matematica o multime de patrate care sa indeplineasca urmatoarele conditii:

  • aria intersectiei intre oricare doua patrate din aceasta multime este egala cu 0;
  • oricare dintre patratele acestei multimi este alcatuit doar din patratele intregi;
  • oricare patratel negru apartine exact unuia dintre patratele multimii;
  • pentru oricare dintre patratele acestei multimi, daca notam cu S aria patratului, atunci suprafata ocupata de patratelele negre din interiorul respectivului patrat apartine intervalului [S / K, 4S / K), unde K este un numar natural nenul dat.

Cerinta

Scrieti un program care determine o multime de patrate care sa respecte conditiile de mai sus.

Date de intrare

Fisierul de intrare patrate4.in contine pe prima linie doua numere naturale nenule separate prin spatiu N si K, cu semnificatia din enunt. Pe fiecare dintre urmatoarele N linii se afla cate doua numere naturale nenule separate prin spatiu, reprezentand pozitia unui patratel negru.

Date de iesire

In fisierul de iesire patrate4.out se va scrie pe prima linie un numar natural nenul np, reprezentand numarul de patrate din multime. Pe fiecare dintre urmatoarele np linii se vor afla trei numere naturale nenule separate prin cate un spatiu; primele doua valori vor reprezenta linia, respectiv coloana pe care se afla patratelul situat in coltul din stanga-sus al patratului respectiv, iar a treia valoare va reprezenta lungimea laturii respectivului patrat.

Restrictii

  • 1 ≤ N ≤ 100 000
  • 5 ≤ K ≤ 10
  • Coordonatele patratelelor negre (linie, coloana) sunt numere naturale din intervalul [1, 1000].

Exemplu

patrate4.inpatrate4.out
19 5
1 1
1 2
2 1
2 2
3 1
3 3
4 3
5 5
5 6
5 7
6 6
6 7
10 7
10 8
7 9
8 10
8 9
9 9
10 9
2
1 1 4
5 5 6

Explicatie

Exista mai multe solutii posibile. O alta solutie ar putea fi:

4
1 1 4
5 5 4
7 9 4
10 7 2

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content