ами ще излезат от последната гонка 2А и 3А. Идеята е че в групата на победителя може да участват първите 3-ма, от групата на втория 2-ма тъй като има вече един по-бърз със сигурност, от групата на 3-ия 1 ...
Пак не разбирам. Как ще разбереш дали 4А и 5А са по-бързи от 1Б?
Ами не ни интересува дали 4А и 5А са по-бързи от 1Б. Те са 4-ти и 5-ти и не могат никога да бъдат някой от първите 3-ма.
Нали търсихме петте най-бързи. За трите най-бързи става със 7 да.
Там май разногласия няма. Народа се премести към 5 най-бързи, доколкото следя дискусията.
моя грешка, макар че 5 от 5 няма никаква "красота".
П.П. за 5 отговора е 9. Ако не ме премързи ще го разпиша с код за общия случай. Малко разнообразие в биченето на код.
За 5-те най-бързи според мен минимума е с 9 или 8 гонки в един от случаите.
Нека A1 е най-бързия след 6-те гонки, с които сме сортиране на матрицата.
Правим 7-мата гонка по "зелената линия" (като при определяне на 3-те най-бързи) от където определяме 2-рия и 3-тия при нас.
За тези двама най-бързи на 7-ма гонка по "зелената линия" имаме 4 варианта:
1. A2+A3
2. A2+B1
3. B1+B2
4. B1+C1
При 4-те случая правим следната операция: двамата най-бързи (2-ри и 3-ти при нас) ги махаме и shift-ваме надясно останалите на редовете им.
За първи вариант като махнем A2 и A3 shift-ваме само пъвия ред и е достатъчно да направим само 8-ма гонка на "зелената линия" и да вземем двата най-бързи за 4-ти и 5-ти т.е. става с 8 гонки.
Иначе в останалите три случая понеже сме махнали лидер (B1 или C1) трябва да сортираме матрицата по новите лидери преди да пуснем "зелената линия" за определяне на 4-ти и 5-ти т.е. те стават с 9 гонки общо.
Я па ти... Дай елаборейтни малко да видим как.
Звучи много добре, но кое ти гарантира, че B3 не е по-бърз от B1 или B2, а ти го изключваш. Всичко, което знаем е, че B1 е по-бавен от A1, и че B2 е по-бавен от A2, както и че B3 е по-бавен от A3. Също така A1 е по-бърз от A2, а A2 е по-бърз от A3. Но това не гарантира, че B1 е по-бърз от B2 или B3. Решението ти не обхваща общия случай. За частни случаи може да е вярно.
Моето предложение е да разпростреш зелената линия до B3, а не до C1. Т.е. седмото надбягване да бъде между B1,B2,B3,A2 и A3. Така получаваш втория най-бърз. В зависимост от коя колона е най-бързия шифтваш нагоре същата и правиш ново надбягване за определяне на третия аналогично. Така се получава 8 надбягвания за 3 най-бързи, и 10 за 5-те най-бързи.
P.S. Всъщност нищо не ти гарантира, че B4 или B5 не е по-бърз от B3. Пак се връщаме на моето първоначално решение за най-общия случай. Съжалявам, но с по-малко от 8 надбягвания за 3-те най-бързи и 10 за 5-те просто не става. Помислете малко и ще видите, че е така.
Е нали затова сме ги наредили така В1->В2->В3.. защото в тоя ред са пристигнали на гонката (В), как така "нишо не ни гарантира"?
Откъде ти хрумна, че с по-малко от 8 гонки за 3-те най-бързи не става ?
Това В1->В2->В3 откъде следва? Пристигнали са на надбягването на първите 5-торки след съответните A1,A2 и A3. Но за отношенията между времената на "B"-тата нищо не знаем. Очаквах по-високо ниво тук при всичките ви претенции.
Днес докато рецензирам проектите на гимназистите научих нещо ново, донякъде свързано с темата. Ще го пусна за всеки случай...
Девойчето, чиито проект чета в момента използва EasyCrypt за да провери дали upper- и lower bounds които е сметнала за алгоритъма й са верни.
И, сега ми остават само 22 проекта за следващите два дни.... :(
За да няма недоразумения, и понеже wqweto не го е изрично уточнил, ще отбележа, че приемам следното:
1.Колоните на матрицата отразяват първоначалните 5 надбягвания между произволни участници. Т.е. A1,B1,C1,D1,E1 са съответно участници в една от първите произволно избрани групи от по 5. 2.Подредбата, че A1 е по-бърз от A2 и т.н. следва от 6-тото надбягване. Това обаче гарантира само, че A1 е по-бърз от A2, A3 и т.н.. Не следва от това обаче, че B1 е по-бърз от B2. Надявам се сега да е станало ясно.
Сега след, като оябсни подробно всичко, ще обясниш твърдението си, че със 7 надбягвания не могат да се намерят 3-те най-бързи ?
A1,B1,C1,D1,E1 е групата на победителите, А1-5 е една първите произволно избрани групи. Ако приемем че горния десен ъгъл има индекси (1,1), а долния ляв (m,n) следва че минималната(най-близо до победата) позиция в класирането която може да има участника е m+n. Следстви на това може да премахнем всички които не могат да са в топ N. И като се има на предвид че като намерим победилтел вече търсим топ N-1.
Бях почнал да пиша пример с взети конкретни резултати от бягане на 5 км, но се отказах. След като сам казваш, че съм обяснил всичко подробно и пак не можеш да разбереш, защо да ти обяснявам повече?
Тук мисля един човек разбра моето решение и го оцени.
На всеки поотделно да обяснявам, трябва да ми плащате за частни уроци.