KOI 전국 2007 중1- 계란 > 문제은행 : 정보올림피아드&알고리즘



1977 : 계란

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
11 회   
시도횟수
51 회   

문제

네 개의 바구니에 계란이 나뉘어 담겨있다. 

우리는 아래에 제시된 단위 작업을 통하여 계란을 한 바구니에 모두 옮겨 담고자 한다.

 

• 계란이 하나 이상 들어 있는 두 개의 서로 다른 바구니 A, B를 선택한다.

• 선택된 각 바구니에서 계란을 하나씩 꺼내서 A, B가 아닌 다른 바구니에 이 두 개의 계란을 담는다.

 

예를 들어 바구니에 계란이 세 개, 한 개 담겨있다고 하자. 이 상태는 (3, 1, 0, 0)로 표시된다. 

그러면 이 상태에서 아래와 같은 세 번의 단위 작업으로 계란을 한 바구니에 모을 수 있다.

 

    (3,1,0,0) → (2,0,2,0) → (1,0,1,2) → (0,0,0,4)

 

괄호속의 숫자는 각 바구니에 들어있는 계란의 수를 표시한 것이다.

 

문제는 가능한 적은 횟수의 단위 작업을 사용하여 모든 계란을 한 곳에 모으는 것이다. 

여러분은 입력으로 받은 초기 바구니 상태에서 출발하여 

계란이 한 바구니에 모두 담기는 최종상태까지의 중간 단계를 차례대로 출력해야 한다.

 


입력형식

첫째 줄에는 채점의 기준이 되는 단위 작업의 사용 횟수 K가 주어진다.

그 다음 줄에는 각 바구니에 들어있는 계란의 수가 공백을 두고 나타난다. 

전체 계란의 수는 4개 이상, 3000개 이하이다.


출력형식

출력 파일의 첫줄에는 초기 바구니의 상태를 입력형식과 동일하게 출력해야 한다.

그 다음 줄부터는 각 단계별 바구니 상태를 하나씩 출력해야 한다. 

마지막 줄에는 반드시 한 바구니에 계란이 모두 모인 상태가 출력되어야 한다.


입력 예

4
3 1 0 0

출력 예

3 1 0 0
2 0 2 0
1 0 1 2
0 0 0 4


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP