URI (BEECROWD) - 2158 - Helping Uncle Cláudio (Ajudando o Tio Cláudio) - Matemática - C, C++ e Haskell

Buenas! Estou aqui mais uma vez para resolver um problema de Matemática! Agora tenho resolvido alguns dessa categoria, pra que vocês possam avançar não apenas nas categorias básicas :)

O exercício de hoje é o Helping Uncle Cláudio (Ajudando o Tio Cláudio). Vamos conferir como se resolve esse problema?

Plataforma: URI (BEECROWD)

Problema: 2158

Linguagens: C, C++ e Haskell

Enunciado:

O ano é 1986, em uma publicação científica foi divulgada a descoberta de uma molécula 3D de carbono, onde os átomos ocupam os vértices de um poliedro convexo com faces pentagonais e hexagonais, como em uma bola de futebol.

Em homenagem ao professor Cláudio Carvalho, a molécula foi denominada Claudeno. Cláudio gosta muito de verificar a quantidade de átomos e de ligações em uma determinada molécula. Hoje com a idade avançada do professor ele não consegue mais fazer os calculos "de cabeça", e solicita que você, o estagiário cuidador de velhinhos, crie um programa que o possa ajudar.

Solução:

Basta ler os valores e aplicar as fórmulas. Pelos exemplos é possível inferir que basta multiplicar o primeiro valor por 5 e o segundo por 6 e dividir por dois para não duplicar as ligações. Os átomos, percebe-se que basta obter o número de ligações menos os próprios valores de fp e fh e mais 2.

Código em C:

A sacada do exercício é declarar fp e fh como long long int, pois assim não se corre o risco de obter overflow. Assim, basta aplicar as fórmulas para ligações e átomos e imprimir os valores. A formatação do long long int deve ser feita com lld, não esqueça disso!

#include <stdio.h>
int main() {
    int c = 1;
    long long int fp, fh;    
    while (scanf("%lld %lld", &fp, &fh) != EOF) {
        long long int ligacoes = (5 * fp + 6 * fh) / 2;
        long long int atomos = 2 + ligacoes - fp - fh;
       
        printf("Molecula #%d.:.\n", c++);
        printf("Possui %lld atomos e %lld ligacoes\n\n", atomos, ligacoes);
    }
    
    return 0;
}

Código em C++:

Mesma lógica aplicada nos outros códigos!

#include <iostream>

int main() {
    int c = 1;
    long long int fp, fh;

    while (std::cin >> fp >> fh) {
        long long int ligacoes = (5 * fp + 6 * fh) / 2;
        long long int atomos = 2 + ligacoes - fp - fh;    

        std::cout << "Molecula #" << (c++) << ".:." << std::endl;
        std::cout << "Possui " << atomos << " atomos e " << ligacoes << " ligacoes";
        std::cout << std::endl << std::endl;
    }
  
    return 0;
}

Código em Haskell:

Aqui basta ler os valores fp e fh e definir ligacoes e atomos conforme as fórmulas indicadas. Assim, basta imprimir os valores.

import System.IO (isEOF)

main :: IO ()
main = do
   let c = 1
   getAns c

getAns :: Int -> IO ()
getAns c = do
   done <- isEOF
   if done
      then return ()
      else do
         line <- getLine
         let [fp, fh] = map read (words line) :: [Integer]
         let ligacoes = div (5 * fp + 6 * fh) 2
         let atomos = 2 + ligacoes - fp - fh
         putStrLn ("Molecula #" ++ show c ++ ".:.")
         putStrLn ("Possui " ++ show atomos ++ " atomos e " ++ show ligacoes ++ " ligacoes\n")
         getAns (c + 1)

Lembrando que a chave aleatória PIX do Blog é 6d8bc7a8-5d74-493a-ab7a-3515baf35956.

Caso possa fazer uma doação, agradeço! Até mais!

URI (BEECROWD) - 2636 - 3-RSA - Matemática - C, C++ e Haskell

Vamos resolver um probleminha bem difícil do Beecrowd! Pelo menos em comparação com os que estamos acostumados. O problema 3-RSA vale 9,1 pontos na plataforma. Mas falando sério, tem problemas que considero bem mais difíceis... enfim, o fato é que o problema está resolvido e que aqui ele será apresentado a vocês!

Plataforma: URI (BEECROWD)

Problema: 2636

Linguagens: C, C++ e Haskell

Enunciado:

Pedro, assim como muitos outros estudantes de graduação, ficou fascinado com a beleza e sofisticação da criptografia. Começou a ler referências históricas, estudar os principais algoritmos e a buscar artigos e reportagens que abordassem o tema sob os mais diferentes aspectos.

Contudo, o grande volume de informações adquiridas num curto espaço de tempo o levou a alguns questionamentos e temores. Preocupado com a computação quântica, que em teoria inutilizaria a criptografia RSA, e motivado pela história do algoritmo DES, que teve uma evolução mais segura denominada 3DES, ele resolveu propôr uma versão mais segura do RSA, denominada 3-RSA.

No 3-RSA, o módulo n, composto no algoritmo original por dois números primos ı́mpares distintos, seria agora composto por 3 primos ı́mpares distintos! Pedro estava certo que esta modificação traria maior dificuldade de quebra do algoritmo, uma vez que os atacantes agora teriam que encontrar 3 fatores de n, e não apenas 2.

Sabendo que, em criptografia, às vezes menos é mais, e disposto a mostrar ao motivado e bem intencionado Pedro que a modificação proposta, de fato, enfraquece o RSA, fatore o módulo n do algoritmo 3-RSA, exibindo seus três fatores primos.

Solução:

A estratégia é utilizar o crivo de eratóstenes para preencher o array primos, assim facilitando a fatoração do número informado (n). Com isso, varrendo o array de primos encontra-se tanto p quanto q. Tendo esses valores e n, fica fácil obter r, pois ele será n/(p*q).

Código em C:

#include <stdio.h> 

int main() { 
    int max = 1000000;
    int i;
    int primos[max+1];
    long long int n;
    long long int p;
    long long int q;

    for (i = 1; i <= max; i += 2)
        primos[i] = 1;

    for (i = 0; i <= max; i += 2)
        primos[i] = 0;

    for (i = 3; i * i <= max; i += 2) {
        if (primos[i]) {
            for (int j = i * i; j <= max; j += i)
                primos[j] = 0;
        }
    }

    while (1) {
        scanf("%lld", &n);
        if (!n)
            return 0;
        for (i = 3; i <= max; i += 2) {
            if (primos[i] && n % i == 0) {
                p = i;
                break;
            }
        }     
        for (i = p + 2; i <= max; i += 2) {
            if (primos[i] && n % i == 0) {
                q = i;
                break;
            }
        }
        long long int r = n / (p * q);
        printf("%lld = %lld x %lld x %lld\n", n, p, q, r);
    }
    return 0; 
}

Código em C++:

A solução segue a mesma lógica do código C.

#include <bits/stdc++.h> 

using namespace std; 

int main() {   
    int max = 1000000;
    int i;
    long long int n;
    long long int p;
    long long int q;
    bool* primos = new bool[max + 1]; 

    for (i = 1; i <= max; i += 2)
        primos[i] = true;
     
    for (i = 0; i <= max; i += 2)
        primos[i] = false;     

    for (i = 3; i * i <= max; i += 2) {
        if (primos[i]) {
            for (int j = i * i; j <= max; j += i)
                primos[j] = false;
        }
    }
    
    while (cin >> n) {    
        if (!n)
            return 0;         

        for (i = 3; i <= max; i += 2) {
            if (primos[i] && n % i == 0) {
                p = i;
                break;
            }
        }
        
        for (i = p + 2; i <= max; i += 2) {
            if (primos[i] && n % i == 0) {
                q = i;
                break;
            }
        }       
        long long int r = n / (p * q);
        cout << n << " = " << p << " x " << q << " x " << r << endl;
    }
    return 0; 
}

Código em Haskell:

Aqui eu acabei nem fazendo o crivo, pois o número será encontrado de qualquer forma (sabe-se que ele é o produto de três primos). O que fiz foi iterar a função findTerm partindo do 3 e somando sempre 2 (ou seja, procurando ímpares). Essa solução passou no beecrowd.

main :: IO ()
main =  do
   n <- readLn :: IO Integer
   if n == 0
      then return ()
      else do
         let maxVal = 1000000
         let p = findTerm 3 maxVal n
         let q = findTerm (p+2) maxVal n
         let r = div n (p * q)
         putStrLn (show n ++ " = " ++ show p ++ " x " ++ show q ++ " x " ++ show r)
         main

findTerm i j n
   | mod n i == 0 = i
   | otherwise = findTerm (i+2) j n

Por hoje era isso! Espero que tenham curtido mais esse post.

Chave PIX do Blog: 6d8bc7a8-5d74-493a-ab7a-3515baf35956.

Toda doação é bem-vinda Obrigado e até a próxima! 

URI (BEECROWD) - 3312 - Imberbe Matemático - Matemática - C, C++ e Haskell

Novo exercício de Matemática resolvido e postado aqui, gente! Resolvi o Imberbe Matemático de algumas formas diferentes e aqui trago essas soluções para vocês. Esse problema vale 5 pontos no Beecrowd, então bora ver como eu pontuei?

Plataforma: URI (BEECROWD)

Problema: 3312

Linguagens: C, C++ e Haskell

Enunciado:

Guilherme tem dez anos e é um pequeno entusiasta da matemática, e descobriu recentemente a existência dos famosos números primos. Com seu grande interesse pela disciplina, sua professora Marlene já lhe adiantou alguns conteúdos e um deles é o fatorial. Guilherme adora fazer exercícios e deseja treinar mais para preparar‐se para a Olimpíada de Matemática. Marlene passou uma lista de números para Guilherme resolver em casa, na qual todos os números primos encontrados deverão ser encontrados também seu respectivo fatorial. Ajude Guilherme a conferir seus exercícios e estudar para a Olimpíada.

Solução:

Há algumas soluções possíveis. Uma delas é usando o Crivo de Eratóstenes.

Código em C:

#include <stdio.h> 
#define LIMITE 101 
#define TOTAL_PRIMOS 25
#define MAX_VALORES 100000
int main() {
    int n;
    int i;
    int j;
    int k;
    int valores[MAX_VALORES];
    int primos[LIMITE];
    int osPrimos[TOTAL_PRIMOS] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
    char *fats[LIMITE];
    char *fatoriais[TOTAL_PRIMOS] = {"2", "6", "120", "5040", "39916800", "6227020800", "355687428096000", "121645100408832000", "25852016738884976640000", "8841761993739701954543616000000", "8222838654177922817725562880000000", "13763753091226345046315979581580902400000000", "33452526613163807108170062053440751665152000000000", "60415263063373835637355132068513997507264512000000000", "258623241511168180642964355153611979969197632389120000000000", "4274883284060025564298013753389399649690343788366813724672000000000000", "138683118545689835737939019720389406345902876772687432540821294940160000000000000", "507580213877224798800856812176625227226004528988036003099405939480985600000000000000", "36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000", "850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000", "4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000", "894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000", "39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000", "16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000", "96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000"};

    for (i = 0; i < LIMITE; i++)
        primos[i] = 0;

    for (i = 0; i < TOTAL_PRIMOS; i++) {
        j = osPrimos[i];
        primos[j] = 1;
        fats[j] = fatoriais[i];
    }

    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d ", &valores[i]);

    for (i = 0; i < n; i++) {
        k = valores[i];
        if (primos[k])
            printf("%d! = %s\n", k, fats[k]);
    }

    return 0; 
}

Código em C++:

#include <iostream> 
#include <string>

const int LIMITE = 101;
const int TOTAL_PRIMOS = 25;
const int MAX_VALORES = 100000;

int main() {
    int n;
    int i;
    int j;
    int k;
    int valores[MAX_VALORES];
    int primos[LIMITE];
    int osPrimos[TOTAL_PRIMOS] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
    std::string fats[LIMITE];
    std::string fatoriais[TOTAL_PRIMOS] = {"2", "6", "120", "5040", "39916800", "6227020800", "355687428096000", "121645100408832000", "25852016738884976640000", "8841761993739701954543616000000", "8222838654177922817725562880000000", "13763753091226345046315979581580902400000000", "33452526613163807108170062053440751665152000000000", "60415263063373835637355132068513997507264512000000000", "258623241511168180642964355153611979969197632389120000000000", "4274883284060025564298013753389399649690343788366813724672000000000000", "138683118545689835737939019720389406345902876772687432540821294940160000000000000", "507580213877224798800856812176625227226004528988036003099405939480985600000000000000", "36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000", "850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000", "4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000", "894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000", "39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000", "16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000", "96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000"};

    for (i = 0; i < LIMITE; i++)
        primos[i] = 0;

    for (i = 0; i < TOTAL_PRIMOS; i++) {
        j = osPrimos[i];
        primos[j] = 1;
        fats[j] = fatoriais[i];
    }

    std::cin >> n;
    for (i = 0; i < n; i++)
        std::cin >> valores[i];

    for (i = 0; i < n; i++) {
        k = valores[i];
        if (primos[k])
            std::cout << k << "! = " << fats[k] << std::endl;
    }

    return 0; 
}

Código em Haskell:

Solução 1:

import Control.Monad (mapM_)

pertence :: Eq a => a -> [a] -> Bool
pertence a [] = False
pertence a (x:xs) = a == x || pertence a xs

filtro :: (Int -> Bool) -> [Int] -> [Int]
filtro p xs = [x | x <- xs, p x]

nDivisivel :: Int -> Bool
nDivisivel n = mod n (n+1) /= 0

divisor :: Int -> Int -> Int -> Bool
divisor 2 _ _ = False
divisor _ _ 1 = True
divisor _ _ 0 = False 
divisor x a b = if mod a b == 0 then divisor (x+1) a (b-1) else divisor x a (b-1) 

crivo :: [Int] -> [Int]
crivo [] = []
crivo (x:xs)
   | divisor 1 x (x-1) = x : crivo xs
   | otherwise = crivo xs

primosAte100 :: [Int]
primosAte100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

fatoriaisAte100 :: [String]
fatoriaisAte100 = ["2", "6", "120", "5040", "39916800", "6227020800", "355687428096000", "121645100408832000", "25852016738884976640000", "8841761993739701954543616000000", "8222838654177922817725562880000000", "13763753091226345046315979581580902400000000", "33452526613163807108170062053440751665152000000000", "60415263063373835637355132068513997507264512000000000", "258623241511168180642964355153611979969197632389120000000000", "4274883284060025564298013753389399649690343788366813724672000000000000", "138683118545689835737939019720389406345902876772687432540821294940160000000000000", "507580213877224798800856812176625227226004528988036003099405939480985600000000000000", "36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000", "850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000", "4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000", "894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000", "39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000", "16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000", "96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000"]

pares :: [(Int, String)]
pares = zip primosAte100 fatoriaisAte100

getResposta [] _ = []
getResposta (x:xs) (y:ys)
   | x == fst y = (show x ++ "! = " ++ snd y) : getResposta xs pares
   | otherwise = getResposta (x:xs) ys

main :: IO ()
main =  do
   n <- readLn :: IO Int
   linha <- getLine
   let valores = map read (words linha) :: [Int]
   let primosEncontrados = crivo valores
   let respostaFinal = getResposta primosEncontrados pares
   mapM_ putStrLn respostaFinal

Solução 2: parecida, mas com alguns detalhes diferentes.

pertence :: Eq a => a -> [a] -> Bool
pertence a [] = False
pertence a (x:xs) = a == x || pertence a xs

filtro :: (Int -> Bool) -> [Int] -> [Int]
filtro p xs = [x | x <- xs, p x]

nDivisivel :: Int -> Bool
nDivisivel n = mod n (n+1) /= 0

divisor :: Int -> Int -> Int -> Bool
divisor 2 _ _ = False
divisor _ _ 1 = True
divisor _ _ 0 = False 
divisor x a b = if mod a b == 0 then divisor (x+1) a (b-1) else divisor x a (b-1) 

crivo :: [Int] -> [Int]
crivo [] = []
crivo (x:xs)
   | divisor 1 x (x-1) = x : crivo xs
   | otherwise = crivo xs

primosAte100 :: [Int]
primosAte100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

fatoriaisAte100 :: [String]
fatoriaisAte100 = ["2", "6", "120", "5040", "39916800", "6227020800", "355687428096000", "121645100408832000", "25852016738884976640000", "8841761993739701954543616000000", "8222838654177922817725562880000000", "13763753091226345046315979581580902400000000", "33452526613163807108170062053440751665152000000000", "60415263063373835637355132068513997507264512000000000", "258623241511168180642964355153611979969197632389120000000000", "4274883284060025564298013753389399649690343788366813724672000000000000", "138683118545689835737939019720389406345902876772687432540821294940160000000000000", "507580213877224798800856812176625227226004528988036003099405939480985600000000000000", "36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000", "850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000", "4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000", "894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000", "39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000", "16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000", "96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000"]

pares :: [(Int, String)]
pares = zip primosAte100 fatoriaisAte100

getAns :: [Int] -> [(Int, String)] -> IO ()
getAns [] _ = return ()
getAns (x:xs) (y:ys)
   | x == fst y = do
      putStrLn (show x ++ "! = " ++ snd y)
      getAns xs pares
   | otherwise = getAns (x:xs) ys

main :: IO ()
main =  do
   n <- readLn :: IO Int
   linha <- getLine
   let valores = map read (words linha) :: [Int]
   let ans = crivo valores
   getAns ans pares

Solução 3: mais uns detalhes diferentes.

pertence :: Eq a => a -> [a] -> Bool
pertence a [] = False
pertence a (x:xs) = if a == x then True else pertence a xs

filtro :: (Int -> Bool) -> [Int] -> [Int]
filtro p [] = []
filtro p (x:xs) = if p x == True then (x: filtro p xs) else (filtro p xs)

nDivisivel :: Int -> Bool
nDivisivel n = mod n (n+1) /= 0

divisor :: Int -> Int -> Int -> Bool
divisor 2 _ _ = False
divisor _ _ 1 = True
divisor _ _ 0 = False 
divisor x a b = if mod a b == 0 then divisor (x+1) a (b-1) else divisor x a (b-1) 

crivo :: [Int] -> [Int]
crivo [] = []
crivo (x:xs) = if divisor 1 x (x-1) == True then x:crivo (ys) else crivo (xs) 
   where (y:ys)= filtro nDivisivel (x:xs)

primosAte100 :: [Int]
primosAte100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

fatoriaisAte100 :: [String]
fatoriaisAte100 = ["2", "6", "120", "5040", "39916800", "6227020800", "355687428096000", "121645100408832000", "25852016738884976640000", "8841761993739701954543616000000", "8222838654177922817725562880000000", "13763753091226345046315979581580902400000000", "33452526613163807108170062053440751665152000000000", "60415263063373835637355132068513997507264512000000000", "258623241511168180642964355153611979969197632389120000000000", "4274883284060025564298013753389399649690343788366813724672000000000000", "138683118545689835737939019720389406345902876772687432540821294940160000000000000", "507580213877224798800856812176625227226004528988036003099405939480985600000000000000", "36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000", "850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000", "4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000", "894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000", "39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000", "16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000", "96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000"]

pares :: [(Int, String)]
pares = zip primosAte100 fatoriaisAte100

getAns :: [Int] -> [(Int, String)] -> IO ()
getAns [] _ = return ()
getAns (x:xs) (y:ys) = do
   if x == fst y
      then do
         putStrLn (show x ++ "! = " ++ snd y)
         getAns xs pares
      else
         getAns (x:xs) ys

main :: IO ()
main =  do
   n <- readLn :: IO Int
   linha <- getLine
   let valores = map read (words linha) :: [Int]
   let ans = crivo valores
   getAns ans pares

E aí? Gostaram das soluções? Eu espero sinceramente que sim! E voltem sempre, sabendo que aqui será possível encontrar muita solução de exercício. Espero cada vez mais poder contribuir com a formação de vocês.

Essa é a chave aleatória do blog para doações: 6d8bc7a8-5d74-493a-ab7a-3515baf35956.

Agradeço aos que puderem ajudar!

Valeu e até a próxima!