Разбор Задач Заочного Тура Школы Программистов Headhunter 2016. Часть 1

Добрый день всем! Крайний срок приема заявок – 30 сентября.

Школа программирования HeadHunter 2016 .

В этой статье мне бы хотелось проанализировать задачи заочного этапа.

Надеюсь, что моя статья будет полезна, учитывая, что при решении задач мне пришлось посетить не один десяток сайтов.

Опыт программирования у меня небольшой, поэтому не утверждаю, что мое решение единственно правильное.

Всегда буду рад услышать вашу критику! Язык программирования Java используется для решения проблем.

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

Проблема 1

Для решения этой задачи можно выбрать два пути: решить ее в лоб, используя три вложенных цикла.

для или преобразуйте выражение и используйте только два вложенных цикла для .

Выберем второй путь.

Буквы в выражении условий задачи являются числами, а это значит, что каждая из них варьируется от 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);
     }
 }
 

   

Для переменной с необходимо использовать тип двойной за правильное выполнение условия с % 1 == 0 .

Эта программа учитывает следующие тождества:

101 + 100 = 201.0 202 + 200 = 402.0 303 + 300 = 603.0 404 + 400 = 804.0 count is 4

Учитывая, что д = 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

Разобьем задачу на несколько этапов.

Нам нужно построить метод, вычисляющий факториал натурального числа (метод факториал (BigInteger м) ), вычисляя значение м , удовлетворяющий условиям задачи (метод мод (BigInteger n) ) и метод, вычисляющий значение функции С(М, Н) (метод решить (BigInteger n, BigInteger m) ).

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

Метод факториал (BigInteger м) реализовать с помощью цикла: текущая переменная в отставку умножить на переменную цикла для а затем присваивайте ему результат до тех пор, пока не будут завершены все итерации цикла.

Метод мод (BigInteger n) ищет наименьшее значение м , что удовлетворяет условиям задачи: факториал(м) % n == 0 .

Для выбора таких значений используем цикл для .

Как только это м нашли, выходим из цикла.

Метод решить (BigInteger n, BigInteger m) вычисляет сумму всех значений, полученных с помощью метода мод (BigInteger n) используя цикл для , переменная которого варьируется от н до м с шагом в единицу.

Старое решение с использованием 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; }

Тестирование примера программы в постановке задачи С(6, 10) :

6 10 25

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

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; } }

Тестирование примера программы в постановке задачи С(6, 10) :

6 10 25 solveTime is 0 ms

Результат выполнения программы за С(2300000, 2400000) :

2300000 2400000 1796256390 solveTime is 130854 ms

Проблема 3