CIELNUM1 - Editorial

editorial
, , ,
1

ROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

There are 3N numbers which are N digits integers and contain only the digits 3, 5 and 8. And there are no less than 3N / 6 Ciel numbers with N digits. Because, for example, let a, b, c be distinct nonnegative integers. Then the all following number are equal.

The number of integers k satisfying f(k, 3) = a, f(k, 5) = b, f(k, 8) = c
The number of integers k satisfying f(k, 3) = a, f(k, 5) = c, f(k, 8) = b
The number of integers k satisfying f(k, 3) = b, f(k, 5) = a, f(k, 8) = c
The number of integers k satisfying f(k, 3) = b, f(k, 5) = c, f(k, 8) = a
The number of integers k satisfying f(k, 3) = c, f(k, 5) = a, f(k, 8) = b
The number of integers k satisfying f(k, 3) = c, f(k, 5) = b, f(k, 8) = a

And all integers in one group are Ciel numbers. In this case the ratio of Ciel numbers are 1/6. If a, b, c are not distinct, the ratio of Ciel numbers are more than 1/6. Check it by yourself:)

Therefore the 50000th Ciel number fits signed 64 bit integer type. And it works in this problem that simply checking whether each number containing only the digits 3, 5, 8 is a Ciel number or not. The number of the integers that we should check is no more than 6 * 50000.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes
2

What is the importance and use of this part of the code ?

bool isciel(int n)
{
int i, count[3];

count[0]=0;
count[1]=0;
count[2]=0;

ciel[13] = 0;
ciel[12] = '\n';

i = 11;

while (n)
 {
	int j = n%4;

	n /= 4;
	
	switch(j)
	 {
		case 0:
			return 0;
		case 1:
			ciel[i] = '3';
			break;
		case 2:
			ciel[i] = '5';
			break;
		case 3:
			ciel[i] = '8';
			break;
	}
	
	count[ j-1 ]++;
	
	i--;
}

if (count[0] > count[1] || count[1] > count[2])
  return 0;
else 
{
	strcpy(test+c,ciel + i + 1);
	c += 12 - i;
	
	if (c > BUFFER)
	{
		test[c]=0;
		printf("%s",test);
		c = 0;
	}
	
	return 1;
}

}