Candy I e CandyIII

Neste post, analisaremos dois problemas do SPOJ:
http://www.spoj.pl/problems/CANDY/
http://www.spoj.pl/problems/CANDY3/

Problema CANDY I

O problema consiste em descobrir o menor número de movimentos necessários para que cada pacote de doces fique com a mesma quantidade de doces. Se a tarefa não for possível, imprima -1.

Observe que a tarefa só é possível se a soma da quantidade de doces de todos os pacotes for divisível pela quantidade de pacotes. 

Para descobrir a menor números de movimentos necessários, basta soma as diferenças entre o número de doces de cada pacote menos a média de números de doces por pacote para os  pacotes com números de doces superior a média. (Difícil né?)

Pseudocódigo
Entrada n o número de pacotes
        vetor p[i] representando número de balas do pacote 1<=i<=n.

soma = 0
Para i = 1 até n faça
   soma += p[i]

Se soma%n==0:
   media = soma/n
   cont = 0
   Para i=1 até n faça
        se p[i] > media
           cont += p[i] - media

Problema CANDYIII

O problema CANDY III é bastante parecido com CANDYI. A tarefa consiste apenas em descobrir se é possível dividir o total de doces de maneira que todas as crianças recebam a mesma quantidade de doces.

Observe que em um problema com restrições razoáveis bastaria somar a quantidade de doces de todas as crianças e testar se o valor encontrado é divisível pela quantidade de criança. Particularmente, este problema não tem nenhuma restrição com relação a quantidade de doces de cada criança e nem em relação a quantidade de crianças.

Para resolver este problema, consideramos que a quantidade de doces de cada criança seria do tipo long long int. Considerando este fato, não temos a garantia que o somatório da quantidade de doces também cabe em long long int. Então, utilizaremos o seguinte resultado de aritmética modular:

(a+b)%n = (a%n + b%n)%n

Observe que este resultado pode ser utilizado para calcular somas difíceis rapidamente.
Por exemplo,
(12124214214214+214214521421412412+42124214215215214+12421412421421)%10
(12124214214214%10+214214521421412412%10+42124214215215214%10+
12421412421421%10)%10
(4+2+4+1)%10
11%10
1

Aritmética do relógio

Você sabia que é possível desenvolver uma aritmética observando um relógio de parede. Essa aritmética é chamada de aritmética modular. A aritmética modular é utilizada em teoria dos números, teoria dos grupos, álgebra abstrata, criptografia, ciência da computação, música etc. 

Primeiro, vamos observar um relógio com o ponteiro das horas sobre o número 12.

Qual é a posição do ponteiro depois de 3 horas? Na aritmética usual, faríamos 12 + 3 = 15. Observe que depois do número 12, os números acabam e começam novamente no 1. Na aritmética do relógio é diferente, 12 + 3 = 3.

Imagine o ponteiro sobre o número 12 novamente, qual é a posição do ponteiro depois de 15 horas? Na aritmética usual, faríamos 12 + 15 = 27.  Na aritmética do relógio, 12 + 15 = 3 horas. Observe que o relógio dá uma volta completa e para sobre o número 3.

Imagine o ponteiro sobre o número 12 novamente, qual é a posição do ponteiro se voltarmos 9 horas? Observe que novamente, o ponteiro terminará sobre o número 3.

Observando a aritmética do relógio, o número 3 é equivalente ao número 15 . O conjunto de todos os números equivalentes ao número 3 é:

|3| = { 3 + 12k : k Z} = {...,-21,-9,3,15,27,...} (1)

Observe que esse conjunto é formado pelos números com o mesmo resto na divisão por 12. O conjunto descrito em (1) é o conjunto solução da seguinte equação modular:

x = 3 (mod 12) ou x mod 12 = 3

Seja a e b dois números inteiros, então a = b (mod 12) se somente se a-b é múltiplo de 12.

Aritmética modular

Essa aritmética continua valendo para um relógio com n horas com as seguintes propriedades:

1. (a+b) mod n = (a mod n + b mod n) mod n

2. (a-b) mod n = (a mod n - b mod n) mod n

3. (a*b) mod n = (a mod n * b mod n) mod n

4. (a/b) mod n = (a mod n * b^-1 mod n) mod n

Aplicações

Divisibilidade

A sua tarefa é, dado um número positivo N com 1000 dígitos, determinar se ele é um múltiplo de onze.

http://br.spoj.pl/problems/ONZE/

#include <stdio.h>
#include <string.h>
int main(){
    char n[1001];
    int d;
    while(1){
    scanf("%s",n);    
    if(strcmp(n,"0")==0) break;
    //Algoritmo da divisao
    d = 0;
    for(int i=0;n[i]!='\0';i++){        
        d = d*10 + n[i]-'0';
        d = d %11;
    }
    if(d==0)
      printf("%s is a multiple of 11.\n",n);
    else
        printf("%s is not a multiple of 11.\n",n);
    }
    return 0;
} 

Critografia RSA

Passo 1: Escolha dois números primos grande p e q.

Passo 2:Calcule n = p*q 

Passo 3: Calcule = (p-1)(q-1) 

Passo 4: Publique a chave pública (e,n)

Passo 5: Guarde a chave privada (d,n)

Passo 6: Cifrar mensagem(a)

   C(a) = ae  mod n

Passo 7: Decifrar mensagem(m)

  D(a) = ad mod n

     

    Observe que tanto a operação de cifragem como a operação de

    decifragem utiliza a potenciação modular.

     Algoritmo 1 an mod m

int exp1(int a, int n , int m){

  int i,res;

  res = 1;

  for(i=1;i<=n;i++)

  res = res*a;

  return res%m;

} 

Desvantagens: facilidade na ocorrência do overflow. Podemos reduzir evitar a
ocorrência do overflow utilizando a propriedades da aritmética modular.

Algoritmo 2: an mod m

int exp2(int a, int n , int m){

  int i,res;

  res = 1;

  for(i=1;i<=n;i++)

  res = (res*a%m)%m;

  return res%m;

}

Desvantagens: número de multiplicações O(n)  

    Exponenciação Modular Rápida

    an  mod m =(a (n/2) mod m)2 mod m , n é par e n > 0

    an  mod m = a mod m* a(n-1) mod m , n é impar e n > 0

    a0  mod m = 1          , caso contrário

    Algoritmo 3: an  mod m

  int fastexpmod (int a, int n, int m){

    if(n==0) return 1;

    else if(n%2==0){

    int x = fastexpmod(a,n/2,m);

    return (x*x)%m; 

    }else{

     return (a%m*fastexpmod(a,n-1,m))%m;

    }

  }

Números randômico e Geradores

Números randômicos e geradores

Uma maneira de gerar números pseudo-randômicos é através de funções da seguinte forma

seed(0) = 0

seed(n+1) = (seed(n) + STEP) % MOD

Essa função gera números pseudo-randômicos entre 0 e MOD-1. Se escolhermos os valores de STEP e MOD cuidadosamente, nós podemos gerar todos os valores no intervalo 0 até MOD-1. Caso contrário, obtermos apenas ciclos com um subconjunto dos valores no intervalo 0 até MOD-1. Um número é dito gerador quando o ciclo gerador por ele tem MOD números.

Considere o seguinte exemplo:

STEP = 3

MOD = 5

Sequência Gerada: 0,3,1,4,2,0,3,1,4,2,0,...

Tamanho do ciclo : 5

STEP = 5

MOD 20

Sequência: 0, 5,10,15,0,5,10,15,...

Tamanho do ciclo: 4

Considere o seguinte problema:
 Descobrir se para os valores de STEP e MOD, a função é geradora ou não?

Uma solução simples seria descobrir o tamanho do ciclo gerador pelo números. Para isso, basta guardar os valores da função a partir do valor inicial 0. Quando aparecer o primeiro número repetido, teremos o fim do ciclo.

int i,x;
  int values[MOD];
  for(i=0; i< MOD; i++)
   values[i] = 0;
  for(i=0;i<MOD;i++){
    x = seed(i);
    if(values[x]==0){
      printf("%d\n",seed(i));
      values[x]=1;
    }else{
      printf("tamanho %d\n",i);
      break;
    }
  }
  if(i==MOD){
    printf("gerador randomico uniforme\n");
  }else{
    printf("nao gerador\n");
  } 

Uma solução maravilhosamente simples existe para esse problema. Uma função é geradora se os valores STEP e MOD são primos entre si.

if(mdc(STEP,MOD)==1){
    printf("gerador randomico uniforme\n");
  }else{
    printf("nao gerador\n");
  }

Esse problema também ocorre na biologia :) . O processo evolutivo da cigarra selecionou como o tamanho do ciclo de vida das cigarras um número primo para protegê-la dos outros predadores.

Leia os seguintes textos:

http://amatematicaandaporai.blogspot.com/2009/03/cigarra-conhece-os-numeros-primos.html

http://www1.folha.uol.com.br/folha/ciencia/ult306u11973.shtml