| ||||||||
|
Несколько вводных слов
Представленные здесь задачи - это продолжение курса программирования, который опубликован здесь. Тем самым, этот курс рассчитан на школьников 9-го математического класса, которые до этого уже полгода изучали программирование. Курс годовой, в режиме 2 часа в неделю. Мне бы хотелось выразить признательность школьникам 9 класса "В" Московской гимназии 1543 (2004-2005 учебный год) за нашу с ними совместную работу по "обкатке" этих задач :-) .
Данные материалы адресованы в первую очередь учителям информатики, но могут быть полезны и школьникам, изучающим программирование. Здесь представлен набор задач, которые использовались при изучении программирования. Задачи снабжены краткими комментариями. Теоретический материал, который рассказывался школьникам и который нужен для решения этих задач, здесь не представлен.
Преподавание курса велось частично с использованием системы автоматической проверки (и эти задачи вошли в данный список вместе с тестами), а частично - без нее (и эти задачи в данный архив не вошли, что будет отмечено в комментариях).
Тестирующая система, использовавшаяся на занятиях, была устроена так, что в случае ошибки (непрохождения какого-либо теста) этот тест оказывался во входном файле в рабочем каталоге школьника.
Все представленные задачи представлены в формате, принятом на сайте www.olympiads.ru. Внутри архива содержатся условие, тесты, проверяющие программы. Там, где используются дополнительные программы, они также есть внутри архивов. Обратите внимание, в html-версии присутствуют некоторые комментарии для преподавателей, которых нет внутри архивов!
Так исторически сложилось, что задачи пронумерованы не по порядку, вернее, по порядку, но с некоторыми пропусками.
Вы можете скачать решения некоторый задач (не гарантируется, что в этом архиве содержатся решения всех задач, равно как не гарантируется, что все содержащиеся решения правильные). Эти решения предназначены в первую очередь для проверки того, что задача добавлена в используемую вами тестирующую систему правильно. Данные решения не предполагалось использовать для того, чтобы по ним восстанавливать решения задач, однако в некоторых случаях они могут помочь и в этом.
Ну и, как обычно, мы предлагаем вам скачать все материалы в одном архиве (3.4 Мб).
Во всех задачах входные данные (если не указано иное) вводятся из файла INPUT.TXT, выходные данные выводятся в файл OUTPUT.TXT.
Комментарии. Цель первых занятий - вспомнить материал прошлого года на достаточно простых задачах.
Задача 201 (Скачать архив)
Дана последовательность чисел. Найти в ней наименьшее число. Входные данные. Задано сначала число N (количество чисел в последовательности), а затем N чисел. Все числа - из диапазона Integer. N≤100 Выходные данные. Выведите наименьшее число. Пример входного файла 7 4 2 5 -1 4 6 2 Пример выходного файла -1
Задача 202 (Скачать архив)
Даны два массива чисел. Требуется вывести в выходной файл те элементы первого массива (в том порядке, в каком они идут в первом массиве), которых нет во втором массиве. Входные данные Во входном файле записано сначала число N - количество элементов в первом массиве, затем N чисел - элементы массива. Затем записано число M - количество элементов во втором массиве. Затем записаны элементы второго массива. Количество элементов каждого массива не превышает 100. Сами элементы - числа из диапазона Longint. Выходные данные В выходной файл выведите те элементы первого массива, которых нет во втором в том порядке, в каком они идут в первом массиве. Пример входного файла 7 3 1 3 4 2 4 12 6 4 15 43 1 15 1 Пример выходного файла 3 3 2 12
Задача 203 (Скачать архив)
Задача "СТОЛОВСКИЕ КОТЛЕТЫ" Входной файл: С.IN Выходной файл: С.OUT Ограничение времени: 10 секунд Главный повар решил устроить в лицее День Уважения к Повару. Для этого он приготовил лицеистам N необычайно вкусных котлет и втайне постановил, что первый пожаловавший отведать поварское кушанье школьник должен получить наибольшее количество вкусных котлет, а каждый последующий - строго меньше, чем предыдущий (повару очень не нравилось, когда к приготовленному им обеду опаздывали и тот вынужден был остывать). Конечно, введенное правило оставляет существенный произвол в числе котлет, получаемых очередным явившимся лицеистом, и это число не в последнюю очередь будет зависеть от предыдущего поведения лицеиста в столовой, а также от волшебных слов, произносимых им. Например, 6 котлет могут быть в результате распределены по одной из следующих четырех схем: 3+2+1 (три котлеты первому из пришедших школьников, две - второму и одну - третьему), 4+2, 5+1 и 6 (все котлеты съедает счастливчик, пришедший первым). Напишите программу, определяющую, каким количеством различных способов повар может распределить приготовленное лакомство среди школьников. Формат входных данных Входной файл содержит одно целое число N - количество приготовленных поваром котлет (0≤N≤200). Формат выходных данных Выходной файл должен содержать одно целое число, равное количеству возможных распределений котлет. Замечание При указанных ограничениях ответ входит в тип Longint Пример файлов входных и выходных данных С.IN 6 С.OUT 4
Комментарии. Задачи 204-206 - это задачи окружной олимпиады прошлого учебного года, в которой школьники не участвовали. Им были предложены эти задачи с двумя целями: во-первых, попробовать свои силы в области олимпиад по информатике, а во-вторых, продолжить вспоминать материал прошлого учебного года.
Задача 204 (Скачать архив)
Задача. "Список" В фирме, выпускающей компьютерные комплектующие, все изделия получают последовательные номера от 1 до N. Каждое изделие после его изготовления поступает в отдел контроля качества, где оно проверяется, и либо уходит в продажу, либо заносится в список бракованных изделий и списывается. К сожалению, список бракованных изделий иногда оказывается чересчур длинным. Тогда для его сокращения подряд идущие числа заменяются интервалом: через тире указываются номера первого и последнего изделия интервала. Например, вместо 1,3,4,5,6,7,8,10,12,16,17,20,21,22,23,24 записывается 1,3-8,10,12,16-17,20-24 Напишите программу, которая по полному списку номеров бракованных изделий, выдаст этот список в сокращенном виде. Входные данные. Вводится сначала число N - общее количество изделий. Затем число M - количество изделий, оказавшихся бракованными. Далее вводятся в возрастающем порядке номера бракованных изделий. Выходные данные. Выведите в одной строке список номеров бракованных изделий в сокращенном виде. Интервалы должны разделяться запятой. В строке не должно быть пробелов. Ограничения Подзадача 1. 1≤M≤N≤100. Подзадача 2. 1≤M≤N≤1000000. Пример 1 (подзадача 1) Пример ввода 10 5 1 3 5 7 9 Пример вывода 1,3,5,7,9 Пример 2 (подзадача 1) Пример ввода 40 16 1 3 4 5 6 7 8 10 12 16 17 20 21 22 23 24 Пример вывода 1,3-8,10,12,16-17,20-24 Пример 3 (подзадача 1) Пример ввода 11 11 1 2 3 4 5 6 7 8 9 10 11 Пример вывода 1-11 Пример 4 (подзадача 2) Пример ввода 10000 1 5 Пример вывода 5
Задача 205 (Скачать архив)
Задача. "Метро" В мегаполисе, испытывающем большие транспортные проблемы, построили легкое метро. Оно состоит из 6 радиальных линий, которые расходятся из центра города, и k кольцевых линий в форме правильных шестиугольников (см. рисунок). Станции метро располагаются на пересечении кольцевых и радиальных линий. На любой станции разрешено делать пересадки с кольцевых линий на радиальные и обратно. Радиальные линии последовательно нумеруются по часовой стрелке от 1 до 6. Кольцевые линии нумеруются от центра города (центр считается кольцевой линией с номером ноль, состоящей из одной станции). Расстояние между двумя соседними станциями на одной радиальной линии равно 1 км. Расстояние между соседними станциями на кольцевой линии с номером i составляет i км. Любая станция обозначается парой чисел - номером радиальной линии r (1≤r≤6) и номером кольцевой линии k (0≤k≤32000), на пересечении которых она находится. Напишите программу, определяющую длину кратчайшего пути между станциями. Входные данные. Вводятся четыре числа - r1, k1, r2, k2 - координаты начальной и конечной станции. Выходные данные. Необходимо вывести расстояние (в км), которое потребуется проехать пассажиру, чтобы попасть c начальной станции на конечную. Пример 1 Пример входного файла 1 5 1 4 Пример выходного файла 1 Пример 2 Пример входного файла 1 5 2 4 Пример выходного файла 5 Пример 3 Пример входного файла 2 0 6 3 Пример выходного файла 3
Задача 206 (Скачать архив)
Задача "День рождения" На день рождения пришли N человек. В некоторый момент именинник решил, что пора устроить какую-нибудь игру. Он выяснил, что i-й человек согласен вступить в игру, если в ней уже принимают участие не менее A[i] и не более B[i] человек. Единожды вступив в игру, никто из нее не выходит. Требуется выяснить, может ли именинник установить такую последовательность вступления в игру, что в итоге все присутствующие станут ее участниками. (Сам именинник в игре участия не принимает.) Входные данные. Сначала вводится количество гостей N (1≤N≤100). Затем вводится N пар чисел A[i] и B[i] (все эти числа из диапазона от 0 до N-1). Выходные данные. Если можно установить последовательность вступления гостей в игру, чтобы в итоге все стали ее участниками, то нужно вывести номера гостей в том порядке, в каком они могут вступать в игру. Если всех вовлечь в игру не удастся, выведите одно число - 0. Пример 1 Пример входного файла 5 4 4 0 3 1 4 1 3 2 2 Пример выходного файла 2 3 5 4 1 Пример 2 Пример входного файла 3 1 1 1 1 1 1 Пример выходного файла 0 Пример 3 Пример входного файла 1 0 0 Пример выходного файла 1
Комментарии. После двух занятий из серии "вспомнить все" школьникам был устроен зачет по основным конструкциям языка паскаль.
Комментарии. Далее идет серия задач на тему "строки".
Задача 207 (Скачать архив)
Входной файл содержит одну строку, в которой записаны фамилия и имя человека (разделяющиеся ровно одним пробелом). В выходной файл выведите эту же информацию, однако сначала имя, а потом фамилию. Пример входного файла: Pupkin Vasya Пример выходного файла: Vasya Pupkin
Задача 208 (Скачать архив)
Во входном файле записана одна строка текста (не больше 255 символов). В выходной файл нужно вывести эту же строку, удалив все парные пробелы (то есть если где-то в строке идет подряд 2 или больше пробелов, то в этом месте нужно оставить только один из них). Пример входного файла My name is Vasya... Пример выходного файла My name is Vasya...
Задача 209 (Скачать архив)
В первой строке входного файла записано число N (от 1 до 100). В каждой из последующих N строк записано сначала некоторое целое число (из диапазона от 0 до 10000), затем пробел, и затем некоторый текст (не более 20 символов). В выходной файл требуется вывести информацию в том же формате, увеличив число в каждой строке (кроме первой, где записано число N) на 1. Пример входного файла 2 14 Start 42 Stop Пример выходного файла 2 15 Start 43 Stop
Задача 210 (Скачать архив)
В первой строке входного файла записано число N (от 1 до 100). В каждой из последующих N строк записано сначала имя человека (не более 20 символов, без пробелов), а затем через пробел число (от 1 до 200) - его возраст. В выходной файл требуется вывести информацию в том же формате, увеличив число в каждой строке (кроме первой, где записано число N) на 1. Пример входного файла 2 Vasya 15 Emmanuil 137 Пример выходного файла 2 Vasya 16 Emmanuil 138
Задача 211 (Скачать архив)
Задача "Копирование файла" Дан файл input.txt (при этом в нем могут быть строки длиннее 255 символов, строк может быть много и т.д.). Создать файл output.txt в точности такой же, как input.txt
Задача 212 (Скачать архив)
Задача. Найди 1543 Дан входной файл (в нем может быть текст, сколь угодно длинные строки и т.д.). Если в нем встречается число 1543, в выходной файл выведите слово URA, если же 1543 в файле не встречается, выведите NO. Пример 1 входного файла hgdfjgkdghkdjgkgkd1543gjdlgkdjlg Пример 1 выходного файла URA Пример 2 входного файла 1=5 4=3 Пример 2 выходного файла NO
Задача 213 (Скачать архив)
В первой строке входного файла записано арифметическое выражение в виде: <число> <операция> <число> = Число - это натуральное число, не превышающее 10000. <операция> - один из знаков +, -, * В начале строки, в конце строки, а также между числами и знаком операции, числом и = может быть любое число пробелов (а может пробелов и не быть). Гарантируется, что длина строки не превышает 200 символов. В выходной файл выведите результат вычисления выражения. Пример входного файла 154 +3 = Пример выходного файла 157
Задача 214 (Скачать архив)
Сколько раз встречается? Входной файл состоит из двух строк. Посчитайте, сколько раз первая строка встречается в качестве подстроки во второй. Длина каждой из строк не превышает 255 символов. Пример входного файла abab abababcab Пример выходного файла: 2 (Пояснение: подстрока abab встречается во второй строке дважды: начиная с 1-го символа и начиная с 3-го символа)
Задача 216 (Скачать архив)
Статистика. В файле input.txt задан текст. Напишите программу, которая посчитает статистику - сколько раз встречается буква A, сколько - B и т.д. При этом большие и маленькие латинские буквы считать одинаковыми. В файле могут быть сколь угодно длинные строки. Длина файла не превышает 100 Кб. Входные данные Во входном файле записан текст, состоящий из английских букв (больших и маленьких), знаков препинания, цифр и т.д. Выходные данные В выходной файл вывести 26 строк. Каждая строка должна соответствовать латинской букве, буквы должны идти в алфавитном порядке. Каждая строка должна содержать сначала большую латинскую букву, которой она соответствует, пробел, символ - (тире), пробел и число: сколько раз буква встречается во входном файле. Пример входного файла Ab - a Пример выходного файла A - 2 B - 1 C - 0 D - 0 <...здесь в выходном файле перечисляются все буквы...> Z - 0
Задача 217 (Скачать архив)
Задача "Таймер" Таймер - это часы, которые умеют подавать звуковой сигнал по прошествии некоторого периода времени. Напишите программу, которая определяет, когда должен быть подан звуковой сигнал. Формат входных данных В первой строке входного файла записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет ограничениям: ЧЧ - от 00 до 23, ММ и СС - от 00 до 60. Во второй строке записан интервал времени, который должен быть измерен. Интервал записывается в формате Ч:М:С (где Ч, М и С - от 0 до 109, без ведущих нулей). Дополнительно если Ч=0 (или Ч=0 и М=0), то они могут быть опущены. Например, 100:60 на самом деле означает 100 минут 60 секунд, что то же самое, что 101:0 или 1:41:0. А 42 обозначает 42 секунды. 100:100:100 - 100 часов, 100 минут, 100 секунд, что то же самое, что 101:41:40. Формат выходных данных В выходной файл выведите в формате ЧЧ:ММ:СС время, во сколько прозвучит звуковой сигнал. При этом если сигнал прозвучит не в текущие сутки, то дальше должна следовать запись +<кол-во> days. Например, если сигнал прозвучит на следующий день - то +1 days. Примеры Входные файлы Выходные файлы 01:01:01 48:0:0 01:01:01+2 days 01:01:01 58:119 02:01:00 23:59:59 1 00:00:00+1 days
Задача 218 (Скачать архив)
Задача "Распаковка строчки"
Будем рассматривать только строчки, состоящие из заглавных
латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD.
Длина этой строки равна 14. Поскольку строка состоит только
из латинских букв, повторяющиеся символы могут быть удалены
и заменены числами, определяющими количество повторений.
Таким образом, данная строка может быть представлена как 4AB5C4D.
Длина такой строки 7. Описанный метод мы назовем упаковкой строки.
Напишите программу, которая берет упакованную строчку и восстанавливает
по ней исходную строку.
Формат входных данных
Входной файл содержит одну упакованную строку. В строке могут
встречаться только конструкции вида nA,
где n - количество повторений символа (целое число от 2 до 99),
а A - заглавная латинская буква,
либо конструкции вида A, то есть символ без числа, определяющего
количество повторений. Максимальная длина строки не превышает 80.
Формат выходных данных
В выходной файл выведите восстановленную строку. При этом строка
должна быть разбита на строчки длиной ровно по 40 символов
(за исключением последней, которая может содержать меньше 40 символов).
Примеры
Входные файлы Выходные файлы
3A4B7D AAABBBBDDDDDDD
22D7AC18FGD DDDDDDDDDDDDDDDDDDDDDDAAAAAAACFFFFFFFFFF
FFFFFFFFGD
95AB AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAB
40AB39A AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Комментарии. Далее изучались темы "процедуры и функции" и "длинная арифметика". Преподавание этих тем велось без использования системы автоматической проверки решений, поэтому в данный архив задачи на эти темы не попали.
Комментарии. Следующая изучаемая тема - динамическое программирование. Традиционно я рассказываю эту тему на примере большого количества задач. Некоторые задачи носят обязательный характер, то есть разбираются и пишутся со всеми, а некоторые адресованы в основном сильным школьникам.
Задача 231 (Скачать архив)
В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути). Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол. Входные данные Во входном файле задано два числа N и M - размеры таблицы (1≤N≤20, 1≤M≤20). Затем идет N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100). Выходные данные В выходной файл запишите минимальную сумму, потратив которую можно попасть в правый нижний угол. Пример входного файла 3 4 1 1 1 1 5 2 2 100 9 4 2 1 Пример выходного файла 8
Задача 232 (Скачать архив)
Задача "Гвоздики" На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить какие-то пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна. Входные данные В первой строке входного файла записано число N - количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000). Выходные данные В выходной файл нужно вывести единственное число - минимальную суммарную длину всех ниточек. Пример входного файла 5 4 10 0 12 2 Пример выходного файла 6
Задача 233 (Скачать архив)
Задача 3. "Подпоследовательности" Дана последовательность, требуется найти длину наибольшей возрастающей подпоследовательности. Входные данные В первой строке входного файла записано число N - длина последовательности (1 ≤ N ≤ 1000). Во второй строке записана сама последовательность (через пробел). Числа последовательности - целые числа, не превосходящие 10000 по модулю. Выходные данные В выходной файл требуется вывести наибольшую длину возрастающей подпоследовательности. Пример входного файла 6 3 29 5 5 28 6 Пример выходного файла 3
Задача 234 (Скачать архив)
Задача "Лесенки" Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий. --- | | --------- | | | | | ----------- | | | | | | ----------------- | | | | | | | | | ----------------- Подсчитать число лесенок, которое можно построить из N кубиков. Входные данные Во входном файле записано число N (1≤N≤100). Выходные данные В выходной файл вывести искомое число лесенок. Пример Пример входного файла 3 Пример выходного файла 2
Задача 235 (Скачать архив)
Задача "Ход конем" Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-4927. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8. Клавиатура телефона выглядит так: 789 456 123 0 Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня. Входные данные Во входном файле записано целое число N (1≤N≤100). Выходные данные Выведите в выходной файл искомое количество телефонных номеров. Пример входного файла 2 Пример выходного файла 16
Задача 236 (Скачать архив)
Задача "Восстановление скобок" Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение. Входные данные Первая строка входного файла содержит заданный шаблон длиной не более 80 символов. Выходные данные Выведите в выходной файл искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2*10^9. Пример входного файла ????(? Пример выходного файла 2
Задача 237 (Скачать архив)
Задача "Шаблон и слово" Требуется определить подходит ли заданное слово под заданный шаблон. Шаблон задается большими латинскими буквами, знаками "?" - любой символ, "*" - любая последовательность символов (даже пустая). Входные данные: в первых двух строках записаны шаблон и слово: в одной строки записан шаблон - последовательность больших латинских букв, "?" и "*", в другой - слово, состоящее только из больших латинских букв (строки короче 100 символов). Выходные данные: вывести YES, если слово подходит или NO, если нет. Примеры input.txt ABBCDA A*CDA output.txt YES input.txt AADAAVA A*DA*AA* output.txt NO
Задача 238 (Скачать архив)
Задача B Покупка билетов Имя входного файла: b.in Имя выходного файла: b.out Максимальное время работы на одном тесте: 5 секунд Максимальный объем используемой памяти: 4 мегабайта Максимальная оценка за задачу: 100 баллов За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя "постояльцев" очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех. Однако для борьбы со спекулянтами кассир продавала не более 3-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека. Известно, что на продажу i-му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов - Bi секунд, трех билетов - Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели. Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны). Формат входных данных Во входном файле записано сначала число N - количество покупателей в очереди (1≤N≤5000). Далее идет N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются начиная от кассы. Формат выходных данных В выходной файл выведите одно число - минимальное время в секундах, за которое могли быть обслужены все покупатели. Примеры b.in 5 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1 b.out 12 b.in 2 3 4 5 1 1 1 b.out 4
Задача 239 (Скачать архив)
(Дополнительная задача) Шаблоны с ? и * Шаблоном называется строка, состоящая из английских букв (a,...,z, A,...,Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * - на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону. Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблона, либо выдать сообщение, что такой строки не существует. Входные данные Заданные шаблоны записаны в первых двух строках входного файла. Длина каждого шаблона не превосходит 80 символов. Выходные данные В выходной файл следует вывести строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение <-1> Пример входного файла A* *B Пример выходного файла AB
Задача 240 (Скачать архив)
1.3. Уравнение с пропущенными цифрами Задано уравнение вида A + B = C, где A, B и C - неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса (?). Примером такого уравнения является ?2+34=4?. Требуется так подставить вместо знаков вопроса цифры, чтобы это равенство стало верным, либо определить, что это невозможно. Найти только одно из возможных решений. Входные данные Заданное уравнение содержится в первой строке входного файла. Длина уравнения не превышает 80 символов. Входной файл не содержит пробелов. Выходные данные В выходной файл требуется вывести верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение "No solution". Пример входного файла ??2?4+9?=355 Пример выходного файла 00264+91=355
Задача 241 (Скачать архив)
(Дополнительная задача) 1.6. Сжатие текста Архиватором называется программа, предназначенная для сжатия данных за счет удаления избыточной информации. В этой задаче вашей целью является разработка простейшего архиватора текстов на русском языке. В таких текстах многие знаки стандартной таблицы символов не встречаются, поэтому они могут быть использованы для замены часто повторяющихся последовательностей символов. Заданы последовательности, которые могут быть заменены некоторыми символами английского алфавита, а также исходный текст, который следует сжать. Поскольку в исходном тексте эти последовательности могут накладываться друг на друга, результат сжатия существенно зависит от порядка замен. Ваша задача состоит в том, чтобы получить сжатый текст наименьшей длины. Входные данные В первой строке входного файла задано целое число R - количество заменяемых последовательностей и целое число N - количество строк в исходном тексте (1≤N≤1000). Далее следуют R пар строк, описывающих возможные замены. Первая строка каждой пары содержит заменяемую последовательность, а вторая - заменяющий символ, являющийся большой или маленькой английской буквой. Различным заменяемым последовательностям соответствуют разные английские буквы (большие и маленькие буквы различаются). В следующих N строках записан текст, подлежащий сжатию. В этом тексте, также как и в заменяемых последовательностях, отсутствуют буквы английского алфавита. Выходные данные В выходной файл вывести заархивированный текст. Примечания Символы перевода строки не заменяются (т.е. замены возможны только внутри строк). Длина каждой строки входного файла не превосходит 255 символов. Пример входного файла 8 10 рхиватор b замен D ены F зам G быт h про d сжат f ом называется g Архиватором называется программа, предназначенная для сжатия данных за счет удаления избыточной информации. В этой задаче вашей целью является разработка простейшего архиватора текстов на русском языке. В таких текстах многие знаки стандартной таблицы символов не встречаются, поэтому они могут быть использованы для замены часто повторяющихся последовательностей символов. Заданы последовательности, которые могут быть заменены некоторыми символами английского алфавита, а также исходный текст, который следует сжать. Поскольку в исходном тексте эти последовательности могут накладываться друг на друга, результат сжатия существенно зависит от порядка замен. Ваша задача состоит в том, чтобы получить сжатый текст наименьшей длины. Пример выходного файла Аbg dграмма, предназначенная для fия данных за счет удаления изhочной информации. В этой задаче вашей целью является разработка dстейшего аbа текстов на русском языке. В таких текстах многие знаки стандартной таблицы символов не встречаются, поэтому они могут hь использованы для Dы часто повторяющихся последовательностей символов. Заданы последовательности, которые могут hь DF некоторыми символами английского алфавита, а также исходный текст, который следует fь. Поскольку в исходном тексте эти последовательности могут накладываться друг на друга, результат fия существенно зависит от порядка D. Ваша задача состоит в том, чтобы получить fый текст наименьшей длины.
Задача 242 (Скачать архив)
(Дополнительная задача)
1.7. Пустоты в кубе
Жюри составило отчет об учебно-тренировочных сборах по информатике
и собирается распечатать его на стандартном листе бумаги. Весь
отчет набран одним моноширинным шрифтом, т.е. все символы (включая
пробелы) имеют одинаковую ширину. Длина строки при печати этим
шрифтом на листе бумаги равна S.
Назовем пустотой последовательность пробелов между соседними словами
в строке, а также от начала строки до первого слова в ней и от
последнего слова в строке до конца строки. Проблема, стоящая перед жюри,
состоит в том, что научный руководитель сборов Владимир Михайлович
Кирюхин отказывается читать текст, если сумма кубов длин пустот по всем
строкам не минимальна. Помогите жюри расположить отчет на листе бумаги так,
чтобы В.М. Кирюхин согласился его прочесть и утвердить результаты сборов.
Для достижения требуемого расположения текста на бумаге разрешается
заменять произвольную пробельную последовательность (т.е. непустую
последовательность подряд идущих пробелов и/или символов перевода
строки) любой другой пробельной последовательностью.
Входные данные
Первая строка входного файла содержит целое число S (1≤S≤80).
В последующих строках записан отчет, содержащий не более 500 слов.
Длина каждой строки отчета не превосходит 250 символов, а длина каждого
слова не превос-ходит S.
Выходные данные
Вывести в первую строку выходного файла минимально возможную сумму
кубов пустот по всем строкам. В последующие строки следует вывести
искомое расположение текста на листе бумаги.
Пример входного файла
30
Победители летних учебно-тренировочных сборов по информатике 1997 г.:
Владимир Мартьянов,
Анатолий Пономарев,
Николай Дуров,
Андрей Лопатин.
Пример выходного файла
325
Победители летних
учебно-тренировочных сборов по
информатике 1997 г.: Владимир
Мартьянов, Анатолий Пономарев,
Николай Дуров, Андрей Лопатин.
Комментарии. Задача 249 - довольно необычна. Существует огромное количество подходов к ее решению (можно придумать правила генерации предложений и "зашить" довольно большой словарь, а можно немножко подумать и придумать способы, как обойтись очень небольшим количеством слов). В результате решения этой задачи порой получаются довольно забавные тексты, эта задача очень непохожа на большинство олимпиадных задач, предоставляет школьникам очень большой размах для творчества (не только программисткого), и этим мне эта задача очень нравится. Эта задача автоматически проверяется лишь частично - проверяющая программа проверяет соблюдение формальных правил, дальше требуется вручную посмотреть, что тексты все-таки отвечают правилам русского языка. К сожалению, в задаче используются русские буквы, и это неминуемо приводит к проблемам с кодировками - предложенная проверяющая программа проверяет решение, считая что генерируется текст в DOS-кодировке.
Задача 249 (Скачать архив)
Задача "Шифровка" На контрольной по алгебре логики Филипп К. и Алла П. по ходу решения задачи хотят обмениваться наборами из 0 и 1, которые у них получаются. Но злобный учитель информатики очень строго следит за тем, чтобы в ходе контрольной ученики решали задачи самостоятельно. Правда, школьникам удалось воззвать к его человеческим чувствам, и он разрешил им обмениваться записками, содержание которых никак не связано с алгеброй логики. К счастью, Филипп и Алла успели договориться, что они будут шифровать наборы из 0 и 1 предложениями русского языка. Слово четной длины будет обозначать 0, нечетной длины - 1, знаки препинания при расшифровке не учитываются. Таким образом, расшифровать такую шифровку очень просто, а вот чтобы зашифровать какую-либо последовательность, требуется незаурядный литературный талант. Помогите им! Напишите программу, которая по введенной последовательности из 0 и 1, строит текст, соответствующий правилам русского языка, имеющий с точки зрения языка хоть какой-то (минимальный!) смысл, и который кодирует заданную последовательность. Входные данные В файле INPUT.TXT записано сначала число N (1≤N≤100) - длина последовательности, а затем последовательность из N чисел, каждое из которых является 0 или 1. Выходные данные В файл OUTPUT.TXT выведите текст на русском языке, который кодирует заданную последовательность. Обратите внимание! В тексте не должно быть одинаковых предложений (предложения считаются одинаковыми, если они совпадают с точностью до знаков препинания, если же они различаются хотя бы порядком следования слов, они уже считаются различными). А в одном предложении ни одно из слов не должно повторяться.
Комментарии. Следующие несколько задач - на алгоритм Дейкстры. Задачи на алгоритм Дейкстры (равно как и дальше задачи на какие-либо стандартные алгоритмы) подобраны по следующему принципу: сначала идет задача, которая встречается как этап в алгоритме, потом - задача просто на то, чтобы написать рассказанный алгоритм, а дальше - набор задач на использование этого алгоритма (при этом решение этих задач для слабых школьников уже не обязательно, а вот того, чтобы каждый мог написать рассказанный алгоритм, стоит добиваться). Задача 251 - это лишь подэтап в алгоритме Дейкстры, однако написав ее, дальше уже несложно написать и весь алгоритм Дейкстры целиком (хотя написание алгоритма "с нуля" вызывает у слабых школьников ступор). Естественно, что алгоритм Дейкстры школьникам рассказывается (хотя, безусловно, бывают школьники, которые могут его придумать сами, но такое встречается все-таки нечасто).
Задача 251 (Скачать архив)
Разминочная задача Во входном файле записано сначала число N (1≤N≤100), а затем N пар чисел. Первое число каждой пары - натуральное, не превышающее 30000. Второе число каждой пары - 0 или 1. Требуется найти и вывести в выходной файл номер пары, в которой второе число равно 1, а из всех таких пар ту, в которой первое число максимально (если таких пар несколько, выведите любую из них). Если пар, у которых второе число равно 1 нет, выведите в выходной файл -1. Пример входного файла 4 25 1 70 1 100 0 3 1 Пример выходного файла 2
Задача 252 (Скачать архив)
Задача "Дейкстра" Дан ориентированный взвешенный граф. Для него вам необходимо найти кратчайшее расстояние от одной заданной вершины до другой. Входные данные: В первой строке входного файла три числа: N, S и F (1 ≤ N ≤ 100; 1 ≤ S, F ≤ N), где N - количество вершин графа, S - начальная вершина, а F - конечная. В следующих N строках по N чисел - матрица смежности графа, где число в i-ой строке j-ом столбце соответствует ребру из i в j: -1 означает отсутствие ребра между вершинами, а любое неотрицательное число - присутствие ребра данного веса. На главной диагонали матрицы - всегда нули. Выходные данные: Вывести искомое расстояние или -1, если пути между указанными вершинами не существует. Пример входного файла: 3 1 2 0 -1 2 3 0 -1 -1 4 0 Пример выходного файла: 6 Описание алгоритма Дейкстры. Храним массив кратчайших уже найденных путей до каждой из вершин. Вначале расстояние до начального элемента - 0, до остальных - бесконечность N раз повторяем шаг алгоритма: 1) Находим вершину, из которой мы еще не ходили, и в расстояние до которой минимально 2) Ходим из этой вершины, т.е.: -Проверяем, если расстояние до данной вершины + ребро из нее в какую-то другую вершину меньше, чем расстояние до той вершины, уменьшаем расстояние до той вершины -Помечаем, что мы походили из этой вершины. После окончания мы получим массив кратчайших путей.
Комментарии. Описание алгоритма Дейкстры - это часть задачи (оно входит в условие задачи) для того, чтобы когда школьники его пишут он был у них перед глазами. При этом перед этим мы с ними подробно разбираем его у доски.
Задача 253 (Скачать архив)
Задача "Заправки" В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее количество денег. Входные данные Во входном файле записано сначала число N (1≤N≤100), затем идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (все это целые числа из диапазона от 0 до 100). Затем идет число M - количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами - номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя. Выходные данные В выходной файл выведите одно число - суммарную стоимость маршрута или -1, если добраться невозможно. Пример входного файла 4 1 10 2 15 4 1 2 1 3 4 2 4 3 Пример выходного файла 3 Комментарий Оптимальное решение - из 1-го города поехать в 3-й, а затем в 4-й. Горючее придется покупать в 1 и 3 городах. Пример входного файла 4 1 10 2 15 0 Пример выходного файла -1 Комментарий Добраться невозможно
Задача 254 (Скачать архив)
Задача "Заправки-2" (Такая же, как и предыдущая задача, но есть еще канистра вместимостью 1 бак) В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее количество денег. При этом есть еще канистра для бензина, куда входит столько же бензина, сколько входит в бак. В каждом городе можно заправить бак, залить бензин в канистру, залить и туда и туда, или же перелить бензин из канистры в бак. Входные данные Во входном файле записано сначала число N (1≤N≤100), затем идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (все это целые числа из диапазона от 0 до 100). Затем идет число M - количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами - номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя. Выходные данные В выходной файл выведите одно число - суммарную стоимость маршрута или -1, если добраться невозможно. Пример входного файла 4 1 10 2 15 4 1 2 1 3 4 2 4 3 Пример выходного файла 2 Комментарий Оптимальное решение - из 1-го города (зарпавив бак и залив в канистру) поехать в 3-й, там перелить бензин из канистры в бак и поехать в 4-й. Пример входного файла 4 1 10 2 15 0 Пример выходного файла -1 Комментарий Добраться невозможно
Задача 255 (Скачать архив)
"Автобусы". Между некоторыми деревнями Пермской области ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день (например, в Ляды из Перми автобус приходит лишь 3 раза в сутки). Ирине Владимировне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d). Входные данные Во входном файле записано число N - общее число деревень (1≤N≤100), деревни d и v, затем количество автобусных рейсов R (0≤R≤10000). Затем - описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена - целые от 0 до 10000). Если в момент t пассажир приезжает в какую-то деревню, то уехать из нее он может в любой момент времени, начиная с t. Выходные данные В выходной файл вывести минимальное время, когда пассажир может оказаться в деревне v. Если он не сможет с помощью указанных автобусных рейсов добраться из d в v, вывести -1. Пример входного файла 3 1 3 4 1 0 2 5 1 1 2 3 2 3 3 5 1 1 3 10 Пример выходного файла 5
Задача 256 (Скачать архив)
Задача B Домой на электричках Имя входного файла: b.in Имя выходного файла: b.out Максимальное время работы на одном тесте: 3 секунды Максимальный объем используемой памяти: 8 мегабайт Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут). Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E. Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, когда ребята могут оказаться дома. Формат входных данных Во входном файле записаны сначала числа N (2 ≤ N ≤ 100) и E (2 ≤ E ≤ N). Затем записано число M (0 ≤ M ≤ 100), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа Ki (2 ≤ Ki ≤ N) - количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе - время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 10^9). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении - либо от города, либо к городу. Формат выходных данных В выходной файл выведите одно число - минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите -1. Пример входного файла 5 3 4 2 1 5 2 10 2 2 10 4 15 4 5 0 4 17 3 20 2 35 3 1 2 3 40 4 45 Пример выходного файла 20
Задача 257 (Скачать архив)
Задача "Пиво в розлив" Имеются три пробирки, вместимостью 100 миллилитров каждая. Первые две пробирки имеют риски, одинаковые на обеих пробирках. Возле каждой риски надписано целое число миллилитров, которое вмещается в часть пробирки от дна до этой риски (см. рисунок). Изначально первая пробирка содержит 100 миллилитров пива, а остальные две пусты. Требуется написать программу, которая выясняет, можно ли отделить в третьей пробирке один миллилитр пива, и если да, то находит минимально необходимое для этого число переливаний. Пиво можно переливать из одной пробирки в другую до тех пор, пока либо первая из них не станет пустой, либо одна из пробирок не окажется заполненной до какой-либо риски.
Входные данные В первой строке входного файла содержится число рисок N (1≤N≤20), имеющихся на каждой из первых двух пробирок. Затем в порядке возрастания следуют N целых чисел V1,..., VN (1≤Vi≤100), приписанных рискам. Последняя риска считается сделанной на верхнем крае пробирок (VN = 100). Выходные данные В первой строке выходного файла должна содержаться строка "YES", если в третьей пробирке возможно отделить один миллилитр пива, и "NO" - в противном случае. В случае ответа "YES" во вторую строку необходимо вывести искомое количество переливаний. Пример входного файла 4 13 37 71 100 Пример выходного файла YES 8
Комментарии. Следующая серия задач - на алгоритм Флойда.
Задача 258 (Скачать архив)
Задача "Флойд-1" Дан полный (т.е. есть ребра между всеми парами вершин) ориентированный взвешенный граф. По его матрице смежности постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса. Входные данные: В первой строке входного файла записано единственное число: N (1 ≤ N ≤ 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы - всегда нули. Выходные данные: Выведите N строк по N чисел - матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно быть равно весу кратчайшего пути из вершины i в вершину j. Пример входного файла 4 0 5 9 100 100 0 2 8 100 100 0 7 4 100 100 0 Пример выходного файла 0 5 7 13 12 0 2 8 11 16 0 7 4 9 11 0
Задача 259 (Скачать архив)
Задача "Флойд-Макс" Дан ориентированный взвешенный граф. В нём вам необходимо найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин. Входные данные: В первой строке входного файла единственное число: N (1 ≤ N ≤ 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует ребру из вершины i в вершину j): -1 означает отсутствие ребра между вершинами, а любое неотрицательное число - присутствие ребра данного веса. На главной диагонали матрицы - всегда нули. Выходные данные: Вывести искомое максимальное кратчайшее расстояние. Пример входного файла 4 0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0 Пример выходного файла 16
Задача 260 (Скачать архив)
Задача "Флойд-существование" Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин определить, существует ли кратчайший путь между ними или нет. Комментарий: Кратчайший путь может не существовать по двум причинам: -Нет ни одного пути -Есть пути сколь угодно маленького веса Входные данные: В первой строке входного файла записано единственное число: N (1 ≤ N ≤ 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j): число 0 обозначает отсутствие ребра, а любое другое число - наличие ребра соответствующего веса. Все числа по модулю не превышают 100. Выходные данные: Выведите N строк по N чисел. j-ое число в i-ой строке должно соответствовать кратчайшему пути из вершины i в вершину j. Число должно быть равно 0, если пути не существует, 1 - если существует кратчайший путь, и 2 - если пути существуют, но бывают пути сколь угодно маленького веса. Пример входного файла 5 0 1 2 0 0 1 0 3 0 0 2 3 0 0 0 0 0 0 4 -1 0 0 0 -1 0 Пример выходного файла 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 2 2 0 0 0 2 2
Комментарии. Научившись считать длины кратчайших путей, стоит обратить внимание на то, как по этим значениям восстановить сам путь. Задача 261 - про это. Каким алгоритмом ищутся длины кратчайших путей здесь - не существенно.
Задача 261 (Скачать архив)
Кратчайший путь Задан ориентированный граф без кратных ребер. Найти кратчайший путь между двумя вершинами. Все веса ребер положительны. Путь всегда существует. Ограничения Максимальное количество вершин не больше 100. Входные и выходные данные Во входном файле в первой строке два числа - n - количество вершин в графе, и m - число ребер в графе. В следующей строке номера начальной и конечной вершины. Далее, в m строчках записаны по три числа, описывающие по одному ребру. Первое число - номер вершины, из которой идет ребро, второе - номер вершины куда идет ребро, третье число - вес ребра (от 0 до 1000). В файл output.txt необходимо выдать стоимость кратчайшего пути из начальной вершины в конечную, и затем сам этот путь: номера вершин через пробел, включая начальную и конечную вершину. Пример входного файла 4 5 2 3 2 1 1 2 3 25 4 3 10 2 4 2 1 3 3 1 2 0 Пример выходного файла 4 2 1 3
Комментарии. Следующая задача - на алгоритм Форда-Белмана.
Задача 262 (Скачать архив)
Задача "Форд-Белман" Дан ориентированный граф, возможно, с кратными ребрами и петлями. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют. Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин. Входные данные Во входном файле записано сначала число N (1≤N≤100) - количество вершин графа, далее идет число M (0≤M≤10000) - количество ребер. Далее идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес - целое число от -100 до 100). Выходные данные В выходной файл выведите N чисел - расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000. Пример входного файла 4 5 1 2 10 2 3 10 1 3 100 3 1 -10 2 3 1 Пример выходного файла 0 10 11 30000
Задача 263 (Скачать архив)
"Лабиринт знаний"
В ЛКШ построили аттракцион "Лабиринт знаний". Лабиринт
представляет собой N комнат, занумерованных от 1 до N,
между некоторыми из которых есть двери. Когда человек проходит
через дверь, показатель его знаний изменяется на определенную
величину, фиксированную для данной двери. Вход в лабиринт
находится в комнате 1, выход - в комнате N. Каждый ЛКШонок
проходит лабиринт ровно один раз и попадает в группу в зависимости
от набранных знаний (при входе в лабиринт этот показатель равен нулю).
Ваша задача показать наилучший результат.
Входные данные. Первая строка входного файла содержит целые числа N
(1 ≤ N ≤ 2000) - количество комнат и M (1 ≤ M ≤ 10000) -
количество дверей. В каждой из следующих M строк содержится описание
двери - номера комнат, из которой она ведет и в которую она ведет,
а также целое число, которое прибавляется к количеству знаний при
прохождении через дверь (это число по модулю не превышает 10000).
Двери могут вести из комнаты в нее саму, между двумя комнатами
может быть более одной двери.
Выходные данные. В выходной файл выведите ":)" - если можно получить
неограниченно большой запас знаний, ":(" -
если лабиринт пройти нельзя, и максимальное количество
набранных знаний в противном случае.
Пример.
input.txt
2 2
1 2 5
1 2 -5
output.txt
5
Задача 264 (Скачать архив)
Задача "Цикл" Дан граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его. Входные данные. Во входном файле в первой строке число N (1≤N≤100) - количество вершин графа. В следующих N строках находится по N чисел - матрица смежности графа. Все веса ребер не превышают по модулю 10000. Если ребра нет, то соответствующее число равно 100000. Выходные данные. В первой строке выходного файла выведите "YES", если цикл существует или "NO" в противном случае. При его наличии выведите во второй строке количество вершин в искомом цикле (считая одинаковые первую и последнюю) и в третьей строке - вершины, входящие в этот цикл в порядке обхода. input.txt 2 0 -1 -1 0 output.txt YES 3 1 2 1
Задача 265 (Скачать архив)
Вам дана табличка, состоящая из N строк и M столбцов. В каждой клетке таблицы стоит либо 0, либо 1. Расстоянием между клетками (x1,y1) и (x2,y2) называется |x1-x2|+|y1-y2|. Вам нужно построить другую таблицу, в которой в каждой клетке стоит расстояние от данной до ближайшей клетки, содержащей 1 (в начальной таблице). Гарантируется, что хотя бы одна 1 в таблице есть. Входные данные В первой строке входного файла содержатся два натуральных числа, не превосходящих 100 - N и M. Далее идут N строк по M чисел - элементы таблицы. Выходные данные Выходной файл должен содержать N строк по M чисел - элементы искомой таблицы. Пример 2 3 0 0 1 1 0 0 Ответ 1 1 0 0 1 1
Задача 266 (Скачать архив)
На стандартной шахматной доске(8х8) живут красный и зеленый шахматные кони. Они беззаботно скачут по ней пощипывая шахматную травку. Сегодня у зеленого коня День Рождения. Кони решили отпраздновать это событие вместе. Для этого им нужно оказаться на одной клетке. Заметим, что красный и зеленый шахматные кони сильно отличаются от черного с белым: они ходят не по очереди, а одновременно, и если они оказываются на одной клетке никто никого не съедает. Сколько ходов им потребуется, чтобы оказаться на одной клетке? Входные данные Во входном файле содержатся координаты коней, записанные по стандартным шахматным правилам (т.е. двумя символами - маленькая латинская буква (от a до h) и цифра (от 1 до 8) задающие столбец и строку соответственно) Выходные данные Выходной файл должен содержать наименьшее необходимое количество ходов, либо -1, если кони не могут встретиться. Пример a1 a3 Ответ 1
Комментарии. Следующая серия задач посвящена остовным деревьям и алгоритмам их поиска - алгоритму Прима и Краскала. Начинается все с задач на понимание школьниками что такое дерево. Дальше идут две очень простых задачи, одна из которых соответствует шагу алгоритма Краскала, вторая - шагу алгоритма Прима.
Задача 267 (Скачать архив)
Задача "Дерево?" Дана матрица смежности неориентированного графа без петель и кратных ребер. Определить, является ли этот граф деревом. Входные данные Во входном файле записано сначала число N - количество вершин графа (от 1 до 100). Далее записана матрица смежности размером N*N, в которой 1 обозначает наличие ребра, а 0 - отсутствие. Матрица симметрична относительно главной диагонали. Выходные данные В выходной файл выведите сообщение YES, если граф является деревом и NO в противном случае Пример входного файла 3 0 1 0 1 0 1 0 1 0 Пример выходного файла YES
Задача 268 (Скачать архив)
Задача "Получи дерево" Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево. Входные данные Во входном файле заданы два числа - N (от 1 до 100) и M - количество вершин и ребер графа соответственно. Далее идет M пар чисел, задающих ребра. Гарантируется, что граф связный. Выходные данные В выходной файл выведите N-1 пару чисел - ребра, которые войдут в дерево. Ребра можно выводить в любом порядке. Пример входного файла 4 4 1 2 2 3 3 4 4 1 Пример выходного файла 1 2 2 3 4 3
Задача 269 (Скачать архив)
Каркас-разминка 1 Входные данные Во входном файле записано сначала число N (1≤N≤100), а затем N чисел от 1 до 100 - элементы массива A[i]. Далее записаны два числа q и w (от 1 до N, не обязательно различные). Требуется все элементы, которые равны A[q] сделать равными A[w]. Постарайтесь сначала считать данные, потом сделать то, что требуется, и только потом вывести результат (а не делать преобразование на этапе вывода). Постарайтесь не пользоваться дополнительными массивами. Выходные данные В выходной файл выведите N чисел - элементы массива A[i] после преобразования. Пример входного файла 5 1 4 2 2 5 3 2 Пример выходного файла 1 4 4 4 5
Задача 270 (Скачать архив)
Каркас - разминка - 2 Входные данные Во входном файле задано число N (от 2 до 100) и матрица смежности полного неориентированного взвешенного графа (полный - обозначает, что есть ребра между всеми парами вершин). Все веса ребер - натуральные числа от 1 до 1000). Далее дано еще N чисел, каждое из которых либо 0, либо 1 - считается, что эти числа записаны в вершинах. Гарантируется, что есть хотя бы один 0 и хотя бы одна 1. Выходные данные Найдите и выведите в выходной файл две вершины так, чтобы: -в первой из них стоял 0 -во второй из них стояла 1 -вес ребра между этими вершинами был минимально возможным. Если таких пар несколько, выведите любую из них. Пример входного файла 3 0 1 2 1 0 4 2 4 0 1 0 0 Пример выходного файла 2 1
Задача 271 (Скачать архив)
Задача "Минимальный каркас" От вас требуется определить вес минимального остовного дерева для неориентированного взвешенного графа. Входные данные: В первой строке входного файла числа N и M (1 ≤ N ≤ 100; 1 ≤ M ≤ 6000), где N - количество вершин в графе, а M - количество рёбер. Далее в M строках следует по тройке чисел A, B, C, где A и B - номера вершин, соединённых ребром, а C - вес ребра (натуральное число, не превышающее 30000) Выходные данные: Вывести одно число - искомый вес. Пример входного файла 3 3 1 2 1 2 3 2 3 1 3 Пример выходного файла 3
Комментарии. Следующие темы - рекурсия, перебор, комбинаторика. Знакомство с рекурсией было дано на примере очень простых задач, которые предлагалось решить с помощью рекурсии и без использования циклов. Система автоматической проверки, к сожалению, не проверяет того, что задача решается именно рекурсией. Учитывая простоту задач, школьникам было предложено поучиться проверять свои работы самостоятельно.
Хочется обратить внимание вот на что: рекурсия изучается достаточно поздно. Изучение рекурсии начинается на задачах, которые уже не раз разбирались, и которые должны быть понятны школьникам, правда, добавляется довольно искусственный запрет на использование циклов. Этот запрет объясняется тем, что "сейчас мы с вами на простых задачах изучим некоторый инструмент, который реально в этих задачах и не нужен. Но дальше нам этот инструмент понадобится на других (уже не столь простых) задачах, которые без него решать будет еще сложнее."
Напишите следующие программы, и самостоятельно проверьте их правильность. Во всех программах должна использоваться рекурсия. Пожалуйста, в комментариях в начале 1-й программы напишите свою фамилию и имя. 1) Вводится число N (не более 15). Вычислите N-ое число Фибоначчи. 2) Вводится число N (не больше 10). Вычислите N! В программе не должно быть ни одного цикла. 3) Вводится число N и N элементов массива. Найдите величину минимального элемента массива (в программе не должно быть циклов, кроме цикла для ввода, в котором запрещается делать что-либо, кроме ввода данных. 4) Та же задача, что и предыдущая, только требуется посчитать сумму элементов массива. 5) Вводится число N и N элементов массива. Требуется, как и ранее, посчитать сумму элементов массива. В программе запрещается использовать циклы. 6) Вводится число N и N элементов массива. Требуется вывести эти элементы в обратном порядке. В программе запрещается описывать массивы и использовать циклы. 7) Вспомним алгоритм Евклида найдите НОД двух чисел, не используя циклов. 8) Вводятся два числа - N и K. Требуется вывести в файл все цепочки длины N такие, что на каждом месте может стоять любое число от 1 до K. Например, для N=2, K=3 должно быть выведено: 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
Комментарии. Также, без автоматической проверки, давалась и тема рекурсивной генерации объектов.
Во всех задачах выведите сначала сами объекты, а затем - их количество.
Задача 1.
Даны два числа N и K. Выведите все последовательности длины
N, в которых на каждом месте может стоять любое число от 1 до K.
Задача 2.
Даны два числа N и K. Выведите все последовательности длины
N, в которых на каждом месте может стоять любое число от 1 до K,
но не могут два одинаковых числа идти подряд.
Задача 3.
Дано число N. Выведите все перестановки из N элементов.
Задача 4.
Дано число N. Выведите все подмножества N-элементного множества.
Задача 5.
Дано число N и число K (K<=N). Выведите все K-элементные подмножества
множества из N элементов (чисел от 1 до N).
Задача 6.
Дано число N. Выведите все возможные представления числа N в виде
суммы натуральных слагаемых (при этом считая, что 1+2 и 2+1 - это
разные представления).
Задача 7.
Дано число N. Выведите все возможные представления числа N в виде суммы
натуральных слагаемых (при этом считая, что 1+2 и 2+1 - это одинаковые
представления, то из них должно быть выведено только одно).
Задача 8.
Дано число N. Сгенерируйте все правильные скобочные последовательности из
N пар скобок.
Задача 9.
Даны числа N и K. Выведите все разбиения N-элементного множества на
K непустых множеств. При этом разбиения, отличающиеся порядком множеств,
считаются одинаковыми (например, разбиваем множество из 3-х элементов на
2 подмножества, тогда разбиения {(1,2)(3)} и {(3),(1,2)} считаются
одинаковыми, а {(1,2)(3)} и {(1,3)(2)} - различными.
Задача 10.
Дано число N. Выведите все разбиения множества N на подмножества
(разбиения, отличающиеся порядком множеств считаются одинаковыми).
Комментарии. Следующая серия задач - решение ребусов. Каждая следующая задача здесь чуть сложнее предыдущей и таит свои подводные камни. Следует обратить внимание, что в последней задаче критично время работы (хотелось, чтобы школьники делали в процессе перебора некоторые отсечения). Поэтому ограничение времени нужно выставлять в этой задаче исходя из условий, в которых решения будут тестироваться.
Задача 272 (Скачать архив)
Задача "Ребус-1" Время работы вашей программы не должно превышать 10 секунд Напишите программу, которая найдет все решения ребуса ABCD+DCBA=CEEC Решением ребуса называется такая замена букв цифрами, что каждая буква заменяется цифрой от 1 до 6 ( другие цифры в этом ребусе не допускаются) так, что разные буквы заменяются разными цифрами, и написанное равенство оказывается верным. Входные данные Вы можете считать, что входной файл в этой задаче отсутствует (однако реально в единственной строке входного файла будет записан решаемый ребус). Выходные данные Выведите каждое решение ребуса на отдельной строке. Решение выводится в виде верного равенства, соответствующего описанному ребусу, в котором все буквы заменены цифрами. Пример (для другого ребуса). Если бы мы решали ребус A+B=CD, и допускались бы цифры от 1 до 9, то входной файл содержал бы строку A+B=CD а выходной файл мог бы быть таким: 3+9=12 4+8=12 4+9=13 5+7=12 5+8=13 5+9=14 6+7=13 6+8=14 6+9=15 7+5=12 7+6=13 7+8=15 7+9=16 8+4=12 8+5=13 8+6=14 8+7=15 8+9=17 9+3=12 9+4=13 9+5=14 9+6=15 9+7=16 9+8=17
Задача 273 (Скачать архив)
Задача "Ребус-2" Время работы вашей программы не должно превышать 20 секунд Напишите программу, которая найдет все решения ребуса ABCD+EFGDF=EHCIG Решением ребуса называется такая замена букв цифрами, что каждая буква заменяется цифрой от 1 до 9 (цифра 0 в этом ребусе не допускается) так, что разные буквы заменяются разными цифрами, и написанное равенство оказывается верным. Входные данные Вы можете считать, что входной файл в этой задаче отсутствует (однако реально в единственной строке входного файла будет записан решаемый ребус). Выходные данные Выведите каждое решение ребуса на отдельной строке. Решение выводится в виде верного равенства, соответствующего описанному ребусу, в котором все буквы заменены цифрами. Пример (для другого ребуса). Если бы мы решали ребус A+B=CD, то входной файл содержал бы строку A+B=CD а выходной файл мог бы быть таким: 3+9=12 4+8=12 4+9=13 5+7=12 5+8=13 5+9=14 6+7=13 6+8=14 6+9=15 7+5=12 7+6=13 7+8=15 7+9=16 8+4=12 8+5=13 8+6=14 8+7=15 8+9=17 9+3=12 9+4=13 9+5=14 9+6=15 9+7=16 9+8=17
Задача 274 (Скачать архив)
Задача "Ребус-3" Время работы вашей программы не должно превышать 10 секунд Напишите программу, которая найдет все решения ребуса ABCD+DCBA=CEEC Решением ребуса называется такая замена букв цифрами, что каждая буква заменяется цифрой от 1 до 9 (цифра 0 в этом ребусе не допускается) так, что разные буквы заменяются разными цифрами, и написанное равенство оказывается верным. Входные данные Вы можете считать, что входной файл в этой задаче отсутствует (однако реально в единственной строке входного файла будет записан решаемый ребус). Выходные данные Выведите каждое решение ребуса на отдельной строке. Решение выводится в виде верного равенства, соответствующего описанному ребусу, в котором все буквы заменены цифрами. Пример (для другого ребуса). Если бы мы решали ребус A+B=CD, то входной файл содержал бы строку A+B=CD а выходной файл мог бы быть таким: 3+9=12 4+8=12 4+9=13 5+7=12 5+8=13 5+9=14 6+7=13 6+8=14 6+9=15 7+5=12 7+6=13 7+8=15 7+9=16 8+4=12 8+5=13 8+6=14 8+7=15 8+9=17 9+3=12 9+4=13 9+5=14 9+6=15 9+7=16 9+8=17
Задача 275 (Скачать архив)
Задача коммивояжера Ограничение времени работы на одном тесте - 10 секунд Дан граф без петель и кратных ребер, все ребра имеют вес, выражающийся натуральным числом. Требуется в этом графе найти путь, проходящий по всем вершинам (причем по каждой - ровно один раз), и в конце возвращающийся в начальную вершину, при этом суммарный вес всех ребер в этом пути должен быть минимально возможным. Входные данные Во входном файле записано сначала число N (3≤N≤9). Затем идет матрица смежности графа (N*N чисел), число в i-ой строке j-ом столбце описывает ребро между вершинами i и j: если ребро существует, то это число равно его весу, если ребра не существует, то записано число 0. Граф неориентированный, то есть матрица симметрична относительно главной диагонали, на главной диагонали стоят нули. Вес каждого ребра задается натуральным числом от 1 до 1000. Выходные данные В выходной файл выведите N+1 число - найденный путь (первая и последняя его вершины должны совпадать). Гарантируется, что путь всегда существует. Пример входного файла 4 0 0 10 20 0 0 3 10 10 3 0 2 20 10 2 0 Пример выходного файла 1 3 2 4 1
Задача 276 (Скачать архив)
Та же задача, что и предыдущая, но 3≤N≤13 Ограничение времени работы на одном тесте - 10 секунд Задача коммивояжера Дан граф без петель и кратных ребер, все ребра имеют вес, выражающийся натуральным числом. Требуется в этом графе найти путь, проходящий по всем вершинам (причем по каждой - ровно один раз), и в конце возвращающийся в начальную вершину, при этом суммарный вес всех ребер в этом пути должен быть минимально возможным. Входные данные Во входном файле записано сначала число N (3≤N≤13). Затем идет матрица смежности графа (N*N чисел), число в i-ой строке j-ом столбце описывает ребро между вершинами i и j: если ребро существует, то это число равно его весу, если ребра не существует, то записано число 0. Граф неориентированный, то есть матрица симметрична относительно главной диагонали, на главной диагонали стоят нули. Вес каждого ребра задается натуральным числом от 1 до 1000. Выходные данные В выходной файл выведите N+1 число - найденный путь (первая и последняя его вершины должны совпадать). Гарантируется, что путь всегда существует. Пример входного файла 4 0 0 10 20 0 0 3 10 10 3 0 2 20 10 2 0 Пример выходного файла 1 3 2 4 1
Задача 277 (Скачать архив)
Задача "Универсальный ребусорешатель" Время работы вашей программы не должно превышать 20 секунд Напишите программу, которая найдет все решения ребуса Решением ребуса называется такая замена букв цифрами, что каждая буква заменяется цифрой от 1 до 9 (цифра 0 в этой задаче не допускается) так, что разные буквы заменяются разными цифрами, и написанное равенство оказывается верным. Входные данные В единственной строке входного файла записан ребус. Ребус состоит из больших латинских букв, знаков плюс и равно и имеет вид <число>+<число≥<число>. Каждое число состоит не меньше чем из 1 и не больше, чем из 7 букв. Выходные данные Выведите каждое решение ребуса на отдельной строке. Решение выводится в виде верного равенства, соответствующего описанному ребусу, в котором все буквы заменены цифрами. Пример входного файла A+B=CD Пример выходного файла 3+9=12 4+8=12 4+9=13 5+7=12 5+8=13 5+9=14 6+7=13 6+8=14 6+9=15 7+5=12 7+6=13 7+8=15 7+9=16 8+4=12 8+5=13 8+6=14 8+7=15 8+9=17 9+3=12 9+4=13 9+5=14 9+6=15 9+7=16 9+8=17
Комментарии. Задачи 278, 279 (или вариант 279-й задачи - задача 280) - это задачи контрольной работы по теме рекурсия. Первая задача этой работы решалась на листочке:
Задача 1 (выполняется в тетради или на листочке) Примечание: то, что задача выполняется не на компьютере обозначает более мягкий подход к ее проверке. Итак, задача 1 ============== Как вам, вероятно, известно из математики, число сочетаний С[n,k] определяется в треугольнике Паскаля по формуле C[n,k]=C[n-1,k-1]+C[n-1,k] Напишите рекурсивную функцию, которая бы вычисляла C[n,k]: function C(n,k:integer):longint; Достаточно только написать функцию, основную программу писать не нужно.
Задача 278 (Скачать архив)
Ханойская башня Есть три стержня. На первом из них расположено N колец (1-е, верхнее, самое маленькое, N-ое, нижнее, самое большое). За один ход разрешается с любого стержня снять верхнее кольцо и надеть его на любой другой стержень. При этом запрещается класть большее кольцо на меньшее. Требуется, чтобы все кольца оказались на стержне номер 2. Входные данные Во входном файле записано одно число N (1≤N≤10) Выходные данные В выходной файл выведите последовательность команд. Каждая команда задается двумя числами - с какого стержня снимаем кольцо, и на какой надеваем Пример входного файла 2 Пример выходного файла 1 3 1 2 3 2
Задача 279 (Скачать архив)
"Двоечные последовательности" Вводится число N. Сгенерируйте в лексикографическом порядке все последовательности длины N, состоящие из чисел 2, 4, 5, в которых количество двоек не превосходит 2-х. В "лексикографическом порядке" обозначает, что если на первых X местах две последовательности совпадают, а на месте X+1 - различаются, то раньше должна идти та из них, в которой число на месте X+1 меньше. 1≤N≤10 Пример входного файла 3 Пример выходного файла 2 2 4 2 2 5 2 4 2 2 4 4 2 4 5 2 5 2 2 5 4 2 5 5 4 2 2 4 2 4 4 2 5 4 4 2 4 4 4 4 4 5 4 5 2 4 5 4 4 5 5 5 2 2 5 2 4 5 2 5 5 4 2 5 4 4 5 4 5 5 5 2 5 5 4 5 5 5
Задача 280 (Скачать архив)
"Троечные последовательности" Вводится число N. Сгенерируйте в анти-лексикографическом порядке все последовательности длины N, состоящие из чисел 3, 4, 5, в которых количество троек не превосходит двух. В "анти-лексикографическом" обозначает "в порядке, обратном к лексигогра- фическому" (см. пример). В "лексикографическом порядке" обозначает, что если на первых X местах две последовательности совпадают, а на месте X+1 - различаются, то раньше должна идти та из них, в которой число на месте X+1 меньше. В анти-лексикографическом, соответственно, наоборот. 1≤N≤10 Пример входного файла 3 Пример выходного файла 5 5 5 5 5 4 5 5 3 5 4 5 5 4 4 5 4 3 5 3 5 5 3 4 5 3 3 4 5 5 4 5 4 4 5 3 4 4 5 4 4 4 4 4 3 4 3 5 4 3 4 4 3 3 3 5 5 3 5 4 3 5 3 3 4 5 3 4 4 3 4 3 3 3 5 3 3 4
Комментарии. Последние три задачи - на тему "обход в глубину". Обратите внимание, что в задаче 282 требуется дополнительный модуль, которому для работы нужны дополнительные файлы. Исходный текст этого модуля можно найти в архиве решения.
Задача 281 (Скачать архив)
"Компоненты связности" В неориентированном графе посчитать количество компонент связности. В графе могут быть петли и кратные ребра. Входные данные. Во входном файле INPUT.TXT записаны сначала два числа N и M, задающие соответственно количество вершин и количество ребер (1≤N≤100, 0≤M≤10000), а затем перечисляются ребра. Каждое ребро задается номерами вершин, которые оно соединяет. Выходные данные. В выходной файл OUTPUT.TXT выведите одно число - количество компонент связности. Пример входного файла 3 4 1 1 1 2 1 3 2 3 Пример выходного файла 1 Пример входного файла 5 3 1 1 1 2 2 1 Пример выходного файла 4 Пример входного файла 5 0 Пример выходного файла 5
Задача 282 (Скачать архив)
Задача "Поиск клада" Вы находитесь в лабиринте, ваша задача - найти клад, который также находится где-то в лабиринте. Карта лабиринта задается квадратной матрицей NxM, в каждой клетке находится: 0 - пустая клетка 1 - стенка 2 - клад. Карта лабиринта вам не известна. В каждый момент времени вам могут быть известны лишь координаты клетки, где вы находитесь и информация о том, что находится в соседних клетках. Для написания программы используйте модуль map (т.е., во-первых, скопируйте файл map.tpu в рабочий каталог, во-вторых, в начале своей программы напишите uses map;) Модуль map берет информацию о карте из файла map.txt (ваша программа не должна что-либо считывать из этого файла). Вам доступна процедура WhereAmI, в качестве параметров которой нужно передать 6 переменных типа byte. Например: WhereAmI (x,y,u,r,d,l). При этом эти переменные не могут быть никакого другого типа кроме byte. В результате выполнения этой процедуры в переменные будет записана следующая информация: x,y - ваши текущие координаты u,r,d,l - в каждой из переменных будет одно из чисел 0,1,2 в зависимости от того, что находится сверху, справа, снизу и слева соответственно от той клетки, где вы находитесь. Система координат устроена таким образом, что верхняя левая клетка лабиринта имеет координаты (1,1), верхняя правая - (M,1), нижняя правая - (M,N), нижняя левая - (1,N). Для перемещения вы должны вызвать функцию Move, в качестве параметра которой указать, в какую сторону вы делаете ход. Это можно сделать как с помощью описанных в модуле констант, так и с помощью чисел: Up = 1 - перемещение вверх (y-1) Right = 2 - перемещение вправо (x+1) Down = 3 - перемещение вниз (y+1) Left = 4 - перемещение влево (x-1) Пример: Move(Up) Результатом функции является число 0, если перемещение прошло успешно, или 1 - если там оказалась стенка. Для корректной работы модуля в текущем каталоге должен находиться файл с картой map.txt Первое число в файле - задает, нужно ли показывать на экране процесс поиска клада и с какой скоростью (0 - процесс не отображается, положительное число - отображается, чем больше число - тем медленнее) Далее идут два числа N и M, задающие размеры карты - каждое из них не должно превышать 30. Далее идет N строк по M чисел в каждой, задающие карту. Последние два числа задают начальные координаты искателя. Пример файла map.txt: 1 5 6 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 2 1 5
Задача 283 (Скачать архив)
Двудольный граф Граф называется двудольным, если его вершины можно раскрасить в два цвета так, что нет ребер, соединяющих вершины одинакового цвета (то есть каждое ребро идет из вершины 1-го цвета в вершину 2-го) Дан граф. Требуется проверить, является ли он двудольным, и если да, то раскрасить его вершины. Входные данные Во входном файле задано сначала число N - количество вершин графа (не превышает 100). Далее идет матрица смежности - матрица размером NxN из 0 и 1 (0 обозначает отсутствие ребра, 1 - наличие). Граф неориентированный, без петель. Выходные данные В первую строку выведите одно из сообщений YES или NO (в зависимости от того, является ли граф двудольным или нет). В случае ответа YES во второй строке выведите N чисел - цвета, в которые нужно раскрасить вершины. Пример входного файла 3 0 1 1 1 0 1 1 1 0 Пример выходного файла NO Пример входного файла 3 0 1 1 1 0 0 1 0 0 Пример выходного файла YES 1 2 2