Форум программистов, компьютерный форум CyberForum.ru

Разобраться в задаче с Codeforce - C++

Восстановить пароль Регистрация
 
PG94
2 / 2 / 0
Регистрация: 15.01.2012
Сообщений: 181
18.08.2012, 11:36     Разобраться в задаче с Codeforce #1
Вот условие(Задача 203B):
В один не самый прекрасный вечер Валере было очень скучно. Чтобы немного себя развлечь, Валера нашел следующее занятие.Он взял белый квадратный клетчатый лист бумаги, состоящий из n × n клеток. После этого он стал закрашивать белые клетки листа одну за другой в черный цвет. Всего он закрасил m различных клеток этого листа. Поскольку у Валеры была какая-то предрасположенность ко всему квадратному, его заинтересовал следующий вопрос — после какого хода впервые на листке можно найти черный квадрат со стороной 3. Однако Валера не знает ответ на этот вопрос и поэтому просит Вашей помощи.
От Вас требуется найти минимальный номер хода, после которого на клетчатом листке образовался хотя бы один квадрат черного цвета со стороной 3 или определить, что такого хода нет.
Входные данные
В первой строке задано два целых числа n и m (1 ≤ n ≤ 1000, 1 ≤ m ≤ min(n· n, 105)) — размер клетчатого листа и количество ходов соответственно.
Далее в m строках задано описание ходов. В i-ой строке находятся два числа xi, yi (1 ≤ xi, yi ≤ n) — номер строки и номер столбца, в котором находится клетка, закрашиваемая на i-ом ходе.
Все числа в строках разделены единичными пробелами. Гарантируется, что все ходы различны. Ходы нумеруются, начиная с 1, в том порядке, в котором они заданы во входных данных. Столбцы клетчатого листа бумаги нумеруются, начиная с 1, слева направо. Строки клетчатого листа бумаги нумеруются, начиная с 1, сверху вниз.
Выходные данные
В единственной строке выведите ответ на задачу — минимальный номер хода, после которого на листе образуется черный квадрат со стороной 3. Если такого хода не существует, выведите -1.
И вот верное решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<conio.h>
using namespace std;
int n,m,x,y,a[1005][1005]={0},i,l,r;
int main()
{   cin>>n>>m;
    for(i=1;i<=m;i++)
    {   cin>>x>>y;
        for(l=x;l<x+3;l++)
        {   for(r=y;r<y+3;r++)
            {   a[l][r]++;
                if(a[l][r]==9)
                {   cout<<i;
                    getch();
                    return 0;
                }
            }
        }
    }
cout<<-1;
getch();
return 0;
}
Самому задачу решить не получилось, но и логика данного кода мне не очень понятна(т.е. почему такие действия дают верный ответ). Буду очень благодарен, если кто-нибудь пояснит приведённое решение.Точнее подход к решению, т.к. сам по себе код и действия, выполняемые программой, мне понятны.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.08.2012, 11:36     Разобраться в задаче с Codeforce
Посмотрите здесь:

комметарии к задаче C++
C++ Codeforce. Такси.
C++ Не могу разобраться в задаче
Crash в задаче с тимуса C++
C++ ошибка в задаче на палиндром
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
cmath
Модератор
 Аватар для cmath
2415 / 1634 / 132
Регистрация: 11.08.2012
Сообщений: 3,252
Завершенные тесты: 5
18.08.2012, 13:03     Разобраться в задаче с Codeforce #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<conio.h>
using namespace std;
int n,m,x,y,a[1005][1005]={0},i,l,r;
int main()
{   cin>>n>>m;
    for(i=1;i<=m;i++)
    {   cin>>x>>y;
        for(l=x;l<x+3;l++)
        {   for(r=y;r<y+3;r++)
            {   a[l][r]++;
                if(a[l][r]==9)
                {   cout<<i;
                    getch();
                    return 0;
                }
            }
        }
    }
cout<<-1;
getch();
return 0;
}
for(l=x;l<x+3;l++) for(r=y;r<y+3;r++) здесь весьма хитрая часть кода. Здесь программа увеличивает на единицу элементы квадратного блока в матрице 3х3 (естественно, при инициализации матрицу обнулили). Положим у нас есть множество блоков-секторов - матрицы размерностью 3х3 (квадратные блоки). Они могут перекрыватся: в этом случае элементы блока (где блоки "заползают" друг на друга) отличны от единицы во столько раз, скольким блокам одновременно принадлежат (за этим и увеличиваем их на единицу). А теперь попробуйте представить 9 таких перекрывающихся блоков (верхний левый элемент указывает на совершенный ход), впрочем, лучше нарисуйте на клетчатом листе бумаги эти блоки, в каждом из которых есть элемент, равный девяти и закрасьте все верхние левые углы этих блоков. Думаю после этого вы поймете в чем соль.
PG94
2 / 2 / 0
Регистрация: 15.01.2012
Сообщений: 181
18.08.2012, 15:39  [ТС]     Разобраться в задаче с Codeforce #3
Спасибо за ответ, хотя до сих пор идея остаётся неясной.
Понятно, что возможны перекрывающиеся блоки, но почему именно такая закономерность? И отчего после одного хода на 1 увеличиваются элементы только одного блока(в моём представлении элемент может принадлежать намного большему кол-ву незавершённых квадратов)? Может есть какое-то правило(напр. из математики), объясняющее исп. данной закономерности или же решение основано на обычной сообразительности?
cmath
Модератор
 Аватар для cmath
2415 / 1634 / 132
Регистрация: 11.08.2012
Сообщений: 3,252
Завершенные тесты: 5
18.08.2012, 16:16     Разобраться в задаче с Codeforce #4
Цитата Сообщение от PG94 Посмотреть сообщение
(в моём представлении элемент может принадлежать намного большему кол-ву незавершённых квадратов
Дело не в незавершенных квадратах, а в завершенных. Если вы последуете моему совету и нарисуете на листе блоки, то поймете, что 9-тка может быть только в районе завершенного квадрата не иначе

Добавлено через 4 минуты
Цитата Сообщение от PG94 Посмотреть сообщение
напр. из математики
Скорее логически прийти к ответу, в математике разбираюсь но не эксперт. Может и есть раздел, занимающийся подобными вопросами, но я о нем не слышал (повторюсь я не эксперт, могу быть не компетентен относительно существования/несуществования каких-нибудь разделов, могу лишь сказать, какие есть точно, ...или посмотреть в википедии)
Yandex
Объявления
18.08.2012, 16:16     Разобраться в задаче с Codeforce
Ответ Создать тему
Опции темы

Текущее время: 17:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru