e-olymp 419. Задача 3n + 1

Задача

Рассмотрим следующий алгоритм генерации последовательности чисел:

Например, для [latex]n[/latex] = 22 будет сгенерирована следующая последовательность чисел:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Полагают (но это еще не доказано), что этот алгоритм сойдется к [latex]n[/latex] = 1 для любого целого [latex]n[/latex]. По крайней мере, это предположение верно для всех целых [latex]n[/latex], для которых 0 < [latex]n[/latex] < 1,000,000.

Длиной цикла числа n будем называть количество сгенерированных чисел в последовательности включая 1. В приведенном примере длина цикла числа 22 равна 16.

Для двух заданных чисел [latex]i[/latex] и [latex]j[/latex] необходимо найти максимальную длину цикла среди всех чисел между [latex]i[/latex] и [latex]j[/latex] включительно.

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

Каждый тест задается в отдельной строке и содержит пару целых чисел [latex]i[/latex] и [latex]j[/latex]. Входные числа будут меньше 1000000 и больше 0. Считайте, что для вычислений достаточно использовать 32 битный целочисленный тип.

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

Для каждой пары чисел [latex]i[/latex] и [latex]j[/latex] выведите числа [latex]i[/latex] и [latex]j[/latex] в том же порядке, в каком они поступили на вход. После чего выведите максимальную длину цикла среди всех целых чисел между [latex]i[/latex] и [latex]j[/latex] включительно. Для каждого теста три числа следует выводить в отдельной строке, разделяя одним пробелом.

Тесты

Входные данные Выходные данные
1 10
100 200
201 210
900 1000
1 10 20
100 200 125
201 210 89
900 1000 174
1 10
10 1
1 10 20
10 1 20
5 25
70 54
38 250
5 25 24
70 54 113
38 250 128

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

Решение задачи

Алгоритм, описанный в условии задачи используется для построения сиракузской последовательности. Интересный факт — какое бы число не взять, в конце получаем единицу. Нам же надо посчитать сколько раз должен сработать алгоритм для подсчитывания «длины цикла». Считывая пару чисел из потока ввода я высчитывал «длину цикла» для каждого числа из заданного введенной парой промежутка. После чего сравнивал количество итераций для каждого такого числа и находил максимальное. И так для каждой пары чисел.

Ссылки

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

e-olymp 108. Среднее число

Задача

Дано три различных числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]. Вывести среднее из них.

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

Числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] целые и по модулю не превышают 1000.

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

Вывести среднее среди трех чисел.

Тесты

Входные данные Выходные данные
10 4 9 9
2 256 8 8
1 2 3 2

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

Решение задачи

Я рассмотрел все возможные случаи, а именно 2 на каждую переменную, в которых она может оказаться «средней», удовлетворяя условию. [latex]a[/latex] средняя, если она лежит между [latex]b[/latex] и [latex]c[/latex] или между [latex]c[/latex] и [latex]b[/latex], [latex]b[/latex] если она лежит между [latex]a[/latex] и [latex]c[/latex] или между [latex]c[/latex] и [latex]a[/latex], и [latex]c[/latex] — остальных случаях.

Ссылки

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

e-olymp 2059. Озеро с лилиями

Задача

На лесном озере начали цвести лилии. В первый день расцвела одна лилия, а потом каждый день количество цветущих лилий удваивалось. На [latex]n[/latex]-ый день всё озеро было покрыто цветущими лилиями. А на какой день была покрыта цветущими лилиями половина поверхности озера?

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

Номер дня [latex]n[/latex](1 < [latex]n[/latex] ≤ 200), на который вся поверхность озера была покрыта цветущими лилиями.

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

День, на который была покрыта лилиями половина поверхности озера.

Тесты

Входные данные Выходные данные
3 2
4 3
185 184

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

Решение задачи

Так как количество лилий увеличивалось вдвое с каждым днем, то половина поверхности озера была покрыта лилиями на предпоследний день [latex](n — 1)[/latex].

Ссылки

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