10191 - Longest Nap

[chos]

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[0] = linea[0];
tarea->emp[1] = linea[1];
tarea->emp[2] = linea[2];
tarea->emp[3] = linea[3];
tarea->emp[4] = linea[4];
tarea->fin[0] = linea[6];
tarea->fin[1] = linea[7];
tarea->fin[2] = linea[8];
tarea->fin[3] = linea[9];
tarea->fin[4] = linea[10];

2.-
fgets (linea, 256, stdin);
tiempo = 600;
tiempo += (linea[1] - 48) * 60;
tiempo += (linea[3] - 48) * 10;
tiempo += (linea[4] - 48);
horas[j] = tiempo;
j ++;
tiempo = 600;
tiempo += (linea[7] - 48) * 60;
tiempo += (linea[9] - 48) * 10;
tiempo += (linea[10] - 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]

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

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[2000];
char linea[257];
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[1080] = 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]

I have the same problem as chos.
I do not know what is wrong.
Can anyone give me some test data?

[yatsen]

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[2000];
  char linea[257];
  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[1080] = 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]

Thank you very much!!!!

[Syed Mubashshir Husain]

I got WA. Please give me input and output.

SMH

[rjhadley]

Can appointments overlap?

[Shaka_RDR]

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 jadwal,idxjadwal;
int h1,h2,m1,m2,i,j;
long selisih,nap,tnap;
long t1,t2,time;
long t[101][2],temp;
char tugas[300],dummy;
#ifndef ONLINE_JUDGE
freopen ("10191.in","r",stdin);
freopen ("10191.out","w",stdout);
#endif

while (scanf ("%d ",&jadwal)!=EOF)
{
day++;

if (jadwal!=0)
{
tnap=nap=0;
t[0][0]=10*60;
t[0][1]=10*60;
for (idxjadwal=1;idxjadwal<=jadwal;idxjadwal++)
{
scanf ("%d%c%d %d%c%d ",&h1,&dummy,&m1,&h2,&dummy,&m2);
gets (tugas);

t1=60*h1+m1;
t2=60*h2+m2;
t[idxjadwal][0]=t1;
t[idxjadwal][1]=t2;
}

t[jadwal+1][0]=18*60;
t[jadwal+1][1]=18*60;
idxjadwal++;


for (i=0;i<idxjadwal;i++)
{
for (j=idxjadwal-1;j>i;j--)
{
if (t[j-1][0]>t[j][0])
{
temp=t[j-1][0];
t[j-1][0]=t[j][0];
t[j][0]=temp;

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

}
}
}

nap=0;
for (i=1;i<idxjadwal;i++)
{
tnap=t[0]-t[i-1][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][1]/60,t[time][1]%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][1]/60,t[time][1]%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]

[Leithian]

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[0].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]

[MD.Morsalin-Al-Saadi]

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[0] - 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]

[Rajib]

Here is some input/output for you.

INPUT:

4
13:00 15:00 Boring lectures...
15:30 17:45 Reading
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.
15:30 17:15 Reading (I love reading, but should I schedule it?)
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]

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

Your output is:

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

[MD.Morsalin-Al-Saadi]

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]

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

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,