e-olymp 8357.Точка в многоугольнике

Задача взята с сайта e-olymp

Условие

Как известно, простой многоугольник — это фигура, состоящая из непересекающихся отрезков («сторон»), соединённых попарно с образованием замкнутого пути. По заданному простому многоугольнику и точке требуется определить, лежит ли эта точка внутри или на границе этого многоугольника или вне его.

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

В первой строке заданы три числа: [latex]n (3 \leq n \leq 10^5)[/latex] и координаты точки. Далее в [latex]n[/latex] строках заданы по паре чисел — координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

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

Вывести строку «YES«, если заданная точка содержится в приведённом многоугольнике или на его границе, и «NO» в противном случае.

Тесты

  Inputs Outputs
1 3 0 0
1 0
0 1
1 1
       NO
2 4 3 2
0 0
1 5
5 5
6 0
      YES
3 8 2 1
0 0
0 4
4 4
4 0
3 0
3 2
1 2
1 0
       NO
4 8 4 3
0 0
0 4
4 4
4 0
3 0
3 2
1 2
1 0
      YES
5 6 1 1
0 0
0 2
1 4
2 2
2 0
1 3
       NO

Код

 

Решение

Проверять на то, находится ли точка внутри многоугольника, будем так:

Берём нашу точку и от нее проводим луч влево паралельно оси абсцис .

Считаем количество пересечений луча со сторонами многоугольника.

Если количество пересечений чётно, то точка лежит вне многоугольника , а если количество пересечений нечётно, то точка лежит внутри многоугольника.

Нужно еще учесть момент, когда точка лежит на одной из сторон.

x0, y0 — координаты нашей точки.

xs, ys -координаты самой первой точки , они нам нужны чтобы проверить пересечение луча со стороной, образованной первой и последней точками.

xi, yi- координаты точки которую вводим.

xt, yt- координаты предыдущей точки, нужны для того, чтобы образовать сторону.

par_am- parity of amount. хранит четность количества пересечений луча со сторонами. Если чётное количество пересечений, то par_am = false, если нечётное, то  par_am = true .

on_side — если мы узнали, что точка лежит на одной из сторон, то дальше ничего искать не нужно.

Метод on_edge рассматривает два случая:

  1. Если сторона паралельна оси [latex]Oy[/latex], посчитаем условие нахождения между минимальной и максимальной [latex]у[/latex]-  координатами. Если оно справедливо, проверяем на равенство [latex]x[/latex] -координат .
  2. Для удобства мы подвинет отрезок и точку так чтоб начало отрезка лежало в точке [latex](0,0)[/latex]. После это проверяем находится ли точка по координате [latex]x[/latex] между концов (включительно) отрезка. Остается сравнить тангенс угла между осью [latex]Ox[/latex] и вектором x2, y2 с тангенсом угла между осью [latex]Ox[/latex] и вектором  x, y и если они равны, то точка  x, y лежит на отрезке (стороне) x1, y1 ,x2, y2.

Считываем первую точку. Запоминаем.

Дальше считываем по точке, которая вместе с предыдущей образует сторону. Делаем проверку:

  1. Лежит ли точка x0, y0 на этой стороне.
  2. Пересекает ли луч сторону.

Чтобы проверить пересекает ли луч сторону делаем:

  1. Проверяем лежат ли две точки по разные стороны луча
  2. Строим уравнение прямой вида [latex]y = kx +b[/latex], проходящее через две точки ( xi, yi, xt, yt) выглядит оно так:
    [latex]y = (y_i-y_t) / (x_i-x_t) \cdot x+(y_i-(y_i-y_t) / (x_i-x_t) \cdot x_i )[/latex]
  3. Подставив вместо y y0, получаем что x равен
    [latex](y_0 \cdot x_i-y_0 \cdot x_t+y_i \cdot x_t-x_i \cdot y_t) / (y_i-y_t)[/latex]
    И он должен быть меньше  x0, так как луч направлен влево.

Ссылки

ideone
e-olymp

Руслан Масальский

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

e-olymp 8376. Рамка

Задача

prb8376.gifРамка $x × y$ представляет собой прямоугольник $x × y$, из середины которого вырезали прямоугольник размером $(x — 2) × (y — 2)$. У нас имеется неограниченный запас плиток $a × 1$. Можно ли полностью замостить рамку $x × y$ плитками $a × 1$?

Например, рамку $5 × 6$ можно замостить плитками $3 × 1$, но нельзя плитками $4 × 1$.

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

Первая строка содержит два натуральных числа $x$ и $y (3 ≤ x, y ≤ 10^6)$. Вторая строка содержит количество типов плиток $n (1 ≤ n ≤ 1000)$. Третья строка содержит n натуральных чисел, не больших $10^6$ — длины плиток.

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

Выведите n строк, содержащих YES или NO. i-ая строка содержит YES если можно замостить рамку плитками i-го типа. Выведите NO иначе.

Тесты

Ввод Вывод
1 5 6
2
3 4
YES

NO

2 18 5
2
6 3
NO

YES

3 3 3
1
1
YES
4 200 4
3
2 3 4
YES

NO

NO

5 1000000 1000000
5
100000 2 1689 11 9004
NO

YES

NO

YES

NO

Код

Решение

Рассмотрим три случая размещения плиток. Для примера возьмем входные данные c e-olymp — $5 × 6$.

Обратим внимание, что ширина плитки равна одному. 

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

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

Третий случай. На рисунке длина плитки равна трём. Плитки укладываются тут не от края до края, а оставляя уголки рамки свободными. Так получаем, что длина рамки минус две единицы (уголки) кратна длине плитки. Ширина тоже кратна длине плитки, но только в полном размере.

Заметим, что если длина плитки будет равна двум, из таких плиток можно сложить рамку любых размеров. Этот случай вынесем отдельно.

Ссылки

Задача на e-olymp

Код задачи на Ideone

e-olymp 8357. Точка в многоугольнике

Задача

Как известно, простой многоугольник — это фигура, состоящая из не пересекающихся отрезков («сторон»), соединённых попарно с образованием замкнутого пути. По заданному простому многоугольнику и точке требуется определить, лежит ли эта точка внутри или на границе этого многоугольника или вне его.

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

