|
||||||||
|
Несколько вводных слов
Представленные здесь задачи - это полугодовой курс (по 2 часа в неделю) по изучению программирования на паскале фактически с "нуля" в 8 математическом (достаточно сильном) классе. Мне бы хотелось выразить признательность школьникам 8 класса "В" Московской гимназии 1543 (2003-2004 учебный год) за нашу с ними совместную работу по "обкатке" этих задач :-) .
Сюда не вошли 3 первых занятия, где школьники не пользовались тестирующей системой. Уже на 4-м занятии с ними была пройдена тема "файлы" (быть может, это несколько рано, однако это диктовалось необходимостью использования системы автоматической проверки - достаточно большие группы приводили к тому, что я не успевал подходить ко всем школьникам). На первых 3 занятиях были пройдены ввод и вывод данных (read, write), переменные (целые, вещественные), условный оператор, циклы.
Тестирующая система, использовавшаяся на занятиях, была устроена так, что в случае ошибки (непрохождения какого-либо теста) этот тест оказывался в файле input.txt в рабочем каталоге школьника. На первых порах изучения программирования, на мой взгляд, это достаточно осмысленно, однако постепенно от этого нужно уходить, чтобы школьники сами учились анализировать условие и придумывать тесты.
Все представленные задачи представлены в формате, принятом на сайте www.olympiads.ru. Внутри архива содержатся условие, тесты, проверяющие программы. Там, где используются дополнительные программы, они также есть внутри архивов. Обратите внимание, в html-версии присутствуют некоторые комментарии для преподавателей, которых нет внутри архивов! Так сложилось, что задачи номер 114 в курсе нет - это не ошибка при выкладывании задач.
Вы можете скачать Все задачи в одном архиве (около 2,8 Мб).
Несколько слов о курсе
Основной целью изучения программирования на этом уровне, на мой взгляд, является научить школьника, понимая, как решается задача, излагать свои мысли на языке программирования (писать программу). Это учит школьника мыслить более точно, четко, разбивать задачу на этапы.
Все это делается (в основном) на очень простых и вроде бы понятных задачах. Понятных в том смысле, что если потребуется какую-то из этих задач решить устно (не на компьютере, а просто с конкретными входными данными на бумажке проделать то, что требуется в задаче), то у восьмиклассника это не должно вызвать затруднений. Это дает возможность практически на пальцах обсуждать алгоритмы решения задач и совершенные ошибки.
Практически с начала обучения программированию я требую от школьников умения пользоваться отладчиком. В этом смысле тестирующая система, которая оставляет на компьютере входной файл, на котором программа не работает, очень это стимулирует - анализировать, как работает программа и сравнивать с тем, как она должна работать. Умение самостоятельно искать неправильный тест - это, на мой взгляд, следующий этап обучения.
По набору тем: сначала идут задачи на циклы, затем - массивы, сортировка, двухмерные массивы. Дальше мы подбираемся к теме графы, однако успеваем лишь затронуть начало этой темы. Это создает некоторый задел на будущее. Заканчивается курс темой процедуры и написанием большой игровой программы. При этом при прохождении всех вышеперчисленных тем детям показываются (подкидываются) разные идейки. Пока это не есть цель изучения, но важно, чтобы когда мы дойдем до соответствующих тем, для них эти идеи были не совсем новыми, а смутно знакомыми. А какие-то из идей так и останутся лишь идеями. Кроме того, периодическое показывание красивых идей стимулирует школьников к поиску нестандартных подходов, обходных путей самостоятельно.
Во всех задачах входные данные вводятся из файла INPUT.TXT, выходные данные выводятся в файл OUTPUT.TXT.
Комментарии. Целью первых занятий является знакомство с темой "файлы" и привыкание к работе с ними, а также привыкание к работе с тестирующей системой.
Задача 101 (Скачать архив)
Вводится два числа. В выходной файл записать их сумму. Пример входного файла 2 3 Пример выходного файла 5
Задача 102 (Скачать архив)
Даны координаты двух полей шахматной доски (координаты клетки - это 2 числа от 1 до 8: номер столбца и номер строки) Одно ли цвета эти клетки на шахматной доске? Вывести в выходной файл сообщение YES, если они одного цвета, и NO иначе Пример входного файла: 1 1 2 2 Пример выходного файла YES Пример входного файла: 1 1 1 4 Пример выходного файла NO
Задача 103 (Скачать архив)
Дана последовательность чисел. Найти в ней наименьшее число. Входные данные. Задано сначала число N (количество чисел в последовательности), а затем N чисел. Выходные данные. Выведите наименьшее число. Пример входного файла 7 4 2 5 -1 4 6 2 Пример выходного файла -1
Комментарии. Заметьте, что эту (и некоторые следующие задачи про последовательности) предполагается решать без использования массива (считается, что школьники к этому моменту их еще не знают). При этом если находятся школьники, знакомые с массивами, которые при решении задачи их используют, ничего плохого в этом нет.
Комментарии. Задачи 104-106 - задачи на использование цикла WHILE.
Задача 104 (Скачать архив)
Является ли число степенью двойки? Вводится число. Напечатать YES, если оно является степенью двойки, NO - иначе Пример входного файла 8 Пример выходного файла YES Пример входного файла 22 Пример выходного файла NO
Задача 105 (Скачать архив)
Посчитать сумму цифр числа Вводится число. Вывести сумму его цифр Пример входного файла 157 Пример выходного файла 13
Задача 106 (Скачать архив)
Вводится последовательность чисел до тех, пока не будет введено два равных числа подряд. Посчитать количество чисел в последовательности. Выходные данные Выведите количество чисел (включая два последних) Пример входа 3 5 24 4 3 5 3 5 3 5 5 Пример вывода 11
Комментарии. Задачи 107-109 предполагают использование вложенных циклов.
Задача 107 (Скачать архив)
Вводятся два числа N и K. Выведите количество чисел из диапазона от 1 до N включительно таких, что их сумма цифр делится на K. Пример ввода 100 3 Пример вывода 33 Пример ввода 22 4 Пример вывода 5
Задача 108 (Скачать архив)
Напечатайте в файл в возрастающем порядке все 3-х значные числа, у которых все цифры различны
Задача 109 (Скачать архив)
Дано число N. Найти число из диапазона от 1 до N с максимальной суммой делителей (включая непростые делители, 1 и само число). Если таких чисел несколько, выведите любое из них. Пример ввода 5 Пример вывода 4
Задача 110 (Скачать архив)
Дана последовательность чисел. Выяснить, сколько раз в ней встречается максимальное число Входные данные. Вводится сначала число N - количество членов последовательности, а затем N чисел - члены последовательности Выходные данные Выведите одно число - сколько раз в последовательности встречается максимальное число. Пример входного файла 7 1 4 2 5 2 5 3 Пример выходного файла 2
Комментарии. Не очень простая задача, если учесть, что тему массивы мы к этому моменту еще не проходили. Тем не менее, массив, в общем-то, и не нужен для ее решения.
Комментарии. Задача 111 готовит школьников к появлению массивов. Здесь уже встречаются такие понятия, как сам элемент и его номер. Здесь же (впрочем, это было и в некоторых более ранних задачах) школьникам предлагается способ ввода, когда вводится сначала количество чисел, а потом сами элементы.
Задача 111 (Скачать архив)
Вводится последовательность чисел. Посчитать в ней количество четных чисел, стоящих на четных местах. Входные данные Вводится сначала число N, а затем N чисел - члены последовательности. Выходные данные. Выведите количество четных чисел, стоящих на четных местах в последовательности. Пример входного файла 5 1 2 4 5 6 Пример выходного файла: 1 Пояснение: единственное четное число, стоящее на четном месте в последовательности - это число 2. Числа 4 и 6 не подходят, так как стоят, соответственно, на 3 и 5-м местах.
Задача 112 (Скачать архив)
Задача "Короткий НОД" Даны два числа. Найти их наибольший общий делитель. Входные данные Вводятся два натуральных числа, не превышающих 30000. Выходные данные Выведите НОД введенных чисел Пример входного файла 9 12 Пример выходного файла 6
Задача 113 (Скачать архив)
Задача "Длинный НОД" Даны два числа. Найти их наибольший общий делитель. Входные данные Вводятся два натуральных числа, не превышающих 10^9 (запись 10^9 обозначает "10 в 9-й степени", то есть 1000000000). Выходные данные Выведите НОД введенных чисел Пример входного файла 9 12 Пример выходного файла 6
Комментарии. Задача 113 отличается от 112 тем, что 112 можно решить полным перебором делителей, а в 113 требуется реализация алгоритма Евклида.
Комментарии. Перед этой задачей школьникам рассказывается, что такое массивы, как с ними работать, как считывать/записывать элементы массива. Дальше идут задачи на массивы.
Задача 115 (Скачать архив)
Вводится сначала число N, а затем N чисел. Выведите эти N чисел в обратном порядке. Входные данные Вводится число N (0<N<100), а затем N чисел из диапазона Integer. Выходные данные Выведите N чисел в обратном порядке Пример входного файла 7 2 4 1 3 5 3 1 Пример выходного файла 1 3 5 3 1 4 2
Задача 116 (Скачать архив)
Вводится сначала число N, а затем N чисел. Выведите эти N чисел в следующем порядке: сначала выводятся все нечетные числа в том порядке, в каком они встречались во входном файле, а затем - все четные. Входные данные Вводится число N (0<N<100), а затем N чисел из диапазона Integer. Пример входного файла 7 2 4 1 3 5 3 1 Пример выходного файла 1 3 5 3 1 2 4
Задача 117 (Скачать архив)
Вводится сначала число N, а затем N чисел. Выведите эти N чисел в следующем порядке: сначала выводятся числа, стоящие на нечетных местах, а затем - стоящие на четных местах. Входные данные Вводится число N (0<N<100), а затем N чисел из диапазона Integer. Пример входного файла 7 2 4 1 3 5 3 1 Пример выходного файла 2 1 5 1 4 3 3
Задача 118 (Скачать архив)
(Может быть, для вас будет проще сначала решить задачу 119, а потом уже - эту) Вводится число N, а затем - N чисел. Определить, сколько среди них пар одинаковых чисел. 2≤N≤100 Пример входного файла: 5 1 3 2 2 3 Пример выходного файла: 2 Пример входного файла: 4 1 1 1 1 Пример выходного файла: 6 Пояснение: Во 2-м примере пару одинаковых чисел образовывают любые два числа последовательности, поэтому ответом будет число пар, которое вообще может быть (это пары чисел, стоящих на местах: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4))
Задача 119 (Скачать архив)
Вводится число N, а затем - N чисел. Определить, сколько среди них пар одинаковых чисел, стоящих рядом. 2≤N≤100 Пример входного файла: 5 1 3 2 2 3 Пример выходного файла: 1 Пример входного файла: 4 1 1 1 1 Пример выходного файла: 3
Задача 120 (Скачать архив)
Вводится число N, а затем N чисел - элементов массива (1≤N≤100), элементы массива - числа из диапазона Integer. Выведите два числа - номера мест в массиве, на которых стоят одинаковые элементы, или два числа 0 (то есть 0 0), если все элементы различны. Если есть несколько пар чисел, являющихся ответом, выведите любую из них. Пример входного файла 5 1 2 1 3 4 Пример выходного файла 1 3 Пример входного файла 4 1 2 3 4 Пример выходного файла 0 0
Задача 121 (Скачать архив)
Даны N отрезков прямой. Найти длину общей части всех этих отрезков. Входные данные. Вводится сначала число N (1≤N≤100). Далее воодится N пар чисел, задающих координаты левого и правого концов каждого отрезка. Все координаты - числа из дапазона от 0 до 30000. Левый конец отрезка всегда имеет координату строго меньшую, чем правый. Выходные данные. Выведите длину общей части этих отрезов. Если у всех этих отрезков общей части нет, выведите 0. Пример входного файла 3 1 10 3 15 2 6 Пример выходного файла 3 Пояснение: общая часть этих отрезков - отрезок от 3 до 6. Пример входного файла 3 1 10 2 20 11 20 Пример выходного файла: 0 Пояснение: у этих отрезков нет общей части
Задача 122 (Скачать архив)
Вводятся числа от 1 до 9 до тех пор, пока не будет введен 0. Всего будет введено не больше 100 чисел. Посчитать количество единиц в этой последовательности, количество двоек, количество троек и так далее (в выходном файле всегда должно быть 9 чисел). Пример входного файла 1 1 4 1 5 8 6 3 5 1 0 Пример выходного файла: 4 0 1 1 2 1 0 1 0
Задача 123 (Скачать архив)
(Та же задача, что и 122, только может быть введено до 100000 чисел) Вводятся числа от 1 до 9 до тех пор, пока не будет введен 0. Всего будет введено не более 100000 чисел Посчитать количество единиц в этой последовательности, количество двоек, количество троек и так далее (в выходном файле всегда должно быть 9 чисел). Пример входного файла 1 1 4 1 5 8 6 3 5 1 0 Пример выходного файла: 4 0 1 1 2 1 0 1 0
Комментарии. Эта задача очень непростая для школьников (в идейном плане). Если раньше массив использовался для хранения последовательности, то здесь нужно использовать массив для подсчета ответа. Многие школьники не замечают эту идею, и, сохранив вводимые числа в памяти, затем 9 раз пробегают по массиву, считая сначала 1, потом 2 и т.д. В этом случае 122 задача проходит, а вот со 123 возникают проблемы. Здесь обязательно нужно остановиться и обсудить эту идею - в некотором смысле, это некоторый подход к идее цифровой сортировки.
Задача 124 (Скачать архив)
В некотором государстве действует N фирм, конкурирующих между собой. У каждой фирмы есть некоторая прибыль в год, равная V[i] американских рублей. У царя есть любимые фирмы, а есть нелюбимые. Соответственно, налог для всех фирм разный и назначается царем в индивидуальном порядке. Налог на i-ую фирму равен p[i] процентов. Собиратели статистики решили посчитать, с какой фирмы в государственную казну идет наибольший доход (в казну идут все налоги). К сожалению, они не учили в детстве ни математику, ни информатику (так что учитесь, дети!), и их задача резко осложняется. Помогите им в этой нелегкой задаче. Входной файл input.txt ----------------------- сначала записано число N - число фирм (0<N≤100). Далее идет N целых неотрицательных чисел, не превышающих 154 - доходы фирм, а затем еще N целых чисел от 0 до 100 - налоги фирм в процентах. Выходной файл output.txt ------------------------ В выходной файл выведите одно число - номер фирмы, от которой государство получает наибольший налог. Если таких фирм несколько, выведите любую из них. Пример входного файла: 3 100 1 50 0 100 3 Пример выходного файла: 3
Комментарии. Здесь, обычно, школьники вспоминают вещественные числа, о которых шла речь на 1-м занятии, и которые больше нигде не встречались. Однако как раз на этой задаче неплохо поговорить с ними о том, что операции с вещественными числами выполняются значительно медленее, чем с целыми и о том, можно ли в этой задаче обойтись только целыми числами (можно, если не делить на 100).
Задача 125 (Скачать архив)
Во входном файле записана последовательность натуральных чисел, не превышающих 1000. Последовательность заканчивается числом 0. Количество чисел в последовательности не превышает 100. Выведите в выходной файл количество чисел в последовательности (не считая 0), а потом сами числа. Пример входного файла 1 3 5 0 Пример выходного файла 3 1 3 5
Задача 126 (Скачать архив)
Во входном файле записана последовательность чисел в странном формате: у каждого числа сначала записано количество цифр в этом числе, а потом через пробел - сами цифры. Последовательность заканчивается числом 0. В выходной файл нужно вывести сначала количество чисел в последовательности, а потом - сами числа. Количество чисел в последовательности не превышает 1000. В числах - не более 4-х знаков. Примеры: Пример 1 input.txt output.txt 2 2 7 3 3 5 1 0 2 27 351 Пример 2 input.txt output.txt 1 1 0 1 1 Пример 3 input.txt output.txt 4 1 2 3 4 2 4 3 0 2 1234 43
Комментарии. Задача достаточно сложная и требует аккуратного программирования.
Задача 127 (Скачать архив)
Дано N целых чисел. Требуется выбрать из них три таких числа, произведение которых максимально. Формат входных данных Во входном файле записано сначала число N - количество чисел в последовательности (3≤N≤100). Далее записана сама последовательность: N целых чисел, по модулю не превышающих 1000. Формат выходных данных В выходной файл выведите три искомых числа в любом порядке. Если существует несколько различных троек чисел, дающих максимальное произведение, то выведите любую из них. Пример входного файла 9 3 5 1 7 9 0 9 -3 10 Пример выходного файла 9 10 9 Пример входного файла 3 -5 -300 -12 Пример выходного файла -5 -300 -12
Комментарии. Задача похожа на задачу с Московской олимпиады 2004 года (с уменьшенными ограничениями). Возможно как решение, перебирающее все тройки чисел (для школьников на этом уровне это тоже отнюдь не простая задача), так и решение, разбирающее случаи (см. комментарии к этой задаче в брошюре с разбором задач Московской олимпиады).
Комментарии. Следующие две задачи - вставка элемента в массив и удаление элемента сначала разбираются на примере самих школьников и стульев, на которых они сидят. Идея о том, что для того, чтобы элемент в массив вставить, нужно сначала сдвинуть всех, кто сидел на этом и последующих местах, достаточно очевидна. Гораздо менее очевидно, почему в случае добавления сдвиг нужно начинать с конца массива, а в случае удаления - с начала.
Задача 128 (Скачать архив)
Дан массив. Требуется удалить из него элемент, стоящий на месте номер B, сдвинув все последующие элементы влево. Входные данные Во входном файле записано сначала число N - количество элементов массива (2≤N≤100), затем N чисел из диапазона Integer - элементы массива, а затем число B (1≤B≤N). Выходные данные В выходной файл выведите N-1 число - элементы массива с удаленным B-м элементом. Примечание Вы должны удалить элемент непосредственно из массива, а не сделать вид при выводе данных, что у вас такого элемента нет. Также вы не должны для этого заводить в программе дополнительный массив. То есть ввод данных осуществляется следующим фрагментом: read(fi,n); for i:=1 to n do read(fi,a[i]); read(fi,b); А вывод - следующим: for i:=1 to n-1 do write(fo,a[i],' '); Необходимые фрагменты вы можете найти в файле P<номер задачи>.PAS (P128.PAS) Пример входного файла 5 1 3 5 6 7 2 Пример выходного файла 1 5 6 7
Текст программы P128.PAS
const nmax=100;
var a:array[1..nmax] of integer;
n:integer;
i:integer;
b:integer;
fi,fo:text;
begin
assign(fi,'input.txt');
reset(fi);
assign(fo,'output.txt');
rewrite(fo);
read(fi,n);
for i:=1 to n do read(fi,a[i]);
read(fi,b);
{Вы должны писать здесь}
for i:=1 to n-1 do write(fo,a[i],' ');
close(fi);
close(fo);
end.
Задача 129 (Скачать архив)
Дан массив. Требуется вставить в него на место номер B элемент, равный C, сдвинув все последующие элементы (включая элемент, стоящий на B-ом месте) вправо. Входные данные Во входном файле записано сначала число N - количество элементов массива (2≤N≤100), затем N чисел из диапазона Integer - элементы массива, затем число B (1≤B≤N) и число C (из диапазона Integer). Выходные данные В выходной файл выведите N+1 число - элементы массива с вставленным элементом. Примечание Вы должны вставить элемент непосредственно в массив, а не сделать вид при выводе данных, что у вас появился такой элемент. Также вы не должны для этого заводить в программе дополнительный массив. То есть ввод данных осуществляется следующим фрагментом: read(fi,n); for i:=1 to n do read(fi,a[i]); read(fi,b,c); А вывод - следующим: for i:=1 to n+1 do write(fo,a[i],' '); Необходимые фрагменты вы можете найти в файле P<номер задачи>.PAS (P129.PAS) Пример входного файла 5 1 3 5 6 7 2 10 Пример выходного файла 1 10 3 5 6 7
Текст программы P129.PAS
const nmax=100;
var a:array[1..nmax] of integer;
n:integer;
i:integer;
b,c:integer;
fi,fo:text;
begin
assign(fi,'input.txt');
reset(fi);
assign(fo,'output.txt');
rewrite(fo);
read(fi,n);
for i:=1 to n do read(fi,a[i]);
read(fi,b,c);
{Вы должны писать здесь}
for i:=1 to n+1 do write(fo,a[i],' ');
close(fi);
close(fo);
end.
Задача 130 (Скачать архив)
В начальный момент в i-ом элементе массива записано число i (всего N элементов). Каждую секунду числа сдвигаются в следующую ячейку (из i-ой в i+1-ую), а из N-ой - в первую. Напечатать состояние массива через T секунд. Во вхоном файле записаны два числа - N (1≤N≤100) и T (0≤T≤30000). В выходной файл выведите N чисел - состояние массива через T секунд. Пример входного файла 5 3 Пример выходного файла 3 4 5 1 2
Комментарии. Задача допускает несколько решений. Можно просто просчитать, кто когда где будет, можно просто промоделинровать процесс (это решение является более предпочтительным). Обязательно стоит обсудить, что перед моделированием процесса, стоит взять T mod N.
Задача 131 (Скачать архив)
Задача Иосифа Флавия Существует легенда, что Иосиф Флавий - известный историк первого века - выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным - он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю. В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от 1 до N, и будем исключать каждого k-ого до тех пор, пока не уцелеет только один человек. (Например, если N=10, k=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.) Задача: определить номер уцелевшего. Входные данные: числа N и k вводятся из файла INPUT.TXT. Ограничения: 1≤N≤500, 1≤k≤100. Выходные данные: Программа должна выдавать номер уцелевшего человека в файл OUTPUT.TXT. Пример входного файла: 10 3 Пример выходного файла: 4
Комментарии. Задача Иосифа Флавия очень богата на идеи. Предполагается, что школьники будут решать ее, моделируя процесс. При этом есть два подхода: завести массив, где помечать, жив человек или нет. Бегать по кругу и считать живых. Второй подход: завести массив с номерами живых людей, и при убивании человека удалять из него человека. При каждом из подходов, задача является довольно сложной и требует аккуратной реализации.
Задача 132 (Скачать архив)
Задача "Троллейбусы" Троллейбусы одного маршрута проходят через остановку каждые k (1≤k≤500) минут. Известны времена прихода пассажиров на эту остановку. Если пассажир приходит на остановку в момент прихода троллейбуса, то он успевает уехать на нем. Напишите программу, которая бы определяла, во сколько должен пройти первый троллейбус (это время от 0 до k-1), чтобы: 1) Суммарное время ожидания троллейбуса для всех пассажиров было минимально. 2) Максимальное из времен ожидания троллейбуса было минимально. Входные данные Во входном файле INPUT.TXT записано сначала число k, затем - число N (0≤N≤100000). Затем идет N чисел, задающих времена прихода пассажиров на остановку. Каждое из этих чисел - целое от 0 до 100000. Выходные данные В выходной файл OUTPUT.TXT запишите два числа, являющиеся ответами на первый и второй вопросы задачи соответственно. Если решений несколько, выведите любое из них. Пример файла INPUT.TXT 100 5 0 210 99 551 99 Пример файла OUTPUT.TXT 10 51
Комментарии. Задача с Кировской областной олимпиады. Задача очень непростая. Идея заключается в том, что времена прихода людей на остановку нас интересуют только по модулю k. Нужно посчитать, сколько человек приходит на остановку в каждый (по mod k) момент времени, а затем перебрать и найти оптимальное время для троллейбуса.
Задача 133 (Скачать архив)
Задача "Поедание плоского сыра" Есть кусок сыра в виде прямоугольника размера NxM. Маленький мышонок хочет съесть весь кусок сыра. Начав в произвольной клетке, он, поедая очередной кусочек (1х1), переходит в соседний (только если он его еще не съел). Помогите маленькому мышонку составить маршрут по прямоугольнику, чтобы он съел весь сыр. Входные данные. В файле INPUT.TXT записаны числа N, M. (1≤N,M≤30) Выходные данные. В файл OUTPUT.TXT вывести маршрут мышонка в виде последовательности координат кусочков, которые он съедает. Кусочки сыра имеют координаты от 1 до N по оси X, от 1 до M по оси Y. Пример входного файла: 2 2 Пример выходного файла: 1 1 2 1 2 2 1 2
Комментарии. Здесь нужно придумать какой-нибудь способ обойти прямоугольник (например, змейка) и его запрограммировать.
Комментарии. Задачи 134-135 - это подготовка к реализации сортировки. На задаче 134 отрабатывается обмен элементов. Задача 135 - поиск минимального элемента и постановка его на 1-е место. После этого до написания сортировки остается только к 135 задаче добавить поиск минимума, начиная со 2-го элемента и постановку его на 2-е место и т.д. Задачи 134-136 являются обязательными для всех.
Задача 134 (Скачать архив)
Числообменник В начальный момент в массиве записаны по порядку числа от 1 до N (i-ое число - на i-ом месте). С массивом проделывают последовательно следующую операцию: берут два числа, стоящих на местах A и B, и меняют их местами. Требуется напечатать массив после выполнения этих операций. Входные данные Записано сначала число N (2≤N≤100). Далее идет число K - количество операций обмена (0≤K≤10000). Далее идет K пар чисел - номера мест элементов, обмен которых происходит. Выходные данные Выведите элементы массива после выполнения этих операций. Пример входного файла: 10 2 1 3 3 5 Пример выходного файла 3 2 5 4 1 6 7 8 9 10
Задача 135 (Скачать архив)
"Вытаскивание" минимума В массиве требуется найти минимальный элемент, и поставить его на первое место, а то, что стояло на 1-м месте - на его место. Если минимальных чисел несколько, можно менять с любым из них. Если минимальное число уже стоит на 1-м месте, ничего изменять не нужно. Входные данные Вводится число N - количество элементов массива (1≤N≤100), а затем - элементы массива (числа от 1 до 10000). Выходные данные Требуется вывести N чисел - элементы массива после перестановки Пример входного файла 5 3 5 4 1 4 Пример выходного файла 1 5 4 3 4
Задача 136 (Скачать архив)
Сортировка Во входном файле задано сначала число N (1≤N≤100), а затем N целых чисел, по модулю не превышающих 1000. Выведите N чисел в порядке неубывания. Пример входного файла 5 3 1 2 4 2 Пример выходного файла 1 2 2 3 4
Задача 137 (Скачать архив)
Сортировка времени Во входном файле записано сначала число N (1≤N≤100), а затем N моментов времени. Каждый момент времени задается 3 целыми числами - часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60). В выходной файл выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не обязательно) Пример входного файла: 4 10 20 30 7 30 00 23 59 59 13 30 30 Пример выходного файла: 7 30 0 10 20 30 13 30 30 23 59 59
Комментарии. Интересно, что в этой задаче школьники обычно пишут сравнение времен (то есть сначала сравнивают часы, потом - минуты и т.д.). Уметь это делать правильно - очень важно. Однако здесь интересно обсудить с ними идею представления времени одним целым числом (часы*360 + минуты*60 + секунды) и сортировку этих чисел, а затем по этим числам восстановление времен.
Задача 138 (Скачать архив)
Большая сортировка Дано число N (1≤N≤100000), а затем N натуральных чисел из диапазона от 1 до 100. Выведите N чисел в неубывающем порядке Пример входного файла 5 3 1 2 4 2 Пример выходного файла 1 2 2 3 4
Комментарии. Это задача на цифровую сортировку (сортировку подсчетом).
Задача 139 (Задача без тестов!)
Неправильная сортировка. Вам дана программа, решающая 136 задачу (p139.pas). Требуется найти в ней ошибку, и объяснить (письменно или устно), почему так происходит.
Текст программы p139.pas
const nmax=100;
var a:array[1..nmax] of integer;
n:integer;
i,j,g:integer;
f1,f2:text;
begin
assign(f1,'input.txt');
reset(f1);
assign(f2,'output.txt');
rewrite(f2);
{Чтение входных данных}
read(f1,n);
for i:=1 to n do read(f1,a[i]);
{Сортировка массива}
for i:=1 to n do begin {Подбираем число на i-ое место}
g:=i; {Считаем, что самое маленькое число,
которое нам встретилось, стоит на месте i}
for j:=i+1 to n do {Перебираем все числа с i+1 до конца массива}
if a[j]<a[g] then g:=j; {Если нашли число, которое меньше,
чем то, что уже найдено, запоминаем его}
{Меняем местами числа, стоящие на i-ом и
на g-ом местах }
{Если a[i]=x, a[g]=y, то после выполнения
команды: }
a[i]:=a[i]+a[g]; {a[i]=x+y, a[g]=y}
a[g]:=a[i]-a[g]; {a[i]=x+y, a[g]=(x+y)-y=x}
a[i]:=a[i]-a[g]; {a[i]=(x+y)-x=y}
{То есть после этого a[i]=y, a[g]=x
обмен значений произошел}
end;
{Выводим результат}
for i:=1 to n do
write(f2,a[i],' ');
close(f1);
close(f2);
end.
Комментарии. Неправильность сортировки заключается в том, что когда происходит обмен элемента с самим собой (i=g), то a[i] и a[g] - это одна и та же переменная, и a[i]-a[g] = 0 всегда. Эта задача очень важная. Во-первых, на ее примере обсуждается возможность побочных эффектов (пока таких, а в дальнейшем это всплывет при передаче параметров в процедуры). Второе - эта задача учит школьников читать текст программы, тестировать и отлаживать чужие программы (предполагается, что школьник сначала найдет тест, на котором программа не работает, а потом будет пошагово выполнять ее, сравнивая с тем, что должно происходить).
Задача 140 (Скачать архив)
Результаты олимпиады N участников олимпиады получили уникальные номера от 1 до N. В результате решения задач на олимпиаде каждый участник получил некоторое количество баллов (целое число от 0 до 600). Известно, кто сколько баллов набрал. Требуется перечислить участников олимпиады в порядке невозрастания набранных ими баллов. Входные данные. Вводится сначала число N (1≤N≤100) - количество участников олимпиады. Далее вводится N чисел - количества набранных участниками баллов (1-е число - это баллы, набранные участником номер 1, 2-е - участником номер 2 и т.д.) Выходные данные. Выведите в выходной файл N чисел - номера участников в порядке невозрастания набранных ими баллов (участники, набравшие одинаковое количество баллов могут быть выведены в любом порядке). Пример входного файла 5 100 312 0 312 500 Пример выходного файла 5 2 4 1 3
Комментарии. Здесь нужно сортировать один массив, и синхронно с ним менять другой. Тоже, в общем-то, не тривиальная идея.
Задача 141 (Скачать архив)
Количество операций Дана программа сортировки (p141.pas). Требуется узнать, сколько раз при сортировке конкретного массива с помощью этой программы выполняется операция сравнения двух элементов массива (строка 25 программы). Входные данные В файле input.txt записан массив в формате (и удовлетворяющий ограничениям) из задачи 136. Выходные данные В файл output.txt ваша программа должна печатать одно число - сколько раз в процессе сортировки этого массива программой p141.pas выполнится команда сравнения двух элементов массива. Пример входного файла 5 3 1 2 4 2 Пример выходного файла 10
Текст программы p141.pas
const nmax=100;
var a:array[1..nmax] of integer;
n:integer;
i,j,g:integer;
f1,f2:text;
begin
assign(f1,'input.txt');
reset(f1);
assign(f2,'output.txt');
rewrite(f2);
{Чтение входных данных}
read(f1,n);
for i:=1 to n do read(f1,a[i]);
{Сортировка массива}
for i:=1 to n do begin {Подбираем число на i-ое место}
g:=i; {Считаем, что самое маленькое число,
которое нам встретилось, стоит на месте i}
for j:=i+1 to n do {Перебираем все числа с i+1 до конца массива}
if a[j]<a[g] then g:=j; {Если нашли число, которое меньше,
чем то, что уже найдено, запоминаем его}
{Меняем местами числа, стоящие на i-ом и
на g-ом местах }
{Если a[i]=x, a[g]=y, то после выполнения
команды: }
if i<>g then begin
a[i]:=a[i]+a[g]; {a[i]=x+y, a[g]=y}
a[g]:=a[i]-a[g]; {a[i]=x+y, a[g]=(x+y)-y=x}
a[i]:=a[i]-a[g]; {a[i]=(x+y)-x=y}
{То есть после этого a[i]=y, a[g]=x
обмен значений произошел}
end;
end;
{Выводим результат}
for i:=1 to n do
write(f2,a[i],' ');
close(f1);
close(f2);
end.
Комментарии. Задача важная. Во-первых, здесь более-менее явно возникает такое понятие как "сложность алгоритма", хотя разговор о том, сколько действий делает программа, можно вести и раньше. Во-вторых, здесь показывается, как это можно практически посчитать (добавить в программу счетчик).
Комментарии. Начиная с этой задачи, возникают многомерные массивы.
Задача 142 (Скачать архив)
Минимум в таблице Дана таблица чисел, состоящая из N строк по M чисел в каждой. Все числа в таблице - натуральные, не превышающие 1000. Требуется найти наименьшее число в этой таблице. Входные данные Во входном файле записано сначала число N - количество строк, а затем число M - количество столбцом таблицы (1≤N≤100, 1≤M≤100). Далее идет сама таблица. Выходные данные В выходной файл выведите наименьшее число, которое встречается в таблице. Пример входного файла 3 4 6 4 10 4 3 7 5 7 6 3 4 3 Пример выходного файла 3
Задача 143 (Скачать архив)
ГАИ Вдоль шоссе в точках X1,X2,...,XN расположены посты ГАИ. В точке X произошло мелкое ДТП (дорожно-транспортное происшествие). Требуется определить, какой из постов ГАИ расположен ближе всего к этой точке, чтобы с него послать к месту происшествия наряд милиции. Входные данные Во входном файле записано сначала число N - количество пунктов ГАИ. (1≤N≤100) Далее следуют координаты расположения постов ГАИ на прямом шоссе (целые числа от -10000 до 10000). Далее идет координата точки, в которой произошло ДТМ (целое число от -10000 до 10000). Выходные данные В выходной файл требуется вывести одно число - номер поста ГАИ, с которого нужно послать наряд к месту ДТП. Если несколько постов ГАИ находятся на одинаковом расстоянии от точки ДТП, выведите любой из них. Пример входного файла 5 10 2 8 -7 3 7 Пример выходного файла 3
Задача 144 (Скачать архив)
Диагональки В квадратной таблице NxN подсчитать суммы чисел, стоящих на диагоналях. Входные данные Во входном файле содержится число N (1≤N≤100), а затем матрица NxN. Элементы матрицы - числа из диапазона integer. Выходные данные В выходной файл выдать сначала сумму чисел на главной, а затем - на побочной диагонали. Пример входного файла 3 1 2 3 4 5 6 10 9 8 Пример выходного файла 14 18
Задача 145 (Скачать архив)
Максимальная строка В матрице найти номер строки, сумма чисел в которой максимальна. Входные данные Во входном файле записаны числа N и M - количество строк и столбцов матрицы (каждое из них - из диапазона от 1 до 100), а затем сама матрица. Элементы матрицы - числа из диапазона integer. Выходные данные В выходной файл вывести номер строки, сумма чисел в которой максимальна. Если таких строк несколько, вывести последнюю из них. Пример входного файла 3 2 1 2 3 4 5 6 Пример выходного файла 3
Задача 146 (Скачать архив)
Нолики В матрице найти положение нулевого элемента. Входные данные Формат входных данных такой же, как в предыдущей задаче. Хотя бы один нулевой элемент в матрице всегда существует. Выходные данные Вывести сначала номер строки, а затем - номер столбца нулевого элемента. Если в матрице несколько нулей, выдать позицию любого из них. Пример входного файла 3 4 0 1 2 3 4 5 0 1 2 3 4 5 Пример выходного файла 2 3
Задача 147 (Скачать архив)
Симметричная матрица Дана квадратная матрица. Проверить, является ли она симметричной относительно главной диагонали. Входные данные. В файле INPUT.TXT записано число n (0<n≤100). В следующих n строках записано по n целых чисел от -32768 до 32767. Выходные данные. В файл OUTPUT.TXT вывести YES, если матрица симметрична относительно главной диагонали, иначе вывести NO. Пример файла INPUT.TXT 3 1 2 3 2 4 5 3 5 6 Пример файла OUTPUT.TXT YES
Задача 148 (Скачать архив)
Треугольник Паскаля Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая содержит на одно число больше, чем предыдущая. Первое и последнее из этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него. Входные данные. В файле INPUT.TXT записано одно число N (0≤N≤30). Выходные данные. В файл OUTPUT.TXT вывести N строк треугольника Паскаля. Примечание. Все числа в треугольнике Паскаля при указанных ограничениях входят в Longint. Пример файла INPUT.TXT 8 Пример файла OUTPUT.TXT 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1
Задача 149 (Скачать архив)
Даны две квадратных таблицы чисел. Требуется построить третью, каждый элемент которой равен сумме элементов, стоящих на том же месте в 1-й и 2-й таблицах. Входные данные Во входном файле записано сначала число N, затем записана первая таблица, а после нее - вторая. Элементы таблиц - числа от 0 до 100. 1≤N≤100. Выходные данные В выходной файл выведите результирующую таблицу. Пример входного файла 3 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 Пример выходного файла 12 14 16 18 20 22 24 26 28
Комментарии. Задачи про хождение по таблице в некотором смысле предваряют тему алгоритмов на графах. Графы затем возникают как вполне логичное обобщение лабиринтов, задаваемых таблицами.
Задача 150 (Скачать архив)
Хождение за золотом - 1 Однажды царь решил вознаградить одного из своих мудрецов за хорошую работу. Он привел его в прямоугольную комнату размром NxM, в каждой клетке которой лежало несколько килограммов золота. Царь разрешил мудрецу сделать обойти несколько клеток (переходя с клетки, где сейчас находится мудрец, в одну из четырех с ней соседних), и собрать все золото, которое попадется на его пути. Вам дан маршрут мудреца. Требуется определить, сколько килограммов золота он собрал. Входные данные Во входном файле записано план комнаты. Сначала записано количество строк N, затем - количество столбцов M (1≤N≤20,1≤M≤20). Затем записано N строк по M чисел в каждой - количество килограммов золота, которое лежит в данной клетке (число от 0 до 50). Далее записано число X - сколько клеток обошел мудрец. Далее записаны координаты этих клеток (координаты клетки - это два числа: первое определяет номер строки, второе - номер столбца, верхняя левая клетка на плане имеет координаты (1,1), правая нижняя - (N,M)). Гарантируется, что мудрец не проходил по одной и той же клетке дважды. Выходные данные В выходной файл выведите количество килограммов золота, которое собрал мудрец. Пример входного файла 3 4 1 2 3 4 5 6 7 8 9 10 11 12 5 1 1 2 1 2 2 2 3 1 3 Пример выходного файла 22
Задача 151 (Скачать архив)
Хождение за золотом - 2 Задача такая же, как и предыдущая, только мудрец мог более одного раза проходить по одной и той же клетке. Золото с нее он брал при этом только один раз - когда проходил по клетке в первый раз. Входные и выходные данные такие же, как в предыдущей задаче. Дополнительное ограничение: число пройденных мудрецом клеток не превышает 10000. Пример входного файла 3 4 1 2 3 4 5 6 7 8 9 10 11 12 9 1 1 2 1 2 2 2 3 1 3 1 2 1 1 1 2 2 2 Пример выходного файла 30
Задача 152 (Скачать архив)
Хождение за золотом - 3 Задача такая же, как и предыдущая, только передвижения мудреца задаются другим способом: Входные данные Во входном файле записано план комнаты. Сначала записано количество строк N, затем - количество столбцов M (1≤N≤20,1≤M≤20). Затем записано N строк по M чисел в каждой - количество килограммов золота, которое лежит в данной клетке (число от 0 до 50). Далее записано число X - сколько клеток обошел мудрец. 1≤X≤10000. Известно, что мудрец начал с клетки с координатами (1,1). Далее записано X-1 число: куда перемещался мудрец: число 1 обозначает, что мудрец делал шаг вправо, число 2 обозначает, что мудрец делал шаг вверх, число 3 обозначает, что мудрец делал шаг влево, число 4 обозначает, что мудрец делал шаг вниз. Известно, что мудрец не выходил из лабиринта, при этом он мог через одну и ту же клетку пройти несколько раз. Выходные данные В выходной файл выведите количество килограммов золота, которое собрал мудрец. 3 4 1 2 3 4 5 6 7 8 9 10 11 12 9 4 1 1 2 3 3 1 4
Задача 153 (Скачать архив)
В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку. Входные данные Во входном файле задано два числа N и M - размеры таблицы (1≤N≤10, 1≤M≤10). Выходные данные В выходной файл запишите искомое число способов. Примечание При указанных ограничениях, число способов входит в тип Longint. Пример входного файла 2 3 Пример выходного файла 3 Пояснение Если у нас есть таблица из 2 строк и 3 столбцов, то существуют следующие способы попасть из левого верхнего угла в правый нижний: 1) вниз, вправо, вправо 2) вправо, вниз, вправо 3) вправо, вправо, вниз Еще один пример входного файла 3 3 Пример выходного файла 6
Комментарии. Задача на динамическое программирование. Впрочем, она используется лишь как повод поговорить о методе последовательного подсчета (не называя его пока динамическим программированием). Решению этой задаче помогает и знание комбинаторики. Следующая задача является логичным продолжением, однако тут уже без динамического программирования не обойтись.
Задача 154 (Скачать архив)
В прямоугольной таблице 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
Комментарии. Перед тем, как решать задачи дальше, обсуждается, каким образом в памяти компьютера можно представлять графы. Речь идет о матрице смежности и списке ребер.
Задача 155 (Скачать архив)
Города и дороги В галактике "Milky Way" на планете "Neptune" есть N городов, некоторые из которых соединены дорогами. Император "Maximus" галактики "Milky Way" решил провести инвентаризацию дорог на планете "Neptune". Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество дорог. Входные данные. В файле INPUT.TXT записано число N (0≤N≤100). В следующих N строках записано по N чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции (i,j) квадратной матрицы стоит единичка, то i-ый и j-ый города соединены дорогами, а если нолик, то не соединены. Выходные данные. В файл OUTPUT.TXT вывести одно число - количество дорог на планете "Neptune". Примечание. Все дороги двусторонние, то есть если есть дорога из города i в город j, то есть и дорога из города j в город i, и это та же самая дорога. Пример файла INPUT.TXT 5 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 Пример файла OUTPUT.TXT 3
Задача 156 (Скачать архив)
Светофорчики В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до N. Входные данные. В файле INPUT.TXT записано два числа N и M (0<N≤100, 0≤M≤N*(N-1)/2 ). В следующих M строках записаны по два числа i и j (1≤i,j≤N ), которые означают, что перекрестки i и j соединены тоннелем. Выходные данные. В файл OUTPUT.TXT вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке. Примечание. Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого. Пример файла INPUT.TXT 7 10 5 1 3 2 7 1 5 2 7 4 6 5 6 4 7 5 2 1 5 3 Пример файла OUTPUT.TXT 3 3 2 2 5 2 3
Задача 157 (Скачать архив)
Цветной дождь В Банановой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение "зован". На следующий день выпал цветной дождь, причем он прошел только над холмами, в некоторых местах падали красные капли, в некоторых - синие, а в остальных - зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся. Посчитать количество таких "плохих" мостов. Входные данные. В файле INPUT.TXT в первой строке записано N (0<N≤100) - число холмов. Далее идет матрица смежности, описывающая наличие мостов между холмами (1-мост есть, 0-нет). В последней строке записано N чисел, обозначающих цвет холмов: 1 - красный; 2 - синий; 3 - зеленый. Выходные данные. В файл OUTPUT.TXT вывести количество "плохих" мостов. Пример файла INPUT.TXT 7 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 1 3 3 Пример файла OUTPUT.TXT 4
Задача 158 (Скачать архив)
Издевательство Эпиграф: Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана. -Издевается! - подумал Борман. -Кольцевая! - догадался Штирлиц. В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется... Естественно, что Штирлицу хочется проезжать мимо точки, в которой, как он воображает, стоит Борман, как можно чаще. Для этого, естественно, выбранный Штирлицем маршрут должен быть как можно короче. Напишите программу, которая выберет оптимальный для Штирлица маршрут. Входные данные Во входном файле INPUT.TXT записано сначала число N (3≤N≤100), а затем матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0. Выходные данные В выходной файл OUTPUT.TXT выведите номера площадей в оптимальном маршруте. Если маршрутов несколько, выведите любой из них. Пример файла INPUT.TXT 5 0 20 10 30 40 20 0 30 1 2 10 30 0 40 1000 30 1 40 0 21 40 2 1000 21 0 Пример файла OUTPUT.TXT 4 5 2
Задача 159 (Скачать архив)
Треугольник На плоскости даны N точек. Никакие две точки не совпадают, никакие три не лежат на одной прямой. Найдите треугольник с вершинами в этих точках, имеющий наименьший возможный периметр. Входные данные Во входном файле INPUT.TXT записано сначала число N - количество точек (3≤N≤50), а затем N пар вещественных чисел, задающих координаты точек. Выходные данные В выходной файл выведите три числа - номера точек, которые должны быть вершинами треугольника, чтобы его периметр был минимален. Если решений несколько выведите любое из них. Примечание Если у вас есть две точки, и координаты одной из них X1,Y1, а другой X2,Y2, то расстояние R между ними можно вычислить по формуле: R:=sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)); Здесь R должна быть переменной вещественного типа (например, real), а sqrt - стандартная функция, вычисляющая квадратный корень. Пример файла INPUT.TXT 5 0 0 1.3 0 -2 0.1 1 0 10 10 Пример файла OUTPUT.TXT 1 2 4
Комментарии. Эта задача к графам никакого отношения не имеет. Но с другой стороны, это ничто иное, как предыдущая задача, в которой граф явно не задан. Впринципе, можно построить полный граф (вес ребра - длина отрезка между точками) и дальше использовать предыдущую задачу. Хотя можно (и, наверно, более правильно) вообще никакого графа не строить, что большинство и делает.
Комментарии. Рассматривается и разбирается волновой алгоритм. Он разбирается на примере таблицы, а затем обощается на графы. На мой взгляд, писать его на графе даже проще, чем на таблице, хотя для понимания таблица, возможно, несколько нагляднее.
Задача 160 (Скачать архив)
Длина пути В неориентированном графе требуется найти длину минимального пути между двумя вершинами. Гарантируется, что путь существует. Входные данные Во входном файле записано сначала число N - количество вершин в графе (1≤N≤100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной. Выходные данные В выходной файл выведите одно число - длину пути (количество ребер, которые нужно пройти). Пример входного файла 5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5 Пример выходного файла 3
Задача 161 (Скачать архив)
Длина пути - 2 (Такая же задача, как длина пути, но путь может не существовать). В неориентированном графе требуется найти длину минимального пути между двумя вершинами. Входные данные Во входном файле записано сначала число N - количество вершин в графе (1≤N≤100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной. Выходные данные В выходной файл выведите одно число - длину пути (количество ребер, которые нужно пройти). Если пути не существует, выведите одно число -1. Пример входного файла 5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 4 5 Пример выходного файла -1
Задача 162 (Скачать архив)
Путь В неориентированном графе требуется найти минимальный путь между двумя вершинами. Входные данные Во входном файле записано сначала число N - количество вершин в графе (1≤N≤100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной. Выходные данные В выходной файл выведите сначала L - длину пути (количество ребер, которые нужно пройти). А затем выведите L+1 число - вершины в порядке следования вдоль этого пути. Если пути не существует, выведите одно число -1. Пример входного файла 5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5 Пример выходного файла 3 3 2 1 5
Комментарии. В этой задаче нужно, сначала вычислив длины путей до вершин, затем "раскрутить" путь (в обратном направлении). Эта идея обсуждается перед тем, как решать задачу.
Задача 163 (Скачать архив)
Числа в вершинах В неориентированном графе без кратных ребер и петель расставить в вершинах числа так, чтобы если вершины соединены ребром, то числа имели общий делитель, а если нет - то нет. Входные данные. В файле INPUT.TXT записано число N (0<N<7) - количество вершин в графе. Затем записана матрица смежности. Выходные данные. В файл OUTPUT.TXT вывести N натуральных чисел из диапазона Longint, которые вы предлагаете приписать вершинам. Пример файла INPUT.TXT 3 0 1 1 1 0 0 1 0 0 Пример файла OUTPUT.TXT 6 2 3
Комментарии. Задача на сообразительность (решение этой задачи от всех не требуется). Вариантов решения, наверно, много. Наиболее изящный выглядит так: припишем каждому ребру простое число (каждому свое). Тогда поставим в вершины числа, являющиеся произведением чисел, приписанных ребрам, выходящим из этой вершины.
Задача 164 (Скачать архив)
"Компоненты связности" В неориентированном графе посчитать количество компонент связности. В графе могут быть петли и кратные ребра. Входные данные. Во входном файле 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
Комментарии. Решение - тоже волна, помечающая компоненту связности. Идея не так проста, как может казаться.
Комментарии. Заканчивается все двумя занятиями по теме "процедуры", на которых школьникам предлагается написать достаточно большую игровую программу, в которой игрок управляет человечком, ищущим клад в лабиринте. Программа проверяется вручную (соответственно, тестов к ней нет). Более того, правила игры формализуются каждым школьником самостоятельно (по принципу "придумай и напиши игру сам").
Написание большой программы не случайно - на ней можно максимально наглядно продемонстрировать красоту разбиения задачи на подзадачи и реализацию каждой из подзадач отдельной процедурой.
Выбор игровой задачи также не случаен. Дети к играм неравнодушны, однако в течение целого полугодия мы с ними решаем задачи, которые далеко не всегда понятно, какое практическое значение имеют. И тут школьникам предлагается написать игру, и они вдруг с удивлением понимают, что для этого им понадобится то, чем мы все полугодие занимались.