UVa 13181 – Sleeping in hostels
As any seasoned backpacker knows, youth hostels found along the road typically have enormous rooms, with rows upon rows of beds waiting to be occupied.
Despite these beds having been used by countless people, fatigue makes everyone disregard lying on the worn-out mattresses, just to be able to sleep for several hours at a stretch, replenishing their energy for the next day. In fact, to maximize getting a good night's sleep, the most important thing is not the cleanliness of the mattress, but rather the distance from the nearest backpacker. This is because a stranger snoring in the bed next to you could ruin your night more than a swarm of bedbugs. When you enter such a room, the goal is to find a bed and maximize the distance from the nearest backpacker (considering both sides).
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The input consists of multiple test cases, representing the occupancy of beds for one night during the journey.
Each line represents a row of beds, containing a sequence of characters consisting of "." and "X" (up to 500,000 characters). A dot (".") represents an empty bed, while "X" represents an occupied bed. It is guaranteed that there is at least one empty bed and one occupied bed. | For each test case, output a line showing the maximum number of empty beds you could potentially have between the bed you choose and the nearest neighboring bed. |
| .X.X. .X…X. .X….X. …X | 0 1 1 2 |
Thought Process
The first and last characters need to be separately evaluated. For the other positions, find the shortest distance to the left and right sides, compare them to find the maximum, and output the result.
Sample Code－ZeroJudge M851: Sleeping in hostels
#include <iostream>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
string str;
while (cin >> str)
{
int ans = -999;
for (int i = 0; i<str.length(); i++)
{
if (str[i] == '.')
{
if (i == 0)
{
int right = 0;
for (int j = i+1; j<str.length(); j++)
{
if (str[j] == 'X') break;
right++;
}
ans = max(ans, right);
}
else if (i == int(str.length())-1)
{
int left = 0;
for (int j = i-1; j>=0; j--)
{
if (str[j] == 'X') break;
left++;
}
ans = max(ans, left);
}
else
{
int right = 0;
for (int j = i+1; j<str.length(); j++)
{
if (str[j] == 'X') break;
right++;
}
int left = 0;
for (int j = i-1; j>=0; j--)
{
if (str[j] == 'X') break;
left++;
}
int check = min(right, left);
ans = max(check, ans);
}
}
}
cout << ans << "\n";
}
}
//ZeroJudge M851
//Dr. SeanXD