Всем доброго времени суток! 30 сентября закончился прием заявок на школу программирования HeadHunter 2016. В этой статье я хотела бы разобрать задачи заочного этапа. Надеюсь, что моя статья будет полезной, учитывая, что при решении задач пришлось посетить не один десяток сайтов. Я имею небольшой опыт в программировании, поэтому я не утверждаю, что мое решение единственно верное. Всегда буду рада услышать Вашу критику!
При решении задач используется язык программирования Java.
Задача 1
Дано равенство, в котором цифры заменены на буквы: rqr + rqq = sqr. Найдите сколько у него решений, если различным буквам соответствуют различные цифры (ведущих нулей в числе не бывает).
Для решения этой задачи можно выбрать два пути: решить ее «в лоб» с использованием трех вложенных циклов for или преобразовать выражение и использовать только два вложенных цикла for.
Выберем второй путь. Буквы в выражении условия задачи являются цифрами, а это значит, что каждое из них изменяется в пределах от 0 до 9. Теперь вспомним представление цисла в десятичной системе счисления и преобразуем выражение к следующему виду: s = 2r + 0.11q. Тогда код решения задачи будет выглядеть следующим образом:
public class FirstTask {
public static void main(String[] args){
int count = 0;
for (int q = 0; q < 10; q++){
for (int r = 1; r < 10; r++){
if ((r != q)){
double s = 2 * r + 0.11 * q;
if (s % 1 == 0 && s != 0 && s < 10)
count++;
}
}
}
System.out.println("count is " + count);
}
}
В условии задачи указано, что не должно быть ведущих нулей, исходя из этого были выбраны начальные значения для переменных. Для переменной s необходимо использовать тип double для корректного выполнения условия s % 1 == 0. Данная программа считает следующие тождества:
101 + 100 = 201.0
202 + 200 = 402.0
303 + 300 = 603.0
404 + 400 = 804.0
count is 4Задача 2
Наименьшее число m, такое, что m! делится без остатка на 10 — это m=5 (5! = 120). Аналогично, наименьшее число m, такое, что m! делится без остатка на 25 — это m=10. В общем случае, значение функции s(n) равно наименьшему числу m, такому что m! без остатка делится на n.
Определим функцию S(M, N) = ∑s(n) для всех n ∈ [M, N]. К примеру, S(6, 10) = 3 + 7 + 4 + 6 + 5 = 25. Найдите S(2300000, 2400000).
Разобьем задачу на несколько этапов. Нам необходимо построить метод, вычисляющий факториал натурального числа (метод factorial(long m)), вычисляющий значение m, удовлетворяющее условию задачи (метод mod(long n)) и метод, вычисляющий значение функции S(M, N) (метод solve(long n, long m)).
Обратите внимание, что в условии задачи необходимо найти значение функции S(2300000, 2400000), факториал от аргументов которой будет большим числом, поэтому для всех числовых переменных используем тип long (иначе вычисления будут некорректными).
Метод factorial(long m) реализуем с помощью простой рекурсии: текущую переменную ret умножаем на переменную цикла for и затем присваиваем ей результат, пока не будут выполнены все итерации цикла.
Метод mod(long n) выполняет поиск наименьшего значения m, которое удовлетворяет условию задачи: factorial(m) % n == 0. Для подбора таких значений используем цикл for. Как только такое m нашлось, выходим из цикла.
Метод solve(long n, long m) вычисляет сумму всех значений, полученных с помощью метода mod(long n) с помощью цикла for, переменная которого изменяется от n до m с шагом в единицу.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class SecondTask {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(br.readLine());
long m = Long.parseLong(br.readLine());
System.out.println(solve(n,m));
}
public static long factorial(long m){
long ret = 1;
for (long i = 1; i <= m; i++)
ret *= i;
return ret;
}
public static long mod(long n) {
long result = 0;
for (long m = 0; m <= n; m++) {
if (factorial(m) % n == 0) {
result = m;
break;
}
}
return result;
}
public static long solve(long n, long m){
long result = 0;
for (long i = n; i <= m; i++)
result += mod(i);
return result;
}
}
Тестируем программу для примера в условии задачи S(6, 10):
6
10
25Результат выполнения программы для S(2300000, 2400000):
2300000
2400000
6596625
Задача 3
Рассмотрим все возможные числа ab для 1<a<6 и 1<b<6:
22=4, 23=8, 24=16, 25=32 32=9, 33=27, 34=81, 35=243 42=16, 43=64, 44=256, 45=1024, 52=25, 53=125, 54=625, 55=3125. Если убрать повторения, то получим 15 различных чисел. Сколько различных чисел ab для 2<a<135 и 2<b<136?
Для возведения числа в степень используем метод Math.pow(x,y) (зачем изобретать велосипед?). Правда, при использовании этого метода необходимо, чтобы все числовые переменные имели тип double.
Решаем задачу с помощью двух коллекций: ArrayList используем для добавления элементов ab, HashSet используем для удаления из коллекции всех повторяющихся элементов.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
public class ThirdTask {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("type the interval for a");
double a1 = Long.parseLong(br.readLine());
double a2 = Long.parseLong(br.readLine());
System.out.println("type the interval for b");
double b1 = Long.parseLong(br.readLine());
double b2 = Long.parseLong(br.readLine());
pow(a1, a2, b1, b2);
}
public static ArrayList<Double> pow(double a1, double a2, double b1, double b2){
ArrayList<Double> arr = new ArrayList<>();
for (double i = a1 + 1; i < a2; i++){
for (double j = b1 + 1; j < b2; j++){
arr.add(Math.pow(i,j));
}
}
System.out.println("arr size is " + arr.size());
HashSet<Double> list = new HashSet<Double>(arr);
System.out.println("now arr size is " + list.size());
return arr;
}
}
Тестируем программу для 1<a<6 и 1<b<6:
type the interval for a
1
6
type the interval for b
1
6
arr size is 16
now arr size is 15Результат выполнения программы для 2<a<135 и 2<b<136:
type the interval for a
2
135
type the interval for b
2
136
arr size is 17556
now arr size is 16640Статья получилась достаточно большой, а впереди еще две объемные задачи, в которых нужно разобрать логику перебора элементов. Остальные задачи разберем в следующей публикации.
Автор: ia_bobrova
