# 某島

… : "…アッカリ～ン . .. . " .. .
November 16, 2012

## Rosalind 1

### 字元串處理、正則表達式

s = gets
print [s.count('A'), s.count('C'), s.count('G'), s.count('T')] * ' '

print gets.gsub('T','U')

s = gets
s.gsub!('A','a'); s.gsub!('T','A'); s.gsub!('a','T')
s.gsub!('C','c'); s.gsub!('G','C'); s.gsub!('c','G')
print s.reverse

$buf = gets() def gc(s) gcc = 0.0 s.each_char{|si| gcc += 1 if (si == 'G' || si == 'C') } return gcc / s.size end def getdna() dna = gets().chomp dna +=$buf.chomp while ($buf = gets()) && ($buf[0] != '>')
return dna
end

dna = "$" while$buf do
_id, _dna = $buf[1..-1], getdna() id, dna = _id, _dna if gc(_dna) > gc(dna) end puts id print gc(dna) * 100, '%'  s = gets.chomp; t = gets.chomp; dist = 0 0.upto(s.size-1){|i| dist += 1 if s[i] != t[i] } p dist  s = gets.chomp; n = s.length; a = Array.new(n){Hash.new(0)} begin 0.upto(n-1){|i| a[i][s[i]] += 1 } end while s = gets def scan(a, n, ch) print ch,':' 0.upto(n-1){|i| print ' ', a[i][ch] } puts end def common(ai) return 'A' if (ai['A'] >= ai['C'] && ai['A'] >= ai['G'] && ai['A'] >= ai['T']) return 'C' if (ai['C'] >= ai['A'] && ai['C'] >= ai['G'] && ai['C'] >= ai['T']) return 'G' if (ai['G'] >= ai['A'] && ai['G'] >= ai['C'] && ai['G'] >= ai['T']) return 'T' end a.each{|ai| #ai.sort_by{|key, value| value} #print ai.begin().value print common(ai) } puts scan(a, n, 'A'); scan(a, n, 'C'); scan(a, n, 'G'); scan(a, n, 'T')  /* .................................................................................................................................. */ const int N = 1009; pair<string, string> A[N]; int n; bool adj(string a, string b, int k){ if (a == b) return false; REP(i, k) if (a[SZ(a)-k+i] != b[i]) return false; return true; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif string id, dna; cin >> id; while (id[0] == '>'){ ERS(id, 0), A[n].fi = id, CLR(dna); while (cin >> id && id[0] != '>') dna += id; A[n++].se = dna; } REP_2(i, j, n, n) if (adj(A[i].se, A[j].se, 3)){ cout << A[i].fi << " " << A[j].fi << endl; } }  dict = { 'UCA' => 'S', # Serine 'UCC' => 'S', # Serine 'UCG' => 'S', # Serine 'UCU' => 'S', # Serine 'UUC' => 'F', # Phenylalanine 'UUU' => 'F', # Phenylalanine 'UUA' => 'L', # Leucine 'UUG' => 'L', # Leucine 'UAC' => 'Y', # Uyrosine 'UAU' => 'Y', # Uyrosine 'UAA' => '_', # Stop 'UAG' => '_', # Stop 'UGC' => 'C', # Cysteine 'UGU' => 'C', # Cysteine 'UGA' => '_', # Stop 'UGG' => 'W', # Uryptophan 'CUA' => 'L', # Leucine 'CUC' => 'L', # Leucine 'CUG' => 'L', # Leucine 'CUU' => 'L', # Leucine 'CCA' => 'P', # Proline 'CCC' => 'P', # Proline 'CCG' => 'P', # Proline 'CCU' => 'P', # Proline 'CAC' => 'H', # Histidine 'CAU' => 'H', # Histidine 'CAA' => 'Q', # Glutamine 'CAG' => 'Q', # Glutamine 'CGA' => 'R', # Arginine 'CGC' => 'R', # Arginine 'CGG' => 'R', # Arginine 'CGU' => 'R', # Arginine 'AUA' => 'I', # Isoleucine 'AUC' => 'I', # Isoleucine 'AUU' => 'I', # Isoleucine 'AUG' => 'M', # Methionine 'ACA' => 'T', # Uhreonine 'ACC' => 'T', # Uhreonine 'ACG' => 'T', # Uhreonine 'ACU' => 'T', # Uhreonine 'AAC' => 'N', # Asparagine 'AAU' => 'N', # Asparagine 'AAA' => 'K', # Lysine 'AAG' => 'K', # Lysine 'AGC' => 'S', # Serine 'AGU' => 'S', # Serine 'AGA' => 'R', # Arginine 'AGG' => 'R', # Arginine 'GUA' => 'V', # Valine 'GUC' => 'V', # Valine 'GUG' => 'V', # Valine 'GUU' => 'V', # Valine 'GCA' => 'A', # Alanine 'GCC' => 'A', # Alanine 'GCG' => 'A', # Alanine 'GCU' => 'A', # Alanine 'GAC' => 'D', # Aspartic Acid 'GAU' => 'D', # Aspartic Acid 'GAA' => 'E', # Glutamic Acid 'GAG' => 'E', # Glutamic Acid 'GGA' => 'G', # Glycine 'GGC' => 'G', # Glycine 'GGG' => 'G', # Glycine 'GGU' => 'G' # Glycine }; mRNA = gets.chomp puts mRNA.gsub(/\w{3}/).each(&dict.method(:[]))[0..-1].gsub(/_.*/, '')  dict = { 'TCA' => 'S', # Serine 'TCC' => 'S', # Serine 'TCG' => 'S', # Serine 'TCT' => 'S', # Serine 'TTC' => 'F', # Phenylalanine 'TTT' => 'F', # Phenylalanine 'TTA' => 'L', # Leucine 'TTG' => 'L', # Leucine 'TAC' => 'Y', # Tyrosine 'TAT' => 'Y', # Tyrosine 'TAA' => '_', # Stop 'TAG' => '_', # Stop 'TGC' => 'C', # Cysteine 'TGT' => 'C', # Cysteine 'TGA' => '_', # Stop 'TGG' => 'W', # Tryptophan 'CTA' => 'L', # Leucine 'CTC' => 'L', # Leucine 'CTG' => 'L', # Leucine 'CTT' => 'L', # Leucine 'CCA' => 'P', # Proline 'CCC' => 'P', # Proline 'CCG' => 'P', # Proline 'CCT' => 'P', # Proline 'CAC' => 'H', # Histidine 'CAT' => 'H', # Histidine 'CAA' => 'Q', # Glutamine 'CAG' => 'Q', # Glutamine 'CGA' => 'R', # Arginine 'CGC' => 'R', # Arginine 'CGG' => 'R', # Arginine 'CGT' => 'R', # Arginine 'ATA' => 'I', # Isoleucine 'ATC' => 'I', # Isoleucine 'ATT' => 'I', # Isoleucine 'ATG' => 'M', # Methionine 'ACA' => 'T', # Threonine 'ACC' => 'T', # Threonine 'ACG' => 'T', # Threonine 'ACT' => 'T', # Threonine 'AAC' => 'N', # Asparagine 'AAT' => 'N', # Asparagine 'AAA' => 'K', # Lysine 'AAG' => 'K', # Lysine 'AGC' => 'S', # Serine 'AGT' => 'S', # Serine 'AGA' => 'R', # Arginine 'AGG' => 'R', # Arginine 'GTA' => 'V', # Valine 'GTC' => 'V', # Valine 'GTG' => 'V', # Valine 'GTT' => 'V', # Valine 'GCA' => 'A', # Alanine 'GCC' => 'A', # Alanine 'GCG' => 'A', # Alanine 'GCT' => 'A', # Alanine 'GAC' => 'D', # Aspartic Acid 'GAT' => 'D', # Aspartic Acid 'GAA' => 'E', # Glutamic Acid 'GAG' => 'E', # Glutamic Acid 'GGA' => 'G', # Glycine 'GGC' => 'G', # Glycine 'GGG' => 'G', # Glycine 'GGT' => 'G' # Glycine }; dna = gets.chomp while exon = gets do dna.gsub!(exon.chomp, '') end puts dna.gsub(/\w{3}/).each(&dict.method(:[]))[0..-1].gsub(/_.*/, '')  s = gets.chomp; n = s.length def cp(a, b) return a == 'G' && b == 'C' || a == 'C' && b == 'G' || a == 'A' && b == 'T' || a == 'T' && b == 'A' end def test(s) n = s.length 0.upto(n/2){|i| return false if !cp(s[i], s[n-1-i]) } return true end 4.upto(8){|len| next if len.odd? 0.upto(n-len){|l| r = l + len - 1 print l+1, ' ', len, "\n" if (test(s[l..r])) } }  ### 概率 I =->{gets.split.map &:to_f} I[].each{|ai| p (ai**2 + (1-ai)**2) / 2 }  I =->{gets.split.map &:to_f} m, n = I[] I[].each{|ai| p (n - m + 1) * ((ai**2 + (1-ai)**2) / 2) ** m }  ### 字元串匹配 T = gets().chomp P = gets().chomp Tn, Pn = T.length, P.length Pi = []; Pi[0] = j = -1 0.upto(Pn-1){|i| j = Pi[j] while (j >= 0 && P[i] != P[j]) i += 1; j += 1; Pi[i] = P[i] == P[j] ? Pi[j] : j } j = 0 0.upto(Tn-1){|i| j = Pi[j] while (j >= 0 && T[i] != P[j]) i += 1; j += 1; p i-Pn+1 if j == Pn }  P = gets().chomp + '$'
Pn = P.length

Pi = []; Pi[0], Pi[1], i, j = -1, 0, 2, 0

while (i < Pn) do
if (P[i-1] == P[j]) then
j +=1; Pi[i] = j; i += 1
else
if (j > 0) then
j = Pi[j]
else
Pi[i] = 0; i += 1
end
end
end

puts Pi[1..-1]*' '

s = gets.chomp
t = gets.chomp

i = 0; t.each_char{|ti|
i += 1 while s[i] != ti; i += 1;
p i
}

/* .................................................................................................................................. */

const int N = 1009;

string S[N]; int dp[N][N];
int n;

void check(string s){
FOR(i, 1, n) if (S[i].find(s) == string::npos) return;
OT(s), exit(0);
}

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

string s; while (cin >> s){
S[n++] = s;
}

FOR(i, 1, n) if (SZ(S[i]) < SZ(S[0])) swap(S[0], S[i]);

int n0 = SZ(S[0]); DWN(len, n0-1, 0){
REP(i, n0-len){
s = S[0].substr(i, len);
check(s);
}
}
}


### 生成排列、組合

/* .................................................................................................................................. */

const int N = 10;
int A[N];

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

int n, f = 1; REP_1_C(i, RD(n)) A[i] = i, f *= i;

printf("%d\n", f); DO(f){
REP_1(i, n) OT(A[i]);
next_permutation(A + 1, A + n + 1);
puts("");
}
}

/* .................................................................................................................................. */

const int N = 10;
int A[N];

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

int n, f = 1; REP_1_C(i, RD(n)) A[i] = i, f *= i;
printf("%d\n", f*_1(n)); DO(f){
REP(s, _1(n)){
REP_1(j, n){
if (!_1(s, (n-j))) putchar('-');
OT(A[j]);
}
puts("");
}
next_permutation(A + 1, A + n + 1);
}
}

/* .................................................................................................................................. */

const int N = 10;
char S[N]; int A[N];
int n; LL k;

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

char str[100]; gets(str);
REP_C(i, strlen(str)) if (str[i] != ' ') S[n++] = str[i];
RD(k); DO(pow(n, k)){
DWN(i, k, 0) putchar(S[A[i]]); puts("");
A[0]++; for (int i=0;A[i]==n;A[i]=0,++A[++i]);
}
}

/* .................................................................................................................................. */

const int N = 15;

char C[N]; int A[N];
int n, k;

