#371. [Usaco2012 Dec]Gangs of Istanbull
[Usaco2012 Dec]Gangs of Istanbull
Description
Life is tough on the farm, and when life is tough you have to get tough. The cows have formed gangs (conveniently numbered 1 to M). The gangs coexisted in peace for a while, but now things are really getting out of control! The cows are competing over control of a great grazing field. This conflict happens over a series of minutes. Each minute a single cow walks into the field. If the field is empty the new cow's gang is considered to take control of the field. If the field is already controlled by the new cow's gang then the cow just starts grazing. Otherwise, a single cow from the controlling gang that is grazing confronts the new cow. These confrontations between two cows start with some arguing and inevitably end up with the pair coming to realize how much more more alike than different they are. The cows, seeing the error in their ways, leave the gang and the field and get a cold glass of soy milk at FJ's tavern. If after this confrontation the field is empty than no gang controls the field. Bessie realizes how these confrontations will occur. She knows how many cows are in each gang. Bessie really wants her gang to control the field after the conflict is over and all cows are either on the field or at FJ's tavern. Help Bessie determine if it is possible for her gang, labeled 1, to control the field in the end. If it is possible, Bessie wants to know the maximum number of cows from her gang that could be on the field at the end. Output this number and the lexicographically earliest ordering of cows that results in this number of cows from Bessie's gang at the end. An ordering X is said to be lexicographically earlier than Y if there is some k such that X[k] < Y[k] and X[i] = Y[i] for i < k.
n头牛结成了m个帮派,现在它们争夺一块草地。每个单位时间内会有一头牛来。如果草地上还没有牛或者只有自己帮派的牛,他会留在这里。但如果已经有别的帮派的牛,它们会打一架,这使得当前牛和草地上的一头牛去找农夫思考人生。问如何安排来的牛的编号顺序,能使一 号帮派最后有最多的牛留在草地上,如果不为0,还要输出字典序最小的一组方案。
Format
Input
-
Line 1: N (1 <= N <= 100) and M (1 <= M <= N) separated by a space. The total number of cows in all the gangs will be N. The total number of gangs is M.
-
Lines 2..1+M: The (1+i)th line indicates how many members are in gang i. Each gang has at least 1 member.
Output
- Line 1: Output YES on a single line if Bessie's gang can control the field after the conflict. Otherwise output NO on a single line.
- Line 2: If Bessie's gang can control the field after the conflict output the maximum number of cows that could be on the field on a single line. * Lines 3..2+N: On the (i+2)th line output the index of the gang of the cow that appears in the ith minute in the lexicographically earliest ordering that leaves the maximum number of cows on the field after the conflict.
Samples
5 3
2
1
2
INPUT DETAILS: There are 5 cows and 3 gangs. Bessie's gang (gang 1) has 2 members, gang 2 has 1 member, and gang 3 has 2 members.
YES
1
1
3
2
3
1
`OUTPUT DETAILS: Only one cow from Bessie's gang can end up on the field.``