Вопросы по олимпиаде

[FsGaCh]

Спасибо, проверил, всё подошло)
Кстати это ешё одно задание к которому у меня нету своего варианта:

Как известно, в разные годы дежурят и развозят подарки разные Деды Морозы. Но все они суеверны - развозят подарки на протяжении всего года, кроме дней, когда на календаре Деда Мороза "Пятница 13".
Сколько дней Дед Мороз не развозил подарки во время своего дежурства?

Входные данные
В первой строке задано количество смен k дежурства Деда Мороза.
Далее в k строках указаны года a и b (1920 ≤ a ≤ b ≤ 2050 по григорианскому календарю), попадающие на очередную смену.
Выходные данные
Вывести количество дней, когда Дед Мороз не будет развозить подарки.

Нужно ли знать календарь для этой задачи?

[BDA]

Благодаря питону знать календарь не надо.

from datetime import date
k = int(input())
res = 0
for i in range(k):
    a, b = map(int, input().split(' '))
    for year in range(a, b + 1):
        for month in range(1, 13):
            res += date(year, month, 13).weekday() == 4
print(res)

[FsGaCh]

Я уже перешёл к олимпиадным задачам, по этому к большинству у меня нету своего варианта:
1)Посчитать сумму двух натуральных чисел A и B, записанных в римской системе счисления. Ответ также записать в римской системе счисления.
M = 1000, D = 500, C = 100, L = 50, X = 10, V = 5, I = 1. Все числа – не превышают 2000.
Входные данные
В строке записано два числа в римской системе счисления, между которыми стоит знак + .
Выходные данные
Единственное число – сумма чисел, записанное также в римской системе счисления. Числа в римской системе счисления записаны большими латинскими буквами.

Не смог выполнить, дошёл до сюда:

values = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
values1 = [1, 5, 10, 50, 100, 500, 1000]
a, b = map(str, input().split('+'))
a1 = [i for i in a]
b1 = [i for i in b]
a2 = 0
b2 = 0
c1 = 0
if len(a1) == 1:
    a2 = values[a]
else:
    for i in range(len(a1) - 1):
        if values[a1[i]] >= values[a1[i+1]]:
            a2 += values[a1[i]]
            if i == len(a1) - 2:
                a2 += values[a1[i+1]]
        else:
            a2 += (values[a1[i+1]] - values[a1[i]])
if len(b1) == 1:
    b2 = values[b]
else:
    for i in range(len(b1) - 1):
        if values[b1[i]] >= values[b1[i+1]]:
            b2 += values[b1[i]]
            if i == len(b1) - 2:
                b2 += values[b1[i+1]]
        else:
            b2 += (values[b1[i+1]] - values[b1[i]])
c = a2 + b2
c_numbers = [i for i in str(c)]
c_numbers_1 = []
for i in range(len(c_numbers)):
    f = int(c_numbers[::-1][i]) * 10 ** i
    if f != 0:
        c_numbers_1.append(f)
print(c_numbers_1, c_numbers)

2)В индийском храме пол прямоугольной формы выложен одинаковыми квадратными плитками 1×1, на каждую из которых высыпано от 0 до k зернышек (k ≤ 300). Размеры пола n×m. Мышка выбегает из левого нижнего угла пола храма и двигается к входу в другую норку, расположенную в противоположном углу. Мышка может двигаться только вправо или вперед, собирая все зернышки с плитки, на которой она находится.
Найти наибольшее количество зернышек, которое может собрать мышка на своем пути.

Входные данные
Первая строка содержит числа n и m – размеры пола (1 ≤ n, m ≤ 500). Далее идет n строк, начиная сверху, в каждой из которых размещено m чисел – количества зернышек на соответствующей плитке.
Выходные данные
Одно число – наибольшее количество зернышек, которое может собрать мышка на своем пути.

3)Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости N квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами – сами спички.
Напишите программу, которая по количеству квадратов N, которое необходимо составить, находит минимальное необходимое для этого количество спичек.
Входные данные
Одно целое число N (1 ≤ N ≤ 10^18).
Выходные данные
Вывести минимальное количество спичек, требуемых для составления N квадратов.

[ViktorR]

Рассуждения по 2-ой задаче (про мышку).
Мышка двигается от нижнего левого угла к правому верхнему.
Если положить, что результат известен, то при обратном движении, от верхнего правого угла к нижнему левому, у мышки будет всегда выбор двух направлений: вперёд/вниз.
На первом шаге заполняем массив. Выбираем ячейку прямо и пишем в ней сумму собранных зёрен.
Продолжаем процесс до конца, а затем вниз до левого нижнего угла.
Аналогично можно посчитать число собираемых зёрен и при движении только вниз, а затем только влево.
Используем этот алгоритм для заполнения всех ячеек.

Теперь можно указать путь мышки и наибольшее количество собранных зёрнышек.

PS: Поскольку в данную ячейку, при движении справа налево, можно попасть двумя путями, то в саму ячейку пишем максимальную сумму из двух: сумма значения в ячейке с суммой из ячейки выше и суммой из ячейки справа.

По поводу 3-й задачи.
Для выкладывания первого квадрата нужны 4-е спички.
Для минимизации числа спичек следующие квадраты используют уже выложенные спички.
Можно показать, что для выкладывания прямоугольника с числом квадратов m*n потребуется:
K = 2*m*n + m + n спичек.
Пусть мы выкладываем вначале квадрат из квадратиков (1), а затем из оставшихся спичек достраиваем квадратики до заданного N (2).
(1)
В квадрате из квадратиков m = n.
Нам требуется 2*m^2 + 2*m спичек.
Получим m как ближайшее целое к корню квадратному из N.

(2)
Нам необходимо выложить ещё z = N - m^2 квадратиков.
Число этих квадратиков не превышает z <= m*k, где k - число рядов квадратиков, дополняющих наш квадрат до N квадратиков.
Понятно, что [z / m] - это число рядов квадратиков, которые надо доложить (берём целую часть от деления).
Теперь посчитаем число построенных квадратиков: m * (m + k).
Для их построения нам нужно известное число спичек, см. формулу выше (n = m + k).
Возможно, что нам потребуется достроить ещё несколько квадратиков в последнем ряду:
p = N - m * (m + k)
Для их построения потребуется ещё 2*p + 1 спичка.

Собственно всё. Осталась самая малость - реализовать на ЯВУ.

[ViktorR]

Моё решение задачи о спичках:

from math import floor, sqrt

def Spichek(N):
    m = floor(sqrt(N))
    z = N - m**2
    if not z:  # z == 0
        # нет дополнительных рядов: N == m**2
        return 2 * m**2 + 2 * m
    k = z // m
    p = N - m * (m + k)
    if not p:  # p == 0
        # нет последнего ряда: прямоугольник m * (m + k)
        return 2 * m * (m + k) + 2 * m + k
    # есть последний ряд из p квадратов
    return 2 * m * (m + k) + 2 * m + k + 2 * p + 1

N = int(input('Введите целое число <= 10^18)'))
print('Минимальное число спичек: ', Spichek(N))

PS: Я не обосновал свой алгоритм.
Собственно почему изначально выбираем квадрат из квадратиков, а затем расширяем (достраиваем) до прямоугольника и, наконец, достраиваем последний ряд.
Обоснование:
Так как фигура, которую мы строим состоит из квадратиков, то для минимизации площади, занимаемой этими квадратиками нам необходимо строить квадрат.
После построения квадрата вновь пристраиваемые квадратики должны использовать границы уже построенной фигуры, поскольку при этом минимизируется число используемых спичек.

PSS: k - пристраиваемое число рядов. Если k чётное, то ряды можно пристраивать и снизу и справа.
Т.е. форма будет оставаться "квадратной", но без части квадратов в нижнем правом углу ...
Нас интересует не форма фигуры и каким способом мы пристраиваем оставшиеся квадратики - не важно.

  _  _   _
I   I   I   I
  -   -   -
I   I   I   I              N = 3*3 = 9
  -   -    -
I   I   I   I
  -   -   -

  _  _   _
I   I   I   I
  -   -   -
I   I   I   I         N = 3*3 + 3 = 12
  -   -    -
I   I   I   I
  -   -   -
I   I   I   I
  -   -   -

  _  _   _
I   I   I   I
  -   -   -
I   I   I   I         N = 3*3 +3 + 2 = 14
  -   -    -
I   I   I   I
  -   -   -
I   I   I   I
  -   -   -
I   I   I
  -   -

[ViktorR]

Вот реализация алгоритма для поиска числа зёрен, собранных мышкой.
1. Этот алгоритм был описан в одной из книг. Мне удалось найти в Сети книгу:
В. Потопахин, Turbo Pascal, Решение сложных задач, 2006
В ней описан алгоритм "Поиск пути с наибольшим весом" и дан пример на Паскале.
К сожалению и описание алгоритма и его реализация грешат ошибками. Видимо спешили для издания (это последняя часть книги). Хотя находил много ошибок и в других главах.
Но это не важно. Важно, что алгоритм рабочий. Его реализацию на Python и привожу.

2. Поскольку пол храма - это двумерный массив, то для его описания выбрал библиотеку Numpy.
В этом случае обращение к элементам массива как и в Pascal.

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

 7 13  2           22 15  2      a = max(15, 5) + 5 = 20    d = max(26, 30) + 18 = 48
 4  5  3            b  a  5      b = max(22, 20) + 4 = 26
18  7 18            d  c 23      c = max(20,23) + 7 = 30

4. Добавил вывод маршрута мышки

Размер пола и число зёрен задаём в тексте скрипта после комментария # ---- Main -----

''' Задача о мышке.
   В индийском храме пол прямоугольной формы выложен одинаковыми квадратными плитками 1×1,
на каждую из которых высыпано от 0 до k зернышек (k ≤ 300). Размеры пола n × m.
   Мышка выбегает из левого нижнего угла пола храма и двигается к входу в другую норку,
расположенную в противоположном углу. Мышка может двигаться только вправо или вперед,
собирая все зернышки с плитки, на которой она находится.
   Найти наибольшее количество зернышек, которое может собрать мышка на своем пути.
   Входные данные: Первая строка содержит числа n и m – размеры пола (1 ≤ n, m ≤ 500).
                   Далее идет n строк, начиная сверху, в каждой из которых размещено
                   m чисел – количества зернышек на соответствующей плитке.
   Выходные данные: Одно число – наибольшее количество зернышек, которое может собрать мышка
                    на своем пути.
'''
# n - число строк, m - число столбцов
import numpy as np
from random import randint

def InitData(np_mas):
    ''' Заполняем таблицу единичными значениями
    '''
    (n, m) = np_mas.shape
    for i in range(n):     # i - номер строки
        for j in range(m): # m  - номер столбца
            np_mas[i][j] = randint(0, zmax)  # число зёрен в квадрате
    # что получилось

def IntermediateData(np_mas):
    ''' Подготовим вспомогательный массив
    '''
    (n, m) = np_mas.shape
    for j in range(m - 2, -1, -1):                          # верхняя строка
        np_mas[0, j] = np_mas[0, j] + np_mas[0, j + 1]
    for i in range(1, n):                                   # правый столбец
        np_mas[i, m - 1] = np_mas[i, m - 1] + np_mas[i - 1, m - 1]
      
    for i in range(1, n):                    # i - номер строки
        for j in range(m - 2, -1, -1):       # m  - номер столбца
           # Возможное число собранных зёрнышек
            np_mas[i, j] = np_mas[i, j] + max(np_mas[i, j + 1], np_mas[i - 1, j])
    return np_mas[n - 1, 0]

def FindTrace(np_mas2):
    ''' Поиск пути
    '''
    (n, m) = np_mas2.shape
    np_str = np.full((n, m), '.', dtype = str)
    i = n - 1; j = 0
    np_str[i, j] = 'Q'
    while True:
        if i == 0 and j == m - 1:
            break
        if i == 0:
            j += 1
        elif j == m - 1:
            i -= 1
        elif np_mas2[i - 1, j] > np_mas2[i, j + 1]:
            i -= 1
        else:
            j += 1
        np_str[i, j] = 'Q'
    return np_str

# ======= Main =======
n = 7      # число строк
m = 7      # число столбцов
zmax = 20  # число зёрен

np_mas = np.zeros((n, m), dtype = int)
InitData(np_mas) # Размещение зёрен
print(np_mas)    # Основной массив

# Используем вспомогательный массив
np_tmp = np.zeros((n, m), dtype = int)
np_tmp = np_tmp + np_mas

k = IntermediateData(np_tmp) # Подготовим вспомогательный массив
                             # Посчитаем число собранных зёрен
print('Зёрен собрано: ', k)
# print(np_tmp) # Тестовая печать вспомогательного массива
print('Путь мышки:')
print(FindTrace(np_tmp))    # Печать карты перемещения мышки

PS: Не всё выполнено аккуратно, но работает

[ViktorR]

К предыдущему посту.
Примеры работы скрипта:
Число зёрен 0 - 20.
Размер пола 3, 7

[[14  4  3 20  5  5  2]
 [10  3 18  5 20 20 14]
 [18  8 15 19 14  9 15]]
Зёрен собрано:  130
Путь мышки:
[['.' '.' '.' '.' '.' '.' 'Q']
 ['.' '.' '.' '.' 'Q' 'Q' 'Q']
 ['Q' 'Q' 'Q' 'Q' 'Q' '.' '.']]

Число зёрен 0 - 20.
Размер пола 4, 4

[[13  7  7 13]
 [11  2 18 15]
 [18  6  2 15]
 [12 12 14  2]]
Зёрен собрано:  89
Путь мышки:
[['.' '.' '.' 'Q']
 ['Q' 'Q' 'Q' 'Q']
 ['Q' '.' '.' '.']
 ['Q' '.' '.' '.']]

Число зёрен 0 или 1
Размер пола 4, 4

[[0 0 0 1]
 [0 0 1 0]
 [0 1 1 1]
 [0 0 1 0]]
Зёрен собрано:  4
Путь мышки:
[['.' '.' '.' 'Q']
 ['.' '.' '.' 'Q']
 ['.' '.' 'Q' 'Q']
 ['Q' 'Q' 'Q' '.']]

[FsGaCh]

3 задания, которые не смог выполнить:

1)Задано два натуральных числа A и B. Найти количество таких пар чисел (P, Q), что для них A является НОД(P, Q), а B – НОК(P, Q).
Входные данные
В единственной строке два натуральных числа A и B (A < 105, B ≤ 106).
Выходные данные
Единственное число – искомое количество пар.

Мой вариант(не работает):

nod, nok = map(int, input().split())
xy = nod * nok
poss = []
x = 0
y = 0
for i in range(1, xy // 2 + 1):
    if xy / i == 0:
        x = i
        y = xy / i
        for k in range(1, x // 2  + 1):
            if x % k == 0 and y % k == 0:
                nod1 = k
        if y % x == 0:
            nod1 = x
        nok1 = (x * y) / nod1
        if nod1 == nod and nok1 == nok:
            poss.append(sort(list(map(int, (str(x) + ' ' + str(y)).split()))))
print(len(poss))

2)Найти НОД (наибольший общий делитель) n чисел.
Входные данные
Первая строка содержит количество чисел n (1 < n < 101). Во второй строке через пробел заданы n натуральных чисел, каждое из которых не превышает 30000.
Выходные данные
НОД заданных чисел.

Мой вариант(выводит ошибку):

def nod(x, y):
    for i in range(0, x + 1):
        if x % i == -1 and y % i == 0:
            nod = i
    return nod
n = int(input())
nums = list(map(int, input().split()))
nod = nod(nums[0], nums[1])
if len(nums) > 2:
    for i in range(2, len(nums)):
        nod = nod(nod, nums[i])
print(nod)

3)Определить площадь четырёхугольника с вершинами A(x1,y1), B(x2,y2), C(x3,y3), D(x4,y4).
Входные данные
В одной строке заданы координаты последовательных вершин четырёхугольника. Все числа целые, не превышающие по модулю 100.
Выходные данные
Вывести площадь четырёхугольника, округленную до целых.

Мой вариант (выводит ошибку):

x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split())
print(int(fabs(y1 - y2) * fabs(x1 - x4)))

[ViktorR]

Сходу по 3-ей:
Четырёхугольник может быть и не прямоугольником и не параллелограммом.
Многоугольник лучше разбивать на треугольники и считать их площади по формуле Герона.

[ViktorR]

По поводу второй - найти НОД

for i in range(0, x + 1):
        if x % i == -1 and y % i == 0:
            nod = i
    return nod

Что за странное условие?
Если i - НОД, то остатки должны быть нулевыми для обоих чисел.
С другой стороны, думаю, что было бы быстрее, если начать искать НОД от меньшего из чисел и в сторону убывания последнего.
Т.е. проверяем какое меньшее.
Пытаемся делить большее на меньшее, если делится, то хорошо.
Ищем первый делитель для меньшего числа (делим на 2, 3, ... и если находим делитель, то выбираем больший и проверяем на остальных числах.

Добавлено:
Так получилось у меня. Но не проверял на выборке.

def findNOD(a):
    NOD = min(nlist)                         # Начальное значение НОД
    for i in range(NOD, 2, -1):              # от максимально возможного
        if not max(map(lambda x: x % i, a)): # все остатки равны нулю
            return i
    else:
        return 1

N = int(input('Количество чисел: '))
slist = input('Строка натуральных чисел: ')

nlist = list(map(int, slist.split()))
NOD = findNOD(nlist)
print(NOD)