Untitled
unknown
plain_text
a year ago
15 kB
12
Indexable
[Problem Description]
When the restaurant receives a delivery order, a delivery rider is assigned. You want to simulate the delivery process hourly.
There are N staff members in the restaurant who fulfill orders.
U, the number of houses of customers ordering food, is given.
The restaurant is located at (0, 0). Each location of customers is given in the form of (uX, uY).
Meanwhile, the location of the restaurant and that of the houses of customers do NOT overlap.
There are R delivery riders. The initial locations of delivery riders are given in the form of (rX, rY).
[Fig. 1] shows the locations of the restaurant, three houses of customers, and three delivery riders.
The blue circle is the restaurant; the red houses are the houses of customers; the yellow bikes are deliver riders.
[Fig. 1]
[Fig. 2] shows the process of fulfilling an order.
[Fig. 2]
(1) A customer orders food.
(2) The order is assigned to one of the staff standing by.
(3) The assigned staff calls a delivery rider standing by nearest to the restaurant.
(4) The contacted delivery rider picks up the food as soon as he/she arrives at the restaurant.
(5) The staff’s status is then changed into standby status. As such, he/she is able to fulfill the next order.
(6) The delivery rider who picked up the food goes to the customer’s house.
(7) As soon as the rider arrives at the house, he/she hands over the food. Then, his/her status becomes standby at the location and waits for the next call.
The customer’s order, delivery rider, and restaurant staff must follow the process as below every hour.
[Order]
Every hour, one order is received at most.
The received orders are listed in the waiting list.
The orders are processed in accordance with the time each order was placed.
In other words, an order that was received earlier than the other will be processed first.
[Delivery Rider]
Delivery riders perform food delivery. They will be in one of the two status mentioned below.
- Delivery Status : Status when the rider receives a call from a restaurant staff until the time before the rider delivers the food to the customer after picking it up in the restaurant.
- Standby Status : Status when the rider is NOT in delivery status. In other words, when the rider did not receive a call from the restaurant staff or when the delivery is done.
The distance of delivery and the delivery time are calculated as follows.
- The distance to move from location A(XA, YA) to location B(XB, YB) is calculated as |XA – XB| +|YA – YB|.
- The time it took for the rider to move between the two locations is the same with the value of the distance between the two.
In [Fig. 3], the current location of the delivery rider is (2, 5); the location of the restaurant is (0, 0); and the location of the customer is (5, 3).
When the customer places an order, the restaurant staff contacts the delivery rider. The distance of the rider going to the restaurant is calculated as |2 - 0| + |5 - 0| = 7. The time it took to do so is 7.
After picking up the food, the distance the rider moved from the restaurant to the customer’s house is calculated as |0 - 5| + |0 - 3| = 8. The time it took to do so is 8.
Ignore the time it took for the ride to pick up the food and the time it took to hand over the food to the customer at the customer’s location.
Therefore, the total time it took for the rider to complete the delivery is 15. The rider stands by at the customer’s house after completing the delivery. As such, the location the rider stands by is at (5, 3).
[Fig. 3]
Every hour, delivery riders, who are in delivery status as they are contacted or delivering food, continue to move around. Those arriving at the customer’s house hand over the food to the customer. Then, they stand by at the location.
Delivery riders in standby status wait for a call in the place where they are currently at.
[Restaurant staff]
Restaurant staff hand over the ordered food to delivery riders. They will be in one of the two status mentioned below.
- Working Status : Status when the staff contacts a rider after being assigned an ordered food until the time he/she waits for the rider to arrive at the restaurant.
- Standby Status : NOT in working status. In other words, a status when the contacted rider picked up the food or when the staff is not waiting for a delivery rider because he/she was not assigned an order.
The restaurant staff work as below hourly.
If the standby-status staff has orders to fulfill in the waiting list, he/she is assigned the order that came first and contacts a delivery rider nearest to the restaurant among delivery riders who are in standby status (standing by or riders who have finished delivery at this point).
(If there are multiple riders who are in standby status and whose distance to the restaurant is all the same, contact the rider whose ID is the smallest.)
If a staff does not have an order to be assigned or if there are no riders in standby status, the staff in standby status maintains the status.
The staff in working status waits until the contacted delivery rider arrives at the restaurant. As soon as the rider arrives, the status of the staff changes into standby status.
Implement each required function by referring to the following API description.
※ The function signature below is based on C/C++. As for other languages, refer to the provided Main and User Code.
The following is the description of API to be written in the User Code.
void init(int N, int U, int uX[], int uY[], int R, int rX[], int rY[])
This function is called in the beginning of each test case.
When this function is called, the time is 0 and there is no order received.
There are N staff members in the restaurant and they are all in standby status. The location of the restaurant is (0, 0).
U, the number of customers’ houses ordering food, is given. Each ID is labeled of 0, 1, 2,…, and U-1.
The location of each house is (uX[0], uY[0]), (uX[1], uY[1]), … (uX[U-1], uY[U-1]) following the ID order.
There are R delivery riders. The ID of each rider is labeled of 0, 1, 2,…, and R-1.
The location of each rider is (rX[0], rY[0]), (rX[1], rY[1]), … (rX[R-1], rY[R-1]) ]) following the ID order.
There are no houses or riders located at the same place with the restaurant.
It is guaranteed that the locations of the customers’ houses do NOT overlap.
However, the locations of riders can overlap with each other.
All riders are in standby status.
Parameters
N : The number of staff members (1 ≤ N ≤ 30)
U : The number of customers (1 ≤ U ≤ 500)
uX[], uY[] : Coordinate plane of customers 0 ≤ uX[i], uY[i] ≤ 300 (0 ≤ i ≤ U-1)
R : The number of delivery riders (1 ≤ R ≤ 2,000)
rX[], rY[] : Coordinate plane of delivery riders 0 ≤ rX[i], rY[i] ≤ 300 (0 ≤ i ≤ R-1)
int order(int mTimeStamp, int uID)
This function makes the customer whose ID is ‘uID’ order food to the restaurant when the time is mTimeStamp.
Regardless of whether the ordered food was delivered, the customer can place orders several times.
The function returns the number of staff members in standby status in the restaurant after the procedure to be processed at mTimeStamp is finished.
Parameters
mTimeStamp : The time when food is ordered (1 ≤ mTimeStamp ≤ 40,000,000)
uID : The ID of a customer who ordered food (0 ≤ uID ≤ U-1)
return
The number of staff members in standby status
int checkWaitingRiders(int mTimeStamp)
This function returns the number of delivery riders in standby status after the procedure to be processed at mTimeStamp is finished.
Parameters
mTimeStamp : The time to return a status (1 ≤ mTimeStamp ≤ 40,000,000)
return
The number of delivery riders standing by
[Example]
Think of the following case when a function is called like the Table below.
순서
Function
Return
Figure
1
init(3, // 3 staff members
3, [1, 3, 5], [1, 4, 0], // 3 customers
3, [1, 4, 2], [1, 3, 1]) // 3 delivery riders
[Fig. 4]
2
checkWaitingRiders(1)
3
3
order(2, 1)
2
4
order(4, 2)
2
5
order(11, 0)
2
6
order(14, 1)
1
7
checkWaitingRiders(18)
1
8
order(19, 2)
2
9
order(20, 2)
1
10
order(22, 2)
2
11
checkWaitingRiders(37)
2
Order 1] After executing init(), the locations of the restaurant (Blue), houses of customers (Red), and delivery riders (Yellow) are shown on the coordinate plane as below. The number beside the image is the ID.
[Fig. 4]
Order 2] When the time is at 1, there are 3 delivery riders standing by.
Order 3] When Customer 1 orders food at Time 2, one of the three staff standing by will be assigned the order. The assigned staff will call Rider 0 who is nearest to the restaurant and prepare the food. As there are two staff standing by, return 2.
Order 4] At Time 4, Rider 0 arrives at the restaurant and picks up the food. Then the rider starts delivering
the food to Customer 1’s house.
The status of the staff who handed the food over to the rider turns into standby status.
As Customer 2 ordered food, one staff is assigned again. The assigned staff will contact Rider 2,
the nearest to the restaurant among the riders standing by. Two staff members are standing by.
Order 5] At Time 11, Rider 0 stands by after arriving at Customer 1’s house.
As Customer 0 ordered food, search for the nearest rider standing by.
As the distance of Rider 0 and that of Rider 1 to the restaurant are the same at 7,
contact Rider 0 whose ID is smaller than the other.
Order 6] At Time 12, Rider 2 stands by after arriving at Customer 2’s house.
At Time 14, Customer 1 places an order and one of the staff standing by contacts Rider 2.
As there is one staff standing by, return 1.
Order 7] At Time 18, only Rider 1 is standing by.
Order 8] At Time 19, Customer 2 places an order and one of the staff standing by contacts Rider 1.
Order 9] At Time 20, Customer 2 places an order and one of the staff standing by contacts Rider 0.
Order 10] At Time 22, Customer 2 places an order.
However, one of the staff standing by looks for a rider standing by but can’t.
Thus, the status of the staff returns to standby and the order remains in the waiting list.
Considering the number of staff standing by, 2 is returned.
Order 11] At Time 37, Rider 2 is still delivering the food. Thus, there are two riders standing by.
12
order(51, 0)
2
13
order(52, 0)
1
14
order(53, 0)
0
15
order(54, 1)
0
16
order(55, 2)
0
17
checkWaitingRiders(66)
2
18
checkWaitingRiders(67)
3
Order 12~14] At Time 53, all staff are assigned an order. Thus, there is NO staff standing by.
Order 15~16] Although orders are placed at Time 54 and 55, as there is no staff to fulfill the order, the orders are listed in the waiting list.
Order 17] At Time 66, two riders finished delivery and are in standby status aside from Rider 0 who is delivering the food of Order 15.
Order 18] At Time 67, all the deliveries are completed. Thus, three riders are standing by.
[Constraints]
1. init() function is called in the beginning of each test case.
2. For each test case, the number of calls of order() functions is less or equal to 20,000.
3. For each test case, the number of calls of checkWaitingRiders() functions is less or equal to 20,000.
4. For each test case, the value of mTimeStamp, which is given every time a function is called, increases.
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
extern void init(int N, int U, int uX[], int uY[],
int R, int rX[], int rY[]);
extern int order(int mTimeStamp, int uID);
extern int checkWaitingRiders(int mTimeStamp);
#define CMD_INIT 100
#define CMD_ORDER 200
#define CMD_CHECK_WAITING_RIDERS 300
#define MAX_USER 500
#define MAX_RIDER 2000
static int ux[MAX_USER];
static int uy[MAX_USER];
static int rx[MAX_RIDER];
static int ry[MAX_RIDER];
static bool run()
{
int query_num;
scanf("%d", &query_num);
int N, U, R;
int mTimeStamp, uID;
int ret, ans;
bool ok = false;
for (int q = 0; q < query_num; q++)
{
int query;
scanf("%d", &query);
if (query == CMD_INIT)
{
scanf("%d %d %d", &N, &U, &R);
for (int i = 0; i < U; i++)
scanf("%d", &ux[i]);
for (int i = 0; i < U; i++)
scanf("%d", &uy[i]);
for (int i = 0; i < R; i++)
scanf("%d", &rx[i]);
for (int i = 0; i < R; i++)
scanf("%d", &ry[i]);
init(N, U, ux, uy, R, rx, ry);
ok = true;
}
else if (query == CMD_ORDER)
{
scanf("%d %d", &mTimeStamp, &uID);
ret = order(mTimeStamp, uID);
scanf("%d", &ans);
if (ret != ans)
{
ok = false;
}
}
else if (query == CMD_CHECK_WAITING_RIDERS)
{
scanf("%d", &mTimeStamp);
ret = checkWaitingRiders(mTimeStamp);
scanf("%d", &ans);
if (ret != ans)
{
ok = false;
}
}
}
return ok;
}
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;
}
void init(int N, int U, int uX[], int uY[],
int R, int rX[], int rY[])
{
}
int order(int mTimeStamp, int uID)
{
return -1;
}
int checkWaitingRiders(int mTimeStamp)
{
return -1;
}
25 100
18
100 3 3 3
1 3 5
1 4 0
1 4 2
1 3 1
300 1 3
200 2 1 2
200 4 2 2
200 11 0 2
200 14 1 1
300 18 1
200 19 2 2
200 20 2 1
200 22 2 2
300 37 2
200 51 0 2
200 52 0 1
200 53 0 0
200 54 1 0
200 55 2 0
300 66 2
300 67 3
10
100 3 3 3
3 2 1
10 2 8
3 0 2
4 6 10
200 6 2 2
200 29 1 2
200 67 0 2
200 127 1 2
300 149 3
300 186 3
200 220 1 2
200 295 1 2
200 354 2 2
30
100 1 5 5
12 23 4 41 29
44 8 27 40 24
0 27 14 31 28
46 2 9 44 40
200 25 2 0
200 62 3 0
200 92 2 0
200 163 2 0
300 185 4
300 220 4
300 288 5
200 298 1 0
300 377 5
300 457 5
300 466 5
200 545 2 0
300 622 5
300 670 5
200 712 1 0
300 741 4
200 817 1 0
200 850 0 0
300 876 3
300 889 4
300 948 4
300 1024 5
300 1098 5
300 1107 5
300 1168 5
200 1184 2 0
300 1256 5
200 1277 0 0
200 1297 2 0
30
100 5 10 1
37 22 15 18 13 22 2 25 5 48
15 49 37 27 41 27 20 29 4 2
38
0
200 29 4 4
200 95 7 5
200 149 8 4