1769 - albume

Tudoraș are o pasiune pentru muzică. El deține câte K albume din discografia fiecăreia dintre cele C formații pe care le ascultă. În fiecare zi, Tudoraș extrage la întamplare exact Q albume din colecția sa, pe care le ascultă în cursul zilei.
La finalul zilei, Tudoraș analizează albumele ascultate. Concret, el numără de la câte formații diferite provin cele Q albume alese și își notează această valoare.
Care va fi media aritmetică a valorilor notate, dacă procesul se repetă pentru un număr infinit de zile?
Cu alte cuvinte, care este valoarea medie (expected value) a numărului de formații ascultate într-o zi?

Date de intrare

Fișierul albumein.txt conține pe prima linie trei valori separate prin spațiu: C K Q.

Date de ieșire

Fișierul albumeout.txt trebuie să conțină pe prima linie o singură valoare reală: media aritmetică a valorilor notate de Tudoraș.

Restricții și precizări

• 1 ≤ C, K ≤ 1000
• 1 ≤ Q ≤ min(1000, C*K)
• Pentru teste în valoare de 10 puncte, K = 1.
• Pentru alte teste în valoare de 10 puncte, Q = C * K.
• Pentru alte teste în valoare de 20 de puncte, C * K ≤ 10.
• În fiecare zi, toate albumele au probabilitate egală de a fi extrase.
• Rezultatul este considerat corect dacă are o eroare absolută de cel mult 10**-6.

Exemplu 1

albumein.txt

2 2 2

albumeout.txt

1.666666667

Exemplu 2

albumein.txt

232 654 27

albumeout.txt

25.542102567

Rezolvare

#1769 - albume
def calculate_expected_value(C, K, Q):
    expected_value = 0
    for i in range(1, C + 1):
        probability = i / C
        expected_value += probability * min(Q, i * K)

    return expected_value

def check_restrictions(C, K, Q):
    if not (1 <= C <= 1000):
        return False
    if not (1 <= K <= 1000):
        return False
    if not (1 <= Q <= min(1000, C * K)):
        return False
    if K != 1 and Q == C * K:
        return False
    if C * K > 10:
        return False
    return True

def main():
    # Citirea datelor de intrare
    with open('albumein.txt', 'r') as file:
        C, K, Q = map(int, file.readline().split())

    # Verificare restricții
    if not check_restrictions(C, K, Q):
        print("false")
        return

    # Calculul valorii așteptate (expected value)
    result = calculate_expected_value(C, K, Q)

    # Scrierea rezultatului în fișierul de ieșire
    with open('albumeout.txt', 'w') as file:
        file.write('{:.6f}'.format(result))

if __name__ == "__main__":
    main()

 Explicatie 

În primul exemplu, există două formații, fiecare cu două albume. Numerotăm albumele în următorul fel:

• a1 = 1 (primul album al primei formații)
• a2 = 1 (al doilea album al primei formații)
• a3 = 2 (primul album al celei de-a doua formații)
• a4 = 2 (al doilea album al celei de-a doua formații)

Suma numărului de formații din fiecare caz este egală cu 1+2+2+1+2+2+2+2+1+2+2+1 = 20.
Cele 12 cazuri au probabilitate egală de a se întâmpla.
Rezultatul este 20 / 12 = 1.(6)