QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#914426#10079. The Lottery WINNERScreenwalkers (Hirotaka Yoneda, Masataka Yoneda, Daiki Kodama)#AC ✓107ms11496kbC++202.4kb2025-02-25 13:21:282025-02-25 13:21:29

Judging History

This is the latest submission verdict.

  • [2025-02-25 13:21:29]
  • Judged
  • Verdict: AC
  • Time: 107ms
  • Memory: 11496kb
  • [2025-02-25 13:21:28]
  • Submitted

answer

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 1012345678;
const int D = 10;
const int A = 26;

int maximum_independent_set(int N, const vector<vector<bool> >& mat) {
	vector<int> g(N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (mat[i][j]) {
				g[i] |= 1 << j;
			}
		}
	}
	int ans = 0;
	auto dfs = [&](auto& self, int x, int bit) -> void {
		if (x == N) {
			ans = max(ans, __builtin_popcount(bit));
			return;
		}
		self(self, x + 1, bit);
		if ((g[x] & bit) == 0) {
			self(self, x + 1, bit | (1 << x));
		}
	};
	dfs(dfs, 0, 0);
	return ans;
}

int main() {
	int N;
	cin >> N;
	vector<vector<int> > lists(1 << D);
	for (int i = 0; i < N; i++) {
		string S;
		cin >> S;
		int bit1 = 0, bit2 = 0;
		for (char c : S) {
			if ('0' <= c && c <= '9') {
				bit1 |= 1 << (c - '0');
			} else {
				bit2 |= 1 << (c - 'A');
			}
		}
		lists[bit1].push_back(bit2);
	}
	for (int i = 0; i < (1 << D); i++) {
		sort(lists[i].begin(), lists[i].end());
		lists[i].erase(unique(lists[i].begin(), lists[i].end()), lists[i].end());
	}
	int ans = INF;
	for (int i = 0; i < (1 << D); i++) {
		vector<int> contain;
		for (int j = 0; j < (1 << D); j++) {
			if ((i & j) == j) {
				contain.push_back(j);
			}
		}
		bool valid = true;
		vector<bool> used(A, false);
		vector<vector<bool> > mat(A, vector<bool>(A, false));
		vector<int> deg(A, 0);
		for (int j : contain) {
			for (int k : lists[j]) {
				if (k == 0) {
					valid = false;
				} else if (!(k & (k - 1))) {
					used[__builtin_ctz(k)] = true;
				} else {
					int a = __builtin_ctz(k);
					int b = __builtin_ctz(k - (1 << a));
					mat[a][b] = true;
					mat[b][a] = true;
					deg[a]++;
					deg[b]++;
				}
			}
		}
		if (valid) {
			vector<int> index(A, -1);
			int cnt = 0;
			int score = D - __builtin_popcount(i);
			for (int j = 0; j < A; j++) {
				if (used[j]) {
					score++;
				} else if (deg[j] >= 1) {
					index[j] = cnt++;
				}
			}
			vector<vector<bool> > nmat(cnt, vector<bool>(cnt, false));
			for (int j = 0; j < A; j++) {
				for (int k = 0; k < A; k++) {
					if (!used[j] && !used[k] && mat[j][k]) {
						nmat[index[j]][index[k]] = true;
					}
				}
			}
			int res = maximum_independent_set(cnt, nmat);
			score += cnt - res;
			ans = min(ans, score);
		}
	}
	cout << ans << endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 3584kb

input:

4
EEXEE
X221
DEE
2555539BD

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 3ms
memory: 3584kb

input:

10
5599595595
9895588899
77871
99999999999999
4444444444444444
04044505
8888888888
09458755848817911
9449857758478478
000000

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 0
Accepted
time: 3ms
memory: 3712kb

input:

15
9999999
0991801909093
3300
80190
083388
93393393399993393
8388838383888388
3088
980981
81811
9909999
9303808099188091
10001011100111001
091300990009
0303333003

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

50
013733073
0307707073733
111111
774747474777747
7131127
44887840707321237
844808400
31848304138301
802314011133
788778877788888
2242121134421314
441024848
220
34141321
47774473434374
11138
777777777777
772772700207
00000000000000
711117711717
31811483443
88222
000000
0803000383
112221121112122
444...

output:

5

result:

ok 1 number(s): "5"

Test #5:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

50
2266797837
33333333333333
7627468364
9669699969696
9777860330188994
2938888329892298
2277740312
000000
967431423001373
00000000000000000
318769
8133
2446472606046
7188811777787887
099909
4040404
1788866661478
099779
999996866
081
3333333333333
8218188342238884
373378883777
8884
66086016399262803
...

output:

5

result:

ok 1 number(s): "5"

Test #6:

score: 0
Accepted
time: 3ms
memory: 3584kb

input:

100
1515942908345919
187
19919
222873337738722
9909900990909900
3155113133511313
33333333333333
20347773
555
0903838238223298
333333
57357
208949477
29900
7758778007200
5500
707884
383030
7157757717555711
525252255522555
9839943485
0075501555527208
1171751751757
33905179300107
117
4443
9809111100098...

output:

6

result:

ok 1 number(s): "6"

Test #7:

score: 0
Accepted
time: 4ms
memory: 3712kb

input:

1000
36112923733922
5955998558
2788962762424
6907207
92785157789
5685885
4099945
110110099049
926
455686
146083
553
3373333377337
81593917
135766766
8916781073
4647
74757
65365342
57959921
8994677
8961771739163979
97275
88888888888888888
5111317531053455
777557575
7567758577
04145990012
39532
831112...

output:

9

result:

ok 1 number(s): "9"

Test #8:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

1000
111114
44444444
444444
4444444444444444
114414414411414
144144441414
4144141
44444444444444
11114441
11144144414444111
4414144
4444444444444444
444444444
4411444
11141141
111
444144414
414441444441411
144
411141411144114
11411411144
4441
1441414
444441441
4444
44444444
111111111
4441444444
4114...

output:

2

result:

ok 1 number(s): "2"

Test #9:

score: 0
Accepted
time: 15ms
memory: 3968kb

input:

50000
50300
2882888282200
5653533556
4060705424555305
00006060660
490526677
77777777777777
846
7372
9506036745209
5355335
1111111111111
9335028055989
178728
110515
2200042022222
151555515515111
027495
04306223
24498449494
36151042
77575755757
57267447645
3565553
3118388
6660600606060660
706362448095...

output:

10

result:

ok 1 number(s): "10"

Test #10:

score: 0
Accepted
time: 16ms
memory: 4096kb

input:

60000
773373333
77777
33333
333777337377
33337
33333
337777337733
7773737777
777777
77737773773
773773733373737
333333333333333
333333333333333
77777777777777777
3333
333333
3333
737773333337
333333
33337733373
77777777777777777
7333373773337337
3333333333333
3773
777773373773333
73733
773333373
777...

output:

2

result:

ok 1 number(s): "2"

Test #11:

score: 0
Accepted
time: 24ms
memory: 4116kb

input:

100000
000888000880088
5255225
185808588
88214
481821142458100
0250
58028
004
000000000
444445
48555554
5855522858858822
4111114
5858512820
02001020220201
4100140014411844
1040
5410541
808800
44050454054444
02220022202222200
180800
2250
550055005505
88888555555888885
554485555884
12004241441450421
5...

output:

6

result:

ok 1 number(s): "6"

Test #12:

score: 0
Accepted
time: 25ms
memory: 4056kb

input:

100000
7777777777777777
774
4444444
44774
774744777
7747
7744747444774
44477447
77777777777777
777447444744
7777777777777
77777777
7777777777
4447477774
44744477477444474
474
77777777777777
77777
74444
44777
474477477444
444444444
444444444
47447477747777
44444
7777777777777
747447774744444
74747
44...

output:

2

result:

ok 1 number(s): "2"

Test #13:

score: 0
Accepted
time: 6ms
memory: 3584kb

input:

10
NIIIIIIIII
AAZZZZZ
JFJJJFFJJ
IPIIIIIII
ZZZZZSZZZ
AV
GGP
GEGE
SSSFFFFFS
VCVVVVVV

output:

5

result:

ok 1 number(s): "5"

Test #14:

score: 0
Accepted
time: 69ms
memory: 3456kb

input:

15
OGGOOGGGOGO
IOOO
NGNN
BAA
LD
DWDWDD
QVQQ
KRKKK
YYYYYYYDY
IIRIII
ZZZAZZAZ
PPPPPPPB
JB
OOTTTOOT
GRGGRGGGGG

output:

7

result:

ok 1 number(s): "7"

Test #15:

score: 0
Accepted
time: 5ms
memory: 3584kb

input:

50
BBPBPPBPPPP
OORORRRO
IVIIIIV
BVBVBBBB
RRVR
VB
PPPOPP
ZZZZZXZZZZ
XXRRRXX
UUGGUGG
XVV
BBBBBBBBP
XVV
BBPP
VVIV
ZIIIIIIIZI
XXBXXXXX
GBGBGBB
UUGGGUG
XPXXPXXX
OPOO
PVPPPVPVPP
OUOOOOOOOOO
UXUXXXXX
RRRBB
OXO
UBBUUU
VVGV
XBXXB
IFFFIIIIIII
OOOUOO
VRVVVVR
OOOOOOX
VGVGV
IIBIBIIII
VVXXXVV
GXGGGGXGGGG
ZOZOOOZO...

output:

7

result:

ok 1 number(s): "7"

Test #16:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

50
HNNNNHH
IRI
DDRDDDDDDD
RRRDRRDR
FFNFFFFFFNF
IIIIFF
RRRRRN
FC
DNNNNNNNNN
NCNCNNNN
UUUUUUUURUU
FDFDDDFDDDD
CCCSCSSSS
JJJJJJJHJ
UUUUJ
HHC
RRRRHRHHRH
NCNNNNNCCN
NHHHHHH
XXXXCXXXCXX
SSSDDSSSDS
NCNNNN
XXRRXXXXX
HCCC
DUDDUDDDUD
JUJUJUJUU
DRDD
NXXXX
HCHHCHC
HHHDDHHHHHD
UUUUUI
DDDJDDDJDDD
SSHHHH
IIRRRR
SS...

output:

8

result:

ok 1 number(s): "8"

Test #17:

score: 0
Accepted
time: 11ms
memory: 3584kb

input:

100
SEESE
CPPPPPC
PUPPPP
BM
VVVJVJJJVJ
PPPJ
CWWWWCC
MUUMM
FMMFMF
ULLU
PFFPPPFFP
PPZZPPP
ZZZZZZZV
XKKXXXKXXX
KGGGKGGG
JJJJJJSJJ
CUUUUUUCU
JJJJJJVVV
CSSS
EEWEWEEEE
BBBXBBBBB
BBBP
XHXXXXXHHXH
VBBBBV
IIRIRIIRIR
UUF
XXXE
XHHHHHXXX
IIIRIIII
ULU
XBX
SPSSSSSSSS
CZZZCZZC
CEEEE
GF
SISISS
UDUUDUU
BBBBWWWW
CBB
...

output:

14

result:

ok 1 number(s): "14"

Test #18:

score: 0
Accepted
time: 6ms
memory: 3584kb

input:

1000
IIIIIEIII
IEEEEIIEEEE
KKKKKKGKKGK
SSNN
EJ
YO
EM
TYYTYT
YWW
WWOO
RX
EGGG
CCCCCCCCO
DRDRRRDRD
SRRRR
IW
NK
RWWWW
RCRRR
WWWMW
PY
YYIIIY
MMOOMMOOMOM
NRN
MMMYYYMM
OD
PPCPCP
OOXXXXXOO
OS
WWNNNWNWNWW
OOD
YNNYYYNNYYN
KGK
WWWWWSWWWW
WWDWDDWWWD
NDN
EMMMMEMMME
WSSSSSSS
IIIIEEIIIIE
EYYEEYYYE
TYYYYYTY
JDJJJ
...

output:

16

result:

ok 1 number(s): "16"

Test #19:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

1000
MTMMTM
CCCEE
MS
TTTTCTTTT
YYYYYTYYY
YYZZZZZYYZ
ZC
MSSMSSS
EEEREEE
YYTY
CRR
ZCCCCCCCC
YYYRYRRYYYY
REEEEEEEEEE
RYYYRYRRRY
ECCEECCEE
ZVZVVVZZVZV
VTVVVVV
SSSSTTSSTS
CCCCM
RTTTTR
EESE
EETETETETET
YVVYVYYYV
YYYYYMYMYY
SSSSMSMSSS
TTTVVTTT
CCCCCMCMCC
ES
EREERE
SSSRSR
CRCCCRCCRC
MMVVVVVMVMM
CCYYYYY
MS
C...

output:

8

result:

ok 1 number(s): "8"

Test #20:

score: 0
Accepted
time: 14ms
memory: 3812kb

input:

50000
MEEEEEEE
XXXZ
EKEEKKKK
IIUU
XXFXFXXX
YNNYYNYNYN
JXXJXJJXXJJ
UUUUUFUU
UGGG
XXXXXXXYX
NNBN
BJJJJJBJJ
BN
GGGIGGGGGG
NGGNGG
GI
EKEK
NUNUUUUU
UUUUE
GGEGGGE
NYYNN
NZNZZNNZNZZ
GUGGUGGGGG
IAAIIIAAI
NEEEEE
GUUUUUUU
YYYYYAYYYY
IZIZIZIIZI
UUUUXUXUX
BXXB
KFFFFF
IGIG
UEEUUUE
KKKM
NJJNNNNN
BJJJBJJJJB
YYYAYY...

output:

13

result:

ok 1 number(s): "13"

Test #21:

score: 0
Accepted
time: 17ms
memory: 3812kb

input:

60000
WWWVWWW
WXWWXWWW
XVV
VOOO
XYYXYX
GGA
GGGYGYG
WS
OYYOO
SSSWSSSSSS
OVVV
DDYYY
XXXXXGXXX
OW
SRRSRSRRS
WAAA
GGVVGG
SGGGGGG
OOOODOOOOOD
DRRRDRR
XDXXX
AAAAAVVV
AVA
YYWY
WOWWWWWWW
XXGXXX
RV
YYYG
DSSDDSSDS
RRRGR
SSGSSSGSGS
OAAAAAOO
AVAV
XXXD
GGX
RRSSSRSSSS
YVVYYYYYVVY
ORRR
AAYAAAYAA
WDDDWD
WGWWWWGWW
Y...

output:

9

result:

ok 1 number(s): "9"

Test #22:

score: 0
Accepted
time: 34ms
memory: 4460kb

input:

150000
RRRERRR
QQRQQRRRQQR
EEEYE
LULLULULU
RQ
UUJJJJJJ
UUUUUUUUCU
RB
YRYRRRYRYY
QLL
QUU
LR
CJCCJ
QQQQQQQRQ
WBW
UULUUUULLU
QC
RYYYYY
BLBBBBBBBB
CCWWCCW
WLL
REEE
QQYQYQQYYQY
BBYYBBBB
WUW
UBBBUBBBB
CJJJJJCJ
YYUU
CBBB
BBCCCBB
LC
UUUUUUWUUU
REREERE
BBBBWWBWB
RURRR
JJLJLJ
CCCR
RBBBRRBR
RL
QUQ
YRRRYRYY
WLL...

output:

9

result:

ok 1 number(s): "9"

Test #23:

score: 0
Accepted
time: 43ms
memory: 4456kb

input:

200000
LB
LLTLL
OW
BTBBBBB
TTTTPTTTT
MYYYMY
YCYYC
LSSSLSS
OOROOO
EEETTT
LLLPLLLPL
OS
TETETTTTTE
RE
BBBBEEEB
EMMEMMMMMMM
CCCTCCCCC
BPP
BPB
EBBBB
TTTTRTT
EEEBEE
MOO
OOPOPPP
WYWWYYYYY
CEECECCEEEE
CCCEECEEEEE
PMPMMPPMPMM
MPMMP
YLLYL
YYYYRYYYYR
MEEMMEEMEEM
OC
MBMMB
OOLL
WR
LPPPPLPPLPP
TLLLLL
SRRR
TTTMTTT...

output:

11

result:

ok 1 number(s): "11"

Test #24:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

500
KTTTTTTTTT
EEEEEEEEEOE
AAWA
XXWWW
AAAOOA
FQQF
OOAOOOOOOO
OYOOYOY
MAAAAMMMAAM
ZZZZWZWWZZZ
WCW
IIRI
MT
XVXVXXXV
RYYYRY
YYYYYYYVY
MMMMJJMMM
KKKKYKYKK
ZX
ODOODOODO
VCCCV
AFAFFF
MMI
GR
IIMI
FJJFJFFJJ
DWWD
IIIIIICCC
AEAE
WWOOWWW
UAAAAA
JJDDJJ
ZWWWWW
YZYYZZYYZY
EUUEUUEEU
XXXXFXXXFF
GTTGTTT
RZRR
TTTET
F...

output:

25

result:

ok 1 number(s): "25"

Test #25:

score: 0
Accepted
time: 4ms
memory: 3456kb

input:

500
GGHG
WWWWZ
PXP
KKKQQ
GGGGZGZZZZZ
BKKBK
SSSSSSQQ
FFFDFDFFDDF
DDBDDBD
AYYYAAYAAY
CCHC
RC
VY
RRRRDRRRD
FQFQFQFQ
HPPP
VFFVVFFFVFF
HHHHHHOHH
OOOOQQOQ
RRRRYRYRRY
KP
SEEESEEE
HVHH
TB
DDDDBD
YYEYYEYEYY
HOO
KKVVVV
JJQJJQ
BSBS
DDDDOO
YGGGGG
RRRRRBBRRR
RRRRRRARR
SSSSSSWSS
GGCGC
CCCCCCCDC
ZSZSSZSSSZ
TWTTWTW...

output:

21

result:

ok 1 number(s): "21"

Test #26:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

500
GGTTGTGT
MNMMMM
GGYY
EEDEEEEEE
NNNTNTNNN
WAWWWWWAWAW
BBBBBBDB
KYKYKK
GAGGGGGG
YYAYYYY
ENE
DKKDKKDDKD
DWDWWWWDD
WWWWWWDW
YYYYK
ANN
MMYMMMMYM
EBBBE
GGGTTT
GGTTTGGTTGT
BBWWWWBWWWW
WGWGWWWGGGG
DEDEEDE
WNN
BGBBBB
MMMMMKM
GGAAGGAGG
BKBB
WEE
BBAB
DED
EYYYYE
NMMMMMMMNMN
EEEEED
NNNWNNNNN
DDMMMMDDMM
TTTMT...

output:

15

result:

ok 1 number(s): "15"

Test #27:

score: 0
Accepted
time: 3ms
memory: 3584kb

input:

759
EEEEEEEV
QQQH
ESEES
SV
XXFXFFXX
DDQQ
KYKK
SY
SSSNSSSN
FFXFFF
SDSSDSSDSS
NQQ
FFFFFFE
QHQQQHHQH
KKKKKVVVK
FFFFFFFFE
VHHVHHVVVH
DXXXXXDX
FFFFFFXXF
SSSSSSSQ
XHXHHHHX
XKKKKXXKX
XK
HYHYH
QEQQQ
HVVVHHVHVV
YX
EESESE
EFE
HXX
QHHH
EDDDEDDE
FD
VHV
XNNN
YYYYYYYFYY
KKKDKK
DEEEEED
DQQQQD
XFXFXFXF
QNQQQQQ
EEHE...

output:

15

result:

ok 1 number(s): "15"

Test #28:

score: 0
Accepted
time: 4ms
memory: 3456kb

input:

800
UUTUUU
DDDDDYDDD
FHHHHF
ZXXXX
UUUZZUUU
PYYYYYY
BC
SSP
BW
OOFOO
PS
XLXLXXLXXXX
ZFFZZZZFFFZ
IIZ
MYYM
YUYYYYUY
IIITIIITTI
GGGGGBGG
XXLLX
DRDDRDRRRRD
UUUBUB
FW
KKPPKPPPKKK
HMHHH
FFFFFFWFF
ZZDDZ
SYY
BBKKB
OI
KKKKFF
DXDDDX
UUHUUHU
TLLLT
GS
BP
BDBDBDDDBDB
TRTTRTTTT
WWFWWW
IIILII
UFF
XXH
BBTB
HMMH
PDDPP...

output:

26

result:

ok 1 number(s): "26"

Test #29:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

1000
LLLLLLLX
FFXX
FL
HFF
FOFFFOFFFFF
OLLOLLO
HXHHXH
OLLL
XXJXXXXXXXX
JOOOJJOJOJO
LXL
XXLXLXL
XXLL
HXXXHXX
OOFO
HHHHHJHHJ
XLLX
FFFFFFLF
HJJJJHHJH
OOJJJJJJ
LOLLO
JHHHJHJJJJJ
XXXLLXLLLXX
XXLLXXXXL
HX
HJ
XOO
XXFXFXXF
HFFHF
HHHHOHOH
XXJJXXXXXXX
JJJJOJ
OFFFFFO
HOOHO
OOOOOJOOJOJ
HHHJ
FLF
JJHH
XFFFXFF
OOOO...

output:

12

result:

ok 1 number(s): "12"

Test #30:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

1000
FFKKK
KKKKN
FFFFFNNF
UUUFUUFU
UKUUUUKKUUU
NDNDNDNNNND
FKF
DNDDD
UKUUUUUUU
NNNFFFNF
KFKKKFFFKF
FFFFKFF
UFUUUUFFFUF
UUUUDDUD
KKKUUKKU
DF
FFKKKK
KKKKKFFK
NKKKNNNN
FDF
DFF
KUKK
FFFUF
DDDUUU
FDDFDFFFDDD
DDND
DKKKK
KUUUKK
FFFFFFFFK
NUUNUUUUU
UUUUUUDUUD
UUUUUUUKU
UFUU
UFF
KNKKKN
UDU
DU
UDUDDDDD
NNNNND...

output:

14

result:

ok 1 number(s): "14"

Test #31:

score: 0
Accepted
time: 6ms
memory: 3712kb

input:

4000
TTTL
WYYYY
MSM
BBAB
MMIMMI
OP
QQDQQQDQD
QSSQ
YWYWYWY
ZXXZXXZ
XIIXXI
YUUUYUYYUU
JJXJJ
XXVXX
MMMMMEME
ZZZNZZZNZNZ
EEECCCE
URRUURRRU
MBBB
QQQQNNQ
JPP
AR
RRRZRRRRR
PK
DDDDDX
DBDBBDDB
RAR
UUUMUUU
OQOOOQQQQO
KKU
YQYQ
TTTTTTTTTTZ
MMMWM
QQQQQQDQD
CQCCCCCCC
FCFFCCFCCC
KMM
GGP
IIIIXIIIII
AAEA
RPPPPRR
DAD...

output:

28

result:

ok 1 number(s): "28"

Test #32:

score: 0
Accepted
time: 5ms
memory: 3712kb

input:

4500
EDDDD
GOG
QFQF
TTC
DUD
CCCHCCHC
OZZZZZO
OA
JDDJDJJJD
XJXJXJX
KHHKHHKHKK
SG
VSSVSSVSVSV
QQQQFQQQQQ
DDDDDDCDDD
XXXXXCX
DDDADDDA
KGG
UUUAUAUAUUU
KKKKDKDDK
WXWXWXWXX
SFSFSS
UVVVVUU
CDCC
XHXX
VVVAVVVA
VOVV
FFFBB
BW
HVHHHVHHHHH
XXXBBX
TJJ
TTVTT
VMV
EEY
MUUMMU
VVVVVVWVVW
XT
AKKKK
MMBMMMM
HHWHHHHWW
SSM...

output:

21

result:

ok 1 number(s): "21"

Test #33:

score: 0
Accepted
time: 3ms
memory: 3584kb

input:

5000
FXXXFF
XZXZXXZ
ZZZZOZZZZZ
RZ
XSXXXXXX
RZZRRRZRZZZ
ZSSZZZSZZ
LVVV
PII
UPUPUUPUP
VE
SSSNSNSNSSN
FFFE
RRRRLRRLLR
NVVVVN
XEEX
UEUEEUEEUU
OEOOOOOEOO
YYYYFYYYF
YLLYYL
YN
OOEE
IEEIIIEII
OOIOOO
RVR
LELEEE
FDD
NO
RSSRSRRSRRR
OOOOOOOIOOO
YYZ
RRD
OLLL
FFSFSFF
ZXXXZX
XXXDX
DSDDDDD
IIU
VVR
VYYYVYYYYV
LLXLLL...

output:

17

result:

ok 1 number(s): "17"

Test #34:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

16
AB1
AB2
AB3
AB4
AB5
AB6
AB7
AB8
AB9
AB0
C
E
F
G
H
EF

output:

6

result:

ok 1 number(s): "6"

Test #35:

score: 0
Accepted
time: 4ms
memory: 3456kb

input:

335
QN
GF
KQ
YD
XL
AW
EK
OI
ER
SG
UN
HY
EG
YB
DV
OG
PG
FA
LN
EP
JG
CM
OP
VB
FH
DI
BE
XZ
UC
IJ
IG
EZ
TD
IP
DQ
ZW
RX
HE
MX
UB
LC
AV
LJ
PV
AE
ZR
LK
SX
CX
BT
PH
QV
SZ
HS
FP
TE
VH
KY
TM
GH
QM
CY
TK
NJ
KX
UF
BH
HO
IZ
DE
SC
RF
TI
LD
UH
SM
NW
AL
AP
VM
SA
YR
WC
JZ
GL
BS
ZV
FC
AQ
GU
BF
GT
FI
HA
BO
JA
PJ
CB
RJ...

output:

35

result:

ok 1 number(s): "35"

Test #36:

score: 0
Accepted
time: 4ms
memory: 3456kb

input:

325
QK
MY
OT
JH
BA
GU
ST
AQ
FJ
OW
BK
NU
RW
DW
BR
DR
WQ
HQ
SK
MU
QJ
SF
LM
XQ
JZ
XL
AD
OX
YI
YF
TQ
XC
LA
YR
HV
WP
NS
BL
GE
DB
ZI
JW
GR
LH
PV
IU
DK
ZG
UY
KV
OR
AW
SG
YB
HC
MD
CM
ZF
FR
YT
QV
XA
FA
IR
HM
ZT
UT
CS
WI
LI
US
SM
SX
BC
WT
UC
ZH
OC
OZ
OJ
CE
TR
AP
DQ
VJ
GY
XV
KT
YJ
ER
RQ
YL
VI
ZS
BN
MI
ZE
MF
ID...

output:

34

result:

ok 1 number(s): "34"

Test #37:

score: 0
Accepted
time: 3ms
memory: 3456kb

input:

255
JA
KE
MU
NI
SE
PA
UV
LK
UA
JN
NB
OM
EL
UP
SV
CD
VW
LW
VT
UR
QF
SD
BU
PJ
DJ
XV
JI
IC
WB
SH
QE
AY
ZS
FU
HN
CR
GI
GS
NU
FO
BL
LJ
ZR
TP
WC
XG
EJ
CG
HE
XZ
JB
QT
NZ
QJ
SL
UK
WD
UH
YJ
WZ
EO
FE
TA
BS
NA
OL
FN
PG
ER
MX
WA
ID
DL
OX
BA
GY
ML
MG
SM
PL
FT
WP
YF
CB
QW
PC
UQ
PV
LA
NX
MC
HL
EI
CX
WK
HG
TL
OH
MH...

output:

32

result:

ok 1 number(s): "32"

Test #38:

score: 0
Accepted
time: 93ms
memory: 4864kb

input:

250000
UMMMMMMMM
GGGGDGDGGD
EPPEPE
IIIY
EGGEGE
RDDD
ERRRR
SSSMSMSSSS
YIYIIIYI
NGNGGGNNNNN
YHHHHHHYHHH
LLLLKK
NNNNNNM
VVIII
BBNBBB
OKOOKK
LNNNNNNLN
GSSGGSSSSSS
BKKBKKKBKB
TBBTBBBTBT
EEKEKK
YYWYYY
QQQQQP
HB
IIIG
MSSMMMMM
XXXXXXXN
XIXXXI
BBBBHHHHH
HHSSHSSHS
YD
KKO
GRGGRGRGRRR
LLULUUUUU
JOOJO
PHHHHHHHH
...

output:

21

result:

ok 1 number(s): "21"

Test #39:

score: 0
Accepted
time: 18ms
memory: 3824kb

input:

50000
NNANNAN
JIIII
YYWWW
XXIIII
UH
WTTTWWW
KZK
YYVYYYY
VXVVXV
YXX
GGGXXG
UXUUX
GGGTGGGG
ZZRRZRR
UGUUUGGU
ZZAZZZZ
AUAUA
YOO
TLTTLLTL
NNCNN
VVT
OOJJOOJJJOO
TUT
ZV
WWWNNWWW
LLVV
PY
WA
KRRKRRKRK
GGGYGGYYGGG
UUPUUUUUPPU
CCCCCCXXXCC
CCCXXCCXX
ANNNNNNAA
TTXT
XTTXXXXT
JJJJJJPJJ
UOUOUUUO
OJJOO
JAJ
AAXAAX
JJ...

output:

22

result:

ok 1 number(s): "22"

Test #40:

score: 0
Accepted
time: 68ms
memory: 4736kb

input:

250000
ONONONN
UUOOO
ZNNZN
OIIIIIIII
FIIIFIFIFIF
FOOO
ZF
UFUFUFF
UUUIUUUUI
MUMMMMMU
IFFF
IIMM
FZFFFZZFF
MOOMOMMOM
MMZMM
NNNU
OOIOOOOIIOO
ZUU
NNZZNNZNNZ
UUUF
OUUUOUUOUU
OUUO
IIIIIIIF
ZOZZZZZZZZZ
UUUOUO
FIFIFIFI
IZIIIIIII
ON
NIIIIINNII
UUIUIIIII
OFFFFFOOOO
ZFZF
FOOOOOOFFO
FFZFFFZFFF
UMMUM
UMUUUMUU
FFO...

output:

6

result:

ok 1 number(s): "6"

Test #41:

score: 0
Accepted
time: 19ms
memory: 4096kb

input:

60000
ZZZQZQZZQ
LQLLQQLQLQ
DQDDDQD
VVZV
LRLRRLL
OOOODOODDOD
DDOODDDD
ZZOZO
VVQ
VRVRVVV
VQQQQQQVQQQ
DRRD
QQVQQQQQ
VVVZZVVVVVV
QOQQQQQQ
QDQ
RRLRRR
LLQ
LVVL
QQQQLLQQQQ
OL
LLV
LO
QQQQQQQDQ
OQOOQO
OZOO
RVV
DDZDZD
OOZZZZZZO
RO
VOOOOOO
ZZRZZZZZRZ
VRRRVRRRR
OD
LQLLQQQQLQQ
DDDDVDDDD
OOOOOOZ
VVVVVZVV
QQVQVQ
D...

output:

16

result:

ok 1 number(s): "16"

Test #42:

score: 0
Accepted
time: 47ms
memory: 4096kb

input:

150000
EESEES
FXXXXFXXXX
KEKKEEKKKE
FLL
ADDD
KKKKO
EEERER
LLRL
JO
FFFFFFFYFFF
BK
JAJJJAA
YYGYYY
FFYYYFYYFF
AAZAAAAA
ZXXZZXXZX
RLLLLRLLLLL
EZZ
RZZ
FFFZF
ZZZZXXZZX
BBG
YSSSS
FFOFFOOFFO
AAAAAAAYYA
SLLS
LLLLLGGG
DDJDJDDD
AAAAEA
OGGG
FFFFOFFO
BBBABB
ZZZZDDD
BBBBJJJJ
ALAA
KKKKKKBB
GRGGGRGGRRG
RRGRRRG
SJS
...

output:

14

result:

ok 1 number(s): "14"

Test #43:

score: 0
Accepted
time: 40ms
memory: 4352kb

input:

150000
HCCHH
QWQQQQ
WWWWWWWVVWW
OOTOOO
XXXXK
QQVQ
CQ
KKBKBKKKKKB
GO
CCCCCKCCK
PPPPQQPP
BBBBBY
HEEEE
CCB
GK
YVVVVVYVV
GOGO
WVVWW
AKAA
CAA
KHKHKKKHHHH
YYV
XVVVVXVVV
WWWT
OQQOQQQOQ
CPCCPCC
QBBBQBBQBBB
AKKKKK
CCCCCQCCC
WWTWWWWWTW
XOXXXXXX
PPOPPPPP
WWWWWHWWWWW
VGV
AV
XKKXKKKKKKK
OOOGOOGGO
HYHH
EEEEVE
XQQ...

output:

22

result:

ok 1 number(s): "22"

Test #44:

score: 0
Accepted
time: 72ms
memory: 4736kb

input:

175000
HUUUHHUHH
HNHNNHHNNH
EENNNEEE
UUCUCUCUCCU
EPPEP
EIIEIEEI
JEJJJJJ
UUUUUUUUZU
DLLLLLLDL
YYGYYGYGGY
OXOXXXOOX
LLLLLLKL
SSSXSXSSXS
WWWWWAW
SSISI
ZCCCZCC
IIEIEIIEII
TTZT
MMPMPMP
SKSSSKKKK
DDDPP
CCHCCCHCCC
ZZZWWW
AE
UUUUUUYU
BS
GGGTGGTGT
HHHSHHHH
XGX
EEEEEEIIEE
LLTTTLTLLTT
PXPX
LPPLLLLLLLL
EEEENEEN...

output:

23

result:

ok 1 number(s): "23"

Test #45:

score: 0
Accepted
time: 45ms
memory: 4480kb

input:

175000
VVVVVIV
WWHWWWHW
EEECEEEEEEE
GGXGXGG
TTTAA
TNNNNTTN
JJWJJJWWWJ
LY
KMKKK
ILLL
XUUXUX
DDDFFFD
GYYGGG
EMM
JJJJJJZZ
JYYJ
HHHWHHHHHHH
DSSS
VFVFF
PPPPRRPPR
SV
SJSSSS
LSLL
OTOTOOO
AAAVAV
EGEGGGGEGEE
GGW
KP
YCYY
WWXW
DDIII
LLLLUUL
DKDDKKD
RRY
AIAAA
UUUAAUA
RUUUUURRRRU
EER
HHMMMH
JJJJJJJJJJG
IIIIIIIIH...

output:

29

result:

ok 1 number(s): "29"

Test #46:

score: 0
Accepted
time: 64ms
memory: 4816kb

input:

250000
EEEII
GGGGGBGGBGB
HHHBH
IID
AXXXAA
EJEEJJEEE
PG
BAAABAAB
ABA
CGCC
SSSSISSIS
YXXYXYX
AAAS
EXEEXXEXX
BBBHBBBBBBB
WWDDDWDW
XXXSSXXXXS
XI
HHJ
AAAAACA
BBPPBB
DGD
JJSJJJJJ
HHHBH
BSBSSS
GW
HYHY
SYYYYSY
YGYYYGYYYY
IIS
EEW
XXJXJXJXJJJ
HHJJJJ
WWWWWWS
YGYGY
BBABBBB
JJSJ
IIIIEI
YYYDYYD
JJCCJC
WWAA
BBBBBI...

output:

13

result:

ok 1 number(s): "13"

Test #47:

score: 0
Accepted
time: 52ms
memory: 4864kb

input:

200000
LOL
UOU
SSRSSSSSR
YU
QJJQJQJJJQ
UPUUUUUU
YP
IPIIII
RRRRRRRRRRQ
UUOUUUOUUUU
PK
PPPPLPP
RQRRQ
PYYPYPP
SSG
IP
IOOOO
KCKKKKKKK
YIYYYYYYYYY
YYYKYYYY
YLL
KY
JPP
RPRRPRRRP
KKKKKKKKKSS
PJP
SSYSSYY
RRRY
GGSGGGG
KGGKKKGKG
RRP
PPPCPCPCP
SPSPPPP
CJJ
SKSKSSSSSSS
KKKKKKKRKK
PPPJPPPJJ
RGGGRGRGG
LLK
NOONONOO...

output:

22

result:

ok 1 number(s): "22"

Test #48:

score: 0
Accepted
time: 65ms
memory: 4460kb

input:

250000
URUURURRRR
UV
OG
FFRF
DUUUU
MSSSSSSSSSS
WTTTTW
UHHH
RRDDRRDDDRD
WLWWW
DDDDDC
WGGGGGGWW
QQQBBB
CFFFFCCFC
FFOFO
QQQB
WD
CLCLLLLL
OOOOOFOOOO
GGGGH
BLLBB
USSSSS
TM
BBRB
HBHHH
TTFTTTT
BFF
FD
UUUUQQUU
HHQ
RRW
GQ
XXFFFXFFFX
GQGGG
VLVVLVVVL
FFFVFFFFFFF
WWWWLLL
WWRRWWWRWWR
UHHHHUUUU
XOOOOOOOOXO
RWRRR
...

output:

16

result:

ok 1 number(s): "16"

Test #49:

score: 0
Accepted
time: 60ms
memory: 4608kb

input:

250000
PPPPPPPPXPP
ELLLLELLL
SSNSSSSS
RRZ
LP
GGR
AAAANANNN
IIUI
ZYYYYZZZ
QQQQNNNQNN
QM
QQJ
RXXRRXRRX
MMR
NA
XRXXXX
SSYYY
AQ
UM
UUSUUS
UULLULLL
UXUUUU
NNNGNNNG
ZGZZGZGGZGG
RFFFRFFRFRR
ZZZFZZFZ
PPPPPPFP
EMMMMEMM
NL
GGGGLGG
XSSS
NSN
IIY
LLLNNLLNN
QQQQQQYQYQQ
XZXZZXX
AAAIAAIIIII
MMMI
UUUMUU
XXXXXXXXXS
S...

output:

20

result:

ok 1 number(s): "20"

Test #50:

score: 0
Accepted
time: 60ms
memory: 4864kb

input:

250000
GZGGZGG
GZGGZGZZGG
GGEEGGE
WWWGGWW
WEEEE
GGGZGGG
ZGZGGGGGZGG
EGGG
ZEZ
ZE
GGGGGW
WEEWWEWW
GGEE
WWGWGWWGWWW
GGGGZG
GGGEEGGE
EWEWEEWW
WGGWG
WWWWWWEW
EEEGEEE
GZG
WWWWWWEWWWW
EZZEZ
ZZZZZGZ
ZG
GZZZZZZZZZ
GEEGE
ZE
GGGGGGGZGGZ
ZWZZ
EEEEWEEWWW
EEEEEEGEE
GZGZZZZZ
GWGGGGG
EEEZEEZEZ
GGGGWGGGWGW
EEGGEEGEE...

output:

3

result:

ok 1 number(s): "3"

Test #51:

score: 0
Accepted
time: 63ms
memory: 4864kb

input:

250000
LOOOLOO
DDL
EEEEEELLL
LLLLLLLE
DLLLDDD
DDDDLD
DDDOD
OOEO
LLLEELLL
LOOO
EEEEO
OOEOOOOEO
LOOO
LOOLL
EDEE
EOOOO
LLEEEEEE
LE
LLLDLLDDL
EDD
EDEDDDDDD
DODODO
OOOOOOOLO
DLD
LDL
DO
DDODDDDD
LD
ODODO
LLOLLLLOLO
OLO
LDL
EEDE
DO
DDLL
LOOLLL
EEEDE
OD
EEEEDED
EDDDDEDED
ODODODDDOD
DLDDDDLLDD
LD
LLLLE
LOOOL...

output:

11

result:

ok 1 number(s): "11"

Test #52:

score: 0
Accepted
time: 69ms
memory: 4736kb

input:

250000
KKTKTT
BBBTTBBBBBB
JJK
KKKRKKKRRK
JJJJT
LBBL
RRTRRRRR
TTTJTTTJT
RRRRLRL
NNNNNNS
RTT
JYJY
NNKK
KUKU
LLB
NNNNNNAAANN
JJJUJJUUJJ
TTLLTTTLLL
TAAATATAT
KKBK
KKKKJKK
LLBLLLLL
SJ
BBJJJB
RT
RB
NT
AAAAARARAAA
TRRTR
TB
BBTBBTBT
YNNYNYYYY
YBYBBYYYYY
LLKK
BYBBYBBYBBB
SJ
RRTR
RRRSRRRRRRR
YLYY
BUUBBBBBU
AU...

output:

10

result:

ok 1 number(s): "10"

Test #53:

score: 0
Accepted
time: 61ms
memory: 4736kb

input:

250000
RRRRRRWRRR
SJS
LLFLL
EZ
RRRRRRQ
WRRRRRRR
JLJ
WRW
WWWWQWWWW
QQQQFQFF
FIIIIFFIIFI
LZZLZ
IIISIIISSIS
VVVVVVLV
SWSSSSWWW
EQEQQQQE
ZZZWZW
RRRS
QJJQ
JJJJIIIJJJ
ZW
FFFFFVF
QWWQWQWWQ
LRRRLRLL
FFFFFFFFFV
QSS
JVVVVJ
ZJJZ
QSSQQQQS
JS
IIWWIII
IQQQQ
SZSZZSSSSZS
LLLLLLR
SVSSSVV
SFSS
WWJJWWJWWWW
WZWZZWWZWWW...

output:

14

result:

ok 1 number(s): "14"

Test #54:

score: 0
Accepted
time: 65ms
memory: 4480kb

input:

250000
SSZSSS
HWWWHHWHWW
HHWHWWHHW
NNNLNL
BBEEEEEB
CDCC
BBSS
HHKKHK
BSSBBSSSSSS
BBBBBBBBBBC
WWDWWWDD
SHH
WWLWWWWW
VS
EW
SSFSSS
KKEK
ZZYYYYZ
SYSYYYSYSYY
VVYVV
ZZZZZPZZZZ
WS
TYT
FSSS
TCCCC
NNK
NDDDNN
EW
FZZZZFFZZ
TTTTWTTTW
WWNWWWWWN
EEVVVV
LLLLZL
LLLLCLCLC
TTTTZTTTTT
ES
BEBBEBBEBB
DWDDWDDW
FFFCFFCFCC
...

output:

20

result:

ok 1 number(s): "20"

Test #55:

score: 0
Accepted
time: 57ms
memory: 4608kb

input:

250000
YYYHYYYYYYY
BBBYYBY
YSSS
SHSSHS
HHSH
SSBSB
SBSSSS
BBBBBHB
YYYBY
BBH
HYYY
BBBBBHBB
YYYYYYYHY
SSSYYSYSYYY
YH
BHHBHHH
HHHBHB
YYYSY
SBSSB
YBYYYYBY
SBBBSBB
BHBBHBBB
HHHHBHH
HYYYHHY
SSSSSSSYSS
YYYBYY
BSBBBBBBBB
SBBBSSBSB
SSSBBS
BBBBYBBBBBB
HHHSHHHHHHS
HSSSSSSSSSH
BBH
SSBSSSSSSS
HHSSHH
YYBBB
BYYBYBB...

output:

6

result:

ok 1 number(s): "6"

Test #56:

score: 0
Accepted
time: 76ms
memory: 4864kb

input:

250000
ETTTETTE
TD
FFXXX
DMD
VFFFFFF
VVWVVWWVWVV
DVVVVDVV
TV
DFFFDDDF
MMMMMTT
FMFFFFFFFFF
VVVCCCV
NNTTTN
XVVXX
MMCCMCMMCMC
MEEEMME
FVVFF
CLLCLL
NCCN
CXXXXXCC
VMV
WXXWWW
MEEMMEM
FN
XV
CLCCCCC
MMXMMXXM
TFFFFF
NTN
XXXFXFXXF
CCMCMM
LLLMLLM
MMMTMMM
EN
WXX
DDCDDDDDDDD
TD
CLCCLLLLL
XLLLLLXLXLL
CCCCCCCNCCC
...

output:

18

result:

ok 1 number(s): "18"

Test #57:

score: 0
Accepted
time: 62ms
memory: 11496kb

input:

1
07610XX79E712EX0290E190E7770981088X39472812346E8140348X960EXE827689607921634EX631E1381268600386E9884E0EX180E707420X6042866142687E48046E900EE8E606E37912X8721X9XEE784241XX7668728248137E296346X3970222101432736132269E76674068386X97388EE32911E8X830087927037X636664308839E7EE7X308979024669X319E6E49EE0443...

output:

1

result:

ok 1 number(s): "1"

Test #58:

score: 0
Accepted
time: 107ms
memory: 8964kb

input:

250000
ETTTETTE
TD
FFXXX
DMD
VFFFFFF
VVWVVWWVWVV
DVVVVDVV
TV
DFFFDDDF
MMMMMTT
FMFFFFFFFFF
VVVCCCV
NNTTTN
XVVXX
MMCCMCMMCMC
MEEEMME
FVVFF
CLLCLL
NCCN
CXXXXXCC
VMV
WXXWWW
MEEMMEM
FN
XV
CLCCCCC
MMXMMXXM
TFFFFF
NTN
XXXFXFXXF
CCMCMM
LLLMLLM
MMMTMMM
EN
WXX
DDCDDDDDDDD
TD
CLCCLLLLL
XLLLLLXLXLL
CCCCCCCNCCC
...

output:

18

result:

ok 1 number(s): "18"