Given the number of animals and the required distance pairs of certain animals, write a program that prints a satisfying solution or informs the user that there is none if a solution does not exist.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Story

The animals are still making too much noise. Some animals antagonize nearby animals and cause them to emit screams of rage or cries of annoyance. However, some animals want to be nearby other particular animals or they emit cries of longing. You have experimented with different animals at different distances from each other. You have made some notes, and to make your life easier you have represented each animal with a unique natural number index. Now you feel that you now have enough information to move forward with your new plans.

The animals will be in a line of exhibits. Each animal will be in its own exhibit, and there are an equal number of animals as exhibits. You have found that certain pairs of animals need to be exactly some distance from each other. You want to find out if there is an arrangement of animals that satisfies all the required distances.

Problem

Given the number of animals and the required distance pairs of certain animals, write a program that prints a satisfying solution or informs the user that there is none if a solution does not exist.

Input

Input will begin with a line containing 2 integers, n and c (1 ≤ n ≤ 20; 0 ≤ c ≤ n choose 2), representing the number of animal exhibits and the number of constraints. The following c lines will each contain a constraint description in the form of 3 space separated integers, f, s, and d (1 ≤ f, s ≤ n; f ≠ s; 0 ≤ c ≤ n - 2), representing the index of the first animal, the index of the second animal, and the exact number of cages that should be in between those 2 animals.

 

For 7 of the 10 cases each animal will be in at most 1 constraint.

Output

Output should contain 1 line. In the event that a solution exists, you should print out n space separated integers representing the animal index given in order from the first cage to the last. If there is no solution the output should be only the phrase “No Solution.” (quotes for clarity).

 

Attachments:

Expert's Answer

511 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of