시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 28 19 9 64.286%

문제

학생들이 선생님을 중심으로 서로 마주보며 둥글게 앉아있다. 학생들은 각각 짝수개의 사탕을 가지고 있다. 선생님이 호루라기를 부는 순간 학생들은 자신의 오른쪽 학생에게 사탕의 반을 준다. 이때 학생들 중 홀수개의 사탕을 가지게 되는 학생들은 선생님으로부터 하나의 사탕을 더 받게 된다. 모든 학생들의 사탕의 개수가 같아지면 게임은 끝나게 된다.

선생님이 호루라기를 부는 횟수와 게임이 끝났을 때 한 학생이 받는 사탕의 개수를 구해보자.

입력

입력은 여러개의 게임으로 이루어져 있다. 각 게임의 첫 번째 줄에는 학생들의 수 N이 주어지며, 다음 N개에 줄에 시계방향 순으로 각 학생들이 가지고 있는 사탕의 개수가 한 줄에 하나씩 주어진다. 학생의 수 N이 0일 때 프로그램을 종료한다. N은 10만보다 작거나 같은 자연수이다.

출력

각 게임이 끝났을 때 라운드 수와 학생들이 가지고 있게 되는 사탕의 수를 공백으로 구분하여 출력한다.

예제 입력 1

6
36
2
2
2
2
2
11
22
20
18
16
14
12
10
8
6
4
2
4
2
4
6
8
0

예제 출력 1

15 14
17 22
4 8

힌트

게임은 무한히 진행되지 않는다. 그 이유는 4가지가 있는데, 각자 생각해 보자.

