Приседания. (Первая лига А)
Будем идти циклом от 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)