## 10191 - Longest Nap

Moderator: Board moderators

chos
New poster
Posts: 3
Joined: Wed Nov 20, 2002 10:24 pm

### 10191 - Longest Nap

I need help with the problem 10191: Longest Nap.
I can't get the input well. I've tried with:

1.-
fgets (linea, 256, stdin);
tarea = (t_tarea *) malloc (sizeof (t_tarea));
strcpy (tarea->emp, "");
strcpy (tarea->fin, "");
tarea->emp = linea;
tarea->emp = linea;
tarea->emp = linea;
tarea->emp = linea;
tarea->emp = linea;
tarea->fin = linea;
tarea->fin = linea;
tarea->fin = linea;
tarea->fin = linea;
tarea->fin = linea;

2.-
fgets (linea, 256, stdin);
tiempo = 600;
tiempo += (linea - 48) * 60;
tiempo += (linea - 48) * 10;
tiempo += (linea - 48);
horas[j] = tiempo;
j ++;
tiempo = 600;
tiempo += (linea - 48) * 60;
tiempo += (linea - 48) * 10;
tiempo += (linea - 48);
horas[j] = tiempo;
j ++;

3.-
fgets (linea, 256, stdin);
sscanf (linea, "%i%c%i %i%c%i", &hora_e, &aux1, &minuto_e, &hora_f, &aux2, &minuto_f);
tiempo_e = (hora_e * 60) + minuto_e;
tiempo_f = (hora_f * 60) + minuto_f;

4.-
fgets (linea, 256, stdin);
k = 0;
while (linea[k] != ':') k ++;
tiempo_e = 600;
tiempo_e += (linea[k - 1] - '0') * 60;
tiempo_e += (linea[k + 1] - '0') * 10;
tiempo_e += (linea[k + 2] - '0');
tiempo_f = 600;
tiempo_f += (linea[k + 5] - '0') * 60;
tiempo_f += (linea[k + 7] - '0') * 10;
tiempo_f += (linea[k + 8] - '0');

But I can't get it. Apparently, with the cases 2 and 4, i get negatives numbers.

Any help? Thanks.

Also... Can, someone that had accepted the problem, say me how he got the times?
[/c]

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
[c] assert(gets(s) != NULL);
assert(sscanf(s, "%d:%d %d:%d", &h1, &m1, &h2, &m2) == 4);
l1 = h1 * 60 + m1;
l2 = h2 * 60 + m2;[/c]

chos
New poster
Posts: 3
Joined: Wed Nov 20, 2002 10:24 pm
It doesn't work. I still get WA...

Take a view to my code to see if you can find the mistake.

Thanks.

[c]
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

main ()
{
int num_casos;
int horas;
char linea;
char aux1;
char aux2;
int i, j;
int tiempo_e;
int tiempo_f;
int max;
int dia;
int hora;
int hora_e;
int hora_f;
int minuto_e;
int minuto_f;
int ant;
int cont;

dia = 1;
fgets (linea, 256, stdin);
while (!feof (stdin))
{
sscanf (linea, "%i", &num_casos);
if (num_casos == 0)
{
printf ("Day #%i: the longest nap starts at 10:00 and will last for 8 hours and 0 minutes.\n", dia);
}
else
{
for (i = 0; i < 1080; i ++)
{
horas = 0;
}
horas = 1;
for (i = 0; i < num_casos; i ++)
{
fgets (linea, 256, stdin);
sscanf (linea, "%d:%d %d:%d", &hora_e, &minuto_e, &hora_f, &minuto_f);
tiempo_e = (hora_e * 60) + minuto_e;
tiempo_f = (hora_f * 60) + minuto_f;
for (j = tiempo_e; j < tiempo_f; j++)
{
if ((j >= 0) && (j <= 1080)) horas[j] = 1;
}
}
ant = 0;
cont = 0;
max = 0;
hora = 600;
for (i = 600; i <= 1080; i ++)
{
if (ant == 0)
{
if (horas == 1)
{
ant = 1;
if (cont > max)
{
max = cont;
hora = i - cont;
}
}
else
{
cont ++;
}
}
else
{
if (horas == 0)
{
ant = 0;
cont = 1;
}
}
}
printf ("Day #%i: the longest nap starts at %02i:%02i and will last for ", dia, hora / 60, hora % 60);
if (max >= 60)
{
printf ("%i hours and %i minutes.\n", max / 60, max % 60);
}
else
{
printf ("%i minutes.\n", max);
}
}
dia ++;
fgets (linea, 256, stdin);
}
}
[\c][/c]

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan
I have the same problem as chos.
I do not know what is wrong.
Can anyone give me some test data?

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan
To chos:
Maybe the problem is your input. I modify your program and got AC.
Here is the new code:

Code: Select all

``````#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

main ()
{
int num_casos;
int horas;
char linea;
char aux1;
char aux2;
int i, j;
int tiempo_e;
int tiempo_f;
int max;
int dia;
int hora;
int hora_e;
int hora_f;
int minuto_e;
int minuto_f;
int ant;
int cont;

dia = 1;

while (scanf("%d\n",&num_casos)==1)
{
if (num_casos == 0)
{
printf ("Day #%i: the longest nap starts at 10:00 and will last for 8 hours and 0 minutes.\n", dia);
}
else
{
for (i = 0; i < 1080; i ++) horas[i] = 0;
horas = 1;
for (i = 0; i < num_casos; i ++)
{
gets (linea);
sscanf (linea, "%d:%d %d:%d", &hora_e, &minuto_e, &hora_f, &minuto_f);
tiempo_e = (hora_e * 60) + minuto_e;
tiempo_f = (hora_f * 60) + minuto_f;
for (j = tiempo_e; j < tiempo_f; j++)
if ((j >= 0) && (j <= 1080)) horas[j] = 1;
}
ant = 0;
cont = 0;
max = 0;
hora = 600;
for (i = 600; i <= 1080; i ++)
{
if (ant == 0)
{
if (horas[i] == 1)
{
ant = 1;
if (cont > max)
{
max = cont;
hora = i - cont;
}
}
else
cont ++;
}
else
{
if (horas[i] == 0)
{
ant = 0;
cont = 1;
}
}
}
printf ("Day #%i: the longest nap starts at %02i:%02i and will last for ", dia++, hora / 60, hora % 60);
if (max >= 60)
{
printf ("%i hours and %i minutes.\n", max / 60, max % 60);
}
else
{
printf ("%i minutes.\n", max);
}
}
}
}
``````

chos
New poster
Posts: 3
Joined: Wed Nov 20, 2002 10:24 pm
Thank you very much!!!!

Syed Mubashshir Husain
New poster
Posts: 9
Joined: Wed Apr 02, 2003 10:28 am

### 10191 input and Output

I got WA. Please give me input and output.

SMH

Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States
Can appointments overlap?

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Contact:

### whats wrong with this ?

hi all... i need some help here... hope nobody minds helping me.... i got 3 WAs for this problem eventhough lots of people said that this one is easy... here is my code :
[c]#include <stdio.h>
#include <string.h>
#include <math.h>

void main()
{
int day=0;
int h1,h2,m1,m2,i,j;
long selisih,nap,tnap;
long t1,t2,time;
long t,temp;
char tugas,dummy;
#ifndef ONLINE_JUDGE
freopen ("10191.in","r",stdin);
freopen ("10191.out","w",stdout);
#endif

{
day++;

{
tnap=nap=0;
t=10*60;
t=10*60;
{
scanf ("%d%c%d %d%c%d ",&h1,&dummy,&m1,&h2,&dummy,&m2);
gets (tugas);

t1=60*h1+m1;
t2=60*h2+m2;
}

{
{
if (t[j-1]>t[j])
{
temp=t[j-1];
t[j-1]=t[j];
t[j]=temp;

temp=t[j-1];
t[j-1]=t[j];
t[j]=temp;

}
}
}

nap=0;
{
tnap=t-t[i-1];
if (tnap>nap)
{
nap=tnap;
time=i-1;
}
}

if (nap>=60)
{
printf ("Day #%d: the longest nap starts at %2ld:%02ld and will last for %ld hours and %ld minutes.\n",day,t[time]/60,t[time]%60,nap/60,nap%60);
}
else
{
printf ("Day #%d: the longest nap starts at %2ld:%02ld and will last for %ld minutes.\n",day,t[time]/60,t[time]%60,nap%60);
}
}
else
{
printf ("Day #%i: the longest nap starts at 10:00 and will last for 8 hours and 0 minutes.\n", day);
}

}
}
[/c]

