#!/usr/bin/env tclsh8.6 namespace import ::tcl::mathop::* proc distance {hold time} { expr {$hold * ($time - $hold)} } proc main {} { gets stdin line; set time [string map {{ } {}} [lindex [split $line :] 1]] gets stdin line; set dist [string map {{ } {}} [lindex [split $line :] 1]] # Binary search for the lowest and highest winning hold times. # Lowest: Stop when curr is winner (> dist) and prev is loser (<= dist) # If curr is a loser, we need to go higher (move low). set low 1 set high [- $time 1] while 1 { set try [expr {$low + ($high - $low) / 2}] # puts "low=$low try=$try high=$high" set curr [distance $try $time] set prev [distance [- $try 1] $time] if {$curr > $dist && $prev <= $dist} break if {$curr <= $dist} { set low $try } else { set high $try } } set lowest $try puts "lowest=$lowest" # Highest: Stop when curr is winner (> dist) and next is loser (<= dist) # If curr is a loser, we need to go lower (move high). set low 1 set high [- $time 1] while 1 { set try [expr {$low + ($high - $low) / 2}] # puts "low=$low try=$try high=$high" set curr [distance $try $time] set next [distance [+ $try 1] $time] if {$curr > $dist && $next <= $dist} break if {$curr <= $dist} { set high $try } else { set low $try } } set highest $try puts "highest=$highest" puts [expr {$highest - $lowest + 1}] } main