Центр Информатизации и Дистанционного Обучения

Задача 1 (методы сортировки)

 

Кувшины

Имеется n кувшинов, в каждом из которых лежит камень белого, синего или красного цвета. «Заглядывая» в каждый кувшин по одному разу, расположите их в таком порядке, чтобы первыми следовали кувшины с белыми камнями, за ними – с синими, далее сосуды с красными камнями.

 

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

В первой строке находится число n - количество кувшинов. В следующей строке n чисел, отражающих цвет камней в соответствующих кувшинах: 1 – белый, 2 – синий, 3- красный.

 

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

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

 

 

 

Задача 2 (вычислительная геометрия)

 

Два прямоугольника

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

 

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

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

 

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

Два числа.

 

 

 

Задача 3 (теория чисел)

 

Коробки для шариков

Некто коллекционирует шарики (маленькие, стеклянные, цветные шарики) и хочет купить коробки для их хранения. Коробки бывают двух типов.

Тип 1: каждая такая коробка стоит c1 рублей и в ней может хранится ровно n1 шариков.

Тип 2: каждая такая коробка стоит c2 рублей и в ней может хранится ровно n2 шариков.

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

 

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

Первая строка содержит n, число шариков. Вторая строка содержит c1 и n1, третья строка содержит c2 и n2. Целые числа c1, n1, c2, n2 положительны и меньше 2 000 000 000.

 

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

Два числа: m1 и m2, если таковые существуют. Иначе вывести сообщение «нет решений».

 

 

 

Задача 4 (строки)

 

Генератор слов

Переставляя буквы в заданном слове, можно составлять различные другие слова, в том числе бессмысленные. Например, из слова «ФАРА» получаются слова «АРФА», «ФААР» и т.д.  Составить программу, которая по заданному слову описанным выше способом, формирует новое, следующее за исходным по алфавиту. В приведенном примере это слово «ФРАА».

 

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

Исходное слово.

 

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

Новое слово.

 

 

Задача 5 (перебор с возвратом)

 

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

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

 

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

Первая строка содержит n, число участников состязания. Каждая из следующих n строк содержит вес одного из участников, вес задается целым числом от1 до 450.

 

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

Два числа: суммарный вес людей в одной команде и суммарный вес людей в другой команде.

 

 

Задача 6 (динамическое программирование)

 

Караван

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

 

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

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

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

 

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

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