Algoritmo para The Marianbad Game

[player.nike]

Boas programadores tenho um problema para fazer um algoritmo dentro d 1 projecto keu tnho em mãos para criação d algoritmos d jogos tipo" jogo do galo","the game  marianbad" k é actualmente o trabalho k m está dar  problemas, etc...o k acontece é k tenho k fazer 1 algoritmo ( ñ refinado e refinado) para o tal jogo"the marianbad game", k , pa kem ñ conhece deixo aki o seu conteúdo e as suas regras...essencialmente o jogo è muito parecido com o jogo do galo e é disputado igualmente entre 2 jogadores k vão cortando "traços" por n linhas até se ficar com nenhuma linha...

Eu tenho o problema d ñ conseguir arrancar com os pr imeiros passos do algoritmo;ou seja, resumindo,ñ sei por onde começar!!

Agradecia k kem tivesse mais por  dentro d algoritmia m ajudasse na criação deste algoritmo..Em baixo segue em anexo a  especificaçaõ do jogo com as respectivas regras...

[Warrior]

As constraints são demasiado grandes para fazeres pesquisa completa?

[shumy]

não percebi nada do jogo.

[Warrior]

Dado um conjunto de fósforos, divididos em filas.

Por exemplo, 5 fósforos na primeira fila, 4 na segunda, 3 na terceira, etc.

Os jogadores jogam alternadamente. Na tua vez de jogar, podes queimar qualquer número de fósforos, desde que se encontrem todos na mesma fila.

Ganha aquele que obrigar o outro a queimar o último fósforo.

Julgo que, caso não seja possível usar complete search (um género de BFS?) a solução deve ser semelhante a esta apresentada nas olimpiadas internacionais de 2005, na polónia:

Rectangle game

Podes encontrar a sua solução neste livro PDF:

http://www.ioi2005.pl/downloads/ioi2005-tasks-and-solutions-a4.pdf

Página 31

Se tiveres com disponibilidade para ler.. Caso contrário, posso tentar explicar.

Passa por desenvolver uma matriz que te indica que combinações são ou não uma winning solution.

Depois de o fazeres, verifica se podes transformar o teu "tabuleiro" numa delas. Em caso afirmativo, uma solução encontrada.

Para processar a matriz, normalmente ela é desenvolvida com programação dinâmica. Encontras uma solução base, e crias novas soluções através dessa primeira.

Para este problema específico, não estou a ver como organizar sequer os dados na matriz, mas só para deixar "claro" que em princípio existe outra solução além de brute force..

[player.nike]

Obrigado Warrior esse jogo dessas Olímpiadas é praticamente o msm keste keu tenho em "mãos" e já da pra ter uma ideia d como arrancar o algoritmo... 😁  Só há uma ou outra diferença k é a regra d cada jogador apenas poder cortar "fósforos" na linhas horizontais e o desenho do jogo , já k funciona, como viste no enunciado, em função d entradas  e saídas, pode ter, por exemplo, 20 fósforos na 1ª linha, 30 na 2ª, 10 na 3ª e 5 na 4ª;ou seja, o número d linhas são ktas o utilizador kiser e o número de fósforos k compõem essas linhas também...

Já agr Warrior posso-t dizer k no meu jogo em kestão, e possívelmente nesse das olímpiadas k m envias-t tb, existem uma série d trukes para s ganhar...ou seja , existem algumas jogadas vitoriosas: por exemplo, s 1 jogador deixar o jogo numa situação em k s tenha em linhas diferentes 2+2 fósforos ganha sempre esse jogador k deixa essa situação para o adversário; outro truke é, sempre k 1 jogador deixar o jogo numa situação d 1+1+1 fósforos em linhas separadas ganha sempre...Ora, resumindo, posso-t dizer Warrior k o k ñ tou a conseguir fazer é por esses trukes em práticas no algoritmo;será k tens uma ideia?s ñ agradeço-t na mesma vou lêr com mais atenção o outro jogo k recomendas-t ou ver s posso fazer alguma analogia...Fika bem.

[Warrior]

Eu acho que podes fazer um algoritmo de pesquisa completa, só mesmo se as constraints forem demasiado grandes.

No enunciado diz claramente o que é considerada uma jogada vitoriosa (aquela cena do binário) tenta: remover, 1 da primeira fila, ve se é vitoriosa, 2 da primeira fila, ve se é vitoriosa, etc, fila a fila, fósforo a fósforo.

Isto dá algo O(n*k) sendo n o número de niveis e k o tamanho do maior nível.

[shumy]

rapidamente: O(n*k) --> O(n) tempo linear. Não se mete constantes.

[Warrior]

k não é considerado uma constante, pois é variável. (foi uma má escolha de letra)

Se tiveres uma matriz de m por n, o tempo que demoras a percorrer é O(n*m), não é só n.

Constantes predeterminadas, como 2, 5, ou 1000, são omitidas.

Apesar de em algumas situações seja útil a sua inclusão. Existem problemas em que as constantes não podem ser ignoradas. Se tiveres um vector de 1 000 000 de inteiros, e quiseres encontrar os dois maiores, existe uma grande diferença entre fazer tudo num único ciclo ou em dois. O(2n) é muito diferente de O(n).

São raras as excepções, mas existem.

[player.nike]

Obrigado Warrior pela resposta , mas a mim ñ m interessa o tempo que se leva a concluir a jogada, mas sim, tal como esta no enunciado do jogo,as jogadas vitoriosas que me permitam, ganhar o jogo -  Por Exemplo:

Input

3

8

5

10

Output:

2 3

0

Envio em anexo o esboço do algoritmo que estou a criar, dá para perceber melhor como funciona o jogo; se fosse possivel da-me a tua opinião pois estou empancado no Ponto 5 ( Definição Jogada Vencedora). Já agora,este algoritmo é para por em pratica em linguagem C.

P.S. O que é  (O) quando te referes á funçao O(n*m)

Muito Obrigado pela Ajuda

[Warrior]

O() refere-se à complexidade do algoritmo em termos de tempo. Estando tu na universidade esperei que fosse importante não só funcionar, como funcionar rapidamente.

Quanto ao número de jogadas vitoriosas possíveis, isso é exactamente o que o meu algoritmo calcula.

Quanto a como saber se é vencedora ou não, isso está explicado no enunciado.

Partindo de

lllll

llll

lll

ll

l

Removendo 2 da linha 3

lllll

llll

lxx

ll

l

Não é uma jogada ganhadora porque:

5 na linha 1 (5 = 101) 4 na linha 2 (4 = 100) 1 na linha 3 (1 = 1) 2 na linha 4 (2 = 10) 1 na linha 5 (1 = 1)

Somando tudo, 101+100+1+10+1=213 (soma os números binários usando o sistema decimal)

Podes concluir que remover dois fósforos da terceira linha não produz uma jogada vencedora, pois nem todos os algarismos do número 213 são pares.

UMA JOGADA É VENCEDORA SE NA SUA SOMA TODOS OS ALGARISMOS FOREM PARES.

O que eu sugeri, foi, remover 1 da primeira linha, testar. Remover dois da primeira linha, testar, etc. De modo a calcular todas as jogadas vitoriosas.

Um pormenor no enunciado:

Your task is to write a program that receives a set of lines with marks and that generates

all the possible winning moves that involve a minimum of marks crossed out.

The minimum. Ou seja, se existirem 2 soluções que envolvam remover 2 fósforos, e 1 que envolva remover 3, deves imprimir 2 e não 3.

Voltando à questão do tempo, podes remover este problema em O(n*k).

Um for de 1 a n, e dentro deste um de 1 a k, sendo n o número de linhas e sendo k o número de fósforos nessa posição do vector.

Removes para cada linha, os k fósforos.

Podes fazer várias optimizações no código, não sei se estás interessado nisso, mas por exemplo:

Não precisas de calcular permanentemente o binário de todas as linhas. Se na primeira linha tens 5 fósforos, não precisas de calcular 5 vezes o binário das linhas 2,3,4 e 5, pois mantém-se constante.  (grande incremento de velocidade à custa de um vector auxiliar)

Tendo como base aquela nuance do enunciado, se já encontraste uma solução com 2 fósforos, escusas de procurar soluções com 3. Etc..

Isto é o que eu faria, se tiver percebido bem o problema.

Um brute-force, testa todas as soluções possíveis.

Não te mostraste preocupado com o tempo que o programa demora a correr, de forma que esta solução deve ser suficiente.

Edit: li agora o teu algoritmo no word, um de nós não entendeu o problema. Não é suposto simulares um jogo, somente indicares, partindo do tabuleiro fornecido, quantas jogadas vitoriosas precisas.

[player.nike]

exactamente Warrior tens razão keu ñ tenha k simular 1 jogo ms o k akontece, e eu já deveria ter mencionado isso é k o tabuleiro pod ñ ter este desenho IIIII ,ms muitos outros tal como 3  que é o mesmo k 3 linhas com, respectivamente, 8 paus na 1ª linha, 10 na 2ª e 2 na 3ª IIIIIIII

              IIII                                              8                                                                                                                                              IIIIIIIIII

              III                                                10                                                                                                                                            II

              II                                                  2

              I

Kto ao meu algoritmo, eu sei k ainda tenho k retokar algumas coisa ms axas k no geral ñ ta bem?

[Warrior]

Não percebi o que queres dizer.

Se te estás a referir, por exemplo, ao segundo caso de teste (8, 5, 10), o processo é exactamente o mesmo.

IIIIIIII

IIIII

IIIIIIIIII

Podes sempre representar qualquer número de casos da forma que eu disse.

Eu tenho quase a certeza que percebi bem o enunciado. Pelo menos aquele que mostraste no primeiro post, em inglês. Se o teu objectivo não é aquele problema, mas uma variação, convém explicá-la.