ONI 2008 - Numeros fáceis de escrever

polska · July 20, 2012 at 02:31 PM

Boas pessoal, estive a resolver alguns exercícios das finais de 2006 a 2008 e deparei-me com este problema: http://www.dcc.fc.up.pt/oni/problemas/2008/final/probB.html

Eu pensei em algo como permutações, se nos dão o número de ordem e querem saber a que número fácil de escrever corresponde, pensei que a permutar estes mesmos números, teria uma solução que passava no tempo sem dificuldades.. Mas não sei se estou certo, e estou a ter dificuldades em perceber como fazer as permutações, alguma ajuda?

Warrior · July 20, 2012 at 04:34 PM

Não estou a perceber a tua ideia com as permutações, uma vez que a ordem dos algarismos é essencial para saber se ele é fácil de escrever ou não.

Por exemplo, 147 é fácil de escrever, mas 417 ou 714 não é.

Edited July 20, 2012 at 04:34 PM by Warrior

pikax · July 20, 2012 at 05:03 PM

eu acho que fica mais facil se pensares no problema como ele e' na realidade, tens o teclado do telemovel(e' uma matriz) basta somares/subtraires o i ou a , basta um ciclo ate' ao maior numero para ficares a saber de todos

Warrior · July 20, 2012 at 05:31 PM

Não consigo perceber o que é o I e o A.

Já agora, qual é o maior número?

polska · July 20, 2012 at 06:28 PM

Secalhar estou com a noção de permutação mal, tipo eu pensei em saber numeros fáceis através de outros já calculados..

Não consigo perceber o que é o I e o A.

Já agora, qual é o maior número?

não é 99?

Edited July 20, 2012 at 06:29 PM by polska

pikax · July 20, 2012 at 07:16 PM

Não consigo perceber o que é o I e o A.

e' o tamanho da matriz, I e o A sao as variaveis que uso quando faco 2 for's, fui pouco explicito desculpem 😄

EDIT: a matriz e' o teclado do telemovel

END EDIT;

não é 99?

Seguem-se exactamente C linhas, cada uma delas contendo um número de ordem N da sequência (1 ≤ N ≤ 150 000). Estes números podem vir por qualquer ordem.

Edited July 20, 2012 at 07:17 PM by pikax

polska · July 20, 2012 at 11:55 PM

e' o tamanho da matriz, I e o A sao as variaveis que uso quando faco 2 for's, fui pouco explicito desculpem 😄

EDIT: a matriz e' o teclado do telemovel

END EDIT;

Tens razão, eu estava apenas a pensar em numeros fáceis com até 2digitos, mas a mais... O que tu me dizes então é fazer um for que verifica se o número é fácil de escrever, até encontrar o máximo necessário.. certo?

Mas isto não é uma brute force?

pmg · July 21, 2012 at 09:25 AM

Mas isto não é uma brute force?

Olha bem para este input:

2
20000
18500

Repara que no calculo (brute-force) do primeiro valor, ja passaste pelo calculo do segundo valor.

Acho que isso (a "memoization") é o que o problema pretende testar. Nao vais calcular duas vezes se o numero 4111233 é facil de escrever...

Warrior · July 21, 2012 at 01:31 PM

Ainda assim isso não seria suficiente para resolver o problema para 100 pontos.

Se bem me lembro da solução, embora possa estar a confundir, este é um dos problemas mais difíceis das ONI.

Edited July 21, 2012 at 01:32 PM by Warrior

polska · July 21, 2012 at 02:37 PM

Olha bem para este input:
2
20000
18500
Repara que no calculo (brute-force) do primeiro valor, ja passaste pelo calculo do segundo valor.

Acho que isso (a "memoization") é o que o problema pretende testar. Nao vais calcular duas vezes se o numero 4111233 é facil de escrever...

Eu também reparei nisso, mas para isso resolver isso bastava fazer o sort dos numeros dados e parava de pesquisar no ultimo..

Ainda assim isso não seria suficiente para resolver o problema para 100 pontos.

Se bem me lembro da solução, embora possa estar a confundir, este é um dos problemas mais difíceis das ONI.

Pois, eu estava mesmo a tentar perceber a solução dos 100 pontos xb .

pmg · July 21, 2012 at 04:53 PM

Hmmm ... tou a ver a dificuldade :/

Deve ser preciso considerar os numeros como strings e fazer uma especie de grafo dinamico, que se vai construindo a medida das necessidades (uma versao reduzida talvez de para os 100 pontos)

Exemplo para dois digitos:

a seguir ao ...12 vem o ...14

a seguir ao ...14 vem o (MUDANCA DE DIGITO: talvez ...21)

Exemplo para tres digitos:

a seguir ao ...452 vem o ...454

a seguir ao ...454 vem o ...455

a seguir ao ...455 vem o ...456

a seguir ao ...456 vem o ...458

a seguir ao ...458 vem o ...474 (sem MUDANCA DE DIGITO)

a seguir ao ...474 vem o ...477

a seguir ao ...477 vem o ...478

a seguir ao ...478 vem o (MUDANCA DE DIGITO: talvez ...521)

mogers · July 21, 2012 at 05:15 PM

Ainda assim isso não seria suficiente para resolver o problema para 100 pontos.

Se bem me lembro da solução, embora possa estar a confundir, este é um dos problemas mais difíceis das ONI.

Não estás a confundir com o problema Em busca dos enunciados perdidos?

Não tenho a minha resolução deste problema aqui comigo, mas parece-me que é um simples problema de pesquisa. Repara que isto é quase como aqueles problemas com labirintos, onde só podes andar para a esquerda,direita, cima e baixo. Neste caso isso é feito na matriz do teclado.

Para lidar com o limite dos 150000 primeiros, ou usas uma priority_queue para processar os mais pequenos, ou primeiro fazes uma bfs até um número grande e verificas à mão qual é o 150000º.

hint: em vez de começares num único ponto da matriz, começas a pesquisa nos digitos 1..9 e em cada passo avanças para os seus vizinhos no grafo.

HappyHippyHippo · July 21, 2012 at 05:26 PM

bem achei o problema engraçado e fiz isso assim dos pés para as mãos ... fiz poucos testes mas deram correcto

de notar que a maior parte do código é a implementação de uma queue num array circular de redimensionamento dinâmico

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Queue
{
   int * list;
   int size;
   int count;
   int start;
   int end;
} Queue;

int queueInit(Queue * queue)
{
   if (queue == NULL)
       return -1;

   if ((queue->list = calloc(sizeof(int), 32)) == NULL)
       return -2;

   queue->size = 32;
   queue->count = 0;
   queue->start = 0;
   queue->end = 0;

   return 0;
}

int queueUninit(Queue * queue)
{
   free(queue->list);
   return 0;
}

int queueResize(Queue * queue)
{
   int * aux = NULL;
   int size = 0;

   if (queue == NULL)
       return -1;

   if ((aux = calloc(sizeof(int), queue->size * 2)) == NULL)
       return -2;

   if (queue->count > 0)
   {
       if (queue->start < queue->end)
       {
           size = queue->end - queue->start;
           memcpy(aux, &queue->list[queue->start], size * sizeof(int));
       }
       else
       {
           size = queue->size - queue->start;
           memcpy(aux, &queue->list[queue->start], size * sizeof(int));

           if ((size = queue->end) != 0)
           {
               size = queue->end;
               memcpy(&(aux[queue->size - queue->start]), &queue->list[0], queue->end * sizeof(int));
           }
       }
   }

   free(queue->list);
   queue->list = aux;
   queue->size *= 2;
   queue->start = 0;
   queue->end = queue->count;

   return 0;
}

int queueEnqueue(Queue * queue, int value)
{
   int result = 0;

   if (queue == NULL)
       return -1;

   if (queue->count == queue->size)
   {
       if ((result = queueResize(queue)) != 0)
           return result;
   }

   queue->list[queue->end] = value;
   queue->count++;

   queue->end++;
   if (queue->end == queue->size)
       queue->end = 0;

   return 0;
}

int queueDequeue(Queue * queue, int * value)
{
   if (queue == NULL || value == NULL)
       return -1;

   if (queue->count == 0)
       return -2;

   *value = queue->list[queue->start];
   queue->count--;

   queue->start++;
   if (queue->start == queue->size)
       queue->start = 0;

   return 0;
}

int main()
{
   Queue bfs, targets;
   int target = 0, check = 0, order = 1;

   queueInit(&bfs);
   queueInit(&targets);

   // esta entrada deverá ser ordenada
   queueEnqueue(&targets, 14);
   queueEnqueue(&targets, 20);
   queueEnqueue(&targets, 24);

   queueEnqueue(&bfs, 1);
   queueEnqueue(&bfs, 2);
   queueEnqueue(&bfs, 3);
   queueEnqueue(&bfs, 4);
   queueEnqueue(&bfs, 5);
   queueEnqueue(&bfs, 6);
   queueEnqueue(&bfs, 7);
   queueEnqueue(&bfs, 8);
   queueEnqueue(&bfs, 9);

   while (targets.count != 0)
   {
       queueDequeue(&targets, &target);

       if (target == 0)
           printf("%d: %d\n", target, 0);
       else
       {
           do
           {
               order++;
               queueDequeue(&bfs, &check);

               switch (check % 10)
               {
                   case 0:
                       queueEnqueue(&bfs, (check*10)+0);
                       queueEnqueue(&bfs, (check*10)+8);
                       break;
                   case 1:
                       queueEnqueue(&bfs, (check*10)+1);
                       queueEnqueue(&bfs, (check*10)+2);
                       queueEnqueue(&bfs, (check*10)+4);
                       break;
                   case 2:
                       queueEnqueue(&bfs, (check*10)+1);
                       queueEnqueue(&bfs, (check*10)+2);
                       queueEnqueue(&bfs, (check*10)+3);
                       queueEnqueue(&bfs, (check*10)+5);
                       break;
                   case 3:
                       queueEnqueue(&bfs, (check*10)+2);
                       queueEnqueue(&bfs, (check*10)+3);
                       queueEnqueue(&bfs, (check*10)+6);
                       break;
                   case 4:
                       queueEnqueue(&bfs, (check*10)+1);
                       queueEnqueue(&bfs, (check*10)+4);
                       queueEnqueue(&bfs, (check*10)+5);
                       queueEnqueue(&bfs, (check*10)+7);
                       break;
                   case 5:
                       queueEnqueue(&bfs, (check*10)+2);
                       queueEnqueue(&bfs, (check*10)+4);
                       queueEnqueue(&bfs, (check*10)+5);
                       queueEnqueue(&bfs, (check*10)+6);
                       queueEnqueue(&bfs, (check*10)+8);
                       break;
                   case 6:
                       queueEnqueue(&bfs, (check*10)+3);
                       queueEnqueue(&bfs, (check*10)+5);
                       queueEnqueue(&bfs, (check*10)+6);
                       queueEnqueue(&bfs, (check*10)+9);
                       break;
                   case 7:
                       queueEnqueue(&bfs, (check*10)+4);
                       queueEnqueue(&bfs, (check*10)+7);
                       queueEnqueue(&bfs, (check*10)+8);
                       break;
                   case 8:
                       queueEnqueue(&bfs, (check*10)+0);
                       queueEnqueue(&bfs, (check*10)+5);
                       queueEnqueue(&bfs, (check*10)+7);
                       queueEnqueue(&bfs, (check*10)+8);
                       queueEnqueue(&bfs, (check*10)+9);
                       break;
                   case 9:
                       queueEnqueue(&bfs, (check*10)+6);
                       queueEnqueue(&bfs, (check*10)+8);
                       queueEnqueue(&bfs, (check*10)+9);
                       break;
               }
           } while (target != order);

           printf("%d: %d\n", target, check);
       }
   }

   queueUninit(&targets);
   queueUninit(&bfs);
   return 0;
}

PS :

o resultado que me dá ao numero de ordem 150000 é o 121458877

e a bfs aumentou até ter 524288 de espaços disponíveis

PS :- pequenos erros corrigidos

pmg · July 21, 2012 at 07:08 PM

o resultado que me dá ao numero de ordem 150000 é o 121458877

A mim da-me (sem passar no tempo da oni): 98788523

O resultado que me da ao numero de ordem #97 é o 521: a ti da-te o 532 (que nao é um resultado valido!)

Edited July 21, 2012 at 07:09 PM by pmg

HappyHippyHippo · July 21, 2012 at 07:10 PM

A mim da-me (sem passar no tempo da oni): 98788523

não faço ideia ... como disse só fiz uns pequenos testes e não estou para calcular à mão os resultados elevados como esses

no que toca a tempos, como nunca entrei sequer no site da ONI sem faço ideia como posso testar 😄

O resultado que me da ao numero de ordem #97 é o 521: a ti da-te o 532 (que nao é um resultado valido!)

já vi onde está o bug:

                   case 5:
                       queueEnqueue(&bfs, (check*10)+3); // <--------- deveria ser 2, foi dos meus dedos gordos 
                       queueEnqueue(&bfs, (check*10)+4);
                       queueEnqueue(&bfs, (check*10)+5);
                       queueEnqueue(&bfs, (check*10)+6);
                       queueEnqueue(&bfs, (check*10)+8);

Edited July 21, 2012 at 07:12 PM by HappyHippyHippo

polska · July 21, 2012 at 07:11 PM

Hmmm ... tou a ver a dificuldade :/

Deve ser preciso considerar os numeros como strings e fazer uma especie de grafo dinamico, que se vai construindo a medida das necessidades (uma versao reduzida talvez de para os 100 pontos)

Exemplo para dois digitos:

a seguir ao ...12 vem o ...14

a seguir ao ...14 vem o (MUDANCA DE DIGITO: talvez ...21)

Exemplo para tres digitos:

a seguir ao ...452 vem o ...454

a seguir ao ...454 vem o ...455

a seguir ao ...455 vem o ...456

a seguir ao ...456 vem o ...458

a seguir ao ...458 vem o ...474 (sem MUDANCA DE DIGITO)

a seguir ao ...474 vem o ...477

a seguir ao ...477 vem o ...478

a seguir ao ...478 vem o (MUDANCA DE DIGITO: talvez ...521)

Não estás a confundir com o problema Em busca dos enunciados perdidos?

Não tenho a minha resolução deste problema aqui comigo, mas parece-me que é um simples problema de pesquisa. Repara que isto é quase como aqueles problemas com labirintos, onde só podes andar para a esquerda,direita, cima e baixo. Neste caso isso é feito na matriz do teclado.

Para lidar com o limite dos 150000 primeiros, ou usas uma priority_queue para processar os mais pequenos, ou primeiro fazes uma bfs até um número grande e verificas à mão qual é o 150000º.

hint: em vez de começares num único ponto da matriz, começas a pesquisa nos digitos 1..9 e em cada passo avanças para os seus vizinhos no grafo.

O que eu pensei neste problema, foi ter então a matriz com os numeros e tinha uma função que gerava todos os números até ao máximo numero de ordem dado no input, por exemplo 30, gerava então os 30 primeiros números fáceis, mas o problema é que ou tinha de lidar com strings ou vectores, porque quando chego a números com 2 ou mais digitos tenho que os juntar...

Eu vou tentar implementar uma solução com as vossas dicas, e vou tentar a minha tambem..

bem achei o problema engraçado e fiz isso assim dos pés para as mãos ... fiz poucos testes mas deram correcto

de notar que a maior parte do código é a implementação de uma 8i]queue[/i] num array circular de redimensionamento dinâmico

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Queue
{
int * list;
int size;
int count;
int start;
int end;
} Queue;

int queueInit(Queue * queue)
{
if (queue == NULL)
	return -1;

if ((queue->list = calloc(sizeof(int), 32)) == NULL)
	return -2;

queue->size = 32;
queue->count = 0;
queue->start = 0;
queue->end = 0;

return 0;
}

int queueUninit(Queue * queue)
{
free(queue->list);
return 0;
}

int queueResize(Queue * queue)
{
int * aux = NULL;
int size = 0;

if (queue == NULL)
	return -1;

if ((aux = calloc(sizeof(int), queue->size * 2)) == NULL)
	return -2;

if (queue->count > 0)
{
	if (queue->start < queue->end)
	{
		size = queue->end - queue->start;
		memcpy(aux, &queue->list[queue->start], size * sizeof(int));
	}
	else
	{
		size = queue->size - queue->start;
		memcpy(aux, &queue->list[queue->start], size * sizeof(int));

		if ((size = queue->end) != 0)
		{
			size = queue->end;
			memcpy(&(aux[queue->size - queue->start]), &queue->list[0], queue->end * sizeof(int));
		}
	}
}

free(queue->list);
queue->list = aux;
queue->size *= 2;
queue->start = 0;
queue->end = queue->count;

return 0;
}

int queueEnqueue(Queue * queue, int value)
{
int result = 0;

if (queue == NULL)
	return -1;

if (queue->count == queue->size)
{
	if ((result = queueResize(queue)) != 0)
		return result;
}

queue->list[queue->end] = value;
queue->count++;

queue->end++;
if (queue->end == queue->size)
	queue->end = 0;

return 0;
}

int queueDequeue(Queue * queue, int * value)
{
if (queue == NULL || value == NULL)
	return -1;

if (queue->count == 0)
	return -2;

*value = queue->list[queue->start];
queue->count--;

queue->start++;
if (queue->start == queue->size)
	queue->start = 0;

return 0;
}

int main()
{
Queue bfs, targets;
int target = 0, check = 0, order = 1;

queueInit(&bfs);
queueInit(&targets);

// esta entrada deverá ser ordenada
queueEnqueue(&targets, 14);
queueEnqueue(&targets, 20);
queueEnqueue(&targets, 24);

queueEnqueue(&bfs, 1);
queueEnqueue(&bfs, 2);
queueEnqueue(&bfs, 3);
queueEnqueue(&bfs, 4);
queueEnqueue(&bfs, 5);
queueEnqueue(&bfs, 6);
queueEnqueue(&bfs, 7);
queueEnqueue(&bfs, 8);
queueEnqueue(&bfs, 9);

while (targets.count != 0)
{
	queueDequeue(&targets, &target);

	if (target == 0)
		printf("%d: %d\n", target, 0);
	else
	{
		do
		{
			order++;
			queueDequeue(&bfs, &check);

			switch (check % 10)
			{
				case 0:
					queueEnqueue(&bfs, (check*10)+9);
					break;
				case 1:
					queueEnqueue(&bfs, (check*10)+1);
					queueEnqueue(&bfs, (check*10)+2);
					queueEnqueue(&bfs, (check*10)+4);
					break;
				case 2:
					queueEnqueue(&bfs, (check*10)+1);
					queueEnqueue(&bfs, (check*10)+2);
					queueEnqueue(&bfs, (check*10)+3);
					queueEnqueue(&bfs, (check*10)+5);
					break;
				case 3:
					queueEnqueue(&bfs, (check*10)+2);
					queueEnqueue(&bfs, (check*10)+3);
					queueEnqueue(&bfs, (check*10)+6);
					break;
				case 4:
					queueEnqueue(&bfs, (check*10)+1);
					queueEnqueue(&bfs, (check*10)+4);
					queueEnqueue(&bfs, (check*10)+5);
					queueEnqueue(&bfs, (check*10)+7);
					break;
				case 5:
					queueEnqueue(&bfs, (check*10)+3);
					queueEnqueue(&bfs, (check*10)+4);
					queueEnqueue(&bfs, (check*10)+5);
					queueEnqueue(&bfs, (check*10)+6);
					queueEnqueue(&bfs, (check*10)+8);
					break;
				case 6:
					queueEnqueue(&bfs, (check*10)+3);
					queueEnqueue(&bfs, (check*10)+5);
					queueEnqueue(&bfs, (check*10)+6);
					queueEnqueue(&bfs, (check*10)+9);
					break;
				case 7:
					queueEnqueue(&bfs, (check*10)+4);
					queueEnqueue(&bfs, (check*10)+7);
					queueEnqueue(&bfs, (check*10)+8);
					break;
				case 8:
					queueEnqueue(&bfs, (check*10)+0);
					queueEnqueue(&bfs, (check*10)+5);
					queueEnqueue(&bfs, (check*10)+7);
					queueEnqueue(&bfs, (check*10)+8);
					queueEnqueue(&bfs, (check*10)+9);
					break;
				case 9:
					queueEnqueue(&bfs, (check*10)+6);
					queueEnqueue(&bfs, (check*10)+8);
					queueEnqueue(&bfs, (check*10)+9);
					break;
			}
		} while (target != order);

		printf("%d: %d\n", target, check);
	}
}

queueUninit(&targets);
queueUninit(&bfs);
return 0;
}

PS :

o resultado que me dá ao numero de ordem 150000 é o 121458877

e a bfs aumentou até ter 524288 de espaços disponíveis

Happy quando tentei compilar o teu programa, para seguir passo a passo, deu-me este erro :s :

error C2440: '=' : cannot convert from 'void *' to 'int *' , nesta linha :

if ((aux = calloc(sizeof(int), queue->size * 2)) == NULL)

HappyHippyHippo · July 21, 2012 at 07:20 PM

Happy quando tentei compilar o teu programa, para seguir passo a passo, deu-me este erro :s :

error C2440: '=' : cannot convert from 'void *' to 'int *' , nesta linha :

if ((aux = calloc(sizeof(int), queue->size * 2)) == NULL)

faz cast ... deves ter prai uma flag no compilador que restringe este tipo de atribuições

pmg · July 21, 2012 at 07:24 PM

error C2440: '=' : cannot convert from 'void *' to 'int *' , nesta linha :

O teu compilador nao esta configurado para C: estas a compilar com um compilador de C++.

Em C, o tipo void* e compativel com ponteiro para qualquer tipo de objecto.

já vi onde está o bug:

Outro bug (depois da correccao anterior): o numero de ordem 146 devia ser 800, a ti da 809 (que nao e valido!)

Edited July 21, 2012 at 07:23 PM by pmg

HappyHippyHippo · July 21, 2012 at 07:29 PM

Outro bug (depois da correccao anterior): o numero de ordem 146 devia ser 800, a ti da 809 (que nao e valido!)

epa ... então não é que me esqueci do 0->0 ??? só tenho 0->9 !!!!!

brigada

ps : já agora não é 0->9 .. é 0->8

A mim da-me (sem passar no tempo da oni): 98788523

já tenho o mesmo resultado

Edited July 21, 2012 at 07:33 PM by HappyHippyHippo

mogers · July 21, 2012 at 07:37 PM

não faço ideia ... como disse só fiz uns pequenos testes e não estou para calcular à mão os resultados elevados como esses

no que toca a tempos, como nunca entrei sequer no site da ONI sem faço ideia como posso testar 😄

Os problemas das ONI costumam ter um limite de tempo de 1 segundo por caso de teste.

Eu prefiro usar algo como

int adj[][6] = { {0,8} , {1,2,4} , {1,2,3,5} , {2,3,6} , {1,4,5,7} , { 2,4,5,6,8} , {3,5,6,9}, {4,7,8}, {0,5,7,8,9}, {6,8,9} };
int nadj[] = { 2 , 3 , 4, 3 , 4, 5 , 4 , 3, 5, 3 };

// ...
queue<int> q;
for (i = 1 ; i < 10 ; i++)
q.push(i);
// ...
 cur = q.front();
 q.pop();
 lastD = cur % 10;
 for (i = 0 ; i < nadj[lastD] ; i++)
	  q.push( cur * 10 + adj[lastD][i] );

Edited July 21, 2012 at 07:53 PM by mogers

Sign In

ONI 2008 - Numeros fáceis de escrever

Recommended Posts

polska

Warrior

pikax

Warrior

polska

pikax

polska

pmg

Warrior

polska

pmg

mogers

HappyHippyHippo

pmg

HappyHippyHippo

polska

HappyHippyHippo

pmg

HappyHippyHippo

mogers

Create an account or sign in to comment

Create an account

Sign in

Home

Activity

Revista PROGRAMAR

Important Information