Статья Автор: Лебедев Дмитрий

Разбор Статграда от 2024-12-17. Часть 5( 9, 17, 18)

Все задания этого блока используют данные из файлов. В заданиях 9 и 18 используются файлы формата электронных таблиц.
Эти файлы открываются, данные выделяются, копируются в блокнот и сохраняются в текстовом формате.
Считается, что эта работа проделана предварительно. К тетради приложены текстовые вариантов файлов.
Считывание данных из файла (для всех заданий) будем осуществлять с помощью функции fread (модифицируя её под задание)

Задание 9

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

Необычность формулировки в том, что кроме данных строки надо использовать данные о столбце
Для упрощения решения сделаем следующее:

Данные будем считывать функцией. В процессе считывания строку данных запишем в "словарь строк",
а элементы строк добавим к соответствующим значениям (спискам) "словарей столбцов"
Далее обрабатываем строки и определяем "требуемые"

Файл к заданию содержит 30000 строк и его обработка "простым" способом требует более 10 сек,
поэтому в решении обрабатывается только 5000 первых строк
Выводиться статистика по всем возможным количествам интересных ячеек (используем принцип "полезного вывода")

def fread (name): # функция чтения данных из файла
  k = 0 # счетчик числа записей
  for ss in open(name):
    k += 1
    A = list(map(int,ss.split()))
    Dstr[k] = A # используются словари из основной программы
    for i in range (len(A)) :
      Dcol[i].append(A[i])
  return k
def solve (X,m) : # функция подсчета интересных ячеек
  rez = 0 # инициализация ответа
  sx, k = sum(X), len(X) #  сумма ячеек и их количество
  for i in range(k): # перебор ячеек
    y = X[i] # значение ячейки
    if X.count(y) >1 : continue # ячейка не уникальная
    if y * k <= sx : continue # значение маловато
    if Dcol[i].count(y) < m : continue # вхождений в столбец маловато
    rez +=1 # ячейка уникальная
  return rez
Dstr = dict() # словарь строк
Dcol = {0 : [],1 : [],2 : [],3 : [],4 : [],5 : []} # словарь значений столбцов
print('строк =', fread('09_24-12.txt')) # вывод о числе прочитанных строк
ans, M = [0]*6 , 331 # инициализация ответа, требуемое число вхождений 331 = 330 +1
for i in Dstr : # обработка строк
  if i >= 5000 : break  # "костыль-ограничение"
  rez = solve(Dstr[i],M) # подсчет интересных ячеек
  ans[rez] +=1 # фиксация результат 
print(ans) # для ответа нужно второе значение

Представленного решения достаточно, но попробуем "загнать" решение в 10 секунд.
Что сделано "плохо"? Нет предварительной обработки столбцов !!!

Надо оставить только те значения, которые входят более M=330 раз.
Добавим функцию, которая это реализует и получим полное решение менее чем за одну секунду.

Надо ли это делать на экзамене? Скорее всего не надо (большие затраты и увеличение вероятности ошибки), но понимать как это можно сделать нужно. Рекомендуется на тренировках повышать эффективность решений.

# ... функцию чтения данных скрыли
def obrabotka (XX, M): # функция, выбирающая из XX элементы с вхождением не менее M
  A, B = set(), set()
  for x in XX:
    if (x in A) or (x in B) : continue
    k = XX.count(x)
    if k >= M : A.add(x)
    else : B.add(x)
  return A    
               
def solve1 (X,m) : # функция подсчета интересных ячеек (модифицированная)
  rez = 0 # инициализация ответа
  sx, k = sum(X), len(X) #  сумма ячеек и их количество
  for i in range(k): # перебор ячеек
    y = X[i] # значение ячейки
    if X.count(y) >1 : continue # ячейка не уникальная
    if y * k <= sx : continue # значение маловато
    if not (y in Dcol[i]) : continue # y не является частым элементом столбца
    rez +=1 # ячейка уникальная
  return rez
Dstr = dict() # словарь строк
Dcol = {0 : [],1 : [],2 : [],3 : [],4 : [],5 : []} # словарь значений столбцов
print('строк =', fread('09_24-12.txt')) # вывод о числе прочитанных строк
M = 330 + 1 # требуемое число вхождений в столбец
for i in Dcol : # дополнительная обработка
  Dcol[i] = obrabotka(Dcol[i],M)
ans = [0]*6 # инициализация ответа, требуемое число вхождений 331 = 330 +1
for i in Dstr : # обработка строк
  rez = solve1(Dstr[i],M) # подсчет интересных ячеек
  ans[rez] +=1 # фиксация результат 
print(ans) # для ответа нужно второе значение

Задание 17

Файл содержит последовательность натуральных чисел, не превышающих 100 000.
Назовём тройкой три идущих подряд элемента последовательности.
Определите количество троек, для которых выполняются следующие условия:

– остаток от деления на 3 ровно одного числа из тройки равен
остатку от деления на 3 минимального элемента всей последовательности;
– остаток от деления на 7 хотя бы двух чисел из тройки равен
остатку от деления на 7 максимального элемента всей последовательности.

Задание стандартное. Попробуем написать решение в обобщенном виде (применимое для пар, четверок и т.д.) Чтение из файла выделим в функции (для общности и, возможно, более сложной обработки).
Текст программы пишем "размашисто" (для возможной отладки печатью)

def fread (name): # функция чтения данных из файла
  return [int(s) for s in open(name)]
Dt = fread('17_24-12.txt') # список с последовательностью
a, b = min(Dt)%3, max(Dt)%7 # предварительная обработка
print('строк = {} min%3 = {} max%7 = {}'.format(len(Dt),a,b) ) 
k = 3 # длина среза (2 для пары, 3 для тройки и т.д.)
ans, sans = 0 , 0 # инициализация ответов
for i in range (k-1, len(Dt)): # пробег по срезам (тройкам)
  xyz = Dt[i-(k-1) : i+1] # выделение среза(тройки)
  ka, kb = 0, 0 # инициализация пром. ответов
  for j in xyz: # вычисление совпадений по модулю
    if j % 3 == a : ka +=1 # по модулю 3
    if j % 7 == b : kb +=1 # по модулю 7
  if (ka != 1) or (kb < 2) : continue # проверка от противного
  ans += 1 # фиксация ответа
  if sum(xyz) > sans : # проверка на максимальность суммы
    sans = sum(xyz) # фиксация суммы
    print([(x,x%3,x%7) for x in xyz], sans,ans) # отладочная печать
print(ans, sans)

Задание 18

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

Задание 1. Определите количество различных маршрутов из исходной точки в правый нижний угол поля.
Задание 2. Определите количество клеток поля, недоступных для робота из- за ограничения на допустимый перепад высот.

Новая постановка задания - отсутствуют стенки, новая формулировака задания.
Задание будем выполнять с помощью программы. Для этого файл скопировали в блокнот и сохранили в текстовом формате.
Далее будем придерживаться следующего плана:

Данные считываем функцией и заносим в словарь, где ключ - координаты ячейки, значение - кортеж вида (содержимое ячейки, количество путей /инициализация нулём)
Функция возвращает размеры таблицы
Меняем количество путей для стартовой ячейки ( (0,0) ) меняем на 1
Обходим таблицу (в зависимости от команд) и вычисляем количество путей. Если ячейка недостижима, то добавляем координаты ячейки в множество недостижимых.

def fread (name): # функция чтения данных из файла
  n, m = 0, 0  # размеры таблицы
  for ss in open(name): # читаем построчно
    A = list(map(int,ss.split())) # строку в список
    m = max(m, len(A)) # фиксация числа столбцов
    for i in range(len(A)) :
      Dt[(n,i)] = (A[i],0) # используется словарь из основной программы
    n += 1 # увиличение номера строки
  return n, m # возвращаем размер таблицы
Dt = dict() # словарь таблицы
n, m = fread('18_24-12.txt')
print('строк = {} столбцов = {}'.format(n,m)) # вывод размеров таблицы
M = 50 # допустимое отклонение высот
Dt[(0,0)] = (Dt[(0,0)][0],1) # для запуска подсчёта числа вариантов
zapret = set() # множество ячеек, в которые нельзя попасть
for i in range (n) : # обход таблицы
  for j in range (m) : 
    a, k = Dt[(i,j)] # распаковка ячейки
    if (i-1,j) in Dt and abs( a- Dt[(i-1,j)][0]) <= M : # проверка прихода по вниз
      k += Dt[(i-1,j)][1] 
    if (i,j-1) in Dt and abs( a- Dt[(i,j-1)][0]) <= M : # проверка прихода по вправо
      k += Dt[(i,j-1)][1]
    if k == 0 : # k не изменилось, значит недостижимая
      zapret.add((i,j))
    else : # фиксация числа путей
      Dt[(i,j)] = (a,k)
print(Dt[(n-1,m-1)],len(zapret)) # ответы на задания

Прикрепленные файлы
09_24-12.txt
17_24-12.txt
18_24-12.txt

Чтобы оставить комментарий нужна авторизация

Печать