Bài tập tuần 1 của Hưng cùi bắp

Tình hình là Hưng có gửi các bạn 3 bài tập (download tại đây: [You must be registered and logged in to see this link.] ). Hôm nay mình sẽ giải 3 bài này (theo yêu cầu của bạn Hồng Hoa Razz

)

Bài 1:
Thuật toán: Bài này các bạn không thể viết xâu ra vì làm vậy sẽ ko thể chứa hết các số với trường hợp n = 2^32 - 1. Ta sẽ có 1 nhận xét đơn giản như sau, ta có xâu s:
s = 110100100010000100000 với các vị trí có giá trị bằng 1 lần lượt là:
0 1 3 6 10 15 21
tương ứng với:
0 = 0
1 = 0 + 1
3 = 0 + 1 + 2
6 = 0 + 1 + 2 + 3
v.v...
Tới đây mình nghĩ các bạn cũng đã nghĩ ra thuật toán rùi

Source:

Code:: int main(){
//freopen ("INP.txt", "r", stdin);
int n;
SC(n);
for (int i = 1; n >= i; i++) n -= i;
if (n == 0) PRS("1");
else PRS("0");
}

Bài 2: bài này bạn thenguyen27192 đã code bằng java tại [You must be registered and logged in to see this link.] các bạn có thể tham khảo.

Bài 3: Đây là bài xử lí số lớn có rất nhiều ứng dụng sau này.

Thuật toán:
Cộng 2 số lớn: tất nhiên là chúng ta không thể cộng thông thường được rùi vì số A và B có đến 10000 chữ số trong khi long long trong C/C++ chỉ hổ trợ đến 18 chữ số nên chúng ta sẽ có 1 thuật toán như sau:

VD ta muốn cộng 2 số sau đây:
9283475923845
192834921348

ta sẽ chia 2 số trên ra thành các nhóm 3 số:
9 283 475 923 845
192 834 921 348

sau đó sẽ cộng lần lượt các nhóm 3 số đó lại kết quả sẽ là:
9 476 310 845 193

Source: (đây là bài cải tiến mới nhất của mình, có lẽ các bạn đọc ko hiểu vì mình dùng các kĩ thuật lập trình mới nhất ở trong code này, nhưng ý tưởng vẫn không có gì thay đổi)

Code:: #define e 1000

vi a, b, cong, tru, nhan;
string s1, s2;

void Xuli(string s, vi &A){
string m;
while (s.size() % 3) s = "0" + s;
int j = s.size() - 1;
while (j >= 0){
   m = "";
   m = m + s[j - 2] + s[j - 1] + s[j];
   j -= 3;
   A.PB(toInt(m));
}
}

string Exchange(vi C){
string ds, s;
ds = "";
FORN (i, 0, C.size()){
   s = toString(C[i]);
   while (s.size() % 3) s = "0" + s;
   ds = s + ds;
}
while (ds.size() > 1 && ds[0] == '0') ds.erase(0, 1);
return ds;
}

string Plus(vi A, vi B){
int du = 0;
FORN (i, 0, A.size()){
   du += A[i] + B[i];
   cong.PB(du % e);
   du /= e;
}
if (du > 0) cong.PB(du);
return Exchange(cong);
}

string Subtract(vi A, vi B){
int du = 0;
bool smaller = false;
if (s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2)){
   smaller = true;
   swap(A, B);
}
FORN (i, 0, A.size()){
   A[i] -= du;
   if (A[i] < B[i]) A[i] += e, du = 1;
   else du = 0;
   tru.PB(A[i] - B[i]);
}
string kq = Exchange(tru);
if (smaller) kq = "-" + kq;
return kq;
}

string Multi(vi A, vi B){
int du = 0;
int T[2005];
RESET(T, 0);
FORN (i, 0, A.size())
   FORN (j, 0, B.size())
      T[i + j] += A[i] * B[j];
FORN (i, 0, A.size() + B.size()){
   du = T[i] + du;
   nhan.PB(du % e);
   du /= e;
}
if (du) nhan.PB(du);
return Exchange(nhan);
}

int main(){
//freopen ("INP.txt", "r", stdin);
cin >> s1 >> s2;
Xuli(s1, a);
Xuli(s2, b);
while (a.size() < b.size()) a.PB(0);
while (a.size() > b.size()) b.PB(0);
cout << Plus(a, b) << endl;
cout << Subtract(a, b) << endl;
cout << Multi(a, b) << endl;
}