+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امیرمحمد به دلیل اوضاع فعلی،‌ در خانه مانده و حوصله‌اش سر رفته است. او می‌خواهد برای ایجاد سرگرمی و مفید بودن، سیستمی طراحی کند که مانند یک دیتابیس عمل می‌کند. هر دیتابیس شامل چند جدول است که از طریق اسم هر جدول، می‌توان به آن دسترسی داشت. خود هر جدول شامل چند سطر و چند ستون است؛ به طوری که هر ستون یک عنوان و یک جنس دارد که می‌تواند **رشته** یا **عدد** باشد و محتواهای آن ستون حتما باید از آن جنس باشند. امیرمحمد می‌خواهد برای سیستمش، بخش مدیریت کاربر نیز بگذارد به این‌صورت که دو سطح دسترسی `editor` و `viewer` وجود داشته باشد. کاربر با سطح دسترسی `editor` می‌تواند تمام دستورات را انجام دهد ولی کاربر با دسترسی `viewer` تنها می‌تواند دستورات `print` و `search` را انجام دهد (در ادامه تعریف این دو دستور آمده است) و اگر درخواست انجام دستور دیگری به غیر از این ۲ نوع دستور را داشت، باید عبارت `access denied` را چاپ شود. در ادامه دستورات موجود در این سیستم را می‌بینید: # دستور اضافه کردن کاربر create user username editor create user username viewer این دستور به این معناست که یک کاربر جدید با نام کاربری `username` و سطح دسترسی گفته شده، به سیستم اضافه شود. `username` یک رشته شامل حروف کوچک انگلیسی می‌باشد و **تضمین می‌شود** که هیچ دو کاربری،‌ نام کاربری یکسان ندارند. تضمین‌ می‌شود در هر کوئری کاربری که درخواست می‌دهد، حتما وجود داشته باشد. # دستور ایجاد و حذف کردن جدول برای ایجاد و یا حذف یک جدول به ترتیب از دستورهای زیر استفاده می‌شود: create table table_name username delete table table_name username که به ترتیب بیانگر این می‌باشد که کاربر با نام کاربری `username` درخواست اضافه‌کردن و یا حذف یک جدول با نام `table_name` را داده است. همچنین در ابتدا هر جدول که تعریف می‌شود، هیچ سطر و ستونی وجود ندارد و در ادامه می‌توان به آن، سطر و ستون اضافه کرد. # اضافه و حدف کردن ستون برای اضافه کردن ستون به سمت راست جدول، از دستور زیر استفاده می‌شود: add column table_name column_name int username add column table_name column_name string username که بیانگر این می‌باشد کاربر با نام کاربری `username` به ترتیب، درخواستی برای ایجاد یک ستون با نام `column_name` در جدول `table_name` کرده و جنس آن ستون هم در کلمه پنجم مشخص می‌شود؛ هنگامی که یک ستون اضافه می‌شود، در صورتی از جنس عدد باشد، سطرهای این ستون با مقدار ۰ و در غیراینصورت با رشته `null` پر می‌شوند. (توجه کنید که منظور از رشته‌ی `null`، یک رشته‌ی به طول ۴ می‌باشد و نه رشته‌ی تهی!) همچنین **تضمین می‌شود** در این فرآیند، هیچوقت دو ستون هم‌نام باهم در یک جدول وجود ندارند و هم‌زمان هیچ دو جدولی نام یکسان نیز ندارند. دستور بعدی، برای حذف کردن یک ستون از جدول می‌باشد: remove column table_name column_name username که بیانگر این است کاربر با نام کاربری `username` درخواست حذف ستون با نام `column_name` در جدول با نام `table_name` را داده است. # اضافه و حذف کردن سطر کاربر با نام کاربری `username` برای اضافه کردن یک سطر به آخر جدول با نام `table_name` از دستور زیر استفاده می‌کند (در هنگام استفاده از این کوئری تضمین می‌شود حداقل یک ستون در جدول وجود دارد): add row table_name username توجه کنید که وقتی یک سطر اضافه می‌شود، در ستون‌هایی که از جنس عدد باشند، مقدار ۰ و در باقی ستون‌ها رشته `null` گذاشته می‌شود.(توجه کنید که منظور از رشته‌ی `null`، یک رشته‌ی به طول ۴ می‌باشد و نه رشته‌ی تهی!) همچنین کاربر با نام کاربری `username` در جدول `table_name` برای حذف کردن یک ردیف که از بالا به پایین، $i$امین سطر می‌باشد، از دستور زیر استفاده میکند: remove row table_name i username # تغییر دادن مقدار یک خانه کاربر با نام کاربری `username` برای تغییر مقدار خانه واقع در سطر $i$ام و ستون با نام `column_name` در جدول `table_name` به مقدار `value` از دستور زیر استفاده می‌کند: change table_name i column_name value username توجه کنید که اگر این ستون از جنس عدد باشد، `value` عدد است و در غیراینصورت یک رشته از حروف کوچک انگلیسی است. # چاپ کردن این سیستم قابلیت این را دارد که بتوان چند ستون از یک جدول را مشخص کرد و جدول را بر اساس ستون‌های مشخص شده، به ترتیب اولویت مرتب کرد و در نهایت چاپ کرد. برای این‌کار اگر کاربر با نام کاربری `username` بخواهد جدول با نام `table_name` را بر اساس ستون‌های با نام‌های `col_1`، `col_2`،...، `col_k` مرتب کند و سپس جدول را خروجی دهد، از دستور زیر استفاده می‌کند: print table_name col_1 col_2 ... col_k username در این دستور، شما باید ردیف‌های جدول را به ترتیب بر اساس ستون‌های `col_1`، `col_2`،...،`col_k` به ترتیب **صعودی** مرتب کنید. یعنی ابتدا برحسب ستون `col_1` مرتب کنید، سپس ردیف‌هایی که مقدارشان در ستون `col_1` برابر بود، بر اساس مقدارشان در ستون `col_2` مرتب کنید و... . همچنین در نهایت اگر دو سطر تمامی مقادیرشان در این $k$ ستون یکسان بود، بر اساس زمان اضافه شدن سطرها به جدول مرتب‌شان کنید (یا به عبارتی دیگر بر اساس اندیس سطرها در جدول اولیه). در نظر داشته باشید که ترتیب ردیف‌ها در جدول اصلی **عوض نمی‌شود**، و با این درخواست صرفا باید جدول مرتب شده بر اساس اولویت‌ها خروجی داده شود. توجه کنید که اگر یک ستون از جنس رشته باشد، مقادیر آن بر اساس ترتیب کتابخانه‌ای به صورت صعودی مرتب می‌شوند و در غیر این صورت بر حسب مقدار عددی مرتب می‌شوند. کاربر با نام کاربری `username` برای خروجی دادن کل جدول `table_name` از دستور زیر استفاده می‌کند: (توجه کنید که در این دستور، سطرهای جدول باید به ترتیب زمان اضافه شدن به جدول، چاپ شوند و نیازی به مرتب‌سازی نیست) print table_name * username # جست‌وجو در جدول این سیستم، قابلیت جست‌وجو بر حسب یک پارامتر خاص نیز دارد. به این صورت که کاربر با نام کاربری `username` درخواست می‌دهد تا تمامی سطرهای جدول `table_name`، که مقدار آن‌ها در ستون با نام `column_name` **دقیقا** برابر با `value` است، چاپ شوند (توجه کنید که تمامی عناصر آن سطر باید چاپ شوند). برای اینکار از دستور زیر استفاده می‌کند: (در این دستور، سطرهای جدول باید به ترتیب زمان اضافه شدن به جدول، چاپ شوند) search table_name column_name value username همچنین اگر این ستون از جنس عدد باشد،‌ `value` یک عدد است و اگر جنس این ستون رشته باشد، `value` یک رشته است. تضمین می‌شود که تنها از دستورات بالا داده می‌شود و هنگامی که درخواستی داده می‌شود، تمامی ستون‌ها و جدول‌هایی که در آن دستور قید شده‌اند، وجود دارند و همچنین هیچ دو جدول و هیچ دو ستونی با نام یکسان هم‌زمان وجود ندارند. در نهایت پس از پایان عملیا‌ت‌ها، در خط‌ آخر ورودی عبارت `done` می‌آید. **پیشنهاد می‌شود حتما به ورودی‌ نمونه و پاسخ‌ آن دقت کنید.** # ورودی ورودی شامل تعدادی خط می‌باشد، که در هر خط، یکی از دستوراتی که در بالا تعریف شده‌اند، آمده است. همچنین در نهایت، در خط آخر ورودی، عبارت `done` می‌آید که برای تشخیص تمام شدن ورودی‌ها می‌باشد. تضمین می‌شود مجموع کاراکتر‌های ورودی حداکثر $40\ 000$ می‌باشد. همچنین تمامی رشته‌ها، شامل حروف کوچک انگلیسی می‌باشند و هیچکدام از اسم‌های جدول‌ها، ستون‌ها و... شامل فاصله (space) نمی‌باشد. تمامی دستورات معتبر می‌باشند یعنی اگر اسم جدول یا ستون یا... در یکی از دستورات آورده شود، تضمین می‌شود حتما آن جدول، ستون یا... وجود دارد. خانه‌هایی از جدول که از جنس عدد باشند، در بازه‌ی $[-10^9, 10^9]$ می‌باشند و همچنین طول رشته‌ها کمتر مساوی ۵۰ می‌باشد. # خروجی به ازای هر دستور مربوط به `print` و `search`، جدول را مطابق با دستور داده شده خروجی دهید. توجه کنید که در خروجی، نام ستون‌ها را نباید چاپ کنید و همچنین هر سطر در یک خط چاپ شود و در هر خط بین مقادیر دو ستون متوالی باید دقیقا یک فاصله (space) باشد. برای درک بهتر، به مثال‌های نمونه توجه کنید. # مثال ## ورودی نمونه ۱ ``` create user amin editor create user sajad viewer create table yek sajad create table do amin create table jadval amin delete table do amin add column jadval yek int amin add column jadval do string amin add column jadval se int amin add row jadval amin search jadval se 0 amin add row jadval amin print jadval * amin add row jadval amin change jadval 1 do salam amin change jadval 2 yek -3 amin print jadval yek do amin remove row jadval 3 amin remove column jadval do amin change jadval 1 yek 3 amin print jadval * amin search jadval yek 3 amin done ``` ## خروجی نمونه ۱ ``` access denied 0 null 0 0 null 0 0 null 0 -3 null 0 0 null 0 0 salam 0 3 0 -3 0 3 0 ``` در ابتدا هنگامی که کاربر `sajad` درخواست ساخت جدول می‌دهد، `access denied` چاپ می‌شود. در دستورات `print` و ‍‍‍`search` که در ادامه آمده‌اند، به ترتیب خروجی‌های زیر چاپ می‌شوند: ``` 0 null 0 ``` ``` 0 null 0 0 null 0 ``` ``` -3 null 0 0 null 0 0 salam 0 ``` ``` 3 0 -3 0 ``` ``` 3 0 ``` # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19679/) مطرح کنید. <details class="blue"> <summary> راهنمایی ۱ </summary> برای پیاده‌سازی راحت‌تر و اصولی‌تر این سوال، باید سعی کنید از ساختار شی‌گرایی استفاده کنید. برای این منظور، می‌توانید یک کلاس داشته باشید که در آن مدیریت جدول‌ها (نگهداری لیست جدول‌ها و حذف و اضافه کردن جدول) انجام شود. همچنین برای هر جدول می‌‌توانید یک کلاس داشته باشید که اطلاعات جدول از قبیل نام ستون‌ها و جنس آن‌ها، محتوای درون هر ردیف یا ستون و... را نگهداری کند. همچنین **برای هر کدام** از درخواست‌های سوال که مربوط به ایجاد تغییرات در جدول و یا چاپ و جست‌وجو می‌باشد، یک تابع تعریف کنید که بتواند آن کار را انجام دهد. </details> <details class="blue"> <summary>راهنمایی ۲</summary> یکی دیگر از بخش‌های این سوال که چالش برانگیز است، این است که چگونه ورودی را بخوانیم و تشخیص دهیم که کدام دستور را باید انجام دهیم و اینکه آیا کاربری که کار مورد نظر را می‌خواهد بکند،‌ دسترسی کافی دارد یا نه (برای تشخیص اینکه `access denied` چاپ کنیم یا کار مورد نظر را انجام دهیم). در هر مرحله، هر خط را ورودی می‌گیریم‌ و سپس کلمه‌های آن را بر حسب کاراکتر فاصله (space) از هم جدا می‌کنیم. برای اینکار می‌توانیم خودمان یک تابع بنویسیم که یک رشته ورودی بگیرد و یک آرایه از رشته‌ها خروجی بدهد و یا همچنین می‌توانیم از تابع *split* استفاده کنیم که در اکثر زبان‌ها وجود دارد. برای مثال اگر رشته‌ی `world is good` را به آن بدهید و بخواهید بر اساس فاصله جدا کنید، خروجی یک آرایه شامل ۳ عضو `world` ، `is` و `good` می‌باشد. ابتدا برای چک کردن اینکه درخواست معتبر می‌باشد یا نه، عضو آخر آرایه را می‌گیرید (عضو آخر، دقیقا همان `username` می‌باشد) و اگر عضو اول آرایه، برابر `print` یا `search` نبود، باید چک کنید که `username` مورد نظر دسترسی `editor` دارد یا نه. همچنین برای انجام بقیه دستور‌ها هم مشابه بالا می‌توانید کار کنید، یعنی با استفاده از دستور‌های شرطی (*if*)، ابتدا برحسب عضو اول آرایه، حالت بندی کنید، سپس دستورهایی که ممکن است کلمه اولشان یکسان باشد را برحسب کلمه دوم یا... مقایسه کنید. به این صورت به سادگی می‌توانید دستورهای مختلف را از هم جدا کنید. </details> <details class="blue"> <summary>راهنمایی ۳</summary> در بخش راهنمایی، میخواهیم به نحوه پیاده سازی دستور چاپ کردن جدول بپردازیم. هنگامی که هر خط ورودی را بر اساس فاصله (space) جدا کنید، در صورتی که کلمه اول برابر با `print` باشد، باید جدول را چاپ کنید، اما دو نوع دستور مختلف وجود دارد برای این‌کار. در صورتی که کلمه‌ی سوم برابر با `*` باشد، باید تمامی جدول را خروجی دهید و در غیراینصورت باید جدول را به نوع دیگر خروجی دهید. یعنی بر اساس اولویت مرتب سازی کنید. فرض کنید اولویت اول برحسب ستون `col_1`، اولویت دوم برحسب ستون `col_2` و در نهایت اولویت $k$ام برحسب ستون `col_k` باشد. می‌توانید با استفاده از نوشتن یک تابع *compare* این‌کار را انجام دهید. کار این تابع به این صورت می‌باشد که دو عنصر می‌گیرد و سپس خروجی‌اش این است که عنصر اول بزرگتر است یا عنصر دوم بزرگتر است یا هر دو عنصر مساوی می‌باشند. شما می‌توانید با استفاده از یک حلقه، به ترتیب این دو عنصر را برحسب اولویت‌ها مقایسه کنید. همچنین روش دوم برای این‌کار، این است که ابتدا همه‌ی سطرها را بر حسب اولویت $k$ام مرتب کنید. سپس همه‌ی سطر‌ها را بر حسب اولویت $k - 1$ ام مرتب کنید و در نهایت بر حسب اولویت اول مرتب کنید. توجه کنید که در هر کدام از این دو روش، مرتب‌سازی‌ای که انجام می‌دهید، باید *stable* باشد، یعنی اگر در یکی از مراحل، سطری اندیس $i$ و سطر دیگری اندیس $j$ داشته باشد ($i < j$)، در مرحله‌ی بعد پس از مرتب سازی،‌ در صورتی که این دو سطر در تمامی اولویت‌ها باهم برابر باشند، باز هم سطری که در مرحله‌ی پیش اندیس $i$ داشت، پیش از سطر دیگری آمده باشد. یعنی ترتیب سطر‌های برابر عوض نشوند. </details>