• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

magician

[4] Concatenar Números - Nível médio-alto

12 mensagens neste tópico

Título:

Concatenar Números

Objectivo:

Num concurso de programação recente, apareceu o seguinte problema:

Dado um número inteiro positivo N, concatenar esse número com ele próprio uma ou mais vezes de modo que o número resultante seja divisivel por um número k. Nota: Ver todos os exemplos!

Explicação de Input:

Dois números N ( 1 <= N <= 1.000.000.000 ) e k ( 1 <= k <= 100.000 )

Explicação de Output:

A solução deve ser o número mínimo de cópias do número usadas ou -1 caso seja impossível. Isto é, se N = 123, o número 123 possui uma cópia de N, 123123 -> 2 cópias, 123123123 -> 3 cópias, etc"

Exemplos de input/output:

Input: 2 9

Output: 9

Explicação:  o resto da divisão de 222.222.222 por 9 é 0.

Processo :

N = 2 e k = 9

1 ) 2 não é divisivel por 9

2 ) 22 não é divisivel por 9

3 ) 222 não é divisivel por 9

4 ) 2222 não é divisivel por 9

5 ) 22222 não é divisivel por 9

6 ) 222222 não é divisivel por 9

7 ) 2222222 não é divisivel por 9

8 ) 22222222 não é divisivel por 9

9 ) 222222222 é divisivel por 9 !

Input: 121  11

Output: 1

Explicação:  121 é divisivel por 11.

Input: 1 2

Output: -1

Explicação:  Não conseguimos formar um número par só com 1's.

Input:  35 98765

Output: 9876

Nota:  O número resultante tem 9876 * 2 digitos.

Input:  1000000000 3

Output: 3

Explicação:  100000000010000000001000000000 é divisivel por 3.

Material de apoio:

Não aplicável.

Restrições:

Para que o tempo de execução seja aceitável e o gasto de memória também, não usar o método trivial de concatenar realmente o numero original repetidas vezes, seja numa string seja usando BigNumbers.

Há soluções que não necessitam disso.

Este problema pode ser resolvido em qualquer linguagem sem problemas!


Desafio Proposto por : mogers


Discussão do problema em:

http://www.portugal-a-programar.pt/index.php?showtopic=16602

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Dim k = InputBox("Insira numero a dividir")
        Dim i = InputBox("Insira primeiro numero que vai ser Concatenado")
        Dim div = i
        Dim num_conctenacoes = 0
        Try
            While (div Mod k <> 0)
                ListBox1.Items.Add(div)
                ListBox2.Items.Add(div Mod k)
                div = div & i
                num_conctenacoes = num_conctenacoes + 1
            End While
            ListBox1.Items.Add(div)
            ListBox2.Items.Add(div Mod k)
            MsgBox(num_conctenacoes)
        Catch ex As Exception
            MsgBox(ex.Message)
        End Try

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem, fica aqui então..

PYTHON - SOLUÇÃO ERRADA

num, div = (raw_input('Digite o numero seguido do divisor (ex. 2, 9): ').replace(' ', '').split(','))
num, div = int(num), int(div)

if num == 1 and div != 1:
    print "Impossivel formar numeros pares so com 1s.."
else:
    length = len(str(num))
    x = 1
    ori = num

    while num%div != 0: 
        num_ = num*(10**length)
        num = ori + num_
        x += 1

    print "O numero",num,"e divisivel por",ori,"ao fim de",x,"concatencacoes"

EDIT: Só para alterar e introduzir o caso de N=1 e K = 1

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

SOLUÇÃO INVÁLIDA (TRIVIAL)

<?php
$num = 2;
$divisor = 9;

if($num == 1) echo "Impossivel formar numeros pares so com 1s..";
else

$numm = $num;
while($num%$divisor != 0) {
	$num = $num . $numm;
}

echo $num . " é divisivel por " . $divisor;
?>

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não mudem os algoritmos apresentados de linguagem para linguagem. Estas soluções não funcionam.

edit: não funcionam para todos os casos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Solução em Python (eu sei que há algo mais eficiente...)

SOLUÇÃO INVÁLIDA (TRIVIAL)

N, k = open("input", "r").read().split()

i = 1
step = 10**len(N)
N = int(N)
tmp = N
k = int(k)

out = ''

if k % 2 == 0:
if N % 2 != 0:
	out = "-1" # com um numero par so' conseguimos formar pares

if out != "": print out
else:
try:
	while tmp % k:
		i += 1
		tmp = tmp*step+N
	print i
except:
	print "-1" #failure, o tmp ficou muito grande. else, no idea.

Podem dar mais exemplos de input e output?

Vejam se estes estão correcto:

35 987655

-> 24219

36 987

-> 69

35 982

-> -1

35 983

-> 491

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É apenas uma função. Ainda não está a ler os dados do input.

f :: Integer -> Integer -> Integer
f x y | (snd.properFraction.(logBase$2)$fromIntegral$y)==0 = if mod x y==0 then 1 else -1
      | (snd.properFraction.(logBase$5)$fromIntegral$y)==0 = if mod x y==0 then 1 else -1
      | mod x 2/=0 && mod y 2==0 = -1
      | mod x 5/=0 && mod y 5==0 = -1
      | otherwise = faux 1 (toInteger.length.show$x) x x y

faux :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer
faux ac size n x y = if mod n y==0
                       then ac
                       else faux (ac+1) size (mod (n*10^size+x) y) x y

NOTA: Esta versão falha em alguns dos casos em que devia dar -1.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nova versão (já lê o input mas tem que ser um por linha):

main :: IO Int
main = getLine >>= aux >>= print.f >> return 0
  where aux l = return (read(words l!!0)::Integer,read(words l!!1)::Integer)

f :: (Integer,Integer) -> Integer
f (x, y) = let f2 = fac2 y
               f5 = fac5 y
               s  = toInteger.length.show$x
           in if not (f2==0 || mod x (2^f2)==0)
                then -1
                else if not (f5==0 || mod x (5^f5)==0)
                       then -1
                       else faux 1 s x x y
        
faux :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer
faux ac size n x y = if mod n y==0
                       then ac
                       else faux (ac+1) size (mod (n*10^size+x) y) x y

fac2::Integer -> Integer
fac2 x | mod x 2==0 = 1 + fac2 (div x 2)
       | otherwise = 0

fac5::Integer -> Integer
fac5 x | mod x 5==0 = 1 + fac5 (div x 5)
       | otherwise = 0

EDIT: alterei a função main de modo a que leia dois inteiros na mesma linha.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

#include <iostream>

using namespace std;

typedef long long i64;

i64 power(i64 a, i64 b) {
i64 p=a;
for (--b; b>0; p*=a, --b);
return p;
}

i64 len(i64 x) {
i64 a=0;
for (; x>0; x/=10, ++a);
return a;
}

i64 concatena(i64 x, i64 y) {
i64 n=x, p=power(10, len(x));
for (i64 i=1; i<=y; ++i, n=(n*p+x))
	if ((n%=y) == 0) return i;

return -1;
}

int main() {
i64 x, y;
cout << "Introduza os dados: ";
cin >> x >> y;

cout << concatena(x, y);

return 0;
}

Baseado no código Haskell do Rui Carlos

EDIT: tinha um bug que fazia com que números muito grandes não funcionassem (ex.: 1000000000 3) porque não estava a fazer o módulo do 1º número.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Aqui vai a minha solução em Java! Baseei me nas formulas do Warrior! Nunca chegaria a solução sem elas lool Acho que funciona para todos os casos...

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int tamanho = Integer.toString(n).length();
        int i = 1;
        int aux = n % k;
        int anterior = 0;

         if(k % 2 == 0 && n % 2 != 0)
            i = -1;

        if(k % 5 == 0 && n % 5 != 0)
            i = -1;

        while( aux != 0 && i > 0){  
            i++;
            anterior = aux;
            aux = (int) ((((anterior * (Math.pow(10.0, tamanho * 1.0) % k)) % k) + (n % k)) % k) ;
            if ( aux == anterior || i > k)
                i = -1;
        }
        System.out.print(i);
    }

}

Acho que agora esta mesmo resolvido, graças a explicação de Rui Carlos e  mogers :P


EDIT (TheDark): Não se esqueçam do [code=linguagem]

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Por curiosidade, deixo aqui a minha solução no concurso e uma um pouco melhor a seguir.

#include <iostream>
#include <set>
using namespace std;

int getSmallest(int n, int k) {
set<long long> s;	// conjunto com os restos ja calculados
int r = 1;

long long y = 1;
while (y<=n) y*=10;	// calcular a pontencia de 10 necessaria
long long a = n % k ;

while (1)
{
	if (a == 0 )  break;
	r++;
	if (s.find(a) != s.end())  return -1; // este resto ja foi calculado anteriormente
	s.insert(a);
	a = (a*y)+n;
	a %= k;
}
return r;
}
int main()
{
int N , K;
while (cin >> N >> K) {
	cout << getSmallest(N,K) << endl;	
}
return 0;
}

Uma solução um pouco melhor...

#include <iostream>
#include <cstring>
using namespace std;

char restos[100002];

int getSmallest(int n, int k) {	
memset( restos , 0 , sizeof(restos) );
long long y = 1 , a = n % k;
while (y<=n) 
	y*=10;		// calcular a pontencia de 10 necessaria
int resp;
for ( resp = 1 ; resp <= k ; resp++ ) {
	if ( a == 0 )		return resp;
	if ( restos[a] )  	return -1;
	restos[a] = 1;
	a = ( (a*y)+n ) % k;
}
return -1;
}

int main()
{
int N , K;
while (cin >> N >> K) {		
	cout << getSmallest(N,K) << endl;
}
return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

E aqui vai a minha solução em perl  :) , os dados podem ser passados por parametro

Pelo que testei funciona.

Aparentemente, a distribuição do perl mais popular no windows é o activeperl. Ora essa implementação vem com um bug que impede passar valores por parametro. Os utilizadores do actve perl vão ter que definir os dados manualmente no codigo.

Utilizadores de linux podem chamar o progrma assim: perl script.pl concatenando divisor

substituindo obviamente pelos valores adequados

use POSIX ceil;

sub log10 {
        my $n = shift;
        return log($n)/log(10);
    }
$c	= $ARGV[0];
$d 	= $ARGV[1];

#inserir os numeros manualmente aqui caso necessario
#$c = 200;
#$d = 15;

$factor = 10**(&ceil(&log10($c)));

$rest 	= $c % $d;
$rest_p = $rest;

my %rests;
$i = 1;
$success = 1;
until($rest==0){
$rest_p = ($rest_p * $factor) % $d;
$rest 	= ($rest_p + $rest) % $d;

if ($rests{$rest} == 1){
	$success = 0;
	last;		
}	
$rests{$rest} = 1;
$i++;
}


if ($success == 0){
print "Problema sem solcucao, impossivel encontrar um numero divisivel por $d concatenando $c \n";
}
else{
for (my $j = 0; $j < $i; $j++) {
	print $c;
}
print " e divisivel por $d \n";
}

Aqui vão uns exemplos do output:

p@p-laptop:~/Desktop$ perl concat2.pl 200 15

200200200 e divisivel por 15

p@p-laptop:~/Desktop$ perl concat2.pl 22 9

222222222222222222 e divisivel por 9

p@p-laptop:~/Desktop$ perl concat2.pl 11 9

111111111111111111 e divisivel por 9

p@p-laptop:~/Desktop$ perl concat2.pl 11 8

Problema sem solcucao, impossivel encontrar um numero divisivel por 8 concatenando 11

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora