Editorial Happy School 2

ami - 14/03/2020

A

Idea : ami, tester : UyênCute

Gọi hàm d(a , b) là số số tự nhiên trong đoạn [a , b] chia 3 dư 1. d(a , b) chính là kết quả bài toán.

Để tính d(a , b), có thể làm như sau :

d(a , b) = d(1 , b) - d(1 , a-1). 

d(1 , x) = (x - 1) / 3 + 1. Nếu x ≤ 0, kết quả là 0.

Idea: cuom1999, tester: cuom1999

Đầu tiên nhận thấy rằng nếu có 2 số liên tiếp bằng nhau thì in ra NO

Tạo một dãy mới b[i] = 1 nếu a[i] < a[i + 1] và = 0 nếu a[i] > a[i + 1].

Dãy số b có độ dài n - 1, và cần có dạng như sau: 11...100...011..1

Để kiểm tra dãy số b có thỏa mãn điều kiện trên không, có thể đếm số lượng đoạn toàn 0/1 liên tiếp, và kiểm tra xem nó có bằng 3 hay không.

C

Idea : ami, tester : UyênCute, cuom1999

Đây là dạng cơ bản của một bài toán quy hoạch động. Gọi f(i , c) là kết quả bài toán, nếu chỉ xét i kí tự đầu của xâu S, và tên LTN chỉ kết thúc ở ký tự c (c = 'L' , 'T' , 'N'). Kết quả của cả bài toán là f(n , 'N').

Để tính f(i , c), ta có cách quy hoạch động sau

f(0 , 'T' ) = f(0 , 'L') = f(0 , 'N') = 0

f(i , c) = f(i - 1 , c)

Nếu s[i] = 'L', f(i , c) = max( f(i , c) , f(i-1 , 'L') + 1)

Nếu s[i] = 'N', f(i , c) = max( f(i , c) , f(i-1 , 'N') + 1, f(i-1 , 'T') + 1)

Nếu s[i] = 'T', f(i , c) = max( f(i , c) , f(i-1 , 'L') + 1 ,  f(i-1 , 'T') + 1)

Bonus: Giải nghĩa LTN :))). 

D

Idea: cuom1999, tester: ami

Đầu tiên nhận xét rằng kết quả bài toán với (n, k) sẽ giống (n / d, k / d) với d = gcd(n, k). Chứng minh ở phía cuối bài. (Đây là phần khó nhất bài toans). (1)

Lúc này, có thể giả sử gcd(n, k) = 1 và chúng ta có 2 TH:

TH1: k lẻ -> YES

Có thể lật theo vòng tròn như sau: (0, 1, ..., k - 1), (1, 2, ..., k), ..., (n - 1, 0, ..., k - 2).

Mỗi đồng xu được lật k lần (do xuất hiện trong k bộ) nên sẽ chuyển thành ngửa -> úp.

TH2: k chẵn -> NO

Vì k chẵn nên n lẻ. Gọi S là số đồng xu úp. Ban đầu S = 0. 

Tại một bước lật, giả sử ta lật a đồng úp -> ngửa và (k - a) đồng ngửa -> úp. Lúc đó Snew =  S - a + (k - a) = S + k - 2a = S (mod 2). Vì thế S luôn chẵn. Nên S không thể bằng n.

C/m nhận xét (1): 

TH1: Nếu có (n / d, k / d) có kết quả YES

Chia n đồng thành các nhóm d đồng liên tiếp. Lúc đó ta có n / d nhóm và mỗi lần lật k đồng nghĩa có thể quy về lật k / d nhóm. Do đó (n, k) cũng có kết quả là YES

TH2: Nếu có (n / d, k / d) có kết quả NO

Tô màu đỏ các đồng sau: 0, d, 2d, ..., (n / d - 1) * d. Có đúng (n / d) đồng đỏ. Đồng thời mỗi lần lật k đồng liên tiếp, ta cũng lật đúng (k / d) đồng đỏ.

Nếu (n, k) có kết quả YES thì tất cả (n / d) đồng đỏ cũng được lật úp => (n / d, k / d) cũng có kết quả YES (mâu thuan). Do đó (n, k) có kết quả NO. 

E

Idea : CàiWinLậu, tester : UyênCute, cuom1999, ami

Để giải bài toán này, các bạn cần có kiến thức về cấu trúc dữ liệu stack (hoặc vector).

Thuật toán cơ bản chỉ là lần lượt đẩy các kí tự vào stack, sẽ có các trường hợp sau :

1) Nếu kí tự hiện tại là dấu ngoặc '(', tiếp tục duyệt

2) Nếu kí tự hiện tại là một toán tử

3) Nếu kí tự hiện tại là dấu ngoặc ')', lấy ra ra 3 kí tự đã đẩy vào gần nhất trong stack. Sẽ có một số A, một số B, và một toán tử opt. Ta sẽ đẩy vào stack kết quả phép tính (A opt B).

Số cuối cùng trong stack chính là kết quả.

F

Idea : CàiWinLậu, tester : UyênCute, cuom1999, ami

Ý tưởng cơ bản cũng là thực hiện các phép toán trên hàng đợi như bài E. Ta có nhận xét, phép tính thao tác bit có thể được làm riêng biệt từng cột. Ví dụ, để tính

cột 12345

      11111

xor

      10101

or

      00010

Ta có thể tính kết quả riêng biệt của cột 1, rồi cột 2, ... và ghép các kết quả này lại. Thêm nhận xét nữa, vì chỉ có 4 xâu nhị phân A,B,C,D, nên chung quy chỉ có 24 cột khác nhau, tương ứng với 24 xâu nhị phân độ dài 4. Do đó, có thể tính trước kết quả nếu A,B,C,D lần lượt là các bit từ trái sang phải của của một xâu nhị phân độ dài 4. Và sau đó chỉ việc ghép kết quả này lại với nhau.

CÁC PHẢN HỒI

Back to Top