|
|
Задачи школьной олимпиады по информатике или методисты шутят
|
|
27.11.2008 |
Не так давно, в школах города Томск прошел внутривузовский тут олипиады по информатике, опредяляющий участников городской олимпиады. Для проведения этого тура методистами были разосланы по школам следующие задания.
Тексты без комментариев.
В некой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение "зован". На следующий день выпал цветной дождь, причем он прошел только над холмами. В некоторых местах падали красные капли, в некоторых - синие, а в остальных - зеленые, в результате чего холмы стали соответствующего цвета. Президенту республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся. Посчитайте количество таких "плохих" мостов.
Однажды, некий школьник Вася сидел у себя дома на кухне, в процессе чего, от нечего делать, методично тыкал вилкой по скатерти. Известно, что он совершил ровно n тычков, а вилка имела ровно m зубцов. Известно также, что зубцы были расположены таким образом, что дырки от них лежали на одной прямой и все соседние дырки были равноудалены друг от друга. После обеда его брат подошел к столу и посчитал количество дырок. Требуется определить, мог ли его брат насчитать на скатерти ровно k дырок.
В связи с изменением политической обстановки в мире и во избежание наступления экономического кризиса в стране, президент Флатландии на очередном заседании кабинета министров поставил перед правительством первоочередную задачу о подготовке пакета реформ. Сразу же после заседания был созван специальный комитет, который подготовил k различных законопроектов, каждый из которых описывал один из возможных путей проведения реформ. Перед парламентом Флатландии (который состоит из n депутатов) встала нелегкая задача выбора одного из этих законопроектов.
Согласно конституции Флатландии, все обсуждения законопроектов в парламенте проходят в одном чтении. После того, как депутаты ознакомятся с проектом закона, проводится голосование. Каждый из депутатов может проголосовать либо за принятие закона, либо против. При этом, закон принимается, если за него проголосовало как минимум L депутат.
Известно, что законопроекты, подготовленные специальным комитетом, будут обсуждаться на заседаниях парламента последовательно, начиная с проекта номер 1 и заканчивая проектом номер k. При этом, если в результате обсуждения законопроекта номер i этот законопроект будет принят, то оставшиеся законопроекты (с номерами от i + 1 до k) не будут обсуждаться вообще. Если же законопроект с номером i будет отклонен, то парламент перейдет к обсуждению следующего законопроекта (с номером i + 1). Если в результате последовательного голосования парламент отвергнет все проекты, то процесс проведения реформ отложится на неопределенное время (в этом случае страну, скорее всего, ожидает глубокий кризис). Известно также, что каждый депутат Флатландии кратко ознакомился с каждым законопроектом еще до первого заседания парламента и составил для себя список всех проектов в порядке своих предпочтений. Обозначим номер j-го законопроекта в списке предпочтений i-го депутата, как a[i,j]. Тогда это будет означать, что i-й депутат во время голосований будет пытаться добиться принятия проекта с номером a[i,1], а если это невозможно, то проекта с номером a[i,2]; если и этого никак не добиться, то i-й депутат будет пытаться протолкнуть закон номер a[i,3] и так далее. При этом
никакой депутат не хочет допустить кризиса в стране, и, поэтому, в первую очередь будет пытаться предотвратить тот случай, когда все законопроекты будут отвергнуты парламентом. Все депутаты Флатландского парламента знают не только свои предпочтения, но и предпочтения всех своих коллег. К тому же они достаточно умны и будут действовать оптимально (то есть будут пытаться добиться принятия закона, как можно более предпочтительного с их точки зрения). Президент Флатландии попросил Вас, как своего главного советника, предсказать результаты работы парламента (а именно то, какой из вариантов закона о реформах будет в итоге принят).
|
  |
