Codeforces 732A Buy a Shovel Solution & Explanation

Difficulty : 800

Problem Description

Polycarp urgently needs a shovel! He comes to the shop and chooses an appropriate one. The shovel that Policarp chooses is sold for k burles. Assume that there is an unlimited number of such shovels in the shop.

In his pocket Polycarp has an unlimited number of “10-burle coins” and exactly one coin of r burles (1 ≤ r ≤ 9).

What is the minimum number of shovels Polycarp has to buy so that he can pay for the purchase without any change? It is obvious that he can pay for 10 shovels without any change (by paying the requied amount of 10-burle coins and not using the coin of r burles). But perhaps he can buy fewer shovels and pay without any change. Note that Polycarp should buy at least one shovel.

Input

The single line of input contains two integers k and r (1 ≤ k ≤ 1000, 1 ≤ r ≤ 9) — the price of one shovel and the denomination of the coin in Polycarp’s pocket that is different from “10-burle coins”.

Remember that he has an unlimited number of coins in the denomination of 10, that is, Polycarp has enough money to buy any number of shovels.

Output

Print the required minimum number of shovels Polycarp has to buy so that he can pay for them without any change.

Examples

Note

In the first example Polycarp can buy 9 shovels and pay 9·117 = 1053 burles. Indeed, he can pay this sum by using 10-burle coins and one 3-burle coin. He can’t buy fewer shovels without any change.

In the second example it is enough for Polycarp to buy one shovel.

In the third example Polycarp should buy two shovels and pay 2·15 = 30 burles. It is obvious that he can pay this sum without any change.

Solution

One way to solve this problem is to enumerate the quantity of shovels purchased starting from 1, up to a maximum of 10, ensuring that the total price is a multiple of 10 or ends with the denomination ‘r’. Then, comparing the quantity obtained with 10, and choosing the smaller one as the answer.

The maximum quantity considered is 10 because in this way, it’s guaranteed that a multiple of 10 can always be achieved.

This approach can be implemented using a simple loop. For each quantity ‘i’, calculate the total price (i * k), check if it meets the criteria, update the answer accordingly, and finally output the answer.

C# Solution

Solution1

string[] arr = Console.ReadLine().Split(" ");
int k = int.Parse(arr[0]);
int r = int.Parse(arr[1]);

for(int i=1; i<=10; i++){
    var tmp = k*i;
    if(tmp%10==0 || tmp%10==r){
        Console.WriteLine(i);
        break;
    }
}

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks you~~

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know !!

The problem link : Problem – 732A – Codeforces

Random Codeforces Posts