A

Idea : Ami , Tester : Cuom1999

Với các phần tử nguyên dương, cách làm tối ưu là chọn phần tử lớn nhất trừ đi 1.

Chứng minh :

(*) Với a , b nguyên dương và a > b, ta có :

 

(a-1) * b = a*b - b < a*b - a  = a*(b-1).

 

Để chứng minh điều tương tự cũng đúng với một dãy số nguyên dương, đầu tiên ta có thể sort dãy số lại theo thứ tự tăng dần, và gọi S = a1*a2*a3*...*an. Ta sẽ so sánh 2 cách chọn phần tử là chọn ai và chọn aj, và ai < aj. Tích của dãy số sau khi chọn ai sẽ là :

 

S1 = S/(ai * aj) * (ai-1) * aj. 

 

Tích của dãy số sau chi chọn aj sẽ là :

 

S2 = S/(ai * aj) * ai * (aj-1). 

 

So sánh tích S1 và S2, ta sẽ so sánh (ai-1) * aj và ai * (aj-1). Theo nhận xét (*), ta có :

 

(ai-1) * aj < ai * (aj-1).

 

Vì vậy S1 < S2, và cách chọn phần tử lớn nhất sẽ đem lại kết quả tối ưu,

B

Idea : Cuom1999 , Tester : Ami

Bài này các bạn chỉ cần làm theo những gì đề bài yêu cầu. Do mỗi xúc xắc chỉ có 6 khả năng nên có thể dùng 3 vòng lặp for lồng nhau để xét hết tất cả khả năng có thể của chúng. 

C

Idea : Ami , Tester : Cuom1999

Ước chung bất kì của một dãy số sẽ là một ước của ước chung lớn nhất của các phần tử trong dãy số đó. Vậy, các bạn có thể tìm ước chung lớn nhất của dãy số, gọi là U và tìm số K nhỏ nhất mà U chia hết cho K. Kết quả bài toán chính là K.

D

Idea : Cuom1999 , Tester : Ami

Do giới hạn của tọa độ là [-500,500] và bán kính hình tròn <= 500 nên tất cả những điểm nguyên cần tìm có tọa độ trong [-1000,1000]. Vì vậy có tối đa 1e6 điểm cần xét. Với mỗi điểm nguyên cần kiểm tra nó có thuộc 1 trong 3 hình hay không. Hình chữ nhật và hình tròn khá cơ bản. Hình tam giác có thể kiểm tra như sau:

Giả sử điểm đang xét là X và tam giác ABC. X nằm trong ABC nếu S(ABX)+S(ACX)+S(BCX) = S(ABC) với S là diện tích. Để tính diện tích tam giác chúng ta có thể dùng công thức ở đây https://www.mathvn.com/2015/11/cong-thuc-tinh-dien-tich-tam-giac-theo.html?m=1

E

Idea : Ami , Tester : Cuom1999

Để không học sinh nào được 0 điểm, ta phải đảm bảo không có học sinh nào sai tất cả các câu. Và đáp án của thầy giáo CàiWinDạo phải đảm bảo điều này. Vậy, nếu ta đảo ngược đáp án của thầy CàiWinDạo, không có học sinh nào có đáp án trùng với đáp án đảo ngược này. Vì nếu có, học sinh đó sẽ được 0 điểm, và thầy CàiWinDạo sẽ khóc hu hu.

Vì các đáp án chỉ có dạng True hoặc False, ta có thể biểu diễn các đáp án bằng một dãy nhị phân với 0 là False và 1 là True. Từ đó, bài toán có thể phát biểu lại thành “tìm một dãy nhị phân độ dài m sao cho trạng thái nghịch đảo của dãy nhị phân này không tồn tại trong tập S". Trạng thái nghịch đảo của một dãy nhị phân B là một dãy nhị phân B' cùng độ dài, và  bit của B' là nghịch đảo các bit tương ứng của B. Ví dụ: nghịch đảo của 111 là 000, nghịch đảo của 010 là 101. 

Để giải quyết bài toán này, chúng ta có thể đảo ngược tất cả các dãy bit trong tập S và mã hoá các trạng thái này thành một số nguyên ở hệ cơ số 10. Vì dãy bit chỉ có độ dài tối đa 50 (có tối đa 50 câu hỏi trong đề thi của thầy giáo CàiWinLậu), nên số nguyên này sẽ có giá trị tối đa là 2⁵⁰-1. Sau đó tìm Mex của dãy số. Mex của một dãy số là số nguyên không âm bé nhất không xuất hiện trong dãy số. Gọi n là độ dài dãy số, có thể chứng minh Mex <= n + 1. 

Vận dụng nhận xét này, ta có thể duyệt hết n + 1 số nguyên không âm đầu tiên và kiểm tra xem số này có tồn tại trong tập S không. Nếu không tồn tại thì đây chính là nghịch đảo của kết quả cần tìm. Các bạn nên lưu ý rằng, vì số nguyên chỉ có giá trị tối đa là 2^m-1. Do đó nếu Mex lớn hơn giá trị này, ta có thể in ra “LN".

F

Idea : Cuom1999 , Tester : Ami

Đặt P(a, b, c) = a³ + b³ + c³ - 3abc = (a+b+c)[(a-b)² + (a-c)² + (b-c)²]/2

 

Hướng tiếp cận đầu tiên là thử cày trâu a, b, c tầm 100 để tìm quy luật. Sau khi thử ta thấy được các số n nhỏ thỏa mãn là 0 1 2 4 5 7 8 9 10 11 13 … Từ đây có thể suy đoán các số n sẽ có dạng 3k+1, 3k+2, hoặc 9k. 

 

Đồng thời ta cũng có magic:

P(a, a, a+1) = 3a+1

P(a, a+1, a+1) = 3a+2

P(a-1, a, a+1) = 9a

 

Bài toán kết thúc!

 

Tại sao lại có magic như vậy? Đầu tiên nhìn vào biểu thức P(a,b,c) chúng ta thấy có 2 nhân tử. Nhân tử thứ hai có dạng [(a-b)² + (a-c)² + (b-c)²] nên ta có thể nghĩ đến việc thử các số a,b,c gần nhau.  

 

Chứng minh cho TH n chia hết cho 3 nhưng không chia hết cho 9: Ta có a³ = a (mod 3) (Fermat nhỏ) nên P(a, b, c) = a+ b+ c (mod 3). Do đó a + b + c chia hết cho 3. Vì vậy nhân tử còn lại =(a² + b² + c² - ab - bc - ca) = (a + b + c)² - 3(ab+bc+ca) cũng chia hết cho 3 nên P(a, b, c) chia hết cho 9 (mâu thuẫn).

 

G

Idea : Cuom1999 , Test : Ami

Cách 1: Giả sử có x nhóm k và y nhóm (k + 1) với x*k + y*(k + 1) = n. Số cách chia là: 

                                               

Giải thích công thức: 

n! là số hoán vị của n người

x! là số hoán vị của x nhóm k

y! là số hoán vị của y nhóm (k + 1)

k! là số hoán vị trong mỗi nhóm k người, do có x nhóm nên ta phải chia cho (k!)^x

Tương tự cho (k+1)!^y

 

Vì n chỉ có 10⁵ nên có thể tìm hết mọi cặp x, y thỏa mãn điều kiện và cộng tổng tất cả biểu thức trên. Mỗi biểu thức có thể như trên có thể tính trong O(1) hoặc O(log) nếu tính sẵn mảng fact[i] = i! % MOD. Đồng thời nghịch đảo modulo có thể được tính: x^(-1) % MOD = x^{(MOD - 2)} % MOD. Lưu ý: Công thức nghịch đảo này chỉ đúng cho MOD là số nguyên tố.

 

 

Cách 2 : Có thể giải bài toán này bằng cách quy hoạch động. Giả sử chúng ta cần tìm cách chia i người thành các nhóm có k hoặc k+1 người. Cố định 1 người ở nhóm 1, ta có thể chọn k-1 (nếu muốn số người trong nhóm 1 là k người)  hoặc k người (nếu muốn số người trong nhóm 1 là k+1 người) trong số i-1 người còn lại và tìm cách chia i-k (nếu đã chọn k người vào nhóm 1) hoặc (i - (k+1)) (nếu đã chọn k+1 người vào nhóm 1) sao cho thoả mãn yêu cầu. Công thức chọn k người từ n người không tính thứ tự chính bằng công thức tổ hợp C(n,k)  = (n!) / (k! * (n-k)!).

Vậy ta có công thức quy hoạch động như sau : 

        F[i] = F[i - k] * C(i-1, k-1) + F[i - (k+1)] * C(i-1,k).

        F[0] = 1

H 

Idea : CaiWinDao , Tester : Cuom1999

Đề bài có thể được viết ngắn gọn lại như sau: Cho dãy a1, a2, …, an và q truy vấn. Mỗi truy vấn có 1 số x, hãy in ra x % a1 % a2 % …. % an. Để giải quyết mỗi truy vấn nhanh, chúng ta cần 1 nhận xét như sau:

* Nhận xét: Nếu x >= a thì x % a < x / 2. Chứng minh xem ở phía cuối.

Từ nhận xét trên, ta thấy rằng phép modulo chỉ được áp dụng tối đa O(logMAX). Thuật toán của bài này như sau: 

    index  = 0;

    x = truy vấn cần tìm;

    while (index <= n):

        (1) tìm i nhỏ nhất sao cho i > index và a[i] <= x 

        if tìm được i:

x %= a[i]

index = i

else:

    break

    return x

 

Cuối cùng chúng ta cần giải quyết bước (1). Ta sử dụng tìm kiếm nhị phân như sau:

Đặt prefixMin[i] = min(a[1], a[2], …, a[i]). Chúng ta có thể tính được prefixMin bằng cách tiền xử lý trong O(n): prefixMin[i] = max(prefixMin[i - 1], a[i]). Bước (1) sẽ trở thành tìm i nhỏ nhất sao cho prefixMin[i] <= x và có thể được tính trong O(logn) bằng tìm kiếm nhị phân.

 

Nhưng chắc gì i tìm được > index? vì x = x_original % a[1] % a[2] % … % a[index] nên x < a[1], a[2], …, a[index] nên min(a[1], a[2], …, a[index]) > x, do đó chắc chắn i tìm được phải > index.

 

* Chứng minh nhận xét: Chia 2 TH:

    TH1: a <= x / 2. Ta có x % a < a <= x / 2

    TH2: a > x / 2. Ta có x % a = x - a < x - x / 2 = x / 2