Vào 23:30 tối nay 29/08/2015 Codeforces Round #318 (Div 1 & 2) sẽ diễn ra.
Thời gian kết thúc đăng ký: 23:25
Mọi người có thể cùng vào đây thảo luận sau khi cuộc thi kết thúc.
Vào 23:30 tối nay 29/08/2015 Codeforces Round #318 (Div 1 & 2) sẽ diễn ra.
Thời gian kết thúc đăng ký: 23:25
Mọi người có thể cùng vào đây thảo luận sau khi cuộc thi kết thúc.
Dịch đề:
Bài A div2:
Có N đại biểu tham gia bầu cử, người thứ i sẽ nhận được a[i] phiếu bầu cử từ a[i] công dân. Người thứ nhất muốn giành chiến thắng, nên tìm cách hối lộ một số công dân để anh ta bầu cử phiếu cho mình. Tính số người ít nhất anh ta cần phải hối lộ, biết người thứ nhất sẽ giành chiến thắng nếu số phiếu của anh ta lớn hơn số phiếu của những người còn lại.
Bài C div2/A div 1:
Cho mảng gồm N số nguyên A1...AN. Mỗi bước có thể chọn một số nguyên trong mảng, tăng gấp 2, gấp 3 lần giá trị của số đó. Hỏi sau một số bước hữu hạn tất cả các phần tử của mảng A đều bằng nhau
Bài D Div2/B div 1:
Cho N cái cột, cột thứ i có độ cao là Hi, tạo thành một số hình. Tại mỗi bước bạn phải xóa toàn bộ viền ngoài của các hình đó. Hỏi sau bao nhiêu bước thì bạn xóa dc toàn bộ các hình đó.
Hóng cao nhân chỉ em bài C div 1 :(
C div 1:
Tính 4 mảng trên bằng DFS 1 lần trên cây trong O(N).
Sau khi có 4 mảng này, thì bạn giải được bài toán nếu coi đỉnh 1 là gốc của cây.
Tuy nhiên trong bài này có thể đặt đỉnh bất kỳ làm gốc --> bạn cần phải tính thêm 1 số thứ nữa :v bạn có thể đọc code mình (account I_love_Hoang_Yen) nhưng code mình khá phức tạp, tính 4 mảng g1 --> g4 với ý nghĩa tương tự f :))
Chúc mừng anh RR lên international grandmaster
các pro chỉ mình cách làm bài Bdiv1 với
Qhd left[i] là số bước ít nhất để xóa cột thứ i từ bên trái-> left[i]=min(a[i],i,left[i-1]+1)
right[i] là số bước ít nhất để xóa cột thứ i từ bên phải-> right[i]=min(a[i],n-i+1,right[i+1]+1)
kết quả : max( min(left[i],right[i]) ) :)
Cảm ơn a và chúc mừng a đã lên international grandmaster :)