on 10:02 p.m. 20 may, 2020 2

SUMMARY HAPPY SCHOOL

Vậy là 5 series của Happy School đã kết thúc, hãy cùng ami tổng kết lại kì thi nào.

Chúc mừng 5 bạn đạt điểm cao nhất

THÍ SINH ĐIỂM THỜI GIAN
_Kuro_Neko_ 514 03:02:36
thuanqvbn03 443 03:23:36
letangphuquy 426 04:33:33
Vinht1k60 423 04:51:52
NaughtyWind 419 08:00:45

Đây là những người AC đầu tiên cho từng bài

BÀI THÍ SINH THỜI GIAN
A Vinht1k60 00:08:34
B thang 00:12:29
C HynDuf 00:34:16
D ami 00:00:00
E ami 00:00:00
F ami 00:00:00
G thoi_bay_corona 00:00:00

Bằng một cách vi diệu nào đó, thoi_bay_corona không được tính vào bảng rank vì bị kẻ mưu hại set quyền admin. Chúng tôi đang điều tra và sẽ xử lý kẻ gian trong thời gian sớm nhất.

Ngoài ra, contest Happy School đã phá vỡ kỷ lục về số người tham dự, các bạn hãy vỗ tay chúc mừng team ami and fans (a.k.a CaiWinDao, cuom1999, dungde99). Team ami and fans xin cảm ơn các bạn đã bỏ thời gian quý báu tham dự, hi vọng contest đã không phụ lòng các bạn.

Editorial

Các bạn có thể vào từng bài để đọc lời giải. (ví dụ lời giải bài A ở đây)

on 9:03 p.m. 10 may, 2020 7

Happy School

Chào các bạn,

Mình là amicuom1999 hân hạnh được chào đón các bạn trong website mới của Lê Quý Đôn-oj.

Cùng chung không khí hân hoan nhân kỉ niệm 1 tuần ngày toàn dân đưa trẻ quay lại trường, mình và cuom1999 xin góp vui bằng một kỳ thi nhẹ nhàng và đơn giản. Kì thi sẽ diễn ra vào ngày 15/5/2020, lúc 19:00. Các bạn sẽ có 3 giờ để giải quyết 6 bài tập. Kì thi sẽ tính rating cho tất cả các bạn. Kì thi lần này sẽ tuyệt đối cân bằng. Nếu mức độ khó của đề không làm hài lòng các bạn, xin các bạn cứ góp ý và blame cuom1999.

Cuối cùng, mình xin cảm ơn thầy Small, admin và là người tài trợ cho trang web. Cảm ơn cuom1999 đã giúp mình chuẩn bị kì thi này. cuom1999 là người lên ý tưởng, làm bộ test, đảm bảo độ cân bằng cho 6/6 bài, là người gánh team, penta kill, .... Cảm ơn các bạn sẽ tham gia nhiệt tình. Chúc các bạn thu được nhiều kiến thức. Top 3 học sinh của thầy Small giải được 4/6 bài hoặc nhiều hơn sẽ vinh dự được thầy Small mời cafe miễn phí.

Update : Các bài nộp cuộc thi sẽ được chấm trên pretest, nhưng vẫn tính điểm theo kiểu OI. Sau khi kì thi kết thúc, các bài nộp sẽ được chấm với bộ test hoàn chỉnh. Ngoài ra, các bạn là học sinh của thầy Small, nếu bị hệ thống phát hiện code trùng nhau, sẽ được bao thầy Small 3 ly cafe.

Update : Ngày giờ cuộc thi đã được điều chỉnh.

Update : Cảm ơn dungde99 đã giúp kiểm tra đề thi và bộ test, cảm ơn CaiWinDao đã giúp các vấn đề về hệ thống và giải đáp thắc mắc.

Update : Cảm ơn các bạn đã tham gia thử thách cùng ami. Lời giải cho các thử thách đã được post, các bạn có thể truy cập vào các bài để đọc.

on 5:00 p.m. 1 may, 2020 4

Editorial lqdoj004

Vậy là contest lqdoj004 đã được tổ chức thành công! Ngoại trừ một sự cố "nho nhỏ" về phần website khiến cho trang bị sập trong vòng hơn 1 tiếng, còn ngoài ra thì cuộc thi này đã diễn ra rất tốt đẹp =)).

BTC xin chúc mừng 5 thí sinh đứng đầu bảng rank:

THÍ SINH ĐIỂM THỜI GIAN
_Kuro_Neko_ 700 03:02:36
thoi_bay_corona 700 03:23:36
NaughtyWind 600 04:33:33
anhkha2003 600 04:51:52
Vinht1k60 600 08:00:45

Và đây là những người AC đầu tiên cho từng bài (Do web bị sập giữa lúc thi nên số liệu cho những bài đầu có thể không đúng với thực tế):

BÀI THÍ SINH THỜI GIAN
A A519LeVanDuc
thang
BichSonNhat
00:00:13
B A519LeVanDuc 00:00:31
C L8cuberlong 00:00:38
D thang 00:01:00
E thoi_bay_corona 00:31:33
F thoi_bay_corona 00:46:06
G _Kuro_Neko_ 00:32:18

Sau đây là lời giải cho 7 bài:


A - Doraemon và cuộc phiêu lưu ở hòn đảo kho báu [Bản dễ]

Bài này ta chỉ việc làm theo đề bài: Kiểm tra tất cả bộ ~(i, j) \, (L \leq i < j \leq R)~ và tìm giá trị tối thiểu của ~(i \times j) \bmod M~.

Độ phức tạp: ~O((R-L)^2)~


B - Doraemon và những chú khỉ khá là không liên quan

Ta thấy rằng khi học sinh đến sớm thứ ~x~ đi vào lớp thì lúc đó lớp có tổng cộng ~x~ học sinh - nói cách khác, học sinh thứ ~i~ đến sớm thứ ~A_i~. Vậy ta chỉ cần sắp xếp lại mảng ~A~ và tìm vị trí ban đầu của mỗi phần tử sau khi sắp xếp.

Độ phức tạp: ~O(N \log N)~ hoặc ~O(N)~ tùy cách cài đặt.


C - Doraemon và thử thách đầu tiên [Bản dễ]

Xét hàng thứ ~i~, nếu như lúc đầu trên hàng đó có ~0~ hoặc ~1~ con quái vật thì ta chỉ có ~1~ cách tô màu duy nhất (màu trắng hoặc màu của con quái vật tương ứng); còn nếu có ~2~ quái vật thì ta có ~2~ cách tô màu (tùy vào con quái vật bên trái hay bên phải tô màu trước). Vậy đáp án cho bài này là ~2^x~, với ~x~ là số hàng có ~2~ con robot.

Độ phức tạp: ~O(N)~.


D - Doraemon và cuộc phiêu lưu ở hòn đảo kho báu [Bản khó]

Do bài này có giới hạn ~L, R \leq 10^9~ nên có thể các bạn nghĩ là sẽ không thể giải được bài này dùng thuật của bản dễ ;) . Tuy nhiên, ai tinh ý thì sẽ phát hiện ra rằng:

  • Trong ~M~ số tự nhiên liên tiếp nhau thì sẽ luôn có 1 số chia hết cho ~M~.

Vậy nếu như ~(R - L + 1) \geq M~ thì đáp án sẽ luôn là ~0~, ngoài ra thì các bạn có thể dùng thuật của bản dễ để giải bài này.

Độ phức tạp: ~O(M^2)~


E - Doraemon tự kỷ với trò chơi mới

Bài này rất đơn giản, chỉ cần làm theo yêu cầu đề bài: Với mỗi ô trống, đặt bánh rán nâu vào và kiểm tra xem có thể lật được bao nhiêu bánh rán trắng là xong.

Độ phức tạp: ~O(N^3)~, ~O(N^2 \log N)~ hoặc ~O(N^2)~ ~(N = 8)~ tùy cách cài đặt.


