Trailing Digits

Question

https://www.acmicpc.net/problem/23204

I've solved a programming challenge where you need to count the occurrences of a specific digit at the end of the product of multiples of a given number within a certain range.

Description

A large shipment of doodads has just arrived, and each doodad has a suggested retail price of b cents. You’ve noticed that consumers are much more likely to purchase goods when most of the trailing digits are the same. For example, items are more likely to be priced at 99 cents rather than 57 cents. So to make your goods more appealing, you’ve decided to sell your goods in bundles. To make a bundle, you choose a positive integer k, and sell k doodads for k × b cents. With an appropriate choice of k you can have a more pleasing price. For example, selling 57-cent doodads in bundles of size 7 means that each bundle sells for 399 cents, which has two trailing 9s, rather than no trailing 9s of 57. This idea of trailing 9s can be generalized to any other trailing digit: bundles of 692 57-cent doodads sell for 39 444 cents (three trailing 4s) and bundles of one million doodads sell for 57 000 000 cents (six trailing 0s).

After a little thought, you realize that you do not want to make your bundles too large—not only can the price be excessive, but who really needs several million doodads? For any type of doodad, your marketing department has a maximum bundle price of a.

Given the price of a doodad, the desired trailing digit, and the maximum price of a bundle, write a program that optimizes the trailing digits.

Input

Input consists of a single line containing three integers b, d, and a, where b (1 ≤ b < \$10^6\$) is the price of a doodad in cents, d (0 ≤ d ≤ 9) is the desired trailing digit, and a (b ≤ a < \$10^{10,000}\$) is the maximum price of a bundle.

Output

Output the maximum number of consecutive occurrences of d that can appear at the end of a bundle price, given that the price of the bundle cannot exceed a.

sample input 1

57 9 1000

sample output 1

2

sample input 2

57 4 40000

sample output 2

3

sample input 3

57 4 39000 

sample output 3

2

code

def main(B,d,a):

    count=0
    max=0
    price=0
    i=1
    while price<a:
        price=B*i
        #print(price)
        #print(str(price))
        count=0


        for x in range(len(str(price))):

            if(str(price)[len(str(price))-1-x]==str(d) ):
                #print("price",str(price))
                count+=1
                #print(count)
            else:
                break

        if(max<count):
            #print("max",count)
            max=count
        i+=1

    print(max)

if __name__ == '__main__':
      main(57,9,1000)
      main(57,4,40000)
      main(57,4,39000 )

I know the code fits but I always exceed the time for the validation page. I could translate to C or c++ language but I receive any suggestions for improve logic or performance

I read it. I just suggest to think of another way to solve the problem. It is a mathematical question, not really a programming's one. (That kind of site is not good to teach programming).
– Jarod42
2023-11-17 16:07:13Z, License: CC BY-SA 4.0

How can I improve the performance?

code V.2

 def reverse_iteration(a, b, d):
    k = a // b  # Start with the maximum possible value of k
    # print(k)
    max_repetition = 0


    while k > 0:
        total_cost = k * b
        bestresult = len(total_cost.__str__())

        if total_cost <= a:
            print("k:", k, "Total Cost:", total_cost)
            # repetition = total_cost % b

            number_str = str(total_cost)
            count = 0
            last_digit = None

            for digit in reversed(number_str):
                if digit == str(d) and (digit == last_digit or last_digit is None):
                    count += 1
                    last_digit = digit
                else:
                    break
            # print(count)
            if count > max_repetition:
                max_repetition = count

            if count == bestresult \
                    or (int(total_cost.__str__()[0])<d and max_repetition==bestresult-1):
                k=-1
                continue

        k -= 1

    print(max_repetition)
if __name__ == '__main__':
  reverse_iteration(1000, 57, 9)
  reverse_iteration(1000, 57, 5)
  reverse_iteration(40000, 57, 4)
  reverse_iteration(39000, 57, 4)

code V.3 calculate relevant factor

def most_trailing_digits(a, b, d):
""" Print the maximal amount of trailing digits "trailing"
    a bundle of doodads priced "retail" may have up to
    a bundle price of "maximum".
"""
    k = a // b  # Start with the maximum possible value of k
    print("max iterations",k)

    max_repetition = 0
    result_with_max_repetition = None
    factors=[]
    reducer = []
    iterations=0
    #determine relevan factors
    for i in range(1, 11):  # Iterar sobre los números del 1 al 10
        resultado = b * i
        if resultado % 10 == d:  # Verificar si el último dígito es el buscado
            factors.append(i)
    print("factors",factors)
    print(k * b)
    for i in factors:
        if i != k % 10:
            if k % 10 <i:
                reducer.append((k % 10) + 10 - i)
            else:
                reducer.append((k % 10) - i)
        else:
            reducer.append(0)

    #last conection
    if reducer[0]==0 and len(reducer)>1:
        reducer[0]=(factors[len(factors)-1] - factors[0])
    #single reducer
    if len(reducer)==1:
        k=k-reducer[0]
        reducer[0]=10

    print("reducer",reducer)
    iteratorReducer=0
    while k > 0:
        iterations+=1
        # print(iterations)
        total_cost = k * b
        bestresult = len(total_cost.__str__())

        if total_cost <= a:
            print("k:", k, "Total Cost:", total_cost)
            # repetition = total_cost % b

            number_str = str(total_cost)
            count = 0
            last_digit = None

            for digit in reversed(number_str):
                if digit == str(d) and (digit == last_digit or last_digit is None):
                    count += 1
                    last_digit = digit
                else:
                    break
            # print(count)
            if count > max_repetition:
                max_repetition = count

            if count == bestresult \
                    or (int(total_cost.__str__()[0])<d and max_repetition==bestresult-1):
                k=-1
                continue

        iteratorReducer += 1
        currenreducer=0
        if len(reducer)==1:
            currenreducer=reducer[0]
        else:
            currenreducer=reducer[iteratorReducer % len(reducer)]

        k = k -currenreducer

    print("iterations",iterations)
    print(max_repetition)

## tests
most_trailing_digits(1000, 57, 9)
most_trailing_digits(1000, 57, 5)
most_trailing_digits(40000, 56, 4)
most_trailing_digits(39000, 57, 4)

Answer 1

Picture yourself coming back to "V1 code" a decade from now:
You can read it, you can run it.
Do you know what does, and to what end?

Name things for what they are good for.
price looks good to go.
In general, picking up terms from the "requirements description" makes it easier to communicate with the source of the requirements.
The names from the input description (B should be lowercase, too) don't suggest anything to me, so look at the introduction of the problem:
b might be retail, d trailing, and a maximum
- that retail and maximum are prices I'd put in the in-code documentation.
The advice from Style Guide for Python Code about name clashes is to append an underscore - not max but max_. (Then again, a lot of names would convey the same meaning and not clash with reserved words.)
The procedure deserves a name more telling than main() - for starters:

def most_trailing_digits(retail, trailing, maximum):
    """ Print the maximal amount of trailing digits "trailing"
        a bundle of doodads priced "retail" may have up to
        a bundle price of "maximum".
    """
    best, price = 0, 0
    i = 0  # trailing may be 0, and maximum as low as retail
    while price <= maximum:
        pass
    print(best)

You may notice differences in use of white-space - Starting out with Python, stick to the guide above.
One of the benefits of even a basic documentation string is being kept for introspection - try help(most_trailing_digits).
The difference in loop termination condition is to avoid a bug:
Bundle price may be maximum price of a bundle.
Python does not require parentheses around conditions.
While they don't interfere with compilers and interpreters, people may consider them unpythonic.
Conditions without parentheses may serve as a reminder of not coding in a C heritage language - for example, ++i is legal, but doesn't increment i.
pass does get used for I don't know better (yet). (And don't want to show more here - sort of ellipsis.)

    trailing = str(trailing)
    while price <= maximum:
        price = retail * i
        #print(price)
        count = 0
        
        for digit in reversed(str(price)):  # decimal, little endian
            if digit != trailing:
                break
            count += 1
        
        if best < count:
            best = count
            #print("max", best)
        
        i += 1
    
    print(best, "is the maximal number of trailing", trailing +
          "s in a bundle price for", retail,
          "cent doodads up to", maximum+".")

if __name__ == '__main__':
      most_trailing_digits(57,9,1000)
      most_trailing_digits(57,4,40000)
      most_trailing_digits(57,4,39000 )

(Ran out of steam)

Answer 2

finally I found a link with a lot of examples. I found trailingdigits.py with a much more elegant approach github.com/RussellDash332/kattis/blob/main/src/… and another webpage that shows more detail about the problem icpc.kattis.com/problems/trailingdigits?tab=submissions all credits and stars for the original repo

code from https://github.com/RussellDash332/kattis

# ©RussellDash332's LICENSE
# @ https://github.com/RussellDash332/kattis/blob/main/LICENSE

b, d, a = input().strip().split()
m = 0; n = 1; p = 1; b = int(b); d = int(d); best = 0

def gcd(a, b):
    while b: a, b = b, a % b
    return a

for l in range(len(a)): # O(log10 a)
    # 10**l * x + d * (10**l-1)//9 = 0 (mod k) for all k that divides b
    # p*x + d*m = 0 (mod b) -> need to find this in O(log2 b)
    # p*x = -d*m (mod b) but gcd(p, b) might not be 1
    g = gcd(p, b) # O(log b)
    if -d*m%b%g == 0:
        x = -d*m//g*pow(p//g, -1, b//g)%(b//g)
        if x == 0: x += b//g # edge case: b//g is optimal rather than b
        t = 10**len(str(x))
        while x < t:
            r = f'{x}{str(d)*l}'; l2 = l; x2 = x
            while x2 % 10 == d: x2 //= 10; l2 += 1 # edge case if x also ends with some d's
            if len(r) < len(a) or (len(r) == len(a) and r <= a): best = max(best, l2)
            x += b//g
    m += p; p *= 10; p %= b; m %= b
print(best)

licence

RussellDash332's LICENSE

improves

• calculate GCD: The Euclidean Algorithm Recall that the Greatest Common Divisor (GCD)
• Checks if the condition -d*m%b%g == 0 is satisfied. This condition is related to finding a solution to the modular equation \$p*x + d*m ≡ 0 (mod b)\$ where \$x\$ is the repeating part. This is still a mystery for me, how does it work?