Решение задачи "Игра с таблицей" с Codeforces

С пояснением   Просмотров: 34

Ashish и Vivek играют в игру на таблице с n строками и m столбцами, захватывая клетки. Незахваченные клетки обозначены 0, а захваченные клетки обозначены 1. Вам дано исходное состояние таблицы.

На каждом ходу, игрок должен захватить одну клетку. Клетку можно захватить, если она еще не захвачена, и она не находится в одной строке или столбце с другой захваченной клеткой. Игра кончается, когда игрок не может сделать ход, в таком случае, он проигрывает.

Если Ashish и Vivek ходят по очереди и Ashish ходит первым, найдите победителя игры если они оба играют оптимально.

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

Код 

#include <bits/stdc++.h>

using namespace std;
void solve()
{
    int n, m, k = 0, t;
    cin >> n >> m;
    set<int> x, y;
    vector<int> a(max(n, m));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> t;
            if(t)
                x.insert(i), y.insert(j);
        }
    }
    k = min(n - x.size(), m - y.size());
    if(k % 2 == 0)
        cout << "Vivek";
    else
        cout << "Ashish";
    cout << endl;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

         

Администратор Photo Автор: Администратор


Код 

#include <vector>
#include <iostream>

using namespace std;

int main() {
    int n, m, t, current, maxHorizontal, maxVertical, min = 0, max;
    cin >> t;
    vector<vector<int>> field;
    for (int i = 0; i < t; ++i) {
        cin >> n;
        cin >> m;
        field.resize(n + 1, vector<int>(m + 1));
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= m; ++k) {
                cin >> current;
                field[j][k] = current;
                if (current == 1) {
                    field[0][k] = 1;
                    field[j][0] = 1;
                }
            }
        }
        maxHorizontal = 0;
        maxVertical = 0;
        for (int j = 1; j <= n; ++j) {
            if (field[j][0] == 0) {
                maxVertical++;
            }
        }
        for (int j = 1; j <= m; ++j) {
            if (field[0][j] == 0) {
                maxHorizontal++;
            }
        }
        min = __min(maxHorizontal, maxVertical);
        if (min % 2 == 1) {
            cout << "Ashish";
        } else {
            cout << "Vivek";
        }
        cout << endl;
        field.clear();
    }
}

         

Шефер Аркадий Photo Автор: Шефер Аркадий


Пояснение к задаче

Ключевая идея:

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

Решение:

Пусть a будет количеством строк, в которых изначально не было заявлено ни одной ячейки, и аналогичным образом b будет количеством столбцов, в которых изначально не было заявлено ни одной ячейки. Каждый раз, когда игрок делает ход, a и b уменьшаются на 1, так как они требуют ячейки только в строках и столбцах без заявленных ячеек.

Если один из a или b становится 0, игрок, чей ход следующий, проигрывает игру. Поскольку и a, и b уменьшаются на 1 после каждого хода, min (a, b) становится 0 вначале. Итак, если min (a, b) нечетно, Ашиш выигрывает игру, в противном случае выигрывает Вивек.

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться