Формат за разпечатване

[Атанас Терзийски]

Хай фенове!

Ония ден на поредната бирена сбирка от няколко човека ни хрумна следната загадка: Как да свърши наздравицата най-бързо, като се "чукнат" всеки с всеки от присъстващите, със следните уточнения:
- всички порции наздравици се извършват едновременно;
- масата е окръжност, а феновете са точки по нея;
- наздравицата е отсечка между две точки, като по същото време не може да има друга такава отсечка, която да я пресича: няма преплитане на ръце;
- броя на точките (фенове) е n.

Всъщност аз помислих сериозно над това, но не успях да доведа решението до край, а може би и задачата да не е лека... знам ли :)

[VooDooMaN]

, честно ли точно това ви хрумна ?

[Атанас Терзийски]

Хаха :)
хрумването ми "дойде" когато се появиха колизии от кръстосани ръце, изчаквания и т.н. -- а бях жаден. Поста включва и част от разсъжденията ми, когато исках да реша задачата... та се наложи да я опроставам...
бе не е лека, нали :)

[Jack Johnson]

Пиячи: n

Ако n е нечетно: най-оптимален брой наздравици = n

Ако n е четно: най-оптимален брой наздравици = n - 1 (обаче с кръстоска)

Подробностите по описанието на алгоритъма оставям на Ники Вълчанов, който може да даде идея как евентуално да се премахне кръстоската при четен брой фенове на бира.

[Атанас Терзийски]

Ако пиячите са n, не може и наздравиците да са n, а повече по няква формула, която не мога да си измисля, но:
Ако имаме пиячи /// наздравеци то изглежда така:
1 /// 0
2 /// 2
3 /// 3
4 /// 6
5 /// 10
...
т.е. това са ръбовете в графа или свързване на всички точки (с всички) или просто броя на звъновете на чашите при чукането им :)

[Jack Johnson]

- всички порции наздравици се извършват едновременно;

Ако имаме 4 души, които са седнали на четирите ръба на един квадрат, то тогава:

1 --- 2
|      |
4 --- 3

Наздравица 1: 1 с 2, 3 с 4
Наздравица 2: 1 с 3, 2 с 4 (преплитане)
Наздравица 3: 1 с 4, 2 с 3

[Атанас Терзийски]

А 2 и 4 ... и ... 1 и 3 няма ли да го направят?

[Jack Johnson]

Алгоритъмът е древногръцки, не помня кой точно го е измислил, но ето каква е идеята:

Върху една окръжност на равни разстояния пореждаме n на брой точки. Номерираме ги последователно от 1 до n.

Свързваме точка 1 с точка n. Свързваме всички останали точки така, че да са успоредни на първата линия, т.е. свързваме 2 с n - 1, 3 с n - 2, 4 с n - 3 и т.н.

Ето тук изникват двата подслучая с четните и нечетните:

Ако n е нечетно, тогава винаги остава една точка, която не може да се свърже с останалите. Тази точка "почива" в този рунд. При първия рунд (наздравица), тази точка е (n + 1) / 2.

Ако n е четно, тогава след първата стъпка имаме окръжност, нарязана от n / 2 на брой хорди, разположени успоредно една спрямо друга.

Дотук беше лесното!

При втория рунд (наздравица) свързваме (1 : n - 1), (2, n - 2), (3, n - 3) и т.н. Отново възникват двата подслучая:

Ако n e нечетно, тогава във втори рунд точка n почива. В следващите рундове свързваме първо (1 : n - 2), на следващия (1 : n - 3) и т.н., докато точка 1 не изреди всички останали точки. Гледаме колко рунда сме направили и това ни е броя на наздравиците - 1. Последната наздравица е тази, при която точка 1 почива и свързваме (2 : n), (3, n - 1)... По този начин общият брой наздравици е точно числото n.

Ако n е четно, тогава се случва същото, както и при горния случай, с тази разлика, че от втори рунд нататък винаги остават две точки, които не могат да се свържат успоредно спрямо останалите. Но ако и те се свържат, тогава следвайки последователните стъпки, описани по-горе, стигаме до извода, че при четно n броят на наздравиците е n - 1.

Ха наздраве! Който успее да оптимизира кръстоската при четен брой пиячи е гений! Или просто ще ходим да пием бира винаги в нечетен брой!

[BORIME4KA]

Ето ви решение...

http://psabev.blogspot.com/2006/07/blog-post_10.html#links

[Атанас Терзийски]

Фенове: Иван Давидов и BORIME4KA,
луди сте!! Супер яко, чесно -- много се накефих ;-) - имате по бира от мен при следващата ни среща - само се обадете като сте из района на ПУ...

[Jack Johnson]

BORIME4KA,

Мисля, че грешиш за нечетните: според мен броят на наздравиците не е n * (n - 1), ами си е точно n - нито повече, нито по-малко. Ако си харесаме дадена точка и при последователните наздравици я свързваме с все по-отдалечаващите се съседни точки, а останалите точки ги свързваме успоредно, тогава на (n - 1)-вата наздравица първоначалната точка ще се здрависа с всички останали. Остава само да направим още една итерация, при която да изключим първата тока, да свържем двете най-близки около нея и след това да прекараме всички останали линии успоредно на първата линия.

Пример:

n = 5

1) 1:5, 2:4, 3 почива
2) 1:4, 2:3, 5 почива
3) 1:3, 4:5, 2 почива
4) 1:2, 3:5, 4 почива
5) 2:5, 3:4, 1 почива

При всяка наздравица отсечките последователно образуват пълен граф => всеки се здрависва с всеки, така че ще си позволя да направя следната корекция:

    * ако програмист може да вдигне наздравица с няколко програмиста едновременно: n-1
    * ако програмист може да вдигне наздравица само с един човек при четно n: n
    * ако програмист може да вдигне наздравица само с един човек при нечетно n: n(!)

Извод: При n на брой пиячи оптималният брой наздравици според гореспоменатите изисквания е n, независимо от броя им, при положение, че n >= 2.

[BORIME4KA]

Приема се 

ksx, само Ванката ще черпиш май...