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

[FsGaCh]

Сообщение от BDA

k = 0
dist = 0
prev_k = 0
while True:
    try:
        for i in map(int, input().split()):
            if k == 0:
                a = i
                k += 1
                continue
            elif k == 1:
                b = i
                k += 1
                continue
            else:
                c = i
            if a > b < c:
                if prev_k > 0:
                    cur_dist = k - prev_k - 1
                    if cur_dist > dist:
                        dist = cur_dist
                prev_k = k - 1
            a = b
            b = c
            k += 1
    except EOFError:
        print(dist)
        break

Может быть что-то не учел.

Спасибо, попробовал, работает. Но я изменил и свой вариант, теперь он работает:

l = list(map(int, input().split()))
l1 = list(map(int, input().split()))
l.extend(l1)
ms = []
for i in range(1, len(l)-1):
    if l[i-1] > l[i] < l[i+1]:
        ms.append(i)
biggest = -1
for i in range(1, len(ms)-1):
    if math.fabs(ms[i] - ms[i - 1]) > biggest:
        biggest = math.fabs(ms[i] - ms[i - 1])
    if math.fabs(ms[i] - ms[i + 1]) > biggest:
        biggest = math.fabs(ms[i] - ms[i+1])
print(int(biggest))

Стало намного короче.

[BDA]

Ну если игнорировать наличие переноса строки во входных данных и возможную длину входной последовательности, то:

def f(x):
    i, (a, b, c) = x
    return a > b < c

l1 = list(map(int, input().split()))
l2 = [i for i, a in filter(f, enumerate(zip(l1, l1[1:], l1[2:])))]
print(max(b - a for a, b in zip(l2, l2[1:])))

[FsGaCh]

Дан квадратный торт, который имеет вид таблицы размером r × c. Каждая ячейка таблицы содержит либо гадкую клубничку, либо является пустой. Например, торт размера 3 × 4 может выглядеть так:


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

Пожалуйста, выведите максимальное количество ячеек, которые может съесть Тортминатор.

Входные данные
Первая строка содержит два целых числа r и c (2 ≤ r, c ≤ 10), обозначающих количество строк и количество столбцов в торте. Следующие r строк содержат по c символов — j-ый символ i-ой строки обозначает содержимое ячейки в строке i и столбце j, и имеет одно из следующих значений:

символ '.' обозначает ячейку торта без гадкой клубнички;
символ 'S' обозначает ячейку торта с гадкой клубничкой.
Выходные данные
Выведите максимальное количество ячеек торта, которые может съесть тортминатор.

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

r, c = map(int, input().split())
t = []
am = 0
for i in range(r):
    t.append(input())
for i in range(r):
    if 'S' not in t[i] and t[i] != c * '#':
        for k in range(c):
            if t[i][k] == '.':
                am += 1
                t[i][k] = '#'
for i in range(c):
    j = []
    for k in range(r):
        j.append(t[k][i])
    if 'S' not in j and j != '#' * r:
        for k in range(r):
            if j[k] == '.':
                am += 1
                t[k][i] = '#'
print(am)

[BDA]

Чуть поправил ваш вариант:

r, c = map(int, input().split())
t = []
am = 0
for i in range(r):
    t.append(list(input()))
for i in range(r):
    if 'S' not in t[i] and t[i] != ['#'] * c:
        for k in range(c):
            if t[i][k] == '.':
                am += 1
                t[i][k] = '#'
for i in range(c):
    j = []
    for k in range(r):
        j.append(t[k][i])
    if 'S' not in j and j != ['#'] * r:
        for k in range(r):
            if j[k] == '.':
                am += 1
                t[k][i] = '#'
print(am)

[FsGaCh]

3 задачи которые не смог сделать:
1)Последовательностью Хэмминга называется последовательность чисел, в порядке возрастания, имеющие из простых делителей только 2, 3, 5. Например, первые 10 чисел этой последовательности таковы: 2, 3, 4, 5, 6, 8, 9, 10, 12, 15. По заданному N найти N-ое число этой последовательности. Нумерация элементов последовательности начинается с 0.
Формат входных данных
Одно число N (0 <= N <= 1000).
Формат выходных данных
В единственной строке искомое число.

