Analysis of tasks of the correspondence tour of the school programmers HeadHunter 2016. Part 1

Good day to all! September 30 ended accepting applications to the school programming HeadHunter 2016 . In this article I would like to review the tasks of the correspondence stage. I hope that my article will be useful, given that when solving problems I had to visit more than a dozen sites. I have little experience in programming, so I do not claim that my decision is the only correct one. I will always be glad to hear your criticism!

When solving problems using the Java programming language.



The article was corrected with the help of user comments: one cycle is used in solving the first task, when calculating the factorial of a natural number, the BigInteger type is used instead of long, the second task is corrected.

Task 1

An equality is given, in which the numbers are replaced by letters: rqr + rqq = sqr. Find how many solutions he has if different numbers correspond to different letters (there are no leading zeros in the number).



To solve this problem, you can choose two ways: solve it head-on using three nested for loops or convert the expression and use only two nested for loops.

')

Choose a second path. The letters in the expression conditions of the problem are numbers, which means that each of them varies from 0 to 9 . Now we recall the representation of the number in decimal number system and transform the expression to the following form: s = 2r + 0.11q . Then the code for solving the problem will look like this:



The problem statement states that there should not be leading zeros, based on this, the initial values ​​for the variables were chosen. For the variable s, you must use the double type to correctly fulfill the condition s% 1 == 0 . This program considers the following identities:

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

If we consider that q = 0 , then we have only one cycle:

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

Task 2

The smallest m such that m! divided by no more than 10 — this is m = 5 (5! = 120). Similarly, the smallest m is such that m! divided by no more than 25 - this is m = 10. In general, the value of the function s (n) is equal to the smallest number m, such that m! no residue divided by n.

We define the function S (M, N) = ∑s (n) for all n ∈ [M, N]. For example, S (6, 10) = 3 + 7 + 4 + 6 + 5 = 25. Find S (2300000, 2400000).



We divide the task into several stages. We need to build a method that calculates the factorial of a natural number (the factorial method (BigInteger m) ), calculates the value of m , satisfies the condition of the problem (the mod method (BigInteger n) ) and the method that calculates the value of the function S (M, N) (the solve method (BigInteger n, BigInteger m) ).



Please note that in the problem statement it is necessary to find the value of the function S (2300000, 2400000) , the factorial from the arguments of which will be a large number, therefore for all numeric variables we use the BigInteger type (otherwise the calculations will be incorrect).



We implement the factorial method (BigInteger m) using a loop: multiply the current variable ret by the for loop variable and then assign the result to it until all the iterations of the loop have been completed.

The mod (BigInteger n) method searches for the smallest m value that satisfies the problem condition: factorial (m)% n == 0 . For the selection of such values, use the for loop. As soon as such m was found, exit the loop.



The solve method (BigInteger n, BigInteger m) calculates the sum of all values ​​obtained using the mod (BigInteger n) method using a for loop, the variable of which changes from n to m in increments of one.



The solution to this problem uses the algorithm in the comments .

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

We test the program for an example in the condition of the problem S (6, 10) :

 6 10 25 solveTime is 0 ms 

The result of the program for the S (2300000, 2400000) :

 2300000 2400000 1796256390 solveTime is 130854 ms 

Task 3

Consider all possible numbers a ^b for 1 <a <6 and 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. If we remove the repetition, we get 15 different numbers. How many different numbers a ^b for 2 <a <135 and 2 <b <136?



To raise a number to a power, we use the Math.pow (x, y) method (why reinvent the wheel?). However, when using this method, it is necessary that all numeric variables have a double type.



We solve the problem using two collections: ArrayList is used to add elements a ^b , HashSet is used to remove all duplicate elements from the collection.

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

We test the program for 1 <a <6 and 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 

The result of the program for 2 <a <135 and 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 

The article turned out to be quite large, and there are still two voluminous tasks ahead of which we need to analyze the logic of sorting the elements. The remaining tasks will be analyzed in the following publication.