ЧИТПАК К ОЛИМПИАДЕ

Памятка к олимпиаде

Помните, что в условиях задач часто используется нумерация индексов от 1, а не от 0.

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

При загрузке готовой программы на сервер комментируйте весь отладочный вывод.

Проверяйте, что при загрузке программы на сервер указан интерпретатор питона именно третьей версии.

Сортировка

Параметр key:

def sum1(a)
    return a[0] + a[1]

L = [[0, 4], [5, 3], [5, 1], [2, 3]]

L.sort()
# L отсортирован сначала по первому элементу вложенных списков,
# если они равны, то по второму
print(L)

L.sort(key=sum1)
# L отсортирован не сравнением двух элементов x и y,
# а сравнением sum1(x) и sum1(y), то есть, по возрастанию
# cуммы элементов во вложенных списках
print(L)

Модуль bisect

Решение задачи “Очень сложная задача” с сайта informatics.mccme.ru (№490).

import bisect


N, x, y = input().split()
N = int(N)
x = int(x)
y = int(y)
if x > y:
    x, y = y, x
# Теперь x всегда быстрый принтер.


# Функция возвращает количество страниц, которые можно напечатать
# за время time.
def pages(time):
    if time < x:
        return 0
    # Быстрый принтер печатает сначала, второй с задержкой x секунд
    return time // x + (time - x) // y
# Так как f на самом деле пользуется x и y, а не их копиями,
# то их нельзя изменять.


# Обёртка вокруг функции f, чтобы ей можно было пользоваться
# как массивом.
# После этих четырёх строк доступ к элементу a[i] будет преобразован
# в вызов функции pages(i)
class FunctionAsArray:
    def __getitem__(self, index):
        return pages(index)
a = FunctionAsArray()

start = 1  # Нижняя граница поиска: 1 секунда
end = N * x + 1  # Верхняя граница: печатаем только быстрым принтером
                 # прибавляем 1, так как bisect_left не включает правый индекс.
answer = bisect.bisect_left(a, N, lo=start, hi=end)
print(answer)

Решения задач на бинарный поиск по ответу

Ссылки на условия всех задач на dz11.programming1189.ru

Решение задачи “Дракон”:

Hd = int(input())  # health dragon
Dd = int(input())  # damage dragon
hp = int(input())  # health pike
dp = int(input())  # damage pike


def damage(pikes):
    """Сколько урона нанесут pikes копейщиков
    с уроном dp и здоровьем hp
    дракону с уроном Dd"""
    pikes_health = pikes * hp
    dmg = 0
    while pikes_health > 0:
        pikes_alive = (pikes_health + hp - 1) // hp
        dmg += pikes_alive * dp
        pikes_health -= Dd
    return dmg


class FunctionAsArray:
    def __getitem__(self, index):
        return damage(index)
a = FunctionAsArray()


start_pikes = 1
end_pikes = (Hd + dp - 1) // dp + 1
import bisect
needed_pikes = bisect.bisect_left(
    a, Hd, lo=start_pikes, hi=end_pikes
)
print(needed_pikes)

Решение задачи “Cookie Clicker”:

C = int(input())  # Cтоимость фабрики
P = int(input())  # Производительность фабрики
N = int(input())  # Сколько нужно печенек
def cookies(time):
    n_factory = 0
    n_cookie = 0
    while True:
        production = 1 + n_factory * P
        t1 = (C + production - 1) // production
        if time < t1:  # Нет времени на покупку фабрики
            return n_cookie + production * time
        n_cookie += production * t1
        time -= t1
        if 1 * time > (1 + P) * time - C:
            # Если невыгодно покупать фабрику
            return n_cookie + production * time
        n_factory += 1
        n_cookie -= C


class FunctionAsArray:
    def __getitem__(self, index):
        return cookies(index)
a = FunctionAsArray()


start_time = 1
end_time = N + 1
import bisect
needed_time = bisect.bisect_left(a, N,
            lo=start_time, hi=end_time)
print(needed_time)

Решение задачи про последовательность 0 и 1:

N = int(input())
a = [0] * (N + 1)
b = [0] * (N + 1)
a[1] = 1
b[1] = 1
for i in range(2, N + 1):
    a[i] = a[i - 1] + b[i - 1]
    b[i] = a[i - 1]
print(a[N] + b[N])

Решение задачи про количество различных проходов в дамку:

# import pprint
a = int(input())
a -= 1
b = int(input())
b -= 1


L = []
for i in range(8):
    inner = []
    for j in range(8):
        inner.append(0)
    L.append(inner)

L[a][b] = 1


def inside(i, j):
    return 0 <= i < 8 and 0 <= j < 8

for i in range(a + 1, 8):
    for j in range(8):
        left = 0
        if inside(i - 1, j - 1):
            left = L[i-1][j-1]
        right = 0
        if inside(i - 1, j + 1):
            right = L[i-1][j+1]
        L[i][j] = left + right
    # pprint.pprint(L)
    # print('i =', i)
    # print()
print(sum(L[7]))

Алгоритм Дейкстры

(work in progress, он ужасен и недоделан)

def dijkstra(N, a, neighbours):
    assert 0 <= a < N
    inf = 'inf'
    visited = [False] * N
    costs = [inf] * N
    costs[a] = 0
    for _ in range(N):
        min1 = inf
        for i in range(N):
            if ((not visited[i]) and (costs[i] != inf) and
                     (min1 == inf or costs[i] < min1)):
                min1 = costs[i]
                minInd = i
        for j in range(neighbours[minInd]):
            nb = neighbours[minInd][j]
            w = weights[minInd][j]
            if costs[nb] == inf or costs[minInd] + w < costs[nb]:
                costs[nb] = costs[minInd] + w
        visited[minInd] = True