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

seland · 2013-02-20 12:51:18

Ймовірно, це найдивніша задача онлайн-туру. Хочу поділитися розв"язком, який все ж таки набрав 100 балів після довгих експериментів.
Спочатку треба зрозуміти, що взагалі відбувається: павук повзе по прямій в системі відліку, пов"язаній з конусом. А в системі відліку, пов"язаній з мухою, павук повзе по кривій, довжину якої і треба знайти. Можно знайти весь час руху: T1=L/V, оскільки вздовж твірної павук повзе лише за рахунок власної швидкості. Тоді розіб"ємо весь час на k відрізків. Для кожного відрізку знайдемо значення відстані від павука до висоти конуса(радіус) на початку відрізка часу і в кінці - R1, R2. Швидкість павука в будь-який момент часу складається з двох перпендикулярних складових: V і wR, де w - кутова швидкість конуса, R - радіус обертання в цей момент часу. Для того, щоб знайти відстань, яку пройде павук за відрізок часу, знайдемо швидкість, з якою рухався павук протягом цього відрізку, вважаючи R=(R1+R2)/2, і помножимо на проміжок часу. Сумуючи для всіх k відрізків ці значення маємо шукану довжину кривої.
Залишається питання, стосовно того, на скільки відрізків розбивати час. Взагалі, якщо не знати, що обмеження часу лише 0.1 секунди, то отримати 100 балів майже неможливо. Для мільйона відрізків проходять лише 9 тестів(усі інші TL). Для 200000 відрізків один тест дає WA, усі інші проходять. Експериментально знайдена оптимальна точність 250000 - яка проходить 100 балів.
Ось невеличкий код розв"язку:
Var
w,r,n,l,t,v,s,T1,r1,r2,middle:real;
i,k:longint;
Begin
read(l,r,n,t,v);
k:=2500000;
s:=0;
r2:=r;
w:=2*Pi*n/t; //Знаходимо кутову швидкість
T1:=l/v; //Знаходимо весь час руху
for i:=1 to k do begin
r1:=r2;
r2:=r*(1-i/k); //Знаходимо новий радіус
middle:=(r1+r2)/2; //Знаходимо середній
s:=s+sqrt(v*v+w*w*middle*middle);
end;
s:=s*T1/k //Домножаємо на довжину одного проміжку часу
write(s);
end.

Жюри_Пасихов · 2013-02-20 16:07:08

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

Код:

Program Spider2;
   var L,R,N,T,V: int64;
       fi,a,b,k,s:Extended;
begin
       read(L,R,N,T,V);
       if N=0 then s:=L else
       begin
       fi:=2*pi*R*N/(V*T);
       k:=L/fi;
       b:=sqrt(1+sqr(fi));
       s:=(k/2)*(fi*b+ln(fi+b));
       end;
       writeln(s);
end.

Дивно, що учасники так погано справилися із цією задачею. Ми вважали її однією із двох на "відкуп"

R_Shpakovych · 2013-02-20 16:32:22

Недолік Вашого способу - це лінійне розбиття по часу та по r2.
При великих кутових швидкостях обертання конуса довжини відрізків кривої біля основи конуса на порядки перевищують довжини відрізків біля вершини конуса. Тому потрібні дуже великі розбиття, щоб отримати задовільну точність при основі конуса.
Точність обчислень значно підвищиться, якщо розбивати криву на відрізки густіше при основі конуса. Наприклад, за квадратичним розподілом:
r2:=r*(1-sqr(i/k));
Зрозуміло, що проміжки часу для кожного відрізка теж будуть різні:
Ti:=T1*(i*i-sqr(i-1))/sqr(k);

R_Shpakovych · 2013-02-20 16:35:19

Моя відповідь стосується першого повідомлення:)

shoa169 · 2013-02-20 17:43:40

seland написав:
вважаючи R=(R1+R2)/2, і помножимо на проміжок часу.

Тем самым, Вы используете [почти] метод трапеций, у которого погрешность результата есть O(h), где h =T / k - шаг интегрирования.
В то же время только чуть более сложный для кодирования метод Симпсона имеет точность O(h^4). Поэтому число интервалов (при сохранении точности решения) будет меньше на несколько порядков.
Будет полезно почитать ещё, скажем, тут - коротко и понятно.

seland · 2013-02-20 21:11:06

Дякую за змістовну критику і красивий авторський розв"язок. Але, оскільки пряму формулу мало хто знає, то хотілося б краще розібратися з розв"язком через інтеграл.

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

#1 2013-02-20 12:51:18

Задача Spider2

#2 2013-02-20 16:07:08

Re: Задача Spider2

Код:

#3 2013-02-20 16:32:22

Re: Задача Spider2

#4 2013-02-20 16:35:19

Re: Задача Spider2

#5 2013-02-20 17:43:40

Re: Задача Spider2

seland написав:

#6 2013-02-20 21:11:06

Re: Задача Spider2

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