"嗚啊啊啊啊~~~"
房間魔王發出震耳欲聾的伸吟.
魔王的身體碎塊發出激烈的強光, 然後從房裡消逝.
身負重傷的妁艷, 搖搖擺擺地走向眼前的大門.
打開了大門, 這是一個監獄樣子的房間.
向遠處一望, 有個著制服的女孩的身影被關在牢中.
近前一看, 是妁艷的妹妹!
妹妹似乎注意到了房門打開的聲音, 抬起頭, 看到了妁艷.
"嗚..., 哥哥!", 妹妹眼框瞬間紅了起來.
兩人重逢了.
但是眼前的牢門之鎖隔開了兩人.
門鎖是由兩個正N邊形組成, 一個在內側一個在外側, 妁艷站在外側.
在兩個N邊形的頂點之間會有一些線, 其中一側的一個頂點必然恰好會連到另一側的其中一個頂點.(它們呈現一一對應)
經過仔細的觀察.
每一道機關都是N邊形的三個頂點, 逆時針方向的一個三角形, 且其內側對應的三角形也是逆時針方向.
必須將所有這樣的三角形都解開, 門鎖才會打開.
妁艷想知道自己要解多久, 有多少三角形的機關要解開.
第一行有一個數字N (3 ≤ N ≤ 300,000), 意義如上文所述.
接下來有一行, 一共有N個數字, 為1~N的一個排列. 第i個數字ai代表外側的第i個頂點對應到內側的第ai個頂點. 編號由逆時針方向為1~N.
輸出唯一的數字, 代表有幾個機關要解.
所有機關的內側對應編號: (1, 3, 4), (1, 3, 5), (1, 4, 5), (1, 2, 5), (3, 4, 2), (3, 4, 5) 共六組.
原TIOJ1773 / problem setter: willyliu
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 12 |
2 | 1 | 12 |
3 | 2 | 12 |
4 | 3 | 12 |
5 | 4 | 12 |
6 | 5 | 12 |
7 | 6 | 12 |
8 | 7 | 16 |