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


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

Ви не зайшли.

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

seland
Новий користувач
Зареєстрований: 2012-12-28
Повідомлень: 14

Задача Spider2

Ймовірно, це найдивніша задача онлайн-туру. Хочу поділитися розв"язком, який все ж таки набрав 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.

Поза форумом

 

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

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 439

Re: Задача Spider2

Так, це один із можливих варіантів розв"язку, не самий кращий. !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.

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

Поза форумом

 

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

R_Shpakovych
Новий користувач
Зареєстрований: 2013-02-20
Повідомлень: 2

Re: Задача Spider2

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

Поза форумом

 

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

R_Shpakovych
Новий користувач
Зареєстрований: 2013-02-20
Повідомлень: 2

Re: Задача Spider2

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

Поза форумом

 

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

shoa169
Новий користувач
Зареєстрований: 2010-11-10
Повідомлень: 56

Re: Задача Spider2

seland написав:

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

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

Поза форумом

 

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

seland
Новий користувач
Зареєстрований: 2012-12-28
Повідомлень: 14

Re: Задача Spider2

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

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt