ACMICL1 - Editorial

editorial
, ,
1

PROBLEM LINK:

http://www.codechef.com/ICL2015/problems/ACMICL1

Author:

Cheral Khandediya

Tester:

Shubham Gupta

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

None

PROBLEM:

You have N mice. All of them eat cupcakes with the same speed except one mice which eats slower. Find the minimum number of cupcakes (say C) required to find the slower mice. INPUT N. OUTPUT C.

QUICK EXPLANATION:

Use grouping . When you provide one cupcake to each group(Each group contains the same number of mice. The group which finishes slower contains the mutant mice. Now again divide this group into smaller groups and continue till you find the slower mice.

Explanation:

Note that: You cannot cut the cup cake into pieces each group has to be given one full cupcake. Assume that all other mutations except one are useless and all mice except one eat cupcakes with the same speed and there is at least one mutation that will be successful. The same cupcake cannot be used more than once. Assume worse case scenario problems faced anywhere.

Explanation for test cases:

  1. N=2 C=2 If there are 2 mutations, 1 in each mice, then both of them can be given a cupcake and the mice which eats less will be the correct mutation.
  2. N=6 C=4 If there are 6 mutations, then divide 6 mice in two groups of 3. Give each group a cupcake. The group which eats less cupcake i.e finishes later contains the mutant mice. Let’s assume “abc” is that group. Now, this group ‘abc’ has 3 mice. Use only two cupcakes for any two mice. If both of them finish with the same speed, the third mice is the slower one else the one which finishes slower among the two. So total number of cupcakes required are 4 (2+2).
  3. N=12 C=5 As in case two, divide the mice into 3 groups of four mice. After using 2 cupcakes you are left with 4 mice. For these 4 mice instead of using (2+2) 4 more cupcakes, Use only 3 cupcakes for any 3 mice. If all 3 of them finish with the same speed, the fourth mice is the slower one else the one which finishes slower among them. So total number of cupcakes required are 5(2+3).

When N is a prime number , the answer won’t be N.
Hence for larger values of N and when is a prime number, first try dividing the mice into groups of 4 and 3. If it is not possible. Without increasing the number of groups and hence the number of cupcakes. If it is not possible to divide, remove 1 or 2 mice and divide the rest into groups. When you end up with a smaller group add those mice back. And countinue the cycle till you find the slower one.

SOLUTION:

int n,cup=0;
scanf("%d",&n);
while (n>=3)
{
	if(n==4){
		cup+=3;
		break;
	}

	if(n%3==0)
	{
		cup=cup+2;
		n=n/3;
	}
	else if ((n+1)%3==0)
	{
		cup=cup+2;
		n=(n+1)/3;
	}
	else
		{cup=cup+2; n= (n+2)/3;}
	
}
if (n==2) 
	cup=cup+2;
printf ("%d\n",cup);