1.Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
6
1 3
5 12
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 32.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
2. На вход программы поступает последовательность из целых положительных чисел. Необходимо выбрать такую подпоследовательность подряд идущих чисел, чтобы их сумма была максимальной и делилась на 89, а также её длину. Если таких подпоследовательностей несколько, выбрать такую, у которой длина меньше.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 68000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10000. Программа должна вывести длину найденной последовательности.
Пример входного файла:
8
2
3
4
93
42
34
5
95
Для делителя 50 при указанных входных данных значением искомой суммы должно быть число 100 (3 + 4 + 93 или 5 + 95). Следовательно, ответ на задачу — 2. В ответе укажите два числа: сначала значение искомой длины для файла A, затем для файла B.
3. Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
14
1
2
1
4
93
8
5
95
6
4
3
2
8
6
В ответе укажите два числа: сначала значение искомой длины для файла А, затем — для файла B. Для приведенного примера ответ — 7.
4. На каждом 3-м километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна 3N километров. Нулевой километр и 3N-й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров. Из каждого пункта мусор вывозит отдельный мусоровоз. Стоимость доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Центр переработки отходов открыли в одном из пунктов сбора мусора таким образом, чтобы общая стоимость доставки мусора из всех пунктов в этот центр была минимальной.
Определите минимальные расходы на доставку мусора в центр переработки отходов.
Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) — количество пунктов сбора мусора на кольцевой автодороге. В каждой из следующих N строк находится число — количество мусора в контейнере (все числа натуральные, количество мусора в каждом пункте не превышает 1000). Числа указаны в порядке расположения контейнеров на автомагистрали, начиная с первого километра.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем — для файла B.
Типовой пример организации данных во входном файле:
6
8
20
5
13
7
19
При таких исходных данных, если контейнеры установлены на каждом километре автодороги, необходимо открыть центр переработки в пункте 6. В этом случае сумма транспортных затрат составит: 1 · 7 + 0 · 19 + 1 · 8 + 2 · 20 + 3 · 5 + 2 · 13.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
5. У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.
Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.
Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.
Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) — количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000). Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем — для файла B.
Пример организации исходных данных во входном файле:
6
1 100
2 200
5 4
7 3
8 2
10 190
При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит:
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
6. Метеорологическая станция ведёт наблюдение за количеством выпавших осадков. Показания записываются каждую минуту в течение N минут.
Определяется пара измерений, между которыми прошло не менее K минут. Найдите максимальную сумму показаний среди таких пар.
Даны два входных файла (A и B), каждый из которых в первой строке содержит число N — количество измерений, во второй строке K — минимальное количество минут между искомыми измерениями. В каждой из следующих N строк находится число: количество выпавших осадков.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем — для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
7. По каналу связи передаётся последовательность целых неотрицательных чисел — показания прибора, полученные с интервалом в 1 мин. в течение T мин. (T — целое число). Прибор измеряет количество атмосферных осадков, полученное регистратором за минуту, предшествующую моменту регистрации, и передаёт это значение в условных единицах измерения
Определите два таких переданных числа, чтобы между моментами их передачи прошло не менее K мин., а их сумма была максимально возможной. Укажите найденное суммарное количество осадков.
Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число K — количество минут, которое должно пройти между двумя передачами показаний, а во второй — количество переданных показаний N (1 ≤ N ≤ 10 000 000, N > K). В каждой из следующих N строк находится одно целое неотрицательное число, не превышающее 100 000, обозначающее количество осадков за соответствующую минуту.
Запишите в ответе два числа: сначала значение искомой величины для файла А, затем — для файла B.
Типовой пример организации данных во входном файле:
3
5
15
10
200
0
30
При таких исходных данных максимально возможное суммарное количество осадков равно 45 — это сумма осадков, выпавших на первой и пятой минутах.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
8. В текстовом файле содержится некоторое количество натуральных чисел. Определите и запишите в ответ максимальную сумму трех чисел, чтобы любые два числа находились на расстоянии не менее К друг от друга.
Первая строка файла содержит число k — расстояние между элементами, вторая строка файла содержит содержит количество элементов в файле.
9. В первых двух строках подаются два натуральных числа: сначала N — количество натуральных чисел в последовательности, затем K — минимальное расстояние, допустимое между любыми двумя элементами.
Требуется найти минимальное значение произведения тройки элементов так, что между любыми элементами тройки расстояние между двумя элементами не менее K (то есть разность их индексов по модулю больше или равна K). 27-8-A 27-8-B
10. В первой строке подаются два натуральных числа N — количество натуральных чисел в последовательности и K — минимальное расстояние, допустимое между любыми двумя элементами.
Требуется найти минимальное значение произведения тройки элементов так, что между любыми элементами тройки расстояние между двумя элементами не менее K (то есть разность их индексов по модулю больше или равна K). 27-9-A (1) 27-9-B
11. Дана дорога длиной N метров, через каждый метр, поставлены приборы высчитывающие высоту над уровнем моря. Требуется найти максимальную оценку участка дороги, то есть сумму показаний высот на концах (то есть по положениям приборов) и длины этой дороги.
В первой строке входных данных задаётся протяженность дороги N (1 ≤ N ≤ 10 000). В каждой из последующих N строк записано целое положительное число, означающее замеченную высоту.
Геодезист измеряет высоту над уровнем моря (в миллиметрах) относительно уровня начала дороги, для каждой из N её метровых отметок. Нумерация отметок начинается с единицы.
Проектировщикам необходимо выбрать участок дороги длиной не менее К метров, на котором значение суммы всех высот, выраженное в миллиметрах, максимально. Это значение называется оценкой участка дороги. Начало и конец искомого участка совпадают с метровыми отметками на дороге. Началом участка считается метровая отметка дороги с меньшим номером.
Определите две метровые отметки дороги так, чтобы расстояние между ними было не менее К метров, а оценка соответствующего участка дороги — максимально возможной. Укажите в ответе найденное числовое значение максимальной оценки, выраженное в миллиметрах.
Входные данные. 27-10-A 27-10-B
Даны два входных файла (файл А и файл В), каждый из которых в первой строке входных данных задаётся протяженность дороги N (1 ≤ N ≤ 10 000), а во второй — натуральное число К — минимально допустимое расстояние (в метрах) между двумя отметками дороги (N > К).
В каждой из следующих N строк находится одно целое число, не превышающее по модулю 10 000 000: высота относительно уровня начального участка дороги (в миллиметрах) на соответствующей метровой отметке дороги.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем — для файла В.
12. Дана последовательность целых чисел. Расстояние между элементами последовательности — это разность их порядковых номеров. Например, если два элемента стоят в последовательности рядом, расстояние между ними
равно 1, если два элемента стоят через один — расстояние равно 2 и так далее.
Необходимо выбрать из последовательности три числа так, чтобы максимальное расстояние между выбранными числами было не меньше K, а их сумма была максимально возможной.
В ответе запишите найденную сумму
Входные данные. 27-11-A 27-11-B
Первая строка входного файла содержит целое число K — параметр для определения расстояния, вторая строка содержит число N — общее количество чисел в наборе (1 < 2K < N). Каждая из следующих N строк содержит одно число, не превышающее по модулю 107.
Пример входного файла:
2
6
6
7
8
2
3
5
Из этого файла в соответствии с условиями можно выбрать числа 7, 8 и 5. Максимальное расстояние в данном случае равно 4 (между числами 7 и 5). Числа 6, 7 и 8 взять нельзя, так как максимальное расстояние в этом случае равно 2, а по условию оно должно быть не меньше 4. В ответе для этого примера надо написать число 20.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала требуемую сумму для файла A, затем — для файла B.
По каналу связи передаётся последовательность целых чисел — показания прибора, полученные с интервалом 1 мин. в течение N мин. (N — натуральное число). Прибор измеряет значение заряда частиц, полученное регистратором за минуту, предшествующую моменту регистрации, и передаёт это значение в условных единицах измерения.
Определите два таких переданных числа, чтобы между моментами их передачи прошло не менее мин., а их произведение было максимально возможным. В ответе запишите — найденное произведение.
Даны два входных файла (файл А и файл В), каждый из которых в первой строке содержит натуральное число K — минимальное количество минут, которое должно пройти между — двумя передачами показаний, а во второй — количество переданных показаний N (1 ≤ N ≤ 10 000 000, N > K). В каждой из следующих N строк находится одно целое число, по модулю не превышающее 100 000, обозначающее числовое значение заряда частиц в минуту.
Запишите в ответе два числа: сначала значение искомой величины для файла A, затем — для файла B.
14. Для участников велогонки на каждом километре кольцевой трассы с двусторонним движением установлены пункты питания. Длина кольцевой трассы равна N километров. Нулевой и N-й километры трассы находятся в одной точке. Известно количество комплектов питания в каждом из пунктов на трассе. В каждый пункт комплекты питания доставляет отдельный электрокар. Стоимость доставки питания вычисляется как произведение количества комплектов питания на расстояние от мобильного цеха их подготовки до пункта питания спортсменов на трассе. Мобильный цех подготовки комплектов расположен в одном из пунктов питания на трассе таким образом, что общая стоимость доставки из цеха во все пункты минимальна.
Определите минимальную суммарную стоимость доставки питания для спортсменов из цеха его подготовки в пункты питания на трассе.
Входные данные. 27-13-A (1) 27-13-B
Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) — количество
пунктов питания на кольцевой трассе. В каждой из следующих N строк находится число — количество комплектов питания на пункте (все числа натуральные, количество комплектов питания на каждом пункте не превышает 1000). Числа указаны в порядке расположения пунктов питания спортсменов на трассе, начиная с первого километра.
Типовой пример организации данных во входном файле:
6
8
20
5
13
7
19
При таких исходных данных, если контейнеры установлены на каждом километре автодороги, необходимо открыть центр переработки в пункте 6. В этом случае сумма транспортных затрат составит: 1 · 7 + 0 · 19 + 1 · 8 + 2 · 20 + 3 · 5 + 2 · 13.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
15. Пусть S — последовательность из N чисел пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три элемента последовательности S, где i < j < k. Определите в последовательности S три таких числа Si, Sj, Sk, что Si > Sj, Sk > Sj и значение выражения (Si − Sj) + (Sk − Sj) максимально. В ответе укажите найденное максимальное значение выражения (Si − Sj) + (Sk − Sj). Гарантируется, что в последовательности есть три числа Si, Sj, Sk, удовлетворяющие условию задачи.
Входные данные. 27-14-А 27-14-В
Дано два входных файла (файл А и файл B), каждый из которых в первой строке содержит число N (5 < N <10 000 000) — количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. В ответе укажите два числа: сначала значение искомой величины для файла А, затем — для файла B.
16. Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, — это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками A(x1, y1) и B(x2, y2) на плоскости, которое вычисляется по формуле: 
В файле A хранятся данные о звёздах двух кластеров, где H = 3, W = 3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H = 3, W = 3 для каждого кластера. Известно, что количество звёзд не превышает 10 000.
Структура хранения информации о звездах в файле Б аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px — среднее арифметическое абсцисс центров кластеров, и Py — среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px × 10 000 , затем целую часть произведения Py × 10 000 для файла А, во второй строке — аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.