QOJ.ac

QOJ

Límite de tiempo: 3 s Límite de memoria: 512 MB Puntuación total: 100 Dificultad: [mostrar] Interactivo

#194. Құпиясөз

Estadísticas

Мен құпиясөзімді тағы да ұмытып қалдым! Компьютерімнің алдында отырып, қате құпиясөздерді теріп жатырмын. Есімде қалғаны — құпиясөзім тек кіші әріптерден тұрады. Бақытыма орай, жүйеге кіру қызметі тек «қате құпиясөз» деп қана жауап бермейді. Ол сондай-ақ менің енгізген жолымның құпиясөзде (міндетті түрде қатар орналаспаған) ішкі тізбек ретінде кездесетін ең ұзын префиксінің ұзындығын да айтады. Формалды түрде, $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" мәнін қайтаруы тиіс.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.