Thursday 13 August 2020

Codeforces Round #664 (Div. 2) Problem A & B


> Be me, have final tests and still spending time to do competitive programming.

Don't. Seriously, don't.

A. Boboniu Likes to Color Balls

Tóm tắt: Cho r viên bi màu đỏ, g viên bi màu lục, b viên bi màu xanh dương và w viên bi màu trắng. Mỗi lượt thay đổi bạn sẽ chọn 1 viên bi màu đỏ, 1 viên bi màu lục và 1 viên bi màu xanh dương, sau đó sơn 3 viên bi trên thành màu trắng. Tìm xem có thể nào sắp xếp các viên bi trên thành một dãy palindrome sau một số lần biến đổi nhất định (có thể không biến đổi) nào đó không.

Hướng dẫn: Để sắp dãy bi trên thành palindrome bắt buộc 3 trong 4 loại bi phải có số bi chẵn. Nếu không, ta phải thực hiện biến đổi (với số lượng bi r, g và b lần lượt > 0), và sau khi biến đổi nếu 3 trong 4 loại bi chẵn thì ta kết luận có thể lập palindrome.

Một số lưu ý:

  • Công thức biến đổi: --r, --g, --b, w += 3
  • Số lẻ trừ đi 1 sẽ trở thành số chẵn, xét mọi số lẻ lớn hơn 1. Do vậy chỉ cần thực hiện biến đổi 1 lần duy nhất.


Tóm tắt: Cho bàn cờ kích thước n × m, bạn đang đứng ở ô (Sx, Sy). Tìm lộ trình đi qua tất cả các ô của bàn cờ, mỗi ô chỉ đi qua đúng 1 lần. Bạn chỉ có thể di chuyển theo hàng ngang hoặc hàng dọc. Chú ý là khi di chuyển từ ô (x, y) sang (z, y) (chiều dọc) hoặc sang (x, z) (chiều ngang) thì các ô nằm giữa tính là chưa đi qua.

Hướng dẫn: n, m ≤ 100 nên có thể dùng DFS đệ quy + mảng đánh dấu.

No comments:

Post a Comment

Popular posts