Программа дополнительных занятий по программированию

Раздел Информатика
Класс 10 класс
Тип Рабочие программы
Автор
Дата
Формат doc
Изображения Есть
For-Teacher.ru - все для учителя
Поделитесь с коллегами:

РАССМОТРЕНО

на заседании кафедры информатики и ИКТ

и рекомендовано к утверждению

Протокол № 6 от 21.05.2015 г.

Зав. кафедрой ___________М.А. Нехорошева


УТВЕРЖДАЮ

Директор МБУ лицея №51

____________ И.В. Щелакова

Приказ № _____ - ОД от ____________г.










Дополнительная образовательная программа по информатике


«Методы решения олимпиадных задач по программированию»



Возраст обучающихся: 10-11 класс

Срок реализации : 2 года







Составила программу:

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

Нехорошева М.А.















Тольятти 2015 г.

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

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

Программа составлена на основе примерной программы олимпиадной информатики, разработанной В.М. Кирюхиным , Председателем ЦПМК по информатике Всероссийских олимпиад школьников МОН РФ (2009 год) с учетом Государственного образовательного стандарта по предмету «Информатика» (Приказ Минобразования 2004 года и Приказ МОН РФ 2005 года) с перспективой стандарта третьего поколения для профильной ступени школьного образования (10-11 классы), а также на основе структуры современного содержания олимпиад по информатике. Программа отражает постоянно растущие требования к участникам олимпиады в освоении наиболее важных разделов информатики с учетом развития олимпиадного движения. Срок реализации программы - 2 года, объем аудиторных часов - 68/136. Что позволяет учащимся выбрать курс - 1 час в неделю или расширенный - 2 часа в неделю.

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

  • дидактическая единица без символа «*», соответствует основному уровню сложности для 10-11 классов, и знание этих дидактических единиц позволяет учащимся проявлять олимпиадный уровень при участии в муниципальных и региональных этапах олимпиад, обеспечивает достижение продуктивного уровня требований к участнику олимпиад по информатике, позволяет подойти к поиску оптимальных решений олимпиадных заданий и обеспечивает им возможность технологично представить свои идеи;

  • символ «*» означает, что дополнительное изучение этих дидактических единиц формирует у школьников устойчивые профильный умения в области олимпиадной подготовки для учащихся 10-11 классов, открывает перед участником олимпиадного состязания возможность проявить свой творческий потенциал на высоком уровне представления решений олимпиадных заданий и позволяет сформировать портфолио достижений такого учащегося на уровне дипломов победителей и призеров региональных и заключительных этапов всероссийской олимпиады школьников по информатике.

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

  1. Математические основы информатики

    1. Функции, отношения и множества

      1. Функции, обратная функция, композиция

      2. Отношения (рефлексивность, симметричность, транзитивность, эквивалентность, лексикографический порядок)

      3. Множества (диаграммы Венна, дополнения, декартовы произведения)

      4. Вполне упорядоченные множества *

      5. Мощность и счетность *

    2. Основные геометрические понятия

      1. Точка, прямая, отрезок, вектор, угол

      2. Декартовы координаты в евклидовом пространстве

      3. Евклидово расстояние

      4. Векторное и скалярное произведение на плоскости

      5. Треугольник, прямоугольник, многоугольник

      6. Выпуклые многоугольники

    3. Основы логики

      1. Логические переменные, операции, выражения

      2. Таблицы истинности

      3. Булевы функции

      4. Формы задания и синтез логических функций

      5. Преобразование логических выражений

      6. Минимизация булевых функций *

      7. Основные законы логики суждений*

      8. Логика предикатов *

    4. Основы вычислений

      1. Основы вычислений:

  • Правила суммы и произведения

  • Арифметические и геометрические прогрессии

  • Числа Фибоначчи

  • Принцип включения-выключения *

      1. Рекуррентные соотношения

      2. Матрицы и действия над ними *

    1. Основы теории чисел

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

      2. Деление с остатком

      3. Наибольший общий делитель

      4. Взаимно простые числа

      5. Делимость. Кольцо вычетов по модулю *

    2. Основы комбинаторики

      1. Перестановки, размещения и сочетания:

  • Основные определения

  • Тождество Паскаля

  • Биномиальная теорема

      1. Коды Грея: подмножества, сочетания, перестановки *

      2. Таблицы инверсий перестановок *

      3. Разбиения на подмножества. Числа Стирлинга *

      4. Скобочные последовательности *

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

      1. Типы графов

      2. Маршруты и связность

      3. Операции над графами

      4. Деревья

      5. Остовные деревья

      6. Раскраска графов

      7. Эйлеровы и гамильтоновы графы

      8. Покрытия и независимость *

      9. Укладка графов. Плоские (планарные) графы *

      10. Двусвязность графа. Мосты, блоки, точки сочленения *

      11. Связь ориентированных ациклических графов и отношений порядка. Транзитивное замыкание *

      12. Двудольные графы *

      13. Потоки и сети *

    2. Основы теории вероятностей

      1. Понятие вероятности и математического ожидания. Аксиомы теории вероятностей *

      2. Формула полной вероятности и формула Байеса. Условное математическое ожидание *

    3. Основы теории игр

      1. Понятие игры и результата игры

      2. Простейшие игры и стратегии

      3. Игры на матрицах *

  1. Разработка и анализ алгоритмов, программирование

    1. Алгоритмы и их свойства

      1. Понятие алгоритма

      2. Концепции и свойства алгоритмов

      3. Запись алгоритма на неформальном языке

    2. Структуры данных

      1. Простые базовые структуры

      2. Множества

      3. Последовательности

      4. Списки

      5. Неориентированные графы

      6. Ориентированные графы

      7. Деревья

      8. Пирамида и дерево отрезков *

    3. Основы анализа алгоритмов

      1. Нотация О большое

      2. Стандартные классы сложности

      3. Асимптотический анализ поведения алгоритмов в среднем и крайних случаях

      4. Компромисс между временем и объемом памяти
        в алгоритмах *

      5. Использование рекуррентных отношений для анализа рекурсивных алгоритмов *

    4. Алгоритмические стратегии

      1. Алгоритмы полного перебора

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

      3. Алгоритмы "разделяй и властвуй" *

      4. Перебор с возвратом *

      5. Эвристики *

    5. Рекурсия

      1. Понятие рекурсии

      2. Рекурсивные математические функции

      3. Простые рекурсивные процедуры

      4. Реализация рекурсии

      5. Стратегия "разделяй и властвуй" *

      6. Рекурсивный перебор с возвратами *

    6. Фундаментальные вычислительные алгоритмы

      1. Простые численные алгоритмы

      2. Классические комбинаторные алгоритмы

      3. Алгоритмы с подмножествами: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего (прибавление и вычитание единицы)

      4. Алгоритмы с сочетаниями и перестановками: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего.

      5. Алгоритмы последовательного и бинарного поиска

      6. Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками)

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

      8. Алгоритмы сортировки за время O(N log N) (быстрая сортировка, пирамидальная сортировка,
        сортировка слиянием) *

      9. Цифровая сортировка *

      10. Алгоритм вычисления номера слова в лексикографически упорядоченном множестве перестановок его символов *

      11. Арифметика многоразрядных целых чисел *

    7. Числовые алгоритмы

      1. Разложение числа на простые множители

      2. Решето Эратосфена

      3. Алгоритм Евклида

      4. Расширенный алгоритм Евклида. Способы реализации алгоритма без деления *

      5. Решение линейных сравнений с помощью алгоритма Евклида *

      6. Эффективная реализация решета Эратосфена (O(n)) *

      7. Эффективная проверка числа на простоту *

      8. Быстрые алгоритмы разложения чисел на простые множители. Ро-эвристика *

    8. Алгоритмы на строках

      1. Поиск подстроки в строке. Наивный метод

      2. Алгоритмы поиска подстроки в строке за O(N+M) *

      3. Периодические и циклические строки *

      4. Алгоритм поиска нескольких подстрок за линейное время *

    9. Алгоритмы на графах

      1. Вычисление длин кратчайших путей в дереве

      2. Обход графа в ширину и в глубину

      3. Способы реализации поиска в ширину ("наивный" и с очередью)

      4. Проверка графа на связность

      5. Алгоритмы поиска кратчайшего пути во взвешенных графах

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

      7. Циклы отрицательной длины - критерий наличия, поиск *

      8. Задача о синхронизации времени и задача о системе неравенств *

      9. Алгоритм поиска эйлерова цикла (в том числе лексикографически минимального) *

      10. Нахождение транзитивного замыкания графа *

      11. Алгоритмы нахождения взвешенных остовных деревьев*

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

      13. Алгоритм нахождения максимального паросочетания и минимального вершинного покрытия в двудольном графе *

      14. Поиск максимального потока в сети *

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

      1. Основная идея динамического программирования. Рекурсивная реализация и развертывание в цикл.

      2. Задачи с монотонным направлением движения в таблице

      3. Задача о рюкзаке - решение методом динамического программирования

      4. Оптимизация решения задачи динамического программирования на примере задачи о рюкзаке (исключение лишних параметров) *

      5. Восстановление решения в задачах динамического программирования *

      6. Общая схема решения задач динамического программирования *

    11. Алгоритмы теории игр *

      1. Динамическое программирование и полный перебор как методы решения игровых задач. Игры на ациклическом графе *

      2. Оценка позиций. Альфа-бета отсечение *

    12. Геометрические алгоритмы

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

      2. Представление точек, прямых и отрезков на плоскости

      3. Нахождение расстояний между объектами на плоскости *

      4. Алгоритмы определения пересечения отрезков на плоскости *

      5. Алгоритмы вычисления площади многоугольника с заданными координатами вершин. Случай целочисленной решетки (формула Пика) *

      6. Алгоритмы построения выпуклой оболочки (алгоритмы Грэхема и Джарвиса) *

      7. Окружности на плоскости, пересечение их с другими геометрическими объектами *

      8. Эффективный алгоритм нахождения пары ближайших точек на плоскости *

СОДЕРЖАНИЕ КУРСА

Количество часов в неделю: 1/2 час в неделю, всего 68/136 учебных часов.

Образовательная область: «Информатика».

Профили: информационно-технологический.

ЦЕЛЬ И ЗАДАЧИ

Цели курса:

  • помочь ученикам изучить и освоить современные методы решения олимпиадных задач по информатике и программированию. Это будет очень способствовать развитию общего уровня учеников и придаст им смелости участвовать и побеждать в олимпиадах по информатике и программированию;

  • компьютерное моделирование процессов.

  • подготовка учащихся к обучению в ВУЗах по следующим специализациям и направлениям:

      • информатика и вычислительная техника;

      • информатика и системы управления;

      • системы компьютерной безопасности;

  • системный анализ и исследование операций (и др.).

Задачи курса:

Достижение цели предполагает решение следующих задач:

  • Изучение синтаксиса языка С++;

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

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

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

  • подготовка к соревнованиям по олимпиадному программированию

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

  • настраивать окружение интегрированной среды в соответствии с решаемой задачей;

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

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

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

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

ОРГАНИЗАЦИЯ УЧЕБНОГО ПРОЦЕССА

Методические особенности программы

Учебно-методический комплекс предусматривает организацию учебного процесса в двух взаимосвязанных и взаимодополняющих формах:

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

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

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

Виды и формы контроля знаний, умений и навыков:

  • индивидуальные задания;

  • компьютерное тестирование;

  • контрольное задание;

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

Способы оценки достижений:

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

  • результаты участия в олимпиадах, конкурсах и НОУ.

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

Требования к уровню подготовки:

В результате изучения курса учащиеся должны:

знать:

  • Типовые алгоритмы и задачи, решаемые с их помощью;

  • Базовые алгоритмы решения задач.

уметь:

  • Разработать алгоритм решения поставленной задачи средней сложности и составить реализацию этого алгоритма на языке программирования С++;

  • Владеть большой алгоритмической базой;

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

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

  • Настраивать окружение интегрированной среды в соответствии с решаемой задачей;

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

ОСНОВНОЕ СОДЕРЖАНИЕ

Типовые алгоритмы и задачи, решаемые с их помощью. Целочисленная арифметика. Простые числа. Числа Мерсенна. Числа Ферма. Совершенные числа. НОК и НОД. Числа Фибоначчи. Алгоритмы с простыми числами. Операции со сверхбольшими числами. Длинная арифметика. Формы хранения длинных чисел. Чтение, выводи сравнение. Сложение, вычитание и умножение. Деление длинного на короткое. Реализация длинной арифметики на С++. Типовые алгоритмы обработки одномерных массивов. Алгоритмы сортировки. Типовые алгоритмы обработки двумерных массивов. Метод вложенных матриц. Алгоритмы на графах. Комбинаторика. Формирование комбинаторных групп из N по К (К - от 1 до N). Динамическое программирование. Перестановки. Понятие перестановки. Перебор перестановок в C++. Лексикографический перебор перестановок. Алгоритмы перебора перестановок. Куча - структура данных. Определение кучи. Просеивание элемента (Heapify). Базовые операции при работе с кучей. Пирамидальная сортировка (HeapSort). STL - Standard Template Library. STL и шаблоны в C++. Пара (pair). Линейный массив (vector). Стек (stack). Очередь (queue). Дек (deque). Очередь с приоритетами (priority_queue). Строка (string). Множество (set). Ассоциативный массив (map). Алгоритмы (algorithm). Комбинаторика. Размещения. Перестановки. Сочетания. Вычисление сочетаний. Субфакториал. Вычислительная геометрия. Геометрические объекты. Понятие вектора. Скалярное и векторное произведение векторов. Псевдоскалярное произведение векторов. Полярная система координат. Поворот точки на плоскости. Уравнение прямой на плоскости. Теорема Пика. Длина объединения отрезков на прямой Проверка пересечения двух отрезков. Пересечение окружности и прямой. Пересечение двух окружностей. Площадь многоугольника. Принадлежность точки многоугольнику. Методы Джарвиса и Грэхема построения выпуклой оболочки. Строки. Определения. Префикс-функция. Z-функция. Реализация построения префикс-функции и Z-функции. Алгоритм Кнута-Морриса-Пратта. Количество различных подстрок в строке. Алгоритм Манакера. Сжатие строки. Полиномиальный хеш. Кольцо вычетов. Полиномиальный хеш. Сравнение строк с помощью хешей. Подсчет различных строк. Алгоритм Рабина-Карпа. Вычисление Z-функции. Поиск всех палиндромов в строке. Лексикографически минимальный сдвиг. Структуры данных. Базовые операции над массивом. Sqrt-декомпозиция. Дерево Фенвика. Двумерное дерево Фенвика. Sparse Table. Дерево отрезков. Теория графов. Понятие графа. Определения и виды графов. Способы представления графа. Матрица весов. Список дуг. Описание Бержа. Список смежности. Поиск в глубину. Определение предка вершины в дереве. Подсчет компонент связности. Поиск цикла в графе. Топологическая сортировка. Поиск в ширину. Алгоритм Флойда. Алгоритм Форда-Беллмана. Алгоритм Дейкстры. Минимальный остов. Свойства минимальных остовов. Алгоритм Прима. Алгоритм Крускала. Система непересекающихся множеств. Эйлеров цикл и путь. Сильная связность графа. Поиск компонент сильной связности. Поиск мостов. Двудольный граф. Проверка на двудольность и разбиение на доли. Поиск максимального паросочетания. Алгоритм Куна. Венгерский алгоритм.

Учебно-тематический план

2 часа в неделю

№ п/п

Тема

Количество часов

Примечание

Вводное занятие. Олимпиадное движение в России

1


    Этапы решения олимпиадной задачи: формализация условия задачи, выбор метода решения задачи. Пример олимпиадной задачи.

    1

    Реализация решения задачи «А+В»

    1


      Целочисленная арифметика

      1


        Простые числа

        1


          Числа Мерсенна

          1


            Числа Ферма

            1


              Совершенные числа

              1


                НОК и НОД

                1


                  Числа Фибоначчи

                  1


                    Алгоритмы с простыми числами

                    2


                      Алгоритмы сортировки

                      Сортировка выбором (SelectSort), сортировка пузырьком (BubbleSort)

                      1


                        Гномья сортировка

                        1


                          Сортировка в C++

                          Сортировка структур в C++

                          1


                            Сортировка подсчетом (CountSort)

                            1


                              Пораздрядная сортировка (RadixSort)

                              1


                                Быстрая сортировка (QuickSort)

                                1


                                  Сортировка слиянием (MergeSort)

                                  1


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

                                    Формы хранения длинных чисел

                                    1


                                      Чтение, выводи сравнение

                                      1


                                        Сложение, вычитание и умножение

                                        3


                                          Деление длинного на короткое

                                          1


                                            Реализация длинной арифметики на С++

                                            1


                                              Перестановки

                                              Понятие перестановки

                                              1


                                                Перебор перестановок в C++

                                                1


                                                  Лексикографический перебор перестановок

                                                  1


                                                    Алгоритмы перебора перестановок

                                                    2


                                                      Куча - структура данных

                                                      Определение кучи

                                                      1


                                                        Просеивание элемента (Heapify)

                                                        1


                                                          Базовые операции при работе с кучей

                                                          1


                                                            Пирамидальная сортировка (HeapSort)

                                                            1


                                                              Задача «Коммерческий калькулятор»

                                                              1


                                                                STL - Standard Template Library

                                                                STL и шаблоны в C++

                                                                1


                                                                  Пара (pair)

                                                                  1


                                                                    Линейный массив (vector)

                                                                    1


                                                                      Стек (stack)

                                                                      1


                                                                        Очередь (queue)

                                                                        1


                                                                          Дек (deque)

                                                                          1


                                                                            Очередь с приоритетами (priority_queue)

                                                                            1


                                                                              Строка (string)

                                                                              1


                                                                                Множество (set)

                                                                                1


                                                                                  Ассоциативный массив (map)

                                                                                  1


                                                                                    Алгоритмы (algorithm)

                                                                                    1


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

                                                                                      Факториал и числа Фибоначчи

                                                                                      Задача «Без двух нулей подряд»

                                                                                      1


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

                                                                                        1


                                                                                          Задача «Фермер»

                                                                                          1


                                                                                            Задача «Сумма степеней двойки»

                                                                                            1


                                                                                              Задача «Игра в монеты»

                                                                                              1


                                                                                                Задача «Шары и коробки»

                                                                                                1


                                                                                                  Задача «Китайские часы»

                                                                                                  1


                                                                                                    Задача «Трипростые числа»

                                                                                                    1


                                                                                                      Задача «Количество путей в лабиринте»

                                                                                                      1


                                                                                                        Комбинаторика

                                                                                                        Размещения

                                                                                                        1


                                                                                                          Перестановки

                                                                                                          1


                                                                                                            Сочетания

                                                                                                            1


                                                                                                              Вычисление сочетаний

                                                                                                              Задача «Парад Победы»

                                                                                                              1


                                                                                                                Субфакториал

                                                                                                                Задача о разбиении числа

                                                                                                                1


                                                                                                                  Задача «Великий комбинатор»

                                                                                                                  1


                                                                                                                    Задача «Волейбол»

                                                                                                                    1


                                                                                                                      Вычислительная геометрия

                                                                                                                      Геометрические объекты

                                                                                                                      1


                                                                                                                        Понятие вектора

                                                                                                                        1


                                                                                                                          Скалярное и векторное произведение векторов

                                                                                                                          1


                                                                                                                            Псевдоскалярное произведение векторов

                                                                                                                            1


                                                                                                                              Полярная система координат

                                                                                                                              1


                                                                                                                                Поворот точки на плоскости

                                                                                                                                1


                                                                                                                                  Уравнение прямой на плоскости

                                                                                                                                  1


                                                                                                                                    Теорема Пика

                                                                                                                                    1


                                                                                                                                      Длина объединения отрезков на прямой Проверка пересечения двух отрезков

                                                                                                                                      1


                                                                                                                                        Пересечение окружности и прямой

                                                                                                                                        1


                                                                                                                                          Пересечение двух окружностей

                                                                                                                                          1


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

                                                                                                                                            1


                                                                                                                                              Принадлежность точки многоугольнику

                                                                                                                                              1


                                                                                                                                                Методы Джарвиса и Грэхема построения выпуклой оболочки

                                                                                                                                                1


                                                                                                                                                  Строки. Определения.

                                                                                                                                                  Префикс-функция

                                                                                                                                                  1


                                                                                                                                                    Z-функция

                                                                                                                                                    1


                                                                                                                                                      Реализация построения префикс-функции и Z-функции

                                                                                                                                                      2


                                                                                                                                                        Алгоритм Кнута-Морриса-Пратта

                                                                                                                                                        1


                                                                                                                                                          Количество различных подстрок в строке

                                                                                                                                                          1


                                                                                                                                                            Алгоритм Манакера

                                                                                                                                                            1


                                                                                                                                                              Сжатие строки

                                                                                                                                                              1


                                                                                                                                                                Полиномиальный хеш

                                                                                                                                                                Кольцо вычетов

                                                                                                                                                                1


                                                                                                                                                                  Полиномиальный хеш

                                                                                                                                                                  1


                                                                                                                                                                    Сравнение строк с помощью хешей

                                                                                                                                                                    1


                                                                                                                                                                      Подсчет различных строк

                                                                                                                                                                      1


                                                                                                                                                                        Алгоритм Рабина-Карпа

                                                                                                                                                                        1


                                                                                                                                                                          Вычисление Z-функции

                                                                                                                                                                          1


                                                                                                                                                                            Поиск всех палиндромов в строке

                                                                                                                                                                            1


                                                                                                                                                                              Лексикографически минимальный сдвиг

                                                                                                                                                                              1


                                                                                                                                                                                Структуры данных

                                                                                                                                                                                Базовые операции над массивом

                                                                                                                                                                                1


                                                                                                                                                                                  Sqrt-декомпозиция

                                                                                                                                                                                  1


                                                                                                                                                                                    Дерево Фенвика

                                                                                                                                                                                    1


                                                                                                                                                                                      Двумерное дерево Фенвика

                                                                                                                                                                                      1


                                                                                                                                                                                        Sparse Table

                                                                                                                                                                                        1


                                                                                                                                                                                          Дерево отрезков

                                                                                                                                                                                          1


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

                                                                                                                                                                                            37

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

                                                                                                                                                                                            1


                                                                                                                                                                                              Способы представления графа

                                                                                                                                                                                              1


                                                                                                                                                                                                Матрица весов

                                                                                                                                                                                                1


                                                                                                                                                                                                  Список дуг

                                                                                                                                                                                                  1


                                                                                                                                                                                                    Описание Бержа

                                                                                                                                                                                                    1


                                                                                                                                                                                                      Список смежности

                                                                                                                                                                                                      1


                                                                                                                                                                                                        Реализация структур для графов в C++

                                                                                                                                                                                                        1


                                                                                                                                                                                                          Поиск в глубину

                                                                                                                                                                                                          1


                                                                                                                                                                                                            Реализация поиска в глубину

                                                                                                                                                                                                            1


                                                                                                                                                                                                              Определение предка вершины в дереве

                                                                                                                                                                                                              1


                                                                                                                                                                                                                Подсчет компонент связности

                                                                                                                                                                                                                1


                                                                                                                                                                                                                  Поиск цикла в графе

                                                                                                                                                                                                                  1


                                                                                                                                                                                                                    Топологическая сортировка

                                                                                                                                                                                                                    1


                                                                                                                                                                                                                      Решение задач

                                                                                                                                                                                                                      3

                                                                                                                                                                                                                      Задача «Производство деталей»

                                                                                                                                                                                                                      1


                                                                                                                                                                                                                        Задача о шахматном коне

                                                                                                                                                                                                                        1


                                                                                                                                                                                                                          Задача коммивояжера

                                                                                                                                                                                                                          1


                                                                                                                                                                                                                            Поиск в ширину

                                                                                                                                                                                                                            1


                                                                                                                                                                                                                              Решение задач

                                                                                                                                                                                                                              3

                                                                                                                                                                                                                              Задача «Lines - 2»

                                                                                                                                                                                                                              1


                                                                                                                                                                                                                                Задача «Алхимия»

                                                                                                                                                                                                                                1


                                                                                                                                                                                                                                  Задача «Лабиринт»

                                                                                                                                                                                                                                  1


                                                                                                                                                                                                                                    Алгоритм Флойда

                                                                                                                                                                                                                                    1


                                                                                                                                                                                                                                      Алгоритм Форда-Беллмана

                                                                                                                                                                                                                                      1


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

                                                                                                                                                                                                                                        1


                                                                                                                                                                                                                                          Минимальный остов. Свойства минимальных остовов.

                                                                                                                                                                                                                                          1


                                                                                                                                                                                                                                            Алгоритм Прима

                                                                                                                                                                                                                                            1


                                                                                                                                                                                                                                              Алгоритм Крускала

                                                                                                                                                                                                                                              1


                                                                                                                                                                                                                                                Система непересекающихся множеств

                                                                                                                                                                                                                                                1

                                                                                                                                                                                                                                                Задача «Минимальный каркас»

                                                                                                                                                                                                                                                1


                                                                                                                                                                                                                                                  Эйлеров цикл и путь

                                                                                                                                                                                                                                                  3

                                                                                                                                                                                                                                                  Алгоритмы поиска эйлерова цикла

                                                                                                                                                                                                                                                  1


                                                                                                                                                                                                                                                    Задача «Ковбои»

                                                                                                                                                                                                                                                    1


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

                                                                                                                                                                                                                                                      1


                                                                                                                                                                                                                                                        Сильная связность графа

                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                        Поиск компонент сильной связности

                                                                                                                                                                                                                                                        1


                                                                                                                                                                                                                                                          Поиск мостов

                                                                                                                                                                                                                                                          1


                                                                                                                                                                                                                                                            Двудольный граф

                                                                                                                                                                                                                                                            5

                                                                                                                                                                                                                                                            Проверка на двудольность и разбиение на доли

                                                                                                                                                                                                                                                            1


                                                                                                                                                                                                                                                              Поиск максимального паросочетания

                                                                                                                                                                                                                                                              1


                                                                                                                                                                                                                                                                Алгоритм Куна

                                                                                                                                                                                                                                                                1


                                                                                                                                                                                                                                                                  Задача о назначениях

                                                                                                                                                                                                                                                                  1


                                                                                                                                                                                                                                                                    Венгерский алгоритм

                                                                                                                                                                                                                                                                    1

                                                                                                                                                                                                                                                                    68

                                                                                                                                                                                                                                                                    И Т О Г О за весь курс обучения

                                                                                                                                                                                                                                                                    136


                                                                                                                                                                                                                                                                    1 час в неделю

                                                                                                                                                                                                                                                                    № п/п

                                                                                                                                                                                                                                                                    тема

                                                                                                                                                                                                                                                                    Количество часов

                                                                                                                                                                                                                                                                    Вводное занятие. Олимпиадное движение в России.

                                                                                                                                                                                                                                                                    1


                                                                                                                                                                                                                                                                      Этапы решения олимпиадной задачи: формализация условия задачи, выбор метода решения задачи. Пример олимпиадной задачи

                                                                                                                                                                                                                                                                      1

                                                                                                                                                                                                                                                                      Реализация решения задачи «А+В»

                                                                                                                                                                                                                                                                      1


                                                                                                                                                                                                                                                                        Целочисленная арифметика

                                                                                                                                                                                                                                                                        1


                                                                                                                                                                                                                                                                          Простые числа

                                                                                                                                                                                                                                                                          1


                                                                                                                                                                                                                                                                            Числа Мерсенна. Числа Ферма

                                                                                                                                                                                                                                                                            1


                                                                                                                                                                                                                                                                              НОК и НОД

                                                                                                                                                                                                                                                                              1


                                                                                                                                                                                                                                                                                Алгоритмы с простыми числами

                                                                                                                                                                                                                                                                                2


                                                                                                                                                                                                                                                                                  Алгоритмы сортировки

                                                                                                                                                                                                                                                                                  Сортировка выбором (SelectSort), сортировка пузырьком (BubbleSort)

                                                                                                                                                                                                                                                                                  1


                                                                                                                                                                                                                                                                                    Гномья сортировка

                                                                                                                                                                                                                                                                                    1


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

                                                                                                                                                                                                                                                                                      Формы хранения длинных чисел

                                                                                                                                                                                                                                                                                      1


                                                                                                                                                                                                                                                                                        Чтение, выводи сравнение

                                                                                                                                                                                                                                                                                        1


                                                                                                                                                                                                                                                                                          Сложение, вычитание и умножение

                                                                                                                                                                                                                                                                                          2


                                                                                                                                                                                                                                                                                            Деление длинного на короткое

                                                                                                                                                                                                                                                                                            1


                                                                                                                                                                                                                                                                                              Перестановки

                                                                                                                                                                                                                                                                                              Понятие перестановки

                                                                                                                                                                                                                                                                                              1


                                                                                                                                                                                                                                                                                                Перебор перестановок в C++

                                                                                                                                                                                                                                                                                                1


                                                                                                                                                                                                                                                                                                  Лексикографический перебор перестановок

                                                                                                                                                                                                                                                                                                  1


                                                                                                                                                                                                                                                                                                    Алгоритмы перебора перестановок

                                                                                                                                                                                                                                                                                                    2


                                                                                                                                                                                                                                                                                                      Куча - структура данных

                                                                                                                                                                                                                                                                                                      Определение кучи

                                                                                                                                                                                                                                                                                                      1


                                                                                                                                                                                                                                                                                                        Просеивание элемента (Heapify)

                                                                                                                                                                                                                                                                                                        1


                                                                                                                                                                                                                                                                                                          Базовые операции при работе с кучей

                                                                                                                                                                                                                                                                                                          1


                                                                                                                                                                                                                                                                                                            Задача «Коммерческий калькулятор»

                                                                                                                                                                                                                                                                                                            1


                                                                                                                                                                                                                                                                                                              STL - Standard Template Library

                                                                                                                                                                                                                                                                                                              STL и шаблоны в C++

                                                                                                                                                                                                                                                                                                              1


                                                                                                                                                                                                                                                                                                                Пара (pair)

                                                                                                                                                                                                                                                                                                                1


                                                                                                                                                                                                                                                                                                                  Линейный массив (vector)

                                                                                                                                                                                                                                                                                                                  1


                                                                                                                                                                                                                                                                                                                    Строка (string)

                                                                                                                                                                                                                                                                                                                    1


                                                                                                                                                                                                                                                                                                                      Множество (set)

                                                                                                                                                                                                                                                                                                                      1


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

                                                                                                                                                                                                                                                                                                                        Факториал и числа Фибоначчи

                                                                                                                                                                                                                                                                                                                        Задача «Сумма степеней двойки»

                                                                                                                                                                                                                                                                                                                        1


                                                                                                                                                                                                                                                                                                                          Задача «Количество путей в лабиринте»

                                                                                                                                                                                                                                                                                                                          1


                                                                                                                                                                                                                                                                                                                            Задача «Трипростые числа»

                                                                                                                                                                                                                                                                                                                            1


                                                                                                                                                                                                                                                                                                                              Задача «Количество путей в лабиринте»

                                                                                                                                                                                                                                                                                                                              1


                                                                                                                                                                                                                                                                                                                              2 год обучения

                                                                                                                                                                                                                                                                                                                                Комбинаторика

                                                                                                                                                                                                                                                                                                                                Размещения. Перестановки. Сочетания.

                                                                                                                                                                                                                                                                                                                                1


                                                                                                                                                                                                                                                                                                                                  Вычисление сочетаний

                                                                                                                                                                                                                                                                                                                                  Задача «Парад Победы»

                                                                                                                                                                                                                                                                                                                                  1


                                                                                                                                                                                                                                                                                                                                    Субфакториал

                                                                                                                                                                                                                                                                                                                                    Задача о разбиении числа

                                                                                                                                                                                                                                                                                                                                    1


                                                                                                                                                                                                                                                                                                                                      Задача «Великий комбинатор»

                                                                                                                                                                                                                                                                                                                                      1


                                                                                                                                                                                                                                                                                                                                        Вычислительная геометрия

                                                                                                                                                                                                                                                                                                                                        Геометрические объекты

                                                                                                                                                                                                                                                                                                                                        1


                                                                                                                                                                                                                                                                                                                                          Скалярное и векторное произведение векторов

                                                                                                                                                                                                                                                                                                                                          1


                                                                                                                                                                                                                                                                                                                                            Полярная система координат

                                                                                                                                                                                                                                                                                                                                            1


                                                                                                                                                                                                                                                                                                                                              Поворот точки на плоскости

                                                                                                                                                                                                                                                                                                                                              1


                                                                                                                                                                                                                                                                                                                                                Уравнение прямой на плоскости

                                                                                                                                                                                                                                                                                                                                                1


                                                                                                                                                                                                                                                                                                                                                  Теорема Пика

                                                                                                                                                                                                                                                                                                                                                  1


                                                                                                                                                                                                                                                                                                                                                    Строки. Определения.

                                                                                                                                                                                                                                                                                                                                                    Префикс-функция

                                                                                                                                                                                                                                                                                                                                                    1


                                                                                                                                                                                                                                                                                                                                                      Z-функция

                                                                                                                                                                                                                                                                                                                                                      1


                                                                                                                                                                                                                                                                                                                                                        Алгоритм Кнута-Морриса-Пратта

                                                                                                                                                                                                                                                                                                                                                        1


                                                                                                                                                                                                                                                                                                                                                          Количество различных подстрок в строке

                                                                                                                                                                                                                                                                                                                                                          1


                                                                                                                                                                                                                                                                                                                                                            Алгоритм Манакера

                                                                                                                                                                                                                                                                                                                                                            1


                                                                                                                                                                                                                                                                                                                                                              Сжатие строки

                                                                                                                                                                                                                                                                                                                                                              1


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

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

                                                                                                                                                                                                                                                                                                                                                                1


                                                                                                                                                                                                                                                                                                                                                                  Способы представления графа. Матрица весов

                                                                                                                                                                                                                                                                                                                                                                  1


                                                                                                                                                                                                                                                                                                                                                                    Список дуг. Описание Бержа. Список смежности.

                                                                                                                                                                                                                                                                                                                                                                    1


                                                                                                                                                                                                                                                                                                                                                                      Реализация структур для графов в C++

                                                                                                                                                                                                                                                                                                                                                                      1


                                                                                                                                                                                                                                                                                                                                                                        Поиск в глубину

                                                                                                                                                                                                                                                                                                                                                                        1


                                                                                                                                                                                                                                                                                                                                                                          Подсчет компонент связности

                                                                                                                                                                                                                                                                                                                                                                          1


                                                                                                                                                                                                                                                                                                                                                                            Поиск цикла в графе

                                                                                                                                                                                                                                                                                                                                                                            1


                                                                                                                                                                                                                                                                                                                                                                              Топологическая сортировка

                                                                                                                                                                                                                                                                                                                                                                              1


                                                                                                                                                                                                                                                                                                                                                                                Решение задач

                                                                                                                                                                                                                                                                                                                                                                                Задача о шахматном коне

                                                                                                                                                                                                                                                                                                                                                                                1


                                                                                                                                                                                                                                                                                                                                                                                  Задача коммивояжера

                                                                                                                                                                                                                                                                                                                                                                                  1


                                                                                                                                                                                                                                                                                                                                                                                    Поиск в ширину

                                                                                                                                                                                                                                                                                                                                                                                    1


                                                                                                                                                                                                                                                                                                                                                                                      Решение задач

                                                                                                                                                                                                                                                                                                                                                                                      Задача «Lines - 2»

                                                                                                                                                                                                                                                                                                                                                                                      1


                                                                                                                                                                                                                                                                                                                                                                                        Алгоритм Флойда

                                                                                                                                                                                                                                                                                                                                                                                        1


                                                                                                                                                                                                                                                                                                                                                                                          Алгоритм Форда-Беллмана

                                                                                                                                                                                                                                                                                                                                                                                          1


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

                                                                                                                                                                                                                                                                                                                                                                                            1


                                                                                                                                                                                                                                                                                                                                                                                              Минимальный остов. Свойства минимальных остовов.

                                                                                                                                                                                                                                                                                                                                                                                              1


                                                                                                                                                                                                                                                                                                                                                                                                Алгоритм Прима

                                                                                                                                                                                                                                                                                                                                                                                                1


                                                                                                                                                                                                                                                                                                                                                                                                  Алгоритм Крускала

                                                                                                                                                                                                                                                                                                                                                                                                  1


                                                                                                                                                                                                                                                                                                                                                                                                    Система непересекающихся множеств

                                                                                                                                                                                                                                                                                                                                                                                                    Задача «Минимальный каркас»

                                                                                                                                                                                                                                                                                                                                                                                                    1


                                                                                                                                                                                                                                                                                                                                                                                                      Эйлеров цикл и путь

                                                                                                                                                                                                                                                                                                                                                                                                      Алгоритмы поиска эйлерова цикла

                                                                                                                                                                                                                                                                                                                                                                                                      1


                                                                                                                                                                                                                                                                                                                                                                                                        Задача «Ковбои»

                                                                                                                                                                                                                                                                                                                                                                                                        1


                                                                                                                                                                                                                                                                                                                                                                                                        Техническое и методическое обеспечение

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        • учебный компьютерный класс на 8 - 12 рабочих мест. Компьютеры объединены в локальную сеть и подключены к серверу;

                                                                                                                                                                                                                                                                                                                                                                                                        • каждый учащийся имеет сетевой адрес, пароль и личное пространство на диске размером не менее 10Mb;

                                                                                                                                                                                                                                                                                                                                                                                                        • подключение к Internet на скорости не менее 128 Кбит / сек.

                                                                                                                                                                                                                                                                                                                                                                                                        Программное обеспечение:

                                                                                                                                                                                                                                                                                                                                                                                                        • операционная система Window 7 и выше;

                                                                                                                                                                                                                                                                                                                                                                                                        • среда программирования Dev-C++;

                                                                                                                                                                                                                                                                                                                                                                                                        • браузер.

                                                                                                                                                                                                                                                                                                                                                                                                        Методическое обеспечение:

                                                                                                                                                                                                                                                                                                                                                                                                        Список рекомендуемой литературы олимпиадной подготовки по информатике издательства «БИНОМ. Лаборатория знаний» (см каталог на сайте www.LBZ.RU ).


                                                                                                                                                                                                                                                                                                                                                                                                        1. Андреева Т. А. Программирование на языке Pascal. Учебное пособие

                                                                                                                                                                                                                                                                                                                                                                                                        2. Златопольский Д. М. Программирование: типовые задачи, алгоритмы, методы

                                                                                                                                                                                                                                                                                                                                                                                                        3. Лесневский А. С. Объектно-ориентированное программирование для начинающих

                                                                                                                                                                                                                                                                                                                                                                                                        4. Окулов С. М. Задачи по программированию

                                                                                                                                                                                                                                                                                                                                                                                                        5. Окулов С. М. Программирование в алгоритмах

                                                                                                                                                                                                                                                                                                                                                                                                        6. Робертсон Л.А. Программирование - это просто: пошаговый подход. (перевод с английского)

                                                                                                                                                                                                                                                                                                                                                                                                        7. Андреева Е. В., Босова Л. Л., Фалина И. Н. Математические основы информатики. Элективный курс. Учебное пособие

                                                                                                                                                                                                                                                                                                                                                                                                        8. Дехтярь М. И. Лекции по дискретной математике. Учебное пособие

                                                                                                                                                                                                                                                                                                                                                                                                        9. Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады

                                                                                                                                                                                                                                                                                                                                                                                                        10. Окулов С.М. и др. Дискретная математика. Теория и практика решения задач по информатике

                                                                                                                                                                                                                                                                                                                                                                                                        Список интернет-ресурсов

                                                                                                                                                                                                                                                                                                                                                                                                        1. contest.samara.ru/

                                                                                                                                                                                                                                                                                                                                                                                                        2. http://acmp.ru

                                                                                                                                                                                                                                                                                                                                                                                                        3. acm.timus.ru/

                                                                                                                                                                                                                                                                                                                                                                                                        Приложение 1

                                                                                                                                                                                                                                                                                                                                                                                                        Задачи, используемые в программе:

                                                                                                                                                                                                                                                                                                                                                                                                        A+B

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

                                                                                                                                                                                                                                                                                                                                                                                                        Требуется сложить два целых числа А и В.

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

                                                                                                                                                                                                                                                                                                                                                                                                        В единственной строке входного файла INPUT.TXT записано два натуральных числа через пробел, не превышающих 109.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Пример

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        2 3

                                                                                                                                                                                                                                                                                                                                                                                                        5


                                                                                                                                                                                                                                                                                                                                                                                                        Коммерческий калькулятор

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в $1.05), потом результат - с 12 ($1.65), и затем - с 13 ($2.3), то всего мы заплатим $5, если же сначала отдельно сложить 10 и 11 ($1.05), потом - 12 и 13 ($1.25) и, наконец, сложить между собой два полученных числа ($2.3), то в итоге мы заплатим лишь $4.6.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Во входном файле INPUT.TXT записано число N (2<=N<=100000). Далее идет N натуральных чисел, которые нужно сложить, каждое из них не превышает 10000.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        4
                                                                                                                                                                                                                                                                                                                                                                                                        10 11 12 13

                                                                                                                                                                                                                                                                                                                                                                                                        4.60

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        2
                                                                                                                                                                                                                                                                                                                                                                                                        1 1

                                                                                                                                                                                                                                                                                                                                                                                                        0.10


                                                                                                                                                                                                                                                                                                                                                                                                        Пицца

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

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Входной файл INPUT.TXT содержит натуральное число N - число прямых разрезов пиццы (N <= 1000).

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

                                                                                                                                                                                                                                                                                                                                                                                                        В выходной файл OUTPUT.TXT выведите ответ на задачу.

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        4

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        3

                                                                                                                                                                                                                                                                                                                                                                                                        7


                                                                                                                                                                                                                                                                                                                                                                                                        Гвоздики

                                                                                                                                                                                                                                                                                                                                                                                                        (Время: 1 сек. Память: 16 Мб)

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        В первой строке входного файла 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 Мб)

                                                                                                                                                                                                                                                                                                                                                                                                        В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.

                                                                                                                                                                                                                                                                                                                                                                                                        Программа дополнительных занятий по программированию

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

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        1 3

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        2 7

                                                                                                                                                                                                                                                                                                                                                                                                        21

                                                                                                                                                                                                                                                                                                                                                                                                        3

                                                                                                                                                                                                                                                                                                                                                                                                        3 10

                                                                                                                                                                                                                                                                                                                                                                                                        274


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

                                                                                                                                                                                                                                                                                                                                                                                                        (Время: 1 сек. Память: 16 Мб)

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

                                                                                                                                                                                                                                                                                                                                                                                                        Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться от одного края экрана до другого. При этом при прыжке с одной платформы на соседнюю, у героя уходит |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 Мб Сложность: 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%)

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

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

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Пример

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        6
                                                                                                                                                                                                                                                                                                                                                                                                        3 29 5 5 28 6

                                                                                                                                                                                                                                                                                                                                                                                                        3

                                                                                                                                                                                                                                                                                                                                                                                                        Пицца

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

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Входной файл INPUT.TXT содержит натуральное число N - число прямых разрезов пиццы (N <= 1000).

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

                                                                                                                                                                                                                                                                                                                                                                                                        В выходной файл OUTPUT.TXT выведите ответ на задачу.

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        4

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        3

                                                                                                                                                                                                                                                                                                                                                                                                        7

                                                                                                                                                                                                                                                                                                                                                                                                        Гвоздики

                                                                                                                                                                                                                                                                                                                                                                                                        (Время: 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

                                                                                                                                                                                                                                                                                                                                                                                                        Зайчик

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

                                                                                                                                                                                                                                                                                                                                                                                                        В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.

                                                                                                                                                                                                                                                                                                                                                                                                        Программа дополнительных занятий по программированию

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

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        1 3

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        2 7

                                                                                                                                                                                                                                                                                                                                                                                                        21

                                                                                                                                                                                                                                                                                                                                                                                                        3

                                                                                                                                                                                                                                                                                                                                                                                                        3 10

                                                                                                                                                                                                                                                                                                                                                                                                        274

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

                                                                                                                                                                                                                                                                                                                                                                                                        (Время: 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 Мб Сложность: 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 Мб Сложность: 43%)

                                                                                                                                                                                                                                                                                                                                                                                                        Любое натуральное число можно представить в виде суммы натуральных слагаемых, каждое из которых является степенью числа 2. Суммы, различающиеся лишь порядком слагаемых, считаются одинаковыми. Например, для числа 7 таких представлений 6 (4+2+1, 4+1+1+1, 2+2+2+1, 2+2+1+1+1, 2+1+1+1+1+1, 1+1+1+1+1+1+1).

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

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

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        4

                                                                                                                                                                                                                                                                                                                                                                                                        4

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        7

                                                                                                                                                                                                                                                                                                                                                                                                        6

                                                                                                                                                                                                                                                                                                                                                                                                        Ход конем

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

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        3

                                                                                                                                                                                                                                                                                                                                                                                                        4

                                                                                                                                                                                                                                                                                                                                                                                                        5

                                                                                                                                                                                                                                                                                                                                                                                                        6

                                                                                                                                                                                                                                                                                                                                                                                                        7

                                                                                                                                                                                                                                                                                                                                                                                                        8

                                                                                                                                                                                                                                                                                                                                                                                                        9


                                                                                                                                                                                                                                                                                                                                                                                                        0


                                                                                                                                                                                                                                                                                                                                                                                                        Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

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

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

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        8

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        16

                                                                                                                                                                                                                                                                                                                                                                                                        Игра - 2

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

                                                                                                                                                                                                                                                                                                                                                                                                        Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали даже. Что ж, расскажем о новой игре. На доске написана последовательность n целых чисел. Играют двое. На очередном ходе игрок выбирает число с правого или с левого края последовательности, затем это число стирается и последовательность становится на одно число меньше, а ход переходит к противнику. Выигрывает тот, кто наберет в сумме больше. Написать программу, определяющую победителя в конкретной игре, при условии, что игроки будут играть оптимально.

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

                                                                                                                                                                                                                                                                                                                                                                                                        В первой строке входного файла INPUT.TXT записано целое число n (0 < n < 100). Во второй строке через пробел заданы n натуральных чисел, не превосходящих 1000.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Пример

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        4
                                                                                                                                                                                                                                                                                                                                                                                                        3 2 5 4

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        6
                                                                                                                                                                                                                                                                                                                                                                                                        5 5 5 5 5 5

                                                                                                                                                                                                                                                                                                                                                                                                        0

                                                                                                                                                                                                                                                                                                                                                                                                        3

                                                                                                                                                                                                                                                                                                                                                                                                        9
                                                                                                                                                                                                                                                                                                                                                                                                        2 1 3 2 9 1 2 3 1

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        4

                                                                                                                                                                                                                                                                                                                                                                                                        10
                                                                                                                                                                                                                                                                                                                                                                                                        2 5 3 12 4 6 13 7 1 3

                                                                                                                                                                                                                                                                                                                                                                                                        1


                                                                                                                                                                                                                                                                                                                                                                                                        Зоопарк

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

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        1. первый медведь, тигр и лев;

                                                                                                                                                                                                                                                                                                                                                                                                        2. первый медведь, тигр и пингвин;

                                                                                                                                                                                                                                                                                                                                                                                                        3. первый медведь, лев и пингвин;

                                                                                                                                                                                                                                                                                                                                                                                                        4. второй медведь, тигр и лев;

                                                                                                                                                                                                                                                                                                                                                                                                        5. второй медведь, тигр и пингвин;

                                                                                                                                                                                                                                                                                                                                                                                                        6. второй медведь, лев и пингвин;

                                                                                                                                                                                                                                                                                                                                                                                                        7. тигр, лев и пингвин.

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

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        4
                                                                                                                                                                                                                                                                                                                                                                                                        2 1 1 1

                                                                                                                                                                                                                                                                                                                                                                                                        7

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        3
                                                                                                                                                                                                                                                                                                                                                                                                        100 100 100

                                                                                                                                                                                                                                                                                                                                                                                                        1000000


                                                                                                                                                                                                                                                                                                                                                                                                        Игра в монеты

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

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Входной файл INPUT.TXT состоит из одной строки, в которой записаны: число стопок N (1 <= N <= 180), за ним идут N чисел, задающих количество монет в стопках слева направо (количество монет в стопке - не менее 1 и не более 20000), а затем число K, ограничивающее количество стопок, которые первый игрок может взять на первом ходе (1 <= K <= 80). Все числа в строке разделены пробелом.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        3 4 9 1 3

                                                                                                                                                                                                                                                                                                                                                                                                        14

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        4 2 2 1 7 3

                                                                                                                                                                                                                                                                                                                                                                                                        5

                                                                                                                                                                                                                                                                                                                                                                                                        3

                                                                                                                                                                                                                                                                                                                                                                                                        5 3 4 8 1 7 2

                                                                                                                                                                                                                                                                                                                                                                                                        18


                                                                                                                                                                                                                                                                                                                                                                                                        Шары и коробки

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

                                                                                                                                                                                                                                                                                                                                                                                                        У вас имеется N выстроенных в ряд коробок, A красных и B синих шаров. Все красные шары (аналогично и синие) идентичны. Вы можете класть шары в коробки. Разрешается размещать в коробках шары как одного, так и двух видов одновременно. Так же разрешается оставлять некоторые из коробок пустыми. Не обязательно класть все шары в коробки.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Входной файл INPUT.TXT содержит целые числа N, A, B. (1 <= N <= 20, 0 <= A, B <= 20)

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

                                                                                                                                                                                                                                                                                                                                                                                                        В выходной файл OUTPUT.TXT выведите ответ на задачу.

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        1 1 1

                                                                                                                                                                                                                                                                                                                                                                                                        4

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        2 1 1

                                                                                                                                                                                                                                                                                                                                                                                                        9


                                                                                                                                                                                                                                                                                                                                                                                                        Китайские часы

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

                                                                                                                                                                                                                                                                                                                                                                                                        Русский бизнесмен Иван Петров закупил в Китае большую партию наручных часов, чтобы продать их на родине за полцены (т.е. в 5 раз дороже, чем они стоили в Китае). Иван столкнулся с проблемой: китайские часы оказались некачественными. Мало того, что часы работали на протяжении всего нескольких часов, пока их не стукнешь, так еще и время подводить неудобно: вращать можно не минутную, а только секундную стрелку, причем, что самое ужасное, только в одну сторону в направлении увеличении времени. Например, для того, чтобы подвести часы на секунду назад, необходимо было сделать более 700 полных оборотов секундной стрелки, на что Иван бы потратил более 10 минут.

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        В первой строке входного файла INPUT.TXT содержится натуральное число N - количество часов (N ≤ 50000). В последующих N строках располагаются показания всех часов в формате h:mm:ss, где h - показывает который час, mm - минуты, ss - секунды (1 ≤ h ≤ 12, 0 ≤ mm ≤ 59, 0 ≤ ss ≤ 59).

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Пример

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        3
                                                                                                                                                                                                                                                                                                                                                                                                        8:19:16
                                                                                                                                                                                                                                                                                                                                                                                                        2:05:11
                                                                                                                                                                                                                                                                                                                                                                                                        12:50:07

                                                                                                                                                                                                                                                                                                                                                                                                        2:05:11


                                                                                                                                                                                                                                                                                                                                                                                                        Трипростые числа

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

                                                                                                                                                                                                                                                                                                                                                                                                        Будем называть натуральное число трипростым, если в нем любые подряд идущие 3 цифры образуют трехзначное простое число.

                                                                                                                                                                                                                                                                                                                                                                                                        Требуется найти количество N-значных трипростых чисел.

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Выходной файл OUTPUT.TXT должен содержать количество N-значных трипростых чисел, которое следует вывести по модулю 109+9.

                                                                                                                                                                                                                                                                                                                                                                                                        Пример

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        4

                                                                                                                                                                                                                                                                                                                                                                                                        204


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

                                                                                                                                                                                                                                                                                                                                                                                                        (Время: 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 сек. Память: 16 Мб Сложность: 38%)

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Входной файл INPUT.TXT содержит в первой строке числа N и K, разделенные пробелом (1 < N <= 15, 0 < K <= 30). Следующие N строк, по N символов в каждой, содержат карту лабиринта, начиная с клетки (1, 1). Символ «0» означает не запрещенную для прохождения клетку, а символ «1» - запрещенную. Начальная и конечная клетки всегда разрешены для прохождения.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        3 6
                                                                                                                                                                                                                                                                                                                                                                                                        000
                                                                                                                                                                                                                                                                                                                                                                                                        101
                                                                                                                                                                                                                                                                                                                                                                                                        100

                                                                                                                                                                                                                                                                                                                                                                                                        5

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        2 8
                                                                                                                                                                                                                                                                                                                                                                                                        01
                                                                                                                                                                                                                                                                                                                                                                                                        10

                                                                                                                                                                                                                                                                                                                                                                                                        0


                                                                                                                                                                                                                                                                                                                                                                                                        Космический мусорщик

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

                                                                                                                                                                                                                                                                                                                                                                                                        В околоземном космическом пространстве накопилось много мусора, поэтому ученые сконструировали специальный аппарат ловушку для космического мусора. Аппарат должен двигаться по достаточно сложной траектории, сжигая по пути мусор. Ловушка может передвигаться в пространстве по 6 направлениям: на север (N), на юг (S), на запад (W), на восток (E), вверх (U) и вниз (D). Движением ловушки управляет процессор. Программа движения задается шестью правилами движения, которые соответствуют каждому из указанных направлений. Каждое такое правило представляет собой строку символов из множества {N, S, W, E, U, D}.

                                                                                                                                                                                                                                                                                                                                                                                                        Команда ловушки состоит из символа направления и целого положительного числа M. Если параметр больше 1, то ловушка перемещается на один метр в направлении, которое указано в команде, а затем последовательно выполняет команды, заданные правилом для данного направления, с параметром меньше на 1. Если же параметр равен 1, то просто перемещается на один метр в указанном направлении.

                                                                                                                                                                                                                                                                                                                                                                                                        Пусть, например, заданы правила, отраженные в таблице справа. Тогда при выполнении команды S(3) мусорщик сначала переместится на 1 метр в направлении S, а потом выполнит последовательно команды N(2), U(2), S(2), D(2), D(2), U(2), S(2), E(2).

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

                                                                                                                                                                                                                                                                                                                                                                                                        Направление

                                                                                                                                                                                                                                                                                                                                                                                                        Правило

                                                                                                                                                                                                                                                                                                                                                                                                        N

                                                                                                                                                                                                                                                                                                                                                                                                        N

                                                                                                                                                                                                                                                                                                                                                                                                        S

                                                                                                                                                                                                                                                                                                                                                                                                        NUSDDUSE

                                                                                                                                                                                                                                                                                                                                                                                                        W

                                                                                                                                                                                                                                                                                                                                                                                                        UEWWD

                                                                                                                                                                                                                                                                                                                                                                                                        E

                                                                                                                                                                                                                                                                                                                                                                                                        U

                                                                                                                                                                                                                                                                                                                                                                                                        U

                                                                                                                                                                                                                                                                                                                                                                                                        D

                                                                                                                                                                                                                                                                                                                                                                                                        WED

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

                                                                                                                                                                                                                                                                                                                                                                                                        Первые шесть строк входного файла INPUT.TXT задают правила для команд с направлением N, S, W, E, U и D соответственно. Каждая строка содержит не более 100 символов (и может быть пустой). Следующая строка содержит команду ловушки: сначала символ из множества {N, S, W, E, U, D}, затем пробел и параметр команды - целое положительное число, не превышающее 100.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Пример

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        N
                                                                                                                                                                                                                                                                                                                                                                                                        NUSDDUSE
                                                                                                                                                                                                                                                                                                                                                                                                        UEWWD

                                                                                                                                                                                                                                                                                                                                                                                                        U
                                                                                                                                                                                                                                                                                                                                                                                                        WED
                                                                                                                                                                                                                                                                                                                                                                                                        S 3

                                                                                                                                                                                                                                                                                                                                                                                                        34


                                                                                                                                                                                                                                                                                                                                                                                                        Объединение блоков

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

                                                                                                                                                                                                                                                                                                                                                                                                        Изделие изготавливают из n блоков, каждый из которых имеет два технологических параметра - mi и ki. Известно, что ki=mi+1, i=1, 2, …, n-1. При этом условии два последовательных блока i и i+1 можно объединять в один новый, который будет иметь технологические параметры - mi и ki+1, и на это потребуется mi*ki+1 технологических операций. Новый блок можно опять объединять с одним из соседних и так далее. Меняя порядок сборки блоков можно добиться уменьшения количества технологических операций.

                                                                                                                                                                                                                                                                                                                                                                                                        Поясним это на примере трех блоков: 34 и 29, 29 и 4, 4 и 15. Если собрать вначале 2 и 3 блок, а затем присоединить собранное к первому, то потребуется 29*15+34*15=435+510=945 операций. Если собрать вначале блок из 1 и 2 исходных блоков, а затем присоединить 3 блок, то потребуется 34*4+34*15=136+510=646 операций.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Входной файл INPUT.TXT содержит в первой строке число n - количество блоков (1 <= n <= 100). Последующие n строк содержат пары чисел (разделенных пробелом) - технологические параметры блоков. Технологические параметры - целые неотрицательные числа, не превышающие 100.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Пример

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        3
                                                                                                                                                                                                                                                                                                                                                                                                        34 29
                                                                                                                                                                                                                                                                                                                                                                                                        29 4
                                                                                                                                                                                                                                                                                                                                                                                                        4 15

                                                                                                                                                                                                                                                                                                                                                                                                        646

                                                                                                                                                                                                                                                                                                                                                                                                        Лесенка

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Во входном файле INPUT.TXT записано натуральное число N (1 ≤ N ≤ 100) - количество кубиков в лесенке.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        3

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        6

                                                                                                                                                                                                                                                                                                                                                                                                        4


                                                                                                                                                                                                                                                                                                                                                                                                        Раз-два, раз-два

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

                                                                                                                                                                                                                                                                                                                                                                                                        Для заданного натурального числа N требуется найти число, состоящее только из цифр 1 и 2, которое делилось бы на 2N.

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

                                                                                                                                                                                                                                                                                                                                                                                                        Входной файл INPUT.TXT содержит натуральное число N, не превосходящее 300.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        12

                                                                                                                                                                                                                                                                                                                                                                                                        Фотограф-зануда

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        1. слева сидит ребенок возрастом в 1 год

                                                                                                                                                                                                                                                                                                                                                                                                        2. разность возрастов двух соседних родственников не превышает 2 года

                                                                                                                                                                                                                                                                                                                                                                                                        Действительно, на фотографии, таким образом, все будут все равно выглядеть, будто расположенные по старшинству (ведь среди людей возрастом, к примеру, 25 и 27 лет не так легко определить старшего). Способов такой посадки существует, понятно, несколько. Фотограф снял все такие способы. Сколько же фотографий получилось в итоге?

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

                                                                                                                                                                                                                                                                                                                                                                                                        Во входном файле INPUT.TXT содержится число N (1 <= N <= 55) - количество членов большой семьи.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        4

                                                                                                                                                                                                                                                                                                                                                                                                        4

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        7

                                                                                                                                                                                                                                                                                                                                                                                                        14


                                                                                                                                                                                                                                                                                                                                                                                                        Фермер - 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 сек. Память: 16 Мб Сложность: 68%)

                                                                                                                                                                                                                                                                                                                                                                                                        Требуется вычислить количество N - значных счастливых билетов. Напомним, что билет называется счастливым, если сумма первой половины его цифр равна сумме другой его половины. Например, билет 564159 счастливый, т.к. 5+6+4=1+5+9.

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

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        4

                                                                                                                                                                                                                                                                                                                                                                                                        670

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        6

                                                                                                                                                                                                                                                                                                                                                                                                        55252

                                                                                                                                                                                                                                                                                                                                                                                                        3

                                                                                                                                                                                                                                                                                                                                                                                                        12

                                                                                                                                                                                                                                                                                                                                                                                                        39581170420


                                                                                                                                                                                                                                                                                                                                                                                                        Великий комбинатор

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Шура Балаганов предложил "по справедливости", т.е. всем поровну. Паниковский порешил себе отдать половину, а остальным "по заслугам". Каждый из K детей лейтенанта предложил что-нибудь интересное. Однако, у Великого Комбинатора имелось свое мнение на этот счет...

                                                                                                                                                                                                                                                                                                                                                                                                        Ваша же задача состоит в нахождении количества способов разделить имеющиеся деньги между всеми участниками этих славных событий: K детьми лейтенанта Шмидта и Остапом Бендером.

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

                                                                                                                                                                                                                                                                                                                                                                                                        Во входном файле INPUT.TXT записаны целые числа X (0 <= X <= 500) и K (0 <= K <= 100). Естественно, что число X делится на 5. Да и при дележе рвать пятирублевые банкноты не разрешается.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Пример

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        15 2

                                                                                                                                                                                                                                                                                                                                                                                                        10

                                                                                                                                                                                                                                                                                                                                                                                                        Волейбол

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

                                                                                                                                                                                                                                                                                                                                                                                                        Партия в волейболе выигрывается командой, которая первой набирает 25 очков с преимуществом минимум в два очка. В случае равного счета 24-24, игра продолжается до достижения преимущества в 2 очка (26-24; 27-25).

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

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

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

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

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Примеры

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        25:12

                                                                                                                                                                                                                                                                                                                                                                                                        1251677700

                                                                                                                                                                                                                                                                                                                                                                                                        2

                                                                                                                                                                                                                                                                                                                                                                                                        20:25

                                                                                                                                                                                                                                                                                                                                                                                                        1761039350070

                                                                                                                                                                                                                                                                                                                                                                                                        3

                                                                                                                                                                                                                                                                                                                                                                                                        25:23

                                                                                                                                                                                                                                                                                                                                                                                                        16123801841550


                                                                                                                                                                                                                                                                                                                                                                                                        Лабиринт

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

                                                                                                                                                                                                                                                                                                                                                                                                        Открыв глаза, Принц Персии обнаружил, что находится на верхнем уровне подземного лабиринта Джаффара. Лабиринт состоит из h уровней, расположенных строго друг под другом. Каждый уровень представляет собой прямоугольную площадку, разбитую на m х n участков. На некоторых участках стоят колонны, поддерживающие потолок, на такие участки Принц заходить не может.

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        В первой строке входного файла INPUT.TXT содержатся натуральные числа h, m и n - высота и горизонтальные размеры лабиринта (2 ≤ h, m, n ≤ 50). Далее во входном файле приведены h блоков, описывающих уровни лабиринта в порядке от верхнего к нижнему. Каждый блок содержит m строк, по n символов в каждой: «.» обозначает свободный участок, «о» обозначает участок с колонной, «1» обозначает свободный участок, в котором оказался Принц в начале своего путешествия, «2» обозначает свободный участок, на котором томится Принцесса. Символы «1» и «2» встречаются во входном файле ровно по одному разу: символ «1» - в описании самого верхнего уровня, а символ «2» - в описании самого нижнего. Соседние блоки разделены одной пустой строкой.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Пример

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        3 3 3
                                                                                                                                                                                                                                                                                                                                                                                                        1..
                                                                                                                                                                                                                                                                                                                                                                                                        oo.
                                                                                                                                                                                                                                                                                                                                                                                                        ...

                                                                                                                                                                                                                                                                                                                                                                                                        ooo
                                                                                                                                                                                                                                                                                                                                                                                                        ..o
                                                                                                                                                                                                                                                                                                                                                                                                        .oo

                                                                                                                                                                                                                                                                                                                                                                                                        ooo
                                                                                                                                                                                                                                                                                                                                                                                                        o..
                                                                                                                                                                                                                                                                                                                                                                                                        o.2

                                                                                                                                                                                                                                                                                                                                                                                                        60


                                                                                                                                                                                                                                                                                                                                                                                                        Минимальный каркас

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

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        В первой строке входного файла INPUT.TXT находятся числа N и M (1 <= N <= 100; 1 <= M <= 6000), где N - количество вершин в графе, а M - количество рёбер. В каждой из последующих M строк записано по тройке чисел A, B, C, где A и B - номера вершин, соединённых ребром, а C - вес ребра (натуральное число, не превышающее 30000).

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Пример

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        3 3
                                                                                                                                                                                                                                                                                                                                                                                                        1 2 1
                                                                                                                                                                                                                                                                                                                                                                                                        2 3 2
                                                                                                                                                                                                                                                                                                                                                                                                        3 1 3

                                                                                                                                                                                                                                                                                                                                                                                                        3


                                                                                                                                                                                                                                                                                                                                                                                                        Домино в казино

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

                                                                                                                                                                                                                                                                                                                                                                                                        Домино известно в качестве игры, в которую люди обычно играют во дворе, чтобы расслабиться после рабочего дня. Но так было лишь до того времени, пока Джон Бигбак не предоставил возможность играть в домино в своем казино «BUMP» (Bring Us Money, Please).

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Например, существует два способа положить две кости домино на доску размера 2x2. Для доски, приведенной ниже, лучший способ положить домино показан слева - в этом случае сумма составляет 1x3 + 4x2 = 11. Если игрок выберет способ, показанный справа, то сумма составит 1x4 + 3x2 = 10, что меньше чем 11.

                                                                                                                                                                                                                                                                                                                                                                                                        Программа дополнительных занятий по программированию

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Первая строка входного файла INPUT.TXT содержит целые числа m, n и k (1 ≤ m ≤ 16, 1 ≤ n ≤ 100, 1 ≤ k ≤ 200). Следующие m строк содержат по n целых чисел каждая и описывают доску. Числа, записанные на доске, неотрицательны и по величине не превосходят 1000. Гарантируется, что существует хотя бы один способ разместить все кости домино на доске.

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

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

                                                                                                                                                                                                                                                                                                                                                                                                        Пример

                                                                                                                                                                                                                                                                                                                                                                                                        INPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        OUTPUT.TXT

                                                                                                                                                                                                                                                                                                                                                                                                        1

                                                                                                                                                                                                                                                                                                                                                                                                        2 2 2
                                                                                                                                                                                                                                                                                                                                                                                                        1 4
                                                                                                                                                                                                                                                                                                                                                                                                        3 2

                                                                                                                                                                                                                                                                                                                                                                                                        11


                                                                                                                                                                                                                                                                                                                                                                                                        42

                                                                                                                                                                                                                                                                                                                                                                                                        © 2010-2022