Задачи для самостоятельного решения. 1.9.2.1. Разбить кучу камней заданных весов на 2 части так, чтобы их суммы отличались минимально

1.9.2.1. Разбить кучу камней заданных весов на 2 части так, чтобы их суммы отличались минимально. В первой строке задаётся число камней n, во второй – n целых чисел – веса камней. В первой строке напечатать два числа – количества камней в первой и второй куче, во второй и третьей строке – веса камней в первой и второй полученной куче.

Исходные данные:

1 2 3 4 9

Результат:

4 1

1 2 3 4

1.9.2.2. Разбить кучу камней заданных весов на 3 части так, чтобы суммы самой большой и самой маленькой отличались минимально. В первой строке задаётся число камней n, во второй строке – n целых чисел – веса камней. В первой строке напечатать три числа – количества камней в первой, второй и третьей куче, во второй, третьей и четвёртой строках – веса камней в первой, второй и третьей полученных частях.

Исходные данные:

1 2 3 4 9

Результат:

2 2 1

1 4

2 3

1.9.2.3. Обход шахматным конем всех клеток на доске размера n на n по одному разу. В первой строке задаётся размер доски n, во второй строке задаётся два числа – номер строки и столбца – начальная позиция коня. Напечатать квадратную матрицу чисел с номерами ходов коня. Начальная позиция имеет номер 1. Если решения нет, то напечатать «НЕТ».

Исходные данные:

Результат:

НЕТ

1.9.2.4. Обход шахматным конем всех клеток на доске размера n на n по одному разу и возврат в начальную клетку. В первой строке задаётся размер доски n, во второй строке задаётся два числа – номер строки и столбца – начальная позиция коня. Напечатать квадратную матрицу чисел с номерами ходов коня. Начальная позиция имеет номер 1. Если решения нет, то напечатать «НЕТ».

Исходные данные:

Результат:

НЕТ

1.9.2.5. Попасть шахматным конем из одной заданной клетки в другую (кратчайший путь) на доске размера n на n. В первой строке задаётся размер доски n, во второй строке задаётся два числа – номер строки и столбца – начальная позиция коня, в третьей строке задаётся два числа – номер строки и столбца – конечная позиция коня. Напечатать квадратную матрицу чисел с номерами ходов коня. Начальная позиция имеет номер 1. Если решения нет, то напечатать «НЕТ».

Исходные данные:

1 1

1 3

Результат:

1 0 0

0 0 2

0 0 0

1.9.2.6. Расставить n ферзей на шахматной доске размера n и напечатать для каждой строки номер позиции, в которой стоит в этой строке ферзь. Значение n вводится.

Результат:

2 4 1 3

1.9.2.7. Два ферзя на доске угрожают друг другу или нет. На шахматной доске размера n даны позиции двух ферзей. Напечатать «ДА», если ферзи угрожают друг другу. Напечатать «НЕТ» в противном случае. В первой строке задаётся размер доски n, во второй строке задаётся два числа – номер строки и столбца первого ферзя, в третьей строке задаётся два числа – номер строки и столбца второго ферзя.

Исходные данные:

1 1

1 3

Результат:

НЕТ

1.9.2.8. Из символов 1, 2, 3 построить последовательность длины N, которая не содержит смежные (соседние) одинаковые подпоследовательности. Значение N вводится.

Исходные данные:

Результат:

1.9.2.9. Дан целочисленный массив из N элементов. Построить дерево Фенвика и вычислять суммы на отрезках для заданных диапазонов. В первой строке задаётся размер массива N, а во второй – сам массив, элементы идут через один пробел. Далее следует число запросов k и сами запросы, каждый в отдельной строке. Каждый запрос содержит пару индексов i и j. На каждый запрос нужно вывести сумму элементов массива от номера i до номера j включительно.

Исходные данные:

1 2 3 4 5 6 7 8 9 10 11

1 11

2 10

7 8

Результат:

1.9.2.10. Медиана на плоскости. На плоскости находятся N точек (N чётно). Никакие три точки не лежат на одной прямой. Ваша задача — выбрать две точки так, что прямая линия, проходящая через них, делит множество точек на две части одинакового размера. Первая строка содержит целое число N (2 ≤ N ≤ 10 000). Каждая из следующих N строк содержит пары целых чисел x_i, y_i (−10⁹ ≤ x_i, y_i ≤ 10⁹) — координаты i-й точки. Вывести номера выбранных точек.

Исходные данные:

0 0

1 0

0 1

1 1

Результат:

1 4

Продвинутые задачки.

1.9.3.1. Охотники и приведения. Группа из N охотников сражается с N привидениями. Каждый охотник вооружен протонной пушкой, которая стреляя лучом в привидение, испепеляет его. Луч распространяется по прямой линии и исчезает после попадания в привидение. Охотники договорились о следующей стратегии. Каждый из них выберет по привидению, образовав таким образом N пар Охотник-привидение, а затем одновременно каждый из охотников стреляет в свое привидение. Как известно, очень опасно дать протонным лучам пересечься, поэтому охотники разбиваются на пары так, чтобы лучи не пересеклись. Задача заключается в том, чтобы помочь охотникам разбиться на пары, удовлетворяющие указанному ограничению

Предположим, что позиция каждого охотника и каждого привидения - это фиксированная точка на плоскости и никакие три точки не лежат на одной прямой.

Составьте программу, которая:

считывает позиции охотников и привидений из входного файла;

разбивает множество введенных позиций на пары Охотник-привидение;

выводит полученную последовательность пар в выходной файл.

В первой строке набора находится число N - количество сражающихся охотников (N<=150), В следующих 2*N строках заданы позиции на плоскости N охотников и N привидений (сначала все охотники, затем - все привидения); каждая позиция занимает отдельную строку и представляет собой пару целых чисел, разделенных пробелами, - координаты позиции на плоскости (абсолютные значения координат не превосходят 32000).

Исходные данные:

-100 -200

-100 200

-200 -100

200 -100

100 200

100 -200

200 100

-200 100

Результаты:

-100 -200 100 -200

-100 200 100 200

-200 -100 -200 100

200 -100 200 100

1.9.3.2. Лопасти и винты. Винт вертолёта состоит из трёх лопастей. Три лопасти подходят для одного винта, если их длины отличаются не более, чем на 1 см. Каждая лопасть может входить только в один винт, но не все лопасти обязательно попадут в какие-то винты. Если решений несколько, можно вывести любое. В первой строке исходных данных указано число лопастей n (n <=100). Во второй строке перечислены n целых чисел – длины лопастей. Написать программу, которая составит из имеющихся лопастей наибольшее число винтов и напечатает их количество в первой строке результата, а в последующих строках тройки номеров лопастей, составляющих собранные винты.

Исходные данные:

3 2 7 4 3 2 1

Результат:

1 2 3

2 3 4

1.9.3.3. Решить судоку. В матрице 9 на 9 некоторые числа уже расставлены по правилам судоку, остальные клетки пустые (0). Расставить недостающие числа по правилам судоку: в каждой строке, каждом столбце и в каждом фрагменте 3 на 3 встречаются все цифры от 1 до 9. Если решений нет, то напечатать «НЕТ» или напечатать заполненную матрицу.

Исходные данные:

6 7 0 0 0 0 0 3 1

8 3 5 1 6 0 0 2 9

0 0 4 9 3 5 7 0 0

7 6 0 0 0 3 9 4 2

0 0 2 6 8 0 0 0 7

5 9 0 0 0 0 0 0 6

0 0 6 0 0 1 0 0 0

1 2 0 0 0 0 0 0 5

4 0 0 0 0 0 0 0 3

Результат:

6 7 9 8 4 2 5 3 1

8 3 5 1 6 7 4 2 9

2 1 4 9 3 5 7 6 8

7 6 8 5 1 3 9 4 2

3 4 2 6 8 9 1 5 7

5 9 1 7 2 4 3 8 6

9 8 6 3 5 1 2 7 4

1 2 3 4 7 8 6 9 5

4 5 7 2 9 6 8 1 3

1.9.3.4. ГО выявить все группы одноцветных камней на доске N на N. В первой строке задаётся размер доски N. В следующих N строках по N символов записано положение камней в игре ГО. Символ ‘.’ обозначает пустое место, символ ‘*’ обозначает чёрный камень, символ ‘O’ – белый камень. Написать программу, которая найдёт и напечатает все группы чёрных камней. В первой строке вывести количество чёрных групп, а далее сами группы в отдельной строке в следующем формате: сначала будет идти натуральное число k – размер группы, потом будут перечислены k пар чисел – позиции камней этой группы (номер строки и номер столбца) – числа от 1 до N. Два камня входят в одну группу, если они являются соседями по вертикали или горизонтали, или имеют других соседей из этой группы.

Исходные данные:

.O...

**..O

..O**

..*..

*OOO.

Результат:

2 2 1 2 2

2 3 4 3 5

1 4 3

1 5 1

1.9.3.5. ГО проверить, что группа одноцветных камней на доске N на N окружена камнями противника (другого цвета). В первой строке задаётся размер доски N. В следующих N строках по N символов записано положение камней в игре ГО. Символ ‘.’ обозначает пустое место, символ ‘*’ обозначает чёрный камень, символ ‘O’ – белый камень. В следующей строке заданы координаты одного из камней некоторой группы. Написать программу, которая напечатает «ДА», если группа камней окружена камнями противника. В противном случае напечатать «НЕТ». Два камня входят в одну группу, если они являются соседями по вертикали или горизонтали, или имеют других соседей из этой группы. Группа камней окружена, если все соседние позиции заняты камнями противника.

Исходные данные:

*O*..

**..O

..O**

..*..

*OOO.

1 2

Результат:

ДА

1.9.3.6. ГО проверить, что группа одноцветных камней на доске N на N имеет по крайней мере два глаза, т.е. жизнеспособна. В первой строке задаётся размер доски N. В следующих N строках по N символов записано положение камней в игре ГО. Символ ‘.’ обозначает пустое место, символ ‘*’ обозначает чёрный камень, символ ‘O’ – белый камень. В следующей строке заданы координаты одного из камней некоторой группы. Написать программу, которая напечатает «ДА», если группа камней имеет два глаза и не может быть окружена и снята с доски. В противном случае напечатать «НЕТ». Два камня входят в одну группу, если они являются соседями по вертикали или горизонтали, или имеют других соседей из этой группы. Группа камней окружена, если все соседние позиции заняты камнями противника.

Исходные данные:

*.*..

**ООO

.*O**

.*О..

*OOO.

3 3

Результат:

НЕТ

СПИСОК ЛИТЕРАТУРЫ

Литература по языкам программирования

Бьерн Страуструп. Язык программирования С++. Специальное издание. Бином, Москва, 2001г.