В первой строке заданы три числа: [latex]n (3 \le n \le 10^5)[/latex] и координаты точки. Далее в $n$ строках заданы по паре чисел — координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

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

Вывести строку «YES», если заданная точка содержится в приведённом многоугольнике или на его границе, и «NO» в противном случае.

Тесты

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

1 0

0 1

1 1

NO
4 3 2

0 0

1 5

5 5

6 0

YES
3 5 6

2 3

8 0

-1 -3

NO
4 -2 3

0 0

5 0

0 6

3 3

 

NO
5 3 1

9 2

3 0

-2 -4

-4 0

-4 5

 

YES

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

 

Решение

Задача сводится к поиску площадей:

1)Считаю площадь многоугольника векторным произведением.

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

3) Суммируем площади.

4)Если сумма равна настоящей площади, то точка внутри многоугольника, нет — снаружи.

Ссылки

e-olymp

ideone

 

e-olymp 479. Вышивка “крестиком”

Задача взята с сайта e-olymp.

Задача

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

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

Сначала кол-во макетов, потом их номера. Все номера узоров у Вали имели одну странность — всегда были нечетными и не превышали 80.

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

Макеты, в порядке, перечисленном во входном файле, разделенные пустой строкой.

Тесты

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

1

2 3 5 X X
 X
X X

X   X
 X X
  X
 X X
X   X

2

1 9 X       X
 X     X
  X   X
   X X
    X
   X X
  X   X
 X     X
X       X

Код

 

Решение

В данной задаче будем использовать потоковую обработку. Сначала считываем количество макетов [latex] n [/latex]. Затем в цикле for (int l = 0; l < n; l ++);   считываем номера узоров.  Выводить [latex] X [/latex] будем по диагоналям (справа налево и наоборот). Однако, стоит учесть, что после последнего символа [latex] X [/latex] в строке, выводить пробел не стоит. В условии задачи данный факт не фигурирует, однако, если же сделать иначе, то задача на сайте e-olymp не пройдет. Из этого вытекает, что пробелы должны располагаться исключительно до последнего крестика в строке. Для этого во внутреннем цикле ставим соответсвующее условие, чтобы при достижении последнего крестика в строке осуществлялся переход на другую строку, если это возможно. Также стоит не забыть, что между разными узорами нужно пропускать строку.

Ссылки

Засчитанное решение на e-olymp.

Код в ideone.

e-olymp 1325. Васькины дорожки

Задача. Васькины дорожки

Кот Василий узнал, что у соседа Димы, проживающего от него через какое-то количество заборов завелись мыши. Так как в своём хозяйстве всех мышей он уже давно выловил, кот отправляется на охоту за мышами к соседу, пролезая через дыры в ограде. На каждом участке Василий, как любой воспитанный кот, перемещается по уже проложенным там тропинкам. В деревне Старые Васюки, где проживает Василий, всего одна улица и та протянулась вдоль реки, поэтому домики расположены только по одну сторону улицы. Известно, что между любыми соседними участками в заборе ровно одна дыра. Сколькими способами Василий может попасть на участок Димы, если известно, что Дима проживает на участке под номером $k,$ а сам Василий проживает на участке под номером $m$?

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

В единственной строке находятся через пробел сначала количество домов в деревне $n,$ затем номер участка Василия $m,$ номер участка Димы $k,$ а далее $n$ чисел, обозначающее количество тропинок, ведущих либо к дыре в заборе, либо от дыры в заборе, либо между дырами в заборе соседей $i$ и $i+1.$ Все входные данные натуральные числа, не превышающие $10.$

 

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

Единственное число — количество различных способов для Василия попасть на нужный участок для охоты.

Тесты

Ввод Вывод
1 3 2 3 4 5 3 15
2 10 5 7 1 2 3 4 5 6 7 8 9 10 210
3 4 2 1 3 4 7 8 12
4 10 8 8 1 9 6 7 5 3 8 2 4 10 2
5 1 1 1 1 1
6 10 1 10 1 1 1 1 1 1 1 1 1 10 10
7 7 5 3 2 2 2 4 4 4 5 32
8 10 1 10 10 10 10 10 10 10 10 10 10 10 10000000000
7 5 3 2 1 2 3 4 5 6 7 8 9 10 6

Решение

Что бы определить количество различных способов попасть на нужный участок мы должны, сначала, посчитать сколькими способами кот Василий может пересечь (по тропинкам) участок на котором он находится. Затем, для каждого из возможных вариантов пересечения первого участка посчитать сколькими способами Василий может пересечь второй участок и так далее, до заданного. Таким образом общее количество вариантов попасть, для нашего друга, из участка $m$ в участок $k$ является произведением количества вариантов пересечения каждого участка в отдельности.

Прочтём значения $n$, $m$ и $k$. Переменная rez будет хранить результат. В цикле от $1$ до наибольшего номера из участков Димы и Василия, будем проверять достигли ли мы наименьшего номера их участков. По достижении начинаем перемножать количества тропинок ведущих к дыркам в заборе. Мы можем это делать с начиная с любого из участков так как операция умножения коммутативна. Завершив цикл в переменной rez у нас уже будет правильный ответ. Выведем его.

Типа данных  unsigned long хватит по условию данной задачи, так как все числа натуральные, а значит большие $0$. И не превышают $10$, следовательно максимальное значение переменной  rez будет $10^{10}$ что помещается в unsigned long.

Код

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

Решение

Код на ideone

e-olymp 1118. Арбузы

Задача

Иван Васильевич пришел на рынок и решил купить два арбуза: один для себя, а другой для тещи. Понятно, что для себя нужно выбрать арбуз потяжелей, а для тещи полегче. Но вот незадача: арбузов слишком много и он не знает, как же выбрать самый легкий и самый тяжелый арбуз. Помогите ему!

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

В первой строке задано количество арбузов $n$ $(n ≤ 30000)$. Вторая строка содержит $n$ чисел, каждое из которых задает массу соответствующего арбуза. Все массы арбузов натуральные и не превышают $30000$.

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

Вывести два числа: массу арбуза, который Иван Васильевич купит теще, и массу арбуза, который он купит себе, или вывести сообщение «$Ooops!$» (без кавычек), если кто-то останется без арбуза.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5
3 5 8 4 6
$3$ $8$
2 8
6 12 9 5 8 15 7 10
$5$ $15$
3 1
10
$Ooops!$

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

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

Из потока данных, где $n$ чисел найдём минимальное и максимальное число. Если $n<2$, то кто-то останется без арбуза, поэтому выведем «$Ooops!$» (без кавычек).

Ссылки

Условие задачи на E-Olymp

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

e-olymp 8358. Среднее значение — 1

Задача

Проект «Средний вес школьника школы» решили выполнить Мамед с Самедом. Что они будут делать с этим числом, они не раскрывают. Они попросили взвеситься всех учеников школы и занесли результаты в таблицу. Помогите им подсчитать средний вес учеников. Но они просят, чтобы учеников с самым большим и с самым маленьким весом не учитывать. Единственное их упущение, они не подсчитали общее количество учеников, но это, конечно, не помешает вам подсчитать то, что они просят.

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

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

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

Средний вес учеников школы без учета учеников с самым большим и самым маленьким весом. Ответ выводить с точностью до килограмм.

Тесты

Входные данные Выходные данные
40   23 27

59 68 23    84   27

53 46

46
5 5 5 5 5 5 5 5 5 5 6 6 5 6 5 6 6 5 6

5  6 5 5 5 5  5  5

5 5 6 6 5 6 8

6
                        1

3

3          4         5 4        6 10

4                    58

5
1 2 0
50 51 52 53 54 55 56 57 58 59

40 34  32

90 91 92 93 94 95 96 97 98 99

70
5 5 5 5 5 5 5 5 5 5 6 6 5 6 5 6 6 5 6

5  6 5 5 5 5  5  5

5 5 6 6 5 6

0
80 99 81 98 82 97

83 96 84 95 85 95

90

Решение

 

Объяснение

Для решения задачи создаём переменные, в которых будем хранить значение суммы всех ве́сов учеников, количество взвешенных, максимальное и минимальное значение из их ве́сов, и количество учеников с таковыми значениями. Далее считываем значения, сразу обрабатывая их. При получении первой переменной ($n=0$), записываем значение и как минимум, и как максимум. Потом сравниваем остальные значения с данным. Если следующие значения больше или меньше, перезаписываем значение соответствующей переменной, также сбрасываем счётчик, который считает, сколько учеников с такой массой. Для каждого случая прописано отдельное условие, поскольку минимум может быть одновременно и максимумом.

После того, как все данные были считаны, выполняем проверку: если количество учеников с минимальным и максимальным весом равно общему количеству взвешенных, то, поскольку нам нужно вывести значение без минимума и максимума, выводим $0$. В противном случае, выводим округлённое значение среднего арифметического без крайних значений.

ideone

e-olymp

e-olymp 178. Каждый третий бесплатно

Задача

Барлимен Баттербар — владелец небезызвестного трактира «Гарцующий пони», расположенного в городке Бри. Именно сюда частенько наведываются уставшие после сражений орки, чтобы отведать кружечку-другую своего любимого напитка – гномоукладчика. Однако в последнее время стали появляться другие заведения, что привело к уменьшению количества клиентов трактира. Чтобы вернуть себе клиентов, Барлимен решил сделать в своем трактире акцию, что каждый заказавший определенное количество кружек гномоукладчика, получает еще один бесплатно. Естественно, чем меньше будет это количество, тем более привлекательной будет эта акция для клиентов, но с другой стороны, если оно будет слишком маленьким, то хозяин не сможет получать прибыль (а может даже и будет терпеть убытки).

Помогите трактирщику определить минимальное количество кружек, за которое может он давать бесплатную так, чтобы получать хоть какую-нибудь прибыль.

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

Каждый тест задан в одной строке и содержит два целых числа: цену закупки одной кружки гномоукладчика $b$ и цену $c$ [latex](0 \leq b \lt c \leq 10^9)[/latex], по которой трактирщик ее продает. Последний тест содержит [latex]b = c = 0[/latex] и не обрабатывается.

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

Для каждого теста вывести в отдельной строке искомое минимальное количество кружек.

Тесты

Входные данные Выходные данные
5 8
100 1000
13 18
0 0
2
1
3
10 11
1 10
10 20
0 0
11
1
2
4 5
2 5
0 5
0 0
5
1
1

 

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

Решение

Вводим первую пару. Условием работы цикла поставим ненулевой $c$ (так как из условия $b$ больше или равно нулю, а $c$ больше $b$ строго).

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

Однако, выразив прибыль как разность цены продажи и закупки, этот способ можно интерпретировать и как поиск минимального количества «разностей», превышающих закупочную цену одной кружки. Тогда можно увидеть схожесть этого действия с делением (15 / 3 — это столько же, сколько троек вмещает в себе пятнадцать). То есть нам нужно делить закупочную цену кружки на прибыль с неё. Но так как нам нужно всегда при этом иметь прибыль, будем брать целую часть от деления, и прибавлять к ней единицу (округлять вверх — не вариант в случае, например, когда цена продажи вдвое больше цены закупки — тогда ответом будет «одна кружка», что нам не подходит, потому что хоть трактир не будет в убытке, но он не получит и прибыли). Выводим формулу:

[latex]m = \bigg \lfloor \frac{b}{c — b} \bigg \rfloor + 1[/latex],

где $m$ — минимальное количество кружек.

Ссылки

e-olymp

Ideone

e-olymp 1507. История Лаурела-Харди

Задача

Лаурел и Харди — два известных киногероя $50$-ых. Они известны своей разницей в весе, как можно увидеть на картинке. Если Вы еще не разобрались, кто из них кто, то я добавлю, что Лаурел легче. В свои юношеские годы Лаурел и Харди любили играть со странными качелями, и когда качели находились в равновесии, то Харди всегда был у земли. Мы рассмотрим двумерную версию качель.

Качели, которыми пользовались Лаурел и Харди, представляют собой часть окружности радиуса $r$, как показано на картинке (они закрашены серым и имеют вид буквы $D$). Харди сел на точку $B$ (самая правая точка качель), а Лаурел сел на точку $A$ (самая левая точка отрезка $AB$). $d = EF$ — расстояние между центром отрезка $AB$ и дуги $AFB$. То есть $E$ — середина отрезка $AB$, а $F$ — середина дуги $AFB$. $MN$ — основа качель, является горизонтальной прямой. $BD = h_1$ — расстояние от Харди до земли. Вам необходимо найти расстояние от Лаурела до земли (обозначаемое $h_2 = AC$).

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

Первая строка содержит количество тестов $N \space (0 < N ≤ 1000)$. Каждая из следующих $N$ строк представляет собой отдельный тест, который имеет следующий формат:

Каждая строка содержит три целых числа $r \space (10 ≤ r ≤ 100), \space$ $d \space (5 ≤ d ≤ r), \space$ $h_1 \space (5 ≤ h_1 ≤ d)$. Значение этих чисел приведено выше.

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

Для каждого теста в отдельной строке вывести его номер и действительной число — значение $h_2$. Это число должно содержать четыре десятичных знака. Формат вывода приведен в примере.

Тесты

Входные данные Выходные данные
2
10 10 10
10 7 6
Case 1: 10.0000
Case 2: 8.0342
3
12 7 7
11 11 8
54 12 6
Case 1: 7.0000
Case 2: 14.0000
Case 3: 19.7383
5
94 21 12
23 9 8
5 4 3
2 2 1
43 26 20
Case 1: 32.1226
Case 2: 10.0439
Case 3: 5.0440
Case 4: 3.0000
Case 5: 32.4231

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

Решение

Для лучшего понимания решения данной задачи, я построил к ней чертеж, который вы можете видеть сверху. Но прежде чем приступить непосредственно к объяснению решения, я хотел бы обратить внимание на то, что мой рисунок (даже без дополнительных построений) немного отличается от данного нам в условии. Эти различия преднамеренны и метод решения справедлив для обоих рисунков.

В $9$ строке введем число $N$ из входного потока, а в $10$ — запустим цикл, который будет работать $N$ раз. Далее за каждый проход цикла будем читать по $3$ следующих числа из входного потока и выводить на экран номер текущего теста. Перед тем, как идти дальше, разберемся в рисунке. Так как по условию отрезок $EF$ делит сегмент $AFB$ пополам, то по свойствам хорд и дуг окружности, он является частью радиуса $r$ нашей окружности с центром в точке $O$ и перпендикулярен хорде $AB$, что и показано на чертеже. Кроме того, я дорисовал радиусы $OA$ и $OB$ окружности к соответствующим точкам и начертил отрезок $BH$, как продолжение $AB$, от точки $B$ до прямой $MN$. Также, я построил прямоугольный треугольник $\triangle OGB$, в котором катет $OG = r-BD$.
Достроив все необходимые отрезки, легко заметить, что мы имеем прямоугольный треугольник $\triangle ACH$ с катетом $AC$, длину которого нам и нужно найти по условию задачи. Предлагаю сделать это, воспользовавшись формулой $AC = AH \cdot \sin(\angle AHC)$. Найдем значения сомножителей.

Из рисунка очевидно, что $\angle AHC = \angle BHD = \angle EBG = \angle OBG-\angle OBE.$
Сначала найдем $\angle OBG$. Для этого рассмотрим треугольник $\triangle OGB$. Длины его гипотенузы и противолежащего к искомому углу катета нам уже известны, так что можем сразу найти $\angle OBG = \arcsin \frac{OG}{OB}$.
Теперь найдем $\angle OBE$. Рассмотрим прямоугольный треугольник $\triangle OEB$. В нем противолежащий искомому углу катет $OE = r-d$, а гипотенуза $OB = r$. Значит, $\angle OBE = \arcsin \frac{OE}{OB}$.
В итоге остаётся только найти разницу этих углов, которая и будет являться величиной искомого $\angle AHC$. В коде же значение этого угла считается в $13$ строке и присваивается переменной a.

Стоит заметить, что если $\angle OBG-\angle OBE = 0$, то длины отрезков $AC$ и $BD$, очевидно, совпадают. В таком случае можем сразу вывести на экран $h_2 = h_1$, как мы и поступили в $15$ строке, и перейти к нахождению $AC$ уже для следующего тестового случая.

Если же величина $\angle AHC$ отлична от $0$, то нам все еще предстоит посчитать длину гипотенузы $AH$ треугольника $\triangle ACH$. Она состоит из хорды $AB$ и отрезка $BH$.
Сперва найдем длину хорды. Известно, что $OF$ делит ее на $2$ одинаковых по длине отрезка, значит, следует опять рассмотреть треугольник $\triangle OEB$. Длину его гипотенузы и одного из катетов мы уже находили, так что просто применим теорему Пифагора и найдем $EB = \sqrt{OB^2-OE^2}$. Тогда $AB = 2 \cdot EB$.
Для нахождения длины $BH$, рассмотрим треугольник $\triangle BDH$, в котором этот отрезок является гипотенузой. Длину катета $BD$ и величину угла $\angle BHD$ мы уже знаем, значит, можем применить формулу $BH = \frac{BD}{\sin(\angle BHD)}$.
Сложим найденные значения длин хорды $AB$ и отрезка $BH$, чтобы получить $AH$. В коде эта длина находится в $17$ строке и присваивается переменной b.

Теперь остается только подставить найденные значения в ранее приведенную формулу и получить наконец длину $h_2$, которую выведем на экран в $18$ строке.

Ссылки

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

e-olymp 500. Ремонт

Задача

Ваш любимый дядя – директор фирмы, которая делает евроремонты в офисах. В связи с финансово-экономическим кризисом, дядюшка решил оптимизировать свое предприятие.

Давно ходят слухи, что бригадир в дядюшкиной фирме покупает лишнее количество стройматериалов, а остатки использует для отделки своей новой дачи. Ваш дядя заинтересовался, сколько в действительности банок краски необходимо для покраски стены в офисе длиной $L$ метров, шириной $W$ и высотой $H$, если одной банки хватает на $16$ метров квадратных, а размерами дверей и окон можно пренебречь? Заказов много, поэтому дядя попросил написать программу, которая будет все это считать.

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

В первой строке содержится количество заказов. Описание каждого заказа состоит из трех натуральных чисел $L$, $W$, $H$ — длины, ширины и высоты офиса в метрах соответственно, каждое из которых не превышает $1000$.

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

Для каждого заказа выводится в отдельную строку одно число – количество банок краски, необходимых для окраски офиса.

Тесты

 

Входные данные
Выходные данные
$1$
$1$ $1$ $1$
$1$
$3$
$8$ $7$ $10$
$15$ $8$ $4$
$3$ $5$ $4$
$19$
$12$
$4$
$2$
$27$ $88$ $19$
$999$ $999$ $999$
$274$
$249501$

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

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

Рассчитаем площадь стен комнаты как сумму площадей $4$ прямоугольников: $$hw + hl + hw + hl = 2hw + 2hl = 2h \cdot (w + l)$$ Теперь, зная площадь стен, рассчитаем количество банок краски. Для этого поделим площадь стен на $16$ и округлим вверх. Для округления вверх можно использовать тернарный условный оператор: если $s$ делится нацело на $16$, то ответ будет $\displaystyle \frac{s}{16}$, в противном случае – $\displaystyle \frac{s}{16} + 1$ (деление переменной int – целочисленное). Так как в задаче необходимо обрабатывать несколько таких примеров подряд, то все вычисления взяты в цикл от $0$ до $r$ (название переменной $r$ в самой задаче не указано, оно выбрано произвольно).

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 3843. Простые

Задача

Пусть $m$ и $n$ $\left(2 ≤ m < n ≤ 107\right)$ — целые числа. Рассмотрим следующее множество:

Prime $\left(m, n\right) = \lbrace{ p | p\;простое, m ≤ p ≤ n \rbrace}$.

Вычислить мощность множества Prime$\left(m, n\right)$.

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

Состоит из нескольких тестов. Два последовательных теста разделены пустой строкой. Для каждого теста в отдельной строке заданы числа $m$ и $n$.

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

Для каждого теста вывести результат в отдельной строке. Результаты соседних тестов разделять пустой строкой. Для каждого теста вывести мощность множества Prime$\left(m, n\right)$.

Тесты

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

70    110

5    150

8

10

33

7    2056

14    181

27    367

307

36

64

77    777

55    555

33    333

116

85

56

Код решения

 

Решение

Для решения этой задачи требуется завести большой массив типа bool и присвоить ему значение true. Затем проверяется, простое ли число, если это не так, то присваиваем значение false.
Затем нужно последовательно сосчитать мощность каждого множества простых чисел, то есть количество простых чисел от n до m, с помощью массива-счётчика: записывается в него прошлые и последующие элементы множества простых чисел.
После этого в цикле задаются нужные значения, считается ответ и выводится.

Условие задачи на e-olymp.com
Код решения на ideone.com

e-olymp 97. Числа Белла

Задача

Число Белла [latex]B_n[/latex] равно количеству разбиений множества из [latex]n[/latex] элементов на произвольное количество непересекающихся непустых подмножеств. Например, [latex]B_3 = 5[/latex], так как существует [latex]5[/latex] возможных разбиений множества [latex]\lbrace a, b, c\rbrace[/latex]: [latex]\lbrace\lbrace a\rbrace, \lbrace b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, c\rbrace, \lbrace b\rbrace\rbrace, \lbrace\lbrace a\rbrace, \lbrace b, c\rbrace\rbrace, \lbrace\lbrace a, b, c\rbrace\rbrace[/latex]. Дополнительно считаем, что [latex]B_0 = 1[/latex].
Рассмотрим определитель [latex]D_n[/latex]:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix}$$
Для заданного простого числа [latex]p[/latex] найти наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

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

Каждая строка ввода содержит два целых числа [latex]n[/latex] и [latex]p[/latex] ( [latex]\;0\leq\; n,\;p \;\leq\; 10000[/latex] ). Известно, что [latex]p[/latex] – простое.

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

Для каждой пары входных значений [latex]n[/latex] и [latex]p[/latex] в отдельной строке выведите наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

Тесты

Входные данные Выходные данные
1 5
3 2
4 2
4 3
10000 3
0
2
5
2
24962375
18 2
465 1009
9998 9221
548 11
134
0
778
14412
1093 1093
1103 1723
3931 617
4868 6113
9534 71
1
0
10635
0
639989
617 17
42 11
0 5
11295
63
0

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

 

Решение

Числа Белла обладают интересным свойством:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix} = \prod_{i=1}^n i! $$

Воспользуемся этим свойством для решения данной задачи. Найдём степень числа [latex]p[/latex] в разложении  на простые множители. Для этого узнаем степень вхождения этого числа в каждый из факториалов. Суммой полученных значений и будет являться искомое число [latex]k[/latex].

Ссылки

Условия задачи на e-olymp
Код задачи на ideone
Число Белла на wikipedia

e-olymp 1154. Кружок хорового пения

Задача

В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex]-й для распевки поёт гамму.

Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]N[/latex] и [latex]M[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.

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

Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]N[/latex] и [latex]M[/latex]. ([latex]1 ≤ N, M ≤ 103[/latex]).

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

Для каждого тестового случая в отдельной строке выведите «YES», если в разминке примут участие все участники хора, в противном случае выведите «NO».

Тесты

Входные данные Выходные данные
1000 1000
1 1
NO
YES
2 5
3 7
14 15
49 37
YES
YES
YES
YES
14 16
891 6
441 9
777 111
NO
NO
NO
NO
4 1
6 3
YES
NO

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

Пусть у нас есть [latex]N[/latex] певцов. Пронумеруем их по порядку от [latex]0[/latex] до [latex]N — 1[/latex]. Распевается каждый [latex]M[/latex]-й. И пусть НОД ([latex]M, N) = k \geq 2[/latex]. Тогда, например, [latex]k — 1[/latex]-ый певец никогда не распоется. На рисунке ниже приведен пример. [latex]6[/latex] певцов,  распевается каждый [latex]2[/latex], начиная из верхнего левого угла при смене по часовой стрелке. Переливающимся кружочком обозначен поющий в данный момент певец.


