Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2353
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2353
Just in Time
By Bruno Junqueira Adami 
Brazil
Timelimit: 1
Hello contestant, I want to play a game. Your coach is in the contest room with a bomb about to explode in his hands. This bomb will be set to detonate in T seconds, and if it detonates in the contest room it is going to explode only your team’s balloons.
I can tell you that the contest room is inside a building that contains N rooms in total. From each room there is exactly one direct tunnel to another room, which can only be used in one direction. For example if room A connects to room B, then you can walk from room A to room B, but not from room B to room A, unless of course room B has a direct tunnel to room A.
The bomb has a special mechanism that detects if your coach stops moving, and if so it immediately triggers the detonation taking all your team’s balloons down. For that reason your coach will constantly walk between the rooms, taking exactly one second to move through each tunnel. The only way for your team to save its balloons is for your coach not to be in the contest room when the bomb detonates.
You don’t have the building map in hand, all I can tell you is that the tunnels are chosen uniformly at random. However, I will give you the possibility to set T , which must be an integer between 2 and N inclusive. Your job is to choose T in such a way that it maximizes your balloons’ chance to survive this riddle.
Let the game begin.
Input
The input consists of a single line that contains one integer N , representing how many rooms there are in the building (2 ≤ N ≤ 109 ).
Output
Output a line with one integer representing the value of T that maximizes your balloons’ chance to survive the riddle.
| Input Samples | Output Samples |
|
3 |
3 |
|
12 |
11 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <math.h>
#define true 1
#define false 0
long isPrime(long);
int main (void)
{
long n;
scanf("%ld", &n);
printf("%ld\n", n == 2 ? 2 : isPrime(n));
}
long isPrime(long x)
{
long i, j;
if (x % 2 == 0)
x -= 1;
for (i = x; i >= 2; i -= 2)
{
_Bool flag = true;
long size = sqrt(i);
for (j = 3; j < = size; j += 2)
if (i % j == 0)
{
flag = false;
break;
}
if (flag)
return i;
}
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
typedef long long ll;
bool isprime(ll x) {
if (x == 2) return true;
if (x % 2 == 0) return false;
for (ll i = 3; i * i < = x; i += 2) {
if (x % i == 0) return false;
}
return true;
}
int main() {
ll n;
scanf("%lld", &n);
while (n > 0) {
if (isprime(n)) {
printf("%lld\n", n);
return 0;
}
n--;
}
return 0;
}
Input
Output