The Fungus Republic had been a peaceful place thanks to the brave deeds of the humble electrician, Maria, but this all changed when her arch-nemesis Wowser invaded. Wowser kidnapped Prince Nectarine (again) and hid him somewhere he thought Maria would never find.
Maria was undaunted, however, and using the signal from Nectarine's mushroom phone was able to narrow down his location to one of N castles. The castles are arranged in a line and are numbered from 0 to N-1 where castle 0 is the leftmost castle, castle 1 is second from the left, etc.
Maria is very hasty about finding the prince, so she has rented a carriage to be pulled by Shoyi the friendly dinosaur. Whenever Maria wants to get out of the carriage or change direction, she must pay Shoyi a tip.
Maria begins at castle 0, facing to the right. When Maria is at castle i, she can do one of three things.
Maria wants to minimise the total number of coins she spends in finding the prince. Maria whips out her trusty laptop and sends you an e-mail, asking you to write a program to help find the prince while minimising the total number of coins she pays Shoyi.
This task has no input or output files. Instead it must use functions from the header file "carriage_lib.h" to gain information. These provided functions are described in detail on the next page.
Your program must interact with functions in "carriage_lib.h", as follows:
The signatures for these functions in C and are as follows:
int carriage_nb_cells(); int carriage_reverse_cost(); int carriage_open_cost(); void carriage_move(int k); int carriage_open();
In order to experiment with your code on your own machine, first download carriage_lib.h to the same folder as your code file and add #include "carriage_lib.h" to the top of your code.
The compiled executable will take four whitespace-separated integers from standard input on the first call to a provided function from the header file. The integers should represent, respectively, N, C1, C2 and p where the castle with index p (between 0 and N-1) contains Prince Nectarine.
The executable will print one line to standard output, either an error message due to invalid input or an invalid move, or an indication of success including the number of coins used.
10 3 4 7
|carriage_nb_cells()||Returns 10, the number of castles.|
|carriage_reverse_cost()||Returns 3, the cost of changing direction.|
|carriage_open_cost()||Returns 4, the cost of opening a castle door.|
|carriage_move(5)||Moves to castle 5, at no cost.|
|carriage_open()||Returns 1, as the Prince is in castle 7, to the right of castle 5. This costs 4 coins.|
|carriage_move(4)||Moves to castle 9, at no cost.|
|carriage_open()||Returns -1, as the Prince is in castle 7, to the left of castle 9. This costs 4 coins.|
|carriage_move(-3)||Moves to castle 6. This costs 3 coins, as it involved a change in direction.|
|carriage_open()||Returns 1, as the Prince is in castle 7, to the right of castle 6. This costs 4 coins.|
|carriage_move(1)||Moves to castle 7. This costs 3 coins, as it involved a change in direction.|
|carriage_open()||Finds the prince! This costs 4 coins. The program outputs that the prince has been found with the use of 22 coins and exits.|