Untitled
unknown
plain_text
a year ago
9.8 kB
4
Indexable
You want to create a program that stores and releases bacteria in and from a storage.
There are N types of bacteria that can be stored in the storage.
Bacteria have life force. Every mHalfTime later from the starting time of bacteria storage, the life force is halved.
When the life force has decimals, remove them. For instance, the life force of 100.5 will be 100.
When the life force of bacteria is less or equal to 9, the bacteria will be disposed.
Once the release of bacteria is called for, the bacterium with the weakest life force among the bacteria is released.
In the storage, the situation mentioned below is repeated every hour.
1. Every mHalfTime later from the starting time of bacteria storage, the life force is halved.
2. Bacteria whose life force is less or equal to 9 are disposed.
3. New bacteria are stored in or released from the storage.
You are required to write a program that manages such a storage.
Implement each required function by referring to the following API description.
※ The function signature below is based on C/C++. As for Java, refer to the provided Solution.java and UserSolution.java.
The following is the description of API to be written in the User Code.
void init(int N, char bNameList[][], int mHalfTime[])
This function is called in the beginning of each test case.
In the beginning, the storage is empty. The current time is 0.
The storage can store N types of bacteria.
The name of bacteria is bNameList[]. The time when the life force of them is halved is mHalfTime[].
The names of bacteria are bNameList[0], bNameList[1], …, and bNameList[N – 1]. The names differ from one another.
The time when the life force of bacteria is halved are mHalfTime[0], mHalfTime[1], …, and mHalfTime[N – 1].
For instance, the name of the 0th bacteria is bNameList[0] and the time when their life force is halved is mHalfTime[0].
bNameList[] is a string whose length is greater or equal to 3 but 9 at most made up of lowercase letters. It ends with ‘＼0’.
Parameters
N : The types of bacteria stored in the storage (1 ≤ N ≤ 100 )
bNameList[] : The name of bacteria ( 3 ≤ The length of bNameList[] ≤ 9 )
mHalfTime[] : The time when the life force of bacteria is halved ( 10 ≤ mHalfTime[] ≤ 10,000 )
void addBacteria(int tStamp, char bName[], int mLife, int mCnt)
This function stores mCnt bacteria whose names are bName with life force of mLife at tStamp time.
The life force of bacteria named bName is mLife at the time of tStamp. Then, every mHalfTime later, the current life force is halved.
Let’s say that the value of mHalfTime of bacteria with the life force of 171 is 10.
Then, every 10 hours later from tStamp time, the life force decreases as follows: 171 -> 85 -> 42 -> 21 -> 10 -> 5. If the life force decreases to 5, the bacteria are disposed.
bName is a string that is made up of lowercase letters whose length is greater or equal to 3 but 9 at most. It ends with ‘＼0’.
Parameters
tStamp : The time when bacteria are stored in the storage (1 ≤ tStamp ≤ 1,000,000 )
bName[] : The name of bacteria ( 3 ≤ The length of bName ≤ 9 )
mLife : The life force of bacteria ( 100 ≤ mLife ≤ 50,000 )
mCnt : The number of bacteria ( 1 ≤ mCnt ≤ 1,000 )
int takeOut(int tStamp, int mCnt)
This function releases mCnt bacteria whose life force is the weakest in the storage at tStamp time and returns the sum of life force of the bacteria that are released.
If the number of bacteria stored in the storage is below mCnt, release all the bacteria that are stored.
If there are bacteria with the same life force, the bacterium whose time of storage is earlier than the others is released first.
Bacteria whose life force is 9 or below are not included as they are disposed at tStamp time.
When calling the function, it is guaranteed that the number of bacteria in the storage is greater or equal to 1.
Parameters
tStamp : The time of bacteria release (1 ≤ tStamp ≤ 1,000,000 )
mCnt : The number of bacteria that are released ( 1 ≤ mCnt ≤ 100 )
Returns
The sum of life force of bacteria that are released
int checkBacteria(int tStamp, char bName[])
This function returns the number of bacteria named bName in the storage at tStamp time.
Bacteria whose life force is 9 or below are not included as they are disposed at tStamp time.
The number of bName bacteria in the storage may be 0.
Parameters
tStamp : The time to check the number of bacteria named bName in the storage (1 ≤ tStamp ≤ 1,000,000 )
bName[] : The name of bacteria ( 3 ≤ The length of bName ≤ 9 )
Returns
The number of bacteria named bName in the storage
[Example]
Let’s look into a case where functions are called as in [Table 1].
Order
Function
Note
Figure
1
init( 3, {“aaa”, “bbb”, “ccc”}, {55, 44, 33} )
2
addBacteria(10, “aaa”, 110, 3)
3
addBacteria(12, “bbb”, 120, 2)
4
addBacteria(19, “ccc”, 160, 4)
5
addBacteria(20, “aaa”, 105, 2)
6
addBacteria(25, “bbb”, 109, 3)
7
takeOut(120, 1)
return 20
[Fig. 1]
8
takeOut(150, 1)
return 15
9
takeOut(151, 1)
return 10
[Fig. 2]
10
checkBacteria(184, “ccc”)
return 0
11
addBacteria(200, “aaa”, 300, 1)
12
addBacteria(201, “bbb”, 310, 1)
13
addBacteria(202, “ccc”, 153, 2)
14
addBacteria(203, “ccc”, 140, 2)
[Fig. 3]
15
takeOut(310, 3)
return 53
16
checkBacteria(311, “aaa”)
return 1
17
checkBacteria(312, “ccc”)
return 1
[Fig. 4]
[Table 1]
[Fig. 1] to [Fig. 4] show the bacteria in the storage. (The numbers inside the parenthesis are the life forces of bacteria.)
In Order 7. takeOut(120, 1), one of the bacteria named “ccc” with the weakest life force of 20 is released. ( The red box in [Fig. 1] )
In Order 9. takeOut(151, 1), one of the bacteria named “ccc” with the lowest life force of 10 is released. ( The red box in [Fig. 2] )
In Order 14. addBacteria(203, “ccc”, 140, 2), two bacteria named “ccc” with life force of 140 are added in the storage. ( The yellow box in [Fig. 2] )
In Order 17. checkBacteria(312, “ccc”), bacteria in the storage are as in [Fig. 4] .
[Constraints]
1. init() is called in the beginning of each test case.
2. The name of bacteria is a string whose length is greater or equal to 3 but 9 at most made up of lowercase letters. It ends with ‘＼0’.
3. For each test case, the number of types of bacteria that are stored is 100 at most.
4. For each test case, the value of tStamp is a value that is always increasing.
5. For each test case, addBacteria() is called up to 15,000 times.
6. For each test case, takeOut() is called up to 15,000 times.
7. For each test case, the sum of calls of the all functions is up to 50,000.
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#define MAX_BCNT 100
#define MAX_NAME 10
extern void init(int N, char bNameList[MAX_BCNT][MAX_NAME], int mHalfTime[MAX_BCNT]);
extern void addBacteria(int tStamp, char bName[MAX_NAME], int mLife, int mCnt);
extern int takeOut(int tStamp, int mCnt);
extern int checkBacteria(int tStamp, char bName[MAX_NAME]);
/////////////////////////////////////////////////////////////////////////
#define CMD_INIT 0
#define CMD_ADD 1
#define CMD_OUT 2
#define CMD_CHECK 3
static bool run() {
int q;
scanf("%d", &q);
int time, life, cnt, halftime[MAX_BCNT];
char bname[MAX_BCNT][MAX_NAME];
int cmd, ans, ret;
bool okay = false;
for (int i = 0; i < q; ++i) {
scanf("%d", &cmd);
switch (cmd) {
case CMD_INIT:
scanf("%d", &cnt);
for (int k = 0; k < cnt; k++) {
scanf("%s %d", bname[k], &halftime[k]);
}
init(cnt, bname, halftime);
okay = true;
break;
case CMD_ADD:
scanf("%d %s %d %d", &time, bname[0], &life, &cnt);
addBacteria(time, bname[0], life, cnt);
break;
case CMD_OUT:
scanf("%d %d %d", &time, &cnt, &ans);
ret = takeOut(time, cnt);
if (ans != ret)
okay = false;
break;
case CMD_CHECK: {
scanf("%d %s %d", &time, bname[0], &ans);
ret = checkBacteria(time, bname[0]);
if (ans != ret)
okay = false;
break;
}
default:
okay = false;
break;
}
}
return okay;
}
int main() {
setbuf(stdout, NULL);
//freopen("sample_input.txt", "r", stdin);
int T, MARK;
scanf("%d %d", &T, &MARK);
for (int tc = 1; tc <= T; tc++) {
int score = run() ? MARK : 0;
printf("#%d %d\n", tc, score);
}
return 0;
}
#define MAX_BCNT 100
#define MAX_NAME 10
void init(int N, char bNameList[MAX_BCNT][MAX_NAME], int mHalfTime[MAX_BCNT])
{
}
void addBacteria(int tStamp, char bName[MAX_NAME], int mLife, int mCnt)
{
}
int takeOut(int tStamp, int mCnt)
{
return -1;
}
int checkBacteria(int tStamp, char bName[MAX_NAME])
{
return -1;
}
25 100
17
0 3
aaa 55
bbb 44
ccc 33
1 10 aaa 110 3
1 12 bbb 120 2
1 19 ccc 160 4
1 20 aaa 105 2
1 25 bbb 109 3
2 120 1 20
2 150 1 15
2 151 1 10
3 184 ccc 0
1 200 aaa 300 1
1 201 bbb 310 1
1 202 ccc 153 2
1 203 ccc 140 2
2 310 3 53
3 311 aaa 1
3 312 ccc 1