Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1612
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1612
Little Ant
By Bruno Adami, Universidade de São Paulo - São Carlos Brazil
Timelimit: 1
A little ant is walking on the top of a tree trunk of length N meters. We can consider that the ant may assume the positions from 0 to N-1. Assume that it is on the X axis of the coordinate plane, but it starts in an unknown position. The only thing known about the ants initial position is that its value is an integer number.
The little ant may take a step to the right or to the left, and this step will make it move one meter. If the ant is at position Pand moves to the right, it will assume the position P+1. If the step is to the left, it will assume the position P-1. If in any moment it assumes the position -1 or N, the ant will fall off the tree trunk! A step takes one second to be completed, and the ant is always moving.
Considering that the ant will always choose the worst sequence of movements, you must choose an initial position that maximizes the time that the ant will stay on the top of the trunk. Output that time.
Input
The first line contains an integer T (T <= 100) indicating the number of test cases.
For each test case we will have a single line with the integer N (1 ≤ N ≤ 109) indicating the size of the tree trunk.
Output
For each case, output the maximum amount of time the little ant can be on the trunk.
Sample Input | Sample Output |
3 1 2 4 |
1 1 2 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <math.h>
int main(void) {
int n, q, i;
scanf("%d", &q);
for (i = 0; i < q; ++i) {
scanf("%d", &n);
printf("%d\n", (int)ceil(n/2.0));
}
return 0;
}
Copy The Code &
Try With Live Editor
Input
1
2
4
Output
1
2
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main(void) {
int n, q, i;
cout << fixed << setprecision(0);
cin >> q;
for (i = 0; i < q; ++i) {
cin >> n;
cout << ceil(n/2.0) << endl;
}
return 0;
}
Copy The Code &
Try With Live Editor
Input
1
2
4
Output
1
2