\\ ......... [[https://hapky.fel.cvut.cz/sou/assignments.php| Zpět do seznamu úloh]] ......... \\ ==== Barvy domečků a střech ==== Quido a Hugo bydlí v téže ulici. Ulice vede kolem břehu jezera, a tak má jen jednu řadu domečků. Domečky mají různé barvy a také jejich střechy mají různé barvy, které mnohdy s barvou domečku ladí nebo neladí, podle vkusu majitelů a také podle toho, která nejlacinější barva byla k dostání, když se domeček nebo střecha naposled opravovaly. Na jedné ze svých cest za Hugem si Quido nedávno všiml, že mezi jeho a Hugovým domečkem se najdou všechny možné barvy domečků, které jsou v ulici. Započítal přitom i svůj a Hugův domeček. Hugo v podobné situaci o den později si naopak všiml, že totéž platí o barvách střech: Ze všech barev střech v ulici se najde každá na některé střeše domečku mezi Hugem a Quidem včetně střech na domečcích obou přátel. Na procházce příštího dne pak zkontrolovali, že se opravdu nemýlili, a Quido řekl: "Kdybych ale nezapočítal buďto můj nebo tvůj domeček, tak by už moje zjištění o barvách domečků neplatilo." "Vidíš," odpověděl Hugo, "o barvách střech se dá říci přesně totéž." {{ :2014_15:img1sm.jpg?nolink |}} ** Obrázek 1.** Pohled z jezera na ulici, kde bydlí Quido a Hugo. Pro přehled jsou u domečků uvedena jejich čísla. Quido a Hugo bydlí v číslech 7 a 12, nevíme sice, kdo ve kterém, ale to nám teď nevadí. ==== Úloha ==== Je dána posloupnost barev domečků v pořadí, jak vedle sebe stojí v ulici a také je dána posloupnost barev střech domečků ve stejném pořadí. Máme určit všechny možné dvojice domečků, ve kterých mohou Quido a Hugo bydlet. \\ \\ **Zkontrolujte si uvedené příklady a najděte správné řešení pro vstupní data dole na stránce pod příklady.** \\ \\ ---- === Vstup === Vstup obsahuje tři textové řádky. První řádek obsahuje jedno celé kladné číslo N představující počet domečků v ulici. Na druhém řádku je uvedeno bez mezer N malých znaků anglické abecedy, každý znak kóduje jednu barvu domečku. Na třetím řádku je opět uvedeno bez mezer N malých znaků anglické abecedy, tentokrát každý znak kóduje jednu barvu střechy odpovídajícího domečku. Pořadí znaků na obou řádcích odpovídá pořadí domečků v ulici. Pořadí je číslováno od jedničky. Hodnota N nepřesáhne 1000000. === Výstup === Výstup obsahuje několik textových řádků, na každém řádku jsou uvedena dvě celá čísla oddělená mezerou. Čísla představují dvojici domečků, ve kterých mohou Quido a Hugo bydlet.\\ Na řádku je vždy napřed menší číslo a řádky mohou být uvedeny v libovolném pořadí.\\ Je zaručeno, že hledaná dvojice domečků je vždy alespoň jedna.\\ === Příklad 1 === == Vstup == 17 ccbdbacddbdadacbd iikkmimiihhkkiimm == Výstup == 7 12 //Schéma ilustrující situaci v příkladu 1 je znázorněno na obrázku 1.// === Příklad 2 === == Vstup == 9 abcabcabc kkmookmom == Výstup == 2 4 5 7 6 8 === Příklad 3 === == Vstup == 80 sydhhppyphydyppyyppyppppppypphyppppsdydhsdhppyspsphydyhdphppysysdpyppphpypppyssy qyrkyyqyryrqrrrryrrrrrykrrrrrkrrrrrdqdqyrddqrrqrkdyrydqkqqykyydkqrkykrykkryrydkr == Výstup == 12 36 65 78 === Příklad 4 a 5 === V příkladu 4 je 10 000 domečků, v příkladu 5 jich je 1 000 000, můžete si je stáhnout zazipované i s výsledky: {{:2014_15:priklad4a5.zip| tady}}.\\ ==== Vaše řešení ==== * Stáhněte si soubory {{:2014_15:zadani1a2.zip| zadani1.txt a zadani2.txt}}. Každý obsahuje jedna vstupní data ve stejném formátu jako uvedené příklady. V prvním souboru je 20 000 domečků a ve druhém souboru je 1 000 000 domečků.\\ * Vytvořte dva textové soubory reseni1.txt a reseni2.txt a do každého zapište odpovídající řešení ve správném formátu.\\ * Oba soubory zazipujte do jednoho archivu (s příponou .zip, na jeho jménu nesejde) a odevzdejte [[https://hapky.fel.cvut.cz/sou/assignments.php| do odevzdávacího systému Hapky]]. ==== Vaše hodnocení ==== Za každé správně vyřešené zadání získáte 10 bodů, takže za obě správně vyřešená zadání získáte celkem 20 bodů.