KIỂM TRA THƯỜNG XUYÊN

# KIỂM TRA THƯỜNG XUYÊN ## BÀI KIỂM TRA SỐ 1 ### TỔNG QUAN VỀ BÀI THI | | Tên tệp chương trình | File dữ liệu vào | File dữ liệu ra | Điểm | | - | - | - | - | - | | Câu 1 | GOQUY.\* | GOQUY.INP | GOQUY.OUT | 7,0 | | Câu 2 | LOINHUAN.\* | LOINHUAN.INP | LOINHUAN.OUT | 7,0 | | Câu 3 | GIAOTHONG.\* | GIAOTHONG.INP | GIAOTHONG.OUT | 6,0 | Dấu \* là đại diện cho phẩn mở rộng, được thay thế bằng `PAS`, `PY` hoặc `CPP` tùy theo ngôn ngữ lập trình được sử dụng là Pascal, Python hay C++ ### Bài 1: GỖ QUÝ :::info Ở một ngôi làng nọ, trên một con đường (được xem như một đường thẳng), có $n$ cây gỗ quý được đánh số theo thứ tự lần lượt từ $1$ đến $n$, cây thứ $i$ có giá trị khai thác là một số nguyên dương $a_i$. Sau khi tính toán, trưởng làng đã quyết định khai thác các cây gỗ đó. Tuy nhiên, Trưởng làng muốn giữ lại một số cây sau khi khai thác để làm bóng mát cho con đường thỏa mãn điều kiện không được khai thác hai cây liên tiếp nhau. ::: **Yêu cầu**: Hãy cho biết tổng giá trị lớn nhất mà Trưởng làng có thể khai thác được. **Dữ liệu vào**: Vào từ file văn bản **`GOQUY.INP`** có nội dung: - Dòng thứ nhất chứa số nguyên dương $N$ $(N \leq 10^5)$. - Trong $N$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên dương $a_i$ $(a_i \leq 10^9)$. **Kết quả**: Ghi ra file văn bản **`GOQUY.OUT`** một số duy nhất là tổng giá trị lớn nhất mả Trưởng làng có thể khai thác được. **Ví dụ**: | GOQUY.INP | GOQUY.OUT | | - | - | | 4 6 2 1 5 | 11 | ### Bài 2: LỢI NHUẬN :::info Theo quy định, nhân viên kế toán của công ty ABC phải kết toán sổ sách vào cuối mỗi ngày rồi báo cáo cho giám đốc công ty số tiền lợi nhuận của công ty trong ngày ấy. Sau $N$ ngày kinh doanh (đánh số từ ngày $1$ đến ngày thứ $N$), báo cáo mà kế toán gửi cho giám đốc công ty là một dãy số gồm $N$ số nguyên $a_1,\ a_2, ...,\ a_N$. Trong đó $a_i$ là lợi nhuận của công ty ở ngày thứ $i$ ($a_i > 0$ có nghĩa là ngày thứ $i$ kinh doanh có lãi, $a_i < 0$ là ngày thứ $i$ kinh doanh bị thua lỗ, còn $a_i = 0$ là ngày thứ $i$ kinh doanh không có lãi mà cũng không bị lỗ). Để định hướng chiến lược kinh doanh trong thời gian tới, với kết quả lợi nhuận trong $N$ ngày qua do kế toán báo cáo, giám đốc công ty muốn tìm dãy con dài nhất gồm các ngày liên tiếp nhau mà tổng lợi nhuận của các ngày ấy bằng $0$. ::: **Yêu cầu**: Bạn hãy lập trình tìm câu trả lời cho giám đốc công ty ABC. **Dữ liệu**: Vào từ file văn bản **`LOINHUAN.INP`** có nội dung: - Dòng đầu tiên chứa số nguyên dương $N$ $(1 \leq N \leq 10^5)$ là số ngày kế toán báo cáo cho giám đốc; - Dòng thứ hai là dãy số nguyên $a_1,\ a_2, ...,\ a_N$ $(|a_i| \leq 10^4)$. Các số trên cùng dòng được ghi cách nhau bởi dấu cách. **Kết quả**: Ghi ra file văn bản **`LOINHUAN.OUT`** một số duy nhất là độ dài dãy con dài nhất tìm được thỏa yêu cầu. Nếu không tìm được dãy con nào thì ghi $-1$. **Ví dụ**: | LOINHUAN.INP | LOINHUAN.OUT | | - | - | | 6 0 1 -2 7 -5 5 | 3 | | 2 4 6 | -1 | *Giải thích*: - Trong ví dụ 1, có $3$ dãy con có tổng lợi nhuận bằng $0$, đó là: - Dãy chỉ gồm 1 phần tử $a_1$ → dãy $0$ - Dãy gồm 2 phần tử $a_5,\ a_6$ → dãy $-5,\ 5$ - Dãy gồm 3 phần tử $a_3,\ a_4,\ a_5$ → dãy $-2,\ 7,\ -5$ $\Rightarrow$ Độ dài dãy con dài nhất thỏa yêu cầu là $3$. - Trong ví dụ 2, không tìm được dãy con nào có tổng lợi nhuận bằng $0$ $\Rightarrow$ đáp số bằng $-1$. **Ràng buộc**: - Có 30% số test ứng với 30% số điểm của bài có $N \leq 100$. - Có 40% số test khác ứng với 40% số điểm của bài có $N \leq 10^3$. - Có 30% số test còn lại ứng với 30% số điểm còn lại của bài có $N \leq 10^5$. ### Bài 3: HỆ THỐNG GIAO THÔNG :::info Thành phố NEW là một thành phố mới, đang lập kế hoạch xây dựng hệ thống giao thông hiện đại cho thành phố. Theo kế hoạch, mạng lưới giao thông của thành phố sẽ có $N$ nút giao thông được đánh số từ $1$ tới $N$. Ban quản lý giao thông đã lập ra một danh sách gồm $M$ tuyến đường hai chiều có thể xây dựng được giữa hai nút giao thông nào đó. Mỗi tuyến đường có một thời gian hoàn thành khác nhau. Các tuyến đường phải được xây dựng sao cho $N$ nút giao thông là liên thông với nhau. Nói cách khác, giữa hai nút bất kỳ cần phải di chuyển được đến nhau qua một số tuyến đường. Ban quản lý giao thông sẽ chọn ra một số tuyến đường từ trong danh sách gồm $M$ tuyến đường ban đầu để đưa vào xây dựng sao cho điều kiện này được thỏa mãn. Do nhu cầu cấp bách, Ban quản lý giao thông sẽ thuê hẳn một đội thi công riêng cho mỗi tuyến đường cần xây dựng. Do đó, thời gian để hoàn thành toàn bộ các tuyến đường cần xây dựng sẽ bằng thời gian lâu nhất hoàn thành một tuyến đường nào đó. ::: **Yêu cầu**: Giúp Ban quản lý giao thông tính thời gian hoàn thành các tuyến đường sớm nhất thỏa yêu cầu đã nêu. **Dữ liệu**: Vào từ file văn bản **`GIAOTHONG.INP`** gồm nhiều dòng: - Dòng đầu tiên chứa số hai số nguyên dương $N$ và $M$ $(1 \leq N \leq 10^3;\ 1 \leq M \leq 10^4)$. - $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$, $v$ và $t$ cho biết có thể xây dựng tuyến đường nối giữa nút $u$ và nút $v$ trong thời gian $t$ $(1 \leq t \leq 10^6)$. Không có hai tuyến đường nào nối cùng một cặp nút giao thông. Các số trên cùng dòng cách nhau ít nhất một dấu cách. **Kết quả**: Ghi ra file văn bản **`GIAOTHONG.OUT`** một số nguyên duy nhất là thời gian sớm nhất hoàn thành các tuyến đường thỏa mãn yêu cầu đặt ra. **Ví dụ**: | GIAOTHONG.INP | GIAOTHONG.OUT | | - | - | | 5 7 1 2 2 1 5 1 2 5 1 1 4 3 1 3 2 5 3 2 3 4 4 | 3 | **Ràng buộc**: - 50% số test ứng với 50% số điểm của bài có $1 \leq N \leq 100;\ 1 \leq M \leq 100$; - 50% số test ứng với 50% số điểm của bài có $100 < N \leq 10^3;\ 100 < M \leq 10^4$. ---