Bạn được cho một dãy số nguyên dương $a_1, a_2, ..., a_n$. Bạn hãy tính tổng các tích của các dãy con liên tiếp khác rỗng của dãy số trên, hay nói cách khác, hãy tính tổng các giá trị $a_l \times a_{l + 1} \times ... \times a_r$ với mọi $1 \le l \le r \le n$.

3
1 2 3

20

5
1 2 3 4 5

409

Đây là một phiên bản khó hơn của bài toán trong sách giáo khoa. Statement được chép nguyên văn từ sách.

Hồng có $n$ file dữ liệu được đánh số từ $0$ đến $n - 1$ và có kích thước tương ứng là $s_0, s_1, ..., s_{n - 1}$ (Mb). Hồng muốn tìm cách lưu trữ nhiều file dữ liệu nhất bằng hai đĩa ổ cứng, mỗi ổ có dung lượng $d$ (Mb). Bạn hãy lập trình giúp Hồng giải quyết bài toán.

5 8
1 2 3 4 5

5

5 10
4 5 6 7 5

4

Đây là một phiên bản khó hơn của bài toán trong sách giáo khoa. Statement được chép nguyên văn từ sách.

Hồng có $n$ file dữ liệu được đánh số từ $0$ đến $n - 1$ và có kích thước tương ứng là $s_0, s_1, ..., s_{n - 1}$ (Mb). Hồng muốn tìm cách lưu trữ nhiều file dữ liệu nhất bằng hai đĩa ổ cứng, mỗi ổ có dung lượng $d$ (Mb). Bạn hãy lập trình giúp Hồng giải quyết bài toán.

5 8
1 2 3 4 5

5

5 10
4 5 6 7 5

4

Đây là một câu chuyện có thật, tuy nhiên đã được biển đổi một chút.

Bạn cũng nên thử bài này

TLEoj được nhiều người biết đến là một trang chấm bài trực tuyến với vô vàng bài tập thú vị và những con người thân thiện. Ngoài ra, TLEoj cũng thường xuyên tổ chức các cuộc thi lập trình để những người nơi đây học hỏi thêm nhiều điều mới lạ hơn. Sau những cuộc thi ấy là một nhóm setter chăm chỉ, thường nghĩ ra những bài tập hay ho, thú vị cho mọi người nơi đây làm và flo của chúng ta là một trong số đó.

Sau một giấc ngủ thoải mái, flo tỉnh dậy và kiểm tra tin nhắn của mình. Bỗng cậu thấy có một tin nhắn được gửi đến với nội dung như sau:

Vì là một trong những admin chính của TLEoj, flo đã rất bực mình và cay cú với người gửi tin nhắn trên. Thế là cậu bắt tay vào làm ngay một bài siêu khó để gửi lại cho người ấy như là một thử thách. Bài ấy có nội dung được tiết lộ như sau.

Tuy là người ra bài nhưng flo lại không thể nào giải được bởi lẽ nó quá khó. Là một con người thân thiện ở TLEoj, bạn hãy giúp flo nhé.

3 1 2
-3 4
5 -1
3 6

0.42399824

Trong lúc các bạn đang ngồi đánh vật với đề thi củ chuối (có $1$ bài troll) (và $3$ bài bait) này thay vì ra ngoài đi chơi Trung Thu như bao người khác (vì bạn vẫn đang bitchless) (hoặc đã trở thành social outcast) (hoặc gia đình bạn đã bỏ mặc bạn ở nhà và chở thằng/con em của bạn đi chơi), ở đâu đó trong thành phố Hà Nội, thằng ra đề đang đi ăn cùng với mấy đứa bạn của nó (chắc chắn không phải vì somehow sinh nhật thứ 16 của nó lại đúng vào đêm Trung Thu). Để giúp các bạn cảm thấy cuộc sống đỡ bất công hơn, thằng ra đề xin được phép kể một câu chuyện như sau.

Để chuẩn bị cho sinh nhật lần thứ 16 của mình (đồng thời cũng trùng vào đêm Trung Thu của năm $2123$), Lib đã nghĩ ra một ý tưởng vô cùng táo bạo (và khá hợp lí): Mua bánh trung thu thay cho bánh sinh nhật. Lib đã xác định được vị trí của N cửa hàng bán bánh trung thu trên thành phố. Vì muốn lần sinh nhật này trở thành troconbo lớn nhất từ trước đến nay, Lib muốn mua được nhiều bánh trung thu nhất có thể. Bình thường, mỗi lần ra đường, Lib chỉ toàn mặc đồng phục trường (không phải là do muốn ngạo nghễ trường chuyên vi en mà là do gu thời trang quá tệ và không biết mặc gì khác). Tuy nhiên, do đã gần đến Trung Thu và nhu cầu tiêu thụ bánh của mọi người đều rất cao, các cửa hàng chỉ bán bánh cho mỗi khách hàng đúng $1$ lần. Tất cả các chủ cửa hàng đều có khả năng nhớ mặt rất tốt - Lib đã thử cách chờ $10^9+7s$ rồi sau đó đến mua lại, và kết quả là bị chửi cho sấp mặt. Chợt nhớ đến việc ở nhà ông bà ngoại mới có $1$ bộ outfit cosplay gái alime mới mua (chắc chắn không phải do bị $1$ thằng nhóc lớp $9$ lên $10$ nào đó dụ mua để [REDACTED][REDACTED][REDACTED][REDACTED]), Lib đã vứt hết liêm sỉ đi để dùng bộ đồ cosplay làm disguise để đi mua bánh ở một cửa hàng nào đó (không nằm trong $N$ cửa hàng đã biết đến). Mọi chuyện đã rất suôn sẻ cho đến khi bác bán hàng - vi một lí do thần kì nào đó, check lại địa chỉ nhà và nhận ra Lib đã đến mua bánh trước đó $2 \times 10^9+7s$ rồi. Và thế là lại bị chửi sấp mặt. Bằng một cách thần kì nào đó, mọi chủ cửa hàng ở năm $2123$ đều là bậc thầy doxxing và biết được chính xác địa điểm mà Lib bắt đầu đạp xe ra khỏi nhà.

Bản đồ giao thông của thành phố Hà Nội (mà Lib cần quan tâm đến trong hành trình mua bánh này) gồm $N$ điểm - $N$ cửa hàng bánh trung thu và $N-1$ con đường hai chiều được đánh số từ $1$ tới $N-1$. Con đường thứ $i$ trong số $N-1$ con đường này nối giữa $2$ điểm $U_i$ và $V_i$ với nhau, và Lib mất $T_i$ phút để đi hết con đường đó bằng xe đạp. Nhà của Lib nằm ở điểm $A$, nhà ông bà nằm ở điểm $B$ (Đảm bảo $A$ $<$ $B$, ở $2$ điểm $A$ và $B$ này cũng có cửa hàng bán bánh (nhưng mà là ở đối diện nhà)).

Ở thời điểm năm $2123$, công nghệ dịch chuyển tức thời đã trở nên hoàn thiện - người người nhà nhà (bọn nhà giàu) ai ai cũng có các bộ dịch chuyển. Ở mỗi cửa hàng bán bánh đều có $1$ bộ dịch chuyển loại "xịn" - có thể dịch chuyển người dùng đến bất kì đâu trên hệ thống thành phố. Liên minh chủ của các tiệm bánh, tuy vô cùng ki bo, luôn sẵn sàng hỗ trợ k hháchàng di chuyển nhanh hơn (dĩ nhiên là sau khi họ đã mua bánh, chả ai ki bo đến mức tổng sỉ vả $1$ thằng bé vì nó muốn mua thêm bánh mà lại cho người ta teleport free cả). Dĩ nhiên, sự hỗ trợ này cũng chỉ là có giới hạn: Nếu chủ cửa hàng biết rằng khách hàng bắt đầu hành trình từ điểm $I$ và khoảng cách giữa điểm $I$ đó và tiệm bánh là $K$, chủ cửa hàng sẵn sàng giúp khách hàng dịch chuyển và tiết kiệm $1$ khoảng cách tối đa là $K$.
Cụ thể hơn, trong hình dưới đây, nếu khách hàng bắt đầu tại điểm $X$ và tiệm bánh ở điểm $Y$, giả sử rằng độ dài cạnh của tất cả các ô vuông là như nhau, chủ tiệm sẽ vui vẻ giúp khách dịch chuyển nếu điểm đến mà khách hàng chọn thuộc vùng màu đỏ (còn nếu vào vùng màu đen là lại ăn chửi tiếp). Giả sử việc mua bánh dịch chuyển và thay quần áo là không mất thời gian, chỉ tính thời gian Lib phải di chuyển từ nhà đến các tiệm bánh bằng xe đạp.

(Giải thích ví dụ: Khoảng cách giữa $X$ và $Y$ trong hình đính kèm là $7$. Vùng màu đỏ là những vùng $1$ khách hàng xuất phát từ $X$, mua bánh ở $Y$ được phép dịch chuyển đến. Vùng màu xanh là vùng sẽ bị từ chối sử dụng thiết bị dịch chuyển + ăn chửi).

Nhà của Lib thì không giàu đến thế và chỉ có $1$ cặp bộ dịch chuyển loại "dởm": Khi cần, chỉ có thể dịch chuyển từ đầu này sang đầu kia của bộ dịch chuyển này. Gọi $2$ đầu này lần lượt là $I$ và $II$. Tuy nhiên, do khả năng doxxing của các chủ tiệm bánh đã đạt đến một cảnh giới vô cùng vi diệu, các bác luôn biết được địa điểm bắt đầu của một hành trình mua bánh - kể cả khi sử dụng cổng dịch chuyển - vì vậy, nếu muốn việc mua bánh lần $2$ từ cùng $1$ cửa hàng trót lọt, $2$ hành trình đi mua bánh phải được bắt đầu ở $2$ địa điểm khác nhau . Ngoài ra, do xe đạp của Lib có khả năng chống xóc cực tệ (đến mức, nếu nó có ý thức, nó sẽ ngay lập tức trở thành "bartender of the year" ở mọi nơi mà nó đến) nên sau khi mua được $1$ cái bánh, Lib không thể mua thêm cái bánh nào khác mà phải trở về hoặc nhà (ở $A$) hoặc nhà ông bà (ở $B$) để cất bánh trước khi có thể mua thêm bánh mới. Ngoài ra, sau khi mua bánh xong, Lib cũng cần phải cất lại quần áo cosplay gái alime ở nhà ông bà (để không bị dính gay seggs allegations) và đảm bảo rằng $2$ đầu $I$ và $II$ được đặt về đúng chỗ của nó (để không bị ăn chửi vì làm mất đồ của gia đình).

Tính từ thời điểm lên ý tưởng, sau $18$ ngày và $45$ lần suy đi tính lại, Lib đã nghĩ được $1$ hành trình để có thể mua được nhiều bánh nhất có thể. Kể từ thời điểm đó đến sinh nhật Lib chỉ còn đúng $K$ phút để có thể đi mua bánh. Dù đã tính được số bánh tối đa có thể mua (và đã mất hết liêm sỉ đến mức sẵn sàng tống việc cosplay gái alime vào đề bài) và lên được hành trình tối ưu để mua bánh, Lib muốn thách thức bạn tìm ra được số bánh tối ưu và $1$ trong số các hành trình tối ưu thỏa mãn đó (để không bị @ trong lúc đang ăn sinh nhật). Nếu có nhiều hành trình mua được số bánh tối đa trong thời gian cho phép, in ra $1$ hành trình thỏa mãn bất kì. Bạn không cần phải in cụ thể chỉ dẫn cho tất cả các hành động - Lib sẽ tự động tìm cách để đi mua bánh với thời gian tối ưu theo phương pháp mà bạn tìm được. Nếu bạn tìm được $1$ hành trình mua được số bánh tối đa thỏa mãn (và in được ra), bạn sẽ được $100\%$ số điểm cho testcase đó. Nếu bạn chỉ xác định được số bánh trung thu tối đa có thể mua, bạn sẽ được $50\%$ số điểm cho testcase đó.

Yêu cầu: Tính số lượng bánh trung thu tối đa mà Lib có thể mua được, đồng thời in ra một thứ tự đi thăm các tiệm bánh thỏa mãn.

7 1 3 15
1 2 2
2 3 4
1 4 3
3 5 5
5 6 3
3 7 2

7
2 7 5 3 2 4 1

7 1 5 10
1 2 2
2 3 4
1 4 3
3 5 5
5 6 3
3 7 2

5
2 6 4 5 1

8 1 5 12
1 2 1
2 3 2
2 7 1
3 4 1
4 5 2
4 6 1
5 8 4

8
4 2 3 6 5 3 1 7

"Vương quốc Byteland có $N$ thành phố được đánh số từ $0$ đến $N-1$. Giữa các thành phố có $M$ con đường hai chiều được đánh số từ $0$ đến $M-1$. Có $K$ cổng dịch chuyển......"

Đang mơ tưởng về một đề bài nữa để gieo rắc đau đớn và làm khổ các học sinh CP trên toàn thế giới, đức vua của vương quốc Byteland bỗng nhận được thông báo rằng: Các thành phố trong vương quốc Byteland, do đã quá lâu mà không có input gì từ nhà vua (do quý ngài đáng kính của chúng ta đã không làm việc gì ngoài mõm ra các task được $10^9+7$ năm rồi) nên đã sắp sửa đánh nhau ầm ầm đến nơi. Mọi chuyện có vẻ không ổn lắm.

Ở vương quốc Byteland hiện tại vẫn có $N$ thành phố - được đánh số từ $1$ đến $N$. Trước đây, giữa các thành phố đều có quan hệ tương đối tốt đẹp với nhau. Tuy nhiên, sau whatever năm phải chịu đựng sự "hữu dụng" của quý ngài problemsetter cho các bài từ IOI đến Codeforces, từ POI đến APIO, cả vương quốc đã bắt đầu tôn thờ $1$ vị thần số học. Vì $1$ lí do nào đó (chắc chắn không phải là do thằng ra đề muốn thế), giữa $2$ thành phố được đánh số $i$ và $j$, nếu giá trị $i*j$ là số chính phương, mức độ xung đột giữa $2$ thành phố này sẽ tự dưng vô cùng bùng nổ và tất cả người dân ở $2$ thành phố này đều sẽ cảm thấy như thể cái bọn đến từ thành phố còn lại đã tàn sát cả họ nhà mình vậy. Còn không thì bình thường, không có chuyện gì cả.

Bỗng dưng tỉnh ngộ sau whatever năm chỉ ngồi code mõm, nhà vua muốn biết rằng: Có bao nhiêu cặp thành phố $i, j$ $(1 \le i < j \le N)$ mà giữa $2$ thành phố này không có xung đột với nhau.

Tùy vào mức độ không-vô-trách-nhiệm của mình, nhà vua có thể sẵn sàng bỏ ra tận $Q$ ngày $(0 \le Q \le 31)$ để vi hành quanh vương quốc (và tận mắt chứng kiến hậu quả của những hành động của mình). Do ngân sách nhà nước gần như đã không còn, để di chuyển giữa 2 thành phố, nhà vua bắt buộc phải sử dụng các cây cầu vốn đã có sẵn, nối giữa mọi cặp $2$ thành phố $(i, j)$ $(1 \le i < j \le N)$. Dù đã xuống cấp trầm trọng, phần lớn những cây cầu vẫn còn có thể đi được. Tuy nhiên, mọi cây cầu kết nối 2 thành phố bị xung đột với nhau đều đã bị phá hủy.

Trong tình hình nguy cấp và tệ hại như vậy, nhà vua muốn xây dựng hành trình cho chuyến vi hành của mình trong mỗi ngày thỏa mãn các điều kiện sau:

• Trong $1$ chuyến vi hành, không có thành phố nào được đi qua nhiều hơn $1$ lần.
• Chỉ sử dụng các cây cầu vẫn còn có thể đi được - nghĩa là, nếu ở bước thứ $A$ đang ở thành phố $B$ thì ở bước thứ $A+1$ không được phép ở $1$ trong các thành phố đang có xung đột với thành phố $B$.
• Nhà vua sẽ ưu tiên đi thăm các thành phố có xung đột với thành phố hiện tại sớm nhất có thể: Nếu bước thứ $A$ của đường đi đi qua thành phố $B$, bước thứ $A+2$ phải đi qua $1$ trong số các thành phố có xung đột với thành phố $B$ mà chưa đi qua (nếu nó có tồn tại). Nếu đến bước thứ $A$ mà không còn thành phố nào xung đột với thành phố đang đi qua nữa, ở bước thứ A+2 đi đến đâu cũng được (dĩ nhiên, phải thỏa mãn tất cả các điều kiện đã nêu ra ở trên.
• Tuy có mong muốn sẽ có thể hòa giải xung đột giữa các cặp thành phố nếu có thể, nhà vua không muốn cố quá để rồi thành quá cố. Cụ thể hơn, trong chuyến vi hành ở ngày thứ $Q$ (mà ta đang xét đến), không tồn tại $1$ nhóm $K+1$ thành phố đôi một không có xung đột với nhau.
• Ở mỗi ngày, sẽ có $C$ thành phố quan trọng - sắp xảy ra bạo loạn. Đường đi bắt buộc phải đi qua tất cả $C$ thành phố này.
• Số thành phố mà đường đi đi qua là lớn nhất có thể.

Yêu cầu: Với mỗi câu hỏi của nhà vua, in ra câu trả lời tương ứng.

5
3 
1 0
2 2
3 5
2 1
3

9
1
2
3

12
2
3 0
3 1
5

61
7
6

Tọa lạc tại vị trí vô cùng đắc địa, phòng 702 D4 trường THPT Chuyên Sư Phạm tự hào là hàng net lâu đời nhất nhì và chắc chắn là cao nhất đường Xuân Thủy - Nơi mà máy nào máy nấy đều có case máy đèn 7 màu, người người nhà nhà đều mang bàn phím custom đi, máy nào cũng có Steam, không thì Genshin hoặc Y8 browser. Ngày hôm nay, các thành viên K56 Tin gồm SpiceDangSpice, Lib, NotNaCl, Kubogi, Normankr07 đang tranh thủ ngồi chơi Minecraft trong lúc chờ thầy Hoàng setup server CSPOI (họ không biết rằng thầy đang setup 2 bài matching và 4 bài mincost flow).

Do đã quá chán nản với việc làm theo Geneva Suggestions và làm đủ các thứ trò con bò, họ đã quyết định: Thay vì tiếp tục mở rộng danh sách "tội ác chống lại loài người" của mình, hôm nay, họ sẽ làm thứ gì đó "Zen" hơn: Xây nhà. Tuy nhiên, do bản tính siêu sv đã ắn sâu vào trong máu, các thành viên lớp 11D6 không thể nào chịu được việc phải đặt các block xuống để xây nhà. Trong hoàn cảnh đó, Lib đã nghĩ ra 1 ý tưởng siêu thiên tài: Phá rừng để làm nhà (vẫn không phải Crimes Against Humanity nhé).

Sau khoảng $10$ phút đi tìm $1$ mảnh rừng chưa bị cháy thành tro, các thành viên lớp 11D6 đã tìm được $1$ mảnh đất có kích thước $M \times N$ block. Các hàng được đánh số từ $1$ đến $M$, các cột được đánh số từ $1$ đến $N$. Trong mảnh rừng này, ở ô $[i][j]$ sẽ có giá trị là $0$ nếu ở đó không có cây nào, ngược lại ô $[i][j]$ sẽ có giá trị là $1$. $1$ ngôi nhà cần phải có dạng $1$ hình vuông kích thước $A \times A$, với tất cả các ô ở trên cạnh đều phải có sẵn cây (để làm tường), và tất cả các ô không nằm trên cạnh của ngôi nhà đều phải không có cây nào. Dĩ nhiên, để tìm được $1$ khu đất đủ to mà không chứa cây nào trong tự nhiên là rất khó, nên vẫn có thể chặt $1$ số cây đi được. Tuy nhiên, do chỉ còn $3$ ngày nữa là thi tuyển, và không ai muốn bị đánh giá là quá nghiện ngập, mải chơi không lo học bởi một Mrs REDACTED nào đó, tập thể sv lớp 11D6 chỉ được phép chặt tối đa không quá $K$ cây.

Yêu cầu: Tính diện tích của ngôi nhà lớn nhất mà các thành viên lớp 11D6 có thể "xây" được thỏa mãn các yêu cầu của đề bài.

9 12 0
0 1 0 1 0 1 1 0 1 1 0 0 
1 1 1 1 1 0 0 0 0 1 1 0  
1 0 1 1 1 1 1 1 1 1 1 1 
1 1 0 1 0 1 0 0 0 1 0 1 
0 1 1 1 1 1 0 0 0 1 0 1 
1 0 1 0 0 1 0 0 0 1 1 0 
0 1 1 0 0 1 1 1 1 1 0 1 
1 1 0 1 1 1 0 0 1 1 1 0 
1 1 1 1 0 1 0 0 0 1 1 0 

25

13 12 1
0 0 0 0 0 0 1 0 0 1 0 0 
0 0 0 1 0 1 1 1 0 0 1 0 
0 1 0 1 1 1 0 1 0 0 1 1 
1 0 1 1 1 1 1 0 1 0 1 1 
1 1 1 0 0 0 1 1 1 0 1 0 
0 1 1 0 0 0 1 0 1 0 0 1 
0 0 1 0 0 1 1 0 0 0 1 0 
1 1 1 1 1 1 1 1 0 1 0 0 
0 1 1 0 1 0 0 1 0 1 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 1 0 0 1 1 0 1 1 1 
0 0 0 0 1 1 0 0 0 0 0 0 
0 0 1 0 0 1 0 0 0 1 0 1 

25

13 12 11
0 1 0 0 0 1 1 1 1 1 1 1 
1 0 0 1 0 1 1 1 0 0 1 1 
0 0 1 0 1 1 0 0 0 1 0 1 
0 1 1 0 1 1 0 1 1 0 0 1 
0 1 1 1 1 1 0 0 0 1 1 1 
1 1 1 1 1 1 1 0 1 0 1 1 
1 0 0 1 1 1 1 1 1 1 1 1 
1 1 0 1 0 0 1 0 1 0 0 1 
1 0 0 1 0 0 1 1 0 1 0 1 
1 0 1 0 1 1 1 0 1 1 1 1 
0 1 1 0 0 0 1 1 1 1 1 1 
1 0 1 0 1 1 0 0 1 1 1 1 
0 0 1 1 1 0 1 1 1 0 1 1 

49

"Ngành Tin Học bắt đầu du nhập về Việt Nam từ năm 1989. Năm đấy, bọn Hội đồng Khoa học Quốc Tế tổ chức IOI lần đầu tiên ở bên Bulgary. Thời đấy, bên mình còn chưa biết cái môn này là cái gì, học và dạy như thế nào, gồm những cái gì nên quyết định tham gia để thấy thế giới người ta học như thế nào thì bú nguyên cái đấy về Việt Nam dạy. Như các bạn bây giờ thì để được đi thi cái đấy đấm nhau hết hơi còn chưa xong, đấu qua mấy vòng rồi đủ các thể loại mới đi thi được, vì bây giờ thằng nào cũng muốn đi, nhưng năm ấy, cố gắng vật vã lắm mới cử được có 3 thằng đi - còn chưa đủ 4 đứa để thành 1 đội. Năm đấy mình đi thi trên tinh thần lớ ngớ chả biết cái gì cả, chỉ đi thi thử cho biết, thế mà chẳng hiểu kiểu gì lại được cái huy chương đồng để mang về. Thậm chí, cả mấy năm sau cũng thế - các năm sau còn nhiều huy chương hơn, thậm chí có cả huy chương vàng. Thực ra hồi đấy kết quả được như thế vì lúc đấy đi thi về cơ bản là "chửi nhau" và "code giấy": lãnh đạo đoàn bên mình đi tranh luận với BTC các thứ để chấm điểm. Đến năm 1994 thì IOI bắt đầu chấm bằng test, và thế là từ đấy kết quả của đoàn VN bắt đầu lẹt đẹt đi hẳn.
Quá trình chấm bài bằng test thì cũng phải mất mấy năm mới hoàn thiện được. Mấy năm đầu, mỗi test chỉ đứng riêng, nên có hiện tượng mấy thằng cắn bẩn, chả code gì còn được điểm cao hơn cả mấy thằng nghĩ ra thuật tử tế. Các bạn cứ thử tưởng tượng thế này: Có 1 bài gồm 10 test, mỗi test được 10 điểm, nhưng chỉ yêu cầu in ra 1 trong 4 số A,B,C,D làm đáp án. Thế là, có mấy thằng, chả cần nghĩ thuật gì, cứ in ra random(1,4) và thế là chẳng làm gì cũng được hơn 20 điểm. Tính toán ra thì tỉ lệ để đúng hết các test bài đấy mà chỉ in random ra tận 1/hơn 1 triệu gì gì đấy, nghĩa là bọn đấy nếu cứ cắm đầu cắm cổ nộp bừa thì trong contest, kiểu gì cũng có thằng AC mà không cần phải làm gì cả, mà thế thì rõ ràng là không tốt. Thế là, rút kinh nghiệm từ cái đấy, mấy năm tiếp theo người ta gộp tầm 10 test lại thành các "batch", và phải đúng hết các test trong 1 batch thì mới được điểm của batch đấy. Các bạn cứ tưởng tượng là, có 50 cái test, nếu để nó thành 50 test riêng, mấy thằng in random kia trung bình kiểu gì cũng đúng được đâu đấy tầm 15 test. Nhưng nếu gộp 10 cái test vào trong 1 batch, và yêu cầu phải đúng hết tất cả các test trong batch mới được điểm của batch đấy, thì mấy thằng cắn bẩn đấy chẳng có cơ hội làm gì cả."
(thực ra còn nhiều hơn nữa, nhưng do mình không ghi lại và chưa nhớ được hết nên chỉ có đến đây thôi)

• Lê Minh Hoàng, trong bài "diễn văn" chào mừng học sinh khóa K56 Tin của trường Chuyên ĐHSP Hà Nội (Thứ 2, ngày 8/8/2022)

Sau hơn 30 năm du nhập về Việt Nam, môn Tin Học đã trở thành một môn học chính thống với mức độ cạnh tranh khá cao (cho bọn trường chuyên), với số lượng học sinh được giải trong các kì thi khu vực và quốc tế càng ngày càng tăng lên. Nhận thấy rằng chất lượng của học sinh trong nước (trong môn Tin Học lập trình) càng ngày càng cao, Bộ Giáo Dục, cùng với các trường chuyên trên khắp cả nước đã và đang có rất nhiều nỗ lực để đẩy mạnh công cuộc đào tạo các IOI medalist có thể cạnh tranh với các anh Tàu, Tàu (ở Mỹ), Tàu (Ở Canada), Tàu (ở Úc), Nhật, Hàn,.... trong tương lai. Với chủ trương "các em khóa sau phải giỏi x10 lần các anh chị tiền bối khóa trước lúc bằng tuổi", Sở Giáo Dục của các thành phố, cùng với hội đồng các trường chuyên trên khắp cả nước đã nghĩ ra những cách vô cùng hay ho để thách thức các em học sinh cấp 2 trên khắp cả nước. Điển hình như việc đề Tuyển Sinh vào 10 của Lê Quý Đôn (Đà Nẵng) tòi hẳn ra 1 bài FFT giải 10^5 đa thức có bậc 10^5 (literally kiến thức nâng cao trên Codeforces, 4* trên VNOI Wiki), hay đề thi HSGTP dành cho học sinh cấp 2 của Hà Nội có quả bài 5 bú nguyên xi 1 bài rating 3000 Codeforces (https://codeforces.com/problemset/problem/526/F) (3k codeforces = ngang ngửa đề thi IOI :wheeze: và từ đó sinh ra câu nói huyền thoại của ahihi1234: "Bài 3k codeforces đấy chỉ là sub 3 thôi con ạ") :wheeze: , hay việc câu C hình đề tuyển sinh vào 10 của 1 trường H nào đó (trong 1 đề thi 150p) khiến 1 nhóm 5 thầy nào đó mất 300 phút (với sự hỗ trợ của GeoGeBruh) để giải và khiến ngay cả đội IMO cũng phải bó tay, hay....... Việc đưa ra những task rất wtf và literally không ai giải nổi để thằng ra đề flex trình độ với bọn nhóc cấp 2 vắt mũi chưa sạch, mới chân ướt chân ráo vào CP xem ra khá được ưa chuộng

Ngoài việc liên tục pressing các em trong quá trình tuyển sinh, ngay cả sau khi đã vào trường rồi, các em vẫn còn lâu mới được yên. Bây giờ meta là học sinh lớp 8 phải hở mồm ra là Larange Interpolatation, FFT, cài mincost flow, matching, Presistent Segment Tree như con, biết extended Li-chao tree with Lazy Propagation, Gormon-Hu tree, Larange Relaxation, Link-Cut Tree, Segment Tree Beats, 3D Convex Hull, Splay Tree,....., AC Alien trong 1 nốt nhạc ầm ầm, còn nếu không được thì sẽ ngay lập tức trở thành nỗi thất vọng trong lòng thầy H nào đó (allegedly) và nếu học sinh học ké dự tuyển mà không được đi thi IOI từ lớp 10 thì cũng sẽ trở thành nỗi nhục của thầy H nào đó và bị chê là "không có gì nổi trội" (allegedly). Nghe đồn còn có trường nào đấy suốt ngày lôi paper của bọn tuyển bên China về dịch để dạy cho HS lớp 10, dù cuối cùng cũng chả biết khi nào mới dùng.

Năm nay, với tư cách là người ra đề cho kì thi Học sinh giỏi Quốc gia môn Tin Học cấp Tiểu học, bạn có nhiệm vụ phải ra 1 đề thi nhuận tràng nhất có thể cho tất cả các bên liên quan. Hiện tại, ban tổ chức đã chuẩn bị được $N$ bài (với nguồn được bú trực tiếp, thay mỗi cái tên và taskname từ COCI, POI, IOI, APIO, IZhO, USACO Platinium , Codeforces (phải có độ khó trên 3k trở lên), CodeChef, VNOI, AtCoder, các thứ các kiểu), với độ khó lần lượt là $A[1]$, $A[2]$, ......, $A[N]$. Nhiệm vụ của bạn chỉ là sắp xếp lại các bài này để tạo thành một đề thi hoàn chỉnh.

Sau khi nhận được sự hưởng ứng "nồng nhiệt" từ các phụ huynh trên khắp cả nước, ban tổ chức đã quyết định tặng cho mỗi thí sinh 1 cỗ máy huyền bí để có thể hỗ trợ giải đề. Nguyên lí hoạt động của máy như sau:

• Khi nhận đề thi, máy sẽ ngay lập tức giải bài đầu tiên trong đề thi. Giá trị máy nhận làm input là độ khó của bài đó.
• Với mọi bài thứ i thỏa mãn $1<i\le N$, độ khó mà máy sẽ gặp phải khi giải bài thứ $i$ sẽ có giá trị là (giá trị đang ở trong máy) % (độ khó của bài thứ i). Input giá trị này vào trong máy để giải bài thứ $i+1$.
• Độ khó của đề thi là giá trị ở trong máy sau khi đã giải hết tất cả N bài.

Như đã nói ở trên, vì muốn đào tạo ra, không phải $1$, không phải $2$, mà là $10^9 + 7$ Tourist da vàng $9$ tuổi, ban tổ chức muốn bạn đưa ra được $1$ đề thi giúp mọi thí sinh được nhuận tràng và rửa ruột nhất có thể, BTC momg muốn đề thi có độ khó càng cao càng tốt. Do thời gian để chuẩn bị đề vô cùng có hạn, bạn chỉ cần xác định độ khó tối đa có thể của 1 đề thi.

Yêu cầu: Hãy xác định độ khó tối đa của $1$ đề thi gồm $N$ bài đã cho trước.

5
8 5 3 7 3

2

Ở thành phố XYZ, ai ai cũng đều biết tới nathan4690 với khả năng "chơi đá" thần sầu của anh khiến tất cả đều ngưỡng mộ. Tuy nhiên, riêng chỉ có bạn là không tin tưởng vào tài năng đó của nathan4690, vì vậy cậu ấy quyết định sẽ thách đấu bạn bằng một trò chơi nho nhỏ.

Trò chơi được thực hiện trên một sân đấu được chia thành $10^6$ vị trí được đánh số từ $1$ đến $10^6$. nathan4690 có một số viên đá, cậu ấy xếp chúng vào $n$ vị trí từ $1$ đến $n$, vị trí thứ $i$ có $a_i$ viên đá. Bạn được thực hiện không quá $10^6$ thao tác sau:

• Chọn $3$ vị trí $i,j,k$ phân biệt có giá trị không quá $10^6$ sao cho vị trí $i$ và $j$ chứa ít nhất một viên đá.
• Lấy hai viên đá từ hai vị trí thứ $i$, $j$, mỗi vị trí một viên đá, rồi chuyển chúng sang vị trí thứ $k$.

Mục tiêu của trò chơi là chuyển hết tất cả các viên đá về một vị trí duy nhất (vị trí kết thúc không quan trọng). nathan4690 đã dễ dàng dành chiến thắng trong trò chơi này, thậm chí không cần dùng đến các vị trí lớn hơn $n$s, còn bạn?

4
1 2 3 1

2
1 2 3
2 4 3

Định nghĩa một dãy hoán vị độ dài $n$ là một dãy số độ dài $n$ chứa tất cả các số nguyên dương bé hơn hoặc bằng $n$ theo một thứ tự bất kỳ. Ví dụ, $[2,3,1,5,4]$ là một dãy hoán vị, nhưng $[1,2,2]$ và $[1,3,4]$ không phải dãy hoán vị.

Bạn được cho một dãy hoán vị $a$ độ dài $n$. Với mỗi $i$ từ $1,2,\ldots,n-1$, theo thứ tự này, bạn thực hiện thao tác sau:

• Khởi tạo một dãy $b$ gồm $n-1$ phần tử theo định nghĩa sau:
  • Nếu $i$ lẻ: $b_j = max(a_j, a_{j+1})$ với mọi $j \in [1,n-1]$
  • Nếu $i$ chẵn: $b_j = min(a_j, a_{j+1})$ với mọi $j \in [1,n-1]$
• Đặt dãy $a$ thành dãy $b$

Dễ thấy, sau mỗi thao tác, độ dài dãy $a$ giảm đi đúng $1$ phần tử, và sau $n-1$ thao tác, dãy $a$ sẽ chỉ còn đúng một phần tử.

Yêu cầu: Hãy tìm phần tử cuối cùng còn lại trong dãy $a$ sau $n-1$ thao tác.

2
3
1 3 2
4
1 2 3 4

3
3