10683 - The decadary watch

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

Moderator: Board moderators

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

10683 - The decadary watch

Post by htl » Mon Aug 09, 2004 11:35 am

Easy problem but got wa. I think the problem is the precision. How do I get the digits of the result precisely? Or are there some critical input?

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Mon Aug 09, 2004 1:15 pm

I don't think there is any critical input.
The main Idea is that the number of MM-s in day of our system is 125/108 time small then in new time system.You must find number of MM-s from 00:00:00 to the given time in our time system(for example P). And p*125/108-rd MM will be in new time system.Than you must make it to seconds, minutes, hours.Besouse p*125/108 is not integer we must take trunc(p*125/108).In problem discription there is written that we must take TRUNCATION.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Mon Aug 09, 2004 5:54 pm

I use t=floor(temp*125/108*100), where t is long and temp is double. temp is the total seconds of given time in traditional format. But it didn't work. How do I improve it?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Aug 09, 2004 9:06 pm

I use the same approach and got Acc at first attempt ... I don't use floor, but integral cast :-)

Best regards
DM

PS. I also think that this problem has no critical inputs, but I may be wrong
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Mon Aug 09, 2004 9:26 pm

why bother using doubles? Since rounding is truncating in this case, just use integers and use integer division:
[cpp]
int millisecs = ...;
int newmillisecs = (millisecs*125)/108;
[/cpp]
Simple as that....

Arm.Turbo
New poster
Posts: 21
Joined: Wed Aug 11, 2004 1:20 pm

Post by Arm.Turbo » Wed Aug 11, 2004 1:28 pm

After many attemps i still got the WA. But I finally found needed representation:
printf("%07.0lf\n",(double)((sum*125)/108));

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Wed Aug 11, 2004 4:04 pm

it might also work with big numbers if use long long.... even easier than multiplying by (125/108): you do not need to simplify your fraction :)

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

10683 -> Problem C - The decadary watch

Post by _.B._ » Sun Aug 15, 2004 4:23 am

Greetings!
I've read about this problen in the other post, but still don't get it's logic.
Will anyone please tell me what's wrong with my code?
Thanks in advance!

[pascal]{ Bernardo E. L
Last edited by _.B._ on Mon Aug 16, 2004 2:55 am, edited 2 times in total.
_.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Sun Aug 15, 2004 7:15 am

Maniac wrote:why bother using doubles? Since rounding is truncating in this case, just use integers and use integer division:
[cpp]
int millisecs = ...;
int newmillisecs = (millisecs*125)/108;
[/cpp]
Simple as that....
why integer division doesn't cause error but does double using?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Aug 15, 2004 8:02 am

You are loosing precision by using the real type for Hora1. The function trunc() can therefor give too low answers. It is better to use integer types all the way.
In your program I used QWord for both Hora1 and Hora2 and then changed two lines:[pascal] Hora1:=((((((HH*60)+MM)*60)+SS)*100)+CC)*100/CienPHora;
Hora2:=trunc(CienPDeci*Hora1/100);[/pascal]into:[pascal]
Hora1:=(((((HH*60)+MM)*60)+SS)*100)+CC;
Hora2:=Hora1*CienPDeci div CienPHora;
[/pascal]and got Accepted.

Another method is to avoid the function trunc() from giving too low answers by adding a small 'fudge factor' before truncation.
Changing the line:[pascal] Hora2:=trunc(CienPDeci*Hora1/100);
[/pascal]to:[pascal] Hora2:=trunc(CienPDeci*Hora1/100+0.000000001);
[/pascal]will also get you accepted.

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Thanks!

Post by _.B._ » Mon Aug 16, 2004 2:07 am

Little Joey, once again, thanks for taking the time to answer! :D
Some times it's easier to code a program, than to read and correct one.
You rule! 8)
I find the second option you gave really interesting, and gives a faster execution time (just a bit).
Now, how do you know how small the 'fudge factor' should be? (0.000000001 this time)

Thanks!, and keep posting!
_.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Aug 16, 2004 9:44 am

I guess it's something of an art :)

It depends on a lot of things:
- the precision of the internal representation of a real;
- the precision of your calculation (order of operators);
- the range of integers you get after truncation;
- the luck that the input set doesn't contain cases for which it fails.

And it's not always possible. Best is trial and error until you get Accepted...

Therefor an all integer solution, if possible, should be preferred, because you get "infinite precision". And it can be as fast as, or almost always faster than a solution with reals, if you can get your algorithm right.

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Na' guara'!!

Post by _.B._ » Mon Aug 16, 2004 6:16 pm

Well, thanks again for the info :wink:
You are right, it'll be better to work with integers, with a good algo 8)

Keep posting!

Thanks!
_.

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

10683

Post by pipo » Fri Aug 20, 2004 4:08 am

Greatings! :)
I have attempted several times, but i still got WA..
i really dont know where code is wrong...
my code is following..

Code: Select all

	char input[9], buf[12];
	int hh, mm, ss, cc, sum;
	float sumf;

	while( scanf("%s", input) != -1 ) 
	{
		sprintf(buf, "%c%c %c%c %c%c %c%c",
			input[0], input[1], input[2], input[3],
			input[4], input[5], input[6], input[7]);
		sscanf(buf, "%d %d %d %d", &hh, &mm, &ss, &cc);
	
		sum = (hh*3600 + mm * 60 + ss) * 100 + cc;

		sumf = (float)sum * (125.0 / 108);

		printf("%07d\n", (int)sumf);
	}
would you tell me where is wrong ?

if any code is wrong, tell me why it is wrong..

thanks for reading.

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Mon Aug 23, 2004 9:21 am

First, you can avoid all floating point problems by using integers, instead of floating point numbers (sum*125/108 works and 125*sum still fits in 32 bit signed integer)
Second, if you use floating point numbers, use double instead of float. (float has only a precision of about 7 decimals, which is critical in this case)
Third, when converting double's to integers, I always do something like

Code: Select all

(int)(floor(f+1e-10)+1e-10)
to avoid small rounding errors.

Post Reply

Return to “Volume 106 (10600-10699)”