Giúp mình với! Đề thi Tin mà như thi HSG Toán vậy!

[bld]

bạn neight nói rõ hơn về cách giải của bạn không ?

[neiht1992]

Theo ý em thì đề không sai nhưng nên sửa lại một tí cho khỏi hiểu nhầm. Thay vì không có bộ ba đoạn thẳng bất kì tạo thành một tam giác thì nên đổi thành không có bộ ba đoạn thẳng bất kì là ba cạnh của 1 tam giác Vì nếu hiểu như anh ijsh@n nghĩa là không có tam giác nào trên hình vẽ thì hình như là không bài toán không có kết quả. Vì còn tùy vào vị trí các điểm.

@bld
ý tưởng của mình là đánh số thứ tự các điểm từ 1 đến N.
Từ điểm số 1 nối đến các điểm 2,4,6,8...
Từ điểm số 2 nối đến các điểm 1,3,5,7...
.....................
*Nếu N chẳn:
Từ 1 nối được tới 2,4,6,...,n được n/2 đoạn
Từ 2 nối được tới 1,3,5,...,n-1 được n/2 đoạn
.....................
Và số đoạn thẳng nối được là n*n/2/2 = sqr(n)/4 (1)
*Nếu N lẻ:
Từ 1 điểm lẻ nối được tới 2,4,6,...,n-1 được (n-1)/2 đoạn
....................
Có (n+1)/2 điểm mang thứ tự lẻ.
Và số đoạn thẳng nối được là (n+1)(n-1)/4 = (sqr(n)-1)/4 (2)

(1)(2)=> kq = (sqr(n)-(n mod 2))/4.

[huysun]

thử xem thế này đúng không.
gọi f(i) là số đoạn thẳng thỏa mãn từ i điểm
=>f(1)=0
f(2)=1



=>f(n)=f(4)+f(n-2)

[=========> Bổ sung bài viết <=========]

à nhầm,
f(n)=f(4)+f(n-2)-1
có thể giải quyết ngon lành n=1 tỉ chỉ với 2 câu lệnh rẽ nhánh, 1 lần lặp (số lần lặp không quá 500 triệu)và 5 biến số.

[neiht1992]

Sáu điểm:

[bld]

mình thấy huysun hơi nhầm, nhìn vào là thấy có nhiều chỗ bất cập ( thấy rõ ở n=6 khi so với neiht )
, còn công thức của neiht thì hay thật , nhưng bld thấy trong hình của neiht chỉ kẻ 8 đoạn thẳng , còn nếu theo quy luật của neiht thì có đến 9 đoạn thẳng
còn neiht nói rõ hơn về chuyện nối các điểm chẵn-lẻ không ( tại sao lại nghĩ như vậy ? )

[m2mpro]

n+(n div 2)

Tôi làm ra được công thức thế này, các bạn xem liệu có đúng hay không ? Nếu đúng tôi sẽ giải thích

[nadongtae]

Cho hỏi một câu, anh em giải quyết như vậy là theo hướng lấy điểm mà không xét độ dài vì hình như đề còn cho tọa độ nữa. Nếu lấy theo độ dài thì số lượng cạnh sẽ ít hơn. Ví dụ với trường hợp n=4 thì có thể chỉ có 3 cạnh không được 4 cạnh đâu.
Cho dễ hình dung: anh em vẽ 1 cái tam giác đều ABC sau đó chấm thêm 1 điểm D ở ngoài tam giác sao cho 3 cạnh nối từ D tới A,B,C không là tam giác. ^^. Thì số cạnh lấy tối đa là 3 với 3 cạnh DA,DB,DC. Vì nếu lấy theo bác huysun là AB,AC, DC,DB thì với 3 cạnh DC,DB,AC là có thể tạo thành 1 tam giác rồi.

Anh em nghĩ sao về trường hợp này. (nếu giải theo cách anh em làm hiện tại thì để phải thêm 1 dòng thế này: độ dài các cạnh là duy nhất.)

công thức của m2mpro hình như có vấn đề n=2 thì 2+2/2 = 3 hình như hơi vô lý

[m2mpro]

À, cái công thức của mình đúng với trường hợp n>2. CÒn hai truờng hợp n=1,n=2 thì tự xét được mà.

[=========> Bổ sung bài viết <=========]

Thành thật xin lỗi, cách tôi đã sai, phải về suy nghĩ lại rồi

[bld]

Mình đã nghiên cứu kỹ công thức của neiht , MMKC_IT , m2mpro
mình cũng nghĩ được cách riêng của mình là tạo n giác rồi vẽ đường chéo , tính xem với mỗi đỉnh , có thể nối với bao nhiêu đỉnh khác (cái này dễ , chỉ cần xét vài trường hợp , dùng div , mod ) được bao nhiêu nhân với n tất cả chia 2 rồi cộng thêm n (n giác )
nhưng xét lại của neiht là hoàn hảo nhất , xét cách này có thể thấy rõ tránh tạo tam giác nhưng tận dụng hết tất cả các tứ giác
việc tạo n giác như bld và MMKC_IT có thể làm mất đi 1 số đường nhất định
tóm lại bld nghĩ công thức sẽ là
(n*n-n mod 2)/4

[m2mpro]

Tôi có một thắc mắc nhờ bạn neight1992 giải đáp đó là với công thức của bạn 6 đỉnh thì sẽ ra 9 đường mà sao bạn lại vẽ chỉ có 8 đường thôi nhỉ

Công thức của bạn đúng rồi đấy, tôi nghĩ lại thì thấy công thức của tôi đúng với n>5 .