rahulch

Untitled

Nov 17th, 2021
1,022
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.59 KB | None | 0 0
  1. ## Allowed 2 days Absent, but 3 or more not allowed
  2. ## https://www.hackerearth.com/problem/algorithm/graduating-5b72b1c7-bc102a51/
  3. ​
  4. daysnum = input()
  5. ​
  6. def attendance(days,prev1=-1,prev2=-1,missgraduation=False):
  7.    
  8.     ## Breaking Condition
  9.     if days == 1:
  10.         return 1
  11.    
  12.     ## DP Memoization
  13.     if (days,prev1,prev2)  in memo:
  14.         return memo[(days,prev1,prev2)]
  15. ​
  16.     total = 0
  17. ​
  18.     if prev1 == 1 and prev2 == 1:
  19.         currval = attendance(days-1, 1,1) + attendance(days-1, 1,0)
  20.         total += currval
  21.         memo[(days,prev1,prev2)] = total
  22.     elif prev1 == 0 and prev2 == 0:
  23.         currval = attendance(days-1, 0,1)
  24.         total += currval
  25.         memo[(days,prev1,prev2)] = total
  26.     elif prev1 == 1 and prev2 == 0:
  27.         currval = attendance(days-1, 0,1) + attendance(days-1, 0,0)
  28.         total += currval
  29.         memo[(days,prev1,prev2)] = total
  30.     elif prev1 == 0 and prev2 == 1:
  31.         currval = attendance(days-1, 1,1) + attendance(days-1, 1,0)
  32.         total += currval
  33.         memo[(days,prev1,prev2)] = total
  34.     else:
  35.         if missgraduation is False:
  36.             total += attendance(days-1, 0,1) + attendance(days-1, 0,0) + attendance(days-1, 1,0) + attendance(days-1, 1,1)
  37.         else:
  38.             total += attendance(days-1, 0,1) + attendance(days-1, 0,0)
  39. ​
  40.         memo[(days,prev1,prev2)] = total
  41.    
  42.     return total
  43. ​
  44. memo = dict()
  45. absent = attendance(daysnum,missgraduation=True) if daysnum > 1 else 1
  46. memo = dict()
  47. result = attendance(daysnum) if daysnum > 1 else 2
  48. memo = None
  49. ​
  50. print(f'{absent}/{result}')
Advertisement
Add Comment
Please, Sign In to add comment