Шостий тур 


Розв’язок задачі відправляти на адресу: soft@atlanta.lutsk.ua 


до 29.12.2004 р. 

Лист повинний містити розв’язок однієї задачі. 

Тема листа VIO 
Вміст листа 

Код учасника ... 
Код задачі VIO_6 
Мова програмування в якій розв’язана задача ... 

Розв’язок задачі розмістити, як вкладений текстовий файл з іменем коду завдання програмного коду розв’язку задачі. 
--------------------------------------------------------------------------------

Задача: (100 балів) 
Koд: VIO_6 
Умова 


Тур 6. 

Дирекцiї мережi ресторанiв, до якої належать m (m<=10) закладів, напередодні Нового року надійшло n (n<=100) заявок на проведення святкових заходів певного числа місяця. Кожен i-ий (1<=i<=m) заклад має цього дня свій режим роботи - з RPi год. по RKi год. Кожна j-та (1<=j<=n) заявка передбачає проведення заходу з ZPj год. по ZKj год. Всi величини RPi, RKi, ZPj, ZKj - цiлi числа з дiапазону 9:24. 

Необхiдно задовольнити максимальну кiлькiсть сумiсних мiж собою заявок та скласти план їх обслуговування по кожному закладу. Сумісність в даному контексті означає що часи проведення заходів не перетинаються. 

Примітка. Якщо є декілька варіантів обслуговування, то навести довільний. 
Час роботи програми не більше 5 хвилин. 

Початкові дані: файл REST.DAT, формат якого: 
1-ий рядок: m 
2-ий рядок: RP1, RK1 
3-ий рядок: RP2, RK2 
... 
m+1-ий рядок: RPm, RKm 
m+2-ий рядок: n 
m+3-ий рядок: ZP1, ZK1 
m+4-ий рядок: ZP2, ZK2 
... 
m+n+2-ий рядок: ZPn, ZKn 

Результат: файл REST.SOL, формат якого: 
1-ий рядок: Z , де Z - максимальна кiлькiсть заявок 
2-ий рядок: Z11, Z12, : , де Z11, Z12, : - номера заявок для 1-ого закладу 
3-ий рядок: Z21, Z22, : , де Z21, Z22, : - номера заявок для 2-ого закладу 
... 
m+1-ий рядок: Zm1, Zm2, : , де Zm1, Zm2, : - номера заявок для m-ого закладу 
Приклад. 
Вхiдний файл REST.DAT: 
3 
9 23 
12 24 
12 24 
9 
9 12 
9 13 
12 14 
12 16 
12 19 
14 21 
17 20 
18 23 
19 24 

Вихiдний файл REST.SOL: 
7 
1 3 6 
4 7 
5 9