Страница: 1 2 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes
Дано $n$ троек чисел $(a_i, b_i, c_i)$.Требуется найти количество пар индексов $i < j$ таких, что они равны по ровно одному индексу

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

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

Требуется написать программу, которая по данным $n$ тройкам ($a_i , b_i , c_i$) значений характеристик каждого из пользователей определяет количество пар потенциальных друзей, то есть таких пар индексов $i < j$, что из трёх равенств $a_i = a_j , b_i = b_j , c_i = c_j$ выполняется ровно одно.

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

Первая строка входных данных содержит число $n$ — количество пользователей. Каждая из последующих $n$ строк содержит три целых положительных числа $a_i , b_i и c_i$ — значения характеристик $i$-го пользователя

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

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

Таблица системы оценивания
Номер подзадачи Баллы Ограничения
$n$ $a_i, b_i, c_i$
1 45 $1 \leq n \leq 100$
$1 \leq a_i, b_i, c_i \leq 50$
2 55 $1 \leq n \leq 100\,000$ $1 \leq a_i, b_i, c_i \leq 100$
Пояснения к примеру

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

Примеры
Входные данные
3
1 2 3
1 4 5
1 2 4
Выходные данные
2
Входные данные
4
100 100 100
100 100 100
100 99 99
99 99 100
Выходные данные
5
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes
Требовалось разместить клетчато-выпуклый многоугольник на поле так, чтобы он занимал как можно меньше плиток размерами $1 \times k$; Плитки, которые покрываются не полностью, следует учитывать.

Одна из центральных площадей Архангельска замощена прямоугольными плитками размера $1 \times k$. Если ввести систему координат, так что левый нижний угол одной из плиток будет иметь координаты (0, 0), то левые нижние углы плиток будут иметь координаты ($i · k + j, j$) для всех целых $i$ и $j$.

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

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

Требуется написать программу, вычисляющую минимальное количество плиток, которые придётся удалить.

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

Первая строка входных данных содержит два числа $n$ и $k$ — количество вершин в основании памятника и размер плитки.

Каждая из последующих $n$ строк содержит два целых числа $x_i$ , $y_i$ — координаты $i$-й вершины основания. Координаты перечислены в порядке обхода против часовой стрелки.

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

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

Таблица системы оценивания

Замечание

Примеры
Входные данные
12 3
2 3
1 3
1 2
3 2
3 1
8 1
8 2
10 2
10 3
8 3
8 4
2 4
Выходные данные
7
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes
Дано изображение дерева из $n$ вершин на прямоугольной сетке. Каждое ребро — либо вертикальный, либо горизонтальный отрезок длины $1$ Дано $q$ запросов, каждый имеет вид "сколько компонент связности образуется при вырезании данного прямоугольного фрагмента"

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

Одно из таких праздничных полотенец находится в музее. К сожалению, некоторые части узора были утеряны, но описание полотенца сохранилось. Дирекция музея планирует восстановить один из прямоугольных фрагментов полотенца, но не ещё не решила какой именно. Затраты на восстановление фрагмента зависят от количества связных частей узора, попавших на этот фрагмент. Часть узора считается связной, если от любой её жемчужины можно по стежкам перейти к любой другой её жемчужине, не выходя за границы фрагмента. Дирекция всегда относит любые две жемчужины, между которыми можно перейти по стежкам, к одной и той же связной части узора.

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

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

Первая строка входных данных содержит два целых числа a и b — размеры полотенца в клетках по горизонтали и вертикали.

Вторая строка содержит два числа $n$ и $q$ — количество жемчужин в узоре и количество фрагментов соответственно.

Следующие ($n − 1$) строк содержат описания стежков. Каждый стежок имеет один из следующих видов:

• $h \times y$ означает, что клетки с координатами $(x, y)$ и $(x + 1, y)$ содержат жемчужины, соединённые горизонтальным стежком ($1 \le x \le a − 1; 1 \le y \le b$);

• $v \times y$ означает, что клетки с координатами $(x, y)$ и $(x, y + 1)$ содержат жемчужины, соединённые вертикальным стежком ($1 \le x \le a; 1 \le y \le b − 1$).

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

Следующие $q$ строк описывают фрагменты. Каждое описание содержит четыре целых числа $x_1$, $y_1$, $x_2$ и $y_2$ — координаты левой нижней и правой верхней клетки фрагмента ($1 \le x_1 \le x_2 \le a; 1 \le y_1 \le y_2 \le b$).

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

Выходные данные должны содержать $q$ строк, где $i$-я строка содержит количество связных частей узора в $i$-м фрагменте.

Таблица системы оценивания

Замечание

Пояснение к тесту из условия

