e-olymp 1454. Лабиринт знаний

Задача

В Летней Компьютерной Школе (ЛКШ) построили аттракцион «Лабиринт знаний». Лабиринт представляет собой n комнат, занумерованных от 1 до n, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход — в комнате n. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.

Пример

 Входные данные Выходные данные
2 2

1 2 5

1 2 -5

5
5 5

1 2 5

2 4 5

4 5 5

3 3 5

2 3 5

15
3 3

1 2 5

1 2 -5

2 2 6

🙁
3 3

1 2 2

2 3 3

3 1 4

🙂

Решение

Засчитанное решение.

Код на ideone.

Создадим вектор расстояний length на n элементов. Все элементы кроме 0-го приравниваем к минимальному числу. Нулевой элемент приравниваем к 0. Также создадим вектор p в котором будем хранить номер вершины из которой мы попали в текущую. Затем в цикле проходим по всем вершинам и в вектор length записываем расстояние за которое мы дошли в эту вершину. n-1 элемент вектора и будет ответом задачи. Затем мы восстанавливаем путь из нулевой вершины в последнюю, но будем это делать не более n раз. Затем проверяем, если в последней вершине значение не изменилось то выводим :(. Затем проверяем был ли в пути цикл, если да то выводи :), в противном случае выводим значение length[n-1].

 

 

А1035

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

Пример

Входные данные Выходные данные
a1

b1

a1
b3
d2
b1
a1
h8
a1
c2
e3
g2
h4
g6
h8

 

Решение

Читаем входные данные. Преобразуем их в координаты начального и финального поля на шахматной доске. Массив chessboard  сначала заполняем -1 (не пройденные поля), затем значение в поле с начальными координатами присваиваем 0. Затем будем отмечать все доступные ходы коня до тех пор пока не изменится значение в финальном поле. Затем, если у нас не совпали начальное и финальное поле будем восстанавливать путь коня. Создаем массив в котором и будет путь коня. Первое значение которое мы заносим в массив будет наше финальное поле. Затем с этого поля будем рассматривать все возможные ходы которые пройдут по уже помеченным клеткам. Если в финальное поле можно было попасть несколькими путями одинаковой длины то нам не имеет значение каким из них возвращаться в начальное поле. Затем выводим массив пути в обратном порядке.

Код на ideone.

А714

Задача

Комплексная матрица [latex]Z[/latex] представляется парой [latex]X[/latex], [latex]Y[/latex] действительных матриц так, что [latex]Z=X+iY[/latex]. Даны действительные квадратные матрицы [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] и [latex]D[/latex] порядка [latex]m[/latex]. Найти произведение двух комплексных матриц [latex]A+iB[/latex] и [latex]C+iD[/latex], т. е. найти действительные квадратные матрицы [latex]X[/latex] и [latex]Y[/latex] порядка [latex]m[/latex] такие, что [latex]X+iY=(A+iB)(C+iD)[/latex].

Пример

Входные данные Вывод
3

9 5 4 8 5 2 6 1 3

1 4 6 5 3 1 9 8 7

4 2 8 3 9 5 1 2 7

5 6 7 4 1 9 3 8 2

X:

16 13 70

9 24 39

-68 -91 -75

 

Y:

99 141 186

96 108 167

110 165 218

 

 

Решение

 

 

 

 

[latex]X+iY=(A+iB)(C+iD)=(AC-BD)+i(AD+BC)[/latex], т. е. [latex]X=AC-BD[/latex], [latex]Y=AD+BC[/latex].

Код на ideone.

AA8

Задача

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

Тесты

Ввод Вывод
abc

012

a0b1c2
0123

0123

00112233

 

e-olimp 4000. Обход в глубину

Задача e-olimp 4000

Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину).

Входные данные

В первой строке содержится два целых числа [latex]n[/latex] и [latex]s[/latex]  [latex](1\leq s\leq n\leq 100)[/latex], где [latex]n[/latex] — количество вершин графа, а [latex]s[/latex] — выделенная вершина. В следующих [latex]n[/latex] строках записано по [latex]n[/latex] чисел — матрица смежности графа, в которой цифра «0» означает отсутствие ребра между вершинами, а цифра «1» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

Выходные данные

Выведите одно число — искомое количество вершин.

Пример:

Входные данные Выходные данные
5 1 3
0 1 1 0 0
1 0 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 0

Решение

 

 

Вводим данные, затем в первом цикле проверяем строку [latex]s[/latex]и записываем в стек все вершины инцидентные данной. Так как в условии гарантируется наличие на главной диагонали нулей, то будем помечать проверенные вершины с помощью элемента расположенного на главной диагонали (то есть будем присваивать ему значение отличное от 0, к примеру 1). После будем проверять все строки в стеке до его опустошения, и увеличивать счётчик на единицу после удаления из стека не помеченной вершины.

Код на ideone.

Засчитанное решение.

 

 

Ю4.21

Задача.

Целочисленный массив K(n, n) заполнить нулями и единицами, расположив их в шахматном порядке.

Тесты.

Ввод Вывод
1 1
3
6

 

 

 

Решение.

В цикле проверяем если сумма номеров элемента в массиве чётна, то печатаем единицу, в противном случае печатаем ноль.

А155

Задача.

Даны натуральное число $n$, действительные числа $x_1, \ldots, x_n, $ где [latex](n\geq 2).[/latex] Вычислить:

[latex]\left( \left( \frac{1}{|x_{1}|+1}+x_{2} \right)\left(\frac{1}{|x_{2}|+1}+x_{3} \right)\cdots\left(\frac{1}{|x_{n-1}|+1}+x_{n} \right)\right)[/latex]

Тесты.

Ввод Вывод
$n$ $x_1, \ldots, x_n$ $k$
2 1 1 1.5
3 0.5 1 2 4.16667
3 -0.3 1 -0.5 0

 

Решение.
Задаем переменные $n, k$и массив действительных чисел с количеством элементов $n$. В первом цикле вводим числа в массив. Во втором умножаем переменную $k$ каждый раз на [latex]\left(\left(\frac{1}{|x_{n-1}|+1}+x_{n} \right)\right)[/latex]. После выводим значение $k$.

А812ж

Задача.

Дан текст, каждый символ которого может быть малой буквой, цифрой или одним из знаков +, -, *. Группой букв будем называть такую совокупность последовательно расположенных букв, которой непосредственно не предшествует и за которой непосредственно не следует буква. Аналогично определим группу цифр и группу знаков.

Найти самую длинную группу цифр. Если эту наибольшую длину имеет несколько групп, то взять первую по порядку.

Тесты.

Ввод Вывод
1aa2bb+-c2cc—**22 22
11aa2bb+-c2cc—**22 11
1aa2bb+-c23cc—**22 23
111aa2bb+-c2cc—**22 111
1aa2bb+-c234cc—**22 234
1aa221bb+-c234cc—**22 221

Код программы (string):

Код программы (cstring):

Решение.

Вводим строку в переменную s. В первом цикле ищем наибольшую группу записывая значение в переменную n. В следующем цикле ищем номер первого символа в группе записывая значение в переменную a. В третьем цикле выводим символы с номерами с a-го по a+n.

Ю3.11

Задача.

Получить таблицу пересчета миль в километры и обратно (1 миля=1,609344 км) для расстояний,не превышающих км, в следующем виде:

мили км
0,6214 1,0000
1,0000 1,6093
1,2428 2,0000
1,8641 3,0000
2,0000 3,2187

Тесты.

Ввод Вывод
k
3 mile     km
0.6214 1.0000
1.0000 1.6093
1.2427 2.0000
1.8641 3.0000
7 mile     km
0.6214 1.0000
1.0000 1.6093
1.2427 2.0000
1.8641 3.0000
2.0000 3.2187
2.4855 4.0000
3.0000 4.8280
3.1069 5.0000
3.7282 6.0000
4.0000 6.4374
4.3496 7.0000
0 mile      km
3.3 mile     km
0.6214 1.0000
1.0000 1.6093
1.2427 2.0000
1.8641 3.0000
2.0000 3.2187

 

 

 

Решение.

 

Читаем значение k. В цикле имеем два значения n  и i, значение  увеличиваем в каждом витке цикла, а значение  тогда, когда значение [latex]i/1.609344[/latex] превысит значение n. Пока этого не произошло печатаем значения соответствующие км и [latex]i/1.609344[/latex] милям. Когда-же значение [latex]i/1.609344[/latex] превысило значение n проверяем, если значение [latex]n\times 1.609344[/latex] меньше или равно печатаем строку, где значения миль равно n, а значение км [latex]n\times 1.609344[/latex], потом проверяем если значение i  меньше или равно значению k, то печатаем строку, где значение миль равно[latex]i/1.609344[/latex]а значение км равно i. То есть для подсчёта целых значений миль используем параметр n, а для подсчёта целых значений км параметр i.

А60д

Задача.

Пусть D — заштрихованная часть плоскости и пусть u определяется по и y следующим образом :

[latex]u=\begin{cases} \sqrt{|x^{2}-1|} & \text{ if } (x, y)\epsilon D \\ x+y & \end{cases}[/latex]

Даны действительные числа x и y. Определить u.
1

Тесты.

Ввод Вывод
x y u
0 0 1
0 0.5 1
-0.3 0.6 0.953939
0.3 0.6 0.953939
-0.2 -0.1 -0.3
0.8 0.6 1.4
0.5 -0.5 0

 

 

 

Решение.

Через переменные x, y обозначим координаты точки.

Мы имеем 3 графика функций:

  1. [latex]y=-x[/latex]
  2. [latex]y=x[/latex]
  3. [latex]x^{2}+y^{2}=1[/latex]

 

Проверяем находится ли точка в заштрихованной области. Точка обязательно должна находиться над или на оси x. 

Если точка принадлежит данной области то для расчёта используем формулу:

[latex]\sqrt{|x^{2}-1|}[/latex]

В противном случае формулу:

[latex]u=x+y[/latex]

 

Ю1.1

Задача.

Из градусов в радианы. Угол α задан в градусах, минутах и секундах. Найти его величину в радианах(с максимально возможной точностью).

Тесты.

Ввод Вывод
градусы(grad) минуты(min) Секунды(sec) радианы(rad)
0 0 0 0
90 0 0 1.570796326794897
179 59 60 3.141592653589793
-270 0 0 -4.7123889803847

 

 

 

 

Решение.

Обозначим через переменные grad, min,  sec  число градусов, минут, секунд.

1 градус= 60 минут= 3600 секунд.

Сначала проверяем число градусов больше 3600  или нет. Если меньше то ничего не меняем, а если больше то от числа градусов отнимаем 360 до тех пор пока оно не станет меньше 360. После используем формулы перевода градусов, минут и секунд в радианы:

[latex]\mathit{rad=grad\frac{\pi }{180}}[/latex]

 

[latex]\mathit{rad=min\frac{\pi }{180}/60}[/latex]

 

[latex]\mathit{rad=sec\frac{\pi }{180}/3600}[/latex]

Если число градусов положительно то используем конечную формулу:

[latex]\mathit{rad=grad\frac{\pi }{180}+min\frac{\pi }{180}/60+sec\frac{\pi }{180}/3600}[/latex]

Если же оно отрицательно то используем другую формулу:

[latex]\mathit{rad=grad\frac{\pi }{180}-min\frac{\pi }{180}/60-sec\frac{\pi }{180}/3600}[/latex]