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

Задача

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

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

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

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

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

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

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

Для каждой пары чисел [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

А410е

Задача

Дана целочисленная матрица $ [a_{ij}], ij=1,\ldots,n.$ Получить $b_{1} \dots b_{n},$ где $b_{i}$ — это $\underset{1\leq j\leq n}{\max a_{ij}}\cdot \underset{1\leq j\leq n}{\min a_{ji}}$

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

Первая строка содержит число $n.$ Следующие строки содержат матрицу $n\times n.$

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

Вывести $b_i \; i=1\dots n.$

Тесты

Входные данные Выходные данные
2
1 2
4 1
2 4
3
1 2 3
4 1 -6
1 -2 -1
3 -8 -6

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

Решение

Очевидно, что из заданной матрицы нужно взять максимальный элемент $i$-й строки и умножить его на минимальный элемент $i$-го столбца. Для нахождения максимума [latex]a_{ij}[/latex], введем переменную и будем присваивать ей начальное значение первого элемента $i$-й строки. Чтобы при расчете максимума проходя по элементам строки мы не сравнивали каждый $i$-й элемент с первым, присваивать начальное значение максимуму будем в цикле по $i$. Аналогично с минимумом, но начальное значение минимума будет равно первому элементу $i$-го столбца.

Ссылки

Условие задачи
Код решения

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

Задача

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

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

В одной строке два целых числа $h$ и $w$ $(1 \leq h,w\leq 1000)$ — высота и ширина куска бумаги.

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

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

Ответ следует вывести с точностью не меньше трех десятичных знаков.

Тесты

Входные данные Выходные данные
$100$ $100$ $50.000$
$10$ $80$ $10.000$
$50$ $76$ $25.333$
$60$ $27$ $20.000$
$8$ $3$ $2.667$

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

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

Существует два варианта оптимального расположения трех квадратов — три в один ряд,

или же два, соприкасающихся одной стороной, и третий над ними

Обозначим за $a$ меньшую сторону листа бумаги, а за $b$ — большую. Если a не больше $\frac{b}{3}$, то оптимальным расположением квадратов в прямоугольнике будет первый вариант, а наибольшей возможной стороной квадратов является меньшая сторона листа бумаги $a$. В противном случае рассмотрим два варианта:

  1. Если $\frac{a}{2} < \frac{b}{3}$, то квадраты будут располагаться в прямоугольнике первым способом, и ответом будет служить число $\frac{a}{2}$.
  2. Иначе квадраты будут располагаться в прямоугольнике вторым способом, и ответом будет служить число $\frac{b}{3}$.

Таким образом, в случае $a > \frac{b}{3}$ ответом будет служить большее из двух чисел $\frac{a}{2}$ и $\frac{b}{3}$. Mинимальное из $\max \left(\frac{a}{2},\frac{b}{3} \right)$ и $a$ число и будет ответом.
Проверим нашу формулу:если $a < \frac{b}{3}$, то $\max \left(\frac{a}{2},\frac{b}{3} \right) = \frac{b}{3}$, и тогда $\min \left( a,\max \left(\frac{a}{2},\frac{b}{3} \right) \right) = a$. Иначе $\min \left( a,\max \left(\frac{a}{2},\frac{b}{3} \right) \right) = \max \left(\frac{a}{2},\frac{b}{3}\right)$, что нам и требуется.

Ссылки

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

e-olymp 7368. Средний балл для фигуристов

Задача


Спортсменам-фигуристам [latex]n[/latex] судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей [latex](0 < n \leqslant 10, 0 < m \leqslant 100)[/latex] для каждого из фигуристов.

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

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

Тесты

# Входные данные Выходные данные
1 5 4
7 8 9 8 10
6 5 5 4 7
9 9 10 7 7
7 7 10 9 8
8.33 5.33 9.00 8.50
2 6 3
6 7 6 5 4 3
9 8 5 5 6 5
7 6 4 1 2 2
5.25 7.00 3.50
3 4 5
6 7 8 6
9 8 5 4
7 6 7 5
4 3 9 3
7 8 7 6
7.00 6.50 6.00 4.00 7.00
4 4 4
7 7 2 3
9 8 3 3
5 4 9 7
4 3 2 6
3.00 8.00 6.00 3.50
5 8 5
4 5 6 7 7 4 9 8
3 5 6 6 7 8 5 9
7 6 3 9 3 7 9 7
5 6 4 3 7 7 5 7
9 8 4 6 7 9 9 4
6.60 6.17 6.75 5.00 7.00

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

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

Для решения задачи нам необходимо изъять все минимальные и максимальные значения в каждой строчке. Переменные [latex]a[/latex] и [latex]b[/latex] — это количество вхождений максимума и минимума соответственно. Берем любой элемент строки, который обозначили переменной [latex]x,[/latex] и будем считать, что он минимальный и максимальный. Далее сравниваем элементы между собой и находим максимум и минимум и подсчитываем их количество. Ещё нам необходимо посчитать сумму оставшихся значений, а также их количество по формуле [latex]n — a — b.[/latex] А затем вычисляем среднее арифметическое для оставшихся значений по формуле [latex]\displaystyle\frac{sum}{n — a — b}[/latex] и выводим результат.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

A406

Задача

С помощью x_{ij}, i=1,2; j=1,\ldots,n. – действительной матрицы на плоскости задано n точек так, что x_{1j}, x_{2j} – координаты j – точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n Матрица x_{ij}, i=1,2. Длина наибольшего отрезка  Комментарий
3 2 8 4

9 1 5

10 Пройдено
4 6 14 2 1

9 3 8 0

13.3417 Пройдено
5 1 8 4 3 7

2 9 5 0 11

11.7047 Пройдено

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

 

Ход решения:

  1. Вводим матрицу.
  2. Находим длину наибольшего отрезка.
    С помощью вложенных циклов мы находим длины всех отрезков по формуле
     AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}).
  3. По алгоритму нахождения максимума находим длину наибольшего отрезка.
  4. Выводим матрицу.
  5. Выводим длину наибольшего отрезка.
    Ссылка на код