H
honghiaduong
[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.
THANH GỖ
Cha của Pinocchio muốn làm lại cho Picochio một cái mũi mới. Ông có N thanh gỗ, thanh gỗ i có độ dài ai. Là người yêu thích toán học ông ta đưa ra một giải thuật sau để lấy ra thanh gỗ có độ dài cần thiết:
- Nếu còn lại 1 thanh gỗ thì ông ta sẽ lấy thanh gỗ này làm mũi cho Pinocchio.
- Nếu còn nhiều hơn một thanh gỗ thì ông ta sẽ làm như sau:
Bước 1: Chọn ra thanh gỗ i có độ dài ai nhỏ nhất, tiếp theo chọn thanh gỗ j có độ dài aj nhỏ nhất trong các thanh còn lại.
Bước 2: Nếu ai = aj thì vứt bỏ bớt một thanh, quay về Bước 1.
Bước 3: Nếu ai < aj thì ra sẽ cắt khỏi thanh aj đi một đoạn bằng ai, quay lại Bước 1.
Yêu cầu: Hãy tính độ dài thanh gỗ mà ông ta nhận được để làm mũi cho Pinocchio.
Giới hạn: 1<=N <=10.000; 1<=ai<=109.
Dữ liệu: Vào từ file văn bản THANHGO.INP: Dòng đầu tiên là số N, dòng sau là N số a1, a2, …., an.
Kết quả: Ghi ra file văn bản THANHGO.OUT: Số X là độ dài thanh gỗ tìm được.
(Các số trên cùng một dòng của file dữ liệu vào cách nhau ít nhất một ký tự trống)
Ví dụ
THANHGO.INP
THANHGO.OUT
3
2 3 4
1
Cha của Pinocchio muốn làm lại cho Picochio một cái mũi mới. Ông có N thanh gỗ, thanh gỗ i có độ dài ai. Là người yêu thích toán học ông ta đưa ra một giải thuật sau để lấy ra thanh gỗ có độ dài cần thiết:
- Nếu còn lại 1 thanh gỗ thì ông ta sẽ lấy thanh gỗ này làm mũi cho Pinocchio.
- Nếu còn nhiều hơn một thanh gỗ thì ông ta sẽ làm như sau:
Bước 1: Chọn ra thanh gỗ i có độ dài ai nhỏ nhất, tiếp theo chọn thanh gỗ j có độ dài aj nhỏ nhất trong các thanh còn lại.
Bước 2: Nếu ai = aj thì vứt bỏ bớt một thanh, quay về Bước 1.
Bước 3: Nếu ai < aj thì ra sẽ cắt khỏi thanh aj đi một đoạn bằng ai, quay lại Bước 1.
Yêu cầu: Hãy tính độ dài thanh gỗ mà ông ta nhận được để làm mũi cho Pinocchio.
Giới hạn: 1<=N <=10.000; 1<=ai<=109.
Dữ liệu: Vào từ file văn bản THANHGO.INP: Dòng đầu tiên là số N, dòng sau là N số a1, a2, …., an.
Kết quả: Ghi ra file văn bản THANHGO.OUT: Số X là độ dài thanh gỗ tìm được.
(Các số trên cùng một dòng của file dữ liệu vào cách nhau ít nhất một ký tự trống)
Ví dụ
THANHGO.INP
THANHGO.OUT
3
2 3 4
1