МИНИСТЕРСТВО ОБРАЗОВАНИЯ РФ

 

 

МОСКОВСКИЙ ИНСТИТУТ СТАЛИ И СПЛАВОВ

(ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ)

 

 

 

 

 

 

 

 

 

Методические указания

по организации и проведению студенческих олимпиад

по программированию

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Москва

2003

 

 

 

 

 

 

 

 

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РФ

 

МОСКОВСКИЙ ИНСТИТУТ СТАЛИ И СПЛАВОВ

(ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ)

 

 

 

 

А.А. Мельников, А.И. Широков, В.К. Титов,

 

 

 

 

 

 

 

 

 

 

 

 

Методические указания

по организации и проведению студенческих олимпиад

по программированию

 

Под редакцией проф. Е.А. Калашникова

 

 

 

 

Второе издание, исправленное и дополненное.

 

 

 

 

 

 

 

 

Москва

2003

 

 

 

 

 

 

 

 

 

 

 

     Эта работа посвящается светлой памяти доцента кафедры Автоматизированных систем управления Московского государственного института стали и сплавов Мельникова Александра Алексеевича, пылкого энтузиаста  студенческих олимпиад, самоотверженно отдававшего много сил для их организации и проведения. Во многом благодаря усилиям Александра Алексеевича возобновились Московские и Российские олимпиады по традициям олимпиад 70-80-х годов. Еще в те годы он был признанным активистом олимпиадного движения, он дважды представлял команду студентов Москвы, как ее руководитель и тренер, на Всесоюзных олимпиадах по программированию.

     Мельников Александр Алексеевич учился в Московском государственном институте стали и сплавов на кафедре Инженерной кибернетики сначала как студен, затем как аспирант, перейдя на преподавательскую работу на этой кафедре. С момента основания в институте кафедры Автоматизированных систем управления он был ее ведущим преподавателем и ученым секретарем. Все студенты кафедры АСУ МИСиС учились программированию и другим предметам у Александра Алексеевича. Им написаны изданные большими тиражами учебные и методические пособия по важнейшим направлениям специальности. Он был ответственным на кафедре за заключительный этап подготовки специалистов - дипломирование. Под его руководством защитили дипломы десятки выпускников кафедры.

     В 2001 году Мельников А.А. возродил роль Московского института стали и сплавов как базового вуза по организации и проведению Олимпиад по программированию среди студентов России под эгидой Министерства образования РФ. Он был одним из главных действующих лиц в организации Московских олимпиад по программированию с 1986  до 1992 годов, когда МИСиС был базовым вузом по проведению Олимпиад по программированию среди технических вузов. Неоднократно он был членом жюри на Всесоюзной олимпиаде по программированию.

     Александр Алексеевич Мельников был человеком, в котором сочеталось очень много лучших человеческих качеств - доброта, жизнелюбие, энтузиазм, ответственность, трудолюбие. Память о нем сохраниться в наших сердцах и умах навсегда.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СОДЕРЖАНИЕ

 

1. Введение.

2. История олимпиад по программированию.

3. Цели и задачи олимпиад по программированию в современных условиях.

4. Участники олимпиады.

5. Оргкомитет олимпиады.

6. Жюри олимпиады.

7. Выбор конкурсных задач.

8. Правила проведения олимпиады.

9. Подведение итогов олимпиады.

10. Критерии оценки результатов.

11. Разбор задач и награждение победителей.

12. Задачи, предлагавшиеся на олимпиаде в МИСиС в 2001 г.

13. Задачи II тура  Московской олимпиады 2001 г.

14. Задачи III тура  Российской олимпиады 2001 г.

15. Задачи, предлагавшиеся на олимпиаде в МИСиС в 2002 г.

16. Задачи II тура  Московской олимпиады 2002 г.

17. Список победителей олимпиад 2001-2002 гг.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. ВВЕДЕНИЕ

 

 

    Согласно приказу Министерства образования РФ № 2019 от 10 мая 2001 г. Московский институт стали и сплавов назначен базовым вузом и ответственным за проведение олимпиад по программированию II тура (Московский регион) и III тура (Россия) среди студентов технических специальностей.

    Цель этих олимпиад возродить традиции межвузовских олимпиад по программированию 70-х – 80-х и начала 90-х годов, которые перестали проводиться из-за прекращения финансирования во времена «демократических» реформ. В те годы регулярно организовывались туры олимпиадных соревнований на республиканских и Всесоюзном уровнях. Прекращение проведения этих олимпиад, вызывало глубокое сожаление, так как наши программисты лишились важного механизма выявления и поощрения талантливой молодежи.

      Воспользовавшись ситуацией, американцы с 1996 года стали проводить олимпиады по программированию в России в рамках  объявленного ими командного чемпионата мира по программированию, организованного американской Ассоциацией ACM (Association for Computing Machinery).

      В Санкт-Петербурге проводятся полуфинальные туры этого чемпионата для Северо-Восточного Европейского региона, в основном охватывающего Россию. Базовым вузом, где проводится этот тур, является Санкт-Петербургский государственный институт точной механики и оптики.  Четвертьфинальные туры для Центрального региона России  проводятся в г. Рыбинске в Рыбинской государственной авиационно-технологической академии.

     Правила и условия проведения проамериканских олимпиад резко отличаются от условий традиционно сложившихся в российских олимпиадах. Разница состоит в следующих принципах:

     а) Условия задач проамериканских олимпиад даются только на английском языке, несмотря на то, что они проводятся на территории России. Это по нашему мнению искусственно ставит в неравные условия тех сильнейших программистов, которые недостаточно хорошо знают английский.

     б)  Формулировки задач наших олимпиад – краткие, четкие, как формулировки математических теорем. Прочитав условие, участник сразу приступает к решению поставленной задачи. Формулировки задач проамериканских олимпиад часто нарочито вычурные, вписанные в образы коротких рассказов, требующие не только перевода с английского языка, но и с языка навязанных образов на язык точных математических понятий. Это отнимает время от непосредственного решения задачи и требует  хорошего знания тонкостей английского языка.

     в) В наших олимпиадах каждый участник имеет право показать силу своего личного таланта. У нас оцениваются личные успехи в соревнованиях между участниками. Каждый выступает за себя и не зависит от неудач своих товарищей по команде. Соревнования у нас лично-командные, но личный зачет проводится отдельно, а командный зачет определяется по сумме очков, полученными членами команды.

         В проамериканских олимпиадах каждой команде выделяется только один компьютер. Внутри команды ее члены обезличены. Кто и какой вклад внес в успех команды - не имеет значения. Такой подход часто приводит к неуспеху команды из-за психологической несовместимости ее членов. Часто очень сильный программист вынужден выступать в команде со слабыми членами за неимением лучших, которых включили в команду только из-за хорошего знания английского или за умение быстро набирать тексты на компьютере.

     г) В проамериканских олимпиадах зачетные очки зависят  от времени сдачи правильно решенной задачи. Это создает в соревнованиях у участников большую нервозность. По существу участники соревнуются не в качестве, а в скорости решений. В наших олимпиадах в первую очередь при оценках решений учитывается их качество и только при равных оценках может учитываться время сдачи.

     д)  Более демократично у нас проводится отбор олимпиадных задач. По традиции руководители команд вузов-участников могут представить для соревнований свои задачи.  Задачи в день соревнований обсуждаются членами жюри, состоящего из руководителей команд, и голосованием выбираются наиболее приемлемые для олимпиады.

     Московский Университет (факультет Вычислительной математики и кибернетики) стал проводить Московские олимпиады по программированию по тем же правилам, которые введены американцами, с той только разницей, что они проводятся на русском языке.

     Несмотря на критические высказывания в адрес олимпиад, проводимых у нас по инициативе американцев, мы приветствуем любые усилия, повышающие интерес у молодежи к программированию и выявляющие среди них таланты. Но, к сожалению, надо признать, что американские мероприятия способствуют политике «утечки мозгов» из России.

     Возрождение наших олимпиад мы считаем хорошей,  нужной и своевременной альтернативой.

 

 

 

2. История Олимпиад по программированию

 

      Первая Московская городская олимпиада по программированию для ЭВМ была проведена в апреле 1979 года. В ней участвовали представители 11 вузов г. Москвы. Олимпиада проводилась  в Московском экономико-статистическом институте (МЭСИ), который выступил инициатором проведения таких олимпиад. МЭСИ начал проводить внутренние институтские олимпиады с 1974 года, а с 1977 года стал приглашать на свои олимпиады студенческие команды других вузов.

     Идея о проведении олимпиад по программированию возникла к тому времени уже и в других вузах г. Москвы. Соревнования по программированию между студентами проводились на кафедрах в МФТИ, МИЭМ. По существу, первые внутривузовские олимпиады по программированию состоялись в 1979 году в вузах МИФИ, МАИ, МАДИ, МИСИ, МИИТ. В 1980 году к этому движению присоединились МИЭМ и МИСиС. Количество вузов, проводящих внутривузовские олимпиады по программированию, росло с каждым годом. После получения информации о проведении первой городской олимпиады по программированию Московский институт стали и сплавов подключился к этой работе. В 1980 году в МИСиС была проведена первая внутривузовская олимпиада и команда института была направлена на вторую городскую

олимпиаду по программированию. Но уже с самой первой олимпиады в МИСиС был принят принцип открытых внутривузовских олимпиад, на которые приглашаются команды других вузов и некоторых школ г. Москвы. Во внутривузовских олимпиадах МИСиС принимали участие студенты МИСИ, МИЭМ, МИИТ и учащиеся таких школ, как 179, 315, физико-математическоя школа №18 при МГУ и другие.

     Открытость внутривузовских олимпиад позволила накопить опыт, на основе которого МИСиС в дальнейшем принял на своей территории кустовую олимпиаду, а затем стал базовым по проведению олимпиады по программированию для студентов инженерно-технических вузов.

     В 1984 году было принято решение разделить вузы г. Москвы на три направления: 1) вузы с большим объемом подготовки по ЭВМ; 2) вузы, не специализирующиеся в подготовке по ЭВМ и 3) университеты и экономические вузы. Городская олимпиада проводилась во всех трех направлениях с раздельным подведением итогов по каждому направлению. Роль базового вуза по проведению городской олимпиады продолжал выполнять МЭСИ. Такая же ситуация имела место и в 1985 году. В 1986 году базовым вузом наряду с МЭСИ был назначен и МИСиС и московская городская олимпиада стала проводиться, как и Всесоюзная, с делением на две группы вузов: в МЭСИ - для студентов университетов и экономических вузов, в МИСиС - для студентов инженерно-технических вузов.

Возглавив Олимпиаду по программированию, МИСиС автоматически принял на себя роль вуза, обеспечивающего участие сборной команды Москвы на всесоюзных Олимпиадах по программированию, которые проводились в разных городах СССР.

Отметим, что студенты МИСиС, традиционно участвуя в городских и всесоюзных Олимпиадах, занимали достаточно высокие места.

Таким образом, историю Олимпиад по программированию можно разделить на этапы:

Первый этап, 1979-1981 года. Московские городские олимпиады проводились в МЭСИ.

Второй этап, 1982-1983 года. Олимпиады проводились в трех вузах: МЭСИ, МИСиС и МИИТ.

Третий этап, 1984-1985 года. Олимпиады проводились в трех вузах, но с разделением по ориентации: МЭСИ (университеты и экономические вузы); МИСИС (вузы не специализирующиеся на выпуске специализирующихся в области ЭВМ) и МИИТ (вузы с большим объемом подготовки по ЭВМ)

Четвертый этап, 1986--1992 года. МЭСИ (университеты и экономические вузы); МИСиС (все технические вузы).

 

           Возрожденные  в 2001 году олимпиады в МИСиС, продолжающие традиции олимпиад до 1992 года, можно считать новым Пятым этапом.

Хотим надеяться, что олимпиадное движение, начатое этим этапом, будет иметь достойное продолжение.

 

 

 

 

 

 

 

 

3. Цели и задачи олимпиад по программированию в современных условиях.

 

 

       Современные компьютерные технологии стремительно изменяют мир программного обеспечения компьютеров, которые практически используются во всех областях человеческой деятельности и становятся неотъемлемой частью организма нашего общества. В этих условиях важнейшей задачей общества является подготовка программистов самой высокой квалификации, способных создавать, совершенствовать, поддерживать программное обеспечение в соответствии с современными требованиями.

      Но как привить студентам интерес к программированию, к решению сложных алгоритмических задач, требующих творческого подхода? Для этого существует много средств, но нам хотелось бы выделить одно из наиболее эффективных – студенческие олимпиады по программированию. Дух соревнований в олимпиаде, достигнутые в ней успехи не только повышают интерес к программированию у наиболее способных студентов, но и развивают в них творческое начало, стремление полнее использовать компьютеры в своей учебной и научной деятельности, желание стать специалистами с высокой компьютерной культурой.

       Предметная олимпиада по программированию проводится с целью пропаганды современных методов и приемов программирования, повышения к ним интереса у студентов, а также выявления и поощрения студентов, добившихся лучших результатов в этой области. Она способствует развитию навыков самостоятельной работы, творческого подхода к решению поставленных задач, не тривиальности мышления, воспитывает у участников стремление к достижению высоких результатов, приносящих чувство глубокого удовлетворения.

      Главная особенность олимпиад по программирования состоит в том, что соревнование проводится с использованием компьютеров. Программы, составляемые участниками олимпиады, выполняются на компьютерах и правильность решения задач, а также некоторые характеристики этих решений определяются по результатам их выполнения на компьютере. Таким образом, важным судьей при подведении итогов олимпиады по программированию выступает компьютер. Это приводит к беспристрастным точным оценкам характеристик качества и эффективности решений.

     Важным моментом проведения олимпиад является подтверждения хорошего уровня учебно-методической работы и качества обучения в современном вузе. Результаты олимпиад дают возможность оценить методы и уровень подготовки талантливых и заинтересованных студентов, требуют далее правильной расстановки акцентов при работе с сильными студентами.

    Соревновательный дух олимпиад приводит к стремлению вузов лучше готовить студентов, прививать им интерес к программированию, выявлять способных студентов, а следовательно, повышает уровень преподавания в вузах и уровень квалификации самих студентов.

 

 

 

 

4. Участники олимпиады

 

       К участию в олимпиадах допускаются команды любых инженерно-технических вузов как Московского региона, так и России, составленные из студентов–победителей внутривузовского тура олимпиады. Команда состоит из трех студентов, причем не менее двух студентов должно быть не старше 4-го курса.

Для участия в олимпиаде каждый ВУЗ должен в оговоренные сроки представить в базовый вуз заявку на участие за подписью проректора вуза. В заявке указывается состав команды (включая запасных, с указанием руководителя и тренера команды) и места, занятые участниками во внутривузовской олимпиаде. Вместе с заявками каждый вуз–участник должен представить в базовый вуз тексты олимпиадных заданий, предлагавшихся студентам на внутривузовской олимпиаде.

       Если в регионе проводился II тур (региональный), то по его результатам оргкомитет и жюри отборочного тура формирует команду из представителей нескольких вузов, или несколько команд от каждого вуза, успешно выступившего на отборочном туре.

 

 

5. Оргкомитет олимпиады.

 

      Оргкомитет II и III туров олимпиады по программированию формируется приказом ректора базового вуза из представителей МИСиС. В функции оргкомитета входит подготовка и проведение II и III туров олимпиады, формирование по итогам II тура команды московского региона для участия в III туре олимпиады.

 

 

6. Жюри олимпиады.

 

       Жюри II и III туров олимпиады по программированию формируется из руководителей команд–участниц олимпиады (представителей вузов). Каждый вуз в жюри имеет один решающий голос. Председателем жюри оргкомитет назначает представителя базового вуза. Все решения жюри принимает коллегиально большинством голосов. При равенстве голосов председатель жюри получает дополнительный решающий голос. Все заседания жюри протоколируются, подписываются всеми членами и включаются в отчет о соответствующем туре олимпиады.

       В функции жюри входит выбор конкурсных задач, проверка заданий на тестах жюри и подведение итогов олимпиады.

 

 

 

 

 

 

7. Выбор конкурсных задач.

 

        Руководитель каждой команды в день проведения олимпиады представляет на рассмотрение жюри одну или несколько олимпиадных задач, подготовленных специально для этого тура. По каждой задаче должно быть представлено:

        – текст задачи;

        – листинг реализующей программы на алгоритмическом языке;

– набор отладочных тестов с результатами счета.

        После обсуждения всех задач, предложенных представителями вузов, и голосования жюри отбирает для олимпиады оговоренное количество задач, набравших наибольшее количество голосов. Жюри вправе вносить изменения в тексты задач и в тестовые данные. Жюри также решает вопрос о языках и системах программирования, на которых участники будут решать предложенные задачи. Также жюри решает, какое время будет предоставлено участникам олимпиады для решения и отладки задач.

 

 

 

8. Правила проведения олимпиады.

 

       Перед началом олимпиады производится регистрация и рассадка участников в аудитории или компьютерных классах с таким расчетом, чтобы члены одной команды не сидели или находились рядом. Каждому участнику при регистрации выдается индивидуальный шифр для его программ по каждой задаче. Под этими шифрами в дальнейшем и фигурируют программы участников. Участников знакомят с правилами проведения олимпиады и выполнения заданий на ЭВМ, а также с правилами сдачи программ в жюри для тестирования. Началом олимпиады считается время окончания обсуждения текстов условий задач с участниками и ответов на их вопросы.

       Во время олимпиады участникам разрешается пользоваться любой справочной литературой, но передавать литературу друг другу запрещается. Контакты участников друг с другом и с руководителями команд строго ограничены. При необходимости участник может обратиться к представителю оргкомитета с просьбой организовать встречу с руководителем, которая должна проходить только в присутствии представителя оргкомитета.

       В случае нарушений этих правил команда (или члены команды) отстраняются от участия в олимпиаде.

      Для решения задач можно использовать только те языки и системы программирования, которые были объявлены в начале олимпиады. На решение и отладку задач участникам отводится заранее объявленное время. После установленного срока сдачи программ прием их в жюри заканчивается. Жюри вправе продлить срок приема задач.

      По завершении решения и отладки задачи участник сдает в оргкомитет исходный текст программы и выполнимый файл для тестирования в жюри. После сдачи программы в оргкомитет внесение в нее исправлений или замена текстов и файлов программ запрещается.

      Все сданные в оргкомитет программы жюри просчитывает на компьютере на контрольных тестах с протоколированием результатов по каждому тесту.

 

 

 

9. Подведение итогов олимпиады.

 

       Проверка работ осуществляется только членами жюри. Программы фигурируют в процессе проверки только под шифрами, выданными участникам при регистрации. Расшифровка работ производится после окончания проверки и ранжирования всех представленных программ. Свое решение об итогах олимпиады жюри выносит после проверки всех заданий в день олимпиады. Переносы заседаний жюри по подведению итогов олимпиады на следующий день или дни не допускается.

       Итоги подводятся на основании принятых жюри критериев оценки результатов.

       Апелляции, поступающие в жюри от членов команд или от их руководителей, рассматриваются жюри в полном составе как до предварительного вынесения решения об итогах олимпиады (до расшифровки работ), так и после расшифровки работ в день проведения олимпиады.

       После рассмотрения всех апелляций принимается окончательное решение, которое протоколируется и подписывается всеми членами жюри.

 

 

 

10. Критерии оценки результатов.

 

          Выполненные участниками олимпиады работы упорядочиваются жюри в соответствии с критериями, применяемыми в порядке, указанном ниже:

          – количество правильно решенных задач (прошедших на всех тестах жюри);

          – количество правильно пройденных тестов из предложенных жюри;

– время, затраченное процессором на все тесты жюри по каждой задаче;

–        суммарное количество исправлений в окончательном тексте программы  по отношению к исходному тексту (применяется в случае, если участники сначала пишут программы в аудитории, а затем отлаживают их на компьютерах).

 

           Две одинаковые задачи (исходные тексты программ) снимаются жюри сразу без возможности апелляции!

 

 

 

11. Разбор задач и награждение победителей.

 

         День разбора конкурсных задач и награждение победителей проводится оргкомитетом в базовом вузе после III тура в один из следующих дней, назначенном жюри. На разбор приглашаются все участники олимпиады и представители вузов (руководители и тренеры команд). Для представителей вузов в этот день предусмотрена работа семинара по выработке рекомендаций по организации и проведению последующих олимпиад.

 

 

_____________________________________________________________________

 

12. Задачи, предлагавшиеся на

 олимпиаде в МИСиС в 2001 г.

 

 

 

 

Задача «Бильярд»

 

          1  4

          2  3

          Бильярдный стол представляет собой клеточный прямоугольник размера M*N. В клетке с координатами (I, J) находится шар. В переменной К задано значение, определяющее направление по диагонали, в котором начинается двигаться шар. Направление кодируется следующим образом: 1 – влево-вверх, 2 – влево-вниз, 3 – вправо-вниз, 4 – вправо-вверх. (Схема ориентации показана в начале условия задачи). Шар движется по диагонали до стенки бильярдного стола и отражается от нее, продолжая движение по перпендикулярному диагональному направлению. Движение шара заканчивается выходом из бильярдного поля, если он попадет в одну из его угловых клеток (лунку).

        Требуется по заданным M, N, I, J, K определить, выйдет ли шар за край бильярдного поля через лунку, и если выйдет, то через какой угол и за сколько ударов о стенку бильярдного стола. Если шар не выйдет за пределы поля, надо проследить его движение до попадания в начальную точку с начальным направлением движения и подсчитать число ударов в одном цикле траектории.

         Составленная программа должна обработать несколько тестов вплоть до конца файла.

 

         Исходные данные: В каждой строке исходного файла (стандартный ввод) задается определенный тест: 5 целых чисел, разделенных пробелами: четыре двузначных числа и одно однозначное.

         Исходные данные корректны: M, N>=2, 1<=J<M, 1<=J<=N, 1<=K<=4.

 

         Результат для каждого теста должен содержать число ударов о стенку и название угла, если шар попадет в лунку.

         Например, для следующих исходных строк:

         2 2 1 1 1

         3 3 1 2 2

         3 5 2 2 4

ответ может иметь вид:

 

Тест 1 : 02 02 01 01 1   - 0 ударов, шар попал в верхнюю, левую лунку.      

Тест 2 : 03 03 01 02 2   - 4 удара, шар в лунку не попадает.                 

Тест 3 : 03 05 02 02 4   - 1 удар, шар попал в нижнюю, правую лунку.                     

 

 

Автор:  В.К. Титов

_____________________________________________________________________

 

 

 

 

 

Задача «Треугольник и отрезок»

 

        Даны треугольник и отрезок. Определить, пересекает ли отрезок контур треугольника. Координаты точек (вершин треугольника и концов отрезка) - вещественные числа.

 

        Исходные данные: Каждая строка входного файла соответствует отдельному тесту и содержит пять пар чисел (координат точек): первые три пары - координаты вершин треугольника, последние две пары - координаты концов отрезка (числа разделены пробелами).

 

        Результат: Для каждого теста дать ответ: пересекается контур треугольника отрезком или нет.

 

        Например, для следующих исходных данных:

        0 0 0 1 1 1 1 1 0 0

        0.1  0.1  0.1  0.2  0.2  0.1  0.1  0.3  0.3  0.1

        1.4  1.0  1.0  1.4  1.4  1.4  1.2  1.0  1.2  1.7

результат может быть представлен в форме:

Тест 1 - Есть пересечение

Тест 2 - Нет общих точек              

Тест 3 - Есть пересечение.

 

 

_____________________________________________________________________

 

 

 

 

 

Задача «Путь коня»

 

          Найти кратчайший путь движения коня на шахматной доске, соединяющий два заданных поля доски. Координаты клеток шахматной доски задаются в обычной шахматной нотации: координата по вертикали - буква от «а» до «h”, координата по горизонтали - цифра от 1 до 8.

 

          Исходные данные:  Каждая строка входного файла соответствует отдельному тесту и содержит в текстовом виде координаты двух клеток шахматной доски: начальное и конечное положение коня, разделенные пробелом.

 

          Результат: для каждого теста выдать последовательность шахматных полей: координаты начального поля, промежуточных полей и конечного поля кратчайшего пути движения коня.

 

          Например, для следующих исходных данных:

          al b3

          al b2

результат может быть представлен в форме:

Тест 1 - al b3

Тест 2 - al c2 el d3 b2

 

 

_____________________________________________________________________

 

 

 

 

 

 

 

 13. Задачи II тура  Московской олимпиады 2001 г.

 

 

Задача A «Составить квадрат»

 

          Лист бумаги в клетку квадратной формы размера NxN произвольно разрезан на прямоугольные части, каждая из которых имеет целое число клеток. Полученные прямоугольные куски перемешаны. Требуется из заданных прямоугольников снова составить квадрат.

           Примечание. Квадрат не обязательно должен быть составлен из прямоугольников в том же порядке, в каком он разрезан. При сборке прямоугольники можно поворачивать.

 

           Исходные данные. В каждой строке входного файла (стандартный ввод) задается отдельный тест в виде целых чисел, разделенных пробелами: первое число M – число прямоугольников, а далее M пар чисел, задающих размеры прямоугольников (M<100).

           Например, строка:

           6 3 4 2 3 4 2 3 3 2 4 2 3

           означает, что задано шесть прямоугольников размером:

           3х4, 2х3, 4х2, 3х3, 2х4, 2х3.

 

           Результат. Найденный вариант составления квадрата должен быть распечатан в виде квадратной матрицы размера NxN, каждая клетка которой содержит двузначное число, обозначающее номер прямоугольника, которому эта клетка принадлежит.

           Если из заданных прямоугольников нельзя составить квадрат, то должно быть напечатано сообщение: «квадрат не может быть составлен».

 

           Пример. Для следующих исходных данных:

           2 1 1 1 2

           6 3 4 2 3 4 2 3 3 2 4 2 3

результат может быть таким:

 

Тест 1 : квадрат не может быть составлен

 

Тест 2 :    1 1 1 3 3 5 5

                1 1 1 3 3 5 5

                1 1 1 3 3 5 5

                1 1 1 3 3 5 5

                2 2 6 6 4 4 4

                2 2 6 6 4 4 4

                2 2 6 6 4 4 4

 

Автор:  В.К. Титов

_____________________________________________________________________

 

 

 

 

Задача B «Домино»

 

              Из заданных костей домино составить цепочки по известным правилам домино. Определить какое наименьшее число цепочек можно составить из заданных костей и указать эти цепочки. Кости заданы в виде пар целых чисел.

              Исходные данные. В каждой строке входного файла (стандартный ввод) задается отдельный тест в виде целых чисел, разделенных пробелами: первое число N – число заданных костей, а далее N пар чисел обозначающих кости.

 

              Например, строка:

              4 5 2 0 6 2 6 5 0

означает набор следующих костей домино:

 

 

·   ·     ·   ·         ·   · ·

· · ·                   · · ·

· · · ·             ·     · · ·

·   ·         ·         ·   ·

 

 

 

             Результат должен быть представлен для каждого теста в виде:

             Тест 1: Число составленных цепочек = 1

             Цепочка 1:  5:2-2:6-6:0-0:5

Что будет обозначать цепочку домино:

·   ·     ·   ·         ·   · ·

· · · ·             ·     · · ·

· · ·                   · · ·

·   ·         ·         ·   ·

 

 

      

      Пример. Для следующего входного файла:

5 1 1 0 0 3 3 2 2 6 6

4 5 2 0 6 2 6 5 0

выходной файл может быть таким:

Тест 1: Число составленных цепочек = 5

Цепочка 1: 1:1

Цепочка 2: 0:0

Цепочка 3: 3:3

Цепочка 4: 2:2

Цепочка 5: 6:6

Тест 2: Число составленных цепочек = 1

Цепочка 1: 5:2-2:6-6:0-0:5

 

 

Автор:  В.К. Титов

_____________________________________________________________________

 

 

 

 

Задача C «Лужи на площади»

 

 

            Прямоугольная площадь размером MxN (2<=M,N<=9), замощенная единичными блоками (квадратными плитами), со временем стала неровной: блоки сдвинулись по вертикали на некоторое число L мм. (L – вводится для каждого блока).

            Определить места образовавшихся на этой площади луж после продолжительного дождя и общий объем воды в этих лужах.

            Считать, что:

             – на границе (на нулевом уровне) имеются сточные решетки;

             – 1 литр воды = (1 мм. высоты  лужи)*(площадь единичной плиты);

             – через точку (угол квадрата) вода не может проходить;

–        после дождя высыхают только те плиты, с которых стекла вода.

 

            Исходные данные. В первой строке входного файла (стандартный ввод) задаются два целых числа M и N. Далее вводится матрица L: M строк, по N чисел в каждой строке (числа отделяются друг от друга пробелами).

            Потом вводятся M и N для следующего теста, за которыми идет своя матрица L. И так далее до конца файла.

 

             Результат. Для каждого теста распечатать матрицу, изображающую площадь, в которой единицами обозначены квадраты, покрытые водой, а нулями – сухие квадраты, и число, равное объему воды всех луж не площади.

            Пример. Для следующих исходных данных:

2 2

 -1 –1

 -1   0

3 3

 5.3  5.3  5.3

 5.3  3.3  5.3

 5.3  5.3  5.3

результат может быть представлен в форме:

Тест 1 - Лужи:  1 1

                          1 0    Объем воды = 3.0

Тест 2 - Лужи:  0 0 0

                          0 1 0

                          0 0 0    Объем воды = 2.0

 

_____________________________________________________________________

 

 

 

 

14. Задачи III тура  Российской олимпиады 2001 г.

 

 

Подготовительный тур.

 

Задача  "Юбилейный календарь"

 

            Юбилейным днем называется день, в который человек прожил число лет кратное 5, или число месяцев, кратное 10, или число недель, кратное 50, или число дней, кратное 100, или число часов, кратное 1000, или число минут, кратное 100 000, или число секунд, кратное 10 000 000.

            Для заданной даты рождения (день/месяц/год) определить все юбилейные дни, которые принадлежат заданному месяцу (месяц/год). 

 

            Примечание. Часы, минуты и секунды начинать считать со следующего дня после рождения. Если кратное число попадает на границу двух дней, юбилейным днем считать первый из них. (Ноль не считать кратным числом).

           Известно, что невисокосный год имеет 365 дней, а високосный – 366 дней.  Год считается високосным, если его номер делится на 4, но не делится 100, но делится на 400.

 

           Исходные данные. В каждой строке входного файла (стандартный ввод) задается  отдельный тест в виде пяти чисел, разделенных пробелами:

 дд мм гггг мм гггг

здесь первые три числа обозначают дату рождения, а два следующих числа обозначают месяц, в котором находятся юбилейные дни. (Месяц юбилейных дней не должен предшествовать месяцу дня рождения. Дата берется из первых трех тысячелетий нашей эры. Период жизни, в котором ищутся юбилейные дни, не превышает 150 лет. Исходные данные считать корректными.)

 

           Результат. Для каждого теста вывести все юбилейные дни, принадлежащие заданному месяцу, с указанием для каждого дня числа прожитых к этому дню соответствующих единиц времени. Если в заданном месяце юбилейных дней нет, вывести сообщение:

  «Юбилейных дней нет».

 

          Пример. Для следующих исходных данных:

12 12 2001 12 2001

01 01 2001 04 2001

 

результат может быть таким:

Тест 1:

Юбилейных дней нет.

Тест 2:

Юбилейные дни:

11 –го числа прожито  ровно 100 дней.

 

 

Автор:  В.К. Титов

_____________________________________________________________________

 

 

 

Основной тур.

 

