Advertisement
rahulch

Untitled

Nov 17th, 2021
934
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. daysnum = input()
  4. def attendance(days,prev1=-1,prev2=-1,missgraduation=False):
  5.    
  6.     ## Breaking Condition
  7.     if days == 1:
  8.         return 1
  9.    
  10.     ## DP Memoization
  11.     if (days,prev1,prev2)  in memo:
  12.         return memo[(days,prev1,prev2)]
  13.     total = 0
  14.     if prev1 == 1 and prev2 == 1:
  15.         currval = attendance(days-1, 1,1) + attendance(days-1, 1,0)
  16.         total += currval
  17.         memo[(days,prev1,prev2)] = total
  18.     elif prev1 == 0 and prev2 == 0:
  19.         currval = attendance(days-1, 0,1)
  20.         total += currval
  21.         memo[(days,prev1,prev2)] = total
  22.     elif prev1 == 1 and prev2 == 0:
  23.         currval = attendance(days-1, 0,1) + attendance(days-1, 0,0)
  24.         total += currval
  25.         memo[(days,prev1,prev2)] = total
  26.     elif prev1 == 0 and prev2 == 1:
  27.         currval = attendance(days-1, 1,1) + attendance(days-1, 1,0)
  28.         total += currval
  29.         memo[(days,prev1,prev2)] = total
  30.     else:
  31.         if missgraduation is False:
  32.             total += attendance(days-1, 0,1) + attendance(days-1, 0,0) + attendance(days-1, 1,0) + attendance(days-1, 1,1)
  33.         else:
  34.             total += attendance(days-1, 0,1) + attendance(days-1, 0,0)
  35.         memo[(days,prev1,prev2)] = total
  36.    
  37.     return total
  38. memo = dict()
  39. absent = attendance(daysnum,missgraduation=True) if daysnum > 1 else 1
  40. memo = dict()
  41. result = attendance(daysnum) if daysnum > 1 else 2
  42. memo = None
  43. print(f'{absent}/{result}')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement