In Phase1, the execution happens within the group and this phase of execution for a group gistops when the total number of soldiers for the group reduced to a threshold thi (thithey will start the...

In Phase1, the execution happens within the group and this phase of execution for a group gistops when the total number of soldiers for the group reduced to a threshold thi (thithey will start the executing process. The counting out begins from the first soldier in the circleof the group and proceeds around the circle in a fixed direction. In each step, a certain number ofpeople ki-1 (ki > 0) are skipped and the next person is executed. The elimination proceeds aroundthe circle, which is becoming smaller and smaller as the executed people are removed. Asmentioned, the execution process for the group gi will stop when the group has thi number ofsoldiers.In summary, for a group gi, you have the total number of soldiers ni (ni =2), and a number ki (ki >0), which indicates that ki-1 persons are skipped and kith person is killed in circle. There is athreshold thi (thigroup reduced to thi. The same process should be applied to all the groups according to their ownn, k and th. The remaining soldiers will be transferred to phase 2.


Problem: Who Will Survive? Before starting to read the problem, consider it like a game and there is no relation of the problem with reality. This is just to practice some problem-solving strategies. Horror Kingdom has trapped G (G ≤ 10) groups of soldiers of their opponent. They want to execute them. They found out a strategy so that the prisoners will kill each other and at the end one prisoner will be alive and he will be released. The kingdom has 10 execution grounds one after another. Each ground has a ground number and a name. The grounds are numbered with a sequence number starting from 1 to 10. As part of the strategy, each group is placed to an execution ground. The groups are numbered based on the assigned execution ground number. Note that G is assumed to be less than or equal to 10 and as a result some grounds could be empty. Each group gi has ni (ni ≥2) number of prisoners. As part of the process, they labeled each prisoner of a group with a sequence number starting from 1 and ending at ni. All the ni number of prisoners of group gi are standing in a circle and waiting to be executed. However, due to distraction it was found out that all prisoners in all the groups were standing in reverse order instead of proper order like the following picture (let us say prisoners count of a group is 7): 7 -> 6-> 5-> 4 -> 3 -> 2-> 1 After realizing the wrong order of sequence, they reversed the circle to the correct order (note that they have not just changed their labels, they have physically changed their order) : 1 ->2-> 3-> 4 -> 5 -> 6-> 7 The execution process is divided into two phases. Phase1 Execution: In Phase1, the execution happens within the group and this phase of execution for a group gi stops when the total number of soldiers for the group reduced to a threshold thi (thi 0) are skipped and the next person is executed. The elimination proceeds around the circle, which is becoming smaller and smaller as the executed people are removed. As mentioned, the execution process for the group gi will stop when the group has thi number of soldiers. In summary, for a group gi, you have the total number of soldiers ni (ni ≥2), and a number ki (ki > 0), which indicates that ki-1 persons are skipped and kith person is killed in circle. There is a threshold thi (thi ki > 0) and then the next integer indicates the value of thi (ni>thi >0) integer. Output Specification: The output has to be written to out.txt file as well as to the console with the exact same format specified by the sample output bellow. The output mainly contains the simulation steps and the last line will contain survived soldier number with the group number. Sample input: 5 4 jubei 7 3 3 6 ukyo 5 2 3 1 samurai 10 3 2 7 haohmaru 9 2 4 3 galford 8 2 1 Sample output: Initial nonempty lists status 1 samurai 10 9 8 7 6 5 4 3 2 1 3 galford 8 7 6 5 4 3 2 1 4 jubei 7 6 5 4 3 2 1 6 ukyo 5 4 3 2 1 7 haohmaru 9 8 7 6 5 4 3 2 1 After ordering nonempty lists status 1 samurai 1 2 3 4 5 6 7 8 9 10 3 galford 1 2 3 4 5 6 7 8 4 jubei 1 2 3 4 5 6 7 6 ukyo 1 2 3 4 5 7 haohmaru 1 2 3 4 5 6 7 8 9 Phase1 execution Line# 1 samurai Soldier# 3 executed Soldier# 6 executed Soldier# 9 executed Soldier# 2 executed Soldier# 7 executed Soldier# 1 executed Soldier# 8 executed Soldier# 5 executed Line#3 galford Soldier# 2 executed Soldier# 4 executed Soldier# 6 executed Soldier# 8 executed Soldier# 3 executed Soldier# 7 executed Soldier# 5 executed Line# 4 jubei Soldier# 3 executed Soldier# 6 executed Soldier# 2 executed Soldier# 7 executed Line# 6 ukyo Soldier# 2 executed Soldier# 4 executed Line# 7 haohmaru Soldier# 2 executed Soldier# 4 executed Soldier# 6 executed Soldier# 8 executed Soldier# 1 executed Phase2 execution Executed Soldier 4 from line 1 Executed Soldier 10 from line 1 Executed Soldier 3 from line 7 Executed Soldier 5 from line 7 Executed Soldier 7 from line 7 Executed Soldier 9 from line 7 Executed Soldier 1 from line 3 Executed Soldier 1 from line 4 Executed Soldier 4 from line 4 Executed Soldier 5 from line 4 Executed Soldier 1 from line 6 Executed Soldier 3 from line 6 Soldier 5 from line 6 will survive Implementation Restrictions: a) You must have to use linked list and queue in your implementation. b) You must have to use circular singly linked list for your solution to get full credit. You need to declare appropriate linked list node structure to store a soldier with sequence number as the data value. c) You have to use linked list implementation of queue. d) Create a node structure for Soldier that has a sequenceNumber and next pointer e) Create a node structure for a queue that has front and back pointers to point soldiers. Also, a good idea would be storing nodeCount, k, th and queue name within the queue structure. f) You have to implement and use enqueue, dequeue, peek, isEmpty function for this given scenario g) In addition to the other functions of a queue like enqueue, dequeue, you code must have to implement the following functions and use them part of the solution: h) soldier* createSoldier(int sequence): It takes an integer, dynamically allocate a soldier structure and returns a soldier node i) void createReverseCircle(queue *q): It takes the reference of a queue, and creates a circular singly linked list for that queue where the nodes contain sequence numbers in reverse order . For example, if n=5 it should produce a circular singly linked list starting from 5 and ending at 1 as sequence number. During this process, use the create_soldier function as well as enqueu() function to add the soldier to the queue. j) void rearrangeCircle(queue* q): This function takes the reference of a queue and reverse the given circular singly linked list where the first node of the linked list is pointed by the front of the queue k) void display(queue q): This function displays a given queue l) It is also encouraged that you create functions for phase1, phase2, and other auxiliary functions to simplify your code m) For phase1 execution, you can avoid using dequeue function, however, you must have to use dequeue function in phase2 execution. n) You also have to use memory leak detector in your code like assignment 1. Your code must compile in Mimir platform. If it does not compile in Mimir, we conclude that your code does not compile even if it works in your computer. Hints: • Read the complete instruction first. It is always a good idea to plan it and do some paper work to understand the problem. • Just draw the scenario for a single group of soldiers first to understand how the execution process works. • Analyze the sample input/output and draw them in paper to see how they are structured • Use an array of queue. The