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).

e-olymp 6128. Простой дек

Задача

Реализуйте структуру данных «дек». Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

  • push_front Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.
  • push_back Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.
  • pop_front Извлечь из дека первый элемент. Программа должна вывести его значение.
  • pop_back Извлечь из дека последний элемент. Программа должна вывести его значение.
  • front Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.
  • back Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.
  • size Вывести количество элементов в деке.
  • clear Очистить дек (удалить из него все элементы) и вывести ok.
  • exit Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит [latex]100[/latex]. Все операции:

pop_front,
pop_back,
front,
back
всегда корректны.

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример входных данных.

Тесты

Входные данные Выходные данные
push_back 3
push_front 14
size
clear
push_front 1
back
push_back 2
front
pop_back
size
pop_front
size
exit
ok
ok
2
ok
ok
1
ok
1
2
1
1
0
bye

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

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

Решение

Создадим массив [latex]folder[/latex] и целочисленные переменные [latex]start[/latex] и [latex]end[/latex] в качестве указателей на начало и конец нашего дека.

  • push_front  — сдвигаем указатель [latex]start[/latex] на [latex]1[/latex] назад, кладем значение в наш дек и выводим ok;
  • push_back  — кладем значение в наш дек, сдвигаем указатель [latex]end[/latex] на [latex]1[/latex] вперед и выводим ok;
  • pop_front  — выводим значение начала дека и перемещаем [latex]start[/latex] вперед на [latex]1[/latex];
  • pop_back  — перемещаем [latex]end[/latex] назад на [latex]1[/latex] и выводим значение конца дека;
  • front  — выводим значение начала дека;
  • back  — выводим значение перед [latex]end[/latex];
  • size  — отнимем от переменной [latex]end[/latex] переменную [latex]start[/latex];
  • clear  — приводим [latex]start[/latex] и [latex]end[/latex] к изначальным позициям;
  • exit  — выводим «bye» и заканчиваем программу.

Ссылки

Ideone C++
Ideone Java
решение e-olymp C++
решение e-olymp Java

KM194. Взаимно простые числа

Задача

Даны два взаимно простых натуральных числа [latex]a[/latex] и [latex]b[/latex]. Рассмотрим множество [latex]M[/latex] целых чисел, представимых в виде [latex][ax+by],[/latex] где [latex]x[/latex] и [latex]y[/latex] — целые неотрицательные числа. Каково наибольшее целое число [latex]c[/latex], не принадлежащее множеству [latex]M[/latex]?

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

[latex]a[/latex] и [latex]b[/latex] — два взаимно простых натуральных числа.

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

[latex]c[/latex] — наибольшее целое число c, не принадлежащее множеству [latex]M[/latex].

Тесты

Входные данные Выходные данные
[latex]a[/latex] [latex]b[/latex] [latex]c[/latex]
5 3 7
2 1 -1
3 2 1

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

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

Решение

Нарисуем на плоскости систему координат [latex]Oxy[/latex] и сформулируем нашу задачу на геометрическом языке. Каждую пару целых чисел [latex]\left(x,y\right)[/latex] мы будем называть «целой точкой» и изображать красной точкой, если обе её координаты неотрицательны [latex]\left(x\geq0, y\geq0\right)[/latex], и синей точкой — если хотя бы одна координата отрицательна.

Взаимно простые натуральные числа [latex]a[/latex] и [latex]b[/latex] мы считаем фиксированными (для примера возьмём [latex]a=5, b=3[/latex]). Для каждого [latex]n[/latex] уравнение [latex]ax+by=n[/latex] определяет, как известно, прямую. Обозначим её через [latex]l_{n}[/latex]. Разумеется, все прямые [latex]l_{n}[/latex] параллельны друг другу. Пусть [latex]n[/latex] — целое. Будем считать прямую [latex]l_{n}[/latex] красной, если она проходит хотя бы через одну красную точку, и синей — в противном случае. Мы должны выяснить, каково наибольшее [latex]c[/latex], которому соответствует синяя прямая [latex]l_{с}[/latex], и доказать, что тогда из двух прямых [latex]l_{n}[/latex] и [latex]l_{c-n}[/latex] одна-синяя и одна-красная ([latex]n[/latex] — любое целое число).
Мы будем пользоваться в нашем решении перемещениями плоскости, которые отображают множество целых точек на себя и одновременно каждую прямую [latex]l_{n}[/latex] переводят в ту же самую или некоторую другую прямую [latex]l_{\acute{n}}[/latex] из нашего семейства. Это, во-первых, параллельные переносы на любой вектор [latex]\left(p, q\right)[/latex] с целыми [latex]p[/latex] и [latex]q:[/latex] [latex]\left(x,y\right)|\dashrightarrow \left(x+p, y+q\right),[/latex] и, во-вторых, повороты на [latex]180^{\circ}[/latex] (или, что то же самое, симетрии относительно точки) с любыми центрами [latex]\left(\frac{p}{2}, \frac{q}{2}\right)[/latex], где [latex]p[/latex] и [latex]q[/latex] — целые: [latex]\left(x,y\right)|\dashrightarrow \left(p-x, q-y\right).[/latex] Докажем, что на каждой прямой [latex]l_{n}[/latex] целые точки встречаются через равные промежутки.
Лемма. Если [latex]\left(x_{0},y_{0}\right)[/latex] — целая точка на прямой [latex]l_{n}[/latex], то ближайшими к ней целыми точками на [latex]l_{n}[/latex] будут [latex]\left(x_{0}-b,y_{0}+a\right)[/latex] и [latex]\left(x_{0}+b,y_{0}-a\right)[/latex] ([latex]a[/latex] и [latex]b[/latex] взаимно просты).
Рассмотрим прямую [latex]l_{0}[/latex], проходящую через [latex]\left(0, 0\right)[/latex]. Пусть [latex]\left(-b_{1}, a_{1}\right)[/latex] — ближайшая к [latex]\left(0, 0\right)[/latex] целая точка [latex]l_{0}[/latex] такая, что [latex]b_{1}>0[/latex], [latex]a_{1}>0[/latex] (мы ещё не знаем, что [latex]b_{1}=b, a_{1}=a[/latex]), [latex]\left(x_{0}, y_{0}\right)[/latex] — целая точка [latex]l_{n}[/latex]. При переносе на вектор [latex]\left(x_{0}, y_{0}\right)[/latex] отрезок прямой [latex]l_{0}[/latex] от [latex]\left(0, 0\right)[/latex] до [latex]\left(-b_{1}, a_{1}\right)[/latex] перейдет в отрезок [latex]l_{n}[/latex] от [latex]\left(x_{0}, y_{0}\right)[/latex] до [latex]\left(x_{0}-b_{1}, y_{0}+a_{1}\right)[/latex] будет ближайшей к [latex]\left(x_{0}, y_{0}\right)[/latex] точкой [latex]l_{n}[/latex] сверху. Точно так же при переносе на вектор [latex]\left(x_{0}+b_{1}, y_{0}-a_{1}\right)[/latex] — тот же отрезок прямой [latex]l_{0}[/latex] перейдёт в отрезок прямой [latex]l_{n}[/latex] от [latex]\left(x_{0}+b_{1}, y_{0}-a_{1}\right)[/latex] до [latex]\left(x_{0}, y_{0}\right)[/latex]. Следовательно, и на этом отрезке целыми точками будут только его концы.
Отсюда уже следует, то на любой прямой [latex]l_{n}[/latex] (уесли на ней есть хоть одна целая точка) промежуток между соседними целыми точками один и тот же: [latex]a_{1}[/latex] единиц по оси [latex]Oy[/latex] и [latex]b_{1}[/latex] — по оси [latex]Ox[/latex]. Это, в частности, относится и к прямой [latex]l_{0}[/latex]. Поскольку [latex]\left(-b, a\right)[/latex] принадлежит [latex]l_{0}[/latex], то отсюда следует, что [latex]b=db_{1}, a=da_{1}[/latex], где [latex]d[/latex] — некоторое целое число. Но числа [latex]a[/latex] и [latex]b[/latex] по условию взаимно просты. Значит, [latex]d=1[/latex], то есть [latex]a=a_{1}, b=b_{1}[/latex]. Лемма доказана.
Из этой леммы следует, что каждая прямая [latex]l_{n}[/latex], где [latex]n[/latex] — целое, переходит ровно через одну точку внутри полосы [latex]0\leq x\leq b-1[/latex]. При этом, очевидно, если прямая красная, то есть где-то переходит через красную точку, то её целая точка в выделенной полосе тоже будет красной (а точка синей прямой, разумеется, синяя).
Теперь заметим, что при симетрии относительно точки [latex]\left(\frac{b-1}{2} -\frac{1}{2}\right)[/latex] [latex]\left(x,y\right)\mapsto\left(\acute{x}, \acute{y}\right) =\left(b-1-x, -1-y\right)[/latex], полоса [latex]0\leq x\leq b-1[/latex] переходит в себя, причем красные точки переходят в синие, и наоборот. Прямая [latex]l_{n}[/latex] после этой симметрии переходит в прямую [latex]l_{ab-a-b-n}[/latex]: если [latex]ax+by=n[/latex], то [latex]a\acute{x}+b\grave{y}=a\left(b-1-x\right)+b\left(-1-y\right)=ab-a-b-n.[/latex] (Через центр симметрии, где [latex]a\left( \frac{b-1}{2}\right)+b\left(- \frac{1}{2}\right) = \frac{ab-a-b}{2},[/latex] ни одна из наших прямых может и не проходить.)
Ясно, что самая нижняя красная прямая — это [latex]l_{0}[/latex]. Следовательно, самая верхняя синяя прямая — это [latex]l_{ab-a-b}.[/latex] Итак, наибольшее число, не принадлежащее множеству, — это [latex]c=ab-a-b,[/latex] и из двух чисел [latex]n[/latex] и [latex]c-n[/latex] одно принадлежит [latex]M[/latex], а другое — нет.

