Комментарии 30
Встречал задачу, похожую на 3-ю. Нужно использовать префиксное дерево. Возможно, даже сжатое.
Встречал задачу похожую на тимбилдинг, решается простым поиском компонент связности графа.
По поводу 6ой задачи. Если я правильно все понял, то участник становится разрабом/манагером в зависимости от соотношений ai / bi. Тоесть алгоритм примерно следующий:
1. делим всех участников на команды, каждую команду сортируем по решающему критерию
2. обработка сертификата
2.1 сетрификат в основной скил, просто += к суммарному
2.2 в побочный — сравнить с самым низким в противоположной команде и свапнуть, если ниже
Я бы делал с помощью 2х std::set — команды, std::unorderd_map — участники по id
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, например.
3 — я задача решается алгоритмом кнут моррис пратт
Если я правильно понял условия, то проще. Нужно не подстроку искать, а просто факт наличия полного слова среди уже введенных. То есть, бора (aka trie) должно быть достаточно. Идем по бору и поддерживаем в переменной количество символов до последней развилки.
Тут возможны варианты:
1) Зашли на терминальную вершину, а слово еще не закончилось. Значит к счетчику символов добавляем длину слова и «дорисуем» бор.
2) Слово закончилось, а в лист мы еще не пришли — добавляем длину слова. И ставим этой вершине статус развилки. Здесь тот момент где внимательность нужна. Пример: aaa aa aaa. После второго слова на вводе третьего мы уже воспользоваться автодополнением с одного символа, а только с трех = вводу слова целиком.
3) Закончили слово ровно на листе. Только в этом случае мы могли воспользоваться автодополнением. Осталось понять сколько символов нужно было ввести — а расстояние от корня до последней развилки мы знаем.
Тут возможны варианты:
1) Зашли на терминальную вершину, а слово еще не закончилось. Значит к счетчику символов добавляем длину слова и «дорисуем» бор.
2) Слово закончилось, а в лист мы еще не пришли — добавляем длину слова. И ставим этой вершине статус развилки. Здесь тот момент где внимательность нужна. Пример: aaa aa aaa. После второго слова на вводе третьего мы уже воспользоваться автодополнением с одного символа, а только с трех = вводу слова целиком.
3) Закончили слово ровно на листе. Только в этом случае мы могли воспользоваться автодополнением. Осталось понять сколько символов нужно было ввести — а расстояние от корня до последней развилки мы знаем.
Что такое WA? Смысл ясен из контекста, но хочется знать термин.
Задача 5.
Возможно, условием выхода из цикла стоит сделать total <= 0.
Насколько понимаю, у нас нет гарантий, что количество книг в наличии на очередной день и книг прочитанных в этот день обязательно сойдется к 1:1.
Вопрос по задаче 4:
Предполагается, что в команде у каждого участника должен быть хотя бы один коллега, которого он хорошо знает, или что любая пара участников одной команды должна хорошо друг друга знать?
Возможно, условием выхода из цикла стоит сделать total <= 0.
Насколько понимаю, у нас нет гарантий, что количество книг в наличии на очередной день и книг прочитанных в этот день обязательно сойдется к 1:1.
Вопрос по задаче 4:
Предполагается, что в команде у каждого участника должен быть хотя бы один коллега, которого он хорошо знает, или что любая пара участников одной команды должна хорошо друг друга знать?
Я думаю стоит показывать условия задачи а объяснения и код — под спойлер
Надо вам на паскале попрограммировать научитесь не использовать безразмерные массивы для элементарны задач. Это я про первую если что. Так что можете её тоже вычеркивать из списка решенных полностью. Зачем держать массив в памяти если по условию нужен только вывод?
но ведь в этом массиве хранятся результаты операций над каждой строкой ввода. Он необходим для каждой строки вывода.
А как бы вы решили эту задачу?
А как бы вы решили эту задачу?
Вывод сделал бы сразу, а не хранил это всё в памяти. Зачем 2 цикла там где достаточно одного? Тем более если олимпиадные задачи где потребление памяти и скорость учитывается это очень важный момент.
Я так понимаю до егэ вы тоже еще не добрались? за последнюю задачку снижают баллы за такие массивы. Я свою сотню с боем отбивал на апелляции.
Я так понимаю до егэ вы тоже еще не добрались? за последнюю задачку снижают баллы за такие массивы. Я свою сотню с боем отбивал на апелляции.
У меня в 5 задаче на 12 тесте выкинуло, вообще я потратил много времени на первый задачу, так как думал, что в код нужно добавлять комментарии типо «Введите число: » и т.д, почему-то решил, что код проверяет человек, только спустя 2 часа понял какой я тупой. Первый раз участвовал в решениях подобных задач, и осознал, что мои знания программирования далеки даже до среднего уровня. Правильно решил только первую
Так а разве можно раскрывать содержимое этого задания ?
4-я задача
Решение
В: Что можно сказать о 2 людях, если они не знают друг друга?
О: они находятся в разных группах.
Решение: построим граф, где вершины — люди, а рёбра проведены между людьми, не знающими друг друга. Проверим этот граф на двудольность https://en.wikipedia.org/wiki/Bipartite_graph, и выведем получившиеся доли, или -1. Сложность O(n^2+m)
О: они находятся в разных группах.
Решение: построим граф, где вершины — люди, а рёбра проведены между людьми, не знающими друг друга. Проверим этот граф на двудольность https://en.wikipedia.org/wiki/Bipartite_graph, и выведем получившиеся доли, или -1. Сложность O(n^2+m)
Вас, как я понял, не приняли на стажировку?
Да, я не прошел тестовые задания.
Наверняка. Один мой знакомый сделал пять задач из шести — ему сказали, что это всё-таки маловато, и его прособеседуют, если места останутся. С одной задачей шансов явно нет.
Кстати, сделал все шесть: они не очень сложные. Дольше всего возился со второй: ограничения такие, что писать можно что угодно (в разумных рамках), но это надо написать. Управился суммарно за три часа.
Кстати, сделал все шесть: они не очень сложные. Дольше всего возился со второй: ограничения такие, что писать можно что угодно (в разумных рамках), но это надо написать. Управился суммарно за три часа.
Кстати, ТС, если хочешь потренироваться в решении задач подобного рода, можешь посмотреть на сайты типа 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ом тесте была именно из-за этого :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как я проходил тестовое задание на летнюю стажировку в Яндекс