245A - System Administrator
Задача на реализацию того, что написано в условии. Код мог выглядеть как-то так:
int[] accepted = new int[2];
int[] lost = new int[2];
for (int i = 0; i < n; i++) {
int z = nextInt() - 1;
accepted[z] += nextInt();
lost[z] += nextInt();
}
for (int i = 0; i < lost.length; i++) {
if (accepted[i] >= lost[i]) {
out.println("LIVE");
} else {
out.println("DEAD");
}
}
245B - Internet Address
В данной задаче требовалось умение работать со строками. Опять же, приведу код одного из прорешивающих:
String s = nextToken();
if (s.startsWith("http")) {
out.print("http://");
s = s.substring(4);
} else {
out.print("ftp://");
s = s.substring(3);
}
out.print(s.substring(0, s.lastIndexOf("ru")));
out.print(".ru");
s = s.substring(s.lastIndexOf("ru") + 2);
if (s.length() != 0) {
out.print("/");
out.println(s);
}
245C - Game with Coins
У этой задачи было несколько решений, видимо, самое простое для осознание использует идею динамического программирования. Динамическое программирование dp[i][up], сколько нужно ходов, чтобы опустошить сундук номер i и все зависящие от него сундуки, при условии, что в нем сейчас находится max(0, ai - up) монет.
Чтобы посчитать dp[i][up] переберем сколько раз мы возьмем монету из этого сундука. Пусть мы возьмем из него p, тогда должно выполняться max(0, ai - up - p) = 0. Перебрав p переходим к подзадачам dp[2·i][p], dp[2·i + 1][p].
После подсчета всех состояний, ответ на задачу будет содержаться в dp[1][0].
Сколько операций выполнит подсчет такого динамического программирования. Очевидно, что p не имеет смысла брать более 1000. Тогда всего состояний в таком dp будет n·1000. Умножить на количество переходов, получается 100·1000·1000 = 108, операций в худшем случае.
245D - Restoring Table
В этой задаче важно было условие, что решение всегда существует. Получить его можно было например так:
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j){
cin >> b[i][j];
if(i == j)
continue;
a[i] |= b[i][j];
}
245E - Mishap in Club
В задаче нужно было применить жадные соображения следующего характера. Если есть человек, который вышел и которого видел Поликарп, то если кто-то заходит в клуб, можно считать, что заходит этот человек. Аналогочно для выходящих. Лаконичный код решения:
int in = 0, out = 0;
for(int i = 0; i < n; ++i){
if(s[i] == '+'){
in++;
out = max(out - 1, 0);
}
if(s[i] == '-'){
out++;
in = max(in - 1, 0);
}
}
cout << in + out << endl;
245F - Log Stream Analysis
В этой задаче нужно было аккуратно распарзить входные данные. Перевести все даты в секунды. А затем, одним проходом по отсортированному массиву чисел, сделать ровно то, что написано в условии. Важно заметить, что размер входных данных был достаточно большим, поэтому читать эти данные нужно было достаточно быстро.
245G - Suggested Friends
В этой задаче планировалось решение за O(m2) с маленькой константой. Для начала предложим, что заданный во входных данных граф отношений связный, тогда количество вершин в нем n ≤ m + 1. Будем хранить такой граф в виде матрицы смежности a и ввиде списка смежных вершин для всех вершин. Теперь переберем вершину, которая будет общим другом предполагамых друзей. Далее переберем пару вершин, из списка смежных ей вершин, проверим, что они не соединены ребром, и сделаем инкремент в некоторую другую матрицу в ячейку b[u][v]. Эта матрица будет хранить количество, общих друзей между u, v, если u и v не соединены ребром.
После того, как мы построили матрицу b можно легко посчитать возможных друзей.
В случае, когда граф несвязный. Надо отдельно решить задачу для компонент связности. При этом надо аккуратно рассмотреть случай, когда возможный друг находится в другой компоненте.
245H - Queries for Number of Palindromes
Решение задачи динамическое программирование. dp[i][j] — количество палиндромов в подстроке s[i...j], isp[i][j] — является ли палиндромом подстрока s[i...j]. Переходы dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + isp[i][j], isp[i][j] = 1, если isp[i + 1][j - 1] = 1, и s[i] = s[j]. Иначе isp[i][j] = 0.
Comments (0)
