//
you're reading...
Bài tập huấn luyện, Dùng cho thi học sinh giỏi

ĐỀ THI OLYMPIC 30/4 LẦN THỨ XXII NĂM 2016 – MÔN TIN HỌC – KHỐI 11


Đề bài


Bài 1:  Robot táo:

Một  nhà  máy  chế  biến  hoa  quả  đang  chế  biến  một sản phẩm từ táo. Nhà máy này đã có một dây chuyền sản xuất gồm nhiều công đoạn. Trong công đoạn đầu tiên, có N quả táo với trọng lượng đã biết  được đưa ngẫu nhiên lên băng chuyền thành hàng dọc và được đánh số từ 1 đến N. Chúng được ngầm phân thành M  =  [N/K]  đoạn, mỗi đoạn gồm đúng K quả (N là bội của K). Các đoạn này cũng được đánh số từ 1 đến  M, kể  từ  đầu băng chuyền. Do yêu cầu kỹ thuật, chúng cần được sắp xếp lại sao cho:
  • Đoạn 1 sẽ gồm  K quả có trọng lượng lớn nhất trong số các quả có mặt trên băng chuyền.
  • Nếu  M  > 1 thì đoạn thứ  i  (i   = 2,…,M) sẽ  là  K  quả  táo lớn nhất trong số các quả còn lại (không có mặt trong  các đoạn từ 1 đến  i – 1).

 

Một robot sẽ di chuyển dọc theo băng chuyền để  thực hiện yêu cầu kỹ thuật nói trên. Mỗi thao tác
của robot  sẽ  gồm việc rút ra khỏi băng chuyền 1 quả táo (các quả còn lại được dồn lại) rồi chèn quả táo này vào vị  trí thích hợp trên băng chuyền (bao gồm cả vị trí đầu và cuối dãy).
Yêu  cầu :  Hãy viết  chương trình tính xem robot cần thực hiện ít nhất bao nhiêu thao tác để xếp lại số táo trên băng  chuyền  theo đúng  yêu cầu kỹ thuật.
Dữ liệu : Vào từ file  văn bản  APROBOT.INP  gồm:
  •  Dòng đầu gồm hai số nguyên  N và  K (1  ≤  K  ≤  N  ≤  5000);
  •  Dòng thứ  hai ghi N số nguyên Wi  (1 ≤  Wi  ≤ 1000,  i   = 1, 2,…,  N) là số đơn vị trọng lượng của quả  táo  i

.Các số trên cùng mỗi hàng đều được ghi cách nhau bởi ít nhất một dấu cách.

Kết  quả:  Ghi  ra  file  văn  bản  APROBOT.OUT  duy nhất một số nguyên,  là số thao tác ít nhất  mà robot cần thực hiện .
Ràng buộc:  50% số test ứng với  50% số điểm  của bài có  N ≤ 100

Bài 2: Du thám:

Bear  là  một  nhà  du  thám  (du  lịch  và  thám  hiểm)  nổi  tiếng  với  khả  năng  di  chuyển  và  trải nghiệm  trong  những  điều  kiện  vô  cùng  khắc  nghiệt.  Trong  chuyến  du  thám  mới  sắp  tới,  anh sẽ  đến với  một  quần  đảo  ở  vùng  hẻo  lánh  của  biển  Nam  Thái  Bình  Dương.  Quần  đảo  này gồm  N  đảo (các đảo được đánh số từ 1 đến  N). Việc đi lại giữa  N  đảo này được đáp ứng bởi  M tuyến phà (mỗi tuyến phà đáp ứng nhu cầu đi lại giữa hai đảo cố định nào đó), đủ đảm bảo để từ mỗi đảo có thể đến được đảo bất kỳ khác bằng cách trực tiếp hoặc thông  qua các tuyến  phà trung  gian. Sau  khi  có  được  những  thông tin  cần thiết, Bear đặt ra nhiệm vụ như sau cho chuyến du thám: chọn  ra  N- 1 trong số  M  tuyến phà đó để thực hiện hành trình đến với  N  đảo, mỗi đảo ít nhất một lần, sao  cho  tổng  thời  gian  thực  hiện  (đơn  vị  tính  là  phút)  là  nhỏ  nhất.  Bear  sẽ  đổ  bộ xuống đảo  1, thực hiện  hành  trình,  quay  về  đảo  1  rồi  thoát  khỏi bằng máy bay để kết thúc chuyến du thám. Bear biết rõ rằng  để  hoàn  thành  nhiệm  vụ đặt ra, hành trình sẽ có thể phải lặp lại nhiều hơn một lần đối với một số đảo cũng  như tuyến  phà. Các thông  tin  mà Bear có được bao gồm:
  • M tuyến  phà với  thời  gian  di chuyển  tương ứng bởi tuyến  đó;
  • Thời  gian  mà Bear cần để thoát ra khỏi mỗi  đảo kể từ lúc đặt chân đến.

 

