Задачи районно-городских командных соревнований 2004

1. Access denied

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

В первой строке входного файла содержатся два целых числа, разделенных пробелом – количество ресурсов системы

$M$ (

$0\ <\ M\ ≤\ 26$ ) и количество пользователей

$N$ (

$0\ <\ N\ ≤\ 100$ ). Во второй строке содержится

$M$ целых чисел от 0 до 1000, разделенных пробелами – минимальные уровни доступа к ресурсам, первое число – минимальный уровень доступа к ресурсу A, второе число – к ресурсу B и т. д. В третьей строке содержится

$N$ целых чисел от 0 до 1000, разделенных пробелами – уровни доступа пользователей.

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

$i$ -я строка выходного файла соответствует

$i$ -му пользователю из входного файла. Имена ресурсов перечисляются в алфавитном порядке.

Пример ввода

5 3
10 11 7 4 30
8 15 10

Пример вывода

CD
ABCD
ACD

2. Квадратный корень

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Выражение

может быть упрощено следующим образом:

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

В первой строке входного файла содержатся целое число

$N$ (

$1\ ≤\ N\ ≤\ 50$ ) – количество слагаемых в исходном выражении. Во второй строке содержится

$N$ целых чисел от 1 до 1000, разделенных пробелами – числа

$A_i$ , стоящие под знаком корня в исходном выражении.

В выходной файл вывести строку, содержащую целые числа

$B_j$ , стоящие под знаком корня в упрощенном выражении, такие что

. Числа

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

Пример ввода 1

2
12 48

Пример вывода 1

Пример ввода 2

5
1 3 5 12 20

Пример вывода 2

1 27 45

3. Потерянное место

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Когда файлы сохраняются на диске, они хранятся в кластерах, имеющих фиксированный размер. Фактическое место, занимаемое файлом на диске, всегда кратно размеру кластера. Так, если кластер имеет размер 100 байт, а файл – 185 байт, то файл занимает 200 байт на диске, и 15 байт на диске являются потерянными.

Напишите программу, выполняющую расчет потерянного места на диске для каждой папки с файлами.

В первой строке входного файла содержатся три целых числа, разделенных пробелами – количество папок на диске

$N$ (

$0\ <\ N\ ≤\ 50$ ), количество файлов на диске

$M$ (

$0\ ≤\ M\ ≤\ 1000$ ) и размер кластера

$S$ (

$0\ <\ S\ ≤\ 1000000$ ). Далее следует

$M$ строк, в каждой строке содержатся два целых числа, разделенных пробелом – номер папки

$F$ (

$0\ ≤\ F\ <\ N$ ), в которой находится файл, и размер файла

$Z$ (

$0\ ≤\ Z\ ≤\ 1000000$ ). Папки нумеруются от 0 до

$N-1$ .

В выходной файл вывести

$N$ строк. В

$i$ -й строке выводится одно целое число – сумма потерянного места при размещении файлов

$(i-1)$ -ой папки (для

$i$ от 1 до

$N$ ).

Пример ввода

Пример вывода

48
14
0

Примечание к примеру: так как в папке с номером 2 файлов нет, то и потери равны 0.

4. Цифры-делители

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

В первой строке входного файла содержатся число

$N$ (

$0\ <\ N\ <\ 10^9$ ).

В выходной файл вывести количество цифр-делителей для числа

$N$ .

Пример ввода

Пример вывода

Примечание к примеру: 661232 делится на 1 и на 2 (таких цифр две) и не делится на 3 и 6.

5. Игра

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

В первой строке входного файла содержится целое число – количество наборов исходных данных

$K$ (

$1\ ≤\ K\ ≤\ 10$ ). Далее следует

$K$ блоков из трех строк, каждый блок описывает одну игровую ситуацию. В первой строке блока содержится целое число – количество юнитов

$N$ (

$0\ <\ N\ ≤\ 50$ ) у каждого из игроков. Во второй строке содержится

$N$ целых чисел от 1 до 1000, разделенных пробелами – сила юнитов игрока-человека. В третьей строке содержится

$N$ целых чисел от 1 до 1000, разделенных пробелами – сила юнитов компьютера.

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

Пример ввода

2
5
5 15 100 1 5
15 5 100 2 5
10
2 3 4 5 6 7 8 9 10 11
10 9 8 7 6 5 4 3 2 1

Пример вывода

120
65

Примечание: в первой игровой ситуации человек ставит юнит с силой 100 напротив юнита компьютера с силой 15, 15 напротив 5, 5 напротив 2, 5 напротив 5 и 1 напротив 100, теряет два юнита с суммой 6, и у него останется три юнита с суммой 120; во второй игровой ситуации человек не теряет ни одного юнита.

6. Плитки

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Напишите программу, подсчитывающую число вариантов замощения L-образной плиткой, прямоугольников заданного размера. Например, для прямоугольника 3x4 существует 4 способа замощения:

В первой строке входного файла содержатся два целых числа, разделенных пробелом – длина прямоугольника

$L$ (

$1\ ≤\ L\ ≤\ 100$ ) и ширина прямоугольника

$W$ (

$1\ ≤\ W\ ≤\ 10$ ).

В выходной файл вывести одно целое число – число вариантов замощения L-образной плиткой, прямоугольника размера

$L$ x

$W$ . Если прямоугольник замостить нельзя, то вывести 0.

Пример ввода

3 4

Пример вывода

7. Гонки на выживание

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Автомобили выстроились на стартовой прямой, ревя моторами. 3, 2, 1, старт! Машины устремились прямо вперед с одинаковой скоростью, но в разных направлениях. Интересно, что это сыпется сзади автомобилей? Какие-то колючки! Вот один из автомобилей, напоровшись на такую колючку, остановился с проколотыми шинами, а его водитель грозит кулаком более удачливому сопернику. Необходимо выяснить номера тех машин, которые уцелеют в такой гонке.

Все машины движутся с одинаковой скоростью только по прямой линии, стартуя с различных точек стартовой прямой. Если траектории автомобилей пересекаются, то та машина, которая приходит к точке пересечения раньше, продолжает движение, другая выбывает из соревнования. Если две машины приходят к точке пересечения одновременно, то движение продолжает та машина, которая во входном файле идет раньше (номер которой меньше). На рисунке показано, что машины, начинающие движение в точках с координатой 0, 10 и 50, уцелеют, а машины, стартующие в точках 20, 30, 40, остановятся.

В первой строке входного файла содержится целое число – количество наборов исходных данных

$K$ (

$1\ ≤\ K\ ≤\ 10$ ). Далее следует

$K$ блоков, каждый блок описывает одну гонку. В первой строке блока содержится целое число – количество машин

$N$ (

$0\ <\ N\ ≤\ 50$ ), участвующих в гонке. Далее следует

$N$ строк, в каждой строке содержатся два целых числа, разделенных пробелом – координата машины на стартовой прямой

$X_i$ (

$0\ ≤\ X_i\ ≤\ 1\ 000\ 000$ ) и направление движения машины

$A_i$ (

$1\ ≤\ A_i\ ≤\ 179$ , в градусах, см. рис.).

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

$N-1$ .

Пример ввода

Пример вывода

8. Экономия топлива

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

В первой строке входного файла содержится целое число – количество наборов исходных данных

$K$ (

$1\ ≤\ K\ ≤\ 10$ ). Далее следует

$K$ блоков, каждый блок описывает один набор. В первой строке блока содержатся два целых числа, разделенных пробелом – количество возможных скоростных режимов вашего автомобиля

$N$ (

$0\ <\ N\ ≤\ 50$ ) и запас топлива

$F$ в миллилитрах (

$100\ ≤\ F\ ≤\ 50000$ ). Далее следует

$N$ строк, в каждой строке содержатся два целых числа, разделенных пробелом – скорость вашего автомобиля

$S_i$ в километрах в час (

$5\ ≤\ S_i\ ≤\ 250$ ) и расход топлива в миллилитрах за час

$C_i$ (

$1000\ ≤\ C_i\ ≤\ 20000$ ) при скорости

$S_i$ .

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

Пример ввода

Пример вывода

100.000
1100.000

9. Олимпиада

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Напишите программу, генерирующую по результатам отдельных соревнований итоговый рейтинг всех стран.

В первой строке входного файла содержатся целое число – количество соревнований

$N$ (

$0\ <\ N\ ≤\ 50$ ). Далее следует

$N$ строк, каждая строка имеет вид:

$"GGG"$

$"SSS"$

$"BBB"$

где

$"GGG"$ ,

$"SSS"$ ,

$"BBB"$ – это трехбуквенные коды стран (3 прописных латинских буквы), получивших соответственно золотую, серебряную и бронзовую медали. Например, строка "RUS KOR USA" означает, что в данном виде спорта страна с кодом RUS – получила золотую медаль, KOR – серебряную и USA – бронзовую. В результатах соревнований появляется не более 50 различных кодов стран.

В выходной файл вывести итоговый рейтинг всех стран в формате:

$"CCC"$

$G$

$S$

$B$

где

$"CCC"$ – это трехбуквенный код страны,

$G$ – число золотых медалей, завоеванных этой страной,

$S$ – число серебряных,

$B$ – число бронзовых. Страны нужно выводить в порядке убывания числа золотых медалей, при равенстве числа золотых – в порядке убывания числа серебряных медалей, при равенстве числа золотых и серебряных – в порядке убывания числа бронзовых медалей, а если и их количество одинаково, то страны должны быть выведены в алфавитном порядке по их трехбуквенному коду.

Пример ввода

4
ITA JPN AUS
KOR TPE UKR
KOR KOR GBR
KOR CHN TPE

Пример вывода

KOR 3 1 0
ITA 1 0 0
TPE 0 1 1
CHN 0 1 0
JPN 0 1 0
AUS 0 0 1
GBR 0 0 1
UKR 0 0 1

21/11/2004	Районно-городские командные соревнования (2)
03/10/2013	Занятие 5 для начинающих (B)

21/11/2004	Районно-городские командные соревнования (3)
18/11/2023	Марафон 80 задач, 5 этап (F)

21/11/2004	Районно-городские командные соревнования (4)
14/07/2015	Практика 1 и 2 курса (1) (D)

21/11/2004	Районно-городские командные соревнования (5)
16/12/2015	Занятие по теме "Жадные алгоритмы" (E)
04/07/2018	Лето 2018 - 5 (упрощенное) (D)
08/07/2020	Лето 2020 - 4 (упрощенное) (D)
07/07/2023	Лето 2023-6 сложные (командное) (G)
07/07/2023	Лето 2023-6 простые (командное) (H)
05/07/2024	Лето 2024-6 простые (командное) (H)
05/07/2024	Лето 2024-6 сложные (командное) (G)

21/11/2004	Районно-городские командные соревнования (6)
03/10/2013	Занятие 5 для продолжающих (A)

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Задачи районно-городских командных соревнований 2004

1. Access denied

2. Квадратный корень

3. Потерянное место

4. Цифры-делители

5. Игра

6. Плитки

7. Гонки на выживание

8. Экономия топлива

9. Олимпиада

21/11/2004	Районно-городские командные соревнования (8)
25/06/2012	1 курс, дорешивание (6C1)
02/07/2012	1 курс, день 6, группа 1 (C1)