G. Ordered Pangrams

@JessyPinkman · Регистрация: 10.05.2020

Студворк — интернет-сервис помощи студентам

В XVIII веке среди байтландских литераторов было популярно следующее развлечение: необходимо было написать литературный текст на заданную тему, в котором можно было бы по возможности встретить весь латинский алфавит в правильном порядке (то есть из которого можно вычеркнуть некоторые буквы так, что в итоге получится строка из 26 латинских букв, отсортированных по возрастанию). Такие тексты называли упорядоченными панграммами
Если текст не был упорядоченной панграммой, то автор платил штраф, равный минимальному количеству букв, которые надо вставить в текст, чтобы он стал упорядоченной панграммой.
По заданному тексту вычислите штраф, который выплачивал его автор в соответствии с правилами игры.

Вход состоит из одной непустой строки, состоящей из не более, чем 50 символов и содержащей только строчные латинские буквы.

zyxabcxyz 20
acmicpcnserc 21

@Elliot_Alderson · 19.06.2021, 18:04

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def fill_dyn_matrix(x, y):
    L = [[0]*(len(y)+1) for _ in range(len(x)+1)]
    for x_i,x_elem in enumerate(x):
        for y_i,y_elem in enumerate(y):
            if x_elem == y_elem:
                L[x_i][y_i] = L[x_i-1][y_i-1] + 1
            else:
                L[x_i][y_i] = max((L[x_i][y_i-1],L[x_i-1][y_i]))
    return L
 
def LCS_DYN(x, y):
    L = fill_dyn_matrix(x, y)
    LCS = []
    x_i,y_i = len(x)-1,len(y)-1
    while x_i >= 0 and y_i >= 0:
        if x[x_i] == y[y_i]:
            LCS.append(x[x_i])
            x_i, y_i = x_i-1, y_i-1
        elif L[x_i-1][y_i] > L[x_i][y_i-1]:
            x_i -= 1
        else:
            y_i -= 1
    LCS.reverse()
    return LCS
 
alp = 'abcdefghijklmnopqrstuvwxyz'
s = input()
print(len(alp) - len(LCS_DYN(alp, s)))

О том, как работает эта программа можно почитать тут:
https://habr.com/ru/post/142825/

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@JessyPinkman 0 / 0 / 0 Регистрация: 10.05.2020 Сообщений: 57

	G. Ordered Pangrams 11.06.2021, 13:18. Показов 3337. Ответов 1 Метки нет (Все метки) В XVIII веке среди байтландских литераторов было популярно следующее развлечение: необходимо было написать литературный текст на заданную тему, в котором можно было бы по возможности встретить весь латинский алфавит в правильном порядке (то есть из которого можно вычеркнуть некоторые буквы так, что в итоге получится строка из 26 латинских букв, отсортированных по возрастанию). Такие тексты называли упорядоченными панграммами Если текст не был упорядоченной панграммой, то автор платил штраф, равный минимальному количеству букв, которые надо вставить в текст, чтобы он стал упорядоченной панграммой. По заданному тексту вычислите штраф, который выплачивал его автор в соответствии с правилами игры. Вход состоит из одной непустой строки, состоящей из не более, чем 50 символов и содержащей только строчные латинские буквы. zyxabcxyz 20 acmicpcnserc 21 0

G. Ordered Pangrams

Решение