JOI春合宿 2010-day2 aplusb
問題文 : 足し算
解法 :
vectorを使って実際に足し算を行う.
繰り上がり/桁数が変わる位置のみに微妙な変化があり, 間の数の計算は省くことができる.
コード :
#include <cstdio> #include <climits> #include <vector> #include <algorithm> using namespace std; typedef long long lint; typedef pair<int, lint> P; int main() { int m1, m2; int idx1 = 0, idx2 = 0; vector<P> n1, n2; vector<P> ret; n1.push_back(P(0, LLONG_MAX)); n2.push_back(P(0, LLONG_MAX)); scanf("%d", &m1); for (int i = 0; i < m1; i++){ int a, b; scanf("%d %d", &a, &b); n1.push_back(P(a, b)); } scanf("%d", &m2); for (int i = 0; i < m2; i++){ int a, b; scanf("%d %d", &a, &b); n2.push_back(P(a, b)); } reverse(n1.begin(), n1.end()); reverse(n2.begin(), n2.end()); int carry = 0; while (1){ if (n1[idx1].second == 0) idx1++; if (n2[idx2].second == 0) idx2++; if (n1[idx1].second > 100000000 && n2[idx2].second > 100000000) break; int ns = min(n1[idx1].second, n2[idx2].second); n1[idx1].second -= ns; n2[idx2].second -= ns; if (n1[idx1].first + n2[idx2].first + carry < 10){ ret.push_back(P(n1[idx1].first + n2[idx2].first + carry, 1)); if (ns - 1) ret.push_back(P(n1[idx1].first + n2[idx2].first, ns - 1)); carry = 0; } else { ret.push_back(P((n1[idx1].first + n2[idx2].first + carry) % 10, 1)); if (ns - 1) ret.push_back(P((n1[idx1].first + n2[idx2].first + 1) % 10, ns - 1)); carry = 1; } } if (carry == 1) ret.push_back(P(1, 1)); reverse(ret.begin(), ret.end()); int size = 0; for (int i = 0; i < ret.size();){ size++; int j = i + 1; while (j != ret.size() && ret[i].first == ret[j].first){ ret[i].second += ret[j].second; ret[j].second = 0; j++; } i = j; } printf("%d\n", size); for (int i = 0; i < ret.size(); i++){ if (ret[i].second) printf("%d %lld\n", ret[i].first, ret[i].second); } return (0); }