Welcome Guest ( Log In | Register )

Help | Search | Members | Calendar

Pages: (4) 1 [2] 3 4   ( Go to first unread post )
Задачка из олимпиады
« Next Oldest | Next Newest » Track this topic | Email this topic | Print this topic
Master of Puppets
Posted: Dec 20 2008, 15:00

Eye of the Vision

Group: Moderator
Member No.: 2067

Joined: August 29, 2006

QUOTE (In the immortal words of nop, since Dec 20 2008, 14:22...)
А почему Гамильтонов цикл?
Не может быть такая комбинация, что вершины повторяются, а суммарный вес минимальный?

Потому что в каждом городе нужно побывать ровно один раз.

Не забывайте, что Бильбо должен выйти из города с номером 1, побывать в каждом городе ровно по одному разу и только в конце путешествия вернуться в город с номером 1.


--------------------
Master of Puppets, I'm pulling your strings, twisting your mind and smashing your dreams!
⠠⠵
 
       Top
nop
Posted: Dec 20 2008, 15:14

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

Да, сорри smile.gif

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
firewall
Posted: Dec 20 2008, 23:12

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

QUOTE (In the immortal words of Master of Puppets, since Dec 20 2008, 13:48...)
В заданном полном неориентированном графе найти Гамильтонов цикл с минимальным весом. Книжка Скиены Programming Challenges тебе поможет.

мм.. как думаешь по времени пройдет? tongue.gif biggrin.gif

--------------------
Newbie(g)
 
     Top
Master of Puppets
Posted: Dec 21 2008, 00:48

Eye of the Vision

Group: Moderator
Member No.: 2067

Joined: August 29, 2006

QUOTE (In the immortal words of firewall, since Dec 20 2008, 23:12)
мм.. как думаешь по времени пройдет? tongue.gif biggrin.gif

хз... 1000 вершин вроде бы не так уж много, гамильтонов цикл ищется бэктрекингом afaik... можно попробовать свести задачу к задаче на эйлеров цикл.

--------------------
Master of Puppets, I'm pulling your strings, twisting your mind and smashing your dreams!
⠠⠵
 
       Top
knightmare
Posted: Dec 21 2008, 01:17

Wise Dreamer

Group: Elite Member
Member No.: 1572

Joined: October 31, 2005

Все гамильтоновы циклы в полном графе - это все перестановки всех вершин. Это и есть перебор. N! опрераций (нахождения и сравнения длин). Ну (N-1)! в условиях этой задачи, но это не важно. Это не решение.


для справки: 1000! = 4,02387260077093773543702433923e+2567

--------------------
армия - эта крута, армейский спецназ - эта ваще крута


Хочу трахнуть Nissan Skyline R34, и ездить на Alessandra Ambrosio
 
    Top
DZUK
Posted: Dec 21 2008, 11:27

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

Слегка модифицированный алгоритм Дейкстры не прокатит? Будет время, подумаю, что означает "слегка":)

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
nop
Posted: Dec 23 2008, 00:13

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

Думаю решение задачи гораздо проще, чем нахождение Гамильтонова цикла...

2 knightmare
А вот и точное значение: biggrin.gif
402387260077093773543702433923003985719374864210714632543799910429938512398629
020592044208486969404800479988610197196058631666872994808558901323829669944590
997424504087073759918823627727188732519779505950995276120874975462497043601418
278094646496291056393887437886487337119181045825783647849977012476632889835955
735432513185323958463075557409114262417474349347553428646576611667797396668820
291207379143853719588249808126867838374559731746136085379534524221586593201928
090878297308431392844403281231558611036976801357304216168747609675871348312025
478589320767169132448426236131412508780208000261683151027341827977704784635868
170164365024153691398281264810213092761244896359928705114964975419909342221566
832572080821333186116811553615836546984046708975602900950537616475847728421889
679646244945160765353408198901385442487984959953319101723355556602139450399736
280750137837615307127761926849034352625200015888535147331611702103968175921510
907788019393178114194545257223865541461062892187960223838971476088506276862967
146674697562911234082439208160153780889893964518263243671616762179168909779911
903754031274622289988005195444414282012187361745992642956581746628302955570299
024324153181617210465832036786906117260158783520751516284225540265170483304226
143974286933061690897968482590125458327168226458066526769958652682272807075781
391858178889652208164348344825993266043367660176999612831860788386150279465955
131156552036093988180612138558600301435694527224206344631797460594682573103790
084024432438465657245014402821885252470935190620929023136493273497565513958720
559654228749774011413346962715422845862377387538230483865688976461927383814900
140767310446640259899490222221765904339901886018566526485061799702356193897017
860040811889729918311021171229845901641921068884387121855646124960798722908519
296819372388642614839657382291123125024186649353143970137428531926649875337218
940694281434118520158014123344828015051399694290153483077644569099073152433278
288269864602789864321139083506217095002597389863554277196742822248757586765752
344220207573630569498825087968928162753848863396909959826280956121450994871701
244516461260379029309120889086942028510640182154399457156805941872748998094254
742173582401063677404595741785160829230135358081840096996372524230560855903700
624271243416909004153690105933983835777939410970027753472000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
Master of Puppets
Posted: Dec 23 2008, 01:12

Eye of the Vision

Group: Moderator
Member No.: 2067

Joined: August 29, 2006

2 nop- [offtop] Mathematica 5 rules? wink.gif[/offtop]

--------------------
Master of Puppets, I'm pulling your strings, twisting your mind and smashing your dreams!
⠠⠵
 
       Top
firewall
Posted: Dec 23 2008, 03:07

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

2 nop - проще? в каком смысле? если ты о временной сложности, то это было понятно из условий biggrin.gif

новая задачка: напишите программу, которая считает сколько нулей в конце факториала очень большого числа smile.gif

--------------------
Newbie(g)
 
     Top
knightmare
Posted: Dec 23 2008, 03:59

Wise Dreamer

Group: Elite Member
Member No.: 1572

Joined: October 31, 2005

QUOTE (In the immortal words of firewall, since Dec 23 2008, 03:07)
новая задачка: напишите программу, которая считает сколько нулей в конце факториала очень большого числа smile.gif

кстати!..

--------------------
армия - эта крута, армейский спецназ - эта ваще крута


Хочу трахнуть Nissan Skyline R34, и ездить на Alessandra Ambrosio
 
    Top
DZUK
Posted: Dec 23 2008, 07:46

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

тюююю, фигня. Надо посчитать скока двоек и пятерок до него в числахsmile.gif

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
firewall
Posted: Dec 23 2008, 10:33

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

QUOTE (In the immortal words of firewall, since Dec 23 2008, 03:07...)
...напишите программу...

<Content removed by the moderator due to low informational level>

This post has been edited by firewall on Dec 23 2008, 16:04

--------------------
Newbie(g)
 
     Top
DZUK
Posted: Dec 23 2008, 15:54

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

Писал один раз, так что не интересно.

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
DZUK
Posted: Dec 23 2008, 16:08

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

CODE

#include <iostream>
int main()
{
int n, c=0, i, t;
std::cin>>n;
if (n<5)
{
 std::cout<<"0\n";
 return 0;
}

for (i=5;i<=n;i++)
{
 t=i;
 while (t%5==0)
 {
  t/=5;
  c++;
 }
}
std::cout<<c<<"\n";
return 0;
}


правдо особо не тестил.

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
firewall
Posted: Dec 23 2008, 16:23

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

QUOTE

#include <iostream>
using namespace std;
int main() {
int n, l = 0;
cin >> n;
while (n) {
  n /= 5;
  l += n;
}
cout << l << endl;
return 0;
}


--------------------
Newbie(g)
 
     Top
firewall
Posted: Dec 23 2008, 16:24

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

QUOTE (In the immortal words of DZUK, since Dec 23 2008, 16:08)
правдо особо не тестил.

+1 )

--------------------
Newbie(g)
 
     Top
nop
Posted: Dec 23 2008, 17:40

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

2 Master of Puppets
[offtop] Of Course, откуда узнал, что это 5-ая версия? smile.gif [/offtop]

2 firewall
В прямом смысле... Нет необходимости свести задачу к нахождению Гам. цикла...

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
Master of Puppets
Posted: Dec 23 2008, 17:51

Eye of the Vision

Group: Moderator
Member No.: 2067

Joined: August 29, 2006

QUOTE (In the immortal words of nop, since Dec 23 2008, 17:40)
2 Master of Puppets
[offtop] Of Course, откуда узнал, что это 5-ая версия? smile.gif [/offtop]

2 firewall
В прямом смысле... Нет необходимости свести задачу к нахождение Гам. цикла...

Потому что у нас универе на всех почти компах этот Mat5 стоит, он очень распространен сейчас. Ты случайно не из Славянского?

--------------------
Master of Puppets, I'm pulling your strings, twisting your mind and smashing your dreams!
⠠⠵
 
       Top
firewall
Posted: Dec 23 2008, 18:04

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

QUOTE (In the immortal words of nop, since Dec 23 2008, 17:40)
2 firewall
В прямом смысле... Нет необходимости свести задачу к нахождение Гам. цикла...

ладно, понял.... только все-равно написать программу для этой задачи сложнее чем для Гам. цикла

--------------------
Newbie(g)
 
     Top
DZUK
Posted: Dec 23 2008, 18:28

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

QUOTE (In the immortal words of firewall, since Dec 23 2008, 17:23)
QUOTE

#include <iostream>
using namespace std;
int main() {
int n, l = 0;
cin >> n;
while (n) {
  n /= 5;
  l += n;
}
cout << l << endl;
return 0;
}

а это не равно случайно [n/5]*n, где [] ознчают целую часть?

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
66 replies since Oct 20 2008, 19:29 Track this topic | Email this topic | Print this topic
Pages: (4) 1 [2] 3 4 
<< Back to Programming languages

 




Arminco Global Telecommunications