Pabėgimo kambarys

시간 제한1초메모리 제한1024 MB

요약
문자열이 주어질 때, R, A, K, T, A, S를 부분 수열로 포함하는 가장 짧은 접두사의 길이를 구한다.
난이도

쉬움10점 중 3점

유형
그리디, 문자열, 시뮬레이션
정답자
아직 제출이 없습니다

문제

Norėdami atšvęsti Lietuvos informatikos olimpiadų trisdešimtmetį, Vertinimo komisijos nariai sugalvojo sau pramogą: pabėgimo kambarį. Pabėgimo kambarys – tai seka užuominų, kurių kiekviena yra pažymėta didžiąja lotyniška raide.

Užuominos yra atskleidžiamos po vieną, nuo pirmos iki paskutinės pateikta tvarka. Komisijos nariai iš kambario ištrūkti gali tuomet, kai iš surinktų užuominų pavyksta sudaryti žodį RAKTAS.

Įsivaizduokime pabėgimo kambarį, kurio užuominų seka yra tokia:

RAUDONASNYKSTUKAS

Iš šio pabėgimo kambario komisija gali ištrūkti įveikusi 1313 užuominų:

RAUDONASNYKSTUKAS

Keturios paskutinės užuominos (pažymėtos pilkai) nėra būtinos, nes žodį RAKTAS pavyks sudaryti iš jau surinktų užuominų (raidės pabrauktos).

Parašykite programą, kuri rastų, kiek mažiausiai užuominų reikia atskleisti norint ištrūkti iš pabėgimo kambario.

입력

Pirmoje eilutėje pateiktas vienintelis skaičius – užuominų kiekis NN.

Antroje eilutėje pateikta NN ilgio simbolių eilutė – užuominų seka. Užuominos žymimos didžiosiomis lotyniškomis raidėmis nuo A iki Z. Pašalinių simbolių nebus.

출력

Išveskite vieną sveikąjį skaičių – mažiausią reikalingų užuominų kiekį.

Pradiniai duomenys bus tokie, kad atsakymas visada egzistuos.

제한

  • 1≤N≤1001 ≤ N ≤ 100

예제2

  1. 예제 1

    입력
    17
RAUDONASNYKSTUKAS
    예상 출력
    13

  2. 예제 2

    입력
    12
INFORMATIKAS
    예상 출력
    12