Задача. Подсчитайте количество счастливых билетов, у которых сумма первых трёх цифр равна N(N≤27). Счастливым билетом называется билет с шестизначным номером, у которого сумма первых трёх цифр равна сумме трёх последних.
Тесты
| Число N | 3 | 27 | 26 | 1 | 10 |
| Количество билетов | 100 | 1 | 9 | 9 | 3969 |
Код программы
|
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 |
import java.util.*; import java.lang.*; import java.io.*; import java.util.Scanner; class Ideone { public static void main (String[] args) throws java.lang.Exception { int n, c = 0; Scanner in = new Scanner(System.in); String reader = in.nextLine(); n = Integer.parseInt(reader); for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа { for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры { if ( n - i - j >= 0 && n - i - j < 10 ) //условие для третьей цифры { c++;//подсчет подходящих номеров } } } System.out.println(c*c); //увеличение количества в c раз для шестизначного числа } } |
Код можно увидеть тут.
Алгоритм
Любой шестизначный номер мы можем представить как 2 трехзначных номера.
Рассмотрим все варианты трехзначных номеров. Две первые цифры такого номера могут быть любыми. Переберем все их комбинации с помощью двух вложенных циклов. Для третьей цифры введем специальное условие. Она должна быть результатом вычитания двух первых цифр из [latex]N[/latex], а также быть именно цифрой, то есть меньшей 10.
Когда в цикле встречается подходящая комбинация, мы увеличиваем счетчик [latex]c[/latex] на 1. Поскольку на самом деле номер шестизначный, то каждой удачной комбинации в первой его половине будет соответствовать [latex]c[/latex] комбинаций во второй. Следовательно, искомое число счастливых билетов будет равно [latex]c^2[/latex].
Ссылка на авторское решение задачи.