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

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

10191 - Longest Nap

Post by chos » Fri Nov 22, 2002 8:26 pm

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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Fri Nov 22, 2002 9:06 pm

[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

Post by chos » Sat Nov 23, 2002 9:33 am

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
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha » Tue Dec 03, 2002 4:43 am

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

Post by yatsen » Tue Dec 03, 2002 9:31 am

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
New poster
Posts: 3
Joined: Wed Nov 20, 2002 10:24 pm

Post by chos » Wed Dec 04, 2002 10:07 pm

Thank you very much!!!!

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

10191 input and Output

Post by Syed Mubashshir Husain » Mon Apr 07, 2003 7:51 am

I got WA. Please give me input and output.

SMH

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Wed Aug 20, 2003 7:15 am

Can appointments overlap?

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

whats wrong with this ?

Post by Shaka_RDR » Mon Dec 29, 2003 8:53 pm

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

Post by Leithian » Sat May 08, 2004 2:37 pm

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
New poster
Posts: 7
Joined: Wed Dec 17, 2003 2:53 pm
Location: Dhaka
Contact:

10191- WA

Post by MD.Morsalin-Al-Saadi » Sun Jun 06, 2004 1:46 pm

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]
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
Location: Bangladesh

INPUT/OUTPUT

Post by Rajib » Tue Jul 13, 2004 9:36 am

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

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

Post by Rajib » Tue Jul 13, 2004 9:53 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. :lol:

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

MD.Morsalin-Al-Saadi
New poster
Posts: 7
Joined: Wed Dec 17, 2003 2:53 pm
Location: Dhaka
Contact:

Post by MD.Morsalin-Al-Saadi » Sun Jul 18, 2004 10:54 am

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

Post by mooseelkdog » Thu Aug 19, 2004 12:57 am

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,
Last edited by mooseelkdog on Sat Aug 21, 2004 7:30 pm, edited 1 time in total.

Post Reply

Return to “Volume 101 (10100-10199)”