Лучше поздно, чем никогда...↵
------------------↵
↵
### [problem:644A]↵
↵
Из условия задачи следует, что либо демократов и республиканцев поровну (если $n$ чётно), либо демократов на одного больше (если $n$ нечётно). Так как представители одной и той же партии не должны сидеть на соседних креслах, представим парламентский зал в виде шахматной доски, где левая верхняя клетка будет белой. Затем начнем перебирать ряды клеток сверху вниз, а клетки в каждом ряду слева направо и будем по очереди сажать парламентариев — демократов в белые клетки, а республиканцев в черные. ↵
↵
Таким образом, если $n > a \cdot b$, ответом будет $-1$. В противном случае рассадка всегда найдется. ↵
↵
Для определения того, какого цвета клетка (и, соответственно, кого нужно в нее посадить), находящаяся в $i$-й строке и $j$-м столбце (в случае, если они нумеруются с единицы), можно поступить следующим образом. Если $(i + j) mod 2 = 0$, значит соответствующая клетка должна быть белой, иначе чёрной.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
Основная часть решения:↵
↵
~~~~~↵
cin >> n >> a >> b;↵
m = n - 1;↵
if (n > a * b) {↵
cout << -1;↵
return 0;↵
}↵
for (int i = 0; i < a; i++) {↵
for (int j = 0; j < b; j++) {↵
if ((i + j) % 2 == 0) {↵
cout << n << " ";↵
n = max(n - 2, 0);↵
} else {↵
cout << m << " ";↵
m = max(m - 2, 0);↵
}↵
}↵
cout << endl;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [problem:644B]↵
↵
Для решения данной задачи очень удобно воспользоваться структурой данных, которая называется очередь.↵
↵
Очередь — это структура данных со следующим принципом доступа к элементам: «первый пришёл — первый ушёл». Добавление элемента (\textit{push}) возможно лишь в конец очереди, а взять элемент из очереди можно только из её начала (\textit{front}). Удалить элемент можно также только из начала очереди (\textit{pop}).↵
↵
В данной задаче нужно было перебрать все запросы в хронологическом порядке. Будем хранить в очереди времена окончания обработки запросов. Для текущего запроса, пока в начале очереди находятся запросы, которые закончат обрабатываться не позднее, чем появился текущий запрос, нужно просто удалять их из начала очереди, так как они никак не повлияют на текущий. Если после этих действий размер очереди равен максимальному допустимому числу, ответ для текущего запроса $-1$. В противном случае, нужно добавить время окончания обработки текущего запроса в очередь, вывести это время и продолжить алгоритм.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
Основная часть решения:↵
↵
~~~~~↵
queue<long long> q;↵
int main() {↵
cin >> n >> b;↵
for (int i = 0; i < n; i++) {↵
cin >> t >> d;↵
while (q.size() && q.front() <= t)↵
q.pop();↵
if (q.empty()) ↵
ans = t;↵
if (q.size() <= b) {↵
ans += d;↵
q.push(ans);↵
cout << ans << ' ';↵
} else↵
cout << -1 << ' ';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [problem:644C]↵
↵
Для решения данной задачи воспользуемся структурами данных $map$ и $set$. Переберем все имеющиеся адреса страниц, затем получим $hostname$ и path для каждого адреса, и добавим текущий path в множество путей для текущего $hostname$ (для этого будет нужен $map$, где ключом будет строка $hostname$, а значением — множество строк $path$).↵
↵
Осталось только объединить все $hostname$, множества путей которых совпадают (это можно сделать с помощью map, где ключом будет множество строк $path$, а значением — вектор строк $hostname$), и вывести те группы, размер которых больше единицы.↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
Основная часть решения:↵
↵
~~~~~↵
cin >> n;↵
for (int i = 0; i < n; i++) {↵
cin>>s, s += '/';↵
int p = s.find('/',7);↵
m[s.substr(0, p)].insert(s.substr(p));↵
}↵
for (auto &i:m) {↵
v[i.second].push_back(i.first);↵
k += (v[i.second].size() == 2);↵
}↵
cout<< k << endl;↵
for (auto &i:v) {↵
if (i.second.size()>1) {↵
for (auto &j:i.second) cout << j << ' '; ↵
cout << endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
------------------↵
↵
### [problem:644A]↵
↵
Из условия задачи следует, что либо демократов и республиканцев поровну (если $n$ чётно), либо демократов на одного больше (если $n$ нечётно). Так как представители одной и той же партии не должны сидеть на соседних креслах, представим парламентский зал в виде шахматной доски, где левая верхняя клетка будет белой. Затем начнем перебирать ряды клеток сверху вниз, а клетки в каждом ряду слева направо и будем по очереди сажать парламентариев — демократов в белые клетки, а республиканцев в черные. ↵
↵
Таким образом, если $n > a \cdot b$, ответом будет $-1$. В противном случае рассадка всегда найдется. ↵
↵
Для определения того, какого цвета клетка (и, соответственно, кого нужно в нее посадить), находящаяся в $i$-й строке и $j$-м столбце (в случае, если они нумеруются с единицы), можно поступить следующим образом. Если $(i + j) mod 2 = 0$, значит соответствующая клетка должна быть белой, иначе чёрной.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
Основная часть решения:↵
↵
~~~~~↵
cin >> n >> a >> b;↵
m = n - 1;↵
if (n > a * b) {↵
cout << -1;↵
return 0;↵
}↵
for (int i = 0; i < a; i++) {↵
for (int j = 0; j < b; j++) {↵
if ((i + j) % 2 == 0) {↵
cout << n << " ";↵
n = max(n - 2, 0);↵
} else {↵
cout << m << " ";↵
m = max(m - 2, 0);↵
}↵
}↵
cout << endl;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [problem:644B]↵
↵
Для решения данной задачи очень удобно воспользоваться структурой данных, которая называется очередь.↵
↵
Очередь — это структура данных со следующим принципом доступа к элементам: «первый пришёл — первый ушёл». Добавление элемента (\textit{push}) возможно лишь в конец очереди, а взять элемент из очереди можно только из её начала (\textit{front}). Удалить элемент можно также только из начала очереди (\textit{pop}).↵
↵
В данной задаче нужно было перебрать все запросы в хронологическом порядке. Будем хранить в очереди времена окончания обработки запросов. Для текущего запроса, пока в начале очереди находятся запросы, которые закончат обрабатываться не позднее, чем появился текущий запрос, нужно просто удалять их из начала очереди, так как они никак не повлияют на текущий. Если после этих действий размер очереди равен максимальному допустимому числу, ответ для текущего запроса $-1$. В противном случае, нужно добавить время окончания обработки текущего запроса в очередь, вывести это время и продолжить алгоритм.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
Основная часть решения:↵
↵
~~~~~↵
queue<long long> q;↵
int main() {↵
cin >> n >> b;↵
for (int i = 0; i < n; i++) {↵
cin >> t >> d;↵
while (q.size() && q.front() <= t)↵
q.pop();↵
if (q.empty()) ↵
ans = t;↵
if (q.size() <= b) {↵
ans += d;↵
q.push(ans);↵
cout << ans << ' ';↵
} else↵
cout << -1 << ' ';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [problem:644C]↵
↵
Для решения данной задачи воспользуемся структурами данных $map$ и $set$. Переберем все имеющиеся адреса страниц, затем получим $hostname$ и path для каждого адреса, и добавим текущий path в множество путей для текущего $hostname$ (для этого будет нужен $map$, где ключом будет строка $hostname$, а значением — множество строк $path$).↵
↵
Осталось только объединить все $hostname$, множества путей которых совпадают (это можно сделать с помощью map, где ключом будет множество строк $path$, а значением — вектор строк $hostname$), и вывести те группы, размер которых больше единицы.↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Пример решения">↵
Основная часть решения:↵
↵
~~~~~↵
cin >> n;↵
for (int i = 0; i < n; i++) {↵
cin>>s, s += '/';↵
int p = s.find('/',7);↵
m[s.substr(0, p)].insert(s.substr(p));↵
}↵
for (auto &i:m) {↵
v[i.second].push_back(i.first);↵
k += (v[i.second].size() == 2);↵
}↵
cout<< k << endl;↵
for (auto &i:v) {↵
if (i.second.size()>1) {↵
for (auto &j:i.second) cout << j << ' '; ↵
cout << endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
