Школьный этап олимпиады по информатике

Задачи для 9-11 классов

Задача В. Королевские кони

Идея решения состоит в следующем. Преобразуем шахматные координаты в “обычные”, числовые. Так как латинские буквы a, b, c, d, e, f, g и h (также, как и числовые символы) располагаются в кодовой таблице последовательно, то разница их кодов даст нам разницу координат. Разница координат взятая по модулю и будет ответом к задаче. Остается определить, в каком порядке нужно выводить.

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

void horse(string &, string &);

int main() {
    string XY1, XY2;
    getline(cin, XY1);
    getline(cin, XY2);
    horse(XY1, XY2);
    return 0;
}

void horse(string &s1, string &s2) {
    int x1 = static_cast<int>(s1.front());
    int y1 = static_cast<int>(s1.back());
    int x2 = static_cast<int>(s2.front());
    int y2 = static_cast<int>(s2.back());
    int a = abs(x1 - x2);
    int b = abs(y1 - y2);
    a < b ? cout << a << " " << b:
            cout << b << " " << a;
    cout << endl;
}

Задача С. Параллелограммы

Параллелограмм – это фигура у которой по две равной стороны. Отсюда, необходимо определить сколько найдется “пар по паре”. В первом варианте полученный массив сортируем и определяем, с помощью стандартного алгоритма, длины цепочек повторяющихся элементов.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    unsigned n;
    cin >> n;
    vector<unsigned> par;
    for (size_t i = 0; i < n; ++i) {
        unsigned d;
        cin >> d;
        par.push_back(d);
    }
    sort(par.begin(), par.end());
    auto k = 0u, i = 0u;
    while (i < n) {
        auto j = 0u, m = par[i];
        while (m == par[i]) {
            j++;
            i++;
        }
        k += j / 2;
    }
    cout << k / 2 << endl;
    return 0;
}

Попробуем ускорить и уменьшить код. Применим итераторы и структуру set (в версии мультимножества).

#include <iostream>
#include <set>

using namespace std;

int main() {
    unsigned n;
    cin >> n;
    multiset<unsigned> par;
    for (size_t i = 0; i < n; ++i) {
        unsigned d;
        cin >> d;
        par.emplace(d);
    }
    auto k = 0u, j = 0u;
    auto first = par.begin();
    while (first != par.end()) {
        j = par.count(*first);
        k += j / 2;
        first = par.upper_bound(*first);
    }
    cout << k / 2 << endl;
    return 0;
}

Программа будет работать быстро, но не факт, что она пройдет тесты на память, поскольку массив всё так же будет храниться целиком. Чтобы достичь максимальной эффективности нужно воспользоваться контейнером map. Он во всем подобен set, но элементом массива является пара: ключ и значение ключа. В map – ключ имеет уникальное значение, чем мы и воспользуемся чтобы не хранить уже имеющееся ключи. Если будет найден ключ с тем же значением, то мы инкрементируем второй элемент пары – значение ключа. Таким образом у нас будет накапливаться количество элементов равных нашему ключу. Кроме того, поиск элементов в этом контейнере (равно как и в set) осуществляется очень быстро.

#include <iostream>
#include <map>

using namespace std;

int main() {
    unsigned n;
    cin >> n;
    map<unsigned, unsigned> par;
    for (size_t i = 0; i < n; ++i) {
        unsigned d;
        cin >> d;
        auto it = par.find(d);
        if (it == par.end())
            par.emplace(d, 1);
        else
            it -> second++;
    }
    auto k = 0u, j = 0u;
    auto frst = par.begin();
    auto last = par.end();
    while (frst != last) {
        j = frst -> second;
        k += j / 2;
        frst++;
    }
    cout << k / 2 << endl;
    return 0;
}
Print Friendly, PDF & Email

Добавить комментарий