|
Шостий тур
Розв’язок задачі відправляти на адресу:
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
|