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

Всім доброго часу доби! 30 вересня закінчився прийом заявок на школу програмування HeadHunter 2016. У цій статті я хотіла б розібрати завдання заочного етапу. Сподіваюся, що моя стаття буде корисною, враховуючи, що при вирішенні завдань довелося відвідати не один десяток сайтів. Я маю невеликий досвід в програмуванні, тому я не стверджую, що моє рішення єдино вірне. Завжди буду рада почути Вашу критику!

При вирішенні завдань використовується мова програмування Java.

Завдання 1
Дано рівність, в якому цифри замінені на літери: rqr + rqq = sqr. Знайдіть скільки у нього рішень, якщо різним буквам відповідають різні цифри (ведучих нулів у числі не буває).

Для вирішення цієї задачі можна вибрати два шляхи: вирішити її «в лоб» з використанням трьох вкладених циклів for або перетворити вираз і використовувати тільки два вкладених циклу for.

Виберемо другий шлях. Букви у вираженні умови задачі є цифрами, а це значить, що кожне з них змінюється в межах від 0 9. Тепер згадаємо уявлення цисла десятковій системі числення і перетворимо вираз до наступного вигляду: s = 2r + 0.11 q. Тоді код розв'язання задачі буде виглядати наступним чином:

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

Стаття вийшла досить великий, а попереду ще дві об'ємні завдання, в яких потрібно розібрати логіку перебору елементів. Інші завдання розглянемо в наступній публікації.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.