- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
دیروز $n$ دوست باهم به رستوران رفته‌اند، آن‌ها خیلی صمیمی هستند و غذاهایی که سفارش می‌دهند باهم به اشتراک می‌گذارند پس موقع حساب و کتاب هم خرج‌هایشان را یکسان بین خودشان تقسیم می‌کنند.
برای اینکه این حساب و کتابشان را راحت انجام دهند همیشه یکی از این افراد «مادرخرج» می‌شود؛ یعنی کل هزینه‌ها را به رستوران می‌دهد و فردای آن روز $n - 1$ نفر دیگر خرج آن روز را برای «مادرخرج» واریز می‌کنند.
اگر فرض کنید کل خرج رستوران $S$ تومان باشد. سهم هر کس دقیقاً $\frac{S}{n}$ تومان می‌شود. پس باید هرکس به جز «مادرخرج» مبلغ $\frac{S}{n}$ به حساب «مادرخرج» واریز کند تا حساب‌ها درست شود.
اما می‌دانیم انجام یک واریز و انتقال پول هزینه‌ای برای ارسال کننده دارد. در این سوال فرض کنید $a$ تومان از حساب واریزکننده بابت کارمزد این واریز کسر خواهد شد.
این موضوع باعث می‌شود که «مادرخرج» در مجموع هزینه کمتری را پرداخت کند! (چون $a$ تومان کمتر از بقیه پرداخت کرده است.)
از شما می‌خواهیم بگویید هر کس (به جز «مادرخرج») چقدر به حساب «مادرخرج» واریز کند تا پول خرج شده توسط همه این $n$ نفر یکسان باشد و یا بگویید انجام چنین کاری امکان پذیر نیست. (فرض کنید همه این $n$ نفر به اندازه کافی پول در حساب‌هایشان دارند.)
توجه کنید هرکس به جز «مادرخارج» دقیقاً یک انتقال پول با مبلغی صحیح و مثبت به حساب «مادرخرج» انجام می‌دهد و هیچ انتقال پول دیگری بین حساب این $n$ نفر مجاز نیست.
همچنین توجه کنید خرج رستوران که توسط «مادرخرج» پرداخت شده هیچ کارمزدی از حساب او کم نمی‌کند بلکه انتقال بین حساب است که کارمزد دارد.
برای بهتر متوجه شدن خواسته سوال توضیحات نمونه را مطالعه کنید.
ورودی
در سطر اول ورودی عدد $t$ داده می‌شود. این عدد نشان‌دهنده تعداد نمونه‌هایی است که باید پاسخ آن‌ها را چاپ کنید.
$$1 \le t \le 100$$
سپس در $t$ سطر بعدی در هر سطر سه عدد صحیح و مثبت $n$ و $S$ و $a$ داده می‌شود که به ترتیب نشان‌دهنده تعداد افراد، مجموع هزینه‌های رستوران و هزینه انجام یک تراکنش برای ارسال کننده است. $$2 \le n \le 100 \quad \quad 1 \le a \le 1000 \quad \quad 1 \le S \le 100 \ 000$$
توجه کنید این $t$ نمونه هیچ ارتباطی به هم ندارند و هر کدام مسئله‌ای مستقل هستند.
خروجی
خروجی شامل $t$ سطر است و در هر سطر پاسخ یک نمونه چاپ می‌شود. درصورتی که عدد صحیح و مثبتی مثل $x$ وجود دارد که اگر هرکس به جز «مادرخرج»، $x$ تومان برای مادرخرج واریز کند، مقدار پول کسر شده از حساب همه یکسان خواهد بود، مقدار $x$ و اگر چنین عدد صحیحی وجود ندارد -1 را چاپ کنید.
مثال
ورودی نمونه
5
3 2000 5
2 201 1
5 30 1
2 100 100
3 3 100
خروجی نمونه
665
100
-1
-1
-1
توضیح نمونه اول
ابتدا از حساب «مادرخرج» ۲۰۰۰ تومان کسر شده‌است، سپس توسط دو نفر دیگر هر کدام ۶۶۵ تومان به حساب مادرخرج واریز شده است. پس در مجموع کل مبلغ پرداخت شده توسط «مادرخرج» برابر است با: $$2000 - 2 \times 665 = 670$$
بقیه افراد هر کدام نفری ۶۶۵ تومان به حساب «مادرخرج» واریز می‌کنند و ۵ تومان هم کارمزد این واریز را پرداخت می‌کنند پس مجموع پرداختی این افراد برابر است با: $$665 + 5 = 670$$ و این عادلانه است چون در مجموع از حساب همه افراد، ۶۷۰ تومان کسر شده‌است.
توضیح نمونه دوم
ابتدا از حساب «مادرخرج» ۲۰۱ تومان کسر شده‌است، سپس توسط فرد دیگر ۱۰۰ تومان به حساب «مادرخرج» واریز شده‌است. پس در مجموع کل مبلغ پرداخت شده توسط «مادرخرج» برابر است با: $$201 - 100 = 101$$
فرد دیگر ۱۰۰ تومان به حساب «مادرخرج» واریز می‌کند و ۱ تومان هم کارمزد این واریز را پرداخت می‌کند پس مجموع پرداختی این فرد برابر است با: $$100 + 1 = 101$$ و این عادلانه است چون در مجموع از حساب همه افراد، ۱۰۱ تومان کسر شده‌است.
توضیح نمونه سوم
هیچ مبلغ صحیح و مثبتی نمی‌توان برای انجام تراکنش انتخاب کرد.
ابتدا از حساب «مادرخرج» ۳۰ تومان کسر شده است. اگر هر فرد به جز مادر خرج مبلغ ۶ تومان به حساب «مادرخرج» واریز کند. مجموع کل مبلغ پرداخت شده توسط مادر خرج برابر است با: $$30 - 4 \times 6 = 6$$ بقیه افراد هر کدام نفری ۶ تومان به حساب «مادرخرج» واریز می‌کنند و ۱ تومان هم کارمزد این واریز را پرداخت می‌کنند پس مجموع پرداختی این افراد برابر است با: $$6 + 1 = 7$$ و این عادلانه نیست چون در مجموع از حساب مادر خرج ۶ تومان کسر شده ولی از حساب بقیه ۷ تومان کسر می‌شود.
با استدلال‌های مشابه می‌توانید نتیجه بگیرید که هیچ عدد صحیح و مثبتی برای تسویه حساب به صورت عادلانه وجود ندارد. پس به جای پاسخ مسئله -1 چاپ می‌کنیم.
توضیح نمونه چهارم
اگر فرد به غیر از «مادرخرج» هر مبلغ صحیح و مثبتی به حساب «مادرخرج» واریز کند مجموع پول کسر شده از حساب مادرخرج کمتر از ۱۰۰ تومان و فرد دیگر بیشتر از ۱۰۰ تومان خواهد بود. پس هیچ روشی برای تسویه حساب عادلانه وجود ندارد. پس به جای پاسخ مسئله -1 چاپ می‌کنیم.
توضیح نمونه پنجم
در این نمونه هزینه کارمزد انتقال زیاد است و چون انتقال با مبلغ منفی نداریم (!) هیچ روشی برای تسویه حساب عادلانه نداریم. پس به جای پاسخ مسئله برابر -1 چاپ می‌کنیم.
ارسال پاسخ برای این سؤال