**Thử thách 100 bài CF**
[toc]
# Codeforces
## 1. Way too long words
https://codeforces.com/problemset/problem/71/A
Tóm tắt đề: từ nào <= 10 kí tự thì in full từ, còn > mười kí tự thì nén theo dạng kí tự 1 + (số kí tự - 2) + kí tự cuối (tag strings)
Hướng giải: check size của từ đề cho, nếu <=10 thì in full string còn trên 10 kí tự thì nén theo cấu trúc đề yêu cầu. Ví dụ:
- word, size là 4 => in word
- localization, size là 12 => in l10n
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
string s; cin >> s;
if(s.size() <= 10) cout << s << "\n";
else cout << s[0] << s.size() - 2 << s[s.size()-1] << "\n";
}
return 0;
}
```
## 2. Team
https://codeforces.com/problemset/problem/231/A
Tóm tắt đề: với mỗi số từ 1 tới n cho nhập ba số a,b,c, nếu a + b + c >= 2 thì hợp lệ, đếm số bộ ba a + b + c hợp lệ (tag brute force, greedy)
Hướng giải: mỗi i từ 1 tới n cho nhập a,b,c là số 1 hoặc 0 để thể hiện rằng mấy bạn đó biết làm hay ko, nếu tổng a + b + c ở bước đó là >=2 thì bài đó các bạn làm đc, ++ vào biến đếm. Ví dụ:
3
1 1 0
1 1 1
1 0 0
Ở bước i = 1, ta có a = 1 b = 1 c = 0 => a + b = 2 >= 2 => hợp lệ
Ta có i = 1 và i = 2 hợp lệ => kết quả là 2
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int a,b,c;
int cnt = 0;
for(int i = 0; i < n; i++) {
cin >> a >> b >> c;
if(a + b + c >= 2) cnt++;
}
cout << cnt;
return 0;
}
```
## 3. Bit++
https://codeforces.com/problemset/problem/282/A
Tóm tắt đề: cho số x ban đầu = 0, mỗi bước từ 1 tới n nhập vào 1 string, nếu string đó là ++ X hoặc X++ thì tăng X lên 1 đơn vị, nếu khác 2 cái trên thì giảm 1 đơn vị (tag implementation)
Hướng giải: như đã nêu trên. Ví dụ:
2
X++
--X
X ban đầu là 0, bước đầu ++ => 0 + 1 = 1, bước sau khác ++ => 1 - 1 = 0;
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int x = 0;
string a[n+1];
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(a[i] == "++X" || a[i] == "X++") x++;
else x--;
}
cout << x;
return 0;
}
```
## 4. Next round
https://codeforces.com/problemset/problem/158/A
Tóm tắt đề: cho dãy N phần tử giảm dần, đếm số phần tử vừa dương vừa lớn hơn bằng phần tử vị trí k (tag special problem, implementation)
Hướng giải: tạo 1 biến lưu giá trị ở vị trí k r duyệt for từ 1 tới n, mỗi bước nếu a[i] dương và a[i] >= a[k] thì cnt++. Ví dụ:
8 5
10 9 8 7 7 7 5 5
a[5] = 7, duyệt qua ta thấy có 6 số >=7 => đáp án là 6
``` cpp
#include <iostream>
using namespace std;
int main() {
int n,k; cin >> n >> k;
int a[n+1];
for(int i = 1; i <= n; i++) cin >> a[i];
int kthplace = a[k];
int cnt = 0;
for(int i = 1; i <= n; i++) {
if(a[i] >= kthplace && a[i] > 0) cnt++;
}
cout << cnt;
return 0;
}
```
## 5. Domino piling
https://codeforces.com/problemset/problem/50/A
Tóm tắt đề: Cho hình chữ nhật có 2 cạnh n và m, tính số hình chữ nhật 2x1 tối đa fill đc hcn đó (tag greedy,math)
Hướng giải: Lấy diện tích (n x m)/(2 x 1). Ví dụ:
2 4
2x4/2x1 = 2 => fill đc 2 hình chữ nhật size 2x1 vào hcn 24
``` cpp
#include <iostream>
using namespace std;
int main() {
int n,m; cin >> n >> m;
int s = n * m;
cout << s/2;
return 0;
}
```
## 6. Beautiful Matrix
https://codeforces.com/problemset/problem/263/A
Tóm tắt đề: cho 1 matrix [5][5] có 1 số 1 và phần còn lại là số 0, đếm số bước cần để dịch ô có số 1 vào vị trí [3][3] (tag implementation)
Hướng giải: đếm tổng khoảng cách từ ô 3 tới ô i và ô 3 tới j
Ví dụ:
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
i là 2 => abs(3-2) = 1
j là 5 => abs(3-5) = 2
=> abs(i) + abs(j) = 3
``` cpp
#include <iostream>
using namespace std;
int main() {
int a[6][6];
for(int i = 1; i <= 5; i++) {
for(int j = 1; j <= 5; j++) {
cin >> a[i][j];
if(a[i][j] == 1) {
cout << abs(3-i) + abs(3-j);
return 0;
}
}
}
return 0;
}
```
## 7. Petya and Strings
https://codeforces.com/problemset/problem/112/A
Tóm tắt đề: so sánh 2 xâu kí tự ko phân biệt hoa thường (tag implementation,strings)
Hướng giải: đổi cả 2 xâu về thường hết r so sánh, nếu xâu đầu bé hơn xâu 2 thì in ra -1, nếu xâu đầu = xâu 2 thì in ra 0, nếu xâu đầu lớn hơn xâu 2 thì in ra 1. Ví dụ:
- aaaa và aaaA, sau khi đổi cả 2 về thường thì thành aaaa và aaaa, giống nhau => in ra 0
``` cpp
#include <iostream>
using namespace std;
int main() {
string s,se;
cin >> s >> se;
for(int i = 0; i < s.size(); i++) {
s[i] = tolower(s[i]);
se[i] = tolower(se[i]);
}
if(s > se) {
cout << 1;
return 0;
}
if(s < se) {
cout << -1;
return 0;
}
if(s == se) {
cout << 0;
return 0;
}
}
```
## 8. Helpful Maths
https://codeforces.com/problemset/problem/339/A
Tóm tắt đề: cho 1 string là phép cộng, sắp xếp các số trong phép cộng đó tăng dần (tag greddy,implementation,sortings,strings)
Hướng giải: push các số trong phép cộng vào 1 vector r dùng hàm sort trong thư viện algorithm để sắp xếp vector đó lại r đổi lại vào string. Ví dụ:
3+2+1 thì push vào vector {3,2,1} r sort thành {1,2,3} r vào string lại là 1+2+3. Code mẫu như sau:
``` cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
string s; cin >> s;
vector<char> v;
for(int i = 0; i < s.size(); i+=2) {
v.push_back(s[i]);
}
sort(v.begin(), v.end());
for(int i = 0; i < s.size(); i+=2) {
s[i] = v[i/2];
}
cout << s;
return 0;
}
```
## 9. Boy or girl
https://codeforces.com/problemset/problem/236/A
Tóm tắt đề: cho 1 xâu nếu số kí tự phân biệt trong xâu đó là chẵn thì in ra "CHAT WITH HER!", lẻ thì in ra "IGNORE HIM!" (tag brute force,implementations,strings)
Hướng giải: duyệt qua các phần tử trong string và insert vào 1 set r check size của set đó % 2 == 0 hay == 1;
Ví dụ:
wjmzbmr thì set sẽ có {w,j,m,z,b,r} => 6 kí tự => in "CHAT WITH HER!";
``` cpp
#include <iostream>
#include <string>
#include <set>
using namespace std;
int main() {
string s; cin >> s;
set<int> se;
for(int i = 0; i < s.size(); i++) {
se.insert(s[i]);
}
int n = se.size();
if(n % 2 == 0) {
cout << "CHAT WITH HER!";
return 0;
}
else {
cout << "IGNORE HIM!";
return 0;
}
}
```
## 10. Watermelon
https://codeforces.com/problemset/problem/4/A
Tóm tắt đề: Cho số W, hỏi số W có thể được tạo thành từ tổng 2 số chẵn sao cho 2 số đều dương hay ko? (tag brute force, math)
Hướng giải: Check xem số W có chẵn hay ko, nếu chẵn thì ok còn ko chẵn thì ko ok vì số lẻ ko thể tạo thành bởi 2 số chẵn. Nhưng có trường hợp đặc biệt khi số chẵn bằng 2 thì cũng ko được vì 2 chỉ có thể tạo thành từ 1 + 1.
Ví dụ: 4 % 2 == 0 => cout << "YES";
``` cpp
#include <iostream>
using namespace std;
int w;
int main() {
cin >> w;
if(w == 2) {
cout << "NO";
return 0;
}
if(w % 2 == 0) {
cout << "YES";
return 0;
}
if(w % 2 == 1) {
cout << "NO";
return 0;
}
}
```
## 11. Word Capitalization
https://codeforces.com/problemset/problem/281/A
Tóm tắt đề: cho một string S, chuẩn hóa nó thành kí tự đầu viết hoa còn các kí tự sau giữ nguyên (tag implementation, string)
Hướng giải: dùng hàm toupper cho s[0]
Ví dụ:
ApPle, vì s[0] đã là upper sẵn rồi nên dùng hàm toupper nó vẫn là ApPle
``` cpp
#include <iostream>
#include <string>
using namespace std;
int main() {
string s; cin >> s;
s[0] = toupper(s[0]);
cout << s;
return 0;
}
```
## 12. Bear and Big brother
https://codeforces.com/problemset/problem/791/A
Tóm tắt đề: cho 2 số a và b sao cho a <= b, mỗi lần a tăng gấp ba thì b tăng gấp đôi, hỏi sau bao nhiêu lần thì a lớn hơn hẳn b?
Hướng giải: dùng vòng lặp while và 1 biến cnt, mỗi khi a còn <= b thì cnt++; a*=3; b*=2
Ví dụ:
a = 4, b = 7 thì a.3^2 > 7x2^2 => càn 2 lần
``` cpp
#include <iostream>
using namespace std;
int main() {
int a,b; cin >> a >> b;
int cnt = 0;
while(a <= b) {
cnt++;
a*=3;
b*=2;
}
cout << cnt;
return 0;
}
```
## 13. Stones on the Table
https://codeforces.com/problemset/problem/266/A
Tóm tắt đề: cho 1 string s có n kí tự, hỏi cần xóa ít nhất bao nhiêu kí tự để các kí tự liền kề nhau trong string ko giống nhau (tag implementation)
Hướng giải: duyệt for các kí tự từ đầu tới kí tự áp chót trong string check xem s[i] có == s[i+1] hay ko, nếu có thì tăng biến đếm. Ví dụ:
5 RRRRR. Duyệt từ s[0] tới s[3] ta thấy s[0] == s[1], s[1] == s[2], s[2] == s[3], s[3] == s[4], vậy kết quả là 4
``` cpp
#include <iostream>
#include <string>
using namespace std;
int main() {
int n; cin >> n;
string s; cin >> s;
int cnt = 0;
for(int i = 0; i < n - 1; i++) {
if(s[i] == s[i+1]) cnt++;
}
cout << cnt;
return 0;
}
```
## 14. Elephant
https://codeforces.com/problemset/problem/617/A
Tóm tắt đề: nhà Elephant ở vị trí 0 và bạn muốn mời 1 bạn nhà ở vị trí x tới chơi, biết 1 bước có thể đi được từ 1 tới 5 vị trí, hỏi bạn nhà ở vị trí x cần đi ít nhất bao nhiêu bước để tới nhà bạn Elephant? (tag Math)
Hướng giải:
Check xem x có chia hết cho 5 hay ko nếu có thì in x/5 còn ko thì in x/5+1. Ví dụ:
13 => ko chia hết cho 5 => in 13/5+1 = 3
```cpp=
#include <iostream>
using namespace std;
int main() {
int x; cin >> x;
if(x % 5 == 0) {
cout << x/5;
return 0;
}
else {
cout << x/5 + 1;
return 0;
}
return 0;
}
```
## 15. Soldier and Bananas
https://codeforces.com/problemset/problem/546/A
Tóm tắt đề: có n số tiền, 1 số k và w quả chuối, quả chuối thứ i có giá i x k, hỏi cần mượn bao nhiêu tiền để mua được w quả chuối đó (tag brute force,implementation,math)
Hướng giải: duyệt for từ 1 tới w, mỗi bước cộng vào biến sum 1 lượng i x k,rồi check xem biến sum có lớn hơn n hay ko, nếu có thì in ra sum - n, nếu ko thì in ra 0. Ví dụ
3 17 4. 3x1+3x2+3x3+3x4=30 => sum > n => sum - n = 17;
``` cpp
#include <iostream>
using namespace std;
int main() {
int k,n,w; cin >> k >> n >> w;
int sum = 0;
for(int i = 1; i <= w; i++) {
sum+=k*i;
}
if(n >= sum) {
cout << 0;
return 0;
}
else {
cout << sum - n;
return 0;
}
}
```
## 16. Word
https://codeforces.com/problemset/problem/59/A
Tóm tắt đề: cho một xâu s, chuyển tất cả các kí tự của xâu s về dạng upper hoặc lower sao cho số kí tự cần chuyển đổi là ít nhất (tag implementation,strings)
Hướng giải: đếm số kí tự upper là lower xem loại nào nhiều hơn, nếu lower ít hơn thì đổi tất cả về thành upper và ngược lại, nếu bằng nhau thì về lower (đề bảo thế). Ví dụ:
ViP => số lower là 1, upper là 2 => chuyển tất cả về upper => VIP
``` cpp
#include <iostream>
using namespace std;
int main() {
string s; cin >> s;
int n = s.size();
int cntlower = 0, cntupper = 0;
for(int i = 0; i < n;i++){
if(islower(s[i])) cntlower++;
else cntupper++;
}
if(cntlower >= cntupper) {
for(int i = 0; i < n; i++) {
s[i] = tolower(s[i]);
}
}
else {
for(int i = 0; i < n; i++) {
s[i] = toupper(s[i]);
}
}
cout << s;
return 0;
}
```
## 17. Wrong Subtraction
https://codeforces.com/problemset/problem/977/A
Tóm tắt đề: cho số n và k lần thay đổi, mỗi lần thay đổi nếu tận cùng của n là 0 thì chia 10 đi, còn tận cùng khác 0 thì -1, tìm số n sau k lần thay đổi (tag implementation)
Hướng giải: tạo 1 vòng lặp chạy k lần mỗi lần check xem tận cùng của n là bao nhiêu (n % 10 = ?) rồi làm theo yêu cầu. Ví dụ:
512 4
k = 4,n % 10 == 2 => 512 - 1 = 511
k = 3, n % 10 == 1 => 511 - 1 = 510
k = 2, n % 10 == 0 => 510/=10 = 51
k = 1, n % 10 == 1 => 51 - 1 = 50;
k = 0 => end chương trình
``` cpp
#include <iostream>
using namespace std;
int main() {
int n,k; cin >> n >> k;
while(k--) {
if(n % 10 != 0) n--;
else n /= 10;
}
cout << n;
return 0;
}
```
## 18. Nearly Lucky Number
https://codeforces.com/problemset/problem/110/A
Tóm tắt đề: số may mắn là số chỉ chứa các digit 4 hoặc 7, số gần may mắn là số mà số số may mắn của nó là số may mắn, hỏi n có phải số gần may mắn hay ko (tag implementation)
Hướng giải: nhập số n dưới dạng string r duyệt qua từng kí tự của n xem có phải 4 hoặc 7 hay ko, nếu có thì cộng vào biến đếm. Sau khi duyệt xong từng char xong string n thì mình duyệt kiểm tra biến đếm có phải sô may mắn hay ko. Ví dụ:
40047 => biến đếm là 3 => ko phải số may mắn => in NO
``` cpp
#include <iostream>
using namespace std;
int main() {
string n; cin >> n;
int size = n.size();
int cnt = 0;
for(int i = 0; i < size; i++) {
if(n[i] == '4' || n[i] == '7') cnt++;
}
if(cnt == 0) {
cout << "NO";
return 0;
}
while(cnt!=0) {
if(cnt % 10 != 4 && cnt % 10 != 7) {
cout << "NO";
return 0;
}
cnt /= 10;
}
cout << "YES";
return 0;
}
```
## 19. Anton and Danik
https://codeforces.com/problemset/problem/734/A
Tóm tắt đề: nhập xâu N, nếu trong N số kí tự A nhiều hơn kí tự D thì in Anton, D nhiều hơn A thì in Danik, bằng nhau thì in Friendship (tag implementation,strings)
Hướng giải: như trên. Ví dụ:
ADAAAA => A = 5, D = 1 => In Anton
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
string s; cin >> s;
int counta = 0, countd = 0;
for(int i = 0; i < n; i++) {
if(s[i] == 'A') counta++;
else countd++;
}
if(counta > countd) cout << "Anton";
if(counta == countd) cout << "Friendship";
if(counta < countd) cout << "Danik";
return 0;
}
```
## 20. Translation
https://codeforces.com/problemset/problem/41/A
Tóm tắt đề: cho xâu s và xâu t, check xem xâu t có phải ngược lại của xâu s hay ko
Hướng giải: đầu tiên ta check size của 2 xâu này, nếu khác nhau thì cout << "NO" thẳng luôn. Sau đó nếu 2 xâu này độ dài bằng nhau thì ta duyệt for i = 0 tới i < s.size(), mỗi bước ta so sánh s[i] và t[s.size()-i-1], nếu có cặp nào khác nhau thì cout << "NO" luôn, nếu không có cặp nào khác nhau thì sau vòng lặp in ra "YES". Ví dụ:
code và edoc
s[0] == t[4-0-1], s[1] == t[4-1-1], s[2] == t[4-2-1], s[3] == t[4-3-1] => in ra "YES"
``` cpp
#include <iostream>
using namespace std;
int main() {
string s,t; cin >> s >> t;
int n = s.size();
int n2 = t.size();
if(n!=n2) {
cout << "NO";
return 0;
}
for(int i = 0; i < n; i++) {
if(s[i] != t[n-i-1]) {
cout << "NO";
return 0;
}
}
cout << "YES";
return 0;
}
```
## 21. Vanya and Fence
https://codeforces.com/problemset/problem/677/A
Tóm tắt đề: cho dãy a có n phần tử, mỗi phần tử a[i] nếu nhỏ hơn hoặc bằng h thì tốn 1 lượng width là 1, nếu lớn hơn h thì tốn 1 lượng width là 2, tính tổng lượng width mà dãy a cần (tag implementation)
Hướng giải: duyệt qua các phần tử trong dãy a, nếu nó <= h thì width++, nếu > h thì width+=2. Ví dụ:
3 7
4 5 14
a[0] = 4 <= 7 => width = 0 + 1 = 1
a[1] = 5 <= 7 => width = 1 + 1 = 2
a[2] = 14 > 7 => width = 2 + 2 = 4
``` cpp
#include <iostream>
using namespace std;
int main() {
int n,h; cin >> n >> h;
int a[1000];
int width = 0;
for(int i = 0; i < n; i++) {
cin >> a[i];
if(a[i] <= h) width++;
else width+=2;
}
cout << width;
return 0;
}
```
## 22. Tram
https://codeforces.com/problemset/problem/116/A
Tóm tắt đề: 1 chiếc tàu ban đầu có số lượng khách là 0, có 2 dãy a và b biểu thị số khách xuống và lên tàu ở mỗi trạm, số khách xuống tàu tại trạm thứ i là a[i] và số khách lên tàu là b[i]. Hỏi sức chứa ít nhất của tàu cần để chứa hành khách là bao nhiêu?
Hướng giải: ta thấy để tìm sức chứa ít nhất chiếc tàu cần thì ta chỉ cần tìm số lượng hành khách trên tàu nhiều nhất. Vậy ta tạo 1 biến now tức số lượng hành khách ban đầu là 0, xong duyệt for n lần mỗi lần cập nhật biến now-=a[i]+=b[i], r lấy max của biến now. Ví dụ:
4
0 3
2 5
4 2
4 0
i = 0 => now - a[i] + b[i] = 0 - 0 + 3 = 3
i = 1 = > now - a[i] + b[i] = 3 - 2 + 5 = 6
i = 2 => now - a[i] + b[i] = 6 - 4 + 2 = 4
i = 3 => now - a[i] + b[i] = 4 - 4 + 0 = 0
``` cpp
#include <iostream>
using namespace std;
int main() {
int now = 0;
int ans = 0;
int n; cin >> n;
int a[n],b[n];
for(int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
now = now - a[i] + b[i];
ans = max(ans,now);
}
cout << ans;
return 0;
}
```
## 23. In Search of an Easy Problem
https://codeforces.com/problemset/problem/1030/A
Tóm tắt đề: cho một dãy n số gồm 0 và 1, nếu có bất kì số 1 nào thì in ra HARD, nếu cả dãy là 0 thì in ra EASY (tag implementation)
Hướng giải: duyệt qua cả dãy nếu phát hiện phần tử nào là 1 thì in ra HARD, còn ko thì in ra EASY. Ví dụ:
3
0 0 1
Phát hiện thấy số 1 => in ra HARD
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int a[n];
for(int i = 0; i < n; i++) {
cin >> a[i];
if(a[i] == 1) {
cout << "HARD";
return 0;
}
}
cout << "EASY";
return 0;
}
```
## 24. George and Accommodation
https://codeforces.com/problemset/problem/467/A
Tóm tắt đề: cho hai mảng p và q có n phần tử, đếm số cặp p[i] > q[i] >= 2 (tag implementation)
Hướng giải: như trên. Ví dụ:
3
1 1
2 2
3 3
1 - 1 < 2, 2 - 2 < 2, 3 - 3 < 2 => in ra 0
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int p[n], q[n];
int cnt = 0;
for(int i = 0; i < n; i++) {
cin >> p[i] >> q[i];
if(q[i] - p[i] >= 2) cnt++;
}
cout << cnt;
return 0;
}
```
## 25. Magnets
https://codeforces.com/problemset/problem/344/A
Tóm tắt đề: cho một dãy a gồm các số 10 và 01, các số có chữ số cuối cùng khác chữ số đầu tiên của kí tự sau thì có thể ghép thành 1 nhóm. Đếm số nhóm ghép được từ dãy đó? (tag implementation)
Hướng giải: set biến cnt ban đầu = 1 do luôn có ít nhất 1 nhóm. Xét từng phần tử xem nếu a[i] == 10 và a[i+1] == 01 hoặc a[i] == 01 và a[i+1] == 10 thì ++cnt. Ví dụ:
6
10 10 10 01 10 10
Xét đến a[2] thấy a[2] == 10 và a[2+1] == 01 => cnt = 1 + 1 = 2
Xét đến a[3] thấy a[4] == 01 và a[3+1] == 10 => cnt = 2 + 1 = 3
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int a[n];
for(int i = 0; i < n; i++) {
cin >> a[i];
}
int cnt = 1;
for(int i = 0; i < n; i++) {
if(a[i] == 10 && a[i+1] == 01) cnt++;
else if(a[i] == 01 && a[i+1] == 10) cnt++;
}
cout << cnt;
return 0;
}
```
## 26. Presents
https://codeforces.com/problemset/problem/136/A
Tóm tắt đề: cho dãy a có n phần tử, phần tử a[i] thể hiện người mà người thứ i tặng quà cho. Hãy in ra từng người đã được tặng quà bởi người nào? (tag implementation)
Hướng giải: tạo một mảng ans, duyệt từng phần tử trong a rồi cập nhật ans[a[i]] = i, công thức này có vì a[i] lưu người được tặng còn i là người tặng (lưu dãy a từ 1 tới n). Ví dụ:
4
2 3 4 1
duyệt qua a[1] => ans[2] = 1;
duyệt qua a[2] = > ans[3] = 2;
duyệt qua a[3] = > ans[4] = 3;
duyệt qua a[4] = > ans[1] = 4;
=> ans = {4,1,2,3}
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int a[n+1];
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans[n];
for(int i = 1; i <= n; i++) {
ans[a[i]] = i;
}
for(int i = 1; i <= n; i++) {
cout << ans[i] << " ";
}
return 0;
}
```
## 27. Is your horseshoe on the other hoof?
https://codeforces.com/problemset/problem/228/A
Tóm tắt đề: cho 1 mảng a có 4 phần tử, tìm số phần tử cần thay đổi sao cho 4 phần tử đó đều khác nhau (tag implementation)
Hướng giải: insert các phần tử của mảng a vào một set, rồi lấy 4 - đi size của set đó. Ví dụ:
1 7 3 3
Khi insert vào set ta thấy size của set đó là 3 xong lấy 4 - 3 ra 1
``` cpp
#include <iostream>
#include <set>
using namespace std;
int main() {
int a[4];
for(int i = 0; i < 4; i++) {
cin >> a[i];
}
set<int> s;
for(int i = 0; i < 4; i++) {
s.insert(a[i]);
}
cout << 4 - s.size();
return 0;
}
```
## 28. Ultra-Fast Mathematician
https://codeforces.com/problemset/problem/61/A
Tóm tắt đề: cho 2 xâu kí tự s và se có cùng số kí tự. Duyệt qua xâu, từng i so sánh s[i] và se[i], nếu giống nhau thì thêm 0 vào string ans, ngược lại thì thêm 1 (tag implementation)
Hướng giải như trên.
Ví dụ:
101
011
s[0] != se[0] => ans = "1"
s[1] != se[1] => ans = "11"
s[2] != se[2] => ans = "110"
``` cpp
#include <iostream>
using namespace std;
int main() {
string s,se;
cin >> s >> se;
string ans = "";
for(int i = 0; i < s.size(); i++) {
if(s[i] != se[i]) ans+="1";
else ans+="0";
}
cout << ans;
return 0;
}
```
## 29. Divisibility Problem
https://codeforces.com/problemset/problem/1328/A
Tóm tắt đề: cho hai số a và b, tìm số lần tăng a lên 1 đơn vị ít nhất để a chia hết cho b (tag math)
Hướng giải: ta check xem a % b có == 0 hay ko, nếu có thì in ra 0 luôn còn ngược lại thì in ra b - (a % b) vì a % b ra số dư của a khi chia cho b rồi nên ta cần thêm b - (a % b) nữa để a % b == 0
Ví dụ:
5 3 => a % b == 2 => đáp án là 1
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int a,b; cin >> a >> b;
if(a % b != 0){
cout << b - (a % b) << '\n';
}
else cout << 0 << "\n";
}
return 0;
}
```
## 30. Pangram
https://codeforces.com/problemset/problem/520/A
Tóm tắt đề: cho 1 xâu kí tự, hãy kiểm tra xem xâu đó có chứa đầy đủ 26 kí tự trong bản alphabet hay ko? (tag implementation, strings)
Hướng giải: dùng set để đếm không trùng. Duyệt từng kí tự trong s rồi chuyển kí tự đó về viết thường (tránh set đếm trùng) r insert vào set, sau đó check xem size của set có bằng 26 hay ko, nếu có in ra "YES", ngược lại in "NO". Ví dụ:
toosmallword
Ta thấy sau khi insert vào set thì set có size là 9 => in NO
``` cpp
#include <iostream>
#include <set>
using namespace std;
int main() {
int n; cin >> n;
string s; cin >> s;
set<char> se;
for(int i = 0; i < n; i++) {
s[i] = tolower(s[i]);
se.insert(s[i]);
}
if(se.size() == 26) {
cout << "YES";
return 0;
}
cout << "NO";
return 0;
}
```
## 31. I wanna be the guy
https://codeforces.com/problemset/problem/469/A
Tóm tắt đề: cho số n và dãy a có p phần tử, dãy b có q phần tử, hãy đếm xem số phần tử phân biệt trong dãy a và b có >= n hay ko? (tag implementation, greedy)
Hướng giải: duyệt 2 vòng for qua 2 dãy r insert vào set sau đó check size, nếu size >= n thì in ra "I become the guy".
còn ngược lại thì in "Oh, my keyboard!". Ví dụ:
4
3 1 2 3
2 2 4
Sau khi duyệt cả 2 vòng for thì size của set là 4 => in I become the guy.
``` cpp
#include <iostream>
#include <set>
using namespace std;
int main() {
int n; cin >> n;
int p; cin >> p;
int a[p];
for(int i = 0; i < p ; i++) {
cin >> a[i];
}
int q; cin >> q;
int b[q];
for(int i = 0; i < q; i++) {
cin >> b[i];
}
set<int> se;
for(int i = 0; i < p; i++) se.insert(a[i]);
for(int i = 0; i < q; i++) se.insert(b[i]);
if(se.size() >= n) cout << "I become the guy.";
else cout << "Oh, my keyboard!";
return 0;
}
```
## 32. Hit the Lottery
https://codeforces.com/problemset/problem/996/A
Tóm tắt đề: cho một số tiền n, có thể rút các tờ tiền có mệnh giá là {1,5,10,20,100}. Hỏi số tiền tối thiểu nhận được sau khi rút là bao nhiêu (tag dp,greedy)
Hướng giải: tạo một mảng a lưu các giá trị {1,5,10,20,100}. Ta nhận thấy để có số tờ tiền tối thiểu thì ta phải chọn những tờ tiền có mệnh giá cao nhất. Vậy ta sẽ tạo 1 biến count duyệt từ cuối mảng về đầu, mỗi bước count+= n/a[i], tức số tờ tiền trị giá a[i] tối đa có thể lấy đc, sau đó n %= a[i], lấy phần dư còn lại sau khi chia a[i] ở bước trên.
Ví dụ:
125
count+=125/100 = 1, n%100=100 = 25
count+=25/20 = 1 + 1 = 2, n%=20 = 5
count+= 5/10 = 2 + 0 = 2, n%=10 = 5
count+=5/5 = 2 + 1 = 3, n%=5 = 0
count+=0/5 = 0 + 3 = 3, n%=5 = 0
=> đáp án là 3
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int a[5] = {1,5,10,20,100};
int count = 0;
for(int i = 4; i >= 0; i--) {
count += n/a[i];
n %= a[i];
}
cout << count;
return 0;
}
```
## 33. Candies and Two Sisters
https://codeforces.com/problemset/problem/1335/A
Tóm tắt đề: cho số n, có bao nhiêu cách chia số n thành 2 phần a và b sao cho a > b (tag math)
Hướng giải: ta check xem n chẵn hay lẻ, nếu lẻ thì in ra n/2 vì số cách chọn a là từ n/2+1 tới n-1, mà số lẻ thì khi chia 2 lấy phần nguyên sẽ bị hụt mất 1 phần nên số tiếp theo sẽ được lấy luôn, còn với số chẵn thì ta in n/2-1 vì khi số chẵn chia 2 sẽ ra 1 số bằng 1/2 số chẵn, lúc đó ko thể lấy a > b được, nên ta lấy từ n/2+1 tới n-1, mà số chẵn thì /2 ko bị hụt nên ta phải -1. Ví dụ:
7
7 / 2 == 1 => 7/2 = 3 => đáp án là 3
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
if(n % 2 == 1) {
cout << n/2 << '\n';
}
else {
cout << n/2 - 1 << '\n';
}
}
return 0;
}
```
## 34. Anton and Letters
https://codeforces.com/problemset/problem/443/A
Tóm tắt đề: cho một tập hợp gồm các kí tự chữ và các dấu {} , theo quy tắc ví dụ như {a, b, c}; đếm số kí tự chữ cái phân biệt trong tập hợp đó (tag constructive algorithms, implementation)
Hướng giải: đầu tiên ta check xem size của string đó nếu <3 thì in thẳng 0 luôn vì <3 thì ko thể chứa kí tự. Sau đó ta duyệt từ i = 3 i+=3 mỗi bước ta insert kí tự vị trí i của xâu đề cho vào set, sau đó in ra size của set. Ví dụ:
{a, b, c}
i = 1 => insert a
i = 4 => insert b
i = 7 => insert c
Vậy size của set là 3
``` cpp
#include <iostream>
#include <set>
using namespace std;
int main() {
string s; getline(cin,s);
int n = s.size();
set<int> se;
if(n < 3) {
cout << 0;
return 0;
}
for(int i = 1; i < n; i+=3) {
se.insert(s[i]);
}
cout << se.size();
return 0;
}
```
## 35. Division
https://codeforces.com/problemset/problem/1669/A
Tóm tắt đề: cho một số rating, in ra theo quy định sau
For Division 1: 1900≤rating
For Division 2: 1600≤rating≤1899
For Division 3: 1400≤rating≤1599
For Division 4: rating≤1399
Hướng giải: như trên. Ví dụ:
1299 <= 1399 => in Division 4
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
if(1900 <= n) cout << "Division 1" << '\n';
else if (1899 >= n && n >= 1600) cout << "Division 2" << '\n';
else if (1599 >= n && n >= 1400) cout << "Division 3" << '\n';
else cout << "Division 4" << '\n';
}
return 0;
}
```
## 36. Black Square
https://codeforces.com/problemset/problem/431/A
Tóm tắt đề: cho một mảng a lưu năng lượng tối thiểu cần dùng để chạm vào phần tử thứ i. Cho một string bao gồm các phần tử cần chạm, tính tổng các phần tử cần chạm đó?
Hướng giải: duyệt qua từng phần tử cần chạm r chuyển nó về idx bằng cách - '0' rồi lấy giá trị a[idx] + vào biến đếm. Ví dụ:
1 2 3 4
1 2 3
Cộng vào ta được đáp án là 6
``` cpp
#include <iostream>
using namespace std;
int main() {
int a[5];
for(int i = 1; i <= 4; i++) {
cin >> a[i];
}
string s; cin >> s;
int cnt = 0;
for(int i = 0; i < s.size(); i++) {
int now = s[i] - '0';
cnt+=a[now];
}
cout << cnt;
return 0;
}
```
## 37. Lucky?
https://codeforces.com/problemset/problem/1676/A
Tóm tắt đề: cho một xâu có 6 kí tự. Đếm xem tổng 3 kí tự đầu có bằng tổng 3 kí tự cuối không?
Hướng giải: như trên. Ví dụ:
213132
2 + 1 + 3 == 1 + 3 + 2 => in "YES"
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
string s; cin >> s;
int cnt_first = 0;
int cnt_second = 0;
for(int i = 0; i < s.size(); i++) {
if(i < 3) cnt_first+=s[i];
else cnt_second+=s[i];
}
if(cnt_first != cnt_second) {
cout << "NO" << '\n';
}
else {
cout << "YES" << '\n';
}
}
return 0;
}
```
## 38. Sum
https://codeforces.com/problemset/problem/1742/A
Tóm tắt đề: cho ba số a,b,c; check xem có số nào bằng tổng 2 số còn lại ko
Hướng giải: như trên. Ví dụ:
1 3 4
4 = 3 + 1 => in ra yes
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int a,b,c; cin >> a >> b >> c;
if(a == b + c || b == a + c || c == a + b) {
cout << "YES" << '\n';
}
else cout << "NO" << '\n';
}
return 0;
}
```
## 39. A + B Again?
https://codeforces.com/problemset/problem/1999/A
Tóm tắt đề: cho một số có 2 chữ số. Tính tổng các digit trong số đó? (tag implementation, math)
Hướng giải: tạo một biến sum và 1 vòng while chạy khi n != 0, trong vòng while đó thì mỗi lần lặp ta cộng vào sum một lượng n % 10 và giảm n đi 10 lần mỗi bước. Ví dụ
38
n % 10 == 8 => sum = 8, n/=10 = 3
n % 10 == 3 => sum = 8 + 3 == 11, n/=10 = 0 => end while
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
int sum = 0;
while(n!=0) {
sum+= n % 10;
n/=10;
}
cout << sum << '\n';
}
return 0;
}
```
## 40. YES or YES
https://codeforces.com/problemset/problem/1703/A
Tóm tắt đề: check xem 1 xâu có phải là "YES" hay không, không phân biệt hoa thường (tag brute force, implementation, strings)
Hướng giải: chuyển xâu của mình về upper hết r kiểm tra
Ví dụ:
yes => YES => in "YES"
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
string s; cin >> s;
for(int i = 0; i < s.size(); i++) {
s[i] = toupper(s[i]);
}
if(s == "YES") cout << "YES" << '\n';
else cout << "NO" << '\n';
}
return 0;
}
```
## 41. Short sort
https://codeforces.com/problemset/problem/1873/A
Tóm tắt đề: cho một xâu 3 kí tự là hoán vị của abc. Hỏi trong một lần swap 1 kí tự bất kì có thể chuyển xâu đó thành abc ko? (tag brute force, implementation)
Hướng giải: ta thấy để xâu đó trở thành abc thì phải có 1 trong 3 kí tự ở sẵn vị trí đúng, tức s[0] == a hoặc s[1] == b hoặc s[2] == c, có 1 trong 3 điều kiện đó thì là có thể, ko có cả 3 thì ko thể. Ví dụ:
acb
a[0] = 'a' => có thể, đối vs TH này ta swap b vs c lại là đc
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
string s; cin >> s;
if(s[0] == 'a' || s[1] == 'b' || s[2] == 'c') cout << "YES" << '\n';
else cout << "NO" << '\n';
}
return 0;
}
```
## 42. Fashionable Array
https://codeforces.com/problemset/problem/2110/A
Tóm tắt đề: cho một dãy a có n phần tử, dãy đó được gọi là dãy fashionable nếu phần tử nhỏ nhất của dãy đó + phần tử lớn nhất % 2 == 0. Hãy tìm số số cần delete ít nhất để cho mảng a thành fashionbale array? (tag sortings, implementation)
Hướng giải: sắp xếp mảng a tăng dần. Tạo 1 biến đếm sau đó duyệt while(phần tử đầu + phần tử cuối % 2 != 0), ta check nếu xóa phần tử cuối thì phần tử đầu + phần tử cuối của dãy mới có chia hết cho 2 hay ko, nếu có thì biến đếm++ r break vòng lặp luôn, ko thì cứ biến đếm++ ,i++. Ví dụ:
1 3 1 => sort thành 1 1 3, ta duyệt while thấy ngay 1 + 3 == 0 nên vòng while ko chạy đc => in ra 0
``` cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
int a[n];
for(int i = 0; i < n; i++) cin >> a[i];
sort(a,a+n);
int i = 0;
int cnt = 0;
while((a[i] + a[n-1]) % 2 != 0 && i < n) {
if((a[n-i-2] + a[i]) % 2 == 0) {
cnt++;
break;
}
else {
i++;
cnt++;
}
}
cout << cnt << '\n';
}
return 0;
}
```
## 43. Plus or Minus
https://codeforces.com/problemset/problem/1807/A
Tóm tắt đề: cho ba số a,b,c. Check xem a + b = c hay a - b = c (tag implementation)
Hướng giải: cứ làm thôi :v
Ví dụ:
1 2 3
1 + 2 == 3 => in '+'
``` cpp
#include <iostream>
using namespace std;
bool check(int a, int b, int c) {
return a + b == c;
}
int main() {
int t; cin >> t;
while(t--) {
int a,b,c; cin >> a >> b >> c;
if(check(a,b,c)) cout << "+" << '\n';
else cout << "-" << '\n';
}
return 0;
}
```
## 44. Marathon
https://codeforces.com/problemset/problem/1692/A
Tóm tắt đề: cho 4 số a,b,c,d. Đếm xem trong 3 số b,c,d có bao nhiêu số lớn hơn a?
Hướng giải: tạo 1 biến đếm r check từng số b c d số nào lớn hơn a thì ++ vào biến đếm. Ví dụ:
2 3 4 1 có 3 và 4 lớn hơn 2 => đáp án là 2
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int a,b,c,d; cin >> a >> b >> c >> d;
int cnt = 0;
if(b > a) cnt++;
if(c > a) cnt++;
if(d > a) cnt++;
cout << cnt << '\n';
}
return 0;
}
```
## 45. Odd One Out
https://codeforces.com/problemset/problem/1915/A
Tóm tắt đề: cho 3 số a,b,c có 2 số bằng nhau và 1 số khác biệt. Hãy in ra số khác biệt đó
Hướng giải: check xem 2 số nào bằng nhau r in ra số còn lại
Ví dụ:
1 1 2
1 = 1 => in 2
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int a,b,c; cin >> a >> b >> c;
if(a == b) cout << c << '\n';
if(a == c) cout << b << '\n';
if(b == c) cout << a << '\n';
}
return 0;
}
```
## 46. Hulk
https://codeforces.com/problemset/problem/705/A
Tóm tắt đề:
Ví dụ cho số 1 thì in ra "I hate it"
Số 2 thì I hate that I love it
Số 3 thì I hate that I love that I hate it
(tag implementation)
Hướng giải: đầu tiên in ra I hate. Sau đó chạy for từ 2 đến n nếu là số chẵn thì in ra "that I love ", nếu lẻ thì in "that I hate ". Ví dụ đã trình bày ở trên
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
cout << "I hate ";
for(int i = 2; i <= n; i++) {
if(i % 2 == 0) {
cout << "that I love ";
}
else {
cout << "that I hate ";
}
}
cout << "it";
return 0;
}
```
## 47. Vanya and Cubes
https://codeforces.com/problemset/problem/492/A
Tóm tắt đề: cho một dãy có hàng 1 là 1 số, hàng 2 là 1 + 2 số, hàng 3 là 1 + 2 + 3 số. Cho số n, hỏi số hàng tối đa có thể tạo được để chứa n số? (tag implementation)
Hướng giải: tạo 1 biến lưu tổng,số hàng và 1 biến để cập nhật hàng tiếp theo. Cho vòng lặp chạy while(sum <= n) thì ++hang r biến cập nhật hàng tiếp theo là now+=hang r sum+=now. Sau vòng lặp sẽ dư ra 1 hàng nên ta sẽ trừ 1 đi.
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int hang = 0;
int sum = 0;
int now = 0;
while(sum <= n) {
hang++;
now = now + hang;
sum = sum + now;
}
cout << hang - 1;
return 0;
}
```
## 48. Mishka and game
https://codeforces.com/problemset/problem/703/A
Tóm tắt đề: cho n cặp a,b. Check coi a > b nhiều hơn hay a < b nhiều hơn hay bằng nhau (tag implementation)
Hướng giải: tạo 2 mảng a,b có n phần tử. Mỗi bước ta cin >> a[i] >> b[i] r cộng cộng biến đếm cái lớn hơn lên. Ví dụ:
3
3 5
2 1
4 2
a[0] < b[0] => cntb++ (cntb = 1)
a[1] > b[1] => cnta++ (cnta = 1)
a[2] > b[2] => cnta++ (cnta = 2)
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int a[n],b[n];
int cnta = 0, cntb = 0;
for(int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
if(a[i] > b[i]) cnta++;
if(b[i] > a[i]) cntb++;
}
if(cnta > cntb) {
cout << "Mishka";
}
if(cntb > cnta) {
cout << "Chris";
}
if(cnta == cntb) {
cout << "Friendship is magic!^^";
}
return 0;
}
```
## 49. Police Recruits
https://codeforces.com/problemset/problem/427/A
Tóm tắt đề: cho n sự kiện bao gồm 2 loại: nếu -1 là có tội phạm, nếu khác -1 là số cảnh sát được tuyển. Hãy đếm số vụ án mà ko được xử lý (tag implementation)
Hướng giải:
Tạo 1 biến count_polices và count_untreated_crimes r duyệt các sự kiện, nếu sự kiện đó là -1 thì cộng số đó vào biến count_polices, còn nếu đó là -1 thì check xem có cảnh sát ko, nếu có thì -- bước polices còn ko có thì ++count_untreated_crimes. Ví dụ
-1 -1 1
-1, cảnh sát = 0 => count_untreated_crimes = 1
-1, cảnh sát = 0 => count_untreated_crimes = 2
1 => count_polices = 1
=> số tội phạm ko đc giải quyết là 2
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int a[n];
int count_polices = 0;
int count_untreated_crimes = 0;
for(int i = 0; i < n; i++) {
cin >> a[i];
if(a[i] != -1) count_polices += a[i];
if(a[i] == -1 && count_polices == 0) count_untreated_crimes++;
if(a[i] == -1 && count_polices != 0) count_polices--;
}
cout << count_untreated_crimes;
return 0;
}
```
## 50. Love story
https://codeforces.com/problemset/problem/1829/A
Tóm tắt đề: cho xâu s, đếm số kí tự ở xâu s khác kí tự tương ứng trong xâu "codeforces" (tag implementation, strings)
Hướng giải: duyệt từng kí tự trong string xong check xem nó có khác kí tự tương ứng trong "codeforces" hay ko, nếu có thì ++ biến đếm;
coolforsez
o != d => cnt = 1
l != e => cnt = 2
s != c => cnt = 3
z != s => cnt = 4
Vậy đáp án bằng 4
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
const string mau = "codeforces";
while(t--) {
string s; cin >> s;
int cnt = 0;
for(int i = 0; i < s.size(); i++) {
if(s[i] != mau[i]) cnt++;
}
cout << cnt << '\n';
}
return 0;
}
```
## 51. New Year and Hurry
https://codeforces.com/problemset/problem/750/A
Tóm tắt đề: có 1 party bắt đầu lúc 0h và 1 contest bắt đầu lúc 20h, contest đó có n bài, và Tom cần k phút để di chuyển tới party, hỏi Tom có thể giải tối đa bao nhiêu bài, biết các bài sắp xếp từ 1 tới n có độ khó i*5 (tag implementation, binary search)
Hướng giải: ta tính thời gian còn lại từ 20h tới 0h, tức 4h. Sau đó ta tạo biến i = 0 , sum = 0 và duyệt while(sum +k <= time_left, r ++i và sum+=i vào, sau đó in ra i - 1. Bài này cũng có thể giải bằng chặt nhị phân cho số lớn hơn). Ví dụ:
3 222
In the first sample, there are 3 problems and Limak needs 222 minutes to get to the party. The three problems require 5, 10 and 15 minutes respectively. Limak can spend 5 + 10 = 15 minutes to solve first two problems. Then, at 20:15 he can leave his house to get to the party at 23:57 (after 222 minutes). In this scenario Limak would solve 2 problems. He doesn't have enough time to solve 3 problems so the answer is 2.
``` cpp
#include <iostream>
using namespace std;
int main() {
int n,k; cin >> n >> k;
int time_left = 4 * 60;
int sum = 0;
if(sum + k > time_left) {
cout << 0;
return 0;
}
int i = 0;
while(sum + k <= time_left && i <= n) {
i++;
sum+= i * 5;
}
cout << i - 1;
return 0;
}
```
## 52. Medium Number
https://codeforces.com/problemset/problem/1760/A
Tóm tắt đề: cho ba số a,b,c. Tìm số ở giữa của ba số đó (tag implementation,sortings)
Hướng giải: tạo vector 3 phần tử r push a,b,c vào vector đó. Sau đó sort vector và in ra phần tử thứ 2. Ví dụ:
3 1 2 => sort thành 1 2 3 => in 2
``` cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
vector<int> a(3);
for(int i = 0; i < 3; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
cout << a[1] << '\n';
}
return 0;
}
```
## 53. I_love_%username%
https://codeforces.com/problemset/problem/155/A
Tóm tắt đề: cho dãy a có n phần tử, đếm số phần tử lớn hơn hoặc nhỏ hơn tất cả phần tử đứng trước nó (tag brute force)
Hướng giải: tạo biến min_before và max_before và gán nó là a[0], sau đó duyệt qua dãy thấy thỏa a[i] > max_before thì cnt++ và cập nhật max_before, tương tự với a[i] < min_before. Ví dụ:
5
100 50 200 150 200
50 < 100 => cnt = 1, min_before = 50
200 > 100 => cnt = 2, max_before = 200
150 và 200 ko thỏa điều kiện nào => cnt = 2
``` cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n;
int a[n];
for(int i = 0; i < n; i++) {
cin >> a[i];
}
int min_before = a[0];
int max_before = a[0];
int cnt = 0;
for(int i = 1; i < n; i++) {
if(a[i] > max_before) {
cnt++;
max_before = a[i];
}
else if (a[i] < min_before) {
cnt++;
min_before = a[i];
}
}
cout << cnt;
return 0;
}
```
## 54. Again Twenty Five!
https://codeforces.com/problemset/problem/630/A
Tóm tắt đề: cho số n, hãy xuất ra 2 số cuối của 5^n. (tag number theory)
Hướng giải: ta nhận thấy 5^1 thì 2 số cuối cùng là 5, còn lớn hơn thì 2 số cuối đều là 25 nên cứ thế mà làm
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
if(n == 1) {
cout << 5;
return 0;
}
else {
cout << 25;
return 0;
}
}
```
## 55. Sereja and Dima
https://codeforces.com/problemset/problem/381/A
Tóm tắt đề: có 2 bạn chơi chơi trò chơi lấy phần tử đầu hoặc cuối của dãy sao cho tổng cuối cùng của mình lớn nhất có thể, hãy xác định tổng của 2 bạn, biết lượt đầu bạn A đi trước (tag greedy,implementation,two pointers)
Hướng giải: push_back tất cả các giá trị vào 1 deque. Sau đó duyệt từ 0 tới n - 1, nếu i % 2 == 0 thì xử lý sum bạn A, i % 2 == 1 thì xử lý sum bạn B, ở mỗi bước ta check xem front hay back của deque hiện tại lớn hơn r cộng vào biến sum 1 lượng đó r pop đi. Ví dụ:
4 1 2 10
i = 0, dq.front() < dq.back() (4 < 10) => sum1 = 10, pop 10 đi
i = 1, dq.front() > dq.back() (4 > 2) => sum2 = 4, pop 4 đi
i = 2, dq.front() < dq.back() (1 < 2) => sum1 = 10 + 2 = 12, pop 2 đi
i = 3, còn 1 phần tử duy nhất là 1 => sum2 = 4 + 1 = 5
=> sum1 = 12, sum2 = 5
``` cpp
#include <iostream>
#include <deque>
using namespace std;
int main() {
int n; cin >> n;
deque<int> dq;
for(int i = 0; i < n; i++) {
int x; cin >> x;
dq.push_back(x);
}
int sum1 = 0;
int sum2 = 0;
for(int i = 0; i < n; i++) {
if(i % 2 == 0) {
if(dq.front() > dq.back()) {
sum1 += dq.front();
dq.pop_front();
}
else {
sum1 += dq.back();
dq.pop_back();
}
}
else {
if(dq.front() > dq.back()) {
sum2 += dq.front();
dq.pop_front();
}
else {
sum2 += dq.back();
dq.pop_back();
}
}
}
cout << sum1 << " " << sum2;
return 0;
}
```
## 56. Creating Words
https://codeforces.com/problemset/problem/1985/A
Tóm tắt đề: cho 2 string, hãy swap kí tự đầu tiên của 2 string r in ra 2 string đó sau khi swap (tag implementation,string)
Hướng giải: tạo 1 biến lưu kí tự đầu tiên của string đầu tiên, r gán kí tự đầu tiên của string đầu tiên là kí tự đầu tiên của string thứ hai, rồi sau đó gán kí tự đầu tiên của string thứ 2 là cái biến lưu kí tự đầu tiên của string đầu tiên kia. Ví dụ:
hot dog
first_0 = s[0] = h
s[0] = t[0] = d;
t[0] = first_0 = h
=> dot hog
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
string first,second; cin >> first >> second;
char first_0 = first[0];
first[0] = second[0];
second[0] = first_0;
cout << first << " " << second << '\n';
}
return 0;
}
```
## 57. Restoring Three Numbers
https://codeforces.com/problemset/problem/1154/A
Tóm tắt đề: cho bốn số là a + b, b + c, a + c và a + b + c, hãy khôi phục lại 3 số a b c theo bất kì thứ tự nào (tag math)
Hướng giải: ta cho nhập 4 số như trên và tìm coi số nào lớn nhất, nếu lớn nhất nó là tổng a + b + c, rồi ta duyệt các số còn lại r lấy lớn nhất trừ ra. Ví dụ:
3 6 5 4 => lớn nhất là 6
6 - 3 = 3
6 - 5 = 1
6 - 4 = 2
=> ba số cần tìm là 3,1,2
``` cpp
#include <iostream>
#include <climits>
using namespace std;
int main() {
int a[4];
int max_value = INT_MIN;
for(int i = 0; i < 4; i++) {
cin >> a[i];
if(a[i] > max_value) max_value = a[i];
}
for(int i = 0; i < 4; i++) {
if(a[i] != max_value) cout << max_value - a[i] << " ";
}
return 0;
}
```
## 58. Codeforces Checking
https://codeforces.com/problemset/problem/1791/A
Tóm tắt đề: cho một kí tự, check xem kí tự đó có trong "codeforces" ko. (tag implementation)
Hướng giải: dùng hàm find để check. Nếu hàm find trả về string::npos thì in NO còn ngược lại in YES.
``` cpp
#include <iostream>
using namespace std;
int main() {
const string s = "codeforces";
int t; cin >> t;
while(t--) {
char c; cin >> c;
size_t check = s.find(c);
if(check == string::npos) cout << "NO\n";
else cout << "YES\n";
}
return 0;
}
```
## 59. Drinks
https://codeforces.com/problemset/problem/200/B
Tóm tắt đề: cho n số, tính trung bình của n số đó, in ra kết quả dưới dạng có 12 số thập phân (tag implementation,math)
Hướng giải: nhập n phần tử và tính tổng n phần tử đó, sau đó chia n ra trung bình
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
int a[n];
int sum = 0;
for(int i = 0; i < n; i++) {
cin >> a[i];
sum+=a[i];
}
double ans = (double) sum / (double) n;
cout << fixed << setprecision(12) << ans;
return 0;
}
```
## 60. Design Tutorial: Learn from Math
https://codeforces.com/problemset/problem/472/A
Tóm tắt đề: hãy biến số n thành tổng 2 hợp số (tag implementation)
Hướng giải: khởi tạo i = 2, từng bước check xem cả i và n - i có phải hợp số (ko ph snt) hay ko, nếu chưa thỏa mãn thì ++i tới khi thỏa mãn
``` cpp
#include <iostream>
#include <cmath>
using namespace std;
bool checkprime(int n) {
if(n <= 1) return 0;
if(n <= 3) return 1;
if(n % 2 == 0 || n % 3 == 0) return 0;
for(int i = 5; i <= sqrt(n); i+=6) {
if(n % i == 0 || n % (i+2) == 0) return 0;
}
return 1;
}
int main() {
int n; cin >> n;
int i = 2;
while(checkprime(i) || checkprime(n-i)) {
i++;
}
cout << i << " " << n-i;
return 0;
}
```
## 61. Holiday off Equality
https://codeforces.com/problemset/problem/758/A
Tóm tắt đề: cho một dãy a có n phần tử, hãy tính tổng số lượng cần thêm vào để tất cả phần tử bằng nhau mà không cần phải giảm phần tử nào (tag implementation, math)
Hướng giải: duyệt qua dãy tìm phần tử lớn nhấn. Sau đó duyệt qua dãy một lần nữa nếu phần tử hiện tại không phải phần tử lớn nhất thì cộng biến sum một lượng max - a[i]. Ví dụ:
0 1 2 3 4
Duyệt qua thấy lớn nhất là 4
i = 0 = > 4 - 0 = 4
i = 1 => 4 + (4 - 1) = 7
i = 2 = > 7 + (4 - 2) = 9
i = 3 => 9 + (4 - 3) = 10
=> Vậy tổng cuối cùng là 10
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int a[n+1];
int find_max;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(i == 1) find_max = a[i];
else {
if(a[i] > find_max) {
find_max = a[i];
}
}
}
int count_sum = 0;
for(int i = 1; i <= n; i++) {
if(a[i] != find_max) {
count_sum += find_max - a[i];
}
}
cout << count_sum;
return 0;
}
```
## 62. Spy detected
https://codeforces.com/problemset/problem/1512/A
Tóm tắt đề: in ra chỉ số của phần tử khác 3 phần tử còn lại trong dãy (tag brute force, implementation)
Hướng giải: duyệt qua mảng r dùng map đếm tần suất. Sau đó duyệt lại thấy phần tử nào mà map của phần tử đó là 1 thì in ra chỉ số. Ví dụ
11 12 11 11
mp[12] = 1 => in ra 2
``` cpp
#include <iostream>
#include <map>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
map<int,int> mp;
int n; cin >> n;
int a[n+1];
for(int i = 1; i <= n; i++) {
cin >> a[i];
mp[a[i]]++;
}
for(int i = 1; i <= n; i++) {
if(mp[a[i]] == 1) {
cout << i << '\n';
break;
}
}
}
return 0;
}
```
## 63. Spell Check
https://codeforces.com/problemset/problem/1722/A
Tóm tắt đề: cho 1 xâu, check xem xâu đó có phải hoán vị của "Timur" hay ko (tag implementation)
Hướng giải: check xem xâu đó có phải 5 kí tự ko, nếu ko thì in thẳng NO, còn nếu 5 kí tự thì sort string r check xem có phải là Timru hay ko, vì Timru là hoán vị của Timur theo thứ tự từ điển
``` cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
string s; cin >> s;
if(n != 5) {
cout << "NO\n";
}
sort(s.begin(),s.end());
if (s == "Timru") {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
return 0;
}
```
## 64. Minimize!
https://codeforces.com/problemset/problem/2009/A
Tóm tắt đề: tìm một số từ khoảng a tới b sao cho (c−a)+(b−c) nhỏ nhất (tag brute force, math)
Hướng giải: duyệt từ a tới b r cập nhật min thôi :v
``` cpp
#include <iostream>
#include <climits>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int a,b; cin >> a >> b;
int ans = INT_MAX;
for(int c = a; c <= b; c++) {
ans = min(ans, (c-a) + (b-c));
}
cout << ans << '\n';
}
return 0;
}
```
## 65. Short Substrings
https://codeforces.com/problemset/problem/1367/A
Tóm tắt đề: một xâu b được tạo thành bởi các xâu con 2 phần tử của xâu a theo thứ tự. Cho xâu b hãy khôi phục lại xâu a (tag implementation,string)
Hướng giải: duyệt các phần tử trong xâu b, bắt đầu từ phần tử thứ 2 (vì phần tử thứ 1 luôn là bắt đầu rồi), mỗi bước ta check xem phần tử sau có bằng phần tử hiện tại không, nếu có thì xóa phần tử phía sau đi. Ví dụ:
abbaac, b == b => abaac
abaac, a == a => abac
Vậy xâu a ban đầu là abac
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
string s; cin >> s;
int i = 1;
while(i < s.size() - 1) {
if(s[i+1] == s[i]) s.erase(i+1,1);
i++;
}
cout << s << '\n';
}
return 0;
}
```
## 66. A+B?
https://codeforces.com/problemset/problem/1772/A
Tóm tắt đề: cho string "A+B" vơi A,B là các số nguyên từ 0 tới 9, hãy tính A + B (tag implementation)
Hướng giải: lấy kí tự A,B trừ '0' rồi cộng lại
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
string s; cin >> s;
int a = s[0] - '0';
int b = s[2] - '0';
cout << a + b << '\n';
}
return 0;
}
```
## 67. Minutes Before the New year
https://codeforces.com/problemset/problem/1283/A
Tóm tắt đề: cho giờ và phút hiện tại, hỏi còn bao nhiêu phút nữa tới năm mới
Hướng giải: đổi tất cả ra phút rồi giờ ra, năm mới thì là 24 x 60, hiện tại thì là h x 60 + m
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int h,m; cin >> h >> m;
int now = h*60+m;
int new_year = 24*60;
cout << new_year - now << '\n';
}
return 0;
}
```
## 68. Do not be distracted
https://codeforces.com/problemset/problem/1520/A
Tóm tắt đề: có 1 xâu theo dõi bài làm của n ngày, hãy kiểm tra xem có ngày nào mà khi đã làm bài khác rồi mà lại quay lại bài hôm trước không, nếu có thì in ra "NO" còn ko thì in ra "YES" (tag brute force, implementation)
Hướng giải: tạo một set lưu các kí tự, mỗi bước ta check xem kí tự sau có khác kí tự trước ko, nếu có thì check tiếp liệu kí tự sau đã từng xuất hiện hay chưa, nếu xuất hiện rồi thì in "NO" r return, còn sau vòng lặp ko có gì thi in YES
ABA
Khi duyệt tới B ta thấy sau đó có A mà A đã xuất hiện trước đó => in ra NO
``` cpp
#include <iostream>
#include <set>
using namespace std;
void solve(string s, set<char> se) {
for(int i = 0; i < s.size() - 1; i++) {
if(s[i+1] != s[i] && se.find(s[i+1]) != se.end()) {
cout << "NO" << '\n';
return;
}
se.insert(s[i]);
}
cout << "YES" << '\n';
return;
}
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
string s; cin >> s;
set<char> se;
solve(s,se);
}
return 0;
}
```
## 69. Square String
https://codeforces.com/problemset/problem/1619/A
Tóm tắt đề: check xem 1 xâu có phải square string hay ko, biết square string là xâu kiểu như "abab","abcabc" (tag implementation, string)
Hướng giải: ta thấy các square string đều có số kí tự chẵn nên việc đầu tiên là ta check số kí tự, nếu lẻ thì in "NO" r return luôn, sau đó ta duyệt từ 0 tới n/2-1, mỗi bước ta check s[i] với s[i+n/2] nếu phát hiện 1 cặp khác thì in "NO" r return luôn, sau vòng lặp mà không có gì (các cặp đều giống nhau) thì in "YES"
Ví dụ:
abcabc
a[0] == a[0 + 6/2]
a[1] == a[1 + 6/2]
a[2] == a[2 + 6/2]
=> in YES
``` cpp
#include <iostream>
using namespace std;
void solve(string s) {
int n = s.size();
if(n % 2 != 0) {
cout << "NO\n";
return;
}
else {
for(int i = 0; i < n / 2; i++) {
if(s[i] != s[n/2+i]) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
return;
}
}
int main() {
int t; cin >> t;
while(t--) {
string s; cin >> s;
solve(s);
}
}
```
## 70. Easy Problem
https://codeforces.com/problemset/problem/2044/A
Tóm tắt đề: cho số n, hãy đếm bao nhiêu cặp (a,b) sao cho a = n - b (tag brute force, math)
Hướng giải: a = n - b => n = a + b. Vì điều kiện a,b luôn dương nên ta thấy a có thể chạy từ 1 tới n-1, mỗi số a có thể ghép với số b tương ứng, v ta chỉ cần in ra n - 1 (hay (n-1-1)+1). Ví dụ:
5
5 - 1 = 4 => in 4. Có 4 cặp là:
1 4
2 3
3 2
4 1
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
cout << n - 1 << '\n';
}
return 0;
}
```
## 71. Equal Candies
https://codeforces.com/problemset/problem/1676/B
Tóm tắt đề: cho một dãy a, hãy tìm tổng giá trị cần giảm ít nhất để cho dãy a bằng nhau (tag greedy,math,sortings)
Hướng giải: duyệt dãy a tìm phần tử bé nhất. Sau đó duyệt lại dãy xem nếu không phải là phần tử bé nhất thì a[i] - min. Ví dụ:
1 2 3 4
min là 1
2 - 1 = 1
3 - 1 = 2
4 - 1 = 3
=> tổng cần giảm là 6
``` cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
int a[n];
int min_val = 1e7+1;
for(int i = 0; i < n; i++) {
cin >> a[i];
min_val = min(min_val,a[i]);
}
long long count = 0;
for(int i = 0; i < n; i++) {
if(a[i] != min_val) count+=a[i] - min_val;
}
cout << count << '\n';
}
return 0;
}
```
## 72. Brain's Photos
https://codeforces.com/problemset/problem/707/A
Tóm tắt đề: cho một mảng 2 chiều, nếu mảng đó toàn là B,W và G thì là Black and White, còn nếu có 1 cái nào khác thì là Color
Hướng giải: duyệt qua r check nếu thấy cái nào khác B W G thì in thẳng ra là ##Color luôn, còn ko thì in ra ##Black&White
``` cpp
#include <iostream>
using namespace std;
int main() {
int n,m; cin >> n >> m;
char a[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(a[i][j] == 'C' || a[i][j] == 'M' || a[i][j] == 'Y') {
cout << "##Color";
return 0;
}
}
}
cout << "##Black&White";
return 0;
}
```
## 73. Odd set
https://codeforces.com/problemset/problem/1542/A
Tóm tắt đề: cho 1 dãy có 2 x n phần tử, hỏi có thể tạo thành n cặp có tổng lẻ ko? (tag math)
Hướng giải: Ta thấy tổng lẻ chỉ có thể tạo thành từ 1 lẻ + 1 chẵn, vậy ta chỉ cần n số lẻ là đc
2
1 2 3 5
có 3 số lẻ => ko đc
``` cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
int size = 2*n;
vector<int> v(size);
int count_odd = 0;
for(int i = 0; i < size; i++) {
cin >> v[i];
if(v[i] % 2 == 1) count_odd++;
}
if(count_odd == n) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
```
## 74. Square Year
https://codeforces.com/problemset/problem/2114/A
Tóm tắt đề: cho một số, hãy chuyển số đó về dạng (a + b)^2, nếu ko được thì in ra -1 (tag binary search,math)
Hướng giải: check xem số đó có phải số chính phương hay không, nếu không phải thì in ra -1 ngay, nếu phải thì in ra 0 và sqrt của số đó
Ví dụ:
1
Là số chính phương => in 0 và 1, hay 1 có thể viết dưới dạng (0+1)/2;
``` cpp
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
string s; cin >> s;
int val = stoi(s);
int root = sqrt(val);
if (root * root == val) {
cout << "0 " << root << '\n'; hợp lệ
} else {
cout << "-1\n";
}
}
return 0;
}
```
## 75. Journey
https://codeforces.com/problemset/problem/2051/B
Tóm tắt đề: ngày thứ nhất đi được a, ngày thứ hai được b, ngày thứ ba được c, ngày thứ 4 được a thứ 5 được b thứ 6 được c và cứ như thế. Hỏi số ngày ít nhất để được n là bao nhiêu? (tag binary search, math)
Hướng giải: tính tổng số bước đi được trong mỗi bộ 3 ngày, sau đó tính ngày, tính số bước đã đi được. Nếu số bước đã đi được lớn hơn bằng mục tiêu ta in thẳng số ngày luôn. Nếu không thì ta check từng bước, nếu walked + a >= n thì in days + 1, walked + b >= n in days + 2, walked + c >= n in days + 3. Ví dụ:
12 1 2 3
Số ngày = 12/(1+2+3) * 3 = 6
Đã đi được = 12/(1+2+3) x (1+2+3) bằng chính 12 => in 6
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
long long n, a, b, c;
cin >> n >> a >> b >> c;
long long one_time = a + b + c;
long long days = (n / one_time) * 3;
long long walked = (n / one_time) * one_time;
if (walked >= n) {
cout << days << '\n';
continue;
}
if (walked + a >= n) days += 1;
else if (walked + a + b >= n) days += 2;
else days += 3;
cout << days << '\n';
}
return 0;
}
```
## 76. Can I square?
https://codeforces.com/problemset/problem/1915/C
Tóm tắt đề: cho n buckets mỗi bucket có a[i] hình vuông, hỏi có thể xây dựng một hình vuông bằng cách sử dụng tất cả hình vuông 1 x 1 đó ko (tag implementation, binary search)
Hướng giải: cộng tất cả hình vuông 1x1 đó lại, nếu là số chính phương thì in ra YES còn lại in ra NO. Ví dụ:
2
14 2
14 + 2 = 16 là số chính phương => in yes
``` cpp
#include <iostream>
#include <cmath>
using namespace std;
bool check(long long n) {
long long root = sqrt(n);
return root * root == n;
}
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
int a[n];
long long cnt = 0;
for(int i = 0; i < n; i++) {
cin >> a[i];
cnt+=a[i];
}
if(check(cnt)) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
```
## 77. Race
https://codeforces.com/problemset/problem/2112/A
Tóm tắt đề: cho ba số a,x,y. Hãy tìm xem có số b nào mà khoảng cách của nó với x và y đều nhỏ hơn khoảng cách tương ứng của x và y với a.
Hướng giải: check thôi
``` cpp
#include <iostream>
#include <cmath>
using namespace std;
bool check(int a, int x, int y) {
for (int b = 1; b <= 100; b++) {
if (b == a) continue;
if (abs(b - x) < abs(a - x) && abs(b - y) < abs(a - y)) {
return true;
}
}
return false;
}
int main() {
int t; cin >> t;
while (t--) {
int a, x, y;
cin >> a >> x >> y;
if(check(a,x,y)) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
```
## 78. To My Critics
https://codeforces.com/problemset/problem/1850/A
Tóm tắt đề: cho ba số hãy check xem có cặp nào mà 2 số lớn hơn bằng 10 ko
Hướng giải: cứ check th
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int a,b,c; cin >> a >> b >> c;
if(a + b >= 10 || a + c >= 10 || b + c >= 10) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
```
## 79. Line Breaks
https://codeforces.com/problemset/problem/2050/A
Tóm tắt đề: cho một dãy a n phần tử có n string và 1 số m, hãy đếm xem có thể lấy tối đa bao nhiêu từ để tổng size của các từ đó không lớn hơn m. (tag implementation)
Hướng giải: duyệt qua dãy a, mỗi bước check nếu tổng hiện tại + tổng phần tử đang xét vẫn <= m thì tăng biến đếm lên và cập nhật tổng, nếu không thì break vòng lặp
``` cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n, m; cin >> n >> m;
vector<string> words(n);
for (int i = 0; i < n; i++) {
cin >> words[i];
}
int total = 0, count = 0;
for (int i = 0; i < n; i++) {
int len = words[i].size();
if (total + len <= m) {
total += len;
count++;
} else break;
}
cout << count << '\n';
}
return 0;
}
```
## 80. Waiting for...
https://codeforces.com/problemset/problem/2038/J
Tóm tắt đề: có n sự kiện, mỗi sự kiện có 2 loại là B - chiếc xe bus với B[i] ghế trống hoặc P - P[i] người chờ xe bus tại trạm. Với mỗi lần xe bus tới hãy xem xem liệu bạn có thể lên hay ko (tag implementation)
Hướng giải: nếu là P x -> cộng thêm x người đang chở, nếu là B x -> nếu số people_wating < x thì in "YES", ngược lại in "NO" r cập nhật people_wating
``` cpp
#include <iostream>
##pragma
using namespace std;
int main() {
int n;
cin >> n;
int people_waiting = 0;
while (n--) {
char type;
int num;
cin >> type >> num;
if (type == 'P') {
people_waiting += num;
} else {
if (people_waiting < num) {
cout << "YES\n";
} else {
cout << "NO\n";
}
people_waiting = max(0, people_waiting - num);
}
}
return 0;
}
```
## 81. Fair Playoff
https://codeforces.com/problemset/problem/1535/A
Tóm tắt đề: có 4 người thi đấu sẽ thi đấu người 1 vs người 2, người 3 vs người 4 rồi vào chung kết. Hãy check xem 2 người được vào chung kết có phải 2 người mạnh nhất hay ko (tag implementation,bruteforce)
Hướng giải: tìm người thắng giữa 2 cặp đấu và check xem đó có phải 2 người mạnh nhất ko
``` cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int s[4];
for (int i = 0; i < 4; ++i) cin >> s[i];
int m1 = max(s[0], s[1]);
int m2 = max(s[2], s[3]);
int a[4];
copy(s, s + 4, a);
sort(a, a + 4);
int strongest = a[3];
int second = a[2];
if ((m1 == strongest && m2 == second) || (m1 == second && m2 == strongest)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
return 0;
}
```
## 82. Blank space
https://codeforces.com/problemset/problem/1829/B
Tóm tắt đề: cho một dãy nhị phân hãy đếm số lượng số 0 liên tiếp dài nhất
Hướng giải: tạo 2 biến consecutive và ans, mỗi lần gặp 0 thì ++ biến consecutive và cập nhật ans = max(ans,consecutive), ko thì reset consecutive về 0
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int n; cin >> n;
int a[n];
for (int i = 0; i < n; ++i) cin >> a[i];
int max_blank = 0, consecutive = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == 0) consecutive++;
else consecutive = 0;
max_blank = max(consecutive, max_blank);
}
cout << max_blank << '\n';
}
return 0;
}
```
## 83. My first Sorting Problem
https://codeforces.com/problemset/problem/1971/A
Tóm tắt đề: cho 2 số x,y. Tìm min và max
Hướng giải: include algorithm vô r làm
``` cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int x,y; cin >> x >> y;
cout << min(x,y) << " " << max(x,y) << '\n';
}
return 0;
}
```
## 84. Yogurt Sale
https://codeforces.com/problemset/problem/1955/A
Tóm tắt đề: một hộp sữa chua có giá a, 2 hộp có giá b, hỏi số tiền ít nhất để mua n hộp là bao nhiêu (tag math)
Hướng giải: đầu tiên ta check liệu mua 2 hộp sữa chua với giá a mỗi hộp có rẻ hơn 1 cặp sữa chua giá b hay ko, nếu bé hơn thì ta in n * a luôn, còn ko thì check tiếp như sau:
- Nếu n lẻ: in n / 2 * b + a
- Nếu n chẵn: in n / 2 * b
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n,a,b; cin >> n >> a >> b;
if(a * 2 <= b) cout << n * a << '\n';
else {
if(n % 2 == 0) cout << n / 2 * b << '\n';
else cout << n / 2 * b + a << '\n';
}
}
return 0;
}
```
## 85. Vlad and the Best of Five
https://codeforces.com/problemset/problem/1926/A
Tóm tắt đề: cho một xâu AB. Cho biết liệu kí tự A hay B nhiều hơn trong xâu
Hướng giải: duyệt qua từng char trong string, nếu là 'A' thì count_a++, 'B' thì count_b++, sau đó so sánh count_a và count_b rồi in kết quả. Ví dụ:
AAABB
sau khi đếm ta có count_a == 3 và count_b == 2, so sánh thấy count_a > count_b nên ta in 'A'
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
string s; cin >> s;
int count_a = 0, count_b = 0;
for(int i = 0; i < 5; i++) {
if(s[i] == 'A') count_a++;
else count_b++;
}
if(count_a > count_b) cout << "A\n";
else cout << "B\n";
}
return 0;
}
```
## 86. Floor Number
https://codeforces.com/problemset/problem/1426/A
Tóm tắt đề: cho số phòng là n, tầng 1 có 2 phòng 1 và 2, các tầng sau mỗi tầng các số phòng là x, hỏi phòng n ở tầng mấy
Hướng giải: tạo 1 biến floor = 1, rooom = 0 rồi while(room < n), sau đó kiểm tra nếu floor bằng 1 thì room+=2, khác thì room+=x, floor++ sau đó in ra floor - 1
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n,x; cin >> n >> x;
int fl = 1;
int room = 0;
while(room < n) {
if(fl == 1) room += 2;
else room += x;
fl++;
}
cout << fl - 1 << '\n';
}
}
```
## 87. Square
https://codeforces.com/problemset/problem/1921/A
Tóm tắt đề: cho lần lượt 4 giá trị x và 4 giá trị y là các điểm trên trục tọa độ. Hãy tìm diện tích hình vuông lớn nhất có thể
Hướng giải: để diện tích lớn nhất ta cần cạnh lớn nhất, vậy ta chỉ cần tìm khoảng cách lớn nhất giữa các cặp điểm của x và y là được
``` cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int x[4], y[4];
for (int i = 0; i < 4; ++i) {
cin >> x[i] >> y[i];
}
int dx = *max_element(x, x+4) - *min_element(x, x+4);
int dy = *max_element(y, y+4) - *min_element(y, y+4);
int side = max(dx, dy);
cout << side * side << '\n';
}
return 0;
}
```
## 88. Calculating Function
https://codeforces.com/problemset/problem/486/A
Tóm tắt đề: cho công thức như sau: f(n) = - 1 + 2 - 3 + .. + ( - 1)^n x n. Tính f(n)
Hướng giải: ta thấy mỗi cặp như -1 + 2 ra kq bằng 1 nên ta lấy 1 * n / 2, nếu n lẻ thì - n thêm vào
``` cpp
#include <iostream>
using namespace std;
int main() {
long long n; cin >> n;
long long ans = 0;
ans+= 1 * n / 2;
if(n % 2 == 1) ans -= n;
cout << ans;
return 0;
}
```
## 89. Normal Problem
https://codeforces.com/problemset/problem/2044/B
Tóm tắt đề: cho 1 xâu hãy lật ngược xâu đó lại
Hướng giải: ta check xâu gốc từ sau cùng lên, nếu phần tử s[s.size()-i-1] == 'p' thì ans[i] = 'q', == 'q' thì ans[i] = 'p', == 'w' thì ans[i] == 'w'
``` cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
string s; cin >> s;
string ans = "";
ans = s;
for(int i = 0; i < s.size(); i++) {
if(s[s.size()-i-1] == 'q') ans[i] = 'p';
else if (s[s.size()-i-1] == 'p') ans[i] = 'q';
else ans[i] = 'w';
}
cout << ans << '\n';
}
return 0;
}
```
## 90. Linear Keyboard
https://codeforces.com/problemset/problem/1607/A
Tóm tắt đề: cho một string có 26 phần tử riêng biệt là các chữ cái alphabet, sau đó cho string s, hãy tính tổng các khoảng cách giữa các phần tử trong string s theo string đầu.
Hướng giải: lưu chỉ số của từng chữ cái trên bàn phím. Sau đó duyệt qua từng cặp kí tự liên tiếp rồi tính tổng khoảng cách
``` cpp
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
string keyboard,word; cin >> keyboard >> word;
int pos[26];
for(int i = 0; i < keyboard.size(); i++) {
pos[keyboard[i] - 'a'] = i;
}
int total = 0;
for(int i = 1; i < word.size(); i++) {
total+= abs(pos[word[i] - 'a'] - pos[word[i-1] - 'a']);
}
cout << total << '\n';
}
return 0;
}
```
## 91. Honest Coach
https://codeforces.com/problemset/problem/1360/B
Tóm tắt đề: cho một dãy có n phần tử hãy split dãy đó vào 2 dãy sao cho khoảng cách giữa số lớn nhất dãy đầu và số bé nhất dãy sau là nhỏ nhất có thể (tag greedy,sortings)
Hướng giải: sort dãy ban đầu lại r tìm khoảng cách bé nhất giữa 2 phần tử liên tiếp
``` cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(),a.end());
int min_dif = 1005;
for(int i = 1; i < n; i++) {
min_dif = min(min_dif, a[i] - a[i-1]);
}
cout << min_dif << '\n';
}
return 0;
}
```
## 92. LCM Problem
https://codeforces.com/problemset/problem/1389/A
Tóm tắt đề: cho l,r. Hãy tìm 2 số x,y sao cho l <= lcm(x,y) <= r và l <= x < y <= r. Nếu có nhiều cặp x,y thì in cặp nào cũng được, ko có cặp x,y nào thì in -1.
Hướng giải: ta có thể chọn x = l, y = 2l, khi đó 2l sẽ là bội chung nhỏ nhất. Vậy ta cần check xem 2l có lớn hơn r hay ko, nếu có thì in -1 còn ko thì in l với 2l luôn.
``` cpp
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
long long l, r;
cin >> l >> r;
if (2 * l <= r) {
cout << l << " " << 2 * l << '\n';
} else {
cout << -1 << " " << -1 << '\n';
}
}
return 0;
}
```
## 93. Make it White
https://codeforces.com/problemset/problem/1927/A
Tóm tắt đề: bạn cần đổi các kí tự B thành W. Hãy đếm độ dài của dãy cần đổi
Hướng giải: tìm vị trí của phần tử B đầu tiên và phần tử B cuối cùng sau đó trừ ra để tìm kết quả
``` cpp
#include <iostream>
#include <map>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n,m; cin >> n >> m;
map<char,int> mp;
string s; cin >> s;
for(int i = 0; i < n; i++) {
mp[s[i]]++;
}
string difficulty = "ABCDEFG";
int need_more = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < difficulty.size(); j++) {
if(mp[difficulty[j]] <= 0) {
need_more++;
}
mp[difficulty[j]]--;
}
}
cout << need_more << '\n';
}
return 0;
}
```
## 94. Problem Generator
https://codeforces.com/problemset/problem/1980/A
Tóm tắt đề: cần làm m vòng, mỗi vòng làm các độ khó từ A tới G. Bạn có sẵn n bài với độ khó cho trước, hỏi cần thêm bao nhiêu bài để làm đủ m contest?
Hướng giải: dùng map để lưu tần suất của các bài có sẵn, sau đó duyệt qua các vòng, mỗi vòng duyệt từ A tới G rồi -- ra, nếu <= 0 thì ++ vào biến need_more
``` cpp
#include <iostream>
#include <map>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n,m; cin >> n >> m;
map<char,int> mp;
string s; cin >> s;
for(int i = 0; i < n; i++) {
mp[s[i]]++;
}
string difficulty = "ABCDEFG";
int need_more = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < difficulty.size(); j++) {
if(mp[difficulty[j]] <= 0) {
need_more++;
}
mp[difficulty[j]]--;
}
}
cout << need_more << '\n';
}
return 0;
}
```
## 95. Perfect Permutation
https://codeforces.com/problemset/problem/233/A
Tóm tắt đề: 1 hoán vị hoàn hảo là tại các vị trí i có p[p[i]] == i và p[i] != i. Hãy in ra hoán vị hoàn hảo của n, nếu không có thì in ra -1
Hướng giải: nếu n lẻ thì ko có honas vị nào như thế vị khi lẻ sẽ luôn có ít nhất 1 p[i] = i. Nếu n chẵn, ta chỉ việc swap vị trí của từng cặp 1 là xong.
``` cpp
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
if (n % 2 == 1) {
cout << -1 << '\n';
} else {
for (int i = 1; i <= n; i += 2) {
cout << i + 1 << " " << i << " ";
}
cout << '\n';
}
return 0;
}
```
## 96. Panoramix's Prediction
https://codeforces.com/problemset/problem/80/A
Tóm tắt đề: cho hai số n và m, hãy check xem m có phải số nguyên tố tiếp theo sau n hay ko?
Hướng giải: tạo một biến next bằng n + 1 r cho lặp tới khi nào next là số nguyên tố, sau đó check xem next có == m hay ko
``` cpp
#include <iostream>
using namespace std;
bool check(int m) {
if (m < 2) return false;
for(int i = 2; i * i <= m; i++) {
if (m % i == 0) return false;
}
return true;
}
int main() {
int n, m; cin >> n >> m;
int next = n + 1;
while (!check(next)) {
next++;
}
if (next == m) cout << "YES";
else cout << "NO";
return 0;
}
```
## 97. Triple
https://codeforces.com/problemset/problem/1669/B
Tóm tắt đề: hãy in 1 phần tử xuất hiện 3 lần trong dãy, ko có thì in -1
Hướng giải: dùng map đếm rồi duyệt map thấy thằng nào tần suất >=3 thì in ra, còn ko thấy thì in -1
```cpp
#include <iostream>
#include <map>
using namespace std;
void solve() {
int n; cin >> n;
int a[n];
map<int,int> mp;
for(int i = 0; i < n; i++) {
cin >> a[i];
mp[a[i]]++;
}
for(auto it : mp) {
if(it.second >= 3) {
cout << it.first << '\n';
return;
}
}
cout << -1 << '\n';
return ;
}
int main() {
int t; cin >> t;
while(t--) {
solve();
}
return 0;
}
```
## 98. HQ9+
https://codeforces.com/problemset/problem/133/A
Tóm tắt đề: cho một xâu, nếu xâu đó có kí tự 'H' hoặc 'Q' hoặc '9' thì in YES, ko có cái nào thì in NO
Hướng giải: duyệt qua string r làm thôi
``` cpp
#include <iostream>
using namespace std;
int main() {
string s; cin >> s;
for(char c : s) {
if(c == 'H' || c == 'Q' || c == '9') {
cout << "YES";
return 0;
}
}
cout << "NO";
return 0;
}
```
## 99. Gravity Flip
https://codeforces.com/problemset/problem/405/A
Tóm tắt đề: cho các hộp đồ chơi ban đầu, cột thứ i có a[i] hộp, các hộp đồ chơi sẽ bị lực hấp dẫn tác động khiến nó dồn về bên phải tới khi cột bên phải có số lượng lớn hơn. Hãy cho biết số lượng hộp đồ chơi của các cột sau khi chịu tác động lực
Hướng giải: sort mảng tăng dần
``` cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n;
int a[n];
for(int i = 0; i < n; i++) cin >> a[i];
sort(a,a+n);
for(int i = 0; i < n; i++) cout << a[i] << ' ';
return 0;
}
```
## 100. Insomnia cure
https://codeforces.com/problemset/problem/148/A
<details> <summary> Bài làm </summary>
Tóm tắt đề: những con rồng chia hết cho k hoặc l hoặc m hoặc n sẽ bị tấn công. Có d con rồng, đếm số con rồng bị tấn công?
Hướng giải: duyệt từ 1 tới n số nào chia hết cho k hoặc l hoặc m hoặc n thì ++ biến đếm
``` cpp
#include <iostream>
using namespace std;
int main() {
int k,l,m,n,d; cin >> k >> l >> m >> n >> d;
int cnt = 0;
for(int i = 1; i <= d; i++) {
if(i % k == 0 || i % l == 0 || i % m == 0 || i % n == 0) cnt++;
}
cout << cnt;
return 0;
}
```
</details>
Sign in with Wallet
Connect another wallet