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

[BDA]

Вместо объявления функции "p" можно написать просто "p = print".
1)

p_list = list(map(int, input().split()))
p_in_one, p_rem = divmod(sum(p_list), 3)
print("IMPOSSIBLE" if p_rem else sum(map(lambda i: abs(i - p_in_one), p_list)) // 2)

2) Получилось не особо компактно. Вроде никакой случай не потерял. Сохранить сначала все веса в один список не очень хорошая затея - может не хватить памяти.

max_val, max_count = None, 0
min_val, min_count = None, 0
s_sum, s_count = 0, 0

while True:
    try:
        for i in map(int, input().split()):
            if max_val is None:
                max_val, max_count = i, 1
                continue

            if min_val is None:
                if i > max_val:
                    min_val, min_count = max_val, max_count
                    max_val, max_count = i, 1
                elif i < max_val:
                    min_val, min_count = i, 1
                else:
                    max_count += 1
                continue

            if i > max_val:
                s_sum += max_val * max_count
                s_count += max_count
                max_val, max_count = i, 1
                continue

            if i == max_val:
                max_count += 1
                continue

            if i < min_val:
                s_sum += min_val * min_count
                s_count += min_count
                min_val, min_count = i, 1
                continue

            if i == min_val:
                min_count += 1
                continue

            s_sum += i
            s_count += 1
                    
    except EOFError:
        if s_count:
            print(round(s_sum / s_count))
        break

3)

t = (0, 0)
way = 0
ways = [(0, 1), (1, 0), (0, -1), (-1, 0)]
places = set([t])
for s in input():
    if s == "S":
        t = tuple(map(sum, zip(t, ways[way])))
        if t in places:
            print(len(places))
            break
        places.add(t)
    elif s == "L":
        way = (way + 3) % 4
    else:
        way = (way + 1) % 4
else:
    print(-1)

[FsGaCh]

Одно задание которое не получилось

1)Какое наименьшее число n можно представить в виде произведения n = a∙b ровно k способами? Произведения a∙b и b∙a считаются одним способом, все числа натуральные (1 ≤ k ≤ 50).

Входные данные

Единственное число – значение k.

Выходные данные

Единственное число – значение n.

Пример

Пример входных данных
2

Пример выходных данных
4

k = int(input())
deliteli = []
n = 2
while len(deliteli) // 2 + 1 != k:
    deliteli = [1, n]
    for i in range(1, n // 2 + 1):
        if n % i == 0:
            deliteli.append(i)
    n += 1
print(n - 1)

[BDA]

Ну перебор всех N слишком дорогое удовольствие. Немного подумал в сторону представления числа, как произведения степеней нескольких простых чисел. В конце концов просто нашел достаточно хорошее объяснение решения на просторах интернета. Практическую реализацию оставляю на вашей совести.

[FsGaCh]

Дробь вида m/n называется правильной, если 0 ≤ m < n и несократимой если НОД(m, n) = 1. Для заданного положительного целого n, в этой задаче необходимо найти количество несократимых правильных дробей со знаменателем n.

Например, существует всего лишь 4 несократимых правильных дроби со знаменателем 12:

1/12, 5/12, 7/12 и 11/12.

Входные данные

Каждая строка входных данных содержит одно единственное целое число n (n < 2000000000) и ввод продолжается пока не встретится число 0 в качестве n (для этого значения входные данные не обрабатываются).

Выходные данные

Для каждого n в выходном файле выведите в отдельной строке количество несократимых правильных дробей со знаменателем n.

Дошёл до сюда, подумывал продолжить но посмотрел в примеры и узнал что мне не уложится во временной лимит:

n = int(input())
while n != 0:
    dels = []

[BDA]

Название задачи на e-olymp само намекает, что стоит изучить теорию, связанную с функцией Эйлера.

[FsGaCh]

Это задание получилось очень грамостким, но думаю оно работает. Как можно упростить?

Кладбище имеет форму прямоугольника, в котором N рядов по M могил в каждом ряду. Кладбище окружено высокой стеной.
Лара Крофт по ночам проникает на кладбище через подкоп с северо-западного угла. За одну ночь она успевает прорыть подземный ход под одной из могил по такому правилу:
Если дальше по ходу движения находится целая могила, то Лара продолжает ход вперёд и расхищает содержимое этой могилы.
Если же впереди стена кладбища или уже разорённая могила, то Лара поворачивает на 90 градусов вправо и продолжает своё нелёгкое дело.
Сокровища находятся всего в двух могилах, и мы знаем, в каких, но Лара этого не знает. Сегодня ночью по дороге домой Лара купила ящик шампанского, значит, сегодня она нашла одну из могил с сокровищами. Мы хотим понять, через сколько дней она найдёт другую могилу?
Исходные данные
В первой строке записаны целые числа N и M — размеры кладбища (2 ≤ N, M ≤ 100). Северо-западная могила имеет координаты (1, 1), а юго-восточная — (N, M). Лара начинает с могилы (1, 1), двигаясь на восток, то есть к могиле (1, 2).
Во второй и третьей строке записаны целые числа (r1, c1) и (r2, c2) — координаты могил с сокровищами (1 ≤ ri ≤ N; 1 ≤ ci ≤ M). Порядок могил не фиксирован, поэтому может случиться и так, что Лара дороет ход до второй могилы раньше, чем до первой.
Результат
Выведите, через сколько дней Лара найдёт оставшиеся сокровища.

y, x = map(int, input().split())
y1, x1 = map(int, input().split())
y2, x2 = map(int, input().split())
graveyard = [[0 for i in range(x)] for k in range(y)]
n = [None, None]
graveyard[x1 - 1][y1 - 1], graveyard[y2 - 1][x2 - 1] = 2, 2
boolean, currentPosX, currentPosY = 0, 0, 0
while inside(graveyard, 2) and n[0] != True:
    if boolean == 0:
        if currentPosX == x - 1:
            boolean = 1
        elif graveyard[currentPosY][currentPosX + 1] == 1:
            boolean = 1
        else:
            if graveyard[currentPosY][currentPosX] == 2:
                if n[0] is None:
                    n[0] = False
                    n[1] = 0
                elif n[0] is False:
                    break
            graveyard[currentPosY][currentPosX] = 1
            currentPosX += 1
            if n[0] is False:
                n[1] += 1
    elif boolean == 1:
        if currentPosY == y - 1:
            boolean = 2
        elif graveyard[currentPosY + 1][currentPosX] == 1:
            boolean = 2
        else:
            if graveyard[currentPosY][currentPosX] == 2:
                if n[0] is None:
                    n[0] = False
                    n[1] = 0
                elif n[0] is False:
                    break
            graveyard[currentPosY][currentPosX] = 1
            currentPosY += 1
            if n[0] is False:
                n[1] += 1
    elif boolean == 2:
        if currentPosX == 0:
            boolean = 3
        elif graveyard[currentPosY][currentPosX - 1] == 1:
            boolean = 3
        else:
            if graveyard[currentPosY][currentPosX] == 2:
                if n[0] is None:
                    n[0] = False
                    n[1] = 0
                elif n[0] is False:
                    break
            graveyard[currentPosY][currentPosX] = 1
            currentPosX -= 1
            if n[0] is False:
                n[1] += 1
    else:
        if currentPosY == 0:
            boolean = 0
        elif graveyard[currentPosY - 1][currentPosX] == 1:
            boolean = 0
        else:
            if graveyard[currentPosY][currentPosX] == 2:
                if n[0] is None:
                    n[0] = False
                    n[1] = 0
                elif n[0] is False:
                    break
            graveyard[currentPosY][currentPosX] = 1
            currentPosY -= 1
            if n[0] is False:
                n[1] += 1
print(n[1])

[BDA]

Думаю, что можно еще сократить.

def grave_number(n, m, i, j):
    ring = min([i, j, n - i + 1, m - j + 1])
    prev_ring = ring - 1
    s = 0

    if ring > 1:
        s += 2 * prev_ring * (n + m - 2 * prev_ring)

    if i == ring:
        return s + j - prev_ring
    else:
        s += m - 2 * prev_ring

    if m - j + 1 == ring:
        return s + i - ring
    else:
        s += n - 2 * prev_ring - 1

    if n - i + 1 == ring:
        return s + m - j - prev_ring
    else:
        s += m - 2 * prev_ring - 1

    return s + n - i - prev_ring

n, m = map(int, input().split())
r1, c1 = map(int, input().split())
r2, c2 = map(int, input().split())
print(abs(grave_number(n, m, r1, c1) - grave_number(n, m, r2, c2)))

Идея в том, чтобы узнать номер могилы по её координатам. Если бы поле было больше, чем 100 на 100, то пытаться его просто обойти может быть слишком долго или дорого по памяти.