btw, MERRY CHRISTMAST 3723o and HAPPY NEW YEAR 07D4h for everybody...... and thanx for the help before....[/c]
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

Leithian
New poster
Posts: 2
Joined: Sat May 08, 2004 2:34 pm

### 10191

Hi there!

I've checked my code for some times now, yet the judge complains about WA. :(
Could someone post a functioning testcase so that I can check whether my output is correct?!
There might be some case I forgot or even a logical error in my code.
Unfortunately I've no idea what's wrong with it. :(

My code:
[cpp]
#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>

using namespace std;

typedef struct {
int time1;
int time2;
} Appointment;

void SwapThis(vector<Appointment>& v, const int i, const int j);
void SelectionSort(vector<Appointment>& v)
{
int i,j,min;
for (i = 0; i < v.size()-1; i++) {
min = i;
for (j = i+1; j < v.size()-1; j++) {
if (v[j].time1 < v[min].time1) {
min = j;
}
if (i != min) SwapThis(v,i,min);
}
}
}

void SwapThis(vector<Appointment>& v, const int i, const int j)
{
Appointment tmp;
tmp.time1 = v[j].time1;
tmp.time2 = v[j].time2;
v[j].time1 = v.time1;
v[j].time2 = v.time2;
v.time1 = tmp.time1;
v.time2 = tmp.time2;
}

Appointment MaxNap(const vector<Appointment> v)
{
Appointment max;
for (int i = 0; i < v.size()-1; i++) {
max.time1 = 10 * 60 + 0;
max.time2 = v.time1;
for (int i = 0; i < v.size()-1; i++) {
if ( (v[i+1].time1 - v.time2) > (max.time2 - max.time1) ) {
max.time1 = v.time2;
max.time2 = v[i+1].time1;
}
}
}
return max;
}

int main(int argc, char* args[])
{
string line;
int cases;
vector<Appointment> appointments;
vector<Appointment> result;
getline(cin,line);
while ((cases = atoi(line.c_str())) != 0) {
Appointment dummy;
// beginning at 10am
dummy.time1 = dummy.time2 = 10 * 60 + 0;
appointments.push_back(dummy);
for (int i = 1;i <= cases;i++) {
Appointment tmp;
getline(cin,line);
// minutes_new = hours*60 + minutes_old :)
tmp.time1 = (atoi(line.substr(0,2).c_str()) * 60) + atoi(line.substr(3,2).c_str());
tmp.time2 = (atoi(line.substr(6,2).c_str()) * 60) + atoi(line.substr(9,2).c_str());
appointments.push_back(tmp);
}
// ending at 18pm
dummy.time1 = dummy.time2 = 18 * 60 + 0;
appointments.push_back(dummy);
// sort the vector by time1
SelectionSort(appointments);
// calculate maximum naptime
result.push_back(MaxNap(appointments));
appointments.clear();
getline(cin,line);
}
for (int i = 0; i <= result.size()-1; i++) {
div_t d1 = div(result.time1,60);
div_t d2 = div(result.time2 - result.time1,60);
string minutes;
minutes = d1.rem;
if (d2.quot > 0) {
if (d1.rem == 0) {
cout << "Day #" << i+1 << ": the longest nap starts at " << d1.quot << ":" << "00" << " and will last for " << d2.quot << " hours and " << d2.rem << " minutes.";
} else {
cout << "Day #" << i+1 << ": the longest nap starts at " << d1.quot << ":" << d1.rem << " and will last for " << d2.quot << " hours and " << d2.rem << " minutes.";
}
} else {
if (d1.rem == 0) {
cout << "Day #" << i+1 << ": the longest nap starts at " << d1.quot << ":" << "00" << " and will last for " << d2.rem << " minutes.";
} else {
cout << "Day #" << i+1 << ": the longest nap starts at " << d1.quot << ":" << d1.rem << " and will last for " << d2.rem << " minutes.";
}
}
cout << endl;
}
cout << endl;
result.clear();
}
[/cpp]

New poster
Posts: 7
Joined: Wed Dec 17, 2003 2:53 pm
Location: Dhaka
Contact:

### 10191- WA

can anybody check my code why i am getting wrong answer? I have checked many inputs but can not find the wrong output.

[c]

#include<stdio.h>
#include<string.h>
#define s 1001

int starting[s]={0},ending[s]={0},count;

void fun_start(int s_h,int s_m,int count)
{
int t;
t = (s_h * 60) + s_m;
starting[count] = t;
}

void fun_end(int e_h,int e_m,int count)
{
int t;
t = (e_h * 60) + e_m;
ending[count] = t;
}

void sor(int count) // sort function
{
int i,j,pos,temp;

pos=count-1;
for(i=0;i<count-1;i++)
{
for(j=0;j<pos-i;j++)
{
if(starting[j+1]<starting[j])
{
temp=starting[j];
starting[j]=starting[j+1];
starting[j+1]=temp;

temp=ending[j];
ending[j]=ending[j+1];
ending[j+1]=temp;
}
}
}
}

int main()
{
int s_h,s_m,e_h,e_m,i,j,count,diff,n,da=0,max,t,h,m,t_h,t_m;
char x[s],colon;

while(1)
{
da++;
if(scanf("%d",&n)==EOF)break;

if(n == 0)
{
printf("Day #%d: the longest nap starts at 10:00 and will last for 8 hours and 0 minutes.\n",da);

}

else
{
count = 0;
for(i=0;i<n;i++)
{
scanf("%d%c%d",&s_h,&colon,&s_m);
fun_start(s_h,s_m,count);
scanf("%d%c%d",&e_h,&colon,&e_m);
fun_end(e_h,e_m,count);
getchar();
gets(x);
count++;
}
sor(count);

max = starting - 600;
t = 600;

for(i=0;i<count-1;i++)
{
diff = (starting[i+1] - ending );
if(max < diff)
{
max = diff;
t = ending;
}
}

diff = (1080 - ending[count-1]);
if(max < diff )
{
max = diff; //total nap time
t = ending[count-1]; //napping starts
}

h = max / 60;
m = max % 60;

t_h = t/60;
t_m = t%60;

if(max <60)
printf("Day #%d: the longest nap starts at %d:%02d and will last for %d minutes.\n",da,t_h,t_m,max);
else
printf("Day #%d: the longest nap starts at %d:%02d and will last for %d hours and %d minutes.\n",da,t_h,t_m,h,m);
//printf("\n");
}
}
return 0;
}
[/c]
Last edited by MD.Morsalin-Al-Saadi on Sun Jul 18, 2004 10:56 am, edited 1 time in total.

Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am

### INPUT/OUTPUT

Here is some input/output for you.

INPUT:
4
13:00 15:00 Boring lectures...
10:00 12:00 Lectures
12:00 13:00 Lunch, like always.
4
10:00 12:00 Lectures
13:00 15:00 Lectures, lectures... oh, no!
16:45 17:45 Reading (to be or not to be?)
12:00 13:00 Lunch, just lunch.
4
12:00 13:00 Lunch, again!!!
10:00 12:00 Lectures, as everyday.
13:00 15:00 Lectures, more lectures!
1
12:00 13:00 I love lunch! Have you ever noticed it?
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 13:00 and will last for 5 hours and 0 minutes.
All the time you should be careful about the problem description... Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
I check your code and it seems everything ok but it can not handle the input like following. Fix it and it may give you Accepted. INPUT:
0
Day #1: the longest nap starts at 0:00 and will last for 18 hours and 0 minutes.
Output should be:
Day #1: the longest nap starts at 10:00 and will last for 8 hours and 0 minutes.
At first you should check all possible inputs and then ask for help... New poster
Posts: 7
Joined: Wed Dec 17, 2003 2:53 pm
Location: Dhaka
Contact:
Rajib,
I checked for input 0 and still getting wrong answer. Do you have any suggesion or any other input I did not consider. New code has been given in my first mail (after editing).

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

### 10191 - Time Limit Exceeded

What does this mean?
You CAN'T assume, however, that the input will be in any specific order.
I assume it means that possibly the times are not necessarily sequential, but, I have the following 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 hour and 0 minutes.
from 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.
I'd post my code but I am sure there is only something wrong with unsorted times on my program. I guess maybe a little reinforcement on this idea might help me decide if that is what it really is (because I have no problem with time or runtime on my computer with this problem, with the input set up on my file, with sequential times)

Thanks in advance for any input at all,
Last edited by mooseelkdog on Sat Aug 21, 2004 7:30 pm, edited 1 time in total.