На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
Коротко: BFS & meet in the middle
На перший погляд: досить тупе, хоча й громіздкувате застосування пошуку в ширину; і взагалі -- передерта і слабко змінена задача 2001 з інформатікса (http://informatics.mccme.ru/moodle/mod/ … terid=2001)
...тільки от правильна реалізація звичайного пошуку в ширину цілком заслужено набирає як правило 60--70%% балів, якщо дуже добре вилизати технічні деталі реалізації, то 75%, І НІЯК НЕ БІЛЬШЕ. Надто великий виходить граф.
Для розв’язання задачі на повний бал, слід модифікувати пошук у ширину ідеєю MEET IN THE MIDDLE. Тобто, робити пошук одночасно і від старта, і від фініша, і зупиняти, коли пошук від старта і пошук від фініша вперше зустрінуться (вперше буде оброблена одна й та сама вершина -- повідомлення змінено лише в межах цих дужок, лише з міркувань благозвучності). Звичайно, мова йде не про справжню одночасність на двох процесорах, а про її емуляцію на одному. Наприклад, так: тримати масив з двох черг, і масив відстаней теж повинен бути вигляду d[2][10000000] (він же d[0..1][0..9999999]) : по одному виміру -- одне з двох значень "від старта"/"від фініша", по іншому -- звичайний номер вершини графа, який у даному випадку є просто значенням числа. І, наприклад, на кожному непарному кроці основного цикла пошуку в ширину працювати з 1-ю чергою та d[1][n], а на кожному парному -- з 0-вою чергою та d[0][n].
Відредаговано Ilya Porublyov (2013-02-17 18:42:08)
Поза форумом
Це все, звичайно, дуже добре, але як Ви прокоментуєте той факт, що в таблиці у мене за першу задачу 50 балів, а на онлайн тестуванні кілька хвилин тому я отримав 90? Така ж сама ситуація виникла ще у багатаьох учасників з мого закладу і не лише по цій задачі.
Поза форумом
Ось результат он-лайн (!) перевірки, того, що прийняла у вас, п. Рубаненко, система в 13-53
Тест Результат Время работы
001 PASSED (+0) 0.02 сек.
002 PASSED (+0) 0.05 сек.
01 PASSED (+2) 0.02 сек.
02 PASSED (+3) 0.02 сек.
03 PASSED (+3) 0.02 сек.
04 PASSED (+3) 0.02 сек.
05 PASSED (+3) 0.02 сек.
06 PASSED (+3) 0.02 сек.
07 PASSED (+3) 0.02 сек.
08 PASSED (+5) 0.02 сек.
09 PASSED (+5) 0.02 сек.
10 PASSED (+5) 0.02 сек.
11 PASSED (+5) 0.02 сек.
12 PASSED (+5) 0.03 сек.
13 FAILED (Wrong Answer) 0.04 сек.
14 FAILED (Wrong Answer) 0.03 сек.
15 PASSED (+5) 0.10 сек.
16 FAILED (Time Out) 0.76 сек.
17 FAILED (Time Out) 0.77 сек.
18 FAILED (Time Out) 0.77 сек.
19 FAILED (Time Out) 0.76 сек.
20 FAILED (Time Out) 0.76 сек.
21 FAILED (Time Out) 0.76 сек.
22 FAILED (Time Out) 0.77 сек.
23 FAILED (Time Out) 0.77 сек.
Прошло тестов: 15 из 25.
Набрано баллов: 50 из 100.
Вм щось зопалу...плутаєте.
Поза форумом
Тест Результат Время работы
00 PASSED (+0) 0.01 сек.
01 PASSED (+4) 0.01 сек.
02 PASSED (+4) 0.01 сек.
03 PASSED (+4) 0.01 сек.
04 PASSED (+4) 0.02 сек.
05 PASSED (+4) 0.01 сек.
06 PASSED (+4) 0.01 сек.
07 PASSED (+4) 0.01 сек.
08 PASSED (+4) 0.01 сек.
09 PASSED (+4) 0.72 сек.
10 FAILED (Time Out) 1.17 сек.
11 FAILED (Time Out) 1.18 сек.
12 PASSED (+4) 0.81 сек.
13 PASSED (+4) 1.15 сек.
14 PASSED (+4) 0.72 сек.
15 PASSED (+4) 1.28 сек.
16 PASSED (+4) 1.13 сек.
17 FAILED (Time Out) 1.51 сек.
18 PASSED (+4) 1.09 сек.
19 PASSED (+4) 1.44 сек.
20 PASSED (+4) 1.08 сек.
21 PASSED (+5) 1.10 сек.
22 PASSED (+5) 1.40 сек.
23 PASSED (+5) 1.45 сек.
24 PASSED (+5) 1.06 сек.
Прошло тестов: 22 из 25.
Набрано баллов: 88 из 100.
А ось результат, що я отримав на онлайн-перевірці по третій задачі...
Можливо це пов"язано з підвищеним навантаженням на сервер під час тестування?
Відредаговано Rubanenko (2013-02-17 18:36:22)
Поза форумом
Наявність тесту 0000 та відсутність тестів 21, 22, 23 наводить на думку, що явно щось не так...
Поза форумом
Ні.
13 FAILED (Wrong Answer) 0.04 сек.
14 FAILED (Wrong Answer) 0.03 сек.
Ось такого при навантаженні не може бути В ПРИНЦИПІ. Я первіряв код, ЯКИЙ СИСТЕМА ПРИЙНЯЛА У ВАС.
Ви, ймовірно, де-що інший
Поза форумом
Будь ласка, припиніть СУТТЄВО редагувати коментарі ПІСЛЯ того, як на них дана відповідь, бо так абсолютно нічого не можна зрозуміти...
Поза форумом
Так, я помилково зкопіював лог з іншої задачі. Але 88 і 80 балів - це теж різні речі.
Поза форумом
І це при тому, що рішення лінійне...
Поза форумом
Ось розв'язок, який ви надіслали, п. Рубаненко. Я не можу зрозуміти,що ви перевіряєте...
type st=string[10];
Var o:array[0..10]of st;
s,s1,s2:st;
used:array[0..10000333]of boolean;
p,c:array[0..10000333]of longint;
ot:array[0..100333]of longint;
n1,k,n2,x,y,u,v,i,j:longint;
pp:integer;
q:char;
procedure add(u:longint);
begin
inc(x);
c[x]:=u;
p[u]:=c[y];
used[u]:=true;
end;
begin
// fillchar(c,sizeof(c),0);
// fillchar(p,sizeof(p),0);
s1:='';
s2:='';
for i:=1 to 7 do
begin
read(q);
s1:=s1+q;
end;
read(q);
for i:=1 to 7 do
begin
read(q);
s2:=s2+q;
end;
o[0]:='';
for i:=1 to 7 do
o[i]:=o[i-1]+'0';
fillchar(used,sizeof(used),false);
val(s1,n1,pp);
val(s2,n2,pp);
c[1]:=n1;
used[n1]:=true;
x:=1;
y:=0;
while x>y do
begin
if used[n2] then break;
inc(y);
v:=c[y];
if (v<9999999)and(not used[v+1]) then add(v+1);
if (v>0)and(not used[v-1]) then add(v-1);
u:=v;
for i:=2 to 9 do
begin
u:=u+v;
if u>9999999 then break;
if (not used[u]) then add(u);
end;
for i:=2 to 9 do
begin
if v mod i<>0 then continue
else u:=v div i;
if not used[u] then add(u);
end;
str(v,s);
s:=o[7-length(s)]+s;
for i:=1 to 6 do
begin
s:=s+s[1];
delete(s,1,1);
val(s,u,pp);
if not used[u] then add(u);
end;
end;
k:=0;
while n2<>n1 do
begin
inc(k);
ot[k]:=n2;
n2:=p[n2];
end;
Write(k,' ',s1);
for i:=k downto 1 do
begin
str(ot[i],s);
s:=o[7-length(s)]+s;
Write(' ',s);
end;
Writeln;
end.Поза форумом
Я Вам зараз про третю задачу кажу. З першою розібрався, але ще є питання про авторське рішення, хоча це вже інша розмова. Зараз моє питання полягає в тому, що результати по третій задачі не збігаються.
Поза форумом
type st=string[10];
Var o:array[0..10]of st;
s,s1,s2:st;
used:array[0..10000333]of boolean;
p,c:array[0..10000333]of longint;
ot:array[0..100333]of longint;
n1,k,n2,x,y,u,v,i,j:longint;
pp:integer;
q:char;
procedure add(u:longint);
begin
inc(x);
c[x]:=u;
p[u]:=c[y];
used[u]:=true;
end;
begin
// fillchar(c,sizeof(c),0);
// fillchar(p,sizeof(p),0);
s1:='';
s2:='';
for i:=1 to 7 do
begin
read(q);
s1:=s1+q;
end;
read(q);
for i:=1 to 7 do
begin
read(q);
s2:=s2+q;
end;
o[0]:='';
for i:=1 to 7 do
o[i]:=o[i-1]+'0';
fillchar(used,sizeof(used),false);
val(s1,n1,pp);
val(s2,n2,pp);
c[1]:=n1;
used[n1]:=true;
x:=1;
y:=0;
while x>y do
begin
if used[n2] then break;
inc(y);
v:=c[y];
if (v<9999999)and(not used[v+1]) then add(v+1);
if (v>0)and(not used[v-1]) then add(v-1);
u:=v;
for i:=2 to 9 do
begin
u:=u+v;
if u>9999999 then break;
if (not used[u]) then add(u);
end;
for i:=2 to 9 do
begin
if v mod i<>0 then continue
else u:=v div i;
if not used[u] then add(u);
end;
str(v,s);
s:=o[7-length(s)]+s;
for i:=1 to 6 do
begin
s:=s+s[1];
delete(s,1,1);
val(s,u,pp);
if not used[u] then add(u);
end;
end;
k:=0;
while n2<>n1 do
begin
inc(k);
ot[k]:=n2;
n2:=p[n2];
end;
Write(k,' ',s1);
for i:=k downto 1 do
begin
str(ot[i],s);
s:=o[7-length(s)]+s;
Write(' ',s);
end;
Writeln;
end.Ось це ви перевіряєте.
А ось це - резулльтат;
001 PASSED (+0) 0.02 сек.
002 PASSED (+0) 0.05 сек.
01 PASSED (+2) 0.02 сек.
02 PASSED (+3) 0.02 сек.
03 PASSED (+3) 0.02 сек.
04 PASSED (+3) 0.02 сек.
05 PASSED (+3) 0.02 сек.
06 PASSED (+3) 0.02 сек.
07 PASSED (+3) 0.02 сек.
08 PASSED (+5) 0.02 сек.
09 PASSED (+5) 0.02 сек.
10 PASSED (+5) 0.02 сек.
11 PASSED (+5) 0.02 сек.
12 PASSED (+5) 0.03 сек.
13 FAILED (Wrong Answer) 0.04 сек.
14 FAILED (Wrong Answer) 0.03 сек.
15 PASSED (+5) 0.10 сек.
16 FAILED (Time Out) 0.77 сек.
17 FAILED (Time Out) 0.77 сек.
18 FAILED (Time Out) 0.77 сек.
19 FAILED (Time Out) 0.77 сек.
20 FAILED (Time Out) 0.77 сек.
21 FAILED (Time Out) 0.77 сек.
22 FAILED (Time Out) 0.76 сек.
23 FAILED (Time Out) 0.76 сек.
Прошло тестов: 15 из 25.
Набрано баллов: 50 из 100.
Поза форумом
Я розумію, що через мою помилку на початку виникло певне недорозуміння, але зараз я питаю про ТРЕТЮ задачу.
Поза форумом
Rubanenko написав:
Я Вам зараз про третю задачу кажу. З першою розібрався, але ще є питання про авторське рішення, хоча це вже інша розмова. Зараз моє питання полягає в тому, що результати по третій задачі не збігаються.
Відкрийте тему по задачі, що вас цікавить, якщо її немає, чітко сформуюйте проблему.
Поза форумом