Yêu  cầu:  Hãy  tính  xem  trong  chuyến  du  thám  của  mình,  Bear  có  thể  hoàn  thành  nhiệm vụ đặt ra với
tổng thời  gian  nhỏ nhất  là bao nhiêu.
Dữ liệu: Vào từ file  văn bản BEAR.INP có cấu trúc:
  • Dòng  đầu ghi  hai  số nguyên  N và  M (5 ≤ N ≤ 10000, N < M ≤ 100000);
  • Dòng thứ hai   ghi N số nguyên  S1, S2,…, SN cho biết:  Si  là  số đơn vị   thời gian tối thiểu để Bear thoát ra khỏi  đảo i  (1 ≤ Si ≤ 1000,  i  = 1, 2,…, N);
  • Mỗi  một  trong  M  dòng  tiếp  theo  ghi  thông  tin  về  một tuyến phà, gồm ba số nguyên  u, v  và  T (1  ≤  u,  v   ≤  N,  1  ≤  T  ≤  1000)  với  ý nghĩa:  T  là  số đơn vị   thời gian di chuyển theo tuyến phà giữa các đảo u và  v .

 

Lưu ý: nói riêng tại đảo 1, mỗi lần thâm nhập đảo này, Bear cũng đều cần thời gian tối thiểu S1 để mới thoát ra khỏi nó.
Kết quả:  Ghi  ra file  văn bản BEAR.OUT  duy nhất một  số nguyên,  là tổng  thời  gian  nhỏ nhất mà Bear có thể cần để hoàn thành  nhiệm  vụ.
Ràng buộc:  50% số test ứng với  50% số điểm  của bài có  N ≤ 1000.

Bài 3. UAV thông minh:

Một  cuộc đua dành cho các máy bay không người lái thông minh (UAV cỡ nhỏ) được tổ chức trên một đường băng dài gồm  N  vạch cách đều nhau, vạch cách vạch 10 mét. Các vạch được đánh số từ 1 đến  N.  Trên  mỗi  vạch  đều  có  đặt  một  bộ   cảm  biến  có  nhiệm  vụ  gửi  về  Trung  tâm  điều khiển (TTĐK)  của  Ban  tổ  chức  cuộc  thi  (BTC)  số  hiệu  của  vạch  khi UAV đứng hay hạ cánh tại vạch này. Cuộc  đua  cho  mỗi  UAV được tiến hành như sau:  UAV vào đứng tại vạch 1, có thời gian một giây để nạp dữ liệu mà BTC cung cấp. Dữ liệu gồm một số nguyên dương  L  và  N  số nguyên  Xi  (i  = 1,…,  N) với  ý  nghĩa:  Xi  là giá trị của vạch  i . Ngay sau đó, UAV phải thực hiện hành trình bằng cách liên tục di chuyển  như sau:
  • Trong  hành  trình  lượt  đi,  UAV  (đứng  tại  vạch  1)  cần  bay  đến được vạch  N  theo quy tắc: nếu đang đứng tại vạch  i   (1 ≤  i   <  N) thì nó sẽ chỉ được phép hạ cánh tại vạch  j   (j   >  i ) mà  Xj  lẻ (ấn định  rằng  XN=1001)  đồng  thời  vạch  j   cách  vạch  i   không  quá  L  vạch (tức là, 1 ≤  j  –  i ≤ L). Tổng  số  lần  UAV  đứng  hay  hạ  cánh  trong  hành  trình  lượt  đi,  bao  gồm  cả  tại vạch 1 và vạch N, được ký hiệu  bởi  U.
  • Trong  hành  trình  lượt  về,  bắt  đầu  với số điểm được BTC cung cấp bằng  XN= 1001, UAV từ vạch  N  bay tiếp về vạch 1 theo quy tắc: Nếu đang đứng ở vạch i (1 < i ≤  N) thì nó sẽ chỉ được phép hạ cánh tại vạch  k  (k   <  i ) mà  Xk  chẵn (ấn định rằng  X1= 1000). UAV sẽ nhận được thêm Xk  điểm nếu vạch k cách vạch i đúng  L  vạch (tức là,  i   –   k   =  L) và bị trừ  Xk  điểm trong trường hợp trái  lại.  Tổng  số điểm  mà UAV thu  được trong  hành  trình  lượt về , được ký hiệu  bởi  V.

 

Lưu ý:
  • Các  UAV   được  lập  trình  sẵn  để  tiếp  nhận  và  xử  lý  dữ  liệu  của  BTC  rồi  tự  động  thực  hiện toàn bộ hành  trình  (lượt đi và về).
  • Dữ liệu  mà BTC  đưa ra luôn  đảm bảo để các UAV có thể thực hiện  được cuộc đua.

 

Yêu cầu:  Hãy lập trình  cho UAV để nó đạt được giá  trị nhỏ nhất của  U và lớn  nhất  của  V.
Dữ liệu: Vào từ file  văn bản UAV.INP có cấu trúc:
  • Dòng  đầu ghi  số nguyên  L (10 ≤ L ≤ 100).
  • Dòng  thứ hai ghi  số nguyên  N (L < N ≤ 500000).
  • Dòng thứ ba ghi lần lượt các số nguyên  X2,…,  XN-1 (0  ≤  Xi  ≤ 106,  i   = 2,…,  N-1). Các số cách nhau  bởi dấu   cách.

 

Kết quả:  Ghi  ra file  văn bản UAV.OUT  2 số nguyên  trên 2 dòng:  dòng đầu là số U, dòng sau là số V.
Ràng buộc:  50% số test ứng với  50% số điểm  của bài có  N ≤ 1000.
File PDF: Tại đây

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: