1015. Test the Difference!
Time Limit: 2.0 second
Memory Limit: 16 MB
There are N (1 ≤ N ≤ 105)
dice at the casino’s "Royal Flush" storehouse. Some of them are equal,
i.e. one can transform one die to another by properly rotating it.
Let’s say that two dice have the same scheme if it’s possible to obtain
one of them from another by a series of rotation. In other case (no
rotations of the first die lead us to the second die) let’s say that
dice have different schemes. Your task is to define the dice with the
same scheme.
Input
The first line of the input contains the number N. Next N
lines contain descriptions of the dice. Each line contains exactly one
description of the die. A line describes the die in 6 numbers
(separated with spaces): the number of points on the left side of the
die, then on the right side, on the top, on the forward side, on the
bottom and on the backward side. Certainly, those 6 numbers represent a
permutation of integer numbers from 1 to 6 inclusively.
Output
The first line of the output should contain the only number Q of different die’s schemes at the storehouse. Next Q
lines should contain the numbers of dice with the same scheme. To be
more precisely the second line must begin with 1 and after that
(separated by spaces) numbers of dice with the same as die #1 scheme
must follow. We assume that all dice from the input are numbered from 1
to N.
The third line (if not all the dice have the same scheme) must begin
with the smallest possible number with the scheme different from the
scheme of the die #1. This number (say P) is followed by numbers of dice with the same scheme as the scheme of the die #P. All next lines must be printed in the same manner. Numbers in each line of the output must be sorted in increasing order.
Sample
| input | output |
|---|---|
|
3 1 2 6 4 5 3 4 3 6 2 5 1 4 1 3 6 2 5 |
2 1 2 3 |
Problem Source: Ural State University Internal Contest '99 #2
答案如下：
2 using System.IO;
3 using System.Collections.Generic;
4
5 namespace Skyiv.Ben.Timus
6 {
7 // http://acm.timus.ru/problem.aspx?space=1&num=1015
8 class T1015
9 {
10 static void Main()
11 {
12 new T1015().Run(Console.In, Console.Out);
13 }
14
15 void Run(TextReader reader, TextWriter writer)
16 {
17 List<int> sort = new List<int>(30);
18 List<int>[] dice = new List<int>[30];
19 Dictionary<int, short> dict = GetDict();
20 for (int n = int.Parse(reader.ReadLine()), i = 1; i <= n; i++)
21 {
22 int q = dict[int.Parse(reader.ReadLine().Replace(" ", null))];
23 if (dice[q] == null)
24 {
25 dice[q] = new List<int>();
26 sort.Add(q);
27 }
28 dice[q].Add(i);
29 }
30 writer.WriteLine(sort.Count);
31 foreach (int q in sort)
32 {
33 foreach (int d in dice[q]) writer.Write(d + " ");
34 writer.WriteLine();
35 }
36 }
37
38 Dictionary<int, short> GetDict()
39 {
40 int[] qs =
41 {
42 123456, 123465, 123546, 123564, 123645, 123654,
43 132456, 132465, 132546, 132564, 132645, 132654,
44 142356, 142365, 142536, 142563, 142635, 142653,
45 152346, 152364, 152436, 152463, 152634, 152643,
46 162345, 162354, 162435, 162453, 162534, 162543
47 };
48 Dictionary<int, short> dict = new Dictionary<int, short>(720);
49 for (int x = 0; x < 2; x++)
50 for (int y = 0; y < 4; y++)
51 {
52 if (x == 1 && (y == 1 || y == 3)) continue;
53 for (int z = 0; z < 4; z++)
54 for (short q = 0; q < qs.Length; q++)
55 dict.Add(Rotation(qs[q], x, y, z), q);
56 }
57 return dict;
58 }
59
60 int Rotation(int die, int x, int y, int z)
61 {
62 for (int i = 0; i < x; i++) die = Rotation(die, 2, 3, 4, 5);
63 for (int i = 0; i < y; i++) die = Rotation(die, 0, 2, 1, 4);
64 for (int i = 0; i < z; i++) die = Rotation(die, 0, 3, 1, 5);
65 return die;
66 }
67
68 int Rotation(int die, params int[] p)
69 {
70 char[] s = die.ToString("D6").ToCharArray();
71 char tmp = s[p[0]];
72 s[p[0]] = s[p[1]];
73 s[p[1]] = s[p[2]];
74 s[p[2]] = s[p[3]];
75 s[p[3]] = tmp;
76 return int.Parse(new string(s));
77 }
78 }
79 }
在本题中，总共可能有 6! = 720 种不同的输入，它们可归类到 30 种不同的骰子，每种骰子对应 24 种不同的输入。本程序中第 38 到 58 行的 GetDict() 方法就是用来将这 720 种不同的输入分为 30 种不同的骰子。变量 Dictionary<int, short> dict 的 Key 刚好遍历这 720 种不同的输入， 其 Value 的取值范围 为 0 到 29，代表 30 种不同的骰子。