首页 > 试题广场 >

多多的骰子组合

[编程题]多多的骰子组合
  • 热度指数：1687 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
多多君拼团购买了N个骰子，为了方便后面进行活动，多多君需要将这些骰子进行分类。



两个骰子为同类的定义是： 
将其中一个骰子通过若干次上下、左右或前后翻转后，其与另一个骰子对应的6面数字均相等。

现在多多君想知道不同种类的骰子的数量分别有多少。

输入描述:
第一行1个整数N，表示骰子的数量。
（1 <= N <= 1,000）
接下来N行，每行6个数字（1～6，且各不相同）
其中第i行表示第i个骰子当前上、下、左、右、前、后这6面的数字。


输出描述:
共2行:
第一行1个整数M，表示不同种类的骰子的个数
第二行M个整数，由大到小排序，表示每个种类的骰子的数量
示例1

输入

2
1 2 3 4 5 6
1 2 6 5 3 4

输出

1
2

说明

第二个骰子相当于是第一个骰子从左向右旋转了一面得到，属于同类。
示例2

输入

3
1 2 3 4 5 6
1 2 6 5 3 4
1 2 3 4 6 5

输出

2
2 1

说明

第三个骰子无法通过任何旋转变换成第一个或第二个骰子。
示例3

输入

10
2 5 1 3 4 6
5 4 3 2 1 6
1 4 6 2 3 5
1 5 6 3 4 2
6 4 2 1 5 3
3 6 4 5 2 1
1 6 3 4 2 5
5 1 4 2 6 3
6 2 3 1 5 4
5 3 6 1 4 2

输出

9
2 1 1 1 1 1 1 1 1

说明

只有第4个骰子(1 5 6 3 4 2)与第8个骰子(5 1 4 2 6 3)属于同一类。

一种可能的变换方式:
1) 首先从右向左翻转1次
 (1 5 6 3 4 2) -> (1 5 4 2 3 6)
2) 然后从上向下翻转2次
 (1 5 4 2 3 6) -> (6 3 4 2 1 5) -> (5 1 4 2 6 3)

备注:
对于50%的数据，有： 1 <= N <= 50
对于100%的数据，有：1 <= N <= 1,000
算法知识视频讲解
添加回答
Python
Bayes305头像 Bayes305
Python3 
class dice():
    def __init__(self, a):
        self.a=a
    def switch_out(self,i,j):
        if i!=j:
            self.a[2*i], self.a[2*i+1], self.a[2*j], self.a[2*j+1] = \
            self.a[2*j], self.a[2*j+1], self.a[2*i+1], self.a[2*i]
    def switch_in(self,i):
        if self.a[2*i]>self.a[2*i+1]:
            self.a[2*i], self.a[2*i+1] = self.a[2*i+1], self.a[2*i]
            self.a[2*i+2], self.a[2*i+3] = self.a[2*i+3], self.a[2*i+2]
    def tidy(self):
        i1=self.a.index(1)//2
        self.switch_out(0, i1)
        self.switch_in(0)
        i2=self.a.index(min(self.a[2:]))//2
        self.switch_out(1, i2)
        self.switch_in(1)
        return tuple(self.a)
n=int(input())
dc={}
for i in range(n):
    nd=dice(list(map(int, input().split()))).tidy()
    dc[nd]=dc.get(nd, 0)+1
print(len(dc.keys()))
for v in sorted(dc.values(), reverse=True):
    print(v, end=" ")


发表于 2021-10-29 07:48:42 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 拼多多集团-PDD 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
1条回答 8964浏览

热门推荐

通过挑战的用户

相关试题

多多的骰子组合

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号