kafka
Недоволен
от тежката
работа и
ниската заплата,
чиновник от
кметството
на град Безумний,
изнамерил
оригинален
метод за
решаване
молбите на
гражданите:
да ги
„размотава”, докато
те се
изморят. Така
всеки
гражданин, който
има проблем и
желае да го
реши в
кметството,
трябва да
мине през
гише “информация”, където
получава
карта с цвят 1
(цветовете са
кодирани с
последователните
цели числа от
1 до nc),
върху която е
записан
номерa bs на офиса,
където би
трябвало да
бъде решен (теоретично)
неговият
проблем. Офисите
са
номерирани с
последователните
цели числа от
1 до nb. Но
чиновникът
от
споменатия
офис, естествено
счита, че не
той трябва да
реши молбата и
много учтиво
дава на
гражданина
ново картонче
в зависимост
от цвета на
картончето, което
вече
гражданинът
има, като
върху новото
картонче
записва номер
на друг офис.
Гражданинът
отива там и
историята се
повтаря по
подобен
начин и в следващия
офис, и т.н.
Отиването от
един офис до друг
отнема на
гражданина
една минута,
а издаването
на новото
картонче е
мигновенно.
След t минути
от
напускането
на гише “информация”
гражданинът
се изтощава
напълно и се
отказва от
по-нататъшни
си опити да
реши проблема
като си отива
у дома.
Задача
При
дадени
стойности на nb, nc, bs и t, определете
номера на
офиса, издал
последното картонче
на
гражданина,
след което
гражданинът
си тръгва за
дома. За
всеки офис е
даден цветът
на новото
картонче,
което се издава
в офиса и
номера на
следващия
офис, записан
върху това
картонче.
Вход
Входният
файл kafka.in съдържа
на първия си
ред числата nb, nc, bs и t, разделени
с интервали.
Всеки от
следващите nb*nc реда
съдържа по
две цели
положителни
числа,
разделени с
интервал. Те
задават
цвета и номера,
записан
върху
картончето,
издадено
съответно от
офис 1,2,...,nb, в
зависимост
от цвета на
донесеното
картонче 1,2,...,nc. Т.е.,
редът от
файла с номер
(i-1)*nc+j+1
(където 1<=i<=nb
и 1<=j<=nc)
съдържа
цвета и
номера на
картончето,
което е
издадено в
офис i
при цвят j на
донесеното
картонче.
Изход
Изходният
файл kafka.out трябва
да съдържа
номера на последния
посетен офис
от
гражданина.
Ограничения
Пример
kafka.in |
kafka.out |
Обяснения |
3 2 2 7 |
1 |
Първият
ред показва,
че nb=3, nc=2, bs=2 и t=7. Третият ред задава,
че ако
гражданинът
отиде в офис 1
с цвят 2 на
картончето, ще му
бъде дадено
картонче с
цвят 1, върху
което е
написан
номер 3. Четвъртият
ред задава,
че ако
гражданинът
отиде в офис 2
с цвят 1 на
картончето, ще му
бъде дадено
картонче с
цвят 2, върху
което е
написан
номер 1. Петият ред задава,
че ако
гражданинът
отиде в офис 2
с цвят 2 на
картончето, ще му
бъде дадено
картонче с
цвят 1, върху
което е
написан
номер 3. Шестият ред задава,
че ако
гражданинът
отиде в офис 3
с цвят 1 на
картончето, ще му
бъде дадено
картонче с
цвят 1, върху
което е
написан
номер 1. Седмият ред задава,
че ако
гражданинът
отиде в офис 3
с цвят 2 на
картончето, ще му
бъде дадено
картонче с
цвят 1, върху
което е
написан
номер 2. Нека
тройката (c,b,m) да
показва, че
гражданинът
има
картонче с цвят
c в офис b и там
е m минути
след
напускане на гише
“информация” . Тогава
пътят на
гражданина
е следният:
(1,2,1)->(2,1,2)->(1,3,3)->(1,1,4)->(2,2,5)->(1,3,6)->(1,1,7),
Това
показва, че
последният
посетен
офис има
номер 1. |
Време
за работа на
програмата: 0.1 секунди
за тест
lect. drd. Radu
Boriga
"Titu Maiorescu" University
- Bucharest
Contact:r_boriga@yahoo.com
Превод
на български:
Емил
Келеведжиев