المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های ای سی ام سایت تهران:دوره ی ۶:g

ACM-Telecom

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

ورودی

در خط اول ورودی $t$ ($ 1 \leq t \leq 20$) به معنی تعداد تست‌کیس‌های ورودی است. هر تست‌کیس با عدد $N$ ($ 1 \leq N \leq 1000 $) شروع می‌شود که تعداد سطرهای جدول اولیه است. در $N$ سطر بعد، در هر سطر دو عدد به شکل $code cost$ آمده‌است که $code$ عددی بین $1$ تا $9999$ است و $cost$ ($ 1 \leq cost \leq 100$) به‌معنی هزینه تماس کد داده شده است. سطرهای یک تست‌کیس دارای $code$ های یکسان نیستند.

خروجی

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

محدودیت‌ها

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

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
1
12
331 4
33 4
335 4
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه