ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Bouncing Balls II
25 сообщений из 27, страница 1 из 2
  1  все
Bouncing Balls II
    #36276577
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
Обнаружил прикольную задачу: http://www.spoj.pl/problems/BOBALLS2/
Пара тысяч частиц бегают в 2D прямоугольном ящике, упруго сталкиваются, отражаются от стенок.
У каждой частицы скорости равны |vx|, |vy| = 1.

Даны координаты и скорости частиц в момент времени t = 0.
Надо найти координаты частиц в моменты t1, t2, t3,... < 10^12 .
...
Рейтинг: 0 / 0
28.10.2009, 11:28:18
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36277541
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zloy den
Участник
Хм, как я понимаю, прямое моделирование не пройдет по скорости? Черт, что-то напоминает, но не могу понять что. Может попробовать поискать циклы до повторяющегося состояния?
...
Рейтинг: 0 / 0
28.10.2009, 15:13:05
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36277664
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
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:36:58
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36277670
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
zloy denХм, как я понимаю, прямое моделирование не пройдет по скорости? Черт, что-то напоминает, но не могу понять что. Может попробовать поискать циклы до повторяющегося состояния?
Я тоже не мгновенно сообразил
...
Рейтинг: 0 / 0
28.10.2009, 15:38:18
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36277714
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zloy den
Участник
RT183.1zloy denХм, как я понимаю, прямое моделирование не пройдет по скорости? Черт, что-то напоминает, но не могу понять что. Может попробовать поискать циклы до повторяющегося состояния?
Я тоже не мгновенно сообразил

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

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

Ага, вот что оно мне напоминало. Я в дипломе такое делал. Правда, как выяснилось мой генератор псевдослучайных перестановок был практически как у Кнута (выяснил в этом году в отпуске, когда sicp читал). Теперь думаю-радоваться от того что сам додумался до нормального алгоритма или грустить от того что мало знаю и придумываю велосипеды
...
Рейтинг: 0 / 0
28.10.2009, 16:54:45
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278034
Crazzy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Crazzy
Участник
А что произойдет, если частицы столкнутся друг с другом лоб в лоб?
...
Рейтинг: 0 / 0
28.10.2009, 17:55:44
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278037
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Это нарисовано на 2 картинке.
...
Рейтинг: 0 / 0
28.10.2009, 17:57:30
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278060
Crazzy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Crazzy
Участник
Интересная фишка при таких вариантах соударений: траектория 1-го шара после соударения становится равной траектории 2-го, если бы виртуально этого соударения не было и 2-й виртуально летел бы в пустоте.
По крайней мере при лобовом столкновении это так, при косом также, при столкновении с отражением также.
...
Рейтинг: 0 / 0
28.10.2009, 18:12:24
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278068
Crazzy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Crazzy
Участник
CrazzyИнтересная фишка при таких вариантах соударений: траектория 1-го шара после соударения становится равной траектории 2-го, если бы виртуально этого соударения не было и 2-й виртуально летел бы в пустоте.
По крайней мере при лобовом столкновении это так, при косом также, при столкновении с отражением также.
Может конечно объяснил кривовато, но по рисункам ощущение, что траектория всех шариков не будет отличаться от наложения всех траекторий движения каждого шарика в предположении, что соударений не было. Просто при соударении траектория сохраняется, но шарики как бы меняются "номерами".
Блин, и тут кажется тоже кривовато объяснил.
...
Рейтинг: 0 / 0
28.10.2009, 18:15:35
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278073
Crazzy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Crazzy
Участник
CrazzyCrazzyИнтересная фишка при таких вариантах соударений: траектория 1-го шара после соударения становится равной траектории 2-го, если бы виртуально этого соударения не было и 2-й виртуально летел бы в пустоте.
По крайней мере при лобовом столкновении это так, при косом также, при столкновении с отражением также.
Может конечно объяснил кривовато, но по рисункам ощущение, что траектория всех шариков не будет отличаться от наложения всех траекторий движения каждого шарика в предположении, что соударений не было. Просто при соударении траектория сохраняется, но шарики как бы меняются "номерами".
Блин, и тут кажется тоже кривовато объяснил.
В общем, шарики виртуально как бы пролетают друг через друга, но меняются при этом номерами.
Во, вроде с 3-го раза сказал, что хотел
...
Рейтинг: 0 / 0
28.10.2009, 18:18:39
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278077
Дональдак
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дональдак
Участник
Crazzy, все понятно. :)
Т.е. можно моделировать только столкновения частиц со стенками, без учета внутренних.
Так?
...
Рейтинг: 0 / 0
28.10.2009, 18:19:49
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278187
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В задаче сказано
Надо найти координаты частиц в моменты t1, t2, t3,... < 10^12.
Если частицы пронумерованны - то пролетание шариков друг сквозь друга не должно быть. В противном случае - всё равно.
...
Рейтинг: 0 / 0
28.10.2009, 19:32:24
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278291
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
на теорию групп похоже.
Там же состояния начнут повторятся
...
Рейтинг: 0 / 0
28.10.2009, 21:17:38
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278308
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
CrazzyИнтересная фишка при таких вариантах соударений: траектория 1-го шара после соударения становится равной траектории 2-го, если бы виртуально этого соударения не было и 2-й виртуально летел бы в пустоте.
По крайней мере при лобовом столкновении это так, при косом также, при столкновении с отражением также.
йес, это решающее наблюдение
(нас не просят найти где будет частица №5, а где №999 и т.д.,
да и какая разница, если каждая частица неотличима от любой другой,
точно так же как электрон неотличим от любого другого электрона etc
)
...
Рейтинг: 0 / 0
28.10.2009, 21:34:34
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278341
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
ДональдакCrazzy, все понятно. :)
Т.е. можно моделировать только столкновения частиц со стенками, без учета внутренних.
Так?
Моделирование -- это немного громко сказано; достаточно несложной ф-ции
и самое главное: не забываем о полной независимости движений частицы вдоль осей X и Y,
и тогда эта ( 1-мерная ) функция пишется легко и приятно
...
Рейтинг: 0 / 0
28.10.2009, 22:07:07
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278352
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
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:19:24
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278369
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
Они просят:
автор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
28.10.2009, 22:33:12
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278783
Crazzy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Crazzy
Участник
А ну если у шаров никакого заранее заданного номера нет, все они неотличимы друг от друга а сортируются по координатам то все не так и сложно.
В общем, RT183.1, давай, уделай этого Blue Mary
И не забудь ссылку выложить, порадуюсь, что тоже в процессе поучаствовал ))
...
Рейтинг: 0 / 0
29.10.2009, 10:11:24
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36278951
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
CrazzyА ну если у шаров никакого заранее заданного номера нет, все они неотличимы друг от друга а сортируются по координатам то все не так и сложно.
В общем, RT183.1, давай, уделай этого Blue Mary
И не забудь ссылку выложить, порадуюсь, что тоже в процессе поучаствовал ))
Так я же ее сутки назад как сдал: http://www.spoj.pl/status/BOBALLS2/
2.
Это не его задача -- он просто добавил ее на spoj, -- это задача с IPSC 2009
...
Рейтинг: 0 / 0
29.10.2009, 11:08:39
| Ответить | Цитировать | Написать  
Bouncing Balls II
    #36279309
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
Под горячую руку сделал и Снукера: 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
29.10.2009, 12:52:22
| Ответить | Цитировать | Написать  
25 сообщений из 27, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Bouncing Balls II
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&startmsg=36276577&tid=1344136]:
 0ms
get settings:
 8ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 191ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 59ms
get tp. blocked users:
 1ms
others: 218ms
total:  510ms
созд. / загр.: 510ms
x
x
Закрыть


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