NGÀY HỘI

Nguồn: Đề thi chọn đội tuyển học sinh giỏi tỉnh Khánh Hòa ngày 04/04/2017

Hành tinh Hough xa xôi được chia thành 2 nửa bán cầu có trình độ khoa học kỹ thuật khác hẳn nhau. Ở Hough A, ngành khoa học máy tính và tự động hóa phát triển mãnh mẽ, mọi công việc của họ đều được thực hiện một cách tự động. Trái ngược với Hough A, ở Hough B trình độ của họ vẫn đang ở mức thời kỳ đồ sắt bởi lẽ họ đề cao lao động chân tay.

Mặc dù trình độ khoa học kỹ thuật ở hai bán cầu rất khác nhau nhưng họ vẫn chung sống hòa bình với nhau từ thế kỷ này qua thế kỷ khác. Hằng năm họ còn tổ chức một cuộc thi lớn dành cho tất cả người dân trên hành tinh. Ở Hough A có n người tham dự còn Hough B có m người tham dự. Nhờ chương trình đo sức khỏe nên Hough A biết trước được chỉ số sức khỏe của tất cả người dân trên hành tinh. Trong cuộc thi, mỗi lượt sẽ có 2 người ở hai bán cầu lên thi đấu, người có chỉ số sức khỏe tốt hơn sẽ dành chiến thắng, mỗi người chỉ được thi đấu tối đa một lần.

Yêu cầu: Hãy cho biết mỗi người tham dự Hough B có chỉ số sức khỏe lớn hơn bao nhiêu người tham dự của Hough A.

Dữ liệu vào: Từ tệp văn bản HOUGH.INP gồm:

+ Dòng đầu tiên ghi 2 số nguyên dương n và m

+ Dòng thứ 2 ghi n số nguyên dương a₁, a₂,…, a_n cho biết chỉ số sức khỏe của n người tham dự cuộc thi ở Hough A.

+ Dòng thứ 3 ghi m số nguyên dương b₁, b₂,…, b_m cho biết chỉ số sức khỏe của m người tham dự cuộc thi ở Hough B.

Kết quả: Ghi vào tệp văn bản HOUGH.OUT gồm m dòng, dòng thứ i cho biết người thứ i ở Hough B có chỉ số sức khỏe nhiều hơn bao nhiêu người ở Hough A.

Ví dụ:

HOUGH.INP	HOUGH.OUT
3 4 1 4 3 4 5 3 3	2 3 1 1

Gới hạn: Trong tất cả các test các số nguyên không vượt quá 10⁹

+ Có 50% số test tương ứng với 50% số điểm có n, m ≤ 10³

+ 50% số test còn lại tương ứng với 50% số điểm có n, m ≤10⁵

 Test - code - solution - đề (word)

QUÂN HẬU

Xét bàn cờ tổng quát kích thước kx k, các hàng của bàn cờ được đánh số từ 1 tới k từ trên xuống dưới và các cột của bàn cờ được đánh số từ 1 tới k  từ trái qua phải. Ô nằm trên giao của hàng i và cột j được gọi là ô (i, j). Từ bàn cờ ban đầu gồm các ô trống, người ta đặt đúng n quân hậu vào n ô hoàn toàn phân biệt trên bàn cờ.

Ta nói một quân hậu ở ô (x, y) khống chế được ô trống (x^’, y^’) nếu đoạn thẳng nối tâm hai ô đó song song với một trong hai cạnh bàn cờ hoặc song song với một trong hai đường chéo của bàn cờ, đồng thời đoạn thẳng nối tâm của hai ô (x, y) và (x’ , y^’) không đi qua tâm của bất kỳ ô nào chứa quân hậu khác.

Như ví dụ trên, quân hậu ở ô (4, 4) có thể khống chế được 16 ô trống đánh dấu “ü” trong hình.

Yêu cầu: Cho biết kích thước bàn cờ và vị trí n quân hậu, hãy đếm số ô trống bị quân hậu khống chế.

Dữ liệu: Vào từ file văn bản QUEENS.INP

·            Dòng 1 chứa hai số nguyên dương k≤10⁹, n≤10⁵

·            n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương lần lượt là chỉ số hàng và chỉ số cột của quân hậu thứ i

Kết quả: Ghi ra file văn bản QUEENS.OUT n dòng, dòng thứ i ghi số ô trống bị quân hậu thứ i khống chế.

Ví dụ:

QUEENS.INP	QUEENS.OUT
8 7 1 1 1 7 3 4 4 4 4 7 6 2 7 7	14 11 20 16 16 19 15

Test - Code - Đề (word)

ĐÓN XE BUS

Nguồn: http://vn.spoj.com/problems/NKBUS/

Một xe buýt của công ty có nhiệm vụ đón nhân viên đến trụ sở làm việc. Trên hành trình, xe buýt sẽ tiếp nhận nhân viên đứng chờ ở các điểm hẹn nếu như xe còn chỗ trống. Xe buýt có thể đỗ lại để chờ những công nhân chưa kịp đến điểm hẹn.

Cho biết thời điểm mà mỗi nhân viên đến điểm hẹn của mình và thời điểm qua mỗi điểm hẹn của xe buýt. Giả thiết rằng xe buýt đến điểm hẹn đầu tiên tại thời điểm 0 và thời gian xếp khách lên xe được bằng 0.

Xe buýt cần phải chở một số lượng nhiều nhất các nhân viên có thể được đến trụ sở. Hãy xác định khoảng thời gian ngắn nhất để xe buýt thực hiện công việc.

Dữ liệu vào: Từ tệp văn bản NKBUS.INP

+ Dòng đầu tiên chứa 2 số nguyên dương n, m theo thứ tự là số điểm hẹn và số chỗ ngồi của xe buýt

+ Dòng thứ i trong số n dòng tiếp theo chứa số nguyên t_i là thời gian cần thiết để xe buýt di chuyển từ điểm hẹn thứ i đến điểm hẹn thứ i+1 (điểm hẹn thứ n+1 sẽ là trụ sở làm việc của công ty) và số nguyên k là số lượng nhân viên đến điểm hẹn i, tiếp theo k số nguyên là các thời điểm đến điểm hẹn của k nhân viên.

Kết qủa ra: ghi vào tệp văn bản NKBUS.OUT

Gồm một dòng duy nhất, là thời gian ngắn nhất tìm được.

Giới hạn

1 ≤ n ≤ 200000, 1 ≤ m ≤ 20000

Tổng số nhân viên không vượt quá 200000.

Kết quả không vượt quá 2³¹-1.

Ví dụ:

NKBUS.INP	NKBUS.OUT
3 2 3 2 4 3 1 3 6 3 7 5 1 5	10

Giải thích: Trên đường đến công ty có 3 trạm xe buýt. Từ trạm 1 đến trạm 2, trạm 2 đến trạm 3, và từ trạm 3 đến công ty lần lượt mất 3, 1 và 5 đơn vị thời gian. Xe buýt có thể đi như sau: đến thẳng trạm 2, đón người thứ 2, đến trạm 3, chờ 1 đơn vị thời gian để đón người duy nhất ở trạm này, và cuối cùng đến công ty. Tổng cộng xe buýt đi mất 3 + 1 + 1 + 5 = 10 đơn vị thời gian.

SOLUTION - CODE