Блог пользователя tamojit9

need explanation of the following logic for problem 204A(round 129 div 1)
Автор tamojit9, 14 лет назад, По-английски 
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;
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
14 лет назад, скрыть # |
← Rev. 6  
Проголосовать: нравится +1 Проголосовать: не нравится

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++;
→ Ответить
  • »
    »
    14 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    "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??

    → Ответить
    • »
      »
      »
      14 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить