Задача
Андрей очень любит ездить по железной дороге. Он садится у окна и внимательно следит за местностью, которую он проезжает. Особенно он обращает внимание на километровые столбы. Каждый столб с километражем, который при делении на $7$ дает в остатке $3$, он считает «счастливым». Составьте программу, которая бы определяла количество «счастливых» столбов, если во время езды он проезжает столбы с отметками от $a$ до $b.$
Входные данные
Два натуральных числа $a$ и $b$ ($0 \leq a \lt b \leq 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 11 12 |
import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception{ BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String[] params = bufferedReader.readLine().split(" "); int a = Integer.parseInt(params[0]); int b = Integer.parseInt(params[1]); System.out.println((b + 4) / 7 - (a + 3) / 7); } } |
Решение задачи
Количество «счастливых» столбцов $l$ от $0$ до $n$, то есть количество натуральных чисел $k$ от $0$ до $n$, таких, что $k \mod7 = 3$, равно количеству чисел от $0$ до $n-3$, делящихся нацело на $7$, увеличенному на $1.$ То есть $l = \lfloor \frac{n-3}{7} \rfloor +1 = \lfloor \frac{n+4}{7} \rfloor$. Тогда количество «счастливых» столбов на промежутке от $a$ до $b$ равно разности количества «счастливых» столбов на промежутке от $0$ до $b$ и количества «счастливых столбов» на промежутке от $0$ до $a$ не включительно. Отсюда получаем итоговую формулу решения, указанную в коде программы.
Поясним теперь использование класса
java.io.BufferedReader вместо
java.util.Scanner. Класс
Scanner предоставляет удобный высокоуровневый инструментарий для парсинга целых чисел из входного потока, за что приходится расплачиваться производительностью. В силу достаточно малого ограничения по времени на работу программы мы вынуждены использовать более низкоуровневый инструментарий для чтения строки с параметрами из входного потока и самостоятельно парсить ее.