Alisher parollarni uzunligi bo'yicha o'sish tartibida kiritadi.
Demak:

• To'g'ri paroldan qisqaroq uzunlikdagi barcha parollar, tartibidan qat'i nazar, har doim to'g'ri paroldan oldin sinaladi — bular muqarrar noto'g'ri urinishlar.
• To'g'ri parol bilan bir xil uzunlikdagi boshqa parollar esa ixtiyoriy tartibda kiritilishi mumkin — ular to'g'ri paroldan oldin ham, keyin ham kelishi mumkin. Aynan shu joyda eng yaxshi va eng yomon holat farqlanadi.
• To'g'ri paroldan uzunroq parollar hech qachon undan oldin sinalmaydi — ular natijaga umuman ta'sir qilmaydi.

Agar to'g'ri parol jami hisobda m-urinishda topilsa (ya'ni undan oldin aynan m−1 ta noto'g'ri urinish bo'lgan bo'lsa):

• less — to'g'ri paroldan qisqaroq parollar soni,
• same — to'g'ri parol bilan bir xil uzunlikdagi boshqa parollar soni (to'g'ri parolning o'zisiz).
• Eng yaxshi holat: to'g'ri parol o'z uzunlik guruhida birinchi bo'lib sinaladi: m_best = less + 1
• Eng yomon holat: to'g'ri parol o'z uzunlik guruhida oxirgi bo'lib sinaladi: m_worst = less + same + 1

Vaqt

Har bir urinish 1 soniya oladi, va har k ta ketma-ket noto'g'ri urinishdan so'ng qo'shimcha 5 soniyalik bloklanish bo'ladi. Agar to'g'ri parolgacha jami m−1 ta noto'g'ri urinish bo'lsa, bloklanishlar soni \(⌊(m−1)/k⌋\) ga teng. Demak:

\(time(m) = m + 5 × ⌊(m − 1) / k⌋\)

Bu funksiya m bo'yicha monoton o'suvchi (m ortishi bilan vaqt hech qachon kamaymaydi), shuning uchun:

- minimal vaqt — time(m_best)
- maksimal vaqt — time(m_worst)

ni hisoblash yetarli, barcha mumkin bo'lgan tartiblarni sanab chiqish shart emas.

Algoritm qadamlari

1. Barcha n ta parolning uzunliklarini o'qib olish.
2. To'g'ri parolning uzunligi L ni aniqlash.
3. Bitta tsikl bilan less (uzunligi < L) va same (uzunligi = L, o'zidan tashqari) sonlarini hisoblash.
4. m_best = less + 1 va m_worst = less + same + 1 ni topish.
5. Yuqoridagi formula bo'yicha ikkala javobni hisoblab chiqarish.

Murakkablik

- Vaqt bo'yicha: \(O(n · L)\) — har bir parolning uzunligini olish (yoki oldindan hisoblab qo'yish orqali O(n)), bu yerda L — parol uzunligi (\(n, L ≤ 100\) bo'lgani uchun bu ahamiyatsiz darajada tez).
- Xotira bo'yicha: \(O(n)\) — parollarni saqlash uchun.

Real cheklovlar (\(n, k ≤ 100\), \(s ≤ 100\)) juda kichik bo'lgani uchun hatto sodda O(n²) yechim ham vaqt limitiga (2000 ms) bemalol sig'adi.

Namuna kod (C++)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;

    vector<string> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];

    string s;
    cin >> s;

    int len = s.size();
    int less_cnt = 0, same_cnt = 0;

    for(int i = 0; i < n; i++){
        int l = a[i].size();
        if(l < len) less_cnt++;
        else if(l == len && a[i] != s) same_cnt++;
    }

    int best = less_cnt + 1;
    int worst = less_cnt + same_cnt + 1;

    int t1 = best + 5 * ((best - 1) / k);
    int t2 = worst + 5 * ((worst - 1) / k);

    cout << t1 << " " << t2 << endl;
    return 0;
}