Моим ученикам
Считай несчастным тот день или тот час, в который ты не усвоил ничего нового и не прибавил
ничего к своему образованию.
Козельский Я.П.
Скачать:
Предварительный просмотр:
Методический материал к программе «Основы программирования- 1 ступень»
Задачи для самостоятельного решения | |||
№ | 1 уровень сложности | 2 уровень сложности | 3 уровень сложности |
1 | Кот в Сапогах поймал четыре щуки и еще половину всего улова. Сколько щук поймал Кот в Сапогах? | Вова однажды сказал: «Позавчера мне было 10 лет, а в будущем году исполнится 13». Может ли так быть? | Может ли шахматный конь пройти с поля a1 на поле h8, побывав на каждом поле ровно один раз? |
2 | Когда моему отцу был 31 год, мне было 8 лет. Теперь отец старше меня вдвое. Сколько мне лет теперь? | Докажите, что если сумма 2014 чисел – нечётное число, то произведение этих чисел чётно. | Существует ли число, состоящее из всех 10 различ- ных цифр, записанных в некотором порядке, которое делится на 11? |
3 | Сколько фунтов зерна нужно смолоть, чтобы после оплаты работы — 10% от помола, осталось ровно 100 фунтов муки? Потерь при помоле нет. | К числу 15 припишите справа и слева по одной циф- ре так, чтобы полученное число делилось на 15. Найдите все такие числа и объясните, почему других быть не может. | Докажите, что любое натуральное число, десятичная запись которого состоит из 3n одинаковых цифр, де- лится на 37. |
4 | Используя ровно четыре раза цифру 4, скобки и зна- ки арифметических действий, представьте любое число от 0 до 10. | Если к моим деньгам добавить половину их, да ещё 10р., то у меня станет 100 р. Сколь- ко у меня денег? | Может ли n! (факториал) заканчиваться ровно на 5 нулей? |
5 | Если бы школьник купил 11 тетрадей, то у него осталось бы 5 р. А на 15 тетрадей у него не хватило 7 рублей. Сколько денег было у школьника? | Можно ли отмерить 8 л воды, находясь у реки и имея два ведра: одно вместимостью 15 л, а другое вместимостью 16 л? | Каково наименьшее натуральное n такое, что n! делится на 990? |
6 | Три прямые разбивают плоскость на 7 областей. Можно ли расставить в этих областях числа от 1 до 7 так, чтобы по обе стороны от каждой прямой сумма чисел была одной и той же? | Можно ли разрезать квадрат на пять прямоуголь-ников так, чтобы никакие два из них не имели общей стороны? | Произведение 10 чисел, каждое из которых есть 1 или –1, равно 1. Доказать, что их сумма не равна 0. |
7 | Написать программу определяющую, сумму цифр четырехзначного натурального числа | Написать программу определяющую, стоимость покупки N пирожков по R рублей и К копеек каждый. | Написать программу определяющую, что показывают электронные часы, если с начала суток прошло N минут. |
8 | Написать программу определяющую, модуль натурального числа, введенного с клавиатуры | Написать программу определяющую, определяющую площадь кольца. Радиусы даны R1, R2 | Написать программу определяющую, на какой день улитка доползет до верха столба высотой H метров, если за сутки она проползает К метров |
9 | Даны три числа. Найти среднее из них (то есть число, расположенное между наименьшим и наибольшим). | Написать программу определяющую является ли введенное двузначное число палиндромом | Написать программу определяющую большее из двух чисел, не используя If. |
10 | Написать программу определяющую по номеру дня недели название дня недели | Написать программу определяющую по дате рождения астрологический знак | В многоквартирном доме N этажей, на каждой площадке по К квартир. На каком этаже и в каком подъезде квартира с номером Р? |
11 | Найти большее из четырех чисел | Определить является ли четырехзначное натуральное число палиндромом | На числовой оси расположены три точки: , , . Определить, какая из двух последних точек (В или С) расположена ближе к А , и вывести эту точку и ее расстояние от точки А. |
12 | Даны три числа. Найти сумму двух наибольших из них. | Даны целочисленные координаты трех вершин прямоугольника, стороны которого параллельны координатным осям. Найти координаты его четвертой вершины. | Даны координаты точки, не лежащей на координатных осях и . Определить номер координатной четверти, в которой находится данная точка. |
13 | Даны четыре целых числа, одно из которых отлично от трех других, равных между собой. Определить порядковый номер числа, отличного от остальных. | Даны три целых числа, одно из которых отлично от двух других, равных между собой. Определить порядковый номер числа, отличного от остальных. | Можно ли из трех отрезков А,В,С сложить треугольник? |
14 | Вывести на экран все делители числа N/ | Вычислить сумму элементов ряда 1+1/2+1/3+1/4…+1/N. N – вводится с клавиатуры | Вывести на экран N элемент из ряда Фибоначчи. |
15 | Написать программу вычисления суммы всех двузначных чисел. | Каждая бактерия делится на две в течение одной минуты. В начальный момент имеется две бактерии. Составьте программу, которая рассчитывает количество бактерий за введенное число минут. | Написать программу, которая выводит на экран 10 первых симметричных чисел из диапазона от 1 до 1000. |
16 | Написать программу нахождения максимального числа в последовательности из N чисел | С клавиатуры вводится натуральное число. Найти его наибольшую цифру. | С клавиатуры вводится натуральное число. Является ли оно простым? |
17 | Является ли числовой ряд из N чисел упорядоченным по возрастанию? | Вводятся по очереди координаты N точек. Определить, сколько из них попадает в круг радиусом R с центром в точке (0,0). | Сложим все цифры какого-либо числа. Пол учим новое число, равное сумме всех цифр исходного числа. Продолжим этот процесс до тех пор, пока не получим однозначное число (цифру), называемое цифровым корнем данного числа. Составить программу нахождения цифрового корня натурального числа N. |
18 | С клавиатуры вводится натуральное число. Разложить его на простые сомножители | Исходное данное — натуральное число S, выражающее площадь. Написать программу для нахождения всех таких прямоугольников, площадь которых равна S и стороны выражены натуральными числами | Написать программу, которая находит все четырехзначные числа abсd (а, b, с, d — цифры числа, причем между ними нет совпадений, т. е. числа, например, типа 1221 нас не устраивают, т. е. любые две цифры числа различны), для которых выполняется условие: ab-cd=a+b+c+d. Другими словами, разность чисел, составленных из старших цифр числа и из младших, равна сумме цифр числа. |
19 | На обработку поступает положительное целое число, не превышающее 109. Нужно написать программу, которая выводит на экран количество цифр в десятичной записи этого числа. | Старинная задача. Сколько можно купить быков, коров и телят, если плата за быка 10 рублей, за корову — 5 рублей, за теленка — полтинник (0.5 рубля), если на 100 рублей надо купить 100 голов скота. | С клавиатуры вводится натуральное число. Найти его двоичное значение. |
20 | Таймер - это часы, которые умеют подавать звуковой сигнал по прошествии некоторого периода времени. Напишите программу, которая определяет, когда должен быть подан звуковой сигнал. На вход подается текущее время и интервал в минутах. | В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз. При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути). Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол. | Дана последовательность из N чисел, требуется найти длину наибольшей возрастающей подпоследовательности. |
21 | Написать подпрограмму функцию для вычисления суммы элементов мвссива | Написать подпрограмму процедуру для изображения елки. | Написать подпрограмму процедуру для изображения многоугольника |
22 | Вычислите наименьшее общее кратное двух чисел, используя подпрограмму нахождения наибольшего делителя. | По координатам вершин треугольника вычислите его периметр, используя подпрограмму вычисления длины отрезка между двумя точками. | Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндромиспользуя подпрограмму |
23 | Написать программу определения наибольшего из четырех чисел, используя подпрограмму определения наибольшего из двух чисел. | Натуральное число, в записи которого N цифр, называется числом Армстронга, если сумма его цифр, возведенная в степень N, равна самому числу. Найти все числа Армстронга от 1 до k. | Составить программу для нахождения чисел из интервала [М, N], имеющих наибольшее количество делителей с помощью подпрограммы |
24 | Является ли массив из 10 элементов палиндромом? | Вывести содержимое массива из 15 элементов в пять строк по три элемента в каждой | Является ли массив из 10 элементов упорядоченным? |
25 | Определить количество элементов массива равных максимальноиу | Поменять местами максимальный и минимальный элементы массива | Сдвинуть элементы введенного массива на один вправо (последний займет место первого) |
26 | Пользователь вводит n элементов массива. Требуется определить количество элементов, значение которых больше, чем у соседних элементов массива. | Найти элемент массива имеющий максимальное отклонение от среднего арифметического. | Сдвинуть элементы введенного массива на один влево (первый займет место последнего) |
27 | Дан одномерный массив размерности N , в котором не все элементы равны нулю. Получить новый массив путем исключения нулевых элементов. | Переставить все нулевые элементы в конец массива | Заполнить массив из 12 элементов случайными числами в интервале [-12..12] и выполнить циклический сдвиг ВПРАВО на 4 элемента. |
28 | Имеются ли в массиве одинаковые элементы | Вывести пять самых маленьких элементов массива | Найти количество различных чисел в одномерном массиве |
29 | Имеются два упорядоченных по возрастанию (предыдущий элемент меньше последующего) массива. Требуется получить третий упорядоченный по возрастанию массив, путем слияния первых двух. | Даны два массива с различным количеством элементов. Перераспределить их элементы так, чтобы в первом массиве были наименьшие из двух массивов, а во втором - наибольшие. | Дан массив, например, состоящий только из 0 и 1. Определить самое большое количество подряд идущих единиц и вывести на экран индексы начала и конца этого диапазона. |
30 | Является ли введенная строка палиндроиом? | Какой из элементов массива встречается чаще других? | В строке найдите все серии подряд идущих пробелов и замените каждую на один пробел. |
31 | Определить количество слов в строке. Слова разделены пробелами. | Дана строка. Найти сумму имеющихся в ней цифр | Дана строка. Вставить после каждого символа пробел. |
32 | Строка состоит из слов, разделенных одним или несколькими пробелами. Найдите слово наибольшей длины. | Дано натуральное число. Получить строку, в которой тройки цифр этого числа разделены пробелом, начиная с правого конца. Например, число 1234567 преобразуется в 1 234 567. | Строка состоит из слов, разделенных одним или несколькими пробелами. Поменяйте местами наибольшее по длине слово и наименьшее. |
33 | Кубики. Кубик с ребром N см покрасили и разрезали на кубики с ребром 1 см. При этом появились такие, у которых окрашено разное количество граней. Например, если N = 3, то после разрезания будет 8 кубиков, у которых окрашено три грани, 12 с двумя гранями, 6 с одной, а один кубик будет совсем неокрашенный. Составьте программу, которая бы определяла, сколько кубиков с каждой возможным количеством окрашенных граней. | В плацкартном вагоне 54 места, которые расположены в девяти купе. Места от 1 до 36 основные и они расположены по четыре в купе (1 - 4 в первом, ..., 33 - 36 в девятом), от 37 до 54 - боковые, разбиты по два, но расположение по купе обратное: места 37, 38 находятся в девятом купе, 39 и 40 в восьмом, ..., 53 и 54 в первом. По номеру места определите номер купе. | Стрелки часов движутся с постоянными угловыми скоростями и показывают h часов m минут. Найти число полных минут до того времени, когда стрелки совпадут. |
34 | Дано простое число. Найти следующее за ним простое число. | Дано четное число n > 2. Проверить для него гипотезу Гольдбаха: каждое четное п представляется в виде суммы двух простых чисел. | Подсчитать число лесенок, которое можно построить из N кубиков. |
Предварительный просмотр:
Задача. "Список"
В фирме, выпускающей компьютерные комплектующие, все изделия
получают последовательные номера от 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
Задача. "Метро"
В мегаполисе, испытывающем большие транспортные проблемы, построили
легкое метро. Оно состоит из 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
Задача "Таймер"
Таймер - это часы, которые умеют подавать звуковой сигнал по
прошествии некоторого периода времени. Напишите программу,
которая определяет, когда должен быть подан звуковой сигнал.
Формат входных данных
В первой строке входного файла записано текущее время в формате
ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет
ограничениям: ЧЧ - от 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
Задача "Распаковка строчки"
Будем рассматривать только строчки, состоящие из заглавных
латинских букв. Например, рассмотрим строку 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
Комментарии. Далее изучались темы "процедуры и функции" и "длинная арифметика". Преподавание этих тем велось без использования системы автоматической проверки решений, поэтому в данный архив задачи на эти темы не попали.
Комментарии. Следующая изучаемая тема - динамическое программирование. Традиционно я рассказываю эту тему на примере большого количества задач. Некоторые задачи носят обязательный характер, то есть разбираются и пишутся со всеми, а некоторые адресованы в основном сильным школьникам.
Задача
В прямоугольной таблице 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
Задача "Гвоздики"
На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить
ниточкой. Требуется соединить какие-то пары гвоздиков ниточками так,
чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а
суммарная длина всех ниточек была минимальна.
Входные данные
В первой строке входного файла записано число N - количество
гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел -
координаты всех гвоздиков (неотрицательные целые числа,
не превосходящие 10000).
Выходные данные
В выходной файл нужно вывести единственное число -
минимальную суммарную длину всех ниточек.
Пример входного файла
5
4 10 0 12 2
Пример выходного файла
6
Задача "Подпоследовательности"
Дана последовательность, требуется найти длину наибольшей возрастающей
подпоследовательности.
Входные данные
В первой строке входного файла записано число N - длина последовательности
(1 ≤ N ≤ 1000). Во второй строке записана сама последовательность
(через пробел). Числа последовательности - целые числа,
не превосходящие 10000 по модулю.
Выходные данные
В выходной файл требуется вывести наибольшую длину возрастающей
подпоследовательности.
Пример входного файла
6
3 29 5 5 28 6
Пример выходного файла
3
Задача "Лесенки"
Лесенкой называется набор кубиков, в котором каждый более верхний
слой содержит кубиков меньше, чем предыдущий.
---
| |
---------
| | | | |
-----------
| | | | | |
-----------------
| | | | | | | | |
-----------------
Подсчитать число лесенок, которое можно построить из N кубиков.
Входные данные
Во входном файле записано число N (1≤N≤100).
Выходные данные
В выходной файл вывести искомое число лесенок.
Пример
Пример входного файла
3
Пример выходного файла
2
Задача "Ход конем"
Шахматная ассоциация решила оснастить всех своих сотрудников такими
телефонными номерами, которые бы набирались на кнопочном телефоне
ходом коня. Например, ходом коня набирается телефон 340-4927. При
этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.
Клавиатура телефона выглядит так:
789
456
123
0
Напишите программу, определяющую количество телефонных номеров
длины N, набираемых ходом коня.
Входные данные
Во входном файле записано целое число N (1≤N≤100).
Выходные данные
Выведите в выходной файл искомое количество телефонных номеров.
Пример входного файла
2
Пример выходного файла
16
Задача "Восстановление скобок"
Задан шаблон, состоящий из круглых скобок и знаков вопроса.
Требуется определить, сколькими способами можно заменить знаки вопроса
круглыми скобками так, чтобы получилось правильное скобочное выражение.
Входные данные
Первая строка входного файла содержит заданный шаблон длиной
не более 80 символов.
Выходные данные
Выведите в выходной файл искомое количество способов. Исходные данные
будут таковы, что это количество не превзойдет 2*10^9.
Пример входного файла
????(?
Пример выходного файла
2
Задача "Шаблон и слово"
Требуется определить подходит ли заданное слово под заданный шаблон.
Шаблон задается большими латинскими буквами, знаками "?" -
любой символ, "*" - любая последовательность символов (даже пустая).
Входные данные: в первых двух строках записаны шаблон и слово:
в одной строки записан шаблон - последовательность больших
латинских букв, "?" и "*", в другой - слово, состоящее только
из больших латинских букв (строки короче 100 символов).
Выходные данные: вывести YES, если слово подходит или NO, если нет.
Примеры
input.txt
ABBCDA
A*CDA
output.txt
YES
input.txt
AADAAVA
A*DA*AA*
output.txt
NO
Задача 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
Задача
(Дополнительная задача)
Шаблоны с ? и *
Шаблоном называется строка, состоящая из английских букв
(a,...,z, A,...,Z) и символов ? и *. Каждый из символов ? разрешается
заменить на одну произвольную букву, а каждый из символов * -
на произвольную (возможно пустую) последовательность букв.
Про любую строку из букв, которую можно получить из шаблона такими
заменами, будем говорить, что она удовлетворяет этому шаблону.
Имеются два шаблона. Требуется найти строку минимальной длины,
которая удовлетворяет обоим шаблона, либо выдать сообщение, что такой
строки не существует.
Входные данные
Заданные шаблоны записаны в первых двух строках входного файла.
Длина каждого шаблона не превосходит 80 символов.
Выходные данные
В выходной файл следует вывести строку минимальной длины, удовлетворяющую
обоим шаблонам, либо сообщение <-1>
Пример входного файла
A*
*B
Пример выходного файла
AB
Задача
1.3. Уравнение с пропущенными цифрами
Задано уравнение вида A + B = C, где A, B и C - неотрицательные целые
числа, в десятичной записи которых некоторые цифры заменены знаками
вопроса (?). Примером такого уравнения является ?2+34=4?. Требуется
так подставить вместо знаков вопроса цифры, чтобы это равенство стало
верным, либо определить, что это невозможно. Найти только одно из
возможных решений.
Входные данные
Заданное уравнение содержится в первой строке входного файла.
Длина уравнения не превышает 80 символов. Входной файл не содержит пробелов.
Выходные данные
В выходной файл требуется вывести верное равенство, полученное из
исходного уравнения заменой знаков вопроса цифрами, либо сообщение
"No solution".
Пример входного файла
??2?4+9?=355
Пример выходного файла
00264+91=355
Задача
(Дополнительная задача)
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ый текст наименьшей длины.
Задача
(Дополнительная задача)
1.7. Пустоты в кубе
Жюри составило отчет об учебно-тренировочных сборах по информатике
и собирается распечатать его на стандартном листе бумаги. Весь
отчет набран одним моноширинным шрифтом, т.е. все символы (включая
пробелы) имеют одинаковую ширину. Длина строки при печати этим
шрифтом на листе бумаги равна S.
Назовем пустотой последовательность пробелов между соседними словами
в строке, а также от начала строки до первого слова в ней и от
последнего слова в строке до конца строки. Проблема, стоящая перед жюри,
состоит в том, что научный руководитель сборов Владимир Михайлович
Кирюхин отказывается читать текст, если сумма кубов длин пустот по всем
строкам не минимальна. Помогите жюри расположить отчет на листе бумаги так,
чтобы В.М. Кирюхин согласился его прочесть и утвердить результаты сборов.
Для достижения требуемого расположения текста на бумаге разрешается
заменять произвольную пробельную последовательность (т.е. непустую
последовательность подряд идущих пробелов и/или символов перевода
строки) любой другой пробельной последовательностью.
Входные данные
Первая строка входного файла содержит целое число S (1≤S≤80).
В последующих строках записан отчет, содержащий не более 500 слов.
Длина каждой строки отчета не превосходит 250 символов, а длина каждого
слова не превос-ходит S.
Выходные данные
Вывести в первую строку выходного файла минимально возможную сумму
кубов пустот по всем строкам. В последующие строки следует вывести
искомое расположение текста на листе бумаги.
Пример входного файла
30
Победители летних учебно-тренировочных сборов по информатике 1997 г.:
Владимир Мартьянов,
Анатолий Пономарев,
Николай Дуров,
Андрей Лопатин.
Пример выходного файла
325
Победители летних
учебно-тренировочных сборов по
информатике 1997 г.: Владимир
Мартьянов, Анатолий Пономарев,
Николай Дуров, Андрей Лопатин.
Задача "Шифровка"
На контрольной по алгебре логики Филипп К. и Алла П. по ходу решения
задачи хотят обмениваться наборами из 0 и 1, которые у них получаются.
Но злобный учитель информатики очень строго следит за тем, чтобы в ходе
контрольной ученики решали задачи самостоятельно. Правда, школьникам
удалось воззвать к его человеческим чувствам, и он разрешил им обмениваться
записками, содержание которых никак не связано с алгеброй логики.
К счастью, Филипп и Алла успели договориться, что они будут шифровать
наборы из 0 и 1 предложениями русского языка. Слово четной длины
будет обозначать 0, нечетной длины - 1, знаки препинания при расшифровке
не учитываются.
Таким образом, расшифровать такую шифровку очень просто, а вот чтобы
зашифровать какую-либо последовательность, требуется незаурядный
литературный талант. Помогите им! Напишите программу, которая
по введенной последовательности из 0 и 1, строит текст,
соответствующий правилам русского языка, имеющий с точки зрения языка
хоть какой-то (минимальный!) смысл, и который кодирует заданную
последовательность.
Входные данные
В файле INPUT.TXT записано сначала число N (1≤N≤100) - длина
последовательности, а затем последовательность из N чисел,
каждое из которых является 0 или 1.
Выходные данные
В файл OUTPUT.TXT выведите текст на русском языке, который кодирует
заданную последовательность. Обратите внимание! В тексте не должно
быть одинаковых предложений (предложения считаются одинаковыми,
если они совпадают с точностью до знаков препинания, если
же они различаются хотя бы порядком следования слов, они уже
считаются различными). А в одном предложении ни одно из слов
не должно повторяться.
Разминочная задача
Во входном файле записано сначала число N (1≤N≤100), а затем
N пар чисел. Первое число каждой пары - натуральное, не превышающее 30000.
Второе число каждой пары - 0 или 1.
Требуется найти и вывести в выходной файл номер пары, в которой второе число
равно 1, а из всех таких пар ту, в которой первое число максимально
(если таких пар несколько, выведите любую из них).
Если пар, у которых второе число равно 1 нет, выведите в выходной файл -1.
Пример входного файла
4
25 1
70 1
100 0
3 1
Пример выходного файла
2
Задача "Дейкстра"
Дан ориентированный взвешенный граф. Для него вам необходимо найти
кратчайшее расстояние от одной заданной вершины до другой.
Входные данные:
В первой строке входного файла три числа: 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) Ходим из этой вершины, т.е.:
-Проверяем, если расстояние до данной вершины + ребро из нее в какую-то другую
вершину меньше, чем расстояние до той вершины, уменьшаем расстояние до
той вершины
-Помечаем, что мы походили из этой вершины.
После окончания мы получим массив кратчайших путей.
Задача "Заправки"
В стране 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
Задача "Заправки-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
"Автобусы".
Между некоторыми деревнями Пермской области ходят автобусы.
Поскольку пассажиропотоки здесь не очень большие, то автобусы
ходят всего несколько раз в день (например, в Ляды из Перми
автобус приходит лишь 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
Задача 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
Задача "Пиво в розлив"
Имеются три пробирки, вместимостью 100 миллилитров каждая.
Первые две пробирки имеют риски, одинаковые на обеих пробирках.
Возле каждой риски надписано целое число миллилитров, которое
вмещается в часть пробирки от дна до этой риски (см. рисунок).
Изначально первая пробирка содержит 100 миллилитров пива,
а остальные две пусты. Требуется написать программу,
которая выясняет, можно ли отделить в третьей пробирке
один миллилитр пива, и если да, то находит минимально
необходимое для этого число переливаний. Пиво можно переливать
из одной пробирки в другую до тех пор, пока либо первая из них
не станет пустой, либо одна из пробирок не окажется заполненной
до какой-либо риски.
Входные данные
В первой строке входного файла содержится число рисок
N (1≤N≤20), имеющихся на каждой из первых двух
пробирок. Затем в порядке возрастания следуют N целых чисел
V1,..., VN (1≤Vi≤100), приписанных рискам. Последняя риска
считается сделанной на верхнем крае пробирок (VN = 100).
Выходные данные
В первой строке выходного файла должна содержаться
строка "YES", если в третьей пробирке возможно отделить
один миллилитр пива, и "NO" - в противном случае. В случае
ответа "YES" во вторую строку необходимо вывести искомое
количество переливаний.
Пример входного файла
4
13 37 71 100
Пример выходного файла
YES
8
Задача "Флойд-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
Задача "Флойд-Макс"
Дан ориентированный взвешенный граф. В нём вам необходимо найти пару
вершин, кратчайшее расстояние от одной из которых до другой
максимально среди всех пар вершин.
Входные данные:
В первой строке входного файла единственное число: 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
Задача "Флойд-существование"
Дан ориентированный взвешенный граф.
По его матрице смежности нужно для каждой пары
вершин определить, существует ли кратчайший путь
между ними или нет.
Комментарий:
Кратчайший путь может не существовать по двум причинам:
-Нет ни одного пути
-Есть пути сколь угодно маленького веса
Входные данные:
В первой строке входного файла записано
единственное число: 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
Кратчайший путь
Задан ориентированный граф без кратных ребер. Найти кратчайший
путь между двумя вершинами. Все веса ребер положительны. Путь
всегда существует.
Ограничения
Максимальное количество вершин не больше 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
Вам дана табличка, состоящая из 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
Задача
На стандартной шахматной доске(8х8) живут красный и зеленый шахматные кони.
Они беззаботно скачут по ней пощипывая шахматную травку. Сегодня у зеленого
коня День Рождения. Кони решили отпраздновать это событие вместе. Для этого
им нужно оказаться на одной клетке. Заметим, что красный и зеленый шахматные
кони сильно отличаются от черного с белым: они ходят не по очереди, а
одновременно, и если они оказываются на одной клетке никто никого не съедает.
Сколько ходов им потребуется, чтобы оказаться на одной клетке?
Входные данные
Во входном файле содержатся координаты коней, записанные по стандартным
шахматным правилам (т.е. двумя символами - маленькая латинская буква (от
a до h) и цифра (от 1 до 8) задающие столбец и строку соответственно)
Выходные данные
Выходной файл должен содержать наименьшее необходимое количество ходов, либо
-1, если кони не могут встретиться.
Пример
a1 a3
Ответ
1
Задача "Дерево?"
Дана матрица смежности неориентированного графа без петель
и кратных ребер. Определить, является ли этот граф деревом.
Входные данные
Во входном файле записано сначала число N - количество вершин
графа (от 1 до 100). Далее записана матрица смежности размером
N*N, в которой 1 обозначает наличие ребра, а 0 - отсутствие.
Матрица симметрична относительно главной диагонали.
Выходные данные
В выходной файл выведите сообщение YES, если граф является деревом
и NO в противном случае
Пример входного файла
3
0 1 0
1 0 1
0 1 0
Пример выходного файла
YES
Задача "Получи дерево"
Дан связный неориентированный граф без петель и кратных ребер.
Разрешается удалять из него ребра. Требуется получить дерево.
Входные данные
Во входном файле заданы два числа - N (от 1 до 100) и M - количество
вершин и ребер графа соответственно. Далее идет M пар чисел,
задающих ребра. Гарантируется, что граф связный.
Выходные данные
В выходной файл выведите N-1 пару чисел - ребра, которые
войдут в дерево. Ребра можно выводить в любом порядке.
Пример входного файла
4 4
1 2
2 3
3 4
4 1
Пример выходного файла
1 2
2 3
4 3
Каркас-разминка 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
Каркас - разминка - 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
Задача "Минимальный каркас"
От вас требуется определить вес минимального остовного дерева
для неориентированного взвешенного графа.
Входные данные:
В первой строке входного файла числа 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) Вводится число 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 на подмножества
(разбиения, отличающиеся порядком множеств считаются одинаковыми).
Задача "Ребус-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
Задача "Ребус-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
Задача "Ребус-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
Задача коммивояжера
Ограничение времени работы на одном тесте - 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
Задача
Та же задача, что и предыдущая, но 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
Задача
Задача "Универсальный ребусорешатель"
Время работы вашей программы не должно превышать 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
Ханойская башня
Есть три стержня. На первом из них расположено N колец (1-е, верхнее, самое
маленькое, N-ое, нижнее, самое большое). За один ход разрешается
с любого стержня снять верхнее кольцо и надеть его на любой другой
стержень. При этом запрещается класть большее кольцо на меньшее.
Требуется, чтобы все кольца оказались на стержне номер 2.
Входные данные
Во входном файле записано одно число N (1≤N≤10)
Выходные данные
В выходной файл выведите последовательность команд.
Каждая команда задается двумя числами - с какого стержня снимаем кольцо,
и на какой надеваем
Пример входного файла
2
Пример выходного файла
1 3
1 2
3 2
"Двоечные последовательности"
Вводится число 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
"Троечные последовательности"
Вводится число 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
"Компоненты связности"
В неориентированном графе посчитать количество компонент связности.
В графе могут быть петли и кратные ребра.
Входные данные.
Во входном файле 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
Задача "Поиск клада"
Вы находитесь в лабиринте, ваша задача - найти клад, который
также находится где-то в лабиринте.
Карта лабиринта задается квадратной матрицей 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
Задача
Двудольный граф
Граф называется двудольным, если его вершины можно раскрасить в два цвета
так, что нет ребер, соединяющих вершины одинакового цвета (то есть
каждое ребро идет из вершины 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