• محدودیت زمان: ۰٫۵ ثانیه
• محدودیت حافظه: ۶۴ مگابایت

دنباله‌ای به طول $n$ به فرم $a_1, a_2, \dots, a_n \,$ از اعداد صحیح داریم. می‌دانیم هیچ عددی در این دنباله، بیش از ۲ بار ظاهر نشده است. برای مثال این دنباله می‌تواند به صورت $4, 3, 2, 7, 8, 2, 3, 1$ باشد.

به یک عدد صحیح «یکتا» می‌گوییم اگر فقط یک‌بار در این دنباله ظاهر شده باشد. برای مثال، در دنباله بالا تنها اعداد $1$، $4$، $7$ و $8$ «یکتا» هستند.

از شما می‌خواهیم برنامه‌ای بنویسید که با دریافت اعداد موجود در این دنباله، ‍XOR اعداد «یکتا» آن را چاپ کند. اگر هیچ عدد «یکتا»یی در این دنباله نبود، صفر چاپ کنید.

ورودی🔗

در خط اول ورودی، عدد طبیعی $n$ نوشته می‌شود.

$1 \leq n \leq 100$

در خط دوم، اعداد آرایه که با یک فاصله از یکدیگر جدا شده‌اند نوشته می‌شوند.

$1 \leq a_i \leq 100$

خروجی🔗

در تنها سطر خروجی، XOR اعداد «یکتا»ی این دنباله را چاپ کند. اگر هیچ عدد «یکتا»یی در این دنباله نبود، $0$ چاپ کنید.

ورودی نمونه ۱🔗

2
1 1

خروجی نمونه ۱🔗

0

هیچ عدد یکتایی در دنباله $1, 1$ وجود ندارد، بنابراین پاسخ این نمونه ۰ خواهد بود.

ورودی نمونه ۲🔗

8
4 3 2 7 8 2 3 1

خروجی نمونه ۲🔗

10

اعداد یکتای دنباله $4, 3, 2, 7, 8, 2, 3, 1$ همان $1$، $4$، $7$ و $8$ هستند بنابراین پاسخ این نمونه برابر است با: $1 \oplus 4 \oplus 7 \oplus 8 = 10$

ورودی نمونه ۳🔗

2
2 1

خروجی نمونه ۳🔗

3

همه اعداد دنباله $1, 2$، یکتا هستند. بنابراین پاسخ این نمونه برابر است با: $2 \oplus 1 = 3$

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

سال ۱۴۹۹ است و دیجی‌کال‍ا از رمزارز خود با نام دیجی‌رمز رونمایی کرده است!

علی می‌خواهد از طریق سرمایه‌گذاری در این رمزارز، $m$ تومان پول کسب کند، اما در حال حاضر هیچ سرمایه‌ای ندارد. او می‌خواهد از دوستش پول قرض کند تا این سرمایه‌گذاری‌ها را انجام دهد.

در بازار دیجی‌رمز ، $n$ فرصت سرمایه‌گذاری وجود دارد که $i$اُمین آن‌ها ابتدا به $c_i$ تومان پول برای شروع نیاز دارد و پس از سرمایه‌گذاری، هر روز $p_i$ تومان سود می‌دهد. علی در هر یک از این فرصت‌ها می‌تواند حداکثر یک بار سرمایه‌گذاری کند، اما او می‌تواند در هر چند فرصت مختلفی که بخواهد سرمایه‌گذاری کند.

به علی کمک کنید تا روشی برای سرمایه‌گذاری انتخاب کند که در کوتاه‌ترین زمان بتواند تمام پول قرض‌گرفته‌شده از دوستش را به او پس بدهد و برای خودش هم حداقل $m$ تومان پول بماند تا به هدفش برسد.

به او بگویید کوتاه‌ترین زمان چند روز است.

ورودی🔗

در سطر اول ورودی دو عدد صحیح و مثبت $n$ و $m$ با فاصله از هم آمده است. $1 \le n \le 100\ 000$

$1 \le m \le 10^9$

در $n$ سطر بعدی، در هر خط دو عدد $p_i$ و $c_i$ که با یک فاصله از هم جدا‌شده‌اند آمده است. $1 \le p_i, c_i \le 10^9$

خروجی🔗

در تنها سطر خروجی کمترین تعداد روزی که لازم است تا علی بعد از پس دادن پول دوستش $m$ تومان سود کند را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

2 5
4 10
10 15

خروجی نمونه ۱🔗

2

اگر علی ۲ روز در فرصت سرمایه‌گذاری دوم سرمایه‌گذاری کند، به اندازه‌ی $2 \times 10 - 15 = 5 \geq 5$ سود می‌کند و به هدفش می‌رسد.

ورودی نمونه ۲🔗

4 10
1 8
3 12
4 17
10 100

خروجی نمونه ۲🔗

6

اگر علی ۶ روز در فرصت سرمایه‌گذاری دوم و سوم سرمایه‌گذاری کند، به اندازه‌ی $(6 \times 3 - 12) + (6 \times 4 - 17) = 6 + 7 = 13 \geq 10$ سود می‌کند و به هدفش می‌رسد.

ورودی نمونه ۳🔗

3 5
4 1
9 10
6 3

خروجی نمونه ۳🔗

1

اگر علی ۱ روز در فرصت سرمایه‌گذاری اول و سوم سرمایه‌گذاری‌کند، به اندازه‌ی $(1 \times 4 - 1) + (1 \times 6 - 3) = 3 + 3 = 6 \geq 5$ سود می‌کند و به هدفش می‌رسد.

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

نقشه متروی تهران را در نظر بگیرید. (این عکس فقط برای دادن یک دید کلی به شماست و نیازی به خواندن کلمات آن نیست.)

اسم تمام ایستگاه‌ها در این فایل در ۷ سطر آمده است. در سطر $i$ام، نام ایستگاه‌های خط $i$ام مترو به ترتیب و با فاصله آمده است. (توجه کنید نام یک ایستگاه شامل کاراکتر فاصله (space) نیست.)

• زمان لازم تردد قطار بین دو ایستگاه ۲ دقیقه
• زمان لازم برای ورود به ایستگاهی که قصد سوار شدن قطار را داریم، ۱۷ دقیقه
• زمان لازم برای خارج شدن از ایستگاه که قصد پیاده زدن در آن را داریم، ۱۲ دقیقه.
• زمان لازم برای تعویض خط نیاز داریم، نیز ۱۰ دقیقه است.

توجه کنید در ایستگاه‌هایی که محل تقاطع دو خط هستند، می‌توان از طریق هر دو خط سوار شد و نیازی به معطلی برای تعویض خط نداریم.

محسن می‌خواهد خریدهای خودش را از دیجیکالا انجام ندهد و با مترو برود و خرید کند. او بعد از مسیریابی فهمید که باید از ایستگاه $s$ سوار مترو شود و در ایستگاه $f$ پیاده شود.

از شما می‌خواهیم برنامه‌ای بنویسید که کمترین زمانی که طول می‌کشد تا محسن به محل خرید برسد را محاسبه کنید.

ورودی🔗

در سطر اول ورودی عدد صحیح و مثبت $q$ آمده است. $1 \leq q \leq 16000$ در $q$ سطر بعدی در هر سطر دو رشته $s$ و $f$ آمده که نام ایستگاه شروع و پایان را نشان می‌دهد.

تضمین می‌شود این دو رشته در فایل ایستگاه‌ها موجوداند.

خروجی🔗

برای هر کدام از $q$ جفت ایستگاه ورودی داده شده، کمینه زمان لازم برای رسیدن از ایستگاه مبدا به ایستگاه مقصد را محاسبه کنید.

مثال🔗

ورودی نمونه ۱🔗

5
Tajrish Gheytariyeh
Tajrish Gholhak
Tarasht Eram-e_Sabz
Aghdasiyeh Sohrevardi
Towhid Baharestan

خروجی نمونه ۱🔗

31
35
43
45
51

سفر اول از «تجریش» به «قیطریه»:

• ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «تجریش» طول می‌کشد.
• ۲ دقیقه طول می‌کشد تا در خط ۱، از ایستگاه «تجریش» به «قیطریه» برسد.
• ۱۲ دقیقه طول می‌کشد تا از ایستگاه «قیطریه» خارج شود.

بنابراین مجموع زمان این سفر برابر است با: $17 + 2 + 12 = 31$

سفر دوم از «تجریش» به «قلهک»:

• ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «تجریش» طول می‌کشد.
• ۶ دقیقه طول می‌کشد تا در خط ۱، از ایستگاه «تجریش» به «قلهک» برسد.
• ۱۲ دقیقه طول می‌کشد تا از ایستگاه «قلهک» خارج شود.

بنابراین مجموع زمان این سفر برابر است با: $17 + 6 + 12 = 35$

سفر سوم از «طرشت» به «ارم سبز»:

• ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «طرشت» طول می‌کشد.
• ۲ دقیقه طول می‌کشد تا در خط ۲، از ایستگاه «طرشت» به «تهران (صادقیه)» برسد.
• ۱۰ دقیقه طول می‌کشد تا از خط از ۲ به ۵ در ایستگاه «تهران (صادقه)» تغییر مسیر بدهد.
• ۲ دقیقه طول می‌کشد تا در خط ۵، از ایستگاه «تهران (صادقیه)» به «ارم سبز» برسد.
• ۱۲ دقیقه طول می‌کشد تا از ایستگاه «ارم سبز» خارج شود.

بنابراین مجموع زمان این سفر برابر است با: $17 + 2 + 10 + 2 + 12 = 43$

سفر چهارم از «اقدیسه» به «سهروردی»:

• ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «اقدسیه» طول می‌کشد.
• ۱۶ دقیقه طول می‌کشد تا در خط ۳، از ایستگاه «اقدسیه» به «سهروردی» برسد.
• ۱۲ دقیقه طول می‌کشد تا از ایستگاه «سهروردی» خارج شود.

بنابراین مجموع زمان این سفر برابر است با: $17 + 16 + 12 = 45$

سفر پنجم از «توحید» به «بهارستان»:

• ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «توحید» طول می‌کشد.
• ۱۰ دقیقه طول می‌کشد تا در خط ۴، از ایستگاه «توحید» به «دروازه شمیران» برسد.
• ۱۰ دقیقه طول می‌کشد تا از خط از ۴ به ۲ در ایستگاه «دروازه شمیران» تغییر مسیر بدهد.
• ۲ دقیقه طول می‌کشد تا در خط ۵، از ایستگاه «دروازه شمیران» به «بهارستان» برسد.
• ۱۲ دقیقه طول می‌کشد تا از ایستگاه «بهارستان» خارج شود.

بنابراین مجموع زمان این سفر برابر است با: $17 + 10 + 10 + 2 + 12 = 51$

کوئری‌های شما باید روی آخرین نسخه‌ی MySQL قابل اجرا باشند.

محمد به‌تازگی به تیم مهندسی دیجی‌کال‍ا پیوسته. او در یکی از تسک‌هایش لازم دارد تا کوئری‌های مختلفی برای کار با داده‌هایی که با آن‌ها سروکار دارد بنویسد. داده‌هایی که محمد با آن‌ها سروکار دارد مربوط به محصولات و سفارش‌های مربوط به آن‌ها است. او یک denormalization روی داده‌ها اعمال کرده، به این‌صورت که علاوه بر اطلاعات سفارش‌های محصولات، مجموع فروش هر محصول نیز در جدول اطلاعات محصولات وجود دارد.

از آن‌جایی که محمد فرصت نوشتن کوئری‌های مدنظرش را ندارد، از شما می‌خواهیم تا این کوئری‌ها را برایش بنویسید.

جزئیات پروژه🔗

داده‌های اولیه برای تست نمونه را از این لینک دانلود کنید.

ساختار جداول به‌شرح زیر است:

جدول products: از این جدول برای نگه‌داری اطلاعات محصولات استفاده می‌شود. ساختار این جدول به‌صورت زیر است:

جدول orders: از این جدول برای نگه‌داری لیست سفارش‌ها استفاده می‌شود. ساختار این جدول به‌صورت زیر است:

جدول order_details: از این جدول برای نگه‌داری اطلاعات اقلام موجود در سفارش‌ها استفاده می‌شود. ساختار این جدول به‌صورت زیر است:

جدول delivery_centers: از این جدول برای نگه‌داری اطلاعات مراکز ارسال استفاده می‌شود. ساختار این جدول به‌صورت زیر است:

جدول deliveries: از این جدول برای نگه‌داری اطلاعات تحویل سفارش‌ها استفاده می‌شود. ساختار این جدول به‌صورت زیر است:

توجه داشته باشید که جدول کاربران صرفاً جهت سادگی در سؤال نیامده است. نیازی به اطلاعات چنین جدولی نیست.

مطلوبات🔗

کوئری‌های زیر را طوری بنویسید که خروجی خواسته‌شده به‌دست آید:

1. محمد اکنون متوجه شده که یک باگ در بک‌اند برنامه‌اش وجود داشته و مقدار ستون total_profit در جدول products لزوماً مطابق با اطلاعات موجود در جداول orders و order_details نیست (در داده‌ها inconsistency وجود دارد). کوئری‌ای بنویسید که مقدار ستون total_profit جدول products را طبق مقادیر موجود در جداول orders و order_details به‌روزرسانی کند تا inconsistency در صورت وجود رفع شود.
2. کوئری‌ای بنویسید که شناسه‌ی ۵ مرکز ارسال برتر از نظر چابک بودن را برگرداند. یک مرکز ارسال در صورتی چابک است که میانگین اختلاف زمانی بین دریافت محصول از انبار تا تحویل آن به مشتری در سفارش‌های تحویل‌داده‌شده‌اش کمتر از سایر مراکز ارسال باشد. نتایج را به‌ترتیب نزولی میزان چابک بودن مرتب کنید. تضمین می‌شود که میزان چابک بودن مراکز ارسال با یکدیگر متفاوت است. نام ستون خروجی اهمیتی ندارد.
3. کوئری‌ای بنویسید که شناسه‌ی محصولاتی که تا ۷ روز پس از انتشارشان کمتر از ۱۰ فروش داشتند را دریافت کند. نام ستون خروجی اهمیتی ندارد.

نکات🔗

• کوئری‌های شما باید روی آخرین نسخه‌ی MySQL قابل اجرا باشند.
• کوئری هر بخش باید تنها شامل یک statement باشد.
• هر کوئری امتیاز جداگانه دارد و اگر کوئری یک قسمت را نتوانستید بنویسید، کوئری‌هایی که حل کردید را بفرستید و قسمت آن کوئری را خالی بگذارید.
• در تست نمونه‌ی این سؤال، فقط کوئری بخش اول تست می‌شود.

آن‌چه باید آپلود کنید🔗

پس از طراحی کوئری‌ها، آن‌ها را در قالب زیر در یک فایل با پسوند .sql آپلود کنید.

-- Section1
    Your first query here
-- Section2
    Your second query here
-- Section3
    Your third query here

کوئری‌های شما باید روی آخرین نسخه‌ی MySQL قابل اجرا باشند.

در تیم مهندسی دیجی‌کال‍ا، یک سیستم رده‌بندی برای سطح مهندسین وجود دارد. امیرحسین که قصد ارتقای درجه‌ی چند نفر از اعضای تیم را دارد، تصمیم گرفته تا سؤالی در خصوص ایندکس‌های دیتابیس از آن‌ها بپرسد و مطمئن شود که آن‌ها درک خوبی از دیتابیس دارند. او سؤالات را از قبل آماده کرده، اما فرصت نوشتن پاسخ نمونه برای این سؤالات را ندارد. از شما می‌خواهیم تا کوئری‌های مدنظر امیرحسین را بنویسید.

جزئیات پروژه🔗

داده‌های اولیه برای تست نمونه را از این لینک دانلود کنید.

ساختار جداول به‌شرح زیر است:

جدول users: از این جدول برای نگه‌داری اطلاعات کاربران استفاده می‌شود. ساختار این جدول به‌صورت زیر است:

جدول products: از این جدول برای نگه‌داری اطلاعات محصولات استفاده می‌شود. فرض می‌شود که هر محصول تنها متعلق به یک دسته‌بندی است! ساختار این جدول به‌صورت زیر است:

توجه داشته باشید که جدول دسته‌بندی‌های محصولات صرفاً جهت سادگی در سؤال نیامده است. نیازی به اطلاعات چنین جدولی نیست.

مطلوبات🔗

کوئری‌های خواسته‌شده از شما، موارد زیر است:

1. کوئری ساخت ایندکس جهت بهینه‌سازی حداکثری سرعت دریافت شناسه‌ی کاربرانی که نام‌شان با یک رشته‌ی خاص آغاز می‌شود:

SELECT id
FROM users
WHERE name LIKE 'Ali%'

2. کوئری ساخت ایندکس جهت بهینه‌سازی حداکثری سرعت دریافت شناسه، نام و قیمت محصولاتی که قیمت‌شان بین دو عدد مشخص است و مربوط به یک دسته‌ی خاص هستند:

SELECT id, name, price
FROM products
WHERE price > 25000 AND price < 50000000 AND category_id = 5

نکات🔗

• کوئری‌های شما باید روی آخرین نسخه‌ی MySQL قابل اجرا باشند.
• کوئری هر بخش باید تنها شامل یک statement باشد.
• هر کوئری امتیاز جداگانه دارد و اگر کوئری یک قسمت را نتوانستید بنویسید، کوئری‌هایی که حل کردید را بفرستید و قسمت آن کوئری را خالی بگذارید.
• در تست نمونه‌ی این سؤال، فقط کوئری بخش اول تست می‌شود.

آن‌چه باید آپلود کنید🔗

پس از طراحی کوئری‌ها، آن‌ها را در قالب زیر در یک فایل با پسوند .sql آپلود کنید.

-- Section1
    Your first query here
-- Section2
    Your second query here

این سؤال تنها با زبان‌های PHP ، Python ، Go و JS (Node.js) قابل حل است.

دیجی‌کال‍ا قصد دارد برای بخش تحویل محصولات خود یک سامانه‌ی ساده‌ی ثبت پیشنهادات و انتقادات راه‌اندازی کند. از شما می‌خواهیم یک API برای این سامانه طراحی کنید.

جزئیات پروژه🔗

پروژه‌ی اولیه را از این لینک دانلود کنید.

در این سؤال، یک REST API شامل endpoint های زیر باید پیاده‌سازی شود:

در این API هر کاربر باید یک توکن داشته باشد. این توکن برای هر کاربر ثابت است.

در همه‌ی endpoint ها، پاسخ باید به‌صورت JSON باشد.

اطلاعات ورودی به‌صورت application/x-www-form-urlencoded به endpoint ها ارسال می‌شوند.

بررسی up بودن سرویس🔗

پاسخ این endpoint باید به‌صورت زیر باشد:

• کد وضعیت: 200
• بدنه: {"ok":true}

ثبت‌نام🔗

دو پارامتر username و password باید به این endpoint ارسال شوند. در صورتی که حداقل یکی از این پارامترها ارسال نشده باشد یا برابر با رشته‌ی خالی باشد، پاسخ باید به‌صورت زیر باشد:

• کد وضعیت: 400
• بدنه: {"ok":false,"error":"no username or password provided"}

اگر کاربری با نام کاربری واردشده از قبل موجود باشد، پاسخ باید به‌صورت زیر باشد:

• کد وضعیت: 400
• بدنه: {"ok":false,"error":"user already exists"}

در غیر این‌صورت، کاربر باید ساخته شود، یک توکن یکتا برایش تولید شود و پاسخ به‌صورت زیر باشد:

• کد وضعیت: 201
• بدنه: {"ok":true,"token":"USER_TOKEN"}

ورود به حساب کاربری🔗

دو پارامتر username و password باید به این endpoint ارسال شوند. در صورتی که حداقل یکی از این پارامترها ارسال نشده باشد یا برابر با رشته‌ی خالی باشد، پاسخ باید به‌صورت زیر باشد:

• کد وضعیت: 400
• بدنه: {"ok":false,"error":"no username or password provided"}

اگر نام کاربری یا رمز عبور نادرست باشد، پاسخ باید به‌صورت زیر باشد:

• کد وضعیت: 400
• بدنه: {"ok":false,"error":"invalid username or password"}

در غیر این‌صورت، پاسخ باید به‌صورت زیر باشد:

• کد وضعیت: 200
• بدنه: {"ok":true,"token":"USER_TOKEN"}

کوتاه کردن لینک🔗

این endpoint نیازمند authentication است. در ریکوئست ارسالی مقدار هدر Authorization باید برابر با توکن کاربر باشد (بدون Bearer یا موارد مشابه).

پارامتر url (لینک) باید به این endpoint ارسال شود. در صورتی که این پارامتر ارسال نشده باشد یا برابر با رشته‌ی خالی باشد، پاسخ باید به‌صورت زیر باشد:

• کد وضعیت: 400
• بدنه: {"ok":false,"error":"no url provided"}

در غیر این‌صورت، لینک باید کوتاه شود و پاسخ به‌صورت زیر باشد (مقدار {slug} می‌تواند رندوم باشد):

• کد وضعیت: 201
• بدنه: {"ok":true,"url":"http://localhost/{slug}"}

دریافت لیست لینک‌های کوتاه‌شده🔗

این endpoint نیازمند authentication است. در ریکوئست ارسالی مقدار هدر Authorization باید برابر با توکن کاربر باشد (بدون Bearer یا موارد مشابه).

این endpoint باید لیست لینک‌های کوتاه‌شده‌ی کاربر به همراه تعداد بازدید هر کدام را در قالب یک لیست برگرداند.

• کد وضعیت: 200
• مثالی از پاسخ:

  [
    {
        "short_url": "http://localhost/SDas2",
        "url": "https://quera.org",
        "visits_count": 3
    },
    {
        "short_url": "http://localhost/zxcA54",
        "url": "https://google.com",
        "visits_count": 0
    }
  ]

  JSON

  Copy

لینک کوتاه‌شده🔗

آدرس این درخواست به‌صورت /{slug} است که {slug} همان رشته‌ای است که به لینک کوتاه‌شده توسط برنامه تخصیص می‌یابد. اگر {slug} ورودی یافت نشود، پاسخ باید به‌صورت زیر باشد:

• کد وضعیت: 404

در غیر این‌صورت، کاربر باید به لینک اصلی با کد پاسخ 301 هدایت شود.

نکات تکمیلی🔗

• نیازی به persistent بودن داده‌ها نیست!
• سیستم داوری docker-compose.yml زیر را خارج از فولدر api پاسخ شما قرار می‌دهد و با دستور docker-compose up --build آن را اجرا می‌کند.

docker-compose.yml

version: "3"

services:
  api:
    build: "./api"
    container_name: "api"
    ports:
      - "80:80"

• شما مجاز به تغییر یا ارسال docker-compose.yml دلخواه نیستید.
• سرویس شما باید روی پورت 80 آدرس localhost قابل دسترسی باشد.
• توصیه می‌کنیم در runner.sh خود APIتان را روی 0.0.0.0:80 اجرا کنید.

نحوه ارسال پاسخ🔗

شما می‌توانید تمامی محتوای موجود در پوشه‌ی api را تغییر دهید و هر فایلی که می‌خواهید اضافه یا کم کنید.

api
├──  api.py   # or main.go somefile.js anyfile.php name.any ...
├── Dockerfile
├── requirements.txt  # or go.mod package.json composer.json
└── runner.sh

توجه کنید که نام فایل کد شما برای سیستم داوری اهمیتی ندارد و این خود شما هستید که در runner.sh از نام آن برای اجرای پروژه استفاده می‌کنید.

در نهایت این پوشه را zip کرده و ارسال کنید. توجه کنید که پس از extract کردن فایل zip شما، باید پوشه‌ی api را ببینیم که درون آن Dockerfile وجود دارد.