#include # define clr(x,a) memset(x,a,sizeof(x)) # define all(a) a.begin(), a.end() # define deb(x) cout<<#x<<"=="< vi; typedef pair pii; const int mxN = 30, mxM = 50000, mxDepth = 50, N[4] = {4, 2, 2, 2}; const ll INF = 1e15; const int srr[9] = {0, 0, 0, -1, -1, -1, 1, 1, 1}; const int scc[9] = {-1, 1, 0, -1, 1, 0, -1, 1, 0}; int n, m, max_depth = 3; ll c[mxM], f[mxM], a, b, d, e, C, F; clock_t END; pii blocks[5][4][3], res[mxM]; bool board[mxDepth][mxN][mxN], curr_board[mxDepth][mxN][mxN]; inline bool in_bounds(int& r, int& c){ return (r >= 1 && r <= n && c >= 1 && c <= n); } void cout_board(int d){ //cout << "Board (" << d << ")\n"; FOR(i, 1, n){ FOR(j, 1, n){ cout << board[d][i][j]; } cout << endl; } } struct Heuristic{ int A = 5, B = 10, C = 15, D = 5, E = 5, F = -15; ll calc(int& a, int& b, int& c, int& d, int& e, int& f){ return a*A + b*B + c*C + d*D + e*E + f*F; } int empty_cells(int& depth){ int ret = 0; FOR(i, 1, n){ FOR(j, 1, n) if(!board[depth][i][j]) ret++; } return ret; } int empty_3x3(int& depth){ //cout << "Empty 3x3 " << depth << endl; int exist, ret = 0; FOR(i, 2, n-1){ FOR(j, 2, n-1){ exist = 1; FOR(s, 0, 8){ if(board[depth][i+srr[s]][j+scc[s]]){ exist = 0; break; } } ret += exist; } } return ret; } int empty_li_blocks(int& depth){ vi v; int ret = 0, temp; ///calculation of ___ FOR(row, 1, n){ temp = 0; FOR(col, 1, n){ if(!board[depth][row][col]) temp++; else if(temp){ v.pb(temp); temp = 0; } } if(temp) v.pb(temp); } ///calculation of | FOR(col, 1, n){ temp = 0; FOR(row, 1, n){ if(!board[depth][row][col]) temp++; else if(temp){ v.pb(temp); temp = 0; } } if(temp) v.pb(temp); } for(int i: v){ if(i >= 4){ ret += i-3; } } ///calculation of L int nr, nc; FOR(rot, 0, 3){ //block[2][rot] //cout << "Rotation: " << rot << endl; FOR(row, 1, n){ FOR(col, 1, n){ temp = 1; if(board[depth][row][col]) continue; //cout << "Pos: " << row << " " << col << "\n"; FOR(i, 0, 2){ nr = row + blocks[2][rot][i].x; nc = col + blocks[2][rot][i].y; if(!in_bounds(nr, nc)){ temp = 0; break; } //cout << " " << nr << ", " << nc << endl; if(board[depth][nr][nc]) temp = 0; } //if(temp) cout << "+= 1\n"; //else cout << endl; ret += temp; } } } return ret; } int holes_in_grid(int& depth){ int ret = 0; return ret; } int alignment_maximization(int& depth){ int ret = 0; return ret; } int surface_minimization(int& depth){ int ret = 0; return ret; } }h; void input(){ freopen("block.in", "r", stdin); cin >> n >> a >> b >> C >> d >> e >> F; max_depth = N[(n-1)/8]; //deb(max_depth); for(int i = 1; i < mxM; i++){ C = (C ^ a) + b; F = (F ^ d) + e; c[i] = C%5; f[i] = F%4; } } void output(){ freopen("block.out", "w", stdout); pr("%d\n", m); FOR(i, 1, m){ pr("%d %d\n", res[i].x, res[i].y); } } void generate_blocks(){ // xx // xx blocks[0][0][0] = mp(-1, 0); blocks[0][0][1] = mp(-1, -1); blocks[0][0][2] = mp(0, -1); blocks[0][1][0] = mp(0, 1); blocks[0][1][1] = mp(-1, 0); blocks[0][1][2] = mp(-1, 1); // .x // xx blocks[1][0][0] = mp(-1, 0); blocks[1][0][1] = mp(0, -1); blocks[1][0][2] = mp(0, 0); blocks[1][1][0] = mp(-1, 0); blocks[1][1][1] = mp(0, +1); blocks[1][1][2] = mp(0, 0); // ..x // xxx blocks[2][0][0] = mp(-1, 0); blocks[2][0][1] = mp(0, -1); blocks[2][0][2] = mp(0, -2); blocks[2][1][0] = mp(0, 1); blocks[2][1][1] = mp(-1, 0); blocks[2][1][2] = mp(-2, 0); // xxxx blocks[3][0][0] = mp(0, -1); blocks[3][0][1] = mp(0, -2); blocks[3][0][2] = mp(0, -3); blocks[3][1][0] = mp(-1, 0); blocks[3][1][1] = mp(-2, 0); blocks[3][1][2] = mp(-3, 0); // .x. // xxx blocks[4][0][0] = mp(-1, 0); blocks[4][0][1] = mp(-2, 0); blocks[4][0][2] = mp(-1, -1); blocks[4][1][0] = mp(0, 1); blocks[4][1][1] = mp(0, 2); blocks[4][1][2] = mp(-1, +1); //rotation FOR(j, 0, 4){ FOR(i, 0, 2){ blocks[j][2][i] = mp(-1*blocks[j][0][i].x, -1*blocks[j][0][i].y); blocks[j][3][i] = mp(-1*blocks[j][1][i].x, -1*blocks[j][1][i].y); } } /* FOR(block, 0, 4){ FOR(rot, 0, 3){ clr(board, 0); FOR(j, 0, 2){ board[4+blocks[block][rot][j].x][4+blocks[block][rot][j].y] = 1; } board[4][4] = 1; FOR(j, 0, 8){ FOR(z, 0, 8){ cout << board[j][z]; } cout << endl; } cout << endl; } }*/ } inline bool possible_move(int& depth, int& row, int& col){ int r2, c2; FOR(i, 0, 2){ r2 = row + blocks[c[depth+m]][f[depth+m]][i].x; c2 = col + blocks[c[depth+m]][f[depth+m]][i].y; if(!in_bounds(r2, c2)) return false; if(board[depth][r2][c2]) return false; //if(board[depth][r2][c2]) return true; } if(board[depth][row][col]) return false; return true; } void clear_rows_cols(int& depth){ vi cols, rows; int temp; FOR(i, 1, n){ temp = 0; FOR(j, 1, n){ if(board[depth][i][j] == 1) temp++; } if(temp == n) rows.pb(i); } FOR(j, 1, n){ temp = 0; FOR(i, 1, n){ if(board[depth][i][j] == 1) temp++; } if(temp == n) cols.pb(j); } FOR(i, 1, n){ for(int j: cols) board[depth][i][j] = 0; } for(int i: rows){ FOR(j, 1, n) board[depth][i][j] = 0; } } void place(int& depth, int& row, int& col){ memcpy(board[depth+1], board[depth], sizeof(board[depth])); board[depth+1][row][col] = true; FOR(i, 0, 2){ board[depth+1][row + blocks[c[m+depth]][f[m+depth]][i].x] [col + blocks[c[m+depth]][f[m+depth]][i].y] = true; } depth++; clear_rows_cols(depth); depth--; } ll calc_heuristic(int& depth){ //cout_board(depth); int a, b, c, d, e, f; a = h.empty_cells(depth); b = h.empty_3x3(depth); c = h.empty_li_blocks(depth); d = h.alignment_maximization(depth); e = h.surface_minimization(depth); f = h.holes_in_grid(depth); //pr("%d %d %d %d %d %d\n", a, b, c, d, e, f); ll ret = h.calc(a, b, c, d, e, f); //deb(ret); return ret; } ll back_tracking(int depth){ if(depth == max_depth){ return calc_heuristic(depth); } int br = -1, bc = -1; ll best_score = 0, temp_score; FOR(i, 1, n){ FOR(j, 1, n){ if(possible_move(depth, i, j)){ //cout << "Possible move: " << i << ", " << j << endl; place(depth, i, j); temp_score = back_tracking(depth+1); if(temp_score > best_score){ best_score = temp_score; br = i; bc = j; } } } } if(depth == 1){ if(best_score == 0) return 0; //deb(best_score); //pr("%d, %d\n", br, bc); board[1][br][bc] = true; FOR(i, 0, 2){ board[1][br + blocks[c[m+depth]][f[m+depth]][i].x] [bc + blocks[c[m+depth]][f[m+depth]][i].y] = true; } res[++m] = mp(br, bc); br = 1; clear_rows_cols(br); return 1; } return best_score; } void solve(){ //freopen("block.out", "w", stdout); int x = 1; while(x){ //if(clock() >= END) return; //cout << "Postavljam block: " << c[m+1] << " " << f[m+1] << endl; x = back_tracking(1); //cout_board(1); //if(m == 15) break; } } int main(){ END = clock() + 4500; // Start timer input(); generate_blocks(); solve(); output(); return 0; }