подсчёт | C++ для приматов

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

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

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

#include <iostream>
#define MAX 101
using namespace std;

int a[MAX];

int main() {
    int n, l, res = 0, i;
    cin >> n;
    for(l = 0; l < n; l++) cin >> i, a[i]++;
    for(i = 1; i <= MAX - 1; i++) res += a[i] / 4;
    cout << res << "\n";
    return 0;
}

#include <iostream>

#define MAX 101

using namespace std;

int a[MAX];

int main() {

int n, l, res = 0, i;

cin >> n;

for(l = 0; l < n; l++) cin >> i, a[i]++;

for(i = 1; i <= MAX - 1; i++) res += a[i] / 4;

cout << res << "\n";

return 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 подсчитываем количество квадратов, которое можно построить.

Задача

Сколько раз будет использована цифра $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

Код

#include <iostream>
using namespace std;

int count_six(int input){
    int rez = 0, mem = 1, length = 0, exp_10 = 1;
    short num;
    while(input > 0){
        num = input % 10;//узнаём последний знак в числе
        input /= 10;//убираем последний разряд из числа
        if (num < 6) rez += num * exp_10 * length; //к результату добавим количество шестёрок в данном разряде
        else if (num == 6) rez += num * exp_10 * length + mem; //к результату добавим количество шестёрок в данном разряде плюс уже пройденное нами число+1
        else rez += num * exp_10 * length + exp_10 * (length == 0? 1 : 10); //к результату добавим количество шестёрок в предыдущем разряде
        if (length != 0) exp_10 *= 10; //проверяем количество пройденных разрядов 
        mem += num * exp_10; //запоминаем пройденное число
        length++; //отмечаем пройденный разряд
    }
    return rez;
}

int main() {
    int a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    cout << count_six(b) - count_six(a - 1);
    return 0;
}

#include <iostream>

using namespace std;

int count_six(int input){

int rez = 0, mem = 1, length = 0, exp_10 = 1;

short num;

while(input > 0){

num = input % 10;//узнаём последний знак в числе

input /= 10;//убираем последний разряд из числа

if (num < 6) rez += num * exp_10 * length; //к результату добавим количество шестёрок в данном разряде

else if (num == 6) rez += num * exp_10 * length + mem; //к результату добавим количество шестёрок в данном разряде плюс уже пройденное нами число+1

else rez += num * exp_10 * length + exp_10 * (length == 0? 1 : 10); //к результату добавим количество шестёрок в предыдущем разряде

if (length != 0) exp_10 *= 10; //проверяем количество пройденных разрядов

mem += num * exp_10; //запоминаем пройденное число

length++; //отмечаем пройденный разряд

}

return rez;

}

int main() {

int a, b;

cin >> a >> b;

if (a > b) swap(a, b);

cout << count_six(b) - count_six(a - 1);

return 0;

}

Решение

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

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

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

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

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
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

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: подсчёт

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

Задача

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

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

Тесты

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

Решение

Ссылки

Related Images:

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

Задача

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

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

Тесты

Код

Решение

Ссылки

Related Images: