Rezultati

Up. imeNalogaJezikRezultatČas oddaje
zerodays-2019 Revolver Python 3 100/100OK 09. maj '19 @ 19:56

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 14/14 10,414 MiB 0,000 s OK
#2 [več] 14/14 10,543 MiB 0,000 s OK
#3 [več] 14/14 10,445 MiB 0,000 s OK
#4 [več] 14/14 10,484 MiB 0,117 s OK
#5 [več] 14/14 10,523 MiB 0,325 s OK
#6 [več] 15/15 10,613 MiB 0,361 s OK
#7 [več] 15/15 10,527 MiB 0,396 s OK

Ocenjevani program (revlover.py):
from collections import defaultdict


def prestej_batche(r):
    st = r.count('.')
    
    dolzine = []

    trenutni = 0

    for c in r:
        if c == '.':
            trenutni += 1
        else:
            if (trenutni != 0): dolzine.append(trenutni)
            trenutni = 0
        
    if trenutni != 0 and r[0] == '.':
        if len(dolzine) > 0:
            dolzine[0] += trenutni
        else:
            dolzine = [trenutni]
    elif trenutni != 0:
        dolzine.append(trenutni)

    return st, dolzine

memo = None

def kalkuliraj(n, p, st, batchi, zaporedni_strel):
    global memo
    if p == 0:
        return 1, []

    if memo.get((p, zaporedni_strel), None) != None:
        return memo[(p, zaporedni_strel)]

    #print(st, zaporedni_strel, batchev)

    zgori = sum([max(b - zaporedni_strel - 1, 0) for b in batchi])
    spodi = sum([max(b - zaporedni_strel, 0) for b in batchi]) 

    if spodi == 0:
        nov_ustrelu = 0
    else:
        nov_ustrelu = zgori / spodi

    #print(nov_ustrelu, zaporedni_strel, st, batchev)
    nov_rol = st/n

    #print(nov_ustrelu, nov_rol)

    if nov_ustrelu != 0:
        a_ustrelu, ustrelu_zaporedje = kalkuliraj(n, p-1, st, batchi, zaporedni_strel+1)
        nov_ustrelu *= a_ustrelu
    
    a_roll, roll_zaporedje = kalkuliraj(n, p-1, st, batchi, 0)    
    nov_rol *= a_roll

    if nov_ustrelu > nov_rol:
        zaporedje = ['FIRE'] + ustrelu_zaporedje
        memo[(p, zaporedni_strel)] = (nov_ustrelu, zaporedje)
        return nov_ustrelu, zaporedje
    else:
        zaporedje = ['ROLL'] + roll_zaporedje
        memo[(p, zaporedni_strel)] = (nov_rol, zaporedje)
        return nov_rol, zaporedje
        
    

T = int(input())
for _ in range(T):
    n, p = map(int, input().split())
    r = input()

    memo = {}

    st, batchi = prestej_batche(r)
    verjetnost, zaporedje = kalkuliraj(n, p-1, st, batchi, 0)
    verjetnost *= st/n
    print('{:.10f}'.format(verjetnost))
    for e in zaporedje:
        print(e)