Pull to refresh

Comments 30

Встречал задачу похожую на тимбилдинг, решается простым поиском компонент связности графа.
В данном случае это не поможет, потому что, например, для полного графа (одна компонента связности) любое разбиение будет удовлетворять условию задачи.
По поводу 6ой задачи. Если я правильно все понял, то участник становится разрабом/манагером в зависимости от соотношений ai / bi. Тоесть алгоритм примерно следующий:
1. делим всех участников на команды, каждую команду сортируем по решающему критерию
2. обработка сертификата
2.1 сетрификат в основной скил, просто += к суммарному
2.2 в побочный — сравнить с самым низким в противоположной команде и свапнуть, если ниже
Я бы делал с помощью 2х std::set — команды, std::unorderd_map — участники по id
то участник становится разрабом/манагером в зависимости от соотношений ai / bi

Скорее в зависимости от разности ai-bi
Я бы делал с помощью 2х std::set

В принципе хватает и двух std::priority_queue (хотя асимптотика остаётся O(nlogn))
Вот строгое доказательство, если кому интересно. Давайте для начала положим всех программистов в первую команду, при этом их эффективность будет равна сумме всех a_i, обозначим ее за S. Теперь нужно переместить (n / 2) программистов во вторую команду. При перемещении программиста из первой команды во вторую суммарная эффективность изменяется на -a_i + b_i. Нужно выбрать ровно n / 2 человек, и для всех них прибавить к S (-a_i + b_i). Логично, что среди всех n чисел (-a_i + b_i) нужно выбрать (n / 2) максимальных, чтобы итоговая сумма была максимальна. А для обработки запросов на изменение, нужно поддерживать сумму a_i, и сумму (n / 2) максимальных (-a_i + b_i). Второе поддерживается с помощью std::multiset, например.
Если я правильно понял условия, то проще. Нужно не подстроку искать, а просто факт наличия полного слова среди уже введенных. То есть, бора (aka trie) должно быть достаточно. Идем по бору и поддерживаем в переменной количество символов до последней развилки.

Тут возможны варианты:
1) Зашли на терминальную вершину, а слово еще не закончилось. Значит к счетчику символов добавляем длину слова и «дорисуем» бор.
2) Слово закончилось, а в лист мы еще не пришли — добавляем длину слова. И ставим этой вершине статус развилки. Здесь тот момент где внимательность нужна. Пример: aaa aa aaa. После второго слова на вводе третьего мы уже воспользоваться автодополнением с одного символа, а только с трех = вводу слова целиком.
3) Закончили слово ровно на листе. Только в этом случае мы могли воспользоваться автодополнением. Осталось понять сколько символов нужно было ввести — а расстояние от корня до последней развилки мы знаем.

Что такое WA? Смысл ясен из контекста, но хочется знать термин.

WA — Wrong Answer, стандартное олимпиадное сокращение.

Другие статусы проверки, например, здесь
Задача 5.
Возможно, условием выхода из цикла стоит сделать total <= 0.
Насколько понимаю, у нас нет гарантий, что количество книг в наличии на очередной день и книг прочитанных в этот день обязательно сойдется к 1:1.

Вопрос по задаче 4:
Предполагается, что в команде у каждого участника должен быть хотя бы один коллега, которого он хорошо знает, или что любая пара участников одной команды должна хорошо друг друга знать?
Я думаю стоит показывать условия задачи а объяснения и код — под спойлер
Надо вам на паскале попрограммировать научитесь не использовать безразмерные массивы для элементарны задач. Это я про первую если что. Так что можете её тоже вычеркивать из списка решенных полностью. Зачем держать массив в памяти если по условию нужен только вывод?
но ведь в этом массиве хранятся результаты операций над каждой строкой ввода. Он необходим для каждой строки вывода.

А как бы вы решили эту задачу?
Вывод сделал бы сразу, а не хранил это всё в памяти. Зачем 2 цикла там где достаточно одного? Тем более если олимпиадные задачи где потребление памяти и скорость учитывается это очень важный момент.
Я так понимаю до егэ вы тоже еще не добрались? за последнюю задачку снижают баллы за такие массивы. Я свою сотню с боем отбивал на апелляции.
Вывод сразу сделать не получится никак, так как сначала нужно считать все значения чтобы узнать что из себя представляет 100%. Вы, кажется, не совсем поняли условие задания.

До ЕГЭ я не доберусь) у нас его нет.
Да условие прочитал не правильно. 2 цикла понадобиться. Безразмерный массив, правда, всё равно глаз режет. Но тут палка о двух концах либо массив либо повторное чтение. Если бы на n не было ограничение 2 вариант лучше. Хотя в этой задачке наверное и так сойдёт.
У меня в 5 задаче на 12 тесте выкинуло, вообще я потратил много времени на первый задачу, так как думал, что в код нужно добавлять комментарии типо «Введите число: » и т.д, почему-то решил, что код проверяет человек, только спустя 2 часа понял какой я тупой. Первый раз участвовал в решениях подобных задач, и осознал, что мои знания программирования далеки даже до среднего уровня. Правильно решил только первую

Так а разве можно раскрывать содержимое этого задания ?

Ну, нигде не было написано что эти задания конфиденциальны.
4-я задача
Решение
В: Что можно сказать о 2 людях, если они не знают друг друга?
О: они находятся в разных группах.
Решение: построим граф, где вершины — люди, а рёбра проведены между людьми, не знающими друг друга. Проверим этот граф на двудольность https://en.wikipedia.org/wiki/Bipartite_graph, и выведем получившиеся доли, или -1. Сложность O(n^2+m)
Наверняка. Один мой знакомый сделал пять задач из шести — ему сказали, что это всё-таки маловато, и его прособеседуют, если места останутся. С одной задачей шансов явно нет.

Кстати, сделал все шесть: они не очень сложные. Дольше всего возился со второй: ограничения такие, что писать можно что угодно (в разумных рамках), но это надо написать. Управился суммарно за три часа.
Да, полностью согласен. Но когда ты проходишь это задание в реальном времени, и понимаешь что от этого зависит то, где ты проведешь как минимум одно лето, включается мандраж.
На чем решали?

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


Писал на C++.

Кстати, ТС, если хочешь потренироваться в решении задач подобного рода, можешь посмотреть на сайты типа codeforces.com
В пятой задаче зачем столько дублирующего кода?

static int foo(int final books, int library, int day) {
    int mustRead = 1;
    int counter = 0;
    while(true) {
      if(day<6) library += books;
      library -= mustRead;
      if (library<0) break;
      counter++;
      mustRead += 1;
      day = (day%7)+1;
    }
    return counter;
}
В 5ом задании, судя по всему, не обрабатывался случай, когда книг хватало только на первый день или не хватало вообще. Во всяком случае, у меня ошибка на 10ом тесте была именно из-за этого :)
Only those users with full accounts are able to leave comments. Log in, please.