SƠN TƯỜNG

Nguồn: kc97blf

Xuân sang hè đến thu về

Đông qua cũng đủ làm tê tái lòng

Mùa đông lạnh giá đã làm tróc đi lớp sơn phủ tường phía sau khách sạn nơi đội tuyển đang ở. Là một người có mắt thẩm mỹ cao, không thể cam tâm đứng nhìn từng lớp sơn rơi rụng như vậy, thầy Hùng quyết định dành một ngày để sơn lại nó, với sự trợ giúp của hết sức đắc lực của Phát. Là một người có tài năng thiên bẩm về hội họa, nhưng ở phương diện nghe hiểu thì hầu như bất lực nên Phát không làm theo đúng sự hướng dẫn của thầy Hùng.

Nếu ta coi bức tường nằm trên trục số thì khoảng tường khách sạn mà thầy Hùng muốn sơn bắt đầu từ điểm a và kết thúc tại điểm b. Ví dụ với a=3 và b=5 thì thầy Hùng muốn sơn một đoạn tường dài 2 đơn vị. Nhưng Phát hiểu sai ý của thầy Hùng nên cậu sơn lại từ điểm c đến điểm d. Có thể một đoạn tường Phát sơn lại trùng với đoạn tường đã được thầy Tùng sơn trước đó.

Hãy xác định xem độ dài đoạn tường mà Phát và thầy Hùng đã sơn.

Dữ liệu vào: File FPAINTING.INP gồm hai dòng:

+ Dòng đầu tiên ghi hai số a và b (a

+ Dòng thứ 2 ghi 2 số c và d. (c

+ Tất cả các số đều nằm trong đoạn [0..100]

Dữ liệu ra: File FPAINTING.OUT một số là kết quả bài toán.

Ví dụ:

FPAINTING.INP	FPAINTING.OUT
7 10 4 8	6

Test

TRÒ CHƠI LAWRENCE

Nguồn: kc97blf
Trong lúc rảnh rỗi, Nguyên đã làm được một trò chơi là Lawrence. Trò chơi này gồm n trạm, các trạm được đánh số từ 1 đến n. Mỗi trạm được gán một giá trị gọi là giá trị chiến thuật. Các trạm được nối với nhau bởi n-1 đường ray hai chiều, đường ray thứ i nối trạm i và i+1 với nhau. Nguyên định nghĩa giá trị chiến thuật của toàn bộ các trạm là tổng các tích của chiến thuật của các cặp trạm được nối trực tiếp hoặc gián tiếp với nhau. Ví dụ với 4 trạm như hình dưới đây:

Giá trị chiến thuật của toàn bộ các trạm là 4×5+4×1+4×2+5×1+5×2+1×2=49

Trong trò chơi này, hệ thống có nhiệm vụ chọn số trạm n trong trò chơi, số lượt đánh bom m của người chơi và gán giá trị chiến thuật cho từng trạm. Ở mỗi lượt đánh bom, người chơi được quyền loại bỏ một đường ray trong trò chơi. Người chơi sẽ thắng nếu đánh bom một cách tối ưu sao cho giá trị chiến thuật của toàn bộ các trạm là nhỏ nhất cho thể trong thời gian 30 giây. Nếu người chơi không đưa ra được cách đánh bom tối ưu, máy sẽ dành chiến thắng.

Ví dụ với 4 trạm như trên và số lượt đánh bom m là 1, nếu người chơi chọn đánh bom đường ray thứ 2:

Giá trị chiến thuật của toàn bộ các trạm còn lại là 4×5+1×2=22. Tuy vậy, nếu người chơi chọn đánh bom đường ray đầu tiên:

Giá trị chiến thuậ của toàn bộ các trạm còn 5×1+5×2+1×2=17. Đây là cách đánh bom tối ưu vì thế người chơi sẽ chiến thắng.

Để tránh hiện tượng giật, lag, hệ thống phải tự tính toán được giá trị chiến thuật nhỏ nhất của toàn bộ các trạm trong mỗi trò chơi trong vòng 1 giây. Hãy giúp Nguyên viết chương trình làm nhiệm vụ này để anh có thể nhanh chóng hoàn thiện trò chơi của mình.

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

+ Dòng đầu tiên ghi 2 số nguyên n và m (1≤n≤500, 0≤m<n). n là số trạm trong trò chơi và m là số lượt đánh bom của người chơi.

+ Dòng thứ 2 chứa n số nguyên có giá trị trong đoạn từ 1 đến 5, số thứ i là giá trị chiến thuật của trạm thứ i.

Kết quả: Ghi vào tệp văn bản LAWRENCE.OUT một số nguyên duy nhất là giá trị chiến thuật nhỏ nhất của toàn bộ trạm.

Ví dụ:

LAWRENCE.INP	LAWRENCE.OUT		LAWRENCE.INP	LAWRENCE.OUT
4 1 4 5 1 2	17		4 2 4 5 1 2	2

Test - code - đề - solution
back

Kiểm tra số nguyên tố

Cho số nguyên dương n và dãy n số nguyên dương a₁, a₂,…,a_n. Hãy cho biết số a_i có phải là số nguyên tố hay không?

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

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

+ Dòng thứ 2 ghi n số nguyên dương a₁, a₂,…,a_n

Dữ liệu ra: ghi vào tệp văn bản CPRIME.OUT gồm n dòng, trong đó dòng thứ i ghi YES nếu số a_i là số nguyên tố, ngược lại ghi NO

Ví dụ:

CPRIME.INP	CPRIME.OUT
3 1 4 7	NO NO YES

Giới hạn:

+ 1≤n≤10⁶

+ 1≤a_i≤10⁷

Test – code

Chương trình tạo test

Chương trình tạo test cho bài Kiểm tra số nguyên tố

Bao gồm 4 test, đánh số từ 00 đến 03

Mỗi test có quy cách: 

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

+ Dòng thứ 2 ghi n số nguyên dương a1, a2,…,an

Gới hạn:

+ 1≤n≤10^6

+ 1≤ai≤10^7

Chu trình đơn

Cho đơn đồ thị vô hướng liên thông gồm n đỉnh và m cạnh. Hãy tìm một chu trình đơn bất kỳ của đồ thị đã cho.

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

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

+ m dòng tiếp theo mỗi dòng ghi 2 số nguyên u, v cho biết (u,v) là 1 cạnh của đồ thị

Dữ liệu ra: ghi vào tệp văn bản CYCLE.OUT

+ Dòng đầu tiên ghi 1 số nguyên cho biết số đỉnh trong cho trình

+ Dòng thứ 2 ghi n số nguyên theo thứ tự các đỉnh trong chu trình, lưu ý đỉnh đầu trùng với đỉnh cuối

Ví dụ:

CYCLE.INP	CYCLE.OUT
3 3 1 2 2 3 3 1	4 1 2 3 1

Test - code
(test có trình chấm ngoài bằng C++)

Chương trình tạo test:

Chương trình tạo test cho bài http://tinhoclqdkh.blogspot.com/2017/02/chu-trinh-on.html

Quy cách: 20 test đánh số từ 00 đến 19, mỗi test có cấu trúc như sau:

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

+ m dòng tiếp theo mỗi dòng ghi 2 số nguyên u, v cho biết (u,v) là 1 cạnh của đồ thị

Chú ý: Các cạnh của đồ thị được sắp xếp tăng dần theo u, nếu u bằng nhau thì tăng theo v, với (u,v) là một cạnh của đồ thị.

Chương trình chấm: Mỗi test đúng được 0.5 điểm, mỗi test sai sẽ thông báo lỗi (có sử dụng lại chương trình của thầy Lê Minh Hoàng)