PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Triangular Vertices

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (涼宮春日症候群)時間18年前 (2006/11/24 03:56)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《pinglunliao (王者：一條孤獨的不歸路)》之銘言： : 原題目：　http://www.cs.ualberta.ca/~contest/club/020208/00209.html : 某個參考解答　http://www.cs.ualberta.ca/~contest/club/020208/00209code1.html : 我對這個參考解答的底下部分有疑問：「他是怎麼推出公式來的？」 : p[psize].n = pset[i]; : x = sqrt(2*pset[i])-1; : while(1){ : if(x*(x-1)/2 < pset[i] && pset[i] <= x*(x+1)/2) break; : x++; : } : p[psize].x = x; : p[psize].y = pset[i]-x*(x-1)/2; : p[psize].z = x*(x+1)/2+1 - pset[i]; : 版友們對　Triangular Vertices　有別的解法嗎？我的想法是把點看成這樣：　Ｙ　↑ 　︴　｜＼｜＼｜＼｜＼｜４15－20－26－33－41－　｜＼｜＼｜＼｜＼｜＼３10－14－19－25－32－　｜＼｜＼｜＼｜＼｜＼２６－９－13－18－24－　｜＼｜＼｜＼｜＼｜＼１３－５－８－12－17－　｜＼｜＼｜＼｜＼｜＼０１－２－４－７－11－…→Ｘ　０　１　２　３　４然後去找出每個點對應的x,y座標檢查兩點是否連線就變成它們的x,y座標X相同或Y相同或X+Y相同距離則為(X相同時)Y的差或(Y相同時)X的差或(X+Y相同時)X的差然後因為題目給的點順序不一定所以要每對之間都檢查 (點最多才6個所以這一定OK) 確定邊之後再檢查是否能連成三角形/平行四邊形/六邊形距離是否相等等等 (可以就直接做成一個小graph來檢查) 上面的式子裡面的x就是我的X+Y+1 裡面的y就是我的Y+1 裡面的z就是我的X ＿那個√2n-1只是要找出的X+Y+1的值的下界估計而已 (這樣while只需要跑個幾圈就找到x了如果不先估計 while可能會跑非常多圈) -- 就我的印象中 92年全國高中資訊能力競賽決賽的題目之一和這題非常像當時的題目是直接把圖形給成上面那樣 (只差沒有畫出座標軸而已) 然後也沒有限定距離要相等只要求有邊連得起來即可 -- **** 說: 不要期望一個精神力差不多已經見底的人阿Orz -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 192.192.197.115