Игра "Бинго"

@Solomina · Регистрация: 09.12.2018

Студворк — интернет-сервис помощи студентам

Вот пример моего решения, которое успешно не проходит ограничение по времени.

Помогите составить эффективный алгоритм.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <algorithm>
#include <iostream>
 
using namespace std;
 
 
int getMax(int **arr, int r, int d, bool col = false)
{
    int res = 0;
    for (int i = 0; i < d; i++)
        res = max(col ? arr[i][r] : arr[r][i], res);
 
    return res;
}
 
int main()
{
    int n, m, q, k;
    cin >> n >> m >> q >> k;
 
    int **table = new int *[n];
    int *maxRows = new int[n];
    int *maxCols = new int[m];
    for (int i = 0; i < m; i++)
        maxCols[i] = 0;
 
    int minV = k + 1;
 
    for (int r = 0; r < n; r++)
    {
        table[r] = new int[m];
        int maxV = 0;
        for (int c = 0; c < m; c++)
        {
            int v;
            cin >> v;
 
            table[r][c] = v;
            maxCols[c] = max(maxCols[c], v);
            maxV = max(maxV, v);
        }
        minV = min(minV, maxV);
        maxRows[r] = maxV;
    }
 
    for (int i = 0; i < m; i++)
        minV = min(maxCols[i], minV);
 
    for (int i = 0; i < q; i++)
    {
        int x;
        int y;
        cin >> x >> y;
        x--;
        y--;
 
        int prev = table[x][y];
        table[x][y] = 0;
 
        if (maxRows[x] == prev)
            maxRows[x] = getMax(table, x, m);
        if (maxCols[y] == prev)
            maxCols[y] = getMax(table, y, n, true);
 
        minV = min(minV, min(maxRows[x], maxCols[y]));
 
        cout << minV << endl;
    }
 
    return 0;
}

@zss · 09.12.2018, 18:38

Комментарий модератора

П.5.18.Правил
Запрещено размещать задания и решения в виде картинок и других файлов с их текстом.
Перепишите условие в тему

@Solomina · 09.12.2018, 19:32 **[ТС]**

C. Бинго!
Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ

«Бинго» — старинная игра с множеством разновидностей. В данной задаче вы познакомитесь с одной из них.
Карточка для игры в «Бинго» представляет собой прямоугольное поле n × m, заполненное числами от 1 до k. Ведущий проводит q раундов, на каждом из которых закрашивается ровно одна ранее не закрашенная клетка. Игрок считается победителем, если на его карточке образуется вертикальная или горизонтальная линия, полностью состоящая из закрашенных клеток.
Чтобы сделать процесс немного интереснее, ведущий один раз за игру разрешает игроку закрасить произвольный набор клеток. При этом игрок должен заплатить ведущему сумму, равную максимальному из чисел, написанных на клетках выбранного набора.
После каждого раунда определите, какую минимальную сумму игрок должен заплатить ведущему, чтобы выиграть в «Бинго» к данному раунду. Если после раунда игрок уже является победителем, то ведущему можно ничего не платить и минимальная сумма равна нулю.

Исходные данные
В первой строке ввода даны целые числа, разделённые пробелом: n, m, q, k (1 ≤ n, m ≤ 105, 1 ≤ n · m ≤ 2 · 105, 1 ≤ q ≤ min(105, n · m), 1 ≤ k ≤ 109) — размер игрового билета, количество раундов и ограничение на величину числа в игровой клетке. Далее следует описание игрового поля: таблица, дано n строк и m столбцов. Числа в каждой строке разделены пробелом. Каждое число натуральное и не превышает k.

Далее следуют q строк описания запросов на закрашивание клеток. В каждой строке даны 2 числа ri и ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m) — координаты строки и столбца закрашиваемой клетки. Гарантируется, что никакая клетка не закрашивается дважды.

Результат
Для каждого раунда выведите в отдельной строке минимальную сумму, которую игрок должен заплатить ведущему.

Пример
исходные данные:
3 3 4 5
1 3 2
3 3 4
4 5 2
3 1
3 2
2 1
1 1
результат:
3
2
1
0

@Solomina · 10.12.2018, 10:16 **[ТС]**

Еще актуально

@holykatty · 11.12.2018, 16:56

Та же проблема.

Новые блоги и статьи Все статьи Все блоги /
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Solomina 0 / 0 / 0 Регистрация: 09.12.2018 Сообщений: 4
	09.12.2018, 19:32 [ТС]
	C. Бинго! Ограничение времени: 2.0 секунды Ограничение памяти: 256 МБ «Бинго» — старинная игра с множеством разновидностей. В данной задаче вы познакомитесь с одной из них. Карточка для игры в «Бинго» представляет собой прямоугольное поле n × m, заполненное числами от 1 до k. Ведущий проводит q раундов, на каждом из которых закрашивается ровно одна ранее не закрашенная клетка. Игрок считается победителем, если на его карточке образуется вертикальная или горизонтальная линия, полностью состоящая из закрашенных клеток. Чтобы сделать процесс немного интереснее, ведущий один раз за игру разрешает игроку закрасить произвольный набор клеток. При этом игрок должен заплатить ведущему сумму, равную максимальному из чисел, написанных на клетках выбранного набора. После каждого раунда определите, какую минимальную сумму игрок должен заплатить ведущему, чтобы выиграть в «Бинго» к данному раунду. Если после раунда игрок уже является победителем, то ведущему можно ничего не платить и минимальная сумма равна нулю. Исходные данные В первой строке ввода даны целые числа, разделённые пробелом: n, m, q, k (1 ≤ n, m ≤ 105, 1 ≤ n · m ≤ 2 · 105, 1 ≤ q ≤ min(105, n · m), 1 ≤ k ≤ 109) — размер игрового билета, количество раундов и ограничение на величину числа в игровой клетке. Далее следует описание игрового поля: таблица, дано n строк и m столбцов. Числа в каждой строке разделены пробелом. Каждое число натуральное и не превышает k. Далее следуют q строк описания запросов на закрашивание клеток. В каждой строке даны 2 числа ri и ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m) — координаты строки и столбца закрашиваемой клетки. Гарантируется, что никакая клетка не закрашивается дважды. Результат Для каждого раунда выведите в отдельной строке минимальную сумму, которую игрок должен заплатить ведущему. Пример исходные данные: 3 3 4 5 1 3 2 3 3 4 4 5 2 3 1 3 2 2 1 1 1 результат: 3 2 1 0 0

@Solomina 0 / 0 / 0 Регистрация: 09.12.2018 Сообщений: 4
	10.12.2018, 10:16 [ТС]
	Еще актуально 0

@holykatty 0 / 0 / 0 Регистрация: 11.12.2018 Сообщений: 1
	11.12.2018, 16:56
	Та же проблема. 0