Time Limit: 3s
Memory Limit: 128MB
사람들 앞에 나와서 발표를 하는 것은 굉장히 어려운 일이다. 특히 요즘같이 스마트폰으로 많은 것을 할 수 있게된 시대에는 핸드폰으로 딴짓을 하기 좋아졌기 때문에 청자들의 집중도를 이끄는 것이 굉장히 중요한 스킬이 됐다.
여기, 연설의 왕 '스피킹'님이 감명깊은 연설을 하기위해 무엇을 준비하는지, 자신만의 노하우를 설명해주신다고 하시니 집중해서 잘 들어보자.
우선, 연설용으로 쓸만한 글은 단어의 중요도를 나타내는 '높낮이'가 일정 패턴을 이루고있다. 이 높낮이의 정보를 간단히 표현하기 위해 4개의 알파벳 소문자 a,e,i,o를 이용해 표현했다고 치자. 이제 "연설용으로 쓸만한 글"은 다음과 같은 특징을 가진다고 한다.
우선 ae 와 io는 연설용으로 쓸만한 글이다. 만약 w1과 w2가 연설용으로 쓸만한 글이라면 w1w2 와 aw1e, iw1o도 연설용으로 쓸만한 글이다. 예를 들어 aaeeio는 aaee + io = a (ae) e + io 로 연설용으로 쓸만한 글이 된다.
하지만 연설용으로 쓸만한 글을 계속해서 말하는 것은 별로 큰 가치가 없다. 연설왕 스피킹님처럼 연설하는 날이 많은 경우, 직전에 했던 연설보다 더더욱 "인상깊은" 연설을 해야만 사람들이 감명을 받을 것이다. 직전 연설보다 인상깊은 연설을 하기 위해선, 위에서 표현한 알파벳표기법으로 글을 나타냈을 때, 직전 연설과 길이가 같으면서 사전순으로 뒷서는 글로 연설을 하면 좀 더 인상깊어진다고 한다.
예를 들어 전날에 aaeeio 라는 글로 연설을 했을 경우, 다음날은 이보다 더 인상깊은 (사전순으로 더 뒷서는) aaeioe 라는 글로 연설을 해야만 사람들은 감명을 받을 것이다.
스피킹은 그 명성으로 인해서, 앞으로 강당앞에 설 일도 많기 때문에 인상깊은 글을 최대한 많이 만들고싶다. 그러기 위해선, 사전순으로 뒷서는 글들 중 가장 사전순으로 앞서는 글을 선택해서 연설한다면 최대한 많이 연설할 수 있을 것이다.
스피킹은 달변가기 때문에 연설 때 사용하는 단어의 양이 굉장히 많다. 따라서 인상깊은 글을 만드는 작업이 매우 힘들기 때문에 컴퓨터의 힘을 빌리려한다. 스피킹이 직전 연설 때 사용했던 글의 높낮이 패턴이 주어졌을 때, 그가 다음에 사용해야 할 글의 패턴을 구해주자.
입력의 첫번째 줄에는 테스트케이스의 개수 t (t ≤ 2000) 이 주어진다.
이어서 t개의 줄에 걸쳐 테스트케이스의 입력드링 주어진다.
각 테스트케이스에는 a,e,i,o로만 이루어진 문자열이 하나 주어진다. 문자열의 길이는 10^6을 넘지 않는다.
각 테스트케이스마다 한줄에 하나씩 정답을 출력한다.
만약 입력으로 들어온 문자열이 연설용으로 적합하지 않다면 INVALID를 출력한다.
만약 이보다 더 인상깊은 연설문구가 없다면 ULTIMATE를 출력한다.
그렇지 않다면, 입력으로 들어온 글보다 인상깊은 글 중 사전순으로 가장 앞서는 문구를 출력한다.
4 eaeeio aaeeio ioioioioio ae
INVALID aaeioe ULTIMATE io
설명해준다고 하더니 결국은 부탁을 들어달라는 것으로 문제가 마무리되었다. 사스가 연설왕....자연스럽게 부탁했어
Regionals 2010, Europe - Central