Mọi người chia sẻ solution bài C, D giúp mình được không :D Cảm ơn :D

Anh RR share solution C với E đi ạ!!!!!!

Bài C teammate mình làm, công thức 2^((M-1) * (N-1)), còn chứng minh như nào thì mình ko biết.

Bài D tư tưởng là xây dựng đồng thời 2 số a và M*a, lần lượt thêm từng chữ số vào, và qhd theo kiểu:

• f(i, s, d) = số cách xây dựng i chữ số đầu, hiệu S(a) - S(a*M) là s, số dư của a*M khi chia d.

Bài D mình dùng quy hoạch động f[i,s1,s2,re] là số lượng số có i chữ số, tổng các chữ số là s1, khi nhân nó với M sẽ được số có tổng i chữ số cuối là s2, và phần thừa phía trước là re. Sau đó for từng chữ số 0-> 9, coi như đặt chữ số đó vào vị trí đầu, tính s1', s2' và re' dựa vào s1, s2, re và M, cập nhật cho trạng thái tiếp theo. Kq được lấy là tổng f[n,s1,s2,re] thoả mãn s1 = s2 + S(re). Đpt khoảng n*(n*9)*(n*9)*m cho mỗi test

Anh RR cho em hỏi solution bài E với 

Bài E:

Đầu tiên dùng Toán, mình đưa về bài toán: Cho N, tìm tất cả các số nguyên tố thuộc 1 trong 3 dạng:

1. -2*i*i + 3
2. 2*i*i + 3
3. (2*i*i + 1) / 3

Với 0 <= i <= N.

Dạng 1 thì chỉ có 1 số duy nhất khi i = 0

Dạng 2 và dạng 3 cách làm giống nhau, nên mình nói cách giải cho 2.

Dùng Toán, chứng minh đc: 

• Nếu 2*i*i + 3 == p1 * p2 * ...,
• thì tồn tại j < i mà 2*j*j + 3 chia hết cho p1 hoặc p2.

Do đó, ta dùng sàng vô cùng hư cấu như này:

for(i = 0 --> N) A(i) = 2*i*i+3

for(i = 0 --> N) {

    if (A[i] <= 1) continue;

    p = A[i]

    if (p == 2*i*i+3) --> A(i) là 1 số nguyên tố cần tìm.

    for(x = i + k*p) { while (A[x] % p == 0) A[x] /= p; }

    for(x = -i + k*p) { while (A[x] % p == 0) A[x] = A[x] / p; }
}

C chỉ cần tính số các bảng (m - 1) * n mà các hàng có tích là 1 và số các cột có tích là -1 là một số chẵn.

Bài C: Nếu ta điền một cách tùy ý vào bảng (n-1)*(m-1) ở góc trên trái thì tồn tại một cách điền duy nhất cho các ô còn lại. Thật vậy:

Ô (i, m) phụ thuộc vào tích n-1 số ở hàng i.

Ô (n, i) phụ thuộc vào tích m-1 số ở cột i.

Ô (n, m) phụ thuộc vào hàng cuối và cột cuối. Tuy nhiên, dễ dàng chứng minh được tích hàng cuối và cột cuối là bằng nhau.

Do đó đáp án là 2 ** ((n-1)*(m-1))

Bài C chứng minh thì đơn giản thôi :v Điền ngẫu nhiên trong bảng (N-1) x (M-1), còn hàng cuối và cột cuối thì tự suy ra.

-> 2^(N-1)(M-1)

Cho mình hỏi thuật toán bài A và bài I :D

cho em hỏi sol bài J với dc không ạ. vẫn không nghĩ ra hướng sáng sủa :)

Bài J thì bạn dijkstra 10 đỉnh trong tập thành phố phải đi qua rồi quy hoạch động trạng thái hoặc là làm 10! thôi :D

dijkstra từ đỉnh 1 đến q đỉnh à.

không hiểu Dijkstra q đỉnh cho lắm :D

Bài B đội mình làm 3^14 log (3^14)=>got AC

quá nhọ cho bài H hiểu sai đề sửa 10 lần ko đúng , bài J làm dijktra thêm 1 trường trạng thái q bit 5000 * 2^10  * log thì TLE liên tục chả biết sửa đâu... Loay hoay mãi 2 bài này + bài B,K hết cả buổi...

server thì chết lên chết xuống nữa, 1 ngày làm không tốt :( 

Hình như đã có bảng rank chính thức http://icpc.fpt.edu.vn/scoreboard.html

bài B có test chưa bạn ơi?

bài J mình thắc mắc cái input ví dụ có 2 lần ghi 3 2 7 với 3 2 9 không rõ là thế nào, lúc mình làm mình có ý định chỉ nhập đỉnh 1 và q đỉnh trong danh sách để djkstra nhưng tự dưng có 2 cái input kia cái nên mình té luôn :3.

:(( Team mình bị biến mất trong bảng rank

Có q thành phố, từ q thành phố đấy dijkstra đi tất cả các đỉnh khác 

=> d[i][j] là khoảng cách từ thành phố city[i] đến thành phố j (1 <= i <= 10)

Rồi bạn làm như mình nói thôi