1. Homepage
  2. Programming
  3. Coin Puzzle

Coin Puzzle

Engage in a Conversation
Coin PuzzleC++

Coin Puzzle CourseNana.COM

Input file: Output file: Time limit: Memory limit: CourseNana.COM

standard input standard output 5 seconds
1024 megabytes

Juldys is exploring a dungeon. She has reached a mysterious room, where she finds n coins scattered on the floor, each with unique symbols on both sides. Juldys likes shiny things (and she particularly likes money) so she quickly picks up the coins. But as she collects the first coin, a heavy door slams down behind her, sealing her inside the room. CourseNana.COM

As she looks around, she sees runes glowing in red on the walls of the room, neatly organised into m rows each consisting of three runes. On closer inspection, she finds that each of the runes matches exactly one of the 2n coin faces! Note that the same rune can appear in several different rows, and that some coin faces may not appear at all. CourseNana.COM

She also finds a locked door at the far end of the room, with n circular indentations that perfectly fit the coins. When she puts a coin into any of the indentations, all rows containing the rune facing outwards stop glowing, but when the coin is removed they glow once again. CourseNana.COM

Juldys figures out that she will have to place all n coins in a way that makes all the runes stop glowing, and only then will the door be unlocked. Help her find a way to place the coins, or determine that she is doomed. CourseNana.COM

Input CourseNana.COM

The first line of input consists of two space-separated integers, n (3 n 22) and m (0 m 100), representing the number of coins and the number of rows of runes respectively. CourseNana.COM

m lines follow, the ith of which contains three space-separated integers, ri,1, ri,2 and ri,3, representing the runes in the ith row. Each ri,j is a nonzero integer between n and n inclusive, where a positive value k represents the “heads” side of coin k and a negative value k represents the “tails” side of coin k. You are guaranteed that no two runes in any row refer to the same coin, i.e. that no two of the three values in any row are equal in absolute value. CourseNana.COM

Output CourseNana.COM

If Juldys can unlock the door with some configuration of coins, output n space-separated letters, the ith of which is either H or T denoting which side of the ith coin should face up (heads or tails). There may be several correct solutions; any configuration of coins which stops all m rows glowing will be accepted. CourseNana.COM

If Juldys cannot unlock the door, output the word “Doomed” (without punctuation). CourseNana.COM

Examples CourseNana.COM

standard input standard output CourseNana.COM

35 123
1 -2 3 1 3 -2 -3 -1 2 123

38 312
3 -1 2
3 1 -2
3 -1 -2 2 1 -3 -2 1 -3 -1 2 -3 -1 -2 -3

For the sample cases, suppose the coins are as follows.
Coin Heads Tails

2cf 3iY CourseNana.COM

In sample case 1, there are five rows of runes:
Row Runes

4YSc CourseNana.COM

Placing just the second coin showing tails will stop the second and third rows glowing, as these are the rows containing f.
Placing the first coin showing heads and the other two showing tails will stop all rows glowing, as all rows

contain at least one out of three displayed runes X, fand Y. CourseNana.COM

Note that this is not the only valid solution; if all three coins show heads, then X, cand iagain account for all five rows. CourseNana.COM


In sample case 2, there are eight rows of runes, and no configuration of coins will account for all eight rows. CourseNana.COM

Get in Touch with Our Experts

Wechat WeChat
Whatsapp Whatsapp
Coin Puzzle代写,C++代写,Coin Puzzle代编,C++代编,Coin Puzzle代考,C++代考,Coin Puzzlehelp,C++help,Coin Puzzle作业代写,C++作业代写,Coin Puzzle编程代写,C++编程代写,Coin Puzzleprogramming help,C++programming help,Coin Puzzleassignment help,C++assignment help,Coin Puzzlesolution,C++solution,