#include <iostream>
#include <string>
#include <vector>
#include <climits>
using namespace std;
int minMutations( string alpha) {
int n = alpha.size ( ) ;
vector< vector< int >> dp( n + 1 , vector< int > ( 2 , INT_MAX ) ) ; // dp[i][j]: min mutations to convert alpha[0...i-1] to omega, considering mutation j at position i
// Base case: converting empty string to omega requires 0 mutations
dp[ 0 ] [ 0 ] = dp[ 0 ] [ 1 ] = 0 ;
// Dynamic programming to fill the dp table
for ( int i = 1 ; i <= n; ++ i) {
if ( alpha[ i - 1 ] == 'A' ) {
dp[ i] [ 0 ] = min( dp[ i - 1 ] [ 0 ] , dp[ i - 1 ] [ 1 ] + 1 ) ;
dp[ i] [ 1 ] = min( dp[ i - 1 ] [ 0 ] + 1 , dp[ i - 1 ] [ 1 ] + 1 ) ;
} else {
dp[ i] [ 0 ] = min( dp[ i - 1 ] [ 0 ] + 1 , dp[ i - 1 ] [ 1 ] ) ;
dp[ i] [ 1 ] = min( dp[ i - 1 ] [ 0 ] + 1 , dp[ i - 1 ] [ 1 ] + 1 ) ;
}
}
// The minimum mutations required to convert alpha to omega is the minimum value in the last row of dp table
return min( dp[ n] [ 0 ] , dp[ n] [ 1 ] ) ;
}
int main( ) {
string alpha;
cout << "Enter the DNA structure alpha: " ;
cin >> alpha;
int result = minMutations( alpha) ;
if ( result == INT_MAX ) {
cout << "Omega cannot be synthesized from alpha." ;
} else {
cout << "Minimum mutations required: " << result;
}
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y2xpbWl0cz4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWluTXV0YXRpb25zKHN0cmluZyBhbHBoYSkgewogICAgaW50IG4gPSBhbHBoYS5zaXplKCk7CiAgICB2ZWN0b3I8dmVjdG9yPGludD4+IGRwKG4gKyAxLCB2ZWN0b3I8aW50PigyLCBJTlRfTUFYKSk7IC8vIGRwW2ldW2pdOiBtaW4gbXV0YXRpb25zIHRvIGNvbnZlcnQgYWxwaGFbMC4uLmktMV0gdG8gb21lZ2EsIGNvbnNpZGVyaW5nIG11dGF0aW9uIGogYXQgcG9zaXRpb24gaQoKICAgIC8vIEJhc2UgY2FzZTogY29udmVydGluZyBlbXB0eSBzdHJpbmcgdG8gb21lZ2EgcmVxdWlyZXMgMCBtdXRhdGlvbnMKICAgIGRwWzBdWzBdID0gZHBbMF1bMV0gPSAwOwoKICAgIC8vIER5bmFtaWMgcHJvZ3JhbW1pbmcgdG8gZmlsbCB0aGUgZHAgdGFibGUKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47ICsraSkgewogICAgICAgIGlmIChhbHBoYVtpIC0gMV0gPT0gJ0EnKSB7CiAgICAgICAgICAgIGRwW2ldWzBdID0gbWluKGRwW2kgLSAxXVswXSwgZHBbaSAtIDFdWzFdICsgMSk7CiAgICAgICAgICAgIGRwW2ldWzFdID0gbWluKGRwW2kgLSAxXVswXSArIDEsIGRwW2kgLSAxXVsxXSArIDEpOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGRwW2ldWzBdID0gbWluKGRwW2kgLSAxXVswXSArIDEsIGRwW2kgLSAxXVsxXSk7CiAgICAgICAgICAgIGRwW2ldWzFdID0gbWluKGRwW2kgLSAxXVswXSArIDEsIGRwW2kgLSAxXVsxXSArIDEpOwogICAgICAgIH0KICAgIH0KCiAgICAvLyBUaGUgbWluaW11bSBtdXRhdGlvbnMgcmVxdWlyZWQgdG8gY29udmVydCBhbHBoYSB0byBvbWVnYSBpcyB0aGUgbWluaW11bSB2YWx1ZSBpbiB0aGUgbGFzdCByb3cgb2YgZHAgdGFibGUKICAgIHJldHVybiBtaW4oZHBbbl1bMF0sIGRwW25dWzFdKTsKfQoKaW50IG1haW4oKSB7CiAgICBzdHJpbmcgYWxwaGE7CiAgICBjb3V0IDw8ICJFbnRlciB0aGUgRE5BIHN0cnVjdHVyZSBhbHBoYTogIjsKICAgIGNpbiA+PiBhbHBoYTsKCiAgICBpbnQgcmVzdWx0ID0gbWluTXV0YXRpb25zKGFscGhhKTsKICAgIGlmIChyZXN1bHQgPT0gSU5UX01BWCkgewogICAgICAgIGNvdXQgPDwgIk9tZWdhIGNhbm5vdCBiZSBzeW50aGVzaXplZCBmcm9tIGFscGhhLiI7CiAgICB9IGVsc2UgewogICAgICAgIGNvdXQgPDwgIk1pbmltdW0gbXV0YXRpb25zIHJlcXVpcmVkOiAiIDw8IHJlc3VsdDsKICAgIH0KCiAgICByZXR1cm4gMDsKfQo=