Fișierul intrare/ieșire oneout.in, oneout.out Sursă OJI 2022 clasa a 9-a
Autor Ciprian Cheșcă Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 1 sec Limită de memorie 20480 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Oneout (clasa a 9-a)

Notă: punctajele testelor pot fi ușor diferite față de concursul original din cauza lipsei de informație asupra scorurilor individuale ale testelor.

Definim un număr liber de pătrate ca fiind un număr natural care nu are ca divizor niciun pătrat perfect mai mare ca 1. Prin convenție, 1 este considerat liber de pătrate.

Așadar, șirul numerelor libere de pătrate este: 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, ...

Se consideră un șir de N numere naturale Xi, 1 ≤ i ≤ N, unde N este un număr natural.

O secvența este un subșir format din numere aflate pe poziții consecutive în șirul dat.

Definim o bisecvență ca un subșir nevid obținut prin eliminarea dintr-o secvență a unui număr care nu este la începutul sau la sfârșitul secvenței.

Cerință

  • Să se determine câte numere libere de pătrate conține șirul dat.
  • Să se determine cea mai lungă bisecvență din șir formată din numere libere de pătrate, obținută prin eliminarea unui număr care nu este liber de pătrate

Date de intrare

Fișierul de intrare oneout.in conține pe primul rând un număr natural C, care poate fi doar 1 sau 2, reprezentând cerința, pe a doua linie numărul natural N iar pe a treia linie N numere naturale, separate prin câte un spațiu, cu semnificația de mai sus.

Date de ieșire

Dacă C este egal cu 1, în fișierul de ieșire oneout.out se va scrie numărul de numere libere de pătrate din șir.

Dacă C este egal cu 2:

  • pe prima linie a fișierului de ieșire oneout.out se vor scrie două numere L și K despărțite printr-un spațiu, unde L reprezintă lungimea maximă a unei bisecvențe cu proprietățile cerute, iar K reprezintă numărul de bisecvențe de lungime maximă existente în șir
  • pe următoarele K linii se vor scrie indicii de început și de sfârșit ai fiecărei bisecvențe de lungime maximă găsite, în ordinea crescătoare a indicelui de start, despărțite printr-un spațiu
  • dacă șirul nu conține nicio bisecvență cu proprietățile cerute, în fișierul de ieșire se va scrie −1

Restricții

  • 3 ≤ N ≤ 106
  • 2 ≤ Xi ≤ 106, 1 ≤ i ≤ N
  • Lungimea unei bisecvențe reprezintă numărul de numere din aceasta

Subtaskuri

  • Pentru teste în valoare de 37 puncte C = 1, din care pentru teste în valoare de 24 puncte 3 ≤ N ≤ 25
  • Pentru teste în valoare de 63 puncte C = 2, din care pentru teste în valoare de 23 puncte 3 ≤ N ≤ 101

Exemplu

oneout.in oneout.out
1
6
10 2 12 7 8 15
4
2
6
10 2 12 7 8 15
3 1
1 4
2
7
5 28 17 24 15 20 18
2 2
1 3
3 5
2
9
3 10 5 8 9 11 4 15 21
3 1
6 9

Explicație

Pentru primul exemplu, C = 1, N = 6, X = {10, 2, 12, 7, 8, 15}. Se rezolvă prima cerință.
Sunt 4 numere libere de pătrate în șirul X, și anume 10, 2, 7, 15.

Pentru al doilea exemplu, C = 2, N = 6, X = {10, 2, 12, 7, 8, 15}. Se rezolvă a doua cerință.
Dacă se elimină 12 se obține bisecvența 10, 2, 7 de lungime 3. Dacă se elimină 8 se obține bisecvența 7, 15 de lungime 2. Deci există o singură bisecvență de lungime maximă = 3, care începe în poziția 1 și se termină în poziția 4.

Pentru al treilea exemplu, C = 2, N = 7, X = {5, 28, 17, 24, 15, 20, 18}. Se rezolvă a doua cerință.
Dacă se elimină 28 se obține bisecvența 5, 17 de lungime 2. Dacă se elimină 24 se obține bisecvența 17, 15 tot de lungime 2. Deci există două bisecvențe de lungime maximă = 2. Prima începe în poziția 1 și se termină în poziția 3. A doua începe în poziția 3 și se termină în poziția 5.

Pentru al patrulea exemplu, C = 2, N = 9, X = {3, 10, 5, 8, 9, 11, 4, 15, 21}. Se rezolvă a doua cerință.
8 nu poate fi eliminat deoarece este situat la sfârșitul unei bisecvențe iar 9 nu poate fi eliminat pentru că ar fi începutul unei bisecvențe.
Singurul număr care nu este liber de pătrate ce poate fi eliminat este 4 și se va obține bisecvența 11, 15, 21 de lungime 3 care începe în poziția 6 și se termină în poziția 9.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii