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

public static void main(String[] args){
        int count = 0;
        for (int r = 1; r < 10; r++){
             double s = 2 * r ;
             if (s < 10) {
                    count++;
             }
         }
  }
  System.out.println("count is " + count);
}

public static void main(String[] args){
        int count = 0;
        for (int r = 1; 2*r < 10; r++){
             count++;
         }
  }
  System.out.println("count is " + count);
}

Те по большому счету — программа не нужна:) Раз q=0, для r остается всего (1,2,3,4), учитывая что 2*r<9

1. В первой задаче встречается сравнение двух вещественных чисел, что само по себе уже плохо. Плюс одно из чисел получено умножением на число 0,11, которое непредставимо в виде конечной двоичной дроби (то есть гарантированно будут ошибки округления). Да, в этом случае всё сработало, но так писать не стоит.

Вместо этого вполне можно было работать с целыми, используя равенство 100s = 220r + 11q. Какая разница, храним мы s в памяти или 100s? А при выводе на экран уже разделим.

Ну и в целом решение "в лоб" не хуже на самом деле. Оно отрабатывает быстро, пишется быстрее и проще в понимании. Не нужно оптимизировать то, что не тормозит. Если, конечно, не стоит цель рассказать о другом интересном решении. ;)

2. Факториал очень быстро растёт. 69! уже больше, чем 10^100. Поэтому лучше не считать его явно. (Да, кстати, в методе factorial у вас нет рекурсии.)

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

Например:
5 = 5^1. m = max {5*1} = 5.
25 = 5^2. m = max {5*2} = 10.
12 = 2^2 * 3^1. m = max {2*2, 3*1} = 4. (То есть 4! — это наименьший факториал, который делится на 12)

Почему работает, надеюсь, понятно, а то объяснять долго. (Но я сейчас это придумал сходу, может проще можно.)

На простые множители раскладывать тоже легко: делим на 2 пока делится и считаем сколько раз разделилось. Потом по нечётным числам: на 3, на 5, на 7 пока не получим единицу в частном.

Наверное, если подумать, то и S как-то можно хитро упростить, но сходу ничего в голову не приходит. Это надо серьёзно с карандашом посидеть.

3. Тоже через множители проще сделать.

И да, если продолжить рассуждения в первой задаче, то она у вас одной команде вывода ответа на экран сведётся, так как там достаточно легко все цифры вручную найти. :)

поэтому для всех числовых переменных используем тип long (иначе вычисления будут некорректными)

factorial(m) % n == 0

Метод factorial(long m) реализуем с помощью простой рекурсии: текущую переменную ret умножаем на переменную цикла for и затем присваиваем ей результат, пока не будут выполнены все итерации цикла.

• Факторизируем число (раскладываем на простые множители)
• В получившемся словаре формата {prime: degree}, где prime — простое число, а degree — его степень, проходим по ключам и находим для каждого из них минимальное число n такое, что n! mod prime ^prime = 0
• Суммируем результат по всем числам в требуемом диапазоне

def foo(a1, a2, b1, b2):

    s = set()

    for a in range(a1+1, a2):
        for b in range(b1+1, b2):
            s.add(pow(a, b))

    return len(s)

bool ab[135][135] = {}; // заполнено значениями false - т.е. "не покрашены ещё"
for(int a1=3; a1 < 135; ++a1) {
  for(int b1=2, a2=a1*a1; a2 < 135; b1+=1, a2*=a1) { // бежим по степеням числа a1
    for(int b2=b1; b2 < 135; b2+=b1) { // красим кратные степени
      ab[a2][b2] = true;  // "повторно использовано"
}}}
int count = 0;
for(int a1=3; a1 < 135; ++a1)
  for(int b1=3; b1 < 135; ++b1)
    if(!ab[a1][b1])
      ++count;