Cho $n$ số nguyên liên tiếp từ 1 đến $n$ và hai số nguyên dương $k,m$
Với mỗi $i$, ta định nghĩa giá trị $C_i$ là tích $k$ số liên tiếp từ $i-k+1$ đến $i$: $C_i=(i-k+1)\cdot (i-k+2)\cdot \dots \cdot (i-1)\cdot i$.

Ví dụ: $n=6,k=3$, ta có các giá trị: $C_3=1\cdot 2\cdot 3,C_4=2\cdot 3\cdot 4,C_5=3\cdot 4\cdot 5,C_6=4\cdot 5\cdot 6$.

Yêu cầu: Cho $n,k,m$, hãy tính tổng $S=C_k+C_{k+1}+\dots+C_n$. Vì $S$ có thể rất lớn nên bạn chỉ cần in ra phần dư của $S$ cho $m$

6 3 1234 

210

10 5 666013 

55440

Một bài toán rất thú vị về tích chia hết

Bạn được cho dãy số $a$ gồm $n$ số và 2 số $m, k$. Nhiệm vụ của bạn là đếm số bộ $k$ số $b_1,b_2,\dots,b_k$ ($1\le b_1<b_2<\dots<b_k\le n$) thỏa mãn $a_{b_1}\times a_{b_2}\times \dots \times a_{b_k}$ chia hết cho $m$. 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$

5 6 3
2 3 1 2 2

6

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

231

Bạn được cho 2 số $l,r$. Ta gọi $f(x)$ là tổng chữ số của $x$. Đếm số lượng số $x$ nằm trong đoạn $[l,r]$ thỏa mãn $f(x)=f(x+f(x))$

5
1 81
12 125
69 420
90 120
12345 54321

9
10
28
2
2939

Đà Nẵng - nơi được mệnh danh là "thành phố đáng đến nhất Việt Nam", nơi đây đang dần trở thành điểm sáng của cả nước trong lĩnh vực du lịch, thu hút hàng triệu lượt du khách mỗi năm bởi vẻ trẻ trung, văn minh và hiện đại.

An là một cậu bé thích khám phá các mảnh đất mới. Để chuẩn bị cho một kì nghỉ hè đáng nhớ sau một năm học đầy căng thẳng, An và gia đình sẽ đi du lịch tại thành phố Đà Nẵng thân yêu. Hơn thế nữa cậu được bố mẹ giao cho công việc lên kế hoạch cho chuyến đi.

Thành phố Đà Nẵng có $n$ điểm tham quan được đánh số từ $1$ đến $n$, điểm tham quan thứ $i$ có tọa độ $(x_i,y_i)$ được kết nối với nhau bằng những con đường một chiều. Vì địa hình đặc thù nên thành phố chỉ đầu tư xây đường đi từ điểm tham quan thứ $i$ đến điểm tham quan thứ $j$ nếu $x_i>x_j$ và $y_i<y_j$. Bạn An muốn có nhiều ký ức đẹp khi đến với mảnh đất Đà Nẵng nên muốn đi qua nhiều điểm tham quan nhất.

Yêu cầu: Em là một người dân đang sinh sống và học tập tại Đà Nẵng, hãy giúp bạn An tìm ra một phương án đi sao cho số điểm tham quan mà bạn An đi qua là lớn nhất.

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

3

Cho $n$ số nguyên không âm $a_1,a_2,\dots,a_n$ và một số nguyên dương $m$. Hãy đếm số bộ ba số $(i,j,k)$ ($i<j<k$) mà $a_i\cdot a_j\cdot a_k$ chia hết cho $m$

5 6
2 3 1 2 2

6

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

85

Chứng khoán là một trong những kênh đầu tư nhiều rủi ro. Nhà đầu tư cần phân tích nhiều yếu tố thị trường để quyết định đầu tư vào một cổ phiếu. Một trong những tham số được nhiều nhà đầu tư quan tâm là tính ổn định giá trị của một cổ phiếu. Xét giá bán của một cổ phiếu trong nhiều phiên giao dịch. Cổ phiếu được xem là có giá ổn định trong một khoảng thời gian nếu khoảng chênh lệch của giá bán cao nhất và giá bán thấp nhất của cổ phiếu đó trong khoảng thời gian trên không vượt quá ngưỡng ổn định giá $T$ cho trước

Yêu cầu: Cho biết giá bạn một cổ phiếu trong $N$ phiên giao dịch. Hãy viết chương trình tính số phiên giao dịch dài nhất mà cổ phiếu đó có giá ổn định

5 10
5 7 9 20 15 13 20 12 11 1

3

Nhập vào một xâu $s$ là họ tên của một người, hãy chuẩn hóa lại họ tên đó. Xâu họ tên là xâu chuẩn hóa khi thỏa mãn điều kiện sau:

• Không có dấu cách nữa
• Chữ cái đầu mỗi từ viết in hoa còn lại in thường

          NgUyen  vAn Ca

Nguyen Van Ca

lE vaN    TEO

Le Van Teo

Cho số nguyên $n$ và dãy gồm $n$ số nguyên $a_1, a_2,\dots,a_n$. Tìm cách xóa đi tối đa 2 dãy con liên tiếp không cắt nhau của dãy đó để các phần tử còn lại có trung bình cộng lớn nhất.

Note: Không có trung bình cộng của dãy rỗng

5
2 5 5 1 3

5

Cho $n$ số nguyên không âm $a_1,a_2,\dots,a_n$ và một số nguyên dương $m$. Hãy đếm số bộ ba số $(i,j,k)$ mà $a_i\cdot a_j\cdot a_k$ chia hết cho $m$ (lưu ý nếu 2 bộ ba mà bộ này là hoán vị của bộ kia thì vẫn tính là 2 bộ, ví dụ $(1,2,3)$ và $(2,1,3)$ là hai bộ khác nhau)

2 5
1 5

7

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

657

An có rất nhiều tiền trong ngân hàng Thụy sĩ, một hôm An cần rút một số tiền $n$ ($n\le 10^5$), ngân hàng chỉ có $k$ ($k\le 10^3$) loại mệnh giá lần lượt là $a_1,a_2,\dots,a_k$. Vì lý do đặc biệt nên An mong muốn số tờ tiền rút được là ít nhất.

125 6
1 2 5 10 20 50

4

5 3
2 4 6

-1

Nhằm bảo mật thông tin trao đổi, người gửi và người nhận thông tin có thể đặt ra các quy tắc để tìm ra mật khẩu. Hiếu muốn trao đổi mật khẩu với Hùng nên đặt ra quy tắc như sau: Hiếu gửi cho Hùng một xâu ký tự, mật khẩu được tìm bằng cách tính tổng các chữ số chẵn có trong xâu rồi ghép với chiều dài của xâu đó

Tin hoc tre 2023

416

Số nguyên tố là số chỉ có đúng 2 ước là 1 và chính nó. Độ cao của 1 số là tổng các chữ số của số đó.

Với một số tự nhiên $n$ cho trước, hãy đếm và liệt kê các số nguyên tố có giá trị không vượt quá $n$ và có độ cao đúng bằng $h$

100 16

79
97
2

Tại hội trại của trường THPT ABC, ban tổ chức hộ trại tổ chức trò chơi có tên "Bốc bóng". Trong trò chơi này ban tổ chức xếp $n$ quả bóng thành một hàng ngang, các quả bóng được đánh số thứ tự từ $1$ đến $n$ (theo thứ tự từ trái sang phải). Trên mỗi quả bóng trong $n$ quả bóng ban tổ chức ghi lên trên đó một con số bất kỳ, quả bóng thứ $i$ được ghi lên con số có giá trị $a_i\ (i=1,2,\dots,n)$. Trong trò chơi này ban tổ chức yêu cầu các đội chơi được chọn và bốc ra khỏi hàng $0$ hoặc một số quả bóng liên tiếp ở đầu, hoặc cuối hoặc cả hai đầu của hàng bóng sao cho thỏa mãn các điều kiện sau:

• Số quả bóng còn lại trên hàng không nhỏ hơn $k$
• Trung bình của các con số được ghi trên các quả bóng còn lại trên hàng là lớn nhất

Đội chơi giành được chiến thắng là đội chơi có cách bốc bóng sao cho thỏa mãn được tất cả các yêu cầu trên của ban tổ chức

Yêu cầu: Em hãy đóng vai trò là 1 người chơi tham gia trong trò chơi này, hãy tìm cách bốc bóng sao cho giành được chiến thắng về cho đội của mình nhé.

6 1
2 -1 8 8 8 -7

8.000

5 3
6 -3 6 9 -8

4.500

Đức vừa phát minh ra một phép toán cộng độc đáo và đặt tên cho nó là "cộng một kiểu Đức", cách cộng như sau: Mỗi lần cộng một số nguyên cho một thay vì tăng giá trị của số đó lên một đơn vị Đức lại tăng tất cả các chữ số của nó lên một đơn vị

VD1: $15$ "cộng một kiểu Đức" sẽ cho kết quả là $26$

VD2: $91$ "cộng một kiểu Đức" sẽ cho kết quả là $102$

Yêu cầu: Với $T$ số nguyên dương $N$ cho trước hãy tính toán và cho biết sau khi thực hiện $K$ lần phép cộng một kiểu Đức thì kết quả sinh ra có bao nhiêu chữ số. Vì câu trả lời có thể rất lớn do đó hãy in ra kết quả sau khi $mod\ 10^9+7$

2
9812 2
9899 3

6
8

Tâm rất yêu thích lập trình tạo phần mềm. Vào dịp rảnh rỗi Tâm đã thiết kế một phần mềm đơn giản. Màn hình phần mềm gồm $N$ địa điểm (đánh số từ $1$ đến $N$), trong đó mỗi địa điểm có đặt một bóng đèn ở trạng thái sáng hoặc tắt. Có $N-1$ con đường một chiều nối trực tiếp giữa các cặp điểm. Mỗi lần Tâm chạm tay vào một địa điểm $X_i$ bất kỳ trên màn hình thì sẽ có một robot xuất phát từ địa điểm $X_i$ di chuyển theo các con đường một chiều, cuối cùng kết thúc ở địa điểm $1$. Robot không thay đổi trạng thái đèn ở địa điểm $X_i$ và địa điểm $1$, các địa điểm còn lại robot đã đi qua thì đèn ở địa điểm đó sẽ thay đổi sang trạng thái ngược lại (sáng thành tắt, tắt thành sáng)

Yêu cầu: Hãy cho biết khi Tâm thực hiện $K$ lần chạm tay (mỗi lần chạm tay vào một địa điểm) thì sau đó sẽ có bao nhiêu địa điểm có đèn sáng. Biết rằng robot xuất phát từ địa điểm bất kỳ luôn có thể di chuyển theo các con đường một chiều đến địa điểm $1$

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

3

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

2

Xét một bàn cờ vua có kích thước $m \times n$ có $m$ hàng $n$ cột.

Các hàng được đánh số từ $1$ đến $m$ và các cột được đánh số từ $1$ đến $n$.

Một quân mã xuất phát từ một ô trên bàn cờ có thể đi đến một trong bốn ô như hình vẽ.

Ngoài ra, trên bàn cờ có $k$ ô mà quân mã không được phép đi vào. Những ô này được gọi là những ô bị cấm.

Yêu cầu: Tìm số cách di chuyển của quân mã từ ô $(x, y)$ đến ô $(m, n)$.

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

1
1
0

Cây nhị phân tìm kiếm (Binary Search Tree – BST) trên tập $n$ khóa số nguyên là một cây nhị phân thỏa mãn: Mỗi nút chứa đúng một khóa và khóa trong một nút lớn hơn mọi khóa trong nhánh con trái và nhỏ hơn mọi khóa trong nhánh con phải. Có nhiều cấu trúc BST để biểu diễn một tập các khóa. Như hình dưới đây là hai BST biểu diễn tập các khóa $\{1,2,3,4,5,6\}$.

Quá trình tìm kiếm một giá trị $x$ trên BST thực hiện như sau: Bắt đầu từ nút gốc, tại mỗi bước, $x$ được so sánh với khóa tại nút đang đứng ($y$):

• Nếu $x=y$, quá trình tìm kiếm kết thúc, kết luận $x$ có trong BST
• Nếu $x<y$, đi sang nhánh con trái và quá trình tìm kiếm tiếp tục trong cây con trái bằng cách tương tự
• Nếu $x>y$, đi sang nhánh con phải và quá trình tìm kiếm tiếp tục trong cây con phải bằng cách tương tự

Nếu tại một bước nào đó, thuật toán không thể đi tiếp được theo luật trên, quá trình tìm kiếm dừng và kết luận $x$ không có trong BST.
Chi phí một phép tìm kiếm giá trị $x$ bằng số phép so sánh khóa được thực hiện trong thuật toán. Như ở hình trên, để tìm khóa $3$ trong cây (a) ta cần $3$ phép so sánh trong khi đó để tìm khóa $3$ trong cây (b) ta chỉ cần $2$ phép so sánh.
Yêu cầu: Cho $n$ khóa đánh số từ $1$ tới $n$ theo thứ tự tăng dần của các khóa, biết rằng người ta thực hiện $c_i$ lần phép tìm kiếm khóa $i$ trên cấu trúc BST biểu diễn tập khóa này ($\forall i = 1,2,...,n$). Hãy tìm cấu trúc BST sao cho tổng chi phí các phép tìm kiếm là nhỏ nhất.

6
4 9 5 1 3 2 

48

Cho đa giác lồi gồm $n$ đỉnh và $m$ đường chéo. Biết rằng nếu hai đường chéo khác nhau chỉ có thể gặp nhau tại đỉnh của đa giác. Các đỉnh của đa giác được đánh số từ 1 tới $n$ theo một hoán vị nào đó.
Yêu cầu: Cho biết danh sách $n$ cạnh và $m$ đường chéo, hãy liệt kê các đỉnh của đa giác theo đúng thứ tự tạo thành đa giác đã cho.

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

1 3 2 4