Delivery robots' control (algorithm)
Budget: $10 – $30 USD
You need to write an algorithm for delivery robots' control (Python 3.7). There is a map N x N. A robot position in only one cell. Also, there are 2 types of cells: passable and not passable. For one second a robot can move to one of four directions (up, down, left, right), if the cell is passable.
At first, you need to output the number of robots you want to use and their coordinates. Each robot costs Cost dollars.
After that, there are T iterations of the simulation. One iteration is one virtual minute, which consists of 60 seconds. On each iteration, you will get the number of new orders, in response, your program needs to output what actions each robot does (60 actions for each robot).
For each successful delivery, you will get max(0, MaxTips – DeliveryTime) dollars, where MaxTips is the maximum amount of tips for one order, and DeliveryTime is the period of time from the appearance of an order to its delivery in seconds.
The total number of dollars you get for one test is TotalTips – R*Cost, where TotalTips is the amount of tips, R – the number of robots, Cost – the cost of one robot. Cost and MaxTips you will get in each test. If you earned less tips than you spent, the amount of earned dollars is 0. Also, you will get 0 for incorrect actions.
Input format:
For input reading, the program must use the standard input.
In the first input row, there are 3 numbers: N, MaxTips and Cost (N ≤ 2 000, MaxTips≤ 50 000, Costc≤ 109). N – is the size of a city, MaxTips – the maximum amount of tips, Cost – the cost of one robot. Then each of the next N rows contains N symbols – the map of the city. There are 2 types of symbols:
‘#’ – the cell is not passable.
‘.’ – the cell is passable.
Then you will get 2 natural numbers T and D D (T ≤ 100 000, D ≤ 10 000 000) – the number of iterations and the total number of orders.
After that, you need to output R – the number of robots you want. 1 <= R <= 100. Then output R pairs of integers from 1 to N – initial coordinates of the robots.
Then, on each of T iteration you will get the information about the orders. On each iteration you will get k – the number of new orders, then k rows with integers Srow, Scor, Frow, Fcol – coordinates of the beginning and ending cells of an order (1 ≤ Srow, Scol, Frow, Fcol ≤ N). New order can be placed in a cell where 1 or more orders are already placed. There is no time limit for delivery.
Output format:
The program should use the standard output.
On each iteration you should output the actions of each robot: R rows with 60 symbols each (one symbol – one action, 60 actions for each robot):
U – movement one cell up
L – movement one cell left
D – movement one cell down
R – movement one cell right
S – don’t move, do nothing
T – don’t move, take the oldest order in this cell
P – don’t move, give the order in this cell
Robots do their actions in order: the first robot does its first action, then the second robot does its first action, and so on to the last robot. Then the first robot does its second action and so on. After the last robot completes its last action, the iteration is over.
Multiple robots may be in the same cell.
The testing system allows your program to read the new data after you program requested it and did the operation “flush”.
Example:
Input:
4 20 10
....
....
....
....
7 7
1
1 1 4 4
1
1 4 4 1
1
4 4 1 1
0
4
1 2 4 4
2 2 3 3
2 1 4 4
2 2 4 4
0
0
Output:
1
4 4
UUULLLTDDDRRRPSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
UUUTLLLDDDPSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
RRRTUUULLLPSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
RTDDDRRPUULLLTDDRRRPSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
Also, additional examples are available (10 items)
At first, you need to output the number of robots you want to use and their coordinates. Each robot costs Cost dollars.
After that, there are T iterations of the simulation. One iteration is one virtual minute, which consists of 60 seconds. On each iteration, you will get the number of new orders, in response, your program needs to output what actions each robot does (60 actions for each robot).
For each successful delivery, you will get max(0, MaxTips – DeliveryTime) dollars, where MaxTips is the maximum amount of tips for one order, and DeliveryTime is the period of time from the appearance of an order to its delivery in seconds.
The total number of dollars you get for one test is TotalTips – R*Cost, where TotalTips is the amount of tips, R – the number of robots, Cost – the cost of one robot. Cost and MaxTips you will get in each test. If you earned less tips than you spent, the amount of earned dollars is 0. Also, you will get 0 for incorrect actions.
Input format:
For input reading, the program must use the standard input.
In the first input row, there are 3 numbers: N, MaxTips and Cost (N ≤ 2 000, MaxTips≤ 50 000, Costc≤ 109). N – is the size of a city, MaxTips – the maximum amount of tips, Cost – the cost of one robot. Then each of the next N rows contains N symbols – the map of the city. There are 2 types of symbols:
‘#’ – the cell is not passable.
‘.’ – the cell is passable.
Then you will get 2 natural numbers T and D D (T ≤ 100 000, D ≤ 10 000 000) – the number of iterations and the total number of orders.
After that, you need to output R – the number of robots you want. 1 <= R <= 100. Then output R pairs of integers from 1 to N – initial coordinates of the robots.
Then, on each of T iteration you will get the information about the orders. On each iteration you will get k – the number of new orders, then k rows with integers Srow, Scor, Frow, Fcol – coordinates of the beginning and ending cells of an order (1 ≤ Srow, Scol, Frow, Fcol ≤ N). New order can be placed in a cell where 1 or more orders are already placed. There is no time limit for delivery.
Output format:
The program should use the standard output.
On each iteration you should output the actions of each robot: R rows with 60 symbols each (one symbol – one action, 60 actions for each robot):
U – movement one cell up
L – movement one cell left
D – movement one cell down
R – movement one cell right
S – don’t move, do nothing
T – don’t move, take the oldest order in this cell
P – don’t move, give the order in this cell
Robots do their actions in order: the first robot does its first action, then the second robot does its first action, and so on to the last robot. Then the first robot does its second action and so on. After the last robot completes its last action, the iteration is over.
Multiple robots may be in the same cell.
The testing system allows your program to read the new data after you program requested it and did the operation “flush”.
Example:
Input:
4 20 10
....
....
....
....
7 7
1
1 1 4 4
1
1 4 4 1
1
4 4 1 1
0
4
1 2 4 4
2 2 3 3
2 1 4 4
2 2 4 4
0
0
Output:
1
4 4
UUULLLTDDDRRRPSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
UUUTLLLDDDPSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
RRRTUUULLLPSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
RTDDDRRPUULLLTDDRRRPSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
Also, additional examples are available (10 items)