Shitpost đêm khuya #5

Q: Lại shitpost đêm khuya, đoán nhé, ông lại được nghỉ đúng không?

A: Chuẩn cmnl, tôi vừa được gia hạn thêm 1 tuần nữa. Cơ mà ở nhà kiểu này tôi thấy chả được tích sự gì: sáng ngủ tới 10h, dậy cày view cho SGO48, chiều ăn uống lên mạng solve mấy bài code, chăm thì khuya lên Khan Academy làm vài bài phương trình vi phân, xong tới tối xem Bomman.

Q: Cuộc sống nghe healthy thế còn đòi mẹ gì nữa?

A: À không, thực ra là trong lúc lên mạng solve bài code hay lên Khan Academy giải toán thì tôi cũng mở SGO48 lên mà nghe ông ạ, thế nên tôi mới viết bài này, chỉ để nói cả buổi tối hôm nay tôi không làm dc gì hết :(

Q: Vậy rốt cục viết post này để khoe cả tối ngồi cày SGO48 thôi?

A: Chuẩn. Giới thiệu vài member nhé: Hikari, Ánh Sáng, Kayceeeeee <3

Đùa thế đủ rồi, mình viết post này để một lúc nào đó nhìn lại sẽ thấy mình đã loser như thế nào trong kỳ nghỉ Tết kéo dài 2 tháng này. Bạn bè mình học được rất nhiều thứ, làm được rất nhiều thứ, mình chỉ ngồi cày code rồi rớt rank code, cày Toán rồi mất gốc Toán :(

Nhưng nói thế thôi, ở quê vui phết ý. Nói vui chứ cả 2 tuần nay mình lười chẳng ra khỏi nhà, sáng ngủ dậy mình lại lên mạng chơi GU, mà gần tuần nay lại nhảy sang cày MV cho SGO48 :| Có thêm idol làm cuộc sống tươi đẹp hơn hay không chưa biết, chỉ biết nhiêu đó tốn mình hết cả dăm bảy buổi sáng rồi :)

Cuối lời, vẫn như mọi shitpost khác trong dịp Tết này: tuần này chưa hết Tết, mà mới bắt đầu Tết thôi. Chúc mừng năm mới!

Nguồn

FRUITS - Chef and Fruits

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

Happy coding!

UWCOI 2020 - online replay (Codechef)

Contest này tính rating, mình không ngờ là tính rating nên solve xong 2 bài + 1 task bài 3 mãn nguyện đi ngủ, tỉnh dậy tụt 23 điểm raitng chui ngược xuống 2* :(

Mà thôi, solution đây:

Bài 1: Peak Finding - đọc đề bài trên Codechef

Bài này chỉ là tìm phần tử max của một dãy N phần tử cho trước.

Code mẫu (C++).

Bài 2: Button Pairs - đọc đề bài trên Codechef

Bài này yêu cầu đếm số cặp trong N số cho trước. Dễ ăn được 60 điểm bằng 2 vòng lặp, nhưng đến test 3 N quá lớn nên phải có cách tiếp cận khác. Phương pháp tiếp cận này lại thuần về toán, đòi hỏi chút kiến thức đại số và xác suất thống kê:

Giả sử ta có 2 số a và b là 2 số nguyên dương, 1 <= a, b <= 1000000 theo yêu cầu của đề bài, x, y là số nguyên dương >= 1 tùy ý:

• Nếu a có dạng 2x (a là số chẵn) và b có dạng 2y + 1 (b là số lẻ), khi đó a + b = 2x + 2y + 1 = 2(x + y) + 1 => kết quả a + b là một số nguyên lẻ. Kết quả tương tự với b là số chẵn và a là số lẻ, vì phép cộng có tính giao hoán.
• Nếu a có dạng 2x (a là số chẵn) và b có dạng 2y (b cũng là số chẵn), khi đó a + b = 2x + 2y = 2(x + y) => kết quả a + b là một số nguyên chẵn.
• Nếu a có dạng 2x + 1 (a là số lẻ) và b có dạng 2y + 1 (b cũng là số lẻ), khi đó a + b = 2x + 1 + 2y + 1 = 2(x + y + 1) => kết quả a + b là một số nguyên chẵn.

Từ đó ta có thể kết luận, một cặp số phù hợp với yêu cầu đề bài là một cặp số gồm 1 số chẵn và 1 số lẻ. Trong dãy N số cho trước ở đề bài, giả sử ta có a số chẵn và b số lẻ. Khi đó, tổng số cặp 1 chẵn 1 lẻ có thể tạo thành là a * b cặp.

Vậy, để AC được task cuối: đếm trong số N số có bao nhiêu số chẵn và bao nhiêu số lẻ, nhân lại sẽ ra kết quả.

(Chú ý phải để kiểu dữ liệu long trong C mới đủ cho test bài này).

Code mẫu (C++).

Happy coding!

Codechef February Long Challenge 2020 - Division 2

Đăng file Zip lên GitHub có lẽ là một ý tưởng tệ vô cùng :( Thôi thì quay trở lại viết lách trên blog vậy.

Phải đăng cái hình này để phân biệt mấy bài contest, bài này nhiều hình nên dễ bị sai thumbnail

Bài viết lần này sẽ là về Long Challenge tháng 2. Lần này solve được 3 bài, code nhấn mạnh là rất xấu, tuy nhiên editorial của 3 bài này lại cùng phương pháp với mình. Nhấn mạnh là code lần này rất xấu nên cân nhắc kỹ trước khi copy hay cố gắng hiểu code các bạn nhé?

Bài 1: School of Geometry - đề bài tiếng Việt

Đề bài yêu cầu tìm giá trị lớn nhất có thể của tổng đường kính N hình tròn. Bài này giải bằng cách sort lần lượt các dãy A và B từ lớn tới nhỏ, khi đó mỗi cặp A[i] và B[i] là 2 cạnh của 1 hình chữ nhật. Tính tổng đường kính các hình chữ nhật đó sẽ được đáp án theo đề bài.

Notes:

• Chú ý điều kiện ràng buộc A[i], B[i] <= 10^9 và N <= 10^4. Trường hợp tệ nhất là 10^4 * 10^9 = 10^13 => phải dùng kiểu dữ liệu long long trong C/C++ hay int_64 trong Pascal.
• Đường kính hình tròn nội tiếp hình chữ nhật tạo bởi cặp A[i] và B[i] bằng độ dài cạnh nhỏ hơn trong cặp A[i] và B[i]. Bạn có thể vẽ hình để kiểm chứng.

Code mẫu (C++).

Bài 2: Hard Cash - đề bài tiếng Việt

Đề bài yêu cầu phân phối các đồng xu theo chiều từ trái qua phải, sao cho số xu của mỗi túi (sau khi phân phối) chia hết cho K và số xu còn dư ra là nhỏ nhất có thể. Từ đây ta có thể suy ra tư tưởng chia xu: chia nhiều nhất có thể để số xu của một túi trở thành bội của K và lấy ít nhất có thể để số xu của một túi trở thành bội của K. Nếu số xu túi đó đã là bội của K thì không lấy cũng không thêm.

Nói ra nghe có vẻ khó, nhưng trong thực tế cài đặt giải thuật khá dễ. Ta gọi S là số xu dư ra, mỗi lần bỏ thêm xu vào một túi ta sẽ lấy xu từ S, mỗi lần lấy xu từ một túi ta sẽ bỏ vào S. Để bỏ xu vào một túi, ta cộng S với số xu hiện tại của túi đó rồi chia lấy dư cho K - phần dư sẽ là phần xu còn lại của S sau khi bỏ số xu cần thiết để số xu trong túi đó chia hết cho K. 

Cụ thể ta lấy test mẫu số 2 làm ví dụ:

3 9

1 10 19

Ban đầu S = 0. 

• Bước 1: (S + số xu túi 1) mod 9 = (1 + 0) mod 9 =  1. S = 1
• Bước 2: (S + số xu túi 2) mod 9 = (1 + 10) mod 9 = 2. S = 2.
• Bước 3: (S + số xu túi 3) mod 9 = (2 + 19) mod 9 = 3. S = 3. Đây cũng là kết quả.

Code mẫu (C++). 

Bài 3: The Theatre Problem - đề bài tiếng Việt

Đề bài yêu cầu chọn thởi điểm phát phim, sao cho mỗi giờ chỉ chiếu 1 bộ phim và doanh thu đạt được cao nhất. Nếu bạn để ý kỹ thì N <= 100 => brute force được.

Code mẫu (C++)

Tổng kết: Contest lần này ăn 300 điểm, nhưng gánh mình lên 3* là Cook-off. Nhưng cũng phải bổ sung quả ảnh ăn mừng lên 3* :D

Do đây là lần đầu cháu nó lên rank nên các bạn thông cảm, cảm ơn các bạn nhiều.

3* nè he

biểu đồ nè he

biểu đồ cột nè he

Năm mới vui vẻ, Happy coding!

Codechef February Cook-off 2020 - Divison 2

Trong post này sẽ có bản hướng dẫn giải + code mẫu cho 2 bài:

• TAX SLABS - Link đề bài
• PENALTY SHOOT-OUT II - Link đề bài

Link hướng dẫn giải + code mẫu (file ZIP)

Happy coding!

SPOJ PTIT135F - Đếm cửa sổ

Link đề bài

Hướng dẫn giải: Ở đây ta không cần duyệt hết từng phần tử của lưới mà chỉ cần duyệt các điểm tô đỏ dưới đây:

################
#****#****#****#
#****#****#****#
#****#....#****#
#....#....#****#
################
#....#****#****#
#....#****#....#
#....#....#....#
#....#....#....#
################

(Test mẫu số 2)

Xét ô cửa tiêu chuẩn (6x6):

######
#****# <- Dòng 1
#****# <- Dòng 2
#****# <- Dòng 3
#****# <- Dòng 4
###### (Ô này đang ở trạng thái kéo 4/4 - trạng thái kết quả thứ 5)

• Nếu ô đầu tiên của dòng 4 là dấu * thì ô cửa kéo 4/4 - trạng thái thứ 5
• Nếu ô đầu tiên của dòng 3 là dấu * mà ô đầu dòng 4 khác * thì ô cửa kéo 3/4 - trạng thái thứ 4
• Tương tự với trạng thái thứ 3, thứ 2.
• Đến khi xét ô đầu dòng 1 khác * thì ô cửa kéo 0/4 - trạng thái thứ 1

Kết hợp với phép đếm, ta dễ dàng tìm được kết quả theo đề bài.

Code mẫu (C)

Update: một bài tập khác cũng có nội dung tương tự là PTITSU1D. Lời giải cho bài tập này, xem tại đây.

Happy coding!

Shitpost đêm khuya #4

Chào các bạn, mình lại viết bài này khi đang ở Bến Tre.

Sở GD-ĐT TPHCM vừa gia hạn thời gian nghỉ cho các trường đến hết 29/02/2020. Điều đó có nghĩa là mình lại có 2 tuần nghỉ nữa, nhưng chưa hẳn là nghỉ vì bọn mình vẫn phải học online từ đầu tuần sau :)

Học sinh tỉnh mình thì không được như vậy. Công văn của tỉnh vẫn cho phép học sinh quay trở lại trường học từ đầu tuần sau (17/02/2020), nhưng theo mình thì các lãnh đạo ngành cũng sẽ dời ngày đến đầu tháng 3 như TPHCM. Thế là như lời một cô bé reply story Instagram của mình, "kẻ ăn không hết người lần chẳng ra", TPHCM vẫn được nghỉ trước các tỉnh khác, và thậm chí lần này còn được nghỉ nhiều.

Sinh viên bọn mình học hành tự do lắm, riêng mình toàn đi học cho vui, đến trước ngày thi mới giở sách ra đọc hoặc lên Khan Academy xem video lý thuyết, thế mà vẫn qua môn bình thường, duy chỉ có điểm không cao. Học sinh lại khác, nhất là học sinh cuối cấp, vì đây là thời điểm nước rút, quyết định cho toàn bộ chặng đường của các em phía trước. Dời lịch học có thể dời luôn cả lịch thi THPTQG, nhưng theo mình căng thẳng nhất vẫn dồn vào vai các em học sinh. Thời gian ôn tập của các em có thể dài hơn, nhưng mình đã trải qua thời gian này rồi, khoảng thời gian ôn thi là căng thẳng hơn cả lúc làm bài thi hay đợi điểm thi. Nhưng qua được giai đoạn này thì ai cũng chơi bời bê bét, như mình bây giờ :)

Tối nay lại là tối 29 Tết đối với sinh viên bọn mình, sáng ngày mai lại là 30 Tết lần thứ 2. 

Nguồn

Chúc mừng năm mới!

WILLITST - Will it ever stop

Đọc đề bài trên SPOJ

Shitpost đêm khuya #3

Mình viết post này ở Bến Tre. Tỉnh duy nhất trong 63 tỉnh không ban hành văn bản cho phép học sinh nghỉ học để phòng tránh virus nCoV. Trường mình vừa dời lịch học GDQP (Giáo dục quốc phòng) sang tháng 4, đủ để thấy tình hình trên Sài Gòn căng thẳng tới mức nào. Duy chỉ có Bến Tre vẫn giữ y quan điểm, không cho nghỉ lấy 1 ngày.

Quan trọng là, ở Bến Tre những người làm giáo dục vẫn chưa nhìn thấy được tình hình cấp bách và sự nguy hiểm của dịch nCoV. Vì Bến Tre là tỉnh nằm cách biệt với các tỉnh khác bởi sông Cổ Chiên và sông Tiền, nếu thực sự có dịch bệnh xảy ra ở các tỉnh xung quanh các quan chức chỉ việc chặn cầu qua 2 con sông trên và Bến Tre tách biệt với phần còn lại của đất nước :)

Ở Bến Tre người ta vẫn sinh hoạt bình thường. Dẫu có sợ virus đó, dẫu có sợ bị lây bệnh đó nhưng mà nó chưa tới, chưa xuất hiện và quan trọng là người ta chưa thấy thì người ta cũng chẳng phải lo lắng gì nhiều. Bởi với họ, cơm áo gạo tiền là quan trọng hơn cả, học sinh được nghỉ 1 ngày thì còn có gia đình nuôi còn người lao động nghỉ đi 1 ngày là mất đi 1 ngày tiền thu nhập. Nói vậy, như lời chú cắt tóc cho mình: "nghe thì ghê nhưng mà thấy tao mới sợ!". Vậy nên suy nghĩ của lãnh đạo tỉnh hay những người làm giáo dục cũng đúng, bởi trò mà nghỉ đi 1 ngày thì lại mất 1 ngày kiến thức, mà trò nghỉ thì thầy cũng phải nghỉ theo, rồi bù thêm này nọ phiền phức chết đi được. Vậy là cả tỉnh lại đi học.



Thôi thì vào học muộn tí cũng chẳng sao, Tết lại kéo dài thêm 1 tuần nữa :) 

Update 07/02/2020: Tết lại về với Bến Tre :)

PPSUM - Puppy and Sum

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

Hướng dẫn giải + code mẫu

Happy coding!

Shitpost đêm khuya #2

Hôm nay là ngày 02 tháng 02 năm 2020. Lúc mình viết bài này là 11:11PM, 5 tiếng sau khi trường mình ra thông báo nghỉ học để phòng chống virus Corona.

Mình từ Bến Tre lên Sài Gòn lúc 14:15PM, đến nơi lúc 18:00PM thì khoảng 30 phút sau trường thông báo nghỉ :) Trùng hợp làm sao hôm nay lại là mồng 9 Tết Âm lịch, ngày cuối cùng của kỳ nghỉ Tết Nguyên đán, cho nên bọn mình đã đùa nhau rằng nghỉ Tết mấy tuần vừa qua chỉ là nghỉ Test, đến hôm nay mới nghỉ Release :))

https://tuoitre.vn/hon-60-dai-hoc-cho-sinh-vien-nghi-phong-dich-20200202122227919.htm

VNUHCM nói chung và HCMUS nói riêng là một trong những trường ra thông báo nghỉ học chậm nhất, nhưng không muộn bằng UFM với NLU. Cho nên mới hồi nãy ở ngoài cửa sổ các ông NLU với UFM cứ thi thoảng lại hú lên, "NLU vẫn đéo cho nghỉ chúng mày ơi!", tầng dưới lại vọng lên, "NLU cố lên nhé, mạnh mẽ lên". Bỗng văng vẳng vang lên "đụ má NLU cho nghỉ rồi aaaa", rồi tiếng vỗ tay, tiếng hú, cứ thế vang vọng phá tan không gian im lặng tĩnh mịch của đêm KTX.

Ngày mai mình lại về Bến Tre, Tết đối với bọn mình vẫn còn. Tết của chúng mình đến từ cách xa hàng ngàn cây số, từ công văn của BGDvĐT, nhưng chỉ mới đến với bọn mình cách đấy mấy giờ.
Mà thôi, Tết còn mà, ăn chơi cái đã :) Bye