1637 - Split

Enunț

Fie un şir a1,a2,…,an de numere naturale. Se împarte şirul în patru secvenţe astfel încât orice element din şir să aparţină unei singure secvenţe şi fiecare secvenţă să conţină cel puţin două elemente. Mai exact, se identifică trei indici i < j < k astfel încât prima secvenţă este formată din elementele a1,a2,…,ai, a doua din elementele ai+1,ai+2,…,aj, a treia din elementele aj+1,aj+2,…,ak şi ultima din elementele ak+1,ak+2,…,an. Pentru fiecare secvenţă se determină costul ei ca fiind diferenţa dintre valoarea maximă şi cea minimă din acea secvenţă.

Cerința

Să se determine o împărţire a şirului în patru secvenţe astfel încât suma costurilor celor patru secvenţe să fie maximă.

Date de intrare

Fișierul de intrare splitin.txt conţine pe prima linie numărul natural N. Pe linia a doua se găsesc N numere naturale, separate prin câte un spaţiu, reprezentând elementele şirului a.

Date de ieșire

Fișierul de ieșire splitout.txt conţine pe prima linie un singur număr natural reprezentând suma maximă a costurilor celor patru secvenţe. Pe linia a doua se află trei numere naturale i, j şi k, separate prin câte un spaţiu, cu semnificaţia din enunţ.

Restricții și precizări

• 8 ⩽ N ⩽ 5.000
• 0 ⩽ Ai ⩽ 100.000.000
• O secvenţă poate avea costul 0 (valoarea maximă egală cu valoarea minimă)
• Dacă există mai multe soluţii cu aceeaşi sumă maximă, atunci se va alege soluţia cu i minim. Dacă există mai multe soluții cu acelaşi i minim, se alege aceea cu j minim, iar dacă există mai multe soluții cu acelaşi i și j minim, se alege aceea cu k minim.

Exemplul 1

Intrare

splitin.txt

11

9 7 3 0 2 1 8 6 0 11 4

Ieșire

Datele de intrare corespund restricțiilor impuse

splitout.txt

29

4 7 9

Explicație

Cele 4 secvențe sunt: 9 7 3 0 (cost 9 - 0 = 9)
2 1 8 (cost 8 - 1 = 7)
6 0 (cost 6 - 0 = 6)
11 4 (cost 11 - 4 = 7).
O altă soluţie care obţine tot suma maximă 29 este 5 7 9, dar nu are i minim.

Exemplul 2

Intrare

splitin.txt

5

9 7 3 0 2

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#1637 - Split

def validare_date(n, sir):
    if not (8 <= n <= 5000):
        return False
    if len(sir) != n:
        return False
    for elem in sir:
        if not (0 <= elem <= 100000000):
            return False
    return True


def maximizeaza_suma(n, sir):
    suma_maxima = float('-inf')
    rezultat = (0, 0, 0)

    for i in range(1, n - 1):
        for j in range(i + 1, n):
            for k in range(j + 1, n + 1):
                secventa1 = sir[:i]
                secventa2 = sir[i:j]
                secventa3 = sir[j:k]
                secventa4 = sir[k:]

                if not secventa1 or not secventa2 or not secventa3 or not secventa4:
                    continue

                cost1 = max(secventa1) - min(secventa1)
                cost2 = max(secventa2) - min(secventa2)
                cost3 = max(secventa3) - min(secventa3)
                cost4 = max(secventa4) - min(secventa4)

                suma_curenta = cost1 + cost2 + cost3 + cost4

                if suma_curenta > suma_maxima:
                    suma_maxima = suma_curenta
                    rezultat = (i, j, k)

    return suma_maxima, rezultat


with open("splitin.txt", "r") as f:
    n = int(f.readline().strip())
    sir = list(map(int, f.readline().split()))


if validare_date(n, sir):
    print("Datele de intrare corespund restricțiilor impuse")
    rezultat_suma, rezultat_secvente = maximizeaza_suma(n, sir)
    with open("splitout.txt", "w") as g:
        g.write(str(rezultat_suma) + "\n")
        g.write(" ".join(map(str, rezultat_secvente)))
else:
    print("Datele de intrare NU corespund restricțiilor impuse")
    exit(0)