e-olymp 930. Номер мобильного телефона

Задача

Задан номер мобильного телефона. Определить, какие цифры отсутствуют в этом номере.

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

В единственной строке задан номер мобильного телефона.

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

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

Тесты

Входные данные Выходные данные
0631562976 2
4 8
2139087 3
4 5 6
1111111111 9
0 2 3 4 5 6 7 8 9
7 9
0 1 2 3 4 5 6 8 9
4848 8
0 1 2 3 5 6 7 9
0921234567 1
8
6723545 4
0 1 8 9
9867453210 0
+38 (037) 123-4-765 1
9

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

Решение

Объявим массив на $10$ элементов, в котором будем хранить количество вхождений каждой цифры в номер телефона. Далее, посимвольно читаем входной поток и увеличиваем соответствующие каждой цифре элементы массива на $1$. После этого, находим количество нулевых элементов массива — это будет количество цифр, которые отсутствуют в номере. Наконец, выводим индексы нулевых элементов массива.

Ссылки

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

e-olymp 1494. Санта Клаус

Задача

Santa Claus
Санта Клаус готовится к Рождеству. В этот праздник он хочет вручить подарки $n$ детям. Его помощники Эльфы уже собрали два мешка, с которыми он отправится в новогоднее путешествие по всем странам мира. И чтобы Санта не запутался, Эльфы составили список детей, чьи подарки уже лежат в каждом из мешков. Санта хочет помочь Эльфам, и поэтому решил положить в третий мешок подарки для тех детей, которым они еще не подготовлены.

Помогите Санте, составьте список детей, чьи подарки надо положить в третий мешок.

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

Первая строка входного файла содержит три целых числа: $n$ — число детей, $m$ и $k$ — число подарков в первом и втором мешке соответственно $(1\leq n,\;m,\;k\leq 100;m+k\leq n)$. Вторая строка входного файла содержит $m$ целых чисел — номера детей, подарки для которых лежат в первом мешке. Третья строка входного файла содержит $k$ целых чисел — номера детей, подарки для которых лежат во втором мешке.

Гарантируется что Эльфы положили для каждого ребенка не более одного подарка. Номера всех детей являются целыми положительными числами не превосходящими $n$. Все дети должны получить подарок на Рождество, иначе Санта расстроится.

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

В первой строке выведите одно число $a$ — сколько подарков должно быть в третьем мешке. Во второй строке выведите в произвольном порядке $a$ чисел — номера детей, которым эти подарки должны быть доставлены.

Тесты

Входные данные Выходные данные
2 1 1
2
1
0
3 1 2
1
2 3
0
7 2 1
7 3
1
4
2 4 5 6
100 14 4
2 93 30 56 17 19 75 22 23 5 49 11 8 33
91 40 81 54
82
1 3 4 6 7 9 10 12 13 14 15 16 18 20 21 24 25 26 27 28 29 31 32 34 35 36 37 38 39 41 42 43 44 45 46 47 48 50 51 52 53 55 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 76 77 78 79 80 82 83 84 85 86 87 88 89 90 92 94 95 96 97 98 99 100
10 3 5
2 5 8
3 7 1 4 9
2
6 10
61 40 5
61 20 5
3 4 9 8 49 31 20 33 35 34 61 1 32 53 51 7 21 44 46 47
2 60 50 19 25
36
5 6 10 11 12 13 14 15 16 17 18 22 23 24 26 27 28 29 30 36 37 38 39 40 41 42 43 45 48 52 54 55 56 57 58 59
12 3 3
1 2 3
11 10 8
6
4 5 6 7 9 12

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

Решение

Создадим массив типа boolean , в котором каждому $i$-ому ребёнку соответствует элемент с индексом $i-1$ , принимающий значение $0$, если для ребёнка ещё нет подарка, и $1$, если подарок уже имеется в одном из мешков. Далее, отмечаем детей, подарки для которых уже лежат в мешках. Наконец, выводим номера тех детей, подарки для которых не были найдены ни в одном из мешков.

Ссылки

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

e-olymp 7492. Будильник

Задача

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

Часы Алисы содержат четыре цифры: две для часов и две для минут. Например, часы ниже показывают [latex]9[/latex]:[latex]30[/latex] (ведущий ноль высвечивается).

Часы имеют следующее представление цифр:

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

Одно целое число [latex]n (0≤ n ≤30)[/latex] — количество подсвеченных сегментов на часах Алисы во сне.

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

Вывести пять символов в формате [latex]hh:mm[/latex] — время, показываемое часами Алисы во сне. Время должно быть корректным: [latex]0 ≤ hh < 24[/latex] and [latex]0 ≤ mm < 60[/latex]. Если существует несколько решений, то вывести любое. Если решения не существует, то вывести [latex]Impossible[/latex].

Тесты

Входные данные Выходные данные
23 00:02
28 Impossible
0 Impossible
15 01:12

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

Решение

Перебираем [latex]i[/latex] и [latex]j[/latex] (от [latex]0[/latex] до [latex]24[/latex] и [latex]60[/latex] соответственно). [latex]a=seg[i/10][/latex] (для десятков) и [latex]a=seg[i[/latex]%[latex]10][/latex] (для остальных чисел) то же самое делаем для [latex]j[/latex]. Тем самым, мы перебираем все возможные варианты количества сегментов. Если [latex]a==n[/latex] (количество сегментов) при переборе и в входных данных совпадает, то выводим наше время и выходим из цикла. Если же при переборе не было такого же числа сегментов, как в входных данных, то решения нет и мы, соответственно, выводим Impossible

Ссылки

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

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

A301. Количество точек в полукругах

Задача

Даны действительные числа [latex]x_1, y_1[/latex], [latex]x_2, y_2[/latex], [latex]\ldots[/latex], [latex]x_{20}, y_{20}[/latex], [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex], [latex]\left( 0 < r_1 < r_2 < \ldots < r_{11} \right)[/latex]. Пары [latex]\left( x_1, y_1 \right)[/latex], [latex]\left( x_2, y_2 \right)[/latex], [latex]\ldots[/latex] [latex]\left( x_{20}, y_{20} \right)[/latex] рассматриваются как координаты точек плоскости. Числа [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex] рассматриваются как радиусы одиннадцати полукругов в полуплоскости [latex]y > 0[/latex] с центром в начале координат. Найти количество точек, попадающих внутрь каждого полукруга (границы-полуокружности не принадлежат полукругам).

Примечание: будем рассматривать задачу с произвольным количеством точек [latex]n[/latex] и полуокружностей [latex]m[/latex].

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

[latex]n[/latex], [latex]m[/latex], [latex]x_i, y_i[/latex], [latex]i = \overline{1, n}[/latex], [latex]r_j[/latex], [latex]j = \overline{1, m}[/latex]

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

[latex]a_j[/latex] — количество точек в [latex]j[/latex]-том полукруге, [latex]j = \overline{1, m}[/latex].

Тест

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

14 4
5 -4
4 90
2 4.91
8 9.0
8.3 4.111
20 49.0
0 301.419
8.01 34.5
2.1 -49.1
0.01 0.03
56 1.91
4.04918 34.49294
-1.85892 5.01674
51 214
14.94 44.09
41.4 -154
-581.49 495
14.39 -81.682
77 194.4
0.3
20.82
50.9
51
65.845
90.37
109.58
170.83
217
301.58901
314

1
6
9
9
11
12
12
12
13
15
15

Иллюстрация к тесту:

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

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

Из входного потока считываем координаты всех точек, и отсеиваем из них те, у которых координата [latex]y \le 0[/latex], так как они по условию не могут принадлежать данным полуокружностям, остальные же добавляем в вектор точек dots. После этого, создаём два массива: первый rads — массив радиусов — считываем из входного потока, второй amounts — обнуляем. В i-ой ячейке массива amounts будем хранить количество точек, которые принадлежат [latex]i[/latex]-тому, и большим чем он полукругам. После этого, используя алгоритм бинарного поиска, находим наименьший полукруг, который содержит точку, и запоминаем его номер. Затем количество точек, содержащихся в данном и больших, чем данный полукругах, увеличиваем на единицу.

