Cho $N$ số nguyên không âm $A[1], A[2],..., A[N]$. Tính tổng $A[1] + A[2] +\dots+ A[N]$.

3 41 60 29 

130

5 35 80 45 66 68 

294

7 38 43 44 65 49 3 77 

319

$T$ là một người vô cùng thượng đẳng, hiện đang làm chủ 1 nhà hàng ở đâu đó. Hắn ta cứ hở ra là lại nói những thứ rất là súc vật và mang tính phân biệt đối xử khá cao - đến mức vài người coi hắn là truyền nhân tương lai của anh họa sĩ người Áo nào đó. Cay cú và nghĩ rằng mình bị kì thị do suốt ngày ăn nói lung tung, hắn muốn hợp lí hóa đống tư tưởng siêu cực đoan của mình bằng cách thống kê những hành động của các thực khách trong nhà hàng của mình.

Ở đất nước của hắn (dĩ nhiên là Byteland, Bitland là cho bọn khố rách áo ôm, đương nhiên rồi) có $N$ thành phố, được đánh số từ $1$ đến $N$. $T$ quá racist nên không phục vụ cho bất kì thực khách nào không đến từ $1$ trong $N$ thành phố của đất nước Byteland cả. Với những khách hàng của mình, hắn chia nhà hàng của hắn thành $2$ khu vực:

• Khu vực phục vụ: Gồm $N$ phòng ăn tập trung được đánh số từ $1...N$. Phòng ăn thứ $i$ chỉ dành cho những người đến từ thành phố $i$, và có sức chứa là $C[i]$ khách. Khi $1$ khách hàng từ thành phố $i$ đến, nếu trong phòng ăn thứ $i$ đang có ít hơn $C[i]$ người, khách hàng này sẽ được đi thẳng vào phòng ăn
• Khu vực chờ: Gồm $N$ phòng chờ được đánh số từ $1...N$. Phòng chờ thứ $i$ chỉ dành cho những người đến từ thành phố $i$, và có sức chứa là $D[i]$ khách. Nếu $1$ khách hàng đến từ thành phố $i$ đến và phòng ăn tập trung thứ $i$ không còn chỗ, khách hàng đó sẽ vào phòng chờ thứ $i$. Nếu $1$ vị khách đang ở trong phòng ăn thứ $i$ bị đuổi ra, họ sẽ vào phòng chờ thứ $i$. Nếu $1$ vị khách bị đuổi khỏi khu vực chờ, họ sẽ không quay trở lại.
• Nếu $1$ khách hàng từ thành phố $i$ đến và cả phòng ăn thứ $i$ lẫn phòng chờ thứ $i$ đều không còn chỗ, họ sẽ đi về và không gây ảnh hưởng gì đến số liệu cả.

Trong 1 ngày sẽ có $Q$ hành động, mỗi hành động được kí hiệu như sau:

• 1 l r k: $1$ nhóm các đại biểu đến nhà hàng. Với mỗi thành phố có số thứ tự $i$ $(l \le i \le r)$, lần lượt có $k$ đại biểu đi đến nhà hàng.

• 2 l r k: Với mỗi phòng có số thứ tự $i$ $(l \le i \le r)$, lần lượt đuổi $k$ người đi. Nếu trong phòng ăn nào đó có ít hơn $k$ người, đuổi tất cả mọi người đi.

• 3 A k: Mời $k$ vị khách vào khu vực chờ sớm nhất (tính đến thời điểm hiện tại) vào phòng ăn tương ứng. Nếu trong khu vực chờ có ít hơn $k$ khách, cho tất cả vào. Nếu trong phòng ăn i không còn chỗ, khách hàng này sẽ tự bỏ về, rời khỏi khu vực chờ.

• 3 B k: Đuổi $k$ vị khách vào khu vực chờ sớm nhất (tính đến thời điểm hiện tại) khỏi nhà hàng.

• 4 A: Tìm số vị khách lớn nhất đến từ cùng 1 thành phố đã đến nhà hàng.

• 4 B: Tìm số vị khách lớn nhất đến từ cùng 1 thành phố đang trong khu vực phục vụ.

• 4 C: Tìm số vị khách lớn nhất đến từ cùng 1 thành phố đang trong khu vực chờ.

• 5 A: Tính tổng số người đang ở trong khu vực phục vụ ở thời điểm hiện tại

• 5 B: Tính tổng số người đang ở trong khu vực chờ ở thời điểm hiện tại.

Dữ liệu đầu vào đảm bảo:

• Số khách hàng từng vào nhà hàng không vượt quá $10^7$
• Số lần $1$ vị khách vào khu vực phục vụ không vượt quá $10^7$
• Trong mọi truy vấn loại 1,2,3; $k \le 10^9$

Yêu cầu: Với mỗi truy vấn loại $4$ hoặc loại $5$, in ra thông tin mà truy vấn yêu cầu.

7 10
100 100 100 100 100 100 100
5 5 5 5 5 5 5
1 1 4 11
1 2 6 12
1 3 7 18
1 1 10 40
1 5 9 12
4 B
4 A
4 C
5 A
5 B

82
82
0
510
0

5 5
2 3 5 3 2
2 2 2 2 2
1 1 5 3
2 1 5 1
3 B 3
3 A 4
4 B

3

Trên mặt phẳng tọa độ $Oxy$ trống, bạn được cho $q$ truy vấn, truy vấn thứ $i$ yêu cầu bạn phủ một hình vuông có độ dài cạnh $1$ lên mặt phẳng sao cho vị trí góc trái dưới của hình vuông nằm ở tọa độ $(u, v)$ (và hiển nhiên góc phải trên của hình vuông nằm ở tọa độ $(u + 1, v + 1)$), đồng thời yêu cầu bạn tính tổng chu vi của phần được phủ bởi các hình vuông.

4
1 1
2 2
2 1
3 1

4
8
8
10

Trong buổi học đầu tiên ở lớp, huyhau6a2 được cho một xâu $s$ gồm $n$ ký tự chỉ bao gồm các chữ cái tiếng anh viết thường. Cô đã dạy cho huyhau6a2 một số định nghĩa như sau:

• Một xâu con của xâu $s$ được tạo ra bằng cách bỏ bớt một số ký tự liên tiếp ở đầu và ở cuối của xâu $s$, với $s[l\rightarrow r]$ là xâu con $s_l s_{l+1}\dots s_r$.
• Gọi $p_i$ là hậu tố bắt đầu từ vị trí $i$ của xâu $s$, định nghĩa $p_i=s[i\rightarrow n]$.
• Gọi $lcp(s_1,s_2,\dots,s_x)$ là giá trị $k$ lớn nhất sao cho $s_1[1\rightarrow k]=s_2[1\rightarrow k]=\dots=s_x[1\rightarrow k]$ và $s_1,s_2,\dots,s_x$ là các xâu bất kỳ

Sau buổi học, cô giáo đã cho huyhau6a2 $q$ truy vấn, mỗi truy vấn gồm 2 số $l,r$. Nhiệm vụ của huyhau6a2 là với mỗi truy vấn, hãy tính giá trị của $lcp(p_l,p_{l+1},\dots,p_r)$.

huyhau6a2 đã giải xong rồi, và giờ đây chính là thử thách dành cho các bạn!

4 3
abbb
1 2
2 3
2 4

0
2
1

Một trò chơi mới được khai trương tại khu vui chơi, nó có tên là: “Thoát khỏi kim tự tháp”.
Mặt trước của khu vực chơi có thể được miêu tả bằng một ma trận $A$ có $n$ hàng (các hàng được đánh số từ $1→n$ từ trên xuống dưới) và $m$ cột (các cột được đánh số từ $1→m$ từ trái sang phải). Trong số các phòng có thể di chuyển qua lại, thời gian di chuyển có thể được xem là $1s$. Bạn sẽ xuất phát ở tầng n, và cố gắng lên đến tầng cao nhất (trong số những tầng có thể lên) trong một khoảng thời gian không quá $t$ giây. Nếu thành công sẽ có thưởng. Có 2 ràng buộc cho trò chơi này là:

• Ràng buộc 1: Bạn bắt buộc phải xuất phát từ hai phòng ở tận cùng bên trái hoặc tận cùng bên phải (trong số những phòng có thể vào được) ở tầng $n$.
• Ràng buộc 2: Bạn bắt buộc không được phép vào một phòng bất kì nếu hoặc nó không thể vào hoặc bạn đã vào phòng đó trước đó.
• Ràng buộc 3: Nếu bạn ở tầng cao nhất và quyết định lên thêm thì đồng nghĩa rằng bạn chọn kết thúc trò chơi, và thời gian bạn lên sẽ không tính và trò chơi sẽ kết thúc.

Explanation

Mô tả	Minh họa
Đây là một ví dụ cho kim tự tháp có thể được cho (các ô vàng là các phòng có thể đi qua, và các ô cam là các phòng không thể đi qua).
Đây là một trường hợp hợp lệ vì thỏa mãn cả 2 ràng buộc đưa ra.
Đây là một trường hợp không hợp lệ vì không thỏa mãn ràng buộc số 1 (không xuất phát tại hai phòng ở tận cùng bên trái hoặc tận cùng bên phải ở tầng n).
Đây là một trường hợp không hợp lệ cũng vì không thỏa mãn ràng buộc số 1 (không xuất phát tại tầng n).
Đây là một trường hợp không hợp lệ vì không thỏa mãn ràng buộc số 2 (đi qua một ô 2 lần).

Để cho trò chơi mang tính thử thách hơn thì ban tổ chức quyết định sẽ giao cho một người chơi bất kì một giá trị t bất kì, và họ sẽ sử dụng một phương pháp sinh số ngẫu nhiên nào đó. Tuy nhiên, họ muốn bất kì giá trị nào cho ra đều sẽ có một cách chơi giúp người chơi giành giải thưởng (không khiến trò chơi trở nên impossible), tuy nhiên vẫn đủ để thử thách người chơi (họ không thể tùy tiện di chuyển mà vẫn thắng). Vì vậy, họ cần tìm ra hai giá trị $L$ và $R$ $(1≤L≤R)$ lần lượt là thời gian nhanh nhất và lâu nhất có thể để một người chơi hoàn thành trò chơi.
Họ quá bận trong việc điều hành các trò chơi khác trong khu vui chơi. Vì vậy, bạn hãy giúp họ tìm ra giá trị $L$ và $R$ thỏa mãn.

Sample

Input

2

4 11
6 7
5 8
4 10
2 11

3 3
2 2
2 3
2 3

Output

8 16
2 2

Explanation

Giải thích test 1: Đường đi nhanh nhất và lâu nhất có thể được thực hiện như bên dưới.

Đường đi nhanh nhất (8)	Đường đi lâu nhất (16)

Tachi có một bài toán nho nhỏ và cần bạn giúp đỡ.

Anh ta có số nguyên $N$, $Q$ và mảng $A = (A_1,..., A_N)$.

Tachi cần xử lí $Q$ truy vấn, mỗi truy vấn trong đó thuộc một trong hai loại sau đây:

• 1 x v: cập nhật $A_x$ thành $v$.
• 2 x: ta có $B_i$ = $\sum_{j = 1}^{i} A_j$, $C_i$ = $\sum_{j = 1}^{i} B_j$ và $D_i$ = $\sum_{j = 1}^{i} C_j$. In ra phần tử $D_x$ chia dư cho $998244353$.

3 3
1 2 3
2 3
1 2 0
2 3

15
9

2 1
998244353 998244353
2 1

0

HoBaoPhuc2009 tạo một số $s$ độ dài vô hạn bằng cách ghép các số nguyên tố có giá trị tăng dần lại với nhau, bắt đầu từ số $2$. Các chữ số đầu của $s$ bao gồm: $2357111317192329\dots$.

Bạn được cho $t$ testcase, mỗi testcase gồm một số $k$. Nhiệm vụ của bạn là tính tích $k$ chữ số đầu tiên của $s$. Vì kết quả có thể rất lớn nên hãy xuất kết quả sau khi $mod\ 10^9+7$.

6
1
2
3
4
5
8

2
6
30
210
210
630

Bạn được cho một dãy số $a$ dương gồm $n$ phần tử và một số nguyên dương $p$. Nhiệm vụ của bạn là kiểm tra xem có cặp chỉ số $1\le i<j\le n$ thỏa mãn $gcd(p^{a_i}-1,p^{a_j}-1)=p^{gcd(a_i,a_j)}-1$. Nếu có thì hãy xuất YES, ngược lại xuất NO.

2 3
1 2

YES

nah không có quote cho bài này đâu 🐧

Theo nguồn bệnh ung thư não lớn nhất thế giới, Sigma được hiểu là một người đàn ông sống cuộc sống dựa trên các quy tắc của riêng mình, phát triển vì đam mê của mình, không bị phân tâm bởi các quy tắc hoặc tiêu chuẩn xã hội. Cũng vì trend đấy, thầy của mondellbit009 là huyhau6a2 đã ra một bài rất khó hiểu, mà nếu hiểu thì cũng không biết làm 🐧, đó là:

Cho một dãy số gồm $n$ phần tử, hãy cho biết có bao nhiều phần tử là sigma. Được biết số sigma là số chỉ có 2 ước là $1$ và chính nó.

mondellbit009 đang rất mệt mỏi để làm bài đấy. Các bạn hãy giúp nhé :D

5
4 3 9 7 10

2

Chắc hẳn các bạn đã biết về bài toán cái túi, hay knapsack. Bài toán này là một phiên bản khác của bài toán cái túi.

Có $n$ món đồ, món đồ thứ $i$ có cân nặng $a_i$. An chọn một số món đồ sao cho tổng cân nặng của chúng đúng bằng $m$ và muốn biết rằng có bao nhiêu cách chọn đồ như vậy. Một món đồ có thể chọn $0$ lần, $1$ lần hoặc nhiều hơn $1$ lần, hai cách chọn được gọi là khác nhau nếu có một món đồ chọn nhiều hoặc ít hơn cách chọn kia. Hãy giúp bạn An đếm nhé

3 4
1 2 3

4

ChepCodeThanhLegend: Rất đơn giản, chúng tôi chép code, và thành Legend (nhưng mà là Legend về số lượng acc bị banned)

ChepCodeThanhLegend là một team được lập bởi những người yêu chép code, cop sol,... Những thành viên của team là mondellbit009, flo và Noobcoder. Là những người bạn của nhau, nên hầu như contest nào bọn họ cũng chép code với nhau. Kể cả những cuộc thi chính thức như HSG, THT, vv.. thì cả team đều cop code nhau để đạt được giải cao. Khi tin cả team cop code ở những kì thi chính thức lọt vào tai huyhau6a2, một người thầy dạy tin vjp pro đứng top 1 server. huyhau6a2 rất tức giận, lập tức bay vào Đà Nẵng để ra bài siêu khó cho những thanh niên chép code làm, thầy ấy ra điều kiện là: Nếu làm được thì thầy cho 500k, còn không thì số acc rate cao trên trời ở TLEOJ sẽ paymau. Bài tập thầy đưa là:

Cho một mảng $a$ có độ dài $n$. Bạn có thể cộng trừ 1 phần tử trong mảng $a$ không quá $m$ đơn vị. Hãy kiểm tra xem mảng đó sau thao tác cộng trừ có tổng bằng số $k$ không?

Đây là một bài rate $3500$, và chắc chắn không có trên mạng nên là khỏi cop :))). Bạn là một coder siêu cấp vjp pro nên hãy giúp cả team lấy 500k nhé ( chắc chắn team sẽ chia cho bạn mà :) )

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

YES
NO
YES

Một bộ ba $(i, j, k)$ được gọi là bộ ba thành tổng nếu nó thỏa mãn:

• $1 \le i, j, k \le n$.
• $i+j+k = m$.

Cho hai số nguyên dương $n, m$, hãy in ra số lượng bộ ba $(i, j, k)$ là bộ ba thành tổng.

3
5 1
2 6
3 7

0
1
6

Trong tiết toán thầy giáo cho lớp của giaminh2211 bài toán sau:

Ta gọi 1 hoán vị độ dài $n$ là 1 dãy số bao gồm $n$ phần thử chỉ chứa các giá trị từ $1$ đến $n$ sao cho mỗi số chỉ xuất hiện đúng 1 lần và có thể viết dưới bất kỳ thứ tự nào.

Ví dụ với $n=3$ thì các hoán vị hợp lệ là $[1,2,3]; [3,1,2]$, còn $[1,2,2],[4,3,2,1]$ thì không

Bạn được cho một số nguyên dương $n$. Nhiệm vụ của bạn là đếm số lượng hoán vị độ dài $n$ sao cho mỗi phần tử trong hoán vị có giá trị lớn hơn hoặc bé hơn tất cả các phần tử đứng trước nó trong hoán vị. Hay nói cách khác, gọi hoán vị là 1 dãy số $p_1,p_2,\dots,p_n$ thì với mọi giá trị $i$ thì thỏa mãn 1 trong 2 điều kiện sau:

• Với mọi $j<i$ thì $p_i>p_j$
• Với mọi $j<i$ thì $p_i<p_j$

Bạn nghĩ giaminh2211 sẽ nhờ bạn như những người ra đề khác sao? Bạn nhầm rồi, giaminh2211 đã giải được bài toán đó, liệu bạn có làm được như anh ấy không?

3
1
2
3

1
2
4

Cho một đa giác lồi $A$ gồm $n$ đỉnh. Đa giác $B$ là đa giác không tự cắt bất kì. Các đỉnh của cả hai đa giác được cho theo chiều kim đồng hồ. Mỗi đa giác không có ba điểm liên tiếp thẳng hàng.

Yêu cầu: Kiểm tra đa giác $B$ có nằm thực sự trong đa giác $A$ hay không? Tức là mọi điểm của $B$ nằm trong đa giác $A$, không có điểm nào của $B$ nằm trên các cạnh và đỉnh của đa giác $A$.

2
6
-2 1
0 3
3 3
4 1
3 -2
2 -2
4
0 1
2 2
3 1
1 0
5
1 2
4 2
3 -3
-2 -2
-2 1
4
0 1
1 2
4 1
2 -1

YES
NO

huyhau6a2 là 1 người rất thích chơi với cây. Vài hôm trước cậu đã mua về 1 cây thần kỳ, cây này bao gồm $n$ đỉnh. Ngoài ra, cây của huyhau6a2 còn có khả năng đặc biệt là có thể thay đổi gốc bất cứ lúc nào.

Chơi với cây quá chán, cậu quyết định rủ người anh em (khác cha khác mẹ) Kubogi vào chơi cây cùng mình và anh Kubogi đã nghĩ ra 1 trò chơi, trò chơi như sau:

Với mỗi lần, Kubogi sẽ đổi gốc của cây thành $x$, và huyhau6a2 phải tìm $LCA(u,v)$. Trong đó $LCA(u,v)$ là tổ tiên chung gần nhất của 2 đỉnh $u$ và $v$.

5 5
1 2
1 3
2 4
2 5
4 5 1
4 5 5
5 1 4
5 1 3
1 5 1

2
5
2
1
1

Do giám đốc của công ty A tặng cho nhân viên công ty B kẹo ngậm cho lâu hết nên công ty B quyết định sẽ trả thù lại cho công ty A bằng cách sẽ tặng những quả trứng gà để lâu ngày, hậu quả khi cầm nặng tay là nó sẽ nổ và tạo ra mùi không ổn tý nào.

Nhân viên của A xếp thành một hàng ngang đánh số từ $1$ đến $n$, công ty B muốn tất cả đều phải mở vậy nên tốt nhất là không thể tặng quà 2 người liên tiếp vì nếu một người mở thì người còn lại sẽ biết và không mở nữa. Và công ty B chỉ có $k$ quả trứng. Hãy đếm số cách tặng quà cho công ty A và in ra kết quả sau khi modulo $m$.

3 2 569

1

Cho hai số nguyên dương $n$ và $k$, đếm số lượng số nguyên dương $x$ phân biệt thỏa mãn đồng thời hai điều kiện sau:

• $1 \leq x \leq n$
• $x$ có đúng $k$ ước nguyên dương

3
3 1
10 2
49 3

1
4
4

Cho cây không trọng số $N$ đỉnh. Gọi $dist(u,v)$ là độ dài của đường đi đơn từ $u$ đến $v$ trên cây. Đếm số cách chọn một tập $S = \{u_1,u_2,...,u_K\}$ thoả mãn:

• $1 \leq u_1<u_2<...<u_K \leq N$
• Với mọi bộ chỉ số $(i,j,k)$ $(1 \leq i,j,k \leq K; i \neq j \neq k)$: $dist(u_i,u_j)+dist(u_j,u_k)>dist(u_i,u_k)$.

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

6

5 3
3 2
2 1
1 5
2 4

2

Cho một bảng kí tự gồm $n$ hàng và $m$ cột. Các hàng được đánh số từ $1→n$ từ trên xuống dưới, và các cột được đánh số từ $1→m$ từ trái sang phải. Bạn có thể thực hiện thao tác sau vô hạn lần (hoặc không thực hiện lần nào):

• Chọn hàng thứ $i$ trên bảng, và đẩy kí tự đầu tiên của hàng đó ra phía sau của hàng $(1≤i≤n)$ (ví dụ với xâu $\text{haudepzai}$ thì nếu để kí tự đầu tiên vào sau hàng thì sẽ là $\text{audepzaih}$)

Hãy tính xem, với vô số cách xoay bảng, có thể có bao nhiêu cách thực hiện thao tác sao cho sẽ có một xâu đối xứng xuất hiện tại cột thứ nhất? Biết rằng, hai cách thực hiện xoay bảng được tính là khác nhau khi bảng kí tự được tạo ra sau khi xoay bằng hai cách là khác nhau.

2
2 2
ac
ab
3 3
aba
bba
cba

1
9

Giá trị Sussy của một số nguyên dương $n$ (kí hiệu là $Sussy(n)$) là $n$ sau khi các chữ số của nó được sắp xếp lại và loại bỏ các chữ số $0$ vô nghĩa. Ví dụ:

• $Sussy(69420) = 2469$; $Sussy(1412) = 1124$.

Cho hai số nguyên dương $l, r$, hãy tính $\sum_{i=l}^{r} Sussy(i)$.

2
13 98
69 420

3297
57282