РОССИЙСКАЯ ФЕДЕРАЦИЯ

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ

КОМИТЕТА ПО СОЦИАЛЬНОЙ ПОЛИТИКЕ И КУЛЬТУРЕ г. ИРКУТСКА

МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ГОРОДА ИРКУТСКА

МУНИЦИПАЛЬНОЕ АВТОНОМНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ЛИЦЕЙ ИГУ ГОРОДА ИРКУТСКА

Авторская адаптационная образовательная программа

спецкурса по информатике и ИКТ

для 10-х, 11-х классов

Решение олимпиадных задач по информатике

Составители:

Зубков Олег Владимирович,

к. ф.-м. н., учитель информатики
МАОУ Лицей ИГУ г. Иркутска,

Шеметова Людмила Николаевна,

учитель информатики

МАОУ Лицей ИГУ г. Иркутска

2015 г.

г. Иркутск

ПАСПОРТ

авторская адаптационная образовательная программа

1. Раздел (заполняется составителем программы).
   а) Зубков Олег Владимирович, муниципальное автономное общеобразовательное

учреждение Лицей ИГУ г. Иркутска, ул. Академика Курчатова, 13а, тел. 41-05-35

Шеметова Людмила Николаевна, муниципальное автономное общеобразовательное учреждение Лицей ИГУ г. Иркутска, ул. Академика Курчатова, 13а, тел. 41-05-35

(фамилия, имя, отчество составителя; учреждение, адрес, телефон)

б) адаптационная образовательная программа «Решение олимпиадных задач по информатике», информатика, 68 и 136 часов

(название программы, предметная область, кол-во часов)

в) спецкурс для обучающихся 10 и 11 классов

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

г) ) с 2015 года, на базе МАОУ Лицей ИГУ г. Иркутска

(с какого времени и на базе какого ОО программа используется)

д) адаптационная программа разработана на основе программы спецкурса Олимпиадные задачи по информатике для 10-11 классов. Автор: Абасов Н.В. Зарегистрирована в ЦИМПО, 11.11.2004

(авторская оценка программы, на базе каких образовательных программ/ пособий составлена)

II. Раздел (заполняется администрацией образовательной организации).

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

(оценка программы администрацией ОО, ее востребованность в ОО)

М.П. Руководитель ОО:________________ Е.Ю. Кузьмина «__» ______2015г.

директор МАОУ Лицея ИГУ г. Иркутска

3. Раздел (заполняется методической службой г. Иркутска)

Программа зарегистрирована в МКУ ИМЦРО, дата регистрации ___________ регистр № ______.

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

протокол № _______от _______________

Директор МКУ ИМЦРО Н.И. Яловицкая _________________ «____»_________2015 г.

Пояснительная записка

Программа спецкурса «Решение олимпиадных задач по информатике» рассчитана на 68 (1 час в неделю) в 10-м классе и 136 часов (2 часа в неделю) в 11 классе и дополняет своим содержанием и методами основной курс ОИВТ. В нем рассматриваются и осваиваются сведения из областей информатики и программирования, важные в общеобразовательном и прикладном отношении; формируются навыки и приемы решения задач с использованием готовых и собственноручно разработанных программных средств; развиваются алгоритмическое мышление, информационная культура вообще, культура программирования, в частности; вырабатывается компетентность в использовании компьютерных технологий.

Данный учебный курс рекомендован для использования в 10-11-х специализированных (профильных) классах с углубленным изучением информатики и программирования. Особое внимание уделяется алгоритмизации и программированию задач творческого типа. Предлагаемый курс предназначен для подготовки интересующихся данной тематикой учеников, предварительно уже имеющих начальные навыки работы в одном из языков программирования и желающих писать грамотные, эффективные и правильно скомпонованные программы. В курсе рассматриваются разделы и разбираются задачи самого различного уровня сложности, впрочем, метод "от простого к сложному" является основополагающим. Если сравнивать сложность рассматриваемых задач, то они охватывают достаточно широкий круг от сложных задач школьного и муниципального (городского) уровня, все типы и сложности регионального уровня и заканчивая сравнительно простыми по сложности темами всероссийского уровня олимпиад.

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

ЦЕЛИ КУРСА:

• развитие алгоритмического мышления, способностей к формализации реально протекающих процессов;

• освоение учащимися основных приемов технологии программирования;

• воспитание культуры решения прикладных задач с использованием программных средств и алгоритмических языков высокого уровня;

• развитие нестандартного мышления для решения прикладных и специальных задач повышенной сложности;

• формирование умения понять проблему, оценить ее сложность и наметить пути ее решения;

• развитие навыков работы в команде;

• развитие настойчивости и упорства при достижении поставленной цели и корректировки методов ее достижения.

ЗАДАЧИ КУРСА:

• закрепить навыки программирования, полученные при изучении курса «Информатика и ИКТ»;

• ознакомиться с основными разделами и темами олимпиадных задач по информатике.

• рассмотреть основные подходы к и реализации известных алгоритмов.

• изучить новые, более эффективные по времени работы алгоритмы.

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

• научиться писать программы грамотно, быстро и правильно, уметь их отлаживать и тестировать.

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

УЧЕНИКИ ДОЛЖНЫ ЗНАТЬ:

• основные правила программирования, тестирования и отладки;

• классификацию и свойства базовых алгоритмических конструкций;

• некоторые сложные алгоритмы для эффективного решения олимпиадных задач по информатике;

• структуру и возможности сред программирования и основные особенности работы с ними;

• основные приемы программирования на языке программирования С++;

• особенности проведения современных соревнований по информатике и программированию;

• особенности работы в автоматических проверяющих системах.

УЧЕНИКИ ДОЛЖНЫ УМЕТЬ:

• проводить предварительный анализ задачи;

• разрабатывать алгоритмическую модель решения задачи;

• реализовывать разработанный алгоритм на языке программирования С++;

• проводить отладку программы с помощью и без помощи среды программирования;

• сознательно выбирать структуры данных, оптимальные для решения задач;

• пользоваться возможностями операционной системы, файловых менеджеров, текстовых редакторов, трансляторов, сред программирования для решения олимпиадных задач по информатике;

• анализировать и интерпретировать полученные результаты;

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

Учебно-тематический план (68 часов).

№

Кол-во ч.

Тема урока

Цели урока

Форма урока

Деятельность учащихся

1.

2ч.

Встроенные типы данных языка C++.

Сформировать представление о встроенных типах данных языка С++ и навыки их использования в программах

Практическое занятие

Групповая и индивидуальная работа

2.

4ч.

Работа с файлами. Написание программ, производящих ввод и вывод через файлы.

Сформировать представление о работе с файлами.

Практическое занятие

Групповая и индивидуальная работа

3.

6ч.

Особенности проведения современных олимпиад по информатике и программированию

Сформировать навыки поведения и работы во время современных соревнований по информатике

Лекция с элементами практической работы

Групповая и индивидуальная работа

4.

2ч.

Современные автоматические системы проведения турниров.

Привить навыки самостоятельной работы с ресурсами сети Интернет для подготовки к соревнованиям по программированию

Лекция с элементами практической работы

Групповая и индивидуальная работа

5.

2ч.

Ресурсы сети Интернет для самостоятельной подготовки к олимпиадам по информатике

Сформировать навыки использования массивов в программах

Лекция с элементами практической работы

Групповая и индивидуальная работа

6.

4ч.

Задачи для начинающих

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

Практическое занятие

Групповая и индивидуальная работа

7.

4ч.

Операторы цикла в С++

Знакомство и закрепление навыков работы с циклически повторяющимися операциями, операторами for, while и do while

Практическое занятие

Групповая и индивидуальная работа

8.

4ч.

Основные конструкции в языке C++, массивы и векторы.

Сформировать навыки обработки и хранения больших объемов информации при помощи встроенных средств языка С++

Лекция с элементами практической работы

Групповая и индивидуальная работа

9.

4ч.

Процедуры и функции в языке С++

Сформировать навыки проектирования программы, разбиения ее на подзадачи

Лекция с элементами практической работы

Групповая и индивидуальная работа

10

4ч.

Задачи целочисленной арифметики. Нахождение НОД, алгоритм Евклида.

Научиться работать с простейшими рекурсивными подпрограммами

Практическое занятие

Групповая и индивидуальная работа

11.

4ч.

Задачи целочисленной арифметики. Решето Эратосфена.

Научиться строить и программно обрабатывать простые числа

Практическое занятие

Групповая и индивидуальная работа

12.

4ч.

Понятие сложности и эффективности алгоритма

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

Практическое занятие

Групповая и индивидуальная работа

13.

4ч.

Задачи целочисленной арифметики. Быстрое возведение в степень.

Наглядное сравнение различных по скорости работы алгоритмов возведения в степень

Практическое занятие

Групповая и индивидуальная работа

14.

4ч.

Задачи целочисленной арифметики. Быстрое вычисление чисел Фибоначчи.

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

Практическое занятие

Групповая и индивидуальная работа

15.

4ч.

Эффективные алгоритмы. Дискретный бинарный поиск.

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

Практическое занятие

Групповая и индивидуальная работа

16.

4ч.

Эффективные алгоритмы. Бинарный поиск ответа на множестве вещественных чисел

Познакомиться с алгоритмами «длинной» арифметики.

Практическое занятие

Групповая и индивидуальная работа

17.

4ч.

Контейнер set в С++, динамическое упорядочение

Познакомиться с дополнительными возможностями библиотеки STL в С++

Лекция с элементами практической работы

Групповая и индивидуальная работа

18.

4ч.

Контейнер map в С++, индексация сложными объектами

Познакомиться с дополнительными возможностями библиотеки STL в С++

Лекция с элементами практической работы

Групповая и индивидуальная работа

Учебно-тематический план (136 часов).

№

Кол-во ч.

Тема урока

Цели урока

Форма урока

Деятельность учащихся

1.

4ч.

Сортировка объектов. Квадратичная и быстрая сортировки.

Вспомнить методы квадратичной сортировки, познакомиться с идеей быстрых методов сортировки.

Лекция с элементами практической работы

Групповая и индивидуальная работа

2.

4ч.

Всроенная сортировка в С++, изменение методов сравнения и сортировки.

Познакомиться со встроенной сортировкой в С++

Лекция с элементами практической работы

Групповая и индивидуальная работа

3.

4ч.

Длинная арифметика

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

Практическое занятие

Групповая и индивидуальная работа

4.

4ч.

Разбор строк. Обработка текста

Ознакомление с задачами, возникающими при обработке текста.

Практическое занятие

Групповая и индивидуальная работа

5.

4ч.

Разбор строк. Решение символьных уравнений.

Решение уравнений, заданных в виде набора символов

Практическое занятие

Групповая и индивидуальная работа

6.

4ч.

Жадные алгоритмы.

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

Практическое занятие

Групповая и индивидуальная работа

7.

4ч.

Геометрия на плоскости. Простейшие фигуры.

Метод pair. Хранение и обработка точек и векторов.

Практическое занятие

Групповая и индивидуальная работа

8.

4ч.

Геометрия на плоскости. Прямые.

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

Лекция с элементами практической работы

Групповая и индивидуальная работа

9.

4ч.

Геометрия на плоскости. Скалярное и векторное произведения векторов.

Сформировать навыки работы с различными произведениями векторов.

Лекция с элементами практической работы

Групповая и индивидуальная работа

10.

4ч.

Геометрия на плоскости. Площадь произвольных (в том числе и невыпуклых) многоугольников. Формула Пика.

Научиться вычислять площадь произвольных многоугольников с целочисленными вершинами.

Лекция с элементами практической работы

Групповая и индивидуальная работа

11.

4ч.

Геометрия на плоскости. Работа с углами.

Научиться применять скалярное произведение и встроенные функции С++ для вычисления и сравнения углов на плоскости.

Лекция с элементами практической работы

Групповая и индивидуальная работа

12.

4ч.

Рекурсия, перебор.

Знакомство с переборными задачами, ограничение перебора, рекурсия.

Практическое занятие

Групповая и индивидуальная работа

13.

4ч.

Математическое моделирование.

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

Практическое занятие

Групповая и индивидуальная работа

14.

4ч.

Двумерные массивы и векторы в С++

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

Лекция с элементами практической работы

Групповая и индивидуальная работа

15.

4ч.

Теория графов. Определение и методы задания графов.

Сформировать понятие о графахи методах их представления в программе.

Лекция с элементами практической работы

Групповая и индивидуальная работа

16.

4ч.

Обходы графа.

Познакомиться с методами обхода графа в ширину и в глубину.

Практическое занятие

Групповая и индивидуальная работа

17.

4ч.

Поиск путей и циклов в графе.

Знакомство с задачами на поиск пути и цикла в графе.

Практическое занятие

Групповая и индивидуальная работа

18.

4ч.

Связность и двудольность в графах.

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

Лекция с элементами практической работы

Групповая и индивидуальная работа

19.

4ч.

Топологическая сортировка ациклических графов.

Упорядочение структур с неоднозначным порядком. Ацикличность.

Лекция с элементами практической работы

Групповая и индивидуальная работа

20.

6ч.

Поиск мостов и точек сочленения графа.

Сформировать понятие мост и точка сочленения. Научиться искать данные объекты в графе.

Лекция с элементами практической работы

Групповая и индивидуальная работа

21.

4ч.

Теория графов. Кратчайшие пути. Алгоритм Флойда.

Сформировать понятие кратчайшего пути и методов его поиска.

Лекция с элементами практической работы

Групповая и индивидуальная работа

22.

4ч.

Теория графов. Кратчайшие пути. Алгоритм Дейкстры.

Сформировать понятие кратчайшего пути и методов его поиска.

Лекция с элементами практической работы

Групповая и индивидуальная работа

23.

4ч.

Теория графов. Кратчайшие пути. Алгоритм Форда-Беллмана.

Сформировать понятие кратчайшего пути и методов его поиска.

Лекция с элементами практической работы

Групповая и индивидуальная работа

24.

6ч.

Теория графов. Минимальный каркас. Алгоритмы Прима и Краскала.

Сформировать понятие минимального каркаса и методов его построения для произвольного неотрицательно помеченного графа.

Лекция с элементами практической работы

Групповая и индивидуальная работа

25.

4ч.

Теория графов. Деревья, их обходы. Наименьший общий предок.

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

Лекция с элементами практической работы

Групповая и индивидуальная работа

26.

4ч.

Динамическое программирование. Простейшие задачи.

Сформировать понятие метода решения задач "динамическое программирование".

Практическое занятие

Групповая и индивидуальная работа

27.

4ч.

Динамическое программирование. Двумерная динамика, задача о рюкзаке.

Закрепить понятие "динамическое программирование" на двумерных массивах.

Практическое занятие

Групповая и индивидуальная работа

28.

4ч.

Динамическое программирование. Динамика на деревьях.

Обобщить понятие "динамическое программирование" на деревья.

Лекция с элементами практической работы

Групповая и индивидуальная работа

29.

4ч.

Динамическое программирование по подмножествам.

Задачи на небольшую по экспоненте динамику по перебираемым подмножествам.

Лекция с элементами практической работы

Групповая и индивидуальная работа

30.

6ч.

Динамическое программирование по профилю

Простые идеи динамики по профилю для подсчета числа укаладок домино на прямоугольнике.

Лекция с элементами практической работы

Групповая и индивидуальная работа

31.

4ч.

Структуры данных. Бинарная куча. Priority queue.

Динамически меняющиеся массивы данных. Поддоержание минимального (максимального) элемента множества.

Практическое занятие

Групповая и индивидуальная работа

32.

6ч.

Структуры данных. Дерево отрезков.

Динамически меняющиеся массивы данных. Быстрое получение информации (сумма, минимум, цвет) о любом непрерывном отрезке множества.

Лекция с элементами практической работы

Групповая и индивидуальная работа

Приложение 1

Тема 18: Геометрия на плоскости. Площадь произвольных (в том числе и невыпуклых) многоугольников. Формула Пика.

План занятия "Целые точки. Формула Пика".

Задачи занятия:

1. Ознакомление с формулой Пика.

2. Нахождение числа целых точек на отрезке и периметре.

3. Нахождение площади произвольной фигуры.

Ход занятия

Решим задачу №209 "Целые точки":

Время на тест 1 сек. Память 16 Мб. Сложность 64%.

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

Входные данные. В первой строке входного файла INPUT.TXT содержится N (3<=N<=1000) - число вершин многоугольника. В следующих N строках идут координаты (X_i и Y_i) вершин многоугольника в порядке обхода по часовой стрелке. X_i и Y_i - целые числа, по модулю не превосходящие 10⁶.

Выходные данные. Ваша программа должна вывести в выходной файл OUTPUT.TXT одно число - ответ на задачу.

Примеры.

INPUT.TXT OUTPUT.TXT

4 1

-1 -1

-1 1

1 1

1 -1

INPUT.TXT OUTPUT.TXT

5 16

6 -2

-3 -2

1 6

-1 -1

6 2

На рис. 1 приведен чертеж для второго примера. Жирными точками указаны искомые целые точки, находящиеся внутри многоугольника. Их 16 штук, потому в файл ответа OUTPUT.TXT программа должна выдать 16. Легко видеть, что эти точки расположены внутри фигуры довольно случайно, и установить факт нахождения конкретной целой точки внутри или за пределами фигуры без чертежа достаточно сложно.

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

рис. 1

Формула Пика имеет вид

S=N_in+1/2N_per - 1.

Для начала проверим эту довольно неожиданную формулу на нашем примере. Для фигуры на рисунке площадь S=24.5, N_in=16, N_per=19 (эти точки выделены косыми засечками). Действительно 24.5=16 + 9.5 - 1.

Преобразуем формулу Пика так как нам нужно:

2N_in = 2S - N_per+2.

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

1. по координатам вершин многоугольника найти число целых точек на ее периметре;

2. по координатам вершин многоугольника найти ее площадь.

Для решения задачи 1 разобьем периметр фигуры на отрезки. Пусть нам дан отрезок AB с координатами (X_A ,Y_A) и (X_B ,Y_B). Найти число целых точек на отрезке AB. Здесь нам поможет нахождение наибольшего общего делителя. Действительно, число целых точек (включая вершины) на отрезке с целочисленными вершинами есть

НОД(X,Y) +1, где X=| X_A - X_B | а Y=| Y_A - Y_B|.

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

Для отрезка M₁M₂ X=9, Y=0, НОД(9,0)=9. Число целых точек на нем 10.

Для отрезка M₂M₃ X=4, Y=8, НОД(4,8)=4. Число целых точек на нем 5.

Для отрезка M₃M₄ X=2, Y=7, НОД(2,7)=1. Число целых точек на нем 2.

Для отрезка M₄M₅ X=7, Y=3, НОД(7,3)=1. Число целых точек на нем 2.

Для отрезка M₅M₁ X=0, Y=4, НОД(0,4)=4. Число целых точек на нем 5.

Учтем, что при суммировании каждая вершина многоугольника будет входить в два отрезка и в итоге получим N_per= НОД(| X₁ - X₂ | , | Y₁ - Y₂ |)+ НОД(| X₂ - X₃| , | Y₂ - Y₃ |)+ … + НОД(| X_N - X₁ | , | Y_N - Y₁ |).

Для фигуры на рис. 1: 9+4+1+1+4=19 и это совпадает с N_per.

Вспомним, что НОД можно найти при помощи следующей рекурсивной функции

int NOD (int a, int b){

if (b ==0) return(a); else return NOD(b, a mod b);

}

Таким образом, мы уже можем решить задачу 1.

Для решения второй задачи воспользуемся идеей площади со знаком. Например, решим ее при помощи трапеций. На рис 2. приведен простой пример, позволяющий наглядно проиллюстрировать идею этого метода. Из каждой вершины M_i проводится перпендикуляр на ось OX и получается проекция этой вершины P_i. Далее рассматривается система трапеций M_iM_i+1P_i+1P_i. Это действительно трапеции, у них есть два параллельных основания M_iP_i и M_i+1P_i+1. Если обратиться к рис. 2, то можно заметить, что площадь

рис. 2

треугольника M₁M₂M₃ можно получить как площадь трапеции M₁M₂P₂P₁ минус площадь трапеции M₂M₃P₃P₂ минус площадь трапеции M₃M₁P₁P₃. Здесь полезно заметить, что, так как мы движемся по периметру, то для точки M_N следующей N+1-й точкой будет, очевидно, точка M₁.

В данном случае вместо того, чтобы считать площадь величиной положительной и потом ее отнимать со знаком минус значительно удобнее рассмотреть площадь со знаком и только суммировать получающиеся величины. Тогда если мы идем от точки M_i к точке M_i+1 слева направо, площадь трапеции M_iM_i+1P_i+1P_i считается положительной и если идем справа налево, то площадь трапеции считается отрицательной. Вспомним, что площадь трапеции есть полусумма оснований, умноженная на высоту, но так как нам нужна удвоенная площадь для подстановки в формулу Пика, то будем искать просто сумму оснований, умноженную на высоту. Так как основания со знаком есть величины Y_i, а высота со знаком есть X_i+1 - X_i, то удвоенная площадь со знаком есть величина (X_i+1 - X_i)*( Y_i+1 + Y_i). Осталось просуммировать эти произведения и получить искомую площадь фигуры со знаком. Если обход происходит по часовой стрелке, то эта площадь будет со знаком плюс, если против часовой стрелки, то со знаком минус. На всякий случай, чтобы не ошибиться со знаком, полезно после взятия суммы для полученной величины взять модуль и получить искомую положительную площадь.

Для фигуры на рис.1:

Трапеция M₁M₂P₂P₁ дает (X₂ - X₁)*( Y₂ + Y₁) =(-3-6)*(-2+(-2))=36.

Трапеция M₂M₃P₃P₂ дает (X₃ - X₂)*( Y₃ + Y₂) =(1-(-3))*(6+(-2))=16.

Трапеция M₃M₄P₄P₃ дает (X₄ - X₃)*( Y₄ + Y₃) =(-1-1)*(-1+6)=-10.

Трапеция M₄M₅P₅P₄ дает (X₅ - X₄)*( Y₅ + Y₄) =(6-(-1))*(2+(-1))=7.

Трапеция M₅M₁P₁P₅ дает (X₁ - X₅)*( Y₁ + Y₅) =(6-6)*(-2+2)=0.

Суммируя, получаем 36+16+(-10)+7+0=49, то есть удвоенную площадь 2*S=2*24.5.

Осталось подставить в формулу 2S - N_per+2 полученные в задачах 1 и 2 величины и получить удвоенное количество точек, расположенных строго внутри многоугольника. В файл OUTPUT.TXT нужно выдать это количество, поделенное пополам .

Для нашего примера:

(49 - 19 +2) / 2= 16, что и является правильным ответом.

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

После этого, при помощи какой-либо оболочки (например Сodeblocks) происходит программирование рассмотренного алгоритма и проверка полученной программы на сайте acmp.ru.

Приложение 2

Все предлагаемые ниже задания предлагались на школьных олимпиадах по информатике и программированию различных уровней. Источник заданий acmp.ru/.

1. Задачи для начинающих

Торт

(Время: 1 сек. Память: 16 Мб Сложность: 6%)

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

Помогите Пете решить эту задачу, определив наименьшее число разрезов торта по заданному числу гостей.

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

Входной файл INPUT.TXT содержит натуральное число N - число гостей, включая самого виновника торжества (N <= 1000).

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

В выходной файл OUTPUT.TXT выведите минимально возможное число разрезов торта.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

2

1

2

3

Разворот

(Время: 1 сек. Память: 16 Мб Сложность: 9%)

Дано натуральное число N и последовательность из N элементов. Требуется вывести эту последовательность в обратном порядке.

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

В первой строке входного файла INPUT.TXT записано натуральное число N (N ≤ 10³). Во второй строке через пробел идут N целых чисел, по модулю не превосходящих 10³ - элементы последовательности.

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

В выходной файл OUTPUT.TXT выведите заданную последовательность в обратном порядке.

Пример

№

INPUT.TXT

OUTPUT.TXT

1

3
1 2 3

3 2 1

Клавиатура

(Время: 1 сек. Память: 16 Мб Сложность: 11%)

Для данной буквы латинского алфавита нужно вывести справа стоящую букву на стандартной клавиатуре. При этом клавиатура замкнута, т.е. справа от буквы «p» стоит буква «a», от буквы «l» стоит буква «z», а от буквы «m» - буква «q».

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

Входной файл INPUT.TXT содержит один символ - маленькую букву латинского алфавита.

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

В выходной файл OUTPUT.TXT следует вывести букву стоящую справа от заданной буквы, с учетом замкнутости клавиатуры.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

q

w

2

t

y

3

p

a

4

l

z

5

m

q

Автобусная экскурсия

(Время: 1 сек. Память: 16 Мб Сложность: 14%)

Оргкомитет Московской городской олимпиады решил организовать обзорную экскурсию по Москве для участников олимпиады. Для этого был заказан двухэтажный автобус (участников олимпиады достаточно много и в обычный они не умещаются) высотой 437 сантиметров. На экскурсионном маршруте встречаются N мостов. Жюри и оргкомитет олимпиады очень обеспокоены тем, что высокий двухэтажный автобус может не проехать под одним из них. Им удалось выяснить точную высоту каждого из мостов. Автобус может проехать под мостом тогда и только тогда, когда высота моста превосходит высоту автобуса.

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

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

Во входном файле INPUT.TXT сначала содержится число N (1<=N<=1000). Далее идут N натуральных чисел, не превосходящих 10000 - высоты мостов в сантиметрах в том порядке, в котором они встречаются на пути автобуса.

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

В единственную строку выходного файла OUTPUT.TXT нужно вывести фразу "No crash", если экскурсия закончится благополучно. Если же произойдет авария, то нужно вывести сообщение "Crash k", где k - номер моста, где произойдет авария. Фразы выводить без кавычек ровно с одним пробелом внутри.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

1
763

No crash

2

3
763 245 113

Crash 2

3

1
437

Crash 1

Подмассив массива

(Время: 1 сек. Память: 16 Мб Сложность: 15%)

Пусть задан массив целых чисел а₁, а₂, ..., а_n. Назовем его подмассивом f(i,j) массив, составленный из чисел массива а_i, a_i+1,..., a_j-1, a_j. Напишите программу, которая будет выводить подмассивы массива a.

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

Первая строка входного файла INPUT.TXT содержит число n (1 <= n <= 1000) - количество элементов в массиве а. Во второй строке содержатся числа a₁, a₂, … , а_n разделенные пробелом. Все а_i находятся в диапазоне от -2³¹ до 2³¹ - 1. В третьей строке находится m (1 <= m <= 100) - количество подмассивов, которые необходимо вывести. Следующие m строк содержат пары чисел i_k, j_k (1 <= i_k <= j_k <= n).

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

В выходной файл OUTPUT.TXT для каждой пары (i_k,j_k) в отдельной строке выведите подмассив f(i_k,j_k).

Пример

№

INPUT.TXT

OUTPUT.TXT

1

6
1 2 3 4 5 6
5
1 1
2 6
3 4
5 6
2 4

1
2 3 4 5 6
3 4
5 6
2 3 4

Метро

(Время: 1 сек. Память: 16 Мб Сложность: 16%)

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

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

Во входном файле INPUT.TXT заданы три числа: сначала N - общее количество станций кольцевой линии, а затем i и j - номера станции, на которой Витя садится, и станции, на которой он должен выйти. Станции пронумерованы подряд натуральными числами 1, 2, 3, …, N (1-я станция - соседняя с N-й), N не превосходит 100. Числа i и j не совпадают. Все числа разделены пробелом.

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

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

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

100 5 6

0

2

10 1 9

1

Нули

(Время: 1 сек. Память: 16 Мб Сложность: 16%)

Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц.

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

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

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

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

Пример

№

INPUT.TXT

OUTPUT.TXT

1

00101110000110

4

Треугольник - 3

(Время: 1 сек. Память: 16 Мб Сложность: 17%)

Даны длины трех отрезков. Требуется проверить: могут ли они являться сторонами треугольника.

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

Входной файл INPUT.TXT содержит 3 натуральных числа X Y Z - длины заданных отрезков. Длины отрезков записаны в одной строке через пробел и не превышают 1000.

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

В выходной файл OUTPUT.TXT выведите YES, если отрезки могут быть сторонами треугольника и NO в противном случае.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

1 2 3

YES

2

1 1 5

NO

Детали

(Время: 1 сек. Память: 16 Мб Сложность: 20%)

На клеточном поле N•M расположены две жёсткие детали. Деталь A накрывает в каждой строке несколько (не ноль) первых клеток, деталь B - несколько (не ноль) последних; каждая клетка либо полностью накрыта одной из деталей, либо нет.

Деталь B начинают двигать влево, не поворачивая, пока она не упрётся в A хотя бы одной клеткой. Определите, на сколько клеток будет сдвинута деталь B.

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

В первой строке входного файла INPUT.TXT записано два числа N и M - число строк и столбцов соответственно (1 ≤ N, M ≤ 100). Далее следуют N строк, задающих расположение деталей. В каждой находится ровно M символов "A" (клетка, накрытая деталью A), "B" (накрытая деталью B) или "." (свободная клетка).

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

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно число - ответ на задачу.

Пример

№

INPUT.TXT

OUTPUT.TXT

1

4 6
AA.BBB
A....B
AAA..B
A..BBB

1

Лифт

(Время: 1 сек. Память: 16 Мб Сложность: 20%)

В доме Вилли установили скоростной лифт новой экспериментальной модели. В этом лифте кнопки с номерами этажей заменены двумя другими кнопками. При нажатии на первую кнопку лифт поднимается на один этаж вверх, а при нажатии на вторую - опускается на один этаж вниз.

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

Зная порядок, в котором Дилли нажимал на кнопки лифта, попробуйте определить общее количество этажей в доме Вилли и Дилли.

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

Первая строка входного файла INPUT.TXT содержит последовательность нажатий на кнопки лифта. Символ «1» означает, что была нажата первая кнопка, а символ «2» - что была нажата вторая кнопка. Символы «1» и «2» не разделены пробелами. Количество нажатий не превосходит 100. Гарантируется, что лифт никогда не опускался ниже первого и не поднимался выше последнего этажа.

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

В выходной файл OUTPUT.TXT следует вывести одно число - количество этажей в доме Вилли и Дилли.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

11

3

2

21212

2

3

1221221221221

6

Автобусы - 2

(Время: 1 сек. Память: 16 Мб Сложность: 23%)

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

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

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

В единственной строке входного файла INPUT.TXT записано через пробел 3 натуральных числа - N, M и K, каждое из них не превосходит 10 000.

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

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

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

10 4 7

2

2

10 4 5

0

Время прибытия

(Время: 1 сек. Память: 16 Мб Сложность: 26%)

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

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

Входной файл INPUT.TXT содержит две строки. В первой строке задано время отправления, а во второй строке - время в пути. Время отправления задается в формате «HH:MM», где HH время в часах, которое принимает значение от 00 до 23, ММ - время в минутах, которое принимает значение от 00 до 59. Время в пути задается двумя неотрицательными целыми числами - количество часов и количество минут. Числа разделяются одним пробелом. Количество часов не превышает 120, минут - 59.

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

Выходной файл OUTPUT.TXT должен содержать одну строку - время прибытия поезда на конечную станцию. Формат вывода этого времени совпадает с форматом ввода времени отправления.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

00:00
10 10

10:10

2

01:02
4 6

05:08

3

11:00
22 0

09:00

2. Геометрия

Длина отрезка

(Время: 1 сек. Память: 16 Мб Сложность: 12%)

Отрезок задан координатами своих концевых точек. Требуется вычислить длину этого отрезка.

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

Входной файл INPUT.TXT содержит координаты концов отрезка в формате X₁ Y₁ X₂ Y₂ . Все координаты - целые числа, не превышающие 1000 по абсолютной величине.

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

В выходной файл OUTPUT.TXT выведите длину отрезка с точностью 10^-5.

Пример

№

INPUT.TXT

OUTPUT.TXT

1

3 4 8 4

5

Две окружности

(Время: 1 сек. Память: 16 Мб Сложность: 17%)

На плоскости даны две окружности. Требуется проверить, пересекаются ли они.

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

Входной файл INPUT.TXT состоит из двух строк. На каждой строке записана информация об одной окружности - координаты ее центра x и y (целые числа, по модулю не превосходящие 5000) и радиус (целое число 1 ≤ r ≤ 1000).

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

В выходной файл OUTPUT.TXT выведите «YES», если окружности пересекаются, и «NO» в противном случае.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

0 0 2
0 3 2

YES

2

1 1 1
4 4 1

NO

Суслик и собака

(Время: 1 сек. Память: 16 Мб Сложность: 19%)

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

Требуется написать программу, которая поможет суслику выбрать норку, в которой он может спастись, если таковая существует.

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

Во входном файле INPUT.TXT записано в первой строке два числа - координаты суслика. Во второй строке записаны два числа - координаты собаки. В третьей строке записано число n - число норок на поле. В следующих n строках записаны координаты норок. Все координаты являются целыми числами, по модулю не превышающими 10000, и записываются через пробел. Количество норок не превышает 1000.

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

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

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

10 10
20 20
1
15 15

NO

2

20 20
10 10
2
15 15
25 25

2

Прямоугольник - 2

(Время: 1 сек. Память: 16 Мб Сложность: 27%)

