// One-star problem
// Problem 10714 Ants
/*
This program is written by
Prof. Chua-Huang Huang
Department of Information Engineering and Computer Science
Feng Chia University
Taichung, Taiwan
Disclaimer:
The programming problem is downloaded from UVa Online Judge (https://uva.onlinejudge.org/).
The program solution is provided for helping students to prepare Collegiate Programming
Examination (CPE). The author does not guarantee the program is completely correct to pass
UVa Online Judge platform or CPE examination platform.
This program is not intended for a student to copy only. He/She should practice the
programming problem himself/herself. Only use the program solution as a reference.
The author is not responsible if the program causes any damage of your computer or
personal properties.
No commercial use of this program is allowed without the author's written permission.
*/
#include
#include
/*
Let use divide all the ants in two groups, the first group is the ants on the left hands
of the central point of the pole and the second group is the ants on the right hand side
of te central point of the pole. If there is an ant at the center of the group, count it
in the first group.
The scenario of the earlies time for ALL ants to fall off the pole is that all ants
in the first group walk to the left and all ants in the second group walk to the right.
The nearest ant to the center, say, K, will be the last one to fall off the pole at time
K if it is in the first group, and at time N-K if it is in the second group. Therefore,
the algorithm for the earlies time for ALL ants to fall is to find the ant with the
maximum value m, if m<=n/2, or n-m, if m>n/2.
The scenario of the latest time for ALL ants to fall off the pole is that the ant nearest
to an end of the pole walk toward the far end. Then this ant must the one farest from the
center of the pole. Let the ant at L be the nearest one to an end, say, left hand side,
and it walks to the right. If L does not meet any other ant, he/she will fall at time N-L,
all other ants must fall off the pole before time N-L. If L meets some another ant,
say, H, and turn back, the turn back position must be on the left half of the pole;
otherwise, it contradicts to the fact that L is the farest ant from the center. H will
pick up the rest journey of L and fall off the pole at time N-L and L falls off before
time N-L. If H meet another ant in the rest of journey, the meeting point must be also
at the left half of the pole and this ant pick up the rest of journey to the right form
that meeting point. Simlaryly, if L is the nearest one to the right end and walk to the
left, the latest time for ALL ants to fall is L. Hence, the algorithm for latest time for
all ant to fall is to find the ant with the maximum value m, if m>n/2, or n-m, if m<=n/2.
*/
int main(void) {
int cases; // Number of cases.
int pole; // Length of the pole.
int ants; // number of ants.
int p; // Position of an ant.
int earliest; // Earliest time for ALL ants to fall.
int latest; // Latest time for ALL ants to fall.
int i, j; // Loop variable.
scanf("%d", &cases); // Input the number of cases.
for (i=0; i