Перейти к содержанию

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


Рекомендуемые сообщения

toll

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

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

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

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

X-tender

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

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

Ссылка на комментарий

0xDEADBEEF

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

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

toll

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

Ссылка на комментарий

X-tender

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

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

Ссылка на комментарий

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

Ссылка на комментарий

X-tender

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

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

Ссылка на комментарий

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

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.

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

Ссылка на комментарий

Lakers

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

Ссылка на комментарий

Lakers

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

L0K1

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

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

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

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

Ссылка на комментарий

L0K1

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

X-tender

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

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

toll

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

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

Ссылка на комментарий

0xDEADBEEF

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

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

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

Ссылка на комментарий

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

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

Ссылка на комментарий

X-tender

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

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

Ссылка на комментарий


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 бактерий.

Ссылка на комментарий

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

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

Ссылка на комментарий

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

Ссылка на комментарий


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 

Ссылка на комментарий

Ура!

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 секунд:

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

Ссылка на комментарий

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

Ссылка на комментарий

Пожалуйста, войдите, чтобы комментировать

Вы сможете оставить комментарий после входа в



Войти
  • Последние посетители   0 пользователей онлайн

    • Ни одного зарегистрированного пользователя не просматривает данную страницу
×
×
  • Создать...