diff options
| -rw-r--r-- | pascal.cpp | 13 | ||||
| -rw-r--r-- | pattern.cpp | 83 | ||||
| -rw-r--r-- | square.cpp | 5 |
3 files changed, 50 insertions, 51 deletions
@@ -11,14 +11,14 @@ int main() { int N; cin >> N; - if (N <= 31) { - // if N <= 31 then just use naïve method + if (N <= 30) { + // if N <= 30 then just use naïve method for (int i = 0; i < N; ++i) cout << i + 1 << " " << 1 << '\n'; } else { - // first we try to make N - 31 - int sum = 0, side = 0, goal = N - 31; - for (int i = 0; i < 31; ++i) { + // first we try to make N - 30 + int sum = 0, side = 0, goal = N - 30; + for (int i = 0; i < 30; ++i) { cout << i + 1 << " " << (side ? i + 1 : 1) << '\n'; // each row sums to 2 ^ (i + 1) @@ -32,7 +32,8 @@ int main() { else ++sum; } - for (int i = 31; sum < N; ++i, ++sum) cout << i + 1 << ' ' << (side ? i + 1 : 1) << '\n'; + // we've undershot so we still need to walk down until our sum is N + for (int i = 30; sum < N; ++i, ++sum) cout << i + 1 << ' ' << (side ? i + 1 : 1) << '\n'; } } }
\ No newline at end of file diff --git a/pattern.cpp b/pattern.cpp index c8f4403..aceee5f 100644 --- a/pattern.cpp +++ b/pattern.cpp @@ -2,49 +2,48 @@ using namespace std; int main() { - if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); + if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); - int T; - cin >> T; - for (int t = 1; t <= T; ++t) { - cout << "Case #" << t << ": "; - - int N; - cin >> N; - string P[55]; - for (int i = 0; i < N; ++i) cin >> P[i]; - - string l, m, r; // left, middle, end parts of final answer - bool ans = 1; // flag so we can quickly break when no solution exists - for (int i = 0; i < N && ans; ++i) { - // tokenize string - vector<string> parts; - parts.push_back(""); - for (auto& c : P[i]) { - if (c == '*') parts.push_back(""); // add new string - else parts.back() += c; // add c to current string - } - - string& s = parts.front(); // leftmost part - for (int j = 0; j < s.size() && ans; ++j) { - if (j >= l.size()) l.push_back(s[j]); // extend l - else if (s[j] != l[j]) ans = 0; // s doesn't match with current l - } - - s = parts.back(); // rightmost part - reverse(s.begin(), s.end()); - for (int j = 0; j < s.size() && ans; ++j) { - if (j >= r.size()) r.push_back(s[j]); // extend r - else if (s[j] != r[j]) ans = 0; // s doesn't match with current r - } - - // add other parts to the middle string - for (int j = 1; j < parts.size() - 1 && ans; ++j) m += parts[j]; - } + int T; + cin >> T; + for (int t = 1; t <= T; ++t) { + cout << "Case #" << t << ": "; + + int N; + cin >> N; + string P[55]; // patterns + for (int i = 0; i < N; ++i) cin >> P[i]; - reverse(r.begin(), r.end()); - + string l, m, r; // left, middle, end parts of final answer + bool ans = 1; // flag so we can quickly break when no solution exists + for (int i = 0; i < N && ans; ++i) { + // tokenize string + vector<string> parts; + parts.push_back(""); + for (auto& c : P[i]) { + if (c == '*') parts.push_back(""); // add new string + else parts.back() += c; // add c to current string + } + + string& s = parts.front(); // leftmost part + for (int j = 0; j < s.size() && ans; ++j) { + if (j >= l.size()) l.push_back(s[j]); // extend l + else if (s[j] != l[j]) ans = 0; // s doesn't match with current l + } + + s = parts.back(); // rightmost part + reverse(s.begin(), s.end()); + for (int j = 0; j < s.size() && ans; ++j) { + if (j >= r.size()) r.push_back(s[j]); // extend r + else if (s[j] != r[j]) ans = 0; // s doesn't match with current r + } + + // add other parts to the middle string + for (int j = 1; j < parts.size() - 1 && ans; ++j) m += parts[j]; + } + // Creates at most ≈5000 < 10000 characters - cout << (ans ? l + m + r : "*") << '\n'; - } + reverse(r.begin(), r.end()); + cout << (ans ? l + m + r : "*") << '\n'; + } }
\ No newline at end of file @@ -8,7 +8,7 @@ typedef long long ll; constexpr int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 }; int S[100001]; // skill levels -vector<int> neighbor[100001]; // vector of neighbors for each competitor +int neighbor[100001][4]; // array of neighbors for each competitor int main() { if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); @@ -19,7 +19,7 @@ int main() { int R, C; cin >> R >> C; ll ans = 0, sum = 0; - vector<int> check; // set of candidate competitors to check + vector<int> check; // vector of candidate competitors to check for (int i = 0; i < R; ++i) { for (int j = 0; j < C; ++j) { cin >> S[i * C + j]; sum += S[i * C + j]; @@ -35,7 +35,6 @@ int main() { // precompute neighbors for (int i = 0; i < R; ++i) { for (int j = 0; j < C; ++j) { - neighbor[i * C + j].resize(4); for (int d = 0; d < 4; ++d) { int x = i + dx[d], y = j + dy[d]; // get neighbor neighbor[i * C + j][d] = valid(x, y) ? x * C + y : -1; |