Source code for tryalgo.binary_search

#!/usr/bin/env pypy3
# -*- coding: utf-8 -*-
"""\
Binary search
jill-jênn vie, christoph dürr et louis abraham - 2014-2020
"""
# pylint: disable=redefined-outer-name

from tryalgo.our_std import readint, readarray

__all__ = ["discrete_binary_search", "continuous_binary_search",
           "optimized_binary_search_lower", "optimized_binary_search",
           "ternary_search"]

# Fill the Cisterns
# http://www.spoj.com/problems/CISTFILL/
# [!] python3 is too slow for this problem

# snip{ discrete_binary_search



# snip}


# snip{ continuous_binary_search

# snip}


[docs]def optimized_binary_search_lower(tab, logsize): """Binary search in a table using bit operations :param tab: boolean monotone table of size :math:`2^\\textrm{logsize}` with tab[0] = False :param int logsize: :returns: last i such that not tab[i] :complexity: O(logsize) """ lo = 0 intervalsize = (1 << logsize) >> 1 while intervalsize > 0: if not tab[lo | intervalsize]: lo |= intervalsize intervalsize >>= 1 return lo
# snip{ optimized_binary_search # snip} # pylint: disable=cell-var-from-loop if __name__ == "__main__": def volume(level): """ Computes the volume of a set of cuboids. """ vol = 0 for base, height, ground in rect: if base < level: vol += ground * min(level - base, height) return vol for test in range(readint()): n = readint() rect = [] for _ in range(n): x, y, w, h = readarray(int) rect.append((x, y, w * h)) V = readint() hi = 1e6 + 40000 if volume(hi) < V: print("OVERFLOW") else: print("%.02f" % continuous_binary_search(lambda x: volume(x) >= V, 0, hi))