Форум программистов
 
О проблемах с регистрацией пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль.

Вернуться   Форум программистов > Скриптовые языки программирования > Python
Регистрация

Восстановить пароль
Повторная активизация e-mail


Ответ
 
Опции темы
Старый 25.07.2020, 15:33   #91
FsGaCh
Пользователь
 
Регистрация: 08.02.2020
Сообщений: 73
По умолчанию

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

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

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

Нужно ли знать календарь для этой задачи?
FsGaCh вне форума Ответить с цитированием
Старый 25.07.2020, 16:31   #92
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 5,858
По умолчанию

Благодаря питону знать календарь не надо.
Код:
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)
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA на форуме Ответить с цитированием
Старый 26.07.2020, 12:20   #93
FsGaCh
Пользователь
 
Регистрация: 08.02.2020
Сообщений: 73
По умолчанию

Я уже перешёл к олимпиадным задачам, по этому к большинству у меня нету своего варианта:
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 квадратов.
FsGaCh вне форума Ответить с цитированием
Старый 26.07.2020, 21:00   #94
ViktorR
Участник клуба
 
Регистрация: 23.10.2010
Сообщений: 1,788
По умолчанию

Рассуждения по 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; 26.07.2020 в 22:18.
ViktorR вне форума Ответить с цитированием
Старый 26.07.2020, 23:00   #95
ViktorR
Участник клуба
 
Регистрация: 23.10.2010
Сообщений: 1,788
По умолчанию

Моё решение задачи о спичках:
Код:
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; 26.07.2020 в 23:29.
ViktorR вне форума Ответить с цитированием
Старый 28.07.2020, 21:33   #96
ViktorR
Участник клуба
 
Регистрация: 23.10.2010
Сообщений: 1,788
По умолчанию

Вот реализация алгоритма для поиска числа зёрен, собранных мышкой.
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 вне форума Ответить с цитированием
Старый 28.07.2020, 21:41   #97
ViktorR
Участник клуба
 
Регистрация: 23.10.2010
Сообщений: 1,788
По умолчанию

К предыдущему посту.
Примеры работы скрипта:
Число зёрен 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' '.']]
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 09.08.2020, 12:27   #98
FsGaCh
Пользователь
 
Регистрация: 08.02.2020
Сообщений: 73
По умолчанию

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)))
FsGaCh вне форума Ответить с цитированием
Старый 09.08.2020, 13:44   #99
ViktorR
Участник клуба
 
Регистрация: 23.10.2010
Сообщений: 1,788
По умолчанию

Сходу по 3-ей:
Четырёхугольник может быть и не прямоугольником и не параллелограммом.
Многоугольник лучше разбивать на треугольники и считать их площади по формуле Герона.
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 10.08.2020, 21:14   #100
ViktorR
Участник клуба
 
Регистрация: 23.10.2010
Сообщений: 1,788
По умолчанию

По поводу второй - найти НОД
Код:
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)
Как-то так, ...

Последний раз редактировалось ViktorR; 10.08.2020 в 23:47.
ViktorR вне форума Ответить с цитированием
Ответ
Купить рекламу на форуме 20000 рублей в месяц

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
готовлюсь к олимпиаде по информатике salauat Паскаль, Turbo Pascal, PascalABC.NET 25 01.12.2013 20:32
Подготовиться к олимпиаде за лето UaKot Свободное общение 20 10.05.2013 17:53
Подготовка к региональной олимпиаде New man Помощь студентам 20 14.12.2012 20:01
Задачи по олимпиаде Darick Помощь студентам 7 23.12.2011 14:45
Как подготовиться к олимпиаде? Kn793 Помощь студентам 16 26.07.2008 11:22


Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru
Пеллетный котёл Emtas
котлы EMTAS