P
phithang_tin
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
giúp mình làm 2 bài này bằng phương pháp QHĐ
Dãy con xen kẽ
Cho dãy số nguyên a1, a2, ..., aN. Mỗi số hạng của dãy này thuộc một trong hai loại khác nhau. Xét tất cả các dãy con của dãy đã cho có tính chất: hai số hạng liên tiếp của dãy con không thuộc cùng một loại. Mỗi dãy con như vậy, được gọi là một dãy con xen kẽ.
Yêu cầu: Tìm giá trị lớn nhất của tổng các số hạng của dãy con xen kẽ.
Dữ liệu: Đọc từ file văn bản XENKE.INP có:
• Dòng đầu chứa số nguyên N (1 ≤ N ≤ 106),
• Dòng thứ i trong N dòng tiếp theo chứa hai số nguyên: ai và li (|ai| ≤ 104, li {1, 2}, trong đó li là loại của ai.
Kết quả: Ghi ra file văn bản XENKE.OUT một số nguyên, là tổng lớn nhất tìm được.
Ví dụ:
XENKE.INP
10
-2 2
-1 1
5 2
1 2
-4 1
5 2
-6 1
-3 1
2 2
4 2
XENKE.OUT
7
bài 2:
Vòng quanh thế giới (Thi chọn HSGQG - Năm học 2000-2001)
Trên tuyến đường của xe chở khách du lịch vòng quanh thế giới xuất phát từ bến xe X, có N khách sạn, được đánh số từ 1 đến N theo thứ tự xuất hiện trên tuyến đường, trong đó khách sạn N là địa điểm cuối cùng của tuyến đường mà tại đó xe bắt buộc phải dừng. Khách sạn i cách điểm xuất phát ai km (i = 1, 2 ,..., N): a1 < a2 < ... < aN.
Để đảm bảo sức khỏe cho hành khách, theo tính toán của các nhà chuyên môn, sau khi đã chạy được P km, xe nên dừng lại nghỉ tại khách sạn. Vì thế, nếu xe dừng lại cho khách nghỉ ở khách sạn sau khi đã đi được Q km thì lái xe phải trả một lượng phạt là (Q-P)2.
Ví dụ: Với N=4, P=300, a1=250, a2=310, a3=550, a4=590. Xe bắt buộc phải nghỉ tại khách sạn 4 là địa điểm cuối cùng của hành trình. Nếu lái xe chỉ dừng lại tại khách sạn thứ 2 thì lượng phạt sẽ là: (310-300)2 + ((590-310)-300)2 = 500.
Yêu cầu: Hãy xác định các vị trí (khách sạn) mà xe phải dừng để tổng lượng phạt mà lái xe phải trả là nhỏ nhất.
Dữ liệu: Vào từ file văn bản TRAVEL.INP mà:
- Dòng đầu chứa số nguyên dương N ( N 10000)
- Dòng thứ hai chứa số nguyên dương P (P 500)
- Dòng thứ ba chứa các số nguyên dương a1, a2, ..., aN (các số này cách nhau bởi dấu cách), ai 2000000, i = 1, 2, ... , N.
Kết quả: Ghi ra file văn bản TRAVEL.OUT mà:
- Dòng đầu là số Z – lượng phạt mà lái xe phải trả.
- Dòng thứ hai ghi số K – số khách sạn mà lái xe phải dừng để nghỉ.
- Dòng thứ ba ghi K số, là số hiệu các khách sạn mà xe dừng (nhất thiết có cả số hiệu của khách sạn cuối cùng).
Ví dụ:
TRAVEL.INP
4
300
250 310 550 590
TRAVEL.OUT
500
2
2 4
Dãy con xen kẽ
Cho dãy số nguyên a1, a2, ..., aN. Mỗi số hạng của dãy này thuộc một trong hai loại khác nhau. Xét tất cả các dãy con của dãy đã cho có tính chất: hai số hạng liên tiếp của dãy con không thuộc cùng một loại. Mỗi dãy con như vậy, được gọi là một dãy con xen kẽ.
Yêu cầu: Tìm giá trị lớn nhất của tổng các số hạng của dãy con xen kẽ.
Dữ liệu: Đọc từ file văn bản XENKE.INP có:
• Dòng đầu chứa số nguyên N (1 ≤ N ≤ 106),
• Dòng thứ i trong N dòng tiếp theo chứa hai số nguyên: ai và li (|ai| ≤ 104, li {1, 2}, trong đó li là loại của ai.
Kết quả: Ghi ra file văn bản XENKE.OUT một số nguyên, là tổng lớn nhất tìm được.
Ví dụ:
XENKE.INP
10
-2 2
-1 1
5 2
1 2
-4 1
5 2
-6 1
-3 1
2 2
4 2
XENKE.OUT
7
bài 2:
Vòng quanh thế giới (Thi chọn HSGQG - Năm học 2000-2001)
Trên tuyến đường của xe chở khách du lịch vòng quanh thế giới xuất phát từ bến xe X, có N khách sạn, được đánh số từ 1 đến N theo thứ tự xuất hiện trên tuyến đường, trong đó khách sạn N là địa điểm cuối cùng của tuyến đường mà tại đó xe bắt buộc phải dừng. Khách sạn i cách điểm xuất phát ai km (i = 1, 2 ,..., N): a1 < a2 < ... < aN.
Để đảm bảo sức khỏe cho hành khách, theo tính toán của các nhà chuyên môn, sau khi đã chạy được P km, xe nên dừng lại nghỉ tại khách sạn. Vì thế, nếu xe dừng lại cho khách nghỉ ở khách sạn sau khi đã đi được Q km thì lái xe phải trả một lượng phạt là (Q-P)2.
Ví dụ: Với N=4, P=300, a1=250, a2=310, a3=550, a4=590. Xe bắt buộc phải nghỉ tại khách sạn 4 là địa điểm cuối cùng của hành trình. Nếu lái xe chỉ dừng lại tại khách sạn thứ 2 thì lượng phạt sẽ là: (310-300)2 + ((590-310)-300)2 = 500.
Yêu cầu: Hãy xác định các vị trí (khách sạn) mà xe phải dừng để tổng lượng phạt mà lái xe phải trả là nhỏ nhất.
Dữ liệu: Vào từ file văn bản TRAVEL.INP mà:
- Dòng đầu chứa số nguyên dương N ( N 10000)
- Dòng thứ hai chứa số nguyên dương P (P 500)
- Dòng thứ ba chứa các số nguyên dương a1, a2, ..., aN (các số này cách nhau bởi dấu cách), ai 2000000, i = 1, 2, ... , N.
Kết quả: Ghi ra file văn bản TRAVEL.OUT mà:
- Dòng đầu là số Z – lượng phạt mà lái xe phải trả.
- Dòng thứ hai ghi số K – số khách sạn mà lái xe phải dừng để nghỉ.
- Dòng thứ ba ghi K số, là số hiệu các khách sạn mà xe dừng (nhất thiết có cả số hiệu của khách sạn cuối cùng).
Ví dụ:
TRAVEL.INP
4
300
250 310 550 590
TRAVEL.OUT
500
2
2 4