void dfs(int dep = 0){
if (dep){
REP(i, dep) putchar(i[A][C]);
puts("");
}

if (dep == k) return;
REP(i, n) A[dep]=i, dfs(dep+1);
}

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

char str[109]; REP_C(i, strlen(gets(str))) if (str[i] != ' ')
C[n++] = str[i];
RD(k);

dfs();
}


### 搜索

/* .................................................................................................................................. */

const int F[11] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
const int N = 10, L = 3628800;
int n = 10;

int D[L]; int a[N], st, ed; bool c[N];

int encode(){ // Cantor
int x = 0; REP(i, n){
int t = 0; FOR(j, i+1, n)
if (a[i]>a[j]) ++t;
x = x * (n-i) + t;
}
return x;
}

void decode(int x){
RST(a, c); REP(i, n){
while (i[a]) ++a[i];
while (x >= F[n-i-1]){
x -= F[n-i-1]; ++a[i];
while (i[a]) ++a[i];
}
i[a] = true;
}
}

void rev(int l, int r){
REP(i, (r - l + 1) / 2)
swap(a[l+i], a[r-i]);
}

int Q[L], cz, op; int bfs(){
if (st == ed) return 0;
Q[cz = 0] = st, op = 1;
RST(D); D[st] = 1;
while (cz < op){
int u = Q[cz++]; decode(u);
FOR(len, 1, n){
REP(l, n - len){
int r = l + len; rev(l, r); int v = encode(); rev(l, r);
if (D[v]) continue;
if (v == ed) return D[u];
Q[op++] = v;
D[v] = D[u] + 1;
}
}
}
return -1;
}

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

while (~scanf("%d", &a[0])){
FOR(i, 1, n) --RD(a[i]); st = encode();
REP(i, n) --RD(a[i]); ed = encode();
OT(bfs());
}
}

/* .................................................................................................................................. */

template<class T1, class T2> ostream& operator <<(ostream& cout, const pair<T1, T2> &rhs){
cout << rhs.fi+1 << " " << rhs.se+1;
return cout;
}

const int F[11] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
const int N = 10, L = 3628800;
int n = 10;

int D[L], pre[L]; PII opt[L]; int a[N], st, ed; bool c[N];

int encode(){ // Cantor
int x = 0; REP(i, n){
int t = 0; FOR(j, i+1, n)
if (a[i]>a[j]) ++t;
x = x * (n-i) + t;
}
return x;
}

void decode(int x){
RST(a, c); REP(i, n){
while (i[a]) ++a[i];
while (x >= F[n-i-1]){
x -= F[n-i-1]; ++a[i];
while (i[a]) ++a[i];
}
i[a] = true;
}
}

void rev(int l, int r){
REP(i, (r - l + 1) / 2)
swap(a[l+i], a[r-i]);
}

void print_path(int v){
if (v == st) return;
print_path(pre[v]);
cout << opt[v] << endl;
}

int Q[L], cz, op; void bfs(){
if (st == ed) {puts(0); return;}
Q[cz = 0] = st, op = 1;
RST(D); D[st] = 1;
while (cz < op){
int u = Q[cz++]; decode(u);
FOR(len, 1, n){
REP(l, n - len){
int r = l + len; rev(l, r); int v = encode(); rev(l, r);
if (D[v]) continue; opt[v] = MP(l, r), pre[v] = u;
if (v == ed){OT(D[u]), print_path(v); return;}
Q[op++] = v, D[v] = D[u] + 1;
}
}
}
}

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

while (~scanf("%d", &a[0])){
FOR(i, 1, n) --RD(a[i]); st = encode();
REP(i, n) --RD(a[i]); ed = encode();
bfs();
}
}


### 動態規劃

/* .................................................................................................................................. */

const int N = 1009;

char A[N], B[N];
int dp[N][N], n, m;

void print_path(int i, int j){
if (!i || !j) return;
if (A[i] == B[j] && dp[i][j] == dp[i-1][j-1] + 1){
print_path(i-1, j-1), putchar(A[i]);
}
else if (dp[i-1][j] > dp[i][j-1]){
print_path(i-1, j);
}
else{
print_path(i, j-1);
}
}

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

RS(A+1), RS(B+1), n = strlen(A+1), m = strlen(B+1);

REP_2_1(i, j, n, m){
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
if (A[i] == B[j]) checkMax(dp[i][j], dp[i-1][j-1] + 1);
}

print_path(n, m);
}

s = gets.chomp; n = s.length; s = '$' + s t = gets.chomp; m = t.length; t = '$' + t

dp = Array.new(n+1){Array.new(m+1){0}}

def min(a, b)
return a < b ? a : b
end

1.upto(n){|i|
dp[0][i] = dp[i][0] = i
}

1.upto(n){|i|
1.upto(m){|j|
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]) + 1, dp[i-1][j-1] + (s[i] != t[j] ? 1 : 0))
}
}

p dp[n][m]

s = gets.chomp; n = s.length; s = '$' + s t = gets.chomp; m = t.length; t = '$' + t

dp = Array.new(n+1){Array.new(m+1){0}}

def min(a, b)
return a < b ? a : b
end

1.upto(n){|i|
dp[0][i] = dp[i][0] = i
}

1.upto(n){|i|
1.upto(m){|j|
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]) + 1, dp[i-1][j-1] + (s[i] != t[j] ? 1 : 0))
}
}

# build alignment .. .
s_ = t_ = ''; i, j = n, m
while !i.zero? || !j.zero? do
if (j.zero? || dp[i][j] == dp[i-1][j] + 1) then
s_ += s[i]; t_ += '-'
i -= 1
elsif (i.zero? || dp[i][j] == dp[i][j-1] + 1) then
s_ += '-'; t_ += t[j]
j -= 1
else
s_ += s[i]; t_ += t[j]
i -= 1; j -= 1
end
end

s_.reverse!; t_.reverse!
puts dp[n][m], s_, t_