Ciao, stavo cercando di risolvere Carlo’s Garden (grasshopper2), purtroppo alcuni testcase non passano. La mia logica è quella di posizionare le trappole sulla stessa diagonale in modo intelligente rispetto ai movimenti della cavalletta, in modo da sbarrarle per forza la strada a una certa distanza. Ho provato un sacco di possibilità a mano (guardando le risposte del programma rispetto ai possibili spostamenti) che risultano sempre corrette, ma comunque alcuni testcase non passano. Quello che mi fa strano è che non passano neanche alcuni della seconda subtask (N = 2) per la quale ho provato tantissimi possibili percorsi …
Volevo chiedere in primis se qualcuno riesce a trovare dei possibili input che non possano sul mio programma.
Condivido il mio codice:
#include <bits/stdc++.h>
using namespace std;
int N;
int main() {
cin >> N;
int g_x = 0, g_y = 0;
int new_g_x = 0, new_g_y = 0;
int diagonale = N*N*N;
int precedente = diagonale;
vector<bool> traps(diagonale*2 + 1, false);
do {
int trap_x = precedente + (new_g_x - g_x) - (new_g_y - g_y);
if ((diagonale * 2) - trap_x < new_g_y) trap_x = diagonale*2 - new_g_y;
if (trap_x < new_g_x) trap_x = new_g_x;
precedente = trap_x;
int plus = 1;
while(traps[trap_x] && plus < 500) {
if (trap_x + plus >= new_g_x && (diagonale * 2) - (trap_x + plus) >= new_g_y && !traps[trap_x + plus]){
trap_x += plus;
break;
}
if (trap_x - plus >= new_g_x && (diagonale * 2) - (trap_x - plus) >= new_g_y && !traps[trap_x - plus]){
trap_x -= plus;
break;
}
plus ++;
}
traps[trap_x] = true;
int trap_y = (diagonale * 2) - trap_x;
// if (trap_x == new_g_x && trap_y == new_g_y) {
// cerr << "Errore: trappola su g." << endl;
// return 1;
// }
cout << trap_x << " " << trap_y << endl;
cout.flush();
g_x = new_g_x;
g_y = new_g_y;
cin >> new_g_x >> new_g_y;
if (new_g_x == -1 && new_g_y == -1) {
break;
}
} while (true);
return 0;
}
Grazie in anticipo.