<center><h1> HAINAMLION's Ultimate STAR Challenges Catalogue (SES0) </h1></center> ## R0P1 - Hundred Codes 1 Month Challenge **Yêu cầu:** - Link bài - Chụp ảnh AC - Tóm tắt, ghi tag đề - Hướng giải bài, ghi ví dụ, trực quan - Code AC --- <center><h3> Progress: 40/100 </h3></center> --- <!-- :::::spoiler Templete ::::info **Link:** []() **ELO:** **Tags:** :::: ::::warning **Tóm tắt:** - **Ví dụ:** | Input | Output | | ----- | ------ | | | | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= //Code here ``` ::: :::: ::::success > Personal Comment: (image) :::: ::::: --> ### Section A (Codeforces) :::::spoiler Codeforces 1A - Theatre Square ::::info **Link:** [1A_CF](https://codeforces.com/contest/1/problem/A) **ELO:** 1000 **Tags:** math :::: ::::warning **Tóm tắt:** - Có một quãng trường hình chữ nhật có kích thước *n x m* - Lát kín hình chữ nhật bằng phiến đá hình vuông có kích thước *a x a* - Câu hỏi: Cần **ít nhất** bao nhiêu phiến đá để lát đầy hình chữ nhật? - Các quy tắc: - Diện tích bề mặt lát được phép **lớn hơn** diện tích quãng trường. - **Không** được làm vỡ phiến đá. - Các cạnh của phiến đá **song song** với các cạnh của quãng trường. **Ví dụ:** | Input | Output | | ----- | ------ | | 6 6 4 | 4 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { long long n, m, a; // Long long để handle số lớn cin >> n >> m >> a; // Nhập vào n, m, a // Tính số phiến đá mỗi chiều dài n long long flagstones_n = (n + a - 1) / a; // Phép chia số nguyên làm tròn lên // Tính số phiến đá mỗi chiều rộng m long long flagstones_m = (m + a - 1) / a; cout << flagstones_n * flagstones_m << endl; // In ra số phiến đá return 0; } ``` ::: :::: ::::success > Personal Comment: First Problem in Codeforces? Peak. ![image](https://hackmd.io/_uploads/r1MQrC9Ngg.png) :::: ::::: :::::spoiler Codeforces 2A - Winner ::::info **Link:** [2A_CF](https://codeforces.com/contest/2/problem/A) **ELO:** 1500 **Tags:** hashing, implementation :::: ::::warning **Tóm tắt:** - Có *n* lượt chơi - Mỗi lượt chơi có người chơi với thông tin là *tên (name)* và *số điểm (score)* trong lượt. - Xem ai có điểm chơi **cao nhất** thì người đó là người chiến thắng. - Nếu **nhiều người** có chung một điểm cao nhất, ai đạt được **trước** thì là người chiến thắng. **Ví dụ:** | Input | Output | | ----------------------------------- | ------ | | 3<br>mike 3<br>andrew 5<br>mike 2 | andrew | | 3<br>andrew 3<br>andrew 2<br>mike 5 | andrew | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <vector> #include <algorithm> #include <string> #include <unordered_map> #include <unordered_set> using namespace std; // Nhóm tên và điểm trong lượt lại thành "PlayerRound" cho tiện, vì mỗi lượt đều có tên và điểm trong lượt struct PlayerRound { string name; int score_change; }; int main() { int n; cin >> n; // Nhập vào n lượt chơi vector<PlayerRound> rounds(n); // Lưu kết quả từng lượt chơi unordered_map<string, int> finalScores; // Lưu điểm cuối cùng của mỗi người for (int i = 0; i < n; i++) { cin >> rounds[i].name >> rounds[i].score_change; // Nhập vào lượt chơi finalScores[rounds[i].name] += rounds[i].score_change; // Cộng trừ vào tổng điểm của người chơi } int highscore = -2e9; // Ban đầu chưa xác định điểm cao nhất nên đặt biến là một số siêu nhỏ for (auto [name, score] : finalScores) { // Duyệt qua các điểm và xem cái nào cao nhất highscore = max(highscore, score); } unordered_set<string> winners; // Lưu tên (những) người chơi có điểm cao nhất for (auto [name, score] : finalScores) { if (score == highscore) { // Nếu số điểm của người chơi bằng số điểm cao nhất winners.insert(name); // Thêm tên người chơi vào } } if (winners.size() == 1) { // Nếu chỉ có 1 người có điểm cao nhất cout << *winners.begin() << endl; // In ra tên người chiến thắng return 0; } unordered_map<string, int> currentScores; // Lưu trữ điểm để tìm ai là người chiến thắng string winner = ""; for (int i = 0; i < n; i++) { // Duyệt lại các lượt chơi currentScores[rounds[i].name] += rounds[i].score_change; // Cộng trừ vào tổng điểm của người chơi if (winners.count(rounds[i].name) && currentScores[rounds[i].name] >= highscore) { // Nếu người chơi có trong danh sách những người có điểm cao nhất và điểm lớn hơn hoặc bằng điểm cao nhất winner = rounds[i].name; // Lưu tên người chiến thắng break; } } cout << winner << endl; // In ra tên người chiến thắng return 0; } ``` ::: :::: ::::success > Personal Comment: This was real hard. ![image](https://hackmd.io/_uploads/HkzXFssVll.png) :::: ::::: :::::spoiler Codeforces 11A - Increasing Sequence ::::info **Link:** [11A_CF](https://codeforces.com/contest/11/problem/A) **ELO:** 900 **Tags:** constructive algorithms, implementation, math **Number requested by:** Thành Hiếu | TeddyDeDoge (TDN - A2) :::: ::::warning **Tóm tắt:** - Cho một dãy số có *n* số. - Cho một số nguyên *d* - Mỗi lần cộng *d* vào một số trong dãy số thì tính là 1 bước. - Tính xem có bao nhiêu bước để cho dãy số được sắp xếp thành từ bé đến lớn. **Ví dụ:** | Input | Output | | -------------- | ------ | | 4 2<br>1 3 3 2 | 3 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; int main() { int n = 0; long long d = 0; // Xài long long phòng trường hợp số quá lớn cin >> n >> d; // Nhập vào n và d vector<long long> b(n); // Lưu dãy số for (int i = 0; i < n; i++) cin >> b[i]; // Nhập vào từng số long long moves = 0; // Lưu số bước for (int i = 1; i < n; i++) { // Duyệt qua dãy số, i bắt đầu từ 1 vì số đầu tiên luôn là số bé nhất if (b[i] <= b[i-1]) { // Nếu số nhỏ hơn hoặc bằng số trước long long diff = b[i - 1] - b[i] + 1; // Tính khoảng cần cộng vào giữa 2 số long long times = (diff + d - 1) / d; // Tính số lần cộng vào (số bước) b[i] += times * d; // Cộng vào số đang được duyệt moves += times; // Cộng vào tổng số bước } } cout << moves << endl; // In ra số bước return 0; } ``` ::: :::: ::::success > Personal Comment: Cái chỗ duyệt lúc đầu ghi i = 0, sai 2 lần cay vaiz :v ![image](https://hackmd.io/_uploads/rybWTdTNle.png) :::: ::::: :::::spoiler Codeforces 22A - Second Order Statistics ::::info **Link:** [22A_CF](https://codeforces.com/contest/22/problem/A) **ELO:** 800 **Tags:** brute force :::: ::::warning **Tóm tắt:** - Cho *n* số nguyên, xem số bé nhì (lớn hơn số bé nhất) là số nào. - Nếu không tìm thấy số bé nhì, in ra "NO" **Ví dụ:** | Input | Output | | -------------- | ------ | | 4<br>1 2 2 -4 | 1 | | 5<br>1 2 3 1 1 | 2 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int n; cin >> n; // Nhập vào n (bao nhiêu số nguyên) vector<int> num(n); // Mảng chứa các số nguyên for (int i = 0; i < n; i++) { // Nhập vào từng số nguyên cin >> num[i]; } sort(num.begin(), num.end()); // Dùng hàm sort() để sắp xếp các phần từ trong mảng từ bé đến lớn for (int i = 0; i < n; i++) { // Duyệt qua từng số nguyên if (num[i] > num[0]) { // Nếu số đang duyệt lớn hơn số bé nhất (biết là số bé nhất vì sắp xếp rồi) cout << num[i]; // In ra số bé nhì break; // Dừng duyệt } else if (i == n - 1) { // Không tìm thấy số bé nhì cout << "NO"; // In ra "NO" break; // Dừng duyệt } } return 0; } ``` ::: :::: ::::success > Personal Comment: Đề bài bị complicated hóa :v ![image](https://hackmd.io/_uploads/SJTOJ1pVxx.png) :::: ::::: :::::spoiler Codeforces 23A - You're Given a String... ::::info **Link:** [23A_CF](https://codeforces.com/contest/23/problem/A) **ELO:** 1200 **Tags:** brute force, greedy :::: ::::warning **Tóm tắt:** - Cho một chuỗi, xem chuỗi con dài nhất nào xuất hiện ít nhất 2 lần trong chuỗi. - Các chuỗi con giống nhau có thể chồng lên nhau. - In ra độ dài chuỗi con. **Ví dụ:** | Input | Output | | ----- | ------ | | abcd | 0 | | ababa | 3 | | zzz | 2 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string s; cin >> s; // Nhập vào chuỗi int lenS = s.length(); // Lưu độ dài chuỗi int maxLenSubStr = 0; // Lưu độ dài chuỗi con dài nhất // Vòng lập i: duyệt qua từng ký tự đầu tiên của chuỗi con // Vòng lập j: duyệt qua từng ký tự đầu tiên của chuỗi đằng sau chuỗi con bắt đầu bằng i // 2 vòng lập i và j cho phép ta so sánh 2 chuỗi con riêng biệt // Vòng lập k: so sánh từng ký tự của 2 chuỗi với nhau for (int i = 0; i < lenS; i++) { for (int j = i + 1; j < lenS; j++) { int currentMatchLen = 0; // Lưu tạm thời độ dài chuỗi con trùng đang được so sánh for (int k = 0; i + k < lenS && j + k < lenS; k++) { if (s[i + k] == s[j + k]) { // Nếu 2 ký tự của 2 chuỗi con giống nhau currentMatchLen++; // Thêm 1 vào độ dài chuỗi con } else break; } maxLenSubStr = max(maxLenSubStr, currentMatchLen); // Xem độ dài chuỗi con mới có dài hơn độ dài cũ không } } cout << maxLenSubStr << endl; // In ra độ dài chuỗi con trùng lớn nhất return 0; } ``` ::: :::: ::::success > Personal Comment: Bài này phức tạp mà lại còn O(N^3), may mà AC 😁 ![image](https://hackmd.io/_uploads/HJwXQu6Exl.png) :::: ::::: :::::spoiler Codeforces 25A - IQ Test ::::info **Link:** [25A_CF](https://codeforces.com/contest/25/problem/A) **ELO:** 1300 **Tags:** brute force :::: ::::warning **Tóm tắt:** - Cho *n* số nguyên, tìm ra số lạ trong dãy số đó rồi in ra vị trí của số (theo thứ tự nhập). **Ví dụ:** | Input | Output | | --------------- | ------ | | 5<br>2 4 7 8 10 | 3 | | 4<br>1 2 1 1 | 2 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; // Nhập vào n (bao nhiêu số nguyên) int even = 0, odd = 0, lastE = 0, lastO = 0; // even lưu bao nhiêu số chẳn, odd lưu bao nhiêu số lẻ, lastE lưu vị trí của số chẳn cuối được duyệt, lastO lưu vị trí của số lẻ cuối được duyệt vector<int> num(n); // Mảng chứa các số nguyên for (int i = 0; i < n; i++) { // Nhận lần lượt vào các số cin >> num[i]; // Nhập số nguyên if (num[i] % 2 == 0) { // Nếu là số chẳn even++; // Thêm 1 vào bộ đếm số chẳn lastE = i; // Đặt lastE thành vị trí của số chẳn đó } else { // Ngược lại (nếu không phải số chẳn thì là số lẻ) odd++; // Thêm 1 vào bộ đếm số lẻ lastO = i; // Đặt lastO thành vị trí của số lẻ đó } } // Suy đoán: chỉ có 1 số lạ trong toàn bộ dãy số if (even > odd) { // Nếu số lượng số chẳn nhiều hơn số lẻ cout << lastO + 1 << endl; // In ra vị trí số lẻ cuối } else { cout << lastE + 1 << endl; // In ra vị trí số chẳn cuối } // (+ 1 vì khi in ra phải in theo hệ đếm từ 1, nghĩa là số đầu tiên ở vị trí 1 chứ không phải 0 như trong máy tính) return 0; } ``` ::: :::: ::::success > Personal Comment: Pretty cool problem tbh. ![image](https://hackmd.io/_uploads/ryr8NR2Veg.png) :::: ::::: :::::spoiler Codeforces 28A - Bender Problem ::::info **Link:** [28A_CF](https://codeforces.com/problemset/problem/28/A) **ELO:** 1600 **Tags:** implementation **Number requested by:** Thảo Nhiên (TDN A2) :::: ::::warning **Tóm tắt:** - Robot Bender cần dùng *m* thanh sắt để tạo một bức tranh là đường gấp khúc kín nối *n* cái đinh có sẵn. - Các quy tắc: - Mỗi thanh sắt chỉ dùng 1 lần và có thể uốn gập 90 độ. - Điểm uốn được gắn vào 1 đinh, 2 đầu thanh sắt gắn vào 2 đinh kề với đinh đó. - Các đoạn thẳng phải song song với trục tọa độ. - Nếu Robot Bender có thể thành công tạo ra bức tranh, in ra "YES" và danh sách thanh sắt dùng cho mỗi đinh, ngược lại in ra "NO". **Ví dụ:** | Input | Output | | ------------------------------------------------------ | --------------------- | | 4 2<br>0 0<br>0 2<br>2 2<br>2 0<br>4 4 | YES<br>1 -1 2 -1 | | 6 3<br>0 0<br>1 0<br>1 1<br>2 1<br>2 2<br>0 2<br>3 2 3 | YES<br>1 -1 2 -1 3 -1 | | 6 3<br>0 0<br>1 0<br>1 1<br>2 1<br>2 2<br>0 2<br>2 2 3 | NO | **Ý tưởng:** 1. Mấu chốt: - Một que bẻ cong lo được 2 đoạn thẳng: Một que được dùng bằng cách bẻ cong 90 độ tại một đinh (góc), hai đầu của nó sẽ nối với hai đinh liền kề. - Quy tắc "bận rộn": Khi bạn đặt một que bẻ cong tại đinh số *i*, thì các đinh *i*-1, *i*, và *i*+1 đều bị "chiếm chỗ". - Hệ quả quan trọng nhất: Vì quy tắc trên, bạn không thể đặt điểm uốn (gấp) ở hai đinh liền kề nhau. Ví dụ, nếu bạn đã gấp que ở đinh số 2, bạn không thể gấp que ở đinh số 1 hoặc số 3 nữa. 2. Hai trường hợp khả thi: - Từ hệ quả trên, để dùng *n*/2 que che hết *n* đoạn thẳng, bạn buộc phải chọn các điểm uốn xen kẽ nhau. Điều này dẫn đến chỉ có 2 kịch bản: - Trường hợp 1 (Kế hoạch Lẻ): Đặt các điểm uốn tại tất cả các đinh có số thứ tự lẻ (1, 3, 5, ...). - Trường hợp 2 (Kế hoạch Chẵn): Đặt các điểm uốn tại tất cả các đinh có số thứ tự chẵn (2, 4, 6, ...). 3. Thử qua các trường hợp - Thử "Kế hoạch Lẻ": - Tính toán: Với mỗi đinh lẻ (1, 3, 5,...), hãy tính xem cần một que dài bao nhiêu. Ví dụ, tại đinh 1, que cần dài bằng distance(*n*, 1) + distance(1, 2). - Kiểm tra: So sánh danh sách các độ dài vừa tính với các que bạn có. Nếu bạn có đủ các que tương ứng, thì đây là một lời giải. In ra "YES" và kết quả rồi dừng lại. - Thử "Kế hoạch Chẵn" (nếu kế hoạch lẻ thất bại): - Tính toán: Làm tương tự, nhưng lần này với các đinh chẵn (2, 4, 6,...). - Kiểm tra: Nếu có đủ que, in "YES" và kết quả. - Nếu cả hai kế hoạch trên đều không thực hiện được (vì thiếu que có độ dài phù hợp), thì bài toán không có lời giải, in ra "NO". :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <vector> #include <cmath> #include <map> using namespace std; struct Point { long long x, y; }; long long distanceNails(Point p1, Point p2) { return abs(p1.x - p2.x) + abs(p1.y - p2.y); } bool solve(int startNode, vector<Point> nails, map<long long, vector<int>>& rodCounts, int n, vector<int>& result) { auto currentRods = rodCounts; vector<int> tempR(n+1, -1); for (int i = 0; i < n / 2; i++) { int foldNail = startNode + 2 * i; int prevNail = (foldNail == 1) ? n : foldNail - 1; int nextNail = (foldNail == n) ? 1 : foldNail + 1; long long lengthRequired = distanceNails(nails[prevNail], nails[foldNail]) + distanceNails(nails[foldNail], nails[nextNail]); if (currentRods.count(lengthRequired) && !currentRods[lengthRequired].empty()) { int rodID = currentRods[lengthRequired].back(); currentRods[lengthRequired].pop_back(); tempR[foldNail] = rodID; } else return false; } result = tempR; return true; } int main() { int n, m; cin >> n >> m; vector<Point> nails(n+1); for (int i = 1; i <= n; i++) { cin >> nails[i].x >> nails[i].y; } map<long long, vector<int>> rods; for (int i = 1; i <= m; i++) { long long length; cin >> length; rods[length].push_back(i); } vector<int> result; if (solve(1, nails, rods, n, result)) { cout << "YES\n"; for (int i = 1; i <= n; i++) cout << result[i] << (i == n ? "" : " "); cout << endl; return 0; } if (solve(2, nails, rods, n, result)) { cout << "YES\n"; for (int i = 1; i <= n; i++) cout << result[i] << (i == n ? "" : " "); cout << endl; return 0; } cout << "NO\n"; return 0; } ``` ::: :::: ::::success > Personal Comment: Hardest one so far, but I gotta do it fh :fire: ![image](https://hackmd.io/_uploads/rJbjGHzHgx.png) :::: ::::: :::::spoiler Codeforces 41A - Translation ::::info **Link:** [41A_CF](https://codeforces.com/problemset/problem/41/A) **ELO:** 800 **Tags:** implementation, strings :::: ::::warning **Tóm tắt:** - Kiểm tra xem chuỗi đầu tiên lật ngược có bằng chuỗi thứ hai không **Ý tưởng:** - Lật ngược chuỗi đầu tiên rồi so sánh với chuỗi thứ hai **Ví dụ:** | Input | Output | | ------------ | ------ | | code<br>edoc | YES | | abb<br>aba | NO | | code<br>code | NO | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <algorithm> using namespace std; int main() { string s, t; cin >> s >> t; reverse(s.begin(), s.end()); if (s == t) cout << "YES" << endl; else cout << "NO" << endl; return 0; } ``` ::: :::: ::::success > Personal Comment: Tuff ahh language :wilted_flower: ![image](https://hackmd.io/_uploads/Hkm8Dc1Igl.png) :::: ::::: :::::spoiler Codeforces 49A - Sleuth ::::info **Link:** [49A_CF](https://codeforces.com/contest/49/problem/A) **ELO:** 800 **Tags:** implementation **Number requested by:** Gia Tuấn | Mokibam (GOT /2) :::: ::::warning **Tóm tắt:** - Cho một chuỗi, kiểm tra chữ cái cuối cùng của chuỗi có phải là nguyên âm (A, E, I, O, U, Y) không. - Chữ cái đó phải có ở trong bảng chữ cái (A - Z). **Ví dụ:** | Input | Output | | ----------------------------------------------------------- | ------ | | Is it a melon? | NO | | Is it an apple? | YES | | ㅤㅤIsㅤㅤㅤㅤㅤit a banana ? | YES | | Isㅤㅤㅤit an appleㅤㅤand aㅤㅤbananaㅤㅤㅤsimultaneouSLY? | YES | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { string ques; getline(cin, ques); // Dùng getline để nhận cả một dòng input thành 1 chuỗi char lastC = ' '; // Lưu từ cuối cùng của câu hỏi vector<char> vowels = {'a', 'e', 'i', 'o', 'u', 'y'}; // Các nguyên âm // Duyệt ngược từ cuối đến đầu chuỗi for (int i = ques.length() - 2; i >= 0; i--) { // ques.length -1 luôn là dấu ? hoặc không có gì, nhưng kiểm tra từ ques.length() - 2 vẫn tối ưu hơn if (isalpha(ques[i])) { // Nếu từ đang duyệt là 1 chữ cái (A - Z) lastC = towlower(ques[i]); // Lưu vào lastC từ đó dưới dạng in thường break; // Dừng duyệt } } if (find(vowels.begin(), vowels.end(), lastC) != vowels.end()) cout << "YES" << endl; // Nếu từ cuối đó là một nguyên âm in ra "YES" else cout << "NO" << endl; // Ngược lại in ra "NO" return 0; } ``` ::: :::: ::::success > Personal Comment: Easy one ngl. ![image](https://hackmd.io/_uploads/SJm7gSpEgl.png) :::: ::::: :::::spoiler Codeforces 50A - Domino piling ::::info **Link:** [50A_CF](https://codeforces.com/problemset/problem/50/A) **ELO:** 800 **Tags:** greedy, math :::: ::::warning **Tóm tắt:** - Cho một hình chữ nhật có kích thước *m* * *n* - Ta có thể đặt bao nhiêu hình chữ nhật có kích thước 2 x 1 cũng được để lấp đầy hình chữ nhật trên - Các quy tắc: - 2 hình chữ nhật không được đặt đè lên nhau - 1 hình chữ nhật lắp đầy 2 ô trong hình chữ nhật lớn - Các hình chữ nhật chỉ được đặt trong hình chữ nhật lớn, được phép đụng cạnh của hình chữ nhật lớn **Ví dụ:** | Input | Output | | ----- | ------ | | 2 4 | 4 | | 3 3 | 4 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int m, n; cin >> m >> n; // Nhập vào m và n cout << m * n / 2 << endl; // Đáp án sẽ là diện tích của hình chữ nhật lớn chia 2 return 0; } ``` ::: :::: ::::success > Personal Comment: Domino mentioned ![image](https://hackmd.io/_uploads/S1h9BTCVlx.png) :::: ::::: :::::spoiler Codeforces 57A - Square Earth? ::::info **Link:** [57A_CF](https://codeforces.com/contest/57/problem/A) **ELO:** 1300 **Tags:** dfs and similar, greedy, implementation **Number requested by:** my mom :::: ::::warning **Tóm tắt:** - Cho *n* là độ dài cạnh Trái Đất hình vuông. - Cho *x1*, *y1* là tọa độ vị trí bắt đầu. - Cho *x2*, *y2* là tọa độ vị trí kết thúc. - Tính khoảng cách **ngắn nhất** từ vị trí bắt đầu đến kết thúc. - Chỉ được **đi trên các cạnh** của Trái Đất. **Ví dụ:** | Input | Output | | --------------- | ------ | | 2 0 0 1 0 | 1 | | 2 0 1 2 1 | 4 | | 100 0 0 100 100 | 200 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; /* Ta trải các cạnh Trái Đất hình vuông thành một đường thẳng (ngược chiều kim đồng hồ) Lúc này ta sẽ có 4 đoạn trên đường thẳng tương ứng với 4 cạnh: - Cạnh dưới [từ (0, 0) đến (n, 0)] <- Ta thấy y luôn bằng 0 + Vị trí trên đường thẳng: từ 0 đến n - Cạnh phải [từ (n, 0) đến (n, n)] <- Ta thấy x luôn bằng n + Vị trí trên đường thẳng: từ n đến 2n - Cạnh trên [từ (n, n) đến (0, n)] <- Ta thấy y luôn bằng n + Vị trí trên đường thẳng: từ 2n đến 3n - Cạnh trái [từ (0, n) đến (0, 0)] <- Ta thấy x luôn bằng 0 + Vị trí trên đường thẳng: từ 3n đến 4n Áp dụng lý thuyết này ta có hàm bên dưới */ int get_pos(int n, int x, int y) { if (y == 0) return x; // Nếu điểm (x, y) nằm trên cạnh dưới else if (x == n) return n + y; // Nếu điểm (x, y) nằm trên cạnh phải else if (y == n) return n * 2 + (n - x); // Nếu điểm (x, y) nằm trên cạnh trên else return n * 3 + (n - y); // Nếu điểm (x, y) nằm trên cạnh trái (không phải nằm trên 3 cạnh còn lại thì chắc chắn nằm trên cạnh trái) } // (Một số điểm có thể nằm trên cả 2 đoạn, nhưng ta đang xét lần lượt các đoạn theo đúng chiều nên tọa độ sẽ chính xác) int main() { int n, x1, y1, x2, y2; cin >> n >> x1 >> y1 >> x2 >> y2; // Nhập vào các số liệu int p1 = get_pos(n, x1, y1); // Lấy tọa độ điểm bắt đầu TRÊN đường thẳng int p2 = get_pos(n, x2, y2); // Lấy tọa độ kết thúc TRÊN đường thẳng int cir = 4 * n; // Tính chu vi hình vuông int dist_st = abs(p1 - p2); // Đi theo chiều của đường thẳng int dist_ar = cir - dist_st; // Ta cũng có thể đi ngược lại (vì là Trái Đất) cout << min(dist_st, dist_ar) << endl; // So sánh khoảng cách của hai cách đi rồi in ra khoảng cách ngắn nhất return 0; } ``` ::: :::: ::::success > Personal Comment: Trái Đất hình vuông is crazy, y như bài này vậy. ![image](https://hackmd.io/_uploads/BJRUWlTExx.png) :::: ::::: :::::spoiler Codeforces 59A - Word ::::info **Link:** [59A_CF](https://codeforces.com/problemset/problem/59/A) **ELO:** 800 **Tags:** implementation, strings :::: ::::warning **Tóm tắt:** - Cho 1 chuỗi, nếu số lượng từ in hoa **lớn hơn** số lượng từ in thường trong chuỗi thì in hoa cả chuỗi, không thì ngược lại. **Ví dụ:** | Input | Output | | ------ | ------ | | HoUse | house | | ViP | VIP | | maTRIx | matrix | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <string> #include <cctype> using namespace std; // Tạo một hàm để in hoa hoặc in thường cả chuỗi // Hàm có sẳn (toupper và tolower) chỉ in hoa/thường được 1 ký tự // Nên chỉ cần duyệt qua từng ký tự rồi xài hàm là được string upLowAll(bool upper, string s) { if (upper) { for (char &c : s) { // Thêm & để thêm con trỏ vào c rồi duyệt qua từng ký tự trong chuỗi ... c = toupper(c); // ... để khi xài hàm thì từ trong chuỗi cũng được thay đổi theo } } else { for (char &c : s) { // (Tương tự như trên nhưng in thường) c = tolower(c); } } return s; } int main() { string s; cin >> s; // Nhập vào chuỗi int upper = 0, lower = 0; // Tạo ra hai biến đếm bao nhiêu ký tự in hoa/thường trong chuỗi for (char c : s) { // Duyệt qua từng ký tự if (isupper(c)) upper++; // Nếu là in hoa thì tăng 1 vào bộ đếm in hoa else lower++; // Ngược lại (in thường) thì tăng 1 vào bộ đếm in thường } cout << ((upper > lower) ? upLowAll(true, s) : upLowAll(false, s)) << endl; // So sánh 2 bộ đếm với nhau rồi từ đó in ra chuỗi được in hoa/thường return 0; } ``` ::: :::: ::::success > Personal Comment: VIP ![image](https://hackmd.io/_uploads/rJ28TqMSlg.png) :::: ::::: :::::spoiler Codeforces 69A - Young Physicist ::::info **Link:** [69A_CF](https://codeforces.com/contest/69/problem/A) **ELO:** 1000 **Tags:** implementation, math :::: ::::warning **Tóm tắt:** - Có *n* lực vector tác dụng lên vật - Một vector có cấu trúc: x - y - z - Nếu x, y, z của từng vector lần lượt cộng lại bằng 0 thì vật cân bằng (Định nghĩa Cân bằng - Equilibrium) **Ví dụ:** | Input | Output | | --------------------------------- | ------ | | 3<br>4 1 7<br>-2 4 -1<br> 1 -5 -3 | NO | | 3<br>3 -1 7<br>-5 2 -4<br>2 -1 -3 | YES | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int n, sum_x = 0, sum_y = 0, sum_z = 0; // Tạo biến n, tạo các biến lưu tổng x, y, z cin >> n; // Nhập vào số lực vector while (n) { // Duyệt qua mỗi lực int x, y, z; // Tạo biến lưu x, y, z của lực cin >> x >> y >> z; // Nhập vào x, y, z của lực sum_x += x; // Cộng vào tổng x sum_y += y; // Cộng vào tổng y sum_z += z; // Cộng vào tổng z n--; // Duyệt qua lực tiếp theo } if (sum_x == 0 && sum_y == 0 && sum_z == 0) cout << "YES" << endl; // Nếu cả ba tổng bằng 0 in YES else cout << "NO" << endl; // Không thì in "NO" return 0; } ``` ::: :::: ::::success > Personal Comment: Cái package của cái bài này nó chưa được update nên chạy chậm vãi, lúc đầu không biết nộp code mà nó cứ bị kẹt ở vài cái test làm hết hồn xD ![image](https://hackmd.io/_uploads/rJnP7khExe.png) :::: ::::: :::::spoiler Codeforces 71A - Way Too Long Words ::::info **Link:** [71A_CF](https://codeforces.com/problemset/problem/71A/) **ELO:** 800 **Tags:** strings :::: ::::warning **Tóm tắt:** - Nhận vào 1 chuỗi, nếu nó có độ dài hơn 10 thì rút gọn, không thì in ra chuỗi gốc. - Cú pháp rút gọn: Chữ cái đầu + Số ký tự ở giữa + Chữ cái cuối **Ví dụ:** | Input | Output | | -------------------------------------------------------------------------------------------------- | ---------------------------- | | 4<br>word<br>localization<br>internationalization<br>pneumonoultramicroscopicsilicovolcanoconiosis | word<br>l10n<br>i18n<br>p43s | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int n; // Nhập vào số lượng chuỗi cin >> n; string s; while (n) { // Duyệt qua từng chuỗi cin >> s; // Nhận vào chuỗi gốc if (s.length() > 10) { // Nếu độ dài lớn hơn 10 string r; // Chuỗi đã rút gọn r += s[0]; // Thêm chữ cái đầu vào chuỗi r += to_string(s.length() - 2); // Thêm số chữ đã rút gọn r += s[s.length() - 1]; // Thêm chữ cái cuối vào chuỗi cout << r << endl; // In ra chuỗi đã rút gọn } else cout << s << endl; // In ra chuỗi gốc n--; // Duyệt sang chuỗi tiếp theo } return 0; } ``` ::: :::: ::::success > Personal Comment: Too Long? Bet. ![image](https://hackmd.io/_uploads/BkxIuhaq4le.png) :::: ::::: :::::spoiler Codeforces 110A - Nearly Lucky Number ::::info **Link:** [110A_CF](https://codeforces.com/contest/110/problem/A) **ELO:** 800 **Tags:** implementation :::: ::::warning **Tóm tắt:** - Đếm có bao nhiêu chữ số '4' và '7' trong số *n*, rồi xem số đếm được có bằng 4 hoặc 7 không. **Ví dụ:** | Input | Output | | ------------------- | ------ | | 40047 | NO | | 7747774 | YES | | 1000000000000000000 | NO | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { string n; cin >> n; // Nhập vào số n dưới dạng chuỗi int lucky = 0; // Đếm số lượng chữ số '4' và '7' for (char c : n) { // Duyệt qua từng ký tự if (c == '4' || c == '7') { // Nếu là '4' hoặc '7' lucky++; // Tăng bộ đếm } } if (lucky == 4 || lucky == 7) cout << "YES"; // Nếu số lượng ký tự hợp lệ bằng 4 hoặc bằng 7 thì in ra "YES" else cout << "NO"; // Không thì in ra "NO" return 0; } ``` ::: :::: ::::success > Personal Comment: Bài này vừa ngủ dậy làm nên làm ẩu vãi :v ![image](https://hackmd.io/_uploads/B1Ri-P7Sll.png) :::: ::::: :::::spoiler Codeforces 112A - Petya and Strings ::::info **Link:** [112A_CF](https://codeforces.com/problemset/problem/112/A) **ELO:** 800 **Tags:** implementation, strings :::: ::::warning **Tóm tắt:** - Cho 2 chuỗi có độ dài bằng nhau, so sánh 2 chuỗi: - Nếu chuỗi đầu lớn hơn chuỗi sau thì in '1' - Nếu chuỗi dầu bé hơn chuỗi sau thì in '-1' - Nếu 2 chuỗi bằng nhau thì in '0' - Không quan trọng in hoa in thường - Cách so sánh: xem 2 chữ cái của 2 chuỗi xem vị trí của 2 tụi nó đứng ở đâu trong bảng chứ cái, từ đó biết lớn bé bằng (kiểu vậy, xem thêm ở [đây](https://en.wikipedia.org/wiki/Lexicographic_order)) **Ví dụ:** | Input | Output | | ------------------ | ------ | | aaaa<br>aaaA | 0 | | abs<br>Abz | -1 | | abcdefg<br>AbCdEfF | 1 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { string a, b; cin >> a >> b; // Nhập vào 2 chuỗi for (int i = 0; i < a.length(); i++) { // So sánh từng ký tự. Vì độ dài bằng nhau nên i < a.length() hay b.length() cũng được char a_ = a[i], b_ = b[i]; // Tạo ra 2 biến riêng để lưu 2 ký tự đang được lấy để so sánh if (isupper(a[i])) a_ = tolower(a[i]); // Nếu in hoa thì chuyển thành in thường if (isupper(b[i])) b_ = tolower(b[i]); // Nếu in hoa thì chuyển thành in thường if (a_ != b_) { // Nếu 2 ký tự khác nhau cout << ((a_ > b_) ? "1" : "-1") << endl; // Nếu ký tự thuộc chuỗi 1 lớn hơn ký tự thuộc chuỗi 2 thì in ra '1', ngược lại in '-1' // (Ở đây ta đang so sánh bằng bảng mã ASCII*) return 0; } } cout << "0" << endl; return 0; } ``` *: [Bảng mã ASCII](https://en.wikipedia.org/wiki/ASCII) ::: :::: ::::success > Personal Comment: Easy one just work with the strings bruh ![image](https://hackmd.io/_uploads/Syu2xRC4xl.png) :::: ::::: :::::spoiler Codeforces 158A - Next Round ::::info **Link:** [158A_CF](https://codeforces.com/problemset/problem/158/A) **ELO:** 800 **Tags:** special problem, implementation :::: ::::warning **Tóm tắt:** - Cho *n* số - Đếm xem có bao nhiêu số lớn hơn hoặc bằng với số thứ *k*, với điều kiện số thứ *k* lớn hơn 0 **Ví dụ:** | Input | Output | | ----------------------- | ------ | | 8 5<br>10 9 8 7 7 7 5 5 | 6 | | 4 2<br>0 0 0 0 | 0 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <vector> using namespace std; int main() { int n, k; cin >> n >> k; // Nhập vào n (bao nhiêu số), k (số thứ mấy để so sánh) vector<int> a(n); // Lưu các số for (int i = 0; i < n; ++i) { cin >> a[i]; // Nhập vào từng số } int kth = a[k - 1]; // Số thứ k (k - 1 vì trong vector, số đầu tiên đứng ở vị trí thứ 0) int count = 0; // Đếm bao nhiêu số lớn hơn hoặc bằng số thứ k, với điều kiện lớn hơn 0 for (int i = 0; i < n; ++i) { // Duyệt qua từng số if (a[i] >= kth && a[i] > 0) { // Nếu lớn hơn hoặc bằng số thứ k count++; // Tăng 1 vào bộ đếm } else { break; } } cout << count << endl; // In ra bao nhiêu số hợp lệ return 0; } ``` ::: :::: ::::success > Personal Comment: Idk it's just easy i guess... ![image](https://hackmd.io/_uploads/HJOyP3CNel.png) :::: ::::: :::::spoiler Codeforces 169A - Chores ::::info **Link:** [169A_CF](https://codeforces.com/contest/169/problem/A) **ELO:** 800 **Tags:** sortings **Number recommended by:** Đình Tùng (TDN - A2) :::: ::::warning **Tóm tắt:** - P và V được giao *n* việc nhà. - Từng việc nhà có độ khó khác nhau. - P làm việc có độ khó > *x*, V làm việc có độ khó <= *x* - P làm *a* công việc và V làm *b* công việc. - Tính số lượng các giá trị *x*, với *x* là độ khó ở giữa để phân chia công việc cho P và V. **Ví dụ:** | Input | Output | | ---------------------- | ------ | | 5 2 3<br>6 2 3 100 1 | 3 | | 7 3 4<br>1 1 9 1 1 1 1 | 0 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, a, b; cin >> n >> a >> b; // Nhập vào n (bao nhiêu công việc), a (số công việc P làm), b (số công việc V làm) vector<int> h(n); // Lưu các công việc và cấp độ tương ứng for (int i = 0; i < n; i++) { cin >> h[i]; // Nhập vào cấp độ của công việc thứ i } sort(h.begin(), h .end()); // Sắp xếp lại các cấp độ theo thứ tự từ bé đến lớn int result = h[b] - h[b-1]; // Lấy độ khó thấp nhất của công V làm trừ cho độ khó cao nhất của công việc mà P làm, ta sẽ có số lượng các giá trị x cout << result << endl; // In ra số lượng các giá trị x return 0; } ``` ::: :::: ::::success > Personal Comment: Another one got complicated. ![image](https://hackmd.io/_uploads/Hk84Xr0Nee.png) :::: ::::: :::::spoiler Codeforces 231A - Team ::::info **Link:** [231A_CF](https://codeforces.com/problemset/problem/231/A) **ELO:** 800 **Tags:** brute force, greedy :::: ::::warning **Tóm tắt:** - Có *n* bài code. - Có 3 người, nếu có 2/3 hoặc 3/3 người biết giải bài code thì ta sẽ giải bài code đó. - Tính số bài code mà đội 3 người họ có thể giải. **Ví dụ:** | Input | Output | | ---------------------------- | ------ | | 3<br>1 1 0<br>1 1 1<br>1 0 0 | 2 | | 2<br>1 0 0<br>0 1 1 | 1 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int n, solve = 0; // Đặt biến solve để lưu số bài code có thể giải cin >> n; // Nhập vào số bài code while (n) { // Duyệt qua từng bài int p, v, t, sure = 0; // Đặt biến cho 3 người và 1 biến để lưu số người giải được bài code cin >> p >> v >> t; // Duyệt qua từng người if (p) sure++; if (v) sure++; if (t) sure++; if (sure > 1) { // Nếu hơn 1 người biết giải solve++; // Thêm 1 vào tổng số bài có thể giải } n--; // Qua bài tiếp theo } cout << solve << endl; // In ra số bài có thể giải bởi đội return 0; } ``` ::: :::: ::::success > Personal Comment: Why can't someone be the MVP and solve all the solutions him/herself lol. ![image](https://hackmd.io/_uploads/HJMMKCiVel.png) :::: ::::: :::::spoiler Codeforces 236A - Boy or Girl ::::info **Link:** [236A](https://codeforces.com/problemset/problem/236/A) **ELO:** 800 **Tags:** brute force, implementation, strings :::: ::::warning **Tóm tắt:** - Cho 1 chuỗi, đếm xem có bao nhiêu ký tự riêng biệt, nếu: - Là số chẳn thì in ra "CHAT WITH HER!" - Là số lẻ thì in ra "IGNORE HIM!" **Ví dụ:** | Input | Output | | ---------- | -------------- | | wjmzbmr | CHAT WITH HER! | | xiaodao | IGNORE HIM! | | sevenkplus | CHAT WITH HER! | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { string s; cin >> s; // Nhập vào chuỗi int ascii[127] = {0}; // Tạo một mảng để đếm số lần xuất hiện của từng ký tự int distC = 0; // Đếm có bao nhiêu ký tự riêng biệt for (int i = 0; i < s.length(); i++) { // Duyệt qua từng ký tự trong chuỗi if (ascii[s[i]] == 0) distC++; // Nếu ký tự chưa bị trùng thì cộng 1 vào distC ascii[s[i]]++; // Cộng 1 vào số lần xuất hiện của ký tự } // (Ta đang dùng ASCII nên chắc chắn không có việc 2 ký tự riêng biệt được đếm chung) cout << ((distC % 2 == 0) ? "CHAT WITH HER!" : "IGNORE HIM!"); // Xem chẳn hay lẻ rồi in ra kết quả mong muốn của đề bài return 0; } ``` ::: :::: ::::success > Personal Comment: Do NOT use this technique in real life :pray: ![image](https://hackmd.io/_uploads/rkg1aPyHgg.png) :::: ::::: :::::spoiler Codeforces 266A - Stones on the Table ::::info **Link:** [266A_CF](https://codeforces.com/problemset/problem/266/A) **ELO:** 800 **Tags:** implementation :::: ::::warning **Tóm tắt:** - Cho 1 chuỗi có *n* ký tự, hãy đếm có bao nhiêu ký tự cần bỏ để 2 ký tự kề nhau không giống nhau **Ví dụ:** | Input | Output | | ---------- | ------ | | 3<br>RRG | 1 | | 5<br>RRRRR | 4 | | 4<br>BRBG | 0 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int n, removals = 0; // Tạo biến n; removals để lưu số lần bỏ ký tự cin >> n; // Nhập vào số lượng ký tự string s; cin >> s; // Nhập vào chuỗi for (int i = 0; i < n; i++) { // Duyệt qua từng ký tự if (s[i] == s[i-1]) removals++; // Nếu ký tự đang duyệt và ký tự trước đó giống nhau thì bỏ, cộng 1 vào bộ đếm bỏ } cout << removals << endl; // In ra bao nhiêu lần bỏ return 0; } ``` ::: :::: ::::success > Personal Comment: RGB ![image](https://hackmd.io/_uploads/rkk9VGMrlg.png) :::: ::::: :::::spoiler Codeforces 269A - Beautiful Matrix ::::info **Link:** [269A_CF](https://codeforces.com/problemset/problem/263/A) **ELO:** 800 **Tags:** implementation :::: ::::warning **Tóm tắt:** - Cho một ma trận 5x5 toàn số 0 có một số 1 trong đó, đếm số bước để di chuyển số '1' vào giữa ma trận **Ví dụ:** | Input | Output | | ------------------------------------------------------------- | ------ | | 0 0 0 0 0<br>0 0 0 0 1<br>0 0 0 0 0<br>0 0 0 0 0<br>0 0 0 0 0 | 3 | | 0 0 0 0 0<br>0 0 0 0 0<br>0 1 0 0 0<br>0 0 0 0 0<br>0 0 0 0 0 | 1 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <cmath> using namespace std; int main() { int n = 0, x = 0, y = 1; // Đặt n để lấy số, x để lưu cột của '1' và y để lưu hàng của '1' (đơn giản hơn để hiểu là x y lưu tọa độ của '1' trong ma trận) while (n != 1) { // Khi chưa biết '1' ở đâu thì tiếp tục cho nhập cin >> n; // Nhập vào số x++; // Cộng 1 vào cột if (x == 6) { // Nếu ra khỏi ma trận x = 1; // Về lại ma trận y++; // Cộng 1 vào hàng } } cout << abs(3 - x) + abs(3 - y) << endl; // Vì ma trận luôn là 5x5, muốn vào giữa thì cứ cho '1' về giữa hàng, sau đó vào giữa cột là đến được giữa ma trận. abs() để làm số âm thành số nguyên (ví dụ: 3 - 5 = -2 thì thành 2, đi 2 bước vào giữa) return 0; } ``` ::: :::: ::::success > Personal Comment: Ban đầu làm cho '1' đi từ từ chậm chậm chill chill vào giữa, xong mới nhận ra là phải tìm đường ngắn nhất cho '1' đi ![image](https://hackmd.io/_uploads/rkIpq6CVlg.png) :::: ::::: :::::spoiler Codeforces 281A - Word Capitalization ::::info **Link:** [281A_CF](https://codeforces.com/problemset/problem/281/A) **ELO:** 800 **Tags:** implementation, strings :::: ::::warning **Tóm tắt:** - Cho một chuỗi, in hoa chữ cái đầu của chuỗi **Ví dụ:** | Input | Output | | ------ | ------ | | ApPLe | ApPLe | | konjac | Konjac | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { string s; cin >> s; // Nhập váo chuỗi cout << (char)toupper(s[0]) << s.erase(0, 1); // In ra chữ cái đầu tiên in hoa nối với đoạn còn lại của chuỗi return 0; } ``` ::: :::: ::::success > Personal Comment: Easy. ![image](https://hackmd.io/_uploads/S1gJ7cJrle.png) :::: ::::: :::::spoiler Codeforces 282A - Bit++ ::::info **Link:** [282A_CF](https://codeforces.com/problemset/problem/282/A) **ELO:** 800 **Tags:** implementation :::: ::::warning **Tóm tắt:** - Cho *n* câu lệnh. - Câu lệnh có cấu trúc: '\++' / '\--' + 'X' hoặc ngược lại. ("X++" hoặc "++X") - *x* mặc định là 0. - Cho ra kết quả sau khi cộng trừ. **Ví dụ:** | Input | Output | | --------------- | ------ | | 1<br>++X | 1 | | 2<br>X++<br>--X | 0 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int n, x = 0; // Đặt biến x mặc định thành 0 cin >> n; // Nhập vào n số câu lệnh while (n) { string stm; cin >> stm; // Nhập vào câu lệnh // Inf IQ move: dù câu lệnh có xáo trộn cỡ nào thì ở giữa chỉ có thể là '+' hoặc '-' if (stm[1] == '+') x++; // Nếu câu lệnh có '+' ở giữa thì cộng 1 vào x else x--; // Nếu không thì chỉ có thể là '-', trừ 1 vào x n--; // Duyệt qua lệnh tiếp theo } cout << x << endl; // In ra kết quả return 0; } ``` ::: :::: ::::success > Personal Comment: Brilliant move from me right there. ![image](https://hackmd.io/_uploads/SJjwnCsVex.png) :::: ::::: :::::spoiler Codeforces 339A - Helpful Maths ::::info **Link:** [339A](https://codeforces.com/problemset/problem/339/A) **ELO:** 800 **Tags:** greedy, implementation, sortings, strings :::: ::::warning **Tóm tắt:** - Cho một phương trình, sắp xếp lại từ bé đến lớn (xem ví dụ bên dưới) **Ví dụ:** | Input | Output | | --------- | --------- | | 3+2+1 | 1+2+3 | | 1+1+3+1+3 | 1+1+1+3+3 | | 2 | 2 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { string s; cin >> s; // Nhập vào phương trình if (s.length() == 1) { // EdgeCaseTM: nếu chỉ có 1 số cout << s << endl; // In ra lại số đó return 0; } vector<char> c; // Tạo mảng c để lưu từng số trong phương trình for (int i = 0; i < s.length(); i++) { // Duyệt từng ký tự của phương trình if (s[i] != '+') c.push_back(s[i]); // Nếu là dấu '+' thì bỏ qua, không thì là số, thêm vô c } sort(c.begin(), c.end()); // Sắp xếp lại c từ bé đến lớn for (int i = 0; i < c.size(); i++) { // Duyệt qua mảng c if (i == c.size() - 1) cout << c[i]; // Nếu là số cuối thì không in ra dấu '+' ở phía sau else cout << c[i] << '+'; // Không thì in ra số kèm dấu '+' } return 0; } ``` ::: :::: ::::success > Personal Comment: I wonder if Xenia can finally calculate without this now :pray: ![image](https://hackmd.io/_uploads/BJ6vVCC4lx.png) :::: ::::: :::::spoiler Codeforces 546A - Soldier and Bananas ::::info **Link:** [546A_CF](https://codeforces.com/problemset/problem/546/A) **ELO:** 800 **Tags:** brute force, implementation, math :::: ::::warning **Tóm tắt:** - Có *w* quả chuối. - Mua quả thứ nhất trả *k* tiền, mua quả thứ hai trả *2k*, mua quả thứ ba trả *3k*, ... - Mình có *n* tiền. - Tính xem cần mượn thêm bao nhiêu tiền để mua hết *w* chuối, nếu không cần mượn thì in ra "0". **Ví dụ:** | Input | Output | | ------ | ------ | | 3 17 4 | 13 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int k, n, w, borrow = 0; // Tạo biến k, n, w; borrow để lưu tạm số tiền tổng, sau đó lưu số tiền cần mượn cin >> k >> n >> w; // Nhập vào k, n, w for (int i = 0; i <= w; i++) { // Cứ mỗi quả chuối thì... borrow += k * i; // ... tính giá tiền rồi thêm vào borrow } borrow = borrow - n; // Tính số tiền cần mượn cout << ((borrow > 0) ? borrow : 0) << endl; // Nếu số tiền cần mượn không phải số âm thì in ra; không thì không cần mượn gì hết, in ra 0 return 0; } ``` ::: :::: ::::success > Personal Comment: Banana! ![image](https://hackmd.io/_uploads/rkcdXcfHgg.png) :::: ::::: :::::spoiler Codeforces 617A - Elephant ::::info **Link:** [617A_CF](https://codeforces.com/contest/617/problem/A) **ELO:** 800 **Tags:** math :::: ::::warning **Tóm tắt:** - Một con voi có thể bước 1, 2, 3, 4, 5 bước mỗi lượt đi. - Cho một điểm *x*. Tính bao nhiêu lượt đi để con voi đến được *x*. - Con voi bắt đầu từ điểm 0. **Ví dụ:** | Input | Output | | ----- | ------ | | 5 | 1 | | 12 | 3 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int x; cin >> x; // Nhập vào x // Ta cứ cho voi đi 5 bước; rồi còn bao nhiêu bước thì đi bấy nhiêu, công thức sẽ là số lượt voi đi 5 bước + 1 lượt voi đi những bước còn lại if (x % 5 != 0) x = x / 5 + 1; // Nếu x không chia hết cho 5 thì có nghĩa là thiếu bước, cần đi thêm 1 lượt (không cần biết là thiếu bao nhiêu) else x = x / 5; // Không thì chia cho 5 để lấy số lượt đi cout << x << endl; // In ra số lượt đi return 0; } ``` ::: :::: ::::success > Personal Comment: One single variable used. Peak. Also sai 1 lần :v do lần đầu x / 5 trước rồi mới xét điều kiện (which is wrong) ![image](https://hackmd.io/_uploads/HkKJTdGHgl.png) :::: ::::: :::::spoiler Codeforces 677A ::::info **Link:** [677A_CF](https://codeforces.com/problemset/problem/677/A) **ELO:** 800 **Tags:** implementation :::: ::::warning **Tóm tắt và Ý Tưởng:** - Cho số *h* - Tạo một bộ đếm - Xem lần lượt qua *n* số, nếu số đó lớn hơn *h* cộng 2 vào bộ đếm, không thì cộng 1 **Ví dụ:** | Input | Output | | ------------------- | ------ | | 3 7<br>4 5 14 | 4 | | 6 1<br>1 1 1 1 1 1 | 6 | | 6 5<br>7 6 8 9 10 5 | 11 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, h, a, result = 0; cin >> n >> h; while(n--){ cin >> a; if (a > h) result += 2; else result++; } cout << result << endl; return 0; } ``` ::: :::: ::::success > Personal Comment: Đi từng người qua cổng r chat bro? ![image](https://hackmd.io/_uploads/B1gWjEy5Ull.png) :::: ::::: :::::spoiler Codeforces 734A - Anton and Danik ::::info **Link:** [734A_CF](https://codeforces.com/problemset/problem/734/A) **ELO:** 800 **Tags:** implementation, strings :::: ::::warning **Tóm tắt:** - Cho một chuỗi với *n* ký tự, nếu: - Số ký tự 'A' nhiều nhất in "Anton" - Số ký tự 'D' nhiều nhất in "Danik" - Nếu bằng nhau in "Friendship" **Ví dụ:** | Input | Output | | ------------ | ---------- | | 6<br>ADAAAA | Anton | | 7<br>DDDAADA | Danik | | 6<br>DADADA | Friendship | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int n, anton = 0, danik = 0; // Tạo biến n; anton để lưu số ký tự 'A'; danik để lưu số ký tự 'D' cin >> n; // Nhập vào n string s; // Lưu chuỗi s cin >> s; // Nhập vào chuỗi for (int i = 0; i < n; i++) { // Duyệt qua từng ký tự trong chuỗi if (s[i] == 'A') anton++; // Nếu là 'A' thì tăng 1 vào bộ đếm anton else danik++; // Ngược lại thì là 'D', tăng 1 vào bộ đếm danik } if (anton > danik) cout << "Anton"; // Nếu anton nhiều hơn danik in ra "Anton" else if (danik > anton) cout << "Danik"; // ___ ít hơn in ra "Danik" else cout << "Friendship"; // ___ bằng nhau in ra "Friendship" return 0; } ``` ::: :::: ::::success > Personal Comment: Nah ain't no way bro fightin' so hard then tie then Friendship like ahh :pray: ![image](https://hackmd.io/_uploads/HyMlKcUrge.png) :::: ::::: :::::spoiler Codeforces 791A - Bear and Big Brother ::::info **Link:** [791A_CF](https://codeforces.com/contest/791/problem/A) **ELO:** 800 **Tags:** implementation :::: ::::warning **Tóm tắt:** - Cho 2 số, sau mỗi lượt: - Số đầu tiên gấp ba. - Số thứ hai gấp đôi. - Sau bao nhiêu lượt tăng thì số đầu tiên sẽ lớn hơn số thứ hai? **Ví dụ:** | Input | Output | | ----- | ------ | | 4 7 | 2 | | 4 9 | 3 | | 1 1 | 1 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int a, b, n = 0; // Đặt biến a và b; n để lưu số lượt tăng cin >> a >> b; // Nhập vào 2 số while (!(a > b)) { // Khi số đầu tiên chưa lớn hơn số thứ 2 a *= 3; // Gấp 3 số đầu tiên b *= 2; // Gấp 2 số thứ 2 n++; // Tăng số lượt tăng lên 1 } cout << n; // In ra số lượt tăng return 0; } ``` ::: :::: ::::success > Personal Comment: Quên set n = 0 ở lượt đầu tiên, giờ phải đi ăn trưa :yum: ![image](https://hackmd.io/_uploads/Hk81bokHeg.png) :::: ::::: :::::spoiler Codeforces 977A - Wrong Subtraction ::::info **Link:** [977A_CF](https://codeforces.com/problemset/problem/977/A) **ELO:** 800 **Tags:** implementation :::: ::::warning **Tóm tắt:** - Cho một số và *k* lượt trừ/chia số theo quy tắc: - Nếu chữ số cuối cùng là '0' thì chia 10 - Không thì trừ 1 **Ví dụ:** | Input | Output | | ------------ | ------ | | 512 4 | 50 | | 1000000000 9 | 1 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int n, k; cin >> n >> k; // Nhập vào n (số gốc) và k (số lượt trừ/chia) for (int i = 0; i < k; i++) { // Lập lại k lượt if (n % 10 == 0) n /= 10; // Nếu n chia hết cho 10 (chữ số cuối là 0) thì chia 10 else n--; // Không thì trừ 1 } cout << n << endl; // In ra kết quả return 0; } ``` ::: :::: ::::success > Personal Comment: Tanya really need to learn how to subtract the right way bruh :moyai: ![image](https://hackmd.io/_uploads/Hk7adsGSex.png) :::: ::::: :::::spoiler Codeforces 2094A - Trippi Troppi ::::info **Link:** [2094A_CF](https://codeforces.com/contest/2094/problem/A) **ELO:** 800 **Tags:** strings :::: ::::warning **Tóm tắt:** - Cho *t* chuỗi, in ra viết tắt của các chuỗi đó. **Ví dụ:** | Input | Output | | ---------------------------------------------------------------------------------------------------------------------------------------------- | --------------------------------------------- | | 7<br>united states america<br>oh my god<br>i cant lie<br>binary indexed tree<br>believe in yourself<br>skibidi slay sigma<br>god bless america | usa<br>omg<br>icl<br>bit<br>biy<br>sss<br>gba | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int t; cin >> t; // Nhập vào bao nhiêu chuỗi cin.ignore(); // Để không bị lỗi getline() while (t) { // Duyệt qua từng chuỗi string s; getline(cin, s); // Nhập vào chuỗi (có khoảng cách) bool getNext = true; // Đặt biến getNext để biết và in ra ký tự tiếp theo; ban đầu đặt là true để lấy ký tự đầu tiên for (int i = 0; i < s.length(); i++) { // Duyệt qua từng ký tự trong chuỗi if (getNext) { // Nếu getNext = true cout << s[i]; // In ra ký tự đang được duyệt getNext = false; // Đặt getNext = false } if (s[i] == ' ') getNext = true; // Nếu ký tự đang được duyệt là khoảng cách (space) thì đặt lại getNext thành true } cout << endl; // Xuống dòng t--; // Qua chuỗi tiếp theo } return 0; } ``` ::: :::: ::::success > Personal Comment: Cái Contest này nó rot kinh khủng :skull: ![image](https://hackmd.io/_uploads/ryPniozHll.png) :::: ::::: ### Section B (Codeforces) :::::spoiler Codeforces 25B - Phone Numbers ::::info **Link:** [25B_CF](https://codeforces.com/contest/25/problem/B) **ELO:** 1100 **Tags:** implementation **Number requested by:** Chí Tịnh (TDN A2) :::: ::::warning **Tóm tắt:** - Cho một dãy số điện thoại với *n* chữ số. - Ngăn cách những chữ số trong số điện thoại cho dễ đọc bằng cách thêm dấu '-' vào giữa dãy số. - Có thể chia thành cụm 2 chữ số hoặc cụm 3 chữ số. **Ví dụ:** | Input | Output | | ------------ | --------- | | 6<br>549871 | 54-98-71 | | 7<br>1198733 | 11-987-33 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int n; cin >> n; // Nhập vào n (số chữ số trong số điện thoại) string s; cin >> s; // Nhập vào dãy số điện thoại // Ý tưởng: cứ chia thành 2 cụm, nếu là số lẻ thì 3 chữ số chia thành 1 cụm là được for (int i = 0; i < n;) { // Duyệt qua số điện thoại để thêm '-' if (i > 0) cout << "-"; // Chỉ cần chữ số đang duyệt không phải chữ số bắt đầu thì in ra '-' if (n - i == 3) { // Nếu còn 3 chữ số cuối cout << s[i] << s[i+1] << s[i+2]; // In ra 3 chữ số cuối break; // Dừng duyệt } else { cout << s[i] << s[i+1]; // In ra 2 chữ số i += 2; // Thêm 2 vào i (để duyệt qua chữ số cách chữ số hiện tại 2 số) } } cout << endl; return 0; } ``` ::: :::: ::::success > Personal Comment: It's kinda cheating but I mean they allowed so... ![image](https://hackmd.io/_uploads/BkO2KH0Nxg.png) :::: ::::: ### ACMSGURU (Codeforces) :::::spoiler Codeforces ACMSGURU 100 - A+B ::::info **Link:** [100_CF_ACM](https://codeforces.com/problemsets/acmsguru/submit) **Tags:** special problem :::: ::::warning **Tóm tắt:** - Nhập vào 2 số rồi in ra tổng **Ví dụ:** | Input | Output | | ----- | ------ | | 5 3 | 8 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int a, b; cin >> a >> b; // Nhập vào 2 số cout << a + b << endl; // In ra tổng return 0; } ``` ::: :::: ::::success > Personal Comment: ![image](https://hackmd.io/_uploads/rkQEHaJBlx.png) :::: ::::: :::::spoiler Codeforces ACMSGURU 123 - The sum ::::info **Link:** [123_CF_ACM](https://codeforces.com/problemsets/acmsguru/problem/99999/123) **Tags:** special problem **Author:** Paul "Stingray" Komkoff, Victor G. Samoilov **Resource:** 5th Southern Subregional Contest. Saratov 2002 **Date:** 10/10/2002 (Info from Codeforces) :::: ::::warning **Tóm tắt:** - Tính tổng từ số thứ 1 đến n trong [dãy Fibonacci](https://en.wikipedia.org/wiki/Fibonacci_sequence) **Ví dụ:** | Input | Output | | ----- | ------ | | 5 | 12 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> #include <vector> using namespace std; int main() { int n; // Tạo biến n cin >> n; if (n < 1) return 0; // EdgeCaseTM: nếu n nhỏ hơn 1 thì không tính tổng vector<int> f(n); // Lưu các số trong dãy fibonacci f[0] = 1; // Số đầu tiên trong dãy là 1 f[1] = 1; // Số thứ hai trong dãy là 1 for (int i = 2; i < n; i++) { // Dùng DP để tính các số tiếp theo trong dãy f[i] = f[i - 1] + f[i - 2]; // Số hiện tại = tổng 2 số trước đó trong dãy } cout << accumulate(f.begin(), f.end(), 0) << endl; // In ra tổng return 0; } ``` ::: :::: ::::success > Personal Comment: Dynamic Programming ![image](https://hackmd.io/_uploads/B1yQiRgBxl.png) :::: ::::: ### VNOJ Online Judge (VNOI) :::::spoiler VNOJ Online Judge post - A cộng B ::::info **Link:** [post_VNOI](https://oj.vnoi.info/problem/post) **Problem type:** Ad hoc (không thuộc thể loại nào) **Category:** ICPC :::: ::::warning **Tóm tắt:** - Cộng 2 số A và B **Ví dụ:** | Input | Output | | ----- | ------ | | 3 4 | 7 | :::: ::::danger **Code (+ Giải thích):** :::spoiler C++ ```cpp= #include <iostream> using namespace std; int main() { int a, b; cin >> a >> b; // Nhập vào 2 số cout << a + b << endl; // In ra tổng 2 số return 0; } ``` ::: :::: ::::success > Personal Comment: VNOI comment section is crazy :pray: ![image](https://hackmd.io/_uploads/rypiYwXSgg.png) :::: ::::: ## R0P2 - 100 Words in Competitive Coding | English | Tiếng Việt | Giải nghĩa | Ví dụ | | ---------------------------------------- | ------------------------------ | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | Programmer | Lập trình viên | Người lập trình ra sản phẩm | Tôi là một lập trình viên (fr fr) | | Project | Dự án | Chứa các sources (video, audio, code, config, ...) có cấu trúc và mục đích riêng tùy thuộc vào dự án đó đang nằm ở vị trí nào ở đâu | Một dự án cpp trong Codeblocks có những file code, file config của complier, file exe, file config của Codeblocks | | Integrated Development Environment (IDE) | Môi trường tích hợp phát triển | Một ứng dụng cung cấp giao diện và môi trường tiện lợi để lập trình, có thể đi kèm với complier và debugger luôn. Một số có thể open-source cho phép người dùng tùy chỉnh lại code nguồn theo ý mình, một số có các plugin, AI hỗ trợ trong việc lập trình | VSCode, Code::Blocks, Visual Studio, CLion, DevC++, ... | | Time Limit Exceeded (TLE) | Vượt quá giới hạn thời gian | Vượt qua mức tối đa thời gian chạy mà Judge cho | Vòng lập bị kẹt (vô hạn) | | All Completed (AC) | Hoàn thành tất cả | Đưa ra đáp án đúng tất cả test case mà bài cho | Hoàn thành 100% test case trong Codeforces thì AC | <br><br><br>Copyright HAINAMLION(C)