Задача
Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.
Малыши часто просили его научить играть на каком-нибудь инструменте. Гусля не отказывал, но сначала предлагал взять инструмент с первым номером, а если ученику хотелось играть на другом, то он выбирал шестой следующий по кругу и так далее. Напишите программу, которая определяла номер попытки, с которой ученик мог получить желаемый инструмент с номером $k$.
Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.
Входные данные
Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.
Выходные данные
Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.
Тесты
| № | Входные данные | Выходные данные |
|---|---|---|
| 1 | 11 3 | 5 |
| 2 | 6 2 | 0 |
| 3 | 13 13 | 3 |
| 4 | 9 8 | 0 |
| 5 | 5 5 | 5 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
import java.util.Scanner; class Main { public static void main (String[] args) { int counter = 1; Scanner in = new Scanner(System.in); int quantity = in.nextInt(); int instrument = in.nextInt(); if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) { System.out.print(0); } else if (quantity == instrument) { for (int num = 1; num % quantity != 0; num += 6) { if (num != 1 && num % quantity == 1){ System.out.print(0); System.exit(0); } else { counter++; } } System.out.print(counter); } else { for (int num = 1; num % quantity != instrument; num += 6) { if (num != 1 && num % quantity == 1) { System.out.print(0); System.exit(0); } else { counter++; } } System.out.print(counter); } } } |
Решение
Для решения задачи нам необходимо рассмотреть ряд натуральных чисел, начиная с единицы и прибавляя каждый раз $6$. С помощью операции деления с остатком мы можем реализовать алгоритм нахождения номера музыкального инструмента. Однако логика решения изменяется в зависимости от введенных пользователем данных. Имеется два случая:
- Если пользователь вводит разные числа.
- Если пользователь вводит одинаковые числа.
В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.
Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.
Ссылки
- Условие задачи на e-olymp
- Код программы на ideone.com
- Засчитанное решение на e-olymp