//
you're reading...
00 - Chủ đề chung, Bài tập huấn luyện, Giáo trình chuyên Tin học 10

Bài tập huấn luyện: Nối xích


Đề bài -Tài liệu Chuyên Tin Quyển 1


Có N đoạn xích (N<20000), mỗi đoạn xích là mỗi xâu mắt xích nối nhau. Các đoạn tách rời nhau, mỗi đoạn có không quá 20000 mắt xích.

Bắng cách cắt ra 1 mắt xích, hàn lại ta có thể nối 2 mắtt xích thành đoạn. Thời gian để cắt – nối xem như  là như nhau với mọi mắt xích.

Nhiệm vụ: nối tất cả các đoạn thành 1 đoạn với time là ít nhất (hay số mắt xích bị cắt nối là ít nhất)

INPUT: file xich.inp 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 theoo ghi N số nguyên dương, sô thứ i là số mắt xích có trong đoạn thứ i (1=< i =< N). Hai số cạnh nhau trên 1 dòng cách nhau ít nhất 1 dấu cách.

OUTPUT:  file xich.out chứa 1 số duy nhất là đơn vị thời gian thực hiện.

Ví dụ

xich.inp xich.out
3 2
4 7 6

 

xich.inp xich.out
5 3
3 5 7 8 9

 


Hướng dẫn


Thuật toán:

  • Sắp xếp số đoạn xích tăng dần.
  • Luôn xử lý các đoạn xích có độ dài bằng 1 theo cách chặt ra rồi đem đi nối 2 đoạn xích khác.
  • Xử lý chặt từ đoạn xích ngắn nhất, tăng dần khi không còn đoạn xích ngắn hơn. Chặt các đoạn xích ngắn (có độ dài lớn hơn 1) theo cách chặt dần mắt xích của nó đem đi nối các đoạn xích khác, cho tới khi nó có độ dài là
  • Việc chặt-hàn dừng lại khi số đoạn xích chỉ còn 1.

[Chương trình mẫu]

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: