10191 - Longest Nap

[mooseelkdog]

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

[mooseelkdog]

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

[shamim]

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]

Thanks, Will try something else.

[johnrz86]

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]

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]

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]

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]

Ah, thank you!

John

[rashed_mondol]

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

[TISARKER]

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.

[Ghust_omega]

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]

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]

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]

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 >".