Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Vietnamese Olympiad in Informatics

Điểm tin VOJ

Số thành viên:6831
Số bài tập:1035
Số bài nộp:913743
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
[VOJ] Bài tập NOIXICH
    
Thông tin
Mã bài:NOIXICH    
Tên bài:Nối Xích
Loại bài:oi
Người đóng góp:soncbg
Giới hạn thời gian:1s
Giới hạn mã nguồn:50000B
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL JS NODEJS PERL 6
Nguồn:Sưu Tầm
Ngày:11-06-2008
Đề bài
Cập nhật: 11h17 ngày 14-09-2014

Người ta có N đoạn dây xích(N <= 20000), mỗi đoạn dây xích là chuỗi các mắt xích được nối với nhau. Các đoạn dây xích này tách rời nhau. Mỗi đoạn mắt xích có không quá 20000 mắt xích. Bằng cách cắt ra một mắt xích, sau đó hàn lại, ta có thể nối hai dây xích thành một đoạn. Thời gian để cắt và hàn mỗi mắt xích là 1 đơn vị thời gian và được xem là bằng nhau với mọi mắt xích. Nhiêm vụ của bạn là phải nối chúng lại thành một đoạn dây xích duy nhất với thời gian ít nhất( hay số mắt xích bị cắt và hàn lại là ít nhất).

Input

Dữ liệu vào cho trong file văn bản có cấu trúc như sau: Dòng đầu tiên là số N, số đoạn xích. Những dòng tiếp theo ghi N số nguyên dương, số thứ i là số mắt xích có trong đoạn xích thứ i(i <= i <= N) Hai số cạnh nhau trên cùng một dòng cách nhau ít nhất một dấu cách.

Output

Một dòng duy nhất là số đơn vị thời gian mà bạn cần để nối N đoạn xích đã cho.

Example

Input:
3
2 3
4

Output:
2
Thông tin
Mã bài:NOIXICH  
Tên bài:Nối Xích
Loại bài:oi
Giá trị:0.1
Số người giải được / đã làm:686 / 865
Bảng xếp hạng
Danh sách bài nộp
Bài nộp
Số bài nộp:3287
Đạt yêu cầu (AC):950
Đúng một phần (PT):1177
Sai kết quả (WA):926
Lỗi biên dịch (CE):232
Chạy bị lỗi (RE):2
Ngôn ngữ dùng nhiều nhất
Pascal:2808
C/C++:435
ADA:38
Brainf**k:4
Bash:1
Ngôn ngữ khác:1