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


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

Ви не зайшли.

#1 2017-10-23 22:16:51

vadym
Олімпієць
Зареєстрований: 2017-10-23
Повідомлень: 3

задача Evacuation

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

Поза форумом

 

#2 2017-10-24 01:05:23

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

Re: задача Evacuation

vadym написав:

Якщо шосейна дорога означає пряме з'єднання, то в прикладі не виконується нерівність трикутника

Щоб виконувалась нерівність трикутника потрібен трикутник (несподівано). А щоб був трикутник треба 3 вершини, з'єднані прямими відрізками. Вершини в задачі є, а от з прямими відрізками - біда. Ні річка, ні дорога (навіть шосейна) не зобов'язані бути прямими.

vadym написав:

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

Дійсно, не задають.

vadym написав:

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

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

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

Відредаговано Dim_ov (2017-10-24 01:06:37)

Поза форумом

 

#3 2017-10-24 18:53:40

vadym
Олімпієць
Зареєстрований: 2017-10-23
Повідомлень: 3

Re: задача Evacuation

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

Поза форумом

 

#4 2017-10-24 20:36:27

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

Re: задача Evacuation

Інформації з умови та вхідних даних достатньо для того, щоб правильно врахувати вплив течії.

Поза форумом

 

#5 2017-10-24 20:40:47

vadym
Олімпієць
Зареєстрований: 2017-10-23
Повідомлень: 3

Re: задача Evacuation

тобто мілина мається на увазі місце прямо біля берега?

Поза форумом

 

#6 2017-10-25 05:30:56

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

Re: задача Evacuation

vadym написав:

тобто мілина мається на увазі місце прямо біля берега?

Може і не прямо біля берега, але у будь якому разі рухом човна поперек течії потрібно знехтувати, бо інакше задача не має розв'язку, оскільки відстань від мілини до берега в умові не згадана.

P.S.
Не зайвим було би у задачі додати це зауваження.
(або, що логічніше, враховувати відстань від мілини до берега) smile
P.S.P.S.
Задача цікава (респект автору!) але була би іще цікавішою, якщо би мілина дійсно знаходилася біля крутого берега на який не можна евакуювати пасажирів, але з якого можна було би перемістити на корабель порожній човен, доставлений шосейною дорогою, що сполучає пристані і мілину (берег біля мілини) з різними швидкостями транспортування на двох ділянках. smile
P.S.P.S.P.S.
А якщо, окрім суходольного сполучення мілини (берега) з пристанями, ще й зробити задачу "морською", берег вважати прямолінійним,  мілину розмістити на відстані від берега і враховувати швидкість припливу/відпливу, та швидкість вітру під певним кутом до берега...  то взагалі задачу-"бомбу" отримали би... smile smile smile

Відредаговано LVV (2017-10-25 15:31:08)


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

Поза форумом

 

#7 2017-10-26 14:01:15

mobiDic
Олімпієць
Зареєстрований: 2017-10-26
Повідомлень: 1

Re: задача Evacuation

LVV написав:

vadym написав:

тобто мілина мається на увазі місце прямо біля берега?

Може і не прямо біля берега, але у будь якому разі рухом човна поперек течії потрібно знехтувати, бо інакше задача не має розв'язку, оскільки відстань від мілини до берега в умові не згадана.

P.S.
Не зайвим було би у задачі додати це зауваження.
(або, що логічніше, враховувати відстань від мілини до берега) smile
P.S.P.S.
Задача цікава (респект автору!) але була би іще цікавішою, якщо би мілина дійсно знаходилася біля крутого берега на який не можна евакуювати пасажирів, але з якого можна було би перемістити на корабель порожній човен, доставлений шосейною дорогою, що сполучає пристані і мілину (берег біля мілини) з різними швидкостями транспортування на двох ділянках. smile
P.S.P.S.P.S.
А якщо, окрім суходольного сполучення мілини (берега) з пристанями, ще й зробити задачу "морською", берег вважати прямолінійним,  мілину розмістити на відстані від берега і враховувати швидкість припливу/відпливу, та швидкість вітру під певним кутом до берега...  то взагалі задачу-"бомбу" отримали би... smile smile smile

Так, а давайте ще прикрутимо до човна магніт, який керується ел струмом з берега і сила току якого буде визначатись положенням зірок в Великій Ведмедиці!

Поза форумом

 

#8 2017-10-27 05:45:53

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

Re: задача Evacuation

mobiDic написав:

Так, а давайте ще прикрутимо до човна магніт, який керується ел струмом з берега і сила току якого буде визначатись положенням зірок в Великій Ведмедиці!

Якщо Ви зможете потім розв'язати таку задачу, то чому б і ні? smile


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

Поза форумом

 

#9 2017-11-12 22:46:32

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 19

Re: задача Evacuation

Итоги подведены, поэтому начну постить бажный код.
Язык python. Авторами гарантируется целый ответ, но явно не гарантируется, что в вылезающие в процессе его получения величины тоже будут целыми, поэтому во избежание проблем делаем расчеты в float. Грубая оценка показывает, что искомое время не может быть сильно больше 10^12, значит точности типа float python'a (53 бита или 10^-16) должно хватить. Комментарии в тексте кода поясняют довольно простую идею решения. Тем не менее, код дает Wrong Answer на тестах 7, 11, 15 и 17. Тому кто скажет почему буду благодарен.

Код:

N, K, L1, L2, L3, V, W, U = map(int,raw_input().split())
L1, L2, L3, V, W, U = map(float,(L1, L2, L3, V, W, U))

if K == 1: #Only one person can leave the boat    
    if N > 1: 
        print -1
    else:
        T = L2/(V+W)
        if V>W: T = min(T, L1/(V-W))
        print int(round(T))
else: #rescue consists of n identical round trips and еру last one-way trip to the shore
    n = (N-2)//(K-1)*(not not(N-1))#the number of round trips. n=0 if N=1
    T = (L1+L2)/(V+W)+L3/U #At first we consider V<W. The round trip is obvious
                            # since only downstream movement is allowed
    T_last = L2/(V+W) #last trip is also obvious    
    if V>W: #Yay! We obtain the ability to go up the stream!
        L = min(L1,L2)
        T = min(T, L/(V+W)+L/(V-W)) #compare with the fastest on-water round trip
        T_last = min(T_last, L1/(V-W))
    print int(round(n*T + T_last))

Поза форумом

 

#10 2017-11-12 23:17:23

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 19

Re: задача Evacuation

Товарищи, а ведь это epic fail. Авторы, конечно, гарантируют целое время, но в тестах оно не всегда так.
Переписал код через Fraction (арифметика с дробями с целым числителем и знаменателем)

Код:

from fractions import Fraction
N, K, L1, L2, L3, V, W, U = map(int,raw_input().split())

if K == 1:  
    if N > 1: 
        print -1
    else:
        T = Fraction(L2, V+W)
        if V>W: T = min(T, Fraction(L1, V-W))
        print T
else:
    n = (N-2)//(K-1)*(not not(N-1))
    T = Fraction(L1+L2, V+W) + Fraction(L3,U) 
                            
    T_last = Fraction(L2, V+W)    
    if V>W:
        L = min(L1,L2)
        T = min(T, Fraction(L, V+W) + Fraction(L, V-W)) 
        T_last = min(T_last, Fraction(L1,V-W))
    print n*T + T_last

И тут понеслось ...

Тест    Результат    Час роботи
00    PASSED (+0)    0.09 с
01    PASSED (+1)    0.04 с
02    PASSED (+1)    0.03 с
03    PASSED (+1)    0.04 с
04    FAILED (Bad Data)    0.04 с
05    PASSED (+1)    0.04 с
06    PASSED (+1)    0.03 с
07    FAILED (Bad Data)    0.04 с
08    PASSED (+1)    0.03 с
09    PASSED (+1)    0.04 с
10    FAILED (Bad Data)    0.03 с
11    FAILED (Bad Data)    0.03 с
12    PASSED (+1)    0.04 с
13    PASSED (+1)    0.03 с
14    PASSED (+1)    0.04 с
15    FAILED (Bad Data)    0.04 с
16    PASSED (+1)    0.04 с
17    FAILED (Bad Data)    0.04 с
18    PASSED (+1)    0.04 с
19    PASSED (+1)    0.03 с
20    PASSED (+1)    0.04 с

Bad Data это когда формат вывода ответа не соответствует ожидаемому. Так вот, когда объект Fraction целый, то print выдает целое число, а если не целый, то вида a/b

>>>print Fraction(2,4)
1/2

>>>print Fraction(12000000000000000,6000)
2000000000000

Поза форумом

 

#11 2017-11-12 23:47:06

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 19

Re: задача Evacuation

Последний пост на тему. Этот код набирает 20/20

Код:

from math import ceil, floor
N, K, L1, L2, L3, V, W, U = map(int,raw_input().split())
L1, L2, L3, V, W, U = map(float,(L1, L2, L3, V, W, U))

if K == 1: 
    if N > 1: 
        print -1
    else:
        T = L2/(V+W)
        if V>W: T = min(T, L1/(V-W))
        print int(ceil(T))
else: 
    n = (N-2)//(K-1)*(not not(N-1))
    T = (L1+L2)/(V+W)+L3/U 
    T_last = L2/(V+W) 
    if V>W: 
        L = min(L1,L2)
        T = min(T, L/(V+W)+L/(V-W)) 
        T_last = min(T_last, L1/(V-W))
    print int(ceil(n*T + T_last))

А этот 14/20

Код:

from math import ceil, floor
N, K, L1, L2, L3, V, W, U = map(int,raw_input().split())
L1, L2, L3, V, W, U = map(float,(L1, L2, L3, V, W, U))

if K == 1:     
    if N > 1: 
        print -1
    else:
        T = L2/(V+W)
        if V>W: T = min(T, L1/(V-W))
        print int(floor(T))
else: 
    n = (N-2)//(K-1)*(not not(N-1))
    T = (L1+L2)/(V+W)+L3/U 
    T_last = L2/(V+W) 
    if V>W: 
        L = min(L1,L2)
        T = min(T, L/(V+W)+L/(V-W)) 
        T_last = min(T_last, L1/(V-W))
    print int(floor(n*T + T_last))

Iтогi падвєдьом (с):
Правильная формулировка вопроса задачи: "Какое наименьшее целое число секунд потребуется на эвакуащию?", поскольку такая формулировка дает указание на правильный способ округления дробного ответа. На вопрос об округлении, заданный участниками раньше, автором дан ответ, что в формулировка задачи исчерпывающая. Тем не менее, она вводит в заблуждение, так как недвусмысленно намекает на то, что ответ обязательно будет целым. Прошу уважаемое жюри обратить свое внимание на эту проблему.

Відредаговано andervish (2017-11-12 23:56:59)

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt