Марафон: задание 27

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 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 не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Ответ:

Последовательность натуральных чисел характеризуется числом Х  — наибольшим числом, кратным 14 и являющимся произведением двух элементов последовательности с различными номерами. Гарантируется, что хотя бы одно такое произведение в последовательности есть.

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

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

Пример организации исходных данных во входном файле:

5

40

1000

7

28

55

Пример выходных данных для приведённого выше примера входных данных:

28000 В ответе укажите два числа: сначала значение искомого произведения для файла А, затем для файла B.

Ответ:

На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 60 000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.

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

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 60 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.

Пример организации исходных данных во входном файле:

4

2

6

13

39

Пример выходных данных для приведённого выше примера входных данных:

4

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

Ответ:

Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2 · 6, 2 · 13, 2 · 39, 6 · 13, 6 · 39, 13 · 39 (результаты: 12, 26, 78, 78, 234, 507). Из них на 26 делятся 4 произведения (2 · 13  =  26; 2 · 39  =  78; 6 · 13  =  78; 6 · 39  =  234).

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.

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

В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.

Пример организации исходных данных во входном файле:

5

34

12

51

52

51

Пример выходных данных для приведённого выше примера входных данных:

51 51 В ответе укажите четыре числа: сначала значение искомой пары для файла А (два числа через пробел), затем для файла B (два числа через пробел). Числа пар впишите в порядке убывания.

Ответ:

Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (34, 12), (34, 52), (51, 51). Наибольшая сумма получается в паре (51, 51). Эта пара допустима, так как число 51 встречается в исходной последовательности дважды.

На вход программы поступает последовательность из N натуральных чисел. Рассматриваются все пары различных элементов последовательности, у которых различные остатки от деления на d  =  160 и хотя бы одно из чисел делится на p  =  7. Среди таких пар необходимо найти и вывести пару с максимальной суммой элементов.

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

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. В качестве результата программа должна напечатать элементы искомой пары. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них. Если таких пар нет, то вывести два нуля.

Пример организации исходных данных во входном файле:

4

168

7

320

328

Пример выходных данных для приведённого выше примера входных данных:

168 320 В ответе укажите четыре числа: сначала значение искомой пары для файла А (два числа через пробел по возрастанию), затем для файла B (два числа через пробел по возрастанию).

Ответ:

Дана последовательность N целых положительных чисел. Необходимо определить количество пар элементов этой последовательности, сумма которых делится на m  =  80 и при этом хотя бы один элемент из пары больше b  =  50.

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

В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.

Пример организации исходных данных во входном файле:

6

40

40

120

30

50

110

Пример выходных данных для приведённого выше примера входных данных:

3 В ответе укажите два числа: сначала количество пар для файла А, затем для файла B.

Ответ:

Пояснение. Из данных шести чисел можно составить три пары, удовлетворяющие условию: (40, 120), (40, 120), (50, 110). У пар (40, 40) и (30, 50) сумма делится на 80, но оба элемента в этих парах не превышают 50.

На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности a_i и a_j, такие, что i < j и a_i > a_j (первый элемент пары больше второго; i и j  — порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m  =  120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.

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

В первой строке входных данных задаётся количество чисел n (2 ≤ n ≤ 12 000).

В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.

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

Пример организации исходных данных во входном файле:

6

60

140

61

100

300

59

Пример выходных данных для приведённого выше примера входных данных:

140 100 В ответе укажите четыре числа: сначала искомую пару чисел для файла А (два числа через пробел), затем для файла B (два числа через пробел).

Ответ:

Пояснение. Из шести заданных чисел можно составить три пары, сумма элементов которых делится на m  =  120: 60 + 300, 140 + 100 и 61 + 59. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.

Набор данных состоит из пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на 3 и при этом была максимально возможной.

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

Первая строка входного файла содержит число N  — общее количество пар в наборе. Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

Пример организации исходных данных во входном файле:

6

1 3

5 10

6 9

5 4

3 3

1 1

Для указанных данных искомая сумма равна 30.

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

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

Ответ:

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

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

Первая строка входного файла содержит число N  — общее количество троек в наборе. Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

Пример входного файла:

3

1 2 3

5 12 4

6 9 7

Для указанных данных искомая сумма равна 24, она соответствует такому распределению чисел по группам: (1, 5, 6), (2, 4, 7), (3, 12, 9).

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

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

Ответ:

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

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

Первая строка входного файла содержит число N  — общее количество пар в наборе. Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

Пример входного файла:

5

15 8

5 11

6 3

7 2

9 14

Для указанных данных надо выбрать числа 15, 11, 6, 7 и 14. Большинство из них нечётны, сумма выбранных чисел равна 53 и тоже нечётна. В ответе надо записать число 53.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

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

Ответ:

В текстовом файле записан набор натуральных чисел, не превышающих 10⁸. Гарантируется, что все числа различны. Из набора нужно выбрать три числа, сумма которых делится на 3. Какую наибольшую сумму можно при этом получить?

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

Первая строка входного файла содержит целое число N  — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число.

Пример входного файла:

4

5

8

14

11 В данном случае есть четыре подходящие тройки: 5, 8, 11 (сумма 24); 5, 8 14 (сумма 27); 5, 14 11 (сумма 30) и 8, 14, 11 (сумма 33). В ответе надо записать число 33.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

Ответ:

В текстовом файле записан набор пар натуральных чисел, не превышающих 10 000. Необходимо выбрать из набора некоторые пары так, чтобы первое число в каждой выбранной паре было нечётным, сумма бо́льших чисел во всех выбранных парах была нечётной, а сумма меньших  — чётной. Какую наибольшую сумму чисел во всех выбранных парах можно при этом получить?

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

Первая строка входного файла содержит целое число N  — общее количество пар в наборе. Каждая из следующих N строк содержит пару чисел.

Пример входного файла:

4

5 2

8 15

7 14

11 9 В данном случае есть три подходящие пары: (5, 2), (7, 14) и (11, 9). Пара (8, 15) не подходит, так как в ней первое число чётное. Чтобы удовлетворить требования, надо взять пары (7, 14) и (11, 9). Сумма бо́льших чисел в этом случае равна 25, сумма меньших равна 16. Общая сумма равна 41. В ответе надо указать число 41.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

Ответ:

Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на k  =  109 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число  — максимально возможную сумму, соответствующую условиям задачи.

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

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 1 000 000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 20 000.

Пример организации исходных данных во входном файле:

6

1 3 7

5 12 6

6 9 11

5 4 8

3 5 4

1 1 1

Для указанных входных данных, в случае, если k  =  5, значением искомой суммы является число 44.

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

Ответ:

На вход программы поступает последовательность из целых положительных чисел. Необходимо выбрать такую подпоследовательность подряд идущих чисел, чтобы их сумма была максимальной и делилась на 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.

Ответ:

Дана последовательность из 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.

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

Дана последовательность натуральных чисел. Необходимо найти максимально возможную сумму её непрерывной подпоследовательности, в которой количество чётных элементов кратно k  =  10.

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

Первая строка входного файла содержит целое число N  — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма всех чисел не превышает 2 · 10⁹.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

Ответ:

На каждом 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 не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Ответ:

Дана последовательность натуральных чисел. Необходимо определить количество её непрерывных подпоследовательностей, сумма элементов которых кратна 999.

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

Первая строка входного файла содержит целое число N  — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма всех чисел и число в ответе не превышают 2 · 10⁹ по абсолютной величине.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

Ответ:

У медицинской компании есть 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 не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Дана последовательность натуральных чисел. Назовём парой любые два числа из последовательности. Необходимо определить количество пар, в которых сумма чисел в паре делится без остатка на 3, а их произведение  — на 1024.

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

Первая строка входного файла содержит целое число N  — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 40 000. Гарантируется, что число в ответе не превышает 2 · 10¹⁰.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала искомое значение для файла A, затем  — для файла B.

Ответ: