Файл: Задача Упаковка коробок ограничение по времени на тест 1 секунда ограничение по памяти на тест 256 мегабайт ввод.docx
Добавлен: 11.12.2023
Просмотров: 173
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Муниципальный этап всероссийской олимпиады школьников по информатике 2021 (9-11 класс)
| Входные данные | Выходные данные |
| 3 1 2 3 | 1 |
| 4 4 2 4 3 | 2 |
| 8 1 2 1 2 3 2 3 3 | 3 |
ограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный выводНа первом собрании кружка робототехники было принято решение о формировании двух групп участников. У каждой группы будет ровно по одному занятию в неделю в один из будних дней (понедельник, вторник, среда, четверг или пятница), причем дни занятий у каждой группы должны быть разными. Также было решено, что количество участников в каждой группе должно быть одинаковым.Каждый участник заполнил форму, в которой отметил дни недели, в которые ему было бы удобно посещать занятия. Перед вами стоит задача определить, возможно ли выбрать два различных будних дня в неделю, в которые будут проходить занятия у каждой из групп, а также поделить всех на две группы таким образом, чтобы каждый занимался в один из тех дней, в который ему удобно, при этом количество участников в каждой из групп должно быть одинаковым.Входные данныеКаждый тест содержит два набора данных.В первой строке каждого набора записано одно четное целое число n (2≤n≤100) — количество участников.В i-й из следующих n строк следует 5 целых чисел 0 или 1, причем j-е число равно 1, если i-му участнику удобно ходить на занятия в j-й будний день, или j-е число равно 0, если i-му участнику неудобно ходить на занятия в j-й будний день. Гарантируется, что каждый из участников хочет ходить на занятия хотя бы в один из будних дней.Выходные данныеДля каждого из двух наборов данных, если возможно разделить всех студентов на две равные группы и выбрать дни для занятий так, чтобы всем студентам было удобно, выведите «Yes» (без кавычек). В противном случае выведите «No» (без кавычек).
| Входные данные | Выходные данные |
| 4 10010 01001 00010 01010 2 00010 00010 | Yes No |
| 2 10000 01000 4 10010 10010 10010 10010 | Yes Yes |
| 4 10000 10100 11000 00001 4 10000 01000 00010 00001 | No No |
Теперь мы зафиксировали пару дней a и b, и хотим проверить, может ли она быть ответом.Всех учеников можно разделить на четыре группы: отметили ни один из дней a и b, отметили только день a, отметили только день b и отметили оба.Очевидно, что если первая группа не пустая, то дни a и b не могут быть ответом.Назовем количество студентов, которые отметили только день a, cnta, а количество студентов, которые отметили только день b, cntb.Если хотя бы одно из cnta или cntb превышает n2, то дни a и b также не могут быть ответом. Иначе всегда можно выбрать n2−cnta студентов из тех, кто отметил оба дня, и послать их в день a. Остальные студенты могут пойти в день b.t = int(input())for i in range(t):n = int(input())a = [[] for i in range(n)]for j in range(n):a[j] = list(map(int, input().split()))ans = Falsefor j in range(5):for k in range(5):if k != j:cnt1 = 0cnt2 = 0cntno = 0for z in range(n):if a[z][j] == 1:cnt1 += 1if a[z][k] == 1:cnt2 += 1if a[z][j] == 0 and a[z][k] == 0:cntno += 1if cnt1 >= n // 2 and cnt2 >= n // 2 and cntno == 0:ans = Trueif ans:print('YES')else:print('NO')Задача 3. Клуб робототехники отправляется на соревнования.ограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный выводКуратор клуба решил отправить на соревнования две команды. Всего в клубе 2 группы по N участников в каждой, и каждый имеет рейтинг от 1 до 5. Куратор хочет отправить на соревнования две равные по силам команды (сумма рейтингов участников 1 команды должна быть ровна сумме рейтингов участников второй команды). Чтобы добиться этого, есть план произвести серию обменов между группами участников. Во время обмена меняется один участник из 1 группы и один из второй.Выведите наименьшее количество обменов, чтобы добиться желаемого равенстваВходные данныеВ первой строке записано целое число n (1 ≤ n ≤ 100) — количество участников в каждой из групп.Вторая строка содержит последовательность целых чисел a1, a2, ..., an (1 ≤ ai ≤ 5), через пробел, где ai — рейтинг i-го участника 1 группыТретья строка содержит последовательность целых чисел b1, b2, ..., bn (1 ≤ bi ≤ 5), через пробел, где bi — рейтинг i-го участника 2 группы.Выходные данныеВыведите искомое наименьшее количество обменов или -1, если желаемого распределения получить невозможно.
| Входные данные | Выходные данные |
| 4 5 4 4 4 5 5 4 5 | 1 |
| 6 1 1 1 1 1 1 5 5 5 5 5 5 | 3 |
| 1 5 3 | -1 |
| 9 3 2 5 5 2 3 3 3 2 4 1 4 1 1 2 4 4 1 | 4 |
-
#include
using namespace std;
const int maxn = 16;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
vectorans(maxn, -1);
ans[0] = 0;
for (int i = 1; i < maxn; ++i) {
for (auto j: vector{4, 6, 9}) {
if (i >= j && ans[i - j] != -1) {
ans[i] = max(ans[i], ans[i - j] + 1);
}
}
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int n;
cin >> n;
if (n < maxn) {
cout << ans[n] << '\n';
} else {
int t = (n - maxn) / 4 + 1;
cout << t + ans[n - 4 * t] << '\n';
}
}
}
Входные данныеВ первой строке следует целое число n (1 ≤ n ≤ 1 00) — количество чисел Пети.В каждой из следующих строк следует непустая строка si, состоящая из строчных латинских букв от 'a' до 'j' — числа Пети после замены цифр на буквы. Длина каждой строки не превосходит шести символов.Выходные данныеОпределите минимальную сумму всех чисел Пети после восстановления. Числа после восстановления должны быть целыми положительными и не должны иметь лидирующих нулей. Гарантируется, что тесты таковы, что корректное восстановление без лидирующих нулей всегда найдётся.
| Входные данные | Выходные данные |
| 3 ab de aj | 47 |
| 5 abcdef ghij bdef accbd g | 136542 |
| 3 aa jj aa | 44 |