Примеры
Входные данные
4 3
8 4
v 1 1
h 1 1
h 2 1
v 2 1
v 2 2
h 1 3
h 3 1
1 1 4 3
3 2 4 3
3 1 3 1
1 2 3 3
Выходные данные
1
0
1
2
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

На кафедре пингвиноведения Южного Антарктического университета проводятся исследования популяций пингвинов. Фотографии скоплений плотно стоящих пингвинов обрабатываются студентами. Распознавание пингвинов на снимках производится следующим образом: на фотографии выбирается характерная полоса высотой в один пиксель, каждый пиксель которой входит в изображение одного из пингвинов.

У всех пингвинов исследуемой популяции живот белый, а спина и крылья — чёрные. Таким образом, если у пингвина на фотографии видна только спина, то на характерной полосе ему соответствует отрезок из чёрных пикселей, а если только живот, то из белых. В остальных случаях, например, когда чёрные крылья видны поверх белого живота, пингвину соответствует отрезок из чёрных и белых пикселей. Для продолжения исследований необходимо, чтобы каждому пингвину соответствовал отрезок, состоящий либо только из чёрных, либо только из белых пикселей.

Для $i$-й фотографии известно максимальное количество пингвинов $k_i$, изображение которых могло попасть на характерную полосу. Поэтому эту полосу пикселей необходимо заменить на упрощённую полосу той же длины, которая будет состоять не более чем из $k_i$ отрезков, каждый из которых либо полностью чёрный, либо полностью белый. Из всех возможных упрощённых полос нужно выбрать оптимальную — то есть ту, которая получается из характерной путём изменения цвета минимального числа пикселей.

Требуется написать программу, решающую поставленную задачу.

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

В первой строке входных данных содержится число $t$ — количество фотографий. Далее следуют $t$ пар строк, $i$-я пара строк описывает i-ю фотографию.

Первая строка описания фотографии содержит два числа: $n_i$ — длину характерной полосы $i$-й фотографии, и $k_i$ — максимальное количество пингвинов, которые могут быть на ней изображены ($k_i \le n_i$).

Вторая строка описания состоит из $n_i$ символов 0 и 1, где 0 обозначает чёрный, а 1 — белый пиксель.

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

Выходные данные должны содержать $t$ строк, где $i$-я строка состоит из $n_i$ символов 0 и 1 и описывает упрощённую полосу, полученную из характерной полосы $i$-й фотографии. Если оптимальных упрощённых полос несколько, выведите любую из них.

Таблица системы оценивания

Примеры
Входные данные
3
9 3
000111000
10 3
0111011010
4 4
0001
Выходные данные
000111000
0111111000
0001
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

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

Для упрощения бухгалтерского учёта фонд принял следующие решения:

• размер любого гранта в денежных единицах должен быть степенью числа 2, то есть равен $2^k$ для некоторого целого $k \ge 0$;

• все гранты, получаемые одной организацией в одном году, должны иметь различные размеры.

В $i$-м году фонд планирует полностью распределить $n_i$ денежных единиц, выделенных на гранты. Сравнивать результативность использования средств возможно только для грантов одинакового размера, выделенных каждой из трёх организаций. Такие гранты называются целевыми. Распределение денежных единиц на гранты между тремя организациям считается оптимальным, если как можно б´oльшая часть общей суммы выделена на целевые гранты.

Например, если в текущем году на все гранты выделено 47 денежных единиц, то оптимальным вариантом распределения будет: выделить каждой из организаций целевые гранты размерами по 2 и 8 денежных единиц, что составит в сумме 30 единиц. Остальные 17 единиц можно распределить, например, выделив первой организации 16 денежных единиц, а третьей — 1 денежную единицу. Выделить более 30 денежных единиц на целевые гранты, распределяя 47 денежных единиц, нельзя.

Требуется написать программу, которая по заданной в $i$-м году общей сумме грантов $n_i$ определяет, сколько денежных единиц следует выделить каждой из трёх организаций при оптимальном распределении грантов.

Более формально (будущим участникам заключительного этапа дальше не читать :) ), требуется найти такие три числа $a$, $b$ и $c$, что $a+b+c=n$, при этом требуется максимизировать $a \& b \& c$, где "&" обозначает побитовое <<И>>.

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

В первой строке входных данных записано целое число $t$ — количество лет ($1 \le t \le 100$). В каждой из последующих $t$ строк записано целое число $n_i$ — общая сумма грантов, которую необходимо полностью распределить в $i$-м году.

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

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

Таблица системы оценивания

Примеры
Входные данные
3
4
21
47
Выходные данные
4 0 0
7 7 7
27 10 10

Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест