[Из песочницы] Разбор задач заочного тура школы программистов HeadHunter 2016. Часть 106.10.2016 14:18

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

Задача 1

Для решения этой задачи можно выбрать два пути: решить ее «в лоб» с использованием трех вложенных циклов 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);
    }
}

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

Задача 2

Разобьем задачу на несколько этапов. Нам необходимо построить метод, вычисляющий факториал натурального числа (метод 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;
    }
}

6
10
25

2300000
2400000
6596625

Задача 3

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 pow(double a1, double a2, double b1, double b2){
        ArrayList 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 list = new HashSet(arr);
        System.out.println("now arr size is " + list.size());
        return arr;
    }
}

type the interval for a
1
6
type the interval for b
1
6
arr size is 16
now arr size is 15

type the interval for a
2
135
type the interval for b
2
136
arr size is 17556
now arr size is 16640