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

mad
New poster
Posts: 3
Joined: Sun Jun 24, 2007 11:51 pm

Post by mad » Thu Jul 05, 2007 11:41 pm

I tryed a lot but I didn 't find where is the mistake in my code. Could someone help me? I'm receiving WA. Thank you in advance.

Code: Select all

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int
intcmp (const void *, const void *);

int
main() 
{
    int time1;
    int time2;
    int i;
    int j;
    int quanttimes;
    int quantcases;
    int nday = 1;
    int diff;
    int biggdifference;
    int napbegin;
    int vethours[200];
    char auxt1[10];
    char auxt2[10];
    char temp[4000];
    
    while ((scanf ("%d\n", &quantcases)) != EOF)
      {  
        quanttimes = 0;
        //reading the times
        for (i = 0; i < quantcases; i++)
          {        
            gets (temp);
            //getting the times
            sscanf (temp, "%s %s", auxt1, auxt2);
           
           
                time1 = ((auxt1[0] - 48) * 10 + (auxt1[1] - 48)) * 60 + ((auxt1[3] - 48) * 10 + (auxt1[4] - 48));
                vethours[quanttimes++] = time1;
	     
                time2 = ((auxt2[0] - 48) * 10 + (auxt2[1] - 48)) * 60 + ((auxt2[3] - 48) * 10 + (auxt2[4] -48));
                vethours[quanttimes++] = time2;
          }

         qsort (vethours,quanttimes,sizeof (int),intcmp);
         
         napbegin = 1080;
          
         //special cases (10:00 and/or 18:00)
         biggdifference = vethours[0] - 600; 
         if ((1080 - vethours[quanttimes - 1]) > biggdifference)
           biggdifference = 1080 - vethours[quanttimes - 1];
         
         //finding the big nap
         for (i = 1; i < (quanttimes - 1); i += 2)        
           if ((diff = (vethours[i + 1] - vethours[i])) > biggdifference) 
             biggdifference = diff;
               
        //finding if there are more than one big nap (picking the earliest)
        for (i = 1, j = 0; i < (quanttimes - 1); i += 2)        
           if ((diff = (vethours[i + 1] - vethours[i])) == biggdifference) 
             if (vethours[i] < napbegin)
               napbegin = vethours[i]; 
        
        //special cases
        if (biggdifference == (vethours[0] - 600))
          {
            if (vethours[0] < napbegin) 
              napbegin = vethours[0];                                   
          }    
        
        else if (biggdifference == (1080 - vethours[quanttimes - 1]))
          if (vethours[quanttimes - 1] < napbegin) 
            napbegin = vethours[quanttimes - 1];                
       
        if (biggdifference < 60)
          printf ("Day #%d: the longest nap starts at %2d:%02d and will last for %d minutes.\n", nday, (napbegin / 60), (napbegin % 60), biggdifference); 
        else
         {
           printf ("Day #%d: the longest nap starts at %2d:%02d and will last for %d hours and %d minutes.\n", nday, (napbegin / 60), (napbegin % 60), (biggdifference / 60), (biggdifference % 60));
         }
        
        nday++;
      } 
    return (0);
}

//compare two numbers (integers)
int
intcmp (const void *n1, const void *n2)
{
  int *a1;
  int *a2;

  a1 = (int *) n1;
  a2 = (int *) n2;

  if (*a1 > *a2)
    return 1;
  
  if (*a1 < *a2)
    return -1;
  
  return 0;
} 

amr saqr
New poster
Posts: 29
Joined: Tue Mar 11, 2008 6:35 pm

Re: 10191 - Longest Nap

Post by amr saqr » Sun Jun 01, 2008 4:25 pm

here is my code, i've got so many wrong answers in this simple problem :S

Code: Select all

Removed after AC :D
Last edited by amr saqr on Mon Jun 09, 2008 9:39 am, edited 1 time in total.
C++ Is The Best.

amr saqr
New poster
Posts: 29
Joined: Tue Mar 11, 2008 6:35 pm

Re: 10191

Post by amr saqr » Mon Jun 09, 2008 9:35 am

zaman wrote:I've tested the inputs in the forum. But still getting wrong answer.Please suggest any sample input that doesn't pass it
i tried ur code with some cases and got this

1
10:00 18:00
Day #1: the longest nap starts at -14316557:0-40 and will last for 0 minutes.
1

10:01 10:06
Day #2: the longest nap starts at 10:06 and will last for 7 hours and 54 minutes
.1

10:00 18:00
Day #3: the longest nap starts at 10:06 and will last for 0 minutes.

and also u must print the new line char after each output '\n'
hope i helped u
C++ Is The Best.

amr saqr
New poster
Posts: 29
Joined: Tue Mar 11, 2008 6:35 pm

Re: What's the Longest nap?

Post by amr saqr » Mon Jun 09, 2008 9:39 am

mhayter1 wrote:Can someone please help me. This problem is supposed to be easy, but I'm having a very tough time with it. My output seem right. Can someone point out the error in my code or give my inputs to break it. Thank you!
try this input
1
10:01 10:06

my output:

Code: Select all

Day #1: the longest nap starts at 10:06 and will last for 7 hours and 54 minutes.
your output:

Code: Select all

Day #1: the longest nap starts at 10:6 and will last for 7 hours and 54 minutes.
hope i helped u
C++ Is The Best.

amr saqr
New poster
Posts: 29
Joined: Tue Mar 11, 2008 6:35 pm

Re:

Post by amr saqr » Mon Jun 09, 2008 9:51 am

mad wrote:I tryed a lot but I didn 't find where is the mistake in my code. Could someone help me? I'm receiving WA. Thank you in advance.
try this input
5
10:30 11:30
12:00 13:00
13:30 14:30
15:00 16:00
16:30 17:30

my output:

Code: Select all

Day #1: the longest nap starts at 10:00 and will last for 30 minutes.
your output:

Code: Select all

Day #1: the longest nap starts at 10:30 and will last for 30 minutes.
the nap always starts from 10:00 or the ending time of any appointment
obviously, u must check your code again
hope i helped u
C++ Is The Best.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10191 - Longest Nap

Post by Obaida » Fri Jul 03, 2009 12:53 pm

At last i got acc... :D
For every one who got several wa like me...
You need to sort the input according to beginning or ending time..
Then go for the max gap..
and don't forget to take care about the gap of very beginning and end.
8)
try_try_try_try_&&&_try@try.com
This may be the address of success.

buiutripa
New poster
Posts: 6
Joined: Wed Oct 21, 2009 1:44 am

Re: 10191 - Longest Nap

Post by buiutripa » Mon Dec 14, 2009 3:19 am

What's are wrong in my code? http://pastebin.com/m6ef06f5c
I tested all input/output of this topic and don't has difference between my and yours.
I tested many especial cases, but my code output correctly, anyone give a input with my code not make the correct output?

Thankz in advance :)

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct {
int ini, fim;
} intervalo;

char tarefa[200];
int s, h1, h2;
intervalo atual;
vector<intervalo> v;

string formata(int hora) {
char str[20];
int h = hora/60;
int m = hora-(h*60);

sprintf(str, "%02d:%02d", h, m);
return str;
}

string formata2(int hora) {
char ho[100], mi[100];
int h = hora/60;
int m = hora-(h*60);

ho[0] = '\0';
if (h != 0) {
sprintf(ho, "%d hours and ", h);
}

sprintf(mi, "%d minutes.", m);

string saida(ho);
saida += mi;

return saida;
}

bool ordena(const intervalo &i1, const intervalo &i2) {
return i1.ini < i2.ini;
}

int main() {
int caso = 1;
while (scanf("%d", &s) == 1) {

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

for (int i = 0; i < s; i++) {
int h1, h2;

scanf("%d:%d", &h1, &h2);
atual.ini = h1*60+h2;

scanf("%d:%d", &h1, &h2);
atual.fim = h1*60+h2;

v.push_back(atual);

fgets(tarefa, 190, stdin);

}

sort(v.begin(), v.end(), ordena);

int inicio = 0;
int maior = 0;

if (v.front().ini > 10*60) {
inicio = 10*60;
maior = v.front().ini - inicio;
}

int diff = (18*60 - v.back().fim);
if (v.back().fim < 18*60 && diff > maior) {
inicio = v.back().fim;
maior = diff;
}

for (vector<intervalo>::iterator it = v.begin(); (it+1) != v.end(); it++) {
int diff = (it+1)->ini - it->fim;
if (diff > maior) {
maior = diff;
inicio = it->fim;
}
}

printf("Day #%d: the longest nap starts at %s and will last for %s\n",
caso++, formata(inicio).c_str(), formata2(maior).c_str());

v.clear();
}

return 0;
}

Mizanur Rahman(IUK)
New poster
Posts: 12
Joined: Wed Aug 18, 2010 12:07 pm

Re: 10191 - Longest Nap

Post by Mizanur Rahman(IUK) » Wed Aug 18, 2010 1:42 pm

Why wa??? Please help me

Code: Select all

#include<stdio.h>
struct f
{
int h1,m1,h2,m2;
}st[100],tmp;

int main()
{
	char c,a[260];
	int naph,napm,i,kh,km,n,sh,sm,eh,em,tm1,tm2,j=1;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
		 scanf("%d%c%d%d%c%d%[^\n]",&st[i].h1,&c,&st[i].m1,&st[i].h2,&c,&st[i].m2,a);
	       //	 for(i=0;i<n;i++)
		 //	printf("h1 %d m1 %d h2 %d m2 %d\n",st[i].h1,st[i].m1,st[i].h2,st[i].m2);
		 if(n==0)
		 {
		 tm1=8*60;
		 kh=10;
		 km=0;
		 }
		 else
		 {
		for(i=0;i<n-1;i++)
		{
			int k=0;
			while(k<=n-i-2)
			{
				if(st[k].h1>st[k+1].h1)
				{
					tmp=st[k];st[k]=st[k+1];st[k+1]=tmp;
				}
				k=k+1;
			}
		}

	      //	for(i=0;i<n;i++)
		//printf("h1 %d m1 %d h2 %d m2 %d\n",st[i].h1,st[i].m1,st[i].h2,st[i].m2);
		sh=10;sm=0;tm1=0;  kh=10;km=0;
		for(i=0;i<n;i++)
		{
		//scanf("%d%c%d",&h1,&c,&m1);
	       //	if(i==n+1) {eh=18;em=0;}
		//else  {
		eh=st[i].h1;em=st[i].m1;//}
		if(em<sm) {em=em+60;eh=eh-1;}
			naph=eh-sh;
			napm=em-sm;
			tm2=naph*60+napm;
			if(tm1<tm2) {tm1=tm2;kh=sh;km=sm;}
	       //	scanf("%d%c%d%[^\n]",&h2,&c,&m2,&a);        //getchar();
		sh=st[i].h2;sm=st[i].m2;
			if(i+1==n)
			{
			eh=18;em=0;
			if(em<sm) {em=em+60;eh=eh-1;}
			naph=eh-sh;
			napm=em-sm;
			tm2=naph*60+napm;
			if(tm1<tm2) {tm1=tm2;kh=sh;km=sm;}
			}
		}
		}
		if(tm1>59)
			{
			//if(km<10&&kh<10)
			//printf("Day #%d: the longest nap starts at 0%d:0%d and will last for %d hours and %d minutes.\n",j,kh,km,tm1/60,tm1%60);
			 if(km<10)
			printf("Day #%d: the longest nap starts at %d:0%d and will last for %d hours and %d minutes.\n",j,kh,km,tm1/60,tm1%60);
			//else if(kh<10)
			//printf("Day #%d: the longest nap starts at 0%d:%d and will last for %d hours and %d minutes.\n",j,kh,km,tm1/60,tm1%60);
			else
			printf("Day #%d: the longest nap starts at %d:%d and will last for %d hours and %d minutes.\n",j,kh,km,tm1/60,tm1%60);
			}
		else
		   {
		//   if(km<10&&kh<10)
		//	printf("Day #%d: the longest nap starts at 0%d:0%d and will last for %d minutes.\n",j,kh,km,tm1);
			 if(km<10)
			printf("Day #%d: the longest nap starts at %d:0%d and will last for %d minutes.\n",j,kh,km,tm1);
		//	else if(kh<10)
		//	printf("Day #%d: the longest nap starts at 0%d:%d and will last for %d minutes.\n",j,kh,km,tm1);
			else
			printf("Day #%d: the longest nap starts at %d:%d and will last for %d minutes.\n",j,kh,km,tm1);
		   }
		j++;
	}
	return 0;
}

Bidhan
New poster
Posts: 6
Joined: Mon May 17, 2010 5:07 pm
Location: University Of Dhaka, Bangladesh.
Contact:

Re: 10191 - Longest Nap

Post by Bidhan » Sat Dec 04, 2010 12:56 pm

1.Though the problem says input would be like
time1 time2 appointment
But it's strange that it may contain no appointment at all, which means an empty string.

2.The first appointment may start after 10:00, which means there's a slot for nap even before the very first appointment.

3.Same as point 2 the last appointment may end before 18:00 leaving time for nap after that.

4.For n=0 the longest nap "last for 8 hours and 0 minutes" starting from 10:00.

5.The appointments may not be sequential. You better sort them before calculation.

6.You can be assured of appointment times not being overlapped.

Input

Code: Select all

5
12:01 13:00
13:00 15:00 I love WA
15:30 17:45 :P
11:00 12:00 huhahaha
12:00 12:01
5
12:01 13:00
13:00 15:00 WAWAWAWA
15:30 15:31 Reading
11:00 12:00 Playing NFS
12:00 12:01
0
Output

Code: Select all

Day #1: the longest nap starts at 10:00 and will last for 1 hours and 0 minutes.
Day #2: the longest nap starts at 15:31 and will last for 2 hours and 29 minutes.
Day #3: the longest nap starts at 10:00 and will last for 8 hours and 0 minutes.

kushol
New poster
Posts: 4
Joined: Wed Jan 05, 2011 10:15 am

Re: 10191 - Longest Nap

Post by kushol » Sat Jun 11, 2011 10:12 pm

Why WA............................................ :(

Code: Select all

Removed
Last edited by kushol on Thu Dec 22, 2011 4:33 pm, edited 1 time in total.

kantarasutran
New poster
Posts: 1
Joined: Tue Jun 14, 2011 6:27 am

REGARDING

Post by kantarasutran » Tue Jun 14, 2011 6:41 am

I am not sure where you are getting your info, but good topic. I needs to spend some time learning much more or understanding more. Thanks for great info I was looking for this info for my mission.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10191 - Longest Nap

Post by plamplam » Thu Jul 21, 2011 3:18 pm

Quite a cushy problem I must say.

There won't be any cases like
0 (Although it is a valid case IMAO)
(Trust me, my program prints garbage if n is 0, I still got Accepted).
Also, there is always going to be a single space between the starting and finishing time.
And appointment times doesn't overlap, I'm not sure if there is going to be an empty string after the end time, because my program just ignores everything after the finishing time. (I used gets and later separated starting and ending time)

Nevertheless, try this set if you get Wrong Answer :) :

Code: Select all

3
10:07 12:19 Football game
13:11 16:17 Why why why me?
16:59 17:30 Nanananna Music :D
1
12:00 16:00 Burdens up my ass
1
12:00 15:59           Miserable At Best
3
15:00 17:00 Hey, don't blow a fuse!
13:00 15:00 Codeforces contest!!
10:00 11:00 Dinner time....yeaa :D
3
13:00 14:00 Shower
14:00 15:00 Again Shower!
15:00 16:00 Not again :(
3
10:00 10:12 Good night mommy
13:01 13:14 Masturbating time/Quickie
14:10 15:57 Secret Research!
1
13:59 14:01 Do you know what this means?
1
13:58 14:01 Got a buck to spare dude?
9
17:57 17:59     Aaaaaaaaaaaaaaaa
13:13 13:58 Break time :D
10:05 10:15 Solving this problem was a bummer(jk)
15:25 16:25 uhunt problem solving
14:21 15:01 ........
10:20 11:01 Pandora Radio()
16:30 17:00 Reading (I need more time to cram for the test).
12:00 12:37 Can't decide what to do, I guess I'll just take a nap.
17:30 17:54 Late night porn
4
14:47 17:04 Popcorn mmmm.....
10:16 11:05 I still watch popeye(Please don't tell anyone)
17:30 17:50 Cleaning up the mess
13:18 14:01 Whoaa
2
16:00 18:00 Shit happened today
11:59 14:01 I tried for 4 hours, but still couldn't solve problem 10191

Code: Select all

Day #1: the longest nap starts at 12:19 and will last for 52 minutes.
Day #2: the longest nap starts at 10:00 and will last for 2 hours and 0 minutes.
Day #3: the longest nap starts at 15:59 and will last for 2 hours and 1 minutes.
Day #4: the longest nap starts at 11:00 and will last for 2 hours and 0 minutes.
Day #5: the longest nap starts at 10:00 and will last for 3 hours and 0 minutes.
Day #6: the longest nap starts at 10:12 and will last for 2 hours and 49 minutes.
Day #7: the longest nap starts at 10:00 and will last for 3 hours and 59 minutes.
Day #8: the longest nap starts at 14:01 and will last for 3 hours and 59 minutes.
Day #9: the longest nap starts at 11:01 and will last for 59 minutes.
Day #10: the longest nap starts at 11:05 and will last for 2 hours and 13 minutes.
Day #11: the longest nap starts at 10:00 and will last for 1 hours and 59 minutes.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

timiscool_sike
New poster
Posts: 1
Joined: Tue Dec 06, 2011 11:06 pm

10191 Wrong Answer-but it always outputs correctly.

Post by timiscool_sike » Tue Dec 06, 2011 11:14 pm

#include<algorithm>
#include<iostream>
#include<fstream>
#include<string>
#include<iterator>
#include<sstream>
#include<vector>

using namespace std;

int main()
{
string str, str1a, str1b, str2a, str2b ;
int hrs, mins1,mins2, time1a,time1b, time2a, time2b, naptime, appointments=0,count= 0, day=0, startindex=0;
vector<int> start, end, inttimes; //start=minute totals for each time, end=minute totals for each break,

start.push_back(600);
start.push_back(1080);

//****inputting strings****//
while(!cin.eof())
{
getline(cin,str);

if(str.size()<=3) //if they put in integer from 1 to 100 (number of appointments)
appointments= atoi(str.c_str());

else //if they put in appointments
{
//strings of 4 times
str1a= str.substr(0,2);
str1b= str.substr(3,2);
str2a= str.substr(6,2);
str2b= str.substr(9,2);

//ints of 4 times
time1a = atoi(str1a.c_str());
time1b = atoi(str1b.c_str());
time2a = atoi(str2a.c_str());
time2b = atoi(str2b.c_str());

//first minutes
mins1= time1a*60 + time1b ;
start.push_back(mins1); //putting first time into first vector
//start.push_back_ba

//second minutes
mins2= time2a*60 + time2b ;
start.push_back(mins2); //putting second time into first vector

//count++;
}

if(count==(appointments)) //if all the appointments for the day have been entered
{
day++;

sort(start.begin(), start.begin()+start.size()); //sorting array of minute totals

for(int i= 0; i<start.size() ;i+=2)
{
end.push_back(start[i+1]-start);
}

for(int i= 0; i<start.size() ;i+=2)
{
if(start[i+1]-start== *max_element(end.begin(),end.end()) )
{
startindex= i;
i=start.size(); //index of longest naptime has been found
//cout<<endl<<"end doesnt work"<<endl;
}
}

naptime= *max_element(end.begin(),end.end()) ; //minute total for longest break

cout<<"Day #"<< day<<": the longest nap starts at "<< start[startindex]/60 <<":";

cout<< (start[startindex]%60) / 10;
cout<< (start[startindex]%60) % 10;

cout<<" and will last for ";
if(naptime>=60)
cout<< naptime/60<<" hours and "<<naptime%60<<" minutes."<<endl;
else
cout<< naptime<<" minutes."<<endl;

count=0;
start.clear();
end.clear();

start.push_back(600);
start.push_back(1080);
startindex=0;
}
else
count++;
}
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10191 Wrong Answer-but it always outputs correctly.

Post by brianfry713 » Thu Jan 19, 2012 3:04 am

This code prints an extra day at the end.
Check input and AC output for thousands of problems on uDebug!

warheadshot
New poster
Posts: 2
Joined: Tue Feb 07, 2012 10:20 am

Re: 10191 - Longest Nap

Post by warheadshot » Tue Feb 07, 2012 10:36 am

Hi, Why I get WA? Thx in advance.

Code: Select all

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
 
char line[257];
int a[100],b[100];int pos=-1;
 
int brek(int x){
        int nn=0,n2=0;int pos1=-1;
        for(int i=0;i<=x;i++){
                int mm=8000,m2=8000;
                for(int j=1;j<=x+1;j++){
                        if(a[j]-b[i]<0){continue;}
                        m2=min(mm,a[j]-b[i]);
                        if(m2!=mm){mm=m2;pos1=b[i];}
                }
                n2=max(nn,mm);
                if(n2!=nn){nn=n2;pos=pos1;}
        }
        return(nn);
}
 
int main(){
        int s,cc,cont=0;int q,w,e,r;
        while(scanf("%d\n",&s)==1){
                cont++;
                a[0]=600;b[0]=600;
                for(int ii=0;ii<s;ii++){
                        gets(line);
                        sscanf (line, "%d:%d %d:%d", &q, &w, &e, &r);
                        a[ii+1]=q*60+w;
                        b[ii+1]=e*60+r;
                }
                a[s+1]=1080;b[s+1]=1080;cc=brek(s);
                cout<<"Day #"<<cont<<": the longest nap starts at ";
                if(pos==-1){cout<<"18:00 and will last for 0 minutes.\n";continue;}
                cout<<pos/60<<":";
                if(pos%60<10){cout<<"0"<<pos%60<<" and will last for ";}else{cout<<pos%60<<" and will last for ";}
                if(cc<60){cout<<cc<<" minutes.\n";continue;}
                cout<<cc/60<<" hours and "<<cc%60<<" minutes.\n";continue;
                                
        }
}

Post Reply

Return to “Volume 101 (10100-10199)”