Заданы координаты трех вершин прямоугольника. Необходимо определить координаты четвертой вершины.

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

Во входном файле INPUT.TXT записаны через пробел координаты трех вершин прямоугольника в произвольном порядке в формате x₁ y₁ x₂ y₂ x₃ y₃. Все числа целые, не превосходящие 1000 по абсолютной величине.

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

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

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

0 3 0 0 5 0

5 3

2

1 4 8 3 7 6

2 1

Стрелок

(Время: 1 сек. Память: 16 Мб Сложность: 28%)

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

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

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

Первая строка входного файла INPUT.TXT содержит натуральное число N - количество мишеней (N ≤ 20). Далее идет N строк с информацией о координатах каждой мишени, при этом в каждой строке указывается два целых числа через пробел X и Y (-10 <= X, Y <= 10).

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

В выходной файл OUTPUT.TXT выведите одно целое число - наименьшее количество выстрелов, необходимых для поражения всех мишеней.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

4
2 2
-2 2
-2 -2
2 -2

4

2

6
2 2
-2 2
-2 -2
2 -2
1 1
-1 3

5

Атака летающих тарелок

(Время: 1 сек. Память: 16 Мб Сложность: 36%)

Вы работаете в фирме, занимающейся разработкой компьютерных игр. Сейчас вы занимаетесь разработкой новой компьютерной игры "Атака летающих тарелок". По сюжету игры на планету Зумла приземляются летающие тарелки, и их надо уничтожать. Игрок управляет лазерной пушкой. Для того, чтобы произвести выстрел он указывает две точки на поверхности Зумлы (которая в игре считается плоской), через которые должен проходить лазерный луч (который является прямой).

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

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

Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 30000) - число приземлившихся летающих тарелок. Вторая строка содержит числа xp₁, yp₁, xp₂, yp₂ - координаты точек, через которые проходит лазерный луч. Далее идут n строк, каждая из которых содержит описание одной летающей тарелки в формате x_i y_i r_i, где x_i, y_i - координаты центра, r_i - радиус тарелки. Все числа целые и не превосходят по модулю 10000. Радиусы летающих тарелок - целые и положительные. Летающие тарелки могут касаться и пересекаться.

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

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

Пример

№

INPUT.TXT

OUTPUT.TXT

1

2
0 0 1 1
2 2 100
1000 1000 1

2
1 2

Треугольник

(Время: 1 сек. Память: 16 Мб Сложность: 32%)

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

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

В четырех строках входного файла INPUT.TXT находятся пары целых чисел - координаты точек. Числа в первых трех строках - это координаты вершин треугольника (x₁,y₁), (x₂,y₂), (х₃,у₃), в четвертой строке - координаты тестируемой точки (x₄,у₄). Все координаты не превышают 10000 по абсолютной величине.

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

В выходной файл OUTPUT.TXT необходимо вывести слово «In», если точка находится внутри треугольника и «Out» в противном случае.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

0 0
100 0
0 100
100 100

Out

2

0 0
100 0
0 100
10 10

In

3

0 0
100 0
0 100
50 50

In

4

0 0
100 0
0 100
0 0

In

Площадь многоугольника

(Время: 1 сек. Память: 16 Мб Сложность: 48%)

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти площадь многоугольника. Стороны многоугольника не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.

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

В первой строке входного файла INPUT.TXT находится число N. В следующих N строках находятся пары чисел (Xi,Yi) - координаты точек. Если соединить точки в данном порядке, а также первую и последнюю точки, получится заданный многоугольник. (3 <= N <= 50 000, -20 000 <= Xi,Yi <= 20 000)

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

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

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

4
5 0
0 5
-5 0
0 -5

50.0

2

4
0 4
0 0
3 0
1 1

3.5

Целые точки

(Время: 1 сек. Память: 16 Мб Сложность: 64%)

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

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

В первой строке входного файла INPUT.TXT содержится N (3≤N≤10³) - число вершин многоугольника. В последующих N строках идут координаты (X_i, Y_i) вершин многоугольника в порядке обхода по часовой стрелке. X_i и Y_i - целые числа, по модулю не превосходящие 10⁶.

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

Ваша программа должна вывести в выходной файл OUTPUT.TXT одно целое число - ответ на задачу.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

4
-1 -1
-1 1
1 1
1 -1

1

2

3
0 0
0 2
2 0

0

3. Теория графов

Светофорчики

(Время: 1 сек. Память: 16 Мб Сложность: 25%)

В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до N.

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

Во входном файле INPUT.TXT записано два числа N и M (0 < N <= 100, 0 <= M <= N*(N-1)/2). В следующих M строках записаны по два числа i и j (1 <= i,j <= N), которые означают, что перекрестки i и j соединены тоннелем. Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.

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

В выходной файл OUTPUT.TXT вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке.

Пример

№

INPUT.TXT

OUTPUT.TXT

1

7 10
5 1
3 2
7 1
5 2
7 4
6 5
6 4
7 5
2 1
5 3

3 3 2 2 5 2 3

Скачки

(Время: 1 сек. Память: 16 Мб Сложность: 32%)

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

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

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

Входной файл INPUT.TXT содержит в первой строке два целых числа N (1 <= N <= 100) и K (1 <= K <= N), где N - количество лошадей, принимающих участие в скачках, K - номер лошади, на которую хочет сделать ставку Иван Иванович. Следующие строки содержат по два числа X и Y (1 <= X, Y <= N), обозначающие, что лошадь с номером X быстрее лошади с номером Y. Пары X и Y не повторяются. Набор данных завершается строкой, содержащей единственный ноль. Эту строку обрабатывать не надо.

Гарантируется, что информация, раздобытая Иваном Ивановичем, корректна.

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

Выходной файл OUTPUT.TXT должен содержать слово «Yes», если Иван Иванович уверен в своем выигрыше и «No» в противном случае.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

3 1
1 2
1 3
0

Yes

2

3 2
2 3
0

No

3

4 2
3 1
2 3
0

No

Нить Ариадны

(Время: 1 сек. Память: 16 Мб Сложность: 40%)

Тезею из лабиринта Минотавра помог выйти клубок ниток. Вы можете вместо клубка использовать персональный компьютер.

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

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

Входной файл INPUT.TXT содержит маршрут Тезея, который представлен строкой, состоящей из букв: N, S, W, E и длиной не более 200.

Буквы означают:

N - один "шаг" на север,
S - один "шаг" на юг,
W - один "шаг" на запад,
E - один "шаг" на восток.

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

В выходной файл OUTPUT.TXT записывается аналогично входному файлу найденный обратный путь. Если маршрут неоднозначен, то следует выбирать согласно следующему приоритету: N, E, S, W.

Пример

№

INPUT.TXT

OUTPUT.TXT

1

EENNESWSSWE

NWW

Друзья

(Время: 1 сек. Память: 16 Мб Сложность: 41%)

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

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

В первой строке входного файла INPUT.TXT заданы два числа: N и S (1 <= N <= 100; 1 <= S <= N), где N - количество человек в клубе, а S - номер конкретного человека. В следующих N строках записано по N чисел - матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j - друзья, а 0 - выражает неопределенность.

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

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

Пример

№

INPUT.TXT

OUTPUT.TXT

1

3 1
0 1 0
1 0 1
0 1 0

2

Lines

(Время: 1 сек. Память: 16 Мб Сложность: 44%)

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

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

В первой строке входного файла INPUT.TXT находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика. (2 <= N <= 50)

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

В выходной файл OUTPUT.TXT выведите в первой строке Yes, если движение возможно, или No, если нет. Если движение возможно, то далее следует вывести N строк по N символов - как и на вводе, но букву X, а также все точки по пути следует заменить плюсами. Если решений несколько, выведите любое.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

5
....X
.OOOO
.....
OOOO.
@....

Yes
+++++
+OOOO
+++++
OOOO+
@++++

2

5
..X..
.....
OOOOO
.....
..@..

No

Алгоритм Дейкстры

(Время: 1 сек. Память: 16 Мб Сложность: 47%)

Дан ориентированный взвешенный граф. Для него вам необходимо найти кратчайшее расстояние от вершины S до вершины F.

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

В первой строке входного файла INPUT.TXT записаны три числа: N, S и F (1 <= N <= 100; 1 <= S, F <= N), где N - количество вершин графа. В следующих N строках записаны по N чисел - матрица смежности графа, где число в i-ой строке j-ом столбце соответствует ребру из i в j: -1 означает отсутствие ребра между вершинами, а любое неотрицательное целое число (от 0 до 100) - наличие ребра данного веса . На главной диагонали матрицы всегда записаны нули.

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

В выходной файл OUTPUT.TXT необходимо вывести искомое расстояние или -1, если пути между указанными вершинами не существует.

Пример

№

INPUT.TXT

OUTPUT.TXT

1

3 1 2
0 -1 2
3 0 -1
-1 4 0

6

Грядки

(Время: 1 сек. Память: 16 Мб Сложность: 47%)

Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

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

• никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).

Подсчитайте количество грядок на садовом участке.

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

В первой строке входного файла INPUT.TXT находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. (1 <= N, M <= 200)

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

В выходной файл OUTPUT.TXT выведите количество грядок на садовом участке.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

5 10
##......#.
.#..#...#.
.###....#.
..##....#.
........#.

3

2

5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####

5

Заправки

(Время: 1 сек. Память: 16 Мб Сложность: 49%)

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

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

Во входном файле INPUT.TXT записано сначала число N (1<=N<=100), затем идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Далее идет число M - количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами - номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.

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

В выходной файл OUTPUT.TXT выведите одно число - суммарную стоимость маршрута или -1, если добраться невозможно.

Пример

№

INPUT.TXT

OUTPUT.TXT

1

4
1 10 2 15
4
1 2
1 3
4 2
4 3

3

Сон

(Время: 1 сек. Память: 16 Мб Сложность: 50%)

Любознательный школьник Петя очень любит программировать. Однажды он настолько увлекся этим делом, что уснул прямо за компьютером! Пете приснилось, что он попал в альтернативную реальность. Альтернативная реальность представляет собой прямоугольный лабиринт, который можно изобразить в виде таблицы размером R × C клеток. Чтобы не опоздать школу, Пете нужно найти выход из лабиринта. Начальная позиция Пети обозначается символом 'S', выход из альтернативной реальности - 'E'. За один ход Петя перемещается в одну из четырех смежных клеток (влево, вправо, вниз, вверх). Если клетка занята стеной (символ 'X'), то Петя пройти в нее не может. В некоторых клетках расположены двери с замками одного из четырех цветов ('R', 'G', 'B', 'Y'). Для прохода в эту клетку, необходимо обладать ключом определенного цвета. Так как ключи многоразовые, то одним ключом можно открыть сколь угодно много соответствующих ему замков.

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

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

Первая строка входного файла INPUT.TXT содержит натуральные числа R и C (R,C <=50). Вторая строка теста содержит 4 целых числа P_i, стоимости покупки ключей 'R', 'G', 'B' и 'Y' соответственно (P_i <= 100). Далее следуют R строк, в каждой из которых C символов, описывающих лабиринт. Каждый лабиринт содержит только один символ 'S' и один символ 'E'.

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

В выходной файл OUTPUT.TXT выведите минимальную сумму денег, необходимую для покупки набора ключей, позволяющего пройти к выходу. Если пути к выходу из альтернативной реальности не существует, и Петя обречен проспать уроки, выведите «Sleep».

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

3 7
1 1 1 1
XXXXXXX
XS.X.EX
XXXXXXX

Sleep

2

6 6
1 5 3 1
XXXXXX
XS.X.X
X..R.X
X.XXBX
X.G.EX
XXXXXX

4

1. Динамическое программирование

Только вправо или вниз

(Время: 1 сек. Память: 16 Мб Сложность: 32%)

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

На рис. 1 приведен пример игрового поля 3 x 4, где сплошная окружность показывает положение начала, а пунктирная окружность - цель. Рис. 2 показывает три возможных пути от начала до цели для рассматриваемого примера игрового поля, с удаленными промежуточными числами.

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

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

Входной файл INPUT.TXT содержит в первой строке размеры поля N (1 ≤ N ≤ 70) и M (1 ≤ M ≤ 70). В последующих N строках входного файла, каждая из которых описывает отдельную строку игрового поля, записаны через пробел по M целых чисел - длины шагов из клеток данной строки.

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

Выходной файл OUTPUT.TXT должен содержать одно число - число различных вариантов путей от верхнего левого угла до правого нижнего. Для каждого поля будет менее чем 2³¹ различных путей.

Пример

№

INPUT.TXT

OUTPUT.TXT

1

3 4
2 1 1 2
3 2 1 44
3 1 1 0

3

Гвоздики

(Время: 1 сек. Память: 16 Мб Сложность: 34%)

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

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

В первой строке входного файла INPUT.TXT записано число N - количество гвоздиков (2 <= N <= 100). В следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

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

В выходной файл OUTPUT.TXT нужно вывести единственное число - минимальную суммарную длину всех ниточек.

Пример

№

INPUT.TXT

OUTPUT.TXT

1

6
3 4 12 6 14 13

5

Без двух нулей подряд

(Время: 1 сек. Память: 16 Мб Сложность: 37%)

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

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

Во входном файле INPUT.TXT записаны два натуральных числа N и K в десятичной системе счисления (2 ≤ K ≤ 10; 2 ≤ N; 4 ≤ N+K ≤ 18).

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

В выходной файл OUTPUT.TXT необходимо вывести целое число в десятичной записи - ответ на задачу.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

2 10

90

2

4 2

5

3

6 3

328

Компьютерная игра

(Время: 1 сек. Память: 16 Мб Сложность: 38%)

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

Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться от одного края экрана до другого. При этом при прыжке с одной платформы на соседнюю, у героя уходит |y2-y1| единиц энергии, где y1 и y2 - высоты, на которых расположены эти платформы. Кроме того, у героя есть суперприем, который позволяет перескочить через платформу, но на это затрачивается 3*|y3-y1| единиц энергии. Конечно же, энергию следует расходовать максимально экономно.

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

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

В первой строке входного файла INPUT.TXT записано количество платформ n (1 ≤ n ≤ 30000). Вторая строка содержит n натуральных чисел, не превосходящих 30000 - высоты, на которых располагаются платформы.

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

В выходной файл OUTPUT.TXT запишите единственное число - минимальное количество энергии, которую должен потратить игрок на преодоление платформ (конечно же в предположении, что cheat-коды использовать нельзя).

Пример

№

INPUT.TXT

OUTPUT.TXT

1

3
1 5 10

9

2

3
1 5 2

3

Максимальная подпоследовательность

(Время: 1 сек. Память: 16 Мб Сложность: 38%)

Дана числовая последовательность, требуется найти длину наибольшей возрастающей подпоследовательности.

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

В первой строке входного файла INPUT.TXT записано число N - длина последовательности (1 <= N <= 1000). Во второй строке записана сама последовательность (через пробел). Числа последовательности - целые числа, не превосходящие 10000 по модулю.

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

В выходной файл OUTPUT.TXT требуется вывести наибольшую длину возрастающей подпоследовательности.

Пример

№

INPUT.TXT

OUTPUT.TXT

1

6
3 29 5 5 28 6

3

Энты

(Время: 1 сек. Память: 16 Мб Сложность: 39%)

Энты были созданы в Первоначальную эпоху вместе с другими обитателями Средиземья. Эльфийские легенды гласят, что когда Варда зажгла звёзды и пробудились Эльфы, вместе с ними пробудились и Энты в Великих Лесах Арды.

Когда Энты пришли в Арду, они ещё не умели говорить - этому искусству их обучали Эльфы, и Энтам это ужасно нравилось. Им доставляло удовольствие изучать разные языки, даже щебетание Людей.

Эльфы выработали хорошую технику обучения энтов своему языку. Первый энт, которого обучили эльфы, выучил всего два слова - «tancave» (да) и «la» (нет). Обученный энт выбрал одного старого и одного молодого энта, не умеющих говорить, и обучил их всем словам, которые знал сам. Затем обучение этих двух энтов продолжили сами эльфы. Каждый обучившийся у эльфов энт снова выбирал из неговорящих сородичей одного старого и одного молодого, обучал их всем словам, которые знал, передавал эльфам и так далее.

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

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

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

Входной файл INPUT.TXT содержит натуральные числа K и P (K <= 10⁶; 1 <= P <= 10⁹), записанные через пробел.

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

Мы понимаем, что число энтов, знающих в точности K слов, может быть слишком велико, поэтому просим вывести в выходной файл OUTPUT.TXT лишь количество энтов, знающих ровно K слов, по модулю P.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

4 10

2

2

8 10

5

3

360 1000

179

Фермер

(Время: 1 сек. Память: 16 Мб Сложность: 46%)

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

Необходимо помочь фермеру определить максимальную площадь пашни.

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

В первой строке входного файла INPUT.TXT записано единственное натуральное число N (1 ≤ N ≤ 1000) - длина стороны квадратного участка фермы. Далее, следует N строк, в каждой из которых находится последовательность (без пробелов) нулей и единиц, описывающих ферму.

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

В выходной файл OUTPUT.TXT необходимо вывести максимально возможную площадь пашни.

Пример

№

INPUT.TXT

OUTPUT.TXT

1

7
1101101
1111110
1011100
0011100
1000010
1100111
1001110

9

Автомобильные пробки

(Время: 1 сек. Память: 16 Мб Сложность: 48%)

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

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

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

Входной файл INPUT.TXT содержит одно натуральное число N (N <= 1000).

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

Выходной файл OUTPUT.TXT должен содержать найденное количество автомобильных пробок.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

2

4

2

3

9

Фермер - 2

(Время: 1 сек. Память: 16 Мб Сложность: 60%)

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

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

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

В первой строке входного файла INPUT.TXT записаны два натуральных числа N и M (1 ≤ N,M ≤ 1000) - размеры фермы. Далее, следует N строк, в каждой из которых находится последовательность (без пробелов) из M нулей и единиц, описывающих ферму. Единицы соответствуют свободным для постройки участкам.

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

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

Пример

№

INPUT.TXT

OUTPUT.TXT

1

5 10
1011011111
0111111110
1111111111
1011111111
1101110111

21

Школа танцев

(Время: 1 сек. Память: 64 Мб Сложность: 62%)

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

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

В первой строке входного файла INPUT.TXT задано число n (1 ≤ N ≤ 10⁶). Во второй строке задается описание построенного ряда из мальчиков и девочек - строка из n символов a и b (символ a соответствует девочке, а символ b - мальчику).

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

В единственной строке выходного файла OUTPUT.TXT должно содержаться единственное число - количество вариантов выбора требуемой группы.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

3
bab

2

2

8
abbababa

13

Симпатичные узоры

(Время: 1 сек. Память: 16 Мб Сложность: 66%)

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

Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во первых, каждый новый клиент очевидно захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во вторых, этот узор должен быть симпатичным. Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2x2 метра, полностью покрытого плитками одного цвета. На рисунке 1 показаны примеры различных симпатичных узоров, а на рисунке 2 - несимпатичных.

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

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

В первой строке входного файла INPUT.TXT находятся два положительных целых числа, разделенные пробелом - M и N (1 ≤ M∙N ≤ 30).

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

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

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

2 2

14

2

3 3

322

1. Математическое моделирование

Задача Иосифа Флавия

(Время: 1 сек. Память: 16 Мб Сложность: 19%)

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

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

Например, если N=10, K=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.

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

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

Входной файл INPUT.TXT содержит два натуральных числа N и K. Ограничения: N<=500, K<=100.

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

В выходной файл OUTPUT.TXT нужно вывести номер уцелевшего человека.

Пример

№

INPUT.TXT

OUTPUT.TXT

1

10 3

4

Дни рождения

(Время: 1 сек. Память: 16 Мб Сложность: 27%)

Два одноклассника Петя и Вася родились не ранее 1993 и не позднее 1994 года, причем, Петя старше Васи.

Напишите программу, которая по заданным дням рождения определяет: на сколько дней Петя старше Васи.

Заметим, что 1993 и 1994 года не являются високосными, т.е. в феврале в них ровно 28 дней.

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

Входной файл INPUT.TXT содержит дату рождения Пети в первой строке и дату рождения Васи во второй. Даты заданы в формате «ДД.ММ.ГГ», например, строка 06.02.93 означает дату рождения 6 февраля 1993 года.

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

В выходной файл OUTPUT.TXT выведите единственное число - искомое количество дней.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

01.01.93
02.01.93

1

2

05.02.94
05.03.94

28

Жук

(Время: 1 сек. Память: 16 Мб Сложность: 30%)

Петя нашел в Интернете по адресу buglab.ru игру-головоломку "Жук", в которой от участников требуется построить для жука лабиринт таким образом, чтобы жук как можно дольше искал выход.

Жук всегда начинает свое движение с левого верхнего угла, а выход всегда находится в правом нижнем. Жук движется не оптимально, а следующим образом: он идет туда, где еще не был, либо был там реже. Т.е. проходя каждую клетку лабиринта, жук запоминает: сколько раз он был в этой клетке и при обдумывании направления своего движения в какой то конкретный момент он смотрит: сколько раз он был в клетке снизу, сколько справа, сколько слева и сколько сверху и движется туда, где он был меньше раз. Если таких направлений несколько и одно из них совпадает с текущим направлением движения, то он не меняет направления, иначе он движется согласно следующим приоритетам: вниз, направо, вверх, налево. Т.е. если минимальное число посещений сразу справа и слева (а двигался он при этом вверх или вниз), то жук идет направо, т.к. у "направо" приоритет выше. Следует заметить, что двигаясь по данному алгоритму жук всегда достигнет выхода в том случае, когда выход существует.

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

Конструктор лабиринта

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

Входной файл INPUT.TXT в первой строке содержит разделенные пробелом целые числа N и M - количество строк и столбцов в лабиринте (4 <= N, M <= 100). Далее следует N строк, содержащих данные лабиринта построчно. Каждая строка содержит M символов - клетки лабиринта текущей строки, где символ "@" обозначает присутствие стены, а символ пробела - пустое пространство. Гарантируется, что граница лабиринта окружена стеной. Предполагается, что жук начинает свое движение из координаты (2, 2) и заканчивает в координате (M-1, N-1), подразумевается, что в этих координатах нет стен.

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

В выходной файл OUTPUT.TXT выведите количество движений жука, если спасительный маршрут для жука существует, и -1 в противном случае.

Примеры

¹

INPUT.TXT

OUTPUT.TXT

1

6 6
@@@@@@
@ @
@ @
@ @ @@
@ @ @
@@@@@@

20

2

8 30
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ @ @ @@@@ @ @ @@@@ @@ @
@ @ @@ @ @ @ @ @ @ @
@ @ @ @ @@ @@ @@ @@
@ @ @ @@
@ @ @@ @ @ @@@ @ @ @ @
@ @ @ @ @ @ @@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

630

3

4 4
@@@@
@ @@
@@ @
@@@@

-1

Сообщество роботов

(Время: 1 сек. Память: 16 Мб Сложность: 30%)

Сообщество роботов живет по следующим законам:

• один раз в начале года они объединяются в группы по три или пять роботов;

• за год группа из трех роботов собирает 5 новых, а группа из 5 роботов - 9 новых;

• роботы объединяются так, чтобы собрать за год наибольшее количество новых роботов;

• каждый робот живет ровно три года после сборки.

В начале первого года было K роботов и все они были только что собраны.

Требуется написать программу, которая найдет количество роботов в начале N-го года.

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

Входной файл INPUT.TXT содержит записанные через пробел числа K (1 <= K <= 500) и N (1 <= N <= 100).

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

Выходной файл OUTPUT.TXT должен содержать одно число - количество роботов в начале N-го года. Количество роботов меньше, чем 2³¹.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

3 2

8

2

8 2

22

Шашки

(Время: 1 сек. Память: 16 Мб Сложность: 45%)

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

Напишите программу, которая выведет положение шашек на доске после выполнения описанных ходов.

Игра происходит на стандартной доске (8х8), которая располагается так, что у игрока, играющего белыми, левая нижняя клетка является черной, и с нее начинается нумерация как строк, так и столбцов. Строки доски нумеруются числами от 1 до 8, столбцы - латинскими буквами от a до h.

В начале игры каждый из двух игроков имеет по 12 шашек своего цвета (белого или черного соответственно). Белые шашки располагаются на клетках a1, a3, b2, c1, c3, d2, e1, e3, f2, g1, g3, h2. Черные шашки располагаются на клетках a7, b6, b8, c7, d6, d8, e7, f6, f8, g7, h6, h8.

Игроки совершают ходы по очереди. Игрок, играющий белыми, ходит первым.

Шашки в процессе игры бывают двух видов: обычная шашка и дамка. В начале игры все шашки обычные. Белая шашка становится дамкой, если она оказывается в строке 8. Соответственно, черная шашка становится дамкой, если она оказывается в строке 1.

Шашка может совершать ходы двух типов:

1. Простой ход заключается в перемещении одной из шашек на одну клетку вперед по диагонали. Например, белая шашка с e3 может сходить на d4 или f4 (если соответствующая клетка свободна). А черная шашка с e3 может сходить на d2 или f2.

2. Рубка заключается в том, что шашка перепрыгивает через шашку (или дамку) противника, находящуюся в диагонально соседней с ней клетке при условии, что следующая клетка этой диагонали свободна. Шашка противника, которую срубили, убирается с доски. Если сразу после окончания рубки та же самая шашка может продолжить рубку, она ее продолжает этим же ходом. Рубка возможна в любом из 4-х диагональных направлений. Если в процессе рубки шашка оказывается в 1-й строке (для черных) или в 8-й (для белых), она становится дамкой.

Дамка может совершать следующие ходы:

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

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

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

В первой строке входного файла INPUT.TXT записано одно число N - количество ходов, которое было сделано с начала партии. Это количество не превышает 1000.

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

Простой ход записывается в виде <начальная клетка>-<конечная клетка>. Например, ход с c3 на d4 записывается как c3-d4.

Рубка записывается в виде <начальная клетка>:<клетка после рубки>. Если рубка продолжается, то ставится еще одно двоеточие, и записывается клетка, где окажется шашка после следующей рубки и т.д. Например, e3:c5:e7 (шашка, изначально расположенная на e3, рубит шашку на d4 и оказывается на c5, после чего рубит шашку на d6 и оказывается на e7).

Рубка a1:h8 может быть осуществлена только дамкой (например, дамка с a1 рубит шашку, стоящую в c3, и заканчивает ход в h8). Рубка дамкой может быть и такой a1:d4:f6:h4 (дамка рубит шашку, стоящую на b2, затем продолжает рубку и рубит шашку на e5, и, наконец, рубит шашку на g5). При этом после каждой рубки указывается клетка, на которой останавливается дамка перед следующей рубкой.

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

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

В выходной файл OUTPUT.TXT выведите изображение доски с расположенными на ней шашками. В первой строке выходного файла должна быть выведена 8-я строка доски, во второй - 7-я и т.д. В каждой строке должно быть ровно 8 символов, описывающих клетки столбцов с a по h.

Белая клетка должна быть изображена символом "." (точка), пустая черная клетка - символом "-" (минус). Черная клетка, в которой стоит белая шашка - символом "w" (маленькая латинская буква w), а клетка с белой дамкой - символом "W" (заглавная латинская буква W). Аналогично клетка с черной шашкой должна быть изображена символом "b" (маленькая латинская буква b), а клетка с черной дамкой - символом "B" (большая латинская буква B).

Пример

№

INPUT.TXT

OUTPUT.TXT

1

3
c3-d4
f6-e5
d4:f6

.b.b.b.b
b.b.b.b.
.b.b.w.b
-.-.-.-.
.-.-.-.-
w.-.w.w.
.w.w.w.w
w.w.w.w.

Игра «Пуговицы»

(Время: 0,5 сек. Память: 16 Мб Сложность: 48%)

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

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

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

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

Во входном файле INPUT.TXT записано одно натуральное число K (1 ≤ K ≤ 10⁸) - общее количество пуговиц.

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

В выходной файл OUTPUT.TXT необходимо вывести целое число L (2 ≤ L < K) - максимальное количество пуговиц, которое можно взять за один ход, обеспечивающее победу второму игроку. Если таких чисел несколько, то следует вывести наименьшее из них. Если таких чисел нет, то следует вывести число 0.

Примеры

№

INPUT.TXT

OUTPUT.TXT

1

3

2

2

26

12

3

31

30

Литература

1. С. А. Абрамов, Г. Г. Гнездилова, Е. Н. Капустина, М. И. Семон. Задачи по программированию. Москва, Изд-во Наука, 1988 г.

2. Л. Залогова, М. Плаксин, С. Русаков и др. Задачник - практикум. Москва, Лаборатория Базовых Знаний, 1999 г.

3. Андреева Е., Фалина И. Информатика: Систем счисления и компьютерная арифметика. М.: Лаборатория Базовых Знаний, 1999. - 256 с.

4. Ахо А., Дж. Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы -М.: Издательский дом "Вильямс", 2000

5. Антонов Ю.С. Олимпиадные задачи по информатике с математическим содержанием // Информатика и образование. - 2000. - №9. - С. 59-60.

6. Вирт Н. Алгортимы и структуры данных. -М.: Мир., 1989.

7. Казиев В.М. Развивающие задачи // Информатика и образование. - 1998. - №2. - С.79-83.

8. Кирюхин В.М. Информатика. Всероссийские олимпиады. -М.: Просвещение, -2008.

9. Кирюхин В.М., Лапунов А.В., Окулов С.М. Задачи по информатике. Международные олимпиады 1989-1996 гг. - М.: ABF, 1996. - 272 с.

10. Окулов С.М., Пестов А.А. 100 задач по информатике. Киров: Изд-во ВГПУ, 2000. - 272 с.

11. Окулов С.М., Пестов А.А., Пестов О.А. Информатика в задачах. - Киров: Изд-во ВГПУ, 1998. - 343 с.

12. Олимпиады по информатике 1999: Сб. задач/ Под ред. Н.Л. Андреевой. - Саратов: Изд-во Сарат. ун-та, 1999. - 48 с.

13. Прохоров В.В. Олимпиадные задачи по информатике // Информатика и образование. - 1991. - №3. - С. 67-75.

14. Чернов А.В. и др. Московские студенческие командные Олимпиады по программированию (сборник задач) / МГУ. - М., 1999. - 72 с.

15. Шестаков А.П. Задачи на длинную арифметику // Информатика и образование. - 6. Кнут Д.Э. Искусство программирования. Том 1. Основные алгоритмы. - М.: Вильямс, 2010. - 720 с.

16. Окулов С.М. Программирование в алгоритмах. - М.: БИНОМ. Лаборатория знаний, 2007. - 384 с.

17. Скиена С.С., Ревилла М.А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям. - М.: КУДИЦ-ОБРАЗ, 2005. - 416 с.

18. Долинский М.С. Решение сложных и олимпиадных задач по программированию. - СПб.: Питер, 2006. - 366 с.

19. Меньшиков Ф.В. Олимпиадные задачи по программированию. - СПб.: Питер, 2006. - 315 с.

20. Порублев И.Н., Ставровский А.Б. Алгоритмы и программы. Решение олимпиадных задач. - М.: Вильямс, 2007. - 480 с.

21. Московские олимпиады по информатике / Под ред. Е.В. Андреевой, В.М. Гуровица и В.А. Матюхина. - М.: МЦНМО, 2006. - 256 с.

22. Московские олимпиады по информатике 2002-2009 / Под ред. Е.В. Андреевой, В.М. Гуровица и В.А. Матюхина. - М.: МЦНМО, 2009. - 416 с.

23. Кирюхин В.М. Методика проведения и подготовки к участию в олимпиадах по

информатике. Всероссийская олимпиада школьников. - М.: БИНОМ. Лаборатория знаний, 2012. - 280 с.

24. Ярославские олимпиады по информатике. Сборник задач с решениями. - М.: БИНОМ. Лаборатория знаний, 2010. - 408 с.

25. Русаков С.В. Олимпиады по базовому курсу информатики. - М.: БИНОМ. Лаборатория знаний, 2009. - 352 с.

26. Лебедев А.Б. Сборник задач по алгоритмизации и программированию для подготовки к ЕГЭ (с решениями). - М.: Феникс, 2010. - 448 с.

27. Брудно А.Л. Каплан Л.И. Московские олимпиады по программированию. -М.: Наука, гл. ред. физю-матю лит., 1990.

28. Кнут Д. Искусство программирования для ЭВМ. Т. 1-3. -М.: Вильямс, 2000.

29. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. -М.: МЦНМО, 1999.

30. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978.

31. Рейнгольд Э. Нивельгельт Ю. Део Н. Комбинаторные алгоритмы: теория и практика. -М.: Мир, 1980.

32. Бьерн Страуструп - Программирование. Принципы и практика использования C++. -М.: Вильямс, 2011. - 1248 с.

33. Стефан Р. Дэвис - С++ Для чайников. - М.: Вильямс, 2003 . - 336 с.

34. Прата С. - Язык программирования C++. 6 Издание. - М.: Вильямс, 2011 . - 1244 с.

35. Литвиненко Н. А. - Технология программирования на С++. - СПб.: БХВ-Петербург, 2010.- 281 с.

Интернет-ресурсы

1. acmp.ru/

2. acm.timus.ru/

3. codeforces.ru

4. acm.mipt.ru/

5. habrahabr.ru/

6. e-maxx.ru/