e-olymp 4496. Приключение Незнайки и его друзей

Задача

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

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

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

В первой строке содержится количество человечков $n$ $(1 \leqslant n \leqslant 10^{6})$ в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают $10^{9}.$ Далее следует количество запросов $m$ $(1 \leqslant m \leqslant 10^{5})$. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число $v$ $(1 \leqslant v \leqslant 10^{9})$ – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа $x$ $(1 \leqslant x \leqslant n)$  и  $y$ $(1 \leqslant y \leqslant 10^{9})$ — это значит, что вес человечка, стоящего на позиции $x$, теперь равен $y$.

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

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

Тесты

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

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

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

Для решения данной задачи я воспользовалась структурой данных — дерево отрезков.
Её особенность заключается в том, что она предварительно производит некоторые вычисления, благодаря чему при частых однотипных вопросах можно быстрее давать ответ.
Функции построения и модификации элемента стандартные, а запрос на получение количества человечков, от грузоподъёмности воздушного шара — специфический. Рассмотрим принцип его работы:
Проверяем поместятся ли все человечки на воздушный шар, если нет, то делим их (условно на левых и правых) и проверяем для левой части данное условие, если помещаются все, то ответ находится в правой части, если нет, то в левой. Углубляемся по дереву до базового случая, когда нужно уточнить помещается ли последний человечек или нет. При спуске, отнимаем от заданной грузоподъемности шара вес человечков, которых мы уже посадили на шар.
В ответ выдаём номер последнего человечка поместившегося на шар, это и будет их количество, так как отсчёт мы вели с единицы.

Ссылки

e-olymp 2496. Конкатенация строк

Задача

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

В результате разворота строки $s$ получается строка $sR$, которая состоит из тех же символов, что и $s$, но идущих в обратном порядке. Например, в результате разворота строки «$abcde$» получается строка «$edcba$». Далее в этой задаче вместо обозначения $sR$ будет использоваться обозначение ($s$).

В результате конкатенации двух строк $s$ и $t$ получается строка $st$, в которой сначала записаны символы строки $s$, а затем — символы строки $t$. Аналогичным образом определяется конкатенация трех, четырех и большего числа строк. Например, при конкатенации строк «$abc$» и «$cda$» получается строка «$abccda$».

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

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

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

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

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

Выведите результат конкатенации.

Тесты

Входные данные Выходные данные
1 russ(ai)(edocn)cup russiancodecup
2 (bi).mazurok ib.mazurok
3 acm.(cpci) acm.icpc
4 Od(asse) Odessa
5 (inu)ver(ytis) university

Код программы(string)

Код программы (c-string)

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

Перебираем каждый символ входной строки, как только встречаем ‘(‘ рекурсивно запоминаем каждый символ, вплоть до ‘)’. А на выходе из рекурсии добавляем эти символы в результирующую строку. Так как при выходе рекурсия будет выполнять сначала самый поздний свой вызов, а только после этого завершать более ранние, то добавляться символы будут в обратном порядке, что нам и нужно. Повторяем вышеописанные действия до конца данной строки.

Ссылки

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)$ в каждом из отрезков. Для этого просуммируем расстояния от этой точки до границ каждого отрезка и сравним с длинами отрезков. Если суммы соответственно совпали с длинами, то отрезки пересекаются, иначе — нет.

Ссылки