Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2402

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

Selos

 

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

Timelimit: 1

Euclides é um garoto que gosta muito de colecionar selos. No seu aniversário, seus pais o presentearam com N selos, todos em formato de quadrados com 1 cm de lado. Euclides gostaria de guardar todos os N selos que ganhou colando-os numa página de papel em branco. Ao decidir por guardá-los assim, no entanto, ele logo percebeu que a única forma que lhe agradava de posicionar os selos na página era a forma de um retângulo completamente coberto pelos mesmos, sem sobreposição.

Ele percebeu também que, independente do número de selos obtido, colocar todos os selos numa única linha ou todos os selos numa única coluna é uma configuração válida. Como essa maneira usa a página do caderno de um jeito muito ineficiente, Euclides gostaria de saber se existe algum modo de dispor os N selos num retângulo que tenha mais de uma linha e mais de uma coluna tal que todas as linhas e colunas sejam completamente ocupadas por selos (isto é, tal que não existam posições sem selos no interior do retângulo).

A figura abaixo exemplifica o primeiro caso de teste, duas maneiras de guardar os selos em forma de retângulo.

 

Entrada

 

A entrada contém uma única linha com um único inteiro N (1 ≤ N ≤ 10 000 000 000.​), o número de selos que Euclides ganhou.

 

Saída

 

A saída deve conter uma linha com um único caracter, que deve ser 'S' se for possível organizar os selos em um retângulo com mais que uma linha e mais que uma coluna ou 'N' caso não seja possível.

 

 

 

Exemplos de Entrada Exemplos de Saída

8

S

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>

#define true 1
#define false 0

_Bool isPrime(long long);

int main (void)
{

	long long n;

	scanf("%lld", &n);
	// printf("%s\n", ((n & 1) || n == 2) ? "N" : "S");
	printf("%s\n", isPrime(n) ? "N" : "S");

}

_Bool isPrime(long long x)
{

	long long i;

	if (x == 1 || x == 2)
		return true;

	if (!(x & 1))
		return false;

	for (i = 3; i * i  < = x; i += 2)
		if (x % i == 0)
			return false;

	return true;

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
8

Output

x
+
cmd
S

#2 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
typedef unsigned long long llu;
int main() {
    llu n, i;
    scanf("%llu", &n);
    if (n % 2 == 0) {
        printf("S\n");
        return 0;
    }
    for (i = 3LLU; i * i  < = n; i += 2)
        if (!(n % i)) {
            printf("S\n");
            return 0;
        }
    printf("N\n");
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
8

Output

x
+
cmd
S
Advertisements

Demonstration


Previous
#2401 Beecrowd Online Judge Solution 2401 Calculadora Solution in C, C++, Java, Js and Python
Next
#2403 Beecrowd Online Judge Solution 2403 Escalonamento Ótimo Solution in C, C++, Java, Js and Python