2008 Canadian Computing Competition, Day 1
Day 1, Problem 3: Mobile
Fred is a baby. Above Fred's crib hangs a mobile. Fred is amused by this mobile. Fred has a twin sister, Mary. Above Mary's crib hangs another mobile. Fred wonders whether the mobile above his crib and the mobile above Mary's crib are the same. Help Fred.
A mobile is a collection of bars, strings, and decorative weights suspended from the ceiling. Each bar is suspended by a string tied to the exact centre of the bar. From each end of a bar hangs a string that is tied either to another bar or to a weight. The bars can rotate freely about their centres. Fred cannot tell two bars apart, even if they have different lengths. Fred also cannot tell two strings apart. Fred therefore considers two mobiles to be the same if the bars of one mobile can be rotated somehow to make the two mobiles appear identical.
Fred has even developed a notation for describing mobiles. He assigns each bar a distinct positive integer from 1 to the number of bars in the mobile, and he assigns the various objects negative integers. 1 always represents the bar suspended from the ceiling. (So, for example, a biplane might be represented by Fred as object -2, a crescent-moon might be object -57, and a star might be object -21.) Fred can only count down to -9999, so you can assume that he gave no objects lower numbers than -9999.
The input contains two mobile descriptions. The first line of a mobile description contains a single nonnegative integer n (1 ≤ n ≤ 100000), indicating the number of bars in the mobile. On the next n lines, there are two numbers per line, with these two numbers representing the objects hanging from bar i.
Output is composed of one line. Write "Fred and Mary have different mobiles." if Fred's information is enough to distinguish the two mobiles; otherwise, "Fred and Mary might have the same mobile.".
5 2 3 4 5 -1 -2 -3 -4 -5 -6 5 2 5 -1 -2 -3 -4 -5 -6 3 4
Fred and Mary might have the same mobile.
Sample Input 2
5 2 3 4 5 -3 -4 -1 -2 -5 -6 5 2 5 -1 -2 -3 -4 -5 -6 3 4
Sample Output 2
Fred and Mary have different mobiles.
Half of all marks will have n ≤ 200. 75% of the marks will be from test cases with n ≤ 5000.
All test cases will have n ≤ 100000.
Your solution must use at most 1 second of CPU time and at most 512MB of memory.
Point Value: 17 (partial)
Time Limit: 1.00s
Memory Limit: 512M
Added: Dec 07, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3