CHEALG - December Lunchtime 2019 Division 2

Link đề bài trên Codechef - bản tiếng Việt
Hướng dẫn giải + code mẫu

Happy coding!

codelearn.io - root (easy)

Link đề bài

Cho một số nguyên n. Mỗi lần bạn sẽ biến n thành tổng các chữ số của n. Hãy tìm n khi tổng của n chỉ còn lại 1 chữ số.

Input: số nguyên n (1 <= n <= 10^9)

Output: số nguyên n là kết quả thỏa yêu cầu đề bài.

Ví dụ:

Input:

12

Output:

3

Input:

99

Output:

9

Giải thích: 

• Ở ví dụ đầu:
• Lần 1: 1 + 2 = 3 (chỉ có 1 chữ số, in ra 3).
• Ở ví dụ sau:
• Lần 1: 9 + 9 = 18
• Lần 2: 1 + 8 = 9 (chỉ có 1 chữ số, in ra 9).

Solution: Đệ quy cơ bản + tách số.

Code C++:

	int root(int n) {
	if (n >= 10) {
	int s = 0;
	while (n > 0) {
	s += n % 10;
	n /= 10;
	}
	return root(s);
	}
	return n;
	}

view raw root.cpp hosted with ❤ by GitHub

December Challenge - Division 2

Link đề bài + hướng dẫn giải (Tiếng Anh)
Update đề bài WATSCORE bằng tiếng Việt

Happy coding!

MDL - Medel

Xem đề bài trên Codechef – bản tiếng Việt

Solution: Giả sử ta có dãy A như testcase số 2, A = {38, 9, 102, 10, 96, 7, 46, 28,  88, 13}.

1. Ta xóa 38, còn lại {9, 102, 10, 96, 7, 46, 28,  88, 13}
2. Ta xóa 10, còn lại {9, 102, 96, 7, 46, 28,  88, 13}
3. Ta xóa 96, còn lại {9, 102, 7, 46, 28,  88, 13}
4. Ta xóa 9, còn lại {102, 7, 46, 28,  88, 13}
5. Ta xóa 46, còn lại {102, 7, 28,  88, 13}
6. Ta xóa 28, còn lại {102, 7, 88, 13}
7. Ta xóa 88, còn lại {102, 7, 13}
8. Ta xóa 13, còn lại {102, 7} cũng là đáp án.

Bây giờ từ dãy A ban đầu, ta sắp xếp các phần tử theo thứ tự tăng dần:

A = {7, 9, 10, 13, 28, 38, 46, 88, 96, 102}

Dễ dàng nhận thấy đáp án chính là 2 phần tử A[0] và A[1]. Điều mà ta cần quan tâm tiếp theo là việc xuất kết quả dựa trên thứ tự xuất hiện của 2 phần tử, nếu A[0] xuất hiện trước thì in A[0] trước, ngược lại in A[1] trước. Việc này có thể dễ dàng xử lý bằng một vòng lặp chạy từ 0 đến N, nếu gặp A[0] trước thì A[0] xuất hiện trước, ngược lại thì A[1] là phần tử xuất hiện trước.

Code mẫu (C++):

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

view raw MDL.cpp hosted with ❤ by GitHub

HPYNOS - Happy Numbers I

Xem đề bài trên SPOJ

Quá trình "tách rời" một số nguyên được miêu tả là quá trình tính tổng bình phương các chữ số của nó lại với nhau. Ví dụ, kết quả của quá trình "tách rời" số 125 là (1^2 + 2^2 + 5^2) = 30. Một số N được gọi là con số vui vẻ, nếu sau nhiều quá trình "tách rời" liên tiếp kết quả đạt thu cuối cùng bằng 1. Nếu kết quả không thể bằng 1 sau nhiêu quá trình "tách rời" liên tiếp, thì N không phải là con số vui vẻ.

Yêu cầu: Viết chương trình nhập vào số nguyên N, xác định xem nó có phải con số vui vẻ hay không.

Ràng buộc:

1 <= N <= 2147483647 (2^31 - 1).

Input: một và chỉ một số nguyên N.

Output: một dòng duy nhất chứa số nguyên T là số lần biến đổi số N để kết luận xem nó có phải con số vui vẻ hay không. Nếu N không phải con số vui vẻ, in ra -1.

Ví dụ:

Input:

19

Output:

4

Giải thích:

1. 19 => 1^2 + 9^2 = 82
2. 82 => 8^2 + 2^2 = 68
3. 68 => 6^2 + 8^2 = 100
4. 100 => 1^2 + 0^2 + 0^2 = 1 (dừng)

Input: 

204

Output

-1

Giải thích:

1. 204 => 2^2 + 0^2 + 4^2 = 20
2. 20 => 2^2 +0^2 = 4
3. 4 => 4^2 = 16
4. 16 => 1^2 + 6^2 = 37
5. 37 => 3^2 + 7^2 = 58
6. 58 => 5^2 + 8^2 = 89
7. 89 => 8^2 + 9^2 = 145
8. 145 => 1^2 + 4^2 + 5^2 = 42
9. 42 => 4^2 + 2^2 = 20 (tiếp tục lặp lại từ bước 2).

Solution: Chú ý là 2^31-1 vẫn nằm trong phạm vi của integer, hơn nữa công việc của chúng ta là xử lý bình phương của các chữ số, không phải cả số hạng nên kiểu dữ liệu toàn bài sử dụng integer vẫn AC bình thường. Dùng một mảng lưu lại những số sau khi xử lý, dùng một thuật toán tìm kiếm hiệu quả. Cuối cùng là duyệt trâu qua từng số hạng đã xử lý để đưa ra kết quả đề bài.

Code mẫu (C++, sử dụng hàm tìm kiếm nhị phân dựng sẵn)

	/**
	* HYPNOS - Happy Numbers I
	* https://www.spoj.com/problems/HPYNOS/
	* 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);
	vector<int> e;
	int n; cin >> n;
	int s = 0, c = 0;
	while (true) {
	while (n > 0) {
	s += (n % 10) * (n % 10);
	n /= 10;
	}
	c++;
	if (s == 1) {
	cout << c << endl;
	break;
	} else {
	// Binary search
	sort(e.begin(), e.end());
	if (binary_search(e.begin(), e.end(), s)) {
	cout << -1 << endl;
	break;
	}
	e.push_back(s);
	n = s;
	s = 0;
	}
	}
	return 0;
	}

view raw HPYNOS.cpp hosted with ❤ by GitHub

ADASTAIR - Ada and the Staircase

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

Solution: Bài này ta tìm khoảng cách giữa hai bậc thang gần nhau nhất, nếu khoảng cách lớn hơn K thì lấy khoảng cách này chia cho K sẽ tìm được số bậc thang cần chèn. Chú ý, nếu khoảng cách chia hết cho K thì sau khi chèn ta xóa đi một bậc.

Ví dụ: K = 2, 2 bậc thang gần nhau nhất là 2 và 6
Ta có khoảng cách = 6 - 2 = 4 > K, nếu lấy 4 / K = 4 / 2 = 2 tức là chèn tới 2 bậc. Tuy nhiên ta chỉ cần chèn 1 bậc (2 - 4 - 6).

Bậc thang đầu tiên có thể cao hơn K.

Code mẫu:

	/**
	* ADASTAIR - https://www.codechef.com/problems/ADASTAIR
	* 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;
	int N, K, S;
	while (T--) {
	cin >> N >> K;
	S = 0;
	vector<int> a; a.push_back(0);
	for (int i = 1; i <= N; ++i) {
	int u; cin >> u; a.push_back(u);
	}
	for (int i = 1; i <= N; ++i)
	if (a[i] - a[i - 1] > K) {
	S += (a[i] - a[i - 1]) / K;
	if ((a[i] - a[i - 1]) % K == 0) S--;
	}
	cout << S << endl;
	}
	return 0;
	}

view raw ADASTAIR.cpp hosted with ❤ by GitHub

ALTARAY - Alternating subarray prefix

(Kể từ bài viết này, những đáp án - code mẫu mình sẽ đăng lên GitHub dưới dạng file zip kèm đề bài pdf).

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

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

Happy coding!

ZOZ - Magic Elements

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

Solution: Duyệt cơ bản. Gọi S là tổng các phần tử trong dãy. i là vị trí hợp lệ nếu A[i] + k > S - A[i].

Code mẫu (C++):

	/**
	* ZOZ - https://codechef.com/problems/ZOZ
	* 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--) {
	int n, k, s = 0, c = 0; cin >> n >> k;
	vector<int>a;
	for(int i = 1; i <= n; ++i) {int u; cin >> u; a.push_back(u); s += u;}
	for (int i = 0; i < n; ++i)
	if (a[i] + k > s - a[i]) c++;
	cout << c << endl;
	}
	return 0;
	}

view raw ZOZ.cpp hosted with ❤ by GitHub

longestArrays - dãy con không giảm dài nhất

(codelearn.io - Training Easy)

Đề bài: Một dãy a được gọi là dãy không giảm nếu thỏa mãn: a[i] <= a[j] với mọi 0 <= i <  j < a.size().

Cho một mảng a gồm các số nguyên. In ra độ dài dãy con không giảm dài nhất của a.

Input: mảng a (0 < a.size() <= 10^6, a[i] <= 10^9.)
Output: Độ dài dãy con không giảm dài nhất của a.

Example:
Input: a = [3, 2, 2, 4, 6, 3].
Output: longestArrays(a) = 4.
Giải thích ví dụ: dãy con không giảm dài nhất của a trong ví dụ trên là [2, 2, 4, 6].

Chú ý: 
Ở đây ta phân biệt khái niệm dãy con tăng dài nhất và dãy con không giảm dài nhất. Hiểu đơn giản là trong dãy con tăng dài nhất thì các phần tử tăng dần từ trái qua phải và không có 2 phần tử nào trong dãy bằng nhau. 
Ở testcase mẫu, nếu yêu cầu đưa ra dãy con tăng dài nhất thì kết quả longestArrays(a) = 3, dãy con là [2, 4, 6]. Còn dãy con không giảm dài nhất theo yêu cầu của đề bài là [2, 2, 4, 6], có 2 phần tử đầu tiên trùng nhau.

Solution: Quy hoạch động cơ bản. Theo testcase mẫu thì dãy con này là dãy con liên tiếp. Gọi F[i] là độ dài dãy con tăng liên tiếp tại vị trí i, F[0] = 1 do tại vị trí 0 chỉ có 1 phần tử. Tại vị trí i, nếu a[i] >= a[i - 1] thì F[i] = F[i - 1] + 1 (độ dài dãy con tại vị trí trước đó tăng lên 1 đơn vị). Nếu không, F[i] = 1 tức là ta bắt đầu xét một dãy con mới tại vị trí i.

Công thức truy hồi:
F[0] = 1
F[i]  = max(F[i - 1] + 1, 1) nếu a[i] >= a[i - 1]

Kết quả sẽ là max(F[])

Code C++:

	/*
	* longestArrays.cpp - Dynamic Programming approach.
	* Code by @trhgquan - https://github.com/trhgquan
	*/
	int longestArrays(vector<int> a) {
	vector<int> b(a.size(), 1);
	int res = 1;
	for (unsigned i = 1; i < a.size(); ++i){
	if (a[i] >= a[i - 1]) b[i] = b[i - 1] + 1;
	res = max(b[i], res);
	}
	return res;
	}

view raw longestArrays.cpp hosted with ❤ by GitHub

Compress the List (Codechef November Lunchtime 2019)

Vừa mới về quê được ít hôm thì cúm. Vừa đau mắt vừa hắt xì đau mũi nên đầu óc cũng không được tỉnh táo cho lắm. Lại thêm lúc đang giải bài thì nổi hứng úp mì tôm ăn, vừa ăn vừa ngẫm cho nên 1 tiếng chỉ AC được 1 bài, định làm sang bài 2 thấy còn có 8 phút nên thôi :(

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

Solution: quy hoạch động. Đề nhìn có vẻ phức tạp nhưng chủ yếu là tìm các dãy con tăng liên tiếp trong dãy các phần tử cho trước, rồi in ra theo một format nhất định.

Gọi dãy ban đầu là dãy A, dãy đánh dấu là dãy B. Một phần tử A[i] được đánh dấu tương ứng B[i], nếu B[i] = 1 thì có 2 khả năng, hoặc là phần tử đó là biên (phần tử đầu hoặc cuối) của một dãy con tăng, hoặc phần tử đó là một phần tử đặc biệt đứng riêng 1 mình.

B[0] = 1

B[i] = B[i - 1] + 1 nếu A[i] - A[i - 1] = 1 (A[i] và A[i - 1] là 2 phần tử tăng liên tiếp).

B[i] = 1 nếu A[i] - A[i - 1] != 1 (A[i] và A[i - 1] không phải 2 phần tử tăng liên tiếp).

Đặc biết: B[N] = 1 nếu B[N] != 1 (*)

(*) Sở dĩ ta đánh dấu phần tử cuối cùng bằng 1:

• Giả sử tồn tại dãy con tăng liên tiếp A[x], A[x + 1], ... , A[N]. Khi đó A[N] là phần tử biên, nên đánh dấu B[N] = 1. 
• Giả sử phần tử A[N - 1] và A[N] là 2 phần tử của dãy con tăng. Khi đó theo đề bài ta không thể tính A[N - 1...N] là một dãy con. Do vậy đánh dấu B[N] = 1.
• Trường hợp cuối A[N] là phần tử riêng biệt. Đánh dấu B[N] = 1 là điều hiển nhiên.

Cuối cùng ta chỉ cần xử lý, in kết quả. Những số cần in sẽ được đánh dấu là 1, những số không in ra thì đã được đánh dấu khác 1.

Code mẫu (C++):

	//
	// CMPRSS - https://codechef.com/problems/CMPRSS
	// 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, N; cin >> T;
	while (T--) {
	cin >> N;
	vector<int>a, b;
	for (int i = 1; i <= N; ++i) {int u; cin >> u; a.push_back(u);b.push_back(1);}
	//
	// The idea is using DP (Dynamic Programming),
	// since we need to count every adjacent subsequence.
	// An element is flagged "1" if it is an edge, or, a single item.
	//
	for (int i = 1; i < N; ++i) {
	if (a[i] - a[i - 1] == 1) b[i] = b[i - 1] + 1;
	if (a[i] - a[i - 1] > 1 && b[i] - b[i - 1] < 0) b[i - 1] = b[i];
	if (i == N - 1 && b[i] != 1) b[i] = 1;
	}
	//
	// Print result
	//
	cout << a[0];
	int c = 1;
	for (int i = 1; i < N; ++i){
	if (b[i] != 1) ++c;
	if (b[i] == 1) {
	if (c >= 2) {
	cout << "...";
	c = 1;
	} else cout << ",";
	cout << a[i];
	}
	}
	cout << endl;
	}
	return 0;
	}

view raw CMPRSS.cpp hosted with ❤ by GitHub