11773 - King's Wish

All about problems in Volume 117. 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
User avatar
nealzane
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:

11773 - King's Wish

Post by nealzane » Sat Apr 17, 2010 6:27 pm

for the example input 18, how is an output '9 1' violating the problem statement?
it seems '9 1' is better than '9 2'
can '9 1' cover a square smaller than 18x18?
8-)

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11773 - King's Wish

Post by emotional blind » Sat Apr 17, 2010 6:44 pm

nealzane wrote:can '9 1' cover a square smaller than 18x18?
Yes, it can cover, 9 x 9

User avatar
nealzane
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:

Re: 11773 - King's Wish

Post by nealzane » Sat Apr 17, 2010 6:50 pm

emotional blind wrote:
nealzane wrote:can '9 1' cover a square smaller than 18x18?
Yes, it can cover, 9 x 9
right, i was aware of it. but for '9 1' i guess 9x9 is not the problem wants because '9 1' covers a length of the square.

the problem says '2 1' is valid for 4x4. while if '9 1' is valid for 9x9, '2 1' cannot be valid for 4x4, since in that case, '2 1' is valid for 2x2 also which is smaller than 4x4.

i guess '9 1' cannot be used for 9x9, just as '2 1' cannot be used for 2x2.
8-)

orfest
New poster
Posts: 5
Joined: Sat Oct 01, 2005 7:11 pm

Re: 11773 - King's Wish

Post by orfest » Sun Apr 18, 2010 3:51 am

Guys, could you please give any difficult test cases?

orfest
New poster
Posts: 5
Joined: Sat Oct 01, 2005 7:11 pm

Re: 11773 - King's Wish

Post by orfest » Sun Apr 18, 2010 3:54 am

Is 3 20 correct answer for test case 60?

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11773 - King's Wish

Post by emotional blind » Sun Apr 18, 2010 6:45 am

nealzane wrote:
emotional blind wrote:
nealzane wrote:can '9 1' cover a square smaller than 18x18?
Yes, it can cover, 9 x 9
right, i was aware of it. but for '9 1' i guess 9x9 is not the problem wants because '9 1' covers a length of the square.

the problem says '2 1' is valid for 4x4. while if '9 1' is valid for 9x9, '2 1' cannot be valid for 4x4, since in that case, '2 1' is valid for 2x2 also which is smaller than 4x4.

i guess '9 1' cannot be used for 9x9, just as '2 1' cannot be used for 2x2.
I think you did not understand the problem properly. In problem statement "For example, if K = 6, you cannot use (2, 1) tile as you can fill 4x4 square with it. (The king does not like smaller replica of his room with same size of tile)." - this line wants to say that 4 x 4 is a smaller possible square, but this is not smallest. The smallest possible square using (2, 1) is 2 x 2.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11773 - King's Wish

Post by emotional blind » Sun Apr 18, 2010 6:56 am

orfest wrote:Is 3 20 correct answer for test case 60?
No, I think right answer is 4 30

User avatar
nealzane
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:

Re: 11773 - King's Wish

Post by nealzane » Sun Apr 18, 2010 8:23 am

thanks Arif for the explanation.
8-)

md_yusuf
New poster
Posts: 9
Joined: Fri Jun 25, 2010 11:09 pm

Re: 11773 - King's Wish

Post by md_yusuf » Sat Jul 03, 2010 1:20 pm

i have not find any simple equation for this problem im getting tle. plz give me a hints. here is my code....


#include<iostream>
using namespace std;
int main()
{
long int n,flag,i,x,j,l,w;
scanf("%ld",&n);
for(i=1;i<=n;i++)
{
flag=0;
scanf("%ld",&x);
for(j=2;j*j<=x;j++)
{
if((x%j)==0)
{
w=j;
l=x/j;
if((l%w)!=0)
{
flag=1;
break;
}
}
}
if(flag==0)
printf("Case %ld: Impossible\n",i);
else
printf("Case %ld: %ld %ld\n",i,l,w);
}
return 0;
}

md_yusuf
New poster
Posts: 9
Joined: Fri Jun 25, 2010 11:09 pm

Re: 11773 - King's Wish

Post by md_yusuf » Sun Jul 04, 2010 1:53 am

I think my algo is wrong .... :(
nobody help me :(

Post Reply

Return to “Volume 117 (11700-11799)”