3282 – Transform1

Fie un șir a = a1, a2, …, aN de numere naturale, nu neapărat distincte, cuprinse între 1 și N. Fie de asemenea două numere naturale x și y. Se definește operația transform(i) astfel: se determină valoarea w = 1 + (x * i + y * ai) mod N, apoi toate elementele egale cu ai din secvența ai, ai+1, …, aN își modifică valoarea în w. De exemplu, pentru șirul a=1, 7, 1, 7, 3, 4, 7, x = 4, y = 5, operația transform(4) înseamnă că w = 1+(4*4+5*7) mod 7 = 3, deci șirul devine 1, 7, 1, 3, 3, 4, 3 (toate elementele de la poziția 4 la 7 și egale cu 7 s-au modificat în 3). După fiecare operație de tip transform se calculează suma elementelor șirului obținut.

Cerința

Să se determine suma maximă care s-a obținut în șirul a efectuând pe rând asupra șirului operațiile transform(1), transform(2), …, transform(N).

Date de intrare

Fișierul de intrare input.txt conține pe prima linie numerele naturale N, x și y. Pe linia a doua se găsesc, separate prin spațiu, elementele șirului a.

Date de ieșire

Fișierul de ieșire output.txt va conține pe prima linie un singur număr natural reprezentând suma maximă obținută.

Restricții și precizări

• 3 ≤ N ≤ 256.000
• 1 ≤ x, y ≤ N

Exemplul 1

input.txt:

7 4 5

1 7 1 7 3 4 7

ouput.txt:

35

Explicație:

După transform(1), în care w = 3, șirul devine 3, 7, 3, 7, 3, 4, 7 care are suma 34.

După transform(2), în care w = 2, șirul devine 3, 2, 3, 2, 3, 4, 2 care are suma 19.

După transform(3), în care w = 7, șirul devine 3, 2, 7, 2, 7, 4, 2 care are suma 27.

După transform(4), în care w = 6, șirul devine 3, 2, 7, 6, 7, 4, 6 care are suma 35.

După transform(5), în care w = 7, șirul devine 3, 2, 7, 6, 7, 4, 6 care are suma 35.

După transform(6), în care w = 3, șirul devine 3, 2, 7, 6, 7, 3, 6 care are suma 34.

După transform(7), în care w = 3, șirul devine 3, 2, 7, 6, 7, 3, 3 care are suma 31.

Suma maximă care s-a obținut este 35.

Exemplul 2

input.txt:

999999999 4 5

1 7 1 7 3 4 7

Output:

Invalid input. Please make sure 3 ≤ N ≤ 256000 and 1 ≤ x, y ≤ N.

Rezolvare

N = 260001

def validate_input(n, x, y):
    if 3 <= n <= 256000 and 1 <= x <= n and 1 <= y <= n:
        return True
    return False

def main():
    with open("input.txt", "r") as input_file, open("output.txt", "w") as output_file:
        n, x, y = map(int, input_file.readline().split())
        a = list(map(int, input_file.readline().split()))

        if not validate_input(n, x, y):
            print("Invalid input. Please make sure 3 ≤ N ≤ 256000 and 1 ≤ x, y ≤ N.")
            return

        S = 0
        Rad = [0] * N
        Val = [0] * N
        tata = [0] * N
        Card = [0] * N

        for i in range(1, n + 1):
            S += a[i - 1]

        for i in range(n, 0, -1):
            if not Rad[a[i - 1]]:
                Rad[a[i - 1]] = i
                Val[i] = a[i - 1]
            tata[i] = Rad[a[i - 1]]
            Card[a[i - 1]] += 1

        Sol = 0
        for i in range(1, n + 1):
            nod = i
            while nod != tata[nod]:
                nod = tata[nod]
            val1 = Val[nod]
            val2 = 1 + (i * x + val1 * y) % n
            rad2 = Rad[val2]

            if val1 == val2:
                Card[val1] -= 1
                if Card[val1] == 0:
                    Val[nod] = 0
                    Rad[val1] = 0
            else:
                S = S + Card[val1] * (val2 - val1)
                Card[val2] = Card[val2] + Card[val1] - 1
                Card[val1] = 0

                if nod < rad2:
                    tata[nod] = rad2
                    Rad[val2] = rad2
                    Val[rad2] = val2
                    Rad[val1] = 0
                    Val[nod] = 0
                else:
                    tata[rad2] = nod
                    Rad[val2] = nod
                    Val[nod] = val2
                    Rad[val1] = 0
                    Val[rad2] = 0

            tata[i] = 0
            Sol = max(Sol, S)

        output_file.write(str(Sol))

if __name__ == "__main__":
    main()