Ссылки

Ideone C++;
Ideone Java;
Решение задачи Журнал «Квант» №11 г.1973 (стр. 44-45);
Условие задачи Журнал «Квант» №3 г.1973 (стр. 35).

MS 7. Средняя зарплата

Задача

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

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

Фамилия работника ([latex]name[/latex]) и величина его зарплаты ([latex]sal[/latex]).

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

Средняя зарплата по компании.

Тесты

Входные данные Выходные данные
[latex]name[/latex] [latex]sal[/latex]
Ivanov 200 200
Ivanov

Smirnov

Popov

Sokolov

100

150

200

150

150

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

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

Решение

В переменную [latex]total[/latex] которая изначально равна [latex]0[/latex] прибавляем зарплату каждого сотрудника, а [latex]sum[/latex] показывает количество сотрудников. Выводим зарплату всех сотрудников деленную на их количество.

Ссылки

Ideone C++
Ideone Java

D2574. Сумма ряда

Задача

Найти сумму сходящегося ряда: [latex]\sum \limits_{n=1}^{n}\frac{\sin{nx}}{2^{n}}[/latex].

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

[latex]n[/latex] — количество шагов;
[latex]x[/latex] — значение [latex]x[/latex].

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

Сумма ряда [latex]\sum \limits_{n=1}^{n}\frac{sin(nx)}{2^{n}}[/latex].

Тесты

Входные данные Выходные данные
[latex]n[/latex] [latex]x[/latex]
10 0.523598 0.651170
25 3.141592 0
15 1.570796 0.399994

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

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

Решение

Проверим решение с WolframAlpha.

Ссылки

Ideone на C++;
Ideone на Java;
WolframAlpha.

A320. Вложенный цикл

Задача

Вычислить [latex]\sum\limits_{k=1}^{n}\left( k^{3}\sum\limits_{l=1}^{m}\left(k-l\right)^{2}\right).[/latex]

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

Произвольные [latex]n[/latex] и [latex]m.[/latex]

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

Значение [latex]\sum\limits_{k=1}^{n}\left( k^{3}\sum\limits_{l=1}^{m}\left(k-l\right)^{2}\right).[/latex]

Тесты

Входные данные Выходные данные
[latex]n[/latex] [latex]m[/latex]
10 15 983455
2 5 150
3 6 816

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

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

Решение

Проверим решение с WolframAlpha.

Ссылки

Ideone C++;
Ideone Java;
WolframAlpha.