3
\$\begingroup\$

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)
\$\endgroup\$
11
  • 1
    \$\begingroup\$ Welcome to Code Review! We need a correct implementation to review. This incorrect code is off-topic. The range is nonsensical, and you're counting all, rather than trailing, occurrences of d. The puzzle author was hoping to get you to reason about e.g. k * b % 100 == 99 or k * b % 1000 == 777. And you don't need all of b for that -- b % 100 or b % 1000 could suffice. \$\endgroup\$
    – J_H
    Commented Nov 17, 2023 at 17:49
  • 1
    \$\begingroup\$ Have another look at "long multiplication": Which "factor 2 digits" have influence on which product digit? \$\endgroup\$
    – greybeard
    Commented Nov 18, 2023 at 13:49
  • 1
    \$\begingroup\$ Start with the least significant digit of the product: the only factor digit "going there" are the least significant digits of both factors. For target 9, 7*7 fits the bill, only; for 4, 2*7. Similar for the tens digit: it is fully determined by the factor's value %100 (see J_H's comment) (Looking closer, p₁p₀ is 10₁₀(a₀b₁+a₁b₀)+a₀b₀.) And so on ... \$\endgroup\$
    – greybeard
    Commented Nov 20, 2023 at 18:35
  • 1
    \$\begingroup\$ Go stare at the 10 × 10 multiplication table that everyone uses in grade school. Now pick a target d like 6, or 7. Ask yourself "what is the infinite set of positive integer pairs that multiply to end with d ?" Now write code which explores a portion of that set. Having solved the one-digit case, can you use that to get to the two-digit case? \$\endgroup\$
    – J_H
    Commented Nov 21, 2023 at 3:29
  • 1
    \$\begingroup\$ In V3 I see provisions for not trying factors unfit to produce one required trailing digit. For another CR question: what about the tens digit? There may be up to 10000 digits: How not to overtax average patience? \$\endgroup\$
    – greybeard
    Commented Nov 21, 2023 at 12:27

2 Answers 2

2
\$\begingroup\$

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)

\$\endgroup\$
1
1
\$\begingroup\$

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?
\$\endgroup\$
3
  • 1
    \$\begingroup\$ This answer is being discussed on meta. \$\endgroup\$ Commented Nov 21, 2023 at 21:57
  • \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ for avoid the close of question could i delete the answer? the research was interesting \$\endgroup\$
    – qleoz12
    Commented Nov 21, 2023 at 22:06
  • 1
    \$\begingroup\$ You could delete the question, however you would lose out on the reputation from the upvote, and it doesn't make the question off topic. I would suggest waiting to act until there is a consensus on the meta discussion. \$\endgroup\$ Commented Nov 22, 2023 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.