e-olymp 1142. Деление на ноль или…

Задача

Как известно, делить на ноль нельзя. А может еще на что-то делить нельзя? Это Вам и предстоит выяснить.

Входные данные

В единственной строке задано два целых знаковых 32-битовых числа $a$ и $b$.

Выходные данные

Выведите значение частного, полученного в результате деления $a$ на $b$. Если деление произвести невозможно, вывести ERROR.

Тесты

Входные данные Выходные данные
1 8 4 2
2 6 0 ERROR
3 0 4 0
4 613 18 34
5 9197 10000 0

Код

Решение

В задаче, единственной невозможной операцией является деление на ноль. Это условие можно проверить с помощью условных операторов if и else. Также, так как $a$ и $b$ являются целыми 32-битными числами, необходимо использовать тип переменных long.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

e-olymp 8680. Чётные соседи

Условие задачи

Задана последовательность целых чисел. Подсчитать количество элементов, у которых чётные соседи.

Входные данные

В первой строке задано количество элементов последовательности $n$ $(n \leqslant 100)$. Во второй строке заданы сами элементы, значение каждого из которых по модулю не превышает $100$.

Выходные данные

Вывести в одной строке количество элементов последовательности с чётными соседями.

Тесты

Входные данные Выходные данные
1 6
1 2 3 4 5 6
2
2 9
3 6 3 5 2 9 1 2 5
0
3 3
2 1 2
1
4 6
13 24 54 66 44 77
2
5 4
100 224 666 222
2

Программный код

Решение

Идея решения задачи состоит в том, чтобы создать три переменные: $prev$ (предыдущий), $pres$ (настоящий, текущий) и $fut$ (будущий). Затем в цикле мы перезаписываем эти переменные т.е.: настоящий становится прошлым, будущий настоящим, а новый будущий мы читаем из cin. Так же, в ходе решения задачи обнаружилась проблема с чтением количества элементов. Допустим, если мы записали, что $n=6$, а дальше ввели $10$ элементов, то количество элементов с чётными соседями будет считаться для $10$ элементов. Чтобы избежать этого мы ограничиваем количество читаемых элементов с помощью счётчика i++ и цикла while.

Ссылки

e-olymp 4439. Возведение в степень

Задача

Вычислить значение $a^b$.

Входные данные

Два натуральных числа $a$ и $b$.

Выходные данные

Выведите значение $a^b$, если известно что оно не превосходит $10^{18}$.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 1 100 1
 2 2 10 1024
 3 3 7 2187
 4 8 9 134217728
 5 10 10 10000000000
 6 100 9 1000000000000000000

Код

Решение

Для решения задачи создадим функцию «pow()», заметим, что для любого числа $a$ и чётного числа $b$ выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
$$a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$$
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного $b$ мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень b нечётна. Здесь мы поступаем очень просто: перейдём к степени b-1, которая будет уже чётной:
$$a^b = a^{b-1} \cdot a$$
Итак, мы фактически нашли рекуррентную формулу: от степени $b$ мы переходим, если она чётна, к $\frac{b}{2}$, а иначе — к $b-1$.

Примечание

Задача требует использование быстрого алгоритма, так как прямое умножение $b$ раз для возведение в $b$-ю слишком медленно, из-за большого количества перемножений. Алгоритм быстрого возведения в степень — это предназначенный для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени.

Ссылки

Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp

e-olymp 8891. Ровно одно условие из двух

Задача

Для заданного целого числа $n$ вывести YES, если выполняется ровно одно из следующих условий и NO в противном случае.

  • число $n$ четное.
  • число $n$ отрицательное и кратное трем.

Входные данные

Одно целое число $n$.

Выходные данные

Вывести YES или NO в зависимости от выполнения условий.

Тесты

ВВОД ВЫВОД
 22  YES
 7  NO
 -30  NO
 -9  YES
 0  YES

Код

 

Решение

Если оба условия выполняются или оба не выполняются, то нужно вывести «NO», а иначе  — «YES».

  • В первом случае проверяем четность числа $n$.
  • Во втором случае проверяем кратность трем и является ли $n$ отрицательным.
  • В обеих случаях исключаем варианты, когда оба условия могли бы выполнятся, то есть исключаем отрицательные числа и кратность трем для первого, и четность числа для второго случая.

Ссылки

e-olymp
ideone

e-olymp 8663. Задача про множення

Задача

На уроці математики Байтик навчився множити, і почав застосовувати цю операцію з різними числами. Наприклад, розкладав число на цифри і знаходив добуток цифр. І тут він задумався, який найбільший добуток цифр серед натуральних чисел, що не перевищує [latex]N[/latex]. Допоможіть розв’язати задачу.

