====== K-Equivalence ======

تابع ‎$f_{a,b}(x)$‎ برابر است با عددی که اگر تمامی ارقام ‎$a$‎ آن را به ‎$b$‎ و تمام ارقام ‎$b$‎ آن را به ‎$a$‎ تبدیل کنیم برابر با ‎$x$‎ شود‎.
‎

به دو عدد   ‎$1 \leq x   و   y  \leq 9$ ‎  می‌گوییم ‎k-equivalent اگر به ازای هر ‎$(i \in K)$‎ ، $f_{x,y}(i)$‎ عضو ‎$K$‎  باشد. می‌توانید بررسی کنید که رابطه k-equivalent‎ یک رابطه‌ی هم ارزی است‎.
‎
به شما مجموعه ‎$K$‎ داده شده است، شما باید تمام رده‌های k-equivalence‎ اعداد ‎$1$‎ تا ‎$9$‎ را به دست آورید.
‎
===== ورودی =====

  * در سطر اول ورودی عدد ‎$1 \leq n \leq 10^4$‎ آمده است. در ‎$n$‎ سطر بعدی در هر سطر یک بازه آمده است‎.
  * مجموعه ‎$K$‎ برابر با اجتماع بازه‌های داده شده است‎.
  * تمام اعداد ورودی در بازه ‎$1$‎ و ‎$10^{18}$‎ قرار می‌گیرند.
 
===== خروجی =====

در هر سطر خروجی یک رده از اعداد k-equivalent‎ را چاپ نمایید‎.
‎

هر رده به صورت تعدادی عدد مرتب کنار هم است. سطر های خروجی باید به صورت ‎lexicographically‎ مرتب باشند‎.
‎
‎
===== محدودیت‌ها =====

  * محدودیت زمان: ۲ ثانیه
  * محدودیت حافظه: ۲۵۶ مگابایت

===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|1‎ \\ 1 566‎ | ‎1234‎‎ \\ 5 \\ 6‎ \\ 789‎|
|1‎ \\ 30 75‎ | 12 \\ 345 \\ 6 \\ 7‎ \\ 89|
</WRAP>


<پاسخ>
‎
فرض کنید مجموعه ‎$K$‎  از بازه های مجزای ‎$[a_2,b_2]$‎ ، ‎$[a_1,b_1]$‎ تا ‎$[a_n,b_n]$‎ تشکیل شده باشد و ‎$b_i < a_{i+1}$‎.

فرض کنید تابع ‎$g(x,y,t)$‎ برابر باشد با کم‌ترین ‎$p$‎ که ‎$p > t$‎ و ‎$f_{x,y}(p) \in K$.

 
 می‌توان نشان داد که شرط لازم و کافی برای این که ‎$x$‎ و$y$ k-equivalent باشند این است که شرایط زیر بر قرار باشد.
‎‎
  *  $g(x,y,0) = a_1$‎
  * ‎ $g(x,y,b_i) = a_{i+1},i < n$‎
  *  $g(x,y,b_n) = \infty$‎
‎ 
پس اگر ما بتوانیم تابع ‎$g$‎ را پیاده سازی کنیم می‌توانیم پاسخ سوال را به‌دست آوریم‎.

‎
برای این کار می‌توانیم سمت چپ‌ترین رقمی از ‎$g(x,y,t)$‎ که با ‎$t$‎ تفاوت دارد را محاسبه کنیم و آن را تصحیح کنیم و به جای ارقام سمت راست آن ‎0‎ قرار دهیم عدد ‎($q(t)$)‎. در صورتی که عدد به‌دست آمده عضوی از ‎$K$‎ باشد، عدد به‌دست آمده همان جواب است، در غیر این صورت مقدار ‎$g(x,y,q(t))$‎ را به عنوان جواب بر می‌گردانیم. چون در هر مرحله یکی از ارقام عدد معلوم می شود، حد اکثر پس از ‎$18$‎ مرحله جواب مشخص می شود‎.

‎
 برای به دست آوردن ‎$q(t)$‎ باید به ازای تمامی ارقام ‎$t$ (شامل صفر‌های بی‌ارزش آن) مقادیر بیش‌تر را قرار دهیم و ارقام سمت راست را برابر با ? قرار دهیم. ‎$f_{x,y}$‎ عدد به‌دست آمده یک بازه را تشکیل می‌دهد، در صورتی که این بازه با ‎$K$‎ اشتراک داشت آن را به عنوان جواب برمی‌گردانیم، در غیر این صورت به سراغ ارقام بعدی‌می رویم‎.

حال به ازای تمام ‎$a$‎ و ‎$b$‎ های بین ‎$1$‎ تا ‎$9$‎ شرایط را چک می‌کنیم و رده‌های ‎k-equivalent‎ را به‌دست می‌آوریم‎.‎
‎

**پيچيدگي**


چون هر کدام از اعداد ورودی حداکثر ‎$18$‎ رقم دارند، تمام اعمال گفته شده از ‎$o(1)$‎ می‌باشد، به غیر از چک کردن این که‌ یک بازه با ‎$K$‎ اشتراک دارد یا نه. اگر تمام ‎$a_i$‎ ها و ‎$b_i$‎ ها را به صورت مرتب داشته باشیم، با استفاده از‎binary search‎ می‌توانیم در زمان ‎$o(\log{n})$‎ چک کنیم که آیا یک بازه ‎$[a',b']$‎ با$K$‎ اشتراک دارد یا نه.
</پاسخ>

  * [[سوال ۶۵|سوال بعد]]
  * [[سوال ۶۳|سوال قبل]]