https://www.thehuxley.com/problem/407
Trata-se de um problema simples, porém a solução do jeito que fiz não é eficiente. Não consegui idenficar nenhuma propriedade que me permitisse torná-lo mais eficiente.
Se considerarmos i-j, como sendo o tamanho da entrada (n), e x como sendo o tamanho do ciclo para cada elemento de i até j, a solução é da ordem de O(x*n).
A questão tem um detalhe na descrição que causou a maioria dos meus erros no início. Ela não diz em nenhum lugar que i é menor que j. Ou seja, também é uma entrada válida um j maior. Assim, você deve se preparar para isso.
Mas não esqueça que no final, o i e o j devem ser impressos na mesma ordem que você leu na entrada.
Outro ponto interessante dessa questão é que a entrada termina quando não existe mais nada a ser lido. Na maioria dos problemas, a entrada termina quando um determinado valor é dado, por exemplo, "leia enquanto o número dado for diferente de -1".
Mas nesse caso, não existe isso e você deve ler até não ter mais nada.
Para fazer isso direito é preciso entender como a entrada é passada para o seu programa. Na maioria dos sistemas operacionais, a entrada padrão é representada por um fluxo e esse fluxo é representado por um arquivo. No caso do linux, esse arquivo é o stdin (http://pt.wikipedia.org/wiki/Fluxos_padr%C3%A3o).
Sendo assim, quando você lê através de um scanf, na verdade você lê do fluxo padrão stdin, que por sua vez é um arquivo do seu S.O. Em C, você pode acessar esse arquivo através da variável stdin, definida no arquivo stdio.h:
FILE *stdin;
Veja que o tipo da variável do FILE * (um ponteiro para um arquivo).
Ora, então se você lê sempre de um arquivo, quando você tenta ler algo e não existe mais nada para ser lido, significa que o scanf deveria avisar você que você chegou ao final do arquivo e não tem mais nada. E o scanf faz justamente isso. Se você olhar a documentação do scanf (http://www.cplusplus.com/reference/cstdio/scanf/), você verá a seguinte documentação:
Return Value:
On success, the function returns the number of items of the argument list successfully filled. This count can match the expected number of items or be less (even zero) due to a matching failure, a reading error, or the reach of the end-of-file.
If a reading error happens or the end-of-file is reached while reading, the proper indicator is set (feof or ferror). And, if either happens before any data could be successfully read, EOF is returned.
Ou seja, se você chamar o scanf e chegar ao final do arquivo, ele retorna EOF (um valor definido no arquivo stdio.h)
Logo, você poderia verificar se chegou ao final do arquivo assim:
int x;
if (scanf("%d", &x) == EOF )
{
printf("final do arquivo\n");
}
else
{
printf("O valor de x digitado foi: %d\n",x);
}
ou ainda, poderia ler números enquanto tivesse algo para ler:
while (scanf("%d",&x)!=EOF)
{
// faz alguma coisa
}
Cada linguagem tem a sua forma de ler até o final da entrada:
C++ : http://stackoverflow.com/questions/201992/how-to-read-until-eof-from-cin-in-c
Python: http://stackoverflow.com/questions/15599639/whats-perfect-counterpart-in-python-for-while-not-eof