e-olymp 88. Месть Ли Чака

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

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

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

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

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные Выходные данные
$531$ $348$ $1645$ $911$
$1784353$ $453345$ $463973$ $214457$
$39252362$ $345673$ $786536$ $302328$
$68790234$ $679643$ $789057$ $281232$
$324$ $8564$ $45074547$ $32984424$

Код программы

Решение задачи

Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. Обозначим начальное местоположение Гайбраша — $g,$ Ли Чака — $l.$, выход $e.$
Безопасный для Гайбраша маршрут существует тогда и только тогда, когда существует путь $\omega,$ такой, что для $\forall v \in \omega \ \rho \left(g, v \right ) + 1 < \rho(l, v).$ С помощью поиска в ширину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в ширину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае — нет.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 179. Распределение

Распределение

Для нападения на некоторые поселения людей, эльфов и карликов вождь Орды Оргрим Думхаммер сформировал из всех имеющих в наличии воинов [latex]N[/latex] различных отрядов, которые были отправлены на завоевания. Однако прибывшие лишь только сейчас разведчики донесли о силах противников, скопленных в этих поселениях, что естественно скорректировало планы Оргрима. И теперь он хочет произвести перераспределение войск по отрядам, переводя воинов из одного отряда в другой. При этом, чтобы не создавать неразбериху в рядах своей армии и выполнить перераспределение как можно быстрее, количество таких переводов должно быть минимально возможным (за один раз переводится один солдат из некоторого отряда в другой).

Напишите программу, которая определяет минимальное количество переводов для перераспределения войск.

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

Первая строка входного файла содержит целое число [latex]N[/latex] [latex](1 ≤ N ≤ 10000)[/latex] – количество отрядов. Вторая строка содержит изначальное распределение воинов по отрядам – [latex]N[/latex] чисел, каждое из которых определяет количество воинов в соответствующем отряде. А в третьей строке – требуемое распределение солдат. Количество солдат в одном отряде не превышает [latex]10^6[/latex]. Гарантируется, что общее число воинов в изначальном распределении и требуемом совпадает.

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

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

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
2
4 2
5 1
1
1
4
4
0
3
2 2 2
4 1 1
2
3
6 3 1
0 0 10
9

 

Код программы

Решение задачи

Данная задача решается вычислением и суммированием разности соответствующих элементов второго массива и первого. Таким образом мы найдем количество воинов, которых не хватает и которых надо перевести в другой отряд. Возьмём эту разность по модулю, затем поделим на [latex]2[/latex], так как мы учитывали всех воинов. В итоге получим минимальное количество переводов из одного отряда в другой.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

A393a

Задача:

Даны натуральное число [latex]n[/latex], целочисленная квадратная матрица порядка [latex]n[/latex]. Получить [latex]{b}_{1}[/latex],…,[latex]{b}_{n},[/latex] где [latex]{b}_{i}[/latex] — это наименьшее из значений, элементов находящихся в начале [latex]i[/latex]-й строки матрицы до элемента, принадлежащего главной диагонали, включительно.

Тесты:

 
Вводимые данные Предполагаемый вывод Комментарий
4 4 3 2 1 4 3 2 1 Тест пройден
4 3 2 1
4 3 2 1
4 3 2 1
1 2 3 4 1 1 1 1 Тест пройден
1 2 3 4
1 2 3 4
1 2 3 4

Решение:

Считываем матрицу и проходим в цикле по каждой строке ведя поиск минимального элемента (но есть одно «Но»,  поиск ведется под главной диагональю матрицы).
У всех элементов находящихся под главной диагональю матрицы, включительно, индекс строк больше или равен индексу столбцов заданной матрицы. Учтем это при составлении программы.
Осталось только написать код с учетом вышеперечисленных особенностей задачи.

Код:

 

Версия программы на Ideone.com

Ссылка на источник

Ю 4.24

Задача:

В массиве [latex]A[n][/latex] каждый элемент, кроме первого, заменить суммой всех предыдущих элементов.

 
Вводимые данные Предполагаемый вывод Комментарий
1 1 1 1 1 1 1 1 2 3 4 5 Тест пройден
1 2 3 4 5 6 7 8 9 1 1 3 6 10 15 21 28 36 Тест пройден
3 5 2 9 0 4 65 156 1 3 3 8 10 19 19 23 88 244 Тест пройден
2 -7 3 8 -4 5 -2 4 2 2 2 -5 -2 6 2 7 5 9 Тест пройден

Код:

Описание:

Простейшие операции с массивом. С помощью цикла записываем данные в массив, после чего, снова с помощью цикла, записываем новые данные во второй массив. Далее выводим результат.

Алгоритм:

  1. Объявление переменной и ввод размерности массива.
  2. Создание массива.
  3. Создание цикла, для записи вводимых данных в массив.
  4. Создание нового  массива.
  5. Создание цикла, для ввода обработанных данных в новый массив.
  6. Создание цикла, для вывода результата.
  7. Окончания работы программы.

Работающая версия программы на Ideone.com

Ссылка на источник

Ю4.35

Постановка задачи

Совместная работа. Известно время $latex t_1,t_2,\cdots,t_n$, за которое некоторую работу может выполнить каждый из $latex n$ рабочих бригады, работая в одиночку. Сколько времени понадобится бригаде на выполнение этой работы, если они будут работать совместно (и при этом никто из них не «сачкует»)?

Тесты

Количество рабочих n. Время t каждого рабочего, требуемое для выполнения некоторой работы.  Время совместной работы.
3 5 7 9 2.2
4 7 9 11 23 2.6
4 1 2 3 4 0.5
5 3 1 5 2 3 0.4

 

Код

Описание решения

В данной задаче нам нужно найти время, за которое n рабочих выполнят какую-то совместную работу. В задаче не указан  общий объём выполняемой работы, по-этому зададим его как 1. Время совместной работы находят по формуле: $latex \frac{1}{\frac{1}{t_1}+\frac{1}{t_2}+\cdots+\frac{1}{t_n}}$.

В программе используем один цикл for в котором задаем значение переменной workingTime и суммируем объем выполняемой работы за час для каждого шага цикла (для каждого рабочего). После завершения цикла получаем объем работы выполняемой всеми работниками вместе за час. Делим общий объем работы на объем работы за час и получаем искомую величину.

Посмотреть, как работает программа можно на сайте  ideone.
Задача была решена на основе данного решения.

Ю4.3

Задача

Центрирование массива. От каждого из заданных чисел [latex]{x}_{1}, {x}_{2}, \ldots, {x}_{m}[/latex] отнять их среднее арифметическое [latex]\overline{x}_{i} = {x}_{i}[/latex] — [latex]{x}_{cp}[/latex], [latex]i = 1, 2[/latex], … , [latex]m[/latex].

[latex]\overline{x}[/latex] = [latex]1/m[/latex];
[latex]E[/latex] от [latex]m[/latex] при [latex]i = 1 (x_1)[/latex];
[latex]{x}_{i}[/latex] = [latex]{x}_{i}[/latex] — [latex]\overline{x}[/latex]; [latex]i = 1, 2[/latex], … , [latex]m[/latex]

Результаты разместить на месте исходных данных.

Тесты

Количество элементов в массиве — m Массив Результат
2 2

5

-1,5

1,5

2 2

6

-2

2

7 2

6

-3

5

1

0

0

0.43

4.43

-4.57

3.43

-0.57

-1.57

-1.57

Код

Протестированный код можно увидеть тут.

Решение

Объявляем массив типа double размерностью m. Считываем размерность из первой строки ввода, конвертируем из типа string в тип int; затем считываем элементы массива из второй строки ввода (их конвертируем в double — для точности вычислений). В циклах: находим сумму введенных чисел, затем их среднее арифметическое, затем высчитываем новые значения элементов массива, вычитая от каждого из них среднее арифметическое всего массива. Записываем новые значения поэлементно в исходный массив arr[ ]. Выводим arr[ ].

 

 

Ю 4.17

Постановка задачи

В массиве [latex]A(n)[/latex] найти и напечатать номера (индексы) локальных максимумов, то есть таких [latex]a_{i}[/latex], что [latex]a_{i-1}<x_{i}>a_{i+1}[/latex].

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

Количество значений и сами значения

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

Индексы локальных максимумов

Тесты

Количество значений Значения Результат
1 6 2 4 6 1 3 7 5 2
2 7 3 1 6 2 8 5 7 2, 4
3 10 2 5 8 3 5 6 9 7 1 4 2, 6

Решение

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Объявляем переменную n для хранения размера массива. Далее создаем массив типа double. Для нахождения локальных максимумов x[i] создаем цикл for, в котором при каждой итерации будем проверять, являются ли значения локальными максимумами. Если значение удовлетворяет условие, выводим на экран индекс этого значения. Например, в первом тесте мы вводим количество значений 6, сами значения 2 4 6 1 3 7 5 и нашим результатом оказывается число с индексом 2, т.е. число 6. Так как числа 4 и 1 меньше 6, наше значение будет удовлетворять условие.

Ю4.32

Постановка задачи

Суммы по косой. Просуммировать элементы матрицы [latex]A(n,n)[/latex] по каждой из линий, параллельных главной диагонали. Напечатать полученные суммы.

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

[latex]n[/latex] — размерность матрицы [latex](n\geq 1)[/latex].
[latex]A[/latex] — квадратная матрица.

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

Суммы элементов матрицы [latex]A[/latex] по каждой из линий, параллельной главной диагонали.

Тесты

Входные данные Выходные данные
Размерность матрицы [latex](n)[/latex] Матрица [latex]A[/latex] Суммы
1 2 [latex]\begin{pmatrix}
3 & 6\\
-7 & -5
\end{pmatrix} [/latex]
-7  -2  6
2 3 [latex]\begin{pmatrix}
1 & 2 & 3\\
4 & 5 & 6\\
7 & 8 & 9
\end{pmatrix} [/latex]
7  12  15  8  3
3 4 [latex]\begin{pmatrix}
4 & 1 & -6 & 3\\
2 & 8 & 19 & 7\\
-8 & -11 & 3 & -13\\
0 & 2 & 16 & -9
\end{pmatrix} [/latex]
0  -6  7  6  7  1  3

Посмотреть работу программы на примере третьего теста можно на сайте ideone.

Решение

Описание решения

Сначала объявляем переменную n — размерность матрицы [latex]A[/latex] — и присваиваем ей значение, которое вводит пользователь. Если [latex](n\geq 1)[/latex] — продолжаем работу, иначе выводим сообщение об ошибке и завершаем работу программы.

Теперь, зная размерность матрицы, можем инициализировать 2 массива:

  1. Двумерный массив double[][] matrix = new double[n][n]; размерностью [latex](n\times n)[/latex], который будет содержать в себе значения элементов матрицы [latex]A[/latex];
  2. Массив double[] sum = new double [2*n - 1]; размерностью [latex](2*n-1)[/latex] для хранения сумм диагоналей. Такая размерность обусловлена следующей логикой: главная диагональ матрицы размерностью [latex](n\times n)[/latex] содержит [latex]n[/latex] элементов. Побочная диагональ, находящаяся выше, содержит в себе уже [latex](n-1)[/latex] элементов и т.д., пока элементов в диагонали больше нуля. Становится ясно, что выше главной диагонали находится [latex](n-1)[/latex] побочных диагоналей, еще столько же ниже. Прибавляем еще главную диагональ к этому числу и выводим формулу количества диагоналей у матрицы, параллельных главной: [latex]2(n-1)+1=2n-1[/latex].

Заполняем с помощью двух циклов for массив matrix из потока ввода, а затем в таких же циклах находим суммы элементов требуемых диагоналей ( sum[(j-i) + (n-1)] += matrix[i][j];).

Известно, что индексы [latex]i,j[/latex] элементов главной диагонали матрицы всегда одинаковы. Аналогично можно заметить, что на побочных диагоналях индекс [latex]j[/latex] отличается от индекса [latex]i[/latex] на число — «расстояние» между главной диагональю и рассматриваемой побочной. К примеру, если рассматривать побочную диагональ, находящуюся выше через одну от главной («расстояние» между ними равно 2), то в таком случае [latex]j-i=2[/latex].

И если на главной диагонали разность индексов будет равна 0, на диагоналях выше эта разность будет числом положительным, а на диагоналях ниже — отрицательным, то при попытке обращения к элементу массива sum[j-i] мы неизбежно столкнемся с ошибкой, так как индекс массива не может быть числом отрицательным. Значит, чтобы избежать этого, нам надо прибавить к этому индексу некую константу, чтобы самая нижняя диагональ [latex]n-1[/latex] обладала индексом 0 в массиве sum. Отсюда и формула [latex](j-i+n-1)[/latex].

A302. Количество различных цифр числа в его десятичной записи

Условие задачи

Дано натуральное число $latex N$. Сколько различных цифр встречается в его десятичной записи?

Тесты

Входные данные: натуральное число $latex N$

Выходные данные: количество различных цифр в десятичной записи числа $latex N$

Входные данные Выходные данные
1 1234567890 10
2 43352 4
3 10101 2
4 1 1

Код

Код доступен на ideone

Пояснение

Для хранения заданного числа $latex N$ будем использовать переменную  n  типа long, которая будет проинициализирована значением из стандартного потока ввода, а для хранения результата — переменную differentDigitsCount  типа int, которую проинициализируем числом 0. Переменные объявляются в начале программы. Для определения количества различных цифр будем использовать массив типа int из 10 элементов, где каждый элемент будет соответствовать количеству вхождений одной из цифр в заданное число . Элементы массива инициализируются числом 0 по умолчанию. В цикле поочередно определяется разряд — последний разряд числа, и соответствующий элемент массива инкрементируется, затем это число разделяется на 10, чтобы «отбросить» последний разряд. Результат работы программы — вывод значения переменной  differentDigitsCount, которое получается путем подсчета ненулевых элементов массива в цикле.

 

 

Ю 4.9

Задача

В матрице [latex]A(n, m) [/latex] все ненулевые элементы заменить обратными по величине и противоположными по знаку.

Тесты

      n        m  Входная матрица              Выходная матрица
     1                     3                         3           6   -2    -1                     0    0     4                    11   2    -3         -0.167     0.500      1.000                  0.000     0.000     -0.250                 -0.091    -0.500      0.333
     2                     3                         4       -3    -9    15   12        -31   -8     2     8           -1     2    -6    -8      0.333   0.111    -0.067   -0.083      0.032   0.125    -0.500   -0.125      1.000  -0.500     0.167    0.125
     3                    4                         3             1   1   1                       1   1   1                       1   1   1                       1   1   1            -1.000  -1.000   -1.000                    -1.000  -1.000   -1.000                    -1.000  -1.000   -1.000                    -1.000  -1.000   -1.000

Решение

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Объявляем и инициализируем переменные n  и m , которые являются размерами нашей матрицы [latex]A[/latex]. Объявляем нашу матрицу и создаем экземпляр с размерами [latex]n[/latex] x [latex]m[/latex]. Далее создаем цикл по i  от 0 до [latex]n-1[/latex] в котором создаем вложенный цикл по  j  от 0 до [latex]m-1[/latex], и в нем поэлементно вводим значения матрицы. В следующем цикле снова создаем вложенный, в котором мы проходим по каждому элементу матрицы и проверяем не равен ли он нулю  if(A[i][j] != 0) . Если условие выполняется, то мы заменяем элемент на обратный и меняем знак. В последнем цикле выводим полученную матрицу, элементы которой будут выводится с точностью до трех символов после запятой.