1

Estou tentando resolver a questão 1805 da URI:

Um número natural é um inteiro não-negativo (0, 1, 2, 3, 4, 5,...). A sua tarefa neste problema é calcular a soma dos números naturais que estão presentes em um determinado intervalo [A, B] inclusive.

Por exemplo, a soma dos números naturais no intervalo [2, 5] é 14 = (2+3+4+5).

Entrada

Cada caso de teste contém dois inteiros A e B (1 ≤ AB ≤ 109), representando o limite inferior e o superior respectivamente.

Saída

Para cada caso de teste, a saída consiste de uma linha contendo a soma dos números naturais do intervalo.

Mas sempre está dando erro:

Time limit exceeded

Não sei o que está errado sendo que os resultados são iguais que a questão.

O código é este:

#include <stdio.h>
int main(int argc, char** argv)
{
    long long int n1,n2,i,j=0;
    scanf("%lld %lld",&n1,&n2);
    for(i=n1;i<=n2;i++)
    {
        j+=i;
    }
    printf("%lld\n",j);
    return 0;
}
5
  • pt.meta.stackoverflow.com/a/5485/28595
    – user28595
    Commented 31/10/2017 às 16:01
  • Enunciado do problema: urionlinejudge.com.br/judge/pt/problems/view/1805 Commented 31/10/2017 às 16:04
  • 2
    Como você é um usuário iniciante e o código é simples, quebrei o galho e postei o código como texto na pergunta para você. Entretanto, evite postar código como imagem. Commented 31/10/2017 às 16:14
  • 1
    @vnbrs Entendo você colocar que é erro de timeout no título, mas acho que a informação de que isso é um erro de timeout faz parte da resposta, ainda mais considerando que o autor da pergunta enfatiza "que os resultados são iguais que a questão", mas nada havia falado sobre o tempo. Commented 31/10/2017 às 16:33
  • tudo bem,com o tempo vou me aprendendo com o tempo,obrigado pelas dicas Commented 31/10/2017 às 17:07

1 Resposta 1

3

O código em si está correto, mas ele tem um desempenho muito ruim.

Tal como está no enunciado:

Entrada

Cada caso de teste contém dois inteiros A e B (1 ≤ AB ≤ 109), representando o limite inferior e o superior respectivamente.

Ou seja, se a entrada for a seguinte:

1 1000000000

O seu programa vai demorar um longo tempo para terminar. E é aí que ele estoura o tempo limite. A solução é procurar uma solução baseada em progressão aritmética que elimine a necessidade de utilizar-se o laço for, fornecendo o resultado em um tempo rápido independente de qual for a entrada utilizada.

3
  • Outros detalhes: 10^9 não necessita de long long int , como em um inteiro de 32 bits (normalmente int, mas às vezes em plataformas mais antigas long int). Commented 31/10/2017 às 16:14
  • 1
    @JeffersonQuesado Lembre que ele ainda vai somar todos esses fatores. O resultado é que no caso de 1 até 10^9, a soma é de 500.000.000.500.000.000, o que estoura um inteiro de 32 bits. Commented 31/10/2017 às 16:19
  • bem percebido. Eu me preocupei só com a entrada, esqueci dos cálculos Commented 31/10/2017 às 16:20

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .