7866.png
ЧЕЛЯБИНСК,ЮУРГУ,ИЕТН

Назад

images/home.png Начало
images/balloon.gif Соревнования
2010

Подразделы

Другие разделы

Дата и время

25/04/2024 23:49:55

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printРазбор задачи D. Загрузка реактора

Тема: полный перебор
Сложность: ниже среднего

12338.png
Для решения этой задачи нужно взять куб из блоков и отсечь от него все лишнее, как говорил Огюст Роден. Лишним в данном случае являются блоки в тех рядах, которые на соответствующих снимках обозначены символом '.'. Если какой-то блок не попадает ни на одном из снимков в пустой ряд, то этот блок нужно оставить, так как в задаче требуется определить максимально возможное количество блоков, находящихся в реакторе.
Нумерацию блоков в кубе будем делать в порядке, показанном на картинке. Стрелки указывают, в каком направлении будет возрастать соответствующий индекс в массиве.
var sn:array[1..3,1..20] of string; { снимки }
    bl:array[1..20,1..20,1..20] of boolean; { куб из блоков }
  i,j,k,kol,n:integer;
...
{ ввод данных }
  readln(n);
  for i:=1 to 3 do
    for j:=1 to n do
      readln(sn[i,j]);
{ заполнение куба }
  for i:=1 to n do
    for j:=1 to n do
      for k:=1 to n do
        bl[i,j,k]:=true;
{ отсечение лишнего }
  for i:=1 to n do
    for j:=1 to n do
      for k:=1 to n do
        if (sn[1,i][j]='.') or (sn[2,i][k]='.') or 
           (sn[3,n-k+1][j]='.') then
          bl[i,j,k]:=false;
После отсечения лишнего могут появиться пустые ряды, находящиеся на снимках в местах, обозначенных символом '#'. Для обнаружения таких новых пустых рядов отметим на снимках символом '+' ряды, в которых есть хотя один блок. Если после таких изменений на снимках останется хоть один символ '#', значит в этом ряду после удаления лишних блоков не осталось ни одного, и, следовательно, на снимках есть противоречия.
  kol:=0;
{ отметка символом '+' непустых рядов и подсчет числа блоков }
  for i:=1 to n do
    for j:=1 to n do
      for k:=1 to n do
        if bl[i,j,k] then
        begin
          sn[1,i][j]:='+';
          sn[2,i][k]:='+';
          sn[3,n-k+1][j]:='+';
          inc(kol);
        end;
{ поиск символов '#' на снимках }
  for i:=1 to 3 do
    for j:=1 to n do
      for k:=1 to n do
        if sn[i,j][k]='#' then
        begin
          writeln(-1);
          halt(0);
        end;
  writeln(kol);
loading