시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 512 MB76312173126326.182%

문제

상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 

상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다.

Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지만, 한 주사위는 단어에 한 번만 사용할 수 있다. 단어는 게임 사전에 등재되어 있는 단어만 올바른 단어이다.

1글자, 2글자로 이루어진 단어는 0점, 3글자, 4글자는 1점, 5글자는 2점, 6글자는 3점, 7글자는 5점, 8글자는 11점이다. 점수는 자신이 찾은 단어에 해당하는 점수의 총 합이다.

단어 사전에 등재되어 있는 단어의 목록과 Boggle 게임 보드가 주어졌을 때, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어 사전에 들어있는 단어의 수 w가 주어진다. (1 < w < 300,000) 다음 w개 줄에는 단어가 주어진다. 단어는 최대 8글자이고, 알파벳 대문자로만 이루어져 있다. 단어 사전에 대한 정보가 모두 주어진 이후에는 빈 줄이 하나 주어진다.

그 다음에는 Boggle 보드의 개수 b가 주어진다. (1 < b < 30) 모든 Boggle은 알파벳 대문자로 이루어져 있고, 4줄에 걸쳐 주어진다. 각 Boggle의 사이에는 빈 줄이 하나  있다.

출력

각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다. 각 Boggle에 대해서 찾을 수 있는 단어가 적어도 한 개인 경우만 입력으로 주어진다.

예제 입력 1

5
ICPC
ACM
CONTEST
GCPC
PROGRAMM

3
ACMA
APCA
TOGI
NEST

PCMM
RXAI
ORCN
GPCG

ICPC
GCPC
ICPC
GCPC

예제 출력 1

8 CONTEST 4
14 PROGRAMM 4
2 GCPC 2
W3sicHJvYmxlbV9pZCI6IjkyMDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJCb2dnbGUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJjZjRcdWI0ZGMgXHVhYzhjXHVjNzg0ICZxdW90O0JvZ2dsZSZxdW90O1x1Yzc0NCBcdWM1YzRcdWNjYWRcdWIwOThcdWFjOGMgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0LiBCb2dnbGVcdWM3NDAgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjOGZjXHVjMGFjXHVjNzA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCA0JnRpbWVzOzQgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YWRmOFx1YjlhY1x1YjRkY1x1YzVkMFx1YzExYyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YjNjNCBcdWJkODBcdWM3NzhcdWM3NDQgQm9nZ2xlXHViODVjIFx1Yzc3NFx1YWNhOFx1YmNmOCBcdWM4MDFcdWM3NzQgXHVjNWM2XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjOWM4IFx1YjU0Y1x1YjljOFx1YjJlNCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNGYwXHViODA4XHVhZTMwIFx1YmM4NFx1YjlhY1x1YWUzMCwgXHVjMTI0XHVhYzcwXHVjOWMwXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM3N2NcdWM3NDQgXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHVjODFjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTc0XHVjMTFjIFx1YmQ4MFx1Yzc3OFx1Yzc0NCBcdWM3NzRcdWFjYThcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5Cb2dnbGVcdWM1ZDBcdWMxMWMgXHViMmU4XHVjNWI0XHViMjk0IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWFlMDBcdWM3OTAoXHVhYzAwXHViODVjLCBcdWMxMzhcdWI4NWMsIFx1YjMwMFx1YWMwMVx1YzEyMClcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1ZDU1YyBcdWM4ZmNcdWMwYWNcdWM3MDRcdWIyOTQgXHViMmU4XHVjNWI0XHVjNWQwIFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjJlOFx1YzViNFx1YjI5NCBcdWFjOGNcdWM3ODQgXHVjMGFjXHVjODA0XHVjNWQwIFx1YjRmMVx1YzdhY1x1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHViOWNjIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWIyZThcdWM1YjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjFcdWFlMDBcdWM3OTAsIDJcdWFlMDBcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjJlOFx1YzViNFx1YjI5NCAwXHVjODEwLCAzXHVhZTAwXHVjNzkwLCA0XHVhZTAwXHVjNzkwXHViMjk0IDFcdWM4MTAsIDVcdWFlMDBcdWM3OTBcdWIyOTQgMlx1YzgxMCwgNlx1YWUwMFx1Yzc5MFx1YjI5NCAzXHVjODEwLCA3XHVhZTAwXHVjNzkwXHViMjk0IDVcdWM4MTAsIDhcdWFlMDBcdWM3OTBcdWIyOTQgMTFcdWM4MTBcdWM3NzRcdWIyZTQuIFx1YzgxMFx1YzIxOFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjYzNlXHVjNzQwIFx1YjJlOFx1YzViNFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVjODEwXHVjMjE4XHVjNzU4IFx1Y2QxZCBcdWQ1NjlcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOFx1YzViNCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHViNGYxXHVjN2FjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWM3NTggXHViYWE5XHViODVkXHVhY2ZjIEJvZ2dsZSBcdWFjOGNcdWM3ODQgXHViY2Y0XHViNGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMTgsIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHViMmU4XHVjNWI0LCBcdWNjM2VcdWM3NDAgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmU4XHVjNWI0IFx1YzBhY1x1YzgwNFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzIxOCB3XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmx0OyB3ICZsdDsgMzAwLDAwMCkgXHViMmU0XHVjNzRjIHdcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlOFx1YzViNFx1YjI5NCBcdWNkNWNcdWIzMDAgOFx1YWUwMFx1Yzc5MFx1Yzc3NFx1YWNlMCwgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWIyZThcdWM1YjQgXHVjMGFjXHVjODA0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHViYWE4XHViNDUwIFx1YzhmY1x1YzViNFx1YzljNCBcdWM3NzRcdWQ2YzRcdWM1ZDBcdWIyOTQgXHViZTQ4IFx1YzkwNFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IEJvZ2dsZSBcdWJjZjRcdWI0ZGNcdWM3NTggXHVhYzFjXHVjMjE4IGJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbHQ7IGIgJmx0OyAzMCkgXHViYWE4XHViNGUwIEJvZ2dsZVx1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIDRcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIEJvZ2dsZVx1Yzc1OCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViZTQ4IFx1YzkwNFx1Yzc3NCBcdWQ1NThcdWIwOTggJm5ic3A7XHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBCb2dnbGVcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjODEwXHVjMjE4LCBcdWFjMDBcdWM3YTUmbmJzcDtcdWFlMzQgXHViMmU4XHVjNWI0LCBcdWNjM2VcdWM3NDAgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBCb2dnbGVcdWM1ZDBcdWMxMWMgXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1Y2MzZVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWNjM2VcdWM3NDAgXHVhYzgzXHVjNzNjXHViODVjIFx1YzEzY1x1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM1NWVcdWMxMWNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAxIEJvZ2dsZVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjYzNlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHVhYzFjXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjkyMDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCb2dnbGUiLCJkZXNjcmlwdGlvbiI6IjxwPkkgYW0gc3VyZSwgeW91IGFyZSBhIGJpZyBmYW4gb2YgdGhlIGJvYXJkIGdhbWUgJmxkcXVvO0JvZ2dsZSZyZHF1bzsuIERvbiZyc3F1bzt0IHdvcnJ5IGlmIHlvdSBhcmUgbm90IGZhbWlsaWFyIHdpdGggdGhlIHJ1bGVzLCBJIHdpbGwgZXhwbGFpbiB0aGVtIHRvIHlvdS4gQSBCb2dnbGUgaXMgYSA0ICZ0aW1lczsgNCBncmlkIG9mIGxldHRlcnMgd2hlcmUgeW91ciBqb2IgaXMgdG8gZmluZCBhcyBtYW55IHdvcmRzIGFzIHlvdSBjYW4uIElmIEkgcGxheSBCb2dnbGUgd2l0aCAob3IgYWdhaW5zdCkgbXkgd2lmZSwgc2hlIGFsd2F5cyB3aW5zICZuZGFzaDsgdGhlIGxvc2VyICh0aGF0JnJzcXVvO3MgbWUpIHRoZW4gYWx3YXlzIGhhcyB0byBkbyBhbGwgdGhlc2UgbGl0dGxlIGpvYnMgbGlrZSB0byB0YWtlIG91dCB0aGUgdHJhc2guIFNvLCBwbGVhc2UgaGVscCBtZSB0byB3aW4gYWdhaW4uPFwvcD5cclxuXHJcbjxwPldvcmRzIGluIGEgQm9nZ2xlIGNhbiBiZSBjb25zdHJ1Y3RlZCBmcm9tIGFkamFjZW50IGxldHRlcnMgKGkuZS4gaG9yaXpvbnRhbGx5LCB2ZXJ0aWNhbGx5IGFuZCBkaWFnb25hbGx5KSwgYnV0IHRoZSBzYW1lIGRpY2UgbWF5IG9ubHkgYmUgdXNlZCBvbmNlIGluIGEgd29yZC4gVGhlIHdvcmRzIGhhdmUgdG8gYmUgbGlzdGVkIGluIG91ciBkaWN0aW9uYXJ5IHRvIGJlIHZhbGlkLjxcL3A+XHJcblxyXG48cD5Xb3JkcyB3aXRoIDEgb3IgMiBsZXR0ZXJzIGNvdW50IDAgcG9pbnRzLCB3b3JkcyB3aXRoIDMgb3IgNCBsZXR0ZXJzIDEgcG9pbnQsIDUgbGV0dGVycyAyIHBvaW50cywgNiBsZXR0ZXJzIDMgcG9pbnRzLCA3IGxldHRlcnMgNSBwb2ludHMuIDggbGV0dGVyIHdvcmRzIHdpbGwgZ2l2ZSAxMSBwb2ludHMuIElmIHlvdSBcdWZiMDFuZCBtb3JlIHRoYW4gb25lIHdvcmQgKGFuZCBJIGhvcGUgeW91IGRvKSwgcG9pbnRzIHdpbGwgYmUgc3VtbWVkIHVwIHRvIGZvcm0geW91ciBzY29yZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIGlzIG9ubHkgb25lIHRlc3QgY2FzZSBwZXIgXHVmYjAxbGUuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2Ygd29yZHMgdyBpbiB0aGUgZGljdGlvbmFyeSAoMSAmbHQ7IHcgJmx0OyAzMDAgMDAwKS4gVGhlbiBmb2xsb3cgdyBsaW5lcywgZWFjaCBjb250YWluaW5nIG9uZSB3b3JkLiBXb3JkcyBjb25zaXN0IG9mIHVwIHRvIDggdXBwZXIgY2FzZSBsZXR0ZXJzICgmcnNxdW87QSZyc3F1bzstJnJzcXVvO1omcnNxdW87KS4gQWZ0ZXIgdGhlIGRpY3Rpb25hcnkgc3BlY2lmaWNhdGlvbiwgdGhlcmUgaXMgYSBibGFuayBsaW5lLiBUaGVuIGZvbGxvd3MgdGhlIG51bWJlciBvZiBCb2dnbGUgYm9hcmRzIGIgaW4gb25lIGxpbmUgKDEgJmx0OyBiICZsdDsgMzApLiBFYWNoIGJvZ2dsZSBpcyBnaXZlbiBhcyBhIDQgJnRpbWVzOyA0IGdyaWQgb2YgdXBwZXIgY2FzZSBsZXR0ZXJzIGluIGZvdXIgbGluZXMuIEJvZ2dsZXMgYXJlIHNlcGFyYXRlZCBieSBibGFuayBsaW5lcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBib2dnbGUsIHByaW50IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1heGltYWwgcG9zc2libGUgc2NvcmUsIHRoZSBsb25nZXN0IHdvcmQgYW5kIG51bWJlciBvZiBmb3VuZCB3b3Jkcy4gV29yZHMgdGhhdCBhcmUgdHdpY2UgKG9yIG1vcmUgb2Z0ZW4pIGluIG9uZSBCb2dnbGUsIG9ubHkgY291bnQgb25jZS4gSWYgdGhlcmUgaXMgbW9yZSB0aGFuIG9uZSBsb25nZXN0IHdvcmQsIHByaW50IHRoZSBsZXhpY29ncmFwaGljYWxseSBzbWFsbGVzdCBvbmUuIFlvdSBtYXkgc2FmZWx5IGFzc3VtZSB0aGF0IHRoZXJlIGlzIGF0IGxlYXN0IG9uZSB2YWxpZCB3b3JkIGluIGVhY2ggQm9nZ2xlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2013 A번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: bjacau12
  • 빠진 조건을 찾은 사람: jh05013