Rainbow Sheep
Baa, baa, bright sheep,
Have you any wool?
Yes, sir, yes, sir,
n bags full;
Some coloured crazy,
and others rather lame,
But there's a single rule
That I must explain
Collect all the wool,
And colours you'll weigh.
The top take the bottom
should leave at most K.
You are a special lab made sheep called "Dolly" which grows rainbow wool. The local farmers and craftspeople in the town would like various colours of wool for their use, but because you grow all colours of wool at equal speeds, you can't give too much more of one colour than another.
In particular, every person would like exactly 1 "unit" of wool, and will only accept certain colours. For a particular colour , let be the units of wool of that colour given to people. You must have it so that for some constant . In other words, you cannot give more units of wool of one colour than some other colour.
For a particular selection of colours, what is the maximum number of people we can give wool to while still obeying the rules of colour distribution, and for this maximum number of people, what is the largest value of ?
Input
Input will begin with three space separate integers, , and . These are:
- The number of people that want wool
- The constant
- The number of colours
lines will follow, detailing the colour preferences of each of the people.
Each line will begin with a single integer , the number of colours this person accepts, and then the line will contain an additional space-separated integers, represent the colours that the th person accepts.
Output
Output should begin with a single integer , the maximum number of people the sheep can give a unit of wool to. Output should next contain lines, each containing two integers:
- The 1-index of the person to give wool
- The colour of the wool to give that person
This method of giving wool to each person should also maximise the minimum amount of any colour wool given out (Subject to the maximum total wool constraint already being followed).
Constraints
- The total number of preferences will not exceed
Test Set A (50% of the points)
- (So many aspects of the problem can be ignored!)
Test Set B (50% of the points)
Example 1
For input
6 1 3
1 1
2 1 2
3 1 2 3
2 1 2
1 1
1 1
A possible solution is
5
1 1
2 2
3 3
4 2
5 1
This way, the maximum number of units assigned per colour (2 people, achieved by colours 1 and 2), and the minimum number of units assigned per colour (1 person, achieved by colour 3), differ by at most .
Example 2
For input
6 6 3
1 1
2 1 2
3 1 2 3
2 1 2
1 1
1 1
A possible solution would not be:
5
1 1
2 1
3 1
4 1
5 1
While this is maximal in terms of wool given out, and does follow the rules of the problem, the value of (The minimum amount of a particular colour of wool is given) is . The solution to Example 1 shows we can give the same amount of wool out while having .
Comments