e-olymp 4752. Кинотеатр

Задача

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера n × m, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

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

prb4752.gif

Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).

prb4752_1.gif

Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.

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

В первой строке заданы числа $n$ и $m$ $(1 ≤ n, m ≤ 1000)$.

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

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

Тесты

Входные данные Выходные данные
1 3 3 3
2 3 4 2
3 6 3 2
4 5 9 5
5 7 5 3

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

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

Для решения задачи проверяем значения до пересадки и после, если они совпадут соответственно, то инкрементируем счётчик. А в конце выводим результат.

Ссылки

e-olymp 927. Количество игрушек

Задача

Задано количество видов игрушек в магазине, количество игрушек каждого вида и стоимость игрушки каждого вида. Определить количество игрушек, стоимость которых меньше $50$ грн.

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

В первой строке задано количество наличных в прейскуранте видов игрушек $n$ $(0 ≤ n ≤ 1000)$. В следующих $n$ строках задано по $2$ числа через пробел: сначала количество игрушек $a$ $(0 ≤ a ≤ 1000)$ очередного вида и их цена $b$ $(0 < b ≤ 10000)$ в грн.

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

Вывести количество игрушек, стоимость которых меньше $50$ грн.

Тесты

Входные данные Выходные данные
1 3
2  100.00
5  23.00
10  22.50
15
2 3
2 10.00
5 2355.00
6 22.50
8
3 4
2 15.00
13 2355.00
10 22.50
1 49.00
13
4 2
2 15.00
13 51.00
2
5 3
3  100.00
5  230.00
7  220.50
0

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

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

Если цена за игрушку меньше 50 грн, то вся партия этого вида игрушек удовлетворяет условию.
Считаем количество игрушек во всех таких партиях.

Ссылки

e-olymp 4192. Олимпиада

Задача

На олимпиаду по информатике прибыло $n$ команд, каждая из которых состоит из $a_i$ мальчиков и $b_i$ девочек $(1 ≤ i ≤ n)$. Для проживания имеются одинаковые комнаты по $m$ мест в каждой. Какое наименшее количество комнат достаточно для размещения участников олимпиады, если мальчиков с девочками селить вместе запрещено?

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

Первая строка содержит числа $n$ и $m$. Каждая следующая из $n$ строк содержит пару чисел $a_i$ , $b_i$ $(1 ≤ i ≤ n)$. Все числовые значения целые неотрицательные и не превышают $100$.

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

Вывести наименьшее необходимое количество комнат.

Тесты

Входные данные Выходные данные
1 2 3
2 1
3 2
3
2 3 5
5 8
2 3
6 1
6
3 2 2
1 1
1 3
3
4 4 2
1 3
5 1
2 7
3 1
12
5 7 2
5 6
3 4
2 5
1 3
9 3
8 7
6 4
33

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

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

Для решения задачи найдём общее количество мальчиков и девочек, затем по отдельности посчитаем в каком количестве комнат они поместятся, но когда мы целочисленно делим количество детей на вместимость одной комнаты, мы определяем какое количество комнат будет заполнено полностью. Но, если количество детей не кратно количеству комнат, то полученный ответ должен быть на единицу больше. Для этого к количеству детей добавим ещё ровно столько, сколько нужно для того, чтобы ответ стал больше на единицу, то есть $m$, но на один меньше, чтобы при количестве детей кратном ответ был прежний. А после сложим полученные значения.

Ссылки

e-olymp 839. Пересечение отрезков

Задача

Два отрезка на плоскости заданы целочисленными координатами своих концов в декартовой системе координат.

Требуется определить, существует ли у них общая точка.

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

В первой строке содержатся координаты первого конца первого отрезка, во второй — второго конца первого отрезка, в третьей и четвёртой — координаты концов второго отрезка. Координаты целые и по модулю не превосходят $10000$.

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

Вывести слово $Yes$, если общая точка есть, или слово $No$ в противном случае.

Тесты

Входные данные Выходные данные
1 0 0
1 0
1 0
1 1
Yes
2 0 0
1 0
2 0
3 0
No
3 7 4
1 1
1 1
3 2
Yes
4 -9725 -8992
9812 9925
-9999 7011
8122 -9248
Yes
5 -9999 -1
10000 1
0 0
0 1
No

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

С ветвлением:

без ветвления:

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

Чтобы проверить пересекаются ли заданные отрезки построим прямые, которым они принадлежат, затем найдём точку их пересечения и проверим принадлежит ли она каждому из отрезков.
Для построения прямых воспользуемся формулой прямой проходящей через две точки и немного её преобразуем:
$\frac{x — x_1}{x_2 — x_1} = \frac{y — y_1}{y_2 — y_1}$ ~ $(x — x_1) \cdot (y_2 — y_1) = (y — y_1) \cdot (x_2 — x_1)$ ~ $x \cdot (y_2 — y_1) — y_2 \cdot x_1 + y_1 \cdot x_1 = y \cdot (x_2 — x_1) — x_2 \cdot y_1 + x_1 \cdot y_1$ ~ $y \cdot (x_2 — x_1) = x \cdot (y_2 — y_1) + x_2 \cdot y_1 — x_1 \cdot y_2$.
Обозначим за $k_x$ множитель при $x$, за $k_y$ множитель при $y$, а всё остальное за $b$. Тогда имеем уравнение вида:
$y \cdot k_y = x \cdot k_x + b$, таких у нас будет 2:

  1. $y \cdot k_{y_1} = x \cdot k_{x_1} + b_1$
  2. $y \cdot k_{y_2} = x \cdot k_{x_2} + b_2$

Теперь рассмотрим несколько случаев:
1. Прямые параллельны, следовательно могут не иметь точки пересечения или совпадать.
Проверим совпадают ли $b_1$ и $b_2$. Так как уравнения не сокращены на НОД, то рассмотрим равенство отношений $b_1$ и $b_2$ на $k_{y_1}$, $k_{x_1}$ и $k_{y_2}$, $k_{x_2}$ соответственно. Если они равны, то прямые совпадают. Иначе не имеют точек пересечения, а следовательно и отрезки тоже не пересекаются.
Когда прямые совпадают, необходимо проверить, что отрезки на этой прямой имеют хоть какую-то общую точку. Каждый из концов каждого отрезка проверим на вхождение в другой. Если такое вхождение есть, то отрезки пересекаются, иначе нет.
2. Прямые не параллельны, а следовательно имеют точку пересечения.
Тогда, решив систему двух линейных уравнений в общем виде получим что:

  • $x = \frac{b_1 \cdot k_{x_2} — b_2 \cdot k_{x_1}}{k_{y_1} \cdot k_{x_2} — k_{x_1} \cdot k_{y_2}}$
  • $y = \frac{b_2 \cdot k_{y_1} — b_1 \cdot k_{y_2}}{k_{x_1} \cdot k_{y_2} — k_{y_1} \cdot k_{x_2}}$

Осталось проверить находится ли точка с координатами $(x, y)$ в каждом из отрезков. Для этого просуммируем расстояния от этой точки до границ каждого отрезка и сравним с длинами отрезков. Если суммы соответственно совпали с длинами, то отрезки пересекаются, иначе — нет.

Ссылки