Фирма "1С". "Алгоритмы. Олимпиадное программирование на языке Java для школьников"

3A. Уравнение

Уравнение AX + B = 0 имеет

• бесконечно много решений в целых числах при A и B равных 0;
• не имеет решений, если A = 0, а B нет;
• если A ≠ 0, то A должно делиться на B, чтобы оно имело единственный корень.

Если A и B равны нулю – ответ «INF»

if (A == 0 && B == 0) out.print("INF"); 

Если A ≠ 0 и B делится на А – частное с противоположным знаком:

else if (A != 0 && B % A == 0) out.print(-B / A);  

иначе «NO»:

else out.print("NO");  

3B. Фишки

В данной задаче фишки расставлены по периметру клетчатой квадратной доски. . Зная формулу для нахождения периметра клетчатой доски: P=4a-4, где P - периметр; a - сторона квадрата, получим, что a=(P-4)/4. Чтобы задача имела решение, необходимо, чтобы a имело смысл.

Таким образом, в задаче нужно проверить делится ли введённое число P на 4 (в этом случае и a будет делиться на 4 по свойству разности сравнений).

Также нужно отдельно рассмотреть случаи, когда введённое число P равно 0 и 1.

3С. Мороженое

Конечно, можно использовать циклы, пытаясь набрать требуемое количество тройками и пятерками.

Но задача решается просто, если понять, что тройками и пятерками можно набрать любое число большее семи! Это несложно доказать. Разделим данное число на 3 с остатком. Если получился остаток 0 – все готово. Если остаток 1 - заменим три тройки двумя пятерками. Если 2 – две тройки одной пятеркой.

Таким образом, ответ «NO» получается только в случаях 1, 2, 4 и 7 шариков. В остальных случаях ответ «YES».

3D. Автобусы

Во-первых, нужно учесть, что К может принимать значение меньше или равное 2. В этом случае следует выводить 0, потому, что в каждый автобус мы будем вынуждены посадить взрослых (а дети так и не уедут).

Теперь рассмотрим случай когда К больше двух: в этом случае нужно будет N/(K-2) автобусов для перевозки детей.

Заметим, что если N не делится нацело на K-2, то автобусов понадобится на один больше.

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

Во всех остальных случаях ответом будет (M+N)/K, но если M+N не делится нацело на K, то на один автобус больше:

// ...выше рассматриваются все особенные «NO» случаи
else 
{	
     res = (M + N) / K;
     if ((M + N) % K != 0) res++;
     out.print(res);
}

3E. Количество нулей

Просто добавим в рассмотренный в тексте занятия цикл увеличение счетчика, если очередная цифра – ноль:

 
   ...
c = x % 10; 
// В переменной с очередная цифра – 
// делаем что-нибудь с ней...
if (c == 0) nZeros++;

3F. Обращение числа Будем использовать цикл получения цифр, как описано в занятии.

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

До цикла заводим переменную res

// int res = 0;
// ...
// В переменной с очередная цифра – 
// прибавляем ее справа к res
   res = res * 10 + c;
// ...

3G. Минимальный делитель

Будем в цикле последовательно перебирать все делители, начиная с двойки. Как только найдем – выйдем из цикла:

// ... d «пробегает» в цикле значения от 2 до N
   if (N % d == 0) break;

и в конце напечатаем d.

Заметим, что правильное d будет найдено в любом случае, ведь любое число делится хотя бы на само себя. Эта программа будет работать долго, если дано простое число – поиск пройдет до него. Можно это оптимизировать так, как разбирается в тексте занятия - перебирать возможные делители до корня из N, и если не нашли – сразу выводить N. Однако тесты к задаче позволяют получить «ОК» и без такой оптимизации.

3H. Почти простые числа

Запустим цикл по поиску нетривиальных делителей, который разбирается в тексте занятия. В нем будем считать количество найденных делителей (Nd).

Nd++;
if (N / d != d) Nd++; // если парный делитель не совпадает с делителем

Из основной теоремы арифметики следует, что если число раскладывается в произведение двух простых, то только их мы и найдем. Если насчитали 2 – «YES», иначе – «NO».

3I. Полярные единички

Заметим, что Тогда можно вычислять остатки последовательно:

В начале m = 1 (остаток от деления единицы на N), e = 1 (количество единичек).

Дальше в цикле

m = (m * 10 + 1) % N; 

и будем считать количество добавленных единичек (e++).

Когда заканчивать цикл? Как только m станет равно нулю. А если это никогда не произойдет? Но остатков конечное число – всего p. Сделаем операцию p раз. Если мы ни разу не встретили ноль, значит, серии остатков начали повторяться! В этом случае нужно вывести ответ «NO». Если же мы получили ноль – еще в одном цикле просто выводим e единичек.

3J. Разложение на простые++

Это технически сложная задача. В цикле разложения на простые нужно накапливать степень и выводить ее вместе со знаком «^». Нужно учесть, что первая степень не выводится. И после последнего множителя не ставится знак умножения. Ограничения задачи вынуждают оптимизировать цикл в случае больших простых.