Рыцари и лжецы (Бинарный поиск)

@semen1984 · Регистрация: 07.05.2024

Студворк — интернет-сервис помощи студентам

В игре за столом участвуют n лжецов и m рыцарей (всего n+m игроков). В каждом раунде каждый из еще участвующих в игре лжецов выбивает из игры одного рыцаря (конечно же, никакие два лжеца не могут выбить одного рыцаря). Если в начале раунда рыцарей меньше, чем лжецов, то некоторые лжецы могут никого и не выбить. После этого, если за столом останется хотя бы один рыцарь, происходит общее собрание рыцарей, и они выбрасывают одного из лжецов из игры. Если все лжецы или все рыцари выбыли из игры, игра заканчивается, иначе начинается новый раунд.

Вам стало интересно, кто же останется в конце игры: лжецы или рыцари? Также вам интересно узнать через сколько раундов закончится игра.

Формат входных данных
В первой строке записано целое число t (1≤t≤10^5) — количество тестовых случаев. Далее следуют t строк, в каждой из которых содержится описание каждого тестового случая.

Описание тестового случая состоит из двух записанных через пробел целых чисел n и m (1≤n≤2⋅10^9, 1≤m≤10^18) — количество лжецов и рыцарей, соответственно.

Формат результата
Для каждого из тестовых случаев выведите ответ в описанном ниже формате.

В первой строке выведите «Liars» (без кавычек), если в конце игры останутся лжецы, и «Knights» (без кавычек), если останутся рыцари.

Во второй строке выведите одно число — количество раундов, произошедших до конца игры.

Примеры
Входные данные
2
2 10
2 3
Результат работы
Knights
2
Liers
2
Примечания
Рассмотрим первый пример. После первого раунда будут выброшены двое рыцарей, после чего один из двух лжецов будет выброшен на собрании. Далее начнется второй раунд, в котором будет убит еще один рыцарь, а последний лжец будет выброшен на собрании. В итоге после двух раундов семеро рыцарей останутся в живых.

Рассмотрим второй пример. После первого раунда на борту космического корабля останется один рыцарь и один лжец. Во втором раунде рыцарь будет выброшен из игры, в результате чего общее собрание не состоится, а значит лжец останется в игре.

Ограничение времени: 2 с
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Я написал решение, но оно не проходит ограничения по времени на некоторых тестах, которые мне недоступны.
Я думаю, что нужно более аккуратно выставлять границу left. Перепробовал несколько вариантов, не нашёл такого, чтобы работало для малых и больших чисел.

Код рабоче-крестьянский, буду рад любым улучшениям.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def check(turns, liars, knights):
    global ans
    for i in range(turns):
        knights -= liars
        if knights <= 0:
            ans = 'Liers'
            break
        liars -= 1
        if liars <= 0:
            ans = 'Knights'
            break
    return knights>0 and liars>0
 
t = int(input())
knights = [0 for i in range(t)]
liars = [0 for i in range(t)]
for i in range(t):
    liars[i], knights[i] = map(int,input().split(' '))
 
for i in range(t):
    left = -1
    right = liars[i]+1
    while right - left > 1:
        mid = (left + right) // 2
        if check (mid, liars[i], knights[i]):
            left = mid
        else:
            right = mid
    print(ans)
    print(right)

@udmurt2024 · 10.07.2024, 18:28

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
t=int(input())
res=[]
for _ in range(t):
    n,m=map(int,input().split())
    i=0
    while n and m:
        m=(m-n if n<=m else 0)
        if m and n:
            n-=1
        i+=1
    res.append([n,m,i])
for r in res:
    print('Liers' if r[0] else 'Knights')
    print(r[2])

@Red white socks · 10.07.2024, 20:23

Для решения задачи надо ответить на 1 вопрос:
Сколько рыцарей будет выкинуто после k раундов, если начальное количество лжецов равно n.

@slonce · 11.07.2024, 00:29

Бинарный поиск это условия задания или Ваше предположение?)

@Red white socks · 11.07.2024, 01:37

slonce, определить выигравшую команду ума много не надо - достаточно сравнить 2 числа.
Но чтобы вычислить количество раундов в случае победы лжецов - нужно решить квадратное уравнение, а точнее локализовать корень двумя последовательными целыми числами.
Можно и через формулу корней квадратного уравнения, но есть такая штука, как представление действительных чисел в двоичной арифметике и там вполне себе целый корень может залететь совсем не туда. Придется дополнительно аккуратно смотреть пограничные случаи.
А можно не думая выполнить бинпоиск, оставаясь в целочисленной арифметике. Да, асимптотика чуть хуже, но здесь совершенно не принципиально.

@semen1984 · 11.07.2024, 09:05 **[ТС]**

Сообщение от udmurt2024

t=int(input())
res=[]
for _ in range(t):
n,m=map(int,input().split())
i=0
while n and m:
m=(m-n if n<=m else 0)
if m and n:
n-=1
i+=1
res.append([n,m,i])
for r in res:
print('Liers' if r[0] else 'Knights')
print(r[2])

спасибо за решение! оно тоже не проходит по превышению машинного времени, как и моё решение на том же тесте

Сообщение от Red white socks

Сколько рыцарей будет выкинуто после k раундов, если начальное количество лжецов равно n.

думаю, что выкинуто будет = k*количество лжецов - (1+2+3+...+k-1)

@Red white socks · 11.07.2024, 09:20

Сообщение от semen1984

думаю, что выкинуто будет = k*количество лжецов - (1+2+3+...+k-1)

Можно и так. Тогда вместо того, чтоб подсчитывать это число у себя в цикле за О(n), можно, применив нехитрые школьные знания за 8-9 класс (когда там арифметическую прогрессию проходят), посчитать это моментально.

@udmurt2024 · 11.07.2024, 09:31

semen1984, а что бинарить?

Python
1
2
3
4
5
6
7
8
t=int(input())
res=[]
for _ in range(t):
    n,m=map(int,input().split())
    sm=(1+n)*n//2
    res.append(['Liers' if sm>=m else  'Knights',n])
for r in res:
    print(*r,sep='\n')

@Red white socks · 11.07.2024, 09:34

udmurt2024,

Сообщение от semen1984

Во второй строке выведите одно число — количество раундов, произошедших до конца игры

@semen1984 · 11.07.2024, 10:36 **[ТС]**

спасибо за помощь!
вспомнил сумму арифметической прогрессии
похоже, что на больших числах тестовых данных именно эта операция съедала машинное время)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def check(turns, liars, knights):
    global ans
    knights = knights - turns*liars + turns*(turns-1) // 2
    if knights <= 0:
        ans = 'Liers'
    else:
        liars -= turns
        if liars <= 0:
            ans = 'Knights'
    return knights>0 and liars>0
 
t = int(input())
knights = [0 for i in range(t)]
liars = [0 for i in range(t)]
for i in range(t):
    liars[i], knights[i] = map(int,input().split(' '))
 
for i in range(t):
    left = -1
    right = liars[i]+1
    while right - left > 1:
        mid = (left + right) // 2
        if check (mid, liars[i], knights[i]):
            left = mid
        else:
            right = mid
    print(ans)
    print(right)

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	10.07.2024, 20:23
	Сообщение было отмечено semen1984 как решение Решение Для решения задачи надо ответить на 1 вопрос: Сколько рыцарей будет выкинуто после k раундов, если начальное количество лжецов равно n. 1

@slonce 88 / 32 / 14 Регистрация: 25.03.2023 Сообщений: 69
	11.07.2024, 00:29
	Бинарный поиск это условия задания или Ваше предположение?) 1

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	11.07.2024, 01:37
	slonce, определить выигравшую команду ума много не надо - достаточно сравнить 2 числа. Но чтобы вычислить количество раундов в случае победы лжецов - нужно решить квадратное уравнение, а точнее локализовать корень двумя последовательными целыми числами. Можно и через формулу корней квадратного уравнения, но есть такая штука, как представление действительных чисел в двоичной арифметике и там вполне себе целый корень может залететь совсем не туда. Придется дополнительно аккуратно смотреть пограничные случаи. А можно не думая выполнить бинпоиск, оставаясь в целочисленной арифметике. Да, асимптотика чуть хуже, но здесь совершенно не принципиально. 1

Рыцари и лжецы (Бинарный поиск)

Решение