Бодолт илгээх | Бүх бодолтууд | Шилдэг бодолтууд | Жагсаалт руу буцах |
CSMS0068 - Үндэс |
1-ээс N (N ≥ 2) хүртлэх тоонуудаар дугаарлагдсан N ширхэг оройнууд бүхий модыг (өөрөөр хэлбэл циклгүй граф) авч үзье. Уг модны хувьд Прюферийн кодыг дараах аргаар байгуулдаг: төгсгөлийн оройнуудаас (модонд ганц ирмэгээр холбогдож байгаа оройнуудаас) хамгийн бага дугаартай оройг сонгон авна. Дараа нь энэ оройг болон түүнийг модтой холбож байсан ирмэгийг устгаж, уг ирмэгийн нөгөө үзүүрт модонд үлдэж байгаа оройн дугаарыг бичнэ. Үлдэж байгаа модны төгсгөлийн оройнуудын дотроос хамгийн бага дугаартайг нь сонгон авч, устгах гэх мэтээр модонд ганц орой үлдтэл үргэлжлүүлнэ. Хамгийн сүүлд үлдэж байгаа оройн дугаар N байх нь илэрхий. Бичигдсэн 1-ээс N хүртлэх утгатай N-1 ширхэг тоонуудыг анхны модны Прюферийн код гэж нэрлэнэ. Таны даалгавар бол хамгийн олон ирмэг гарсан байх оройн дугаарыг олох явдал юм. Ийм орой олон байвал хамгийн бага дугаартайг нь хэвлэнэ. 2 ≤ N ≤ 7500 гэж үзнэ.
Input
Оролт дээр ямар нэг модны Прюферийн код өгөгдөнө. Тоонууд нэг нэг мөрөнд өгөгдөнө.
Output
Хамгийн олон ирмэг гарсан оройн дугаарыг хэвлэнэ. Ийм орой олон байвал хамгийн бага дугаартайг нь хэвлэнэ.
Example
Input: 2 1 6 2 6 Output: 2
Нэмсэн: | sw40 |
Огноо: | 2009-02-20 |
Хугацааны хязгаарлалт: | 0.208s |
Эх кодын хэмжээний хязгаарлалт: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Програмчлалын хэлүүд: | Бүгд дараах хэлүүдээс бусад: ADA95 ASM64 BASH BF C++ 4.3.2 C99 CLPS CLOJURE D ERL FSHARP GO ICON ICK JS-RHINO LUA NEM NICE NODEJS OCAML PERL6 PIKE PRLG-swi SCALA SCM guile SCM qobi SED ST TCL VB.NET WHITESPACE |
Эх сурвалж: | ? |
hide comments
2014-09-14 09:34:35 batorshih
N-iin hyazgaar 100000 yum bna |
|
2011-01-12 13:45:08 Almabek[SMCS]
http://en.wikipedia.org/wiki/Prufer_sequence |
|
2009-02-23 11:14:07 sw40
Жишээн дээрх графын холболтын жагсаалт: 1: 4 6 2: 3 5 6 3: 2 4: 1 5: 2 6: 1 2 |
|
2009-02-23 06:53:33 osb
neg sn zuragtai tailbarlaad ogooch tehu |