Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ## Allowed 2 days Absent, but 3 or more not allowed
- ## https://www.hackerearth.com/problem/algorithm/graduating-5b72b1c7-bc102a51/
-
- daysnum = input()
-
- def attendance(days,prev1=-1,prev2=-1,missgraduation=False):
- ## Breaking Condition
- if days == 1:
- return 1
- ## DP Memoization
- if (days,prev1,prev2) in memo:
- return memo[(days,prev1,prev2)]
-
- total = 0
-
- if prev1 == 1 and prev2 == 1:
- currval = attendance(days-1, 1,1) + attendance(days-1, 1,0)
- total += currval
- memo[(days,prev1,prev2)] = total
- elif prev1 == 0 and prev2 == 0:
- currval = attendance(days-1, 0,1)
- total += currval
- memo[(days,prev1,prev2)] = total
- elif prev1 == 1 and prev2 == 0:
- currval = attendance(days-1, 0,1) + attendance(days-1, 0,0)
- total += currval
- memo[(days,prev1,prev2)] = total
- elif prev1 == 0 and prev2 == 1:
- currval = attendance(days-1, 1,1) + attendance(days-1, 1,0)
- total += currval
- memo[(days,prev1,prev2)] = total
- else:
- if missgraduation is False:
- total += attendance(days-1, 0,1) + attendance(days-1, 0,0) + attendance(days-1, 1,0) + attendance(days-1, 1,1)
- else:
- total += attendance(days-1, 0,1) + attendance(days-1, 0,0)
-
- memo[(days,prev1,prev2)] = total
- return total
-
- memo = dict()
- absent = attendance(daysnum,missgraduation=True) if daysnum > 1 else 1
- memo = dict()
- result = attendance(daysnum) if daysnum > 1 else 2
- memo = None
-
- print(f'{absent}/{result}')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement