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

Присяжнюк А.В. · 2009-07-19 21:38:28

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

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

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

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

Журі_Пасіхов · 2009-07-20 09:50:26

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

Присяжнюк А.В. · 2009-07-20 12:33:23

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

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

vitert · 2009-07-20 13:19:19

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

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

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

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

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

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

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

badm · 2009-07-20 13:55:14

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

badm · 2009-07-20 14:03:39

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

Журі_Пасіхов · 2009-07-20 15:17:47

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

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

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

Присяжнюк А.В. · 2009-07-20 19:44:59

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

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

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

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

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

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

vitert · 2009-07-20 21:10:34

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

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

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

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

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

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

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

CUPIDON · 2009-07-20 22:54:07

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

Журі_Пасіхов · 2009-07-21 08:02:00

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

Журі_Пасіхов · 2009-07-21 08:16:00

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

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

vitert · 2009-07-21 16:01:14

Журі_Пасіхов написав:
CUPIDON написав:
Ну,шановні журі, то звідки пірати починають свій маршрут?
Відповіді немає.

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

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

CUPIDON · 2009-07-21 18:05:35

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

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

Журі_Пасіхов написав:
немає відповіді

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

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

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

Присяжнюк А.В. · 2009-07-22 17:21:49

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

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

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

Журі_Пасіхов · 2009-07-22 18:06:22

CUPIDON написав:
vitert написав:
Журі_Пасіхов написав:
Щоб зняти цю дискусію і не занурюватися в різні інтерпретації вироджених випадків, "спрощуємо" життя - накладаємо умову. яку пропонує п.Присяжнюк -кількість скарбів N(3<=N<=20)"
В цьому випадку зрозуміло що починають із першої схованки.
Ну, дозволь не погодитись! це дуже важливо, оскільки в тесті
1
3 5 1 3 2 3 4
можливі обидві відповіді, залежно від початку:
якщо з початку кординат-проти год.стр, а якшо з 1 схов, то за.. дилема..
Журі_Пасіхов написав:
немає відповіді
як вже було вищесказано:
математика - точна наука і не терпить неточності...
тому, шановні судді, прошу вас дати чітку відповідь на це питання.

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

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

Присяжнюк А.В. · 2009-07-22 19:11:22

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

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

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

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

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

Журі_Пасіхов · 2009-07-23 11:37:52

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

ANTEY · 2009-07-29 14:24:19

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

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

Присяжнюк А.В. · 2009-07-29 21:57:14

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

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

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

ANTEY · 2009-07-30 07:38:44

Ну, гаразд, С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)

Присяжнюк А.В. · 2009-07-30 08:58:11

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... .

ANTEY · 2009-07-30 10:00:12

Присяжнюк А.В. написав:
Ось прямо тільки що:

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

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

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

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

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

Журі_Пасіхов · 2009-07-31 10:26:41

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

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

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

Задача CORSIAR

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

Re: Задача CORSIAR

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

Re: Задача CORSIAR

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

Re: Задача CORSIAR

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

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

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

Re: Задача CORSIAR

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

Re: Задача CORSIAR

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

Re: Задача CORSIAR

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

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

Re: Задача CORSIAR

vitert написав:

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

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

Re: Задача CORSIAR

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

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

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

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

Re: Задача CORSIAR

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

Re: Задача CORSIAR

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

Re: Задача CORSIAR

CUPIDON написав:

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

Re: Задача CORSIAR

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

CUPIDON написав:

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

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

Re: Задача CORSIAR

vitert написав:

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

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

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

Re: Задача CORSIAR

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

Re: Задача CORSIAR

CUPIDON написав:

vitert написав:

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

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

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

Re: Задача CORSIAR

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

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

Re: Задача CORSIAR

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

Re: Задача CORSIAR

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

Re: Задача CORSIAR

ANTEY написав:

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

Re: Задача CORSIAR

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

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

Re: Задача CORSIAR

ANTEY написав:

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

Re: Задача CORSIAR

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

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

Re: Задача CORSIAR

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