Nhân kỷ niệm ngày thành lập Đoàn, cô Tổng phụ trách tổ chức 1 trò chơi có thưởng cho các bạn lớp 9 như sau: Có $N$ ô vuông được vẽ thẳng hàng trên sân trường, các ô vuông được đánh số từ $1, 2, \dots, N$. Mỗi ô vuông $i$ ($1\le i\le N$) có giá trị năng lượng là $h_i$. Một bạn học sinh đang ở ô vuông thứ $i$, bạn ấy có thể nhảy tới ô vuông tiếp theo các cách:

• Nếu bạn ở ô vuông thứ $i$ thì bạn có thể nhảy đến ô vuông thứ tự $i+1,i+2,\dots,i+k$
• Chi phí năng lượng của bạn tiêu hao cho 1 lần nhảy là $|h_j-h_i|$ với $h_j$ là ô vuông đích mà bạn nhảy tới
  Bạn học sinh nào di chuyển từ ô số $1$ đến ô số $N$ với chi phí năng lượng thấp nhất sẽ được cô thưởng một phần quà

Yêu cầu: Hãy tìm chi phí thấp nhất để giúp các bạn học sinh nhảy từ ô vuông số $1$ đến ô vuông thứ $N$

5 3
10 25 35 40 20

20

Ở một trường P nọ, các học sinh rất thích tiết thể dục. Thầy giáo dạy thể dục thường cho khởi động từ giữa
hàng, tức là thầy sắp xếp học sinh theo chiều cao từ nhỏ đến lớn, lúc này bạn khởi động đầu tiên là bạn ở giữa
hàng nếu hàng lẻ và bạn ở giữa hàng có chiều cao thấp hơn đối với hàng chẵn. Thầy giáo không nhớ tên học sinh
nhưng thầy ấy có thể ước lượng chiều cao của các nhóm học sinh đi vào sân thể dục.
Có n nhóm học sinh đi vào, nhóm thứ i có a[i] bạn và có chiều cao ước lượng như nhau là v[i].

Yêu cầu: Xác định chiều cao của bạn sẽ khởi động đầu tiên lần lượt theo thứ tự đi vào của các nhóm học sinh.

INPUT gồm nhiều dòng: dòng 1 chứa số nguyên dương n là số nhóm học sinh, n dòng tiếp theo mỗi
dòng chứa hai số nguyên dương v[i] và a[i] đại diện cho nhóm học sinh thứ i.

OUTPUT gồm nhiều dòng: dòng thứ i là chiều cao của học sinh sẽ khởi động khi các nhóm từ 1
đến i đã đi vào sân thể dục.

• 1 ≤ n ≤ 2e5.
• 1 ≤ v[i], a[i] ≤ 1e9.

Cho một dãy $A$ ban đầu rỗng. Bạn cần thực hiện $q$ truy vấn, mỗi truy vấn thuộc một trong hai dạng sau:

• $+\ u$: thêm phần tử $u$ vào dãy $a$. $(u \ge 0)$
• $-\ u$: xóa phần tử $u$ khỏi dãy $a$. Dữ liệu vào đảm bảo dãy $a$ tồn tại phần tử $u$.

Sau mỗi truy vấn, bạn cần in ra trung vị của dãy $A$. Trung vị của một dãy $C$ có $n$ phần tử là phần tử lớn thứ $[\frac{n + 1}{2}]$ của dãy $C$. Nếu dãy $A$ rỗng in ra $-1$.

5

+ 1
+ 2
+ 3
+ 4
- 2

1
1
2
2
3

Cho một dãy $a$ gồm $n$ phần tử. Bạn phải thực hiện $q$ truy vấn, mỗi truy vấn yêu cầu bạn phải tìm số $r$ lớn nhất sao cho $r \le n$ và $(\Sigma^{i \le r}_{i = l}(a_i \times [u \le a_i \le v])) \le k$. Trong đó:

• $\Sigma^{i \le r}_{i = l} c_i$ là tổng các giá trị $c_i$ mọi trường hợp $i$ từ $l$ đến $r$.
• $[u \le a_i \le v]$ là hàm chân lý, trả về $1$ (true) khi và chỉ khi $u \le a_i \le v$ và trả về $0$ (false) trong các trường hợp còn lại.

Hay nói cách khác, bạn cần tìm giá trị $r$ lớn nhất sao cho đoạn mã giả sau trả về một giá trị $s \le k$ (lưu ý: $r$ có thể bằng $l - 1$):

gán s bằng 0

với mọi i từ l đến r:
    nếu u <= a_i <= v:
        tăng s lên a_i

trả về s

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

6
7
2

Cho một bảng hình chữ nhật có kích thước $m \times n$ ($m$ hàng $n$ cột) và hai dãy số nguyên $a_1, a_2, ..., a_m$ và $b_1, b_2, ..., b_n$. Ô ở hàng $i$ cột $j$ của bảng sẽ được điền số $a_i + b_j$. Bạn phải cắt ra $k$ hình chữ nhật, mỗi hình chữ nhật có kích thước là $h \times w$ ($h$ hàng $w$ cột, không được xoay), và các hình chữ nhật không được có ô chung (có thể chung đỉnh hoặc chung cạnh), sao cho tổng các số được ghi trên các ô của các hình chữ nhật là lớn nhất.

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

10

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

28

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

52

Cho các số nguyên dương $n, c, r$ và hai chữ số $u \le v$. Tìm số tự nhiên nhỏ nhất có $n$ chữ số (có thể có các chữ số $0$ ở đầu), chia $c$ dư $r$ và các chữ số của nó (tính cả các chữ số $0$) lớn hơn hoặc bằng $u$ và bé hơn hoặc bằng $v$.

2 5 9 12 0

96

2 0 9 12 0

00

Chắc hẳn các bạn còn nhớ bài TLE-oj Cup Round 6 - Truy vấn AOX của huyhau6a2. Đây là bản khó của bài tập này. Bản khó và bản dễ chỉ khác nhau về phần dữ liệu

Bạn được cho 1 xâu $a$ gồm $n$ ký tự chỉ gồm các ký tự như &, |, ^ (tương đương với phép toán AND, OR, XOR). Bạn phải thực hiện $q$ truy vấn:

• $1$ $k$ $x$: Cập nhật ký tự thứ $k$ trong xâu $a$ thành $x$ ($1\le k\le n$, $x$ thuộc 1 trong 3 loại ký tự như trên)
• $2$ $l$ $r$ $k$ $u$ $v$: Tính độ đẹp của xâu trong đoạn $[l,r]$ với các giá trị $k,u,v$ ($1\le l\le r\le n,1\le k\le 60,0\le u\le v<2^k$)

huyhau6a2 định nghĩa độ đẹp của một xâu ký tự $a$ độ dài $x$ với các giá trị $k,u,v$ như sau: Là số lượng dãy $b$ thỏa mãn ($0\le b_i<2^k$):

Chú ý: Thứ tự thực hiện tính toán theo các ký tự của xâu $a$ được thực hiện từ trái sang phải

VD: Xâu |^ với $k=1,u=1,v=1$ thì có các khả năng như sau:

• 0|0^0=0
• 0|0^1=1
• 0|1^0=1
• 0|1^1=0
• 1|0^0=1
• 1|0^1=0
• 1|1^0=1
• 1|1^1=0

Theo như kết quả ở trên, có 4 kết quả thỏa mãn. Vậy độ đẹp của xâu |^ với $k=1,u=1,v=1$ là $4$

Nhiệm vụ của bạn là phải tính toán các kết quả của truy vấn 2. Vì kết quả rất lớn nên hãy xuất kết quả $mod\ 10^9+7$

3 4
&|^
2 2 3 1 1 1
1 3 |
2 2 3 1 0 1
2 1 3 2 2 2

4
8
39

Ta định nghĩa $F_i$ là số fibonacci thứ $i$ với công thức như sau:

• Nếu $i\le 2$ thì $F_i=1$
• Ngược lại, $F_i=F_{i-1}+F_{i-2}$

Cho $q$ truy vấn, mỗi truy vấn gồm 4 số $a,b,c,M$. Nhiệm vụ của bạn là phải tính $F_{a^b}\text{ }mod\text{ }F_c$. Vì kết quả có thể rất lớn nên hãy xuất kết quả $mod\text{ }M$

4
3 3 3 10
3 3 5 10
3 3 5 2
4 16 15 300

0
3
1
77

"Vệ tinh của chúng ta vừa phát hiện ra một nền văn minh mới ở một hành tinh xa xôi. Chúng ta đã chụp được 1 tấm ảnh low-res có dạng 1 hình vuông $N\times N$ của hành tinh. Bức ảnh cho thấy nhiều dấu hiệu của sự sống văn minh, và các nhà khoa học đã xác định được $m$ điểm đáng quan tâm trên tấm ảnh này. Các điểm trong bức ảnh được đánh số từ $0$ đến $m-1$ ............"

Đấy đã là chuyện của 7 năm trước.

7 năm sau kể từ cái ngày mà bài Aliens đã phổ biến cái thuật toán DP China siêu ảo ma đấy cho các thí sinh trên toàn thế giới, mọi thứ đã thay đổi ít nhiều. Giờ đây, ai cũng biết đến Alien trick. Người người nhà nhà đều biết đến Alien trick. Thằng nhóc lớp 1 mới bập bẹ được 1-2 câu bằng tiếng Anh cũng biết đường nói "Using this formula, all $g_i$ can be computed in $O(n)$ time using Convex Hull Trick optimization, if all $l_i$ and $r_i$ are sorted beforehand. The solution from subtask 5 can also be modified to find the minimum number of photos required to achieve the optimum, call it $p(C)$". Mẹ bạn, bà của bạn và cả cụ của bạn cũng biết đến Alien trick. Mọi bài DP chia đoạn giờ đều trở nên vô nghĩa - cứ ốp Alien trick vào rồi chỉnh công thức truy hồi là AC trong 30s.

Là một coder đã mất hoàn toàn khả năng giao tiếp với gái (human female beings) sau 3 năm ròng chỉ ngồi ru rú trong nhà và 1 đấm AC tất cả các bài trong tất cả các kì thi OI của các nước, khu vực, và quốc tế (và cả liên hành tinh luôn, sau khi nó sẽ được tổ chức lần đầu tiên vào năm sau với sự góp mặt của tầm 1000 thí sinh đến từ sao Hỏa, dự tính là vậy), bạn mong muốn tìm được 1 sinh vật ngoài hành tinh nào đó làm partner để cảm thấy đỡ cô đơn. Tuy nhiên, việc tìm kiếm này xem ra không hề dễ.

Bề mặt của hành tinh được coi là 1 lưới vuông $N\times N$, trong đó các hàng được đánh số từ $1\rightarrow N$, các cột được đánh số từ $1\rightarrow N$. Trên bề mặt hành tinh có $M$ vị trí có thể có bạn đời tương lai của bạn, và bạn muốn khảo sát hết tất cả các điểm này bằng cách chụp các bức ảnh từ 1 vệ tinh mà bạn thuê được. Với mọi $1\le i\le M$, điểm thứ $i$ nằm ở hàng $X[i]$, cột $Y[i]$.

Sau từng ấy năm, ngành công nghệ vũ trụ đã phát triển hơn nhiều. Thay vì chỉ có 1 vệ tinh có quỹ đạo di chuyển trên đường chéo $Y=X$, giờ đã có $P$ vệ tinh, vệ tinh thứ $a$ $(1\le a\le P)$ chỉ có thể di chuyển trên đường chéo có chỉ số là $B[a]$. Đường chéo $b$ gồm tất cả các ô $i$ trên bề mặt hành tinh mà có $X[i]+Y[i]=b$.

Ngành công nghệ chụp ảnh cũng đã tiến bộ hơn rất nhiều: Thay vì mất $1$ đơn vị tiền tệ cho mỗi ô được chụp (không tính lặp), giờ đây, sử dụng kiến thức siêu tà đạo về việc giảm từ 2 chiều xuống còn 1 chiều, các pháp sư Trung Hoa đã khiến cho việc chụp 1 bức ảnh dạng hình vuông $C\times C$ chỉ mất đúng $C$ đơn vị tiền tệ. Tuy nhiên, các vệ tinh vẫn chỉ có thể chụp được các bức ảnh thỏa mãn điều kiện cũ:

• Vùng được chụp bởi mỗi tấm ảnh là 1 hình vuông có 2 góc trái trên và phải dưới thuộc đường chéo là quỹ đạo của vệ tinh đó.
• Tọa độ của cả 4 góc của hình vuông là nguyên. Bức ảnh được phép chụp cả những ô không nằm trong bảng

Dù mọi thứ đã thay đổi nhiều là vậy, vẫn có 1 điều chưa thay đổi: Bạn vẫn nghèo vcl. Vì vậy, bạn cần phải tìm cách chụp tối đa $K$ tấm ảnh sao cho:

• Tất cả các điểm trong số $M$ điểm quan trọng đều được chụp trong ít nhất 1 tấm ảnh
• Tổng chi phí để chụp $K$ tấm ảnh là nhỏ nhất
• Bạn chỉ được phép thuê đúng 1 trong số $P$ vệ tinh để chụp ảnh, vì từ vệ tinh thứ 2 trở đi bạn sẽ phải trả $inf\times (inf^{inf})$ đơn vị tiền tệ (điều này rất tệ cho tình hình kinh tế của bạn và gia đình bạn)

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

6

5 4 2 2
5 7
2 2
2 4
3 3
5 3

4

Giải thích:

• 2 hình vuông màu xanh dương là 1 cách để chụp tất cả các vị trí quan trọng bằng 2 bức ảnh, với chi phí bỏ ra là 8 (không tối ưu)
• Hình vuông màu vàng là 1 cách để chụp tất cả các vị trí quan trọng bằng 1 bức ảnh, với chi phí bỏ ra là 5 (không tối ưu)
• Hình vuông màu đỏ là 1 cách để chụp tất cả các vị trí quan trọng bằng 1 bức ảnh, với chi phí bỏ ra là 4 (tối ưu)

Bạn được cho 2 số $n$ và $m$. Mỗi bước bạn được trừ $n$ cho ước chung lớn nhất của $n$ và $m$. Nhiệm vụ của bạn là đếm số bước để đưa $n$ về $0$

10 3

4

Cho $a = a_1, a_2, ..., a_n$ là một dãy số nguyên không âm. Hãy đếm số cách chia dãy $a$ thành các đoạn con liên tiếp, sao cho $MEX$ của các đoạn con, theo thứ tự, tạo thành một dãy không giảm. Ở đây, $MEX$ của đoạn con $[i..j]$ là số nguyên không âm nhỏ nhất không xuất hiện trong $\{a_i, a_{i + 1}, ..., a_j\}$

8
3 0 2 1 0 1 3 2

8

Cho một số nguyên dương $n$. Xét một hoán vị $A = (1, 2, 3, ..., n)$. Bạn phải sử dụng chính xác $n! - 1$ thao tác, mỗi thao tác sẽ đổi chỗ hai số trong dãy $A$, để tạo ra tất cả các hoán vị cùa dãy $(1, 2, 3, ..., n)$.

Định nghĩa: Dãy số $A$ được xem là hoán vị của dãy số $B$ khi và chỉ khi nếu sắp xếp lại hai dãy số $A$ và $B$ theo thứ tự tăng dần, ta thu được hai dãy giống hệt nhau. Ví dụ $(2, 1, 3)$ là hoán vị của $(1, 2, 3)$, nhưng $(1, 2, 4)$ thì không.

2

1 2

3

1 2
1 3
1 2
1 3
1 2

Cho một số nguyên dương $n$. Xét một chuỗi nhị phân có $n$ bit với các bit ban đầu đều là $0$. Bạn phải sử dụng chính xác $2^n - 1$ thao tác, mỗi thao tác sẽ thay đổi trạng thái của một bit, để tạo ra tất cả chuỗi bit có $n$ bit..

2

1
2
1

Một dãy ngoặc đúng là một xâu thỏa mãn tính chất sau:

• Xâu đó là một xâu rỗng, hoặc
• Xâu đó có dạng $(A)$, với $A$ là một dãy ngoặc đúng, hoặc
• Xâu đó có thể được tách thành hai xâu $AB$, với $A, B$ là các dãy ngoặc đúng khác xâu rỗng.

Với định nghĩa trên, giả sử dãy ngoặc đúng có độ dài $2n$ thì nó sẽ có $n$ ngoặc mở và $n$ ngoặc đóng.

Một cách phân tích một dãy ngoặc đúng $a$ có độ dài $2n$ được định nghĩa là một cách đặt các số $1, 2, ..., 2n$ thành $n$ cặp $(x_1, x_2), (x_3, x_4), ..., (x_{2n-1}, x_{2n})$ sao cho thỏa mãn các điều kiện sau:

• $x_{2i-1} < x_{2i}$ với mọi $1 \le i \le n$.
• $x_{2i-1} < x_{2i+1}$ với mọi $1 \le i < n$.
• $a_{2i-1}$ là ngoặc mở và $a_{2i}$ là ngoặc đóng với mọi $1 \le i \le n$.
• Nếu bỏ đi hai ký tự ở vị trí thuộc cùng một cặp $(x_{2i-1}, x_{2i})$ bất kỳ thì dãy ngoặc thu được vẫn là dãy ngoặc đúng.

Ví dụ: Một cách phân tích dãy ngoặc $(()())$ đó là phân tích thành các cặp $(1, 3), (2, 6), (4, 5)$, vì

• $1 < 2 < 4$, $1 < 3$, $2 < 6$ và $4 < 5$.
• Nếu bỏ đi cặp $(1, 3)$ hoặc cặp $(4, 5)$ thì dãy ngoặc còn lại sẽ là $(())$, vẫn là dãy ngoặc đúng.
• Nếu bỏ đi cặp $(2, 6)$ thì dãy ngoặc còn lại sẽ là $()()$.

Cho một dãy ngoặc đúng $a$. Bạn hãy đếm số cách phân tích dãy ngoặc đúng $a$ theo định nghĩa như trên.

(()())

4

(())

2

Bạn được cho 1 xâu $a$ gồm $n$ ký tự chỉ gồm các ký tự như &, |, ^ (tương đương với phép toán AND, OR, XOR). Bạn phải thực hiện $q$ truy vấn:

• $1$ $k$ $x$: Cập nhật ký tự thứ $k$ trong xâu $a$ thành $x$ ($1\le k\le n$, $x$ thuộc 1 trong 3 loại ký tự như trên)
• $2$ $l$ $r$ $k$ $u$ $v$: Tính độ đẹp của xâu trong đoạn $[l,r]$ với các giá trị $k,u,v$ ($1\le l\le r\le n,1\le k\le 20,0\le u\le v<2^k$)

huyhau6a2 định nghĩa độ đẹp của một xâu ký tự $a$ độ dài $x$ với các giá trị $k,u,v$ như sau: Là số lượng dãy $b$ thỏa mãn ($0\le b_i<2^k$):

Chú ý: Thứ tự thực hiện tính toán theo các ký tự của xâu $a$ được thực hiện từ trái sang phải

VD: Xâu |^ với $k=1,u=1,v=1$ thì có các khả năng như sau:

• 0|0^0=0
• 0|0^1=1
• 0|1^0=1
• 0|1^1=0
• 1|0^0=1
• 1|0^1=0
• 1|1^0=1
• 1|1^1=0

Theo như kết quả ở trên, có 4 kết quả thỏa mãn. Vậy độ đẹp của xâu |^ với $k=1,u=1,v=1$ là $4$

Nhiệm vụ của bạn là phải tính toán các kết quả của truy vấn 2. Vì kết quả rất lớn nên hãy xuất kết quả $mod\ 10^9+7$

3 4
&|^
2 2 3 1 1 1
1 3 |
2 2 3 1 0 1
2 1 3 2 2 2

4
8
39

Trong máy tính có hai số nguyên dương $A$ và $B$, và bạn chỉ biết được số $B$, nhưng bạn biết được rằng $A, B \le 2 \times 10^5$. Bạn cần tìm số $A$ trong không quá $3$ thao tác giao tiếp với máy chấm. Với mỗi thao tác, bạn cần đưa ra một số $m \le 2 \times 10^{6}$, và máy chấm sẽ trả về giá trị $A^B$ sau khi đã chia lấy dư cho $m$.

Bài nộp của bạn được chấm qua các testcases. Trong mỗi testcase có thể có nhiều subtest, các subtest này được chấm điểm riêng biệt.

Ngôi trường của Tuấn chuẩn bị kỉ niệm ngày thành lập trường. Nhà trường đã trồng một hàng cây xanh trông rất đẹp. Hàng cây gồm $n$ cây xanh được đánh số thứ tự từ $1$ đến $n$ (theo hướng từ trái sang phải) và cách đều nhau, tức là khoảng cách giữa hai cây kề nhau là không đổi.

Để tưới nước cho cây, nhà trường có kế hoạch lắp đặt $m$ ($1\leq m\leq n$) vòi tưới nước tự động. Vòi nước thứ $i$ ($i=1,2,3,...,m$) được lắp tại vị trí cây thứ $X_i$ thì có thể tưới nước cho cây thứ $X_i$ và $R_i$ cây liền kề bên trái và $R_i$ cây liền kề bên phải vòi nước đó, tức là vòi thứ $i$ sẽ tưới nước cho cây thứ $j$ nếu $|j-X_i|\leq R_i$. $R_i$ được gọi là bán kính tưới nước của vòi thứ $i$.
Cho biết vị trí lắp $m$ vòi nước tại $m$ cây có số thứ tự là $X_1, X_2, ..., X_m$ ($1\leq X_1<X_2<\cdots<X_m\leq n$) và các bán kính tưới nước là $R_1, R_2, ..., R_m$ ($1\leq R_1, R_2, ..., R_m\leq 100$).

Yêu cầu: Tính xem, có bao nhiêu cây được tưới nước khi lắp $m$ vòi nước tự động như trên. Một cây được tưới nước nếu có ít nhất một vòi nước có thể tưới nước cho cây đó.

8 2
2 2
5 1

6

Trò chơi chọn bóng mà nhóm của Tuấn thiết kế được bạn bè và giáo viên trong trường đánh giá rất cao. Sau thành công này, Tuấn cùng nhóm bạn tập trung học tập để thi vào lớp chuyên tin của một trường chuyên danh giá trong tỉnh. Những bài tập mà Tuấn làm đều yêu cầu kỹ năng thiết kế thuật toán chuyên nghiệp. Một trong các bài tập mà bạn ấy đang xây dựng thuật toán có nội dung như sau:

Cho chuỗi kí tự $S$ chỉ gồm các kí tự chữ cái latinh thường từ a, ..., z. Một chuỗi con $X$ (gồm các kí tự ở vị trí liên tiếp) của $S$ được gọi là một chuỗi có mật độ xuất hiện cao nếu trong chuỗi $X$ có một kí tự mà số lần xuất hiện của kí tự đó nhiều hơn số các kí tự còn lại trong chuỗi $X$.

Ví dụ, chuỗi $S=$abbbabced, chuỗi con $X=$abbbabc là một chuỗi có mật độ xuất hiện cao, vì có kí tự b xuất hiện $4$ lần, số các kí tự còn lại là $3$. Nếu $X=$abbbabce, kí tự xuất hiện nhiều lần nhất $4$ lần (kí tự b) và số kí tự còn lại là $4$. Do vậy chuỗi $X=$abbbabce không phải là một chuỗi có mật độ xuất hiện cao.

Yêu cầu: Tìm một chuỗi con $X$ (gồm các kí tự ở vị trí liên tiếp) của $S$ là một chuỗi có mật độ xuất hiện cao và độ dài lớn nhất.

Tuấn cũng đã có thuật toán của mình, còn bạn thì sao? Hãy lập trình giải bài toán trên để đối chiếu kết quả nhé.

abbbabced

7

ababab

5

abc

1

Ngày thành lập Đoàn 26/3 sắp đến. Tuấn cùng nhóm bạn của mình được giao thiết kế một trò chơi trí tuệ dành cho các đoàn viên trong trường. Sau một thời gian tìm hiểu và nghiện cứu, nhóm của Tuấn đã xây dựng một trò chơi có nội dung như sau:

Một rổ bóng có $n$ quả bóng. Các quả bóng được đánh số từ $1$ đến $n$. Quả bóng thứ $i$ có màu được mã hóa bởi một số nguyên dương $c_i$ ($1\leq c_i\leq k$), trong đó $k$ là số màu khác nhau trong $n$ quả bóng. Mỗi lần chời, người chơi sẽ chọn hai quả bóng khác màu trong rổ bóng và đưa hai quả bóng này ra khỏi rổ. Người chơi sẽ dừng lại khi trong rổ không còn quả bóng nào hoặc không có hai quả bóng khác màu. Số bóng được lấy ra khỏi rổ là số điểm của người chơi.

Tuấn cùng nhóm bạn muốn biết người chơi có thể đạt được điểm lớn nhất là bao nhiêu? Bạn hãy lập trình để tìm kết quả này nhé.

6 2
1 2 2 1 1 1

4

4 3
3 3 1 2

4

Tuấn là một học sinh rất yêu thích Tin học. Ước mơ của cậu sau này là trở thành một lập trình viên tài năng. Tuấn thường xuyên tìm hiểu các thông tin, sự kiện liên quan đến Công nghệ. Một sự kiện công nghệ nổi tiếng trên toàn thế giới trong thời gian gần đây là sự ra mắt robot thông minh ChatGPT của công ty công nghệ OpenAI. Tuấn cũng rất tò mò về ChatGPT nên đã sử dụng để giải bài toán. Bài toán mà Tuấn đưa cho ChatGPT như sau:

Cho số nguyên dương $n$. Tìm số lượng các số nguyên dương $x$ nhỏ hơn $n$ thỏa mãn: $x$ và $n$ là hai số nguyên tố cùng nhau (tức là ước chung lớn nhất của $x$ và $n$ bằng $1$).

Thật là thú vị, khi Tuấn nhập $n=5$. ChatGPT đưa ra kết quả là: Có $4$ số, cụ thể là các số: $1,2,3,4$. Tuấn muốn các bạn lập trình giải bài toán này để cùng kiểm tra kết quả của ChatGPT nhé.

5

4

10

4