Для контекста посмотрите этот пост.
Всем привет!
Хочу поблагодарить всех за участие в этом шуточном соревновании — как авторов, так и участников. Спасибо каждому, кто даже хотя бы зарегистрировался на соревнование, кто не поленился и отправил хотя бы одну посылку — мне очень приятно и это большая честь для меня, что кого-то интересуют мои задачи. Хочу также извиниться за то, что соревнование было не совсем честным. В конце концов, контест первоапрельский — вы знали на что вы шли ;)
Перейдём к награждению! В нашей "олимпиаде", как и в большинстве, будут победители и призёры. Статус призёра получают все, кто решил хотя бы 7 задач, а статус "победитель" получают те, кто решил 10 задач, или же решил 9 задач но получил не больше чем 1029 единиц штрафа.
Таким образом, победителями соревнования становятся:
Призёры:
Все призёры получат памятные дипломы, а победители дополнительно получат кое-что ещё. Чемпиона тоже ожидает особый приз)
А теперь, наконец, перейдём к разбору задач.
[problem:376055A]
Автор задачи: Nartov_dima
Интересный фактЯ не придумал аналог выражения "А и Б сидели на трубе" на английском, поэтому в английской версии идут следующие буквы алфавита.
Подсказка 1Какие самые банальные операции можно произвести с двумя числами?
Подсказка 2Что ещё может обозначаться двумя полосками $$$|S|$$$?
РешениеВыражение ($$$|a|, |b| \leq 100$$$) означает, что длина чисел $$$a$$$ и $$$b$$$ не превышает $$$100$$$, а дальше не трудно догадаться что два числа необходимо просто перемножить.
Код на Pythona = int(input())
b = int(input())
print(a * b)
[problem:376055B]
Автор задачи: gordeve
Интересный фактЭта задача основана на реальных событиях! Почти.
РешениеВ этой задаче не было подводных камней как таковых. Необходимо просто реализовать что написано в условии и понять, что если элементы ещё не вводились, то минимум и максимум мы найти не сможем.
Код на C++#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int mi = 1000001, ma = -1000001;
while (n--){
string s;
cin >> s;
//cout << s.substr(0, 6) << "]" << '\n';
if (s.substr(0, 6) =="Insert"){
//cout << s.substr(7, s.length() - 8) << '\n';
mi = min(mi, stoi(s.substr(7, s.length() - 8)));
ma = max(ma, stoi(s.substr(7, s.length() - 8)));
cout << "ok\n";
}
else if (s == "GetMin"){
if (mi == 1000001)
cout << "error\n";
else
cout << mi << '\n';
}
else {
if (ma == -1000001)
cout << "error\n";
else
cout << ma << '\n';
}
}
return 0;
}
[problem:376055C]
Автор задачи: gordeve
Интересный фактЭта задача задумывалась как интерактивная, но была упрощена и превращена в не интерактивную из-за моих слабых (на тот момент) умений в Polygon.
Подсказка 1Как избежать уменьшения рейтинга?
РешениеОчевидно, что рейтинг меняется только если $$$s_i = Fake$$$, тогда если $$$a_i < a_{i + 1}$$$, то рейтинг увеличивается, а иначе уменьшается. Собственно говоря, а почему бы просто не сделать так, чтобы каждый элемент был больше предыдущего? Делаем $$$a_i = i$$$ и получаем плюсик на задаче.
Код на C++#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cout << i << ' ';
return 0;
}
[problem:376055D]
Автор задачи: shevnin_d
Интересный фактИгра "Говорящий Бен" очень быстро теряет популярность и уже совсем скоро (если не уже) эта задача станет неактуальной!
Подсказка 1Все фразы Бена случайны и не зависят от вопроса.
РешениеКак жить, когда интерактор не может гарантированно дать нам честный ответ на наш вопрос, а нам нужно найти число? В такой ситуации остаётся переиграть врунишку в его игре и поймать его на слове. В условии не говорится, какое ИМЕННО число мы должны найти, поэтому мы можем спрашивать "это число равно $$$1$$$?" и как только Бен ответит "Да", то остановиться, как и требуется в условии.
Код на C++#include <iostream>
using namespace std;
int main()
{
while (true){
cout << "= 1" << endl;
string s;
cin >> s;
if (s == "Yees.")
return 0;
}
return 0;
}
[problem:376055E]
Автор задачи: unknowableshade
Интересный фактЯ забыл, что существуют другие операционные системы кроме Windows.
РешениеПрохождение игры будет выложено только при особой необходимости.
Ответы:
- X50N4O
- LSV0J0
- X5BGKE
- XOPVQY
- NX1X3P
- T6LKS0
- QV528F
- FC6O1I
[problem:376055F]
Автор задачи: gordeve
Интересный фактЭта задача была самой сложной на первоапрельском контесте 2020 года, а на этом — 3-я по сложности. Подумать только.
РешениеЕсть несколько способов определить что больше, одним из этих способов является самый обыкновенный цикл с отсечением. Гарантируется, что он будет работать недолго, т.к. произведение растёт гораздо быстрее чем сумма. Ну и если внимательно посмотреть на формат выходных данных, то можно заметить, что всё, кроме "equal" надо выводить с кавычками.
Код на C++#include <iostream>
using namespace std;
int main()
{
int l, r;
cin >> l >> r;
if (l == 0){
if (r == 0)
cout << "equal";
else
cout << "\'sum\'";
}
else {
int sum = l;
int prod = l;
for (int i = l + 1; i <= r; i++){
sum += i;
prod *= i;
if (prod > sum)
break;
}
if (sum < prod)
cout << "\'product\'";
else if (sum > prod)
cout << "\'sum\'";
else
cout << "equal";
}
return 0;
}
[problem:376055G]
Автор задачи: gordeve
Подсказка 1Как-то в тексте много опечаток.
Подсказка 2Как-то странно написано про модуль.
РешениеДля программиста одно из самых важных умений – читать между строк. Действительно, если внимательно взглянуть на условие, то можно заметить что некоторые буквы либо повторяются, либо же наоборот отсутствуют. Если написать их всех вместе, то получится «ПАРЫРАВНЫХ». Теперь необходимо аккуратно реализовать поиск всех пар равных строк, чтобы не попасться на ограничения по времени, а так же не забыть про cin.tie(0). Завершающей ловушкой этой задачи было ограничение на то, что итоговое число не превосходит 998244353, что значит, что если итоговый результат больше этого числа, то нужно просто сократить его до этого числа.
Код на C++#include <iostream>
#include <algorithm>
using namespace std;
string s[1000100];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> s[i];
sort(s, s + n);
long long x = 1, ans = 0;
for (int i = 1; i < n; i++){
if (s[i] == s[i - 1])
x++;
else{
ans += x * (x - 1) / 2;
x = 1;
if (ans >= 998244353){
cout << 998244353 << '\n';
return 0;
}
}
}
cout << min(ans + x * (x - 1) / 2, (long long)998244353) << '\n';
return 0;
}
[problem:376055H]
Автор задачи: khadzakos
Интересный факт30% россиян живут в неполных семьях.
Подсказка 1Сколько раз может оживать отчим?
Подсказка 2Посмотрите внимательно на ограничения.
РешениеЕсли так разобраться, то 3 операции можно представить так — увеличить значение в какой-то вершине на единицу, уменьшить это же значение или же узнать сумму значений от корня дерева до вершины. Заметим, что $$$q \leq 10^4$$$, что позволяет нам обрабатывать все запросы за квадрат. А именно — для начала посчитаем DFS-ом глубину каждой вершины, а также время входа $$$tin_v$$$ и время выхода $$$tout_v$$$. Когда мы рассматриваем запрос 3-его вида, то нам достаточно заново обработать все запросы до него. Если менялось значение вершины, которая наш предок, то изменится и значение в рассматриваемой вершине. Посмотреть, является ли одна вершина предком другой легко — вершина $$$A$$$ явл. предком вершины $$$B$$$ если $$$tin_A \leq tin_B \ and \ tout_B \leq tout_A$$$ (это свойство эйлерова обхода). Таким образом, итоговая асимптотика — $$$O(n + q^2)$$$.
Код на C++#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
vector <int> g[100100];
int tin[100100], tout[100100];
int d[100100];
int tmr = 0;
vector <pair <int, int> > queries;
void dfs(int v, int p = -1, int dep = 0)
{
tin[v] = ++tmr;
d[v] = dep;
for (auto to : g[v])
if (to != p)
dfs(to, v, dep + 1);
tout[v] = ++tmr;
}
bool isAncestor(int a, int b)
{
return tin[a] < tin[b] && tout[b] < tout[a];
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
int n;
cin >> n;
for (int i = 2; i <= n; i++){
int x;
cin >> x;
g[x].push_back(i);
g[i].push_back(x);
}
dfs(1);
int q;
cin >> q;
while (q--){
int t, x;
cin >> t >> x;
if (t == 3){
int ans = d[x];
for (auto it : queries){
if (isAncestor(it.second, x)){
//cout << x << ' ' << it.second << ' ' << isAncestor(x, it.second) << '\n';
if (it.first == 1)
ans--;
else if (it.first == 2)
ans++;
//cout << "--" << it.first << ' ' << ans << '\n';
}
}
cout << ans << '\n';
}
queries.push_back({t, x});
}
return 0;
}
[problem:376055I]
Автор задачи: unknowableshade
Интересный фактЭто предпоследняя задача и она на геометрию, а значит она самая сложная!
Подсказка 1Чем больше цифр, тем больше число.
РешениеДля решения нам необходимо знать несколько утверждений:
- Чем больше цифр в числе, тем больше число
- Единица требует меньше всего звёзд, на втором месте ноль
- Все звёзды можно соединить единицами и нулями так, чтобы они не пересекались.
Получается, что достаточно вывести $$$n/2$$$ единиц, а если $$$n$$$ – нечётное, вычесть из получившегося числа единицу, чтобы получилось число вида $$$11…110$$$.
Код на C++#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++){
int x, y;
cin >> x >> y;
}
for (int i = 0; i < n / 2; i++)
if (n % 2 && i == n / 2 - 1)
cout << 0;
else
cout << 1;
return 0;
}
[problem:376055J]
Автор задачи: Фольклор
Интересный фактВторое по популярности число после правильного ответа это, как ни странно, $$$228$$$.
РешениеИ так, эту задачу можно по праву называть самым настоящим социальным экспериментом. Некоторые люди писали $$$1$$$, некоторые писали $$$1000000000$$$. Две невезучих души так и не встретили друг друга — один написал $$$42069$$$, а другой $$$69420$$$. Но ответ, который выбрало подавляющее большинство (около 25 человек), это, конечно же, $$$0$$$. В завершении разбора хочу сказать, что каждый год была задача, где ответом было число $$$0$$$ и так получилось, что в этом году, благодаря усилиям сообщества, такая задача вновь появилась :)
"День Дураков" официально окончен. Спасибо за внимание! Буду рад услышать критику в комментариях!
Мне понравился контест, но тесты, конечно, слабоватые в некоторых задачах были:
Я так и не понял решение $$$C$$$. Написал что-то случайное. Подумал, что рейтинг поднимается для True композиций и надо максимальные числа вывести именно для них, а для Fake всё равно что. Почему именно с Fake поднимается рейтинг?
Решение $$$D$$$ у меня, оказывается, неправильное. :-)
Попытавшись сдать эту задачу 36 раз, я в конце концов подумал, что ключ во фразе "и вот у такого человека вам необходимо за $$$40$$$ вопросов узнать число $$$n$$$, лежащее в пределе от $$$1$$$ до $$$10^9$$$". То есть, я ровно 40 раз спросил про "= 6" (которое в тестовом примере было).
Задача $$$H$$$, конечно, у меня самая ошибочная — зашла на 45-й раз. Сначала перепугался, что $$$nq \approx 10^9$$$ и решил написать решение с HLD за $$$O(n \log n + q \log^2 n)$$$. Получил WA, подумал, что задача в чём-то другом состоит. В конце концов, зашло решение за $$$O(nq)$$$ (249 мс) и это очень меня удивило.
Ещё меня очень беспокоила фраза "Советуем решать задачу под песню: Calvin Harris — Summer" . В таких задачах обычно просто так такое не пишут. Не очень понимаю, зачем это было. Жутко расстроило то, что, в конце концов, она оказалась там просто так. Долго пытался понять её глубинный смысл в этой задаче. В песне было что-то про листья, и я изо всех сил долго и честно пытался хоть как-то связать это.)
А все остальные задачи очень даже ничего.
Я единственный, видимо, кто сдал задачу $$$A$$$ на C++. Идея с $$$|a|, |b|$$$ очень понравилась. Ещё подумал на то, что во фразе "А и Б" имеет место побитовое И. Пытался с этим связать как-то ответ изначально. Хорошая задача и понятное условие.
Задача $$$B$$$ неплохая. Без подвохов.
Задача $$$F$$$ очень повеселила. Наверное, одна из самых хороших, по моему мнению. Но даже её я решил криво. Не увидел одинарные кавычки у первых двух слов. Приметил, что фраза "без кавычек" есть только у третьего слова и подумал, что остальные нужно выводить с двойными кавычками.)
Задача $$$G$$$ хорошая. Сразу подумал на то, что опечатки там не просто так, но почему-то очень долго до меня доходило, что буквы надо выписать. Хотя я в прошлом уже видел похожую задачу.
В задаче $$$I$$$ так и не понял, почему точки, лежащие на одной прямой, образуют $$$0$$$. Скорее ещё одну длинную единицу. :-)
И задача $$$J$$$.
Когда я делал задачу H, добавляя песню, я просто хотел сделать отсылку к гачи) В следующий раз учту, но прикольно получилось, что кто-то искал какой-то скрытый смысл.
Теперь я назову это намеренной мерой для отвлечения внимания!
Кстати для меня стало большим удивлением то, что многие думали именно над HLD в этой задаче, хотя сам ее решал с помощью LCA (но видел решения и через ordered_set, которое мне очень понравилось).
UPD: к сожалению тесты и вправду были слабые, поэтому O(nq) заходило(
Я очень не хотел писать HLD. До последнего пытался как-то этого избежать. В результате, совсем уже не найдя никаких связей между песней и задачей, я всё-таки потратил примерно 2 часа (код+отладка) для того, чтобы с нуля всё написать (ни разу до этого не писал HLD, были попытки, но в конце концов всё бросал).
HLD просто очень стандартный метод для решения подобного рода задач, поэтому, вероятно, много людей и решило им воспользоваться. Мне понравилось решение авторское за $$$O(n + q^2)$$$, но я до него не додумался бы.)
I enjoyed this contest very much but one small thing the English statement says
Output a single number less than 998244353 - the answer to the problem
I don't know if it's like that in the Russian statement but damn this was the worst lie of the contest.
I cannot say that this was a lie, not an intentional lie at least. The chosen wording behind the output was meant to make the unobservant people think that you need to print the answer $$$mod\ 998244353$$$ since the possible true answer ($$$10^6 * 10^6$$$) could be quite big.