Разбор задач. Бинпоиск_1

[@stavinsky]

Не сразу догадался что заголовки кликабельны.
Хотелось бы больше теории и понимания зачем вы эту статью написали. Как-будто чего-то не хватает. Спасибо

[@ratel_03]

Здравствуйте, спасибо за комментарий! Начало статьи изменил

[@lamerok]

С корнем конечно работать будет, но странностей в этом коде очень много :)
right = 1e10#1 c 10-тью нулями.
Разрешающая способность числа с плавающей точкой примерно 7 знаков. Т.е. если вы прибавите, скажем к числу 100000001F + 1F, то получите тоже самое число.
У вас выходит…
middle * middle + sqrt(middle) — (10^10/2) * (10^10)/2 ~ 9 степень к ней вы прибавляете корень из 19 степени ~10 степень. Получаем к 19 степени вы прибавляете 10 степень… Разница 9 степеней. Т.е. сложение работать не будет, хотя условие if middle * middle + sqrt(middle) >= c конечно сработает верно. Но при этом, если программа изменится, и вы напишите c = double(input()). Вас, например, попросят поточнее решение найти — уже ничего работать не будет.
Кроме того, хорошим тоном является брать в скобки все операции. Я конечно уверен, что вы знаете приоритеты всех операций и уверены что тут:
if middle * middle + sqrt(middle) >= c все выполнится в такой вот последовательности:
if (((middle * middle) + sqrt(middle)) >= c), а не в такой скажем
if (middle * middle + (sqrt(middle) >= c)))
Но лучше всегда ставить скобки, чтобы четко определить приоритет операций, не все программисты помнят приориты всех операций, а их скажем в С++ более 50.
Еще одно замечания касается передачи параметра в функцию при сравнении
if middle * middle + sqrt(middle) >= c
тут в функцию sqrt передается параметр middle. Это хорошо, что sqrt его не меняет и вы это точно знаете. Но что если определении функции будет такое float sqrt(float&)? тогда вы передадите туда middle, оно там изменится и что в итоге будет проверяться в
if sqrt(middle) + middle * middle >= c? что выполнится первым, вызов функции, изменение middle или умножение middle на middle, а потом вызов функции???
Лучше взять корень, присвоить его временной переменной, а потом выполнить проверку в условии.

Да и еще границы int от 2^31 до + 2^31. Если у вас print(int(round(left*10e6))/10e6) если left будет больше 2148, будет ерунда. Так как оно просто неверно преобразуется в int.
В общем тут много загадок :) Скорее всего все надо считать в double, а не флоате. И вместо int использовать long long.

[@IgorPie]

Жил был метод хорды и его усовершенствованная версия — метод половинного деления. И перекочевали они из вычислительной математики, в том числе и в виде «бинарного поиска».

[@mayorovp]

Зачем вы каждый раз считываете числа n и m, а потом их не используете?

Если это то что я думаю, то ваши решения могут не пройти любой из тестов просто из-за изменения в форматировании входного файла…

[@ratel_03]

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

[@qw1]

решения могут не пройти любой из тестов просто из-за изменения в форматировании входного файла

Почему, если в условии ясно написано

Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива.

[@mayorovp]

Потому что на других площадках таких уточнений в условии может и не быть.

[@5nw]

Просто напомню что в Python для этого есть bisect, bisect_left и bisect_right
В результате, получим такое решение первой задачи:

import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

for v in b:
    left = bisect.bisect_left(a, v)
    if left >= n or a[left] != v:
        print(0)
    else:
        print(left + 1, bisect.bisect_right(a, v))

В целях обучения это конечно не актуально, но на соревновании поможет сэкономить несколько минут