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)

• J_H: 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.
• greybeard: Have another look at "long multiplication": Which "factor 2 digits" have influence on which product digit?
• greybeard: 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, p1p0 is 1010(a0b1+a1b0)+a0b0.) And so on ...
• J_H: 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?
• greybeard: 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?

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)

• greybeard: Please heed What should I do when someone answers my question?

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?

• Sᴀᴍ Onᴇᴌᴀ: This answer is being discussed on meta.
• qleoz12: @SᴀᴍOnᴇᴌᴀ for avoid the close of question could i delete the answer? the research was interesting
• Sᴀᴍ Onᴇᴌᴀ: 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.