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

Задача

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

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

Натуральное число [latex]N[/latex].

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

Количество различных цифр [latex]sum[/latex].

Тесты

Входные данные Выходные данные
[latex]N[/latex] [latex]sum[/latex]
12345678900987654321 sum:10
302 sum:3

Код программы с использованием deque

 

Решение

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

Код программы с использованием массива

Решение

Создадим массив [latex]folder[/latex] в котором будем хранить кол-во встреч для различных цифр десятичной записи в соответствующих позициях массива. Увеличиваем на один значения соответствующей позиции массива и делим [latex]N[/latex] на [latex]10[/latex]. Для определения [latex]sum[/latex] делаем цикл и проверяем ненулевые значения массива [latex]folder[/latex].

Ссылки

Ideone через deque;
Ideone через массив;
Условие задачи (стр. 126).

Related Images:

Душевая кабина

Разбор задачи F с 1/8 ACM ICPC по украинскому региону 25 марта 2017.

Задача

Степан приобрел душевую кабину, которую решил установить в дачном домике. Дачный домик представляет собой прямоугольник [latex]N \times M[/latex], разбитый на одинарные квадратики. Степан знает, что душевая кабина занимает ровно две клетки с общей стороной. Также Степану известно, что некоторые клетки дома заняты разными вещами. Помогите Степану узнать сколькими способами он может разместить душевую кабину в дачном домике.

 

Ввод

В первом ряду входных данных находятся два целых числа  [latex] N,M(1<=N,M<=1000)[/latex] — размеры дачного домика Степана. Каждый из следующих [latex] N[/latex] рядов содержит по  [latex] M[/latex] символов — описание дачного домика Степана. Символ «#» означает, что соответствующая клетка уже чем-то занята, а символ «.» — что она свободна и может стать одной из двух, занятых душевой кабиной.

Вывод

Одно число — количество способов расположить душевую кабину в дачном домике.

Тесты

Код

Решение

Считываем символы в массив . Размер такого массива всегда будет [latex]n \times m[/latex]. Зная это, заводим цикл, в котором проверяем наличие точки(‘.’). Затем проверяем первое условие: если следующий символ тоже точка и если мы не перешли на новую строку, увеличиваем счетчик. Зная количество символов в каждой строке, проверяем символ «под» точкой и если они совпадают опять же увеличиваем счетчик.

Related Images:

А290

Задача. Даны действительные числа [latex]x_{1},\ldots,x_{n}[/latex], [latex]y_{1},\ldots,y_{n}[/latex]. Получить [latex]x’_{1},\ldots,x’_{n}[/latex],[latex]y’_{1},\ldots,y’_{n}[/latex], преобразовав для получения [latex]x’_{i},y’_{i}[/latex] члены [latex]x_{i},y_{i}[/latex] по правилу: если они оба отрицательны, то каждый из них увеличить на 0.5; если отрицательно только одно число, то отрицательное число заменить его квадратом; если оба числа неотрицательны, то каждое из них заменить на среднее арифметическое исходных значений.

Тесты

n [latex]x_{1},\ldots,x_{n}[/latex] [latex]y_{1},\ldots,y_{n}[/latex] [latex]x’_{1},\ldots,x’_{n}[/latex][latex]y’_{1},\ldots,y’_{n}[/latex] Комментарий
4 1 4 -3 8

3 -2 -4 2

2 4 -2.5 5

2 4 -3.5 5

Пройдено
5 0 -0.5 4 -9 0.35

0 -0.5 11 0.247 1.650

0 0 7.5 81 1

0 0 7.5 0.247 1

Пройдено
3 0 3 -0.14942

-3 0 793

0 1.5 0.0223263

9 1.5 793

Пройдено

Реализация (массив структур)

Алгоритм решения (массив структур)
Для выполнения данной задачи, воспользуемся массивом структур. Каждый [latex]i[/latex]-ый элемент такого массива заполняем двумя действительными числами [latex]x_{i}[/latex] и [latex]y_{i}[/latex]. После этого мы выполняем проверку и преобразование этих чисел по заданным в условии правилам. Затем их выводим.

Реализация (класс vector)

Алгоритм решения (класс vector)
Данный способ реализации помогает решить задачу преобразования чисел [latex]x_{1},\ldots,x_{n}[/latex], [latex]y_{1},\ldots, y_{n}[/latex] для неизвестного значения [latex]n[/latex] — количества элементов [latex]x_{i}[/latex] и [latex]y_{i}[/latex]. Их количество будет зависить от количества введенных элементов. Программа считывает элементы [latex]x_{i}[/latex] и [latex]y_{i}[/latex] поочередно, т.е. [latex]x_{1}\rightarrow y_{1}\rightarrow x_{2} \rightarrow y_{2} \rightarrow\ldots\rightarrow x_{n}\rightarrow y_{n}[/latex]. В остальном алгоритм такой же как с массивом структур.

