top of page

CCC 2020 S5: Josh’s Double Bacon Deluxe

DP problems.

  • They choose the coach’s burger. In this case, no further disruptions are caused and Josh gets his burger.

  • They choose Josh’s burger. In this case, no further disruptions are caused and Josh doesn't get his burger.

  • They choose someone else’s burger and create another disruption.

Optimal subquestion:

The ith person can get his favourite burger. Assume b[] is the list that is each person's favourite burger. b[0] is coach, b[n-1] is Josh.

f(i) = 1 if b[i] = b[0]

f[i] = f[last[i]] if b[i] is in the last list that is the most right side person faourite burger that is same as ith

f[i] = (1+c)/(n-i) , c is the sum of problity of from n-2 to i.


The result is (1+c)/n.


import sys
input = sys.stdin.readline

n = int(input())
b = list(map(int, input().split()))
dp = [0] * n
c = 0
last = {b[-1]: n - 1}
if b[-1] == b[0]:
    dp[-1] = 1
    c += 1
    print("{:.8f}".format(c))
else:
    for i in range(n - 2, -1, -1):
        if b[i] == b[0]:
            dp[i] = 1
        elif b[i] in last:
            dp[i] = dp[last[b[i]]]
        else:
            dp[i] = (1 + c) / (n - i)
        c += dp[i]
        if b[i] not in last:
            last[b[i]] = i

    print("{:.8f}".format(c / n))

This is 15 marks solution.

Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC '22 J5 - Square Pool

#include<iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool rowcom(pair<int, int> a, pair<int, int> b){ return a.first < b.first; } bool colcom(pair<int,

コメント


bottom of page