Blahfoo
BAN USERAssuming there exists one character in the string the removal of which turns string into palindrome, we can do as follows:
1. Keep two pointers front=0 and back=n-1.
2. while string[front++] == string[back--] continue;
3. if string[front+1, back] is palindrome then return string without character[front]
else return string without character[back]
Edit: based on gastonbm's reply, changed last step to check for palindrome.
Foo_function is monotonically increasing for t in [0, 10^18] because all coefficients are positive. Therefore there is at most one solution to the equation F(t) - K = 0 for t in [0, 10^18]
import sys
import math
file = open('input')
n = int(file.readline())
def polyvalAt(x):
return a*x*x*x + b*x*x + c*x + d
def dbydx_polyvalAt(x):
return 3*a*x*x + 2*b*x + c
for line in file:
if n == 0:
break
n = n - 1
a, b, c, d, k = map(float, line.split())
# transform F(t) = K to F(t) - K = 0
d = d - k
# if d > 0 then no solution exists
if d > 0:
print('Inv')
continue
mid = 0
while (1):
if abs(polyvalAt(mid)) > 0.000001:
mid = mid - polyvalAt(mid)/dbydx_polyvalAt(mid)
else:
break
print(int(mid))
I think what he meant was use linked lists which store
dynamically allocated character arrays. Each node holds
a character pointer and size of array.
Inserting in position i would be:
1. Mark size=i in first node.
2. Allocate node with pointer=input_string and size=strlen(input_string)
3. Allocate node with pointer=head->pointer+i and size
head_size-i
Concatenation is trivial i.e. head->next=target
@balaji
- Blahfoo June 05, 2014Read up on Newton raphson method which is a fast method of finding zeros of a polynomial. Of course, one can do it in a more usual bisection method similar to binary search, but this is probably faster.