5670번 - 휴대폰 자판 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 192 MB92843376223933.523%

문제

휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발하였다. 이 모듈은 사전 내에서 가능한 다음 글자가 하나뿐이라면 그 글자를 버튼 입력 없이 자동으로 입력해 준다! 자세한 작동 과정을 설명하자면 다음과 같다.

  1. 모듈이 단어의 첫 번째 글자를 추론하지는 않는다. 즉, 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드시 첫 글자는 사용자가 버튼을 눌러 입력해야 한다.
  2. 길이가 1 이상인 문자열 c1c2...cn이 지금까지 입력되었을 때, 사전 안의 모든 c1c2...cn으로 시작하는 단어가 c1c2...cnc로도 시작하는 글자 c가 존재한다면 모듈은 사용자의 버튼 입력 없이도 자동으로 c를 입력해 준다. 그렇지 않다면 사용자의 입력을 기다린다.

예를 들면, 사전에 "hello", "hell", "heaven", "goodbye" 4개의 단어가 있고 사용자가 "h"를 입력하면 모듈은 자동으로 "e"를 입력해 준다. 사전상의 "h"로 시작하는 단어들은 모두 그 뒤에 "e"가 오기 때문이다. 그러나 단어들 중 "hel"로 시작하는 것도, "hea"로 시작하는 것도 있기 때문에 여기서 모듈은 사용자의 입력을 기다린다. 이어서 사용자가 "l"을 입력하면 모듈은 "l"을 자동으로 입력해 준다. 그러나 여기서 끝나는 단어인 "hell"과 그렇지 않은 단어인 "hello"가 공존하므로 모듈은 다시 입력을 기다린다. 사용자가 "hell"을 입력하기 원한다면 여기서 입력을 멈출 것이고, "hello"를 입력하기 원한다면 직접 "o" 버튼을 눌러서 입력해 줘야 한다. 따라서 "hello"를 입력하려면 사용자는 총 3번 버튼을 눌러야 하고, "hell", "heaven"은 2번이다. "heaven"의 경우 "he"에서 "a"를 입력하면 바로 뒷부분이 모두 자동으로 입력되기 때문이다. 비슷하게, "goodbye"는 단 한 번만 버튼을 눌러도 입력이 완료될 것이다. "g"를 입력하는 순간 뒤에 오는 글자가 항상 유일하므로 끝까지 자동으로 입력되기 때문이다. 이때 사전에 있는 단어들을 입력하기 위해 버튼을 눌러야 하는 횟수의 평균은 (3 + 2 + 2 + 1)/4 = 2.00이다.

사전이 주어졌을 때, 이 모듈을 사용하면서 이와 같이 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에 사전에 속한 단어의 개수 N이 주어지며(1 ≤ N ≤ 105), 이어서 N개의 줄에 1~80글자인 영어 소문자로만 이루어진 단어가 하나씩 주어진다. 이 단어들로 사전이 구성되어 있으며, 똑같은 단어는 두 번 주어지지 않는다. 각 테스트 케이스마다 입력으로 주어지는 단어의 길이 총합은 최대 106이다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 문제의 정답을 소수점 둘째 자리까지 반올림하여 출력한다.

예제 입력 1 

4
hello
hell
heaven
goodbye
3
hi
he
h
7
structure
structures
ride
riders
stress
solstice
ridiculous

예제 출력 1 

