Коробка

Любая коробка определяется 3мя размерами: высотой, шириной и длиной. Пусть это значения A, B и C соответственно. В силу того, что все эти значения равноправны (коробку можно вращать), то мы можем полагать, что A <= B <= C. Так же ясно, что для того, чтобы построить коробку нужно иметь набор из трех пар плиток. Плитки в каждой паре идентичны и представляют собой плитки, не имеющие общих граней (противоположные). Причем должна быть возможность стыковать плитки из разных пар друг с другом.

Формализуем вышеописанную идею. Размеры каждой из коробок отсортируем по возрастанию, т.е. будем всегда считать например, что высота меньше либо равна ширине. После чего получившиеся наборы плиток мы можем отсортировать сначала по высоте, а затем (при равных высотах) по ширине. Таким образом, мы должны получить следующую последовательность:

   AB
   AB
   AC
   AC
   BC
   BC

Отсортировав плитки остается лишь проверить на равенство элементов в 3х четверках. Например, если в a[i].h хранится высота, а в a[i].w соответственно длина i-й коробки, то следует проверить на равенство следующие элементы: a[1].h=a[2].h=a[3].h=a[4].h и a[1].w=a[2].w=a[5].h=a[6].h и a[3].w=a[4].w=a[5].w=a[6].w . Такое решение не является самым оптимальным как по времени выполнения, так и по объему кода программы, но тем неменее оно более понятно.

Во входных данных мы имеем 12 чисел, некоторые из которых могут совпадать. Несложно понять, что в правильной коробке не может быть более 3х наборов различных размеров (это понятно так же из рассуждений в Решении №1). Пронумеруем всевозможные наборы размеров. Мы это можем делать сразу при чтении входных данных. В некоторой переменной C будем хранить количество различных размеров, а в массиве F[X] будет номер размера X или 0, если такого размера нет. Так же используем 2х-мерный массив G[i][j], где будет находиться количество плиток с номерами размеров i и j, для простоты, чтобы каждый раз не вращать плитки следует сделать так, чтобы G[i][j]=G[j][i]. Определить значение C и заполнить вышеописанные массивы возможно в одном цикле, сразу при чтении данных.

Теперь для определения возможности построения коробки достаточно знать ранее вычисленные значения C и G. Здесь нужно рассмотреть все случаи, которые могут быть в зависимости от количества разных размеров C:

C=1. Это означает, что все размеры одинаковые, т.е. все плитки представляют из себя равные квадраты и мы можем построить из них коробку в форме куба. Заметим так же, что в этом случае определено только G[1][1], которое равно 12 (это даже можно не проверять).

C=2. В этом случае для возможности построения коробки мы должны иметь 2 одинаковых квадратных плитки и 4 одинаковых прямоугольных, для чего необходимо проверить, что G[1][2]=4 и либо G[1][1]=2 либо G[2][2]=2 (один из размеров дает две плитки, а другой 0).

C=3. Здесь мы имеем случай, когда все размеры (высота, ширина и длина) различны. Тут для возможности построения коробки необходимо убедиться в том, что при этом получаются ровно по 2 одинаковых плитки для всевозможных G[i][j], 1 <= i,j <= 3. Иначе говоря, должно получаться G[1][2]=G[1][3]=G[2][3]=2.

C>3. При таком варианте, как уже говорилось ранее, мы не можем в любом случае построить коробку.

[Все попытки] [Задача]