## 10191 - Longest Nap

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...
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!
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
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;

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];

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;
}

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
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!!!
``````

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

### 10191 WA!!

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
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
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;
}
``````
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: