Codechef December Challenge 2020 - Division B

 Trước hoặc trong những giờ deadline căng thẳng, mình thường mở coding contest lên và dành nhiều chất xám + thời gian cho nó, trong khi đáng lẽ ra nên dành cho những deadline hay bài tập kia.

Contest này làm được 4 bài, đáng lẽ ra thời gian viết cái editorial này mình nên ngồi đọc sách để làm quiz thì lại bỏ thời gian ra ngồi gõ cạch cạch viết blog. Ngạc nhiên chưa.

Và làm được 4 bài là do đề dễ, không phải do mình giỏi.

---

VACCINE1 - Vaccine Production

Tóm tắt: Công ty A bắt đầu sản xuất vaccine COVID từ ngày $D_1$, mỗi ngày sản xuất được $V_1$ liều vaccine. Công ty B bắt đầu sản xuất vaccine từ ngày $D_2$, mỗi ngày sản xuất được $V_2$ liều vaccine. Hiện tại là ngày 1, cần $P$ lô vaccine, tìm số ngày ít nhất để sản xuất đủ $P$ liều.

Hướng dẫn: Toán. Tổng số ngày sản xuất  = số ngày trước khi 2 công ty sản xuất + số ngày công ty A sản xuất trước công ty B + số ngày công ty B sản xuất trước công ty A + số ngày cả 2 công ty sản xuất để đủ $P$ liều.

Code mẫu (C++).

---

EVENPSUM - Even Pair Sum

Tóm tắt: Cho 2 số nguyên dương $A$ và $B$, tìm xem trong khoảng từ $1\le x\le A,1\le y\le B$ có bao nhiêu cặp $(x,y)$ sao cho $x+y$ chẵn.

Hướng dẫn: Toán. Để $x+y$ chẵn thì chỉ có 2 trường hợp $x$ và $y$ đều chẵn hoặc đều lẻ.

Chứng minh: 

• trường hợp $x$ và $y$ đều chẵn, ta có thể viết lại $x$ dưới dạng $x=2a$, $y$ dưới dạng $y=2b(a,b\in \mathbb{Z})$. Khi đó $x+y=2a+2b=2(a+b)$ là một số chẵn.
• trường hợp $x$ và $y$ đều lẻ, ta có thể viết lại $x$ dưới dạng $x=2a+1$, $y$ dưới dạng $y=2b+1(a,b\in \mathbb{Z})$. Khi đó $x+y=2a+2b+2=2(a+b+1)$ là một số chẵn.

Giả sử ta đếm được $n$ số chẵn trong đoạn $[1,A]$, $m$ số chẵn trong đoạn $[1,B]$. Khi đó tổng số lượng cặp chẵn-chẵn tạo thành sẽ là $n\times m$. Tương tự, đếm được $u$ số lẻ trong đoạn $[1,A]$, $v$ số lẻ trong đoạn $[1,B]$. Tổng số lượng cặp lẻ-lẻ tạo thành là $u\times v$.

Tóm lại, đáp án là $(n\times m)+(u\times v)$ với $n,m,u,v$ được định nghĩa như trên.

Code mẫu (C++).

---

VACCINE2 - Vaccine Distribution

Tóm tắt: Chefland có $N$ người, người thứ $i$ có tuổi là $a_i$. Bệnh viện Chefland chỉ có thể tiêm vaccine cho $D$ người mỗi ngày. Một người $\ge 80$ tuổi hoặc $\le 9$ tuổi sẽ được xem là có nguy cơ nhiễm bệnh, số còn lại được xem như ít có nguy cơ nhiễm bệnh. Biết rằng mỗi ngày chỉ tiêm vaccine cho một nhóm người, có nguy cơ hoặc ít có nguy cơ, tìm số ngày ít nhất để tiêm hết cho $N$ người. 

Hướng dẫn: Toán. Gọi số người có nguy cơ là $x$, số người ít nguy cơ là $y$. Khi đó tổng số ngày = ${\displaystyle \lceil \frac{x}{D}\rceil +\lceil \frac{y}{D}\rceil }$.

Code mẫu (C++).

---

POSPREFS - Positive Prefixes

Tóm tắt: Mảng $A$ gồm $N$ phần tử được xây dựng sao cho $A_i=-i$ hoặc $A_i=i$. Cho số nguyên $K(1\le K\le N)$, tìm một cách xây dựng lại mảng $A$ sao cho có đúng $K$ vị trí $i$ thỏa $1\le i\le N$ và ${\displaystyle \sum _{j=1}^i{A}_j>0}$ (1).

Phát biểu (1) tương đương với phát biểu tìm một cách xây dựng mảng $A$ sao cho có đúng $N-K$ vị trí $i$ thỏa ${\displaystyle \sum _{j=1}^i{A}_j\le 0}$. (2)

Hướng dẫn: Algoritham.

Giả sử ban đầu ta có mảng $A$ dương $(A_i=i,\mathrm{\forall }i\in [1,N])$. Để xây dựng mảng $A$ theo phát biểu (1) thì hơi lằng nhằng, nên mình sẽ theo phát biểu (2). Khi đó, ta sẽ tiến hành đảo dấu một số phần tử để thu được $N-K$ vị trí $i$ thỏa điều kiện đề bài.

Để làm việc đó, ta đảo dấu thuận - đảo dấu các phần tử tại vị trí $i$ lẻ, bắt đầu từ đầu mảng. Nếu đến hết mảng mà chưa đủ $N-K$ phần tử thì ta tiến hành đảo dấu nghịch - đảo dấu các phần tử ở vị trí $i$ chẵn, nhưng lần này bắt đầu từ cuối mảng.

Ví dụ 1: $N=10,K=6,N-K=4$.

Đảo dấu thuận: $A=\{1,-2,3,-4,5,-6,7,-8,9,10\}$. Ta nhận thấy mảng này đã thỏa đề bài.

Ví dụ 2: $N=10,K=2,N-K=8$.

Đảo dấu thuận: $A=\{1,-2,3,-4,5,-6,7,-8,9,-10\}$. Ta chỉ mới thu được 5 vị trí $i$ thỏa đề bài, nên sẽ tiến hành đảo dấu nghịch.

Đảo dấu nghịch: $A=\{1,-2,3,-4,-5,-6,-7,-8,-9,-10\}$. Ta nhận thấy mảng này đã thỏa đề bài.

Chú ý là một khi đã đổi dấu phần tử $A_i>0$ thành $A_i\le 0$, ta không đổi ngược lại.

Code mẫu (C++).