Как стать автором
Обновить

Разбор задач заочного тура школы программистов HeadHunter 2016. Часть 1

Время на прочтение 5 мин
Количество просмотров 16K
Всем доброго времени суток! 30 сентября закончился прием заявок в школу программирования HeadHunter 2016. В этой статье я хотела бы разобрать задачи заочного этапа. Надеюсь, что моя статья будет полезной, учитывая, что при решении задач пришлось посетить не один десяток сайтов. Я имею небольшой опыт в программировании, поэтому я не утверждаю, что мое решение единственно верное. Всегда буду рада услышать Вашу критику!
При решении задач используется язык программирования Java.

Статья исправлена с помощью комментариев пользователей: используется один цикл в решении первой задачи, при вычислении факториала натурального числа используется тип BigInteger вместо long, исправлена вторая задача.

Задача 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

Если учесть, что q = 0, то имеем только один цикл:
public class FirstTask {
    public static void main(String[] args){
        int count = 0;
        for (int r = 1; 2 * r < 10; r++)
        count++;
        System.out.println("count is " + count);
    }
}

Задача 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(BigInteger m)), вычисляющий значение m, удовлетворяющее условию задачи (метод mod(BigInteger n)) и метод, вычисляющий значение функции S(M, N) (метод solve(BigInteger n, BigInteger m)).

Обратите внимание, что в условии задачи необходимо найти значение функции S(2300000, 2400000), факториал от аргументов которой будет большим числом, поэтому для всех числовых переменных используем тип BigInteger (иначе вычисления будут некорректными).

Метод factorial(BigInteger m) реализуем с помощью цикла: текущую переменную ret умножаем на переменную цикла for и затем присваиваем ей результат, пока не будут выполнены все итерации цикла.
Метод mod(BigInteger n) выполняет поиск наименьшего значения m, которое удовлетворяет условию задачи: factorial(m) % n == 0. Для подбора таких значений используем цикл for. Как только такое m нашлось, выходим из цикла.

Метод solve(BigInteger n, BigInteger m) вычисляет сумму всех значений, полученных с помощью метода mod(BigInteger n) с помощью цикла for, переменная которого изменяется от n до m с шагом в единицу.
Старое решение с использованием BigInteger
public class SecondTask {
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BigInteger n = BigInteger.valueOf(Integer.parseInt(br.readLine()));
        BigInteger m = BigInteger.valueOf(Integer.parseInt(br.readLine()));
        solve(n,m);
    }
    public static BigInteger factorial(BigInteger n) {
        BigInteger res = BigInteger.ONE;
        if (n.intValue() == 0 || n.intValue() == 1) return res;
        else {
            for (BigInteger i = BigInteger.ONE; i.compareTo(n) <= 0; i = i.add(BigInteger.ONE)) {
                res = res.multiply(i);
            }
        }
        return res;
    }
    public static BigInteger s(BigInteger n) {
        BigInteger res = BigInteger.ZERO;
        for (BigInteger m = BigInteger.ZERO; m.compareTo(n) <= 0; m = m.add(BigInteger.ONE)) {
            System.out.println("m = " + m);
            if ((factorial(m)).mod(n).equals(BigInteger.ZERO)) {
                res = m;
                break;
            }
        }
        return res;
    }
    public static BigInteger solve(BigInteger N, BigInteger M){
        BigInteger res = BigInteger.ZERO;
        for (BigInteger i = N; i.compareTo(M) <= 0; i = i.add(BigInteger.ONE)){
            BigInteger m = s(i);
            res = res.add(m);
        }
        return res;
    }

Тестируем программу для примера в условии задачи S(6, 10):
6
10
25

Результат выполнения программы для S(2300000, 2400000) (был использован тип long:
2300000
2400000
6596625


Решение этой задачи использует алгоритм в комментарии.
public class SecondTask {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        Date startSolve = new Date();
        solve(n, m);
        Date finishSolve = new Date();
        long solveTime = finishSolve.getTime() - startSolve.getTime();
        System.out.println("solveTime is " + solveTime + " ms");
    }
    public static int s(int n) {
        TreeMap<Integer, Integer> treemap = new TreeMap<Integer, Integer>();
        int i = 2, count = 1;
        while (i <= n){
            if (n % i == 0){
                if (treemap.containsKey(i)){
                    count++;
                    treemap.put(i, count);
                } else {
                    count = 1;
                    treemap.put(i, count);
                }
                n = n / i;
                i--;
            } i++;
        }
        int p = treemap.lastKey(), k = treemap.get(treemap.lastKey()), m = 0;
        if (k > p){
            do k--;
            while(k > p);
            m = k * p;
        } else m = k * p;
        return m;
    }
    public static int solve(int n, int m){
        int res = 0;
        for (int i = n; i <= m; i++)
            res += s(i);
        System.out.println(res);
        return res;
    }
}

Тестируем программу для примера в условии задачи S(6, 10):
6
10
25
solveTime is 0 ms

Результат выполнения программы для S(2300000, 2400000):
2300000
2400000
1796256390
solveTime is 130854 ms

Задача 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 используем для удаления из коллекции всех повторяющихся элементов.
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

Статья получилась достаточно большой, а впереди еще две объемные задачи, в которых нужно разобрать логику перебора элементов. Остальные задачи разберем в следующей публикации.
Теги:
Хабы:
+7
Комментарии 46
Комментарии Комментарии 46

Публикации

Истории

Работа

Java разработчик
356 вакансий

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн