-
-
Save greenkey/1fd7a44c0b110ec9cd6f69b99b000adf to your computer and use it in GitHub Desktop.
| #! /usr/bin/env python | |
| import sys | |
| def solve(line): | |
| pancake_row = [p == '+' for p in line.split()[0]] | |
| pan_size = int(line.split()[1]) | |
| flips = 0 | |
| i = 0 | |
| while i < (len(pancake_row) - pan_size + 1): | |
| if not pancake_row[i]: | |
| for j in range(i,i + pan_size): | |
| pancake_row[j] = not pancake_row[j] | |
| flips += 1 | |
| i += 1 | |
| if all(pancake_row): | |
| return flips | |
| return 'IMPOSSIBLE' | |
| def progress(s): | |
| print("%-80s\r" % s, file=sys.stderr, end='') | |
| if __name__ == '__main__': | |
| if len(sys.argv) > 1: | |
| inputfile = sys.argv[1] | |
| else: | |
| inputfile = 'input.test' | |
| with open(inputfile) as f: | |
| cases = int(f.readline()) | |
| for i in range(cases): | |
| progress(i) | |
| line = f.readline().strip() | |
| print('Case #%d: %s' % (i+1, solve(line))) |
You don't totally understand the question well. This is a state transfer machine problem. Naive solution consists of Wide First Search(wfs) and mathematical branches trimming. You loop though the array from left to right? I don't believe this is a accept answer.
here is simple mathematics about trmming:
K * flips = x* 2p + y * (2q-1). Where x represents the number of '+' in initial state and y represents the number of '-'. A Filter can be summarised as
int
math_rule(const char* arr, int l, int K){
int i, x=0, y=0;
for (i=0; i < l; i++) {
if (arr[i] == '+') {
x += 1;
} else
if (arr[i] == '-') {
y += 1;
}
}
// K*n = x*2*k1 + y*(2*k2 - 1)
if (x == y and K % 2 == 0 and x % K != 0) {
return IMPOSSIBLE;
}
return 0;
}
each state can represented by a bit representation or an unique integer. I am serious. Google's problems need to you to think twice before coding.
Consider the case ++-+-++ 3
i don't see any possible solution for this.
here x=5,y=2,k=3.
here x!=y, k%2!=0
So by your logic, its not impossible.
Could you please explain how to flip all values?
Genius!