[Code Jam]-Round D APAC Test 2016
Link đề và test: https://code.google.com/codejam/contest/11214486/dashboard
- Thao tác M: thay đổi giá trị của một ô trong lưới sang 0 hoặc 1
- Thao tác Q: Xác định số lượng miền liên thông giá trị 1. Một miền liên thông giá trị 1 được xem là một tập các ô mà tất cả đều là 1, trong miền đó mọi ô đều có thể tới được từ bất kì ô nào bằng cách di chuyển giữa các ô dọc theo cạnh (không phải góc).
INPUT:
- Dòng 1: T là số lương testcase. Tiếp theo là T test
Mỗi Test: dòng đầu chứa 2 số R,C. R dòng tiếp theo, mỗi dòng chứa các kí tự 0,1. Các dòng này biểu diễn trạng thái ban đầu của lưới.
Dòng tiếp theo chứa một số nguyên N chỉ số lượng thao tác trên lưới. N dòng tiếp theo, mỗi dòng thể hiện một thao tác. Tất cả các thao tác M sẽ có cấu trúc M x y x với nghĩa: ô ở vị trí dòng x, cột y sẽ chuyển thành giá trị z. Tất cả các thao tác Q có cấu trúc Q.
OUTPUT:
Đối với mỗi Test, đưa ra 1 dòng theo cấu trúc "Case #x:" với x là thứ tự testcase. Đói với tất cả các thao tác Q trong các test, đưa ra một dòng chứa số lượng miền liên thông 1.
Giới hạn:
T thuộc [1,10]
R,C thuộc [1,100]
x thuộc [0,R]
y thuộc [0,C]
z thuộc [0,1]
(6 điểm cho các test có N<=10; 8 điểm cho các test có N<=1000)
G kỹ sư có thể di chuyển khí cầu lên, xuống bằng cách gửi tín hiệu radio để điều khiển thả chấn lưu hoặc nhả bớt không khí ra. Nhưng họ không thể di chuyển các khí cầu theo chiều ngang. Họ phải lợi dụng sức gió để làm việc đó.
Có M độ cao khác nhau là vị trí của các khí cầu. Gió tại các độ cao khác nhau có thể thổi theo các hướng và tốc độ khác nhau. Đặc biệt, ở độ cao j, tốc độ gió là Vj, với giá trị dương thể hiện gió từ trái sang phải và ngược lại. Một khí cầu ở vị trí P, tốc độ gió tại vị trí đó là V sẽ di chuyển đến vị trí P+V sau 1 đơn vị thời gian, ở vị trí P+2V sau 2 đơn vị thời gian,... Nếu khí cầu chạm tới tháp, khí cầu đó sẽ được thu hồi.
Sẽ mất |Ho-Hnew| điểm năng lượng để di chuyển 1 khí cầu giữa hai độ cao khác nhau (không mất thời gian di chuyển). Bạn có Q điểm năng lượng có thể dùng, tuy vậy bạn cũng không cần phải dùng hết số điểm đó. Hỏi cần ít nhất bao nhiêu thời gian để có thể thu hồi toàn bộ khí cầu nếu bạn tiết kiệm năng lượng nhất?
INPUT:
Dòng đầu là số lượng test T. Tiếp theo là T test.
Mỗi test: dòng đầu chứa 3 số nguyên N, M, Q thể hiện số khí cầu, số lượng độ cao, số điểm năng lượng có sẵn. Dòng thứ hai chứa M số nguyên, giá trị thứ j trong dòng (tính từ vị trí đầu là vị trí 0) chính là vận tốc gió ở độ cao j.
N dòng tiếp theo, dòng thứ i chứa 2 số Pi và Hi chỉ vị trí và độ cao của khí cầu thứ i
OUTPUT:
Đối với mỗi Test, đưa ra theo cấu trúc "Case #x:y" với x là số hiệu Test (test đầu là 1) và y là số đơn vị thời gian nhỏ nhất cần thiết để thu hồi tất cả các khí cầu, là IMPOSSIBLE nếu như không thể thu hồi được toàn bộ khí cầu với năng lượng được cho.
Giới hạn:
- Test kích thước nhỏ:
1 ≤ T ≤ 100.
1 ≤ N ≤ 10.
1 ≤ M ≤ 10.
-10 ≤ Vj ≤ 10.
1 ≤ Q ≤ 10.
0 ≤ Hi <M.
-10 ≤ Pi ≤ 10.
- Test kích thước lớn:
1 ≤ T ≤ 25.
1 ≤ N ≤ 100.
1 ≤ M ≤ 1000.
-100 ≤ Vj ≤ 100.
1 ≤ Q ≤ 10000
0 ≤ Hi <M.
-10000 ≤ Pi ≤ 10000.
Hàng ngày, Alice thức dậy vào giờ G, đi làm vào giờ W, trở về nhà vào giờ H và đi ngủ vào giờ B. Alice không thể cho thỏ ăn khi đang làm việc hoặc đang ngủ tức là trong các đoạn [W,H) và [B,G). Chú ý thời gian W, B không thể cho thỏ ăn, nhưng vào thời điểm H,G thì có thể. Ở các thời điểm khác, Alice có thể nhấn một nút để cho thỏ ăn hoặc không nhấn nút. Giữa hai thời điểm bất kỳ, con thỏ xác định số giây liên tiếp mà tại đó nó không được cho ăn và chết nếu quãng thời gian đó bằng X.
Hiện tại là thời điểm 00.00.00 trong ngày 0, con thỏ vừa được đưa đến với Alice qua dịch vụ thư (người đưa thư nhấn nút lúc 00:00:00, có thể khi đó Alice đang ngủ và anh ta rời đi) Alice muốn chắc chắn rằng con thỏ của cô vẫn "sống" tại thời điểm 00:00:00 của ngày D. Hỏi số lần tối thiểu Alice cần phải cho thỏ ăn để con thỏ có thể sống đến thời điểm đó?
INPUT:
Dòng đầu là số lượng testcase T. Tiếp theo là T testcase. Mỗi test gồm 6 dòng: 5 dòng đầu thể hiện các thời điểm G,Ư,H,B và X ở dạng hh:mm:ss; dòng cuối cùng chứa số D
OUTPUT:
Đối với mỗi testcase đưa ra theo cấu trúc "Case #x:y" với x là số thứ tự testcase (testcase đầu tiên là test 1) và y là số lần cho thỏ ăn tối thiểu mà Alice cần. Nếu không thể nuôi con thỏ tới thời điểm 00:00:00 ngày D thì y=-1
Giới hạn:
1 ≤ T ≤ 100.
Đảm bảo Alice luôn đi ngủ trước nửa đêm và thức dậy vào nửa đêm hoặc sau nửa đêm.
G,W,H,B theo thứ tự tăng dần trong cùng 1 ngày.
Test #2: con thỏ xấu số bị chết trước khi Alice thức giấc vào ngày 0
Bài A. Dynamic Grid
Trên một lưới kích thước R dòng, C cột, giá trị của mỗi ô có thể là 0 hoặc 1. Ta thực hiện N thao tác trên lưới đó, các thao tác có thể là:- Thao tác M: thay đổi giá trị của một ô trong lưới sang 0 hoặc 1
- Thao tác Q: Xác định số lượng miền liên thông giá trị 1. Một miền liên thông giá trị 1 được xem là một tập các ô mà tất cả đều là 1, trong miền đó mọi ô đều có thể tới được từ bất kì ô nào bằng cách di chuyển giữa các ô dọc theo cạnh (không phải góc).
INPUT:
- Dòng 1: T là số lương testcase. Tiếp theo là T test
Mỗi Test: dòng đầu chứa 2 số R,C. R dòng tiếp theo, mỗi dòng chứa các kí tự 0,1. Các dòng này biểu diễn trạng thái ban đầu của lưới.
Dòng tiếp theo chứa một số nguyên N chỉ số lượng thao tác trên lưới. N dòng tiếp theo, mỗi dòng thể hiện một thao tác. Tất cả các thao tác M sẽ có cấu trúc M x y x với nghĩa: ô ở vị trí dòng x, cột y sẽ chuyển thành giá trị z. Tất cả các thao tác Q có cấu trúc Q.
OUTPUT:
Đối với mỗi Test, đưa ra 1 dòng theo cấu trúc "Case #x:" với x là thứ tự testcase. Đói với tất cả các thao tác Q trong các test, đưa ra một dòng chứa số lượng miền liên thông 1.
Giới hạn:
T thuộc [1,10]
R,C thuộc [1,100]
x thuộc [0,R]
y thuộc [0,C]
z thuộc [0,1]
(6 điểm cho các test có N<=10; 8 điểm cho các test có N<=1000)
Sample
Bài B. gBalloon
Công ty công nghệ G triển khai dự án gồm rất nhiều quả khí cầu. Thỉnh thoảng họ thu thập các quả khí cầu lại để bảo dưỡng tại đỉnh của tòa nhà công ty, đỉnh tòa nhà được đặt ở vị trí 0 theo chiều ngang. Mỗi khí cầu hiện đang ở vị trí Pi và ở độ cao Hi.G kỹ sư có thể di chuyển khí cầu lên, xuống bằng cách gửi tín hiệu radio để điều khiển thả chấn lưu hoặc nhả bớt không khí ra. Nhưng họ không thể di chuyển các khí cầu theo chiều ngang. Họ phải lợi dụng sức gió để làm việc đó.
Có M độ cao khác nhau là vị trí của các khí cầu. Gió tại các độ cao khác nhau có thể thổi theo các hướng và tốc độ khác nhau. Đặc biệt, ở độ cao j, tốc độ gió là Vj, với giá trị dương thể hiện gió từ trái sang phải và ngược lại. Một khí cầu ở vị trí P, tốc độ gió tại vị trí đó là V sẽ di chuyển đến vị trí P+V sau 1 đơn vị thời gian, ở vị trí P+2V sau 2 đơn vị thời gian,... Nếu khí cầu chạm tới tháp, khí cầu đó sẽ được thu hồi.
Sẽ mất |Ho-Hnew| điểm năng lượng để di chuyển 1 khí cầu giữa hai độ cao khác nhau (không mất thời gian di chuyển). Bạn có Q điểm năng lượng có thể dùng, tuy vậy bạn cũng không cần phải dùng hết số điểm đó. Hỏi cần ít nhất bao nhiêu thời gian để có thể thu hồi toàn bộ khí cầu nếu bạn tiết kiệm năng lượng nhất?
INPUT:
Dòng đầu là số lượng test T. Tiếp theo là T test.
Mỗi test: dòng đầu chứa 3 số nguyên N, M, Q thể hiện số khí cầu, số lượng độ cao, số điểm năng lượng có sẵn. Dòng thứ hai chứa M số nguyên, giá trị thứ j trong dòng (tính từ vị trí đầu là vị trí 0) chính là vận tốc gió ở độ cao j.
N dòng tiếp theo, dòng thứ i chứa 2 số Pi và Hi chỉ vị trí và độ cao của khí cầu thứ i
OUTPUT:
Đối với mỗi Test, đưa ra theo cấu trúc "Case #x:y" với x là số hiệu Test (test đầu là 1) và y là số đơn vị thời gian nhỏ nhất cần thiết để thu hồi tất cả các khí cầu, là IMPOSSIBLE nếu như không thể thu hồi được toàn bộ khí cầu với năng lượng được cho.
Giới hạn:
- Test kích thước nhỏ:
1 ≤ T ≤ 100.
1 ≤ N ≤ 10.
1 ≤ M ≤ 10.
-10 ≤ Vj ≤ 10.
1 ≤ Q ≤ 10.
0 ≤ Hi <M.
-10 ≤ Pi ≤ 10.
- Test kích thước lớn:
1 ≤ T ≤ 25.
1 ≤ N ≤ 100.
1 ≤ M ≤ 1000.
-100 ≤ Vj ≤ 100.
1 ≤ Q ≤ 10000
0 ≤ Hi <M.
-10000 ≤ Pi ≤ 10000.
Sample
Ví dụ:
Ở test mẫu trên hình: 2 khí cầu, bạn sẽ dùng 1 điểm năng lượng. Phương án tốt nhất: dùng 1 điểm năng lượng di chuyển khí cầu ở vị trí 3, độ cao 3 xuống độ cao 2. Khi làm việc đó, cần dùng 2 đơn vị thời gian cho cả 2 khí cầu chạm vào vị trí tháp để thu hồi
Bài D: Virtual Rabbit
Alice vừa mua một chú thỏ ảo. Chú thỏ nhảy quanh màn hình và có thể được cho ăn bằng cách nhấp một nút. Alice rất thích con thỏ ảo, nhưng cô quá bận và cô không muốn dành quá nhiều thời gian để chăm sóc chú thỏ. Tuy nhiên, nếu chú thỏ bị bỏ đói quá lâu, nó sẽ chết và Alice sẽ thua trong trò chơi.Hàng ngày, Alice thức dậy vào giờ G, đi làm vào giờ W, trở về nhà vào giờ H và đi ngủ vào giờ B. Alice không thể cho thỏ ăn khi đang làm việc hoặc đang ngủ tức là trong các đoạn [W,H) và [B,G). Chú ý thời gian W, B không thể cho thỏ ăn, nhưng vào thời điểm H,G thì có thể. Ở các thời điểm khác, Alice có thể nhấn một nút để cho thỏ ăn hoặc không nhấn nút. Giữa hai thời điểm bất kỳ, con thỏ xác định số giây liên tiếp mà tại đó nó không được cho ăn và chết nếu quãng thời gian đó bằng X.
Hiện tại là thời điểm 00.00.00 trong ngày 0, con thỏ vừa được đưa đến với Alice qua dịch vụ thư (người đưa thư nhấn nút lúc 00:00:00, có thể khi đó Alice đang ngủ và anh ta rời đi) Alice muốn chắc chắn rằng con thỏ của cô vẫn "sống" tại thời điểm 00:00:00 của ngày D. Hỏi số lần tối thiểu Alice cần phải cho thỏ ăn để con thỏ có thể sống đến thời điểm đó?
INPUT:
Dòng đầu là số lượng testcase T. Tiếp theo là T testcase. Mỗi test gồm 6 dòng: 5 dòng đầu thể hiện các thời điểm G,Ư,H,B và X ở dạng hh:mm:ss; dòng cuối cùng chứa số D
OUTPUT:
Đối với mỗi testcase đưa ra theo cấu trúc "Case #x:y" với x là số thứ tự testcase (testcase đầu tiên là test 1) và y là số lần cho thỏ ăn tối thiểu mà Alice cần. Nếu không thể nuôi con thỏ tới thời điểm 00:00:00 ngày D thì y=-1
Giới hạn:
1 ≤ T ≤ 100.
Đảm bảo Alice luôn đi ngủ trước nửa đêm và thức dậy vào nửa đêm hoặc sau nửa đêm.
G,W,H,B theo thứ tự tăng dần trong cùng 1 ngày.
00:00:00 ≤ G < W < H < B ≤ 23:59:59.
00:00:00 < X ≤ 23:59:59.
00:00:00 < X ≤ 23:59:59.
Small dataset
1 ≤ D ≤ 1000.
Large dataset
1 ≤ D ≤ 1014.
Sample
Test #1: Alice có thể cho thỏ ăn vào 08:00:00 và 20:00:00 hàng ngàyTest #2: con thỏ xấu số bị chết trước khi Alice thức giấc vào ngày 0
Comments
Post a Comment