Задача 6099. Источник: Поляков. Задание КИМ 24

Страница задачи 6099

Решение

Создадим массив d из 16 элементов, где будем подсчитывать количество каждой цифры шестнадцатеричной системы в текущем фрагменте строки, а в переменной k - количество найденных уникальных цифр. Фрагмент ограничен позициями left и right. Пока не найдены все 16 цифр, сдвигаем позицию right. После нахождения всех цифр, сдвигаем позицию left, пока одна из цифр не исчезнет из подстроки. Циклически повторяем поиск до конца исходной строки, анализируя длину каждой подстроки со всеми 16 цифрами на возможный минимум.

Python

s = open('24-249.txt').readline()
mn = len(s)
k = 0
d = [0] * 16
left = 0
right = 0
while right < len(s):
    while right < len(s) and k < 16:
        if s[right] <= 'F':
            i = int(s[right], 16)
            d[i] += 1
            if d[i] == 1:
                k += 1
        right += 1
    if k == 16:
        mn = min(mn, right - left)
    while k == 16:
        if s[left] <= 'F':
            i = int(s[left], 16)
            d[i] -= 1
            if d[i] == 0:
                k -= 1
        left += 1
        if k == 16:
            mn = min(mn, right - left)
print(mn)

PascalABC

var
    i, min, k, left, right: Integer;
    s: String;
    d: Array of Integer := ArrFill(16, 0);
    f: TEXT;
begin
    Assign(f, '24-249.txt');
    Reset(f);
    Readln(f, s);
    min := s.Length;
    k := 0;
    left := 1;
    right := 1;
    while right <= s.Length do
    begin
        while (right <= s.Length) and (k < 16) do
        begin
            if s[right] <= 'F' then
            begin
                if s[right] <= '9' then
                    i := ord(s[right]) - 48
                else
                    i := ord(s[right]) - 55;
                d[i] := d[i] + 1;
                if d[i] = 1 then
                    k := k + 1
            end;
            right := right + 1;
        end;
        if (k = 16) and (right - left < min) then
            min := right - left;
        while k = 16 do
        begin
            if s[left] <= 'F' then
            begin
                if s[left] <= '9' then
                    i := ord(s[left]) - 48
                else
                    i := ord(s[left]) - 55;
                d[i] := d[i] - 1;
                if d[i] = 0 then
                    k := k - 1
            end;
            left := left + 1;
            if (k = 16) and (right - left < min) then
                min := right - left;
        end;
    end;
    Writeln(min);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("24-249.txt");
    string s;
    f >> s;
    int min = s.length();
    int i, k = 0, left = 0, right = 0;
    int d[16] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    while (right < s.length())
    {
        while (right < s.length() && k < 16)
        {
            if (s[right] <= 'F')
            {
                if (s[right] <= '9')
                    i = (int)s[right] - 48;
                else
                    i = (int)s[right] - 55;
                d[i]++;
                if (d[i] == 1)
                    k++;
            }
            right++;
        }
        if (k == 16 && right - left < min)
            min = right - left;
        while (k == 16)
        {
            if (s[left] <= 'F')
            {
                if (s[left] <= '9')
                    i = (int)s[left] - 48;
                else
                    i = (int)s[left] - 55;
                d[i]--;
                if (d[i] == 0)
                    k--;
            }
            left++;
            if (k == 16 && right - left < min)
                min = right - left;
        }
    }
    cout << min << endl;
}

Ответ

42

Отправить замечание по решению