IOI '13 P5 - Robots - Olympiads Online Judge

IOI '13 P5 - Robots

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 2.5s

Memory limit: 64M

Problem type

Allowed languages

C, C++

Marita's little brother has left toys all over the living room floor! Fortunately, Marita has developed special robots to clean up the toys. She needs your help to determine which robots should pick up which toys.

There are $T$ ~T~ toys, each with an integer weight $W[i]$ ~W[i]~ and an integer size $S[i]$ ~S[i]~. Robots come in two kinds: weak and small.

There are $A$ ~A~ weak robots. Each weak robot has a weight limit $X[i]$ ~X[i]~, and can carry any toy of weight strictly less than $X[i]$ ~X[i]~. The size of the toy does not matter.
There are $B$ ~B~ small robots. Each small robot has a size limit $Y[i]$ ~Y[i]~, and can carry any toy of size strictly less than $Y[i]$ ~Y[i]~. The weight of the toy does not matter.

Each of Marita's robots takes one minute to put each toy away. Different robots can put away different toys at the same time.

Your task is to determine whether Marita's robots can put all the toys away, and if so, the shortest time in which they can do this.

Examples

As a first example, suppose there are $A = 3$ ~A = 3~ weak robots with weight limits $X = [6, 2, 9]$ ~X = [6, 2, 9]~, $B = 2$ ~B = 2~ small robots with size limits $Y = [4, 7]$ ~Y = [4, 7]~, and $T = 10$ ~T = 10~ toys as follows:

Toy number	0	1	2	3	4	5	6	7	8	9
Weight	4	8	2	7	1	5	3	8	7	10
Size	6	5	3	9	8	1	3	7	6	5

The shortest time to put all the toys away is three minutes:

	Weak robot 0	Weak robot 1	Weak robot 2	Small robot 0	Small robot 1
First minute	Toy 0	Toy 4	Toy 1	Toy 6	Toy 2
Second minute	Toy 5		Toy 3		Toy 8
Third minute			Toy 7		Toy 9

As a second example, suppose there are $A = 2$ ~A = 2~ weak robots with weight limits $X = [2, 5]$ ~X = [2, 5]~, $B = 1$ ~B = 1~ small robot with size limit $Y = [2]$ ~Y = [2]~, and $T = 3$ ~T = 3~ toys as follows:

Toy number	0	1	2
Weight	3	5	2
Size	1	3	2

Implementation

You should submit a file implementing the function putaway() as follows:

Your Function: `putaway()`

C/C++

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]);

Pascal

function putaway(A, B, T : LongInt; var X, Y, W, S : array of LongInt) : LongInt;

Description

This function should calculate the smallest number of minutes required for the robots to put all of the toys away, or should return $-1$ ~-1~ if this is not possible.

Parameters

$A$ ~A~: The number of weak robots.
$B$ ~B~: The number of small robots.
$T$ ~T~: The number of toys.
$X$ ~X~: An array of length $A$ ~A~ containing integers that specify the weight limit for each weak robot.
$Y$ ~Y~: An array of length $B$ ~B~ containing integers that specify the size limit for each small robot.
$W$ ~W~: An array of length $T$ ~T~ containing integers that give the weight of each toy.
$S$ ~S~: An array of length $T$ ~T~ containing integers that give the size of each toy.
Returns: The smallest number of minutes required to put all of the toys away, or $-1$ ~-1~ if this is not possible.

Sample Session

The following session describes the first example above:

Parameter	Value
A	`3`
B	`2`
T	`10`
X	`{6, 2, 9}`
Y	`{4, 7}`
W	`{4, 8, 2, 7, 1, 5, 3, 8, 7, 10}`
S	`{6, 5, 3, 9, 8, 1, 3, 7, 6, 5}`
Returns	`3`

The following session describes the second example above:

Parameter	Value
A	`2`
B	`1`
T	`3`
X	`{2, 5}`
Y	`{2}`
W	`{3, 5, 2}`
S	`{1, 3, 2}`
Returns	`-1`

Constraints

$1 \le T \le 1\,000\,000$ ~1 \le T \le 1\,000\,000~
$0 \le A, B \le 50\,000$ ~0 \le A, B \le 50\,000~ and $1 \le A + B$ ~1 \le A + B~
$1 \le X[i], Y[i], W[i], S[i] \le 2\,000\,000\,000$

Subtasks

Subtask	Points	Additional Input Constraints
1	14	$T = 2$ ~T = 2~ and $A + B = 2$ ~A + B = 2~ (exactly two toys and two robots)
2	14	$B = 0$ ~B = 0~ (all robots are weak)
3	25	$T \le 50$ ~T \le 50~ and $A + B \le 50$ ~A + B \le 50~
4	37	$T = 10\,000$ ~T = 10\,000~ and $A + B \le 1\,000$ ~A + B \le 1\,000~
5	10	None

Comments

There are no comments at the moment.