Ю4.8

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

В массиве [latex]C(m)[/latex] заменить каждый третий элемент полусуммой двух предыдущих, а стоящий перед ним — полусуммой соседних с ним элементов.

Алгоритм решения

1.Инициализируем переменную [latex]n[/latex], которая будет размером массива и сам массив [latex]a[/latex];
2.С помощью ввода задаем длину массива;
3.С помощью цикла и ввода заполняем массив;
3.Меняем каждый третий элемент начиная со второго;
4.Находим полусумму двух предыдущих элементов;
5.Берем число стоящее перед числом кратным трем;
6.Заменяем его на полусумму стоящих рядом элементов.

Тесты

Кол-во элементов Элементы Результат
3 5 9 1 5 3 7
6 8 7 6 9 4 0 8 7 7,5 9 4,5 6,5
9 2 5 7 3 6 9 4 6 2 4,5 3,5 3 6 4,5 4 5,5 5

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

Код на ideone.com.

Задача оригинал на языке С++(другого автора) на java.mazurok.com.

e-olymp 2666. Половина

Задача

Напишите программу, заполняющую массив [latex]n × n[/latex] следующим образом: на побочной диагонали стоят нули, выше диагонали двойки, ниже единицы.

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

Дано натуральное число [latex]n[/latex] [latex](n \leqslant 20).[/latex]

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

Выведите массив, заполненный по указанному правилу.

Тесты

# Входные данные Выходные данные
1 2 20
01
2 3 220
201
011
3 4 2220
2201
2011
0111
4 5 22220
22201
22011
20111
01111
5 10 2222222220
2222222201
2222222011
2222220111
2222201111
2222011111
2220111111
2201111111
2011111111
0111111111

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

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

Для решения задачи создадим двумерный массив, количество строк и столбцов которого не превышают [latex]20.[/latex] Заполнять его будем при помощи двойного цикла, как указано в решении задачи. Введем следующие обозначения:

  • [latex]i + j = n — 1,[/latex] если ячейка [latex](i,j)[/latex] лежит на побочной диагонали;
  • [latex]i + j > n — 1,[/latex] если ячейка [latex](i,j)[/latex] лежит ниже побочной диагонали;
  • [latex]i + j < n — 1,[/latex] если ячейка [latex](i,j)[/latex] лежит выше побочной диагонали.

Далее заполняем массив в соответствии с введеными обозначениями и условием задачи, а затем выводим его на экран. Задача решена.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 7809. Утренняя зарядка

Задача


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

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

Единственная строка входного файла содержит последовательность чисел, записанных через пробел, означающие цвет футболки. Цвет — число в диапазоне от [latex]0[/latex] до [latex]9.[/latex] Всего в строке не более, чем [latex]10^6[/latex] чисел.

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

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

Тесты

# Входные данные Выходные данные
1 0 3 6 3 0 0 1 2
2 8 8 9 9 7 6 7 8 4 3
3 5 6 7 3 2 0
4 2 7 6 8 9 2 1 1
5 8 7 7 5 4 3 5 4 8 4

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

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

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

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 907. Первый не больший чем 2.5

Задача

Задан массив вещественных чисел. Найти первый элемент массива, значение которого не превышает 2.5.

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

В первой строке задано количество элементов массива $n\left ( 0 < n \leq 100 \right )$. В следующей строке задано $n$ вещественных чисел.

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

Вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. В случае отсутствия такого элемента в массиве вывести «Not Found» (без кавычек).

Тесты

Входные данные Выходные данные
$5 \\ 6 \ 7.5\ 2.1 \ 2.0 \ 0$ $3 \ 2.10$
$5 \\ 6 \ 7.5 \ 5.1 \ 7.0 \ 80$ $Not \ Found$
$7 \\ 5 \ 4.7 \ 50 \ 8.9 \ 2.7 \ 3 \ 1.5$ $7 \ 1.5$

Решение задачи с помощью потоковой обработки

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

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

Будем просматривать все веденные элементы и для каждого осуществлять проверку, если элемент не превышает 2.5, тогда в ответе выводим в одной строке сначала индекс найденного первого указанного элемента и его значение с 2 десятичными знаками. Если же такого элемента нет, выводим на экран $Not \ Found.$

Решение задачи с помощью массивов

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

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

Введем обозначения: $x$ – имя массива, $n$ – количество элементов в массиве, $i$ – индекс элемента массива. Нам необходимо просмотреть весь массив. Если значение просматриваемого элемента не превышает 2,5, то в ответе вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. Если же такого элемента в массиве нет, вывести $Not \ Found.$

Ссылки

Условие задачи на e-olymp

Код решения с помощью потоковой обработки на ideone

Код решения с помощью массивов на ideone

e-olymp 1560. Уменьшающееся число

Задание

Над целым числом можно производить следующие операции:

  1. Если число делится на 3, то делить его на 3;
  2. Если число делится на 2, то делить его на 2;
  3. Вычитать 1.

По заданному натуральному числу [latex]n[/latex] найти наименьшее количество операций, после выполнения которых получится 1.

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

Каждая строка содержит одно натуральное число [latex] n(1 ≤ n ≤ 10^{6})[/latex].

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

Для каждого значения [latex]n[/latex] в отдельной строке вывести наименьшее количество операций, после выполнения которых получится 1.

Тесты

Ввод Вывод
1
5
10
0
3
3
12
7
21
3
3
4
256
1037
8771
9022
102651
8
11
13
13
19

Код

Решение

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

Ссылки

1.Код на Ideone
2.Условие на e-olymp

Шифровка

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

Взята с сайта.
Мюллер много раз пытался поймать Штирлица с поличным, но тот всё время выкручивался. Как-то раз Штирлиц просматривал электронную почту. В это время незаметно вошел Мюллер и увидел, как у него на экране появился бессмысленный набор символов. «Шифровка», — подумал Мюллер. «UTF-8», — подумал Штирлиц.
Известно, что Штирлиц шифрует текст следующим образом:

1)Убирает все пробелы и знаки препинания.
2)Заменяет все подряд идущие одинаковые буквы на одну такую букву.
3)Многократно вставляет в произвольное место текста две одинаковых буквы.

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

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

aaxxHuuuuelllnnloxxvvoo!

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

Hello!

Решение с использованием функционала класса String

Решение с использованием функционала структуры данных ArrayList

Решение

Записываем строку в переменную типа $latex String$. Записываем ее в $latex ArrayList$ посимвольно. В следующем цикле добавляем проверку на индекс текущего элемента чтобы не выйти за пределы списка и проверяем совпадают ли ближайшие 2 символа, если да то удаляем их, если нет то переходим к следующему шагу цикла. По его окончанию выводим элементы списка.
Пример решения со строками на ideone.
Пример решения с списком на 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[ ].

 

 

A410e

Дана целочисленная матрица [latex]\begin{bmatrix}a_{i,j}\end{bmatrix},i,j=1,..,n[/latex].Получить [latex]b_{1},..,b_{n}[/latex],где [latex]b_{i}[/latex] — это:

[latex]\underset{1\leq j\leq n}{\max a_{ij}}\ * \underset{1\leq j\leq n}{\min a_{ji}}[/latex]

Исходя из задачи ясно, что из данной матрицы надо взять максимальный элемент [latex]i[/latex]-й строки и умножить его на минимальный элемент [latex]i[/latex] -го столбца. Так например, если нам дана матрица 2-го порядка [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] то [latex]b_{1} = 2[/latex], [latex]b_{2} = 4[/latex].

 

Тесты

Матрица порядка [latex]n[/latex], где [latex]n[/latex]: [latex]a[i][j][/latex] Результат
2 [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] 2 4
3 [latex]\begin{Vmatrix}1&2&3\\4&1&-6\\1&-2&-1\end{Vmatrix}[/latex] 3 -8 -6

Решение

Для нахождения максимума  [latex]a_{ij}[/latex], введем переменную и будем придавать ей начальное значение 1-го элемента [latex]i[/latex]-й строки. Дабы при расчете максимума проходя по элементам строки мы не сравнивали каждый [latex]i[/latex]-й элемент с 1-м, придавать начальное значение максимуму мы будем в цикле по [latex]i[/latex]. Аналогично с минимумом [latex]a_{ij}[/latex], одно единственное но, начальное значение минимума будет равно первому элементу [latex]i[/latex]-го столбца.

http://ideone.com

e-olymp 2166: Анаграммы

Задача

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

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

Два слова заданы в отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.

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

Следует вывести «YES«, если введенные слова являются анаграммами друг друга и «NO» если нет.

Решение

В задаче требуется определить являются ли два введенных слова анаграммами.
Основная проблема состоит в том, что буквы находятся в словах на различных позициях и это мешает нам просто сравнить строки. Поэтому упорядочим символы в строке по алфавиту с помощью метода Arrays.sort, который вызываем в функции sortString, которая вернет нам новую отсортированную строку.
Теперь мы можем выполнить сравнение строк с помощью функции equals(), которая вернет нам true только в том случае, если строки идентичны. В таком случае и выводим «YES», а в противном случае «NO».

Код

На Ideone.

Тест

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

marsh

YES
ananas

nnaass

NO
tommarvoloriddle
iamlordvoldemort
YES

Ссылка на задачу на e-olimp и на ее решение.

e-olymp 138. Банкомат

Задача. В банкомате имеются в достаточном количестве купюры номиналом [latex]10, 20, 50, 100, 200[/latex] и [latex]500[/latex] гривен. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в [latex]n[/latex] гривен[latex](0 \leq n \leq 100000)[/latex], или вывести [latex]-1[/latex], если указанную сумму выдать нельзя.

Тесты

Сумма 130 999 7360 3 80 123450 567 440
Число купюр 3 -1 18 -1 3 249 -1 4

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

Алгоритм

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

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

Следует учесть, что сумма может быть и такой, что банкомат не сможет ее выдать. Это будет происходить тогда, когда сумма содержит некоторую часть, меньшую самой меньшей купюры. Чтобы выяснить, так ли это, мы смотрим, что осталось от суммы после применения «жадного»алгоритма. Если остаток равен [latex]0[/latex], то исходную сумму можно получить с помощью имеющихся купюр, и на экран выводится результат, полученный в цикле. Если же остаток больше [latex]0[/latex], такую операцию осуществить невозможно и программа выводит [latex]-1[/latex].

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

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