题目 3037

「Snowflake Snow Snowflakes」 雪花雪花雪花

查看题解 ↗GitHub ↗如何评测
题号
3037
时间限制
1000 ms
内存限制
128 MB
标签
哈希最小表示法数据结构

有N片雪花,每片雪花由六个角组成,每个角都有长度。

第i片雪花六个角的长度从某个角开始顺时针依次记为ai,1,ai,2,…,ai,6a_{i,1},a_{i,2},\dots,a_{i,6}。

因为雪花的形状是封闭的环形,所以从任何一个角开始顺时针或逆时针往后记录长度,得到的六元组都代表形状相同的雪花。

例如ai,1,ai,2,…,ai,6a_{i,1},a_{i,2},\dots,a_{i,6}和ai,2,ai,3,…,ai,6,ai,1a_{i,2},a_{i,3},\dots,a_{i,6},a_{i,1}就是形状相同的雪花。

ai,1,ai,2,…,ai,6a_{i,1},a_{i,2},\dots,a_{i,6}和ai,6,ai,5,…,ai,1a_{i,6},a_{i,5},\dots,a_{i,1}也是形状相同的雪花。

我们称两片雪花形状相同,当且仅当它们各自从某一角开始顺时针或逆时针记录长度,能得到两个相同的六元组。

求这N片雪花中是否存在两片形状相同的雪花。

输入格式

第一行输入一个整数N,代表雪花的数量。

接下来N行,每行描述一片雪花。

每行包含6个整数,分别代表雪花的六个角的长度(这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到)。

同行数值之间,用空格隔开。

输出格式

如果不存在两片形状相同的雪花,则输出:

No two snowflakes are alike.

如果存在两片形状相同的雪花,则输出:

Twin snowflakes found.

数据范围

1≤n≤1000001 \le n \le 100000,
0≤ai,j<100000000 \le a_{i,j} <10000000

输入样例:

文本
2
1 2 3 4 5 6
4 3 2 1 6 5

输出样例:

文本
Twin snowflakes found.

来源

  • 《算法竞赛进阶指南》
  • acwing 可能含有视频讲解

数据下载

题目 3037 的公开数据

正在读取文件列表…

常用命令

题目 3037 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。