Saturday 15 August 2020

Educational Codeforces Round 93 - Problem A&B

> Joined contest

> Solved 2 out of 7

> pain.png


> Monday is the first day of last week before I travel back home

Idk anons, may be this is the last nice week?

A. Bad Triangle

Tóm tắt: Cho mảng a gồm n số nguyên được sắp xếp không giảm (i.e a[i] ≤ a[i + 1]). Tìm và in ra màn hình một bộ ba số nguyên i, j, k sao cho 1 ≤ i < j < k ≤ na[i], a[j] và a[k] không lập được một tam giác có diện tích khác 0. Nếu không tìm được bộ ba i, j, k như vậy, in -1 ra màn hình.

Hướng dẫn:

Xem qua Triangle inequality (Bất đẳng thức tam giác)

Vì đây là mảng không giảm nên ta có thể tìm một bộ i < j < k và a[i] + a[j] ≤ a[k]. Nếu dùng 3 vòng lặp thì sẽ dính TLE, nên mẹo chút là duyệt theo cặp (i và i + 1), sau đó kiếm tra xem có tồn tại k sao cho a[i] + a[i + 1] ≤ a[k] hay không.

Link code mẫu (C++).

B. Substring Removal Game

Tóm tắt: Alice và Bob chơi một trò chơi: ban đầu có một xâu nhị phân s, lần lượt từng người sẽ xóa một xâu con gồm các ký tự liên tiếp giống nhau (i.e dãy ký tự liên tiếp giống nhau, ít nhất 1 ký tự) từ xâu s. Sau mỗi lượt xóa, người chơi được cộng số lượng điểm bẳng với số lượng số 1 đã xóa trong lượt đó (i.e 111000 → 000 (xóa 3 số 1 liên tục ở đầu) → cộng 3 điểm). Trò chơi kết thúc khi xâu s trở thành rỗng. 

(xem ví dụ trong đề bài).

Biết rằng Alice chơi trước, sau đó đến Bob và cứ tiếp tục như vậy đến khi kết thúc, mỗi người đều chơi tối ưu nhất có thể. Tính số điểm của Alice khi kết thúc.

Hướng dẫn: Phương pháp tham lam: cách chơi tối ưu nhất là mỗi người chọn xâu chỉ gồm ký tự 1 dài nhất hiện có trong s rồi xóa đi. Vậy ta đếm số lượng xâu 1 liên tục rồi sắp xếp lại, sau đó cộng điểm của Alice theo thứ tự Alice bắt đầu game trước.

Link code mẫu (C++).

No comments:

Post a Comment

Popular posts