vladrus13's blog

By vladrus13, history, 4 years ago, In Russian

Приседания. (Первая лига А)

Будем идти циклом от 1 до $$$n$$$ и складывать все числа, либо просто воспользуемся формулой $$$1\,+\,2\,+\,3\,+\,...\,+\,n\,=\,n\,*\,(n\,+\,1)\,/\,2$$$

n = int(input())
print(n * (n + 1) // 2)

Игра. (Первая лига B)

Сыграем в эту игру! Заведем счетчик ходов $$$c$$$ и в цикле будем уменьшать здоровье скелета $$$n$$$ на нужное число

n = int(input())
c = 0
while n > 0:
    c += 1
    if c % 5 == 0:
        n -= 10
    else:
        n -= 1

print(c)

Открытка на день рожденья. (Первая лига C, Высшая лига A)

Просто посчитаем, сколько дырочек придется вырезать для каждой цифры. Для чисел 0, 4, 6 и 9 придется вырезать одну дырочку, а для числа 8 целых две. Теперь посмотрим на число и для каждой цифры прибавим нужное число дырок

n = input()
s = 0
for c in n:
    if c == '0' or c == '4' or c == '6' or c == '9':
        s += 1
    if c == '8':
        s += 2
print(s)

Путь Ежика. (Первая лига D, Высшая лига B)

Запишем для каждого числа от 1 до $$$n$$$ на какой позиции оно находится. Пусть это будет массив $$$b$$$. Теперь мы очень легко вычислим, сколько же надо Ежику преодолеть, что бы добраться от $$$k$$$ до $$$k + 1$$$ числа. Это просто $$$abs(b[k] - b[k + 1])$$$. Мы хотим пройти все числа от 1 до $$$n$$$, то есть это расстояние от 1 до 2, от 2 до 3, и так далее.

n = int(input())
a = [int(x) for x in input().split()]
b = [0] * n
for i in range(n):
    b[a[i] - 1] = i
s = 0
for i in range(n - 1):
    s += abs(b[i] - b[i + 1])
print(s)

Строительство дома. (Первая лига E, Высшая лига C)

Давайте заметим один факт — блоки в доме сверху мы должны ставить самые ненадежные, тогда снизу будут находиться блоки покрепче. Будем строить дом сверху вниз. Отсортируем все блоки по возрастанию надежности и будем брать всегда самые ненадежный еще не взятый блок и ставить его внизу всех. Может оказаться, что взятый блок не выдержит уже построенной башни, тогда этот блок смело выкидывается. Таким образом, мы просто строим башню и затем берем ее длину

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
s = 0
for x in a:
    if x >= s:
        s += 1
print(s)

Купоны. (Первая лига F, Высшая лига D)

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

Отлично, теперь у нас есть все подарки, кроме самого дорогого и все купоны, кроме самого дорогого. Куда выгоднее отдать самый дорогой купон из оставшихся? Конечно же, за самый дорогой подарок из оставшихся...

И продолжая так до самого конца (или пока купоны не закончатся, мы продолжаем отдавать за самый дорогой подарок самый дорогой купон). То есть за $$$i$$$-ый по дороговизне подарок мы отдаем $$$i$$$-ый по дороговизне купон.

n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

a.sort(reverse=True)
b.sort(reverse=True)

s = 0
for i in range(n):
    if i < m:
        s += max(a[i] - b[i], 0)
    else:
        s += a[i]

print(s)

Оценки за контрольную. (Первая лига G, Высшая лига E)

Давайте установим такое правило: если мы обошли по результатам $$$i$$$ человек, то у нас будет $$$i$$$ баллов. Тогда выходит, что в любой ситуации, когда у нас такая расстановка людей возможна, каждый получит правильный балл, потому что люди, обогнавшие людей по результатам контрольной, действительно по баллам будут выше. Однако иногда у нас попадаются невозможные ситуации, и мы просто проверяем, правильно ли мы расставили баллы простым проходом по всем людям и проверкой того, что каждый ученик обогнал нужное число людей.

n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

for i in range(n):
    aa = 0
    bb = 0
    for j in range(n):
        if a[j] < a[i]:
            aa += 1
        if a[j] > a[i]:
            bb += 1
    if aa != a[i] or bb != b[i]:
        print(-1)
        exit()

print(*a)

Квадратный кроссворд. (Первая лига H, Высшая лига F)

Давайте просто переберем все варианты слов и попробуем поставить их в кроссворд. Если для какой-то четверки вышло, то это ответ.

n, m = [int(x) for x in input().split()]
s = [input() for i in range(n)]
cnt = 0
for a in s:
    for b in s:
        if a[0] != b[0]:
            continue
        if a == b:
            continue
        for c in s:
            if a[-1] != c[0]:
                continue
            if c == a or c == b:
                continue
            for d in s:
                if b[-1] != d[0] or d[-1] != c[-1]:
                    continue
                if d == a or d == b or d == c:
                    continue
                cnt += 1
print(cnt)

Одномерный бильярд. (Высшая лига G)

Будем брать жадно всегда шары с меньшим номером. Почему это работает? Представим, что мы сначала забили шар с большим номером, тогда мы уже недополучили 1 очко. Но при этом мы не получим за один шар больше чем 1 очко, то есть из двух шаров мы не возьмем больше чем 1 очко. Значит, мы не ухудшили ситуацию. Зато есть случаи, когда забить меньший номер лучше, потому что иногда выбивание шара с одного конца приводит к выбиванию шара с другого конца, и значит, нужно было выбить сразу меньший, и остаться в той же ситуации, но с большим числом очков.

n = int(input())
a = [int(x) for x in input().split()]
l = 0
r = n - 1
b = [0]
for i in range(n):
    ll = a[l]
    if a[l] < b[-1]:
        ll += n
    rr = a[r]
    if a[r] < b[-1]:
        rr += n
    if ll < rr:
        b.append(a[l])
        l += 1
    else:
        b.append(a[r])
        r -= 1
s = 0
b = b[1:]
for i in range(n - 1):
    if b[i] < b[i + 1]:
        s += 1
print(s)

Индиана Джонс. (Высшая лига H)

n, m = [int(x) for x in input().split()]
for i in range(n):
    s = input()
    for j in range(m):
        if s[j] == 'A':
            a = [i, j]
        if s[j] == 'B':
            b = [i, j]
        if s[j] == 'C':
            c = [i, j]

rev = False
dxa = abs(a[0] - b[0])
dya = abs(a[1] - b[1])
dxc = abs(c[0] - b[0])
dyc = abs(c[1] - b[1])

if dyc < dya or dyc == dya and dxc > dxa:
    a, c = c, a
    rev = not rev
if dyc == 0 and dya == 0:
    a, c = c, a
    rev = not rev

path = ""
p = a[:]


def go_y(p, y):
    global path
    while p[1] > y:
        path += "L"
        p[1] -= 1
    while p[1] < y:
        path += "R"
        p[1] += 1


def go_x(p, x):
    global path
    while p[0] > x:
        path += "U"
        p[0] -= 1
    while p[0] < x:
        path += "D"
        p[0] += 1


go_y(p, b[1])
go_x(p, b[0])
if a[0] == b[0]:
    if b[0] == 0:
        path += "D"
        p[0] += 1
    else:
        path += "U"
        p[0] -= 1
if c[1] == b[1]:
    if b[1] == 0:
        path += "R"
        p[1] += 1
    else:
        path += "L"
        p[1] -= 1
    go_x(p, c[0])
    go_y(p, c[1])
else:
    go_y(p, c[1])
    go_x(p, c[0])


if rev:
    s = ""
    for c in path[::-1]:
        if c == "R":
            s += "L"
        if c == "L":
            s += "R"
        if c == "U":
            s += "D"
        if c == "D":
            s += "U"
    path = s

print(path)
  • Vote: I like it
  • 0
  • Vote: I do not like it