Темы --> Информатика --> Язык программирования
    Процедуры и функции(96 задач)
    Массивы(232 задач)
    Типы данных(356 задач)
    Циклы(177 задач)
    Условный оператор (if)(164 задач)
    Python(260 задач)
    Standard Template Library(2 задач)
---> 952 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 181 182 183 184 185 186 187 >> Отображать по:
#113538
Вечеринка Петара
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Вечеринка Петара ]
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
32 megabytes

Петар организует вечеринку по случаю своего дня рождения и планирует пригласить некоторых сотрудников из компании, где он работает генеральным директором. Каждый сотрудник, включая Петара, имеет уникальный номер от 1 до N и тип шуток, которые он рассказывает, V i . Также, каждый сотрудник в компании кроме Петара имеет ровно одного начальника. Так как Петар - генеральный директор компании, он имеет номер 1 и руководит всеми сотрудниками (не обязательно напрямую).

На вечеринке есть некоторые правила, которым должны отвечать все присутствующие: 1. На вечеринке не должно быть двух людей с одинаковым типом шуток. 2. Человек не может быть приглашен на вечеринку, если на нее не приглашен его прямой начальник. 3. Человек не может быть приглашен на вечеринку, если типы шуток, которые рассказывает он и его приглашенные подчиненные, не образуют последовательное множество.

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

Последовательное множество - такое множество, в котором, если отсортировать его по возрастанию, разность между соседними элементами будет равна 1. Например (3, 1, 2) и (5, 1, 2, 4, 3) - последовательные множества, а (2, 5, 3) - нет.

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

Первая строка содержит одно целое число N ( 1 ≤ N ≤ 10000 ). Вторая строка содержит N целых чисел V i - типы шуток, рассказываемые i -м человеком ( 1 ≤ V i ≤ 100 ). Каждая из следующих N - 1 строк содержит два целых числа A и B ( 1 ≤ A , B ≤ N ), обозначающих что сотрудник с номером A является прямым начальником сотрудника с номером B .

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

Выведите единственное число - количество возможных наборов типов шуток на вечеринке.

Примеры
Входные данные
4
2 1 3 4
1 2
1 3
3 4
Выходные данные
6
Входные данные
4
3 4 5 6
1 2
1 3
2 4
Выходные данные
3
Входные данные
6
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6
Выходные данные
10
#113540
Игра Мирко
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Игра Мирко ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Мирко большой любитель шахмат и программирования, но обычные шахматы уже наскучили ему, поэтому он начал экспериментировать и придумал свою игру. Он взял шахматную доску с N рядами и N столбцами и расположил на ней K ладей. Игра Мирко следует таким правилам: 1. У каждой ладьи есть своя сила, заданная натуральным числом. 2. Ладья видит все клетки поля в своем ряду и своем столбце кроме той, на которой стоит сама. 3. Клетка считается атакованной в том случае, если побитовый XOR сил всех ладей, которые видят эту клетку, положителен. Изначально Мирко некоторым образом расположил ладьи на поле, и теперь собирается сделать P перемещений. Каждый раз он будет брать одну ладью и ставить ее на другую клетку поля (при этом ладья не обязательно будет перемещена вдоль ряда или столбца в котором она стоит). После каждого перемещения, определите сколько клеток на поле атакованы.

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

Первая строка содержит 3 целых числа N , K , P ( 1 ≤ N ≤ 1000000000 , 1 ≤ K , P ≤ 10000 ). Каждая из следующих K строк содержит 3 натуральных числа R i , C i , X i ( 1 ≤ R i , C i ≤ N , 1 ≤ X i ≤ 1000000000 ), которые обозначают что на клетке ( R i , C i ) стоит ладья с силой X i . Каждая из следующих P строк содержит 4 натуральных числа R 1 , C 1 , R 2 , C 2 ( 1 ≤ R 1, C 1, R 2, C 2 ≤ N ), которые означают что ладья, стоящая на клетке ( R 1, C 1 ), была передвинута на поле ( R 2, C 2 ). Гарантируется, что в момент перемещения на клетке ( R 1, C 1 ) есть ладья и что ни в какой момент времени на одной клетке нет двух и более ладей.

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

Выведите P строк, где в k -й строке записано единственное число - количество клеток поля, атакованных после первых k перемещений.

Примеры
Входные данные
2 2 2
1 1 1
2 2 1
2 2 2 1
1 1 1 2
Выходные данные
4
0
Входные данные
2 2 2
1 1 1
2 2 2
2 2 2 1
1 1 1 2
Выходные данные
4
2
Входные данные
3 3 4
1 1 1
2 2 2
2 3 3
2 3 3 3
3 3 3 1
1 1 1 2
3 1 3 2
Выходные данные
6
7
7
9
#113542
Карты
  
Темы: [Массивы]
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Карты ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
32 megabytes

Недавно Пьеро увлекся робототехникой, поэтому он решил создать робота, который проверяет колоду игральных карт на полноту. Он уже выполнил значительную часть работы - он написал программу, которая распознает ярлыки карт. Для простоты будем считать, что у всех карт есть масть и номер. Масть карты является одним из символов P , K , H , T , а номер карты является целым числом от 1 до 13. Робот отмечает каждую карту в формате TXY, где T - масть, а XY - номер. Если номер карты состоит из одной цифры, то X = 0. Например, масть P и номер 9 обозначаются как P09. Полная колода имеет 52 карты - для каждой из четырех мастей есть ровно одна карта с номером от 1 до 13. Робот прочитал ярлыки всех карт в колоде и объединил их в строку S . Помогите Пьеро закончить робота, написав программу, которая читает строку, сделанную из карточных ярлыков и выводит, сколько карт отсутствует для каждой масти. Если в колоде есть две одинаковые карты, выведите GRESKA (ОШИБКА на хорватском).

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

Единственная строка S ( 1 ≤ S ≤ 1000 ), содержащая ярлыки всех карт.

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

Если в колоде есть 2 одинаковые карты, выведите “GRESKA”. Иначе в единственной строке выведите через пробел четыре целых числа - количество отсутствующих карт мастей P , K , H , T соответственно.

Примеры
Входные данные
P01K02H03H04
Выходные данные
12 12 11 13
Входные данные
H02H10P11H02
Выходные данные
GRESKA
Входные данные
P10K10H10T01
Выходные данные
12 12 12 12
#113543
Акция
  
Темы: [Массивы]
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Акция ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
32 megabytes

В местном книжном магазине акция: "Возьми 3, заплати за 2 самых дорогих". То есть, каждый покупатель, который возьмет 3 книги, получит самую дешевую из них бесплатно. Разумеется, он может взять и больше книг, и, некоторым образом разделив их на группы по 3, получать самую дешевую в каждой группе бесплатно. Например, пусть цены книг, выбранных покупателем, будут следующие: 10 3 2 4 6 4 9. Он может разделить их на группы таким образом: (10, 3, 2), (4, 6, 4), (9). Тогда он получит книгу стоимостью 2 из первой группы и книгу стоимостью 4 из второй группы бесплатно. При этом из третьей группы он ничего не получит бесплатно, так как в ней всего 1 книга. Девушка, работающая в магазине, очень добрая и всегда хочет помочь покупателю заплатить как можно меньше денег за выбранные книги. Помогите ей для выбранных покупателем книг распределить их по группам так, чтобы сумма денег, в результате заплаченная покупателем, была минимальна.

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

В первой строке записано одно натуральное число N ( 1 ≤ N ≤ 100000 ) - количество книг, выбранных покупателем. В каждой из следующих N строк записано одно натуральное число C i ( 1 ≤ C i ≤ 100000 ) - цена соответствующей книги.

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

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

Примеры
Входные данные
4
3
2
3
2
Выходные данные
8
Входные данные
6
6
4
5
5
5
5
Выходные данные
21
#113551
Траектория обучения
  
Темы: [Рекурсия] [Стек]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

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

Программа обучения первого университета состоит из последовательности перечисленных в хронологическом порядке n различных дисциплин a1, a2, ..., an, имеющих рейтинги x1, x2, ..., xn соответственно. Программа обучения второго университета состоит из последовательности перечисленных в хронологическом порядке m различных дисциплин b1, b2, ..., bm, имеющих рейтинги y1, y2, ..., ym соответственно.

Студент имеет возможность составить план обучения в первом университете таким образом, чтобы изучить дисциплины на позициях учебной программы с la по ra включительно (1 ≤ la ≤ ra ≤ n), либо отказаться от стажировки в первом университете. Аналогично он может составить план обучения во втором университете таким образом, чтобы изучить дисциплины на позициях учебной программы с lb по rb включительно (1 ≤ lb ≤ rb ≤ m), либо отказаться от стажировки во втором университете.

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

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

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

Первая строка входных данных содержит целые числа n и m — количество дисциплин в программах обучения первого и второго университетов (1 ≤ n, m ≤ 500 000).

Вторая строка входных данных содержит n целых чисел ai — дисциплины, входящие в программу обучения первого университета, перечисленные в хронологическом порядке (1 ≤ ai ≤ n + m).

Третья строка входных данных содержит n целых чисел xi — рейтинги дисциплин, входящих в программу обучения первого университета, перечисленные том же порядке, что и дисциплины ai (1 ≤ xi ≤ 109).

Четвёртая строка входных данных содержит m целых чисел bi — дисциплины, входящие в программу обучения второго университета, перечисленные в хронологическом порядке (1 ≤ bi ≤ n + m).

Пятая строка входных данных содержит m целых чисел yi — рейтинги дисциплин, входящих в программу обучения второго университета, перечисленные том же порядке, что и дисциплины bi (1 ≤ yi ≤ 109).

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

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

Вторая строка выходных данных должна содержать целые числа la, ra — позиции в учебной программе первой и последней дисциплин, входящих в план обучения в первом университете, либо «0 0», если студент отказался от стажировки в первом университете.

Третья строка выходных данных должна содержать целые числа lb, rb — позиции в учебной программе первой и последней дисциплин, входящих в план обучения во втором университете, либо «0 0», если студент отказался от стажировки во втором университете.

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

Примечание

В первом тесте из условия приведённые планы обучения в университетах приводят к суммарному рейтингу дисциплин (7 + 4 + 10 + 1 + 5) + (5 + 3 + 4) = 27 + 12 = 39. Если бы студент выбрал только вторую и третью дисциплины в первом университете и весь курс обучения во втором университете, суммарный рейтинг дисциплин был бы (7 + 4) + (3 + 5 + 3 + 4 + 12) = 11 + 27 = 38.

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

Примеры
Входные данные
7 5
3 1 4 8 6 9 2
2 7 4 10 1 5 3
9 2 11 3 8
3 5 3 4 12
Выходные данные
39
2 6
2 4
Входные данные
2 3
1 2
1 4
2 3 1
17 2 15
Выходные данные
34
0 0
1 3
Входные данные
3 3
4 2 1
10 1 2
5 4 2
1 2 9
Выходные данные
19
1 1
3 3
Страница: << 181 182 183 184 185 186 187 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест