**Problem:**

If two possible points in a game is p and q, what is the largest impossible score of the game which can't be achieved? Or it can't be determined? In other words, for integers p, q ≥ 0, what is the maximum number m which can't be written as a linear combination of p, q, i.e. px + qy, where, x, y ≥ 0.

**Solution:**

The score can only be determined when p and q are co-primes, i.e. g = GCD(a,b) = 1. Otherwise, we can only make the multiples of g and the remaining numbers can't be made which means the maximum number can't be determined, or infinite! This also covers the case if exactly one of p or q is 0.

One other required condition is p,q > 1. If anyone of p or q is 1, there is no such score which can't be achieved, i.e. answer will be 0. If p and q both are 0, we can't even make any score...

Now, we can arrange the numbers from 0 to p*q-1 in a rectangular array as follows:

0 1 ....... q-1

q q+1 ....... 2q-1

... ... ....... ...

... ... ....... ...

(p-1)q (p-1)(q-1) ....... pq-1

For example, if p = 3 and q = 7, we have the following table:

(0) 1 2 (3) 4 5 (6)

7 8 (9) 10 11 (12) 13

14 (15) 16 17 (18) 19 20

We have circled the multiples of p in the above table and claim these observations:

**There will be q circled numbers.**As we have exactly p numbers in each of q columns, so each column will have exactly one circled number, i.e. multiple of p, which implies, there will be a total of q circled number in this table.**No two circled numbers are in same same column and there will be only one circled number in any column.**For the same reason stated above, exactly one circled number in each column.**Any circled number is possible.**This is trivial, because, the circled numbers are multiple of one of the two given numbers, i.e. in the form p*x + q*0 or p*0 + q*x.**Any number below the circled one in the same column is possible.**We have seen any circled number is possible. A circled number is the first multiple of p in the respective column, i.e. n*p, where n ≥1, so the following numbers in the column will be: n*p + q, n*p + 2*q. n*p + 3*q, ... ... ... which are always possible.**Any number above the circled one in the same column is impossible.**This is also explained in the previous step. As any circled number in a column is the first one which is a multiple of one element, the number above this one will be neither the multiple of any of the two numbers. So it is impossible.**Any number ≥ p*q is possible.**As we complete p rows of the table with q columns, we already have one circled number in each column, so, any number > p*q-1 (i.e. the last element of the table) will be surely following any of the q circled numbers, so any number starting from the p+1^{th}row, starting from p*q will be possible.

Now considering all these observations, we can see that, largest impossible number is the number just above the last circled number. The last circled number is p*q-p, i.e. 21-3 = 18 and number above it is (p*q-p)-q, i.e. 18-7 = 11. So in general, largest impossible number is:

**p*q - p - q**.

**Conclusion:**

If you are given p, q :: two positive numbers, the largest number, m, which can't be expressed as a linear combination of p, q i.e. in the form px + qy, where x and y are two non-negative numbers, is p * q - p - q, when p, q > 1 and GCD(p, q) is 1 i.e. p, q are co-primes.

any uva or spoj problem regarading this concept??

ReplyDeletehttp://www.codechef.com/problems/CHEFLUCK

Delete