Задача A " Египреческие числа"

 

            В древней Египреции натуральные числа обозначались следующим образом. Из местного алфавита брались первые N букв и из них составлялись слова длины K (K<=N), состоящие из различных букв (цифр). Затем все такие возможные слова упорядочивались в алфавитном порядке и полученный набор слов соответствовал конечному интервалу натуральных чисел, начиная с единицы. Если для нужд страны переставало хватать этого ограниченного ряда чисел, сенат Египреции временами своим указом увеличивал или число N, или число K.

           Мы будем обозначать буквы египреческого алфавита известными нам строчными буквами латинского алфавита (и, следовательно, N<=26). Тогда египреческая единица при K=5 (для любого N>= K) будет обозначаться: abcde.

            В задаче требуется для заданных N и K и заданного египреческого числа определить следующее по порядку число (т.е. на единицу большее), если оно существует.

            Примечание. Напомним 26 латинских букв в их алфавитном порядке:

a b c d e f g h i j k l m n o p q r s t u v w x y z.

 

            Исходные данные. В первой строке входного файла (стандартный ввод) задаются два целых десятичных числа N и K. Во второй – египреческое число из множества, соответствующего заданным N и K.

            Далее вводятся N и K для следующего теста, за которыми идет новое египреческое число. И так далее до конца файла.

 

             Результат. Для каждого теста вывести изображение следующего египреческого числа из того же множества с заданными N и K, если оно существует. Если оно не существует вывести: «Число не существует».

             Пример. Для следующих исходных данных:

10  5

abcde

5  5

abcde

26  4

zyxw

 

результат должен быть таким:

 

Тест 1:

abcdf

Тест 2:

abced

Тест 3:

Число не существует.

 

 

Автор:  В.К. Титов

_____________________________________________________________________

 

 

 

Задача B "Ферзекони"

 

             Ферзеконем называется мифическая шахматная фигура, которая может ходить и как ферзь и как конь. Расставить на обычной шахматной доске максимальное число ферзеконей так, чтобы они не били друг друга. Подсчитать число различных таких расстановок на доске максимального числа ферзеконей.

 

              Исходные данные. Входных данных нет.

 

              Результат. Вывести один из возможных вариантов расстановки максимального числа ферзеконей в виде матрицы размера 8х8, в которой положение ферзеконей указано звездочками, а пустые клетки доски – нулями. Затем вывести число различных расстановок.

 

 

_____________________________________________________________________

 

 

 

 

 

Задача С "Расставить знаки между числами"

 

             Для заданного набора целых чисел без знака расставить между ними арифметические знаки сложения, вычитания и умножения так, чтобы результат вычисления полученного арифметического выражения был максимальным.

             Число знаков умножения в этом выражении должно быть равным или на 1 больше, чем знаков сложения, а знаков сложения – равно или на 1 больше, чем знаков вычитания. В наборе должно быть не менее четырех чисел, а в полученном выражении должны присутствовать  все три арифметических знака.

 

             Исходные данные. В каждой строке входного файла (стандартный ввод) задан отдельный тест: набор целых чисел, разделенных пробелами. Каждый набор содержит не более 100 чисел и заканчивается переходом на следующую строку. Все тесты заканчиваются признаком конца файла.

 

             Результат. Для каждого теста вывести текстовую строку, представляющую соответствующий набор чисел со вставленными между ними арифметическими знаками и заканчивающуюся знаком равно, после которого идет числовое значение полученного арифметического выражения.

 

             Пример. Для следующих исходных данных:

 

1 1 1 1 1 1 1 1 1 1 1 1

2 3 4 5

результат должен быть таким:

Тест 1:

1х1х1х1х1+1+1+1+1-1-1-1=2

Тест 2:

2-3+4х5=19

 

 

 

_____________________________________________________________________

 

 

 

 

 

15. Задачи, предлагавшиеся на

 олимпиаде в МИСиС в 2002 г.

 

 

15.1. Первый тур.

 

 

Задача А «Возрастающие матрицы».

 

 

         Матрица A размера M × N, заполненная всеми целыми числами от 1 до M × N, называется возрастающей, если выполняются следующие условия:

 

Ai,j > Ai-1,j   ,  где  i=2,…,N,  j=1,…,M

 

Ai,j > Ai,j-1   ,  где  i=1,…,N,  j=2,…,M

 

        Для заданных M и N необходимо найти число всех различных возрастающих матриц порядка  M × N. ( Ограничения: M × N<20, M≥1, N≥1).

 

        Входные данные. В каждой строке входного файла (стандартный ввод) задан отдельный тест: два целых числа M и N, разделенные пробелом.

Все тесты заканчиваются признаком конца файла.

 

        Выходные данные. Для каждого теста распечатать число всех возрастающих матриц, соответствующих заданным  M и N.

 

Пример.

Входные данные:

2 2

2 3

Выходные данные:

Тест 1

Число возрастающих матриц = 2

Тест 2

Число возрастающих матриц = 5

 

 

Автор:  В.К. Титов

_____________________________________________________________________

 

 

 

 

 

 

Задача B «Лес».

 

       Лес – это  клеточное поле в виде прямоугольника  размера M × N. В отдельной клетке леса может находиться только одно дерево. Деревья в лесу двух типов: те, которые можно вырубить, и те, которые рубить запрещено. Требуется вырубить наибольшее количество деревьев, которые можно вывезти за пределы леса. Срубленные деревья можно вывозить только по свободным клеткам леса, переходя между ними по горизонтальным и вертикальным общим сторонам. ( Ограничения: 0≤M≤100, 0≤N≤100).

 

Входные данные. В первой строке каждого теста содержатся два целых числа M и N, разделенные пробелом. Далее следуют M строк по N символов в каждой, задающих исходную структуру леса. Каждый символ в строке может быть:

‘.’  - пустая клетка леса;

‘!’ – дерево для вырубки;

‘#’  - дерево, запрещенное для вырубки.

Входной файл (стандартный ввод) может содержать несколько тестов. Все тесты заканчиваются признаком конца файла.

 

Выходные данные. Для каждого теста программа должна напечатать количество деревьев, которые можно вывезти из соответствующего леса.

 

Пример.

Входные данные:

3 4

.##.

#!!#

.##.

6 9

###..####

#..!##!!#

#.#!#.#!#

!!#!#!#.#

#.#!#!#!#

..##.##!#

 

Выходные данные:

Тест 1

Число срубленных деревьев = 0

Тест 2

Число срубленных деревьев = 11

 

 

Автор:  В.К. Титов

_____________________________________________________________________

 

 

 

 

Задача С  «Прямоугольники».

 

        В трехмерном пространстве с декартовой системой координат 0xyz расположено N  прямоугольников, стороны которых параллельны осям координат. Необходимо определить общее количество попарных пересечений областей прямоугольников. Прямоугольники могут пересекаться в точке, отрезке или прямоугольной области. Совпадающие прямоугольники считаются пересекающимися. ( Ограничения:  0≤N≤100).

 

Входные данные.  Каждый прямоугольник задается одной из своих диагоналей, то есть координатами двух своих вершин, принадлежащим разным сторонам. Все координаты – целые числа.

В первой строке каждого теста содержится число  N. Далее следуют еще N строк, в каждой из которых расположено по шесть целых чисел, задающих  диагонали.

То есть, каждый тест входного файла имеет вид:

N

x11 y11 z11 x12 y12 z12

x21 y21 z21 x22 y22 z22

.   .   .   .   .   .   .   .   .   .   .   .

xN1 yN1 zN1 xN2 yN2 zN2

 

Выходные данные. Для каждого теста программа должна напечатать количество всех попарных пересечений прямоугольников, если такие имеются, или 0, если пересечений нет.

 

Пример.

 

Входные данные:

3

-1 –1  0  1  1  0

 0 –1 –1  0  1  1

-1  0 –1  1  0  1

2

5  6  7  8  9  7

5  6  8  9  7  8

 

Выходные данные:

Тест 1

Число пересекающихся пар прямоугольников = 3

Тест 1

Число пересекающихся пар прямоугольников = 0

 

 

 

Автор:  В.К. Титов

_____________________________________________________________________

 

 

 

15.2. Второй тур.

 

 

 

Задача А «Натянутые веревки».

 

           В большую доску вбито N гвоздей. Некоторые пары гвоздей связываются веревочками, натянутыми по прямой линии.

           Найти такой вариант связывания гвоздей веревочками, чтобы их суммарная длина была минимальной, при условии, что к каждому гвоздю привязана хотя бы одна веревочка. ( Ограничения:  2≤N≤100).

 

Входные данные. В первой строке каждого теста содержится целое число N. Во второй строке через пробелы следуют N пар чисел, обозначающих координаты точек доски, в которые вбиты гвозди.

Входной файл (стандартный ввод) может содержать несколько тестов. Все тесты заканчиваются признаком конца файла.

 

Выходные данные. Для каждого теста программа должна напечатать минимальную суммарную длину и пары номеров соединенных гвоздей.

 

Пример.

Входные данные:

5

1 1 1 2 2 1 2 3 3 3

5

-1.0 1.0 0.0 0.0 1.0 1.0 –1.0 –1.0 1.0 –1.0

Выходные данные:

Тест 1

Длина веревок = 3

Пары соединенных гвоздей : (1,2) (1,3) (4,5)

Тест 2

Длина веревок = 4.828427

Пары соединенных гвоздей : (1,2) (2,3) (4,5)

 

 

_____________________________________________________________________

 

 

 

 

Задача В «Шахматные фигуры».

 

 

           На шахматной доске размера MxM расставить заданные шахматные фигуры так, чтобы они не били друг друга, или напечатать сообщение, что их расставить невозможно. ( Ограничения:  2≤M≤16).

 

          Входные данные. В строке каждого теста через пробелы следуют 6 чисел:

M K Q R B N,  где M задает размер доски, K – число королей, Q – число ферзей, R – число ладей, B – число слонов, а N – число коней.

Входной файл (стандартный ввод) может содержать несколько тестов. Все тесты заканчиваются признаком конца файла.

 

        Выходные данные. Для каждого теста программа при возможной расстановки фигур должна напечатать квадратную матрицу, изображающую шахматную доску с найденной расстановкой, где пустые клетки обозначаются знаком - , а фигуры соответственно буквами K Q R B N (король, ферзь, ладья, слон, конь). Если расстановка невозможна, напечатать соответствующее сообщение.

 

Пример.

Входные данные:

5 9 0 0 0 0

16 0 17 0 0 0

4 1 1 1 1 0

Выходные данные:

Тест 1

 K-K-K

 -----

 K-K-K

 -----

 K-K-K

Тест 2

Расстановка заданных фигур невозможна.

Тест 3

 K---

 --Q-

 B---

 ---R

_____________________________________________________________________

 

 

 

 

Задача С «Скобки».

 

 

            Задана строка, состоящая из символов открывающих и закрывающих скобок четырех видов: ( ) [ ] < > { } . Определить является ли последовательность скобок в заданной строке правильной.

           Расстановка скобок считается правильной, если,
во-первых, множество всех скобок можно разбить на пары однозначно соответствующих друг другу скобок одного вида, в каждой из которых открывающая скобка расположена левее закрывающей;

во-вторых, предыдущее условие выполняется для любой  подпоследовательности строки, заключенной между открывающей и закрывающей скобками, соответствующими друг другу.

           Если заданная последовательность скобок не является правильной, то указать номер символа в строке, на котором нарушается свойство правильности.

 ( Ограничения:  число символов в строке меньше 80, признаком конца последовательности символов в строке является пробел).

 

            Входные данные. Строка каждого теста содержит только символы указанных скобок и заканчивается пробелом. Входной файл (стандартный ввод) может содержать несколько тестов. Все тесты заканчиваются признаком конца файла.

 

           Выходные данные. Для каждого теста программа должна напечатать сообщение о правильности или неправильности заданной последовательности скобок. Если последовательность неправильна, то указать номер символа, на котором нарушается свойство правильности.

 

Пример.

Входные данные:

({{}[]}<()>)

((({{{[[[<<<>>>]]]]}}})))

Выходные данные:

Тест 1

Скобки расставлены правильно.

Тест 2

Скобки расставлены неправильно.

Нарушение правильности на 19-м символе.

 

 

_____________________________________________________________________

 

 

15.1. Тренировочный тур.

 

 

 

Задача A «Треугольная таблица».

 

          Натуральные числа организованы в таблицу, как показано ниже:

  

        По заданному числу N вывести 8 чисел, его окружающих, в виде матрицы 3*3 . Например:

 

           Примечание. Как видно из примера, для заданных чисел, оказавшихся у границы треугольной таблицы, отсутствующие числа в выводимой матрице заменяются прочерками.

 

           Ограничение: N≤4 000 000 000  .

           Исходные данные. Входной файл (стандартный ввод) состоит из одной строки.

Первое в строке число М  означает число тестов, а далее через пробелы идут М чисел, каждое из которых означает заданное число N для очередного теста.

 

           Например, для вводимой строки:

2  10  7

должен быть следующий результат:

Тест 1 :    N=10

 

-	-	17
-	10	18
5	11	19

 

Тест 2 :    N=7

 

2	6	12
3	7	13
4	8	14

 

 

_____________________________________________________________________

 

 

 

Задача В «Объединение отрезков»

 

      Задано N отрезков на прямой. Концы отрезков задаются парами целых чисел (l, r), где l и r - координаты концов отрезка на оси  Х. Найти суммарную длину всех частей оси Х, покрытых заданными отрезками.

           Ограничения: N≤30, -100000<l≤r<100000.

 

           Исходные данные. В каждой строке входного файла (стандартный ввод) задан отдельный тест: сначала идет число N, а затем N пар координат концов отрезков. Все числа разделены пробелами. Все тесты заканчиваются признаком конца файла.

 

            Результат. Для каждого теста вывести одно число: суммарную длину области, покрытой отрезками.

 

             Пример. Для следующих исходных данных:

 

2 1 2 3 4

3 0 5 1 4 2 3

4 1 1 2 2 3 3 4 4

 

результат должен быть таким:

Тест 1:  2

Тест 2:  5

Тест 3:  0

 

 

_____________________________________________________________________

 

 

 

 

Задача С «Факториал»

 

 

          Факториалом натурального числа N называется произведение всех натуральных чисел от 1 до N и обозначается N! (то есть, N!=1*2*3*…*(N-1)*N). Требуется для заданного двузначного числа N найти точное значение факториала этого числа, то есть распечатать все цифры числа N! .

           Ограничение:  10≤N<100.

 

           Исходные данные. Входной файл (стандартный ввод) состоит из одной строки.

Первое в строке число М  означает число тестов, а далее через пробелы идут М чисел, каждое из которых означает заданное число N для очередного теста.

 

           Например, для вводимой строки:

2  10  25

должен быть следующий результат:

 

Тест 1 :    N=10  10!=3628800

 

Тест 2 :    N=25  25!=15511210043330985984000000

 

 

_____________________________________________________________________

 

 

 

16. Задачи II тура  Московской олимпиады 2002 г.

 

 

 

Задача А «Октаэдр с буквами»

 

                На гранях октаэдра расставлены буквы, по одной букве на каждой из восьми граней.

      Кодом заданной расстановки букв на октаэдре называется последовательность расставленных букв, полученная следующим образом:

выбирается произвольная вершина и инцидентная ей грань;

вокруг выбранной вершины по часовой стрелке обходятся грани, начиная с выбранной, и выписываются в строку расставленные на гранях буквы;

затем октаэдр переворачивается и продолжается выписывание букв с граней обходом по часовой стрелке вокруг противоположной по отношению к выбранной вершине, начиная с грани, смежной  той, на которой кончился обход на предыдущем этапе.

        Например, на рисунке показана проекция октаэдра с расставленными буквами, где большие буквы принадлежат видимым верхним граням, а маленькие буквы  нижним , невидимым граням. Кодом такой расстановки букв на октаэдре может быть следующая последовательность: ABCDdcba.

        Очевидно, что код для заданной расстановки букв на октаэдре определяется не однозначно. Например, кодом указанной выше расстановки может быть также последовательность: ADdabcCB.

         Требуется для заданных двух последовательностей из восьми букв определить, являются ли они кодами одной и той же расстановки букв на октаэдре или нет.

         Примечание. Буквы на октаэдре не обязательно разные, допускаются повторения.

         Ограничения: Буквы для расстановки  используются только заглавные латинские буквы.

          Исходные данные. В каждой строке входного файла (стандартный ввод) задан отдельный тест. В строке каждого теста два слова-кода, разделенные пробелом. 

Все тесты заканчиваются признаком конца файла.

            Результат. Для каждого теста вывести одно слово: ДА, если введенные коды соответствуют одной и той же расстановке букв на октаэдре, или НЕТ, если – не соответствуют.

            Пример. Для следующих исходных данных:

ABCDDCBA  ADDABCCB

XXXXYYYY  XYXYXYXY

результат должен быть таким:

Тест 1: ДА

Тест 2: НЕТ

 

Автор:  В.К. Титов

_____________________________________________________________________

 

 

 

 

Задача B "Перешейки связного графа"

 

 

            Неориентированный граф задается набором ребер, в виде пар произвольных натуральных  чисел, где числа обозначают вершины графа. Граф называется связным, если любые два ребра принадлежат некоторой цепочке графа. Цепочка – это такая последовательность ребер графа, что любые два рядом стоящие в цепочке ребра имеют общую вершину. Перешейком связного графа называется ребро, удаление которого из графа делает граф несвязным.

           Для заданного связного графа перечислить все его ребра, которые являются перешейками.

           Исходные данные. В каждой строке входного файла (стандартный ввод) задается отдельный тест – граф в виде набора натуральных чисел, разделенных пробелами:

Первое число  N – число ребер, далее идет N пар чисел, обозначающих ребра (N<=50).

Например, строка:

3 5 6 7 5 5 9

представляет граф:   

                                   

а строка:

4 11 13 13 15 15 17 17 11

представляет граф:

                                     

      Числа, обозначающие  вершины графа, являются просто их метками, а не порядковыми номерами.

Все тесты заканчиваются признаком конца файла.

       Результат. Для каждого теста вывести набор ребер графа, являющихся перешейками. Если таких ребер нет, вывести сообщение: «Перешейков нет».

Ребра выводить в виде пар вершин, заключенные в скобки.

       Пример. Для следующих исходных данных:

3 5 6 7 5 5 9

5 3 5 2 4 1 2 3 6 3 1

результат может быть таким:

Тест 1:

Перешейков нет

Тест 2:

Перешейки: (1,2), (1,3)

 

 

Автор:  В.К. Титов

_____________________________________________________________________

 

 

 

 

Запасная задача “Степенные ряды”

 

 

 

Для функции

g(x) =1 / [1 – f(x)]

 

найти первые n + 1 коэффициентов разложения b_i в степенной ряд

 

g(x) = b₀ + b₁x¹ + b₂x² + b₃x³ + … ,

 

если f(0) = 0 и известны коэффициенты разложения a_i  для f(x), т.е.

 

f(x) = a₁x¹ + a₂x² + a₃x³ + … .

 

Входом служит цепочка чисел  n, a₁, a_2, … , a_n, разделенных пробелами.

Для простоты считать, что все входные данные целые, а n < 20.

Выходом должна быть цепочка целых  b₀, b₁, … , b_n, разделенных пробелами.

 

Примеры

1. Исходные данные:

5 1 0 0 0 0

    Результат:
1 1 1 1 1 1

2. Исходные данные:

 6 0 1 0 0 0 0

    Результат:
 1 0 1 0 1 0 1

 

 

 

Автор: Г.Б. Рубальский, МГСУ

_____________________________________________________________________