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

문제

표준 휴대전화의 키패드에는 글자들이 다음과 같이 번호키와 대응되어있다.

글자 C를 입력하기 위해서는 '2'키를 3번 눌러야 한다. 이와 같이 글자를 입력하기 위해 눌러야 하는 키의 번호와 눌러야 하는 횟수는 글자가 어떤 키의 리스트에 속해있는가와 리스트에서 몇 번째인지에 따라 다르다.

Exupery Telephone Company (ETC)는 축적된 글자별 사용 빈도 데이터베이스를 이용하여 휴대전화 사용자들의 평균 키 입력 횟수를 줄이기 위해 글자 배치들을 변경하려고 한다. 예를 들어, S를 7키에서 8키로 옮길 수 있다. 

글자들이 나타나는 순서는 알파벳 순서를 지켜야 하지만 각 키마다 배정되는 글자의 수는 달라도 된다.

각 알파벳의 빈도수와 키의 개수가 주어졌을 때, 알파벳을 어떻게 배치해야 입력 회수의 평균값이 작아지는지 구하는 프로그램을 작성하시오.

각 키에 알파벳은 적어도 한 개 있어야 하며, 많아야 여덟 개까지 있을 수 있다.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다: 첫째 줄에는 키의 개수 K가 주어진다 (4 ≤ K ≤ 26) 둘째 줄에는 첫 13개 알파벳의 사용 빈도가 주어진다. 셋째 줄에는 마지막 13개 알파벳의 사용 빈도가 주어진다.

출력

각 테스트 케이스에 대해 최적의 키 배열에서의 평균 키 입력 횟수(소수점 셋째자리까지), A~Z의 배열을 공백을 사이에 두고 출력한다.

예제 입력 1

2
8
8.167 1.492 2.782 4.253 12.702 2.228 2.015 6.094 6.966 0.153 0.772 4.025 2.406
6.749 7.507 1.929 0.095 5.987 6.327 9.056 2.758 0.978 2.360 0.150 1.974 0.075
9
1.0 10.0 11.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
10.0 10.0 10.0 10.0 10.0 11.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0

예제 출력 1

1.647 AB CD EFG HIJK LM NOPQ RS TUVWXYZ
1.570 A B CDEFG HIJKLM N OP QR STUV WXYZ
W3sicHJvYmxlbV9pZCI6IjI3MDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTAgXHViY2Y0XHViMGI0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWQ0NWNcdWM5MDAgXHVkNzM0XHViMzAwXHVjODA0XHVkNjU0XHVjNzU4IFx1ZDBhNFx1ZDMyOFx1YjRkY1x1YzVkMFx1YjI5NCBcdWFlMDBcdWM3OTBcdWI0ZTRcdWM3NzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWJjODhcdWQ2MzhcdWQwYTRcdWM2NDAgXHViMzAwXHVjNzUxXHViNDE4XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tleS5wbmdcIiBzdHlsZT1cIndpZHRoOiAyMjVweDsgaGVpZ2h0OiAyNjNweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhZTAwXHVjNzkwIENcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCAmIzM5OzImIzM5O1x1ZDBhNFx1Yjk3YyAzXHViYzg4IFx1YjIwY1x1YjdlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVhZTAwXHVjNzkwXHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViMjBjXHViN2VjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQwYTRcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1YjIwY1x1YjdlY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHVkNjlmXHVjMjE4XHViMjk0IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWM1YjRcdWI1YTQgXHVkMGE0XHVjNzU4IFx1YjlhY1x1YzJhNFx1ZDJiOFx1YzVkMCBcdWMxOGRcdWQ1NzRcdWM3ODhcdWIyOTRcdWFjMDBcdWM2NDAgXHViOWFjXHVjMmE0XHVkMmI4XHVjNWQwXHVjMTFjIFx1YmE4NyBcdWJjODhcdWM5ZjhcdWM3NzhcdWM5YzBcdWM1ZDAgXHViNTMwXHViNzdjIFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0RXh1cGVyeSBUZWxlcGhvbmUgQ29tcGFueSAoRVRDKVx1YjI5NCBcdWNkOTVcdWM4MDFcdWI0MWMgXHVhZTAwXHVjNzkwXHViY2M0IFx1YzBhY1x1YzZhOSBcdWJlNDhcdWIzYzQgXHViMzcwXHVjNzc0XHVkMTMwXHViY2EwXHVjNzc0XHVjMmE0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWQ3MzRcdWIzMDBcdWM4MDRcdWQ2NTQgXHVjMGFjXHVjNmE5XHVjNzkwXHViNGU0XHVjNzU4IFx1ZDNjOVx1YWRlMCBcdWQwYTQgXHVjNzg1XHViODI1IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWM5MDRcdWM3NzRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWUwMFx1Yzc5MCBcdWJjMzBcdWNlNThcdWI0ZTRcdWM3NDQgXHViY2MwXHVhY2JkXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgU1x1Yjk3YyA3XHVkMGE0XHVjNWQwXHVjMTFjIDhcdWQwYTRcdWI4NWMgXHVjNjJlXHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWUwMFx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWIwOThcdWQwYzBcdWIwOThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjOWMwXHVjZjFjXHVjNTdjIFx1ZDU1OFx1YzljMFx1YjljYyBcdWFjMDEgXHVkMGE0XHViOWM4XHViMmU0IFx1YmMzMFx1YzgxNVx1YjQxOFx1YjI5NCBcdWFlMDBcdWM3OTBcdWM3NTggXHVjMjE4XHViMjk0IFx1YjJlY1x1Yjc3Y1x1YjNjNCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWMwMSBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NTggXHViZTQ4XHViM2M0XHVjMjE4XHVjNjQwIFx1ZDBhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzQ0IFx1YzViNFx1YjViYlx1YWM4YyBcdWJjMzBcdWNlNThcdWQ1NzRcdWM1N2MgXHVjNzg1XHViODI1IFx1ZDY4Y1x1YzIxOFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWFjMTJcdWM3NzQgXHVjNzkxXHVjNTQ0XHVjOWMwXHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjMDEgXHVkMGE0XHVjNWQwIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0MCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YWMxYyBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWI5Y2VcdWM1NDRcdWM1N2MgXHVjNWVjXHViMzVmIFx1YWMxY1x1YWU0Y1x1YzljMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWMxMzggXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNDogXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQwYTRcdWM3NTggXHVhYzFjXHVjMjE4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICg0ICZsZTsgSyAmbGU7IDI2KSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2NhYiAxM1x1YWMxYyBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NTggXHVjMGFjXHVjNmE5IFx1YmU0OFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWM4XHVjOWMwXHViOWM5IDEzXHVhYzFjIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc1OCBcdWMwYWNcdWM2YTkgXHViZTQ4XHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjZDVjXHVjODAxXHVjNzU4IFx1ZDBhNCBcdWJjMzBcdWM1ZjRcdWM1ZDBcdWMxMWNcdWM3NTggXHVkM2M5XHVhZGUwIFx1ZDBhNCBcdWM3ODVcdWI4MjUgXHVkNjlmXHVjMjE4KFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWMxNGJcdWM5ZjhcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzApLCBBflpcdWM3NTggXHViYzMwXHVjNWY0XHVjNzQ0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzA2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGV4dCBNZXNzYWdpbmcgSW1wcm92ZW1lbnQ/IiwiZGVzY3JpcHRpb24iOiI8cD5PbiBhIHN0YW5kYXJkIG1vYmlsZSBwaG9uZSB0aGUgbGV0dGVycyBhcmUgZGlzdHJpYnV0ZWQgYWNyb3NzIHRoZSBrZXlzIDIgdGhyb3VnaCA5IGFzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tleS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNjNweDsgd2lkdGg6MjI1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VG8gZW50ZXIgdGhlIGxldHRlciBDLCB5b3UgcHJlc3Mga2V5IDIgdGhyZWUgdGltZXMgKHNlZWluZyBBLUItQykuIFRoZSBudW1iZXIgb2Yga2V5c3Ryb2tlcyB0byBlbnRlciBhIGxldHRlciBkZXBlbmRzIG9uIHdoZXJlIGl0IGlzIGluIHRoZSBsaXN0IG9mIGxldHRlcnMgb24gaXRzIGtleS48XC9wPlxyXG5cclxuPHA+VGhlIEZsYXRoZWFkIFRlbGVwaG9uZSBDb21wYW55IChGVEMpIGlzIGNvbnNpZGVyaW5nIHJlYXJyYW5naW5nIHRoZSBsZXR0ZXJzIG9uIHRoZSBrZXlzIHRvIHJlZHVjZSB0aGUgYXZlcmFnZSBudW1iZXIgb2Yga2V5c3Ryb2tlcyByZXF1aXJlZCB0byBlbnRlciBuYW1lcyBldGMuIG9yIHNlbmQgdGV4dCBtZXNzYWdlcy4gVGhlIGxldHRlcnMgbXVzdCBzdGlsbCBhcHBlYXIgaW4gYWxwaGFiZXRpY2FsIG9yZGVyIG9uIHRoZSBrZXlzIGJ1dCBkaWZmZXJlbnQgbnVtYmVycyBvZiBsZXR0ZXJzIG1heSBhcHBlYXIgb24gZWFjaCBrZXkgYW5kIHBvc3NpYmx5IG1vcmUga2V5cyBjb3VsZCBiZSB1c2VkLiBGVEMgaGFzIHNldmVyYWwgZGF0YWJhc2VzIG9mIGxldHRlciBmcmVxdWVuY2llcyB1c2VkIGluIGRpZmZlcmVudCBhcHBsaWNhdGlvbnMuIEZvciBpbnN0YW5jZSwgaXQgbWlnaHQgaGVscCB0byBtb3ZlIFMgZnJvbSB0aGUgNyBrZXkgdG8gdGhlIDgga2V5LiBUaGV5IG5lZWQgYSBwcm9ncmFtIHdoaWNoIGlzIGdpdmVuIHRoZSBmcmVxdWVuY2llcyBvZiB0aGUgbGV0dGVycyBhbmQgYSBudW1iZXIgb2Yga2V5cyBhbmQgcmV0dXJucyB0aGUgYXNzaWdubWVudCBvZiBsZXR0ZXJzIHRvIGtleXMgd2l0aCB0aGUgc21hbGxlc3QgYXZlcmFnZSBudW1iZXIgb2Yga2V5c3Ryb2tlcyB1c2luZyB0aGUgZ2l2ZW4gZnJlcXVlbmNpZXMuIEVhY2gga2V5IHVzZWQgbXVzdCBoYXZlIGF0IGxlYXN0IG9uZSBsZXR0ZXIgYW5kIGF0IG1vc3QgZWlnaHQgbGV0dGVycy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgTiwgKDEgJmxlOyBOICZsZTsgMTAwMCkgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgdGhyZWUgbGluZXMgb2YgaW5wdXQuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgSywgKDQgJmxlOyBLICZsZTsgMjYpLCB0aGUgbnVtYmVyIG9mIGtleXMgd2hpY2ggYXJlIHRvIGJlIHVzZWQuIFRoZSBzZWNvbmQgYW5kIHRoaXJkIGxpbmVzIGNvbnRhaW4gMTMgZGVjaW1hbCB2YWx1ZXMgZWFjaCBnaXZpbmcgdGhlIHBlcmNlbnQgZnJlcXVlbmN5IG9mIHRoZSBsZXR0ZXJzIEEgdGhyb3VnaCBaIGluIG9yZGVyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0LCB5b3Ugc2hvdWxkIGdlbmVyYXRlIG9uZSBsaW5lIG9mIG91dHB1dCB3aXRoIHRoZSBmb2xsb3dpbmcgdmFsdWVzOiBUaGUgZGF0YSBzZXQgbnVtYmVyIGFzIGEgZGVjaW1hbCBpbnRlZ2VyIChzdGFydCBjb3VudGluZyBhdCBvbmUpLCB0aGUgYmVzdCBhdmVyYWdlIG51bWJlciBvZiBrZXlzdHJva2VzIHRvIHRocmVlIGRlY2ltYWwgcGxhY2VzLCBhIHNwYWNlIGFuZCB0aGUgbGV0dGVycyBBIHRocm91Z2ggWiwgZm9yIHRoZSBiZXN0IGFycmFuZ2VtZW50LCBpbiBvcmRlciB3aXRoIGEgc2luZ2xlIHNwYWNlIGF0IHRoZSBicmVhayBiZXR3ZWVuIGxldHRlcnMgb24gZGlmZmVyZW50IGtleXMuIEl0IGlzIHBvc3NpYmxlIHRoYXQgdGhlIHNhbWUgaW5wdXQgZGF0YSBzZXQgbWF5IHByb2R1Y2UgZGlmZmVyZW50IG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=