Editing 3282 – Transform1 (section)

= Restricții și precizări =

* <code>3 ≤ N ≤ 256.000</code>
* <code>1 ≤ x, y ≤ N</code>

== Exemplul 1 ==
input.txt:

7 4 5

1 7 1 7 3 4 7

ouput.txt:

35

Explicație:

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

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

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

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

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

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

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

Suma maximă care s-a obținut este <code>35</code>.

== 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 ==
<syntaxhighlight lang="python3" line="1">
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()

</syntaxhighlight>