Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Судоку

(Время: 1 сек. Память: 16 Мб Сложность: 27%)

Эта задача сводится к задаче, в которой необходимо определить: является ли представленный набор k чисел таковым, что он состоит из множества разных чисел от 1 до k (в нашем случае k=n2). С одной стороны, можно было бы отсортировать этот набор чисел и проверить: в полученном массиве равно ли значение элемента его номеру. Этот метод прошел бы в силу того, что ограничения невелики, однако, этот способ неэффективен и сложнее по реализации, чем следующий. Мы можем определить некоторый массив d[1..k] (в нашем случае лучше описать такой массив из 100 элементов, независимо от n), заполнив его предварительно нулями. В процессе перебора всех чисел представленного набора элементов для каждого числа x будем выполнять присваивание d[x]=1, которое обеспечит факт присутствия числа x в списке. По окончании этой операции достаточно будет проверить все элементы массива d от 1 до k: если встретился хотя бы 1 ноль, то условие не выполнено, иначе все верно.

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

  for i=1..n{
    for j=1..n{
      d[1..100]={0..0};
      for y=(i-1)*n+1 .. i*n{
        for x=(j-1)*n+1 .. j*n{
          d[a[y][x]]=1;
        }    
      }
      Check(d);
    }
  }

[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru