Решаем сложные и олимпиадные задачи

[0xDEADBEEF]

toll

1. Распределение не даст ничего

2. ... те ищем их построением выпуклой оболочки, хордане даст нам для реализации ничего.

3. собственно как и любяа точка, нетакли?

4. Такс, ну я не профи, но я даж не знаю как реализовоывать написанное.

X-tender

На четверьфиналах на русском, на полуфиналах раз-от-разу, до половины на английском, финал - полностью

Видимо бактерии в клетках сами живут с каждой итерацией. кактотак.

[X-tender]

0xDEADBEEF

у нас на английском было... Как они плодятся между ходами совершенно непонятно.... ну никак не выходит картина по примеру

Добавлено спустя 5 минут 8 секунд:

toll

По твоей задаче: три точки наиболее удаленные от центра окружности будут лежать на ее границе, т.е. будет 3 хорды

[toll]

X-tender

необязательно .... может и больше точек лежать на окружности...

0xDEADBEEF эту задачу можно решать по разному ... единственно правильного решения нет ... задачка на самом деле больше практическая ну например определить площадь рассеяния неких частиц ... а НОРМАЛЬНОЕ распделение это значит что такая площадь существует ... ну для наглядности : из дробовика выстрелили в мишель и получили ... мишень в дырках ...вот

[X-tender]

toll, может и больше, но я не про это, а про то что для однозначного ответа можно использовать уравнение окружности и перебор по три точки

[toll]

X-tender

непойдет ... нарисуй тупоугольный треугольник ... и впиши его в окружность ...

эту задачу решают методом сжимающейся окружности ... но чтоб уменьшить число переборов ... используют разные подходы например тот что предложил я (он не идеален просто один из вариантов)

[Lakers]

вот как производится заселение:

for i:=1 to 9 do begin

readln(x,y);

inc(a[x,y]);

if (x-1>0)and(a[x-1,y]<>0) then

begin

inc(a[x-1,y]);

if a[x-1,y]>4 then a[x-1,y]:=1;

end;

if (x+1>0)and(a[x+1,y]<>0) then

begin

inc(a[x+1,y]);

if a[x+1,y]>4 then a[x+1,y]:=1;

end;

if (y-1>0)and(a[x,y-1]<>0) then

begin

inc(a[x,y-1]);

if a[x,y-1]>4 then a[x,y-1]:=1;

end;

if (y+1<4)and(a[x,y+1]<>0) then

begin

inc(a[x,y+1]);

if a[x,y+1]>4 then a[x,y+1]:=1;

end;

end.

вобщем инкремируютсяф непустые клетки.

[L0K1]

Lakers

Я примерно так и понял -> они не бесконечно заселяются, а пока не получится стабильная картина, и она получается максимум за 20x20 заселений. Перебор вариантов заселений и сравнение с оригиналом.

[X-tender]

Lakers

уфф... ни за что бы в голову такое не пришло. В задаче про это вообще сказано не было... теперь будем думать

L0K1

вариантов заселений 20!, даже если убрать зеркальные, то все равно перебором никак не вписаться во временные рамки

Добавлено спустя 12 минут 19 секунд:

toll, ну вписаться то впишется, но это будет не минимальный радиус, конечно...

А если попробовать посчитать среднее X и Y? т.е. Xc=(X1+X2+..+Xn)/n и так же Y? или рассчитать центр масс

[0xDEADBEEF]

L0K1

Заселение может и остановится стабильном, может зациклится, а может и уйти в бесконечность. Это-же жизнь, невозможно сказать что будет через N шагов не запустив. "Перебор вариантов заселения" не пройдёт по причине возможного его бесконечного зацикливания.

X-tender

Откуда цифра 20! ? Это варианты начальных заселений? Т.е. куды мы сами селим? Таких вроде бесконечно много.

Тому кто запрогоет, поставлю пивасик) Кто запрогоет перебором - буду поить пока не откажется)

toll

Опиши поконкретнее этот метод?

А теперь открываем школьный учебник геометрии и читаем: "Вокруг произвольного многоугольника нельзя описать окружность". Вот. А ято наивный подума на оболочку. Итог - эвристика и приближенное решение. И пербор, перебор, перебор...

[X-tender]

0xDEADBEEF

мы бесконечно не можем заселять, мы заселяем однократно, уже единожды заселенные не заселяются

"Вокруг произвольного многоугольника нельзя описать окружность".

нам нужно не именно "описать", т.е. чтобы все точки лежали на окружности, а чтобы все нужные точки находились в круге.

[Lakers]

X-tender в задаче про это сказано...

Процесс рисования заключается в том, что биоинженеры поочередно селят в свободные клетки холста по одной бактерии, при этом в каждой из соседних заселенных клеток (сверху, снизу, справа, слева) количество бактерий увеличивается на одну

[0xDEADBEEF]

X-tender

А, нуда, это я пропустил. ТОгда разве не 40! вроде как МxN.

Нет, не препутал) Можно вроде если он правильный либо его серединные перпендикуляы пересикаются в одной точке (сдаётся мне это одно и тоже).

[muvick]

если перебор то (m*n)! то есть 400! =)

на 9 тесте WA... , какие есть идеи по поводу того какие там ловушки есть.

[Lakers]

muvick

как решаеш?

[muvick]

using namespace std;

int n,m;
int OK;
int x[400],y[400];
unsigned int a[20][20],b[20][20];

void place(int depth)
{
if (depth == m*n) OK = 1;
for (int i=0;i {
for (int j=0;j {
if (OK) return;
if (b[i][j] == 0 ) continue;
if (a[i][j] > b[i][j]) return;
if (a[i][j] == b[i][j])
{
b[i][j] = 0;
if (i > 0) if (b[i-1][j]) b[i-1][j]--;
if (i if (j > 0) if (b[i][j-1]) b[i][j-1]--;
if (j
x[depth] = i;
y[depth] = j;
place(depth+1);
return;
}
}
}
for (int i=0;i {
for (int j=0;j {
if (OK) return;
if (b[i][j] == 5 && a[i][j]==1)
{
a[i][j] = 5;
place(depth);
a[i][j] = 1;
}
}
}
}

int main()
{
cin>>n>>m;
for (int i=0;i {
for (int j=0;j {
cin>>a[i][j];
b[i][j] += 5;
b[i][j] -= (i==0) + (i==n-1) + (j==0) + (j==m-1);
}
}

place(0);

if (!OK) cout<<"No";
else
{
cout<<"Yes"< for (int i=0;i {
cout< }
}

return 0;
}

#include 

массив b - максимально возможное количество бактерий в этой клетке. 1 сама + 4 соседа

если = 0 , то уже пройденная клетка

ясно что если количество бактерий совпадает с максимальным количеством, то заселение в этой клетке должно произойти раньше, чем в соседних

если бактерий больше чем максимум, то аборт.

изза вымирания отдельный цикл - предположения что там было 5 бактерий.

[Lakers]

вообще я думаю её надо решать с конца,т.е. находить точки в обратном порядке, т.е. это ячейки с единицами. после по правилам убирать из соседних ячеек бактерии и дальше снова искать точку но уже предпоследнюю и так далее пока не получим пустую картину.

я думаю поиск в ширину тут поможет...

[muvick]

делал и так, на 8 тесте таймлимит, с оптимизацией делается WA, наверное кривая оптимизация

[Lakers]

а у тебя предусмотрена что картина недоконца заселена изначатьно?

[muvick]

такого не может быть, там написано что дана матрица из цифр от 1 до 4, а если не полностью заселена, то на незаселенных клетках должны быть нули.

[Lakers]

точно...выложи листинг,посмотреть охота.

[muvick]

тот который с конца решает или сначала?

код смотреть в спойлере выше

[Lakers]

тот что на 9 WA.

А можно и оба...

Добавлено спустя 59 минут 11 секунд:

выложи еще с обратным поиском.

[muvick]

using namespace std;

int n,m;
int OK;
int x[400],y[400];
unsigned int a[20][20],b[20][20];

void backtr(int depth)
{
unsigned int c[20][20];
for (int i=0; i for (int j=0; j c[i][j] = b[i][j];

if (depth<0)
{
OK = 1;
return;
}
for (int i=0; i {
for (int j=0; j {
if (OK) return;
switch (b[i][j])
{
case 0:break;
case 1:
if ((a[i][j]&3) != 1) return;
a[i][j] = 0;
b[i][j] = 0;
x[depth] = i;
y[depth] = j;
backtr(depth-1);
return;
default:
if ((a[i][j]&3) == 1)
{
x[depth] = i;
y[depth] = j;
a[i][j]--;
if (i > 0) if (b[i-1][j]) {a[i-1][j]--;b[i-1][j]--;}
if (i if (j > 0) if (b[i][j-1]) {a[i][j-1]--;b[i][j-1]--;}
if (j
b[i][j] = 0;
backtr(depth-1);
b[i][j] = c[i][j];

a[i][j]++;
if (i > 0) if (b[i-1][j]) {a[i-1][j]++;b[i-1][j] = c[i-1][j];}
if (i if (j > 0) if (b[i][j-1]) {a[i][j-1]++;b[i][j-1] = c[i][j-1];}
if (j }
break;
}
}
}
}

int main()
{
cin>>n>>m;
for (int i=0;i {
for (int j=0;j {
cin>>a[i][j];
b[i][j] = 5;
b[i][j] -= (i==0) + (i==n-1) + (j==0) + (j==m-1);
}
}

backtr(n*m-1);

if (!OK) cout<<"No\n";
else
{
cout<<"Yes"< for (int i=0;i {
cout< }
}

return 0;
}

#include 

[X-tender]

Ура!

0xDEADBEEF

готовь пиво

use strict;
my @a;
my @b;
##########################################################
sub print_holst
{
my $i=shift;
my @a=@_;

my $tab;
while ($i>0) {$tab.="\t";$i--;}

foreach my $outer (@a){
print $tab;
foreach my $inner (@{$outer})
{
print "$inner\t";
}
print "\n";
}
}
##########################################################
sub test
{
my @temp=@_;
my $res=1;
foreach my $outer (@temp){
foreach my $inner (@{$outer})
{
if ($inner>0) {$res=0;}
}
}
return $res;
}
##########################################################

sub testing
{
my $i=shift;
my $j=shift;
my $iter=shift;
my @temp;
foreach my $outer (@_){
push @temp,[@{$outer}];
}

my $res=0;
print "$iter\t$i:$j\n";
print_holst($iter,@temp);
print "\n";
if (($i!=-1)&&($j!=-1))
{
$temp[$i][$j]--;
if (($i-1>=0) && ($temp[$i-1][$j]>0)) {$temp[$i-1][$j]--;$temp[$i-1][$j]=1 if $temp[$i-1][$j]==4;}
if (($i+1>=0) && ($temp[$i+1][$j]>0)) {$temp[$i+1][$j]--;$temp[$i+1][$j]=1 if $temp[$i+1][$j]==4;}
if (($j-1>=0) && ($temp[$i][$j-1]>0)) {$temp[$i][$j-1]--;$temp[$i][$j-1]=1 if $temp[$i][$j-1]==4;}
if (($j+1>=0) && ($temp[$i][$j+1]>0)) {$temp[$i][$j+1]--;$temp[$i][$j+1] if $temp[$i][$j+1]==4;}
}

BLOOP:
for($i=0;$i<3;$i++)
{
for ($j=0;$j<3;$j++)
{
if ($temp[$i][$j]==1)
{
$res=testing($i,$j,$iter+1,@temp);
last BLOOP if $res;
}
}
}

print_holst($iter,@temp);
print "\n";
return test(@temp) || $res;
}

##########################################################
open IN,"input1.txt";
##########################################################
while ()
{
push @a, [split ' ',$_];
push @b, [split ' ',$_];
}

##########################################################
print_holst(0,@a);
print "\n--------------------------\n";
##########################################################
if (testing(-1,-1,0,@a)) {print "ura\n";}
else {print "blin\n";}

Добавлено спустя 3 минуты 34 секунды:

Вкратце решение такое додумался сразу как только сказали про не заселение если в клетке 0

Решаем с конца - в последней заселенной клетке всегда будет 1, т.к. до этого туда никто никого подселить не мог, соответственно рекурсивно перебираем клетки с 1

Добавлено спустя 4 минуты 10 секунд:

Блин устал... на плюсы завтра перепишу и загоню на проверку, впрочем я думаю теперь и так поверите

[muvick]

для 3х3 это и вправду решение, но для больших не потянет, так как при 5 бактериях 4 умирают, и может быть что не эта клетка было заселена последней.