Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2366

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2366

Maratona

 

Por OBI - Olimpíada Brasileira de Informática 2009 BR Brazil

Timelimit: 1

A maratona é talvez a prova mais desgastante entre as modalidades olímpicas: são quarenta e dois mil, cento e noventa e cinco metros de percurso. Por isso, os organizadores sempre posicionam vários postos de água ao longo do trajeto da prova, onde copos de água são distribuídos aos competidores.

João Saci é um jovem atleta que tem boas chances de se tornar um maratonista de primeira linha. No entanto, João Saci descobriu que somente consegue terminar uma maratona se ingerir alguns copos de água durante o percurso. O Laboratório de Biomecânica da universidade local, através de experimentos, determinou que João Saci consegue percorrer exatamente mais dois mil metros após o instante em que ingere um copo de água. A distância que João Saci consegue percorrer após ingerir um copo de água é denominada de distância intermediária máxima. Assim, se a distância entre dois postos de água consecutivos no percurso da maratona for sempre menor ou igual do que a distância intermediária máxima de João Saci, ele consegue terminar a prova. Caso contrário ele não consegue terminar a prova.

O Laboratório de Biomecânica quer agora realizar estudos similares com outros maratonistas, que têm valor de distâncias intermediárias máximas distintas, e precisa de sua ajuda.

Sua tarefa é escrever um programa que, dada a posição dos postos de água ao longo do percurso, e a distância intermediária máxima de um atleta, determine se o atleta consegue ou não completar a prova.

 

Entrada

 

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado).

A primeira linha da entrada contém dois números inteiros N e M, separados por um espaço em branco, indicando respectivamente o número de postos de água (2 ≤ N ≤ 10000) e a distância intermediária máxima de um atleta, em metros (1 ≤ M ≤ 42195). A segunda linha contém N números inteiros Pi, separados por um espaço em branco, representando a posição dos postos de água ao longo do trajeto da maratona. A posição de um posto de água é dada pela distância, em metros, do início do percurso até o posto de água (0 ≤ Pi ≤ 42195 para 1 ≤ iN). O primeiro posto de água está sempre localizado no ponto de partida (ou seja, P1 = 0) e todos os postos estão em posições distintas. Além disso, os postos de água são dados na ordem crescente de sua distância ao início do percurso.

Note que a distância total da prova é a oficial para a maratona, ou seja, 42195 metros.

 

Saída

 

Seu programa deve imprimir, na saída padrão, uma única linha contendo o caractere ‘S’ se o atleta consegue terminar a prova, ou o caractere ‘N’ caso contrário.

 

 

 

Exemplos de Entrada Exemplos de Saída

3 20000

0 20000 33333

S

Code Examples

#1 Code Example with C++ Programming

Code - C Programming


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main (void)
{

	unsigned i;
	bool termina = true;
	unsigned atual, anterior;
	int qtsPostos, distIntMax;

	scanf("%u %u", &qtsPostos, &distIntMax);

	anterior = 0;
	for (i = 0; i  <  qtsPostos; ++i)
	{

		scanf("%u", &atual);
		if ((atual - anterior) > distIntMax)
			termina = false;

		anterior = atual;

	}

	if (termina && (42195 - anterior  < = distIntMax))
		printf("S\n");
	else
		printf("N\n");

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3 20000
0 20000 33333

Output

x
+
cmd
S

#2 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
int vetor[10010];
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vetor[n] = 42195;
    for (int i = 0; i  <  n; i++) scanf("%d", &vetor[i]);
    for (int i = 1; i  < = n; i++) {
        if (vetor[i] - vetor[i - 1] > m) {
            printf("N\n");
            return 0;
        }
    }
    printf("S\n");
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3 20000
0 20000 33333

Output

x
+
cmd
S
Advertisements

Demonstration


Previous
#2355 Beecrowd Online Judge Solution 2355 Brazil and Germany Solution in C, C++, Java, Js and Python
Next
#2367 Beecrowd Online Judge Solution 2367 Competição de Chocolate Solution in C, C++, Java, Js and Python