KHOÁ LUYỆN ĐỀ DÀNH CHO HS THCS GÓI 1

# KHOÁ LUYỆN ĐỀ DÀNH CHO HS THCS ## :books: ĐỀ SỐ 1: ĐỀ THI HSG AN GIANG (2021 - 2022) **SỞ GIÁO DỤC VÀ ĐÀO TẠO AN GIANG** KỲ THI CHỌN HỌC SINH GIỎI CẤP TRUNG HỌC CƠ SỞ NĂM HỌC 2021-2022 Môn: TIN HỌC Ngày thi: 02/04/2022 --- (Đề thi gồm 02 trang) Thời gian: 150 phút (Không kể thời gian giao đề) ### TỔNG QUAN ĐỀ THI | TT | Tên bài | Tên tệp bài làm | Đầu vào | Đầu ra | Điểm | | - | - | - | - | - | - | | 1 | BÀI 1 | BAI01.PAS | BAI01.INP | BAI01.OUT | 5,0 điểm | | 2 | BÀI 2 | BAI02.PAS | BAI02.INP | BAI02.OUT | 5,0 điểm | | 3 | BÀI 3 | BAI03.PAS | BAI03.INP | BAI03.OUT | 5,0 điểm | | 4 | BÀI 4 | BAI04.PAS | BAI04.INP | BAI04.OUT | 5,0 điểm | ### :question: Bài 1 :::info Cho xâu ký tự $S$ có 4 hoặc 5 ký tự số, được quy ước như sau: hai ký tự cuối là hai chữ số cuối của một năm trong thế kỷ 21, một hoặc hai ký tự đầu cho biết ngày, các ký tự còn lại cho biết tháng. **Giả sử**: tháng 1, 3, 5, 7, 8, 10, 12 có 31 ngày, các tháng còn lại có 30 ngày, riêng tháng 2 năm thường có 28 ngày, năm nhuận có 29 ngày. *Năm nhuận là năm chia hết cho 4 và không chia hết cho 100 hoặc năm chia hết cho 400*. ::: :::warning Viết chương trình kiểm tra xâu $S$ (có 4 hoặc 5 ký tự số) có phải là ngày hợp lệ có dạng ngày/tháng/năm theo đúng yêu cầu bên trên, cụ thể như sau: **Input** (dữ liệu nhập) cho trong tập tin `BAI01.INP` là giá trị của xâu S. **Output** (dữ liệu xuất) ghi vào tập tin `BAI01.OUT` ngày hợp lệ được tạo ra theo yêu cầu bên trên. Trong trường hợp xâu không tạo được ngày hợp lệ thì kết quả `KHONG TAO DUOC`, trường hợp xâu $S$ có nhiều cách tạo hợp lệ thì chỉ cần ghi ra một cách tạo hợp lệ. ::: **Chương trình ví dụ**: | Lần thử | BAI01.INP | BAI01.OUT | | - | - | - | | 1 | 1316 | 1/3/16 | | 2 | 11216 | 11/2/16 (hoặc 1/12/16) | | 3 | 29217 | KHONG TAO DUOC | ### :question: Bài 2 :::info Trên mặt đồng hồ, kim giờ đang chỉ vào số $12$. Có hai thao tác trên đồng hồ gồm: thao tác điều chỉnh kim đồng hồ qua chiều thuận $N$ số được ký hiệu: $+N$ và thao tác điều chỉnh kim theo chiều ngược lại $N$ số được ký hiệu: $-N$. Hãy tìm giá trị số mà kim giờ chỉ định sau khi thực hiện một thao tác điều chỉnh. Ví dụ: - Với $N=3$ nghĩa là điều chỉnh kim giờ di chuyển theo chiều thuận $3$ chữ số, từ số $12$ đến $3$. - Với $N=-11$ nghĩa là điều chỉnh kim giờ di chuyển theo chiều nghịch $11$ chữ số, từ số $12$ về số $1$. ::: :::warning Viết chương trình xác định giá trị số mà kim giờ chỉ đến theo các yêu cầu sau: **Input** (dữ liệu nhập) cho trong tập tin `BAI02.INP` là số nguyên $N$ $(-10^9 \le N \le 10^9)$. **Output** (dữ liệu xuất) ghi vào tập tin `BAI02.OUT` là giá trị kim giờ chỉ đến sau khi đã thực hiện thao tác điều chỉnh. ::: **Chương trình ví dụ**: | Lần thử | BAI02.INP | BAI02.OUT | | - | - | - | | 1 | 3 | 3 | | 2 | -4 | 8 | ### :question: Bài 3 :::warning Viết chương trình tìm số nguyên dương $a$ nhỏ nhất sao cho $a^a$ chia hết cho $N$ $(2 \le N \le 10^9)$ theo các yêu cầu sau: **Input** (dữ liệu nhập) cho trong tập tin `BAI03.INP` là số nguyên $N$ $(2 \le N \le 10^9)$. **Output** (dữ liệu xuất) ghi vào tập tin `BAI03.OUT` là số nguyên dương $a$ nhỏ nhất sao cho $a^a$ chia hết cho $N$. ::: **Chương trình ví dụ**: | Lần thử | BAI03.INP | BAI03.OUT | | - | - | - | | 1 | 9 | 3 | | 2 | 6 | 6 | ### :question: Bài 4 :::info *Chuỗi lặp lại* là chuỗi mà nếu ta đọc từ trái sang phải có chuỗi ký tự liền sau giống dãy ký tự trước đó; Độ dài chuỗi lặp lại nhỏ nhất là 2 ký tự và là một số chẵn. **Ví dụ**: chuỗi `abab` là chuỗi lặp lại; chuỗi `abcab` **không** phải là chuỗi lặp lại. ::: :::warning Viết chương trình nhập theo yêu cầu sau: **Input** (dữ liệu nhập) cho trong tập tin `BAI04.INP` là chuỗi ký tự $S$ có chiều dài không quá 255 ký tự. **Output** (dữ liệu xuất) ghi vào tập tin `BAI04.OUT` là chuỗi con lặp lại dài nhất của $S$. Biết rằng chuỗi con của $S$ là chuỗi gồm một số ký tự liên tiếp nhau trong $S$ có độ dài nhỏ hơn hoặc bằng độ dài của chuỗi $S$. Trong trường hợp không tìm được chuỗi lặp lại thì thông báo `KHONG TIM DUOC`. ::: **Chương trình ví dụ**: | BAI04.INP | BAI04.OUT | | - | - | | zababcabcdq | abcabc | --- ## :books: ĐỀ SỐ 2: ĐỀ THI HSG THCS AN GIANG (2022 - 2023) **SỞ GIÁO DỤC VÀ ĐÀO TẠO AN GIANG** KỲ THI CHỌN HỌC SINH GIỎI CẤP TRUNG HỌC CƠ SỞ NĂM HỌC 2022-2023 Môn: TIN HỌC Ngày thi: 18/03/2023 --- (Đề thi gồm 02 trang) Thời gian: 150 phút (Không kể thời gian giao đề) ### TỔNG QUAN ĐỀ THI | TT | Tên bài | Tên tệp bài làm | Đầu vào | Đầu ra | Điểm | | - | - | - | - | - | - | | 1 | BÀI 1 | BAI01.PAS | BAI01.INP | BAI01.OUT | 6,0 điểm | | 2 | BÀI 2 | BAI02.PAS | BAI02.INP | BAI02.OUT | 6,0 điểm | | 3 | BÀI 3 | BAI03.PAS | BAI03.INP | BAI03.OUT | 4,0 điểm | | 4 | BÀI 4 | BAI04.PAS | BAI04.INP | BAI04.OUT | 4,0 điểm | ### :question: Bài 1 :::warning Không phải cử ngắn gọn là dễ! Bạn có thể kiểm chứng điều đó ở bài toán sau: Cho $3$ số nguyên $A$, $B$, $C$ $(1 < A, B, C < 10^{12})$. Hãy tìm số dư khi chia $A^B$ cho $C$. **Input** (dữ liệu nhập) cho trong tập tin `BAI01.INP` gồm một dòng chứa $3$ số nguyên $A$, $B$, $C$ (các số cách nhau ít nhất một ký tự khoảng trắng). **Output** (dữ liệu xuất) ghi vào tập tin `BAI01.OUT` một số nguyên – là số dư tìm được. ::: **Dữ liệu thử**: | BAI01.INP | BAI01.OUT | | - | - | | 3 4 5 | 1| ### :question: Bài 2 :::info Số tự nhiên có rất nhiều tính chất thú vị. Ví dụ với số $23$, số đảo ngược của nó là $32$. Hai số này có ước chung lớn nhất là $1$. Những số như thế được gọi là số thân thiện, tức là số $23$ được gọi là số thân thiện, số $32$ cũng được gọi là số thân thiện. ::: :::warning **Yêu cầu**: cho 2 số nguyên $a$, $b$ $(10 < a < b < 10^5)$. Đếm số lượng số thân thiện trong đoạn giá trị $[a, b]$. **Input** (dữ liệu nhập) cho trong tập tin `BAI02.INP` chứa 2 số $a$, $b$. **Output** (dữ liệu xuất) ghi vào tập tin `BAI02.OUT` số lượng số thân thiện tìm được. ::: **Dữ liệu thử**: | BAI02.INP | BAI02.OUT | | - | - | | 20 30 | 3 | ### :question: Bài 3 :::info Cho trước khoá là một hoán vị (đảo vị trí các số) của $n$ số $(1, 2, ..., n)$. Khi đó để mã hoá một xâu kí tự ta có thể chia xâu từ trái qua phải thành từng nhóm có $n$ kí tự (với $2<n<10$); riêng nếu nhóm cuối cùng không đủ $n$ kí tự thì ta có thể thêm các ký tự trắng vào sau cho đủ. Sau đó hoán vị các kí tự trong từng nhóm theo khóa. Sau đó, ghép các nhóm xâu lại theo thứ tự ta được một xâu đã mã hoá. ::: :::warning Hãy viết chương trình mã hoá một xâu ki tự cho trước với các yêu cầu sau: **Input** (dữ liệu nhập) cho trong tập tin `BAI03.INP` gồm 02 (hai) dòng, cụ thể như sau: - Dòng thứ nhất: ghi khóa là số $n$ và 1 hoán vị của nó (cách nhau ít nhất 1 ký tự trắng). - Dòng thứ hai: ghi xâu cần mã hóa. **Ouput** (dữ liệu xuất) ghi vào tập tin `BAI03.OUT` gồm nhiều dòng, mỗi dòng là $n$ ký tự của xâu đã được mã hóa (bao gồm ký tự trắng). ::: **Chương trình ví dụ**: | BAI03.INP | BAI03.OUT | | - | - | | **8** **87345621** hello every body | vello eh ydy bore | ### :question: Bài 4 :::info Cho số nguyên dương $N$ $(N \le 3000)$. Hãy xác định một số $M$ nguyên dương nhỏ nhất là bội số của số $N$ sao cho biểu diễn của $M$ trong hệ thập phân chỉ chứa các chữ số $0$ và $1$. ::: :::warning Viết chương trình giải quyết các yêu cầu trên với các điều kiện như sau: **Input** (dữ liệu nhập) cho trong tập tin `BAI04.INP` gồm một dòng duy nhất ghi giá trị $N$. **Output** (dữ liệu xuất) ghi vào tập tin `BAI04.OUT` gồm một dòng duy nhất ghi giá trị $M$. ::: **Dữ liệu thử**: | BAI04.INP | BAI04.OUT | | - | - | | 40 | 1000 | --- ## :books: ĐỀ SỐ 3: ĐỀ THI HSG THCS BÀ RỊA - VŨNG TÀU (2014 - 2015) **SỞ GIÁO DỤC VÀ ĐÀO TẠO BÀ RỊA - VŨNG TÀU** KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 TRUNG HỌC CƠ SỞ NĂM HỌC 2014-2015 Môn: TIN HỌC Ngày thi: 25/03/2015 --- (Đề thi gồm 02 trang) Thời gian: 150 phút (Không kể thời gian giao đề) ### TỔNG QUAN ĐỀ THI | TT | Tên bài | Tên tệp bài làm | Đầu vào | Đầu ra | Điểm | | - | - | - | - | - | - | | 1 | THỪA KẾ | SUBTRACT.PAS | SUBTRACT.INP | SUBTRACT.OUT | 7,0 điểm | | 2 | CHỌN QUÀ | CHOICE.PAS | CHOICE.INP | CHOICE.OUT | 7,0 điểm | | 3 | ĐỔ NƯỚC VÀO CHAI | WATER.PAS | WATER.INP | WATER.OUT | 6,0 điểm | ### :question: Bài 1: Thừa kế :::info Có một ông phú hộ rất giàu có, tài sản của ông ta là một dãy số nguyên liên tiếp bắt đầu là $a$ và kết thúc là $b$. Khi đến tuổi già, trước khi qua đời ông muốn chia tài sản của mình cho 2 người con, người con thứ 1 được nhận các tài sản có giá trị là các số chẵn, người con thứ 2 được nhận các tài sản có giá trị là các số lẻ. Nhưng ông phú hộ vẫn chưa biết trước được ai sẽ là người nhận được nhiều hơn và nhiều hơn là bao nhiêu. ::: :::warning Yêu cầu: Hãy xác định trong 2 người con ai sẽ là người nhận được nhiều tài sản hơn và nhiều hơn là bao nhiêu? **Dữ liệu vào**: Từ file `SUBTRACT.INP` gồm 2 số nguyên dương $a$, $b$ $(a < b \le 10^9)$ **Kết quả ra**: Ghi vào file `SUBTRACT.OUT` gồm 2 số nguyên trên 2 dòng - Số thứ nhất ghi số $1$ nếu người con thứ nhất được nhiều tài sản hơn, ngược lại ghi số $2$. - Số thứ hai ghi độ chênh lệch tài sản giữa 2 người con. ::: **Ví dụ 1**: | SUBTRACT.INP | SUBTRACT.OUT | | - | - | | 3 10 | 1 4 | - Tài sản người con thứ 1 nhận được là $S_1=4+6+8+10=28$ - Tài sản người con thứ 2 nhận được là $S_2=3+5+7+9=24$ - Vậy người con thứ 1 nhận được nhiều tài sản hơn và nhiều hơn là $4$. **Ví dụ 2**: | SUBTRACT.INP | SUBTRACT.OUT | | - | - | | 4 13 | 2 5 | - Tài sản người con thứ 1 nhận được là $S_1=4+6+8+10+12=40$ - Tài sản người con thứ 2 nhận được là $S_2=5+7+9+11+13=45$ - Vậy người con thứ 2 nhận được nhiều tài sản hơn và nhiều hơn là $5$ ### :question: Bài 2: Chọn quà :::info Trong một cuộc thi vui để học Nam là người đạt điểm cao nhất trong số các thí sinh. Phần thưởng của Nam là 2 món quà được chọn từ $N$ món quà của Ban tổ chức. Các món quà của Ban tổ chức là dãy số nguyên dương $a_1, a_2, ... a_N$, món quà thứ $i$ có giá trị $a_i$. Nam được chọn ra 2 món quả tùy ý khác nhau sao cho tổng giá trị của các món quà còn lại là số chẵn. ::: :::warning **Yêu cầu**: Hãy cho biết Nam có bao nhiêu cách chọn khác nhau? **Dữ liệu vào**: Từ file `CHOICE.INP`: - Dòng đầu tiên là số nguyên dương $N$ $(N \le 10^6)$ - $N$ dòng tiếp theo, mỗi dòng là một số nguyên dương $a_i$ $(a_i \le 10^9)$ **Kết quả ra**: Ghi vào file `CHOICE.OUT` một số nguyên là số cách chọn 2 món quà thỏa mãn đề bài. ::: **Ví dụ**: | CHOICE.INP | CHOICE.OUT | | - | - | | 5 1 2 3 4 5 | 6 | Các cách chọn là (1, 2); (1, 4); (2, 3); (2, 5); (3, 4); (4,5); ### :question: Bài 3: Đổ nước vào chai :::info Sau khi được tham quan nhiều địa điểm, các bạn được vui chơi và thi đua cùng các bạn qua trò chơi do nước vào chai. Các điểm lấy nước được xếp trên cùng một hàng được đánh số thứ tự lần lượt từ $1$ đến $N$. Vị trí thứ $i$ có lượng nước là $a_i$ ($a_i$ là một số nguyên dương, $i=1,2,..,N$). Thể lệ trò chơi là người lấy nước lần lượt từ điểm số $1$ đến điểm thứ $N$ và không được lấy nước ở 2 điểm liền nhau. Đội chiến thắng là đội có số lượng nước nhiều nhất. Bạn giúp đội mình lấy ra lượng tước nhiều nhất nhé. ::: :::warning **Yêu cầu**: Hãy cho biết tổng lượng nước nhiều nhất có thể lấy được? **Dữ liệu vào**: Từ file `WATER.INP`: - Dòng đầu tiên là số nguyên dương $N$ $(N<10^5)$ - $N$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên dương $a_i$ $(a_i \le 10^9)$ **Kết quả ra**: Ghi vào file `WATER.OUT` tổng lượng nước nhiều nhất có thể lấy được. ::: **Ví dụ**: | WATER.INP | WATER.OUT | | - | - | | 5 1 5 2 4 6 | 11 | --- ## :books: ĐỀ SỐ 4: ĐỀ THI HSG THCS BÀ RỊA - VŨNG TÀU (2015 - 2016) **SỞ GIÁO DỤC VÀ ĐÀO TẠO BÀ RỊA - VŨNG TÀU** KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 NĂM HỌC 2015-2016 Môn: TIN HỌC Ngày thi: 25/03/2016 --- (Đề thi gồm 02 trang) Thời gian: 150 phút (Không kể thời gian giao đề) ### TỔNG QUAN ĐỀ THI | TT | Tên bài | Tên tệp bài làm | Đầu vào | Đầu ra | Điểm | | - | - | - | - | - | - | | 1 | ĐẾM SỐ PHONG PHÚ | ABUNDENT.\* | ABUNDENT.INP | ABUNDENT.OUT | 7,0 điểm | | 2 | GHÉP SỐ | NUMBER.\* | NUMBER.INP | NUMBER.OUT | 7,0 điểm | | 3 | NỐI XÍCH | CONCHAIN.\* | CONCHAIN.INP | CONCHAIN.OUT | 6,0 điểm | ### :question: Bài 1: Đếm số phong phú :::info *Số phong phú* là số có tổng các ước số nguyên của nó kể cả số $1$ (không kể chính nó) **lớn hơn** nó. Ví dụ: Số $6$ có tổng các ước $1 + 2 + 3 = 6$ **không** là số phong phú. Số $12$ có tổng các ước là $1 + 2 + 3 + 4 + 6 = 16$ (Lớn hơn $12$) là số phong phú. ::: :::warning **Yêu cầu**: Hãy cho biết có bao nhiêu số phong phú không lớn hơn $N$. **Dữ liệu vào** từ file `ABUNDENT.INP`: - Chứa duy nhất số nguyên $N$ $(0 < N \le 10^5)$ **Kết quả** ghi vào file `ABUNDENT.OUT`: - Ghi một số nguyên duy nhất là kết quả tìm được theo yêu cầu. ::: **Ví dụ**: | ABUNDENT.INP | ABUNDENT.OUT | | - | - | | 24 | 4 | Trong ví dụ trên có 4 số phong phủ là $12$, $18$, $20$, $24$. ### :question: Bài 2: Ghép số :::info Cho 3 số gồm $0$, $1$, $2$. Người ta muốn tạo ra những số có $N$ chữ số từ 3 số trên sao cho số vừa tạo thỏa mãn các yêu cầu sau: - Là số chia hết cho $5$. - Không có 2 chữ số liền kề giống nhau. - Chữ số đầu tiên lớn hơn $0$. Ví dụ: với $n = 4$; Các số thỏa mãn: $2020, 2120...$ Số không thỏa mãn $2110$ (2 chữ số liền kề giống nhau), $2021$ (không chia hết cho $5$)... ::: :::warning **Yêu cầu**: Hãy cho biết có bao nhiêu số thỏa mãn các yêu cầu trên. **Dữ liệu vào**: Từ file `NUMBER.INP` chứa duy nhất số nguyên $N$ $(0 < N \le 21)$ **Dữ liệu ra**: Ghi vào file `NUMBER.OUT` kết quả tìm được theo yêu cầu. ::: **Ví dụ**: | NUMBER.INP | NUMBER.OUT | | - | - | | 4 | 6 | ### :question: Bài 3: Nối xích :::info Cho một dãy $N$ mắt xích lần lượt có độ bền là $a_1, a_2, ..., a_N$. Nếu nối hai mắt xích nằm cạnh nhau là mắt xích thứ $i$ và $i+1$ $(1 \le i<N)$ thì độ bền của mối nối là $d_i$ tính theo công thức: $$ d_i = \left\{ \begin{array}{rcl} 0 & \mbox{khi} & a_i \ge a_{i+1} \\ a_{i+1}-a_{i} & \mbox{khi} & a_i < a_{i+1} \\ \end{array}\right. $$ Khi nối tất cả các mắt xích nằm cạnh nhau thành một dây xích thì độ bền của dây xích bằng tổng độ bền của từng mắt xích cộng với với tổng độ bền của từng mối nối. ::: :::warning **Yêu cầu**: Hãy tìm cách sắp xếp các mắt xích sao cho độ bền của dây xích tạo thành là lớn nhất có thể. **Dữ liệu vào**: Từ file `CONCHAIN.INP`: - Dòng đầu tiên là số nguyên dương $N$ $(N \le 10^5)$ - $N$ dòng tiếp theo, mỗi dòng là một số nguyên dương $a_i$ $(a_i \le 10^6)$ **Dữ liệu ra**: Ghi vào file `CONCHAIN.OUT` một số nguyên là tổng độ bền lớn nhất của dây xích tạo thành. ::: **Ví dụ**: | CONCHAIN.INP | CONCHAIN.OUT | | - | - | | 5 5 7 1 4 3 | 28 | --- ## :books: ĐỀ SỐ 5: ĐỀ THI HSG THCS BÀ RỊA - VŨNG TÀU (2016 - 2017) **SỞ GIÁO DỤC VÀ ĐÀO TẠO BÀ RỊA - VŨNG TÀU** KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 THCS NĂM HỌC 2016-2017 Môn: TIN HỌC --- (Đề thi gồm 02 trang) Thời gian: 150 phút (Không kể thời gian giao đề) ### TỔNG QUAN ĐỀ THI | TT | Tên bài | Tên tệp bài làm | Đầu vào | Đầu ra | Điểm | | - | - | - | - | - | - | | 1 | TÌM SỐ DƯ | MODULO.PAS | MODULO.INP | MODULO.OUT | 8,0 điểm | | 2 | TRÒ CHƠI BẮN SÚNG | SHOOT.PAS | SHOOT.INP | SHOOT.OUT | 7,0 điểm | | 3 | PHÁT THƯỞNG | OFTEN.\* | OFTEN.INP | OFTEN.OUT | 5,0 điểm | ### :question: Bài 1: Tìm số dư :::info Cho biểu thức: $S = 1^3 + 2^3 + ... + n^3$ Gọi $r$ là số dư của $S$ khi chia cho $2017$. Kí hiệu: $r = S\ \mbox{mod}\ 2017$ ::: :::warning **Yêu cầu**: Xác định số dư $r$. **Dữ liệu**: Vào từ file `MODULO.INP` một số nguyên duy nhất $N$ $(1 < n \le 10^9)$. **Kết quả**: Ghi vào file `MODULO.OUT` một số duy nhất là kết quả tìm được theo yêu cầu. ::: **Ví dụ**: | MODULO.INP | MODULO.OUT | | - | - | | 4000 | 69 | ### :question: Bài 2: Trò chơi bắn súng :::info Với thành tích 1 huy chương vàng và 1 huy chương bạc tại Olympic của xạ thủ Hoàng Xuân Vinh, mọi người trên khắp đất nước Việt Nam luôn tự hào về chàng trai áo lính. Những người yêu thích môn bắn súng rất muốn noi theo tấm gương về sự nỗ lực, phấn đấu và rèn luyện của anh. Một bạn học sinh đã yêu thích và đã đưa ra luật chơi môn bắn súng cùng các bạn như sau: Người chơi tham gia bắn vào đích với $n$ viên đạn cho trước, người chiến thắng khi đảm bảo không có 2 lần liên tiếp bắn không trúng đích và trong loạt bắn của mình, phải có ít nhất hai lần liên tiếp bắn trúng đích. Em hãy tìm xem có bao nhiêu cách để trở thành người chiến thắng trong lượt bắn với $n$ viên đạn. ::: :::warning **Yêu cầu**: Hãy cho biết có bao nhiêu trường hợp khác nhau của loạt bắn gồm $n$ viên đạn thoả điều kiện. **Dữ liệu**: Vào từ file `SHOOT.INP` chữ số nguyên $n$ $(n<32)$; **Kết quả**: Ghi vào file `SHOOT.OUT` một số duy nhất là số trường hợp thoả điều kiện. ::: **Ví dụ**: | SHOOT.INP | SHOOT.OUT | | - | - | | 4 | 6 | ### :question: Bài 3: Phát thưởng :::info Vào ngày 13/3/2017 vừa qua, tỉnh Bà Rịa - Vũng Tàu chúng ta được vinh dự đại điện cho khu vực phía Nam đăng cai tổ chức cuộc thi Khoa học kĩ thuật cấp quốc gia học sinh trung học năm 2017. Có rất nhiều đội thi đại diện cho các tỉnh thành khu việc phía Nam đến tham gia dự thi. Nhằm khích lệ tinh thần cho các đội tuyển dự thi, ban tổ chức đã đưa ra một hình thức rất thú vị để thưởng cho đội thi có số điểm cao nhất như sau: Ban tổ chức có $n$ phần thưởng, được xếp thành một hàng và được đánh số thứ tự từ $1$ đến $n$, phần thưởng thứ $i$ có giá trị là $a_i$ ($a_i$ là một số nguyên dương, $i=1, 2, ..., n$). Đội có số điểm cao nhất sẽ được phép chọn nhiều phần thưởng trong các phần thưởng trên nhưng phải đảm bảo không được chọn 2 phần thưởng đặt kế nhau. ::: :::warning **Yêu cầu**: Hãy giúp cho đội thi có số điểm cao nhất chọn các phần thưởng sao cho tổng giá trị các phần thưởng là cao nhất. **Dữ liệu**: Vào từ file `OFTEN.INP`: - Dòng đầu là số nguyên dương $n$ $(n \le 10^5)$. - $n$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên dương $a_i$ $(a_i \le 10^9)$. **Kết quả**: Ghi vào file `OFTEN.OUT` tổng giá trị lớn nhất của các phần thưởng thỏa mãn yêu cầu. ::: **Ví dụ**: | OFTEN.INP | OFTEN.OUT | | - | - | | 4 3 2 1 5 | 8 | ---