Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TORCH - Rước đuốc Olympic

Olympic Bắc Kinh 2008 đang diễn ra vô cùng sôi nổi và quyết liệt. Ngay từ lúc này, những nhà tổ chức của Olympic London 2012 đã tính đến kế hoạch cho lễ rước đuốc của Olympic lần tới. Họ dự định sẽ đi qua N thành phố. Mỗi thành phố có tọa độ (x, y) trên mặt phẳng. Kế hoạch của lễ rước đuốc là ngọn đuốc sẽ bắt đầu từ thành phố 1, đi lần lượt giữa các thành phố khác mỗi thành phố đúng 1 lần rồi quay trở lại thành phố 1. Bạn hãy tìm một hành trình để tổng đường đi là nhỏ nhất.

Dữ liệu

  • Dòng thứ nhất ghi số N.
  • N dòng tiếp theo, mỗi dòng ghi một cặp số (x, y) là tọa độ của các thành phố

Kết quả

  • Dòng đầu tiên ghi độ dài của hành trình có đường đi ngắn nhất mà bạn tìm được với ít nhất 3 chữ số sau dấu phẩy.
  • Dòng thứ hai ghi N số bắt đầu bằng số 1 và tiếp theo là lần lượt các thành phố trên hành trình.

Giới hạn

  • 1 ≤ N ≤ 100
  • Tọa độ các thành phố có trị tuyệt đối không quá 105.

Ví dụ

Dữ liệu
4
0 0
1 0
0 5
1 5

Kết quả 1
12.0000
1 2 4 3	

Kết quả 2
20.1980
1 4 2 3	

Kết quả 3
12.1980
1 2 3 4

Cách tính điểm

Với mỗi test, ban tổ chức có đưa ra một đáp số ExpectedResult. Gọi kết quả của bạn là Result.

  • Nếu Result ≤ ExpectedResult bạn sẽ được 10 điểm.
  • Nếu ExpectedResult < Result < 1.5 × ExpectedResult bạn sẽ được 9 – 1.5(Result – ExpectedResult) / 25
  • Ngoài ra, bạn sẽ không được điểm.

Với test ví dụ ở trên, với ExpectedResult = 12, output 1 sẽ được 10 điểm, output 2 sẽ được 0 điểm, output 3 sẽ được 7.997 điểm.


Được gửi lên bởi:VOJ Team
Ngày:2008-08-09
Thời gian chạy:0.600s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ADA95 ASM32 BASH BF C CSHARP C99 CLPS LISP clisp LISP sbcl D ERL FORTRAN GOSU HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PERL PERL6 PHP PIKE PRLG-swi PYTHON PYPY RUBY RUST SCM guile SCM qobi SED ST WHITESPACE
Nguồn bài:HAOI 2008 - Day 2 - Author: Lê Đôn Khuê

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.