<prompt> Unapewa nambari n inayowakilisha idadi ya kadi za kucheza ulizonazo. Nyumba ya kadi inakidhi masharti yafuatayo:Nyumba ya kadi ina safu mlalo moja au zaidi za pembetatu na kadi mlalo. Pembetatu huundwa kwa kuegemea kadi mbili dhidi ya nyingine. Kadi moja lazima iwekwe kwa mlalo kati ya pembetatu zote zilizo karibu mfululizo. Pembetatu yoyote kwenye safu ya juu kuliko ya kwanza lazima iwekwe kwenye kadi ya mlalo kutoka kwa safu iliyotangulia. Kila pembetatu imewekwa katika sehemu ya kushoto kabisa inayopatikana katika safu mlalo.Rejesha _idadi ya tofauti nyumba ya kadi unaweza kujenga kwa kutumia zote_ n _kadi._ Nyumba mbili za kadi huchukuliwa kuwa tofauti ikiwa kuna safu ambapo nyumba hizo mbili zina idadi tofauti ya kadi.Mfano wa 1:Ingizo: n 16Pato: 2Maelezo: Nyumba mbili halali za kadi zimeonyeshwa.Nyumba ya tatu ya kadi kwenye mchoro si sahihi kwa sababu pembetatu ya kulia kabisa kwenye safu ya juu haijawekwa juu ya kadi ya mlalo.Mfano wa 2:Ingizo: n 2Pato: 1Maelezo: Nyumba moja halali ya kadi imeonyeshwa.Mfano wa 3:Ingizo: n 4Pato: 0Maelezo: Nyumba tatu za kadi kwenye mchoro si halali.Nyumba ya kwanza ya kadi inahitaji kadi ya usawa iliyowekwa kati ya pembetatu mbili.Nyumba ya pili ya kadi hutumia kadi 5.Nyumba ya tatu ya kadi hutumia kadi 2.Vikwazo: 1 n 500  <response>: kutoka kwa makusanyo leta defaultdictdef maxQualityRecadjDict, maadili, nodi, timeLeft, alitembelea: ikiwa mudaUmebaki 0: return float-inf ubora wa juu 0 alitembelea.ongezanodi kwa jirani, wakati katika adjDictnode: adjDictjirani.ondoanodi, wakati maxQuality maxmaxQuality, maxQualityRecadjDict, values, neighbour, timeLeft - time, alitembelea adjDictjirani.ongezanodi, wakati alitembelea.ondoanodi return maxQuality maadilinodi ikiwa nodi haijatembelewa kwingine 0def maxQualityn, maadili, kingo, maxTime: adjDict defaultdictorodha kwa ajili yako, v, wakati katika kingo: adjDictu.ongeza v, wakati adjDictv.ongezau, wakati alitembelea set return maxQualityRecadjDict, values, 0, maxTime, alitembelea 