Мен құпиясөзімді тағы да ұмытып қалдым! Компьютерімнің алдында отырып, қате құпиясөздерді теріп жатырмын. Есімде қалғаны — құпиясөзім тек кіші әріптерден тұрады. Бақытыма орай, жүйеге кіру қызметі тек «қате құпиясөз» деп қана жауап бермейді. Ол сондай-ақ менің енгізген жолымның құпиясөзде (міндетті түрде қатар орналаспаған) ішкі тізбек ретінде кездесетін ең ұзын префиксінің ұзындығын да айтады. Формалды түрде, $P = p_1 p_2 \dots p_N$ құпиясөзі мен $Q = q_1 q_2 \dots q_N$ енгізуі үшін жүйеге кіру қызметінің жауабы — барлық $1 \le i \le L$ үшін $q_i = p_{k_i}$ шарты орындалатындай $1 \le k_1 < k_2 < \dots < k_L \le N$ индекстері табылатын ең үлкен $L$ саны. Жүйе маған құпиясөзімнің ұзындығы $N$ санын және құпиясөзімде әліпбидің тек алғашқы $S$ әрпі қолданылатынын білдіретін $S$ санын да хабарлайды. Мысалы, $S = 4$ болса, менің құпиясөзім тек $\text{a}$, $\text{b}$, $\text{c}$ және $\text{d}$ әріптерінен тұрады (бірақ олардың барлығы бірдей кездесуі міндетті емес).
Құпиясөзімді қалпына келтіруге көмектесіңізші!
Іске асыру мәліметтері
Бұл — интерактивті есеп. Сіз келесі функцияны іске асыруыңыз керек:
C: char* guess(int n, int s);
C++: string guess(int n, int s);
- Аргументтері: жоғарыда сипатталғандай $N$ және $S$.
- Қайтаратын мәні: дұрыс құпиясөз.
Сіздің программаңыз келесі функцияны шақыра алады:
C: int query(char* str);
C++: int query(string str);
- Аргументі: әліпбидің алғашқы $S$ әрпінен құралған, ұзындығы $1$-ден $N$-ге дейінгі жол.
- Қайтаратын мәні: $0$ мен
strұзындығының арасындағы бүтін сан — сіздің сұранысыңызға жүйеге кіру қызметінің берген жауабы. - Компиляция қателерін болдырмау үшін бұл функцияны шақырмас бұрын жаһандық көріну аймағының кез келген жерінде жоғарыдағы мәтінді дәл сол күйінде пайдаланып жариялауыңыз керек.
- Әр тест жағдайы үшін бұл функцияны ең көбі $50\,000$ рет шақыра аласыз.
Программаңызда қосымша функцияларды анықтауға болады.
Үлгі грейдер
Кодыңызды жергілікті түрде тексеру үшін үлгі grader.{c,cpp} берілген. Үлгі грейдер кіріс деректерін password.in файлынан келесі форматта оқиды:
- $1$-жол: $N$ $S$
- $2$-жол: құпиясөз
Грейдерді өз шешіміңізбен бірге компиляциялай аласыз. Содан кейін алынған орындалатын файлды іске қосып, берілген кіріс деректерінде құпиясөзді табу стратегияңызды тексере аласыз.
Ішкі есептер
Тесттер топ бойынша бағалануы мүмкін. Ішкі есептер ретімен төмендегідей:
| Ішкі есеп | Ұпай үлесі | Кіріс шектеулері |
|---|---|---|
| 1 | 10% | $N \le S \le 26$; құпиясөздегі барлық әріптер әртүрлі |
| 2 | 20% | $2 \le N \le 100$ және $2 \le S \le 4$ |
| 3 | 20% | $2 \le N \le 2\,000$ және $2 \le S \le 20$ |
| 4 | 30% | $2 \le N \le 3\,500$ |
| 5 | 20% | $2 \le N \le 5\,000$ |
Мысалдар
Құпиясөз $\text{aab}$ болсын. Грейдер guess(3, 2) функциясын шақырады. Шақырулар журналы келесідей болуы мүмкін:
| Шақыру | Қайтаратын мәні |
|---|---|
guess("ab") |
2 |
guess("abb") |
2 |
guess("bab") |
1 |
guess("aab") |
3 |
Осы сәтте guess(3, 2) функциясы "aab" мәнін қайтаруы тиіс.