Gerald's blog

By Gerald, 7 years ago, In Russian,

245A - Системный администратор

Задача на реализацию того, что написано в условии. Код мог выглядеть как-то так:

    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 - Интернет-адрес

В данной задаче требовалось умение работать со строками. Опять же, приведу код одного из прорешивающих:

    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 - Игра с монетами

У этой задачи было несколько решений, видимо, самое простое для осознание использует идею динамического программирования. Динамическое программирование 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 - Восстановление таблицы

В этой задаче важно было условие, что решение всегда существует. Получить его можно было например так:

    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 - Происшествие в клубе

В задаче нужно было применить жадные соображения следующего характера. Если есть человек, который вышел и которого видел Поликарп, то если кто-то заходит в клуб, можно считать, что заходит этот человек. Аналогочно для выходящих. Лаконичный код решения:

    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 - Анализ потока логов

В этой задаче нужно было аккуратно распарзить входные данные. Перевести все даты в секунды. А затем, одним проходом по отсортированному массиву чисел, сделать ровно то, что написано в условии. Важно заметить, что размер входных данных был достаточно большим, поэтому читать эти данные нужно было достаточно быстро.

245G - Возможные друзья

В этой задаче планировалось решение за O(m2) с маленькой константой. Для начала предложим, что заданный во входных данных граф отношений связный, тогда количество вершин в нем n ≤ m + 1. Будем хранить такой граф в виде матрицы смежности a и ввиде списка смежных вершин для всех вершин. Теперь переберем вершину, которая будет общим другом предполагамых друзей. Далее переберем пару вершин, из списка смежных ей вершин, проверим, что они не соединены ребром, и сделаем инкремент в некоторую другую матрицу в ячейку b[u][v]. Эта матрица будет хранить количество, общих друзей между u, v, если u и v не соединены ребром.

После того, как мы построили матрицу b можно легко посчитать возможных друзей.

В случае, когда граф несвязный. Надо отдельно решить задачу для компонент связности. При этом надо аккуратно рассмотреть случай, когда возможный друг находится в другой компоненте.

245H - Запросы на количество палиндромов

Решение задачи динамическое программирование. 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.

 
 
 
 
  • Vote: I like it
  • +21
  • Vote: I do not like it