После обработки вектора точек, массив amounts преобразуем в массив количеств точек, содержащихся в конкретных полукругах, так как до этой обработки он содержит количество точек, которые «аккумулированы» i-тым, и большими чем i-тый полукруги.

Таким образом, общая асимптотика программы составит [latex]O \left(m+n \cdot \log_{2}{m}\right)[/latex], где [latex]n[/latex] — количество точек, а [latex]m[/latex] — полукругов.

Ссылки

Ю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].

А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] имеет наименьшее значение.

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

[latex]n[/latex] — количество бегунов [latex](n\geq 4)[/latex].
[latex]a_{1}, a_{2},\ldots, a_{n}[/latex] — результаты спортсменов в беге на [latex]100[/latex] м.

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

[latex]i, j, k, l[/latex] — номера спортсменов, избранных для команды [latex](1\leq i\leq j\leq k\leq l\leq n)[/latex]

Тесты

Входные данные Выходные данные
Количество спортсменов [latex](n)[/latex] Результаты бега спортсменов Номера спортсменов, избранных для команды
1 3 2.1  3.7  1.1 [latex]n[/latex] не должно быть меньше 4
2 4 1.4  2.1  0  0.2 Результаты должны быть больше 0
3 6 6.5  4.1  1.2  8  9.1  4.9 1  2  3  6
4 12 2.5  9  14  7.1  1.3  4.9  6.7  1.9  10.01  2.45  0.01  13 5  8  10  11

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

Решение

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

Отличительной особенностью задач из категории «потоковая обработка» является то, что обработка большого объема данных происходит циклически, без их запоминания. То есть, когда пользователь вводит в программу массив значений, программа запоминает очередное значение, обрабатывает его соответствующим образом, а потом заменяет новым поступившим значением. Это дает преимущество в использовании памяти перед программами, которые запоминают весь массив целиком.

Так как по условию размер отбираемой команды — [latex]4[/latex] бегуна ( final int teamSize = 4;), введем ограничение на количество бегунов в целом — их должно быть [latex]4[/latex] или больше, иначе программа выдаст сообщение об ошибке и завершит работу.

Введя количество бегунов n, пользователь после этого будет вводить результат каждого. Программа запоминает этот результат ровно на один шаг цикла ( double a = in.nextDouble();), за который разберется, что с ним делать, а затем заменит следующим результатом.

Так как программа не запоминает весь массив целиком, найти [latex]4[/latex] наименьших значения перебором не получится. Поэтому инициализируем [latex]2[/latex] массива, один из которых ( double[] resRun = new double[teamSize];) будет хранить результаты бегунов, отобранных в команду, а другой ( int[] nRun = new int[teamSize];) — их номера.

Результаты бегунов, отобранных в команду изначально равны нулю; это говорит о том, что еще ни один бегун в команду отобран не был. Результаты и номера первых [latex]4[/latex] бегунов мы запомним в этих массивах, так как иначе мы просто потеряем эти данные и больше не сможем сравнить их со следующими. Теперь, когда 4 бегуна отобраны, следует найти номер бегуна с наихудшим результатом (с помощью функции public static int FindMax(double[] resRun, int[] nRun)). Этот бегун — первый в очереди на замену, если очередной полученный результат вдруг окажется лучшим (меньшим). Следует отметить, что программа будет искать номер наихудшего бегуна лишь в тех случаях, когда этот бегун будет заменен; в ином случае, когда результат очередного бегуна хуже, мы замены в команде не производим, соответственно, худший бегун в команде остается тем же.

Таким образом, с каждым шагом цикла результаты отобранных в команду бегунов становятся либо меньше, либо остаются прежними. После обработки последнего введенного результата, мы получим массив resRun лучших результатов и массив nRun номеров этих бегунов. Остается лишь отсортировать номера бегунов ( Arrays.sort(nRun);), как того требует условие, и вывести их значения.