AFL (Australian Football League)
Bert
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?
Bert
spam?
Sjouke Burry
> Guys this isn't spam. Are you not replying because you think this is
> spam?
and it is not in your computer.
Richard Heathfield
> Here's my problem:
>
<spec snipped>
>
> 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");
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.
<snip>
If you're thinking "but he didn't answer my question!", you're probably
right - I probably didn't. But for all I know, your failure to check that
the file opened successfully *might* be the solution to your problem.
I hope that you will become a great programmer some day, and the way in
which I answer your questions is, believe it or not, designed to help you
achieve that. I suppose you will be annoyed by my point about fopen, and I
can't help that. What I'm hoping is that you'll say, "okay, fine, if
that's the way that pedantic SOB wants to play it, I'll give him a program
that checks the darn value and takes appropriate action if it's NULL -
then he won't have that excuse in future". And then we'll move on to the
next thing you're not doing right... and eventually you'll get this stuff
right without even thinking about it. And at that point, whether or not
you continue to do these little programming contest things, you'll be well
on the way to becoming a Real Programmer(tm).
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Ben Bacarisse
> AFL
>
> Input File: aflin.txt
> Output File: aflout.txt
> Time Limit: 1 second
>
> 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.
<snip>
> 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%.
Do you have an example of a "slow" data set. Obviously I can make my
own, but such puzzles often come with data sets. I have a simple
solution and I like to see if really is as bad as your tutor
suggests. Also I would not mind some more test data...
> He said he'd tell me
> how to use data structures when I start school, but what data
> structure should I be using?
You may not need any fancy structures. How slow is your program? If
speed is needed one suitable data structure for this problem would be
a heap. In particular look up how to implement a heap in an array.
--
Ben.
Bert
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.
Bert
> You may not need any fancy structures. How slow is your program?
It's got one second to finish and have the output in the output file.
Richard Heathfield
> On Jul 11, 9:07 am, Bert <albert.xtheunkno...@gmail.com> wrote:
<snip>
>> FILE* in = fopen("aflin.txt" , "r");
<snip>
>
> '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.
Your next line is:
FILE* out = fopen("alfout.txt", "w");
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.
Moving on... you read from your input file as follows:
fscanf(in, "%d", &nseats );
but you don't check whether this call succeeded. The fscanf function yields
a result that is either EOF (if an input error occurs before any
conversion) or 0 (if, say, the input doesn't make sense to fscanf in the
light of the format specifier, e.g. SIX instead of 6), or the number of
fields successfully converted. In your case, you want one field to be
converted, so you want fscanf to return 1. Your code should check that it
does, and you should decide what to do in the event that it doesn't. Many
learners decide simply to abort the program at this point. That's
acceptable while you're learning, but a more robust response would involve
explaining the problem to the user and offering another chance to provide
good input.
You have just provided some evidence that you are prepared to respond to
advice, which is why I've provided two tips this time rather than just
one. If you fix up your code again, next time I'll give you three. If you
don't want all three of them to be "check the result of /this/ fscanf
call", you can avoid that by adding code to check the results of all of
the fscanf calls, not just the one I mentioned above, before posting again
- this will save you a fair bit of time.
Bert
> Your code should check that it
> does, and you should decide what to do in the event that it doesn't. Many
> learners decide simply to abort the program at this point. That's
> acceptable while you're learning, but a more robust response would involve
> explaining the problem to the user and offering another chance to provide
> good input.
Nah, programming comps don't need crap.
> You have just provided some evidence that you are prepared to respond to
> advice, which is why I've provided two tips this time rather than just
> one. If you fix up your code again, next time I'll give you three. If you
> don't want all three of them to be "check the result of /this/ fscanf
> call", you can avoid that by adding code to check the results of all of
> the fscanf calls, not just the one I mentioned above, before posting again
> - this will save you a fair bit of time.
-Little child to mummy-'I feel so special, mother'
[SIGH] - I found myself copying and pasting your name instead of
typing it out. You need to truncate your name.
FILE* in = fopen("aflin.txt" , "r");
if (in == NULL) { printf("Error"); return 0; }
FILE* out = fopen("alfout.txt", "w");
if (in == NULL) { printf("Error"); return 0; }
int nseats, t, b;
int richard_heathfield = fscanf(in, "%d", &nseats );
if (richard_heathfield != 1) { printf("Error"); return 0; }
richard_heathfield = fscanf(in, "%d", &t );
if (richard_heathfield != 1) { printf("Error"); return 0; }
int booked[t];
int i = 0;
for (; i < t; i++)
{
richard_heathfield = fscanf(in, "%d", &booked[i]);
if (richard_heathfield != 1) { printf("Error"); return 0; }
}
richard_heathfield = fscanf(in, "%d", &b);
if (richard_heathfield != 1) { printf("Error"); return 0; }
int bookings[nseats];
for (i = 0; i < b; i++)
{
richard_heathfield = fscanf(in, "%d", &bookings[i]);
if (richard_heathfield != 1) { printf("Error"); return 0; }
}
Richard Heathfield
> On Jul 13, 6:38 pm, Richard Heathfield <r...@see.sig.invalid> wrote:
>> Your code should check that it
>> does, and you should decide what to do in the event that it doesn't.
>> Many learners decide simply to abort the program at this point. That's
>> acceptable while you're learning, but a more robust response would
>> involve explaining the problem to the user and offering another chance
>> to provide good input.
>
> Nah, programming comps don't need crap.
And yet you seem determined to supply it. Fair enough.
<snip>
Ben Bacarisse
> On Jul 13, 6:38 pm, Richard Heathfield <r...@see.sig.invalid> wrote:
>> Your code should check that it
>> does, and you should decide what to do in the event that it doesn't. Many
>> learners decide simply to abort the program at this point. That's
>> acceptable while you're learning, but a more robust response would involve
>> explaining the problem to the user and offering another chance to provide
>> good input.
>
> Nah, programming comps don't need crap.
I want my program to check that my test input is OK even if the
customer never cares.
> [SIGH] - I found myself copying and pasting your name instead of
> typing it out. You need to truncate your name.
> int nseats, t, b;
>
> int richard_heathfield = fscanf(in, "%d", &nseats );
> if (richard_heathfield != 1) { printf("Error"); return 0; }
>
> richard_heathfield = fscanf(in, "%d", &t );
> if (richard_heathfield != 1) { printf("Error"); return 0; }
>
> int booked[t];
> int i = 0;
> for (; i < t; i++)
> {
> richard_heathfield = fscanf(in, "%d", &booked[i]);
> if (richard_heathfield != 1) { printf("Error"); return 0; }
> }
>
> richard_heathfield = fscanf(in, "%d", &b);
> if (richard_heathfield != 1) { printf("Error"); return 0; }
> int bookings[nseats];
>
> for (i = 0; i < b; i++)
> {
> richard_heathfield = fscanf(in, "%d", &bookings[i]);
> if (richard_heathfield != 1) { printf("Error"); return 0; }
> }
Good programmers never choose to repeat code like this. There is an
obvious candidate for a function here. In fact my solution to this
problem includes:
int read_num(FILE *fp)
{
static unsigned long line = 0;
int n;
line += 1;
char first[2];
if (fscanf(fp, "%1[0-9+-]", first) != 1 ||
ungetc(first[0], fp) == EOF ||
fscanf(fp, "%d\n", &n) != 1) {
fprintf(stderr, "Input error on line %lu.\n", line);
exit(EXIT_FAILURE);
}
return n;
}
I was prepared to discuss methods and compare code, but you seem to
have gone of the rails with sarcasm.
--
Ben.
CBFalconer
>
... snip ...
>
> -Little child to mummy-'I feel so special, mother'
>
> [SIGH] - I found myself copying and pasting your name instead of
> typing it out. You need to truncate your name.
>
> FILE* in = fopen("aflin.txt" , "r");
> if (in == NULL) { printf("Error"); return 0; }
> FILE* out = fopen("alfout.txt", "w");
> if (in == NULL) { printf("Error"); return 0; }
>
> int nseats, t, b;
>
> int richard_heathfield = fscanf(in, "%d", &nseats );
> if (richard_heathfield != 1) { printf("Error"); return 0; }
Congratulations. You have achieved my PLONK file. Bye.
--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
Nick Keighley
> Guys this isn't spam. Are you not replying because you think this is
> spam?
although you ask questions you don't seem to like advice.
But anyway here's mine:
- don't put your whole program in main(). Use subroutines.
As a rule of thumb a function should fit on a page (or
a screen if you prefer)
--
Nick Keighley
You are in a clearing. You can see a spire in the distance.
You can also see a copy of "C Unleashed".
: INV
You have;
a DeathStation 900 laptop,
a voucher for a free pizza,
and a torch.
: TAKE BOOK
You can't. It's too heavy.
Bill Godfrey (clc)
Keith Thompson
[...]
> You may not need any fancy structures. How slow is your program? If
> speed is needed one suitable data structure for this problem would be
> a heap. In particular look up how to implement a heap in an array.
Note that the word "heap" is used in two different ways. The more
common meaning is that "the heap" is the region of memory managed by
malloc() and free(); that's not what Ben is referring to.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Keith Thompson
That doesn't answer the question. It tells us how fast the program
needs to be; the question was how fast (or slow) it *is*.
Bert
with it? I really can't do it.
santosh
> Can someone please tell me the pseudocode for this and how the came up
> with it? I really can't do it.
<snip>
Basically you should maintain two lists, one for booked seats and the
other free ones. For each request scan the free list for the largest
sized block greater than the request itself, deduct the appropriate
amount and add it to the booked list and update the free list.
Reading and writing the files should be pretty straightforward. Just
code to the specifications given.
vipp...@gmail.com
> Can someone please tell me the pseudocode for this and how the came up
> with it? I really can't do it.
<snip top post>
Please don't top-post.
<http://www.catb.org/jargon/html/T/top-post.html>
<http://www.caliburn.nl/topposting.html>
Ben Bacarisse
> Can someone please tell me the pseudocode for this and how the came up
> with it? I really can't do it.
>
> Bert wrote:
>> Here's my problem:
<snip>
Questions about algorithms and methods are better in
comp.programming. If you post there, include a link to the problem
specification if possible.
<almost all the rest is off-topic:>
I did this with a single list representing consecutive runs of free
seats. As you read the input you need to be able to marks seats as
taken. This, in effect, turns your initial one-element list into two
then three and so on (there are a few things you can do to tidy this
up). During this phase you want the list in seat-number order so you
can find the block containing seat number X. It is simple to keep it
in this order.
Later, when you are making bookings, you need the list in size order
since you are instructed to take from the longest run. I did this
with a sort. Then, after each booking, the remaining block gets put
back in the right place, keeping the size order. Because I had the
sorting written (a compare function and a call to qsort) I just used
that after each booking. I knew this would be slow, but it might be
fast enough. Later, I changed to inserting the new block in the right
place. I started with an array, since the problem specifier was kind
enough to provide an upper limit on the number of seats. Since an
array was fast enough, I left it at that.
The key is a good data structure -- one that makes the things you need
to do with it simple. You also need to get into the habit of writing
more functions. A central part of programming is identifying the
sub-parts of a problem so they can be written separately and
combined. Very early on I had an outline with a nebulous data
structure and "mark_seat_as_taken" and "make_booking" functions.
--
Ben.
Stephen Sprunk
> 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.
Ignoring any actual coding questions here, the algorithm is seriously
broken. For any request to buy K seats, you want to find the _shortest_
run of available seats that still meets the request. If there is no
matching run, the allocation must fail (or be divided into two requests
and recurse), rather than potentially double-booking seats.
Otherwise, you will sell a run of 10 seats to 10 people wanting 1 seat
each, then find yourself unable to fulfill an order for a 10-seat block
-- or worse, finding only single seats available and then double-booking
the next 9 seats.
I'd normally ignore that point, but this actually has implications for
more topical situations, like a memory allocator trying to decide which
of several available blocks would best meet a request.
S
31349 83652
> Ignoring any actual coding questions here, the algorithm is seriously
> broken. For any request to buy K seats, you want to find the _shortest_
What you seem to have missed is that the original problem is
not a "real-life" problem :)