ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Электрофорез
25 сообщений из 37, страница 1 из 2
  1  все
Электрофорез
    #35540628
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
3002. Electrophoretic
Problem code: ELECTRO

Scientist Frank, majoring in electrochemistry, has developed line-shaped strange electrodes called F-electrodes. During being activated, each F-electrode causes a special potential on and between the two lines touching the F-electrode's endpoints at a right angle. Then electrically-charged particles located inside the potential area get to move in the direction parallel to the potential boundary (i.e. perpendicular to the F-electrode), either toward or against F-electrode. The moving direction can be easily controlled between the two possibles; it is also possible to get particles to pass through F-electrodes. In addition, unlike ordinary electrodes, F-electrodes can affect particles even infinitely far away, as long as those particles are located inside the potential area. On the other hand, two different F-electrodes cannot be activated at a time, since their potentials conflict strongly.

We can move particles on our will by controlling F-electrodes. However, in some cases, we cannot lead them to the desired positions due to the potential areas being limited. To evaluate usefulness of F-electrodes from some aspect, Frank has asked you the following task: to write a program that finds the shortest distances from the particles' initial positions to their destinations with the given sets of F-electrodes.


Input
The input consists of multiple test cases. The first line of each case contains N(1 ≤ N ≤ 100) which represents the number of F-electrodes. The second line contains four integers xs, ys, xt and yt, where (xs, ys) and (xt , yt) indicate the particle’s initial position and destination. Then the description of N F-electrodes follow. Each line contains four integers Fxs, Fys, Fxt and Fyt, where (Fxs, Fys) and (Fxt , Fyt) indicate the two endpoints of an F-electrode. All coordinate values range from 0 to 100 inclusive.

The input is terminated by a case with N = 0.

Output
Your program must output the case number followed by the shortest distance between the initial position to the destination. Output "Impossible" (without quotes) as the distance if it is impossible to lead the elementary particle to the destination. Your answers must be printed with five digits after the decimal point.

Example
Input:
2
2 1 2 2
0 0 1 0
0 1 0 2
0

Output:
Case 1: 3.00000


--------------------------------------------------------------------------------
Added by: Jin Bin
Date: 2008-09-08
Time limit: 10s
Source limit: 50000B
Languages: All except: C99 strict
Resource: JAG wintercamp 08, day2
...
Рейтинг: 0 / 0
15.09.2008, 19:46
| Ответить | Цитировать | Написать  
Электрофорез
    #35540639
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
Подскажите, не решение, а почему это a shortest path проблем?
Я этого в упор не вижу. Вижу 6-7 вариантов, которые нужно сосчитать без всяких переборов и выбрать из них наикратчайший.
Но это не проходит.
...
Рейтинг: 0 / 0
15.09.2008, 19:52
| Ответить | Цитировать | Написать  
Электрофорез
    #35540646
C#C++
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C#C++
Гость
Нельзя ли в двух словах (но на русском), в чем суть задачи. У меня с английским не очень, переводить влом
...
Рейтинг: 0 / 0
15.09.2008, 19:56
| Ответить | Цитировать | Написать  
Электрофорез
    #35540650
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
rettyПодскажите, не решение, а почему это a shortest path проблем?Замените каждый из электродов на коридор, границами которого являются прямые, проведенные через концы электродов и перпендикулярные самому электроду.
...
Рейтинг: 0 / 0
15.09.2008, 20:00
| Ответить | Цитировать | Написать  
Электрофорез
    #35540653
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
rettyПодскажите, не решение, а почему это a shortest path проблем?
Я этого в упор не вижу. Вижу 6-7 вариантов, которые нужно сосчитать без всяких переборов и выбрать из них наикратчайший.
Но это не проходит.Потому что это действительно кратчайший путь.
Читай внимательнее описание электродов. Если кратко, то: "электрон движется перпендикулярно к или от электрода".
...
Рейтинг: 0 / 0
15.09.2008, 20:01
| Ответить | Цитировать | Написать  
Электрофорез
    #35540677
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
Тут могут попереть недопонятки, поэтому я лучше покажу свой код.
Разбираться в нем не обязательно, но мою идею ухватить можно. Но она не работает.
Наш китайский тов. Jin Bin, the problemsetter, прямо сказал: это задача поиска наикратчайшего пути
и таким маленьким кодом (как у меня) ее вряд ли можно сделать.

Все вертикальные электроды я проецирую на ось Y, все горизонтальные - на ось X... и фперед.
Даже случай совпадения начальной и конечной позиций учитываю, когда вообще электроды не нужны.

Код: 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.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
tc =  0 
while  1 :
    n = input()
    if n ==  0 :
        break
    x1, y1, x2, y2 = map(int, raw_input().split())
    ax, ay = [ 0 ]* 101 , [ 0 ]* 101 
    for i in range(n):
        xx1, yy1, xx2, yy2 = map(int, raw_input().split())
        if yy1 == yy2:
            xx1, xx2 = min(xx1, xx2), max(xx1, xx2)
            for j in range(xx1, xx2 +  1 ):
                ax[j] =  1 
        if xx1 == xx2:
            yy1, yy2 = min(yy1, yy2), max(yy1, yy2)
            for j in range(yy1, yy2 +  1 ):
                ay[j] =  1 
                
    if x1 == x2 and y1 == y2:
        tc +=  1 
        print 'Case ' + str(tc) + ': 0.00000'
        continue
    
    res = [ 999 ,  999 ,  999 ,  999 ,  999 ,  999 ,  999 ]
    
    #v. 0 
    if ay[y1] ==  1  and ay[y2] ==  1 :
        i = x1
        while i >  0  and ax[i] ==  0 :
            i -=  1 
        if ax[i] ==  1 :
            res[ 0 ] = abs(x1 - i) + abs(x2 - i) + abs(y1 - y2)
            
    #v. 1 
    if ay[y1] ==  1  and ay[y2] ==  1 :
        i = x1
        while i <  100  and ax[i] ==  0 :
            i +=  1 
        if ax[i] ==  1 :
            res[ 1 ] = abs(x1 - i) + abs(x2 - i) + abs(y1 - y2)
            
    #v. 2 
    if ax[x1] ==  1  and ax[x2] ==  1 :
        i = y1
        while i >  0  and ay[i] ==  0 :
            i -=  1 
        if ay[i] ==  1 :
            res[ 2 ] = abs(y1 - i) + abs(y2 - i) + abs(x1 - x2)
            
    #v. 3 
    if ax[x1] ==  1  and ax[x2] ==  1 :
        i = y1
        while i <  100  and ay[i] ==  0 :
            i +=  1 
        if ay[i] ==  1 :
            res[ 3 ] = abs(y1 - i) + abs(y2 - i) + abs(x1 - x2)
            
    #v. 4 
    if ay[y1] ==  1  and y1 == y2:
        res[ 4 ] = abs(x1 - x2)
        
    #v. 5 
    if ax[x1] ==  1  and x1 == x2:
        res[ 5 ] = abs(y1 - y2)
        
    #v. 6 
    if (ay[y1] ==  1  and ax[x2] ==  1 ) or (ax[x1] ==  1  and ay[y2] ==  1 ):
        res[ 6 ] = abs(x1 - x2) + abs(y1 - y2)
        
    ans = min(res)

    tc +=  1 

    if ans ==  999 :
        print 'Case ' + str(tc) + ': Impossible'
    else:
        print 'Case ' + str(tc) + ': ' + str(ans) + '.00000'
