algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

problem.txt (1823B)


      1 Monocarp has a
      2  slices of cheese and b
      3  slices of sausage. He wants to make the maximum possible number of sandwiches for his friends from them.
      4 
      5 Monocarp is very thrifty, so he must use all a
      6  slices of cheese and all b
      7  slices of sausage without any leftovers to make the sandwiches. In addition, he has the following rules for making sandwiches:
      8 
      9 each sandwich must contain at least one slice of cheese and at least one slice of sausage;
     10 each of the a
     11  slices of cheese and each of the b
     12  slices of sausage must be placed on exactly one sandwich;
     13 for each sandwich, the number of slices of cheese must be strictly greater than the number of slices of sausage.
     14 Help Monocarp determine the maximum number of sandwiches he can make, or determine that it is impossible to distribute all slices according to these rules.
     15 
     16 Input
     17 The first line contains an integer t
     18  (1≤t≤104
     19 ) — the number of test cases.
     20 
     21 The only line of each test case contains two integers a
     22  and b
     23  (1≤a,b≤100
     24 ) — the number of slices of cheese and sausage, respectively.
     25 
     26 ---
     27 
     28 - a slices cheese
     29 - b slices sausage
     30 - make max sandwiches
     31 
     32 - each sandwich must contain at least one slice of cheese and at least one slice of sausage;
     33 - each of the a slices of cheese and each of the b slices of sausage must be placed on exactly one sandwich;
     34 - for each sandwich, the number of slices of cheese must be strictly greater than the number of slices of sausage.
     35 
     36 ---
     37 
     38 - min cheese == 2
     39 - min sausage == 1
     40 - cheese must be > sausage
     41 
     42 ---
     43 
     44 6 4
     45 
     46 ch == 6
     47 sa == 4
     48 
     49 2 ch
     50 2 ch
     51 1 sa
     52 1 sa
     53 
     54 rem: 2 ch, 2 sa
     55 
     56 since have to use all, must distribute on priors.
     57 
     58 ---
     59 
     60 5 1
     61 
     62 5 ch, 1 sa
     63 
     64 res: 1
     65 
     66 ---
     67 
     68 4 5
     69 
     70 -1
     71 
     72 ---
     73 
     74 prior = 0
     75 if ch <= sa:
     76     return prior -1
     77 else: 
     78     (ch > sa)
     79     ch -= 2
     80     sa -= 1
     81     if both fail, then return prior
     82     prior += 1
     83     goto if