Il nuovo sistema di gara delle Selezioni Territoriali funziona alla grande, ma Mojito…
- User
Il nuovo sistema di gara delle Selezioni Territoriali funziona alla grande, ma Mojito non è così convinto... sembra infatti che la nota mascotte delle Olimpiadi abbia fiutato un virus nascosto fra i file inviati da un partecipante!
Conosciamo la lunghezza del virus e sappiamo che si ripete uguale nei quattro file che abbiamo ricevuto, ma non sappiamo dove. Aiutaci ad individuare il virus!
Rappresentazione realistica dell'aspetto di un virus informatico
Dettagli I quattro file F 1 , F 2 , F 3 , F 4 F 1 ,F 2 ,F 3 ,F 4 sono dati in input, rappresentati come quattro stringhe di caratteri di lunghezza rispettivamente N 1 , N 2 , N 3 , N 4 N 1 ,N 2 ,N 3 ,N 4 .
Il virus è una stringa di caratteri V V di lunghezza M M. La lunghezza M M è data in input, ma non si conosce il contenuto della stringa V V del virus.
Sappiamo con certezza che il virus V V appare all'interno di tutti e quattro i file, come sottostringa di caratteri consecutivi. Sappiamo inoltre che NON ci sono altre sottostringhe consecutive di lunghezza M M che si ripetono uguali in tutti e quattro i file.
Le posizioni dei caratteri nelle stringhe sono numerati a partire da 0 0. Per ciascuno dei quattro file F i F i , trova la posizione in cui è inserito il virus, ovvero la posizione dove appare il primo carattere del virus V V all'interno della stringa F i F i .
Assunzioni T
12 T=12, sono presenti 12 12 casi di input. 2 ≤ N 1 , N 2 , N 3 , N 4 ≤ 100 2≤N 1 ,N 2 ,N 3 ,N 4 ≤100, i file non sono più lunghi di 100 100 caratteri. 2 ≤ M ≤ 20 2≤M≤20, il virus non è più lungo di 20 20 caratteri. M ≤ min ( N 1 , N 2 , N 3 , N 4 ) M≤min(N 1 ,N 2 ,N 3 ,N 4 ), il virus non è più lungo del file più corto. Tutti i caratteri dei file sono lettere minuscole dell'alfabeto inglese (dalla a alla z), NON sono presenti spazi. È garantito che il virus esiste ed è unico. Dati di input La prima riga del file di input contiene un intero T T, il numero di casi di test. Seguono T T casi di test, numerati da 1 1 a T T. Ogni caso di test è preceduto da una riga vuota.
In ciascun caso di test:
La prima riga contiene quattro interi, N 1 N 1 , N 2 N 2 , N 3 N 3 e N 4 N 4 , separati da uno spazio, che corrispondono alla lunghezza di ciascuno dei quattro file. La seconda riga contiene un solo intero M M, che corrisponde alla lunghezza del virus. Le successive 4 4 righe contengono rispettivamente le quattro stringhe F 1 F 1 , F 2 F 2 , F 3 F 3 e F 4 F 4 . Dati di output Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura
Case #t: p1 p2 p3 p4 dove t è il numero del caso di test (a partire da 1
- e i valori p1, p2, p3, p4 sono le posizioni in cui si trova il virus in ciascuno dei quattro file. Con posizione si intende l'indice del primo carattere del virus, il primo carattere del file ha indice zero.
Esempi di input/output Input: Download
2
8 12 10 7 4 ananasso associazione tassonomia massone
6 9 11 10 3 simone ponessimo milionesimo cassonetto Output: Download
Case #1: 4 0 1 1 Case #2: 3 1 4 4 Spiegazione Nel primo caso d'esempio il virus è asso: ananasso, associazione, tassonomia, massone.
Nel secondo caso d'esempio il virus è one: simone, ponessimo, milionesimo, cassonetto. Nota che sim è presente nei primi tre file ma non nel quarto, quindi non è il virus cercato.
Esempi di implementazione Per aiutarti con questo task, abbiamo preparato degli esempi di implementazione di una soluzione. Includono solo le parti di lettura dell'input e scrittura dell'output:
PLS SOLVE AND EXPLAIN EVERYTHING PLSS AND UR THINKING AND THE TRICK
USE THIS TEMPLATE FOR THE CODE IN CPP #include <bits/stdc++.h> #define int long long using namespace std;
signed main() { cin.tie(0); ios_base::sync_with_stdio(false); ///
}
- Assistant
Certamente! Affrontiamo il problema passo dopo passo, spiegando il ragionamento e l'approccio per arrivare alla soluzione desiderata. Successivamente, forniremo un'implementazione in C++ utilizzando il template fornito.
Comprensione del Problema
Abbiamo quattro file, F₁, F₂, F₃ e F₄, ciascuno rappresentato come stringhe di caratteri. Un virus V, anch'esso una stringa, di lunghezza M è presente in tutti e quattro i file come una sottostringa consecutiva. Il virus V compare esattamente una volta in ciascun file, ed è l'unico virus di lunghezza M che soddisfa questa condizione.
L'obiettivo è determinare le posizioni di inizio del virus in ciascuno dei quattro file.
Input Format
- T: Numero di casi di test.
- Per ogni caso di test:
- Una riga vuota (tranne forse il primo caso di test).
- Quattro interi N₁, N₂, N₃, N₄: lunghezze dei quattro file.
- Un intero M: lunghezza del virus.
- Quattro stringhe F₁, F₂, F₃, F₄: contenuto dei quattro file.
Output Format
Per ogni caso di test, stampare una riga nel formato:
Case #t: p1 p2 p3 p4dove
tè il numero del caso di test (iniziando da 1) ep1,p2,p3,p4sono le posizioni di inizio del virus nei file F₁, F₂, F₃ e F₄ rispettivamente.Approccio alla Soluzione
Per ogni caso di test, dobbiamo identificare la sottostringa di lunghezza M che appare in tutti e quattro i file e determinare le sue posizioni di inizio in ciascun file. Poiché il virus è unico e garantito per esistere, possiamo procedere seguendo questi passaggi:
-
Enumerare le Sottostringhe Candidate:
- Consideriamo tutte le possibili sottostringhe di lunghezza M in uno dei file (ad esempio, F₁).
- Per ogni sottostringa di F₁, verifichiamo se essa appare anche negli altri tre file (F₂, F₃, F₄).
-
Verificare la Presenza nei Restanti File:
- Utilizziamo il metodo
finddelle stringhe in C++ per cercare la sottostringa nei restanti file. - Se la sottostringa è presente in tutti e quattro i file, abbiamo identificato il virus.
- Utilizziamo il metodo
-
Ottenere le Posizioni di Inizio:
- Una volta identificato il virus, usiamo nuovamente il metodo
findper ottenere le posizioni di inizio in ciascun file.
- Una volta identificato il virus, usiamo nuovamente il metodo
-
Gestione dei Casi di Test:
- Ripetiamo il processo per tutti i T casi di test, assicurandoci di gestire correttamente le righe vuote che precedono ciascun caso di test.
Implementazione
Ecco come possiamo implementare la soluzione in C++:
#include <bits/stdc++.h> #define int long long using namespace std; signed main() { cin.tie(0); ios_base::sync_with_stdio(false); int T; cin >> T; cin.ignore(); // Ignora il carattere di nuova linea dopo T for(int test_case=1; test_case<=T; test_case++) { // Leggi e ignora eventuali righe vuote string line; while(getline(cin, line)){ if(line.empty()) continue; else break; } // Ora, line contiene la prima riga del caso di test con N1 N2 N3 N4 // Se non abbiamo ancora letto nulla, leggere di nuovo // Parse N1, N2, N3, N4 int N1, N2, N3, N4; // Usa uno stringstream per estrarre gli interi stringstream ss(line); ss >> N1 >> N2 >> N3 >> N4; // Leggi M int M; cin >> M; cin.ignore(); // Ignora il carattere di nuova linea dopo M // Leggi F1, F2, F3, F4 string F1, F2, F3, F4; getline(cin, F1); getline(cin, F2); getline(cin, F3); getline(cin, F4); // Enumerare tutte le sottostringhe di F1 di lunghezza M string virus; int p1, p2, p3, p4; bool found = false; for(int i=0; i <= N1 - M; i++) { string candidate = F1.substr(i, M); // Verifica se candidate è presente in F2, F3, F4 size_t pos2 = F2.find(candidate); if(pos2 == string::npos) continue; size_t pos3 = F3.find(candidate); if(pos3 == string::npos) continue; size_t pos4 = F4.find(candidate); if(pos4 == string::npos) continue; // Se trovato in tutti, assegna le posizioni virus = candidate; p1 = i; p2 = pos2; p3 = pos3; p4 = pos4; found = true; break; // Poiché è unico, possiamo uscire } // Output nel formato richiesto cout << "Case #" << test_case << ": " << p1 << " " << p2 << " " << p3 << " " << p4 << "\n"; } return 0; }Spiegazione del Codice
-
Inizializzazione e Lettura di T:
cin.tie(0); ios_base::sync_with_stdio(false); int T; cin >> T; cin.ignore(); // Ignora il carattere di nuova linea dopo Tcin.tie(0)eios_base::sync_with_stdio(false)ottimizzano le operazioni di input/output.- Leggiamo il numero di casi di test
Te ignoriamo il carattere di nuova linea successivo.
-
Loop sui Casi di Test:
for(int test_case=1; test_case<=T; test_case++) { // ... }- Iteriamo da 1 a T, dove
test_caserappresenta il numero corrente del caso di test.
- Iteriamo da 1 a T, dove
-
Gestione delle Righe Vuote:
string line; while(getline(cin, line)){ if(line.empty()) continue; else break; }- Utilizziamo
getlineper leggere le righe fino a trovare una non vuota, che sarà la linea contenente N₁, N₂, N₃, N₄.
- Utilizziamo
-
Estrazione di N₁, N₂, N₃, N₄:
int N1, N2, N3, N4; stringstream ss(line); ss >> N1 >> N2 >> N3 >> N4;- Usiamo uno
stringstreamper estrarre i quattro interi dalla riga letta.
- Usiamo uno
-
Lettura di M e dei File:
int M; cin >> M; cin.ignore(); // Ignora il carattere di nuova linea dopo M string F1, F2, F3, F4; getline(cin, F1); getline(cin, F2); getline(cin, F3); getline(cin, F4);- Leggiamo
M, ignoriamo la nuova linea successiva, e poi leggiamo le quattro stringhe dei file.
- Leggiamo
-
Enumerazione delle Sottostringhe e Verifica:
for(int i=0; i <= N1 - M; i++) { string candidate = F1.substr(i, M); size_t pos2 = F2.find(candidate); if(pos2 == string::npos) continue; size_t pos3 = F3.find(candidate); if(pos3 == string::npos) continue; size_t pos4 = F4.find(candidate); if(pos4 == string::npos) continue; // Se trovato in tutti, assegna le posizioni virus = candidate; p1 = i; p2 = pos2; p3 = pos3; p4 = pos4; found = true; break; // Poiché è unico, possiamo uscire }- Per ogni possibile sottostringa di lunghezza
Min F₁, verifichiamo se appare in F₂, F₃ e F₄ usando il metodofind. - Se la sottostringa è presente in tutti e quattro i file, registriamo le posizioni di inizio e interrompiamo la ricerca, poiché il virus è unico.
- Per ogni possibile sottostringa di lunghezza
-
Output Risultato:
cout << "Case #" << test_case << ": " << p1 << " " << p2 << " " << p3 << " " << p4 << "\n";- Stampiamo le posizioni trovate nel formato richiesto.
Esempio di Funzionamento
Consideriamo il primo esempio fornito:
Input:
2 8 12 10 7 4 ananasso associazione tassonomia massone 6 9 11 10 3 simone ponessimo milionesimo cassonettoOutput:
Case #1: 4 0 1 1 Case #2: 3 1 4 4Spiegazione:
-
Primo Caso di Test:
- Il virus è "asso" di lunghezza 4.
- In F₁ ("ananasso"), "asso" inizia alla posizione 4.
- In F₂ ("associazione"), "asso" inizia alla posizione 0.
- In F₃ ("tassonomia"), "asso" inizia alla posizione 1.
- In F₄ ("massone"), "asso" inizia alla posizione 1.
-
Secondo Caso di Test:
- Il virus è "one" di lunghezza 3.
- In F₁ ("simone"), "one" inizia alla posizione 3.
- In F₂ ("ponessimo"), "one" inizia alla posizione 1.
- In F₃ ("milionesimo"), "one" inizia alla posizione 4.
- In F₄ ("cassonetto"), "one" inizia alla posizione 4.
Conclusione
Abbiamo implementato una soluzione che, per ogni caso di test, esamina tutte le possibili sottostringhe di lunghezza M nel primo file e verifica la loro presenza negli altri tre file. Una volta identificato il virus, le posizioni di inizio vengono registrate e stampate nel formato richiesto.