Форум Всеукраїнської інтернет-олімпіади NetOI

Ilya Porublyov написав:

... словосполучення "попарно різні" має у математиці (в тому числі й у шкільній) цілком конкретний смисл, який робить послідовність "1 2 1 3 2 3" недопустимою.

Ну, згоден з Вами лише частково, бо, якщо враховувати послідовність запису чисел (що цілком припустимо, наприклад, коли мова йде про упорядкування масиву, чи про координати на площині), то в комбінації 1 2 1 3 2 3 Ви не знайдете жодних упорядкованих  однакових пар чисел (або жодної однакової координати)


За роз'яснення умови дякую.

Ilya Porublyov написав:

...справді є певна надлишковість...

.

Відредаговано LVV (2011-11-22 15:41:10)

Пример к задаче("5  2  5  1  3  4") возможно сортировать за 3 хода:
525134->(меняем местами №4 и №1) 125534->(меняем местами №5 и №3) 123554->(меняем местами №6 и №4) 123455
Но в ответе к задаче указано "4".
Это ошибка в ответе к примеру, или я неправильно понимаю условие задачи?

Відредаговано SYPIAC (2011-11-22 17:09:19)

Проц. 1,6 ГГц.
Затраты времени на тест из 32767 карточек около 4 секунд.
Есть кто-то, у кого побыстрее (с учетом "железа")?

А может автор поделится лимитом времени авторского решения?

Відредаговано LVV (2011-11-28 15:21:15)

Спасибо. Будем искать. "В лоб" не прокатило...

LVV написав:

Спасибо. Будем искать. "В лоб" не прокатило...

У нас, мабуть, різні "лоби", бо моє рішення "в лоб" працюе ~20мс.

Залізо, звісно, відрізняється, але не настільки, щоб різниця була аж такою(Core2Duo 2.33 GHz)

VIRUS написав:

А каким образом вы вводите 32767 значений?

Ну, кроме предложенного Dim_ov, еще можно, например, вместо ввода с клавиатуры всякий раз создаватьть неповтряющийся массив псевдослучайных номеров. Примерно так (С++):

// N-количество номеров(карточек)
for(int i=1; i<=N; i++)
{
a: n[i]=1+rand()%N;
for (int j=1; j<i; j++)
if (n[i]==n[j]) goto a;
}

Правда, при N=32767 придётся "немного" подождать.
Разумеется после отладки решения, эта часть кода заменяется на:

for(int i=1; i<=N; i++)
{
cin >> n[i]
}

Відредаговано LVV (2011-11-28 18:43:16)

Dim_ov написав:

LVV написав:

Ну, еще можно, например, вместо ввода с клавиатуры всякий раз создаватьть неповтряющийся массив псевдослучайных номеров. Примерно так (С++):

але такий спосіб абсолютно непридатний для відладки рішення чи перевірки його на правильність. Тільки дозволить поміряти час виконання, та й то, не завжди точно(залежно від способу виміру).


Особливо шкідливо, як на мене,  для новачків. Великі тести повинні бути статичними. Це дозволить дуже легко виявити "гейзенбаги" внаслідок виходу за границі масиву чи неініціалізованих змінних - вивід на цей однаковий великий тест іноді буде різним.

Я щось не зрозумів, ви проти статичних тестів, чиза них.
В мене якраз і запропоновано створення статичного масиву. А з псевдовипадкового набору на випадковий перейти легко за допомогою srand. До того ж можна швиденько перевірити і на впорядкованих масивах змінивши пару рядків коду.

Як на мене, це простіше, ніж організовувати роботу з файлами, а потім відміняти її. До того ж, для заповнення тих самих файлів, прийдеться виконати аналогічний запропонованому мною код. Чи Ви якось по іншому створюєте файли для перевірки?

Відредаговано LVV (2011-11-28 19:03:31)

Готов с Вами согласиться, на счет работы с файлами для новичков, только по той причине, что у нас (не знаю как у вас) все задания II и III тура олимпиад по информатике, построены на работе с файлами. Данные читаются из файлов и результаты выводяться в файлы. А значит есть смысл потренироваться лишний раз работать с файлами.

LeonID написав:

Дуже легка задача, раніше на другому етапі були набагато складніші умови.

Може ще на 3-4 турі "відіграються"

Я лише другий рік тут. Досвід невеликий. Але вважаю, що задачі подібного рівня мають таки тут бути. Не забувайте, що це перш за все олімпіада для школярів. І нехай на заочних турах це лише теоретично, бо проконтролювати сторонню допомогу учасникам ніхто не в змозі. Та все таки, добре, коли деякі завдання 9-10 класники в змозі виконати самостійно (чи майже самостійно, після певної підказки дорослих). Це підбадьорює їх. 
Статистика покаже, чи легкі завдання, чи ні. Доречі, здається мені, що задача Platforms зовсім не така вже й легка (хоч може просто я ще не докумекав до оригінального її рішення).

Відредаговано LVV (2011-12-08 12:08:07)

Та че там, давайте сразу решения!
Если вы нашли легкое решение, то не надо про него всем говорить

Відредаговано il____ (2011-12-08 17:36:15)

Dim_ov написав:

il____ написав:

Та че там, давайте сразу решения!
Если вы нашли легкое решение, то не надо про него всем говорить

Розумію ваш страх перед тим, що зараз всі ваші конкуренти прочитають повідомлення MrOlimp`а і РАПТОВО розв’яжуть задачу краще за вас, але запевняю, цього не станеться

По-перше, саме рішення не прозвучало. По-друге, якщо попереднє обговорення з ТЛ могло хоча-б дати натяк на те, як повинна працювати програма, і до чого треба прагнути, то вислів про дві строчки коду не дає жодних підказок. У багатьох задачах повний перебір можна написати в одну строчку, але пройде таке рішення також один-два тести Ну і насамкінець, не факт, що те двох-строчкове рішення вірне(в усякому разі до оголошення результатів)

Просто я сам зробив программу у дві строки, але якщо ж не так було б, то я бзадумався над рішенням

Відредаговано il____ (2011-12-09 19:57:54)