Способы решения олимпиадных задач по программированию

ОКСАНА СЕЛЕНДЕЕВА, основатель Международной школы программирования для детей CODDY

АНДРЕЙ ЛОЗИЦКИЙ, преподавателем курса «Олимпиадное программирование» Школы CODDY

Олимпиада по программированию:
разбираем задачу, выбираем подход и язык для решения

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

Решение олимпиадной задачи

Разберем классическую задачу 1 на алгоритмы вместе с Андреем Лозицким, преподавателем курса «Олимпиадное программирование» Школы CODDY.

Условие задачи

Доля успешных попыток

• Ограничение по времени на тест – 2 секунды.
• Ограничение по памяти на тест – 256 мегабайт.
• Ввод – стандартный ввод.
• Вывод – стандартный вывод.

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

Таким образом, на данный момент ваша доля успешных попыток на Codeforces составляет x / y .

Ваше любимое рациональное число в диапазоне [0;1] – это p / q .

Теперь вам интересно: какое минимальное количество попыток вам придется сделать, если вы зададитесь целью сделать долю успешных попыток равной p / q ?

Первая строка содержит одно целое число t ( l ) – количество тестов.

Каждая из следующих t строк содержит четыре целых числа x , y , p и q ( 0 9 ; 0 9 ; y > 0 ; q > 0 ).

Гарантируется, что p / q – несократимая дробь.

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

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

• В первом тесте нужно совершить 4 удачные попытки, тогда доля успешных попыток будет 7/14 или 1/2.
• Во втором тесте – 2 удачные и 8 провальных попыток, тогда доля успешных попыток будет 9/24 или 3/8.
• В третьем тесте доля успешных попыток уже равна 2/7.
• В четвертом тесте доли успешных попыток 1/1 нельзя добиться ни при каких условиях.

Затем посмотрите на ограничения, которые написаны в условии задачи: программа должна работать не более 2 секунд и использовать не более 256 Мб памяти.

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

Сложность алгоритма – зависимость объема работы, которая выполняется алгоритмом от размера входных данных. Обозначается O ( f ( n )).

Например, если сложность алгоритма будет O ( n 2 ), а входные данные примерно равны 10 9 , то решение не сможет пройти такой тест. Алгоритму потребуется примерно 10 18 операций, а самый быстрый язык программирования может выполнять максимум 10 9 операций в секунду. Поэтому сложность алгоритма должна зависеть от другой функции, которая растет медленнее, чем f ( n ) = n 2 .

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

Также смотрите, какой ввод/вывод нужен: стандартный или файловый. При стандартном вводе/выводе программа должна вывести результат на экран, а при файловом – записать его в текстовый файл.

Решение

Исходно мы имеем x успешных и ( y – x ) неуспешных попыток. Так как p / q – несократимая дробь, то в конце мы должны иметь p * r успешных и ( q * r – p * r ) неуспешных попыток, где r – некоторое натуральное число.

Понятно, что количество успешных и неуспешных попыток может только увеличиваться, тогда в конечном счете должны быть верны неравенства p * r >= x и q * r – p * r >= y – x .

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

Так как по условию задачи нам нужно найти минимальное количество попыток, при котором доля успешных попыток станет равной p / q , то нам нужно найти минимальное r , при котором равенства станут верными, а ответом на задачу будет q * r – y .

Переменную r нужно искать на отрезке [1;10 9 ], так как y 9 . Если для r = 10 9 данные неравенства не будут выполнены, то такого r не существует, и в этом случае выведем минус 1.

Искать r можно разными способами:

• Подставлять поочередно числа из отрезка [1;10 9 ]. Сложность алгоритма будет O ( n * t ). Но тогда для самого худшего случая потребуется сделать 10 12 операций за 2 секунды. На это не способен ни один язык программирования.
• Использовать бинарный поиск на отрезке [1;10 9 ]. Тогда сложность алгоритма будет O ( log ( n )* t ), и нам потребуется в самом худшем случае совершить примерно 30 000 операций за 2 секунды. На это уже способен любой язык программирования.
• Решить эффективнее: неравенства p*r >= x и q*r – p*r> = y – x решаемы. Из первого неравенства получаем, что r >= x / p , из второго: r >= ( y – x )/( q – p ). Для того чтобы оба неравенства выполнялись, r должно удовлетворять условию r >= max (( x / p ); ( y – x )/( q – p )). Минимальное r ищется из соотношения max (( x / p ); ( y – x )/( q – p )) с округлением вверх. Нужно учесть два частных случая, когда q и p равны 1 и 1 или 0 и 1. В этом случае нужно вывести минус 1. Данное решение является самым эффективным – оно не зависит от входных параметров. Сложность таких алгоритмов обозначается O (1).

Код решения с линейным поиском

Код решения с бинарным поиском

Код решения с формулой

Язык для решения задач

После того как придумали решение задачи, определитесь с языком программирования. Далеко не на каждой олимпиаде разрешают выбрать любой язык. Самые популярные – Python, C++, C#, Java, Pascal.

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

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

В первом случае лучше использовать Python, во втором – C++. Python – один из самых простых языков, но он довольно медленный. В зависимости от задачи Python работает в 100, а то и в 1000 раз медленнее, чем С++. Наоборот, С++ – один из самых быстрых языков программирования, но при написании кода можно наделать ошибок, на исправление которых уйдет времени больше, чем на подготовку самого решения.

Основная проблема не в том, что для работы на языке С++ необходимо быть аккуратным: после каждой команды ставить «;», объявлять тип переменной, ставить фигурные скобки. Проблема в том, что если программист допустил ошибку в алгоритме, например в результате работы программы он выходит за пределы массива, то Python сообщит об этом, а С++ – нет.

Тренировки перед олимпиадами

Чтобы научиться решать олимпиадные задачи, нужно много практиковаться. Для самостоятельного изучения теории советуем книги Томаса Кормена «Алгоритмы. Построение и анализ» и Дональда Кнута «Искусство программирования» в четырех томах. Подробный справочник по алгоритмам также есть на сайте MAXimal (http://e-maxx.ru). Там разобраны алгоритмы на языке С++, которые применяют на олимпиадах.

Для практики рекомендуем ресурсы с архивами олимпиадных задач: HackerRank (https://www.hackerrank.com), AtCoder (http://atcoder.jp), Codeforces (http://codeforces.com). На этих сайтах вы сможете решать задачи, сразу тестировать их и изучать подробные разборы. Также каждую неделю проходят тренировочные соревнования. Чтобы принять участие, необходимо только зарегистрироваться.

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

Чтобы натренироваться, участвуйте в олимпиадах Яндекс.Алгоритм, Google Code Jam, Facebook Hacker Jam и подобных. Призеры и победители получают ценные призы, а участников с интересными решениями приглашают на работу.

1 Задача из третьего раунда Олимпиады VK CUP 2017 – Международного чемпионата по программированию для участников от 14 до 23 лет.

Источник

Решение олимпиадных задач по программированию

Решение олимпиадных задач по программированию

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

Тематическое планирование. 1

Текст пособия. 2

ПРАВИЛА ПРОВЕДЕНИЯ ОЛИМПИАД ПО ПРОГРАММИРОВАНИЮ. 3

2. ПОИСК И СОРТИРОВКА. 6

3. КОМБИНАТОРНЫЕ ЗАДАЧИ. 9

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

1. Цели и задачи курса

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

Учащиеся, освоившие программу в полном объеме, должны

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

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

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

Правила проведения олимпиад. Техника программирования олимпиадных задач

Алгоритмы поиска и сортировки в олимпиадных задачах

Задачи на полный перебор вариантов

Динамическое программирование: основные приемы для решения задач

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

Создание программ решения комбинаторных задач

Программирование полного перебора

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

ВВЕДЕНИЕ

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

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

1. Техника программирования

Основы языка программирования (Си, Паскаль)

Одномерные массивы. Двумерные массивы. Многомерные массивы.

Операции над строками. Выделение чисел из строки

Работа с файлами

Чтение и запись в текстовый файл. Преобразование полученных из файла данных в удобную структуру. Типизированные файлы. Нетипизированные файлы.

Работа с динамической памятью

Хранение больших массивов. Создание и работа с динамическими списками.

Методы и принципы решения задач

Сложность алгоритмов. Умение оценивать сложность алгоритмов и программ.

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

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

Математические функции, задаваемые рекурсивно. Выход из рекурсии. Замена рекурсии циклами.

Переборные задачи. Комбинаторика

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

Основные идеи динамического программирования. Примеры использования динамического программирования.

Хранение чисел, которые не вмещаются в диапазоны значений стандартных типов. Арифметические операции над длинными числами.

Геометрические объекты (точка, прямая, отрезок, окружность).

Особенности вещественной арифметики.

Проведение прямой через две точки.

Нахождение точки пересечения двух прямых. Проверка прямых на параллельность и совпадение.

Принадлежность точки фигуре на плоскости (например, треугольнику).

Нахождение площади многоугольника.

Понятие графа. Основные способы хранения графа.

Алгоритмы обхода графов (поиск в глубину и ширину).

Поиск кратчайшего пути во взвешенном графе (алгоритм Дейкстры).

Эйлеров путь и эйлеров цикл. Критерий эйлеровости графа.

Замыкание графи. Алгоритм Флойда.

Потоки в сетях. Алгоритм Форда-Фалкерсона.

Построение каркаса минимального веса. Алгоритмы Краскала и Прима-алгоритм.

Сортировки на графах.

Олимпиады по программированию

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

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

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

Но прежде напомним общие правила проведения олимпиад по программированию.

ПРАВИЛА ПРОВЕДЕНИЯ ОЛИМПИАД ПО ПРОГРАММИРОВАНИЮ

Соревнования обычно длятся 4,5–5 часов. На это время участнику предоставляется компьютер и предлагается решить несколько задач. Набор задач для всех участников одинаковый. Во время тура запрещается пользоваться личными компьютерами, калькуляторами, электронными записными книжками, средствами связи (пейджерами, телефонами), а также учебной литературой и личными записями. Рабочими языками, как правило, считаются паскаль и си. На рабочем месте участника устанавливаются полностью системы Borland Pascal 7.0 и Borland C / C ++ 3.1. В последнее время все чаще на соревнованиях используется Free Pascal . Участник сам определяет язык и систему, в которой будет работать. Разные задачи можно решать с использованием разных языков программирования.

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

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

1. Отправлять жюри следует исходный текст на любом из допустимых языков программирования (как правило, это Бейсик, Паскаль или Си). Причем программа должна быть реализована в виде одного файла и не требовать подключения каких-либо модулей. Часто использование даже фразы “ uses crt ” может привести к ошибке.

2. Все входные данные вводятся из файла, указанного в условии задачи (часто это файл “ INPUT . TXT ”), результат записывается в выходной файл (например, “ OUTPUT . TXT ”). Входные и выходные файлы размещаются в текущем каталоге DOS . Типичная ошибка новичка – попытка указать пути к файлам, например, написать ’ a :\ input . txt ’. Поскольку у жюри в дисководе диск отсутствует, то программа выдает сообщение об ошибке и завершает работу.

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

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

5. Все необходимые директивы компиляции следует размещать внутри исходных текстов.

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

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

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

ЗАДАЧИ

Во всех задачах исходные данные хранятся в файле INPUT . TXT , а результат следует записывать в файл OUTPUT . TXT .

1. АРИФМЕТИКА

Задача 1.1. Гарри Поттер на досуге занимается исследованием свойств чисел. Однажды в старом заклинании он увидел число и захотел узнать, а делится ли оно на 3? Напишите программу, помогающую Гарри решить эту проблему для любого N (0 N Формат входных данных:

Исходный файл содержит одно целое число N .

Формат выходных данных:

В выходной файл вывести слово «ДА», если число N делится на 7, или остаток от деления N на 7.

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

Задача 1.2. После того, как Гарри решил свою задачу, вредная Гермиона решила узнать, а делится ли это число на 11?

Формат входных и выходных данных тот же, что и в задаче 1.2.

Задача 1.3. А на 13?

Формат входных и выходных данных тот же, что и в задаче 1.2.

Указание к решению. Так как признак делимости числа на 13 не известен ни нам, ни волшебникам школы Хогварц, то для решения этой задачи придется заняться моделированием деления в столбик.

Задача 1.4. Только-только Гарри Поттер разобрался с задачами Гермионы, как пришел Рон Уизли и задал новую задачу. А что, если число N задано своим двоичным представлением (длина числа не превышает 10000 двоичных разрядов) и надо определить, делится ли оно на 15?

Формат входных данных:

Исходный файл содержит число N в двоичном представлении.

Формат выходных данных:

В выходной файл вывести слово «ДА», если число N делится на 15, или слово «НЕТ» в противном случае.

Указание к решению. Здесь нам поможет тот факт, что признаком деления на 9 в десятичной системе счисления является делимость на 9 суммы цифр числа. Действительно, пусть есть число

S = a [ n ]*10 n + a [ n -1]*10( n -1) + . + a[1]*10 + a[0].

Его можно переписать иначе :
S =a[n]*(10n-1)+a[n] + a[n-1]*(10(n-1)-1)+a[n-1] + . + a [1]*(10-1)+ a [1] + a [0].

Так как 10k — 1 делится на 9 нацело, то S mod 9 =(a[n]+. +a[1]+a[0]) mod 9.

Аналогично получаем, что признаком деления на 15 в системе счисления по основанию 16 будет делимость на 15 суммы всех шестнадцатеричных цифр числа. Мы разбиваем двоичное число справа налево на четверки цифр, которые преобразовываем в шестнадцатеричные цифры, находим их сумму и делим ее на 15. Если остаток 0, то введенное число делится на 15, иначе – нет.

Задача 1.5. Чтобы навсегда избавиться от вопросов друзей про деление чисел, Гарри захотел решить общую задачу. Дано число N в K-ичной системе счисления (K N не более 1000 знаков.

Формат входных данных:

В первой строке входного файла записаны через пробел два целых числа K и m. Во второй строке записано число N в системе счисления по основанию K .

Формат выходных данных:

В выходной файл вывести остаток от деления N на m .

Указания к решению. Разумеется, можно непосредственно вычислить число N в десятичной системе счисления, после чего разделить его на m, но в этом случае придется представлять число в виде (например) массива цифр и моделировать операции над этим числом. Существует другой простой алгоритм. В системе счисления с основанием K число представляется в виде

Найдем остаток от деления его на m (остаток от деления a на b обозначим a mod b):

(a[n]*Kn + a[n-1]*K(n-1) + . +a[0]*K0) mod m =

= mod m = mod m .

Последнее равенство легко доказывается. Пусть Ki mod m=t, тогда

(a[i]*Ki) mod m = (a[i] * (p*m+t)) mod m =

= (a[i]* p*m) mod m + (a[i]*t) mod m =

= (a[i] * (Ki mod m)) mod m,

при этом для любых чисел b[i] выполняется

mod m = mod m .

Отметим также очевидное равенство

Ki mod m =[(Ki-1 mod m) * K] mod m,

Ki-1 = p*m+t, то Ki-1 mod m = t,

Ki mod m = t*K mod m = [(Ki-1 mod m)*K] mod m.

Запись этого алгоритма (тут a[i] — K-ичные цифры числа):

s:=0; t:=1;
for i:=0 to n do
begin
s:=(s+a[i]*t) mod m;
t:=t*K mod m;
end;

В переменной S после окончания работы алгоритма будет храниться искомый остаток

Задача 1.6. Ну и, наконец, в отместку Гермионе и сам придумал для них задачу. Любое натуральное число N можно единственным способом представить с помощью некоторых целых неотрицательных d[0], . , d[s] в виде

при условии , что 0 где d[s]<>0.

Дан набор из (s+1) натуральных чисел d[0], . d[s] и натуральное K, s 2. ПОИСК И СОРТИРОВКА

Задача 2.1. Для игры в квидич используются мячи — снитчи. Проблема заключается в том, что они разного размера. Для проведения матча требуется выбрать снитч нужного веса. Перед началом матча все снитчи выстраиваются в ряд в порядке неубывания весов и Гарри Поттер должен как можно быстрее найти снитч с весом ровно Х кг или сообщить судье об отсутствии нужного мяча.

Формат входных данных:

В первой строке входного файла записаны через пробел два целых числа N и X . В следующих N строках записаны веса мячей в порядке неубывания (по одному числу в строке). Веса – целые числа, не превосходящие 100, 0 N £ 50000.

Формат выходных данных:

В выходной файл вывести номер снитча, имеющего вес X или число 0, если такого снитча нет.

Лимит времени: 1 секунда на тест.

Указания к решению. Очевидное решение состоит в просмотре всего ряда снитчей сначала до конца, что требует времени, пропорционального числу снитчей. Однако этот алгоритм не использует того факта, что веса снитчей уже отсортированы. Наилучший метод поиска состоит в том, чтобы проверить, стоит ли нужный мяч в середине ряда. Если да, то ответ получен. Если вес x меньше веса среднего снитча, то мы можем применить тот же метод поиска к отсортированному подряду слева от среднего элемента; аналогично, если x больше веса среднего мяча, то в дальнейшем мы будем рассматривать правую половину ряда.

Задача 2.2. В школе Хогварц ученики, помимо других предметов, изучают алхимию. Известно, что химические вещества состоят из отдельных элементов. Однажды на уроке алхимии Северус Снегг выдал ученика набор из N химических веществ и для каждого вещества выписал список составляющих его элементов. Элемент задается своим номером в таблице Менделеева (маги тоже ею пользуются!). Известно, что существует элемент, входящий в состав всех веществ. Помогите магам-ученикам найти его. Для простоты считаем, что все вещества состоят из одинакового числа элементов. Всего в таблице Менделеева 250 элементов (по крайней мере, у магов).

Формат входных данных:

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

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

Формат выходных данных:

В выходной файл вывести номер найденного элемента.

Лимит времени: 1 секунда на тест.

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

Задача 2.3. В совятнике школы Хогварц для почтовых сов сделали полочки для сидения. Будем обозначать занятое совой место 1, а свободное 0. Таким образом совятник задается квадратной таблицей А[1:N,1: N ], элементы которой равны 0 или 1, причем пусть всегда А[i, i]=0 для любого i (на этих полочках установлены светильники).

Необходимо найти, если они есть, такие строку i0 и столбец j0, чтобы в столбце j0 были все 0, а в строке i0 — все 1 (кроме элемента A[i0,i0], равного 0).

Формат входных данных:

В первой строке входного файла записано целое число: N – размер совятника. В следующих N строках записаны через пробел по N чисел 0 или 1. (0 N Формат выходных данных:

В выходной файл вывести через пробел найденные i0 и j0 или –1, если таких строки и столбца нет.

Лимит времени: 1 секунда на тест.

Указания к решению. Простейшим решением является просмотр элементов i-й строки и i-го столбца, i=1,2. N (номера строки и столбца должны быть равны, иначе они пересекаются не по диагональному элементу) массива до нахождения индекса k, такого что элементы k-ой строки и k-го столбца удовлетворяют требуемому свойству или установления факта, что такого индекса нет. Очевидно, что в последнем случае необходим просмотр почти всех элементов массива.

Однако возможно существенно сократить количество операций, используя следующий факт. Рассмотрим элемент A[k, j], k<>j. Возможны следующие ситуации:

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

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

Таким образом, рассматривая на каждом шаге значения элементов A[k, j], таких, что A[k, j] является элементом интересующего нас подмассива, потребуется просмотр ровно N-1 элемента для установления единственного индекса k, удовлетворяющего требуемому свойству. Осталось проверить только элементы этого столбца и строки.

k:=1
для j от 2 до N
если A[k, j] = 0
то k:=j

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

Задача 2.4. На плоскости задается выпуклый N-угольник целочисленными кооpдинатами своих веpшин в порядке обхода по контуpу. Вводятся кооpдинаты точки (X, Y). Опpеделить:

a) является ли она веpшиной N-угольника;

б) пpинадлежит ли она N-угольнику.

Задача 2.5. На пpямой своими концами заданы N отpезков. Найти точку, принадлежащую максимальному числу отрезков.

3. КОМБИНАТОРНЫЕ ЗАДАЧИ

Задача 3.1. При составлении волшебных зелий Северус Снегг заставляет учеников заучивать все рецепты. Но однажды Рон Уизли не приготовил домашнее задание и не может приготовить смесь. Верная Гермиона передала Гарри Поттеру шпаргалку, на которой записаны названия элементов, входящих в рецепт. Но необходимо знать, в каком порядке их следует смешивать. И вот теперь Гарри пытается перебрать различные варианты смешивания, чтобы выручить Рона.

Помогите Гарри получить все возможные варианты приготовления зелья.

Формат входных данных:

В первой строке входного файла записано целое число: N – количество составных элементов требуемой смеси. В следующих N строках записаны названия элементов. (0 N Формат выходных данных:

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

Источник

Вам также может понравиться

Ясень семена способ распространения

Ясень обыкновенный Fraxinus excelsior – так в ботанической

Ярлыки способы создания ярлыков ос windows

Создаем ярлыки на рабочем столе Windows Создаем ярлыки

Японское удобрение фуджима способ применения

Удобрения Фуджима Знаете потрясающее удобрение, палочка

Японский чай способ заварки

Технология заваривания японского чая Известно, что