# -*- coding: utf-8 -*-
# Compute upper bounds on min fragment.
import sys, fractions
from fractions import Fraction
def floor(q):
"""Floor function that can cope with Fraction. Bah, why does the
fractions module not contain one of these?"""
if q < 0: return -ceil(-q)
return int(q)
def ceil(q):
"""Ceiling function that can cope with Fraction. Also bah."""
if q < 0: return -floor(-q)
if q == int(q): return int(q)
return int(q) + 1
def ceilpe(q):
"""ceil(q+ε)"""
return floor(q) + 1
def floorme(q):
"""floor(q-ε)"""
return ceil(q) - 1
def writinghawk(n,m):
"""Upper bound on the best solution by .
We begin by ruling out the case where m | n, which is the only case in
which we can avoid cutting _any_ m-stick. With that constraint, we
know the min frag must be at most m/2, and we assume we will cut
_every_ m-stick at least once.
Now suppose the min frag is s, so that every piece is at least s and
at most m-s. We derive constraints on s by considering the total
number of pieces in the dissection.
Each stick of length n is cut into at least n/(m-s) and at most n/s
pieces. Because it must also have an integer number of pieces, that
means it's at least ⌈n/(m-s)⌉ and at most ⌊n/s⌋. Summing over all
n-sticks, the total number of pieces P in the dissection must satisfy
m⌈n/(m-s)⌉ ≤ P ≤ m⌊n/s⌋.
By similarly considering the number of pieces that a stick of length m
is cut into, we derive a second inequality n⌈m/(m-s)⌉ ≤ P ≤ n⌊m/s⌋
(identical to the first inequality, but with n,m are swapped
everywhere they appear except in the divisor m-s).
So when s becomes big enough that either of those inequalities is
self-inconsistent (with LHS > RHS) or when the two are incompatible
(because they define ranges for P that do not meet), there can be no
dissection with s that large."""
if n % m == 0:
return m
s = 1
while True:
# See if s+ε is viable.
# lo_n = m * ⌈n/(m - s - ε)⌉
# = m * ⌈n/(m - s) + ε'⌉
lo_n = m * ceilpe(Fraction(n, m - s))
# hi_n = m * ⌊n/(s + ε)⌋
# = m * ⌊n/s - ε'⌋
hi_n = m * floorme(Fraction(n, s))
# lo_m = n * ⌈m/(m - s - ε)⌉
# = n * ⌈m/(m - s) + ε'⌉
lo_m = n * ceilpe(Fraction(m, m - s))
# hi_m = n * ⌊m/(s + ε)⌋
# = n * ⌊m/s - ε'⌋
hi_m = n * floorme(Fraction(m, s))
if max(lo_n, lo_m) > min(hi_n, hi_m):
return s
# Find the next point where one of those floors changes.
s_new = min(m - Fraction(n, ceilpe(Fraction(n, m - s))),
Fraction(n, floorme(Fraction(n, s))),
m - Fraction(m, ceilpe(Fraction(m, m - s))),
Fraction(m, floorme(Fraction(m, s))))
s = s_new
def fivemack(n, m):
"""Upper bound on certain n,m pairs by Tom Womack.
If m/3 is an integer and also a multiple of n-m, then no solution can
be better than m/3.
Proof: suppose the shortest fragment is m/3 + ε for some ε > 0. Then
if any segment of stick less than _twice_ that length arises while
you're dissecting, it must remain whole. In particular, any fragment
shorter than 2m/3 + 2ε must be monolithic in this way.
So consider a short stick (of length m) from which we cut a piece of
length m/3+ε. The other piece of that stick has length 2m/3-ε and
hence is monolithic; so it must have been cut as a whole from a longer
stick of length n. Let n = m+k, because we'll want to talk about k a
lot. Now we reason as follows:
- a piece m/3+ε shares a short stick with 2m/3-ε
- that 2m/3-ε shares a long stick with m/3+k+ε
- that m/3+k+ε shares a short stick with 2m/3-k-ε
- that 2m/3-k-ε shares a long stick with m/3+2k+ε
... and so on, so that we derive the existence of pieces of lengths
m/3+ε, m/3+k+ε, m/3+2k+ε, ... 2m/3+ε (which we must reach since m/3 is
an exact multiple of k). That 2m/3+ε is still monolithic (recall that
only a piece of at least 2m/3+2ε can avoid being so) and so it must
share a short stick with a piece of length m/3-ε, which is shorter
than our presumed minimum fragment. Contradiction."""
if m % (3*(n-m)) == 0:
return m/3
return None
def most_trivial(n, m):
"""The most trivial possible bound."""
return m
def trivial(n, m):
"""Trivial upper bound of m/2.
If m does not divide n, then at least one m-stick must be cut into
more than one piece, reducing the best option to at most m/2."""
if n % m == 0:
return None
return Fraction(m, 2)
bounds = [
(writinghawk, "writinghawk's piece-counting bound"),
(fivemack, "fivemack's conditional m/3 bound"),
(trivial, "trivial bound of m/2"),
(most_trivial, "trivial bound of m"),
]
def upper_bound(n, m):
assert n > m
best = m+1, None
for boundtype in bounds:
b = boundtype[0](n, m)
if b is not None:
if b < best[0]:
best = b, boundtype[1]
elif b == best[0]:
best = b, best[1] + ", " + boundtype[1]
return best
def main():
n = int(sys.argv[1])
m = int(sys.argv[2])
if n < m: m,n = n,m
b = upper_bound(n, m)
print "upper_bound(%d,%d) = %s (%s)" % (n, m, b[0], b[1])
if __name__ == "__main__":
main()