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

برای شرکت بهتر در مسابقه پیشنهاد می‌کنیم لینک‌های زیر را مطالعه کنی!

می‌تونی سوالاتت رو هم از قسمت "سوال بپرسید" مطرح کنی. همچنین برای دسترسی به آخرین اخبار و اطلاعیه‌ها (روال مصاحبه و دوره‌های بعدی) بعد از آزمون کانال رو چک کن:

فرار مالیاتی!


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

مالیات اصلی‌ترین راه تامین درآمد بسیاری از کشور‌ها از جمله کشور‌های پیشرفته است و هزینه‌ی بسیاری از پروژه‌های زیرساختی، عمرانی و حتی حقوق کارمندان دولت، معلمان و ... از طریق دریافت مالیات از کسبه، شرکت‌ها و ... تامین می‌شود. فرار مالیاتی به زبان ساده یعنی مالیات‌دهنده تلاش کند کمتر از میزان واقعی مالیات پرداخت کند. مثلاً فرض کنید یک کاسب در طول سال، ۱۰۰ میلیون تومان سود (مجموع درآمد منهای هزینه‌ها) داشته و با نرخ ۱۵ درصد باید ۱۵ میلیون تومان مالیات بپردازد. حالا اگر این کاسب تلاش کند با روش‌های مختلف میزان سود اصلی خود را کمتر نشان دهد، مالیات کمتری نیز می‌پردازد. به این عمل فرار مالیاتی می‌گوییم.

در حال حاضر فرار مالیاتی یک چالش بزرگ در کشور‌های دنیاست، گزارش‌های مختلف نشان می‌دهد در ایران خودمان سالانه بین ۴۰ تا ۱۵۰ هزار میلیارد تومان فرار مالیاتی داریم. یکی از موثرترین راه‌های جلوگیری از فرار مالیاتی در برخی از کشور‌های پیشرفته تحلیل داده‌های مالی به صورت گراف است. به این صورت که تمام داده‌های مالی شامل تراکنش‌ها، خرید و فروش‌ها و مالکیت‌ها را به صورت راس‌های گراف اصلی (گرافی بسیار بزرگ) مدل می‌کنیم و انواع شکل‌هایی که احتمال دارد فرار مالیاتی باشد را به صورت گراف الگو (گرافی بسیار کوچک) مدل می‌کنیم. سپس در گراف اصلی زیرگراف‌هایی که شبیه گراف الگوی فرار مالیاتی باشد را پیدا می‌کنیم.

مثال‌های از تخلفات که به راحتی قابل تبدیل به گراف‌های الگو هستند:

  • کاسبی که در سال گذشته یک آپارتمان با قیمت بالای سه میلیارد تومان و یک خودروی ۵۰۰ میلیون تومانی خریده است اما در اظهارنامه مالیاتی سودش را کمتر از ۵۰ میلیون اعلام کرده است.
  • شرکتی که در اظهارنامه مالیاتی ضررده اعلام شده اما پاداش آخر سال مدیران آن صد‌ها میلیون تومان بوده است.

در ادامه حالت ساده شده‌ی این مسئله آورده شده، که حل آن می‌تواند مقدمه‌ای بر حل مسئله‌ی فرار مالیاتی باشد، پس تلاش خود را به کار ببرید، این گوی و این میدان!


در این مسئله یک گراف اصلی و یک گراف الگو به شما داده می‌شود. حال شما می‌بایست تعداد زیر گراف‌های موجود در گراف اصلی را پیدا کنید به طوری که این زیرگراف‌ها مشابه گراف الگو باشند. (برای فهم بهتر مسئله به شکل‌های پایین صفحه مراجعه کنید)

توجه: برنامه‌ی شما حتما باید به زبان JavaJava باشد و شما مجاز به ایجاد هر گونه کلاس، تابع، اینترفیس و ... هستید.

نکات مهم:🔗

  1. گراف‌ها رنگی و جهت‌دار هستند.
  2. گراف الگو ضعیفا همبند است. (در صورتی که جهت یال‌ها را در نظر نگیریم، گراف ما همبند است)
  3. بین هر دو راس گراف الگو حداکثر یک یال در هر جهت وجود دارد.
  4. هر راس گراف شامل یک ‌‌‌شناسه یکتا و یک رنگ است.
  5. هر یال گراف شامل یک شناسه راس مبدا و یک شناسه راس مقصد است.

ورودی🔗

اطلاعات گراف اصلی🔗

  1. در خط اول ورودی ‌‌n1n_1 (تعداد راس‌های گراف اصلی) وارد می‌شود.
  2. سپس در n1n_1 خط بعدی یک رشته (شناسه راس) و aia_i (شماره رنگ راس‌) برای راس‌های گراف اصلی با یک فاصله از هم وارد می‌شوند.
  3. سپس مقدار ‌‌m1m_1 (تعداد یال‌های گراف اصلی) وارد می‌شود.
  4. سپس در m1m_1 خط بعدی دو رشته برای شناسه‌ی راس مبدا و شناسه‌ی راس مقصد یال‌های گراف اصلی با یک فاصله از هم وارد می‌شوند.

اطلاعات گراف الگو🔗

  1. در خط بعد ‌‌n2n_2 (تعداد راس‌های گراف الگو) وارد می‌شود.
  2. سپس در n2n_2 خط بعدی یک رشته (شناسه راس) و bib_i (شماره رنگ راس‌) برای راس‌های گراف الگو با یک فاصله از هم وارد می‌شوند.
  3. سپس مقدار ‌‌m2m_2 (تعداد یال‌های گراف الگو) وارد می‌شود.
  4. سپس در m2m_2 خط بعدی دو رشته‌ی شناسه‌ی راس مبدا و شناسه‌ی راس مقصد یال‌های گراف الگو با یک فاصله از هم وارد می‌شوند. 1n130 0001 \le n_1 \le 30\ 000 1ai41 \le a_i \le 4 1m110n11 \le m_1 \le 10*n_1 1n251 \le n_2 \le 5 1bi41 \le b_i \le 4 1m2201 \le m_2 \le 20

خروجی🔗

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

مثال🔗

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

5
1 1
2 2
3 2
4 2
5 2
8
1 2
1 5
2 3
2 4
2 5
3 4
5 3
5 4
3
A 1
B 2
C 2
2
A B
B C
Plain text

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

5
Plain text
توضیحات نمونه‌ی ۱

گراف اصلی نمونه ۱: گراف اصلی نمونه ۱

گراف الگو نمونه ۱: گراف الگو نمونه ۱

با توجه به جدول زیر تعداد زیرگراف‌های مشابه گراف الگو در گراف اصلی، ۵ تاست، بنابراین عدد ۵ در خروجی چاپ می‌شود.

راس A راس B راس C
زیرگراف ۱ راس ۱ راس ۲ راس ۳
زیرگراف ۲ راس ۱ راس ۲ راس ۴
زیرگراف ۳ راس ۱ راس ۲ راس ۵
زیرگراف ۴ راس ۱ راس ۵ راس ۳
زیرگراف ۵ راس ۱ راس ۵ راس ۴

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

5
1 1
2 2
3 2
4 2
5 2
4
1 2
1 3
1 4
1 5
3
A 1
B 2
C 2
2
A B
A C
Plain text

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

12
Plain text
توضیحات نمونه‌ی ۲

گراف اصلی نمونه ۲: گراف اصلی نمونه ۲

گراف الگو نمونه ۲: زیرگراف نمونه ۲

با توجه به جدول زیر تعداد زیرگراف‌های مشابه گراف الگو در گراف اصلی، ۱۲ تاست، بنابراین عدد ۱۲ در خروجی چاپ می‌شود.

راس A راس B راس C
زیرگراف ۱ راس ۱ راس ۲ راس ۳
زیرگراف ۲ راس ۱ راس ۲ راس ۴
زیرگراف ۳ راس ۱ راس ۲ راس ۵
زیرگراف ۴ راس ۱ راس ۳ راس ۲
زیرگراف ۵ راس ۱ راس ۳ راس ۴
زیرگراف ۶ راس ۱ راس ۳ راس ۵
زیرگراف ۷ راس ۱ راس ۴ راس ۲
زیرگراف ۸ راس ۱ راس ۴ راس ۳
زیرگراف ۹ راس ۱ راس ۴ راس ۵
زیرگراف ۱۰ راس ۱ راس ۵ راس ۲
زیرگراف ۱۱ راس ۱ راس ۵ راس ۳
زیرگراف ۱۲ راس ۱ راس ۵ راس ۴

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

2
1 1
2 1
2
1 2
2 1
2
A 1
B 1
1
A B
Plain text

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

2
Plain text
توضیحات نمونه‌ی ۳

گراف اصلی نمونه ۳: گراف اصلی نمونه ۳

گراف الگو نمونه ۳: زیرگراف نمونه ۳

با توجه به جدول زیر تعداد زیرگراف‌های مشابه گراف الگو در گراف اصلی، ۲ تاست، بنابراین عدد ۲ در خروجی چاپ می‌شود.

راس A راس B
زیرگراف ۱ راس ۱ راس ۲
زیرگراف ۲ راس ۲ راس ۱
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.