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

vadym · 2017-10-23 22:16:51

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

Dim_ov · 2017-10-24 01:05:23

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

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

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

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

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

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

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

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

vadym · 2017-10-24 18:53:40

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

Dim_ov · 2017-10-24 20:36:27

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

vadym · 2017-10-24 20:40:47

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

LVV · 2017-10-25 05:30:56

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

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

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

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

mobiDic · 2017-10-26 14:01:15

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

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

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

LVV · 2017-10-27 05:45:53

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

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

andervish · 2017-11-12 22:46:32

Итоги подведены, поэтому начну постить бажный код.
Язык 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))

andervish · 2017-11-12 23:17:23

Товарищи, а ведь это 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

andervish · 2017-11-12 23:47:06

Последний пост на тему. Этот код набирает 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)

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

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

задача Evacuation

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

Re: задача Evacuation

vadym написав:

vadym написав:

vadym написав:

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

Re: задача Evacuation

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

Re: задача Evacuation

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

Re: задача Evacuation

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

Re: задача Evacuation

vadym написав:

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

Re: задача Evacuation

LVV написав:

vadym написав:

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

Re: задача Evacuation

mobiDic написав:

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

Re: задача Evacuation

Код:

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

Re: задача Evacuation

Код:

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

Re: задача Evacuation

Код:

Код:

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