sharpc (sharpc) wrote,
sharpc
sharpc

Categories:
  • Music:

SRM 454

Автор сета — Gluk. Контест, к сожалению, был почти целиком технический. Боги Топкодера, судя по всему, разгневались на меня, иначе чем объяснить тот факт, что последние 3 контеста у меня падали 250? Падение продолжается с одним перерывом аж с апреля, так что я уже примеряю зеленую форму лузера (привет, shuffle_c :)).

↓1282


div2 250
Найти наименьшее число в [A;B], которое по сумме цифр ближе всего к C. A,B,C до 1ккк, но B−A до 100к.

Ограничение на длину интервала позволяет нам просто перебрать все его числа.

class MinimalDifference {
public:
    int digitsum(int n)
    {
        int res = 0;
        while (n) { res += n % 10; n /= 10; }
        return res;
    }

    int findNumber(int A, int B, int C) {
        int res = A, mres = numeric_limits<int>::max();
        for (int i = A; i <= B; ++i) {
            if (abs(digitsum(i) - digitsum(C)) < mres) {
                mres = abs(digitsum(i) - digitsum(C));
                res = i;
            }
        }
        return res;
    }
};



div2 500
Найти, за какое минимальное число перестановок строк и/или столбцов можно (если можно) сделать в таблице букв n×n заданное слово из n разных символов по горизонтали или вертикали (n до 50).

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

class WordsGame {
public:
    int swaps(string a, string b)
    {
        int res = 0;
        size_t n = a.length();
        for (int i = 0; i < n; ++i) if (a[i] != b[i]) {
            swap(a[i], a[a.find(b[i])]);
            ++res;
        }
        return res;
    }

    int minimumSwaps(vector <string> grid, string word) {
        size_t n = word.length();
        int res = numeric_limits<int>::max();
        for (int i = 0; i < n; ++i) {
            bool has = true; for (int j = 0; j < n; ++j) if (grid[i].find(word[j]) == string::npos) has = false;
            if (has) res = min(res, swaps(grid[i], word));
            string vword; for (int j = 0; j < n; ++j) vword.push_back(grid[j][i]);
            has = true; for (int j = 0; j < n; ++j) if (vword.find(word[j]) == string::npos) has = false;
            if (has) res = min(res, swaps(vword, word));
        }
        return res == numeric_limits<int>::max() ? -1 : res;
    }
};



div1 250
Левоассоциативная операция ^^ над двумя числами преобразует их соответствующие цифры в (ai ^ bi) % 10. Найти N ^^ (N−1) ^^ ... ^^ 1. N до 1кк.

Ограничение на N позволяет вычислить ответ циклом от N до 1. До сих пор удивляюсь, что заставило меня написать цикл в другую сторону :)

class DoubleXor {
public:
    int calculate(int N) {
        int p10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000};
        int res = 0;
        for (int i = N; i >= 1; --i) {
            int nres = 0;
            for (int z = 0; z < 8; ++z) {
                nres += ((((i / p10[z]) % 10) ^ ((res / p10[z]) % 10)) % 10) * p10[z];
            }
            res = nres;
        }
        return res;
    }
};



div2 1000 & div1 500
Спичками выложено число N до 1018−1 (как обычно, цифра до 7 спичек, только к единице снизу добавлена спичка). Сколько разных чисел (включая начальное) можно получить, переместив для получения каждого не более K спичек?

Представим, что у нас есть большая кучка спичек, а все операции сводятся к перемещению спички из числа в кучку и наоборот. Тогда одному ходу по условию будет соответствовать, например, только перемещение спички из кучки в число. Получим ДП [число обработанных цифр][количество оставшихся перемещений][количество спичек в кучке] = количество различных чисел. Тогда ответом будет являться сумма элементов массива, соответствующих всем обработанным цифрам и начальному количеству спичек в кучке (в реализации — 128). Легко посчитать, захардкодив внешний вид цифр, сколько спичек нужно снять, а сколько положить, чтобы из любой цифры получить любую. После этого будем пробовать сменить каждую цифру на любую.

Эту задачу я дебажил почти полчаса, ни на секунду не предположив, что неправильно считаю (логарифмом) количество цифр в N :)

long long dp[20][128][256];

class NumbersAndMatches {
public:
    long long differentNumbers(long long N, int K) {
        long long p10[19] = {1}; for (int i = 1; i < 19; ++i) p10[i] = p10[i-1] * 10;
        memset(dp, 0, sizeof(dp));
        dp[0][K][128] = 1;
        int D = 0; for (long long n = N; n; ++D) n /= 10;
       
        int digit[][7] = {  {1,1,1,0,1,1,1},
                    {0,0,1,0,0,1,1},
                    {1,0,1,1,1,0,1},
                    {1,0,1,1,0,1,1},
                    {0,1,1,1,0,1,0},
                    {1,1,0,1,0,1,1},
                    {1,1,0,1,1,1,1},
                    {1,0,1,0,0,1,0},
                    {1,1,1,1,1,1,1},
                    {1,1,1,1,0,1,1}};

        int add[10][10], del[10][10];
        memset(add, 0, sizeof(add));
        memset(del, 0, sizeof(del));
        for (int i = 0; i < 10; ++i) for (int j = 0; j < 10; ++j) for (int k = 0; k < 7; ++k) {
            add[i][j] += digit[j][k] > digit[i][k];
            del[i][j] += digit[j][k] < digit[i][k];
        }
       
        for (int i = 0; i < D; ++i) {
            for (int j = 0; j <= K; ++j) {
                for (int k = -126; k <= 126; ++k) if (dp[i][j][k + 128]) {
                    int odigit = (N / p10[D-i-1]) % 10;
                    for (int ndigit = 0; ndigit < 10; ++ndigit) {
                        if (add[odigit][ndigit] <= j) {
                            dp[i+1]
                              [j - add[odigit][ndigit]]
                              [k + add[odigit][ndigit] - del[odigit][ndigit] + 128] += dp[i][j][k + 128];
                        }
                    }
                }
            }
        }
       
        long long result = 0;
        for (int j = 0; j <= K; ++j) result += dp[D][j][128];
        return result;
    }
};



div1 1000
Таблица заполнена числами таким образом:
1291025
4381124
5671223
1615141322
1718192021

Для каждого числа X в таблице S(X) равно сумме всех элементов таблицы не ниже и не правее X. Дано число N (до 10ккк), найти сумму S(X) для всех X не ниже и не правее N по модулю 109+7.

В итоговую сумму каждое X входит столько раз, сколько чисел внутри прямоугольника, образованного X и N. Если попытаться сложить эти произведения напрямую, получим TL, т.к. 10ккк это много. Но можно посчитать сумму сразу для какого-то участка таблицы, где числа идут в одном направлении — например, len чисел, начиная с числа from, которое находится на расстоянии dl строк и dc колонок от N, и которые идут в направлении (dirl; dirc). Сумма по номеру числа в последовательности от получившегося полинома 2-й степени легко складывается в закрытую формулу, вычисляемую за O(1), либо в Maple, либо почленно с использованием известных формул для сумм квадратов и первых степеней. После этого следует просуммировать каждый отрезок (их O(sqrt(N))) внутри квадрата, а потом дополнить до прямоугольника. Если внимательно проделать эту механическую работу, не забыв везде понатыкать long long и модуль, можно получить AC. На контесте с этим справились только 3 человека.

const int M = 1000000007;

class MegaSum {
public:
    pair<long long, long long> loc(long long N)
    {
        long long layer = (long long) sqrt((double) (N - 1));
        long long d = N - layer * layer;
        if (layer % 2 == 1) return d <= layer ? make_pair(d - 1, layer) : make_pair(layer, layer - (d - layer - 1));
        else return d <= layer ? make_pair(layer, d - 1) : make_pair(layer - (d - layer - 1), layer);
    }
   
    long long sumn2(long long n) { return (2*n*n*n+3*n*n+n) / 6 % M; }
    long long sumn(long long n) { return (n*n+n) / 2 % M; }

    long long sum(long long from, long long len, long long dl, long long dc, long long dirl, long long dirc)
    {
        ++dl; ++dc;
        if (dirl) { swap(dl, dc); swap(dirl, dirc); }
        long long res = (long long) dl * ((-dirc * sumn2(len - 1) +
            (((-from * dirc + dc) % M) * sumn(len - 1) % M) +
            (from % M) * (dc * len % M)) % M) % M;
        return res;
    }

    int calculate(long long N)
    {
        long long res = 0;
        pair<long long, long long> ep = loc(N);
        bool wide = ep.first < ep.second;
        long long ns = min(ep.first, ep.second) + 1, ms = max(ep.first, ep.second) + 1;
        for (long long i = 0; i < ns; ++i) {
            res += sum(i*i+1, i+1, ep.first-(i%2?0:i), ep.second-(i%2?i:0), i%2?1:0, i%2?0:1) % M;
            res += sum(i*i+i+2, i, ep.first-(i%2?i:i-1), ep.second-(i%2?i-1:i), i%2?0:-1, i%2?-1:0) % M;
            res %= M;
        }
        for (long long i = ns; i < ms; ++i) {
            if (wide) res += sum(i%2?i*i+1:(i+1)*(i+1)-ns+1, ns, i%2?ns-1:0, ms-i-1, i%2?1:-1, 0) % M;
            else      res += sum(i%2?(i+1)*(i+1)-ns+1:i*i+1, ns, ms-i-1, i%2?0:ns-1, 0, i%2?-1:1) % M;
            res %= M;
        }
       
        return res % M;
    }
};



В заключение упомяну об интересном факте: оказывается, вплоть до 1976 года было неизвестно, существуют ли непрерывно изгибающиеся многогранники без самопересечений. Оказывается, существуют :) Пока не доказано, что минимальным (9 вершин) многогранником с таким свойством является полиэдр Штеффена. Вот он на видео. Я склеил его для проверки — действительно, изгибается :) Самым интересным связанным результатом является теорема Сабитова, доказанная в 1996, из которой следует верность гипотезы «кузнечных мехов» о том, что объем любого изгибающегося многогранника постоянен. Примеры изгибающихся многогранников для пространств с размерностью 5 и выше еще не построены :)

Попутно отмечу, что мало что может сравниться по омерзительности с подключением GMP под виндой, даже если он уже собран. Дьявольские байты вызывают Access violation, не имеют .lib-файлов, нормального C++-враппера и всячески демонстрируют си головного мозга у создателей, какбе призывая образ ржавой секиры ужаса в мысли несчастных программистов.

Ну и запишу-ка я Evenfall в список открытий этого года, а Eternal Tears Of Sorrow c альбомом Children Of The Dark Waters в свой ежегодный топ музыкальных альбомов.
Tags: олимпиады
Subscribe

Recent Posts from This Journal

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments