Miawinator: Pagină nouă: Considerăm şirul de numere naturale nenule distincte . Notăm cu lungimea maximă a unei secvențe de elemente cu valori consecutive care se poate obţine prin ordonarea crescătoare a primelor `i` elemente din şirul dat. De exemplu, pentru șirul `7, 2, 3, 8, 20, 4, 10, 9` avem: . = Cerința = Să se determine . = Date de intrare = Fişierul `input.txt` conţine pe prima linie numărul natural `N`. Pe fiecare din următoarel...

2024-01-04T21:34:55Z

Pagină nouă: Considerăm şirul de numere naturale nenule distincte . Notăm cu lungimea maximă a unei secvențe de elemente cu valori consecutive care se poate obţine prin ordonarea crescătoare a primelor <code>i</code> elemente din şirul dat. De exemplu, pentru șirul <code>7, 2, 3, 8, 20, 4, 10, 9</code> avem: . = Cerința = Să se determine . = Date de intrare = Fişierul <code>input.txt</code> conţine pe prima linie numărul natural <code>N</code>. Pe fiecare din următoarel...

New page

Considerăm şirul de numere naturale nenule distincte . Notăm cu lungimea maximă a unei secvențe de elemente cu valori consecutive care se poate obţine prin ordonarea crescătoare a primelor <code>i</code> elemente din şirul dat. De exemplu, pentru șirul <code>7, 2, 3, 8, 20, 4, 10, 9</code> avem: .

= Cerința =
Să se determine .

= Date de intrare =
Fişierul <code>input.txt</code> conţine pe prima linie numărul natural <code>N</code>. Pe fiecare din următoarele <code>N</code> linii se găseşte câte un număr natural, deci pe linia <code>i+1</code> se va afla elementul , pentru <code>i=1...N</code>.

= Date de ieșire =
Fişierul <code>output.txt</code> conţine exact <code>N</code> linii. Pe linia <code>i</code> (<code>i = 1...N</code>) se va afișa valoarea .

= Restricții și precizări =

* <code>3 ≤ N ≤ 200.000</code>

== Exemplul 1 ==
input.txt:

8

7

3

2

8

20

4

10

9

output.txt:

1

1

2

2

2

3

3

4

Explicație:

L1 Șirul: <code>7</code>. Lungime maximă <code>1</code>.

L2 Șirul: <code>7, 3</code>. Lungime maximă <code>1</code>.

L3 Șirul: <code>7, 3, 2</code>. Şirul sortat este <code>2, 3, 7</code>. Lungimea maximă este <code>2</code> (dată de secvenţa <code>2, 3</code>).

L4 Șirul: <code>7, 3, 2, 8</code>. Lungime maximă <code>2</code> (dată de <code>2, 3</code>)

L5 Șirul: <code>7, 3, 2, 8, 20</code>. Lungime maximă <code>2</code> (dată de <code>2, 3</code>).

L6 Șirul: <code>7, 3, 2, 8, 20, 4</code>. Şirul sortat este <code>2, 3, 4, 7, 8, 20</code>. Lungimea maximă este <code>3</code> (dată de secvenţa <code>2, 3, 4</code>).

L7 Șirul: <code>7, 3, 2, 8, 20, 4, 10</code>. Lungime maximă <code>3</code> (dată de <code>2, 3, 4</code>).

L8 Șirul: <code>7, 3, 2, 8, 20, 4, 10, 9</code>. Şirul sortat este <code>2, 3, 4, 7, 8, 9, 10, 20</code>. Lungimea maximă este <code>4</code> (dată de secvenţa <code>7, 8, 9, 10</code>).

== Exemplul 2 ==
input.txt:

999999999

7

3

2

8

20

4

10

9

Output:

Input-ul nu convine conditiilor

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare(n):
if not(3<=n<=200000):
print("Input-ul nu convine conditiilor")
exit()

infile = "input.txt"
outfile = "output.txt"
nMax = 200013
vMax = 1000013

vz = [False] * vMax
v = [0] * nMax
pos = [0] * vMax
n = 0

def read():
global n
with open(infile, "r") as fin:
n = int(fin.readline().strip())
verificare(n)
for i in range(n):
v[i + 1] = int(fin.readline().strip())
assert not vz[v[i + 1]]
vz[v[i + 1]] = True

def solve():
global n
best = 0

with open(outfile, "w") as fout:
for i in range(1, n + 1):
begin, end = v[i], v[i]

if pos[v[i] - 1]:
begin = pos[v[i] - 1]
if pos[v[i] + 1]:
end = pos[v[i] + 1]

pos[begin] = end
pos[end] = begin

best = max(best, end - begin + 1)
fout.write(f"{best}\n")

if __name__ == "__main__":
read()
solve()

</syntaxhighlight>

1639 - Secvente 3 - Revision history