PDP-34 (2024)- Phase C' - 3 (bureaucracy)

View as PDF

Submit solution

Points: 40 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types
Allowed languages
C, C++, Java

Bureaucracy

The bureaucratic mechanism of the country deals with document processing. To process a document, an employee must work for some hours, the number of which is known in advance. As a result, another document is created.

We have recorded all the types of documents that exist in the country and have numbered them from 1 to N. Some of these documents, whose number is S, we call "initial", and we consider that we have them at our disposal from the beginning. Some documents, whose number is D, we call "final", and our goal is to create them. Note that it is possible for a document to be both initial and final, or neither initial nor final.

Each employee works for at most L hours per day and is paid with a gold coin for their work. During the day, they process exactly one document, provided that the processing time does not exceed L hours. This means that no document processing requiring more than L hours can be done. This explains why some things "get lost in bureaucracy"!

The supervisor selects D employees and assigns each of them to create one of the D final documents (specific and different). Each employee starts from an initial document of their choice. (Assume there is an unlimited supply of initial documents and that more employees can start from the same initial document.) If the employee is lucky, their assigned document is the same as the final document, so they don't need to do anything and won't work any day or get paid any gold coins. Otherwise, the employee will need one or more days to create the final document assigned to them, doing suitable processing each day They discard any intermediate documents they may create along the way, regardless of whether they are final and assigned to other colleagues who could find them useful! Employees naturally want to work as few hours as possible per day. So if each of them makes the best possible choices of documents for processing, find the minimum possible value of L that is sufficient to create all final documents. Also, for the minimum value of L, find the number C of gold coins that will need to be paid to the employees collectively (i.e., the total number of days they will work).

Assume that all final documents can be created using the described process, provided that the value of L is sufficiently large.

Problem

Develop a program in one of the following languages: PASCAL, C, C++, JAVA, which will read the data of the documents and will print the requested values of L and C.

For your submissions to DMOJ, use STDIN and STDOUT. The input and output format will be as described below.

Input Files

The input file named bureaucracy.in is a text file with the following structure. The first line of the input contains four integers N, S, D, and R, separated in pairs by a single space: N is the total number of documents, S is the number of initial documents, D is the number of final documents, and R is the number of different possible document processing operations. The second line of the input will contain S integers, separated in pairs by a single space: the numbers of the initial documents. Similarly, the third line will contain D integers: the numbers of the final documents. Each of the next R lines will contain three integers A, B, and E, separated in pairs by a single space, describing a possible document processing operation: document B is derived from document A, and this processing requires E hours.

Output Files

The output file named bureaucracy.out is a text file with a single line, which should contain two integers, L and C, separated by a single space: L should be the minimum value of work hours per day required to create all final documents, and C should be the minimum number of gold coins that will need to be spent for this value of L.

Examples of Input - Output Files:

input:

7 2 4 9
1 3
4 7 3 6
1 2 2
3 7 3
2 4 3
4 5 1
4 2 2
5 7 2
3 6 4
5 6 1
1 7 5

output:

3 7

Explanation of the example: There are 7 types of documents, numbered from 1 to 7. Documents 1 and 3 are initial. Documents 4, 7, 3, and 6 are final. Note that document 3 is both initial and final, so the employee assigned to it does not need to do anything.

By choosing L = 3 working hours per day, the employee assigned to create the final document 4 can start from 1 and follow the path 1 \to 2 \to 4, working a total of 2 days. The employee assigned to create the final document 6 can also start from 1 and follow the path 1 \to 2 \to 4 \to 5 \to 6, working a total of 4 days. Finally, the employee assigned to create the final document 7 can start from 3 and follow the path 3 \to 7, working only 1 day. Thus, creating all final documents will cost a total of C = 2 + 4 + 1 = 7 gold coins.

With a smaller value of L, for example, L = 2, only the final document 3 can be produced.

Constraints
  • 1 \leq N \leq 10.000
  • 1 \leq S \leq N and 1 \leq D \leq N
  • 1 \leq R \leq 100.000
  • 1 \leq A \leq N and 1 \leq B \leq N and A \neq E
  • 1 \leq E \leq 1.000.000.000
  • In the output, all lines must terminate with a newline character.
  • Time Limit: 1 sec.
  • Maximum Available Memory: 64 MB.

  • For test cases with a total value of 20%, 2 \leq N \leq 10.

  • For test cases with a total value of 40%, 2 \leq N \leq 1000 and 1 \leq E \leq 1.000.
  • For test cases with a total value of 60%, 2 \leq N \leq 1.000.

Note: Ensure efficient input reading and output printing, especially if you're translating into C++ or Java.


Comments

There are no comments at the moment.