3883 - Comisia

Cerința

Odată cu primăvara a sosit şi recrutarea comisiilor, iar asemenea ghioceilor, abuzurile răsar pretutindeni pentru a prevesti acest fapt. Astăzi dorim să recrutăm o comisie dintr-un şir de N oameni găsiţi aleator pe stradă în timp ce stăteau la o coadă. Fiecare dintre cei N oameni are un număr minim de oameni pe care comisia trebuie să-l întrunească pentru ca persoana respectivă să accepte participarea. De-asemenea, am atribuit fiecărei persoane, într-un mod subiectiv şi profund discriminatoriu, un grad de risc. Cu cât acest grad de risc este mai mare, cu atât mai mult rău poate face persoana respectivă comisiei, fie că este vorba de încălcat confidenţialitatea subiectelor, sustragerea echipamentului tehnic sau agresarea verbală sau/şi fizică a altor membri ai comisiei. Fiindcă persoanele au fost găsite stând la coadă şi oricum nu voiam să ne agităm să-i ordonăm în vreun fel, este necesar ca întreaga comisie să formeze o subsecvenţă continuă a cozii. Ştiind acest lucru, dorim să găsim o comisie validă de risc total minim.

Date de intrare

Fişierul de intrare comisiain.txt contine pe prima linie numarul N reprezentand numarul de persoane. Pe a doua linie se va afla şirul A, adică N numere reprezentand cerintele fiecarei persoane. Mai exact, dacă a i-a valoare este egală cu x, persoana cu numărul i din coadă îşi doreşte cel puţin x membri în comisie. Pe a treia linie se va afla şirul B, adică N numere reprezentand factorul de risc al fiecarei persoane.

Date de ieșire

În fişierul de ieşire comisiaout.txt se va afla o singură valoare, reprezentând riscul total minim al unei comisii care întruneşte cerinţele persoanelor implicate.

Restricții și precizări

• 3 ≤ N ≤ 200.000
• 1 ≤ Ai ≤ N
• 1 ≤ Bi ≤ 1.000.000.000
• Pentru teste in valoare de 20 de puncte N ≤ 4.000.

Exemplul 1

comisiain.txt

3

1 2 2

50 6 6

comisiaout.txt

Datele introduse corespund restricțiilor impuse.

12

Explicație

Prima persoană este dispusă să fie singurul membru al comisiei, dar aceasta avea, fără vreun motiv aparent, un topor în mână în momentul chestionării, motiv pentru care i s-a atribuit gradul de risc 50. Este astfel mai bine să formăm comisia din persoanele 2 şi 3.

Exemplul 2

comisiain.txt

2

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 1000000001

comisiaout.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

# 3883 - Comisia
def validare(n1, lista_cerinte1, lista_riscuri1):           # functia de validare a datelor de intrare
    if n1 < 3 or n1 > 200000:
        raise ValueError

    for cerinta in lista_cerinte1:
        if cerinta < 1 or cerinta > n1:
            raise ValueError

    for risc in lista_riscuri1:
        if risc < 1 or risc > 1000000000:
            raise ValueError

    fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")


def risc_minim(n1, lista_cerinte1, lista_riscuri1):                     # functia de rezolvare
    dp = [float('inf')] * (n1 + 1)
    dp[0] = 0
    for i in range(1, n1 + 1):
        suma = 0
        for j in range(i, 0, -1):
            suma += lista_riscuri1[j - 1]
            if lista_cerinte1[j - 1] <= i:
                dp[i] = min(dp[i], dp[j-1] + suma)

    fisier_iesire.write(str(min(dp[1:])))


if __name__ == '__main__':
    fisier_intrare = open("comisiain.txt", "r")         # declararea fisierelor
    fisier_iesire = open("comisiaout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

    try:
        dim_n = int(fisier_intrare.readline())
        lista_cerinte = list(map(int, fisier_intrare.readline().split()))
        lista_riscuri = list(map(int, fisier_intrare.readline().split()))

        validare(dim_n, lista_cerinte, lista_riscuri)                 # apelul functiei de validare
        risc_minim(dim_n, lista_cerinte, lista_riscuri)               # apelul functiei de rezolvare

    except ValueError:
        fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")