Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Bouncing Balls II / 25 сообщений из 27, страница 1 из 2
  1  все
28.10.2009, 11:28:18
    #36276577
RT183.1
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
Обнаружил прикольную задачу: http://www.spoj.pl/problems/BOBALLS2/
Пара тысяч частиц бегают в 2D прямоугольном ящике, упруго сталкиваются, отражаются от стенок.
У каждой частицы скорости равны |vx|, |vy| = 1.

Даны координаты и скорости частиц в момент времени t = 0.
Надо найти координаты частиц в моменты t1, t2, t3,... < 10^12 .
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 15:13:05
    #36277541
zloy den
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
Хм, как я понимаю, прямое моделирование не пройдет по скорости? Черт, что-то напоминает, но не могу понять что. Может попробовать поискать циклы до повторяющегося состояния?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 15:36:58
    #36277664
RT183.1
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
50 частиц в ящике 15х12:
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
 15   12         ---- dX, dY
 50 
 1   2  - 1   1      ----  X, Y, VX, VY
 1   5  - 1  - 1 
 1   6   1   1 
 1   7  - 1   1 
 2   4  - 1   1 
 2   5   1  - 1 
 2   6   1   1 
 2   2  - 1  - 1 
 2   7   1   1 
 2   8  - 1  - 1 
 2   10  - 1  - 1 
 3   1   1  - 1 
 3   6   1  - 1 
 3   7  - 1   1 
 3   8   1   1 
 3   9   1   1 
 3   10  - 1  - 1 
 4   2   1   1 
 4   3  - 1   1 
 4   7  - 1  - 1 
 4   9   1  - 1 
 4   10  - 1  - 1 
 5   4  - 1   1 
 5   9   1  - 1 
 6   3  - 1   1 
 6   6   1   1 
 6   9  - 1  - 1 
 7   2   1   1 
 7   3  - 1  - 1 
 7   5   1  - 1 
 7   4   1   1 
 7   9  - 1   1 
 8   4   1  - 1 
 8   5   1  - 1 
 8   6  - 1   1 
 8   7   1   1 
 8   8  - 1   1 
 9   1   1  - 1 
 9   2  - 1  - 1 
 9   8   1  - 1 
 9   4  - 1  - 1 
 9   5   1   1 
 9   7  - 1  - 1 
 9   3   1  - 1 
 10   3  - 1   1 
 10   4  - 1  - 1 
 10   8   1  - 1 
 10   10   1   1 
 11   1  - 1  - 1 
 11   7  - 1   1 
 1 
 1000000000000

через 1000 миллиардов секунд будут в таких позициях (отсортено):
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
 0   5 
 0   12 
 1   1 
 1   9 
 1   9 
 1   10 
 1   12 
 2   0 
 2   2 
 3   1 
 3   11 
 4   5 
 4   7 
 5   4 
 6   5 
 6   6 
 6   9 
 7   1 
 7   6 
 8   4 
 8   6 
 8   8 
 8   10 
 9   1 
 9   6 
 9   11 
 10   2 
 10   8 
 11   2 
 11   3 
 11   8 
 11   9 
 11   11 
 12   1 
 12   1 
 12   2 
 12   11 
 12   11 
 12   12 
 13   0 
 13   1 
 13   4 
 13   6 
 13   9 
 13   10 
 13   11 
 14   2 
 14   6 
 14   7 
 15   7
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 15:38:18
    #36277670
RT183.1
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
zloy denХм, как я понимаю, прямое моделирование не пройдет по скорости? Черт, что-то напоминает, но не могу понять что. Может попробовать поискать циклы до повторяющегося состояния?
Я тоже не мгновенно сообразил
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 15:54:05
    #36277714
zloy den
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
RT183.1zloy denХм, как я понимаю, прямое моделирование не пройдет по скорости? Черт, что-то напоминает, но не могу понять что. Может попробовать поискать циклы до повторяющегося состояния?
Я тоже не мгновенно сообразил

Так что, оно?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 16:05:59
    #36277752
RT183.1
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
> Так что, оно?

Не, это не "то" (это гиблая идея, с циклами)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 16:14:30
    #36277767
zloy den
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
Ладно, попробую еще подумать (если время найду)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 16:20:49
    #36277782
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
Я решал нечто подобное (только для одной частицы). Задача сводилась даже не к моделированию её полёта, а к закрашиванию траектории. Для последнего траектория рисуется "длинными прыжками" (это интервал между столкновениями о борта коробки). Координаты прыжков я кажется считал через сложение и вычистание по модулю, где модуль - суть длина и ширина коробки.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 16:25:20
    #36277791
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
zloy denХм, как я понимаю, прямое моделирование не пройдет по скорости? Черт, что-то напоминает, но не могу понять что. Может попробовать поискать циклы до повторяющегося состояния?
Повторение может быть наступит не очень скоро. Чем-то постановка мне напоминает генератор псевдослучайной последовательнсти, где сосотояние - это суть положение частиц в ящике. И чем их больше - тем длинне будет период.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 16:54:45
    #36277872
zloy den
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
mayton
Повторение может быть наступит не очень скоро. Чем-то постановка мне напоминает генератор псевдослучайной последовательнсти, где сосотояние - это суть положение частиц в ящике. И чем их больше - тем длинне будет период.

Ага, вот что оно мне напоминало. Я в дипломе такое делал. Правда, как выяснилось мой генератор псевдослучайных перестановок был практически как у Кнута (выяснил в этом году в отпуске, когда sicp читал). Теперь думаю-радоваться от того что сам додумался до нормального алгоритма или грустить от того что мало знаю и придумываю велосипеды
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 17:55:44
    #36278034
Crazzy
Crazzy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
А что произойдет, если частицы столкнутся друг с другом лоб в лоб?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 17:57:30
    #36278037
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
Это нарисовано на 2 картинке.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 18:12:24
    #36278060
Crazzy
Crazzy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
Интересная фишка при таких вариантах соударений: траектория 1-го шара после соударения становится равной траектории 2-го, если бы виртуально этого соударения не было и 2-й виртуально летел бы в пустоте.
По крайней мере при лобовом столкновении это так, при косом также, при столкновении с отражением также.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 18:15:35
    #36278068
Crazzy
Crazzy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
CrazzyИнтересная фишка при таких вариантах соударений: траектория 1-го шара после соударения становится равной траектории 2-го, если бы виртуально этого соударения не было и 2-й виртуально летел бы в пустоте.
По крайней мере при лобовом столкновении это так, при косом также, при столкновении с отражением также.
Может конечно объяснил кривовато, но по рисункам ощущение, что траектория всех шариков не будет отличаться от наложения всех траекторий движения каждого шарика в предположении, что соударений не было. Просто при соударении траектория сохраняется, но шарики как бы меняются "номерами".
Блин, и тут кажется тоже кривовато объяснил.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 18:18:39
    #36278073
Crazzy
Crazzy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
CrazzyCrazzyИнтересная фишка при таких вариантах соударений: траектория 1-го шара после соударения становится равной траектории 2-го, если бы виртуально этого соударения не было и 2-й виртуально летел бы в пустоте.
По крайней мере при лобовом столкновении это так, при косом также, при столкновении с отражением также.
Может конечно объяснил кривовато, но по рисункам ощущение, что траектория всех шариков не будет отличаться от наложения всех траекторий движения каждого шарика в предположении, что соударений не было. Просто при соударении траектория сохраняется, но шарики как бы меняются "номерами".
Блин, и тут кажется тоже кривовато объяснил.
В общем, шарики виртуально как бы пролетают друг через друга, но меняются при этом номерами.
Во, вроде с 3-го раза сказал, что хотел
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 18:19:49
    #36278077
Дональдак
Дональдак
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
Crazzy, все понятно. :)
Т.е. можно моделировать только столкновения частиц со стенками, без учета внутренних.
Так?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 19:32:24
    #36278187
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
В задаче сказано
Надо найти координаты частиц в моменты t1, t2, t3,... < 10^12.
Если частицы пронумерованны - то пролетание шариков друг сквозь друга не должно быть. В противном случае - всё равно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 21:17:38
    #36278291
tchingiz
tchingizПривилегированный пользователь
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
на теорию групп похоже.
Там же состояния начнут повторятся
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 21:34:34
    #36278308
RT183.1
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
CrazzyИнтересная фишка при таких вариантах соударений: траектория 1-го шара после соударения становится равной траектории 2-го, если бы виртуально этого соударения не было и 2-й виртуально летел бы в пустоте.
По крайней мере при лобовом столкновении это так, при косом также, при столкновении с отражением также.
йес, это решающее наблюдение
(нас не просят найти где будет частица №5, а где №999 и т.д.,
да и какая разница, если каждая частица неотличима от любой другой,
точно так же как электрон неотличим от любого другого электрона etc
)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 22:07:07
    #36278341
RT183.1
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
ДональдакCrazzy, все понятно. :)
Т.е. можно моделировать только столкновения частиц со стенками, без учета внутренних.
Так?
Моделирование -- это немного громко сказано; достаточно несложной ф-ции
и самое главное: не забываем о полной независимости движений частицы вдоль осей X и Y,
и тогда эта ( 1-мерная ) функция пишется легко и приятно
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 22:19:24
    #36278352
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
RT183.1йес, это решающее наблюдение
(нас не просят найти где будет частица №5, а где №999 и т.д.,
да и какая разница, если каждая частица неотличима от любой другой,
точно так же как электрон неотличим от любого другого электрона etc
)
Да. Я тоже об этом думал. Но тогда рисунки (1),(2),(3),(4) безсмысленны. В них частицы пролетают друг сквозь друга.

Что вы скажете по тесту в задании? Набор координат в output соответствует порядку вводимых параметров частиц?

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
Input:
 6   4 
 4 
 1   2   1   1 
 5   2   1   1 
 2   1   1  - 1 
 3   1  - 1  - 1 
 1 
 4 

Output:
 1   3 
 3   2 
 5   2 
 6   3
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.10.2009, 22:33:12
    #36278369
RT183.1
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
Они просят:
авторThe balls in each output block must be sorted – primarily by to their first, secondarily by their second coordinate (i.e. by X, then by Y coords) at that point in time.

т.е. в общем случае порядок нумерации конечно побьется
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.10.2009, 10:11:24
    #36278783
Crazzy
Crazzy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
А ну если у шаров никакого заранее заданного номера нет, все они неотличимы друг от друга а сортируются по координатам то все не так и сложно.
В общем, RT183.1, давай, уделай этого Blue Mary
И не забудь ссылку выложить, порадуюсь, что тоже в процессе поучаствовал ))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.10.2009, 11:08:39
    #36278951
RT183.1
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
CrazzyА ну если у шаров никакого заранее заданного номера нет, все они неотличимы друг от друга а сортируются по координатам то все не так и сложно.
В общем, RT183.1, давай, уделай этого Blue Mary
И не забудь ссылку выложить, порадуюсь, что тоже в процессе поучаствовал ))
Так я же ее сутки назад как сдал: http://www.spoj.pl/status/BOBALLS2/
2.
Это не его задача -- он просто добавил ее на spoj, -- это задача с IPSC 2009
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.10.2009, 12:52:22
    #36279309
RT183.1
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bouncing Balls II
Под горячую руку сделал и Снукера: http://www.spoj.pl/problems/SNOOKER/
=From any point on the boundary you can hit the ball in two directions and they are considered to be two different ways.
For instance in the image shown below, from the point S the ball can be hit in two ways as shown.

Given the dimensions of the board your task is to find the number of ways
in which the ball can be hit so that it eventually reaches one of the four holes.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Bouncing Balls II / 25 сообщений из 27, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 538ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1344136]:
 0ms
get settings:
 16ms
get forum list:
 23ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 177ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 67ms
get tp. blocked users:
 2ms
others: 232ms
total:  538ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]