Задача
Андрей очень любит ездить по железной дороге. Он садится у окна и внимательно следит за местностью, которую он проезжает. Особенно он обращает внимание на километровые столбы. Каждый столб с километражем, который при делении на $7$ дает в остатке $3$, он считает «счастливым». Составьте программу, которая бы определяла количество «счастливых» столбов, если во время езды он проезжает столбы с отметками от $a$ до $b.$
Входные данные
Два натуральных числа $a$ и $b$ ($0 ≤ a < b ≤ 10^9$).
Выходные данные
Вывести количество «счастливых» столбов.
Тесты
| Входные данные | Выходные данные |
| $0$ $5$ | $1$ |
| $26$ $49$ | $3$ |
| $73$ $80$ | $2$ |
| $5$ $8$ | $0$ |
| $17$ $37$ | $3$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 |
#include <iostream> using namespace std; int main() { int a, b; cin>>a>>b; int result = (b+4)/7 - (a+4)/7 + (a%7==3); cout<<result; return 0; } |
Решение задачи
Количество «счастливых» столбцов $l$ от $0$ до $n$, то есть количество натуральных чисел $k$ от $0$ до $n$, таких, что $k \mod7 = 3$, равно количеству чисел от $0$ до $n-3$, делящихся нацело на $7$, увеличенному на $1.$ То есть $l = \frac{n-3}{7}+1 = \frac{n+4}{7}$ (деление целочисленное). Тогда количество «счастливых» столбов на промежутке от $a$ до $b$ равно разнице количества «счастливых» столбов на промежутке от $0$ до $b$ и количества «счастливых столбов» на промежутке от $0$ до $a.$ Кроме того, если столб с отметкой $a$ является счастливым, мы должны увеличить полученный результат на $1$. Отсюда получаем итоговую формулу решения, указанную в коде программы.
Ссылки
Условие задачи на e-olymp
Код решения
Зачтено.
Но можно было чуть проще (b + 4) / 7 - (a + 3) / 7