Это был бы самый обычный разбор, если бы не новая фича — спойлеры. Заценить как это круто и удобно можно уже прямо в этом посте, к каждой задаче под спойлером прикладывается код решения. Скажем спасибо [user:kuviman,2016-03-14] :)↵
↵
Текст разбора: [user:MikeMirzayanov,2016-03-14], [user:fcspartakm,2016-03-14] и [user:GlebsHP,2016-03-14].↵
↵
### [problem:637A]↵
↵
Автор идеи: [user:MikeMirzayanov,2016-03-14]. Разработка: [user:fcspartakm,2016-03-14].↵
↵
Для решения данной задачи достаточно было проитерироваться по поставленным лайкам в хронологическом порядке и в отдельном массиве поддерживать количество лайков, которые уже были поставлены фотографиям (например, в $cnt[i]$ будет храниться количество лайков, поставленных $i$-й фотографии). Для нахождения ответа достаточно на каждой итерации обновлять имеющийся максимум лайков текущим значением $cnt[i]$, и если $cnt[i] > maxCnt$ обновлять ответ, где $maxCnt$ — это текущее максимальное количество лайков.↵
↵
Асимптотика такого решения — $O(n)$, где $n$ — количество поставленных лайков.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
Основная часть решения:↵
↵
~~~~~↵
int n;↵
int a[N];↵
int cnt[M];↵
↵
int main() {↵
scanf("%d", &n);↵
int maxCnt = 0, ans;↵
for (int i = 0; i < n; i++) {↵
scanf("%d", &a[i]);↵
cnt[a[i]]++;↵
if (cnt[a[i]] > maxCnt) {↵
ans = a[i];↵
maxCnt = cnt[a[i]];↵
}↵
}↵
printf("%d", ans);↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [problem:637B]↵
↵
Автор идеи: [user:GlebsHP,2016-03-14]. Разработка: [user:fcspartakm,2016-03-14].↵
↵
Для решения данной задачи нужно проитерироваться в обратном порядке по адресатам сообщений, начиная с последнего, так как верно то, что чем позднее Поликарп отправит сообщение какому-то собеседнику, тем выше этот собеседник будет в списке чатов. На каждой итерации нужно проверять, что текущий собеседник еще не был добавлен в список чатов (то есть Поликарп еще не писал ему сообщение). Это можно сделать с помощью структуры данных $set$. Таким образом, если текущего собеседника еще нет в списке чатов, нужно добавить имя этого собеседника в конец ответного списка чатов и добавить имя этого собеседника в $set$. ↵
↵
Асимптотика такого решения — $O(n \cdot log(n))$, где $n$ — количество сообщений, отправленных Поликарпом.↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
↵
Основная часть решения:↵
↵
~~~~~↵
int n;↵
string a[N];↵
set<string>names;↵
↵
int main () {↵
cin >> n;↵
for (int i = 0; i < n; i++) { ↵
cin >> a[i];↵
} ↵
for (int i = n - 1; i >= 0; i--) {↵
if(names.count(a[i]))↵
continue;↵
names.insert(a[i]);↵
cout << a[i] << endl;↵
} ↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [problem:637C]↵
↵
Автор идеи: [user:GlebsHP,2016-03-14]. Разработка: [user:GlebsHP,2016-03-14].↵
↵
Для начала научимся решать задачу проверки фиксированного значения $k$. Правда ли, что если мы в каждом промокоде совершим не более чем $k$ ошибок, ты мы сможем однозначно идентифицировать исходных промокод? Иначе говоря, верно ли, что для любой последовательности из шести цифр, существует не более одного промокода отличающегося от данной последовательности в $k$ или менее позициях.↵
↵
Для каждого промокода можно построить множество последовательностей отличающихся от него не более чем в $k$ позициях, то есть шар радиуса $k$ в данной метрике. Так, для промокода $123456$ подойдут последовательности $?23456$, $1?3456$, $12?456$, $123?56$, $1234?6$ и $12345?$ (вопросик заменяется на любую цифру). Очевидно, что некоторое $k$ подходит, если никакие два шара радиуса $k$ не пересекаются. Этого уже достаточно для решения задачи, просто честно перебрать значения $k$ и проверить наличие пересечения шаров. Единственная тонкость — процесс необходимо остановить как только найдётся любая последовательность принадлежащая двум шарам.↵
↵
Благодаря условию $n \leq 1000$ задачу можно было решить и гораздо проще. Заметим, что два шара радиуса $k$ пересекаются если расстояние между их центрами не превосходит $2 \cdot k$. Таким образом достаточно найти пару прокодов с минимальным расстоянием между ними и выбрать максимальное подходящее $k$. Не забываем про случай $n = 1$.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
↵
Основная часть решения:↵
↵
~~~~~↵
int calc_dist(const string& s1, const string& s2) {↵
int d = 0;↵
for (int i = 0; i < (int) s1.size(); i++)↵
d += (s1[i] != s2[i]);↵
↵
return d;↵
}↵
↵
int main() {↵
int n;↵
cin >> n;↵
vector <string> code(n);↵
↵
for (int i = 0; i < n; i++)↵
cin >> code[i];↵
↵
int ans = 12;↵
for (int i = 0; i < n; i++)↵
for (int j = i + 1; j < n; j++)↵
ans = min(ans, calc_dist(code[i], code[j]) - 1);↵
↵
cout << ans / 2 << endl;↵
↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [problem:637D]↵
↵
Автор идеи: [user:MikeMirzayanov,2016-03-14]. Разработка: [user:fcspartakm,2016-03-14].↵
↵
В самом начале отсортируем все координаты препятствий по возрастанию. Затем воспользуемся следующим фактом: если спортсмен может преодолеть препятствие номер $x$ и успевает разбежаться перед прыжком до препятствия номер $x + 1$ (то есть $s \le a[x + 1] - a[x] - 2$, где $s$ — длина разбега перед прыжком), ему выгодно разбежаться и начать новый прыжок в точке $a[x + 1] - 1$.↵
↵
Таким образом, для решения задачи достаточно проитерироваться по препятствиям слева направо. Пусть спортсмен преодолеть препятствие с номером $i$. Тогда нужно найти первое такое препятствие с номером $j$ (правее $i$), что спортсмен успеет разбежаться для прыжка после препятствия $j - 1$ и до препятствия $j$. В таком случае спортсмену необходимо выполнить прыжок из точки $a[i + 1] - 1$ в точку $a[j - 1] + 1$. Если расстояние между этими точками больше чем $d$, значит спортсмен не сможет добраться до финиша. В противном случае нужно выполнить такой прыжок и продолжить работу программы. После преодоления всех препятствий нужно проверить нужно ли спортсмену бежать до финишной точки, или он уже находится в ней. ↵
↵
Асимптотика такого решения — $O(n \log n)$, где $n$ — количество препятствий.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
↵
Основная часть решения:↵
↵
~~~~~↵
int a[N];↵
int n, m, s, d;↵
vector<pair<string, int> > ans;↵
↵
int main () {↵
cin >> n >> m >> s >> d;↵
for(int i = 0; i < n; i++) {↵
cin >> a[i];↵
}↵
sort(a, a + n);↵
int curPos = 0;↵
for (int i = 0; i < n; ) {↵
int prev = i;↵
if(a[i] - curPos - 1 >= s) {↵
i++;↵
while(i < n && a[i] - a[i - 1] - 2 < s)↵
i++;↵
int jumpDist = a[i - 1] + 1 - (a[prev] - 1);↵
if (jumpDist > d) {↵
cout << "IMPOSSIBLE" << endl;↵
return 0;↵
}↵
ans.push_back(make_pair("RUN", a[prev] - curPos - 1));↵
ans.push_back(make_pair("JUMP", jumpDist));↵
curPos = a[i - 1] + 1;↵
} else {↵
cout << "IMPOSSIBLE" << endl;↵
return 0;↵
} ↵
}↵
if(curPos != m)↵
ans.push_back(make_pair("RUN", m - curPos));↵
for(int i = 0; i < (int)ans.size(); i++) {↵
cout << ans[i].first << ' ' << ans[i].second << endl;↵
} ↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Текст разбора: [user:MikeMirzayanov,2016-03-14], [user:fcspartakm,2016-03-14] и [user:GlebsHP,2016-03-14].↵
↵
### [problem:637A]↵
↵
Автор идеи: [user:MikeMirzayanov,2016-03-14]. Разработка: [user:fcspartakm,2016-03-14].↵
↵
Для решения данной задачи достаточно было проитерироваться по поставленным лайкам в хронологическом порядке и в отдельном массиве поддерживать количество лайков, которые уже были поставлены фотографиям (например, в $cnt[i]$ будет храниться количество лайков, поставленных $i$-й фотографии). Для нахождения ответа достаточно на каждой итерации обновлять имеющийся максимум лайков текущим значением $cnt[i]$, и если $cnt[i] > maxCnt$ обновлять ответ, где $maxCnt$ — это текущее максимальное количество лайков.↵
↵
Асимптотика такого решения — $O(n)$, где $n$ — количество поставленных лайков.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
Основная часть решения:↵
↵
~~~~~↵
int n;↵
int a[N];↵
int cnt[M];↵
↵
int main() {↵
scanf("%d", &n);↵
int maxCnt = 0, ans;↵
for (int i = 0; i < n; i++) {↵
scanf("%d", &a[i]);↵
cnt[a[i]]++;↵
if (cnt[a[i]] > maxCnt) {↵
ans = a[i];↵
maxCnt = cnt[a[i]];↵
}↵
}↵
printf("%d", ans);↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [problem:637B]↵
↵
Автор идеи: [user:GlebsHP,2016-03-14]. Разработка: [user:fcspartakm,2016-03-14].↵
↵
Для решения данной задачи нужно проитерироваться в обратном порядке по адресатам сообщений, начиная с последнего, так как верно то, что чем позднее Поликарп отправит сообщение какому-то собеседнику, тем выше этот собеседник будет в списке чатов. На каждой итерации нужно проверять, что текущий собеседник еще не был добавлен в список чатов (то есть Поликарп еще не писал ему сообщение). Это можно сделать с помощью структуры данных $set$. Таким образом, если текущего собеседника еще нет в списке чатов, нужно добавить имя этого собеседника в конец ответного списка чатов и добавить имя этого собеседника в $set$. ↵
↵
Асимптотика такого решения — $O(n \cdot log(n))$, где $n$ — количество сообщений, отправленных Поликарпом.↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
↵
Основная часть решения:↵
↵
~~~~~↵
int n;↵
string a[N];↵
set<string>names;↵
↵
int main () {↵
cin >> n;↵
for (int i = 0; i < n; i++) { ↵
cin >> a[i];↵
} ↵
for (int i = n - 1; i >= 0; i--) {↵
if(names.count(a[i]))↵
continue;↵
names.insert(a[i]);↵
cout << a[i] << endl;↵
} ↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [problem:637C]↵
↵
Автор идеи: [user:GlebsHP,2016-03-14]. Разработка: [user:GlebsHP,2016-03-14].↵
↵
Для начала научимся решать задачу проверки фиксированного значения $k$. Правда ли, что если мы в каждом промокоде совершим не более чем $k$ ошибок, ты мы сможем однозначно идентифицировать исходных промокод? Иначе говоря, верно ли, что для любой последовательности из шести цифр, существует не более одного промокода отличающегося от данной последовательности в $k$ или менее позициях.↵
↵
Для каждого промокода можно построить множество последовательностей отличающихся от него не более чем в $k$ позициях, то есть шар радиуса $k$ в данной метрике. Так, для промокода $123456$ подойдут последовательности $?23456$, $1?3456$, $12?456$, $123?56$, $1234?6$ и $12345?$ (вопросик заменяется на любую цифру). Очевидно, что некоторое $k$ подходит, если никакие два шара радиуса $k$ не пересекаются. Этого уже достаточно для решения задачи, просто честно перебрать значения $k$ и проверить наличие пересечения шаров. Единственная тонкость — процесс необходимо остановить как только найдётся любая последовательность принадлежащая двум шарам.↵
↵
Благодаря условию $n \leq 1000$ задачу можно было решить и гораздо проще. Заметим, что два шара радиуса $k$ пересекаются если расстояние между их центрами не превосходит $2 \cdot k$. Таким образом достаточно найти пару прокодов с минимальным расстоянием между ними и выбрать максимальное подходящее $k$. Не забываем про случай $n = 1$.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
↵
Основная часть решения:↵
↵
~~~~~↵
int calc_dist(const string& s1, const string& s2) {↵
int d = 0;↵
for (int i = 0; i < (int) s1.size(); i++)↵
d += (s1[i] != s2[i]);↵
↵
return d;↵
}↵
↵
int main() {↵
int n;↵
cin >> n;↵
vector <string> code(n);↵
↵
for (int i = 0; i < n; i++)↵
cin >> code[i];↵
↵
int ans = 12;↵
for (int i = 0; i < n; i++)↵
for (int j = i + 1; j < n; j++)↵
ans = min(ans, calc_dist(code[i], code[j]) - 1);↵
↵
cout << ans / 2 << endl;↵
↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [problem:637D]↵
↵
Автор идеи: [user:MikeMirzayanov,2016-03-14]. Разработка: [user:fcspartakm,2016-03-14].↵
↵
В самом начале отсортируем все координаты препятствий по возрастанию. Затем воспользуемся следующим фактом: если спортсмен может преодолеть препятствие номер $x$ и успевает разбежаться перед прыжком до препятствия номер $x + 1$ (то есть $s \le a[x + 1] - a[x] - 2$, где $s$ — длина разбега перед прыжком), ему выгодно разбежаться и начать новый прыжок в точке $a[x + 1] - 1$.↵
↵
Таким образом, для решения задачи достаточно проитерироваться по препятствиям слева направо. Пусть спортсмен преодолеть препятствие с номером $i$. Тогда нужно найти первое такое препятствие с номером $j$ (правее $i$), что спортсмен успеет разбежаться для прыжка после препятствия $j - 1$ и до препятствия $j$. В таком случае спортсмену необходимо выполнить прыжок из точки $a[i + 1] - 1$ в точку $a[j - 1] + 1$. Если расстояние между этими точками больше чем $d$, значит спортсмен не сможет добраться до финиша. В противном случае нужно выполнить такой прыжок и продолжить работу программы. После преодоления всех препятствий нужно проверить нужно ли спортсмену бежать до финишной точки, или он уже находится в ней. ↵
↵
Асимптотика такого решения — $O(n \log n)$, где $n$ — количество препятствий.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
↵
Основная часть решения:↵
↵
~~~~~↵
int a[N];↵
int n, m, s, d;↵
vector<pair<string, int> > ans;↵
↵
int main () {↵
cin >> n >> m >> s >> d;↵
for(int i = 0; i < n; i++) {↵
cin >> a[i];↵
}↵
sort(a, a + n);↵
int curPos = 0;↵
for (int i = 0; i < n; ) {↵
int prev = i;↵
if(a[i] - curPos - 1 >= s) {↵
i++;↵
while(i < n && a[i] - a[i - 1] - 2 < s)↵
i++;↵
int jumpDist = a[i - 1] + 1 - (a[prev] - 1);↵
if (jumpDist > d) {↵
cout << "IMPOSSIBLE" << endl;↵
return 0;↵
}↵
ans.push_back(make_pair("RUN", a[prev] - curPos - 1));↵
ans.push_back(make_pair("JUMP", jumpDist));↵
curPos = a[i - 1] + 1;↵
} else {↵
cout << "IMPOSSIBLE" << endl;↵
return 0;↵
} ↵
}↵
if(curPos != m)↵
ans.push_back(make_pair("RUN", m - curPos));↵
for(int i = 0; i < (int)ans.size(); i++) {↵
cout << ans[i].first << ' ' << ans[i].second << endl;↵
} ↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
