#4461
veverite
Două veverițe gemene au descoperit un depozit de alune care are o formă foarte ciudată. Mai precis, depozitul are forma unei matrice N x N
cu N
impar. Fiecare poziție din matrice este o cameră și în fiecare cameră se află câte o alună. Camerele sunt numerotate cu numărul de linie și numărul de coloană. Cunoscând N
, să se răspundă la Q
întrebări de forma: “Ce traseu a notat Chip pe poziția P
?”
Problema | veverite | Operații I/O |
veverite.in /veverite.out
|
---|---|---|---|
Limita timp | 0.3 secunde | Limita memorie |
Total: 256 MB
/
Stivă 64 MB
|
Id soluție | #44014038 | Utilizator | |
Fișier | veverite.cpp | Dimensiune | 8.80 KB |
Data încărcării | 07 Iunie 2023, 21:27 | Scor / rezultat | 11 puncte |
veverite.cpp: In member function 'int BigInt::operator[](int) const': veverite.cpp:2:2163: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] using namespace std;class BigInt{ string digits;public: long long getLonglong(); BigInt(unsigned long long n = 0); BigInt(string &); BigInt(const char *); BigInt(BigInt &); friend void divide_by_2(BigInt &a); friend bool Null(const BigInt &); friend int Length(const BigInt &); int operator[](const int)const; BigInt &operator=(const BigInt &); BigInt &operator++(); BigInt operator++(int temp); BigInt &operator--(); BigInt operator--(int temp); friend BigInt &operator+=(BigInt &, const BigInt &); friend BigInt operator+(const BigInt &, const BigInt &); friend BigInt operator-(const BigInt &, const BigInt &); friend BigInt &operator-=(BigInt &, const BigInt &); friend bool operator==(const BigInt &, const BigInt &); friend bool operator!=(const BigInt &, const BigInt &); friend bool operator>(const BigInt &, const BigInt &); friend bool operator>=(const BigInt &, const BigInt &); friend bool operator<(const BigInt &, const BigInt &); friend bool operator<=(const BigInt &, const BigInt &); friend BigInt &operator*=(BigInt &, const BigInt &); friend BigInt operator*(const BigInt &, const BigInt &); friend BigInt &operator/=(BigInt &, const BigInt &); friend BigInt operator/(const BigInt &, const BigInt &); friend BigInt operator^(BigInt &, const BigInt &); friend BigInt sqrt(BigInt &a); friend ostream &operator<<(ostream &,const BigInt &); friend istream &operator>>(istream &, BigInt &); friend BigInt NthCatalan(int n); friend BigInt NthFibonacci(int n); friend BigInt Factorial(int n);};long long BigInt::getLonglong(){ long long x = 0; for (int i = digits.size()-1; i >= 0; --i) x = x*10 + digits[i]-'0'; return x;}BigInt::BigInt(unsigned long long nr){ do{ digits.push_back(nr % 10); nr /= 10; } while (nr);}BigInt::BigInt(const char *s){ digits = ""; for (int i = strlen(s) - 1; i >= 0;i--) { if(!isdigit(s[i])) throw("ERROR"); digits.push_back(s[i] - '0'); }}BigInt::BigInt(BigInt & a){ digits = a.digits;}bool Null(const BigInt& a){ if(a.digits.size() == 1 && a.digits[0] == 0) return true; return false;}int Length(const BigInt & a){ return a.digits.size();}int BigInt::operator[](const int index)const{ if(digits.size() <= index || index < 0) throw("ERROR"); return digits[index];}bool operator==(const BigInt &a, const BigInt &b){ return a.digits == b.digits;}bool operator!=(const BigInt & a,const BigInt &b){ return !(a == b);}bool operator<(const BigInt&a,const BigInt&b){ int n = Length(a), m = Length(b); if(n != m) return n < m; while(n--) if(a.digits[n] != b.digits[n]) return a.digits[n] < b.digits[n]; return false;}bool operator>(const BigInt&a,const BigInt&b){ return b < a;}bool operator>=(const BigInt&a,const BigInt&b){ return !(a < b);}bool operator<=(const BigInt&a,const BigInt&b){ return !(a > b);}BigInt &BigInt::operator=(const BigInt &a){ digits = a.digits; return *this;}BigInt &BigInt::operator++(){ int i, n = digits.size(); for (i = 0; i < n && digits[i] == 9;i++) digits[i] = 0; if(i == n) digits.push_back(1); else digits[i]++; return *this;}BigInt BigInt::operator++(int temp){ BigInt aux; aux = *this; ++(*this); return aux;}BigInt &BigInt::operator--(){ if(digits[0] == 0 && digits.size() == 1) throw("UNDERFLOW"); int i, n = digits.size(); for (i = 0; digits[i] == 0 && i < n;i++) digits[i] = 9; digits[i]--; if(n > 1 && digits[n - 1] == 0) digits.pop_back(); return *this;}BigInt BigInt::operator--(int temp){ BigInt aux; aux = *this; --(*this); return aux;}BigInt &operator+=(BigInt &a,const BigInt& b){ int t = 0, s, i; int n = Length(a), m = Length(b); if(m > n) a.digits.append(m - n, 0); n = Length(a); for (i = 0; i < n;i++){ if(i < m) s = (a.digits[i] + b.digits[i]) + t; else s = a.digits[i] + t; t = s / 10; a.digits[i] = (s % 10); } if(t) a.digits.push_back(t); return a;}BigInt operator+(const BigInt &a, const BigInt &b){ BigInt temp; temp = a; temp += b; return temp;}BigInt &operator-=(BigInt&a,const BigInt &b){ if(a < b) throw("UNDERFLOW"); int n = Length(a), m = Length(b); int i, t = 0, s; for (i = 0; i < n;i++){ if(i < m) s = a.digits[i] - b.digits[i]+ t; else s = a.digits[i]+ t; if(s < 0) s += 10, t = -1; else t = 0; a.digits[i] = s; } while(n > 1 && a.digits[n - 1] == 0) a.digits.pop_back(), n--; return a;}BigInt operator-(const BigInt& a,const BigInt&b){ BigInt temp; temp = a; temp -= b; return temp;}BigInt &operator*=(BigInt &a, const BigInt &b){ if(Null(a) || Null(b)){ a = BigInt(); return a; } int n = a.digits.size(), m = b.digits.size(); vector<int> v(n + m, 0); for (int i = 0; i < n;i++) for (int j = 0; j < m;j++){ v[i + j] += (a.digits[i] ) * (b.digits[j]); } n += m; a.digits.resize(v.size()); for (int s, i = 0, t = 0; i < n; i++) { s = t + v[i]; v[i] = s % 10; t = s / 10; a.digits[i] = v[i] ; } for (int i = n - 1; i >= 1 && !v[i];i--) a.digits.pop_back(); return a;}BigInt operator*(const BigInt&a,const BigInt&b){ BigInt temp; temp = a; temp *= b; return temp;}BigInt &operator/=(BigInt& a,const BigInt &b){ if(Null(b)) throw("Arithmetic Error: Division By 0"); if(a < b){ a = BigInt(); return a; } if(a == b){ a = BigInt(1); return a; } int i, lgcat = 0, cc; int n = Length(a), m = Length(b); vector<int> cat(n, 0); BigInt t; for (i = n - 1; t * 10 + a.digits[i] < b;i--){ t *= 10; t += a.digits[i] ; } for (; i >= 0; i--){ t = t * 10 + a.digits[i]; for (cc = 9; cc * b > t;cc--); t -= cc * b; cat[lgcat++] = cc; } a.digits.resize(cat.size()); for (i = 0; i < lgcat;i++) a.digits[i] = cat[lgcat - i - 1]; a.digits.resize(lgcat); return a;}BigInt operator/(const BigInt &a,const BigInt &b){ BigInt temp; temp = a; temp /= b; return temp;}void divide_by_2(BigInt & a){ int add = 0; for (int i = a.digits.size() - 1; i >= 0;i--){ int digit = (a.digits[i] >> 1) + add; add = ((a.digits[i] & 1) * 5); a.digits[i] = digit; } while(a.digits.size() > 1 && !a.digits.back()) a.digits.pop_back();}istream &operator>>(istream &in,BigInt&a){ string s; in >> s; int n = s.size(); for (int i = n - 1; i >= 0;i--){ if(!isdigit(s[i])) throw("INVALID NUMBER"); a.digits[n - i - 1] = s[i]; } return in;}ostream &operator<<(ostream &out,const BigInt &a){ for (int i = a.digits.size() - 1; i >= 0;i--) cout << (short)a.digits[i]; return cout;} ^ veverite.cpp: In function 'BigInt& operator/=(BigInt&, const BigInt&)': veverite.cpp:2:5097: warning: unused variable 'm' [-Wunused-variable] using namespace std;class BigInt{ string digits;public: long long getLonglong(); BigInt(unsigned long long n = 0); BigInt(string &); BigInt(const char *); BigInt(BigInt &); friend void divide_by_2(BigInt &a); friend bool Null(const BigInt &); friend int Length(const BigInt &); int operator[](const int)const; BigInt &operator=(const BigInt &); BigInt &operator++(); BigInt operator++(int temp); BigInt &operator--(); BigInt operator--(int temp); friend BigInt &operator+=(BigInt &, const BigInt &); friend BigInt operator+(const BigInt &, const BigInt &); friend BigInt operator-(const BigInt &, const BigInt &); friend BigInt &operator-=(BigInt &, const BigInt &); friend bool operator==(const BigInt &, const BigInt &); friend bool operator!=(const BigInt &, const BigInt &); friend bool operator>(const BigInt &, const BigInt &); friend bool operator>=(const BigInt &, const BigInt &); friend bool operator<(const BigInt &, const BigInt &); friend bool operator<=(const BigInt &, const BigInt &); friend BigInt &operator*=(BigInt &, const BigInt &); friend BigInt operator*(const BigInt &, const BigInt &); friend BigInt &operator/=(BigInt &, const BigInt &); friend BigInt operator/(const BigInt &, const BigInt &); friend BigInt operator^(BigInt &, const BigInt &); friend BigInt sqrt(BigInt &a); friend ostream &operator<<(ostream &,const BigInt &); friend istream &operator>>(istream &, BigInt &); friend BigInt NthCatalan(int n); friend BigInt NthFibonacci(int n); friend BigInt Factorial(int n);};long long BigInt::getLonglong(){ long long x = 0; for (int i = digits.size()-1; i >= 0; --i) x = x*10 + digits[i]-'0'; return x;}BigInt::BigInt(unsigned long long nr){ do{ digits.push_back(nr % 10); nr /= 10; } while (nr);}BigInt::BigInt(const char *s){ digits = ""; for (int i = strlen(s) - 1; i >= 0;i--) { if(!isdigit(s[i])) throw("ERROR"); digits.push_back(s[i] - '0'); }}BigInt::BigInt(BigInt & a){ digits = a.digits;}bool Null(const BigInt& a){ if(a.digits.size() == 1 && a.digits[0] == 0) return true; return false;}int Length(const BigInt & a){ return a.digits.size();}int BigInt::operator[](const int index)const{ if(digits.size() <= index || index < 0) throw("ERROR"); return digits[index];}bool operator==(const BigInt &a, const BigInt &b){ return a.digits == b.digits;}bool operator!=(const BigInt & a,const BigInt &b){ return !(a == b);}bool operator<(const BigInt&a,const BigInt&b){ int n = Length(a), m = Length(b); if(n != m) return n < m; while(n--) if(a.digits[n] != b.digits[n]) return a.digits[n] < b.digits[n]; return false;}bool operator>(const BigInt&a,const BigInt&b){ return b < a;}bool operator>=(const BigInt&a,const BigInt&b){ return !(a < b);}bool operator<=(const BigInt&a,const BigInt&b){ return !(a > b);}BigInt &BigInt::operator=(const BigInt &a){ digits = a.digits; return *this;}BigInt &BigInt::operator++(){ int i, n = digits.size(); for (i = 0; i < n && digits[i] == 9;i++) digits[i] = 0; if(i == n) digits.push_back(1); else digits[i]++; return *this;}BigInt BigInt::operator++(int temp){ BigInt aux; aux = *this; ++(*this); return aux;}BigInt &BigInt::operator--(){ if(digits[0] == 0 && digits.size() == 1) throw("UNDERFLOW"); int i, n = digits.size(); for (i = 0; digits[i] == 0 && i < n;i++) digits[i] = 9; digits[i]--; if(n > 1 && digits[n - 1] == 0) digits.pop_back(); return *this;}BigInt BigInt::operator--(int temp){ BigInt aux; aux = *this; --(*this); return aux;}BigInt &operator+=(BigInt &a,const BigInt& b){ int t = 0, s, i; int n = Length(a), m = Length(b); if(m > n) a.digits.append(m - n, 0); n = Length(a); for (i = 0; i < n;i++){ if(i < m) s = (a.digits[i] + b.digits[i]) + t; else s = a.digits[i] + t; t = s / 10; a.digits[i] = (s % 10); } if(t) a.digits.push_back(t); return a;}BigInt operator+(const BigInt &a, const BigInt &b){ BigInt temp; temp = a; temp += b; return temp;}BigInt &operator-=(BigInt&a,const BigInt &b){ if(a < b) throw("UNDERFLOW"); int n = Length(a), m = Length(b); int i, t = 0, s; for (i = 0; i < n;i++){ if(i < m) s = a.digits[i] - b.digits[i]+ t; else s = a.digits[i]+ t; if(s < 0) s += 10, t = -1; else t = 0; a.digits[i] = s; } while(n > 1 && a.digits[n - 1] == 0) a.digits.pop_back(), n--; return a;}BigInt operator-(const BigInt& a,const BigInt&b){ BigInt temp; temp = a; temp -= b; return temp;}BigInt &operator*=(BigInt &a, const BigInt &b){ if(Null(a) || Null(b)){ a = BigInt(); return a; } int n = a.digits.size(), m = b.digits.size(); vector<int> v(n + m, 0); for (int i = 0; i < n;i++) for (int j = 0; j < m;j++){ v[i + j] += (a.digits[i] ) * (b.digits[j]); } n += m; a.digits.resize(v.size()); for (int s, i = 0, t = 0; i < n; i++) { s = t + v[i]; v[i] = s % 10; t = s / 10; a.digits[i] = v[i] ; } for (int i = n - 1; i >= 1 && !v[i];i--) a.digits.pop_back(); return a;}BigInt operator*(const BigInt&a,const BigInt&b){ BigInt temp; temp = a; temp *= b; return temp;}BigInt &operator/=(BigInt& a,const BigInt &b){ if(Null(b)) throw("Arithmetic Error: Division By 0"); if(a < b){ a = BigInt(); return a; } if(a == b){ a = BigInt(1); return a; } int i, lgcat = 0, cc; int n = Length(a), m = Length(b); vector<int> cat(n, 0); BigInt t; for (i = n - 1; t * 10 + a.digits[i] < b;i--){ t *= 10; t += a.digits[i] ; } for (; i >= 0; i--){ t = t * 10 + a.digits[i]; for (cc = 9; cc * b > t;cc--); t -= cc * b; cat[lgcat++] = cc; } a.digits.resize(cat.size()); for (i = 0; i < lgcat;i++) a.digits[i] = cat[lgcat - i - 1]; a.digits.resize(lgcat); return a;}BigInt operator/(const BigInt &a,const BigInt &b){ BigInt temp; temp = a; temp /= b; return temp;}void divide_by_2(BigInt & a){ int add = 0; for (int i = a.digits.size() - 1; i >= 0;i--){ int digit = (a.digits[i] >> 1) + add; add = ((a.digits[i] & 1) * 5); a.digits[i] = digit; } while(a.digits.size() > 1 && !a.digits.back()) a.digits.pop_back();}istream &operator>>(istream &in,BigInt&a){ string s; in >> s; int n = s.size(); for (int i = n - 1; i >= 0;i--){ if(!isdigit(s[i])) throw("INVALID NUMBER"); a.digits[n - i - 1] = s[i]; } return in;}ostream &operator<<(ostream &out,const BigInt &a){ for (int i = a.digits.size() - 1; i >= 0;i--) cout << (short)a.digits[i]; return cout;} ^ veverite.cpp: In function 'int main()': veverite.cpp:13:2481: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] int DIR[NUM_DIRECTIONS][2] = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };bool visited[MAX_N + 2][MAX_N + 2];char num_freedoms[MAX_N + 1][MAX_N + 1];BigInt sol[MAX_SOLUTIONS + 1], current_sol;int size, target_depth, center, num_solutions;inline void process_solution(int row, int col) { sol[++num_solutions] = current_sol;}inline void set_cell(int row, int col, bool val) { visited[row][col] = val; int delta = 1 - 2 * val; num_freedoms[row][col - 1] += delta; num_freedoms[row][col + 1] += delta; num_freedoms[row - 1][col] += delta; num_freedoms[row + 1][col] += delta;}inline void set_both_cells(int row, int col, bool val) { set_cell(row, col, val); set_cell(size - row + 1, size - col + 1, val);}void compute_freedoms() { for (int row = 1; row <= size; row++) { for (int col = 1; col <= size; col++) { num_freedoms[row][col] = !visited[row - 1][col] + !visited[row + 1][col] + !visited[row][col - 1] + !visited[row][col + 1]; } }}void prepare_matrices() { target_depth = (size * size - 1) / 2; center = (size + 1) / 2; for (int i = 1; i <= size; i++) { visited[i][0] = visited[i][size + 1] = true; visited[0][i] = visited[size + 1][i] = true; } set_both_cells(1, 1, true); compute_freedoms();}inline int get_forced_dir(int row, int col) { for (int dir = 0; dir < NUM_DIRECTIONS; dir++) { int r = row + DIR[dir][0]; int c = col + DIR[dir][1]; if (!visited[r][c] && (num_freedoms[r][c] == 1)) { return dir; } } return NONE;}inline void push_bits(int val) { current_sol = (current_sol * (1LL << BIT_WIDTH)) + val;}inline void pop_bits() { current_sol = current_sol / (1LL << BIT_WIDTH);}void backtrack(int depth, int row, int col) { if (depth == target_depth) { process_solution(row, col); return; } if ((row == center) && (col == center)) { return; } int start = 0, end = NUM_DIRECTIONS - 1; int forced_dir = get_forced_dir(row, col); if (forced_dir != NONE) { start = end = forced_dir; } for (int dir = start; dir <= end; dir++) { int r = row + DIR[dir][0]; int c = col + DIR[dir][1]; if (!visited[r][c]) { push_bits(dir); set_both_cells(r, c, true); backtrack(depth + 1, r, c); set_both_cells(r, c, false); pop_bits(); } }}void print_solution(int pos, FILE* f) { for (int d = target_depth - 1; d >= 0; d--) { int val = (sol[pos] / (1LL << (BIT_WIDTH * d))).getLonglong() & BIT_MASK; fputc('0' + val, f); } fputc('\n', f);}int main() { int num_queries; FILE* fin = fopen("veverite.in", "r"); FILE* fout = fopen("veverite.out", "w"); fscanf(fin, "%d %d", &size, &num_queries); prepare_matrices(); backtrack(0, 1, 1); while (num_queries--) { int pos; fscanf(fin, "%d", &pos); print_solution(pos, fout); } fclose(fin); fclose(fout); return 0;} ^ veverite.cpp:13:2579: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] int DIR[NUM_DIRECTIONS][2] = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };bool visited[MAX_N + 2][MAX_N + 2];char num_freedoms[MAX_N + 1][MAX_N + 1];BigInt sol[MAX_SOLUTIONS + 1], current_sol;int size, target_depth, center, num_solutions;inline void process_solution(int row, int col) { sol[++num_solutions] = current_sol;}inline void set_cell(int row, int col, bool val) { visited[row][col] = val; int delta = 1 - 2 * val; num_freedoms[row][col - 1] += delta; num_freedoms[row][col + 1] += delta; num_freedoms[row - 1][col] += delta; num_freedoms[row + 1][col] += delta;}inline void set_both_cells(int row, int col, bool val) { set_cell(row, col, val); set_cell(size - row + 1, size - col + 1, val);}void compute_freedoms() { for (int row = 1; row <= size; row++) { for (int col = 1; col <= size; col++) { num_freedoms[row][col] = !visited[row - 1][col] + !visited[row + 1][col] + !visited[row][col - 1] + !visited[row][col + 1]; } }}void prepare_matrices() { target_depth = (size * size - 1) / 2; center = (size + 1) / 2; for (int i = 1; i <= size; i++) { visited[i][0] = visited[i][size + 1] = true; visited[0][i] = visited[size + 1][i] = true; } set_both_cells(1, 1, true); compute_freedoms();}inline int get_forced_dir(int row, int col) { for (int dir = 0; dir < NUM_DIRECTIONS; dir++) { int r = row + DIR[dir][0]; int c = col + DIR[dir][1]; if (!visited[r][c] && (num_freedoms[r][c] == 1)) { return dir; } } return NONE;}inline void push_bits(int val) { current_sol = (current_sol * (1LL << BIT_WIDTH)) + val;}inline void pop_bits() { current_sol = current_sol / (1LL << BIT_WIDTH);}void backtrack(int depth, int row, int col) { if (depth == target_depth) { process_solution(row, col); return; } if ((row == center) && (col == center)) { return; } int start = 0, end = NUM_DIRECTIONS - 1; int forced_dir = get_forced_dir(row, col); if (forced_dir != NONE) { start = end = forced_dir; } for (int dir = start; dir <= end; dir++) { int r = row + DIR[dir][0]; int c = col + DIR[dir][1]; if (!visited[r][c]) { push_bits(dir); set_both_cells(r, c, true); backtrack(depth + 1, r, c); set_both_cells(r, c, false); pop_bits(); } }}void print_solution(int pos, FILE* f) { for (int d = target_depth - 1; d >= 0; d--) { int val = (sol[pos] / (1LL << (BIT_WIDTH * d))).getLonglong() & BIT_MASK; fputc('0' + val, f); } fputc('\n', f);}int main() { int num_queries; FILE* fin = fopen("veverite.in", "r"); FILE* fout = fopen("veverite.out", "w"); fscanf(fin, "%d %d", &size, &num_queries); prepare_matrices(); backtrack(0, 1, 1); while (num_queries--) { int pos; fscanf(fin, "%d", &pos); print_solution(pos, fout); } fclose(fin); fclose(fout); return 0;} ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
1 | 0.008 secunde | OK. | 2 | 2 | ||
2 | 0.032 secunde | OK. | 2 | 2 | ||
3 | 0.012 secunde | OK. | 2 | 2 | ||
4 | 0.028 secunde | OK. | 2 | 2 | ||
5 | 0.192 secunde | OK. | 3 | 3 | ||
6 | Depășit | Limita de timp depășită | 4 | 0 | ||
7 | Depășit | Limita de timp depășită | 4 | 0 | ||
8 | Depășit | Limita de timp depășită | 4 | 0 | ||
9 | Depășit | Limita de timp depășită | 4 | 0 | ||
10 | Depășit | Limita de timp depășită | 5 | 0 | ||
11 | Depășit | Limita de timp depășită | 9 | 0 | ||
12 | Depășit | Limita de timp depășită | 10 | 0 | ||
13 | Depășit | Limita de timp depășită | 7 | 0 | ||
14 | Depășit | Limita de timp depășită | 7 | 0 | ||
15 | Depășit | Limita de timp depășită | 7 | 0 | ||
16 | Depășit | Limita de timp depășită | 9 | 0 | ||
17 | Depășit | Limita de timp depășită | 9 | 0 | ||
18 | Depășit | Limita de timp depășită | 10 | 0 | ||
Punctaj total | 11 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema veverite face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.