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 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 ≤ i ≤ N). 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
0 20000 33333
Output
#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
0 20000 33333
Output