Untitled

[Restrictions]



Execution Time

3 sec (C++) / 3 sec (Java) for 25 test cases combined

Memory Limit

Maximum 256MB is available for heap and static memory combined (Note: Maximum 1MB can be used for stack)



※ The following practice problem is the Professional Test problem designed to improve Samsung Electronics Employees' capability to solve SW problems.

The testcase provided along with the problem is also for practice.

 

  ①   Test takers who will be using C or C++ to write their answer,

  ㅇ   please select C++ as for the Language before submitting the answer.

  ②   Consists of the Main part and User Code part.

  ㅇ   A.  Main Part         : Cannot be edited. But note that a validation logic can be added in here

  ㅇ   A.  Main Part         : for the purposes of solution evaluation such as to detect an abnormal solution.

  ㅇ   B.  User Code Part  : Code which the test taker must actually write.

  ㅇ   B.  User Code Part  : Make sure that standard input/output functions are NOT included when submitting the code.

  ③   Cautions When Programming on Local PC

  ㅇ   A.  2 files must be generated. ( main.cpp / solution.cpp or Solution.java / UserSolution.java )

  ㅇ   B.  Please copy the Main part into main.cpp or Solution.java.

  ㅇ   C.  To use the sample_input.txt, uncomment the code (commented)

  ㅇ   C.  which uses the file as the standard input within the Main part code.

  ㅇ   D.  Delete or comment all standard input/output functions for debugging before submitting your code.

  ④   Since not all constraints are specified in this document, analyze the given code for further information.

  ⑤   Given codes can differ depending on the programming language. Analyze codes according to your language selection.


[Problem Description]






                                           [Fig. 1]


Users exchange files through a P2P network.


They are connected to the network, and a link, which has no direction, connects two different users.


The network consists of a single tree; the users are the nodes and the links are the edges.


In other words, when a user transmits a file to another user, there is only one possible transmission path, which creates a graph.


[Fig. 1] shows an example where the network consists of 6 users and 5 links.


Since there is a link which has no direction and directly connects User 1 and User 3, User 1 can transmit a file to User 3, and vice versa.


If User 1 sends a file to User 5, the transmission path is "1, 3, 4, 5."


 


Each link has its own bandwidth.


To send a file, the link uses some of its bandwidth.


In [Fig. 1], the numbers for each link represent "bandwidth in use/total bandwidth."


For example, the link connecting User 1 and User 3 has 0/150, meaning that its total bandwidth is 150 and 150 is available for use since 0 bandwidth is currently in use.


 


The user can change the status of his/her individual files to ‘Share.’


 


You are required to provide a service where the user can download files via the P2P network.


 


The following is the description of API to be written.


※ The function signature below is based on C/C++. As for Java, refer to the provided Solution.java and UserSolution.java.


void init(int N, int mUID1[], int mUID2[], int mBandwidth[])

This function is called once in the beginning of each test case.

 

There are N number of users on the network.

Each user is assigned an ID from 1, 2, 3, … , to N.

 

The number of links is N-1. For i = 0, 1, … , N-2, the “i”th link connects two users, mUID1[i] and mUID2[i], and its bandwidth is mBandwidth[i].

 

The link directly connects two different users. The maximum number of such a link is 1.

 

In the beginning of the test case, no bandwidth is in use since no files are being sent.

In the beginning of the test case, there are no files whose status is ‘Share.’

 

 

Parameters

   N : Number of users on the network (2 ≤ N ≤ 200)

   mUID1 : ID of User 1 of the link (1 ≤ mUID1[i] ≤ N)

   mUID2 : ID of User 2 of the link (1 ≤ mUID2[i] ≤ N)

   mBandwidth : the bandwidth of the link (1 ≤ mBandwidth[i] ≤ 100,000)

int share(int mUID, char mFilename[], int mFilesize)

A user, mUID, changes the status of a file named mFilename to ‘Share,’ which is owned by the user.

 

The size of the file is mFilesize.

If the names of files on the network are the same, this means that their file sizes and content are the same as well.

The file mFilename might be already shared by mUID.

 

 

Parameters

   mUID : User ID (1 ≤ mUID ≤ N)

   mFilename : File name (4 ≤ the length of the name ≤ 9)

   mFilesize : File size (1 ≤ mFilesize ≤ 1,000)

Return

   Number of different files shared by mUID including mFilename

int request(int mUID, char mFilename[], int mTID)

mUID makes a request to download mFilename from the network.

 

The ID of this request is mTID.

If the names of files on the network are the same, this means that their file sizes and content are the same as well.

 

Who transmits the file can be determined according to the following criteria:

1. Check the transmission path for each user who has changed the file status to ‘Share.’

  Select a user of the link whose bandwidth available for use is greater or equal to the size of the file.

2. If there are two or more such users, select the one who can send the file using the minimum number of links.

3. If there are two or more such users, select the one with the smallest ID.

 

If there is such a user, file transmission starts immediately, and for each link on the transmission path, the bandwidth is used as much as the size of the file.

If there is no such a user, the request is ignored and -1 is returned.

 

For the request function called in each test case, mTID cannot be duplicated.

It is guaranteed that mUID does not have mFilename when this function is called.

Several request() can be called with the same mUID and mFilename, but with different mTIDs, and each request() also uses separate link bandwidth because file transmission by each request() is independently performed.

 

Parameters

   mUID : User ID (1 ≤ mUID ≤ N)

   mFilename : File name (4 ≤ the length of the name ≤ 9)

   mTID : Request ID (1 ≤ mTID ≤ 5,000)

Return

   -1 if there is no user who can send the file;

   ID of the user if there is such a user

int complete(int mTID)

File transmission by mTID is successfully completed.

 

The bandwidth of all links on the path originally allocated for the transmission becomes available again.

Not only the user who makes the request, mTID, but also other users on the path receive the file, and the status of the file is set to ‘Share.’

For instance, if User 1 transmits a file to User 5, and the transmission path is "1, 3, 4, 5," the file is shared with User 3, User 4, and User 5 when this function is called.

 

It is guaranteed that mTID is the request by which the file transmission is currently in progress.

 

Parameters

   mTID : ID of the request which is successfully completed (1 ≤ mTID ≤ 5,000)

Return

   Number of different files shared by the user who makes the request, mTID, including the received file


 


 


[Example]


Think of the case where functions are called as shown in [Table 1].


This shows Sample TC #1.


Order

Function

Description

Return

Figure

1

init(6, [1, 2, 4, 4, 6], [3, 3, 3, 5, 5], [150, 200, 100, 300, 1000])

 

[Fig. 1]

2

share(3, “tetris”, 50)

1

 

3

request(5, “tetris”, 222)

For each of the links on the path of "3, 4, 5," the bandwidth as much as 50 is used.

3

 

4

share(6, "packman", 20)

 

1

 

5

request(2, “packman”, 888)

For each of the links on the path of "6, 5, 4, 3, 2," the bandwidth as much as 20 is used.

6

[Fig. 2]

6

complete(222)

The bandwidth originally allocated for Request 222 becomes available.

1

[Fig. 3]

7

request(2, "tetris", 333)

The file "tetris" is currently shared by User 3, User 4, and User 5.

And the file is sent from User 3 because the user can send it using the minimum number of links.

For each of the links on the path of "3, 2," the bandwidth as much as 50 is used.

3

 

8

share(1, "database", 90)

 

1

 

9

request(5, "database", 555)

The file "database" is currently shared by User 1.

However, this request is ignored and -1 is returned because the link connecting User 3 and User 4 has not enough bandwidth to use.

Therefore, no bandwidth is used for the request.

-1

[Fig. 4]

10

complete(888)

The bandwidth originally allocated for Request 888 becomes available.

1

 

11

request(2, "tetris", 111)

The request has the same user/file ID as those in the request() at Order #7, but it is considered to be a different request.

In other words, the request() at Order #7 and Order #11 use separate link bandwidth.

3

[Fig. 5]

12

complete(111)

The bandwidth originally allocated for Request 111 becomes available.

2

 

13

request(4, “database”, 777)

For each of the links on the path of "1, 3, 4," the bandwidth as much as 90 is used.

1

[Fig. 6]


                                           [Table 1]


 


 


[Fig. 2] shows the status of the network and the files shared by user after the functions are executed until Order #5.


 




                                           [Fig. 2]


 


[Fig. 3] shows the status of the network and the files shared by user after the functions are executed until Order #6.






                                           [Fig. 3]


 


[Fig. 4] shows the status of the network and the files shared by user after the functions are executed until Order #9.






                                           [Fig. 4]


 


[Fig. 5] shows the status of the network and the files shared by user after the functions are executed until Order #11.






                                           [Fig. 5]


 


[Fig. 6] shows the status of the network and the files shared by user after the functions are executed until Order #13.






                                           [Fig. 6]


 


[Constraints]


1. init() is called once in the beginning of each test case.


2. For each test case, share() can be called up to 5,000 times.


3. For each test case, request() can be called up to 5,000 times.


4. For each test case, complete() can be called up to 5,000 times.


5. The file name (mFilename), the parameter of share() and request() is a string which consists of lowercase English letters of minimum 4, but no larger than 9, ending with ‘＼0.’


6. For the request function of each test case, mTID cannot be duplicated.


 


[Input and Output]


As the input and output are processed in the provided code in the Main, they are not processed separately in the User Code.


The output result for the sample input is in the format of “#TC number result.” It is the correct answer if the result is 100; it is the wrong answer if it is 0.