RiseOJ – 자동 완성 (실버)

설명

소 베시는 새 휴대전화가 생겨 문자 메시지 보내기를 즐기고 있지만, 큰 발굽으로 그렇게 작은 화면에 입력하는 것이 어려워 계속 철자 오류를 낸다. 농부 존은 부분 단어를 받아 어떻게 완성할지 제안하는 자동 완성 앱을 만들어 그녀를 돕기로 했다.

자동 완성 앱은 각각 a..z 범위의 소문자로 이루어진 W개의 단어로 된 사전에 접근할 수 있으며, 모든 단어의 글자 수 총합은 최대 1,000,000이다. 앱은 각각 최대 1000개의 소문자를 포함하는 N개의 부분 단어 (1 <= N <= 1000) 목록을 입력으로 받는다. 각 부분 단어 i와 함께 정수 K_i도 주어지는데, 앱은 부분 단어 i를 접두사로 갖는 단어 중 알파벳순으로 (K_i)번째 단어를 찾아야 한다. 즉, i번째 부분 단어의 유효한 완성들을 모두 정렬했을 때, 이 수열에서 (K_i)번째인 완성을 출력해야 한다.

제약

문제 제공: Traditional

입력 형식

첫째 줄: 두 정수 W와 N.

둘째 줄부터 W+1번째 줄까지: i+1번째 줄에 사전의 i번째 단어가 주어진다.

W+2번째 줄부터 W+N+1번째 줄까지: W+i+1번째 줄에 정수 K_i와 이어서 부분 단어가 주어진다.

출력 형식

첫째 줄부터 N번째 줄까지: i번째 줄에는 i번째 부분 단어의 (알파벳순으로) (K_i)번째 완성의 사전 내 인덱스(범위 1..W의 정수)를 출력하거나, 완성이 K_i개 미만이면 -1을 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 auto.in · 출력을 쓸 파일 auto.out

예제 1

입력

10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da

출력

3
1
-1

설명

Output details: The completions of a are {aa,aaa,aab,ab,abc,ac}. The 4^th is ab, which is listed on line 3 of the dictionary. The completions of da are {daa,dab,dadba}. The 2^nd is dab, listed on line 1 of the dictionary. There is no 4^th completion of da.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > February > Silver

올림피아드 > USACO > 2013-2014 > February > Silver

태그

JudgeUSACO

자동 완성 (실버)

평가 및 의견

풀이 제출