Статья Автор: Лебедев Дмитрий

Интересные задачи с курсов НИУ ВШЭ

Олимпийская система
В соревновании по олимпийской системе участвуют N= 2^k участников (k - количество раундов). Участники играют «на вылет», проигравшие участники выбывают из соревнования, выигравшие проходят в следующий тур, ничьи не предусмотрены.

Все участники пронумерованы числами от 1 до N. В первом туре играют участники с номерами 1 и 2, 3 и 4, 5 и 6 и т. д., всего играется N/2 игр.
По результатам этих игр участники выходят во второй тур. Во втором туре играют победители первой и второй игры первого тура, победители третьей и четвёртой игры первого тура и т. д. Они выходят в третий тур. В третьем туре играют вместе победители первой и второй игры второго тура, победители третьей и четвёртой игры второго тура и т. д. Всего будет сыграно N -1 встреча.

Вам даны результаты всех игр. Определите номер участника, ставшего победителем соревнования.
Результат соревнования представлен ОДНИМ числом, полученным по следующему правилу:

результат каждой встречи записали при помощи цифр 0 и 1:
- 0 - означает победу участника с меньшим номером
- 1 - означает победу участника с большим номером
результаты всех встреч записали подряд в виде последовательности из 0 и 1
слева к последовательности приписали 1 и получили N-значное двоичное число.
полученное число перевели в десятичную систему

Например:
В сореновании участвовало 8 у.частников Результаты игр: 0, 1, 1, 0, 1, 0, 0.
В первом туре играли участники 1 и 2, 3 и 4, 5 и 6, 7 и 8. Результаты игр первого тура: 0, 1, 1, 0, во второй тур вышли участники 1, 4, 6, 7.
Во втором туре играли участники 1 и 4, 6 и 7. Результаты игр второго тура: 1, 0. В третий тур вышли участники 4 и 6.
В последнем, третьем, туре играют участники 4 и 6, результат игры: 0, поэтому победителем соревнования является участник 4.
Результат этого турнира был бы представлен как '1'+'0110100' или 10110100₂= 180₁₀

Входные данные
Одно число N
Выходные данные
Номер победителя

def fun1(NN):
  g = [ int(s) for s in bin (NN) [3:]]
  N = len(g)+1
  k, n  = 0, 0
  while 2**k < N :
    k += 1
    m = -2 **k +1
    x = g [m + n]
    n = n * 2 + x
  return n+1

def fun2 (NN):
  k, n = - 1, 0
  while NN > 1 :
    k += 1
    m = 2 ** k - n - 1
    NN = NN >> m
    n = n * 2 + (NN & 1) 
    NN = NN >> (2 ** k - m)
  return n+1
NN = int(input())
print(fun1(NN), fun2(NN))

Иосиф и вороны
Иософ изучает ворон и обратил внимание, что они сидят на деревьях, расположенных вдоль улицы, номера которых кратны числу C (т.е. на деревьях с номерами C, 2C, 3C, ...). Иосиф шел мимо деревьев с номерами от A до B включительно и считал ворон. Сколько ворон он насчитал?

a = int(input())
b = int(input())
k = int(input())
r = b//k  - (a-1)//k
print(r)

Чтобы оставить комментарий нужна авторизация

Печать