You are not logged in.
Pages: 1
Today they gave us in the LCPC training this exercise:
We define a stable string:
1- the string is {}
2- if S is a stable string then {S} is also stable
3- if S and T are stable strings then TS is also stable
examples of stable strings:
{}, {}{}, {{}{}}...
examples of unstable strings:
}{, }{{{...
Given a string of size N 2<=N<=2000 (N is given even)
find the least operations to do on a string to make it stable:
the only operation allowed is to change { to } or vice-versa
Examples:
{{ result: 1
}{ result: 2
{{{} result:1
I will post my solution soon
def replacements(s):
t = s.replace("{}","")
while(t != s):
s = t
t = s.replace("{}","")
return len(t)/2
Ah bummer. Found something wrong with it.
[edit]Hoping the fuck-ups have ceased.
def replacements(s):
t = s.replace("{}","")
while(t != s):
s = t
t = s.replace("{}","")
count = 0
s = t.lstrip("}")
count += (len(t)-len(s))/2 + (len(t)-len(s))%2
t = s.rstrip("{")
count += (len(s)-len(t))/2 + (len(s)-len(t))%2
return count + len([x for x in t if x == "{"]) - len(t)/2
print replacements("}{}}}{{{")
Last edited by arithma (September 6 2012)
mine is similar to arithma's code
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s="}{{}";
int total=0;
int b=s.length()-1;
for(int i=0;i<b;i++)
{
if(s[0]=='}')
{
s[0]='{';
total++;
}
if(s[s.length()-1]=='{')
{
s[s.length()-1]='}';
total++;
}
if(s.substr(i,2)=="{}")
{
s=s.substr(0,i)+s.substr(i+2);
if(i==0)
i=-1;
else
i-=2;
}
b=s.length()-1;
}
int size=s.length();
cout << (total+size/2);
return 0;
}
Pages: 1