алгоритмы

2 вариант

1 задача

Дана матрица а размером n*m и массив чисел х размером m В данной матрице заменить все элементы строки с максимальной суммой элементов на элементы заданного массива чисел. Если таких строк несколько, то заменить элементы в строке с наименьшим индексом. Ничего вводить или выводить НЕ нужно. Нужно написать программу, обрабатывющую матрицу с указанным именем и размерами; и ис- пользуюущую одномерный массив чисед с указанным именем.

# Ввод количества строк и столбцов
n = int(input()) # Количество строк
m = int(input()) # Количество столбцов

# Ввод матрицы a размером n * m a = [] # Пустая матрица

for i in range(n): # Повторяем n раз (по количеству строк) a.append(list(map(int, input().split()))) # Вводим строку и

преобразуем в список чисел

# Ввод массива чисел x размером m
x = list(map(int, input().split())) # Вводим m чисел и сохраняем в список x

# Шаг 1. Найдём строку с максимальной суммой элементов
max_sum = -10**10 # Переменная для хранения максимальной суммы max_index = 0 # Индекс строки с максимальной суммой

for i in range(n): # Перебираем строки матрицы
s=0 # Здесь будем хранить сумму элементов строки for j in range(m): # Перебираем элементы строки

        s += a[i][j]
    if s > max_sum:

ранее

        max_sum = s
        max_index = i

# Шаг 2. Заменяем найденную строку на массив x
for j in range(m): # Перебираем элементы в строке

a[max_index][j] = x[j] # Заменяем элемент строки на соответствующий элемент из массива x

# Проверка (если нужно) — вывод матрицы после изменений

for i in range(n):
print(*a[i]) # Выводим строку матрицы через пробел

# Складываем элементы строки
# Если сумма этой строки больше найденной

# Обновляем максимум
# Запоминаем номер строки

3 3

12 3

12 3

00 0

99 9

99 9

12 3

00 0

2 задача

Напишите программу для решения следующей задачи. Алексей составляет N-буквенные последовательности из букв слова М, А, Г. И, Я. Программа должна вывести:

1. Номер последней последовательности, в которой каждая буква встречается не более одного раза, причем среди них не больше двух гласных. Если такой последовательности в списке нет, вывести 0. Нумерация последовательностей начинается с 1.

2. Все последовательности, которые может составить Алексей, в лексикографическом порядке. Входные данные: Вводится одно натуральное число N (2 <= $ N $ <= 8) Выходные данные: Программа должна вывести ответы на задачу: в первой строке - ответ на первый вопрос, в по-следующих - ответ на второй вопрос.

letters = ['А', 'Г', 'И', 'М', 'Я'] # Буквы по алфавиту vowels = ['А', 'И', 'Я'] # Гласные буквы

n = int(input()) # Ввод длины слова words = [] # Список всех слов

# Функция генерации всех слов на рекурсии (без циклов)

def generate(s):
if len(s) == n: # Если слово нужной длины

words.append(s) # Добавляем его в список

return

add_letter(s, 0) # Начинаем добавлять буквы с позиции 0

# Функция добавления букв на позицию — вместо цикла

def add_letter(s, i):
if i == len(letters): # Проверка выхода за границу

return

generate(s + letters[i]) # Добавляем букву и углубляем рекурсию add_letter(s, i + 1) # Переходим к следующей букве

# Проверка подходит ли слово по условиям

def good(word):
if len(set(word)) != len(word): # Если буквы не разные

return False
return count_vowels(word, 0, 0) <= 2 # Проверяем число гласных

# Подсчёт гласных в слове на рекурсии

def count_vowels(word, i, c):
    if i == len(word):

return c # Возвращаем кол-во гласных if word[i] in vowels:

        return count_vowels(word, i + 1, c + 1)
    return count_vowels(word, i + 1, c)

# Поиск последнего подходящего слова на рекурсии

def find_last(i):
    if i == len(words):

return 0 # Не нашли
res = find_last(i + 1) # Проверяем дальше if res > 0:

return res # Нашли подходящее дальше if good(words[i]):

return i + 1 # +1 потому что нумерация с 1 return 0

# Вывод всех слов на рекурсии

def print_words(i):
    if i == len(words):

return

    print(words[i])
    print_words(i + 1)

# Запуск программы

generate('')
ans = find_last(0)

print(ans)
print_words(0)

1 5 А Г И М Я

# Генерация слов
# Поиск ответа

# Ответ на 1 вопрос
# Ответ на 2 вопрос

3 задача

Напишите программу, которая определяет во введсином тексте слова, содержащие 7 гласных букв. Сло- вом будем считать любую непрерывную последовательность букв, справа и слева ограниченную любыми другими символами, кроме букв; либо началом (концом) строки. Строчные и прописные буквы не разли- чаются. Найденные слова нужно вывести в обратном алфавитном порядке, каждое слово должно выводиться один раз. Различыми считаются слова, отличающиеся хотя бы одним символом. Прмечание: гласные буквы русского алфавита а. у. о, ы, и, э. я, ю. е. е. Вводится русский текст, состоящий из нескольких строк (ввод из файла, текст на русском языке)

# Открываем файл с текстом для чтения (кодировка utf-8 для русского текста)
f = open('name.txt', encoding='utf-8')

s = f.read() # Считываем весь текст в переменную s f.close() # Закрываем файл

# Множество гласных букв

vowels = 'ауоыиэяюеё'
# Перебираем символы и заменяем все, что не буквы, на пробелы

alf = 'абвгдеёжзийклмнопрстуфхцчшщъыьэюя'

new_s = '' # Строка, куда будем записывать только буквы и пробелы for c in s:

if c.lower() in alf: # Если буква — добавляем new_s += c.lower()

else: # Если не буква — ставим пробел new_s += ' '

# Разбиваем строку на слова

words = new_s.split()

# Множество найденных слов с 7 гласными (чтобы не было повторов)

result = set()

# Проверяем каждое слово

for word in words:
count = 0 # Счетчик гласных в слове for c in word:

        if c in vowels:
            count += 1

if count == 7: # Если ровно 7 гласных — добавляем слово result.add(word)

# Выводим найденные слова в обратном алфавитном порядке

for word in sorted(result, reverse=True):
    print(word)

4 задача

Дан массив из п чисел, отсортированный по неубыванию, и к запросов. Для каждого запроса выведите максимальный номер элемента массива, меньший данного (нумерация элементов массива начинается с 1). Входные данные В первой строке входных данных содержатся числа п и к (0 < n, k <= 105) — длина массива и число запросов. Во второй строке содержатся п элементов массива, отсортированного по не-убыванию. В третьей строке содержатся запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2•10^9 . Выходные данные Для каждого из k запросов выведите максимальный комер элемента массива, меньший дан-ного. Если таких нет, выведите 0.

# Функция бинарного поиска
# Ищет максимальный индекс элемента массива a, который меньше x def bin_search(a, x):

l = -1 # Левая граница поиска (до начала массива)
r = len(a) # Правая граница поиска (после конца массива)

while r - l > 1: # Пока границы не сомкнулись m = (l + r) // 2 # Находим середину
if a[m] < x: # Если середина меньше x

l = m # Сдвигаем левую границу else: # Иначе середина >= x

r = m # Сдвигаем правую границу
return l + 1 # Возвращаем номер элемента (индексация с 1)

# Основная часть программы
n, k = map(int, input().split()) # Вводим размер массива и число запросов
a = list(map(int, input().split())) # Вводим массив (он уже отсортирован)
queries = list(map(int, input().split())) # Вводим запросы

for x in queries: # Перебираем каждый запрос print(bin_search(a, x)) # Выводим ответ для каждого запроса

55

0 2 3 0 5

3358 9

2 4 8 1 10

5 задача

Напишите программу для решения следующей задачи. Кандидаты в отряд космонавтов проходят 3 испытания, за каждое из которых можно получить от 0 до 100 баллов. Кроме того, можно получить дополнительные от 0 до 10 баллов по итогам со-беседования. Каждому кандидату присваивается уникальный идентификационный номер (ID) - натуральное число, не превышающее 100 000. В отряде имеется фиксированное число мест, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется по убыванию суммы набранных баллов, включая баллы за собе-седование. При равенстве сумм баллов в рейтинговом списке выше стоит участник с бОльшими баллами за собеседование. Если и эти баллы равны, то кандидаты в рейтинговом списке располагаются в порядке возрастания их ID. В отряд на все вакантные места зачисляются кандидаты согласно рейтинговому списку. Входные данные: В первой строке находятся два натуральных числа, не превышающих 10 000, через пробел: число N - количество кандидатов и число К - количество мест в отряде. В следующих N строках находятся по 5 чисел через пробел: ID кандидата (натуральное число, не превышающее 100 000) и четыре целых неотрицательных числа - сначала результаты испытаний, затем результат собеседования. Выходные данные: Программа должна вывести К строк - список ID кандидатов, зачисленных в отряд космонавтов, в том порядке, в котором они расположены в рейтинговом списке.

# Ввод количества кандидатов и мест

n, k = map(int, input().split())
candidates = [] # Список для хранения информации о кандидатах

# Ввод данных о каждом кандидате

for i in range(n):
data = list(map(int, input().split())) # ID и баллы
ID = data[0]
score_tests = sum(data[1:4]) # Сумма баллов за 3 испытания score_interview = data[4] # Баллы за собеседование total_score = score_tests + score_interview # Общая сумма баллов candidates.append(( -total_score, -score_interview, ID ))
# Добавляем кортеж: (отрицательные баллы для сортировки по

убыванию, потом ID)

# Сортируем список кандидатов по правилам:
# 1) по убыванию total_score
# 2) при равенстве по убыванию score_interview # 3) при равенстве по возрастанию ID candidates.sort()

# Выводим ID первых k кандидатов из отсортированного списка

for i in range(k):
print(candidates[i][2]) # ID хранится третьим элементом кортежа

1 вариант

1 задача

Дана матрица а размером n*m • и массив чисел х размером m. В данной матрице заменить все элементы строки с максимальной суммой элементов на элементы заданного массива чисел. Если таких строк несколько, то заменить элементы в строке с наибольшим индексом.

# Ввод количества строк и столбцов
n = int(input()) # Количество строк
m = int(input()) # Количество столбцов

# Ввод матрицы a размером n * m a = [] # Пустая матрица

for i in range(n): # Повторяем n раз (по количеству строк) a.append(list(map(int, input().split()))) # Вводим строку и

преобразуем в список чисел

# Ввод массива чисел x размером m
x = list(map(int, input().split())) # Вводим m чисел и сохраняем в список x

# Шаг 1. Найдём строку с максимальной суммой элементов
max_sum = -10**10 # Переменная для хранения максимальной суммы max_index = 0 # Индекс строки с максимальной суммой

for i in range(n): # Перебираем строки матрицы
s=0 # Здесь будем хранить сумму элементов строки for j in range(m): # Перебираем элементы строки

        s += a[i][j]
    if s > max_sum:

ранее

        max_sum = s
        max_index = i

# Шаг 2. Заменяем найденную строку на массив x
for j in range(m): # Перебираем элементы в строке

a[max_index][j] = x[j] # Заменяем элемент строки на соответствующий элемент из массива x

# Проверка (если нужно) — вывод матрицы после изменений

for i in range(n):
print(*a[i]) # Выводим строку матрицы через пробел

# Складываем элементы строки
# Если сумма этой строки больше найденной

# Обновляем максимум
# Запоминаем номер строки

2 задача

Напишите программу для решения следующей задачи. Вася составляет N-символьные последовательности из букв слова С, И, Р, О, П, причём в каждой последовательности обязательно есть ровно одна бухва О, при этом стоять она может только после согласной буквы. Программа должна вывести:

1. Сколько последовательностей может составить Вася.

2. Все последовательности, которые может составить Вася, в лексикографическом порядке. Входные данные: Вводится одно натуральное число N (2 ≤ N <= 8) Выходные данные: Программа должна вывести ответы на задачу: в первой строке - ответ на первый вопрос, в по-следующих - ответ на второй вопрос.

def rec(s, n, count_o, result):
if len(s) == n: # Если длина строки равна n

if count_o == 1: # Ровно одна 'О' result.append(s) # Добавляем в результат

return

letters = 'ИПРСО' # Буквы по порядку

def try_letters(index): # Рекурсивный перебор букв
if index == len(letters): # Все буквы просмотрели

return

        c = letters[index]
        if c == 'О':

if count_o == 0 and len(s) > 0 and s[-1] in 'ПРС': # 'О' только после согласной

                rec(s + c, n, count_o + 1, result)
        else:

rec(s + c, n, count_o, result) try_letters(index + 1) # Следующая буква

try_letters(0) # Начинаем перебор

def print_rec(result, index): # Функция для рекурсивного вывода if index == len(result): # Все напечатали

return

print(result[index]) # Печатаем элемент print_rec(result, index + 1) # Переходим к следующему

n = int(input()) # Ввод длины строки
result = [] # Результирующий список строк
rec('', n, 0, result) # Запускаем рекурсию для генерации строк

print(len(result)) # Сначала выводим количество строк print_rec(result, 0) # Вывод всех строк рекурсией

1 0

3 задача

Напишите программу, которая определяет слова, встречающиеся в тексте максимальное количество раз и выводит их в обратном алфавитном порядке. Словом будем считать любую непрерывную последователь-ность букв, справа и слева ограниченную любыми другими символами, кроме букв; либо началом (кон-цом) строки. Строчные и прописные буквы русского алфавита не различаются. Вводится текст, состоящий из нескольких строх (ввод из файла, текст на русском языке) | Вывести в обратном алфавитном порядке слова, встречающиеся в тексте максимальное количество раз. Каждое слово нужно вывести в отдельной строке

# Открываем файл и читаем текст

file = open('input.txt', encoding='utf-8')
s = file.read() # Читаем весь текст в строку file.close()

# Делаем все буквы строчными

s = s.lower()

# Убираем все символы кроме букв (заменяем на пробел)

for c in s:
    if not ('а' <= c <= 'я' or c == 'ё'):

s = s.replace(c, ' ')
# Разбиваем текст на слова по пробелам

words = s.split()

# Создаем словарь для подсчета количества слов

d = dict()

for word in words:
d[word] = d.get(word, 0) + 1 # Если слово уже есть — увеличиваем

счётчик
# Находим максимальное количество повторений

max_count = max(d.values())

# Собираем слова, которые встречаются max_count раз

result = []
for word in d:

    if d[word] == max_count:
        result.append(word)

# Сортируем в обратном алфавитном порядке

result.sort(reverse=True)

# Выводим слова

for word in result:
    print(word)

4 задача

Требуется определить в заданном массиве количество элементов, равных искомому числу. Входные данные В первой строке вводится одно натуральное число N, не превосходящее 105: количество чисел в массиве. Во второй строке вводятся N натуральных чисел, не превосходящих 10°. каждое следующее не меньше предыдущего. В третьей строке вводится количество искомых чисел М - натуральное число, не превосходящее 106. В четвертой строке вводится М натуральных чисел, не превосходящих 10°. Выходные данные Для каждого запроса выведите в отдельной строке одно число: количество элементов массива. равных числу-запросу. Элементы массива нумеруются с единицы. Если в массиве нет такого числа, выведите О.

def left_bound(a, x):
# Ищем левую границу (первое вхождение x) l, r = -1, len(a)
while r - l > 1:

        m = (l + r) // 2
        if a[m] >= x:

r=m else:

l=m return r

def right_bound(a, x):
# Ищем правую границу (первое число больше x) l, r = -1, len(a)
while r - l > 1:

        m = (l + r) // 2
        if a[m] > x:

r=m else:

l=m return r

# Ввод данных

n = int(input())
a = list(map(int, input().split()))
(отсортированных)
m = int(input())
queries = list(map(int, input().split())) # Список из m запросов

# Обработка каждого запроса

for x in queries:
    lb = left_bound(a, x)
    rb = right_bound(a, x)

 # Кол-во чисел в массиве
# Список из n чисел

# Кол-во запросов

    if lb < len(a) and a[lb] == x:
        count = rb - lb

    else:
        count = 0

    print(count)

2 11 2 11 2
2

5 задача

Напишите программу для решения следующей задачи. Кандидаты в отряд космонавтов проходят 3 испытания, за каждое из которых можно получить от 0 до 100 баллов. Кроме того, можно получить дополнительные от 0 до 10 баллов по итогам со-беседования. Каждому кандидату присваивается уникальный идентификационный номер (ID) - натуральное число, не превышающее 100 000. В отряде имеется фиксированное число мест, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется по убыванию суммы набранных баллов, включая баллы за собе-седование. При равенстве сумм баллов в рейтинговом списке выше стоит участник с бОльшими баллами за собеседование. Если и эти баллы равны, то кандидаты в рейтинговом списке располагаются в порядке возрастания их ID. В отряд на все вакантные места зачисляются кандидаты согласно рейтинговому списку. Входные данные: В первой строке находятся два натуральных числа, не превышающих 10 000, через пробел: число N - количество кандидатов и число К - количество мест в отряде. В следующих N строках находятся по 5 чисел через пробел: ID кандидата (натуральное число, не превышающее 100 000) и четыре целых неотрицательных числа - сначала результаты испытаний, затем результат собеседования. Выходные данные: Программа должна вывести К строк - список ID кандидатов, зачисленных в отряд космонавтов, в том порядке, в котором они расположены в рейтинговом списке.

# Ввод количества кандидатов и мест

n, k = map(int, input().split())
candidates = [] # Список для хранения информации о кандидатах

# Ввод данных о каждом кандидате

for i in range(n):
data = list(map(int, input().split())) # ID и баллы
ID = data[0]
score_tests = sum(data[1:4]) # Сумма баллов за 3 испытания score_interview = data[4] # Баллы за собеседование total_score = score_tests + score_interview # Общая сумма баллов candidates.append(( -total_score, -score_interview, ID ))
# Добавляем кортеж: (отрицательные баллы для сортировки по

убыванию, потом ID)

# Сортируем список кандидатов по правилам:
# 1) по убыванию total_score
# 2) при равенстве по убыванию score_interview # 3) при равенстве по возрастанию ID candidates.sort()

# Выводим ID первых k кандидатов из отсортированного списка

for i in range(k):
print(candidates[i][2]) # ID хранится третьим элементом кортежа