3282 – Transform1 - Revision history

Corjuc Eunice: Pagină nouă: 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 2024-01-03T21:37:59Z Pagină nouă: Fie un șir <code>a = a1</code>, <code>a2</code>, …, <code>aN</code> de numere naturale, nu neapărat distincte, cuprinse între <code>1</code> și <code>N</code>. Fie de asemenea două numere naturale <code>x</code> și <code>y</code>. Se definește operația <code>transform(i)</code> astfel: se determină valoarea <code>w = 1 + (x * i + y * ai) mod N</code>, apoi toate elementele egale cu <code>ai</code> din secvența <code>ai</code>, <code>ai+1</code>, …, <code>aN</cod... New page Fie un șir <code>a = a1</code>, <code>a2</code>, …, <code>aN</code> de numere naturale, nu neapărat distincte, cuprinse între <code>1</code> și <code>N</code>. Fie de asemenea două numere naturale <code>x</code> și <code>y</code>. Se definește operația <code>transform(i)</code> astfel: se determină valoarea <code>w = 1 + (x * i + y * ai) mod N</code>, apoi toate elementele egale cu <code>ai</code> din secvența <code>ai</code>, <code>ai+1</code>, …, <code>aN</code> își modifică valoarea în <code>w</code>. De exemplu, pentru șirul <code>a=1, 7, 1, 7, 3, 4, 7</code>, <code>x = 4</code>, <code>y = 5</code>, operația <code>transform(4)</code> înseamnă că <code>w = 1+(44+57) mod 7 = 3</code>, deci șirul devine <code>1</code>, <code>7</code>, <code>1</code>, <code>3</code>, <code>3</code>, <code>4</code>, <code>3</code> (toate elementele de la poziția <code>4</code> la <code>7</code> și egale cu <code>7</code> s-au modificat în <code>3</code>). 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 <code>a</code> efectuând pe rând asupra șirului operațiile <code>transform(1)</code>, <code>transform(2)</code>, …, <code>transform(N)</code>. = Date de intrare = Fișierul de intrare <code>input.txt</code> conține pe prima linie numerele naturale <code>N</code>, <code>x</code> și <code>y</code>. Pe linia a doua se găsesc, separate prin spațiu, elementele șirului <code>a</code>. = Date de ieșire = Fișierul de ieșire <code>output.txt</code> va conține pe prima linie un singur număr natural reprezentând suma maximă obținută. = 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>