시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 3 3 100.000%

문제

상범 마법 팬케이크 하우스의 요리사는 가끔씩 팬케이크를 만들다가 잠에 빠진다. 그래서 쌓아둔 팬케이크의 한쪽이 종종 타버린다. 명백하게 탄 팬케이크를 서빙하는 건 좋은 생각이 아니다. 서빙하기 전에 웨이트리스는 팬케이크 더미를 배치해서 타버린 쪽이 아래를 향하도록 할 것이다. 또, 가장 위에는 크기가 제일 작은 팬케이크를, 가장 아래에는 크기가 제일 큰 팬케이크를 놓아 크기 순으로 정렬을 하려고 한다. 웨이트리스를 도와 올바르게 팬케이크를 쌓는 프로그램을 작성하시오.

우리는 한쪽면이 타버린 N개의 팬케이크 더미를 뒤집어야 한다. 우리가 위에서부터 k개의 팬케이크를 하나의 단위로 뒤집으면 맨 위에 있던 팬케이크는 k번째로 들어가고, k번째에 있던 팬케이크는 맨 위로 올라오게 된다.

예를 들면 다음과 같다.(+는 바닥이 탄 것, -는 위가 탄 것, 숫자는 팬케이크의 크기)

+1 -3 -2 [flip 2] => +3 -1 -2 [flip 1] => -3 -1 -2 [flip 3] => +2 +1 +3 [flip 1] => -2 +1 +3 [flip 2] => -1 +2 +3 [flip 1] => +1 +2 +3

최대 3n-2 번의 뒤집기(flip)한 수열을 찾는 프로그램을 만들어야 한다.

(수열의 처음과 마지막은 처음 주어진 상태와 아래가 모두 탄 팬케이크로 만든 상태가 된다)

입력

첫 줄에 테스트 케이스의 수 N이 입력으로 들어온다. 다음 N줄에는 각각의 줄에 팬케이크 수 M, 과 팬케이크의 크기(1~M)이 섞인 순서로 +또는 -부호를 달고 한번씩 등장한다. (M ≤ 30)

출력

각각의 케이스에 대해 한 줄씩 출력한다. 뒤집는 횟수 K(≥0), 한 번에 뒤집어야 하는 케이크 더미의 수 K개를 공백으로 구분하여 출력한다. 하나의 케이스에 대해 여러 개의 답이 존재할 수 있다. (예로 든 문제에서 3 2 3 또한 답이 될 수 있다.)

예제 입력 1

3
3 +1 -3 -2
4 -3 +1 -2 -4
5 +1 +2 +3 +4 -5

예제 출력 1

6 2 1 3 1 2 1
6 4 1 4 3 1 2
3 5 1 5

힌트

W3sicHJvYmxlbV9pZCI6IjI3MTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWJjOTQgXHViOWM4XHViYzk1IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2YyBcdWQ1NThcdWM2YjBcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzBjMVx1YmM5NCBcdWI5YzhcdWJjOTUgXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjIFx1ZDU1OFx1YzZiMFx1YzJhNFx1Yzc1OCBcdWM2OTRcdWI5YWNcdWMwYWNcdWIyOTQgXHVhYzAwXHViMDU0XHVjNTI5IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWIyZTRcdWFjMDAgXHVjN2EwXHVjNWQwIFx1YmU2MFx1YzljNFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YzMxM1x1YzU0NFx1YjQ1NCBcdWQzMmNcdWNmMDBcdWM3NzRcdWQwNmNcdWM3NTggXHVkNTVjXHVjYWJkXHVjNzc0IFx1Yzg4NVx1Yzg4NSBcdWQwYzBcdWJjODRcdWI5YjBcdWIyZTQuIFx1YmE4NVx1YmMzMVx1ZDU1OFx1YWM4YyBcdWQwYzQgXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1YzExY1x1YmU1OVx1ZDU1OFx1YjI5NCBcdWFjNzQgXHVjODhiXHVjNzQwIFx1YzBkZFx1YWMwMVx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1YzExY1x1YmU1OVx1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHVjNmU4XHVjNzc0XHVkMmI4XHViOWFjXHVjMmE0XHViMjk0IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2YyBcdWIzNTRcdWJiZjhcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTc0XHVjMTFjIFx1ZDBjMFx1YmM4NFx1YjliMCBcdWNhYmRcdWM3NzQgXHVjNTQ0XHViNzk4XHViOTdjIFx1ZDVhNVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI2MTAsIFx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDBcdWIyOTQgXHVkMDZjXHVhZTMwXHVhYzAwIFx1YzgxY1x1Yzc3YyBcdWM3OTFcdWM3NDAgXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjLCBcdWFjMDBcdWM3YTUgXHVjNTQ0XHViNzk4XHVjNWQwXHViMjk0IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWM4MWNcdWM3N2MgXHVkMDcwIFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyBcdWIxOTNcdWM1NDQgXHVkMDZjXHVhZTMwIFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWM3NDQgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNmU4XHVjNzc0XHVkMmI4XHViOWFjXHVjMmE0XHViOTdjIFx1YjNjNFx1YzY0MCBcdWM2MmNcdWJjMTRcdWI5NzRcdWFjOGMgXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1YzMxM1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2YjBcdWI5YWNcdWIyOTQgXHVkNTVjXHVjYWJkXHViYTc0XHVjNzc0IFx1ZDBjMFx1YmM4NFx1YjliMCBOXHVhYzFjXHVjNzU4IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2YyBcdWIzNTRcdWJiZjhcdWI5N2MgXHViNGE0XHVjOWQxXHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNmIwXHViOWFjXHVhYzAwIFx1YzcwNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBrXHVhYzFjXHVjNzU4IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyBcdWQ1NThcdWIwOThcdWM3NTggXHViMmU4XHVjNzA0XHViODVjIFx1YjRhNFx1YzlkMVx1YzczY1x1YmE3NCBcdWI5ZTggXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjM1OCBcdWQzMmNcdWNmMDBcdWM3NzRcdWQwNmNcdWIyOTQga1x1YmM4OFx1YzlmOFx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDBcdWFjZTAsIGtcdWJjODhcdWM5ZjhcdWM1ZDAgXHVjNzg4XHViMzU4IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1YjI5NCBcdWI5ZTggXHVjNzA0XHViODVjIFx1YzYyY1x1Yjc3Y1x1YzYyNFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC4oK1x1YjI5NCBcdWJjMTRcdWIyZTVcdWM3NzQgXHVkMGM0IFx1YWM4MywgLVx1YjI5NCBcdWM3MDRcdWFjMDAgXHVkMGM0IFx1YWM4MywgXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yzc1OCBcdWQwNmNcdWFlMzApPFwvcD5cclxuPHA+XHJcblx0KzEgLTMgLTIgW2ZsaXAgMl0gPSZndDsgKzMgLTEgLTIgW2ZsaXAgMV0gPSZndDsgLTMgLTEgLTIgW2ZsaXAgM10gPSZndDsgKzIgKzEgKzMgW2ZsaXAgMV0gPSZndDsgLTIgKzEgKzMgW2ZsaXAgMl0gPSZndDsgLTEgKzIgKzMgW2ZsaXAgMV0gPSZndDsgKzEgKzIgKzM8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjZDVjXHViMzAwIDNuLTIgXHViYzg4XHVjNzU4IFx1YjRhNFx1YzlkMVx1YWUzMChmbGlwKVx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdChcdWMyMThcdWM1ZjRcdWM3NTggXHVjYzk4XHVjNzRjXHVhY2ZjIFx1YjljOFx1YzljMFx1YjljOVx1Yzc0MCBcdWNjOThcdWM3NGMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzBjMVx1ZDBkY1x1YzY0MCBcdWM1NDRcdWI3OThcdWFjMDAgXHViYWE4XHViNDUwIFx1ZDBjNCBcdWQzMmNcdWNmMDBcdWM3NzRcdWQwNmNcdWI4NWMgXHViOWNjXHViNGUwIFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWI0MWNcdWIyZTQpPFwvcD5cclxuXHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjIFx1YzIxOCBNLCBcdWFjZmMgXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjXHVjNzU4IFx1ZDA2Y1x1YWUzMCgxfk0pXHVjNzc0IFx1YzExZVx1Yzc3OCBcdWMyMWNcdWMxMWNcdWI4NWMgK1x1YjYxMFx1YjI5NCAtXHViZDgwXHVkNjM4XHViOTdjIFx1YjJlY1x1YWNlMCBcdWQ1NWNcdWJjODhcdWM1MjkgXHViNGYxXHVjN2E1XHVkNTVjXHViMmU0LiAoTSAmbGU7IDMwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDU1YyBcdWM5MDRcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI0YTRcdWM5ZDFcdWIyOTQgXHVkNjlmXHVjMjE4IEsoJmdlOzApLCBcdWQ1NWMgXHViYzg4XHVjNWQwIFx1YjRhNFx1YzlkMVx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjZjAwXHVjNzc0XHVkMDZjIFx1YjM1NFx1YmJmOFx1Yzc1OCBcdWMyMTggS1x1YWMxY1x1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHViMDk4XHVjNzU4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWM2MDhcdWI4NWMgXHViNGUwIFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyAzIDIgMyBcdWI2MTBcdWQ1NWMgXHViMmY1XHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0Lik8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzE1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmxpcHBpbmcgQnVybmVkIFBhbmNha2VzICIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGNvb2sgYXQgdGhlIEZyb2Jib3p6IE1hZ2ljIFBhbmNha2UgSG91c2Ugc29tZXRpbWVzIGZhbGxzIGFzbGVlcCBvbiB0aGUgam9iIHdoaWxlIGNvb2tpbmcgcGFuY2FrZXMuIEFzIGEgcmVzdWx0LCBvbmUgc2lkZSBvZiBhIHN0YWNrIG9mIHBhbmNha2VzIGlzIG9mdGVuIGJ1cm5lZC4gQ2xlYXJseSwgaXQgaXMgYmFkIGJ1c2luZXNzIHRvIHNlcnZlIHZpc2libHkgYnVybmVkIHBhbmNha2VzIHRvIHRoZSBwYXRyb25zLiBCZWZvcmUgc2VydmluZywgdGhlIHdhaXRyZXNzIHdpbGwgYXJyYW5nZSB0aGUgc3RhY2tzIG9mIHBhbmNha2VzIHNvIHRoYXQgdGhlIGJ1cm5lZCBzaWRlcyBhcmUgZmFjaW5nIGRvd24uIFlvdSBtdXN0IHdyaXRlIGEgcHJvZ3JhbSB0byBhaWQgdGhlIHdhaXRyZXNzIGluIHN0YWNraW5nIHRoZSBwYW5jYWtlcyBjb3JyZWN0bHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIHN0YXJ0IHdpdGggYSBzdGFjayBvZiBOIHBhbmNha2VzIG9mIGRpc3RpbmN0IHNpemVzLCBlYWNoIG9mIHdoaWNoIGlzIGJ1cm5lZCBvbiBvbmUgc2lkZS4gVGhlIHByb2JsZW0gaXMgdG8gY29udmVydCB0aGUgc3RhY2sgdG8gb25lIGluIHdoaWNoIHRoZSBwYW5jYWtlcyBhcmUgaW4gc2l6ZSBvcmRlciB3aXRoIHRoZSBzbWFsbGVzdCBvbiB0aGUgdG9wIGFuZCB0aGUgbGFyZ2VzdCBvbiB0aGUgYm90dG9tIGFuZCBidXJuZWQgc2lkZSBkb3duIGZvciBlYWNoIHBhbmNha2UuIFRvIGRvIHRoaXMsIHdlIGFyZSBhbGxvd2VkIHRvIGZsaXAgdGhlIHRvcCBrIHBhbmNha2VzIG92ZXIgYXMgYSB1bml0IChzbyB0aGUgay10aCBwYW5jYWtlIGlzIG5vdyBvbiB0b3AgYW5kIHRoZSBwYW5jYWtlIHByZXZpb3VzbHkgb24gdG9wIGlzIG5vdyBpbiB0aGUgay10aCBwb3NpdGlvbiBhbmQgdGhlIGJ1cm5lZCBzaWRlIGdvZXMgZnJvbSB0b3AgdG8gYm90dG9tIGFuZCB2aWNlIHZlcnNhKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUgKCsgaW5kaWNhdGVzIGJ1cm5lZCBib3R0b20sIC0gYSBidXJuZWQgdG9wKTombmJzcDs8XC9wPlxyXG5cclxuPHA+KzEgLTMgLTIgW2ZsaXAgMl0gJnJBcnI7ICszIC0xIC0yIFtmbGlwIDFdICZyQXJyOyAtMyAtMSAtMiBbZmxpcCAzXSAmckFycjs8YnIgXC8+XHJcbisyICsxICszIFtmbGlwIDFdICZyQXJyOyAtMiArMSArMyBbZmxpcCAyXSAmckFycjsgLTEgKzIgKzMgW2ZsaXAgMV0gJnJBcnI7ICsxICsyICszJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBtdXN0IHdyaXRlIGEgcHJvZ3JhbSB3aGljaCBmaW5kcyBhIHNlcXVlbmNlIG9mIGF0IG1vc3QgKDNuICZuZGFzaDsgMikgZmxpcHMsIHdoaWNoIGNvbnZlcnRzIGEgZ2l2ZW4gc3RhY2sgb2YgcGFuY2FrZXMgdG8gYSBzb3J0ZWQgc3RhY2sgd2l0aCBidXJuZWQgc2lkZXMgZG93bi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBkZWNpbWFsIGludGVnZXIsIE4sIHRoZSBudW1iZXIgb2YgcHJvYmxlbSBpbnN0YW5jZXMgdG8gZm9sbG93LiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBnaXZlcyBhIHNlcGFyYXRlIGRhdGFzZXQgYXMgYSBzZXF1ZW5jZSBvZiBudW1iZXJzIHNlcGFyYXRlZCBieSBzcGFjZXMuIFRoZSBmaXJzdCBudW1iZXIgb24gZWFjaCBsaW5lIGdpdmVzIHRoZSBudW1iZXIsIE0sIG9mIHBhbmNha2VzIGluIHRoZSBkYXRhIHNldC4gVGhlIHJlbWFpbmRlciBvZiB0aGUgZGF0YSBzZXQgaXMgdGhlIG51bWJlcnMgMSB0aHJvdWdoIE0gaW4gc29tZSBvcmRlciwgZWFjaCB3aXRoIGEgcGx1cyBvciBtaW51cyBzaWduLCBnaXZpbmcgdGhlIGluaXRpYWwgcGFuY2FrZSBzdGFjay4gVGhlIG51bWJlcnMgaW5kaWNhdGUgdGhlIHJlbGF0aXZlIHNpemVzIG9mIHRoZSBwYW5jYWtlcyBhbmQgdGhlIHNpZ25zIGluZGljYXRlIHdoZXRoZXIgdGhlIGJ1cm5lZCBzaWRlIGlzIHVwICgtKSBvciBkb3duICgrKS4gTSB3aWxsIGJlLCBhdCBtb3N0LCAzMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCB5b3Ugc2hvdWxkIGdlbmVyYXRlIG9uZSBsaW5lIG9mIG91dHB1dCB3aXRoIHRoZSBmb2xsb3dpbmcgdmFsdWVzOiBUaGUgZGF0YXNldCBudW1iZXIgYXMgYSBkZWNpbWFsIGludGVnZXIgKHN0YXJ0IGNvdW50aW5nIGF0IG9uZSksIGEgc3BhY2UsIHRoZSBudW1iZXIgb2YgZmxpcHMgKEssIHdoZXJlIEsgJmd0Oz0gMCkgcmVxdWlyZWQgdG8gc29ydCB0aGUgcGFuY2FrZXMgYW5kIGEgc2VxdWVuY2Ugb2YgSyBudW1iZXJzLCBlYWNoIG9mIHdoaWNoIGdpdmVzIHRoZSBudW1iZXIgb2YgcGFuY2FrZXMgdG8gZmxpcCBvbiB0aGUgY29ycmVzcG9uZGluZyBzb3J0aW5nIHN0ZXAuIFRoZXJlIG1heSBiZSBzZXZlcmFsIGNvcnJlY3Qgc29sdXRpb25zIGZvciBzb21lIGRhdGFzZXRzLiBGb3IgaW5zdGFuY2UgMyAyIDMgaXMgYWxzbyBhIHNvbHV0aW9uIHRvIHRoZSBmaXJzdCBwcm9ibGVtIGJlbG93LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==