wallcrawler's blog

How do you solve the "rational resistance" — 343A/344C problem on Codeforces?
By wallcrawler, history, 7 years ago, In English

I am not able to understand the editorial of the same. Please Help!! Link to the problem : http://mirror.codeforces.com/problemset/problem/343/A

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

When a > b, you can use floor(a / b) resistors consecutively connected, and now, you still need to obtain the fraction (a mod b) / b because:

floor(a / b) + (a mod b) / b = a / b

For example, 8 / 3 = 2 + 2 / 3.

So, the problem become to obtain the ratio 2 / 3. Now we have to obtain this ratio from the parallel property, because no consecutive resistors can make it. And as we can see from the statement, parallel connected resistors R1, R2, ... obtain one resistor with resistance with value equals to 1 / (1 / R1 + 1 / R2 + ...), and as this fraction shows, the denominator can be represented as several resistors consecutively connected to each other. So, the task return to be obtaining this sum 1 / R1 + 1 / R2 + ....

For that, we can rewrite the fraction 2 / 3 as 1 / (3 / 2), and then try to obtain 3 / 2 from consecutively connected resistors with the same way we used in the case of a > b above, and the solution goes recursively like that until the remaining fraction become 0.

This is my submission for this problem

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Don't know it'll be helpful or not but I found this link somewhat related to this problem.

https://math.stackexchange.com/questions/2160766/how-many-resistors-are-needed

→ Reply