[Solved] Algorithm Homework4-CIMS Printer

Due to some reason there is only one printer still working at Courant Institute of Mathematical Sciences. There are tons ofprinting jobs queuing for that printer and you may have to wait for a very very long time to get your paper printed.Printing jobs are assigned a priority between 1 and 9 (inclusive) where 9 is highest priority and 1 is the lowest. The printingsystem manages the jobs as follows.Select the first job from the queue.If there is some job in the queue with higher priority than the selected job then move the selected job to the end of thequeue without printing it.Otherwise, print that job.Now your problem is that it becomes so tricky to determine when your paper will be printed. You are to write a program tofigure it out. The program is given the current printing queue and the position of you job in the queue. It should output howlong it will take until your paper is printed. Assume that there are no additional jobs added to the queue and printing a singlejob takes exactly one minute (regardless of its size) and that the queue operations happen instantly (i.e., there is noadditional time spent on them).InputThe first line of input contains two integers N and M where N stands for the number of jobs in the print queue (1 <= N <= 100 ) and M is the position of your job (0 <= M <= N – 1 ; with 0 being the first position in the queue).The second line has N integers in the range, giving the priorities of jobs in the queue from the first position to the last.OutputYou should print one line with a single number, the number of minutes until your job is printed.Example 1Input:1 05Output:1Example 2Input:4 21 2 3 4Output:2Example 3Input:6 01 1 9 1 1 1Output:5Page 1/2FerryFerries used to carry cars across theriver. In your village, there is still a ferrythat can take up to N cars and needsT minutes to cross the river. A car mayarrive at either river bank and wait to becarried to the opposite bank. The ferryoperates continuously between thebanks as long it is carrying at least onecar or there is at least one car waiting oneither side. Whenever the ferry arrives atone bank, it unloads cars carried andloads up to N cars waiting at that bank.When there are more than N carswaiting, they are loaded on the firstcome-first-serve basis. If there is no carwaiting on either bank, the ferry stopsand waits until one car arrives. The ferryis initially on the left bank. You are askedto answer at what time does each cararrive at the other bank.InputThe first line of input contains threeintegers N , T and M (1 <= N, T, M <= 10,000 ). Eachof the following M lines gives the arrivaltime of a car and the bank at which thecar arrives ( left or right ). The cars are ordered by their arrival times (so the arrival times are non-decreasing) andthe time spent on loading and unloading can be ignored.OutputFor each car, you should print one line containing one number, the time at which the car is unloaded at the opposite bank.Example 1Input:2 10 100 left10 left20 left30 left40 left50 left60 left70 left80 left90 leftOutput:103030505070709090110Page 2/2Example 2Input:2 10 310 right25 left40 leftOutput:304060Page 1/2Line UpQueuing, it’s what the British are renowned for doing – and doing very well. Better than anyone else in the world, ifreputation is to be believed. Today, queues can be found just about anywhere (even in the virtual world).Standard Queues are well known to most computerscience students. It’s a first-in-first-out data structure.Kobayashi is already familiar with it. But she isassigned to write some code to maintain a variant ofStandard Queues: Group Queues.In a group queue each element belongs to a group. Ifan element is pushed to the queue and there is noelement that belongs to the same group in the queue,it will be placed behind the last element in the queue.Otherwise, if there are already some elements thatbelong to the same group, it should be placedimmediately behind them.Dequeuing works the same as int the standard queue: We will remove the first element according to the current order fromhead to tail in the queue.Kanna is preparing for her school’s Sports Festival, and she wants Kobayashi to come to this important event. ButKobayashi will not be able to attend unless she can finish her program early. As Kobayashi’s colleague and close friend, youdecide to help her. You need to write a program that simulates such a group queue.InputThe 1st line contains an integer n ( 1 <= n <= 1,000 ) equal to the number of groups, as described above.Then n group descriptions follow. Each group is described on one line by an integer k (the number of elementsbelonging to the group) followed by k integers (the indexes of the elements in this group).Elements are indexed with integer in the range [ 0 , 999,999 ] . And a group may consist of up to 1,000 elements.Finally, a list of commands follows. There are 3 different kinds of commands:Push ind : Push the element with index ind into the group queue.Pop : Output the first element and remove it from the queue.Shutdown : Stop your program (end of input).There may be up to 200,000 commands in the input file, so the implementation of the group queue should be efficient:both enqueuing and dequeuing of an element should only take a constant time.OutputFor each Pop command, print an integer, the index of the element which is dequeued, followed by a newline.Example 1Input:23 1 2 33 4 5 6Push 1Push 4Push 2Push 5Push 3Push 6PopPopPopPage 2/2PopPopPopShutdownOutput:123456Example 2Input:23 1 2 33 4 5 6Push 1Push 2Push 4PopPopPush 3Push 5PopPopPush 6PopPopShutdownOutput:124536Page 1/2Labor StrikeThere are n labor unions in New York City. You have learned that the labor union i will undertake a strike every s_idays.For example, assume the 1st day is Sunday, and labor union 1 undertakes a strike ever 4 days. Then there will be a strikeon the 4th day (the Wednesday), the 8th day (following Sunday) and so forth. (See the table below.)Because the MTA employees support all the unions, the subways do not work if at least one of the unions is on strike. Theonly exception to this are Fridays and Saturdays: even if a union has a planned strike for that day, the subways will stilloperate as usual.You need to figure out the number of days that you can not take the subway in the following m days.You can assume the 1st day is always Sunday.InputThe 1st line contains an integer m ( 7 <= m <= 3650 ) equal to the number of days for which you wish the make thecalculation.The next line contains another integer n ( 1 <= n <= 100 ) representing the number of labor unions.The i-th of the next n lines contain a positive integer s_i (which will never be a multiple of 7) giving the striking period oflabor union i.OutputOutput one integer followed by a newline: the total number of days with strikes.Example 1 (shown in the table above)Input:143438Output:5You can find there will be strikes on the 3rd, 4th, 6th, 8th, 9th, and 12th days. So the subway will not operate on the 3rd, 4th,8th, 9th, and 12th days (since the 6th day is a Friday).Page 2/2Example 2Input:100412152540Output:15Page 1/2Ruthless WarLight Kingdom is fighting a ruthless war against Conflict Empire. As a general of Light Kingdom, you decided to attack theenemy with a linear formation of soldiers. You ordered that each soldier in the attack line should protect their two nearestneighbors in the line. These two neighbors are called pals. Note that the leftmost soldier does not have a left pal and therightmost soldier does not have a right pal. If the either of the pals of a soldier is killed, then the next living neighbor to theleft/right becomes that soldier’s new pal.As the time passes, the battle becomes much more fierce and many soldiers are being killed by light sabers, blaster pistolsand magical spells. In order to keep soldier aware of their pals you need to update them about their new pals after receivingeach loss report.InputThe first line of input contains two integers N and M ( 1 <= N <= M <= 100,000 ) representing the number ofsoldiers in the attack line and the number of loss reports respectively. Soldiers are numbered from 1 to N according totheir positions in the attack line where 1 identifies the leftmost soldier and N identifies the rightmost soldier. Each of thefollowing M lines describes a loss report and contains two integers L (left) and R (right), meaning that soldiers from Lto R were killed ( 1 <= L <= R <= N ). It is guaranteed that those soldiers were alive until that moment.OutputYou should print M lines. In the i-th line should contain the new pal relationships formed after removing from the attack linethe soldiers who were killed according to the i-th loss report. That is, for the loss report L R , print the first living soldier tothe left of L and the first living soldier to the right of R . If there is no surviving soldier in some direction, print the character* instead.Example 1Input:1 11 1Output:* *Example 2Input:10 42 56 91 110 10Output:1 61 10* 10* *Example 3Input:5 11 1Output:Page 2/2*