//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Tách từ

Một từ trong tiếng Việt được cấu tạo nên từ các âm tiết. Khi cho một câu trong tiếng Việt, việc tách các âm tiết thành các từ riêng biệt là một công việc cần thiết nhưng không đơn giản. Chẳng hạn câu: “Ông già đi nhanh quá” có thể được tách thành “/Ông/ già đi /nhanh / quá/” hoặc “Ông già/ đi / nhanh /quá”. Bạn là trợ lý của giáo sư có danh tiếng, công việc của bạn là giúp giáo sư viết một chương trình tách từ. Phần cốt lõi của chương trình là việc mô tả một cấu trúc dữ liệu cho phép thực hiện ba thao tác cơ bản trên 1 dãy n đơn âm cho trước (các đơn âm được đánh số lần lượt từ 1 tới n, theo thứ tự từ trái qua phải). Hai đơn âm cạnh nhau có thể được nối, hoặc không nối với nhau, một từ là một dãy đơn âm liên tiếp (cực đại) nối với nhau. Các thao tác trên cấu trúc dữ liệu bao gồm:

  • J i  j: Nối từ đơn âm thứ i tới đơn âm thứ j với nhau
  • D i  j: Tách các đơn âm từ đơn âm thứ i  tới đơn âm thứ j (i ≤ j )
  • C: Đòi hỏi trả về số lượng từ ( số lượng dãy đơn âm nối nhau)

Chẳng hạn với n = 4 và trạng thái hiện tại của dãy đơn âm đang là ( 1_2 3_4 ) :

  • J 2 3                { Dãy đơn âm sẽ biến đổi thành: 1_2_3_4 }
  • D 2 4               { Dãy đơn âm sẽ biến đổi thành: 1_2  3  4 }
  • C                     { Trả về giá trị: 3 ,  do có ba từ là 1_2, 3 và 4 }

InputWS.INP

  • Dòng đầu ghi số K là số từ trong dãy ban đầu và số M là số lượng thao tác.
  • Dòng tiếp theo ghi K số nguyên dương lần lượt là độ dài của các từ tính từ trái qua phải
  • M dòng tiếp theo mỗi dòng bắt đầu bằng 1 chữ cái (J/D/C). Trong trường hợp chữ cái bắt đầu là J hoặc D tiếp theo ghi số hiệu từ mà thao tác cần thực hiện.

Output:            WS.OUT

  • Ứng với mỗi thao tác C trong input, ghi ra 1 số trên 1 dòng trong file output là số lượng từ tại thời điểm tương ứng.

Giới hạn:

  • Số đơn âm không quá 50 000.
  • M ≤ 100 000
  • Thời gian: 2 s/test
  • Bộ nhớ: 16MB

Ví dụ:

WS.INP WS.OUT
2 3

2 2

J 2 3

D 2 4

C

3

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ả

Danh mục

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Market Maze

Footsteps

Mercurial

More Photos

Thống kê

  • 95,638 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: