telerik contest
8 отговора
867 прегледа
Re: telerik contest
"Приемат се само решения, реализирани на езика C#, работещи върху платформата Microsoft .NET Framework 1.1"
'Бах то'о contest, или както там му викат...а що не са указали под кой SP на джамовете тряа да бачкат тия решения? :)))
Quidquid latine dictum sit, altum viditur
'Бах то'о contest, или както там му викат...а що не са указали под кой SP на джамовете тряа да бачкат тия решения? :)))
Quidquid latine dictum sit, altum viditur
Re:
Отново комбинаторна задача. Лимитът от време е много добър. Светлин пак се е постарал.
Варианта с пълно изчерпване го забравяме веднага. Още на първо ниво имаме 2500 възможности.
На второ четене ми идва идеята за отстраняването на най-голямата площадка, но това е доста далеч от оптималното решение. Вероятно повечето участници ще ползват тази стратегия.
Не вярвам недетерминистичните алгоритми да дадат по-добри резултати в по-добро време, пък и кой ще се занимава да оценява вероятностни алгоритми, както са и условията на конкурса.
Минават ми разни мисли за Динамично оптимиране, но никога не съм успявал да реша задача с този метод, така че който го разбира - good luck.
При наложените ограничения със сигурност ще се прибягва към евристика. Примерно, много добра идея е модификация на пълното изчерпване, така че да не бъде толкова пълно. Тоест изчерпване на p нива, прилагане на операциите, след това изчерпване на нови p нива и така. Ще трябва да се калибрира внимателно, така че p да не води до прехвърляне на лимита от време, но пък да бъде максимално, спрямо обема на входните данни.
Похвално, хората са решили да си направят малко евтин PR и да си осигурят кадърни кандидати за работа. Според мен това е честна сделка, любопитно ми е колко участници ще се съберат.
Ако някой е навит да се пробваме, като екип и да си разделим евентуална награда, нека да ми пише в този форум.
Не съм ползвал C#, а и съм се набутал в голяма каша, тоест нямам достатъчно свободно време. Въпреки това един добър екип може да направи много повече от сам човек.
Всъщност, не ме интересуват наградите. Отдавна имам laptop и Pocket PC, по-скоро ми е за екипната работа. Задачата е интересна и е точно за екипна работа. Сигурен съм, че можем да измислим приличен алгоритъм.
Варианта с пълно изчерпване го забравяме веднага. Още на първо ниво имаме 2500 възможности.
На второ четене ми идва идеята за отстраняването на най-голямата площадка, но това е доста далеч от оптималното решение. Вероятно повечето участници ще ползват тази стратегия.
Не вярвам недетерминистичните алгоритми да дадат по-добри резултати в по-добро време, пък и кой ще се занимава да оценява вероятностни алгоритми, както са и условията на конкурса.
Минават ми разни мисли за Динамично оптимиране, но никога не съм успявал да реша задача с този метод, така че който го разбира - good luck.
При наложените ограничения със сигурност ще се прибягва към евристика. Примерно, много добра идея е модификация на пълното изчерпване, така че да не бъде толкова пълно. Тоест изчерпване на p нива, прилагане на операциите, след това изчерпване на нови p нива и така. Ще трябва да се калибрира внимателно, така че p да не води до прехвърляне на лимита от време, но пък да бъде максимално, спрямо обема на входните данни.
Похвално, хората са решили да си направят малко евтин PR и да си осигурят кадърни кандидати за работа. Според мен това е честна сделка, любопитно ми е колко участници ще се съберат.
Ако някой е навит да се пробваме, като екип и да си разделим евентуална награда, нека да ми пише в този форум.
Не съм ползвал C#, а и съм се набутал в голяма каша, тоест нямам достатъчно свободно време. Въпреки това един добър екип може да направи много повече от сам човек.
Всъщност, не ме интересуват наградите. Отдавна имам laptop и Pocket PC, по-скоро ми е за екипната работа. Задачата е интересна и е точно за екипна работа. Сигурен съм, че можем да измислим приличен алгоритъм.
Re:
#include <stdio.h>
void packit(int **board, const int M, const int N)
{
int i, j;
int temp;
int done;
for(i=0; i<M; i++)
do
{
done = 1;
for(j=N-1; j>0; j--)
if(board[i ][j-1]==0 && board[i ][j]!=0)
{
board[i ][j-1] = board[i ][j];
board[i ][j] = 0;
done = 0;
}
}
while(done == 0);
for(i=0; i<M-1; i++)
do
{
done = 1;
if(board[i ][0]==0 && board[i+1][0]!=0)
{
for(j=N-1; j>=0; j--)
{
board[i ][j] = board[i+1][j];
board[i+1][j] = 0;
}
done = 0;
}
}
while(done == 0);
}
void removeit(int **board, const int M, const int N, const int i, const int j, const int c)
{
if(i<0 || j<0 || i>=M || j>=N || board[i ][ j] == 0)
return;
if(board[i ][j] == c)
{
board[ i ][ j ] = 0;
removeit(board, M, N, i-1, j, c);
removeit(board, M, N, i, j-1, c);
removeit(board, M, N, i+1, j, c);
removeit(board, M, N, i, j+1, c);
}
}
void update(const int **board, int **neighbours, const int M, const int N, const int i, const int j, const int c, int *pcnt)
{
if(i<0 || j<0 || i>=M || j>=N || neighbours[i ][j]!=0)
return;
if(board[i ][j] == c)
{
(*pcnt)++;
neighbours[ i ][ j ] = *pcnt;
update(board, neighbours, M, N, i-1, j, c, pcnt);
update(board, neighbours, M, N, i, j-1, c, pcnt);
update(board, neighbours, M, N, i+1, j, c, pcnt);
update(board, neighbours, M, N, i, j+1, c, pcnt);
neighbours[ i ][ j ] = *pcnt;
}
}
void allocate(int **board, int **neighbours, const int M, const int N)
{
int i, j, cnt;
for(i=0; i<M; i++)
for(j=0; j<N; j++)
neighbours[ i ][ j ] = 0;
for(i=0; i<M; i++)
for(j=0; j<N; j++)
if(board[i ][j]!=0 && neighbours[i ][j]==0)
{
cnt = 0;
update(board, neighbours, M, N, i, j, board[i ][j], &cnt);
}
}
void print(int **board, const int M, const int N)
{
int i, j;
for(j=N-1; j>=0; j--)
{
for(i=0; i<M; i++)
printf("%d ", board[i ][j]);
printf( "\n" );
}
}
void read(int **board, int *pM, int *pN, int *pK)
{
int i, j;
scanf("%d%d%d", pM, pN, pK);
for(j=*pN-1; j>=0; j--)
for(i=0; i<*pM; i++)
scanf("%d", &board[i ][j]);
}
void clear(int **board, int **neighbours)
{
int i, j;
for(i=0; i<50; i++)
for(j=0; j<50; j++)
{
board[ i ][ j ] = 0;
neighbours[ i ][ j ] = 0;
}
}
int next(const int **neighbours, const int M, const int N, int *pk, int *pl)
{
int i, j;
int max;
max = neighbours[ 0 ][ 0 ];
*pk = 0; *pl = 0;
for(i=0; i<M; i++)
for(j=0; j<N; j++)
if(max < neighbours[i ][j])
{
max = neighbours[i ][j];
*pk = i;
*pl = j;
}
if(max <= 1)
return( 0 );
else
return( 1 );
}
void game(int **board, int **neighbours)
{
int k, l;
int M, N, K;
read(board, &M, &N, &K);
allocate(board, neighbours, M, N);
while(next(neighbours, M, N, &k, &l) != 0)
{
/*print(board, M, N);
printf( "\n" );
print(neighbours, M, N);
printf( "\n" );*/
printf("%d %d\n", k, l);
removeit(board, M, N, k, l, board[k][l]);
packit(board, M, N);
allocate(board, neighbours, M, N);
}
}
int main()
{
int i;
int **board;
int **neighbours;
board = (int**)malloc( 50*sizeof(int*) );
neighbours = (int**)malloc( 50*sizeof(int*) );
for(i=0; i<50; i++)
{
board[ i ] = malloc( 50*sizeof(int) );
neighbours[ i ] = malloc( 50*sizeof(int) );
}
clear(board, neighbours);
game(board, neighbours);
for(i=0; i<50; i++)
{
free( board[i ] );
free( neighbours[i ] );
}
free( board );
free( neighbours );
return( 0 );
}
Re: telerik contest
Поредните имитатори.
Явно и тези яко са закъсали откъм хора и се опитват да подмамят някой по-несветнат.
Абе тези измислени фирми на какво се крепят, че не фалират?
Абе не знам ами виж какъв цитат открих на сайта им :
"Сред клиентите на telerik са водещи световни компании като Microsoft, Intel, Dell, Hewlett-Packard, Fujitsu, Motorola, Sony Ericsson, Xerox, Philips, NASA, France Telecom, Reuters, NEC,Kodak, образователни организации и правителствени институции."
Те тва е българска софтуерна компания !
Явно и тези яко са закъсали откъм хора и се опитват да подмамят някой по-несветнат.
Абе тези измислени фирми на какво се крепят, че не фалират?
Абе не знам ами виж какъв цитат открих на сайта им :
"Сред клиентите на telerik са водещи световни компании като Microsoft, Intel, Dell, Hewlett-Packard, Fujitsu, Motorola, Sony Ericsson, Xerox, Philips, NASA, France Telecom, Reuters, NEC,Kodak, образователни организации и правителствени институции."
Те тва е българска софтуерна компания !