Задача на реализацию


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 38282. Сборная Юпитера
Темы: Задача на реализацию   

Каждый год в одном из уголков нашей вселенной проходят Интеллектуальные Олимпийские Игры. В этом году честь проводить это масштабное мероприятие выпала планете Юпитер. Вам предстоит отобрать две команды на Игры из имеющихся n кандидатов в сборную.

Все кандидаты являются школьниками, каждый кандидат учится в определенном классе. Как и на Земле, на Юпитере 11 классов, пронумерованных от 1 до 11. На Игры отбирается две команды по результатам отборочных соревнований. На соревнованиях проводится пять отборочных туров. По итогам каждого тура каждый школьник может набрать от 0 до 300 баллов, чем больше, тем лучше.

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

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

Входные данные
Первая строка входных данных содержит единственное число n — количество кандидатов в сборную Юпитера ( 8 ≤ n ≤ 500 ).

Следующие n строк содержат информацию о кандидатах. Каждая строка содержит 6 целых чисел — номер класса, в котором учится очередной кандидат, и его результаты на отборочных турах.

Номер класса является числом от 1 до 11, а результат на каждом туре — числом от 0 до 300.

Гарантируется, что все участники имеют различные суммарные баллы.

Гарантируется, что есть хотя бы 8 кандидатов, обучающихся не в 11 классе.

Выходные данные
Выведите две строки.

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

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

Примеры
№ Входные данные Выходные данные
1 10
9 50 271 287 282 42
10 230 241 137 14 240
10 276 109 300 197 300
8 205 292 194 232 74
10 294 291 299 300 255
9 195 275 265 134 9
11 204 259 96 263 83
7 141 223 85 84 26
11 286 294 289 221 261
10 277 52 117 272 262		 3 4 5 9
1 2 6 10

ID 38623. Набор для торта
Темы: Комбинаторные структуры    Задача на реализацию   

Ушан с планеты Блук открыл пекарню. В его пекарне продается N видов тортов. Каждый вид торта имеет три параметра: «красота», «вкус» и «популярность». I-й вид торта имеет красоту xi, вкус yi и популярность zi. Эти значения могут быть нулевыми или отрицательными.
Громозека решил, что купит М кусочков торта. Он выбирает набор следующим образом:
- Нельзя использовать два и более куска одного и того же вида торта.
- При указанном выше условии выбирается набор тортов, который максимизирует (абсолютное значение общей красоты) + (абсолютное значение общего вкуса) + (абсолютное значение общей популярности).
Найдите максимально возможное значение (абсолютное значение общей красоты) + (абсолютное значение общего вкуса) + (абсолютное значение общей популярности) для набора тортов, который выберет Громозека.

Входные данные
В первой строке через пробел записаны два целых числа N (1<=N<=1000) и M (0<=M<=N). В следующих N строках записано по  три целых числа xi, yi и zi (-109<=xi, yi, zi <=109, 1<=i<=N).

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

 

Примеры
№ Входные данные Выходные данные Пояснение
1 5 3
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9		 56 Подумайте о 2-м, 4-м и 5-м видах тортов. Общая красота, вкус и популярность будут следующими:
Красота: 1 + 3 + 9 = 13
Вкус: 5 + 5 + 7 = 17
Популярность: 9 + 8 + 9 = 26
Значение (абсолютное значение общей красоты) + (абсолютное значение общей вкусовой привлекательности) + (абсолютное значение общей популярности) здесь равно 13 + 17 + 26 = 56. Это максимальное значение.
2 5 3
1 -2 3
-4 5 -6
7 -8 -9
-10 11 -12
13 -14 15		 54 Подумайте о том, чтобы иметь 1-й, 3-й и 5-й виды тортов. Общая красота, вкус и популярность будут следующими:

Красота: 1 + 7 + 13 = 21
Вкус: (−2) + (- 8) + (- 14) = - 24
Популярность: 3 + (- 9) + 15 = 9
Значение (абсолютное значение общей красоты) + (абсолютное значение общей вкусовой привлекательности) + (абсолютное значение общей популярности) здесь равно 21 + 24 + 9 = 54. Это максимальное значение.
3 10 5
10 -80 21
23 8 38
-94 28 11
-26 -2 18
-69 72 79
-26 -86 -54
-72 -50 59
21 65 -32
40 -94 87
-62 18 82		 638 Если у нас есть 3-й, 4-й, 5-й, 7-й и 10-й виды тортов, общая красота, вкус и популярность будут -323, 66 и 249 соответственно.
Значение (абсолютное значение общей красоты) + (абсолютное значение общей вкусовой привлекательности) + (абсолютное значение общей популярности) здесь равно 323 + 66 + 249 = 638. Это максимальное значение.
4 3 2
2000000000 -9000000000 4000000000
7000000000 -5000000000 3000000000
6000000000 -1000000000 8000000000		 30000000000 Значения красоты, вкуса и популярности тортов, а также значение, которое будет напечатано, могут не соответствовать 32-битным целым числам.

 
ID 38873. Комната
Темы: Задача на реализацию   

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

Входные данные
На вход подаётся три целых числа: w, l и h — длина, ширина и высота комнаты, каждое
на отдельной строке (1000 ≤ w, l, h ≤ 10 000).

Выходные данные
Если комната является хорошей, выведите «good», иначе выведите «bad».
 

Примеры
№ Входные данные Выходные данные
1 4000
6000
3000		 bad
2 4600
8600
1600		 good

ID 39062. Сломанный принтер
Темы: Циклы    Задача на реализацию   

Сломанный цветной принтер, печатая цифры, закрашивает все замкнутые области в красный цвет.  Например, в цифрах 0, 4, 6, 9 одна замкнутая область. В цифре 8 - 2 замкнутых области.  В других цифрах нет замкнутых областей, которые закрашиваются. В принтере красной краски осталось на покраску h замкнутых областей.  Найдите минимальное неотрицательное число, напечатав которое в принтере закончится красная краска. Число не должно содержать ведущих нулей.  Если в принтере отсутствует красная краска, то он не может напечатать цифру с замкнутой областью.


Входные данные
На вход подается число h (0 <= h <= 510).

Выходные данные
Выведите число, которое необходимо напечатать.
 
Примеры
№ Входные данные Выходные данные
1 15 48888888
2 70 88888888888888888888888888888888888

ID 39388. Отслеживание контактов
Темы: Задача на реализацию    Задачи на моделирование   

Фермер Джон продолжает заботиться о здоровье своих коров, последовательно пронумерованных 1…N.
Недавно ФД проверил их всех и выяснил, что некоторые из них больны. Используя видео из амбара, ФД может узнать какие пары коров взаимодействовали распространяя при этом болезнь. ФД собрал список с указанием времени, в которое происходило взаимодействие пар коров в видео (t,x,y), означающем, что в момент времени t корова x взаимодействовала с коровой y. Также ФД знает следующее:

  1.  Ровно одна корова была инфицирована изначально (нулевой пациент).
  2.  После того, кк корова инфицирована, она передаёт инфекцию её следующим K взаимодействиям (возможно включая одного и того же партнера несколько раз). После K раз передачи инфекций, она перестаёт передавать инфекцию (осознав что заражает, она начинает тщательно мыть копыта).
  3.  Однажды заболев, она остаётся больной.

К несчастью, ФД не знает, какая из его N коров, является "нулевым пациентом", кроме того он не знает значение K!. Помогите ему сузить диапазоны этих неизвестных, основываясь на его данных. Гарантируется, что ответ существует.

Входные данные
Первая строка ввода содержит N (2≤N≤100) и T (1≤T≤250). Следующая строка содержит строку длиной N, состоящую из 0 и 1, описывающую текущее состояние N коров ФД, 0 - здорова, 1 - больна. Каждая из последующих T строк описывает запись из списка взаимодействий ФД, и состоит из трёх чисел, t, x, y, где t - положительное целое время взаимодействия (t≤250), x и y - различные целые в интервале 1…N,, указывающее какие коровы взаимодействовали в момент времени T. В один момент времени T происходит не более одного взаимодействия.
Выходные данные
Выведите одну строку, содержащую три целых числа x, y, z, где x - количество различных коров, которые могли быть "нулевым пациентом" y - минимально возможное значение K, подходящее к исходным данным z - наибольшее возможное значение K, подходящее к исходным данным Если для K нет верхней границы, выведите "Infinity" для z. Заметим, что возможно K=0.
Примеры
№ Входные данные Выходные данные
1 4 3
1100
7 1 2
5 2 3
6 2 4		 1 1 Infinity

ID 39397. Громозека и Алиса - 2
Темы: Задача на реализацию    Одномерные массивы    Циклы   

Алиса и Громозека пошли гулять по городу. Заходя в первое кафе, Алиса посмотрела на часы и запомнила время входа. Далее она запоминала только количество минут, которое они с Громозекой тратили между двумя посещенными кафе (от входа в одно кафе, до входа в другое). По окончании прогулки, Алиса решила восстановить хронологию - время входа в очередное кафе.
Напишите программу, которая определит, в какое время Алиса и Громозека заходили в очередное кафе. 

Входные данные
В первой строке задан, момент времени, в который Громозека и Алиса вошли в первое кафе. Формат времени: часы (число от 00 до 23), далее идет двоеточие, затем минуты (число от 00 до 59). Строка времени записана без пробелов.
Во второй строке записано натуральное число N (2 <= N <= 1000) - количество посещенных кафе (включая кафе из которого они вышли в начальный момент времени и последнее кафе). В третьей строке записано N-1 число: первое показывает время в минутах от входа в первое кафе до входа во второе, второе - время от входа во второе кафе до входа в третье и т.д. Каждое из этих чисел натуральное и не превышает 1000.

Выходные данные
Выведите для каждого кафе время входа Алисы и Громозеки. Формат времени должен быть такой же, как и во входных данных.
 

Примеры
№ Входные данные Выходные данные
1 07:00
4
10 5 3		 07:00
07:10
07:15
07:18

ID 27222. Where's Bessie?
Темы: Обход в глубину    Перебор    Задача на реализацию   

Фермер Джон тестирует новую камеру, которая может "схватить картинку" и автоматически вычислить положение коров. К несчастью, у камеры не очень хороший алгоритм поиска коров и ФД нуждается в Вашей помощи.
Картинка, получаемая камерой, может быть описана решёткой из N×N символов, каждый в интервале A…Z, представляющих один из 26 возможных различных цветов. ФД считает наилучшим такой алгоритм распознавания коров: PCL (возможное размещение коровы) - это прямоугольник на решётке (возможно вся решётка) со сторонами параллельными сторонам решётки, не содержащий внутри других PCL и обладающий следующим свойством: внутри этого прямоугольника должны присутствовать ровно два цвета, один формирует непрерывный регион, а другой формирует два или более непрерывных регионов.
 
Например, такой образ
 
AAAAA
ABABA
AAABB
есть PCL, поскольку символы A формируют непрерывный регион, символы B форрмируют более одного непрерывного региона. Интерпретация - это корова с цветом A и с пятнами цвета B.
 
Регион является непрерывным, если вы может пройти его весь, перемещаясь из одной клетки в другую соседнюю по направлениям вверх, вниз, влево, вправо.
 
По заданному образу камеры ФД определите количество PCL.
 
ФОРМАТ ВВОДА:
 
Первая строка ввода содержит N, размер решётки (1≤N≤20). Следующие N строк описывают образ, каждая состоит из N символов.
 
ФОРМАТ ВЫВОДА:
 
Количество PCL в образе.
 
Ввод Вывод
4
ABBC
BBBC
AABB
ABBC
 2

ID 43349. Секретная последовательность
Темы: "Два указателя"    Одномерные массивы    Задача на реализацию   

Алиса оставила для своего отца профессора Селезнева секретную последовательность a[1..n]. Чтобы ее не прятать, она решила написать ее на самом видном месте, но в другом порядке следования чисел. Профессор Селезнев знает, что Алиса переписала секретную последовательность в следующем виде:

  • первым числом слева записано число a1;
  •  первым числом справа записано число a2;
  • вторым числом слева (после a1) записано число a3;
  • вторым числом справа (то есть перед числом a2) записано число a4;
  • все остальные числа записаны аналогичным образом.

То есть, если бы секретная последовательность была a = [1, 2, 3, 4, 5, 6], то профессор бы увидел следующую последовательность [1, 3, 5, 6, 4, 2]. Профессор Селезнев очень торопился и успел только сохранить в компьютер последовательность, которую увидел. Напишите программу, которая покажет профессору исходную секретную последовательность.



Входные данные
Первая строка содержит размер последовательности n (1 <= n <= 300), записанной Алисой для своего отца. Вторая строка содержит n чисел ai (1 <= ai <= 109) - саму последовательность.

Выходные данные
Выведите исходную последовательность, которую Алиса выписывала для отца.
 
 
Примеры
№ Входные данные Выходные данные
1

6
1 3 5 6 4 2

 1 2 3 4 5 6
2 1
23		 23

 
ID 43351. Книги Томми
Темы: "Два указателя"    Бинарный поиск    Задача на реализацию   

Томми очень любит читать. Он взял из библиотеки n книг (в i-й книге ai страниц, страницы нумеруются с 1). Томми очень бережно относится к книгам, поэтому каждую из них обернул в обложку. Но, так как у него не оказалось ни одной прозрачной обложки, он пронумеровал книжки от 1 до n и написал номер на обложке каждой книги.

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

Например, если бы Томми взял 2 книги и, при этом, в в первой книге 3 страницы, а во второй - 5 страниц, то прочитав в первый день 2 страницы, а во второй день - 4 страницы у Томми на доске было бы записано два числа 2 и 6.

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


Входные данные
Программа получает на вход несколько строк. Первая строка содержит два целых числа n и m (1 <= n, n <= 2·105) - количество книг, взятых Томми из библиотеки и количество дней, в течении которых Томми читал книги. Во второй строке следует последовательность a1, a2, ... an (1 <= a1<= 1010), где ai равно количеству страниц в i-й книге. В третьей строке следует последовательность d1, d2, ... dm (1 <= dj <= a1 + a2 +...+ an), где dj равно общему числу страниц, прочитанных Томми к j-му дню. Все dj заданы в порядке возрастания.

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

Выведите m строк. В каждой строке выведите по два числа - номер книги k (1 <= k <= n) и номер страницы в этой книге s (1 <= s <= ak), на которой остановился Томми в текущий день.

 
Примеры
№ Входные данные Выходные данные
1 3 6
10 15 12
1 9 12 13 15 17		 1 1
1 9
2 2
2 3
2 5
2 7
2 2 3
5 10000000000
5 6 9999999999		 1 5
2 1
2 9999999994

ID 43474. Громозека и валерьянка
Темы: Цикл for    Циклы    Простые задачи на перебор    Задача на реализацию   

Громозека очень любит валерьянку. На его родной планете Чумароза можно купить за k чумриков (местная валюта) первую упаковку валерьянки, за 2·k чумриков - вторую и так далее (иными словами, за i-ю упаковку надо заплатить i·k чумриков). Громозека хочет купить w упаковок валерьянки.  У него есть n чумриков. Сколько чумриков ему придется взять в кредит в чумарозском банке, чтобы купить w упаковок валерьянки?


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

В первой строке записано три положительных целых числа k, n, w (1  <=  k, w  <=  1000, 0 <= n <= 109), стоимость первой упаковки, изначальное количество чумарозиков у Громозеки и количество упаковок валерьянки, которые он хочет купить.


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

Выведите единственное целое число - количество чумарозиков, которое Громозеке необходимо взять в кредит в банке. Если брать кредит не надо, выведите 0.

 
Примеры
№ Входные данные Выходные данные
1 3 17 4 13

ID 43532. Книжки с полки
Темы: Одномерные массивы    Задача на реализацию   

Петя обладает обширной библиотекой книг. Сейчас он стоит возле полки с приключенческими рассказами. На ней расположены n книг. Все книги на полке у Пети всегда пронумерованы слева направо. Книга с номером i имеет ai страниц. На полке, возле которой сейчас стоит Петя, количество страниц в каждой книге различно.

Особенность полок в библиотеке Пети такова, что он может брать только крайнюю книгу с полки (то есть либо самую левую, либо самую правую).

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

 

Входные данные
В первой строке записано одно целое число n (2 <= n <= 100) - количество книг на полке. Во второй строке находится n целых различных чисел a1, a2, ..., an (1 <= ai <= 106) - количество страниц в книге.

 

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

 
Примеры
№ Входные данные Выходные данные
1 
5
1 5 4 3 2
 
2
2 
8
2 1 3 4 5 6 8 7
 
4

ID 43718. Мишины кубики
Темы: Использование сортировки    Жадный алгоритм    Задача на реализацию    Простые задачи на перебор    "Два указателя"   

У маленького Миши есть кубики, на каждом из которых написана одна английская строчная буква. Вчера он выкладывал кубики в два ряда. В первом ряду у Миши n кубиков с буквами, во втором - m кубиков с буквами. Так получилось, что в двух этих рядах нет совпадающих букв. Другими словами, ни одна буква не содержится одновременно в обоих рядах.
Сегодня маленький Миша решил продолжить играть с кубиками. Но теперь он берет один любой кубик из какого-либо ряда и составляет из них третий ряд, добавляя кубик всегда в конец. Маленький Миша никогда не берет более k кубиков подряд из одного и того же ряда. Миша закончил играть тогда, когда у него закончились кубики в каком-то одном ряду (в первом или во втором).
Наблюдавший за игрой папа заметил, что играя таким образом у Миши получилась лексикографически наименьшая строка. По известным двум строкам, которые образуются путем прочтения букв первого и второго ряда и числу k определите строку, которую получил маленький Миша.

Строка x лексикографически меньше строки y только и только тогда, когда выполняется одно из следующих условий:
- x является префиксом y, но x != y;
- в первой позиции, где x и y различаются, в строке x находится буква, которая стоит в алфавите раньше, чем соответствующая буква y.


Входные данные
Программа получает на вход несколько строк. В первой строке записаны три числа: n - количество кубиков в первом ряду, m - количество кубиков во втором ряду, k - целое число(1 <= n, m, k <= 100). Во второй строке записана строка a длиной n - строка, образованная прочтением букв, написанных на кубиках первого ряда. В третьей строке - строка b длиной m - строка, образованная прочтением букв, написанных на кубиках второго ряда.

Выходные данные
Выведите ответ на задачу.
 
 

Примеры
№ Входные данные Выходные данные
1 6 4 2
aaaaaa
bbbb		 aabaabaa