e-olymp 1290. Номерной знак

Задача

Международный номерной регистрационный знак легкового автомобиля состоит из $A$ арабских цифр и $B$ больших букв латинского алфавита. Будем считать, что для обеспечения уникальности номера разрешено использовать любую последовательность букв и цифр.
Сколько существует различных таких номеров?

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

В единственной строке через пробел $2$ неотрицательных целых числа $B$ и $A$. Оба числа не превышают $26$.

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

Единственное число — ответ к задаче.

Тесты

Входные данные Выходные данные
1 3 3 17576000
2 2 5 67600000
3 7 1 80318101760
4 1 1 260
5 26 26 615611958020715731079667428840020377600000000000000000000000000

Код

Решение

Начнем с того, что к условию задачи прилагается картинка, на которой видно, что во всех номерных знаках буквы и цифры не перемешаны между собой произвольно, а имеют свои четко распределенные места, в примере это последовательность, в которой на первой позиции стоит буква, далее три цифры и на последних двух позициях снова буквы. Это важный момент, поскольку если бы действительно было разрешено использовать любую последовательность, возможных комбинаций было бы гораздо больше. Поскольку в латинском алфавите $26$ букв, для выбора буквы на первое место существует $26$ возможных вариантов, на второе тоже $26$, как и на третье, четвертое и т. д. То есть для того чтобы найти все комбинации из букв для $B$ мест, нужно умножить $26$ на $26$ $B$ раз. Точно так же это работает с арабскими цифрами. Их всего $10$, соответственно, умножаем $10$ на $10$ $A$ раз, где $A$ — количество мест в номерном знаке для цифр. Поэтому, чтобы найти количество возможных комбинаций букв и цифр, перемножаем полученные результаты. Отсюда получаем формулу $26^B\cdot 10^A$.

Числа, возникающие при возведении в степень, слишком велики для типа long, поэтому в коде используется дополнительный тип для больших целочисленных значений из пакета java.math — BigInteger.

Следует также отметить, что домножение на $10^A$ осуществляется в последнем цикле приписыванием A нулей к полученному результату.

Ссылки

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

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 841. Спираль

Условие

Вывести квадрат, состоящий из $N \times N$ клеток, заполненных числами от $1$ до $N^{2}$ по спирали.

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

В первой строке находится единственное число $N (2 \leq N \leq 100)$.

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

Выводится $N$ строк по $N$ чисел, разделённых пробелами. Не допускается начинать спираль в ином, кроме верхнего левого, углу, закручивать спираль против часовой стрелки или изнутри наружу.

Тесты

Входные данные Выходные данные
1 3 1 2 3
8 9 4
7 6 5
2 4 1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
3 5 1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
4 10 1 2 3 4 5 6 7 8 9 10
36 37 38 39 40 41 42 43 44 11
35 64 65 66 67 68 69 70 45 12
34 63 84 85 86 87 88 71 46 13
33 62 83 96 97 98 89 72 47 14
32 61 82 95 100 99 90 73 48 15
31 60 81 94 93 92 91 74 49 16
30 59 80 79 78 77 76 75 50 17
29 58 57 56 55 54 53 52 51 18
28 27 26 25 24 23 22 21 20 19

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

Решение

Для того чтобы решить эту задачу нам нужно определить способ заполнения. Первым делом, если $N$ — нечетное, то находим центр матрицы и заполняем его числом $N \times N $ a[(n / 2)][(n / 2)] = (n * n);. В условии написано, что “Не допускается начинать спираль в ином, кроме верхнего левого углу, закручивать спираль против часовой стрелки или изнутри наружу.”, то есть начинать мы будем с верхнего левого угла. Для этого мы сделаем цикл for(int i = 0; i < (n / 2); i++); , в котором сделаем 4 такта. Каждый такт заполняет определенную часть матрицы:

    • 1 такт – заполняет верхнюю грань слева направо;
    • 2 такт – заполняет правую грань сверху вниз;
    • 3 такт – заполняет нижнюю грань справа налево;
    • 4 такт – заполняет левую грань снизу вверх, как показано на рисунке ниже.

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


Ссылки:
Задача на e-olymp
Код на OnlineGDB
Код на Ideone
Засчитанное решение на e-olymp

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

e-olymp 1780. Коды Грея

Задача

Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.

Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: «двоичный отражённый (рефлексный) код Грея». Именно этот код обычно имеется в виду, когда говорят о неконкретном «коде Грея».

Отображённый двоичный код Грея строится следующим образом. Начинаем со строк [latex]0[/latex] и [latex]1[/latex], которые представляют соответственно целые числа [latex]0[/latex] и [latex]1[/latex].

0
1

Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим [latex]1[/latex] слева от новых записей списка, а слева от уже имевшихся разместим [latex]0[/latex].

00
01
11
10

Таким образом получен отражённый код Грея для [latex]n = 2[/latex]. Чтобы получить код для [latex]n = 3[/latex], повторим описанную процедуру и получим:

000
001
011
010
110
111
101
100

При таком способе построения легко увидеть по индукции по [latex]n[/latex], что, во-первых, каждая из [latex]2^n[/latex] комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.

Для каждого заданного числа [latex]k[/latex] вывести десятичное значение [latex]k[/latex]-го кода Грея.

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

Во входном файле содержится некоторый набор тестовых данных, каждое число [latex]k (0 < k < 10^{18})[/latex] в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает [latex]10^5[/latex].

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

Для каждого заданного числа [latex]k[/latex] вывести в отдельной строке десятичное значение [latex]k[/latex]-го кода Грея.

Входные данные Выходные данные
1 3
14
5
12
2
9
7
10
2 10
50
15
43

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

Решение

Рассмотрим биты числа [latex]n[/latex] и биты числа [latex]G(n)[/latex]. Заметим, что [latex]i[/latex]-ый бит [latex]G(n)[/latex] равен единице только в том случае, когда [latex]i[/latex]-ый бит [latex]n[/latex] равен единице, а [latex]i+1[/latex]-ый бит равен нулю, или наоборот ([latex]i[/latex]-ый бит равен нулю, а [latex]i+1[/latex]-ый равен единице). Таким образом, имеем: [latex]G(n) = n \oplus (n>>1)[/latex], где [latex]\oplus[/latex] — операция «побитовое исключающее ИЛИ», а [latex]>>[/latex] — «побитовый сдвиг вправо».

Ссылки

Ссылка на e-olymp.
Ссылка на Ideone

e-olymp 143. Точка и треугольник

Точка и треугольник

Принадлежит ли точка [latex]O[/latex] треугольнику [latex]ABC[/latex]?

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

Содержит координаты точек [latex]O, A, B, C[/latex]. Числовые значения не превышают по модулю 100.

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

Вывести 1, если точка [latex]O[/latex] принадлежит треугольнику [latex]ABC[/latex] и 0 в противоположном случае.

Входные данные Выходные данные
1 2 6 -9 3 8 1 5 11 1
2 -13 10 -12 5 99 80 17 13 0
3 98 -50 -87 7 5 3 23 17 0
4 5 15 7 12 5 3 2 54 1
5 2 2 3 1 1 3 9 11 1

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

Решение

Для того, чтобы точка [latex]M[/latex] принадлежала треугольнику, заданному точками [latex]D([/latex]$x_{1}$,$y_{1}$[latex]), [/latex] [latex]E([/latex]$x_{2}$,$y_{2}$[latex]), [/latex][latex]F([/latex]$x_{3}$,$y_{3}$[latex]), [/latex] необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше либо равно нулю или же меньше либо равно нуля. Пользуясь формулой для косого произведения, запишем произведения векторов.
[$\overline{DE}$,$\overline{MD}$]=($x_{1}$-$x_{0}$) $\cdot$ ($y_{2}$-$y_{1}$)-($x_{2}$-$x_{1}$) $\cdot$ ($y_{1}$-$y_{0}$)
[$\overline{EF}$,$\overline{ME}$]=($x_{2}$-$x_{0}$) $\cdot$ ($y_{3}$-$y_{2}$)-($x_{3}$-$x_{2}$) $\cdot$ ($y_{2}$-$y_{0}$)
[$\overline{FD}$,$\overline{MF}$]=($x_{3}$-$x_{0}$) $\cdot$ ($y_{1}$-$y_{3}$)-($x_{1}$-$x_{3}$) $\cdot$ ($y_{3}$-$y_{0}$)
Если [$\overline{DE}$,$\overline{MD}$], [$\overline{EF}$,$\overline{ME}$] и [$\overline{FD}$,$\overline{MF}$] больше либо равно нулю или же меньше либо равно нуля, то точка принадлежит треугольнику.

 

Ссылки

Ссылка на Ideone
Ссылка на e-olymp

e-olymp 1610. Зайцы в клетках

Зайцы в клетках

Всем известен, так называемый, принцип Дирихле, который формулируется следующим образом:

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

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

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

В одной строке заданы два натуральных числа $n$ и $m$ $(1 ≤ n, m ≤ 10^{9})$.

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

Максимальное количество зайцев, которое гарантированно окажется в одной клетке.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
3 50 17
5 5 1
1070 589 1
20 150 8

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

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

Пусть $n$ — количество клеток, и $m$ — количество зайцев.
Найдем отношение $\frac{m}{n}$. Если это отношение больше либо равно единице то $m\geq n$ и мы имеем ответ. $\frac{m+n-1}{n}$ — это формула выводит ответ в целом виде, если он целый, и округляет в большую сторону, если он дробный. Иначе $m\leq n$ и максимальное гарантированное количество зайцев в одной клетке равно единице. Это следует из условия задачи.

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

e-olimp 57. Бабочка-санитар

Задача

e-olimp 57. Бабочка-санитар

e-olimp 57. Бабочка-санитар

Школьники, идя из дому в школу или наоборот — со школы домой, любят кушать конфеты. Но, как всегда, это приятное дело иногда имеет неприятные последствия – детки часто выбрасывают обертки на школьном дворе.
Мурзик всегда следил за чистотой школьного двора и ему в этом с радостью помогали бабочки, благодарные за прекрасные фотографии, сделанные им. Бабочки могли использовать собственные крылышки как линзы, причем они могли изменять их фокусное расстояние. Заметив обертку от конфетки, лежавшую на школьном дворе в точке с координатами $X_{1}$ $Y_{2}$, бабочка перелетала в точку с координатами $X_{2}$, $Y_{2}$, $Z_{2}$, расположенную на пути солнечных лучей к обертке и, изменяя фокусное расстояние своих крылышек-линз, сжигали обертку от конфеты.
Какую оптическую силу $D$ имели крылышки-линзы бабочки в этот момент?

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

В первой строке 2 числа: координаты $X_{1}$, $Y_{1}$ обертки от конфетки. Во второй – 3 числа: координаты $X_{2}$, $Y_{2}$, $Z_{2}$ бабочки в момент сжигания обертки.
Все входные данные целые числа, не превышающие по модулю 1000.

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

Единственное число – оптическая сила крылышек-линз D, вычисленная с точностью до 3-х знаков после запятой за правилами математических округлений.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
10 20
10 20 100
0.010
600 400
300 867 409
0.001
30 50
1000 1000 1000
0.001
60 21
11 44 -7
0.018

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

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

$F=\sqrt{(x-x_{1})^{2} + (y-y_{1})^{2} + z^{2}}$ — формула для нахождения расстояния между двумя точками пространства. По этой формуле находим фокусное расстояние между крыльями-линзами и бумажкой. Оптическая сила линзы $\frac{1}{F}$, где $F$ — фокусное расстояние.

Этой строкой кода мы выводим оптическую силу линзы с точностью до трех знаков после запятой.
Условие задачи на e-olimp
Код решения ideon

e-olymp 51. К-домино

Задача

ДоминоРаботник отдела технического контроля любил выбраковывать «доминошки», которые содержали одинаковые значения. Так как на предприятии, выпускающем [latex]K[/latex]-домино, этого не знали, к нему постоянно поступали претензии на сумму, равную стоимости [latex]K[/latex]-домино. Стоимость [latex]K[/latex]-домино составляла ровно столько гривен, сколько было в купленном покупателем наборе доминошек.Для того, чтобы его не уволили с работы, работник ОТК выбраковывал иногда не только все не любимые «доминошки», а несколько больше, но не более половины гарантированно выбраковыванных.Зная сумму претензии, пришедшей на предприятие, установите, какой из наборов [latex]K[/latex]-домино был куплен покупателем.

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

Единственное число [latex]S[/latex] – сумма претензии, пришедшей на предприятие, [latex]S ≤ 2000000000[/latex].

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

Единственное число – индекс [latex]K[/latex] купленного покупателем [latex]K[/latex]-домино.

Входные данные Выходные данные
1 5 3
2 10 4
3 1000000 1414
4 555666777888 1054198
5 13 5

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

Решение

[latex]K[/latex]-домино — набор домино с минимальным количеством точек на одной из половин доминошки.
Количество дублей, то есть количество точно выбракованных доминошек — [latex]k[/latex]+1. Общее количество доминошек [latex]k[/latex]-домино:$$(k+1){{k+2}\over{2}}$$
Пусть работник дополнительно выбраковывал [latex]e[/latex] доминошек. [latex]s[/latex] — сумма претензии, тогда имеем:

[latex]k+1+e+s= (k+1){{k+2}\over{2}}[/latex]  
[latex]k^2<=2s+1[/latex]  
[latex]k=[\sqrt{2s+1}][/latex]

Ссылки

Ссылка на e-olymp.
Ссылка на Ideone

e-olimp 7365

Ссылка на оригинал задачи

Задача «Молоко и пирожок»

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее 30 кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость 200 мл, а упаковки молока – 0.9 л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

Тесты:

Количество детей Вес Количество упаковок молока Количество пирожков
3 30 29 30 1 1
5 25 41 56 20 20 1 3
4 30 30 30 30 0 0
7 25 26 27 28 29 23 24 2 7

Код:

Алгоритм:

  1. Объявление и ввод значений переменных.
  2. Используем цикл for для подсчета необходимого количества пирожков.
  3. На основе предыдущих данных и округления в большую сторону (метод  Math.ceil ), подсчитываем необходимое количество пакетов молока.
  4. Окончание работы программы.

Работающая версия программы на Ideone.com

Ссылка на источник