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
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:
1. Una riga vuota (tranne forse il primo caso di test).
2. Quattro interi N₁, N₂, N₃, N₄: lunghezze dei quattro file.
3. Un intero M: lunghezza del virus.
4. 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 p4
```
dove `t` è il numero del caso di test (iniziando da 1) e `p1`, `p2`, `p3`, `p4` sono 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:
1. **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₄).
2. **Verificare la Presenza nei Restanti File**:
- Utilizziamo il metodo `find` delle stringhe in C++ per cercare la sottostringa nei restanti file.
- Se la sottostringa è presente in tutti e quattro i file, abbiamo identificato il virus.
3. **Ottenere le Posizioni di Inizio**:
- Una volta identificato il virus, usiamo nuovamente il metodo `find` per ottenere le posizioni di inizio in ciascun file.
4. **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++:
```cpp
#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**
1. **Inizializzazione e Lettura di T**:
```cpp
cin.tie(0);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
cin.ignore(); // Ignora il carattere di nuova linea dopo T
```
- `cin.tie(0)` e `ios_base::sync_with_stdio(false)` ottimizzano le operazioni di input/output.
- Leggiamo il numero di casi di test `T` e ignoriamo il carattere di nuova linea successivo.
2. **Loop sui Casi di Test**:
```cpp
for(int test_case=1; test_case<=T; test_case++) {
// ...
}
```
- Iteriamo da 1 a T, dove `test_case` rappresenta il numero corrente del caso di test.
3. **Gestione delle Righe Vuote**:
```cpp
string line;
while(getline(cin, line)){
if(line.empty()) continue;
else break;
}
```
- Utilizziamo `getline` per leggere le righe fino a trovare una non vuota, che sarà la linea contenente N₁, N₂, N₃, N₄.
4. **Estrazione di N₁, N₂, N₃, N₄**:
```cpp
int N1, N2, N3, N4;
stringstream ss(line);
ss >> N1 >> N2 >> N3 >> N4;
```
- Usiamo uno `stringstream` per estrarre i quattro interi dalla riga letta.
5. **Lettura di M e dei File**:
```cpp
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.
6. **Enumerazione delle Sottostringhe e Verifica**:
```cpp
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 `M` in F₁, verifichiamo se appare in F₂, F₃ e F₄ usando il metodo `find`.
- Se la sottostringa è presente in tutti e quattro i file, registriamo le posizioni di inizio e interrompiamo la ricerca, poiché il virus è unico.
7. **Output Risultato**:
```cpp
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
cassonetto
```
### **Output:**
```
Case #1: 4 0 1 1
Case #2: 3 1 4 4
```
**Spiegazione:**
- **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.