10208 - Liar or Not Liar that is the...

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

Moderator: Board moderators

Post Reply
Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

10208 - Liar or Not Liar that is the...

Post by Adrian Kuegel » Sat Jan 26, 2002 2:51 pm

Can someone, who has solved this problem, please give me the correct output for
4
10!
Thanks in advance!

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Post by shahriar_manzoor » Sun Jan 27, 2002 2:53 am

He might be honest.

He is a liar.
7

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jan 27, 2002 5:28 pm

Thank you. I have now solved the problem.
I had thought that the sides have to be >0, and therefore printed
4 ->he is a liar

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

10208 - WA

Post by txandi » Sun Feb 29, 2004 2:21 am

I can't find out what's wrong in my program... it seems to work well but when I summit it, I get WA :(

Can anyone give some inputs/outputs to check if my program is correct?

Thanks for all!

PD: I'm new here... Can I send my code to someone in order to check if it's ok? Or can anyone tell me what I have to do to see which is my wrong answer?

Thanks again!

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sun Feb 29, 2004 8:50 am

I just solved this question.
At first I get 4 WA.....I don't understand why.

As I know that Shahriar Manzoor always design tricky data,
I modified my code to answer
"He might be honest." if the input is N and it is a square number.
For example, if the input is 4, you need to answer "honest".

Then I get accepted.
BUT!! How can a "right-angled triangles" have an edge length zero??? :evil:
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

Post by txandi » Tue Mar 02, 2004 10:05 pm

It works, the side can be 0!!!

Thanks!

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

10208 crazy shariar

Post by harry » Tue Sep 07, 2004 8:05 am

can any body tell me what is the output of the following input
10000000
10000000!

Here
4<=N<=10000000
hope N!=0

thanks in advance.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Sep 07, 2004 12:05 pm

My output:

Code: Select all

He might be honest.

He is a liar.
7 11 43 47 59 67 71 83 131 151 163 191 283 307 311 347 367 383 443 479 487 491 503 571 599 607 619 659 691 719 727 739 811 827 883 887 907 967 1039 1051 1063 1087 1091 1123 1151 1163 1187 1231 1303 1423

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

Post by harry » Tue Sep 07, 2004 6:04 pm

thanks for the reply.
my output are same as yours.
but w.a.
any tricky input plz.
thanks in advance.

jdmetz
New poster
Posts: 25
Joined: Fri May 27, 2005 5:23 pm
Location: Ann Arbor, MI USA

some input to try

Post by jdmetz » Thu Jul 14, 2005 1:18 pm

If you are still having trouble, try these input.

Input:

Code: Select all

884!
7816782!
9999991
9999971
9999965
9999895
9999819
9999729
9840769
9728161
Output:

Code: Select all

He is a liar.
11 23 67 79 151 163 167 223 227 239 251 263 271 283 443 463 467 479 487 491 499 503 523 547 563 571 587 599 607 619 631 643 647 659 683 691 719 727 739 743 751 787 811 823 827 839859 863 883

He is a liar.
19 79 83 139 179 199 211 223 307 359 367 419 439 467 499 647 739 751 811 839 859 863 887 907 911 967 983 1063 1087 1279 1303 1439 1447 1483 1487 1499 1523 1567 1579 1607 1667 17591823 1831 1871 1999 2003 2027 2083 2099

He is a liar.

He is a liar.

He might be honest.

He is a liar.

He is a liar.

He might be honest.

He might be honest.

He might be honest.

s000015
New poster
Posts: 5
Joined: Sat Oct 08, 2005 1:56 pm
Location: Taiwan

10208 I don't understand...

Post by s000015 » Tue Aug 01, 2006 7:49 am

Output:

Code: Select all

Apart from that you also need to print the prime numbers with which you need to divide N! to make it the square of a valid largest side of one of his lands.
Sample I/O:

Code: Select all

4!

He is a liar.
3
but 4!/3 = 8, 8 isn't a square of a valid largest side...

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

Post by mf » Tue Aug 01, 2006 10:04 am

Why, 8 = 2^2 + 2^2, so 8 is the square of hypotenuse of a right triangle with legs 2 and 2.

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

10208(Liar or not Liar) Helppppppppp

Post by Shuvra(CSE-BUET) » Thu Aug 24, 2006 4:01 pm

I found the problem very odd. I can't understand how to solve this. How can prime factorization help me here? I could not find the pattern.
It is not possible like prob. 106 to generate and check x,y,z tripple.
Funny thing is that Shahriar Manzoor has a very big heart ,and so always deals with very big number like 10000000! .
Ha ha ha.......
:D
Life is a challenge.

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 10208 - Liar or Not Liar that is the...

Post by suneast » Fri Dec 31, 2010 11:19 am

Thx so much to U all... :D
I finally got ac after passed the test case pase above...

I found that, the problem is just about sieve the prime factors and check the factor is SQUARE or not :wink:

Code: Select all

O(NlogN) time to make a prime table till 10^7
consider that: a^2 + b^2 = c^2
if a = m^2 - n^2, b= 2mn, c = m^2 + n^2
the format above is fine, so we just need to enum m,n to get "c"
we can initiate the table fine[c], like

Code: Select all

#define MAXN 10^7
for( i:1->INF)
   if(i*i>MAXN) break
      for( j:i->INF)
	     if(i*i+j*j>MAXN) break;
		 else fine[i*i+j*j]=true
N(N!):

Code: Select all

factorize N (N!), into p1^n1 *... pi^ni * ....
if( ni is odd && fine[pi]=false ), "He is a liar."
otherwise, "He might be honest."
if the input is N!, just store no more than 50 pi,
and finally output
done!
more : if N is SQUARE the answer is always "He might be honest." :wink:

Post Reply

Return to “Volume 102 (10200-10299)”