fork download
copy 
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3.  
  4. #define FOR(i, n) for (int i=0; i<n; i++)
  5. int lg[(1 << 15) + 1]; // I'm too lazy to do this properly
  6.  
  7. void run(void) {
  8. 	int n;
  9. 	char aa[17], bb[17];
  10. 	int a[16], b[16];
  11. 	scanf("%d %s %s", &n, aa, bb);
  12. 	FOR(i, n)
  13. 		a[i] = aa[i] - 'a', b[i] = bb[i] - 'a';
  14.  
  15. 	int mask = 0; // current bitmask
  16. 	int cha[26], chb[26]; // count # of each character for the current mask
  17. 	FOR(i, 26)
  18. 		cha[i] = chb[i] = 0;
  19.  
  20. 	int cnta = 0, cntb = 0; // count # of distinct characters
  21. #define ADD(chx, cntx, c) (cntx += !(chx[c]++))
  22. #define DEL(chx, cntx, c) (cntx -= !(--chx[c]))
  23.  
  24. 	FOR(i, n)
  25. 		ADD(cha, cnta, a[i]), ADD(chb, cntb, b[i]);
  26.  
  27. 	int res = (cnta < cntb) ? cntb : cnta;
  28.  
  29. 	for (int i=1; i < 1<<n; i++) {
  30. 		int lbit = i & (-i); // the least significant bit
  31. 		int pos = lg[lbit];
  32. 		mask ^= lbit;
  33. 		if (mask & lbit) {// we have just switched it on, i. e. we swap a[i] and b[i]
  34. 			ADD(cha, cnta, b[pos]), DEL(cha, cnta, a[pos]);
  35. 			ADD(chb, cntb, a[pos]), DEL(chb, cntb, b[pos]);
  36. 		} else {
  37. 			ADD(cha, cnta, a[pos]), DEL(cha, cnta, b[pos]);
  38. 			ADD(chb, cntb, b[pos]), DEL(chb, cntb, a[pos]);
  39. 		}
  40.  
  41. 		int max = (cnta > cntb) ? cnta : cntb;
  42. 		res = (res < max) ? res : max;
  43. 	}
  44.  
  45. 	printf("%d\n", res);
  46. }
  47.  
  48. int main(void) {
  49. 	FOR(i, 16)
  50. 		lg[1 << i] = i;
  51. 	int t;
  52. 	scanf("%d", &t);
  53. 	while (t--)
  54. 		run();
  55. 	return 0;
  56. }
Success #stdin #stdout 0.07s 10448KB
comments (?)
stdin
copy 
100
16
kwimcjektsbyccwb
vlgxahfycuamxkfv
16
kjfwhhiwugygjkqk
bpcozkergmpyegrs
16
qivaemixnqkevoaz
gaxpxuedusmsrtjd
16
qcxxlvronydjugpi
osihzywzgmhriijv
16
eqgxhkjuzdneragm
siesnrmbdvfnojrn
16
jrbggysimxlknvnz
otxdqtxahoyckntf
16
fhhzjbbfwysjmlbu
amupglaulbqwjhvr
16
tdzqxaeiklptefdr
xzclbgcdmegelpnp
16
fcmufxiuwatlcxla
rkrkldpmyysemedh
16
wvbwaouypkywkdgo
icoskdsnhipbdviz
16
dxeaskaixytboayt
bcvgeffdkytkntti
16
cgxsulwlzzutvbey
bzrjdiwxtujfmook
16
tdwmnfatdqiffyzi
cwsqamyqatjvxsqs
16
ckqrohlgevrkygni
poaqdbjhyswbewva
16
rybuxozpnkyojxtv
ggojojrgazcisoge
16
whtjpptwsdylljil
rvhttmuwbnotguyq
16
zvxzxzjjveupfrtb
yckvdmwzxxxushyt
16
ykuwminxaijhnxeh
rjbcqloeoilstlgq
16
bvwizsvnysjglzzg
kfdcayhcprdudbiq
16
zwzwvrzjdwpceohx
fagiyqxifqbuugfs
16
bsdepcmkjpctnxyw
yvgjosomqrlqipkh
16
hggerxqwrcbrfhbb
hdceavfnhlmjnrch
16
hvjfvavqtofzobqy
penkgljhdgdzltac
16
undboadnjxwebeub
sqnsutgdbzzikwaf
16
dzwjmbonmrzdbmbc
hrxvtryivwigwtwr
16
hvfsvehbyqlgajmp
owevbsbqsxynopfl
16
vwbmygszovasjuyi
woqyciwnmildvmom
16
gdsahwetrzbnrlvh
wiqqbqukfeseoobe
16
gijomzamshpaojtg
hdvswmncgfczgvcv
16
dxqapptjkzlxxicc
fmroghrkeizjeopw
16
ycehqeztfjfnmhle
xwjkbgwqbveedpcc
16
iveuvbdhasjbaydv
nktibegxhpopfnlx
16
ubduvuvrunnejaam
exwjcafvznlwaccl
16
uulhbfeqcuddednn
zqtcmvirzeaszqbw
16
ijfkaodtsuxjghln
xwtdaoljwjtgmuon
16
htznxzwqwohjlgay
jcmdifiorpidjkdr
16
xftkcjhygfefccpz
posdmrcxvljoqnzh
16
nwvmwkerxfhbpsgx
vrmrhbnnaffehthj
16
pypasjxngsbabjhk
ltpvqyzckhbdezxl
16
kcpmowrtvetlrkbr
zoqrdgdxlulrmfdr
16
agkygsnomyaaxkxh
ivxoezojqtokbzpx
16
zackcccplsklhwws
foyskpztvhkrjapb
16
ancbsddhklgrmnra
vxcuitshskicklsd
16
ykaksixkvkvmyntp
lacvopedsdmzfpnw
16
kngajauvhbirgkeq
kuveiolkjvwfuyqo
16
umcraiwjzmsffuov
xjvmnvgzepeqtafk
16
jxvccqmeculfhjwo
pocusnkuaplucazd
16
zbvmcqistloyhmex
foxzmuugrctyvylg
16
lfrgjlcspnjgulhl
qlyvyxnvurzshsva
16
wibdpymxklmktoxh
qccatsjnzyaarlnm
16
ysgyapkqdtabopnj
tipznoqiluxsqycx
16
nxjrhzafhlcpjhgn
tpiwhndzrwvuojkk
16
cxaanagekrmfjkyj
wwoftwhfdiohpnok
16
bsffkquthphqsrnu
xrkqptifacnxwquq
16
hoxhpmvtajfmvyro
pssrdhehvutmkrrd
16
oxghuwzqschdutfj
bkmvitwmjoghfehs
16
upsiskgzoyyfdnvd
rhvzwtblgujypmfg
16
fmnobdqacpyghzez
cdgbjkpylastiqen
16
imggrvrcjkuuwuup
roemgtrquhvjlokv
16
qinwquitnnydcgkf
qiwwacxcaorskuyn
16
tqblkvvzioaipfph
fdxbskfzoetkptyb
16
geusivigyeaywmkr
cyiqrtmwedphwxnd
16
ohkkacwmyukavgcn
ciqoxnslejlvdztu
16
cwlmmbbtwfglrzui
zcqdupxeefwjdshz
16
vxnspmuuvhxcqbef
ekoigkuxwtovksky
16
cnjbrcnzrcuamvco
etjfapbwivoysphx
16
vdhoqqtewzpkwapg
dnoibapapeimszqw
16
rnaqbcvwemepsfki
ocsjejeidvegsspa
16
nlcecigmhbnwxilz
tqtbkcnkjheifelc
16
wuxqnqiyqwoakxkm
arcfwjuidiunbncu
16
yfthwdtqfgckrrgq
gsmukgacolqzktgt
16
necgmklodxlvckvt
cswjkkaafdmhptxa
16
jtmcvljthpnjffjr
nsqdzhcmvbfniogz
16
evgiayvofivhwilp
qgnqkcnrcnrkende
16
ctlodpixumeawttk
anuhjwxmcafifekr
16
fwhqzgcrqqtjknib
abnnzwtdfqiahodf
16
moydnmidejmxshxo
llitboxifcbnzmzf
16
fchiudhqoncljsug
mnnhvpbubxzqdvbq
16
dgjlodflufeqxpli
uazwtpoqcpvybtlq
16
oumqwwcwuqjztqdn
onxyvfxdzvwnewse
16
hbzbtwhqrxnuthun
lveasttcxujbywyk
16
ujdoursxtxceetev
eyfqubniaolsdpbg
16
ivbwoazipuxpblcn
huxadaoejafiivgs
16
hsxiyhujvskxrnvf
ppsdjrdnsarojbbj
16
dmlavbbmmlsdulzv
bmoeofuaiuatmowz
16
hidxeshrwqzuyxhp
seijxivbxfzlsygg
16
lhsvnfntzdmixaow
blnmmhwkjoeoyuyc
16
kayfjkqhjdwzuugb
qcrnfyowhadwggrn
16
ssjdtmjaxhzhylut
xsbtnodeeekydxfr
16
mpucczfsskrzknpk
fvwcnpsvepfmzsrv
16
qbzlprtfpnqypike
pozcsbpnrqnoqtqh
16
dxouxplejphbivpw
rjpjrrlikyhgmjzk
16
uagcwdjlqepveiyx
grntwhszkjqgqzrx
16
wflwlpakevfbfxsb
tzpfatffwcjxwjqp
16
mnxuvadbrgdzibqy
liijsksotnmtkbep
16
tuexdxezsvfvajlu
axbczjufbjkzjqbj
16
aqkdozfevhzmgadj
kcbqxnrxoieivvyi
16
klsdcnvvezgdumzr
djudjhxnjluxlnla
16
frqcfsyfhuvneirq
ilonwzgkyjakwiqy
16
vtyvnwitiziwopxu
ugwejnjgziaavnkc
stdout
copy 
10
10
10
11
10
11
9
9
9
9
9
11
9
10
10
11
10
11
11
11
12
10
10
10
9
9
10
11
9
10
10
10
9
10
10
11
11
9
11
10
10
9
10
10
10
11
11
10
10
11
10
11
10
9
10
11
11
11
9
10
10
11
12
11
11
12
10
11
10
9
10
10
10
10
10
10
9
10
11
10
10
11
11
9
8
11
11
9
11
8
9
11
12
9
12
9
10
9
11
9
https://ideone.com/wPLK9R
language:
C99 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!