Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Электрофорез / 25 сообщений из 37, страница 1 из 2
  1  все
15.09.2008, 19:46:50
    #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:52:15
    #35540639
retty
retty
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
Подскажите, не решение, а почему это a shortest path проблем?
Я этого в упор не вижу. Вижу 6-7 вариантов, которые нужно сосчитать без всяких переборов и выбрать из них наикратчайший.
Но это не проходит.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.09.2008, 19:56:16
    #35540646
C#C++
C#C++
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
Нельзя ли в двух словах (но на русском), в чем суть задачи. У меня с английским не очень, переводить влом
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.09.2008, 20:00:36
    #35540650
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
rettyПодскажите, не решение, а почему это a shortest path проблем?Замените каждый из электродов на коридор, границами которого являются прямые, проведенные через концы электродов и перпендикулярные самому электроду.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.09.2008, 20:01:41
    #35540653
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
rettyПодскажите, не решение, а почему это a shortest path проблем?
Я этого в упор не вижу. Вижу 6-7 вариантов, которые нужно сосчитать без всяких переборов и выбрать из них наикратчайший.
Но это не проходит.Потому что это действительно кратчайший путь.
Читай внимательнее описание электродов. Если кратко, то: "электрон движется перпендикулярно к или от электрода".
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.09.2008, 20:20:59
    #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:26:53
    #35540687
retty
retty
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
C#C++Нельзя ли в двух словах (но на русском), в чем суть задачи. У меня с английским не очень, переводить влом
типа есть электроды в виде линий разных размеров и положений, гориз. и верт.
В любой момент может быть включен только ОДИН электрод; электрод может пропускать частицу
через себя, отталкивать или притягивать, строго перпендикулярно к свой линии
Надо найти наикратч. путь для частицы, если он вообще есть, включая/ выключая или меняя их знак с + на -, соответствующие электроды
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.09.2008, 20:28:46
    #35540688
retty
retty
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
если бы я сразу увидел, что это сложнее, чем я написал, я бы ее вообще не делал;
а сейчас ну просто не могу придумать "нелинейный" случай, на котором я обламываюсь
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.09.2008, 20:41:30
    #35540703
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
rettyтипа есть электроды в виде линий разных размеров и положений, гориз. и верт.что-то не найду в первом посте ничего насчет "гориз. и верт."
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.09.2008, 20:52:49
    #35540722
retty
retty
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
miksoft rettyтипа есть электроды в виде линий разных размеров и положений, гориз. и верт.что-то не найду в первом посте ничего насчет "гориз. и верт."
там упоминаются potential boundaries, но неважно.
Я ассертами уже ВСЁ проверил.
Там только целые числа, 0 <= N <= 100
И все отрезки только или гориз. или вертик.: assert (xx1 == xx2) or (yy1 == yy2)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.09.2008, 20:59:44
    #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, 21:32:01
    #35540755
retty
retty
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
usefulness -- это для прикола, а найти надо длину, а не сам путь или какие электроды на этом пути надо включать/выключать
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.09.2008, 21:53:30
    #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:57:00
    #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, 22:01:00
    #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:05:14
    #35540777
retty
retty
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
>Если я правильно понял, то задача тривиальна.

Вот я тоже "думал", да облажался. Мне просто нужен контр-пример где мы с тобой ошибаемся.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.09.2008, 22:22:47
    #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:36:48
    #35540805
retty
retty
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
Еще такой (но по-любому он в моем коде просчитывается):

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

Смотрим на картинку (линк дать не могу; это видно только под моим логином).
Строка №11, но никакой рантайм ерры не было, а был wrong answer.
Чуйвствую себя обманутым вкладчиком и мавродией в одном лице.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.09.2008, 17:42:20
    #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, 18:19:00
    #35542756
retty
retty
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
да как-то охоты большой нет, из-за этой непонятки с "(не)параллельностью";
или дождусь когда кто-нибудь другой сдаст (пока никто даже попыток не делал)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.09.2008, 18:37:47
    #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, 19:14:01
    #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:06
    #35542853
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Электрофорез
rettyВо дела, поменял assert на

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


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