k790alex's blog

Round #231 (Div. 2) — B. Very Beautiful Number
By k790alex, 11 years ago, In English

I participated in this contest but I could'n be able to solve this task: 394B - Very Beautiful Number

I really want to know a method for solving it but like this contest was held in a black day (a day without data recovered) for codeforces, I couldn't find editorial.

I saw some accepted solutions but I would like to see a explication with more details.

I only could think in a solution using divisivility rules for 1 to 9 but I couldn't complete at all.

I think my idea have to many work for a div2 problem B, then if someone could explain me an easy solution, i would be grateful.

Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

So I haven't actually coded a solution to this problem, but I did some math and this is what I got:

Let p be the number of digits and c be the factor that it's multiplied by when the last digit is moved.

Now, we will define some quantities we want to solve for (currently unknown). Let b = the last digit of our answer. (This will be 7 in sample case 1) Let x = the concatenation of all other digits in our answer. (This will be 14258 in sample case 1)

Now, our original number is simply n1 = 10*x + b. Our number after the last digit is moved is n2 = x + b*(10^(p-1))

And by the desired property of the desired answer, n2 = n1 * c.

So, x + b*(10^(p-1)) = c*(10*x + b) Simplifying this, we get: x*(10*c — 1) = b * (10^(p-1) — c)

Now we just have to brute force over b (since it can only go up to 9 because it's one digit), and verify which ones produce an integer value of x of the correct length.

Hopefully this makes sense. :)

→ Reply