Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.
Arranging Time Table
You have started working in North West Tirana
high school. And, you have to arrange the time tables.
There are classrooms with different sizes and several
different student classes with different number of
students. A student class may be assigned to a
classroom, if the number of students in the class
is less than or equal to the classroom capacity.
For example, if there are 25 students in a class, it
can be assigned to classroom with the capacity 27,
but it can not be assigned to a classroom with the
capacity 24.
Question:
Write a program that is going to get information for n
classrooms and k student classes. And then, it will show
the possible placements.
Input specification
In the first line, you will be given two integers: The
number of classrooms(n) and the number of student classes(k),
where 0 ≤ k ≤ n ≤ 15.
In the following line, you will be given n integers:
the capacities of n classrooms. And in the following line,
you will be given k integers: number of students in k classes.
Output specification:
In the first line, show total number of possible
classroom arrangements (nRes). Then in the following nRes
lines, show nr of students and classroom capacity pairs
such that all student classes are assigned to classrooms
where every pair is followed by a semicolon. If there is no
possible placement, you print 0.
Note: There is no result (nRes) greater than
5,000.
Sample Input I
4 3
24 50 30 55
50 30 25
|
Sample Output I
4
50 50; 30 30; 25 55;
50 50; 25 30; 30 55;
30 50; 25 30; 50 55;
25 50; 30 30; 50 55;
|
Explanation:
There are 4 possible arrangements.
- Class with 52 students can be assigned to classroom with the capacity 55
- Class with 25 students can be assigned to classroom with the capacity 50
- Class with 30 students can be assigned to classroom with the capacity 30
And, there are 3 other class to classroom arrangements.
Для отправки решений необходимо выполнить вход.
|