Ссылка на код (массив структур)
Ссылка на код (класс vector)

Related Images:

e-olymp 2955. Персистентый массив

Условие

Задача взята отсюда.

Дан массив (вернее, первая, начальная его версия). Нужно уметь отвечать на два запроса:

  • [latex]a_i[j] = x[/latex] — создать из [latex]i[/latex]-ой версии новую, в которой [latex]j[/latex]-ый элемент равен [latex]x[/latex], а остальные элементы такие же, как в [latex]i[/latex]-ой версии.
  • [latex]get[/latex] [latex]a_i[j][/latex] — сказать, чему равен [latex]j[/latex]-ый элемент в [latex]i[/latex]-ой версии.

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

Количество чисел в массиве [latex]n[/latex] [latex](1 \leq n \leq 10^5)[/latex] и [latex]n[/latex] элементов массива. Далее количество запросов [latex]m[/latex] [latex](1 \leq m \leq 10^5)[/latex] и [latex]m[/latex] запросов. Формат описания запросов можно посмотреть в примере. Если уже существует [latex]k[/latex] версий, новая версия получает номер [latex]k + 1[/latex]. И исходные, и новые элементы массива — целые числа от [latex]0[/latex] до [latex]10^9[/latex]. Элементы в массиве нумеруются числами от [latex]1[/latex] до [latex]n[/latex].

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

На каждый запрос типа [latex]get[/latex] вывести соответствующий элемент нужного массива.

Тесты

Входные данные выходные данные
1 6
1 2 3 4 5 6
11
create 1 6 10
create 2 5 8
create 1 5 30
get 1 6
get 1 5
get 2 6
get 2 5
get 3 6
get 3 5
get 4 6
get 4 5
6
5
10
5
10
8
6
30
2 2
42 2048
17
create 1 1 1
create 2 2 1
create 3 2 5
create 3 1 4
create 5 2 6
get 1 1
get 1 2
get 2 1
get 2 2
get 3 1
get 3 2
get 4 1
get 4 2
get 5 1
get 5 2
get 6 1
get 6 2
42
2048
1
2048
1
1
1
5
4
1
4
6

Код

Решение

Для решения задачи воспользуемся так называемым Персистентным Деревом Отрезков — т.е. деревом, «помнящим» историю своих изменений. Дерево будем хранить не с помощью массива а на указателях — используя структуру типа «узел».

(Тут [latex]lchild[/latex] и [latex]rchild[/latex] — ссылки на левый и правый поддеревья соответственно, а [latex]val[/latex] — значение, хранящееся в узле.)

Замечание: тут и далее под левым подотрезком отрезка [latex][l, l + 1, \ldots, m, m + 1, \ldots, r — 1, r][/latex], [latex]m = \lfloor\frac{l + r}{2}\rfloor[/latex] подразумевается отрезок [latex][l, \ldots, m][/latex] а под правым — [latex][m + 1, \ldots, r][/latex].

Заведем вектор-хранилище корней дерева [latex]versions[/latex] (об этом позднее). Для начала занесем туда 1 элемент — корень изначального дерева, и построим на нем дерево из элементов массива. Вопрос в том, какую информацию хранить в вершинах дерева? Оказывается, достаточно хранить в листьях элементы массива, а остальные узлы заполнять ни чем не надо — исходя из условия, запросы будут только к конкретным элементам массива. Рекурсивная процедура построения дерева стандартна, отличается только технической реализацией (вместо номеров вершин передаем ссылки на необходимые нам узлы) — рекурсивно создаем у текущего узла [latex]lchild[/latex] и [latex]rchild[/latex] и вызываем функцию построения для них, пока длина отрезка, за который они отвечают, не станет равна единице. Тогда присваиваем полю [latex]val[/latex] этого узла значение соотв. элемента массива.

Например, для массива {[latex]1, 2, 3, 4, 5, 6[/latex]} в результате построения мы получим следующую структуру (где на самом деле значения хранятся только на отрезках длины [latex]1[/latex], для остальных узлов подотрезки массива, отвечающие им, только подразумеваются).
graph1
Теперь разберемся, как эффективно создавать новые версии массива. Пусть у нас уже есть [latex]k[/latex] версий массива и мы хотим создать из [latex]i[/latex]-й [latex](k+1)[/latex]-ю. Для начала добавим в хранилище новый узел-корень, отвечающий данной версии.

Теперь рассуждаем так: допустим, элемент, который надо поменять, находиться в правом подотрезке (для левого, рассуждения будут симметричны). Левые подотрезки идентичны, тогда просто присваиваем [latex]lchild[/latex] нового узла ссылку на [latex]lchild[/latex] исходного. Правые будут отличаться. Тогда создаем у нового узла [latex]rchild[/latex], и проводим те же размышления относительного правого подотрезка, [latex]rchild[/latex]-ов исходного и нового узлов, повторяя это до тех пор, пока мы не придем в лист дерева, тогда просто присвоим этому новому узлу требуемое значение. Получаем несложный рекурсивный алгоритм функции void add(Node* to, Node* from, int l, int r, int npos, int nv);

Для наглядности, рассмотрим пример с тем же массивом. Пусть сперва нас просят выполнить create 1 6 42 — создать из первой версии новую, где шестой элемент равен [latex]42[/latex], а затем create 2 4 667 — создать новую уже из второй, где [latex]4[/latex]-й элемент равен [latex]667[/latex]. Вот, что мы получим в результате (черный цвет — первая версия, красный — вторая, синий — третья):

graph2

Рассмотрим, как получилась вторая версия. Создаем корень {[latex]1, 2, 3, 4, 5, 42[/latex]}. Необходимый нам элемент в правом подотрезке. Тогда [latex]lchild[/latex] нового корня будет ссылаться на [latex]lchild[/latex] исходного, а [latex]rchild[/latex] {[latex]4, 5, 42[/latex]}. Мы создаем. Аналогично поступаем с {[latex]4, 5, 42[/latex]} относительно {[latex]4, 5, 6[/latex]}. Левое поддерево {[latex]4, 5[/latex]} — общее, создаем правое поддерево {[latex]42[/latex]} и завершаем алгоритм. Для получения третьей версии можно провести аналогичные рассуждения, но уже беря в качестве исходного дерева вторую версию.

Так как на каждом этапе отрезок делится пополам, то очевидно, что как и в стандартной реализации ДО, асимптотика этой функции будет [latex]O(\log{n})[/latex], а при создании новой версии будет создано не более чем [latex]\lceil\log_2{n}\rceil[/latex] вершин, т.е. алгоритм является достаточно эффективным как в плане времени, так и расходуемой памяти.

Осталось реализовать функцию int get(Node* node, int l, int r, int pos); Она реализуется стандартно: спускаемся по необходимой версии дерева (из нужного узла-корня в [latex]storage[/latex]), в левое или правое поддерево, пока не дойдем до необходимой нам вершины (это будет отрезок единичной длины), далее возвращаем содержимое [latex]val[/latex] этого узла. Реализация облегчается еще и тем, что запрашивают элемент — т.е. отрезок единичной длины, и не надо рассматривать случай, когда необходимый отрезок лежит частично в левом, а частично в правом поддереве.

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

Ссылки

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

Рабочий код на Ideone.

Замечание

Легко заметить, что в функции int get(Node* node, int l, int r, int pos); можно очень просто избавиться от рекурсии:

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

Related Images:

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

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

 

Решение

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

Related Images:

A701a

Задача

Даны квадратная матрица [latex]A[/latex] порядка [latex]n[/latex] и вектор [latex]b[/latex] с [latex]n[/latex] элементами. Получить вектор:
a) [latex]Ab[/latex];

Размерность
матрицы
Матрица Вектор Результирующий
вектор
2
1 2
3 4
1
2
5
11
3
3 2 6
3 2 1
5 3 8
4
5
7
64
29
91
4
1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6
1
2
3
4
30
70
20
50
 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
5
6
7
8
9
115
290
465
640
815

Алгоритм действия достаточно прост:
Вводим размерность матрицы. Потом в цикле вводим саму матрицу. Вводим вектор. Далее идет сам алгоритм матрично-векторного произведения.

Последовательный алгоритм умножения матрицы на вектор может быть представлен следующим образом. Исходные данные: [latex]A[n][m][/latex] – матрицы размерности [latex]n[/latex]× [latex]m[/latex] . [latex]B[m][/latex] – вектор, состоящий из [latex]m[/latex] элементов. Результат: [latex]rezult[n][/latex] – вектор из [latex]n[/latex] элементов.

 

Матрично-векторное умножение – это последовательность вычисления скалярных произведений. Поскольку каждое вычисление скалярного произведения векторов длины [latex]m[/latex] требует выполнения [latex]m[/latex] операций умножения и [latex]m-1[/latex] операций сложения, его трудоемкость порядка [latex]O(m)[/latex]. Для выполнения матрично-векторного умножения необходимо выполнить [latex]n[/latex] операций вычисления скалярного произведения, таким образом, алгоритм имеет трудоемкость порядка [latex]O(nm)[/latex].

Ниже представлен сам код (C++).

Код на Java:

 

Также, Вы можете воспользоваться ссылкой (C++)/ссылкой (Java) на саму программу.

 

Related Images:

Ю4.21

Задача.

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

Тесты.

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

 

 

 

Решение.

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

Related Images:

A403a

Задача

Дана целочисленная квадратная матрица порядка [latex]15[/latex]. Выяснить, имеются ли в матрице ненулевые элементы, и если имеются, указать индекс одного из ненулевых элементов.

Тест

i, j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Результат
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 Index: 0 3
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 9 0 0 0 0 0 0 8 0 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7
12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
14 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

i,j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Результат
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0    Ненулевых элементов нет
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Код на языке С++ :

 

Ссылка на программу: http://ideone.com/72Gn1G

Решение:

Задача довольно простая.Вводим квадратную матрицу [latex]z(n,n)[/latex] порядка 15. Далее в цикле описываем условие, что если:

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

Код на языке Java:

 

Ссылка на программу:http://ideone.com/SiTKYZ

Related Images:

Ю4.1

Задача. Разделение по знаку. В массиве С(n) подсчитать количество отрицательных и сумму положительных элементов.

Тесты:

n Входной массив Кол-во отрицательных элементов Сумма положительных элементов Комментарий
5 1.01 3 7.11 -1 -0.99 2 11.12 Пройден
14 1 2 -4.2 3.5 6.2 8 11 -144 288 9.2 -22 12 -13.5 14 4 354.9 Пройден

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

 

В ходе решении данной задачи я использую цикл for, в котором сначала считываются, а затем обрабатываются данные. Переменная-счётчик [latex]k[/latex]  нужна для того, чтобы узнать кол-во отрицательных элементов. А если встречаются неотрицательные элементы, то подсчитывается их сумма в переменной [latex]S[/latex]. Для проверки выполнения программы можно воспользоваться ссылкой.

Решение на Java:

Ссылка на решение.

Related Images:

А156а

Задача. Даны натуральное число [latex]n[/latex], действительные числа [latex]x_{1}, \cdot x_{n},(n\geq 3)[/latex]. Вычислить:

[latex](x_{1}+2x_{2}+x_{3})(x_{2}+2x_{3}+x_{4}) \cdot (x_{n-2}+2x_{n-1}+x_{n})[/latex].

Тесты:

Ввод Вывод Комментарий
6 1 1 1 1 1 1 256 Пройден
9 1 2 0 1 2 0 1 2 0 18000 Пройден
5 5 5 5 5 5 8000 Пройден

Код на С++

Код на Java

 

Решение:

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

С работой программы на С++ можно ознакомиться здесь, а на Java здесь.

Related Images:

А170

Задача. Даны натуральные числа [latex]n, a_{1}, a_{2},\ldots, a_{n} (n\geq 4)[/latex]. Числа [latex]a_{1}, a_{2},\ldots , a_{n}[/latex] — это измеренные в сотых долях секунды результаты [latex]n[/latex] спортсменов в беге на [latex]100[/latex] м. Составить команду из четырёх лучших бегунов для участия в эстафете [latex]4\times100[/latex], т.е. указать одну из четверок натуральных чисел [latex]i, j, k, l[/latex], для которой [latex]1\leq i\leq j\leq k\leq l\leq n[/latex] и [latex]a_{i} + a_{j}+a_{k} + a_{l}[/latex] имеет наименьшее значение.

Тесты

      n         c Результаты бега спортсменов Номера спортсменов, избранных для команды Комментарий
6 3 11.77 12.34 12.14 11.15 11.16 11.40 4 5 6 Пройден
6 4 11.68 0 12.15 11.54 11.26 11.00 Введен отрицательный или нулевой результат Не пройден
6 2 11.68 -12.34 12.14 11.55 11.29 11.00 Введен отрицательный или нулевой результат Не пройден

 

Код программы на C++:

В этой задаче необходимо было найти номера лучших бегунов, для создания из них команды. Размер команды вводим сразу же после общего количества бегунов с клавиатуры. Для нахождения номеров бегунов нам потребуется функция mini, которая находит минимальный элемент массива и возвращает его значение, а также  функция team, вызывающая функцию mini. В функции team уже создан массив номеров бегунов, в который мы вначале  введем данные и отсортируем его по возрастанию. Также будем выводить номер этого минимального элемента на экран, прибавляя 1 (как бы считая бегунов с 1, а не с 0),  и присваивать этому (найденному) элементу массива какое-то большое значение для того, чтобы при следующей проверке программа не считала его минимальным элементом, а находила следующий минимальный.

В строках

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

В конечном итоге, применяем функцию team и получаем, собственно, ответ.

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

 

Related Images: