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


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

Ви не зайшли.

#1 2009-07-19 21:38:28

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Задача CORSIAR

В умові сказано:

... кількість скарбів N(1<=K<=20)...

Вважаю за необхідне терміново уточнити в умові, що все-таки кількість скарбів N(3<=N<=20), бо у випадку одного скарбу - ми не рухаємось нікуди, так як точка старту і точка фінішу співпадають, а у випадку двох скарбів - ми рухатимось по відрізку туди й назад і визначити напрям обходу строго математично неможливо, а що виводити у подібних випадках (коли напрямок обходу однозначно визначити неможливо) в умові не сказано.

Відредаговано Присяжнюк А.В. (2009-07-20 19:52:37)


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#2 2009-07-20 09:50:26

Журі_Пасіхов
Гість

Re: Задача CORSIAR

Уважно перечитиавши умову задачі, стверджую, що корегування вона НЕ ПОТРЕБУЄ.

 

#3 2009-07-20 12:33:23

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Задача CORSIAR

І все таки дозволю собі "посперечатись". Я (як і довільний інший учасник) не зобовязаний розвязувати задачу "авторським" способом.  smile
Нехай Маємо такі, коректні (за умовою), вхідні дані:
1
2 1 1 2 -1
Припустимо, що й нащадків було двоє.
Ось хід "думок" одного: "Діставшись до 2-го скарбу я повертався на 180 градусів через ліве плече і прямував назад. Значить я здійснював обхід проти годинникової стрілки."
Ось хід "думок" другого: "Діставшись до 2-го скарбу я повертався на 180 градусів через праве плече і прямував назад. Значить я здійснював обхід за годинниковою стрілкою."

Так як все таки вони здійснювали обхід: ЗА чи ПРОТИ годинникової стрілки?
Ще раз наголошую, що мене в даний момент не цікавлять ніякі формули та авторський розвязок... smile


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#4 2009-07-20 13:19:19

vitert
Новий користувач
Зареєстрований: 2009-07-20
Повідомлень: 4

Re: Задача CORSIAR

Присяжнюк А.В. написав:

І все таки дозволю собі "посперечатись". Я (як і довільний інший учасник) не зобовязаний розвязувати задачу "авторським" способом.  smile
Нехай Маємо такі, коректні (за умовою), вхідні дані:
1
2 1 1 2 -1
Припустимо, що й нащадків було двоє.
Ось хід "думок" одного: "Діставшись до 2-го скарбу я повертався на 180 градусів через ліве плече і прямував назад. Значить я здійснював обхід проти годинникової стрілки."
Ось хід "думок" другого: "Діставшись до 2-го скарбу я повертався на 180 градусів через праве плече і прямував назад. Значить я здійснював обхід за годинниковою стрілкою."

Так як все таки вони здійснювали обхід: ЗА чи ПРОТИ годинникової стрілки?
Ще раз наголошую, що мене в даний момент не цікавлять ніякі формули та авторський розвязок... smile

Цитата із задачі: "Швиденько діставшись на острів, вони обійшли всі схованки, рухаючись від однієї до іншої найкоротшим шляхом, а після цього вони опинилися там звідки почали свої пошуки..."

А звідки вони починали свої пошуки - із першої схованки, чи із початку координат?

Присяжнюк А.В. написав:

а у випадку двох скарбів - ми рухатимось по відрізку туди й назад і визначити напрям обходу строго математично неможливо

І у видадку трьох скарбів ми можемо рухатись по відрізку туди і назад, і у випадку 4,5 -1000 - адже ці точки можуть лежати на одній прямій. Алеж є ще одна цитата із задачі "стежки, які вони натоптали ніде не перитинаються".
Але згоден якщо пошук починаєтья із першої схованки і вертаються в першу схованку, то не зрозуміло у випадку 2 чи 1 схованки, якщо ж пошук із початку координат і вертаються в початок координат, то як бути коли одна схованка?

Відредаговано vitert (2009-07-20 13:26:39)

Поза форумом

 

#5 2009-07-20 13:55:14

badm
Новий користувач
Зареєстрований: 2009-06-24
Повідомлень: 3

Re: Задача CORSIAR

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

Поза форумом

 

#6 2009-07-20 14:03:39

badm
Новий користувач
Зареєстрований: 2009-06-24
Повідомлень: 3

Re: Задача CORSIAR

А можна і ще простіше.. але то буде не цікаво

Поза форумом

 

#7 2009-07-20 15:17:47

Журі_Пасіхов
Гість

Re: Задача CORSIAR

Присяжнюк А.В. написав:

І все таки дозволю собі "посперечатись". Я (як і довільний інший учасник) не зобовязаний розвязувати задачу "авторським" способом.  smile
Нехай Маємо такі, коректні (за умовою), вхідні дані:
1
2 1 1 2 -1
Припустимо, що й нащадків було двоє.
Ось хід "думок" одного: "Діставшись до 2-го скарбу я повертався на 180 градусів через ліве плече і прямував назад. Значить я здійснював обхід проти годинникової стрілки."
Ось хід "думок" другого: "Діставшись до 2-го скарбу я повертався на 180 градусів через праве плече і прямував назад. Значить я здійснював обхід за годинниковою стрілкою."

Так як все таки вони здійснювали обхід: ЗА чи ПРОТИ годинникової стрілки?
Ще раз наголошую, що мене в даний момент не цікавлять ніякі формули та авторський розвязок... smile

Из старого  анекдота (расценивайте как подскзку...) "и ты.... прав.... и ты прав..." :-)

 

#8 2009-07-20 19:44:59

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Задача CORSIAR

vitert написав:

А звідки вони починали свої пошуки - із першої схованки, чи із початку координат?

Про це в умові задачі також нічого не сказано... smile
Я ставши "потомком джентельменів удачі" у їх роздумах припускав, що з першої схованки, оскільки це не проблематично, так як існує паралельний перенос - хто мені заважає перенести першу схованку у початок координат?

Журі_Пасіхов написав:

Из старого  анекдота (расценивайте как подскзку...) "и ты.... прав.... и ты прав..." :-)

Все классические алгоритмы, описанные в литературе, касающиеся определения направления обхода применяются к "НЕВЫРОЖДЕННОМУ N-угольнику, у которого НЕТ САМОПЕРЕСЕКАЮЩИХСЯ сторон".
Вторая часть этого ограничения была использована в условии - "...при цьому стежки, які вони натоптали, ніде не перетиналися..."
А вот для вырожденных случаев (N=1 и N=2) должно либо быть либо указание в условии задачи, что выводить, либо избавиться от них путем, предложенным мной в самом первом сообщении: "кількість скарбів N(3<=N<=20)"

Математика - наука точная и не терпит неопределенности.
Мы же здесь вроде как учимся решать олимпиадные задачи, а не играть в "Что? Где? Когда?"... smile

Відредаговано Присяжнюк А.В. (2009-07-20 19:52:18)


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#9 2009-07-20 21:10:34

vitert
Новий користувач
Зареєстрований: 2009-07-20
Повідомлень: 4

Re: Задача CORSIAR

Присяжнюк А.В. написав:

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

Так це не проблема, оскільки не впливає на результат обходу, але коли маємо наприклад 2 схованки то в перщому випадку це трикутик з яким усе зрозуміло, у другому пряма з якою не зовсім зрозуміло.

Журі_Пасіхов написав:

Из старого  анекдота (расценивайте как подскзку...) "и ты.... прав.... и ты прав..." :-)

Присяжнюк А.В. написав:

Все классические алгоритмы, описанные в литературе, касающиеся определения направления обхода применяются к "НЕВЫРОЖДЕННОМУ N-угольнику, у которого НЕТ САМОПЕРЕСЕКАЮЩИХСЯ сторон".
Вторая часть этого ограничения была использована в условии - "...при цьому стежки, які вони натоптали, ніде не перетиналися..."
А вот для вырожденных случаев (N=1 и N=2) должно либо быть либо указание в условии задачи, что выводить, либо избавиться от них путем, предложенным мной в самом первом сообщении: "кількість скарбів N(3<=N<=20)"

Математика - наука точная и не терпит неопределенности.
Мы же здесь вроде как учимся решать олимпиадные задачи, а не играть в "Что? Где? Когда?"... smile

Повністю згоден, хоча ніколи не читав про класичні алгоритми, а мабуть уже пора. Оскільки задача коректна то я припускаю мається на увазі таке:
1 схованка - відповідь будь-яка буде правильна
2 схованки - бути не може окільки це суперечить "...при цьому стежки, які вони натоптали, ніде не перетиналися...", "...рухаючись від однієї до іншої найкоротшим шляхом...". Хоча співпадання не є перетином? Тоді також будь-яка відповідь правильна.
Починали мабуть все-таки із 1 схованки - але також не факт???

Відредаговано vitert (2009-07-20 21:30:26)

Поза форумом

 

#10 2009-07-20 22:54:07

CUPIDON
Новий користувач
Зареєстрований: 2009-06-12
Повідомлень: 25

Re: Задача CORSIAR

Ну,шановні журі, то звідки пірати починають свій маршрут?! І, якщо з початку координат, то як бути у випадку з 1 схов.?(Стежки не перетинаються). або, якщо з 1 схованки, то як бути у випад. 2 схов.? Тому раджу зробити так, як пропонує Присяжнюк А.В.!

Поза форумом

 

#11 2009-07-21 08:02:00

Журі_Пасіхов
Гість

Re: Задача CORSIAR

Щоб зняти цю дискусію і не занурюватися  в різні  інтерпретації вироджених випадків, "спрощуємо" життя - накладаємо умову. яку пропонує п.Присяжнюк -кількість скарбів N(3<=N<=20)"
Відповідне повідомлення учасникам буде надіслано.

 

#12 2009-07-21 08:16:00

Журі_Пасіхов
Гість

Re: Задача CORSIAR

CUPIDON написав:

Ну,шановні журі, то звідки пірати починають свій маршрут?

Відповіді немає.

 

#13 2009-07-21 16:01:14

vitert
Новий користувач
Зареєстрований: 2009-07-20
Повідомлень: 4

Re: Задача CORSIAR

Журі_Пасіхов написав:

CUPIDON написав:

Ну,шановні журі, то звідки пірати починають свій маршрут?

Відповіді немає.

Журі_Пасіхов написав:

Щоб зняти цю дискусію і не занурюватися  в різні  інтерпретації вироджених випадків, "спрощуємо" життя - накладаємо умову. яку пропонує п.Присяжнюк -кількість скарбів N(3<=N<=20)"

В цьому випадку зрозуміло що починають із першої схованки.

Поза форумом

 

#14 2009-07-21 18:05:35

CUPIDON
Новий користувач
Зареєстрований: 2009-06-12
Повідомлень: 25

Re: Задача CORSIAR

vitert написав:

Журі_Пасіхов написав:

Щоб зняти цю дискусію і не занурюватися  в різні  інтерпретації вироджених випадків, "спрощуємо" життя - накладаємо умову. яку пропонує п.Присяжнюк -кількість скарбів N(3<=N<=20)"

В цьому випадку зрозуміло що починають із першої схованки.

Ну, дозволь не погодитись! це дуже важливо, оскільки в тесті
1
3 5 1 3 2 3 4
можливі обидві відповіді, залежно від початку:
якщо з початку кординат-проти год.стр, а якшо з 1 схов, то за.. дилема..

Журі_Пасіхов написав:

немає відповіді

як вже було вищесказано:

математика - точна наука і не терпить неточності...

тому, шановні судді, прошу вас дати чітку відповідь на це питання.

Поза форумом

 

#15 2009-07-22 17:21:49

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Задача CORSIAR

Ще раз уважно вчитався в умову і розглянув наведений контрприклад...

Шановний CUPIDON правий, тут дійсно потрібно в умові уточнити, що "пірати завжди розпочинали свій шлях з ПЕРШОЇ схованки".

"Брут, ты мне брат, но истина - дороже"... smile


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#16 2009-07-22 18:06:22

Журі_Пасіхов
Гість

Re: Задача CORSIAR

CUPIDON написав:

vitert написав:

Журі_Пасіхов написав:

Щоб зняти цю дискусію і не занурюватися  в різні  інтерпретації вироджених випадків, "спрощуємо" життя - накладаємо умову. яку пропонує п.Присяжнюк -кількість скарбів N(3<=N<=20)"

В цьому випадку зрозуміло що починають із першої схованки.

Ну, дозволь не погодитись! це дуже важливо, оскільки в тесті
1
3 5 1 3 2 3 4
можливі обидві відповіді, залежно від початку:
якщо з початку кординат-проти год.стр, а якшо з 1 схов, то за.. дилема..

Журі_Пасіхов написав:

немає відповіді

як вже було вищесказано:

математика - точна наука і не терпить неточності...

тому, шановні судді, прошу вас дати чітку відповідь на це питання.

НЕМАЄ ВІДПОВІДІ.....
Але олімпіада навчальна...., тому цитата з умови (для особливо уважних :-) 

Спочатку ви вводите з клавіатури одне число - кількість контрольних прикладів К (1<=K<=100), а тоді К разів читаєте з клавіатури кількість скарбів N(3<=N<=20) та N пар дійсних чисел - координати чергового скарбу (перше число - абсциса, друге - ордината).

 

#17 2009-07-22 19:11:22

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Задача CORSIAR

Журі_Пасіхов написав:

Спочатку ви вводите з клавіатури одне число - кількість контрольних прикладів К (1<=K<=100), а тоді К разів читаєте з клавіатури кількість скарбів N(3<=N<=20) та N пар дійсних чисел - координати чергового скарбу (перше число - абсциса, друге - ордината).

Мова йде про інше - в умові сказано

...Швиденько діставшись на острів, вони обійшли всі схованки...

Так от питання (не моє): куди вони дістались: до початку координат, чи першого скарбу, чи взагалі довільної точки.
Тобто, людей цікавить точка "висадки піратського десанту".... 
Мабуть для конкретної задачі це питання не є принциповим, але з точки зору дотримання технічних умов (як це прийнято на всіх олімпіадах високого рівня),  питання є принциповим і, мабуть, варте на відповідь і уточнення в умові.
Тут можна сперечатись, але, на жаль, правда буде на стороні запитуючої сторони... smile
Більше того, варто вказати, що скарби новоявлені пірати обходили у ПОРЯДКУ ПЕРЕЧИСЛЕННЯ, НАВЕДЕННОМУ В УМОВІ (саме це, мабуть, мається на увазі, виділене у повідомленні Ю.Я.Пасіхова жирним шрифтом), адже у противному випадку ніхто не заважав їм почати обхід у протилежному - в умові на вибір початкового напрямку та ПОЧАТКОВОЇ ТОЧКИ ОБХОДУ ніяких обмежень не накладено !!!
Черговий скарб буде також черговим і у зворотньому напрямку !!!

З повагою - АВП


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#18 2009-07-23 11:37:52

Журі_Пасіхов
Гість

Re: Задача CORSIAR

Я думаю, ЩО БІЛЬШ ТОЧНО СКАЗАТИ НЕМОЖЛИВО - ЧЕРГОВИЙ  (рос. ОЧЕРЕДНОЙ ) - той, який йде наступним...Це однозначно задає умову обходу в порядку переліку.. Якщо ж "де висадилися"  -  так само зрозуміло, якщо скарби задані переліком в черговості обходу, то біля першого вказаного.
І ще одне. Шановні учасники! КОНТРОЛЬНИЙ ПРИКЛАД Є НЕВІД"ЄМНОЮ ЧАСТИНОЮ УМОВИ. ЯКЩО ВИНИКАЄ ЯКІСЬ НЕРОЗУМІННЯ, АНАЛІЗ ПРИКЛАДУ ПОВИНЕН ПРОЯСНИТИ СИТУАЦІЮ.

 

#19 2009-07-29 14:24:19

ANTEY
Новий користувач
Зареєстрований: 2009-07-26
Повідомлень: 3

Re: Задача CORSIAR

Скажіть, будь ласка, чому задачі CORSIAR та VIRUS в перевірці онлайн на тестовому прикладі видають: FAILED (Wrong Answer). Хоча відповідь правильна, згідно з прикладом.....

Відредаговано ANTEY (2009-07-29 19:04:19)

Поза форумом

 

#20 2009-07-29 21:57:14

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Задача CORSIAR

ANTEY написав:

Скажіть, будь ласка, чому задачі CORSIAR та VIRUS в перевірці онлайн на тестовому прикладі видають: FAILED (Wrong Answer). Хоча відповідь правильна, згідно з прикладом.....

Дивно, видно не уважно читаєте умову, а саме про формат  вхідних та вихідних данних.

Прямо тільки що перевірив задачу CORSIAR:
Результат перевірки
Тест    Результат    Час виконання
01    PASSED (+0)    0.01 сек.
Прошло тестов: 1 из 1.
Набрано баллов: 0 из 0.


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#21 2009-07-30 07:38:44

ANTEY
Новий користувач
Зареєстрований: 2009-07-26
Повідомлень: 3

Re: Задача CORSIAR

Ну, гаразд, СORSIAR задача з "складним считуванням і виводом" , але VIRUS....
Якщо написати:
Var
   s,s2 :string;
begin
   readln(s);
   read(s2);
   writeln('2 5 4 1 3');
End. - вона в мене всеодно не йде... При чому перевірці абсолютно всеодно написано "write" чи "writeln". а СORSIAR я вводю руками тестовий приклад і показує правильно...

Присяжнюк А.В. написав:

Дивно, видно не уважно читаєте умову, а саме про формат  вхідних та вихідних данних.

В таких випадка пише в дужках "Вad Data", а в мене пише "Wrong Answer".....

Відредаговано ANTEY (2009-07-30 09:46:39)

Поза форумом

 

#22 2009-07-30 08:58:11

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Задача CORSIAR

ANTEY написав:

Ну, гаразд, СORSIAR задача з "складним считуванням і виводом" , але VIRUS....
Якщо написати:
Var
   s,s2 :string;
begin
   readlns(s);
   read(s2);
   writeln('2 5 4 1 3');
End. - вона в мене всеодно не йде... При чому перевірці абсолютно всеодно написано "write" чи "writeln". а СORSIAR я вводю руками тестовий приклад і показує правильно...
В таких випадка пише в дужках "Вad Data", а в мене пише "Wrong Answer".....

Ось прямо тільки що:

Результат перевірки
Тест    Результат    Час виконання
01    PASSED (+0)    0.01 сек.
Прошло тестов: 1 из 1.
Набрано баллов: 0 из 0.

У Вас по-перше в у першому рядку зчитування помилка: не readlnS(s); а readln(S);

Але не це суттєво. Там приклад видно трішки інший - не потрібно виводити те, що й так ясно - зробіть задачу повністю!!!.  Адже ніхто Вам не гарантує, що приклад 1:1 такий як в умові (хоча це й так у більшості випадків).

Аналог, щоб було зрозуміліше.: Дано квадрат числа. Вивести саме число, якщо воно завжди додатне.
Приклад введення  4
Приклад виведення 2
Ви відправляєте 2, але виявляється у першому тесті Вам "підсунули" не 4, а 25... smile.


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#23 2009-07-30 10:00:12

ANTEY
Новий користувач
Зареєстрований: 2009-07-26
Повідомлень: 3

Re: Задача CORSIAR

Присяжнюк А.В. написав:

Ось прямо тільки що:

Результат перевірки
Тест    Результат    Час виконання
01    PASSED (+0)    0.01 сек.
Прошло тестов: 1 из 1.
Набрано баллов: 0 из 0.

У Вас по-перше в у першому рядку зчитування помилка: не readlnS(s); а readln(S);

Але не це суттєво. Там приклад видно трішки інший - не потрібно виводити те, що й так ясно - зробіть задачу повністю!!!.  Адже ніхто Вам не гарантує, що приклад 1:1 такий як в умові (хоча це й так у більшості випадків).

Аналог, щоб було зрозуміліше.: Дано квадрат числа. Вивести саме число, якщо воно завжди додатне.
Приклад введення  4
Приклад виведення 2
Ви відправляєте 2, але виявляється у першому тесті Вам "підсунули" не 4, а 25... .

Дякую. Просто привик, що тестовий приклад є той, який дається з задачою...
А задачу я повністю зробив... Судячи з тесту є десь помилка, хоча на простеньких a b c, чи щось таке робить...

Поза форумом

 

#24 2009-07-31 10:26:41

Журі_Пасіхов
Гість

Re: Задача CORSIAR

Авторський тест з умови задачі і тест для он-лайн перевірки може співпадати, а може й не співпадати...
В другому випадку учасникам краще - маєте додатковий тест для перевірки...

 

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

Powered by Likt
© Copyright 2002–2009 Likt