Докажем, что если [latex]M[/latex] и [latex]N[/latex] взаимно просты, то все участники распоются. Для начала заметим, что при [latex]i[/latex]-ой смене (где [latex]i[/latex] некоторое натуральное число) очередь вернется к участнику, с которого распевка начиналась,то есть смена циклическая. Поскольку НОД ([latex]M, N) = 1 [/latex], то НОК ([latex]M, N) = M*N [/latex], то есть распевающий сменится [latex]N[/latex] раз для завершения цикла. Покажем, что ни один из певцов не споет более [latex]1[/latex] раза. Пусть есть некоторый [latex]k[/latex]-ый распевающий, очередь которого наступила более [latex]1[/latex] раза за время цикла. Однако, как и для первого распевающего, очередь для [latex]k[/latex] наступит через [latex]N[/latex] смен, то есть после завершения цикла. Получили опровержение. Значит каждый распоется не более [latex]1[/latex] раза. Теперь, учитывая количество смен, получим, что каждый распоется ровно [latex]1[/latex] раз. В случае, когда НОД ([latex]M, N) \geq 2 [/latex] получим, что за цикл распоется менее, чем [latex]N[/latex] участников хора.

 

Ссылки

Условие задачи на сайте  E-Olymp

код задачи на Ideone

e-olymp 1128. Проблема Лонги

Задача

Лонги хорошо разбирается в математике, он любит задумываться над трудными математическими задачами, которые могут быть решены при помощи некоторых изящных алгоритмов. И вот такая задачка возникла:
Дано целое число [latex]n[/latex] [latex](1 < n < 231)[/latex], Вы должны вычислить [latex]\sum\limits_{i=1}^n gcd [/latex] для всех [latex] 1 ≤ i ≤ n[/latex].
"О, я знаю, я знаю!" — воскликнул Лонги! А знаете ли Вы? Пожалуйста, решите её.

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

Каждая строка содержит одно число [latex]n[/latex].

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

Для каждого значения [latex]n[/latex] следует вывести в отдельной строке сумму [latex]\sum\limits_{i=1}^n gcd [/latex] для всех [latex] 1 ≤ i ≤ n[/latex].

Тесты

Входные данные Выходные данные
[latex]2[/latex] [latex]6[/latex] $3$
$15$
[latex]1[/latex] [latex]50[/latex] [latex]100[/latex] $1$
$195$
$520$
[latex]7[/latex] [latex]4791[/latex] [latex]12345678[/latex] [latex]478900[/latex] $13$
$15965$
$170994915$
$4980040$
[latex]123[/latex] [latex]7777[/latex] [latex]157423949[/latex] [latex]904573[/latex] $2147483648$ $405$
$54873$
$613124817$
$1809145$
$35433480192$

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

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

Согласно свойству НОД, если некоторые числа [latex]a_1[/latex] и [latex]a_2[/latex] взаимно просты, то [latex]\gcd \left(a_1 \cdot a_2, c\right) = \gcd \left(a_1, c\right) \cdot \gcd \left(a_2, c\right)[/latex], где [latex]c[/latex] — некоторая константа. Если же вместо [latex]c[/latex] взять [latex]i[/latex] ([latex] 1 ≤ i ≤ a_1 \cdot a_2[/latex]) и просуммировать по [latex]i[/latex] обе части равенства, получим:
[latex]\sum\limits_{i=1}^{a_1 \cdot a_2} \gcd \left(a_1 \cdot a_2, i\right) = \sum\limits_{i=1}^{a_1 \cdot a_2} \left(\gcd \left(a_1, i\right) \cdot \gcd \left(a_2, i\right)\right) = \sum\limits_{i=1}^{a_1} \gcd \left(a_1, i\right) \cdot \sum\limits_{i=1}^{a_2} \gcd \left(a_2, i\right)[/latex].
Значит мы можем данное число представить как произведение простых в некоторых степенях. Эти числа, очевидно, будут взаимно простыми, из чего следует возможность применения данного свойства и последующего суммирования по [latex]i[/latex].
Теперь докажем, что для любого простого числа [latex]p[/latex] в степени [latex]a\geqslant 1[/latex] верно следующее равенство:
[latex]\sum\limits_{i=1}^{p^a} \gcd\left(p^a, i\right) = \left(a + 1\right)\cdot p^a — a \cdot p^{a-1} [/latex].
Обозначим $\sum\limits_{i=1}^{r} \gcd\left(r, i\right)$ как $g\left(r\right)$.
База индукции:
[latex]a = 1[/latex]:
$$g\left(p\right) = \gcd\left(p, 1\right) + \gcd\left(p, 2\right) + \ldots + \gcd\left(p, p\right) = \left(p — 1 \right) + p = 2 \cdot p — 1.$$
Если [latex]a = 2[/latex]:
$$g\left(p^{2}\right) = \gcd\left(p^{2}, 1\right) + \gcd\left(p^{2}, 2\right) + \ldots + \gcd\left(p^{2}, p\right) + \gcd\left(p^{2}, p + 1\right) + \ldots + \\ + \gcd\left(p^{2}, 2 \cdot p\right) + \ldots + \gcd\left(p^{2}, p^{2}\right) = 1 + 1 + \ldots + p + 1 + \ldots + p + \ldots + p^{2} = \\ = \left( p^{2} — p \right) + p \cdot \left( p — 1 \right) + p^{2} = 3 \cdot p^{2} — 2\cdot p.$$
Для любых $a \geqslant 2$:
$$g\left(p^{a}\right) = \sum\limits_{j=1}^{p^{a-1}} \gcd\left(p^a, j\right) + \sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a, j\right) + p^{a} =g\left(p^{a — 1}\right) + p^{a} + \\ + \sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a — 1, j\right).$$
Причем:
$$\sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a — 1, j\right) = \sum\limits_{j=1}^{p^{a} — p^{a-1} — 1} \gcd\left(p^{a — 1}, j\right) = \\ = \sum\limits_{j=1}^{p^{a} — p^{a-1}} \gcd\left(p^{a — 1}, j\right) — p^{a — 1} = \left( p — 1\right)\cdot g\left(p^{a-1}\right) — p^{a-1}.$$
Откуда следует:
$$g\left(p^{a}\right) = p^{a} — p^{a-1} + p\cdot g\left(p^{a-1}\right).$$
Предположение индукции:
Пусть [latex]a = b[/latex]:
$$g\left(p^{b}\right) = \left(b + 1\right) \cdot p^b — b \cdot p^{b-1}.$$
Шаг индукции:
Пусть [latex]a = b + 1[/latex]:
$$g\left(p^{b + 1}\right) = p^{b + 1} — p^{b} + p\cdot g\left(p^{b}\right) = p^{b + 1} — p^{b} + p\cdot \left[\left(b+1\right) \cdot p^{b} + b\cdot p^{b-1}\right] = \\ = \left(b + 2\right)\cdot p^{b+1} — \left(b + 1\right)\cdot p^{b}.$$

Ссылки

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

e-olymp 176. Выбор вождя

Условие задачи
Орки – одна из рас, населяющих мир Драэнор. Не отличаясь высоким интелектом, орки все же славятся своею силой и отвагой в бою. Ежегодно орки из разных кланов собираются в Долине Силы для того, чтобы избрать вождя всей Орды. В отличие от глупых людей, орки презирают выборы посредством голосования (да и, скажем прямо, все эти бюлетени, урны и избирательные участки чужды и непонятны орку, не державшему в руках ничего, кроме дубины и топора). Кандидаты в вожди сражаются друг с другом в честных поединках. В каждом поединке участвуют два претендента, один из которых выходит из него победителем, а другой оказывается поверженным. Проигравший в одном поединке орк выбывает из числа претендентов и не может участвовать в последующих поединках. Оставшийся в конце концов после всех боев кандидат и становит вождем Орды.

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

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


Входные данные
В первой строке входного файла записано количество [latex]N[/latex] претендентов на звание вождя в этом году [latex](1 ≤ N ≤ 1000000)[/latex], а во второй – [latex]N[/latex] целых чисел в пределах от [latex]1[/latex] до [latex]10000[/latex], каждое из которых определяет силу соответствующего кандидата.

Выходные данные
Выходной файл должен содержать одно число – количество претендентов, которые могут стать вождями.

Continue reading

e-olymp 49. Кот учёный

Задача

Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной $l$, $n$ рыбин. Зная координаты головы и хвоста каждой из них, подсчитайте, на какие сутки у кота визникнет чувство голода, если оно возникает тогда, когда за сутки он съест меньше, чем $k$ рыбин. Рыбину он может съесть, если сможет дотянуться хотя бы к одной её точке. Координаты дуба $(0, 0)$.

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

В первой строке находятся числа $l$, $n$, $k$. Далее идет $n$ строк: координаты головы $(x_{1i}, y_{1i})$ и хвоста $(x_{2i}, y_{2i})$ каждой рыбины. Все входные данные — целые числа, не превышающие по модулю $100$.

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

Вывести день, на который у кота появится чувство голода.

Тесты

Входные данные Выходные данные
[latex]4\, 4\, 2[/latex] [latex]2[/latex]
[latex]1\, 1\, -1\, 3[/latex]
[latex]2\, 2\, 4\, 2[/latex]
[latex]-3\, -4\, -3\, 4[/latex]
[latex]1\, -5\, 4\, -4[/latex]
[latex]3\, 2\, 1[/latex] [latex]3[/latex]
[latex]1\, 2\, 3\, 4[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]3\, 5\, 4[/latex] [latex]1[/latex]
[latex]2\, 4\, 5\, 7[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]8\, 10\, 2\, 7[/latex]
[latex]12\, 3\, 4\, 2[/latex]
[latex]100\, 100\, -100\, -100[/latex]

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

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

Для каждой рыбы мы будем делать такой процесс.
Для начала проверим расстояния от начала координат до каждого из концов рыбы. Если хотя бы одно из них меньше либо равно длине цепи, то кот сможет съесть эту рыбу и ничего больше проверять не надо. Если же эти расстояния больше длины цепи поступим так. Найдем уравнение прямой проходящей через две точки (координаты начала и конца рыбы). Оно имеет вид: $$\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$$ Приведем его к виду $ax+by+c=0$. Получим, что $a=y_2-y_1$, $b=-(x_2-x_1)$, $c=y_1(x_2-x_1)-x_1(y_2-y_1)$. Теперь проверим длину перпендикуляра к этой прямой от начала координат (т. к. если длина перпендикуляра больше длины цепи, кот точно не дотянется до рыбы). Расстояние $d$ от точки $(0,0)$ до прямой $ax+by+c=0$ посчитаем по формуле: $$d=\frac{a\cdot 0+b\cdot 0+c}{\sqrt{a^2+b^2}}$$ Избавляясь от корня и деления, получим условие: $$c^2\leq l^2(a^2+b^2)$$ (где $l$ — длина цепи). Если это условие выполняется, остается проверить, что точка пересечения перпендикуляра и прямой лежит между началом и концом рыбы (нам достаточно проверить по одной из координат, например по второй). Прямая, перпендикулярная исходной и проходящая через точку $(0,0)$, будет иметь вид: $$\frac{x}{a}=\frac{y}{b}$$ (т. к. $(a,b)$ — нормальный вектор к прямой, проходящей через начало и конец рыбы). Получаем систему из двух уравнений и двух неизвестных. Решая эту систему, получаем, что вторая координата точки пересечения равна: $$y=\frac{-cb}{a^2+b^2}$$ Теперь проверяем, лежит ли эта координата, между вторыми координатами начала и конца рыбы. Если да, то кот сможет съесть эту рыбу, иначе — нет.
Ответом на задачу будет $\left \lfloor\frac{count}{k}\right \rfloor+1$, где $count$ — количество рыб, до которых смог дотянуться кот, $k$ — минимальное количество рыб, которое кот должен съесть в сутки.

Ссылки

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

e-olymp 907. Первый не больший чем 2.5

Задача

Задан массив вещественных чисел. Найти первый элемент массива, значение которого не превышает 2.5.

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

В первой строке задано количество элементов массива [latex]n (0 < n ≤ 100)[/latex]. В следующей строке задано [latex]n[/latex] вещественных чисел.

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

Вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. В случае отсутствия такого элемента в массиве вывести «Not Found» (без кавычек).

Тесты

Входные данные Выходные данные
[latex]5 \\ 6 \; 7.5 \; 2.1 \; 2.0 \; 0[/latex] [latex]3 \; 2.10[/latex]
[latex]5 \\ 6 \; 7.5 \; 5.1 \; 7.0 \; 80[/latex] [latex]Not \; Found[/latex]
[latex]7 \\ 5 \; 4.7 \; 50 \; 8.9 \; 2.7 \; 3 \; 1.5[/latex] [latex]7 \; 1.5[/latex]

Решение задачи с помощью массивов

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

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

Введем обозначения: [latex]x[/latex] – имя массива, [latex]n[/latex] – количество элементов в массиве, [latex]i[/latex] – индекс элемента массива. Нам необходимо просмотреть весь массив. Если значение просматриваемого элемента не превышает 2,5, то в ответе вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. Если же такого элемента в массиве нет, вывести Not Found.

Решение задачи с помощью потоковой обработки

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

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

Будем просматривать все веденные элементы и для каждого осуществлять проверку, если элемент не превышает 2.5, тогда в ответе выводим в одной строке сначала индекс найдененого первого указанного элемента и его значение с 2 десятичными знаками. Если же такого элемента в массиве нет, выводим на экран Not Found.

Ссылки

Условие задачи на e-olymp
Код решения с помощью массивов на ideone
Код решения с помощью потоковой обработки на ideone

e-olymp 441. Наиболее круглое число

Наиболее круглое число

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

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

В первой строке входных данных задано количество чисел [latex]N[/latex] [latex](1  ≤  N  ≤  100)[/latex]. Каждая из последующих N строк содержит одно число в пределах от [latex]1[/latex] до [latex]10^{9}[/latex].

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

Вывести наиболее круглое число среди заданных [latex]N[/latex] чисел.

Тесты

Входные данные Выходные данные
4
71200
10
200
10001
200
5
711
1
2
10001
234567
1
10
7
1
2
1
2
3
4
6
8
9
1
4
100000
200000
500000
800000
100000

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

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

Имеет смысл проверять каждое введенное число: не является ли оно меньше либо равно чем [latex]p[/latex], где [latex]p[/latex] — наименьшее число с количеством нулей равным [latex]maxk[/latex]. [latex]maxk[/latex] — текущее наибольшее количество нулей. Для того, чтобы найти [latex]p[/latex], мы в цикле умножаем [latex]1[/latex] [latex]maxk[/latex]-раз на [latex]10[/latex]. Очевидно, что [latex]p[/latex] нужно менять только тогда, когда меняется [latex]maxk[/latex], также следует до цикла полагать [latex]p=1[/latex]. Для того чтобы [latex]p[/latex] не умножалось на [latex]10[/latex] лишнее количество раз. Таким образом мы отсеиваем заведомо негодные числа и ускоряем код.
Положим [latex]maxn[/latex] — наиболее круглое число.
Так как по условию числа не могут быть больше чем [latex]10^{9}[/latex], имеет смысл изначально поставить переменную [latex]maxn=10^{9}[/latex]. Это делается для того случая, когда во всех числах [latex]m[/latex] не будет нулей и нужно будет выбрать наименьшее. Если мы положим в переменную [latex]maxn[/latex] любое другое число то [latex]maxn[/latex] может быть меньше чем [latex]m[/latex] и мы не сможем выбрать ответ так как все [latex]m[/latex] будут больше его.

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

e-olymp 6350. Изированная вода

Задача

Изированная вода

В Бердичеве ещё в советские времена продавалась знаменитая изированная вода. Собственно это была обычная газировка на разлив, но продавал её Изя, поэтому и воду все называли изированной. Продавец газировки был человеком не только очень умным и добродушным, но и очень сообразительным. О складе его ума говорит хотя бы тот факт, что у него было $2$ диплома о высшем образовании: он закончил физмат пединститута и мехмат университета, а о сообразительности – то, что имея два диплома, он продавал газировку и довольно успешно. Старожилы утверждают, что попить его газировки прилетали в те времена даже с самой Москвы…

Изя, герой задачи

С постоянными покупателями, и не только с ними, Изя был очень общительным человеком, и иногда, как говорится «под настроение клиента», задавал им свои задачки на сообразительность, которых у него в запасе было великое множество. Одна из подобных его задачек приведена в задаче «Покупка воды». Задав подобную задачку, он ждал от клиента быстрого, сообразительного и, главное, верного ответа на неё, если же ответ запаздывал, или был не верным, Изя всегда говорил что-то типа: «Молодой человек, придёте завтра – Вы сегодня не заслужили на обслуживание». Естественно, это была шутка и клиент всё равно имел возможность приобрести очень вкусную изированную воду.

Перед тем как сформулировать наш вопрос, напомним задачку, упоминаемую выше: «Стоимость бутылки воды, учитывая стоимость пустой бутылки, составляет $1$ руб. $20$ коп., а стоимость пустой бутылки – $20$ коп. Сколько бутылок воды можно выпить на $N$ руб., учитывая, что пустые бутылки можно сдавать, и на полученные деньги приобретать новые бутылки воды?».

Нас же будет интересовать ответ на следующий вопрос: «А сколько покупателей услышали сегодня от Изи фразу «Приходите завтра!»?».

Входные данные
В первой строке входных данных находится единственное число $N (1 ≤ N ≤ 10^6)$ — количество покупателей, которым Изя задавал упоминаемую в условии задачку.

В последующих $N$ строках задано через пробел $N$ пар чисел, первое из которых — количество денег в кошельке перед началом операции «Покупка ГазВоды», а второе — ответ покупателя.

Все входные данные — целые неотрицательные числа, не превышающие $10^9$.

Выходные данные
Вывести единственное число — количество покупателей, услышавших от продавца ответ «Придёте завтра» и при этом ответили неправильно. Подсчитывать же тех, кто долго думал, не обязательно, за Вас это сделает проверяющая система вердиктом TL (Time Limited).

Тесты

Входные данные Выходные данные
5
2 1
2 2
1 2
1 1
2 1
3
3
45 45
38 37
12 10
2
3
5 4
7 6
3 2
0
2
1280 1280
1900 1899
1
7
1 1
2 2
3 2
6 5
6 6
7 3
2 2
5

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

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

Для решения этой задачи необходимо решить задачу «Покупка воды». Решение очень простое: количество бутылок воды, которое можно выпить на $n$ грн. равно $n — 1$.

Используем это в цикле для проверки на правильность ответа покупателя. Если ответ неправильный, то увеличиваем переменную  j, которая считает количество неправильных ответов, на один, и, после завершения цикла, выводим ее значение.

Ссылки

Код задачи на e-olymp.com
Решение задачи на ideone.com

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

Задача

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

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей [latex](0 < n ≤ 10, 0 < m ≤ 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]\frac{sum}{n-a-b}[/latex] и выводим результат.

Ссылка на e-olymp

Ссылка на ideone