Codechef January Lunchtime 2020 - Division 2

Ngoài lề: một số bài đăng gần đây của mình có đăng code thay vì đăng link đến repo lưu file .zip, đó là vì những bài đăng này được viết từ trước và mình đã lên lịch đăng nó cách nhau 2 - 3 tuần. Những bài đăng về sau mình vẫn giữ nguyên format là kèm link file zip mã nguồn. Làm vậy sẽ cung cấp được nhiều file hơn cùng đề bài và lời giải chi tiết.

Bài đăng sẽ bao gồm lời giải cho

• BFRIEND - Bob and His Friends
• STFOOD - Chef and Street Food

Link hướng dẫn giải + code mẫu

Happy coding!

PLAYSTR - Playing with Strings

Đề bài trên Codechef - bản tiếng Việt

Solution: Đề bài yêu cầu đổi chỗ 2 bit nằm ở 2 vị trí khác nhau, không thêm không xóa. Vậy một chuỗi bit A chỉ có thể biến đổi thành chuỗi B khi và chỉ khi số lượng bit 0 của chuỗi A bằng số lượng bit 0 của chuỗi B, tương tự với số lượng bit 1.

Code mẫu (C++):

	/**
	* PLAYSTR - https://codechef.com/problems/PLAYSTR
	* Code by @trhgquan - https://github.com/trhgquan
	*/
	#include<iostream>
	#include<string>
	#include<vector>
	using namespace std;
	int main() {
	int t; cin>>t;
	while(t--) {
	int n; cin>>n;
	string a, b;
	cin >> a; cin >> b;
	vector<int> c = {0,0};
	for(int i = 0;i < n; ++i){
	if (a[i] == '1') c[0]++;
	if (b[i] == '1') c[1]++;
	}
	if (c[0] == c[1]) cout << "YES" << endl;
	else cout<< "NO" << endl;
	}
	return 0;
	}

view raw PLAYSTR.cpp hosted with ❤ by GitHub

January Long Challenge and Cookoff - Division 2

Bài đăng sẽ bao gồm lời giải cho

• Breaking Bricks - BRKBKS (Long Challenge)
• Chef Chick - CHFCHK (Cookoff)

Thông tin thêm: Cookoff khác Lunchtime ở chỗ Lunchtime được tính theo từng bareme điểm còn Cookoff chỉ có AC hoặc WA.

Hướng dẫn giải + Code mẫu

Happy coding!

LONGSEQ - Chef and Digits of a Number

Đọc đề bài trên Codechef - bản tiếng Việt

Solution: Dễ dàng nhận thấy số D chỉ có thể đổi được nếu trong số đó chỉ có 1 chữ số 1/0 và D.length - 1 chữ số loại còn lại.

Code mẫu (C++):

	/**
	* LONGSEQ - https://codechef.com/problems/LONGSEQ
	* Code by @trhgquan - https://github.com/trhgquan
	*/
	#include<iostream>
	#include<vector>
	using namespace std;
	int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T; cin >> T;
	while (T--) {
	string s; cin >> s;
	int l = s.size() - 1;
	vector<int> a = {0, 0};
	for (char i: s) a[int(i) - 48]++;
	if ((a[0] == 1 && a[1] == l) ||
	(a[1] == 1 && a[0] == l))
	cout << "Yes" << endl;
	else cout << "No" << endl;
	}
	return 0;
	}

view raw LONGSEQ.cpp hosted with ❤ by GitHub

SMPAIR - Cặp có tổng nhỏ nhất

Link đề bài trên Codechef

Bạn được cho một dãy số a[1], a[2], ... , a[N]. Tìm tổng nhỏ nhất của ai + aj, với 1 < i < j <= N.

Input: Dòng đầu tiên chứa một số nguyên T là số bộ test. Mỗi bộ test được miêu tả như sau:

Dòng đầu tiên của mỗi bộ test là số nguyên N - số phần tử của dãy số a.

Dòng tiếp theo lần lượt là các số a[1], a[2], ..., a[N], mỗi số cách nhau một dấu cách.

Output: Với mỗi bộ test, in ra màn hình một số nguyên duy nhất là kết quả của bộ test.

Ràng buộc:

• T = 10^5, N = 2: 13 điểm
• T = 10^5, 2 <= N <= 10: 16 điểm
• T = 1000, 2 <= N <= 100: 31 điểm
• T = 10, 2 <= N <= 10^5: 40 điểm
• 1 <= a[i] <= 10^6

Solution: phương pháp tham lam. Sắp xếp dãy a theo thứ tự tăng dần, tổng của 2 phần tử đầu tiên (cũng là 2 phần tử nhỏ nhất) là kết quả.

Code mẫu (C++):

	/**
	* SMPAIR - https://codechef.com/problems/SMPAIR
	* Code by @trhgquan - https://github.com/trhgquan
	*/
	#include<iostream>
	#include<algorithm>
	#include<vector>
	using namespace std;
	int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int T, n; cin >> T;
	while (T--) {
	cin >> n;
	vector<int>a;
	for (int i = 0; i < n; ++i) {int u; cin >> u; a.push_back(u);}
	sort(a.begin(), a.end());
	cout << a[0] + a[1] << endl;
	}
	return 0;
	}

view raw SMPAIR.cpp hosted with ❤ by GitHub