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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2011-11-22 13:07:35

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Sorting

За умовою:
"N карток пронумеровані від 1 до N (1≤N≤32767)"
Що, начеб-то, означає "пронумеровані підряд (послідовно)", тобто 1 2 3 4 5 6, або 1 2 3 4 5 6 7 8 9 і т.д.

Але навіщо тоді фраза
"N попарно різних натуральних чисел"?
Як можна з пронумерованих підряд(послідовно) карток, знайти пару з однаковими номерами?

Питання:
Чи можливий такий варіант нумерації карток 1 1 2 2 3 3 (пронумеровано від 1 до 3)
і розташування їх після перетасовки в такому порядку 1 2 1 3 2 3 (попарно різні)

Відредаговано LVV (2011-11-22 13:39:30)


Вік живи - вік навчайся.

Поза форумом

 

#2 2011-11-22 14:37:22

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Sorting

У тому, що "занумеровані числами від 1 до N" та "попарно різні" справді є певна надлишковість, бо одне слідує з іншого. Але ж повтор однієї й тієї ж інформації не є помилкою, а комусь можливо буде так ясніше.

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

Якщо хочете -- забудьте про авторське формулювання і вважайте, що "дана перестановка, треба за мінімальну кількість обмінів отримати тотожню перестановку". Але чи буде так зрозуміліше учасникам-школярам?

Поза форумом

 

#3 2011-11-22 14:50:16

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Sorting

Ilya Porublyov написав:

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

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


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

Ilya Porublyov написав:

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

.

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


Вік живи - вік навчайся.

Поза форумом

 

#4 2011-11-22 16:45:26

Unknown
Новий користувач
Зареєстрований: 2011-10-28
Повідомлень: 31

Re: Sorting

Вы еще к буквам придирайтесь, вам же ясно условие.
Насчет вопроса в условии все сказано четко и ясно: "N попарно різних натуральних чисел"

Відредаговано Unknown (2011-11-22 16:46:57)

Поза форумом

 

#5 2011-11-22 17:08:32

SYPIAC
Новий користувач
Зареєстрований: 2011-11-22
Повідомлень: 1

Re: Sorting

Пример к задаче("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)

Поза форумом

 

#6 2011-11-22 17:42:17

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Sorting

SYPIAC написав:

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

Думаю, Вы неверно поняли условие, так как первое число - это количество карточек, а не номер карточки.


Вік живи - вік навчайся.

Поза форумом

 

#7 2011-11-28 15:14:22

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Sorting

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

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

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


Вік живи - вік навчайся.

Поза форумом

 

#8 2011-11-28 15:37:17

reiten
журі
Звідки: Киев
Зареєстрований: 2005-10-16
Повідомлень: 196

Re: Sorting

Я пусть и не автор, но могу сказать, что простор для совершенствования еще есть... раз этак в 100-200.


"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар

Поза форумом

 

#9 2011-11-28 15:39:40

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Sorting

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


Вік живи - вік навчайся.

Поза форумом

 

#10 2011-11-28 16:34:39

VIRUS
Новий користувач
Звідки: Днепропетровск
Зареєстрований: 2011-10-29
Повідомлень: 30

Re: Sorting

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


Чтобы найти баг, ты должен мыслить к как баг.

Поза форумом

 

#11 2011-11-28 17:01:48

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Sorting

LVV написав:

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

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

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

Поза форумом

 

#12 2011-11-28 17:03:23

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Sorting

VIRUS написав:

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

Під час дебагу ввід-вивід ведеться через файли. А вже перед відправкою переключається на консоль.

Поза форумом

 

#13 2011-11-28 18:37:28

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Sorting

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 придётся "немного" smile подождать.
Разумеется после отладки решения, эта часть кода заменяется на:

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

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


Вік живи - вік навчайся.

Поза форумом

 

#14 2011-11-28 18:42:00

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Sorting

LVV написав:

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

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


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

Відредаговано Dim_ov (2011-11-28 18:46:06)

Поза форумом

 

#15 2011-11-28 18:57:41

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Sorting

Dim_ov написав:

LVV написав:

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

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


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

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

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

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


Вік живи - вік навчайся.

Поза форумом

 

#16 2011-11-28 19:01:12

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Sorting

Вибачаюсь, здалося, що Ви random-seed скидаєте. smile

Але все одно, як на мене, краще таким чином нагенерувати тестів у файли, а потім уже ними користуватися для дебагу.

Поза форумом

 

#17 2011-11-28 19:37:35

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Sorting

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


Вік живи - вік навчайся.

Поза форумом

 

#18 2011-12-02 21:32:44

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Sorting

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

Поза форумом

 

#19 2011-12-03 01:02:06

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Sorting

LeonID написав:

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

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

Поза форумом

 

#20 2011-12-07 23:50:13

MrOlimp
Новий користувач
Зареєстрований: 2011-11-10
Повідомлень: 4

Re: Sorting

Серед задач другого туру є й ще легша=) З кодом у дві строки.

Поза форумом

 

#21 2011-12-08 06:55:27

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Sorting

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

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


Вік живи - вік навчайся.

Поза форумом

 

#22 2011-12-08 17:21:43

samus1c
Новий користувач
Зареєстрований: 2011-11-09
Повідомлень: 18

Re: Sorting

MrOlimp написав:

Серед задач другого туру є й ще легша=) З кодом у дві строки.

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

Поза форумом

 

#23 2011-12-08 17:36:03

il____
Новий користувач
Зареєстрований: 2011-12-08
Повідомлень: 10

Re: Sorting

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

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

Поза форумом

 

#24 2011-12-08 18:27:17

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Sorting

il____ написав:

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

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

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

Поза форумом

 

#25 2011-12-08 22:21:16

il____
Новий користувач
Зареєстрований: 2011-12-08
Повідомлень: 10

Re: Sorting

Dim_ov написав:

il____ написав:

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

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

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

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

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

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt