Ciao,
Sto tentando di risolvere il problema “sport intellettuali”, ho pensato ad un approggio greedy-implementation ma totalizzo solamente 2 punti.
Qualcuno mi potrebbe spiegare l’idea risolutiva? (Ho letto il codice della soluzione ma non riesco a capire…)
L’idea di base è semplice , devi capire come per ogni carta capire se quella potrà rimanere sola sul tavolo, basta notare quale condizione permette ad una di rimanere in tavola e applicarla a tutte le carte.
Non so quale sia la soluzione ufficiale , comunque l’idea di base sarà la stessa.
2 Mi Piace
Ho caricato sulla piattaforma training la mia soluzione, che allego qui di seguito.
Ottengo solo 20 punti su 100.
Qualcuno riuscirebbe ad aiutarmi a capire come risolvere al meglio questo problema?
#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector <int> carte;
int val,N1;
// uncomment the following lines if you want to read/write from files
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
assert(1 == scanf("%d", &N1));
for(int i=0; i<N1; i++){
assert(1 == scanf("%d", &val));
carte.push_back(val);
}
int somma;
while (carte.size()>0 ){
for (int i=0; i<carte.size()-1;i++){
somma = carte[i]+carte[i+1];
if (somma %2 == 1){
//cout << "Removed "<<carte[i]<<" e "<<carte[i+1]<<endl;
carte.erase(carte.begin()+i+1);
carte.erase(carte.begin()+i);
break;
}
}
if (carte.size() < 2){
break;
}
else
if (carte.size() == 2){
int somma_fin = carte[0]+carte[1];
if (somma_fin % 2 == 0){
break;
}
}
}
//cout << "Output"<<endl;
cout << carte.size()<<endl;
for(int i=0; i<carte.size(); i++){
cout << carte[i]<<" ";
}
cout << endl;
return 0;
}
Ciao, il tuo codice simula una singola partita e pertanto fornisce uno solo dei possibili risultati. Quindi l’approccio non è adatto per individuare tutte le combinazioni con cui una partita può terminare.
Considera che il numero N di carte sul tavolo, comprese tra 0 e N-1, è dispari ne consegue che ci sono N/2+1 carte pari e N/2 carte dispari e che per ottenere una somma dispari tra due carte consecutive occorrono due carte successive pari-dispari o dispari-pari.
Pertanto dopo tutti gli accoppiamenti possibili p-d e/o d-p sul tavolo rimarrà una carta pari. Quindi si tratta di individuare tutte le possibili carte pari che possono rimanere sul tavolo.
Prendiamo l’esempio del subtask:
11
1 0 2 6 4 5 3 9 8 10 7
d p p p p d d d p p d
Osservando la sequenza delle carte p/d che sono sul tavolo ogni possibile carta pari che può rimanere sul tavolo in una partita è la prima carta pari dopo ogni combinazione di coppie p-d e/o d-p.
Per tornare all’esempio, la prima carta pari che si incontra dopo una sequenza d-p (1,0) è 2 e a seguire la successiva prima carta pari è 8 che viene dopo la sequenza di coppie (4,5), (6,9) e (2,9). Non ci sono altre possibili carte pari, pertanto basta ogni volta inserire la carta trovata in un vector e stampare il risultato finale.
Ho provato a seguire la tua soluzione, ma purtroppo non mi pare funzionare molto bene (0/100).
#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
bool pari(int val){
if (val % 2 == 0)
return true;
else
return false;
}
int main() {
vector <int> carte;
set <int> carte_final;
int val,N1, somma;
// uncomment the following lines if you want to read/write from files
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
assert(1 == scanf("%d", &N1));
for(int i=0; i<N1; i++){
assert(1 == scanf("%d", &val));
carte.push_back(val);
}
for (int j=0; j<carte.size()-1; j++){
for (int i=j; i<carte.size()-1;i++){
somma = carte[i]+carte[i+1];
if (somma % 2 == 1){
if (i+2 < carte.size() && pari(carte[i+2])){
carte_final.insert(carte[i+2]);
cout << "starting from "<<j<<" card"<<carte[i]<<" + "<<carte[i+1]<<" -> "<<carte[i+2]<<" removed"<<endl;
}
}
}
}
//cout << "Output"<<endl;
cout << carte_final.size()<<endl;
for (auto it = carte_final.begin(); it != carte_final.end(); ++it)
cout << ' ' << *it;
cout << endl;
return 0;
}
Mi mostra solo 2 e 10 anziché 2 e 8. Cosa sto sbagliando?
Direi che devi controllare solo le carte pari che occupano posizioni di indice pari (il 10 sta in posizione 9)
e rimarranno sul tavolo solo quelle per le quali la quantità di carte pari alla loro sinistra è uguale alla quantità di carte dispari alla loro sinistra.(Se è così a sinistra sarà così anche a destra e viceversa).
Quindi nell’esempio sono da analizzare solo le carte:2,4,8;
ma il 4 non rimarrà ha alla sua sinistra 1 carta dispari e 3 pari (e a destra 4 dispari e 2 pari).
Grazie!
Seguo la tua strategia, che mi ha convinto, ma ottengo solo 10/100.
Cosa sbaglio?
#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
void conta_sx(vector <int> cards, int final_ind, int &pari, int &dispari){
for (int i=0; i<final_ind; i++){
if (cards[i] % 2 == 0)
pari++;
else
dispari++;
}
}
void conta_dx(vector <int> cards, int initial_ind, int &pari, int &dispari){
for (int i=initial_ind+1; i<cards.size(); i++){
if (cards[i] % 2 == 0)
pari++;
else
dispari++;
}
}
int main() {
vector <int> carte;
set <int> carte_final;
int val,N1;
// uncomment the following lines if you want to read/write from files
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
assert(1 == scanf("%d", &N1));
for(int i=0; i<N1; i++){
assert(1 == scanf("%d", &val));
carte.push_back(val);
}
int conta_sx_pari, conta_sx_dispari, conta_dx_pari, conta_dx_dispari;
for (int j=0; j<carte.size();j=j+2){
cout << "Analyzing card "<<carte[j]<<endl;
if (carte[j]%2!=0)
continue;
conta_dx_dispari = 0;
conta_dx_pari = 0;
conta_sx_pari = 0;
conta_sx_dispari = 0;
conta_sx(carte, j, conta_sx_pari, conta_sx_dispari);
conta_dx(carte,j, conta_dx_pari, conta_dx_dispari);
cout << "sx pari "<<conta_sx_pari<<" sx dispari "<<conta_sx_dispari<<" dx pari "<<conta_dx_pari<<" dx dispari "<<conta_dx_dispari<<endl;
if ((conta_sx_pari == conta_sx_dispari && conta_sx_dispari!=0 ) && (conta_dx_dispari == conta_dx_pari && conta_dx_dispari!=0)){
carte_final.insert(carte[j]);
cout << "Inserted "<<carte[j]<<endl;
}
}
cout << "********Output*************"<<endl;
cout << carte_final.size()<<endl;
for(auto it=carte_final.begin(); it!=carte_final.end(); ++it){
cout << *it<<" ";
}
cout << endl;
return 0;
}
Con una sola modifica funziona:
#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
void conta_sx(vector <int> cards, int final_ind, int& pari, int& dispari) {
for (int i = 0; i < final_ind; i++) {
if (cards[i] % 2 == 0)
pari++;
else
dispari++;
}
}
void conta_dx(vector <int> cards, int initial_ind, int& pari, int& dispari) {
for (int i = initial_ind + 1; i < cards.size(); i++) {
if (cards[i] % 2 == 0)
pari++;
else
dispari++;
}
}
int main() {
vector <int> carte;
set <int> carte_final;
int val, N1;
// uncomment the following lines if you want to read/write from files
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
assert(1 == scanf("%d", &N1));
for (int i = 0; i < N1; i++) {
assert(1 == scanf("%d", &val));
carte.push_back(val);
}
int conta_sx_pari, conta_sx_dispari, conta_dx_pari, conta_dx_dispari;
for (int j = 0; j < carte.size(); j = j + 2) {
//cout << "Analyzing card " << carte[j] << endl;
if (carte[j] % 2 != 0)
continue;
conta_dx_dispari = 0;
conta_dx_pari = 0;
conta_sx_pari = 0;
conta_sx_dispari = 0;
conta_sx(carte, j, conta_sx_pari, conta_sx_dispari);
conta_dx(carte, j, conta_dx_pari, conta_dx_dispari);
//cout << "sx pari " << conta_sx_pari << " sx dispari " << conta_sx_dispari << " dx pari " << conta_dx_pari << " dx dispari " << conta_dx_dispari << endl;
if ((conta_sx_pari == conta_sx_dispari ) && (conta_dx_dispari == conta_dx_pari )) {
carte_final.insert(carte[j]);
//cout << "Inserted " << carte[j] << endl;
}
}
//&& conta_sx_dispari != 0 TOLTO!!
//&& conta_dx_dispari != 0 TOLTO!!
//cout << "********Output*************" << endl;
cout << carte_final.size() << endl;
for (auto it = carte_final.begin(); it != carte_final.end(); ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
Si può fare più semplice, comunque la parte sbagliata era:
if ((conta_sx_pari == conta_sx_dispari && conta_sx_dispari!=0 ) && (conta_dx_dispari == conta_dx_pari && conta_dx_dispari!=0)){
conta_sx_dispari può essere 0 (purchè lo sia anche conta_sx_dispari) un numero pari in posizione 0 rimane a tavola come pure un numero pari in ultima posizione (conta_dx_dispari=0 e conta_dx_pari=0).
Comunque basta fare i controlli solo a sinistra (se conta_sx_pari =conta_sx_dispari sicuramente torneranno anche i controlli a destra quindi inutile farli) oppure solo a destra …
1 Mi Piace
Grazie!
Non mi ero proprio accorto del pattern che mi hai suggerito tu (numero pari sx = numero pari dx).
Potresti spiegarmi come arrivi a dire che se a sinistra il numero di carte dispari è uguale al numero di carte pari, allora lo sarà anche a destra e viceversa?
Io sono riuscito a trovare una soluzione peggiore ( O(N^3) )che tuttavia mi consente di fare 90/100. Dato che nelle assunzioni c’è N <= 100 non mi sono sforzato a trovarne al momento una migliore.
void solve(){
fstream file_in("input.txt", fstream::in);
fstream file_out("output.txt", fstream::out);
set<int> u;
int n;
file_in >> n;
vector<int> s(n), v;
for(int i = 0; i < n; i++)
file_in >> s[i];
bool flag; // flag che indica se sono state fatte mosse
for(int start = 0; start < n - 1; start++){ //scorre tutte le possibili sequenze di mosse
int i = start;
v = s;
flag = true;
while(flag){//fin quando vengono fatte mosse c'è la possibilità che se ne faccia un altra
flag = false;
while(i < v.size() - 1 && v.size() > 1){// fin quando posso fare somme di 2 carte vicine e fin quando c'è piu di una carta sul tavolo
if((v[i] + v[i+1]) % 2 != 0){ // se la somma è dispari le elimino
flag = true;
v.erase(v.begin() + i);
v.erase(v.begin() + i);
if(i > 0) //se le carte eliminate non erano le prime due
i--; //al prossimo ciclo controllo quella subito prima con quella subito dopo
}
else i++; // se la somma non è dispari passo alle prossime due
}
i = 0;
}
if(v.size() == 1) //se e rimasta una sola carta la inserisco nell'output
u.insert(v[0]);
}
file_out << u.size() << endl;
for(int x : u)
file_out << x << " ";
//cout << endl;
file_in.close();
file_out.close();
}
Spero si capisca la logica dai commenti… secondo voi qual’è il problema che non mi consente di superare l’ultimo subtask?
Le carte pari sono 1 più delle dispari. Siccome prendiamo in considerazione solo carte pari per le restanti avremo in totale tante carte pari per quante sono le dispari. Quindi siano K le pari e le dispari restanti:
ora se a sinistra della carta che analizziamo (e che come abbiamo detto è pari) ce ne sono K1 pari e K1 dispari (con K1<=K) a destra avremo K-K1 pari ed altrettante dispari. C.V.D.
Ok ho capito l’idea ma l’assunzione che fai all’inizio “le carte pari sono 1 in più delle dispari” non è sempre vera, banalmente se abbiamo le carte {1,2,3} non è vera.
Inoltre se abbiamo le carte {3,4,2,1,5}, 3 e 5 non potrebbero restare sul tavolo?
- 3 resta perché si eliminano prima 2 e 1 e poi 4 e 5
- 5 resta perché si eliminano (3,4) e (2,1)
Ovviamente so di sbagliare qualcosa io poiché questa soluzione fa 100/100 e non credo sia sbagliato il sistema di correzione.
Leggi meglio il testo del problema: le carte sono numerate da …
Se fai partire la numerazione da 1 tutta la trattazione rimane vera invertendo le pari con le dispari, ovvero rimarranno solo le dispari che sono una in più delle pari e …
avevo letto male ti ringrazio