...
Рейтинг: 0 / 0
15.09.2008, 20:20
| Ответить | Цитировать | Написать  
Электрофорез
    #35540687
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
C#C++Нельзя ли в двух словах (но на русском), в чем суть задачи. У меня с английским не очень, переводить влом
типа есть электроды в виде линий разных размеров и положений, гориз. и верт.
В любой момент может быть включен только ОДИН электрод; электрод может пропускать частицу
через себя, отталкивать или притягивать, строго перпендикулярно к свой линии
Надо найти наикратч. путь для частицы, если он вообще есть, включая/ выключая или меняя их знак с + на -, соответствующие электроды
...
Рейтинг: 0 / 0
15.09.2008, 20:26
| Ответить | Цитировать | Написать  
Электрофорез
    #35540688
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
если бы я сразу увидел, что это сложнее, чем я написал, я бы ее вообще не делал;
а сейчас ну просто не могу придумать "нелинейный" случай, на котором я обламываюсь
...
Рейтинг: 0 / 0
15.09.2008, 20:28
| Ответить | Цитировать | Написать  
Электрофорез
    #35540703
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
rettyтипа есть электроды в виде линий разных размеров и положений, гориз. и верт.что-то не найду в первом посте ничего насчет "гориз. и верт."
...
Рейтинг: 0 / 0
15.09.2008, 20:41
| Ответить | Цитировать | Написать  
Электрофорез
    #35540722
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
miksoft rettyтипа есть электроды в виде линий разных размеров и положений, гориз. и верт.что-то не найду в первом посте ничего насчет "гориз. и верт."
там упоминаются potential boundaries, но неважно.
Я ассертами уже ВСЁ проверил.
Там только целые числа, 0 <= N <= 100
И все отрезки только или гориз. или вертик.: assert (xx1 == xx2) or (yy1 == yy2)
...
Рейтинг: 0 / 0
15.09.2008, 20:52
| Ответить | Цитировать | Написать  
Электрофорез
    #35540728
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
И что-то я не очень понял, как to write a program that finds the shortest distances from the particles' initial positions to their destinations with the given sets of F-electrodes поможет To evaluate usefulness of F-electrodesНапример, кратчайших путей может быть несколько, но в каждом из этих путей будут задействованы разные электроды (и даже разное их количество).
...
Рейтинг: 0 / 0
15.09.2008, 20:59
| Ответить | Цитировать | Написать  
Электрофорез
    #35540755
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
usefulness -- это для прикола, а найти надо длину, а не сам путь или какие электроды на этом пути надо включать/выключать
...
Рейтинг: 0 / 0
15.09.2008, 21:32
| Ответить | Цитировать | Написать  
Электрофорез
    #35540768
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
Я проверяю все (как мне кажется) возможные варианты.
Первые 4 -- это как на рисунке в первом посте; влево, вправо, вниз, вверх.
И еще такие (+ симметричные им, для другой оси):
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
    |
    |         *A
    |

        *B
    _______                                       X
---------------------------------------------------> 
Ответ: abs(x1 - x2) + abs(y1 - y2)


|Y
|
|       *A
|
|
|       *B
|
|    __________электрод_____                      X
---------------------------------------------------> 
Ответ: abs(y1 - y2)

Если есть гориз. электрод от x = 3 до x = 8, то в массиве оси X: ax[3..8] <-- 1.
...
Рейтинг: 0 / 0
15.09.2008, 21:53
| Ответить | Цитировать | Написать  
Электрофорез
    #35540770
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
|
|         *A


     *B
    __________                                    X
---------------------------------------------------> 
Ответ: abs(x1 - x2) + abs(y1 - y2)
-------------------------------------

|Y
|
|       *A
|
|
|       *B
|
|    __________электрод_____                      X
---------------------------------------------------> 
Ответ: abs(y1 - y2)
------------------------
Если есть гориз. электрод от x = 3 до x = 8, то в массиве оси X: ax[3..8] <-- 1.
...
Рейтинг: 0 / 0
15.09.2008, 21:57
| Ответить | Цитировать | Написать  
Электрофорез
    #35540774
C#C++
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C#C++
Гость
rettyusefulness -- это для прикола, а найти надо длину, а не сам путь или какие электроды на этом пути надо включать/выключатьЕсли я правильно понял, то задача тривиальна.

Есть 2 основных случая:

1) т.(xs, ys) проецируется на вертикальный электрод, т. (xt, yt) - на горизонтальный.
Тогда двигаем заряд на (xt, ys), потом на (xt, yt)

2) т.(xs, ys) и т.(xt, yt) проецируются на вертикальные электроды. Тогда ищем горизонтальный электрод, который содержит точку (x1, y1), такую, что либо x1 находится между xs и xt, либо сумма расстояний от x1 до xs и xt минимальна (тогда x1 будет лежать на краю электрода). Далее заряд имеет такую траекторию: (xs, ys) - (x1, ys) - (x1, yt) - (xt, yt). Если нет горизонтальных электродов, то нет пути.

Заменяя в данном примере слова "горизонтальный" на "вертикальный" (и наоборот) + добавляя разные частные случаи, получаем все варианты расположений электродов. Длина пути вычисляется элементарно.
...
Рейтинг: 0 / 0
15.09.2008, 22:01
| Ответить | Цитировать | Написать  
Электрофорез
    #35540777
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
>Если я правильно понял, то задача тривиальна.

Вот я тоже "думал", да облажался. Мне просто нужен контр-пример где мы с тобой ошибаемся.
...
Рейтинг: 0 / 0
15.09.2008, 22:05
| Ответить | Цитировать | Написать  
Электрофорез
    #35540793
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
Т.е. я вижу только эти три формы путей (+ их повороты на 90/180 гр.):

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
 1 .
_____________


 2 .
|
|
|
|
|
|________________________


 3 .
 ___________________
|
|
|
|
|_____________________________
Более сложных путей я не представляю.
В смысле, представляю, конечно, но они всегда избыточны.
...
Рейтинг: 0 / 0
15.09.2008, 22:22
| Ответить | Цитировать | Написать  
Электрофорез
    #35540805
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
Еще такой (но по-любому он в моем коде просчитывается):

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
 4 .
|A
|
|
|_______________________________
                                |
                                |
                                |
                                |
                                |
                                |
                                |B
...
Рейтинг: 0 / 0
15.09.2008, 22:36
| Ответить | Цитировать | Написать  
Электрофорез
    #35541002
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
Приплыли.
Из мово прайвита от проблемсеттераit's not assumed that all semgents is parallel to the coordinate axis.

Смотрим на картинку (линк дать не могу; это видно только под моим логином).
Строка №11, но никакой рантайм ерры не было, а был wrong answer.
Чуйвствую себя обманутым вкладчиком и мавродией в одном лице.
...
Рейтинг: 0 / 0
16.09.2008, 06:48
| Ответить | Цитировать | Написать  
Электрофорез
    #35542668
lllIIIlI
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
lllIIIlI
Гость
а можете записать условие задачи в более математическом виде:

функция цели:
F(x1,x2,...) -> min

область определения неизвестных:
a1 < x1 < b1,
a2 < x2 < b2,
...

ограничения:
g1(x1,x2,...) > 0,
g2(x1,x2,...) > 0,
g3(x1,x2,...) >= 0,
g4(x1,x2,...) = 0,
...
...
Рейтинг: 0 / 0
16.09.2008, 17:42
| Ответить | Цитировать | Написать  
Электрофорез
    #35542756
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
да как-то охоты большой нет, из-за этой непонятки с "(не)параллельностью";
или дождусь когда кто-нибудь другой сдаст (пока никто даже попыток не делал)
...
Рейтинг: 0 / 0
16.09.2008, 18:19
| Ответить | Цитировать | Написать  
Электрофорез
    #35542799
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
Во дела, поменял assert на

Код: plaintext
1.
2.
        if xx1 != xx2 and yy1 != yy2:
            print xx1 /  0

и получил runtime error (NZEC) 0.02s 3.7M PYTH
...
Рейтинг: 0 / 0
16.09.2008, 18:37
| Ответить | Цитировать | Написать  
Электрофорез
    #35542852
C#C++
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C#C++
Гость
rettyВо дела, поменял assert на

Код: plaintext
1.
2.
        if xx1 != xx2 and yy1 != yy2:
            print xx1 /  0

и получил runtime error (NZEC) 0.02s 3.7M PYTHЗначит, все-таки есть электроды "под углом"?
...
Рейтинг: 0 / 0
16.09.2008, 19:14
| Ответить | Цитировать | Написать  
Электрофорез
    #35542853
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
rettyВо дела, поменял assert на

и получил runtime error (NZEC) 0.02s 3.7M PYTH
Может, там просто отключены assert-ы?
...
Рейтинг: 0 / 0
16.09.2008, 19:14
| Ответить | Цитировать | Написать  
Электрофорез
    #35542906
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
вроде бы нет (сами админы рекомендуют "вставляйте ассерты, если в чем сомневаетесь")
Хотя может там сам проблемсеттер может (под)менять ризалт прогона кода. Хрен его знает как там у них всё устроено.
И бывает такое (но очень редко): The official test cases were incorrect, but it was fixed now. If you find any problems, please contact me.
...
Рейтинг: 0 / 0
16.09.2008, 19:52
| Ответить | Цитировать | Написать  
25 сообщений из 37, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Электрофорез
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=35540653&tid=1344884]:
 0ms
get settings:
 6ms
get forum list:
 10ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 166ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 60ms
get tp. blocked users:
 1ms
others: 224ms
total:  486ms
созд. / загр.: 486ms
x
x
Закрыть


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