Разбор ДЗ №1

Последний среди равных

Требовалось написать функцию, которая ищет последний элемент среди равных.

Вспомним, что первый среди равных ищется кодом вида

def search(haystack, needle):
    left  = 0
    right = len(haystack)
    
    while right - left > 1:
        m = (left + right - 1) // 2
        if haystack[m] < needle: left  = m+1
        else:                    right = m+1
    
    if right > left and haystack[left] == needle: return left

Теперь нужно аккуратно «симметрично отразить» этот код относительно середины массива. Получается вот что:

def search(haystack, needle):
    left  = 0
    right = len(haystack)
    
    while right - left > 1:
        m = (left + right) // 2
        if haystack[m] > needle: right = m
        else:                    left  = m
    
    if right > left and haystack[left] == needle: return left

Ранг элемента

Нужно было написать функцию, которая ищет ранг элемента needle в упорядоченном массиве haystack — количество элементов, меньших needle.

Ранг элемента находится примерно так же, как и первый среди равных:

def search(haystack, needle):
    left  = 0
    right = len(haystack)
    
    while right - left > 1:
        m = (left + right - 1) // 2
        if haystack[m] < needle: left  = m+1
        else:                    right = m+1
    
    if right > left and haystack[left] >= needle: return left
    
    return len(haystack)

Тут ровно два изменения: знак >= вместо == и возвращаемое значение функции в случае неудачного поиска.

Функция вместо массива

Нужно было найти ранг элемента в случае, когда массив моделируется функцией.

Нужно просто взять решение предыдущего упражнения и специализировать под требования задания:

def search(haystack, needle):
    f,left,right = haystack  ## именно так подаются данные на вход
    
    while right - left > 1:
        m = (left + right - 1) // 2
        if f(m) < needle: left  = m+1
        else:             right = m+1
    
    if right > left and f(left) >= needle: return left
    
    return haystack[2]

Диапазонный запрос

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

Делается это очень просто: считаем ранг элемента, и пляшем от него.

import sys

numbers = [int(x) for x in sys.stdin.read().split()]

a,b = numbers[-2:]
numbers = numbers[1:-2]

for i in range(search(numbers, a), len(numbers)): ## здесь search из 2-го задания
    x = numbers[i]
    if x < b: print(x)
    else:     break

Вычислять же правую границу бинарным поиском здесь совсем не обязательно: всё равно требуется пройти по всем найденным элементам (чтобы их напечатать).

Ранг с ключом

Данные подаются в формате:

def read_data():
    n = int(input())
    a0, b0 = [int(x) for x in input().split()]

    pairs = []
    for i in range(n):
        pairs.append([i]+[int(x) for x in input().split()])
    
    return a0, b0, sorted(pairs, key = lambda x: x[1]+x[2])

Требуется вывести (в порядке возрастания) номера тех пар чисел, сумма которых не больше суммы заданной пары a0,b0.

Сначала перепишем функцию нахождения ранга следующим образом:

def search(haystack, needle, keyfunc):
    left  = 0
    right = len(haystack)
    
    while right - left > 1:
        m = (left + right - 1) // 2
        if keyfunc(haystack[m]) < needle: left  = m+1
        else:                             right = m+1
    
    if right > left and keyfunc(haystack[left]) >= needle: return left
    
    return len(haystack)

затем воспользуемся ей:

a0, b0, numbers = read_data()

n = search(numbers, a0+b0+1, lambda x: x[1]+x[2])
##                       ^^=====\\
##                              ||
## стоит обратить внимание на ==//

print(*sorted([numbers[i][0]+1 for i in range(n)]))

Бинарный поиск ответа

Была задача с немного нетривиальным условием. Вот её решение:

def check(segments, k, l):
  total = sum([x // l for x in segments])
  return total >= k

## это последний среди True (специализация решения 1-й задачи)
def solve(segments, k):
  left  = 1
  right = max(segments)+1
  
  while right - left > 1:
    m = (right + left) // 2
    if check(segments, k, m): left  = m
    else:                     right = m
  
  if check(segments, k, left): return left
  
  return 0
  
import sys

n, k, *numbers = [int(x) for x in sys.stdin.read().split()]
print(solve(numbers,k))

Идея в том, что если нельзя выпилить K отрезков некоторой длины, то нельзя выпилить и K отрезков любой большей длины. Поэтому предикат «L -> можно ли выпилить нужное количество отрезков длины L?» является монотонным и к нему можно применить бинарный поиск.

Возведение в степень

Без лишних комментариев:

def power(a,b):
    if b == 0:     return 1
    
    root = power(a,b//2)

    if b%2 == 0: return root*root
    return            a*root*root

Быстрое вычисление чисел Фибоначчи

Есть замечательное соотношение (вы его должны были изучать на спецматематике):

F(n+k) = F(n)*F(k+1) + F(n-1)*F(k)

Те, кто в него не верит, могут воспользоваться индукцией по k:

F(n)*F(1) + F(n-1)*F(0) = F(n)*1 + F(n-1)*0 = F(n)*1 = F(n)
F(n)*F(2) + F(n-1)*F(1) = F(n)*1 + F(n-1)*1 = F(n+1)

  F(n)*F(k+2) + F(n-1)*F(k+1) = по определению F =
= F(n)*F(k+1) + F(n)*F(k)   +   F(n-1)*F(k) + F(n-1)*F(k-1) = переупорядочиваем =
= F(n)*F(k+1) + F(n-1)*F(k)   +   F(n)*F(k) + F(n-1)*F(k-1) = предположение индукции =
= F(n+k) + F(n+k-1) = F(n+k+1)

Из этого соотношения, в частности, следует:

F(2n)   = F(n)*F(n+1) + F(n-1)*F(n) = 2 F(n)*F(n+1) - F(n)*F(n)
F(2n+1) = F(n+1)*F(n+1) + F(n)*F(n)

Ну и из этой пары соотношений следует очевидное решение (сравните с решением предыдущего номера):

def two_fibs(n):  ## f(n), f(n+1)
    if n == 0: return 0,1
    if n == 1: return 1,1
    
    root = two_fibs(n//2)
    
    a = 2*root[0]*root[1] - root[0]*root[0]
    b = root[1]*root[1] + root[0]*root[0]
    
    if n%2 == 0: return a,b
    return b,a+b

def fib(n): return two_fibs(n)[0]