Dinh Can's Blog

 ĐỀ THI HỌC SINH GIỎI TIN HỌC THPT CẤP TỈNH VĨNH LONG 2022-2023

ĐỀ THI HỌC SINH GIỎI TIN HỌC LỚP 9 CẤP TỈNH THANH HÓA 2022-2023

 ĐỀ THI HỌC SINH GIỎI TIN HỌC LỚP 12 CẤP TỈNH LÂM ĐỒNG 2022-2023

Có N những đứa trẻ muốn chơi đu quay, và nhiệm vụ của bạn là tìm một chiếc thuyền gondola cho mỗi đứa trẻ. Mỗi gondola có thể có một hoặc hai trẻ em trong đó và ngoài ra tổng trọng lượng trong gondola không được vượt quá x. Bạn biết trọng lượng của mỗi đứa trẻ.

            Số lượng gondola tối thiểu cần thiết cho trẻ em là bao nhiêu?

Dữ liệu vào:

-         Dòng đầu tiên chứa hai số nguyên N (1 ≤ N ≤ 2.10⁵) và x (1 ≤ x ≤ 10⁹): số lượng trẻ em và trọng lượng tối đa cho phép.

-         Dòng tiếp theo chứa N số nguyên p₁, p₂, …, p_N (1 ≤ p_i ≤ x) cân nặng của mỗi đứa trẻ.

Kết quả: In ra một số nguyên là số gondola ít nhất.

Ví dụ:

ĐỀ THI HSG TIN HỌC LỚP 9 TP. HÀ NỘI 2022-2023

Bạn được cung cấp một mảng chứa mỗi số giữa 1 … n chính xác một lần. Nhiệm vụ của bạn là thu thập các số từ 1 đến n theo thứ tự tăng dần.

            Trên mỗi dòng, bạn đi qua dãy từ trái sang phải và thu thập càng nhiều số càng tốt. Tổng số vòng sẽ là bao nhiêu?

Dữ liệu vào:

            Dòng đầu tiên có một số nguyên N (1 ≤ n ≤ 2.10⁵) là kích thước mảng.

            Dòng tiếp theo có N số nguyên x₁, x₂, …, x_n là các số trong mảng.

Kết quả: In ra một số nguyên là tổng số vòng.

Ví dụ:

Bạn được cung cấp thời gian đến và đi của N khách hàng trong một nhà hàng. Số lượng khách hàng tối đa trong nhà hàng tại bất kỳ thời điểm nào là bao nhiêu?

Dữ liệu vào:

            Dòng đầu tiên có một số nguyên N là số lượng khách hàng (1 ≤ n ≤ 2.10⁵).

            Tiếp theo, có N dòng mô tả các khách hàng. Mỗi dòng chứa hai số nguyên a và b (1 ≤ a < b ≤  10⁹): thời điểm đến và đi của một khách hàng.

            Bạn có thể cho rằng tất cả thời gian đến và đi là khác nhau.

Kết quả: In ra một số nguyên là số lượng khách hàng tối đa.

Ví dụ:

ĐỀ THI HSG TIN HỌC THPT CẤP TỈNH HÀ TĨNH 2022-2023

ĐỀ THI HSG TIN HỌC THPT CẤP TỈNH THANH HÓA 2022-2023

Nhiệm vụ của bạn là chia các số 1, 2, …, n thành hai tập hợp có tổng bằng nhau.

Dữ liệu vào: chứa một số nguyên duy nhất n (1 ≤ n ≤ 10⁶)

Dữ liệu ra: In ra “YES” nếu phép chia có thể thực hiện được, ngược lại in ra “NO”.

            Sau đó, nếu có thể phân chia, hãy in ra một ví dụ về cách tạo các tập hợp. Đầu tiên, in số phần tử trong tập hợp đầu tiên, theo sau là chính các phần tử đó trong một dòng riêng biệt, sau đó, in tập hợp thứ hai theo cách tương tự.

Ví dụ:

Một nhà máy có N máy móc có thể được sử dụng để sản xuất sản phẩm. Mục tiêu của bạn là kiếm được tổng cộng t sản phẩm.

            Đối với mỗi máy, bạn biết được số giây cần thiết để tạo ra một sản phẩm. Các máy có thể hoạt động đồng thời và bạn có thể tự quyết định lịch trình của chúng.

            Thời gian ngắn nhất cần thiết để làm ra t sản phẩm?

Dữ liệu vào:

- Dòng đầu tiên có hai số nguyên N và t (1 ≤ N ≤ 2.10⁵; 1 ≤ t ≤ 10⁹): số lượng máy móc, sản phẩm.

- Dòng tiếp theo có N số nguyên k₁, k₂, …, k_{N (}1 ≤ k_i ≤ 10⁹) thời gian cần thiết để tạo ra một sản phẩm sử dụng mỗi máy.

Dữ liệu ra: In một số nguyên: thời gian tối thiểu cần thiết để thực hiện t sản phẩm.

Ví dụ:

Giải thích: Máy 1 làm được 2 sản phẩm, máy 2 làm được 4 sản phẩm và máy 3 làm được 1 sản phẩm.

Cho dãy A gồm N số nguyên a₁, a₂, ..., a_n (|a_i| ≤ 10⁹). Một đoạn con a[i..j] có độ dài là j-i+1 (1 ≤ i ≤ j ≤ N). Đoạn con được gọi là đoạn xen kẽ nếu hai phần tử bất kỳ nào đứng cạnh nhau đều trái dấu.

            Yêu cầu của bài tập này bạn cần viết chương trình thực hiện nhiệm vụ sau: Với mỗi vị trí i ( 1 ≤ i ≤ N) hãy tính độ dài dãy con xen kẽ dài nhất của dãy A bắt đầu ở vị trí i.

Dữ liệu nhập: 

            - Dòng đầu ghi T là số lượng bộ test ( 1 ≤ T ≤ 20)

            - Trong 2T dòng tiếp theo ghi thông tin về các bộ test: dòng đầu ghi N, dòng hai ghi dãy A

Kết quả:

- Gồm T dòng, mỗi dòng ghi N số nguyên lần lượt là độ dài dãy con xen kẽ dài nhất tìm được tương ứng với mỗi test trong input.

Ràng buộc:

            - 50% test: 1 ≤ N ≤ 1000

            - 50% test: N ≤ 100.000

Ví dụ:

Ở vương quốc NONAME người ta đưa ra một quy tắc đặt tên kỳ lạ: Mỗi dòng họ chọn một dãy ký tự độ dài n chỉ gồm các ký tự in hoa trong bảng chữ cái tiếng Anh. Khi đó để đặt tên cho một người trong dòng họ thì chỉ cần thay đổi thứ tự của các ký tự với nhau.

            Yêu cầu: Cho biết hai xâu tên của hai người trong vương quốc, hãy kiểm tra xem hai người này có cùng dòng họ hay không?

Dữ liệu nhập:

-         Dòng thứ nhất là số nguyên T (1 <= T <= 10) là số trường hợp cần kiểm tra.

-         Các dòng tiếp theo mô tả T trường hợp gồm:

+ Dòng thứ nhất là số nguyên dương n

+ Dòng thứ hai là xâu tên thứ nhất

+ Dòng thứ ba là xâu tên thứ hai

Kết quả: In ra t dòng là kết quả kiểm tra cho T trường hợp. Nếu cùng dòng họ thì in 1 còn không ghi 0.

Ví dụ: