# **Editorial of Thi Thử Tỉnh 2**
###### tags: `ITNTP`
> Không AC thì mọi lý luận đều là nhảm nhí
> [name=LamTer triết lý]
> Bí quá thì mới đọc phần dưới, không thì quay lại mà ngẫm nghĩ
> [name=Bảo]
# https://itntp.contest.codeforces.com/group/TODoi5LDTj/contest/367604
# A. Tam giác vuông
Vì bài này có chứa các điểm có tọa độ âm nên ta không thể dùng array / vector được
(khi dùng thì phải đẩy tọa độ thêm 10^9 đơn vị, gây rắc rối)

Như vậy ta sẽ dùng 1 kiểu dữ liệu gọi là map.
Nếu mọi người chưa biết map là gì thì có tài liệu cho mọi người tham khảo.
- https://www.cplusplus.com/reference/map/map/

Ta chứng minh được rằng **với 3 điểm A, B, C bất kỳ trên mặt phẳng tọa độ Oxy**, nếu A.x = B.x và A.y = C.y thì tam giác ABC vuông tại A thỏa mãn đề bài.

Như vậy mình cần tìm 1 điểm A(B.x, C.y), chạy 2 vòng lặp. Có điều độ phức tạp là O($N^2$). Do đó, cách này không sử dụng được.
Làm sao cho O($N$) hoặc O($N log N$).

Vì tọa độ của các điểm **là số nguyên** nên ta làm như sau: Đếm số lần các giá trị hoành độ (x) và tung độ (y) xuất hiện ở các điểm đã cho. (2 map mx, my)
**Ví dụ:**

3
0 0
1 0
1 1

Ta có hoành độ 0 xuất hiện 1 lần, hoành độ 1 xuất hiện 2 lần, tung độ 0 xuất hiện 2 lần, tung độ 1 xuất hiện 1 lần.

Tiếp theo, ans <- 0
for i: 1 -> n ans += (số lần x[i] - 1) * (số lần y[i] - 1);

**Vì sao ?**
Có y điểm cùng nằm trên cùng 1 tung độ -> Tạo ra y - 1 đường thẳng có chung đầu mút A
Có x điểm cùng nằm trên cùng 1 hoành độ -> Tạo ra x - 1 đường thẳng có chung đầu mút A -> (x + 1) * (y + 1) tam giác.

Độ phức tạp: O($N log N$)
**Giá trị ban đầu của 1 key trong map luôn luôn bằng 0 hoặc "" nên cứ làm như dùng vector**
**Solution:** https://ideone.com/cB55bS (Gia Bảo)
# B. A cộng B
Bài này A, B nguyên dương <= 10 ^ 2000 nên ta chỉ có thể dùng string rồi tính từ chữ số nhỏ nhất lên hoặc ép vào kiểu bignum (sử dụng vector).
*<-> Chú ý là trong test của anh Lâm thì chữ số đầu tiên có thể là 0 nên phải loại bỏ nó đi đến khi nào nó không phải. Rồi tính thêm trường hợp a = "0" hoặc b = "0"*
**Solution:**
- Dùng string (Gia Bảo): https://ideone.com/5hZeZu
- Ép vào vector (Gia Bảo): https://ideone.com/wiuOeN
- BigNum: Trên mạng đầy
# C. Xếp gạch
Bài này hay nhưng cũng đơn giản nếu nhìn ra.
Để làm được bài này ta cần xây dựng trật tự để hiểu rõ thuật toán.
Vì diện tích là 2 * n nên **chỉ có 2 cách bố trí:** xếp gạch nằm ngang và nằm dọc.

a 
a 

Lúc này, aa có 3 cách chọn màu nên số cách sẽ là 3.
Tiếp theo, ta cho thêm 2 cục gạch nằm ngang trên 2 dòng.

abb
acc

Khi đó, bb và cc đều có 2 cách chọn (để không trùng với màu của aa -> số cách là 3 * 2 = 6. Ta cho thêm 2 cục gạch nằm ngang nữa.

abbdd
accee

Khi đó, dd và ee có 3 cách chọn màu, đầu tiên là bb -> ee, cc -> dd. Thứ hai là bb nhận màu 1, cc nhận màu 2 thì dd nhận màu 3, ee nhận màu 1 và ngược lại -> số cách là 6 * 3 = 18.
Giờ ta cho lại 1 cục nằm dọc.

abbddf
acceef

Khi đó, ff nằm cạnh dd, ee nên ff chỉ có 1 cách chọn -> số cách là 18. Giờ ta cho thêm 1 cục gạch nằm dọc nữa.

abbddfg
acceefg

Thì gg có 2 cách chọn màu -> số cách là 18 * 2 = 36.
Rồi ta phân tích các hình khác như trường hợp trên.
Ngoài ra còn có trường hợp bắt đầu bằng 2 viên gạch nằm ngang thì số cách ban đầu là 6.

aa
bb

**Ý tưởng của bài này:**
<pre>
Nếu n = 1 thì chắc chắn đáp án = 3
Nếu n > 1:
ans = 1
Nếu a[1] = a[2] thì ans = 6, i = 3;
Ngược lại thì ans = 3, i = 2;
Chạy từ i đến n:
Nếu mà a[i] == a[i + 1] thì chia ra 2 trường hợp:
a[i - 1] == b[i - 1] thì ans *= 2
còn không thì ans *= 3
i++
Ngược lại nếu mà a[i - 1] == b[i - 1] thì ans *= 2
In ra ans
</pre>
**Solution:** https://ideone.com/fPLhwp (Gia Bảo)
# D.Dãy nhị phân
Bài này cũng có không có gì đặc biệt, chỉ là để kiểm tra kiến thức của mọi người về đệ quy quay lui.
Ai chưa làm được thì đọc lại kiến thức trước khi đọc solution.
**Solution:** https://ideone.com/11NNUW
> Đừng ngại ngùng chia sẻ cho mọi người kiến thức mới nhưng cũng phải giữ lấy 1 chút cho riêng mình.
> [name=Bảo]