http://www.spoj.com/problems/IGOR/
First of all we need to have a good look at constraints. Firstly, The value of the query can be up to 10^9 which tells us that we can't have a brute force solution passed. Secondly, the length of the given line is not going to be more than 14 so here is what I suggest. We can calculate all the possible lines, (they will be no more than 2^14) and then output the result. Then, just because there are 2^14 maximum possibilities and queries up to 10^9 we can say for sure that the sequence of +s and -s is going to repeat itself at some point, so we have to calculate the sequences first and stop the calculations until we reach a point where the new sequence we have got has already been gotten earlier. So how do we know which sequence we calculated fast? We can turn the sequence of +s and -s into a sequence of 1s and 0s and considering it us a binary number turn it into a decimal number and mark it as "visited". We will also need to keep the "time" , "time" tells us the time. Whenever we reached a number which was marked previously we stop our calculations . Here is what we will get in the end.
N1,N2,N3,N4,. . . . . . . .Nm
starting from a certain number R the number are going to repeat themselves, which means our sequence will have this look
N1,N2,... Nr, N(r+1)....Nm, Nr,N(r+1).....Nm and so on.
All that is left is to input the query time and find the right one and output it. Check the source code for some other details and better understanding.
First of all we need to have a good look at constraints. Firstly, The value of the query can be up to 10^9 which tells us that we can't have a brute force solution passed. Secondly, the length of the given line is not going to be more than 14 so here is what I suggest. We can calculate all the possible lines, (they will be no more than 2^14) and then output the result. Then, just because there are 2^14 maximum possibilities and queries up to 10^9 we can say for sure that the sequence of +s and -s is going to repeat itself at some point, so we have to calculate the sequences first and stop the calculations until we reach a point where the new sequence we have got has already been gotten earlier. So how do we know which sequence we calculated fast? We can turn the sequence of +s and -s into a sequence of 1s and 0s and considering it us a binary number turn it into a decimal number and mark it as "visited". We will also need to keep the "time" , "time" tells us the time. Whenever we reached a number which was marked previously we stop our calculations . Here is what we will get in the end.
N1,N2,N3,N4,. . . . . . . .Nm
starting from a certain number R the number are going to repeat themselves, which means our sequence will have this look
N1,N2,... Nr, N(r+1)....Nm, Nr,N(r+1).....Nm and so on.
All that is left is to input the query time and find the right one and output it. Check the source code for some other details and better understanding.
No comments:
Post a Comment