TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

87.5% (7/8)

Description

此題是Open Testdata問題,也就是題目的Test-input是開放下載的。
請按這裡下載所有測資
壓縮檔內除了所有測資以外還包括一個可供本地驗證答案正確性的程式。

龍吼,Dragon Shouts,是上古時代的龍經常使用的一種法術,藉由吼叫出特定的龍語辭彙,龍族可以召喚各種強力的魔法效果。
龍族生來就可以隨意的使用龍吼,但是凡人若想學習的話必須要經年累月的冥思和練習,好讓人類也可以接受龍的思想和語言,
這是因為龍吼不只是一種魔法,更是一種生命之'道',精通並使用一種龍吼代表著將龍的思想納入自己的靈魂本質,成為構成你的人格的其中一個要素。
而改變自己的靈魂並不是一件容易的事,一般人藉由冥想和練習至少需要30、40年以習得龍吼,除非你是Dovahkiin。

雖然修煉龍吼並不是一件容易的事,但是其成果卻是匹敵龍一般的力量,因此上古時代的勇者們為了反叛殘暴的暴君,龍們,大多苦心修練龍吼以推翻龍的暴政。
因此在龍的暴政早已被推翻的現代,修煉龍吼的人已經是少之又少,絕大多數的人終其一生一聲可能都沒聽過真正的龍吼。

而前面提到的Dovahkiin則是一個龍語辭彙,意思是"龍種"或"獵龍種",相傳Dovahkiin是繼承了龍之血的人類,他可以很容易的學會龍的辭彙,
並且可以吸收死去的龍的智慧以迅速精通一句龍吼,簡單來說就是萬中選一的龍吼練武奇材啦。
一個時代的Dovahkiin不只是天生的屠龍戰士,更往往是英雄或救世主,上古時代推翻龍之暴政的戰士、光榮的人類國王、帶領人類熬過艱苦時代的英雄,有許多都是那個時代的Dovahkiin。

而接下來才是你,もも,的故事...


你,もも,是這個時代最後的Dovahkiin。
在一次與正圓(一種肉圓,好ㄘ)的唇槍舌戰中,你不禁脫口而出了一句"Fus Ro Dah!!!",結果正圓就被你言語所蘊含的遠古之力轟飛宇宙了。
被你自己的言語之力所震憾後,你於是上山請益於灰鬍子們(灰鬍子是一群修煉龍吼的武僧集團,他們自從1500年前龍的暴政被推翻後就閉關於上山與世隔絕、與世無爭),
而你得知了自己居然是一個Dovahkiin後,你於是和灰鬍子們一起待在山上修煉龍吼,過了一年你儼然成為了一名實力超越灰鬍子的龍吼高手。

精通多句龍吼,並且洞悉龍吼的真諦後,你發現龍吼其實是一種藉由聲音發動的法術,該法術會運用聲音影響自身的狀態,
再透過自己去影響外界事物(例如冰凍敵人)或是改變自身的組成(例如使自身隱形)。
發現了嗎?影響自身的狀態,就是影響自己的身體,自己的細胞,自己的血液。並且龍吼是藉由聲音發動的,而聲音的本質是空氣的疏密波,也就是波動。波紋!
沒錯!龍吼和波紋氣功其實是一體兩面的!兩者都是藉由波動來引出血液中蘊藏的生命能量的技藝!1500年前的祖先們運用龍吼擊退龍,150年前的波紋戰士運用波紋擊敗柱汁男!
但是波紋戰士打敗柱汁男的經過就又是另一個故事了...

以上都是廢話
以下開始是真正的題目

旅行銷售員問題描述的是:給你n個城市,一個銷售員要從某一個城市出發,走遍每一個城市剛好一次,再回到他出發的城市,並求出最短的路徑。換言之求出一個權重最小的漢米頓迴路。
但是求出一個旅行銷售員問題的最佳解其實非常困難!! 因此今天我們不要求你求出最佳解,只要求你求出"次佳解"或"不錯的解"就可以了,當然如果你求出了最佳解那也一樣是可以接受的。

每筆測資的開頭有三個數字$z, n, t$分別代表測資編號,共有幾個城市,和此題的接受門檻。
接下來共有$n$行,對於第$i$行有兩個整數$x_i, y_i$代表第$i$個城市的座標。(城市編號從$0$開始數到$n-1$)

請輸出$n$個正整數代表依序經過的城市編號。
並且經過的總距離要不大於$t$此答案才會被接受。

反正就是輸出一個總距離小於等於$t$的漢米頓迴路啦~

平面座標上的兩點間距離公式:
d = sqrt(sqr(x1-x2)+sqr(y1-y2))

Input Format

每筆測資的開頭有三個數字$z, n, t$分別代表測資編號,共有幾個城市,和此題的門檻。
接下來共有$n$行,對於第$i$行有兩個整數$x_i, y_i$代表第$i$個城市的座標。
(城市編號從$0$開始數到$n-1$)

Output Format

請輸出$n$個正整數代表依序經過的城市編號。

Sample Input

[sample input 0]
0 3 10
0 0
1 0
0 1

[sample input 1]
1 8 20.000005
0 4
4 4
5 4
5 3
0 2
0 0
2 0
5 0

Sample Output

[sample output 0]
0 1 2

[sample output 1]
1 2 3 7 6 5 4 0

Hints

如果對於sample input 1的輸出是0 1 2 3 4 5 6 7,
則總距離會是$4 + 1 + 1 + \sqrt{26} + 2 + 2 + 3 + \sqrt{41} \gt 20.000005$,因此不會被接受為正確答案。

一個保證會AC前兩筆測資的程式:

#include <iostream>
#include <cmath>
int main()
{
   int z;
   std::cin >> z;
   if(z == 0)
      std::cout << "0 1 2" << std::endl;
   else
      std::cout << "1 2 3 7 6 5 4 0" << std::endl;
   return 0;
}

對於測資編號0,1: 同範例測資
對於測資編號2,3,4: $n = 8, 0 \leq x_i \leq 10, 0 \leq y_i \leq 10$
對於測資編號5: $n = 40, 0 \leq x_i \leq 100, 0 \leq y_i \leq 100$
對於測資編號6: $n = 40, 0 \leq x_i \leq 1000, 0 \leq y_i \leq 1000$
對於測資編號7: $n = 100, 0 \leq x_i \leq 2500, 0 \leq y_i \leq 2500$
對於測資編號8: $n = 200, 0 \leq x_i \leq 20, 0 \leq y_i \leq 20$
對於測資編號9: $n = 200, 0 \leq x_i \leq 15, 0 \leq y_i \leq 15$
對於測資編號10: $n = 200, 0 \leq x_i \leq 2500, 0 \leq y_i \leq 2500$
對於測資編號11: $n = 200, 0 \leq x_i \leq 100, 0 \leq y_i \leq 100000$

Problem Source

Subtasks

For Testdata: 0 ~ 1, Score: 0
For Testdata: 2 ~ 4, Score: 8
For Testdata: 5 ~ 6, Score: 18
For Testdata: 7 ~ 7, Score: 18
For Testdata: 8 ~ 9, Score: 24
For Testdata: 10 ~ 11, Score: 32
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144