HSG Tin cấp quốc gia 2009-2010!

[linhhahaduc]

Bài 1 : Dijkstra heap - Gọi Minlen[i,j] là Độ dài ngắn nhất đến đỉnh i và đã vượt sông j lần
bài 2 : ( Không biết mình có hiểu sai đề ko nữa ) Cứ làm bình thường , lấy min của tất cả các khoảng cách của điểm M đến N điểm trong đa giác
Bài 3 : Luồng - Bài NKLIGHT trên vnoi . http://vn.spoj.pl/problems/NKLIGHT/

[hang_vt]

k , cao siêu quá rồi
Bài 1 : dij .
- Gán maxs = tổng đường đất + 1
- Nếu đỉnh a->b là sông thì gán gằng maxs
- Dij bình thường
- d[n] mod maxs là tổng độ dài đường đất còn d[n] div maxs là số lần vượt sông
Bài 2 : Min của
- K/c từ M đến các điểm
- K/c từ M đến cạnh nếu hình chiếu của M nằm trên canh
Bài 3 : QHĐ

[mini_bestboy]

Mình chưa hiểu rõ bài 3 của hang_vt lắm, phải chăng khi xây dựng 1 trạm chiếu sáng trên dòng (hay cột) thì nó chiếu sáng tất cả các trạm trên cùng dòng (hay cột) đó, và các trạm này không cần phải chiếu sáng ?
Còn về bài 2, nếu đề ko xếp sẵn thứ tự đỉnh đa giác thì chắc quay lui đặt cận cho xong, chưa suy nghĩ tối ưu hơn nữa.

bài 2 : ( Không biết mình có hiểu sai đề ko nữa ) Cứ làm bình thường , lấy min của tất cả các khoảng cách của điểm M đến N điểm trong đa giác

Không phải đâu bạn ơi, khoảng cách gần nhất đến "điểm thuộc đa giác" ý chứ !

Bài 2 : Min của
- K/c từ M đến các điểm
- K/c từ M đến cạnh nếu hình chiếu của M nằm trên canh

Khoảng cách từ M đến cạnh, mà đề lại ko cho thứ tự cạnh, thế phải duyệt N^2 lần tạo thành cạnh à ?

[hang_vt]

Bài 2:
1 for để tính k/c 1 điểm -> đoạn thẳng
for thừ 1 để kt hình chiếu of nó có nằm trên cạnh hay k , nếu có thì dùng ct tính thôi
Bài 3 : mini k hỉu chỗ nào ?

[mini_bestboy]

Bài 2:
1 for để tính k/c 1 điểm -> đoạn thẳng
for thừ 1 để kt hình chiếu of nó có nằm trên cạnh hay k , nếu có thì dùng ct tính thôi
Bài 3 : mini k hỉu chỗ nào ?

Nhưng để tạo thành 1 cạnh thì cần 2 điểm, đề lại ko cho thứ tự điểm nên => có N điểm thì tạo thành tổ hợp N chập K cạnh => số khá lớn
Bài 3 như mình nói, nếu 1 trong các đèn nằm trên cùng 1 dòng hoặc cạnh được xây dựng thì các đèn khác còn lại khỏi cần xây dựng ?
Mà QHĐ CT truy hồi thế nào vậy Hang ?

[mr_invincible]

Đọc đến cuối topic thì mình thấy ko hiểu lắm. Đây là topic bàn về bạn nên học gì ôn gì trước khi thi QG hay trao đổi các bài toán?

Về việc học gì, thi thế nào: Đọc qua thì mình thấy có bạn vẫn còn đang dùng TP (?). Học Free Pascal không quá mất thời gian như các bạn nghĩ. Thời gian để dùng quen chắc mất cỡ 2 tuần. Các bạn làm bài bằng TP khi đi thi sẽ gặp rất nhiều khó khăn và khó có thể đạt kết quả tốt. Chẳng hạn nếu dùng TP bạn sẽ gặp rắc rối khi xử lý bộ nhớ. Năm ngoái có bạn trước khi nộp bài đổi mảng bài 2 thành 100 000 * 100 000. Lỗi này có lẽ là do chưa được làm quen với FP nên không hiểu khả năng của nó (?). Các bạn cũng sẽ vứt điểm đi nếu như không biết int64 hay qword là gì.
Mình cũng khuyên là các bạn đi thi thì xác định rõ mục tiêu của mình là gì => bạn hi vọng được giải gì. Bạn nên tìm thử bảng điểm năm ngoái để hiểu rõ tình hình thực tế kết quả năm ngoái như thế nào. Theo mình nhớ thì chênh lệch giữa địa phương và các khối chuyên là rất lớn.


Còn về "Đề lập đội tuyển hsg tin lớp 12 THPT dự thi quốc gia 2009-2010 tỉnh BR_VT" thì bài 3 mình chưa thấy ai làm QHD đúng (ko khẳng định không thể làm bằng qhd, chỉ là mình chưa thấy). Nếu bạn nghĩ cách của bạn đúng, bạn nên post cụ thể lời giải. Post một từ "QHD" lên hoàn toàn không có tác dụng nào (?)

[mini_bestboy]

Đọc đến cuối topic thì mình thấy ko hiểu lắm. Đây là topic bàn về bạn nên học gì ôn gì trước khi thi QG hay trao đổi các bài toán?

Về việc học gì, thi thế nào: Đọc qua thì mình thấy có bạn vẫn còn đang dùng TP (?). Học Free Pascal không quá mất thời gian như các bạn nghĩ. Thời gian để dùng quen chắc mất cỡ 2 tuần. Các bạn làm bài bằng TP khi đi thi sẽ gặp rất nhiều khó khăn và khó có thể đạt kết quả tốt. Chẳng hạn nếu dùng TP bạn sẽ gặp rắc rối khi xử lý bộ nhớ. Năm ngoái có bạn trước khi nộp bài đổi mảng bài 2 thành 100 000 * 100 000. Lỗi này có lẽ là do chưa được làm quen với FP nên không hiểu khả năng của nó (?). Các bạn cũng sẽ vứt điểm đi nếu như không biết int64 hay qword là gì.
Mình cũng khuyên là các bạn đi thi thì xác định rõ mục tiêu của mình là gì => bạn hi vọng được giải gì. Bạn nên tìm thử bảng điểm năm ngoái để hiểu rõ tình hình thực tế kết quả năm ngoái như thế nào. Theo mình nhớ thì chênh lệch giữa địa phương và các khối chuyên là rất lớn.


Còn về "Đề lập đội tuyển hsg tin lớp 12 THPT dự thi quốc gia 2009-2010 tỉnh BR_VT" thì bài 3 mình chưa thấy ai làm QHD đúng (ko khẳng định không thể làm bằng qhd, chỉ là mình chưa thấy). Nếu bạn nghĩ cách của bạn đúng, bạn nên post cụ thể lời giải. Post một từ "QHD" lên hoàn toàn không có tác dụng nào (?)

=> Hồi đó giờ ở trường dạy TP quen rồi, bây giờ chuyển sang FP thật khó, báo lỗi mà chã biết là lỗi gì, còn bên TP thì cũng thuộc khá nhiều báo lỗi. Đi thi thì ai chả muốn đạt giải cao hả bạn

Thế đề bài 3 bạn làm theo cách nào ? Có thể trình bày rõ hơn ko ?

[hang_vt]

bài 3 :
Gọi t[i,j] là tổng chi phí xây dựng nhỏ nhất:
- Nếu ô i,j có đèn thì t[i,j]:=min(t[i-1,j]+a[i],t[i,j-1]+b[j]).
- Nếu ô i,j không có đèn thì:
+ Nếu hàng i không có đèn , cột j không có đèn thì t[i,j]:=t[i-1,j-1].
+ Nếu hàng i có , cột j không có thì t[i,j]:=t[i,j-1].
+ Nếu hàng i không có , cột j có thìt[i,j]:=t[i-1,j].
+ Nếu hàng + cột có thì t[i,j]:=min(t[i-1,j]+a[i],t[i,j-1]+b[j]).

[mini_bestboy]

Hình như mình làm theo CT QHĐ trên thì không ra dc kết quả của Ví dụ ?
Kết quả theo như VD của mảng T là :
10 10 10
12 15 15

Còn về bài 2, khoảng cách từ điểm M đến các đỉnh luôn nhỏ hơn từ M đến các đường chéo thì đúng, nhưng mình hỏi là, người ta cho bạn N điểm như thế, làm sao bạn phân biệt dc 2 điểm nào tạo ra cạnh, 2 điềm nào tạo đường chéo ?

[pascal_of_newbie]

Sac mo tu bao gio day