2)Рассмотрим последовательность натуральных чисел, в десятичной записи кото*рых встречаются только цифры 1, 3, 7, записанной в порядке возрастания. Вот первые эти числа: 1, 3, 7, 11, 13, 17, 31, 33, 37… По заданному N найти N-ое число этой последовательности. Нумерация элементов последовательности начинается с 1.
Формат входных данных
Одно число N (0 < N <= 1018).
Формат выходных данных
В единственной строке искомое число.

Мой вариант:

def contains(n):
    l = []
    for i in str(n):
        if i == '1' or i == '3' or i == '7':
            l.append(i)
    if len(l) == len(str(n)):
        return True
    else:
        return False
n = int(input())
c = 1
num = 1
while c != n:
    if contains(num):
        c += 1
        num += 1
print(num)

3)По заданным натуральным числам m и n найти десятичную запись дроби m/n с указанием периода.
Входные данные
В единственной строке через пробел заданы два натуральных числа: m и n (0 < m < n <= 108).
Выходные данные
Единственное число – ответ к задаче в виде: 0.число_до_периода (период).

[VeryStupidPerson]

В Вашем коде проверяется в два раза больше чисел, чем нужно. Число никогда не будет делится нацело на числа больше своей половины. Исправьте range(1, n+1) на range(1, n // 2 + 1) и прибавьте к списку после цикла for само число.

[FsGaCh]

Сообщение от VeryStupidPerson

В Вашем коде проверяется в два раза больше чисел, чем нужно. Число никогда не будет делится нацело на числа больше своей половины. Исправьте range(1, n+1) на range(1, n // 2 + 1) и прибавьте к списку после цикла for само число.

Извините, но это к какому заданию относится?

[VeryStupidPerson]

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

n = int(input())
all = ''
for i in range(1, n+1):
    if n % i == 0:
        all = all + str(i) + ' '
print(all)

[FsGaCh]

Ешё 2 задачки:
1)На день рождения Пете подарили набор карточек с буквами. Теперь Петя с большим интересом составляет из них разные слова. И вот, однажды, составив очередное слово, Петя заинтересовался вопросом: "А сколько различных слов можно составить из тех же карточек, что и данное?".

Помогите ему ответить на этот вопрос.

2)Как-то раз, придя домой со школы, Света обнаружила записку от мамы, в которой она просила сделать салат. Света знала, что салат – это смесь двух или более ингредиентов, поэтому ей не составило труда выполнить мамину просьбу.

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

Зная, что вы любите интересные задачки, и хотите стать программистами, Света попросила вас написать программу, которая определяет количество различных салатов для произвольного числа ингредиентов.

К обеим у меня нету своего варианта.

[BDA]

Про салаты. Пусть количество ингредиентов N. Нужно посчитать сумму из сочетаний от из N по 2 до из N по N (количество сочетаний из N по K равно N!/(K!*(N-K)!) ). Вольфрамальфа услужливо упростила сумму сочетаний:

n = int(input())
print(2 ** n - 1 - n)

Еще проще обосновать формулу, если посчитать бинарное число длины N рецептом салата. Единички будут обозначать необходимость положить ингредиент. Всего чисел такой длины 2^N. При этом рецепты со всеми нулями (один такой рецепт) и с одной единичкой не подходят (N рецептов). Поэтому вычитаем 1 и N.

Про карточки. Если все буквы уникальны, то ответ - факториал от длины слова. Чтобы учесть повторы букв, еще делю на факториалы количеств повторов каждой буквы.

import math 
import collections

s = input()
res = math.factorial(len(s))
for v in collections.Counter(list(s)).values():
    res //= math.factorial(v)
print(res)

Про Хэмминга. Решения на любой вкус и цвет: https://rosettacode.org/wiki/Hamming_numbers

Про 1, 3, 7. Перебор всех чисел по очереди не уложится по времени для такого большого N. Нужно сразу строить число:

n = int(input()) - 1
k = 3
c = 1
while n >= k:
    n -= k
    k *= 3
    c += 1
res = ''
while c:
    res = "137"[n % 3] + res
    n //= 3
    c -= 1
print(res)