Connection Status:
Competition Arena > QuickCount

QuickCount

SRM 134 · 2003-02-08 · by LunaticFringe

SRM 134 · 2003-02-08 · by LunaticFringe
Class Name: QuickCount
Return Type: int[]
Method Name: howMany
Arg Types: (int, int, int)
Problem Statement

Problem Statement

Here is an algorithm for counting quickly: instead of saying a number, simply say the rightmost non-zero digit of that number. So for example, 13700 becomes just 7 (assuming you are counting in base 10).

Given two base-10 integers, first and last, as well as a number base, numBase, return a int[] containing the number of times you would say each digit if you were to count from first to last in base numBase. The int[] should contain exactly (numBase - 1) elements; the first element is the number of times you say the digit 1, the second element is how many times you say the digit 2, etc.

Constraints

  • first will be between 1 and 2000000000, inclusive.
  • last will be between 1 and 2000000000, inclusive.
  • first will be less than or equal to last.
  • numBase will be between 2 and 10, inclusive.
Examples
0)
1
9
10
Returns: { 1,  1,  1,  1,  1,  1,  1,  1,  1 }

Each digit from 1 to 9 is said exactly once.

1)
1
20
10
Returns: { 3,  3,  2,  2,  2,  2,  2,  2,  2 }

The numbers 1 through 9 correspond to the digits 1 through 9, respectively. The numbers 11 through 19 correspond to the digits 1 through 9, respectively. The number 10 becomes the digit 1, and the number 20 becomes the digit 2. In total, digits 1 and 2 are said three times each, and all other digits are said twice.

2)
16
31
4
Returns: { 6,  5,  5 }

The counting is now being done in base four. Here is 16 through 31 in base four (note that this table uses HTML, and will not look correct with plaintext plugins): 1610 = 1004 � � � � � � � � 2010 = 1104 � � � � � � � � 2410 = 1204 � � � � � � � � 2810 = 1304 1710 = 1014 � � � � � � � � 2110 = 1114 � � � � � � � � 2510 = 1214 � � � � � � � � 2910 = 1314 1810 = 1024 � � � � � � � � 2210 = 1124 � � � � � � � � 2610 = 1224 � � � � � � � � 3010 = 1324 1910 = 1034 � � � � � � � � 2310 = 1134 � � � � � � � � 2710 = 1234 � � � � � � � � 3110 = 1334 The base four numbers 100, 101, 110, 111, 121, and 131 will all become the digit 1. The numbers 102, 112, 120, 122, and 132 will become the digit 2. The numbers 103, 113, 123, 130, and 133 will become the digit 3. Therefore, the digit 1 will be said 6 times, and the digits 2 and 3 will be said 5 times each.�

3)
1
2000000000
2
Returns: { 2000000000 }

In base 2, everything will be spoken using the digit '1', since every positive number is a series of only zeroes and ones when converted to binary.

4)
1
1
2
Returns: { 1 }

Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class QuickCount with a public method vector<int> howMany(int first, int last, int numBase) · 56 test cases · 2 s / 256 MB per case

Submitting as anonymous