(Разбор)Муниципальный этап всероссийской олимпиады школьников по. Задача Упаковка коробок ограничение по времени на тест 1 секунда ограничение по памяти на тест 256 мегабайт ввод
 Скачать 37.9 Kb.
|
|
Муниципальный этап всероссийской олимпиады школьников по информатике 2021 (9-11 класс) Задача 1. Упаковка коробок. ограничение по времени на тест 1 секунда ограничение по памяти на тест 256 мегабайт ввод стандартный ввод вывод стандартный вывод У Васи есть n пустых коробок. Для каждого i (1 ≤ i ≤ n) i-я коробка — это куб со стороной длины ai. Вася может положить коробку i в другую коробку j, если соблюдаются следующие условия: i-я коробка не лежит в другой коробке; j-я коробка не содержит других коробок; коробка i меньше коробки j (ai < aj). Вася может сколько угодно раз класть коробки друг в друга. Он хочет минимизировать количество видимых коробок. Коробка называется видимой, если она не лежит в какой-либо коробке. Помогите определить минимальное возможное количество видимых коробок. Входные данные В первой строке записано одно целое число n (1 ≤ n ≤ 5000) — количество коробок у Васи. Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 106), где ai — длина стороны i-й коробки. Выходные данные Выведите минимальное количество видимых коробок.
Ответом на данную задачу будет число коробок с максимально часто встречающимся размером. Например так: using namespace std; int main() { int n, el, k = 0, m = 0; vector <int> v; cin >> n; for (int i = 0; i < n; ++i) { cin >> el; v.push_back(el); } for (auto el : v) { k = 0; for (auto el2 : v) { if (el == el2) { ++k; } } if (k > m) { m = k; } } cout << m; } Задача 2. Занятия по подгруппам. ограничение по времени на тест 1 секунда ограничение по памяти на тест 256 мегабайт ввод стандартный ввод вывод стандартный вывод На первом собрании кружка робототехники было принято решение о формировании двух групп участников. У каждой группы будет ровно по одному занятию в неделю в один из будних дней (понедельник, вторник, среда, четверг или пятница), причем дни занятий у каждой группы должны быть разными. Также было решено, что количество участников в каждой группе должно быть одинаковым. Каждый участник заполнил форму, в которой отметил дни недели, в которые ему было бы удобно посещать занятия. Перед вами стоит задача определить, возможно ли выбрать два различных будних дня в неделю, в которые будут проходить занятия у каждой из групп, а также поделить всех на две группы таким образом, чтобы каждый занимался в один из тех дней, в который ему удобно, при этом количество участников в каждой из групп должно быть одинаковым. Входные данные Каждый тест содержит два набора данных. В первой строке каждого набора записано одно четное целое число n (2≤n≤100) — количество участников. В i-й из следующих n строк следует 5 целых чисел 0 или 1, причем j-е число равно 1, если i-му участнику удобно ходить на занятия в j-й будний день, или j-е число равно 0, если i-му участнику неудобно ходить на занятия в j-й будний день. Гарантируется, что каждый из участников хочет ходить на занятия хотя бы в один из будних дней. Выходные данные Для каждого из двух наборов данных, если возможно разделить всех студентов на две равные группы и выбрать дни для занятий так, чтобы всем студентам было удобно, выведите «Yes» (без кавычек). В противном случае выведите «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 = False for j in range(5): for k in range(5): if k != j: cnt1 = 0 cnt2 = 0 cntno = 0 for z in range(n): if a[z][j] == 1: cnt1 += 1 if a[z][k] == 1: cnt2 += 1 if a[z][j] == 0 and a[z][k] == 0: cntno += 1 if cnt1 >= n // 2 and cnt2 >= n // 2 and cntno == 0: ans = True if 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, если желаемого распределения получить невозможно.
Для решения данной задачи воспользуемся массивом cnt[]. Проитерируемся по первому массиву с рейтингами, и если очередной рейтинг равен x, увеличим cnt[x] на единицу. Аналогичным образом, проитерируемся по второму массиву, и если очередной рейтинг равен y, уменьшим cnt[y] на единицу. Если после этого хотя бы один из элементов массива cnt нечетный, ответом будет - 1 (это означает, что учеников с таким рейтингом нечетное количество и их никак не удастся разделить пополам). Если же все элементы массива четны, то ответом будет сумма абсолютных величин массива cnt, делённых пополам, причем итоговую сумму тоже нужно разделить пополам, так как каждый обмен при таком нахождении ответа будет посчитан дважды. #include using namespace std; const int maxn = 16; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); vector ans[0] = 0; for (int i = 1; i < maxn; ++i) { for (auto j: vector 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'; } } } Задача 4. Минимальная сумма. ограничение по времени на тест 1 секунда ограничение по памяти на тест 256 мегабайт ввод стандартный ввод вывод стандартный вывод У Пети есть n целых положительных чисел a1, a2, ..., an. Его друг Вася решил пошутить и решил заменить все цифры в числах на буквы. Причём использовал он строчные буквы латинского алфавита от 'a' до 'j' и заменил все цифры 0 на одну букву, все все цифры 1 на другую букву, все цифры 2 на третью букву и так далее. Для любых двух разных цифр Вася использовал разные буквы от 'a' до 'j'. Перед вами стоит задача восстановить числа Пети. Восстановленные числа должны быть целыми положительными без лидирующих нулей. Так как ответов может быть много, определите минимальную сумму всех чисел Пети после восстановления. Гарантируется, что все числа Пети изначально не имели лидирующих нулей. Входные данные В первой строке следует целое число n (1 ≤ n ≤ 1 00) — количество чисел Пети. В каждой из следующих строк следует непустая строка si, состоящая из строчных латинских букв от 'a' до 'j' — числа Пети после замены цифр на буквы. Длина каждой строки не превосходит шести символов. Выходные данные Определите минимальную сумму всех чисел Пети после восстановления. Числа после восстановления должны быть целыми положительными и не должны иметь лидирующих нулей. Гарантируется, что тесты таковы, что корректное восстановление без лидирующих нулей всегда найдётся.
Примечание В первом примере нужно заменить букву 'a' на цифру 1, букву 'b' на цифру 0, букву 'd' на цифру 2, букву 'e' на цифру 3, а букву 'j' на цифру 4. Тогда получатся числа [10, 23, 14]. Сумма этих чисел равна 47, что является минимально возможной суммой чисел после корректного восстановления. Во втором примере числа после восстановления могут выглядеть, например, следующим образом: [120468, 3579, 2468, 10024, 3]. В третьем примере числа после восстановления могут выглядеть, например, следующим образом: [11, 22, 11]. Чтобы итоговая сумма получилась минимальной необходимо и достаточно чтобы буквы встречающиеся с большей частотой( с учетом позиции) имели меньшее числовое значение. Единственное исключение 0 – такое значение не может иметь буква встречающаяся хоть раз на первой позиции. function pow(i:int64):int64; begin if i=1 then pow:=1 else pow:=pow(i-1)*10; end; var j,i,k :int64; s:string; a:array [1..10,1..2]of int64; imin,max,sum :int64; begin readln(k); for j:=1 to k do begin readln(s); case s[1] of 'a': A[1,2]:=7; 'b': A[2,2]:=7; 'c': A[3,2]:=7; 'd': A[4,2]:=7; 'e': A[5,2]:=7; 'f': A[6,2]:=7; 'g': A[7,2]:=7; 'h': A[8,2]:=7; 'i': A[9,2]:=7; 'j': A[10,2]:=7; end; for i:=1 to length(s) do case s[i] of 'a': A[1,1]+=pow(length(s)-i+1); 'b': A[2,1]+=pow(length(s)-i+1); 'c': A[3,1]+=pow(length(s)-i+1); 'd': A[4,1]+=pow(length(s)-i+1); 'e': A[5,1]+=pow(length(s)-i+1); 'f': A[6,1]+=pow(length(s)-i+1); 'g': A[7,1]+=pow(length(s)-i+1); 'h': A[8,1]+=pow(length(s)-i+1); 'i': A[9,1]+=pow(length(s)-i+1); 'j': A[10,1]+=pow(length(s)-i+1); end; end; imin:=10;max:=-1; for i:=1 to 10 do if (a[i,1]>max) and (a[i,2]<>7) then begin imin:=i; max:=a[i,1]; end; swap(a[1,1],a[imin,1]); swap(a[1,2],a[imin,2]); for j:=2 to 9 do for i:=2 to 9 do if a[i,1]>a[i+1,1] then begin swap(a[i,1],a[i+1,1]); swap(a[i,2],a[i+1,2]); end; sum:=0; i:=10;k:=1; for i:=10 downto 2 do begin sum:=sum+a[i,1]*k; k:=k+1; end; write(sum); END. |