Fișierul intrare/ieșire | oneout.in, oneout.out | Sursă | OJI 2022 clasa a 9-a |
---|---|---|---|
Autor | Ciprian Cheșcă | Adăugată de | Teodor Plop • teodor94 |
Timp de execuție pe test | 1 sec | Limită de memorie | 20480 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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.