1 năm, 6 tháng trước

Vòng loại phía Bắc của ACM Việt Nam vừa diễn ra :D Bạn nào vừa thi vào đây trao đổi nhé.

Cho những ai chưa biết:

Đội mình làm đc 10 bài (trừ B, bọn mình làm 3^14 nhưng TLE suốt :'( ), không biết các đội làm như nào :D

1 năm, 6 tháng trước

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

1 năm, 6 tháng trước

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

1 năm, 6 tháng trước
Trả lời arsenal2310
  Hiện bài gốc

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.
1 năm, 6 tháng trước
Trả lời arsenal2310
  Hiện bài gốc

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

 

1 năm, 6 tháng trước

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

1 năm, 6 tháng trước
Trả lời HoangLe1995
  Hiện bài gốc

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; }
}

 

1 năm, 6 tháng trước
Trả lời arsenal2310
  Hiện bài gốc

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.

1 năm, 6 tháng trước
Trả lời arsenal2310
  Hiện bài gốc

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))

1 năm, 6 tháng trước
Trả lời RR
  Hiện bài gốc

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)

1 năm, 6 tháng trước

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

1 năm, 6 tháng trước

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 :)

1 năm, 6 tháng trước
Trả lời ntduc95
  Hiện bài gốc

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

1 năm, 6 tháng trước
Trả lời iamquang95
  Hiện bài gốc

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

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

 

 

1 năm, 6 tháng trước

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 :( 

 

1 năm, 6 tháng trước

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

1 năm, 6 tháng trước

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

1 năm, 6 tháng trước
Trả lời iamquang95
  Hiện bài gốc

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.

1 năm, 6 tháng trước
Trả lời Songuku95
  Hiện bài gốc

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

1 năm, 6 tháng trước
Trả lời ntduc95
  Hiện bài gốc

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