Олимпиада в честь дня рождения Югорского НИИ информационных технологий (7-8 класс)

Задача A. Крузо

Выведем сначала нужное число букв "V", а затем нужное число "I".

n = int(input())

s = ""
for i in range(n // 5):
    s += "V"
for i in range(n % 5):
    s += "I"

print(s)

Задача B. Ромб

Сделаем ровно то, что написано в условии задачи.

n = int(input())
a = int(input())
b = int(input())

x = [["."] * n for i in range(n)]

k = n // 2

for i in range(n):
    for j in range(n):
        if a <= abs(i - k) + abs(j - k) <= b:
            x[i][j] = "*"

for z in x:
    print("".join(z))

Задача C. Штангист

Промоделируем процесс описанный в условии задачи:

n = int(input())
a = list(map(lambda x: x == "1", input().split()))

ans = 0
for i in range(n):
    x, y = map(int, input().split())
    if a[i]:
        if x < y:
            ans += y - x

print(ans)

Задача D. Хаотические разбиения

Научимся сначала генерировать все возможные разбиения рекурсивным перебором.

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

Чтобы оставить только хаотические, не ставим, чтобы предпоследнее слагаемое стало равно полусумме соседей.

a[i - 1] != (a[i - 2] + a[i]) / 2
2 * a[i - 1] != a[i - 2] + a[i]
a[i] != 2 * a[i - 1] - a[i - 2]

И получаем следующий код.

def search(n, prefix=[], x=0, y=0):
    if n == 0:
        return print(*prefix, sep='+')
    for z in range((y + 1) if y else 1, n + 1):
        if x and x + z == 2 * y:
            continue
        search(n - z, prefix + [z], y, z)


n = int(input())
search(n)

Задача E. Генераторы квадратов

Раз сумма без любого слагаемого - полный квадрат, в качестве слагаемых можно использовать только числа вида n - x*x для целых x, обозначим их как b[1], b[2], …, b[t] Таких чисел порядка квадратного корня из n.
 
Надо почитать число способов представить n в виде суммы k слагаемых, каждое из заданного массива b.

Можно воспользоваться опять рекурсивным перебором вариантов.

def search(x, n, k, prefix):
    if k == 1:
        if n > prefix[-1] and n in terms_set:
            print("YES")
            print(*(prefix + [n]))
            exit(0)
        return
    if x == len(terms) or terms[x] * k > n:
        return
    search(x + 1, n - terms[x], k - 1, prefix + [terms[x]])
    search(x + 1, n, k, prefix)


n, k = map(int, input().split())
terms = []
for x in range(1, n):
    if x * x >= n:
        break
    terms.append(n - x * x)
terms.sort()
terms_set = set(terms)
search(0, n, k, [])
print("NO")