2.00
1.67
2.71
W3sicHJvYmxlbV9pZCI6IjU2NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3MzRcdWIzMDBcdWQzZjAgXHVjNzkwXHVkMzEwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ3MzRcdWIzMDBcdWQzZjBcdWM1ZDBcdWMxMWMgXHVhZTM4XHVjNzc0XHVhYzAwIFBcdWM3NzggXHVjNjAxXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YjgyNFx1YmE3NCBcdWJjODRcdWQyYmNcdWM3NDQgUFx1YmM4OCBcdWIyMGNcdWI3ZWNcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTggXHVjMmRjXHVjMmE0XHVkMTVjXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkIFx1YzVmMFx1YWQ2Y1x1YzJlNFx1YzVkMCBcdWFkZmNcdWJiMzRcdWQ1NThcdWIyOTQgXHVjMmI5XHVkNjAxXHVjNWYwXHVhZDZjXHVjNmQwXHVjNzQwIFx1YzBhY1x1YzgwNFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzQgXHVjNzc0IFx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWIzNTQgXHViZTY4XHViOWFjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yzc5MFx1ZDMxMCBcdWJhYThcdWI0YzhcdWM3NDQgXHVhYzFjXHViYzFjXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM3NzQgXHViYWE4XHViNGM4XHVjNzQwIFx1YzBhY1x1YzgwNCBcdWIwYjRcdWM1ZDBcdWMxMWMgXHVhYzAwXHViMmE1XHVkNTVjIFx1YjJlNFx1Yzc0YyBcdWFlMDBcdWM3OTBcdWFjMDAgXHVkNTU4XHViMDk4XHViZmQwXHVjNzc0XHViNzdjXHViYTc0IFx1YWRmOCBcdWFlMDBcdWM3OTBcdWI5N2MgXHViYzg0XHVkMmJjIFx1Yzc4NVx1YjgyNSBcdWM1YzZcdWM3NzQgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIFx1Yzc4NVx1YjgyNVx1ZDU3NCBcdWM5MDBcdWIyZTQhIFx1Yzc5MFx1YzEzOFx1ZDU1YyBcdWM3OTFcdWIzZDkgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YzEyNFx1YmE4NVx1ZDU1OFx1Yzc5MFx1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YmFhOFx1YjRjOFx1Yzc3NCBcdWIyZThcdWM1YjRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjZDk0XHViODYwXHVkNTU4XHVjOWMwXHViMjk0IFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjOTg5LCBcdWMwYWNcdWM4MDRcdWM3NTggXHViYWE4XHViNGUwIFx1YjJlOFx1YzViNFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzNjXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjY2FiIFx1YWUwMFx1Yzc5MFx1YjI5NCBcdWMwYWNcdWM2YTlcdWM3OTBcdWFjMDAgXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwY1x1YjdlYyBcdWM3ODVcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFlMzhcdWM3NzRcdWFjMDAgMSBcdWM3NzRcdWMwYzFcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0IGM8c3ViPjE8XC9zdWI+YzxzdWI+MjxcL3N1Yj4uLi5jPHN1Yj5uPFwvc3ViPlx1Yzc3NCBcdWM5YzBcdWFlMDhcdWFlNGNcdWM5YzAgXHVjNzg1XHViODI1XHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjMGFjXHVjODA0IFx1YzU0OFx1Yzc1OCBcdWJhYThcdWI0ZTAgYzxzdWI+MTxcL3N1Yj5jPHN1Yj4yPFwvc3ViPi4uLmM8c3ViPm48XC9zdWI+XHVjNzNjXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWIyZThcdWM1YjRcdWFjMDAgYzxzdWI+MTxcL3N1Yj5jPHN1Yj4yPFwvc3ViPi4uLmM8c3ViPm48XC9zdWI+Y1x1Yjg1Y1x1YjNjNCBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVhZTAwXHVjNzkwIGNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0IFx1YmFhOFx1YjRjOFx1Yzc0MCBcdWMwYWNcdWM2YTlcdWM3OTBcdWM3NTggXHViYzg0XHVkMmJjIFx1Yzc4NVx1YjgyNSBcdWM1YzZcdWM3NzRcdWIzYzQgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIGNcdWI5N2MgXHVjNzg1XHViODI1XHVkNTc0IFx1YzkwMFx1YjJlNC4gXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCBcdWMwYWNcdWM2YTlcdWM3OTBcdWM3NTggXHVjNzg1XHViODI1XHVjNzQ0IFx1YWUzMFx1YjJlNFx1YjliMFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0LCBcdWMwYWNcdWM4MDRcdWM1ZDAgJnF1b3Q7aGVsbG8mcXVvdDssICZxdW90O2hlbGwmcXVvdDssICZxdW90O2hlYXZlbiZxdW90OywgJnF1b3Q7Z29vZGJ5ZSZxdW90OyA0XHVhYzFjXHVjNzU4IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM3ODhcdWFjZTAgXHVjMGFjXHVjNmE5XHVjNzkwXHVhYzAwICZxdW90O2gmcXVvdDtcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHViYTc0IFx1YmFhOFx1YjRjOFx1Yzc0MCBcdWM3OTBcdWIzZDlcdWM3M2NcdWI4NWMgJnF1b3Q7ZSZxdW90O1x1Yjk3YyBcdWM3ODVcdWI4MjVcdWQ1NzQgXHVjOTAwXHViMmU0LiBcdWMwYWNcdWM4MDRcdWMwYzFcdWM3NTggJnF1b3Q7aCZxdW90O1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHViMmU4XHVjNWI0XHViNGU0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWFkZjggXHViNGE0XHVjNWQwICZxdW90O2UmcXVvdDtcdWFjMDAgXHVjNjI0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViN2VjXHViMDk4IFx1YjJlOFx1YzViNFx1YjRlNCBcdWM5MTEgJnF1b3Q7aGVsJnF1b3Q7XHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWFjODNcdWIzYzQsICZxdW90O2hlYSZxdW90O1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVhYzgzXHViM2M0IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNWVjXHVhZTMwXHVjMTFjIFx1YmFhOFx1YjRjOFx1Yzc0MCBcdWMwYWNcdWM2YTlcdWM3OTBcdWM3NTggXHVjNzg1XHViODI1XHVjNzQ0IFx1YWUzMFx1YjJlNFx1YjliMFx1YjJlNC4gXHVjNzc0XHVjNWI0XHVjMTFjIFx1YzBhY1x1YzZhOVx1Yzc5MFx1YWMwMCAmcXVvdDtsJnF1b3Q7XHVjNzQ0IFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YmE3NCBcdWJhYThcdWI0YzhcdWM3NDAgJnF1b3Q7bCZxdW90O1x1Yzc0NCBcdWM3OTBcdWIzZDlcdWM3M2NcdWI4NWMgXHVjNzg1XHViODI1XHVkNTc0IFx1YzkwMFx1YjJlNC4gXHVhZGY4XHViN2VjXHViMDk4IFx1YzVlY1x1YWUzMFx1YzExYyBcdWIwNWRcdWIwOThcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzc4ICZxdW90O2hlbGwmcXVvdDtcdWFjZmMgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWIyZThcdWM1YjRcdWM3NzggJnF1b3Q7aGVsbG8mcXVvdDtcdWFjMDAgXHVhY2Y1XHVjODc0XHVkNTU4XHViYmMwXHViODVjIFx1YmFhOFx1YjRjOFx1Yzc0MCBcdWIyZTRcdWMyZGMgXHVjNzg1XHViODI1XHVjNzQ0IFx1YWUzMFx1YjJlNFx1YjliMFx1YjJlNC4gXHVjMGFjXHVjNmE5XHVjNzkwXHVhYzAwICZxdW90O2hlbGwmcXVvdDtcdWM3NDQgXHVjNzg1XHViODI1XHVkNTU4XHVhZTMwIFx1YzZkMFx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWM1ZWNcdWFlMzBcdWMxMWMgXHVjNzg1XHViODI1XHVjNzQ0IFx1YmE0OFx1Y2Q5YyBcdWFjODNcdWM3NzRcdWFjZTAsICZxdW90O2hlbGxvJnF1b3Q7XHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YWUzMCBcdWM2ZDBcdWQ1NWNcdWIyZTRcdWJhNzQgXHVjOWMxXHVjODExICZxdW90O28mcXVvdDsgXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwY1x1YjdlY1x1YzExYyBcdWM3ODVcdWI4MjVcdWQ1NzQgXHVjOTE4XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjICZxdW90O2hlbGxvJnF1b3Q7XHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YjgyNFx1YmE3NCBcdWMwYWNcdWM2YTlcdWM3OTBcdWIyOTQgXHVjZDFkIDNcdWJjODggXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwY1x1YjdlY1x1YzU3YyBcdWQ1NThcdWFjZTAsICZxdW90O2hlbGwmcXVvdDssICZxdW90O2hlYXZlbiZxdW90O1x1Yzc0MCAyXHViYzg4XHVjNzc0XHViMmU0LiAmcXVvdDtoZWF2ZW4mcXVvdDtcdWM3NTggXHVhY2JkXHVjNmIwICZxdW90O2hlJnF1b3Q7XHVjNWQwXHVjMTFjICZxdW90O2EmcXVvdDtcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHViYTc0IFx1YmMxNFx1Yjg1YyBcdWI0YjdcdWJkODBcdWJkODRcdWM3NzQgXHViYWE4XHViNDUwIFx1Yzc5MFx1YjNkOVx1YzczY1x1Yjg1YyBcdWM3ODVcdWI4MjVcdWI0MThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWJlNDRcdWMyYjdcdWQ1NThcdWFjOGMsICZxdW90O2dvb2RieWUmcXVvdDtcdWIyOTQgXHViMmU4IFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwY1x1YjdlY1x1YjNjNCBcdWM3ODVcdWI4MjVcdWM3NzQgXHVjNjQ0XHViOGNjXHViNDIwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gJnF1b3Q7ZyZxdW90O1x1Yjk3YyBcdWM3ODVcdWI4MjVcdWQ1NThcdWIyOTQgXHVjMjFjXHVhYzA0IFx1YjRhNFx1YzVkMCBcdWM2MjRcdWIyOTQgXHVhZTAwXHVjNzkwXHVhYzAwIFx1ZDU2ZFx1YzBjMSBcdWM3MjBcdWM3N2NcdWQ1NThcdWJiYzBcdWI4NWMgXHViMDVkXHVhZTRjXHVjOWMwIFx1Yzc5MFx1YjNkOVx1YzczY1x1Yjg1YyBcdWM3ODVcdWI4MjVcdWI0MThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWM3NzRcdWI1NGMgXHVjMGFjXHVjODA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWI0ZTRcdWM3NDQgXHVjNzg1XHViODI1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWJjODRcdWQyYmNcdWM3NDQgXHViMjBjXHViN2VjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQ2OWZcdWMyMThcdWM3NTggXHVkM2M5XHVhZGUwXHVjNzQwICgzICsgMiArIDIgKyAxKVwvNCA9IDIuMDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1YzgwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHViYWE4XHViNGM4XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YmE3NFx1YzExYyBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWMwMSBcdWIyZThcdWM1YjRcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWJjODRcdWQyYmNcdWM3NDQgXHViMjBjXHViN2VjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQ2OWZcdWMyMThcdWM3NTggXHVkM2M5XHVhZGUwXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBhY1x1YzgwNFx1YzVkMCBcdWMxOGRcdWQ1NWMgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCgxICZsZTsgTiAmbGU7IDEwPHN1cD41PFwvc3VwPiksIFx1Yzc3NFx1YzViNFx1YzExYyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCAxfjgwXHVhZTAwXHVjNzkwXHVjNzc4IFx1YzYwMVx1YzViNCBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViMmU4XHVjNWI0XHViNGU0XHViODVjIFx1YzBhY1x1YzgwNFx1Yzc3NCBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWI2MTFcdWFjMTlcdWM3NDAgXHViMmU4XHVjNWI0XHViMjk0IFx1YjQ1MCBcdWJjODggXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWIyZThcdWM1YjRcdWM3NTggXHVhZTM4XHVjNzc0IFx1Y2QxZFx1ZDU2OVx1Yzc0MCBcdWNkNWNcdWIzMDAgMTA8c3VwPjY8XC9zdXA+XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4MTVcdWIyZjVcdWM3NDQgXHVjMThjXHVjMjE4XHVjODEwIFx1YjQ1OFx1YzlmOCBcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHViYzE4XHVjNjJjXHViOWJjXHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1NjcwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2VsbHBob25lIFR5cGluZyIsImRlc2NyaXB0aW9uIjoiPHA+QSByZXNlYXJjaCB0ZWFtIGlzIGRldmVsb3BpbmcgYSBuZXcgdGVjaG5vbG9neSB0byBzYXZlIHRpbWUgd2hlbiB0eXBpbmcgdGV4dCBtZXNzYWdlcyBpbiBtb2JpbGUgZGV2aWNlcy4gVGhleSBhcmUgd29ya2luZyBvbiBhIG5ldyBtb2RlbCB0aGF0IGhhcyBhIGNvbXBsZXRlIGtleWJvYXJkLCBzbyB1c2VycyBjYW4gdHlwZSBhbnkgc2luZ2xlIGxldHRlciBieSBwcmVzc2luZyB0aGUgY29ycmVzcG9uZGluZyBrZXkuIEluIHRoaXMgd2F5LCBhIHVzZXIgbmVlZHMgUCBrZXlzdHJva2VzIHRvIHR5cGUgYSB3b3JkIG9mIGxlbmd0aCBQLjxcL3A+XHJcblxyXG48cD5Ib3dldmVyLCB0aGlzIGlzIG5vdCBmYXN0IGVub3VnaC4gVGhlIHRlYW0gaXMgZ29pbmcgdG8gcHV0IHRvZ2V0aGVyIGEgZGljdGlvbmFyeSBvZiB0aGUgY29tbW9uIHdvcmRzIHRoYXQgYSB1c2VyIG1heSB0eXBlLiBUaGUgZ29hbCBpcyB0byByZWR1Y2UgdGhlIGF2ZXJhZ2UgbnVtYmVyIG9mIGtleXN0cm9rZXMgbmVlZGVkIHRvIHR5cGUgd29yZHMgdGhhdCBhcmUgaW4gdGhlIGRpY3Rpb25hcnkuIER1cmluZyB0aGUgdHlwaW5nIG9mIGEgd29yZCwgd2hlbmV2ZXIgdGhlIGZvbGxvd2luZyBsZXR0ZXIgaXMgdW5pcXVlbHkgZGV0ZXJtaW5lZCwgdGhlIGNlbGxwaG9uZSBzeXN0ZW0gd2lsbCBpbnB1dCBpdCBhdXRvbWF0aWNhbGx5LCB3aXRob3V0IHRoZSBuZWVkIGZvciBhIGtleXN0cm9rZS4gVG8gYmUgbW9yZSBwcmVjaXNlLCB0aGUgYmVoYXZpb3Igb2YgdGhlIGNlbGxwaG9uZSBzeXN0ZW0gd2lsbCBiZSBkZXRlcm1pbmVkIGJ5IHRoZSBmb2xsb3dpbmcgcnVsZXM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+VGhlIHN5c3RlbSBuZXZlciBndWVzc2VzIHRoZSBmaXJzdCBsZXR0ZXIgb2YgYSB3b3JkLCBzbyB0aGUgZmlyc3QgbGV0dGVyIGFsd2F5cyBoYXMgdG8gYmUgaW5wdXQgbWFudWFsbHkgYnkgcHJlc3NpbmcgdGhlIGNvcnJlc3BvbmRpbmcga2V5LjxcL2xpPlxyXG5cdDxsaT5JZiBhIG5vbi1lbXB0eSBzdWNjZXNzaW9uIG9mIGxldHRlcnMgYzxzdWI+MTxcL3N1Yj5jPHN1Yj4yPFwvc3ViPi4uLmM8c3ViPm48XC9zdWI+IGhhcyBiZWVuIGlucHV0LCBhbmQgdGhlcmUgaXMgYSBsZXR0ZXIgYyBzdWNoIHRoYXQgZXZlcnkgd29yZCBpbiB0aGUgZGljdGlvbmFyeSB3aGljaCBzdGFydHMgd2l0aCBjPHN1Yj4xPFwvc3ViPmM8c3ViPjI8XC9zdWI+Li4uYzxzdWI+bjxcL3N1Yj4gYWxzbyBzdGFydHMgd2l0aCBjPHN1Yj4xPFwvc3ViPmM8c3ViPjI8XC9zdWI+Li4uYzxzdWI+bjxcL3N1Yj5jLCB0aGVuIHRoZSBzeXN0ZW0gaW5wdXRzIGMgYXV0b21hdGljYWxseSwgd2l0aG91dCB0aGUgbmVlZCBvZiBhIGtleXN0cm9rZS4gT3RoZXJ3aXNlLCB0aGUgc3lzdGVtIHdhaXRzIGZvciB0aGUgdXNlci48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Gb3IgaW5zdGFuY2UsIGlmIHRoZSBkaWN0aW9uYXJ5IGlzIGNvbXBvc2VkIG9mIHRoZSB3b3JkcyAmbGRxdW87aGVsbG8mcmRxdW87LCAmbGRxdW87aGVsbCZyZHF1bzssICZsZHF1bztoZWF2ZW4mcmRxdW87IGFuZCAmbGRxdW87Z29vZGJ5ZSZyZHF1bzssIGFuZCB0aGUgdXNlciBwcmVzc2VzICZsZHF1bztoJnJkcXVvOywgdGhlIHN5c3RlbSB3aWxsIGlucHV0ICZsZHF1bztlJnJkcXVvOyBhdXRvbWF0aWNhbGx5LCBiZWNhdXNlIGV2ZXJ5IHdvcmQgd2hpY2ggc3RhcnRzIHdpdGggJmxkcXVvO2gmcmRxdW87IGFsc28gc3RhcnRzIHdpdGggJmxkcXVvO2hlJnJkcXVvOy4gSG93ZXZlciwgc2luY2UgdGhlcmUgYXJlIHdvcmRzIHRoYXQgc3RhcnQgd2l0aCAmbGRxdW87aGVsJnJkcXVvOyBhbmQgd2l0aCAmbGRxdW87aGVhJnJkcXVvOywgdGhlIHN5c3RlbSBub3cgbmVlZHMgdG8gd2FpdCBmb3IgdGhlIHVzZXIuIElmIHRoZSB1c2VyIHRoZW4gcHJlc3NlcyAmbGRxdW87bCZyZHF1bzssIG9idGFpbmluZyB0aGUgcGFydGlhbCB3b3JkICZsZHF1bztoZWwmcmRxdW87LCB0aGUgc3lzdGVtIHdpbGwgaW5wdXQgYSBzZWNvbmQgJmxkcXVvO2wmcmRxdW87IGF1dG9tYXRpY2FsbHkuIFdoZW4gaXQgaGFzICZsZHF1bztoZWxsJnJkcXVvOyBhcyBpbnB1dCwgdGhlIHN5c3RlbSBjYW5ub3QgZ3Vlc3MsIGJlY2F1c2UgaXQgaXMgcG9zc2libGUgdGhhdCB0aGUgd29yZCBpcyBvdmVyLCBvciBpdCBpcyBhbHNvIHBvc3NpYmxlIHRoYXQgdGhlIHVzZXIgbWF5IHdhbnQgdG8gcHJlc3MgJmxkcXVvO28mcmRxdW87IHRvIGdldCAmbGRxdW87aGVsbG8mcmRxdW87LiBJbiB0aGlzIGZhc2hpb24sIHRvIHR5cGUgdGhlIHdvcmQgJmxkcXVvO2hlbGxvJnJkcXVvOyB0aGUgdXNlciBuZWVkcyB0aHJlZSBrZXlzdHJva2VzLCAmbGRxdW87aGVsbCZyZHF1bzsgcmVxdWlyZXMgdHdvLCBhbmQgJmxkcXVvO2hlYXZlbiZyZHF1bzsgYWxzbyByZXF1aXJlcyB0d28sIGJlY2F1c2Ugd2hlbiB0aGUgY3VycmVudCBpbnB1dCBpcyAmbGRxdW87aGVhJnJkcXVvOyB0aGUgc3lzdGVtIGNhbiBhdXRvbWF0aWNhbGx5IGlucHV0IHRoZSByZW1haW5kZXIgb2YgdGhlIHdvcmQgYnkgcmVwZWF0ZWRseSBhcHBseWluZyB0aGUgc2Vjb25kIHJ1bGUuIFNpbWlsYXJseSwgdGhlIHdvcmQgJmxkcXVvO2dvb2RieWUmcmRxdW87IG5lZWRzIGp1c3Qgb25lIGtleXN0cm9rZSwgYmVjYXVzZSBhZnRlciBwcmVzc2luZyB0aGUgaW5pdGlhbCAmbGRxdW87ZyZyZHF1bzsgdGhlIHN5c3RlbSB3aWxsIGF1dG9tYXRpY2FsbHkgZmlsbCBpbiB0aGUgZW50aXJlIHdvcmQuIEluIHRoaXMgZXhhbXBsZSwgdGhlIGF2ZXJhZ2UgbnVtYmVyIG9mIGtleXN0cm9rZXMgbmVlZGVkIHRvIHR5cGUgYSB3b3JkIGluIHRoZSBkaWN0aW9uYXJ5IGlzIHRoZW4gKDMgKyAyICsgMiArIDEpXC80ID0gMi4wMC48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzLCBnaXZlbiBhIGRpY3Rpb25hcnksIHRvIGNhbGN1bGF0ZSB0aGUgYXZlcmFnZSBudW1iZXIgb2Yga2V5c3Ryb2tlcyBuZWVkZWQgdG8gdHlwZSBhIHdvcmQgaW4gdGhlIGRpY3Rpb25hcnkgd2l0aCB0aGUgbmV3IGNlbGxwaG9uZSBzeXN0ZW0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHRlc3QgY2FzZSBpcyBkZXNjcmliZWQgdXNpbmcgc2V2ZXJhbCBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHdvcmRzIGluIHRoZSBkaWN0aW9uYXJ5ICgxICZsZTsgTiAmbGU7IDEwPHN1cD41PFwvc3VwPikuIEVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyBjb250YWlucyBhIG5vbi1lbXB0eSBzdHJpbmcgb2YgYXQgbW9zdCA4MCBsb3dlcmNhc2UgbGV0dGVycyBmcm9tIHRoZSBFbmdsaXNoIGFscGhhYmV0LCByZXByZXNlbnRpbmcgYSB3b3JkIGluIHRoZSBkaWN0aW9uYXJ5LiBXaXRoaW4gZWFjaCB0ZXN0IGNhc2UgYWxsIHdvcmRzIGFyZSBkaWZmZXJlbnQsIGFuZCB0aGUgc3VtIG9mIHRoZSBsZW5ndGhzIG9mIGFsbCB3b3JkcyBpcyBhdCBtb3N0IDEwPHN1cD42PFwvc3VwPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IGEgbGluZSB3aXRoIGEgcmF0aW9uYWwgbnVtYmVyIHJlcHJlc2VudGluZyB0aGUgYXZlcmFnZSBudW1iZXIgb2Yga2V5c3Ryb2tlcyBuZWVkZWQgdG8gdHlwZSBhIHdvcmQgaW4gdGhlIGRpY3Rpb25hcnkuIFRoZSByZXN1bHQgbXVzdCBiZSBvdXRwdXQgYXMgYSByYXRpb25hbCBudW1iZXIgd2l0aCBleGFjdGx5IHR3byBkaWdpdHMgYWZ0ZXIgdGhlIGRlY2ltYWwgcG9pbnQsIHJvdW5kZWQgaWYgbmVjZXNzYXJ5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Latin America > Latin America Regional Contests 2012 C번

  • 문제를 번역한 사람: kks227
  • 문제를 만든 사람: Pablo Ariel Heiber

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)