Вхідні дані

Одне число [latex]N(1\leqslant N\leqslant 2\times 10^{9})[/latex].

Вихідні дані

Максимальний добуток цифр серед чисел, що не перевищують [latex]N[/latex].

Тести

Вхідні дані Вихідні дані
57 36
1000 729
7999 5103
28994 10368
4876 2268

 

Код програми

Алгоритм

Складність задачі полягає в обмеженості у часі.

  1. Знайдемо добуток цифр заданого числа.
  2.  Змінемо останню цифру на [latex]9[/latex] та віднімемо [latex]1[/latex] від попереднього розряду. Визначаємо поточний добуток цифр отриманого числа. Повторюємо цю операцію з наступними розрядами числа.
  3. Порівнюємо поточний добуток з максимальним.

Приклад:

Приклад розкладу числа на різних етапах алгоритму:

 

Посилання

Задача на e-olymp
Зарахований розв’язок
Код на ideone

 

e-olymp 8352. Такси

Условие задачи

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

Входные данные

Три натуральных числа, не превосходящих $100$ — количество пассажиров в первой, второй и третьей маршрутках соответственно.

Выходные данные

Выведите одно число — наименьшее количество пассажиров, которое требуется пересадить. Если это невозможно, выведите слово IMPOSSIBLE (заглавными буквами).

Тесты

Ввод Вывод
1 1 2 3 1
2 6 7 4 IMPOSSIBLE
3 18 10 2 8
4 54 10 96 IMPOSSIBLE
5 27 27 27 0

Код программы

Решение

Мы сможем рассадить пассажиров поровну в три маршрутки только тогда, когда их общее количество кратно трем. Если это условие не выполняется, выводим на экран слово IMPOSSIBLE.

Иначе вычисляем среднее арифметическое исходного количества пассажиров каждой маршрутки по формуле: $\frac{b_{1}+b_{2}+b_{3}}{3}$ и находим минимальное количество пересаживаемых пассажиров, суммируя только положительные отклонения от среднего арифметического.

Ссылки

e-olymp 365. Рамка

Задача

Василий и Петр игрались на уроке. На прямоугольном листке бумаги в клеточку Василий по линях сетки рисует отрезок, параллельный одной из сторон листка, и рамку прямоугольной формы. Он шепчет на ухо Петру координаты концов отрезка и координаты двух противоположных углов рамки, а Петр старается быстро определить длину части отрезка, оказавшуюся внутри рамки. У него это плохо получалось, и он написал программу, которая это делала всегда правильно. Напишите её и вы.

Входные данные

Заданы через пробел $8$ чисел — координаты начала и конца отрезка и координаты противоположных углов рамки. Координаты — целые числа, не превышающие по модулю $35000$.

Выходные данные

Вывести одно число — длину части отрезка, которая оказалась внутри рамки.

Тесты

Входные данные

Выходные данные

1 4 1 9 1 2 3 5 -2 1
2 2 2 6 2 4 4 7 1 2
3 3 2 3 5 4 3 6 2 0
4 1 2 5 2 2 5 4 1 2

Код программы

 

Решение

Так как отрезок параллелен одной из сторон листка, то абсциссы (или ординаты) концов отрезка должны совпадать. Будем рассматривать случай когда они находятся между абсциссами (или ординатами соответственно) соответствующих вершин прямоугольника (в противном случае отрезок не проходит через рамку и ответ $0$).Отрезок не проходит через рамку

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

В противном случае, отрезок проходит через рамку и мы можем подсчитать какая его часть находится внутри рамки. Для этого необходимо найти разность между абсциссами (ординатами) концов части отрезка находящийся внутри прямоугольника.  Абсциссой левого конца такого отрезка будет максимальная из абсцисс левого конца изначального отрезка и крайней слева абсциссы прямоугольника, абсциссой правого конца такого отрезка будет минимальная из абсцисс правого конца изначального отрезка и крайней справа абсциссы прямоугольника (для ординат аналогично).

Обозначим  искомую длину как $ans$, тогда $ans = min(x_{2}, x_{4})-max(x_{1}, x_{3})$.

Для ординат  $ans = min(y_{2}, y_{4})-max(y_{1}, y_{3})$.

Отрезок проходит через рамку

Ссылки

Условие задачи на e-olymp

Код программы на ideone

e-olymp 8283. Музыка

Задача

Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.

Малыши часто просили его научить играть на каком-нибудь инструменте. Гусля не отказывал, но сначала предлагал взять инструмент с первым номером, а если ученику хотелось играть на другом, то он выбирал шестой следующий по кругу и так далее. Напишите программу, которая определяла номер попытки, с которой ученик мог получить желаемый инструмент с номером $k$.

Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.

Входные данные

Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.

Выходные данные

Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.

Тесты

Входные данные Выходные данные
1 11 3 5
2 6 2 0
3 13 13 3
4 9 8 0
5 5 5 5

Код

Решение

Для решения задачи нам необходимо рассмотреть ряд натуральных чисел, начиная с единицы и прибавляя каждый раз $6$. С помощью операции деления с остатком мы можем реализовать алгоритм нахождения номера музыкального инструмента. Однако логика решения изменяется в зависимости от введенных пользователем данных. Имеется два случая:

  1. Если пользователь вводит разные числа.
  2. Если пользователь вводит одинаковые числа.

В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.

Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.

Ссылки

  • Условие задачи на e-olymp
  • Код программы на ideone.com
  • Засчитанное решение на e-olymp

e-olymp 7612. Алекс и квадраты оригами

Задача

Алекс любит оригами — японское искусство складывания из бумаги. Большинство конструкций оригами начинаются с квадратного листа бумаги. Алекс собирается сделать подарок для своей матери. Подарочная конструкция требует три одинаковых квадратных листа бумаги, но у Алекса имеется только один прямоугольный лист. Он может из него вырезать квадраты, стороны которых должны быть параллельны сторонам листа. Помогите Алексу определить максимально возможный размер квадратов, который он способен вырезать.

Входные данные

В одной строке два целых числа [latex] h [/latex] и [latex] w [/latex] [latex] \left ( 1\leqslant h,w\leqslant 1000 \right ) [/latex] — высота и ширина куска бумаги.

Выходные данные

Выведите одно действительное число — наибольшую длину стороны квадратов. Всегда можно вырезать три одинаковых квадрата из листа бумаги размером [latex] h \times w[/latex] так, чтобы их стороны были параллельны сторонам листа.
Ответ следует вывести с точностью не меньше трех десятичных знаков.

Тесты

Входные данные Выходные данные
30  11 10.0000
8  3 2.6667
210  297 105.0000
60  59 29.5000
250  100 83.3333

Программный код

Алгоритм решения`

Допустим, что [latex] w [/latex] всегда больше чем [latex] h [/latex] . Из условия следует, что варианта расположения данных квадратов два: . В первом случае ответом будет  [latex] \max\left ( \frac{h}{2}, \frac{w}{3} \right ) [/latex]. Во втором же, ответом будет [latex] h [/latex] .

Детали реализации

  • В первой версии программы используется тернарный оператор: ans = ( w >= 3 * h ? h : max (h / 2, w / 3) );
  • В обоих версиях программы имя метода max() становится видимым благодаря оператору статического импорта: import static java.lang.Math.max;. Также мы импортируем класс Scanner: import java.util.Scanner;
  • Для  вывода ответа с точностью не меньше трех десятичных знаков используется форматирование чисел с плавающей точкой.

Ссылки :
Задача на e-olymp
Код № 1 на ideone
Код № 2 на ideone
Засчитанное решение № 1
Засчитанное решение № 2

e-olymp 8893. Каждое условие из двух

Условие задачи

Для заданного целого числа $n$ вывести YES, если выполняется каждое из следующих условий и NO в противном случае.

  • Число $n$ кратное трем;
  • Число $n$ четное и двухзначное.

Входные данные

Одно целое число $n$.

Выходные данные

Вывести YES или NO в зависимости от выполнения условий.

Тесты

Входные данные Выходные данные
1 12 YES
2 27 NO
3 -12 YES
4 60  YES
5 10 NO
6 00000012 YES

Код

Решение

У нас дана целочисленная переменная $n$. Для решения данной задачи надо проверить выполняет ли переменная все условия чтобы выводилось YES.

  1. Для начала надо проверить является ли переменная двухзначным числом (то есть в диапазоне от 10 до 99 включительно). С отрицательными знаками делаем то же самое (от -10 до -99 включительно)
  2. Смотрим, является ли переменная кратной трем. Для этого остаток от деления переменной на три должен равняться нулю.
  3. Смотрим, является ли переменная четной. Для этого остаток от деления переменной на два должен равняться нулю.

Если выполняются все условия, то выводим YES, в остальных случаях NO. Задача решена

Ссылки

  • Задача на сайте e-olymp
  • Код решения Ideone