1. Затори на дорогах (JAMMINGбалів
Автомобільні затори трапляються усюди, навіть у нашому невеличкому містечку. Дороги у нас мають дві смуги в одному напрямку, а автомобілі є лише двох типів габаритів: легкові (у пробці займають квадрат 1х1, якщо за 1 взяти ширину смуги) та вантажні (у пробці займають місце 2х1 вздовж смуги).
Водії дуже дисципліновані у тому плані, що вони не стають поперек смуги, не займають чужу площу, але й не залишають вільних місць.
Визначте, скільки існує різних за послідовністю типів машин (легкова - вантажна) заторів між мерією міста та моїм будинком, якщо вони на одній вулиці, а відстань між ними S.
Формат вхідних даних:
Вхідний файл містить єдине число S (1£S£10000) – задана відстань.
Формат вихідних даних:
Єдиний рядок вихідного файлу повинен містити відповідь – кількість розстановок автомобілів в першій і другій смузі разом. Достеменно відомо, що кількість цифр у відповіді не перевищує 700.
JAMMING. DAT | JAMMING. SOL |
2 | 4 |
Приклад вхідних та вихідних даних:
Ідея: Кількість послідовностей для однієї смуги рівне N-1 числу ФІБОНАЧІ, а для двох смуг їх добуток.
const maxl = 1000;
type longint = array [1..maxl] of byte;
procedure add(a, b: longint; var c: longint);
var i, p: integer;
begin
p:=0;
for i:=maxl downto 1 do begin
c[i]:=(a[i]+b[i]+p) mod 10;
p:=(a[i]+b[i]+p) div 10;
end;
end;
procedure mul(a, b: longint; var c: longint);
var i, j, p, t: integer;
begin
fillchar(c, sizeof(c), 0);
for i:=maxl downto 1 do begin
p:=0;
for j:=maxl downto 1 do begin
t:=c[i+j-maxl] + a[i]*b[j] + p;
c[i+j-maxl]:=t mod 10;
p:=t div 10;
end;
end;
end;
var f0, f1, f2: longint;
i, n: integer;
begin
assign(input, 'jamming. dat'); reset(input );
assign(output, 'jamming. sol'); rewrite(output);
readln(n);
fillchar(f0, sizeof(f0), 0);
fillchar(f1, sizeof(f1), 0); f1[maxl]:=1;
for n:=1 to n do begin
add(f0, f1, f2);
f0:=f1; f1:=f2;
end;
mul(f1, f1, f1);
i:=1; while f1[i]=0 do inc(i);
for i:=i to maxl do write(f1[i]); writeln;
close(input); close(output);
end.
TEST0
2
4
TEST1
3
9
TEST2
5
64
TEST3
10
7921
TEST4
12
54289
TEST5
15
974169
TEST6
17
6677056
TEST7
20
119814916
TEST8
406
26119758617711589056112697415390198449842420677629708065941562510465159210226699689676276740874458452907821742441231594373811457250753819075046821231149755254052955180769
TEST9
1010
74823596808418144970832931075942523313227960460987707983746990533162495270593096468852414371653558710956498765971157709676253706234052411287783327917220645748754354985882428209769136507030647457402031371855271988911864004344052461849484499317176804346208410597013046033628808875330074698301533647372254009620738815298130640699378693817405983105033855835318787824438605173037801038556184408842470090070596513692249434081796
3 -- 2
4 -- 3
5 -- 5
6 -- 8
7 -- 13
8 -- 21
9 -- 34
10 -- 55
11 -- 89
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
5
2. Найкоротший шлях (PATH)
На площині задано 
прямокутників зі сторонами, паралельними осям координат, та дві різні точки 
та 
. Ніякі два прямокутники не перетинаються і не дотикаються одне одного. Точки та не належать жодному з прямокутників. Шлях між точками та може дотикатися вершин і проходити вздовж сторін прямокутників, але не повинен заходити всередину прямокутників. Визначте довжину 
найкоротшого шляху між точками та .
Формат введення/виведення:
Напишіть програму PATH, яка читає координати точок та прямокутників з файлу PATH. DAT і записує довжину найкоротшого шляху у файл PATH. SOL.
У першому рядку файлу PATH. DAT знаходиться число . У другому рядку знаходяться координати 
та 
точки . У третьому рядку знаходяться координати 
та 
точки . У наступних рядках знаходиться по чотири числа 
– координати протилежних вершин 
-го прямокутника.
Шукана довжина повинна бути визначена із точністю до 
(це значить, що ваша відповідь не повинна відрізнятися від відповіді журі більш, ніж на 
).
Обмеження: 
.
Приклад:
PATH. DAT: 2 2 1 | PATH. SOL: 20.093368739633874 |
Розв’язок задачі:
Дана задача є нестандартною інтерпретацією стандартних алгоритмів пошуку найкоротших шляхів на графі. Одразу ж можна сказати, що шуканий шлях проходитиме лише через точки А та B і вершини прямокутників (можливо, уздовж їх сторін). Тому закономірно, зводячи задачу до графа, вважати вершинами останнього вершини прямокутників, а ребрами – можливість пролягання шляху по відрізку, що сполучає пару таких вершин.
Для можливості роботи з нашим графом необхідно для кожної пари вершин визначити, чи існує між ними ребро. Тобто, чи не перетинає якийсь із прямокутників відрізок, що їх сполучає.
Нам заздалегідь відомо, що жодна з вершин не лежить всередині жодного прямокутника. Тому відрізок може перетнути якийсь із прямокутників, якщо перетне хоча б одну його сторону. Тут корисно буде написати підпрограму, яка перевірятиме, чи перетинаються два відрізки.
Можна користуватися такою умовою: відрізок AB перетинає відрізок CD тоді і тільки тоді, коли точки A та B знаходяться по різні боки від прямої CD і навпаки, точки C та D знаходяться по різні боки від прямої AB.
function line2line(x11,y11,x12,y12,
x21,y21,x22,y22:real):boolean;
function cmp(x, y,x1,y1,x2,y2:real):real;
var a, b,c:real;
begin
a:=y1-y2;
b:=x2-x1;
c:=x1*y2-x2*y1;
cmp:=a*x+b*y+c;
end;
begin
line2line:=(cmp(x11,y11,x21,y21,x22,y22)*
cmp(x12,y12,x21,y21,x22,y22) <0) and
(cmp(x21,y21,x11,y11,x12,y12)*
cmp(x22,y22,x11,y11,x12,y12) <0);
end;
На базі цієї підпрограми можна написати ще одну, яка визначатиме, чи перетинаються прямокутник та відрізок.
function line2rect(x1,y1,x2,y2,rx1,ry1,rx2,ry2:real):boolean;
begin
line2rect:=line2line(x1,y1,x2,y2,rx1,ry1,rx1,ry2)
or line2line(x1,y1,x2,y2,rx1,ry2,rx2,ry2)
or line2line(x1,y1,x2,y2,rx2,ry2,rx2,ry1)
or line2line(x1,y1,x2,y2,rx2,ry1,rx1,ry1);
end;
Слід звернути увагу на те, що у даній задачі ми маємо справу зі зваженим графом. Якщо ребро між двома вершинами існує, то припишемо йому вагу, рівну його довжині.
Тепер, коли граф побудовано, можна реалізувати на ньому алгоритм Дейкстри для знаходження найкоротшого шляху між точками A та B.
const maxn = 30;
infinity = 1e20;
function cmp(x, y,x1,y1,x2,y2:real):real;
var a, b,c:real;
begin
a:=y1-y2;
b:=x2-x1;
c:=x1*y2-x2*y1;
cmp:=a*x+b*y+c;
end;
function line2line(x11,y11,x12,y12,
x21,y21,x22,y22:real):boolean;
begin
line2line:=(cmp(x11,y11,x21,y21,x22,y22)*
cmp(x12,y12,x21,y21,x22,y22)<0) and
(cmp(x21,y21,x11,y11,x12,y12)*
cmp(x22,y22,x11,y11,x12,y12)<0);
end;
function line2rect(x1,y1,x2,y2,rx1,ry1,rx2,ry2:real):boolean;
begin
line2rect:=line2line(x1,y1,x2,y2,rx1,ry1,rx1,ry2)
or line2line(x1,y1,x2,y2,rx1,ry2,rx2,ry2)
or line2line(x1,y1,x2,y2,rx2,ry2,rx2,ry1)
or line2line(x1,y1,x2,y2,rx2,ry1,rx1,ry1);
end;
function len(x1,y1,x2,y2:real):real;
begin
len:=sqrt(sqr(x1-x2)+sqr(y1-y2));
end;
var i, j,k, n,qh, qt:integer;
r:array [0..maxn*4+1,1..2] of real;
g:array [0..maxn*4+1,0..maxn*4+1] of boolean;
Q:array [1..maxn*maxn] of byte;
s:array [0..maxn*4+1] of real;
begin
assign(input,'path. dat'); reset(input);
assign(output,'path. sol'); rewrite(output);
readln(n, r[0,1],r[0,2],r[n*4+1,1],r[n*4+1,2]);
for i:=1 to n do begin
readln(r[i,1],r[i,2],r[i+2*n,1],r[i+2*n,2]);
r[i+n,1]:=r[i,1]; r[i+n,2]:=r[i+2*n,2];
r[i+3*n,1]:=r[i+2*n,1]; r[i+3*n,2]:=r[i,2];
end;
for i:=0 to 4*n do
for j:=i+1 to 4*n+1 do
if (i=0)or(j=4*n+1)or(i+2*n<>j) then begin
g[i, j]:=true;
for k:=1 to n do
if line2rect(r[i,1],r[i,2],
r[j,1],r[j,2],
r[k,1],r[k,2],
r[k+2*n,1],r[k+2*n,2]) then
begin
g[i, j]:=false;
break;
end;
g[j, i]:=g[i, j];
end;
for i:=1 to maxn*4+1 do s[i]:=infinity;
Q[1]:=0; qh:=1; qt:=1;
while qh<=qt do begin
for i:=1 to maxn*4+1 do
if g[Q[qh],i] and
(len(r[Q[qh],1],r[Q[qh],2],
r[i,1],r[i,2])+s[Q[qh]]<s[i]) then
begin
inc(qt);
Q[qt]:=i;
s[i]:=len(r[Q[qh],1],r[Q[qh],2],
r[i,1],r[i,2])+s[Q[qh]];
end;
inc(qh);
end;
writeln(s[4*n+1]:0:6);
close(input); close(output);
end.
TEST0
2
2
1
20.093369
TEST1
1
0 0
0 3
102.225300
TEST2
1
5.000000
TEST3
1
12.000000
TEST4
1
12.000000
TEST5
2
12.000000
TEST6
3
0
12.211450
TEST7
5
0 0
11 11
15.556349
TEST8
5
0 0
11 11
16.119695
TEST8
10
1 0
2
11
13
15
17
1
102.225300