F - Doraemon, chú mèo máy đến từ tương lai

Ta có vài nhận xét sau:

  • ~x \oplus x = 0~. (1)

  • Nếu không bit ~1~ nào của ~x~ có cùng vị trí với bit ~1~ của ~y~ (2) thì ~x \oplus y = x + y~.

  • Do ~M \leq 10^9~ nên bit có giá trị cao nhất có thể của ~M~ là ~30~ (Do ~2^{30} = 1073741824 > 10^9~). (3)

  • Nếu ~M | x~ và ~M | y~ (4) thì ~M | (x + y)~.

Không mất tính tổng quát, giả sử ~x \leq y \leq z~. Ta có ~x \oplus y \oplus z = 0 \Leftrightarrow x \oplus y = z~ (1). Nếu ta có thể tìm được ~x~ và ~y~ thỏa mãn (2) và (4) thì khi ta lấy ~z = x + y~ thì ta sẽ có ~1~ bộ ba ~(x, y, z)~ thỏa mãn. Dựa vào ~(3)~, ta có thể chọn ~x = M~ và ~y = M \times 2^{30}~.

Vậy ~1~ bộ ba có thể là ~x = M, y = M \times 2^{30}, z = M + M \times 2^{30}~.

Độ phức tạp: ~O(T)~


G - Doraemon và thử thách đầu tiên [Bản khó]

Đầu tiên ta sẽ loại bỏ hết các hàng và cột không có quái vật nào vì chúng không quan trọng trong bài này.

Gọi ~X~ và ~Y~ là số hàng và cột có quái vật ~(1 \leq X \leq N, 1 \leq Y \leq M)~.

Ta ánh xạ một cách tô màu với một đường đi từ ô ~(0, 0)~ đến ô ~(X, Y)~ như sau:

Xuất phát tại ô ~(0, 0)~, tại một thời điểm mà ta đang đứng ở ô ~(x, y)~, ta đi sang ô ~(x + 1, y)~ nếu ô ~(x + 1, y)~ là ô cuối cùng có màu của hàng ~x + 1~, nếu không ta đi sang ô ~(x, y + 1)~, và ô ~(x, y + 1)~ là ô cuối cùng có màu của cột ~y + 1~ (vì nếu cả hai không phải ô cuối cùng thì ô ~(x + 1, y + 1)~ sẽ có màu của cả hàng ~x + 1~ và cột ~y + 1~).

Ánh xạ là đơn ánh vì với mỗi cách tô màu, ta có một và chỉ một cách đi. Ánh xạ là toàn ánh vì với mỗi cách đi ta chỉ có một cách tô màu. Cách biến đổi từ đường đi về một cách tô màu như sau:

Giả sử ta đang đứng tại vị trí ~(x, y)~. Nếu tại lượt sau ta đi sang ô ~(x + 1, y)~ thì ô này phải là ô cuối cùng có màu của hàng ~x + 1~. Ta tô các ô từ ~(x + 1, 1)~ đến ~(x + 1, y)~ bằng màu của hàng ~x + 1~, sau đó tiếp tục làm tiếp. Khi đến một ô ~(x, y)~, ta đã tô màu cả bảng từ ~(1, 1)~ đến ~(x, y)~ nên sau khi làm xong tất cả các ô đều được tô màu.

Vậy ánh xạ là song ánh, suy ra số cách tô màu bằng số đường đi từ ô ~(0, 0)~ đến ô ~(X, Y)~ hay ~\binom{X + Y}{X}~.

Ở dưới là một ví dụ về ánh xạ giữa cách tô màu và đường đi:

Độ phức tạp: ~O(N \log N)~ hoặc ~O(N)~ tùy vào cách cài đặt.

on 8:50 p.m. 7 apr, 2020 7

Test blog

Cho tam giác ~ABC~ vuông tại A. Chứng minh ~b^2+c^2=a^2~.