A1031

Задача. Получить все перестановки элементов 1, …, 6.

Решение

Все перестановки считаются и выводятся с помощью рекурсивной функции perestanovka().

Когда в ней складывается новый набор элементов, проверяем что бы в нем не было повторяющихся значений (считаем факториал и сумму, они должны совпадать со стандартом (6! = 720,  1+2+3+4+5+6 = 21) и тогда выводим.

Что бы убедиться, что выведено правильное количество перестановок, выводим в конце значение счетчика cnt (находится внутри функции perestanovka()) и требуемое значение перестановок ( 6! = 720). Эти значения совпадают.

А на Java решение выглядит так:
 

А717а

Задача

Две правые треугольные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы в виде последовательности [latex]\frac{\left(n+1\right)*n}{2}[/latex] чисел: сначала идет [latex]n[/latex] элементов первой строки, затем [latex]n-1[/latex] элемент второй строки, начиная со второго элемента, и т. д. (из последней, [latex]n[/latex]-й строки берется только [latex]n[/latex]-й элемент).

Получить матрицу [latex]A*B[/latex].

Тесты

n матрица A матрица B результат (матрица A*B) комментарий
2 1 2

3

4 5

6

4 17

0 18

пройден
3 1 -1 2

4 6

6

1 -1 1

0 0

3

1 -1 7

0 0 15

0 0 18

пройден

Решение

Сначала обнуляем и вводим обе матрицы. Так как они заданы строкой чисел и известно, что они правые треугольные, заполняем ячейки массива, начиная от диагональных элементов.

Умножение выполнимо, потому что оба сомножителя — квадратные матрицы одного и того же порядка. Перемножаем матрицы стандартным способом (строки первой матрицы на столбцы второй).

Ссылка на код.

e-olimp 1098. Ходи ферзем!

Задача о восьми ферзях

Задача о восьми ферзях

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

Входные данные. В одной строке задано сначала натуральное число T (T < 6) — количество тестов. Далее через пробел задано T блоков по 8 целых чисел от 1 до 8 – номера горизонталей, на которых находится ферзь с i-той вертикали. Вертикали пронумерованы подряд.

Выходные данные. Одна строка, содержащая последовательность соответствующих минимальных количеств ходов без пробелов.

Тесты

Входные данные Выходные данные Комментарий
2 1 1 1 1 1 1 1 1 2 4 6 8 3 2 7 5 71 пройден

Решение

«Поиск с возвратом» в задаче о восьми ферзях.
Алгоритм.
При решении задачи используется два массива : массив расстановок из теста и массив правильной расстановки. Первоначально массив правильных расстановок — пустой (все значения элементов массива = -1).

Для вычисления правильных расстановок вызывается рекурсивная функция line_up (параметром которого является номер столбца). Внутри функции line_up вызывается функция check (параметр — номер столбца), она проверяет горизонтальную линию и две диагонали на поля, которые бьет ферзь. Элементам массива правильных расстановок присваиваются номера горизонтальных линий (алгоритм «Поиск с возвратом»).

Как только достигается одна из возможных правильных расстановок вызывается функция calc_min_strok(). Если элемент одного массива не равен элементу другого — это ход. Функция calc_min_strok() вычисляет количество ходов для данной расстановки и решает минимальное оно или нет для данного теста.

Решение на Java:
(Что бы прошло на e-olimp нужно удалить все комментарии)

 

e-olimp 5075

Задача Ориентированный граф задан списком ребер. Найдите степени всех вершин графа.
Входные данные. Входной файл содержит числа [latex]n[/latex]  [latex]\left(1\leq n\leq 100\right)[/latex] — число вершин в графе и [latex]m[/latex] [latex]\left(1\leq m\leq n*\left(n-1\right)\right)[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

Выходные данные. Выведите в выходной файл [latex]n[/latex] пар чисел — для каждой вершины сначала выведите полустепень захода и затем полустепень исхода.

Тесты

Тесты Результат Комментарии
4 41 21 3

2 3

3 4

0 21 12 1

1 0

пройден
4 1
3 2
0 01 00 1

0 0

пройден

Решение

Решение на Java:
 

 

АА24

Задача

 Ввести строку S и целое положительное число N, а также символы C1 и С2. Заменить каждое вхождение символа C1 на N символов C2.

Тесты

Данная строка C1 C2 n Получаемая строка Комментарий
a111a111 a = 3 ===111===111 пройден
omnomnom n  1 om-om-om пройден
Nina N Z 1 Zina пройден

Решение

 Мы идем по данной строке, если попадаем на символ, который не нужно заменять (не С1), то просто переписываем его в новую строку, если попадаем на символ С1, записываем в созданную новую строку n символов С2.

Код на Java:
 

Ю12.13

Задача

Морзянка. Вводимый с клавиатуры или из файла текст перевести в последовательность точек и тире с помощью азбуки Морзе. Результат можно иллюстрировать звуком.

Тесты:

Текст Результат Комментарий
SOS  …—…  пройден
 A true SOS !!!  .- -…- — .-. ..- . -…- … — … -…- —..— —..— —..— -…-  пройден

 

Код:

Я создала ассоциативный  массив  через map, и связала буквы («ключ«) и соответствующие им значения в азбуке Морзе («значение«). Чтобы не заполнять его еще и большими буквами, во вводимом тексте уменьшаю буквы с помощью функции tolower .  

Решение через c-string :

Ссылки:

string

c-string.

Решение на Java: