10191 - Longest Nap

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mooseelkdog
New poster
Posts: 18
Joined: Fri Oct 10, 2003 8:46 am
Location: Airway Heights

OK....sorting yet still TLE

I am sorting my times using shell sort and I can get my simple test cases to work, can anyone send or post or tell me of cases which would send my algorithm into a tizzy? Any input is greatly appreciated, thanks
Last edited by mooseelkdog on Sat Aug 21, 2004 7:31 pm, edited 1 time in total.

mooseelkdog
New poster
Posts: 18
Joined: Fri Oct 10, 2003 8:46 am
Location: Airway Heights

In C++, now WA

I have good output, I believe, having rewritten this in C++, here is the output:
Day #1: the longest nap starts at 15:00 and will last for 30 minutes.
Day #2: the longest nap starts at 15:00 and will last for 1 hours and 45 minutes.
Day #3: the longest nap starts at 17:15 and will last for 45 minutes.
Day #4: the longest nap starts at 10:00 and will last for 8 hours and 0 minutes.
Day #5: the longest nap starts at 13:00 and will last for 5 hours and 0 minutes.
Day #6: the longest nap starts at 10:00 and will last for 2 hours and 0 minutes.
Day #7: the longest nap starts at 10:00 and will last for 1 hours and 0 minutes.
Day #8: the longest nap starts at 14:59 and will last for 1 hours and 1 minutes.
For the following input:
4
10:00 12:00 Lectures
12:00 13:00 Lunch, like always.
13:00 15:00 Boring lectures...
15:30 17:45 Reading
4
10:00 12:00 Lectures
12:00 13:00 Lunch, just lunch.
13:00 15:00 Lectures, lectures... oh, no!
16:45 17:45 Reading (to be or not to be?)
4
10:00 12:00 Lectures, as everyday.
12:00 13:00 Lunch, again!!!
13:00 15:00 Lectures, more lectures!
15:30 17:15 Reading (I love reading, but should I schedule it?)
0
1
12:00 13:00 I love lunch! Have you ever noticed it?
3
12:00 13:00 Huh? I just wondered!
13:35 14:05 Lecture just a little.
14:30 16:30 Last lecture, go home.
5
11:00 11:45 Talking, blah, blah, blah.
12:30 13:30 Blah, double blah.
14:30 15:30 Hmmmmmmmmmmmmmmmmmmmm.
16:30 17:30 OKKKKKKKKKKKKKKKKKKKK.
17:30 18:00 Er, done.
6
16:00 16:20 Making whoopee
10:00 10:35 Coffee time
12:20 12:59 Breaking bread
16:20 18:00 Last Lecture
13:45 14:59 Lecture History
10:35 12:10 Lectue Weasel
but now I get wrong answer, I just don't see how the code is wrong......The output file stuff I used to get the output I quoted earlier, I didn't submit the code with it, and if I did I would comment out the #define, anyway If somebody could please tell me how this can possibly be giving any wrong answer....PLEASE.....this is driving me nuts
Last edited by mooseelkdog on Sat Aug 21, 2004 7:32 pm, edited 1 time in total.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Well your code is far too long

I remember my code was much shorter than this. Long codes are more prone to error. Try to generalize your algorithm instead of using too many if..else.

Good Luck.

mooseelkdog
New poster
Posts: 18
Joined: Fri Oct 10, 2003 8:46 am
Location: Airway Heights
Thanks, Will try something else.

johnrz86
New poster
Posts: 3
Joined: Tue Nov 02, 2004 7:29 pm

10191

Hey all,

Could someone please provide some sample input/output for 10191 (Longest Nap)? It seems like such a simple problem but I keep getting WA, and it's driving me up the wall!!!

Here is my code...
[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
int start;
int end;
} task;

task t[105];

int taskCompare(task *a, task *b) {
if (a->start < b->start) return -1;
if (a->start > b->start) return 1;
return 0;
}

int main() {
int n, i, max, start, day=1;
char s_hr, s_min, e_hr, e_min, line[300];
int taskCompare();

while (scanf("%d", &n) != EOF) {
for (i=0; i<n; i++) {
scanf("%d:%d %d:%d ", &s_hr, &s_min, &e_hr, &e_min);
gets(line);

t.start = s_hr * 60 + s_min;
t.end = e_hr * 60 + e_min;
}

if (n) qsort(t, n, sizeof(task), taskCompare);

max = 0;
start = 600;

if (n) {
if (t[0].start - 600 > max) {
max = t[0].start - 600;
start = 600;
}
for (i=0; i<n-1; i++) {
if (t[i+1].start - t.end > max) {
max = t[i+1].start - t.end;
start = t.end;
}
}
if (18*60 - t[n-1].end > max) {
max = 18*60-t[n-1].end;
start = t[n-1].end;
}
} else {
start = 600;
max = 18*60 - 600;
}

printf("Day #%d: the longest nap starts at %d:", day, start/60);
if (start % 60 < 10)
printf("0%d", start % 60);
else
printf("%d", start % 60);
printf(" and will last for ");
if (max / 60)
printf("%d hours and %d minutes.\n", max/60, max%60);
else
printf("%d minutes.\n", max);

day++;
}

return 0;
}
[/c]

Any suggestions would be appreciated. Thanks.

John

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh
I don't know why this kind of solution of this problem always gets WA
After getting lots of WA by this way I change my code and solve it by array Flagging

johnrz86
New poster
Posts: 3
Joined: Tue Nov 02, 2004 7:29 pm

I tried that too...

I tried to solve it that way too. But for some reason, my code still wouldn't work. I've tried every test case I can think of without noticing anything wrong.

[c]
#include <stdio.h>
#include <string.h>

int main() {
int i, n, sh, sm, eh, em, start, flag, count, max, day=1;
int schedule[1100];
char line[300];

while (scanf("%d", &n) != EOF) {
memset(schedule, 0, 1100*sizeof(int));

while (n--) {
scanf("%d:%d %d:%d ", &sh, &sm, &eh, &em);
gets(line);

for (i=(sh*60+sm); i<(eh*60+em); i++)
if ((i >= 600) && (i <= 1080)) schedule = 1;
}

flag = 0;
start = 600;
count = 0;
max = 0;

schedule[1080] = 1;
for (i=600; i<=1080; i++) {
if (flag == 0) {
if (schedule) {
flag = 1;
if (count > max) {
max = count;
start = i - count;
}
} else
count++;
} else {
if (!schedule) {
flag = 0;
count = 1;
}
}
}

printf("Day #%d: the longest nap starts at %02d:%02d and will last for ", day, start/60, start%60);
if (max / 60) printf("%d hours and ", max/60);
printf("%d minutes.\n", max % 60);

day++;
}

return 0;
}
[/c]

I'd appreciate any pointers. Thanks in advance.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
To johnrz86:

The only difference between the output of your program and my program occurred when there's an "empty" appointment (just spaces):

Sample:

Code: Select all

``````3
10:00 10:01 Lectures, as everyday.
12:00 12:59
17:59 18:00 Lunch, again!!!
``````
Your output:

Code: Select all

``````Day #1: the longest nap starts at 12:59 and will last for 5 hours and 1 minutes.
``````
My output:

Code: Select all

``````Day #1: the longest nap starts at 12:59 and will last for 5 hours and 0 minutes.
``````

johnrz86
New poster
Posts: 3
Joined: Tue Nov 02, 2004 7:29 pm
Ah, thank you!

John

rashed_mondol
New poster
Posts: 2
Joined: Wed Nov 10, 2004 8:26 am
Location: Bangladesh

10191 WA!!

I submitted my code and get WA.Please help me

My code :

#include<stdio.h>
#include<string.h>
int time(char x[10]);
void display(char x[10],int max,int n);
void main()
{
char x[10],y[10],rec[10],fc[10],l[1000];
int j,tem,f1,f2,n,i,max,k,len;
j=1;
while(scanf("%d",&n)!=EOF)
{
f1=600;
strcpy(fc,"10:00");
max=0;
for(i=0;i<n;i++)
{
scanf("%s%s",x,y); gets(l);
f2=time(x);
tem=time(y);
k=f2-f1;
if(max<k) { max=k;strcpy(rec,fc);}
f1=tem;
strcpy(fc,y);
}
k=1080-f1;if(max<k) {max=k;strcpy(rec,fc); }
display(rec,max,j);
j++;
}
}
void display(char x[10],int max,int n)
{
int min,hour;
hour=max/60;
min=max%60;
if(hour==0) printf("Day #%d: the longest nap starts at %s and will last for %d minutes.\n",n,x,min);
else printf("Day #%d: the longest nap starts at %s and will last for %d hours and %d minutes.\n",n,x,hour,min);
}
int time(char x[10])
{
int value;
value=0;
value=(x[0]-48 ) * 10;
value=value+(x[1]-48 );
value=value * 60;
value=value+(x[3]-48 )* 10;
value=value+(x[4]-48 );
return value;
}
Acm Boss

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

Re: 10191 WA!!

I suggested u that try alaways for not giveing code.
There is no time for checking ur code.But I just gave an sample input
and try it.Hope it will help u.
========================================
Sample Input:

2
12:00 18:00 Reading
10:00 11:00 Lectures

Sample output:
Day #1: the longest nap starts at 11:00 and will last for 1 hours and 0 minutes.

Valo Vai Valo.Ki bujlen.
Mr. Arithmetic logic Unit

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Compile Error 10191

Hi !! I change from C to C++ and I get Compile Error Please Help me,I have Fedora 3 and g++ 3.4.2 I wish to know What are the flags for Compile under Linux

Code: Select all

``````#include <iostream>
#include <vector>
#include <cstdio>
#include <utility>
#define MAX(a,b) ((a>b)?(a):(b))

using namespace std;

int main(){
int h1,h2,h3,h4,n,i;
char A[260];
vector < pair<int,int> > v;
int casos=1;
while(scanf("%d",&n)==1){
v.clear();
for(i=0;i<n;i++){
scanf("%d:%d %d:%d %[^\n]",&h1,&h2,&h3,&h4,A);
pair<int,int> hora;
hora.first = h1*60+h2;
hora.second = h3*60+h4;
v.push_back(hora);
}
sort(v.begin(),v.end());

int max=0;
int begin=10*60;
for(i=0;i<n;i++){

int aux=(i+1!=n)?(v[i+1].first - v[i].second):(18*60 - v[i].second);

if(max<aux){
max = aux;
begin = v[i].second;
}
}
int Horas = begin/60;
int HorasDiff = max/60;
int Min = begin%60;
int MinDiff = max%60;
printf("Day #%d the longest nap starts at %d:%s%d",casos++,Horas,(Min<10)?"0":"",Min);
if(HorasDiff == 0)
printf(" and will last for %d minutes.\n",MinDiff);
else
printf(" and will last for %d hours and %d minutes.\n",HorasDiff,MinDiff);
}
return 0;
}
``````
Thanks In Advance
Keep posting !!

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
I am not sure, still that iostream and cstdio might be a reason.And why are
you declaring the namespace std if you are not using it ?

Regards,
Suman.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Submit via www interface to receive the exact compile report on your email address: http://acm.uva.es/problemset/submit.php. But first try to include algorithm - you use sort which might be undefined.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
Yes, I think Krzysztof is right, that's the only problem I see, too.

Sumankar: I really don't understand what you are talking about. Both your points are wrong.

There is nothing wrong with including both <cstdio> and <iostream>, in fact I do it always (as I have it in my template file). This way I can choose whether to use the more convenient cin+cout, or the more powerful scanf+printf. The libraries <cstdio> and <iostream> do NOT collide in any way.

Moreover, he IS using the namespace std!

All the symbols in all the libraries in STL (and also in cstdio) are declared in the std namespace. Without the "using namespace std;" line you would have to write things like "std::vector< int >".