Editorial Happy School 1

ami - 07/03/2020

A

Idea : cuom1999, tester : ami

Điều kiện cần và đủ để thắng trò chơi là n chia hết cho k. Vì vậy, các bạn chỉ cần kiểm tra điều kiện này.

B

Idea : cuom1999, tester : ami

Khởi tạo mảng cnt[ x ] là số kì thi mà học sinh có id = x đã tham gia. Học sinh x sẽ tham gia tất cả kì thi nếu cnt[ x ] = n, học sinh x sẽ tham gia ít nhất một kì thi nếu cnt[ x ] ≥ 1. Ta có thể tính toán x bằng cách for hết tất cả các kì thi i và idi,j trong kì thi đó, tăng cnt[ idi,j ] lên 1. Để tránh đếm một thí sinh 2 lần trong 1 kì thi, ta có thể sắp xếp lại các id trong 1 kì thi theo thứ tự tăng dần, và chỉ tăng cnt[ idi,ị ] nếu idiị = idi,j-1.

Sau đó, để in kết quả, có thể for hết các id theo thứ tự từ 1 đến 106 (vì các id chỉ nằm trong khoảng này) và kiểm tra điều kiện cần.

C

Idea : ami, tester : cuom1999

Gọi cntL[ c ] là số lần xuất hiện kí tự c trong bảng L. cntN[ c ] là số lần xuất hiện kí tự c trong bảng N.

Rõ ràng, nếu cntL[ c ] <= cntN[ c ], ta không nên đổi kí tự c của bảng L thành bất kì kí tự nào khác, vì như vậy, sẽ lại tốn thêm một thao tác để tăng cntL[ c ] về lại số ban đầu. 

Ta sẽ chỉ thay đổi các kí tự c mà cntL[ c ] > cntN[ c ]. Để thay đổi một cách tối ưu, ta sẽ chuyển c về một trong các kí tự c1 mà cntL[ c1 ] < cntN[ c1 ].

Vậy, ta có thuật toán như sau, tím một kí tự c bất kỳ và một kí tự c1 bất kì mà cntL[ c ] > cntN[ c] và cntL[ c1 ] < cntN[ c1 ]. Sau đó, thực hiện việc thay đổi c thành c1 cho đến khi cntL[ c ] = cntN[ c ] hoặc cntL[ c1 ] = cntN[ c1 ]. Độ phức tạp sẽ khoảng N*262.

Có thể thực hiện nhanh hơn, quan sát rằng, mọi phần dư ra của một kí tự c mà cntL[ c ] > cntN[ c1 ] đều được thay đổi. Ta sẽ for hết các kí tự từ 'a' - 'z' và tính tổng của phần dư ra này. Đó chính là kết quả.

E

Idea: cuom1999, tester: ami

Cách 1: Quy hoạch động

Đặt d[i] là đáp án ứng với số i. Khi đó d[2k] = 1 và d[0] = 0.

Nếu i không là lũy thừa của 2, gọi k là số thỏa mãn 2k < i < 2k+1. Nhận thấy rằng cách tối ưu lúc này là viết i = 2k + j hoặc i = 2k + 1 - j với j là một số chắc chắn nhỏ hơn i (do j = 2k+1 - i < 2k). Do đó d[i] = min(d[i - 2k], d[2k + 1 - i]) + 1.

ĐPT: O(n)

Cách 2: BFS

Vì n chỉ có 106 nên có thể tạo một đồ thị gồm 222 đỉnh (vì sao?), với mỗi đỉnh ứng từ 0 tới 222 - 1.  Mỗi đỉnh i sẽ được nối tới các đỉnh i + 2k và i - 2k (0 <= k <= 21 và các số này phải >= 0 và < 222 ). Nhiệm vụ còn lại là tìm đường đi ngắn nhất từ 0 tới n và có thể dùng BFS.

ĐPT: O(m + n) = O(nlogn) vì từ mỗi đỉnh có logn cạnh

F

Idea : ami, tester : cuom1999

Ta sẽ tính toán cách đổi tiền tối ưu - là cách đôi x thành ít đồng tiền nhất, sử dụng ฿25, ฿10, ฿5, ฿1. Với một đồng tiền i, cách đổi tối ưu sẽ là : 

     *Đổi x thành nhiều đồng ฿25 nhất gọi kết quả này là u , tính phần dư ra y (y < 25).

     *Đổi y thành ít đồng tiền nhất, sử dụng các đồng ฿1, ฿5, ฿10, gọi kết quả này là v

Cách đổi tối ưu sẽ là u + v.

Quan sát rằng, vì y < 25, ta gọi cnt[ y ] là cách đổi y thành ít đồng tiền nhất sử dụng ฿1, ฿5, ฿10. Có thể tính y bằng quy hoạch động, đệ quy, tham.

Như vậy, với một số x, ta luôn có thể biểu diễn

     *i = u * 25 + y

Để tính xem có bao nhiêu đồng tiền i <= k và không dùng quá x đồng tiền,  ta sẽ for hết các phần dư y có thể.

Với mỗi y, ta đã biết rằng sẽ cần dùng ít nhất là cnt[ y ], vậy bài toán đưa về đến xem có bao nhiêu u mà u * 25 + y ≤ k và u + cnt[ y ] ≤ x. Mình sẽ để phần tính toán này như một bài tập cho các bạn. Độ phức tạp sẽ là O(25).

G

Idea: cuom1999, tester: ami

Đặt g = gcd(a, b)

Đầu tiên, ta nhận thấy rằng nếu x hoặc y không chia hết cho g thì đáp án là NO

Nếu ngược lại, có thể thực hiện thao tác a /= g, b /= g, x /= g, y /= g.

Lúc này gcd(a, b) = 1.

Các ô đi tới được từ (0, 0) là (au + bv, am + bn) với u = n (mod 2) và v = m (mod 2).

Vì (a, b) = 1 nên tồn tại i, j thỏa mãn ai + bj = 1 (định lý Bezout).

 

TH1: a + b lẻ, giả sử a chẵn b lẻ -> đi được tới mọi (x, y)

Chứng minh:

Chọn n = -a, m = b -> đi được tới (au + bv, 0) thỏa mãn u = a (mod 2) và v = b (mod 2).

Vì a * i chẵn và ai + bj = 1 nên j lẻ

+ Nếu i chẵn thì chọn (u, v) = (i, j)

+ Nếu i lẻ thì chọn (u, v) = (i + b, j - a)

Khi đó au + bv = 1 -> đi đến được (1, 0). Tương tự đi đến được (0, +-1) và (-1, 0) nên đi đến được mọi ô. 

 

TH2: a, b lẻ -> đi được tới (x, y) thỏa mãn x + y chẵn

Chứng minh:

Do a, b lẻ nên i + j chẵn

ĐK cần: tô màu trắng đen xen kẽ như bàn cờ. Giả sử ô (0, 0) là ô trắng thì con mã luôn nhảy tới ô trắng hay x + y luôn chẵn

ĐK đủ: 

+ Nếu i lẻ, j lẻ thì chọn (u, v) = (m, n) = (i, j) -> au + bv = am + bn = 1 -> đi đên được ô (1, 1)

+ Nếu i chẵn, j chẵn thì chọn (u, v) = (m, n) = (i + b, j - a) -> au + bv = am + bn = 1 -> đi đến được ô (1, 1)

Do đó (0, 0) đi được tới (1, 1), và tương tự (+- 1, +- 1) -> đi được tới mọi ô (x, y) mà x + y chẵn

 

 

CÁC PHẢN HỒI

Back to Top