Şokolad#7253
Şokolad, hansı ki, "Nəm Nəm" konfet şirkəti tərəfindən istehsal olunur, kvadratcikdən ibarət 1\times N ölçülü plitka şəklindədir. Hər bir kvadratcikdə məşhur konfet ustasından biri təsvir olunub. Şirkət tərəfindən istehsal olunan müxtəlif şokoladlarda eyni konfet ustası təsvir olunur, lakin fərqli ardıcıllıqla.
Tapşırıq. İki şokolad plitkasında portretlərin verilmiş ardıcıllığı üçün birinci plitkanı neçə ən az hissəyə bölmək lazım olduğunu müəyyən edən proqram yazın ki, onun hissələrini dəyişməklə ikinci plitkanı yaratmaq mümkün olsun. Plitkanı yalnız kvadratciklərin sərhədləri boyunca qırmaq olar, plitkanı və ya onun hissələrini çevirmək olmaz.
Giriş faylının ilk sətri şokolad plitkasının ölçüsünü, yəni kvadratciklərin sayını təyin edən (2 \le N \le 10^5) natural ədədini ehtiva edir. Bütün konfet ustaları -dən -ə qədər nömrələnib. Faylın ikinci və üçüncü sətrləri hər biri fərqli natural ədəd ehtiva edir (bütün ədədlər -dən çox deyil) — müvafiq olaraq birinci və ikinci plitkalardakı portretlərin ardıcıllığı. Bu ardıcıllıqların fərqli olduğu məlumdur.
Çıxış faylına yalnız bir ədəd yazılmalıdır — birinci plitkanı ikinci plitkadakı portretlərin ardıcıllığını əldə etmək üçün hansısa şəkildə dəyişməklə ən az neçə hissəyə bölmək lazım olduğunu göstərən ədəd.
Nümunə 1
Birinci plitkanı dörd hissəyə belə bölmək olar: kvadratcik , kvadratcik , iki kvadratcik və , kvadratcik . Bu hissələri lazım olan şəkildə dəyişməklə, ikinci plitkadakı portretlərin eyni ardıcıllığını əldə edəcəyik. Üç və ya iki hissəyə bölməklə ikinci plitkadakı portretlərin eyni ardıcıllığını əldə etmək mümkün deyil.
Test dəsti 4 blokdan ibarətdir, hansı ki, əlavə olaraq aşağıdakı şərtlər yerinə yetirilir:
20 bal: 2 \le N \le 3
20 bal: 3 < N \le 6
30 bal: 6 < N \le 1000
30 bal: 1000 < N \le 10^5