레이팅 미적용농장의 삶은 고달프고, 삶이 고달플 때는 강해져야 한다. 소들은 갱단을 결성했다 (편의상 1부터 M까지 번호가 붙어 있다). 갱단들은 한동안 평화롭게 공존했지만, 이제 상황이 정말 걷잡을 수 없게 되었다!
소들은 거대한 방목지의 지배권을 두고 다투고 있다. 이 다툼은 여러 분에 걸쳐 일어난다. 매 분마다 소 한 마리가 방목지에 들어온다. 방목지가 비어 있으면 새로 온 소의 갱단이 방목지를 지배하게 된다. 방목지가 이미 새로 온 소의 갱단의 지배 아래에 있으면, 그 소는 그냥 풀을 뜯기 시작한다. 그렇지 않으면, 풀을 뜯고 있던 지배 갱단의 소 한 마리가 새로 온 소와 맞선다. 이 대결에서 두 소는 모두 갱단과 방목지를 떠난다. 이 대결 후 방목지가 비게 되면 어떤 갱단도 방목지를 지배하지 않는다.
베시(Bessie)는 다툼이 끝나고 모든 소가 방목지에 있거나 떠난 후, 1번 갱단인 자신의 갱단이 방목지를 지배하기를 간절히 바란다. 베시의 갱단이 최종적으로 방목지를 지배하는 것이 가능한지 판정하는 것을 도와주자. 가능하다면, 베시는 마지막에 방목지에 남을 수 있는 자기 갱단 소의 최대 수와, 그 수를 달성하는 소들의 사전순으로 가장 앞서는 순서도 알고 싶어 한다.
첫째 줄: 공백으로 구분된 N (1 <= N <= 100)과 M (1 <= M <= N). 모든 갱단의 소의 총수는 N이다. 갱단의 총수는 M이다.
둘째 줄부터 1+M번째 줄까지: (1+i)번째 줄은 갱단 i의 구성원 수를 나타낸다. 각 갱단에는 적어도 1마리의 구성원이 있다.
첫째 줄: 다툼 후 베시의 갱단이 방목지를 지배할 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.
둘째 줄: YES라면, 방목지에 남을 수 있는 소의 최대 수.
셋째 줄부터 2+N번째 줄까지: YES라면, (i+2)번째 줄에 다툼 후 방목지에 최대 수의 소를 남기는 사전순으로 가장 앞서는 순서에서 i번째 분에 등장하는 소의 갱단 번호를 출력한다.
gangs.in · 출력을 쓸 파일 gangs.out5 3
2
1
2YES
1
1
3
2
3
1Input 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.
Output details: Only one cow from Bessie's gang can end up on the field.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > December > Gold