Advertisement
radmickey

Untitled

Feb 7th, 2023
793
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.23 KB | None | 0 0
  1. from sys import stdin, stdout
  2. from functools import lru_cache
  3.  
  4. input, print = stdin.readline, stdout.write
  5.  
  6. @lru_cache(None)
  7. def check_h(n, w, h, r, cnt_strip):
  8.     hOfRow = h / cnt_strip
  9.     Cnt1 = n // cnt_strip
  10.     Cnt2 = (n - 1) // cnt_strip + 1
  11.  
  12.     maxW = hOfRow
  13.     minW = hOfRow * r
  14.  
  15.     if (minW * Cnt1 > w or minW * Cnt2 > w):
  16.         return -1
  17.     if (maxW * Cnt1 < w or maxW * Cnt2 < w):
  18.         return 1
  19.     return 0
  20.  
  21. t = int(input())
  22. ans = []
  23.  
  24. for _ in range(0, t):
  25.     my_list = [i for i in input().split()]
  26.     w, h, n, r = int(my_list[0]), int(my_list[1]), int(my_list[2]), float(my_list[3])
  27.     left = 0
  28.     right = n + 1
  29.  
  30.     if (r == int(r)):
  31.         r = int(r)
  32.  
  33.     while (right - left > 1):
  34.         m = (left + right) // 2
  35.         res = check_h(n, w, h, r, m)
  36.         if (res == -1):
  37.             left = m
  38.         elif (res == 1):
  39.             right = m
  40.         else:
  41.             left = m
  42.             right = m
  43.  
  44.     cnt_strip = right
  45.  
  46.     if (check_h(n, w, h, r, cnt_strip) == 0):
  47.         minCntInRow = n // cnt_strip
  48.         maxCntInRow = (n - 1) // cnt_strip + 1
  49.        
  50.         ans += [f'{cnt_strip} {minCntInRow} {maxCntInRow}']
  51.     else:
  52.         ans += ['-1']
  53. print('\n'.join(ans))
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement