TÓPICO

Sobre o problema

Wellerson Salvatore perguntou 3 years ago

Em outro post vi que esse problema se resolve com O(1) porem não entendo muito bem o que isso significa será que alguém pode me recomendar algo para ler ou um vídeo para assistir a respeito disso?

Este tópico foi resolvido e não pode receber novas respostas.

  • Wellerson Salvatore respondido 3 years ago

    Deu certo com um tempo de 0.572s, vlw pela dica agora vou estar estudando um pouco mais sobre BIG-o e algoritmos.

  • Wellerson Salvatore respondido 3 years ago

    não entendi muito bem o que você quis dizer com 'and bit-a-bit com o valor 0x03', com relação a c++ usei a mesma ideia mas tambem deu TLE.

    #include <bits/stdc++.h>
    #include<math.h>
    using namespace std;
    int main(int argc, char const *argv[])
    {
        int t, i;
        long long int n;
        cin >> t;
        int vetor[4] = {1, 7, 9, 3};
    
        for(i = 0; i < t; i++) {
            cin >> n;
            cout << vetor[n % 4] << "\n";
    
        }
        return 0;
    }
    

    re - acabei de ler a respeito do an bit-a-bit e achei isso 'O operador AND bit a bit compara cada bit do primeiro operando com o bit correspondente de seu segundo operando. Se os dois bits forem 1, o bit de resultado correspondente será definido como 1. Caso contrário, o bit de resultado correspondente será definido como 0.' e consegui entender um pouco.

  • Wesckeley Martins respondido 3 years ago

    Então dá TLE em Python, observe que nenhuma submissão em Python passou nesse exercício. Se usar a mesma ideia em C/C++ seu código passa. O tempo tá muito apertado para o tamanho dos casos de teste. Observe também que não há verificação quando você usa a array nessa forma, pois asssume-se acesso direto na ram. Outra maneira de fazer o resto da divisão por 4 é simplesmente fazer um and bit-a-bit com o valor 0x03, isto é, n % 4 = n & 0x03.

  • Wellerson Salvatore respondido 3 years ago

    def calculo():
        vetor = [1, 7, 9, 3]
        print(vetor[n%4])
    t = int(input())
    for i in range(t):
        n = int(input())
        calculo()
  • Wellerson Salvatore respondido 3 years ago

    Com n mod 4 da pra saber o valor de 7^n mod 10 sem precisar calcular 7^n, só que isso ainda da TLE... Pois alem de calcular n mod 4 ainda tem que fazer a verificação e isso custa tempo de execução.

  • Wesckeley Martins respondido 3 years ago

    A ideia é essa mesmo, agora é só relacionar n com 7^n mod 10. Dado n é possível saber o valor de 7^n mod 10 sem precisar calcular 7^n?

  • Wellerson Salvatore respondido 3 years ago

    Acho que estou vendo esse padrão de forma errada, primeiro achei que fosse o resto da divisão ex:

    7^0 =        1 % 10 = 1
    7^1 =        7 % 10 = 7
    7^2 =       49 % 10 = 9
    7^3 =      343 % 10 = 3
    7^4 =     2401 % 10 = 1
    7^5 =    16807 % 10 = 7
    7^6 =   117649 % 10 = 9
    7^7 =   823543 % 10 = 3
    7^8 =  5764801 % 10 = 1
    7^9 = 40353607 % 10 = 7

    tem tambem o padrão do n % 4 ex:

    n - 4
    4 % 4 == 0
    5 % 4 == 1
    6 % 4 == 2
    7 % 4 == 3
    SENDO
    0 -> 1
    1 -> 7
    2 -> 9
    3 -> 3

    foram esses os padrões que entendi.

  • Wesckeley Martins respondido 3 years ago

    Você ainda está fazendo a conta 7^n mod 10 nos seus códigos. Tente usar o padrão pra não precisar fazer essas contas, a ideia é essa. Observe também que 0 <= N <= 10^9, ou seja, mesmo que consiga resolver o TLE (fazendo as contas), provavelmente vc receberia um WA no C++, pois 7^(10^9) é bem grande.

  • Wellerson Salvatore respondido 3 years ago

    Talvez eu que esteja errando algo...

    #python
    def calculo():
        print((7 ** n) % 10)
    t = int(input())
    for i in range(t):
        n = int(input())
        calculo()
    //c++
    #include <bits/stdc++.h>
    #include<math.h>
    using namespace std;
    int main(int argc, char const *argv[])
    {
        int t, i;
        long long int r, n;
        cin >> t;
    
        for(i = 0; i < t; i++) {
            cin >> n;
            r = pow(7,n);
            r = r % 10;
            cout << r << "\n";
        }
        return 0;
    }
  • Wesckeley Martins respondido 3 years ago

    Então, os arquivos de entrada e saída desse problema são provavelmente muito grandes. Em C/C++ deve passar em 1s, já linguagens como Java acho que não passa.

  • Wellerson Salvatore respondido 3 years ago

    Obrigado perla dica vou estar lendo esse livro. A respeito da função 7^n mod 10 consegui identificar o padrão, mas mesmo assim continua dando TLE.

  • Wesckeley Martins respondido 3 years ago

    Fala Wellerson! Pra saber um pouco mais da notação O, dê uma olhada em Big O, eu particulamente gosto do livro do Cormen. Agora pra saber como responder cada caso de teste em O(1), basta observar o comportamento da função 7^n mod 10, escreva os primeiros termos no papel e tente achar um padrão.