{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\n\u003cp\u003e\nYour job is to simulate the operation on a machine called ACM (Asynchrounous Calculating Machine) to determine how long each program takes to finish their job.\nThis helps detecting unexpected thread behaviors, like race and deadlock.\n\u003c/p\u003e\n\n\u003cp\u003e\nACM has many processing units and can run many threads simultaneously.\nIt runs a global scheduler, which maintains all the threads, assigns a thread on each processing unit and manages all semaphores.\nEach thread has its own thread id and every thread is one of three states: RUNNING, READY, and WAITING.\nGlobal scheduler has one thread queue which contains all the threads in READY state.\n\u003c/p\u003e\n\n\u003ch3\u003e\nexplanation of a program\n\u003c/h3\u003e\n\n\u003cp\u003e\nA program consists of one or more code blocks.\nEach code block has a list of ACM operations, including the actual computations and thread creation.\nEach thread runs operations in only one of the given code blocks, and it runs operations from the top of the block to the bottom, unless it receives killThread-signal from other threads.\n\u003c/p\u003e\n\n\u003ch3\u003e\nexplanation of operations\n\u003c/h3\u003e\n\n\u003cp\u003e\nACM simulation program simulates 9 operations.\nHere I describe them all.\nPlease note that word enclosed by [] should have some actual name or value.\n\u003c/p\u003e\n\n\u003cdl\u003e\n\u003cdt\u003ecompute [clock]\u003c/dt\u003e\u003cdd\u003e Spend [clock] clocks for computation. When this operation is interrupted after spending T clocks by other threads or the scheduler and is resumed later, it consumes [clock] - T clocks.\u003c/dd\u003e\n\u003cdt\u003e[thread-var] \u0026lt;- forkR [code block] \u003c/dt\u003e\u003cdd\u003e Generate a native thread running on [code block] and store its id in a thread variable [thread-var]. It can run simultaneously with any threads which are generated in other processing unit. If [thread-var] is used before in the thread, its previous value is overwritten and lost. (This means that we will not be able to refer to the thread although it might run forever.)\u003c/dd\u003e\n\u003cdt\u003e[thread-var] \u0026lt;- forkI [code block] \u003c/dt\u003e\u003cdd\u003e Generate a virtual thread running on [code block] and store its id in a thread variable [thread-var]. A virtual thread shares some OS resources with its parent thread, so they can\u0027t run simultaneously even there are idle processing units. This restriction is applied to any two threads which are directly or indirectly connected by the parent-child relatinship of forkI. If [thread-var] is used before in the thread, its previous value is overwritten and lost.\u003c/dd\u003e\n\u003cdt\u003e yield \u003c/dt\u003e\u003cdd\u003e Make the current thread from running state to ready state. The thread goes to the end of the thread queue.\u003c/dd\u003e\n\u003cdt\u003e killThread [thread-var] \u003c/dt\u003e\u003cdd\u003e Send a kill signal to the [thread-var] thread. [thread-var] guaranteed to be used in either forkR or forkI operations in the same code block before this operation. When a thread receives a kill signal, it immediately cancels its resource requests by lock, changes into ready state if it\u0027s in block state, and ends its operation when it\u0027s in running state. This operation does not change the semaphore values. If the target thread is already ended, this operation does nothing.\u003c/dd\u003e\n\u003cdt\u003e lock [semaphore name] [amount] \u003c/dt\u003e\u003cdd\u003e Request [amount] of [semaphore name]. If the value of [semaphore name] is greater or equal to the [amount], it just subtracts the [amount] from the semaphore variable. Otherwise, the operation blocks the current thread until the variable is greater or equal to the [amount]. Once the variable gets greater or equal to the [amount], the thread gets into READY state and goes into the thread queue after subtracting [amount] from the variable. If there are more than one thread requesting for the same semaphore, the thread which locked the semaphore first always gets READY first. So, the other threads won\u0027t get READY even if the semaphore variable meets their demands. If there are more than one thread getting READY, the thread which locked the semaphore earlier goes into the queue first.\u003c/dd\u003e\n\u003cdt\u003e unlock [semaphore name] [amount] \u003c/dt\u003e\u003cdd\u003e Add [amount] to [semaphore name]. Values of semaphores can be larger than initial values. The thread doesn\u0027t get blocked at all by this operation.\u003c/dd\u003e\n\u003cdt\u003e loop [loop count] \u003c/dt\u003e\u003cdd\u003e Run the code snippet between loop and corresponding next command for [loop count] times.\u003c/dd\u003e\n\u003cdt\u003e next \u003c/dt\u003e\u003cdd\u003e This corresponds a loop command in the same code block. The code snippet between loop and next should be run.\u003c/dd\u003e\n\u003cdt\u003e end \u003c/dt\u003e\u003cdd\u003e End the operation. This command only appears in the end of the code block, and each code block has this operation at the end.\u003c/dd\u003e\n\u003c/dl\u003e\n\n\u003cp\u003e\nEach parameter should either be a name or a digit. A name is an alphabetic string (case-sensitive) and its length is at most 200. Here are some explanations.\n\u003c/p\u003e\n\n\u003cdl\u003e\n\u003cdt\u003e [thread-var] \u003c/dt\u003e\u003cdd\u003e It is a name. It only refers to the id in the same thread. Each thread has its own value even it has the same name.\u003c/dd\u003e\n\u003cdt\u003e [clock] \u003c/dt\u003e\u003cdd\u003e It is a non-negative integer which is at most 1,000.\u003c/dd\u003e\n\u003cdt\u003e [semaphore-name] \u003c/dt\u003e\u003cdd\u003e It is a name.\u003c/dd\u003e\n\u003cdt\u003e [amount] \u003c/dt\u003e\u003cdd\u003e It is a non-negative integer which is at most 1,000.\u003c/dd\u003e\n\u003cdt\u003e [loop count] \u003c/dt\u003e\u003cdd\u003e It is a non-negative integer which is at most 1,000.\u003c/dd\u003e\n\u003c/dl\u003e\n\n\u003cp\u003e\nAdditionally, you may assume following constraints.\n\u003c/p\u003e\n\n\u003cul\u003e\n\u003cli\u003e Total number of lines that all threads evaluate throughout simulation never exceeds 100,000.\u003c/li\u003e\n\u003cli\u003e Size of input file never exceeds 100KB.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003e\nexplanation of a simulator\n\u003c/h3\u003e\n\n\u003cp\u003e\nThreads are assigned to CPUs when\n\u003c/p\u003e\n\n\u003cul\u003e\n\u003cli\u003e a simulation starts. (A thread is assigned to CPU 1. Its code block is the first code block of the input.)\u003c/li\u003e\n\u003cli\u003e there are more than one threads that are in ready state which can be assigned to a CPU. (Threads are asssinged in the thread queue order. If there are more than one CPUs that can be assinged to the thread, the smallest CPU is selected.)\u003c/li\u003e\n\u003cli\u003e time step is a multiple of time slice. (If the CPU has a thread that is running state, the thread goes to ready state in asscending order of the CPU id. After this, threads are assigned to each CPU in asscending order of the CPU id.)\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\nIn each step, the simulator does round-robin preemption (when time step is a multiple of time slice), executes operations of each running threads and increments time step.\nWhen a compute operation is executed, the thread gets computing time.\nA thread that has computing time greater than 0 cannot do any operations.\nAfter each step, the simulator decrements positive computing time of each running thread.\n\u003c/p\u003e\n\n\u003cp\u003e\nOperations executed in the same time step is executed in ascending order of the CPU id.\nIn the same time step, a CPU id of an operation is greater or equal to CPU ids of operations which have already been executed.\n\u003c/p\u003e\n\n\u003cp\u003e\nTime step starts from 0.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003e\nInput consists of multiple testcases.\n\u003c/p\u003e\n\n\u003cp\u003e\nEach testcase begins with a line that contains two integers separated by a space.\nThey mean the number of time steps of the simulation and the maximum number of threads that ACM is capable, respectively.\nThe next line contains a single integer, which indicates the number of CPUs available.\nThe following line has an integer that means time slice of the scheduler.\n\u003c/p\u003e\n\n\u003cp\u003e\nDescription of semaphores follows.\nIt begins with the number of semaphores which is followed by information of each semaphore, one per line.\nThe information of a semaphore consists of an alphabet string (case-sensitive) and an integer, which specify the name of the semaphore and its initial value, respectively.\n\u003c/p\u003e\n\n\u003cp\u003e\nFinally code blocks are given.\nThe number of code blocks comes first, and then each code block is described.\nThe first line of the description of each code block is the name of the block (case-sensitive alphabet string), followed by a colon (:).\nFollowing lines describe content of the code block.\nA code block is an array of operations described above, and one operation is written in one line.\nYou may assume that every code block always ends with an \u0027end\u0027 operation.\n\u003c/p\u003e\n\n\u003cp\u003e\nInput terminates with two zeroes separated by a space character.\n\u003c/p\u003e\n\n\u003ch3\u003e\nconstraints\n\u003c/h3\u003e\n\n\u003cul\u003e\n\u003cli\u003e Threre is 1 thread queue.\u003c/li\u003e\n\u003cli\u003e The id of the \u003cvar\u003en\u003c/var\u003e-th created thread is \u003cvar\u003en\u003c/var\u003e.\u003c/li\u003e\n\u003cli\u003e CPU ids are 1 though the number of CPUs.\u003c/li\u003e\n\u003cli\u003e The number of time steps is at most 1,000.\u003c/li\u003e\n\u003cli\u003e The maximum number of threads is at most 1,000.\u003c/li\u003e\n\u003cli\u003e The number of CPUs is at most 100.\u003c/li\u003e\n\u003cli\u003e Time slice is at most 1,000\u003c/li\u003e\n\u003cli\u003e The number of semaphores is at most 1,000.\u003c/li\u003e\n\u003cli\u003e The number of code blocks is at most 1,000.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nFor each test case, print its case number on the first line.\n\u003c/p\u003e\n\n\u003cp\u003e\nIf the number of living threads exceeds ACM\u0027s capacity, put information of all threads which terminated before exceeding the capacity, and then put \"\u0026lt;\u0026lt;oops\u0026gt;\u0026gt;\".\nIf not, and if there are one or more threads not finished at the end of the simulation, put information of all threads terminated, and then put \"\u0026lt;\u0026lt;loop\u0026gt;\u0026gt;\".\nOtherwise (i.e. when all threads terminates within the time), just put information of all threads.\nAll quotes are for clarity.\n\u003c/p\u003e\n\n\u003cp\u003e\nInformation of threads must be written in increasing order of thread ID, one per line.\nInformation of a single thread is denoted by two integers, the thread ID and the time it terminated, separated by a single space character.\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input\u003c/h2\u003e\n\n\u003cpre\u003e50 50\n1\n10\n1\nsemaphore 1\n1\ncodeBlockA:\nloop 2\ncompute 10\nnext\nend\n50 50\n1\n10\n1\nsemaphore 1\n2\ncodeBlockA:\nhoge \u0026lt;- forkR codeBlockB\nyield\ncompute 1\nkillThread hoge\nlock semaphore 1\ncompute 1\nend\ncodeBlockB:\ncompute 1\nlock semaphore 2\nend\n5 5\n1\n3\n1\nsemaphore 1\n1\ncodeBlockA:\nhoge \u0026lt;- forkI codeBlockA\ncompute 1\nend\n5 5\n1\n2\n1\nsemaphore 1\n1\ncodeBlockA:\ncompute 1\nhoge \u0026lt;- forkI codeBlockA\nhoge \u0026lt;- forkI codeBlockA\nend\n0 0\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input\u003c/h2\u003e\n\n\u003cpre\u003eCase 1:\n1 20\nCase 2:\n1 3\n2 3\nCase 3:\n1 1\n2 2\n3 4\n4 4\n5 5\n\u0026lt;\u0026lt;loop\u0026gt;\u0026gt;\nCase 4:\n1 1\n2 3\n3 3\n\u0026lt;\u0026lt;oops\u0026gt;\u0026gt;\n\u003c/pre\u003e\n"}}]}