Problema informatica - Multimi

Problema 1  Clasele XI-XII 100 Puncte

Multimi

Un boier are o livada cu meri, aranjata pe 10000 de randuri, numerotate de la 1 la 10000. De asemenea are la dispozitie n tarani pe care sa ii puna la munca, fiecare taran alegandu-si un interval de randuri consecutive pe care sa le culeaga. (un rand poate fi ales de mai multi tarani care il culeg in acelasi timp)

Cerinte:

Boierul vrea sa il ajutati sa gaseasca multimea minima (cu celele mai putine randuri) (pentru ca taranii sa nu munceasca foarte mult), astfel incat fiecare taran sa participe la culegerea a cel putin doua randuri de meri din aceasta multime.

Date de intrare: Datele se citesc din fisierul multimi.in astfel:

- pe prima linie numarul n de tarani

- pe urmatoarele n linii, cate doua numere x si y separate printr-un singur spatiu, care reprezinta capetele intervalului de randuri muncite de taranul respectiv (taranul munceste si randurile x si y)

Date de iesire: Rezultatul se va tipari in fisierul multimi.out astfel:

- pe prima linie cardinalul multimii minime

- pe urmatoarea linie indicele randurilor care se afla in multimea minima, separate printr-un singur spatiu (solutia nu este unica)

Restrictii si precizari:

- 0<n<=10000

- 0<x,y<=10000

- daca solutia nu este unica se va afisa oricare dintre ele

Exemplu

multimi.in multimi.out

3

4 6 7

Timp maxim de executie 1 secunda