e-olymp 145. Квадраты

Задача взята с сайта e-olymp

Задача

Заданы длины $n$ отрезков. Какое наибольшее количество квадратов можно из них составить? Сторона каждого квадрата должна состоять только из одного отрезка.

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

В первой строке находится количество отрезков $n \left(1 \leqslant n\leqslant 10^6\right)$. Во второй строке заданы $n$ натуральных чисел — длины отрезков, числовые значения которых не превышают $100$.

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

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

Тесты

#   ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 9
2 2 4 2 3 2 1 2 4
1
2 11
2 2 4 2 2 4 2 2 1 2 2
2
3 5
8 9 8 9 11
0

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

Решение

Пусть имеется $k$ отрезков одинаковой длины. Тогда из них можно составить $\frac{k}{4}$ квадрата. Длины отрезков изменяются от $1$  до $100$. Подсчитываем количество отрезков длины $i\left(1\leqslant i\leqslant 100\right)$ в массив $a\left[i\right]$. Тогда максимально возможное количество квадратов, которое можно составить из данных отрезков, равно $$\frac{a\left[1\right]+a\left[2\right]+\dots +a\left[100\right]}{4}.$$
Для этого совершим сортировку подсчетом. В ячейке a[i] подсчитываем количество отрезков длины i . В переменную res  подсчитываем количество квадратов, которое можно построить.

Ссылки

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

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

Сортировка подсчетом на Wikipedia

e-olymp 7228. Сколько шестерок?

Задача

Сколько раз будет использована цифра $6$, если записать подряд последовательные натуральные числа от $a$ до $b$?

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

Два натуральных числа $a$ и $b$ [latex](1 ≤ a, b ≤ 10^9)[/latex].

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

Количество цифр $6$ в последовательных натуральных числах от $a$ до $b$.

Тесты

Ввод Вывод
1 5 256 46
2 56 110 16
3 27357 43577 5852
4 368325775 56 296285528
5 584937543 984938576 420000314

Код

Решение

Выписав и посчитав количества шестёрок от $1$ до [latex]10, 100, 1000, …[/latex] Мы обнаружим закономерность, они равны [latex]1, 20, 300, …[/latex] соответственно.

Доказательство проведем по математической индукции.

  1. Для [latex]n = 1[/latex] [latex]countSix(10^1) = 1[/latex].
  2. Для [latex]n ≤ k[/latex] $countSix(10^{k}) = k \cdot 10^{k-1}$
  3. Для [latex]n = k+1[/latex] $countSix(10^{k+1}) = k\cdot10^{k-1}\cdot10+10^k = (k+1)\cdot10^k$

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

Ссылки