/* Задача 2.1 КУБЧЕТА От 12 пръчки с равна дължина, всяка от които е оцветена с някакъв цвят трябва да се построи куб. Да се направи програма CUBE.EXE, която определя по колко различни начина може да бъде построен куба. Два куба се считат за еднакви, ако единият може да бъде завъртян и поставен до другия по такъв начин, че съответните ръбове да са еднакво оцветени. Входните данни са 12 цели положителни числа c1, c2, .., c12 – цветовете на дадените пръчки (1 <= c1 <= c2 <= ... <= c12 <= 6), които се въвеждат от един ред на стандартния вход. На стандартния изход да се изведе едно число – броя на различните кубове, които могат да се построят от дадените пръчки. РЕШЕНИЕ от Иван Анев Два куба са еднакви ако може единият да се завърти така, че съответните ръбове на двата куба да са напълно еднакви. Идеята на задачата е да се оцвети един куб по всички възможни начини и за всяко оцветяване, получения куб да се завърти по всички възможни начини и да се провери дали получения низ след някое завъртане не сме го броили вече. Сега ще опишем метода за реализация на всяка от стъпките. Генерирането на всички възможни оцветявания става като първия ръб го оцветим с всички възможни цветове и после оцветим останалите върхове по всички възможни начини с останалите цветове. Което на свой ред става като оцветим втория ръб с всеки от останалите цветове и после оцветим останалите ръбове по всички възможни начини с останалите цветове и така изпълняваме стъпката рекурсивно до достигане на последния ръб, за който е останал един цвят. Това генериране може да се ускори малко, като фиксираме цвета на първия ръб. Това е коректно, защото винаги съществува ръб с фиксирания цвят, и винаги може да го завъртим, така че този ръб да е в позиция едно. Тоест фиксирайки цвета на ръб едно, ние отстраняваме само кубове, който може да получим по друг начин, тоест не губим решения. Въртенето на един куб е пермутация на неговите ръбове. Един куб може да бъде поставен по 24 различни начина, тоест имаме 23 различни завъртания. Може да се направи една помощна програма, която ни дава 23 завъртяния във вид на пермутация или да ползваме 3-те основни завъртания и директно да генерираме 23 други. Как разбираме дали конкретен куб сме го броили вече. Всеки куб може да се представи като наредено множество от 12 числа, като всеки цвят (число) отговаря за един ръб (първия цвят за първия ръб, втория цвят за втория ръб и т.н.). Всеки куб попада в една група от 24 куба, в която чрез посочените трансформации (въртене) може да се стигне от всеки във всеки. Всеки от тези кубове се представа като наредена 12-ица от числа. Ние ще броим куба с най-малкото лексикографско представяне като наредена 12-ица числа. А именно, когато генерираме поредното оцветяване, ние ще приложим 23-те начина на завъртане и ако при някое завъртане получим куб с по-малко лексикографско представяне, няма да броим конкретното оцветяване. Ако за някое оцветяване, след прилагане на 23-те начина на въртене получаваме само кубове с по-големи лексикографски представяния, то ще знаем, че сегашното оцветяване е минимално лексикографско в своята група от 24 куба, и трябва да го преброим. Едно лексикографско представяне е по-малко от друго, ако първия цвят (число) на ръб, в който се различават двете представяния, номера на цвета на първия е по-малък от втория. */ /* NAME: Ivan Anev PROG: cube LANG: C++ */ #include <iostream> #include <cstring> using namespace std; int rs[3][12] = { {8, 5, 0, 4, 11, 9, 1, 3, 10, 6, 2, 7}, {1, 2, 3, 0, 5, 6, 7, 4, 9, 10, 11, 8}, {4, 3, 7, 11, 8, 0, 2, 10, 5, 1, 6, 9} }; class Cube { private: int cs[6], cb[12]; int ans; private: void gen(int l) { int i; if (l == 12) { if (check()) ans++; } else { for (i = 0; i < 6; i++) if (cs[i]) { cb[l] = i; cs[i]--; gen(l + 1); cs[i]++; } } } int check() { int r1, r2; int nc1[12], nc2[12], nc3[12]; memcpy(nc1, cb, sizeof(cb)); for (r1 = 0; r1 < 4; r1++) { rotate(nc2, nc1, 1); memcpy(nc1, nc2, sizeof(nc1)); for (r2 = 0; r2 < 4; r2++) { rotate(nc3, nc2, 0); memcpy(nc2, nc3, sizeof(nc2)); if (memcmp(cb, nc3, sizeof(cb)) > 0) return 0; } } memcpy(nc1, cb, sizeof(cb)); for (r1 = 0; r1 < 3; r1++) { rotate(nc2, nc1, 2); memcpy(nc1, nc2, sizeof(nc1)); if (r1 == 1) continue; for (r2 = 0; r2 < 4; r2++) { rotate(nc3, nc2, 0); memcpy(nc2, nc3, sizeof(nc2)); if (memcmp(cb, nc3, sizeof(cb)) > 0) return 0; } } return 1; } void rotate(int nc[], int cb[], int r) { int i; for (i = 0; i < 12; i++) nc[i] = cb[rs[r][i]]; } public: void solve() { int i, c; memset(cs, 0, sizeof(cs)); for (i = 0; i < 12; i++) { cin >> c; cs[c-1]++; } ans = 0; for (i = 0; cs[i] == 0; i++) ; cb[0] = i; cs[i]--; gen(1); cout << ans << '\n'; } }; Cube cube; int main() { cube.solve(); return 0; }