Problem B for Train 2
Задачу добавил: elena
Успешно сдано решений: 4
Problem B. Bureaucracy generator
Author: I. Ludov, A.Klenin
Input file: input.txt Time limit: 2 sec
Output file: output.txt Memory limit: 64 Mb
A large software company has started a new high-budget project — the game console platform called "Y-Sphere". The company is proud of its sophisticated development process standards, and has recently received a prestigious CMM (Capacity for Managers Maximization) certificate.
Using those powerful standards, it was easily calculated that the project will need precisely S developers. Now the only problem is how to manage them efficiently. Fortunately, CMM process has the answer: of course a proper management hierarchy is needed, that can be built by following few simple rules:
1. Each manager has managerial capacity — number of immediate subordinates he can control. He must be assigned to manage neither more (too difficult for him), nor less (not efficient enough).
2. Each manager's immediate subordinates must be either all managers (who in turn have their own subordinates), or all developers.
3. Each developer and manager has exactly one immediate superior manager, except a single highest level manager called Project Leader, who has none.
4. Each manager must have capacity strictly lower then his immediate superior (so that more qualified managers take higher positions in hierarchy).
The company has managers of N different capacities. It has unlimited number of managers of each capacity.
Your program must plan a proper management hierarchy or determine that it is impossible.
Input file format
Input contains two integers S N, followed by N different integers ai — available managerial capacities.
Output file format
Output must contain integer M — total count of required managers, who are numbered from 1 to M. Next must be M pairs of integers si ci, where si is the number of i-th manager's immediate superior (or zero for Project Leader), ci is capacity of i-th manager, taken from the list of available capacities. If the there is no solution, output a single number -1. If there is more than one solution, output any of them.
1 <= S, ai, ci <= 100, 1 <= N <= 10
Sample input 1
3 1 2
Sample output 1
Sample input 2
Sample output 2