Albert
7/13/2008 8:07:00 AM
On Jul 11, 9:07 am, Bert <albert.xtheunkno...@gmail.com> wrote:
> Here's my problem:
>
> AFL
>
> Input File: aflin.txt
> Output File: aflout.txt
> Time Limit: 1 second
>
> It's football season, and the rush is on. You have the unfortunate job
> of trying to arrange seating in the stadium for the horde of fans
> phoning in to the ticket office.
>
> Luckily you are only responsible for a single row of seats. For each
> football fan who phones in with a booking for k people, you have to
> find a continuous block of k empty seats in the row in which they can
> sit. To save yourself the hassle of having to decide each time which
> block of k empty seats to book, you decide upon the following
> strategy.
>
> Each time a fan phones in with a booking for k people, you find the
> longest continuous sequence of empty seats in the row (if there is a
> tie then you choose the leftmost longest sequence). You then book the
> first k seats in this sequence (and hope that the sequence of empty
> seats is long enough). These seats are then marked as taken, and you
> move on to answer the next phone call.
>
> As an example, consider a row of 10 seats numbered 1,2,...,10. Say
> that seats 3 and 8 have already been taken before you start making
> bookings. The initial state of the row is illustrated in the following
> diagram, where the shaded seats have already been taken.
>
> Suppose that the first phone call is for a booking of size 1. The
> longest continuous sequence of empty seats is from seats 4 to 7, so
> you place the booking at the beginning of this sequence, claiming seat
> 4.
>
> Suppose that the next request is for a booking of size 2. The longest
> continuous sequence of empty seats is now from seats 5 to 7, so the
> booking is made for seats 5 and 6.
>
> Let the next request be another booking of size 1. There are now two
> longest continuous sequences of empty seats, each of length two. One
> is from seats 1 to 2 and the other is from seats 9 to 10. You choose
> the leftmost of these longest sequences and book seat 1.
>
> And so on. After a few days of carrying out this procedure it is
> becoming rather tedious, so you decide to write a computer program
> that can carry it out for you. Grabbing your laptop and an AFL-branded
> meat pie, you set to work.
> Input
>
> The first line of input will contain the single integer n representing
> the total number of seats in the row (1 <= n <= 30,000). These seats
> are numbered 1,2,...,n from left to right.
>
> The second line of input will contain the single integer t
> representing the total number of seats that have already been taken (0
> <= t <= n). Following this will be t lines, each containing the number
> of a seat that has been taken (no two of these seat numbers will be
> identical).
>
> The next line of input will contain the single integer b representing
> the total number of bookings that you must make (0 <= b <= n).
> Following this will be b lines, each describing a single booking. Each
> of these lines will contain a single integer k representing the number
> of seats to be booked (1 <= k <= n). The bookings will be presented in
> order from the first phone call to the last.
> Output
>
> For each booking, your program should write a single line of output.
> This line should contain a single integer describing the leftmost seat
> that was booked.
>
> You may assume that it is possible to successfully make all of the
> requested bookings using the strategy described above.
> Sample Input
>
> The following sample data corresponds to the example discussed
> earlier.
>
> 10
> 2
> 3
> 8
> 3
> 1
> 2
> 1
>
> Sample Output
>
> 4
> 5
> 1
>
> Here's my code so far
>
> #include <stdio.h>
>
> struct group* nextseat(struct group g[], int ngroups);
> int main()
> {
> /****************************************/
> FILE* in = fopen("aflin.txt" , "r");
> FILE* out = fopen("alfout.txt", "w");
>
> int nseats, t, b;
>
> fscanf(in, "%d", &nseats );
> fscanf(in, "%d", &t );
>
> int booked[t];
> int i = 0;
> for (; i < t; i++)
> {
> fscanf(in, "%d", &booked[i]);
> }
>
> fscanf(in, "%d", &b);
> int bookings[b];
>
> for (i = 0; i < b; i++)
> {
> fscanf(in, "%d", &bookings[i]);
> }
> /****************************************/
>
> /
> ******************************************************************************/
> i = 0; // what group we're up to
> int j = 1; // what booked seat we're up to
>
> struct group {
> int length;
> int fseat;
> } g[nseats];
>
> int ngroups = 0;
> g[i].length = booked[i] - 1;
> if (g[i].length > 0)
> {
> g[i].fseat = 1;
> ++ngroups;
> }
> ++i;
>
> for (; i <= t - 1; i++)
> {
> g[i].length = booked[j] - booked[j-1] - 1;
> if (g[i].length == 0)
> {
> --i;
> }
> else
> {
> ++ngroups;
> g[i].fseat = booked[j-1] + 1;
> }
> ++j;
> }
>
> g[i].length = nseats - booked[j-1];
> if (g[i].length > 0)
> {
> g[i].fseat = booked[j-1] + 1;
> ++ngroups;
> }
>
> int k = 0;
> for (; k < ngroups; k++)
> printf("group[%d] length: %d fseat %d\n", k, g[k].length,
> g[k].fseat);
> /
> ******************************************************************************/
>
> int longest_length = 0;
> int nlonglengroups = 0;
> struct group* longlengroups[ngroups];
>
> for (i = 0; i < ngroups; i++)
> {
> if (g[i].length > longest_length)
> {
> longest_length = g[i].length;
> }
>
> /* if (g[i].length == longest_length)
> {
> longlengroups[nlonglengroups] = &g[i];
> ++nlonglengroups;
> } */
> }
>
> for (i = 0; i < ngroups; i++)
> {
> if (g[i].length == longest_length)
> {
> longlengroups[nlonglengroups] = &g[i];
> ++nlonglengroups;
> }
> }
>
> struct group* leftmostlonggroup = longlengroups[0];
> for (i = 0; i < nlonglengroups; i++)
> {
> if (longlengroups[i]->fseat < leftmostlonggroup->fseat)
> {
> leftmostlonggroup = longlengroups[i];
> }
> }
> printf("%d", leftmostlonggroup->fseat);
>
> return 0;
>
> }
>
> For the bit from the last /****/ to the return 0, how do I put that
> into one loop? I've broken this part into three steps:
>
> 1. Find the longest length
> 2. Find the groups that have this 'longest length'
> 3. Find the group which has the longest length and is the leftmost (ie
> with the lowest fseat)
>
> I don't understand how to pack it into one loop.
> And my tutor said this would work for maybe 80% of possible inputs but
> would go over 1 second to output the other 20%. He said he'd tell me
> how to use data structures when I start school, but what data
> structure should I be using?
I worked out the solution to my question:
int longest_length = 0;
struct group* longest_group;
if (t > 0)
{
for (i = 0; i < ngroups; i++)
{
if (g[i].length > longest_length)
{
longest_length = g[i].length;
longest_group = &g[i];
}
}
}
else
{
longest_group = &g[0];
}
printf("%d", longest_group->fseat);
'You fail to check whether this call succeeded - fopen returns a null
pointer if it cannot open the file. You need to decide what you should
do
in that circumstance, and then add code to carry out that plan if the
file
fails to open. For example, you might prompt the user to give you a
different filename, or you might simply print an error message and
quit.
But you can't just *assume* that the file will be opened successfully,
not
if your goal is to become a good programmer. '
FILE* in = fopen("aflin.txt" , "r");
if (in == NULL) { printf("Error"); return 0; }
Just don't go crazy over its neatness.