11052 - Economic phone calls

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

11052 - Economic phone calls

Post by ImLazy » Wed Jul 26, 2006 2:56 pm

I find the offical I/O, and for this input:

Code: Select all

3
06:06:05:06 641037712 -
04:13:06:36 17 -
10:25:14:37 793127405919586 +
The output is:

Code: Select all

1
But I think the output should be "2". The first or the second log must be kept, otherwise the third log will come to the current year.
I stay home. Don't call me out.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Jul 26, 2006 3:11 pm

The last log is always in the current year.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Jul 26, 2006 3:14 pm

I think ImLazy is right - there are two years and by keeping only one log you can't determine that. Unless I misunderstood the problem.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Jul 26, 2006 3:18 pm

You should determine years, starting from the last log entry and going backwards (read the 'Recovery of Years' section carefully.)
And you'll always assign to the last log entry the current year.
Two previous log entries simply can't influence that.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Jul 26, 2006 3:23 pm

Yes, sorry, I just reread it - I did misunderstand it. That's how I understood it during the contest so my mind was stuck. 2am contests right after work are fun :)

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Wed Jul 26, 2006 3:26 pm

Oh, I misunderstood the problem. The last log in the input is the latest. I used to think the first one is.
I stay home. Don't call me out.

sarah
New poster
Posts: 7
Joined: Tue Aug 30, 2005 2:54 pm
Location: Iran
Contact:

Post by sarah » Fri Jul 28, 2006 10:10 am

Can you explain the greedy approach for this problem, #11052?
And what is the correct output for this input?

Code: Select all

1
07:21:14:00 1337 -
0

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Fri Jul 28, 2006 11:18 pm

i think the answer for the above input is 0 , because we don't need to store anything , by the way i have used a greedy solution for this problem , but i 've got WA , can someone post some IO ?

tanx
Arsalan
In being unlucky I have the record.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Jul 29, 2006 1:36 am

arsalan_mousavian wrote:i think the answer for the above input is 0
Yes, the correct answer is 0.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Jul 29, 2006 2:04 am

arsalan_mousavian wrote:but i 've got WA , can someone post some IO ?
Some random test cases:

Code: Select all

19
01:23:21:41 47 -
09:11:14:05 47 -
10:31:11:11 47 +
09:04:22:52 47 -
05:10:17:55 47 -
02:15:19:30 47 -
09:21:01:26 47 +
01:24:06:53 47 +
04:29:18:25 47 -
02:18:05:01 47 +
09:25:15:37 47 -
12:17:21:05 47 +
09:14:02:54 47 -
04:13:08:13 47 +
06:03:22:23 47 +
03:18:15:21 47 -
07:13:00:54 47 -
02:17:06:22 47 -
11:27:08:54 47 +
11
04:16:03:43 47 +
06:18:03:31 47 -
10:29:00:30 47 +
01:11:00:58 47 -
04:05:14:19 47 -
10:10:18:58 47 -
09:24:04:08 47 +
04:17:02:08 47 +
02:24:19:47 47 -
04:11:06:18 47 -
04:18:15:31 47 +
8
01:03:10:18 47 +
03:06:10:53 47 -
01:09:03:21 47 -
11:03:09:27 47 +
12:11:05:20 47 -
05:19:19:24 47 -
08:23:13:42 47 -
04:07:12:38 47 +
12
01:04:07:12 47 -
03:21:15:37 47 -
01:18:09:44 47 +
01:26:23:36 47 -
12:28:17:08 47 +
12:12:11:31 47 -
11:28:14:05 47 -
04:02:21:49 47 -
10:04:05:50 47 +
03:03:02:39 47 -
06:18:13:52 47 -
10:04:04:24 47 +
20
03:23:08:57 47 +
01:01:01:18 47 -
08:26:13:26 47 +
05:15:11:29 47 -
11:29:03:25 47 -
11:09:15:44 47 -
08:08:08:40 47 +
11:27:20:58 47 -
11:22:04:25 47 +
04:04:20:52 47 -
01:04:13:36 47 -
05:08:04:00 47 -
03:30:07:08 47 -
07:26:09:25 47 -
05:10:21:17 47 -
07:31:02:07 47 +
12:04:15:12 47 -
06:17:06:12 47 -
12:22:00:32 47 -
10:19:10:48 47 -
0
My AC's output:

Code: Select all

15
7
6
6
19

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Sat Jul 29, 2006 3:35 pm

thanks martin macko for you reply , but my program passes all your input ,
any suggestions ?

yours
Arsalan
In being unlucky I have the record.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Jul 29, 2006 3:40 pm


User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Mon Jul 31, 2006 10:56 am

The sample output of this problem is 6 but my program produces 5 and my program is AC. Is that means that the sample output is WRONG?
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jul 31, 2006 1:30 pm

Tell us which 5 log entries should be kept, according to your program.

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Input for this problem is lacking

Post by fh » Tue Aug 01, 2006 10:30 am

I found my mistake, my code assume that if t'>t then phone call t' occurs in the previous year whether the correct assumption should be t' >= t.

So, for the sample input, i got 5 :

12:31:23:59 0123456789012345 +
07:21:19:00 1337 -
01:01:00:00 0987654321 -
07:21:14:00 1337 - (DELETED)
11:11:11:11 11111111111 +
01:01:00:00 0123456789 +
01:01:00:00 0987654321 - (DELETED)

Strangely, I got AC.

So i think the sample input is not in the judge test cases.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

Post Reply

Return to “Volume 110 (11000-11099)”