W3sicHJvYmxlbV9pZCI6IjI3NjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWQwZDUgXHViMDk4XHViMjA0XHVhZTMwIFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0NCBcdWM5MTFcdWMyZWNcdWM3M2NcdWI4NWMgXHVjMTFjXHViODVjIFx1YjljOFx1YzhmY1x1YmNmNFx1YmE3MCBcdWI0NjVcdWFlMDBcdWFjOGMgXHVjNTQ5XHVjNTQ0XHVjNzg4XHViMmU0LiBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVhYzAxXHVhYzAxIFx1YzlkZFx1YzIxOFx1YWMxY1x1Yzc1OCBcdWMwYWNcdWQwZDVcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzc0IFx1ZDYzOFx1YjhlOFx1Yjc3Y1x1YWUzMFx1Yjk3YyBcdWJkODBcdWIyOTQgXHVjMjFjXHVhYzA0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkIFx1ZDU1OVx1YzBkZFx1YzVkMFx1YWM4YyBcdWMwYWNcdWQwZDVcdWM3NTggXHViYzE4XHVjNzQ0IFx1YzkwMFx1YjJlNC4gXHVjNzc0XHViNTRjIFx1ZDU1OVx1YzBkZFx1YjRlNCBcdWM5MTEgXHVkNjQwXHVjMjE4XHVhYzFjXHVjNzU4IFx1YzBhY1x1ZDBkNVx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjOGMgXHViNDE4XHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWMxMjBcdWMwZGRcdWIyZDhcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzBhY1x1ZDBkNVx1Yzc0NCBcdWIzNTQgXHViYzFiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWMwYWNcdWQwZDVcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YWMxOVx1YzU0NFx1YzljMFx1YmE3NCBcdWFjOGNcdWM3ODRcdWM3NDAgXHViMDVkXHViMDk4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMTIwXHVjMGRkXHViMmQ4XHVjNzc0IFx1ZDYzOFx1YjhlOFx1Yjc3Y1x1YWUzMFx1Yjk3YyBcdWJkODBcdWIyOTQgXHVkNjlmXHVjMjE4XHVjNjQwIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwYWNcdWM3NDQgXHViNTRjIFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViYzFiXHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWFjOGNcdWM3ODRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1YzVkMCBcdWM5MDRcdWM1ZDAgXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDEgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjMGFjXHVkMGQ1XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCAwXHVjNzdjIFx1YjU0YyBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjODg1XHViOGNjXHVkNTVjXHViMmU0LiBOXHVjNzQwIDEwXHViOWNjXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWFjOGNcdWM3ODRcdWM3NzQgXHViMDVkXHViMGFjXHVjNzQ0IFx1YjU0YyBcdWI3N2NcdWM2YjRcdWI0ZGMgXHVjMjE4XHVjNjQwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVhYzhjIFx1YjQxOFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHRcdWFjOGNcdWM3ODRcdWM3NDAgXHViYjM0XHVkNTVjXHVkNzg4IFx1YzljNFx1ZDU4OVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YWRmOCBcdWM3NzRcdWM3MjBcdWIyOTQgNFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YWMwMVx1Yzc5MCBcdWMwZGRcdWFjMDFcdWQ1NzQgXHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjc2NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNhbmR5IFNoYXJpbmcgR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+QSBudW1iZXIgb2Ygc3R1ZGVudHMgc2l0IGluIGEgY2lyY2xlIGZhY2luZyB0aGVpciB0ZWFjaGVyIGluIHRoZSBjZW50ZXIuIEVhY2ggc3R1ZGVudCBpbml0aWFsbHkgaGFzIGFuIGV2ZW4gbnVtYmVyIG9mIHBpZWNlcyBvZiBjYW5keS4gV2hlbiB0aGUgdGVhY2hlciBibG93cyBhIHdoaXN0bGUsIGVhY2ggc3R1ZGVudCBzaW11bHRhbmVvdXNseSBnaXZlcyBoYWxmIG9mIGhpcyBvciBoZXIgY2FuZHkgdG8gdGhlIG5laWdoYm9yIG9uIHRoZSByaWdodC4gQW55IHN0dWRlbnQsIHdobyBlbmRzIHVwIHdpdGggYW4gb2RkIG51bWJlciBvZiBwaWVjZXMgb2YgY2FuZHksIGlzIGdpdmVuIGFub3RoZXIgcGllY2UgYnkgdGhlIHRlYWNoZXIuIFRoZSBnYW1lIGVuZHMgd2hlbiBhbGwgc3R1ZGVudHMgaGF2ZSB0aGUgc2FtZSBudW1iZXIgb2YgcGllY2VzIG9mIGNhbmR5LjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gd2hpY2ggZGV0ZXJtaW5lcyB0aGUgbnVtYmVyIG9mIHRpbWVzIHRoZSB0ZWFjaGVyIGJsb3dzIHRoZSB3aGlzdGxlIGFuZCB0aGUgZmluYWwgbnVtYmVyIG9mIHBpZWNlcyBvZiBjYW5keSBmb3IgZWFjaCBzdHVkZW50IGZyb20gdGhlIGFtb3VudCBvZiBjYW5keSBlYWNoIGNoaWxkIHN0YXJ0cyB3aXRoLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IG1heSBkZXNjcmliZSBtb3JlIHRoYW4gb25lIGdhbWUuIEZvciBlYWNoIGdhbWUsIHRoZSBpbnB1dCBiZWdpbnMgd2l0aCB0aGUgbnVtYmVyIE4gb2Ygc3R1ZGVudHMsIGZvbGxvd2VkIGJ5IE4gKGV2ZW4pIGNhbmR5IGNvdW50cyBmb3IgdGhlIGNoaWxkcmVuIGNvdW50ZXItY2xvY2t3aXNlIGFyb3VuZCB0aGUgY2lyY2xlLiBUaGUgaW5wdXQgZW5kcyB3aXRoIGEgc3R1ZGVudCBjb3VudCBvZiAwLiBFYWNoIGlucHV0IG51bWJlciBpcyBvbiBhIGxpbmUgYnkgaXRzZWxmLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGdhbWUsIG91dHB1dCB0aGUgbnVtYmVyIG9mIHJvdW5kcyBvZiB0aGUgZ2FtZSBmb2xsb3dlZCBieSB0aGUgYW1vdW50IG9mIGNhbmR5IGVhY2ggY2hpbGQgZW5kcyB1cCB3aXRoLCBib3RoIG9uIG9uZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgZ2FtZSBlbmRzIGluIGEgZmluaXRlIG51bWJlciBvZiBzdGVwcyBiZWNhdXNlOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlRoZSBtYXhpbXVtIGNhbmR5IGNvdW50IGNhbiBuZXZlciBpbmNyZWFzZS48XC9saT5cclxuXHQ8bGk+VGhlIG1pbmltdW0gY2FuZHkgY291bnQgY2FuIG5ldmVyIGRlY3JlYXNlLjxcL2xpPlxyXG5cdDxsaT5ObyBvbmUgd2l0aCBtb3JlIHRoYW4gdGhlIG1pbmltdW0gYW1vdW50IHdpbGwgZXZlciBkZWNyZWFzZSB0byB0aGUgbWluaW11bS48XC9saT5cclxuXHQ8bGk+SWYgdGhlIG1heGltdW0gYW5kIG1pbmltdW0gY2FuZHkgY291bnQgYXJlIG5vdCB0aGUgc2FtZSwgYXQgbGVhc3Qgb25lIHN0dWRlbnQgd2l0aCB0aGUgbWluaW11bSBhbW91bnQgbXVzdCBoYXZlIHRoZWlyIGNvdW50IGluY3JlYXNlPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==