tamojit9's blog

need explanation of the following logic for problem 204A(round 129 div 1)
By tamojit9, 14 years ago, In English 
long long calc(long long a) {
	if (a < 10) return a;
	long long r = a / 10;
	r += 8;
	long long f = a;
	while (f >= 10) f /= 10;
	if (f <= a % 10) r++;
	return r;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
14 years ago, hide # |
← Rev. 6  
Vote: I like it +1 Vote: I do not like it

Function calc(a) computes number of all good numbers which are less of equal to a.

if (a < 10) return a; — in case of one-digit input.

It's simple to prove that each tenth number is good (first and last digits are equal): 

	long long r = a / 10;

Don't forget about one-digit numbers: 

	r += 8;

Let's compute the first digit f of the number a

	long long f = a;
	while (f >= 10) f /= 10;

and check whether (a div 10 * 10 + f) <= a: 

	if (f <= a % 10) r++;
→ Reply
  • »
    »
    14 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    "It’s simple to prove that each tenth number is good (first and last digits are equal): long long r = a / 10;" not able to understand the above lines and one digit numbers should be 1 to 9(why 8) please explain??

    → Reply
    • »
      »
      »
      14 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      Ok, assume that a % 10 == 0. (Last string checks another case)

      For t > 0 every interval [ t * 10, (t + 1) * 10 ) contains exactly one good number. So the interval [10, a) contains (a - 10) / 10 good numbers, or a / 10 - 1. Add nine one-digit numbers and get a / 10 - 1 + 9 = a / 10 + 8.

      → Reply