المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۷:سوال ۴۷

سوال ۴۷

در شکل زیر٬ نقطه‌ها متناظر با ۱۱ کار هستند و بدین معنی است که قبل از اتمام کار $A$، کار $B$ نمی‌تواند شروع شود. دو کارگر داریم که هر یک می‌تواند هر کار را در یک ساعت انجام دهد. آیا با استفاده از این دو کارگر می‌توان با رعایت شرط فوق٬ تمام کارها را در مدت حداکثر ۶ ساعت انجام داد؟

پاسخ

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

$\quad\quad\quad\quad$ نفر اول $\quad\quad\quad\quad$ نفر دوم

$\quad\quad\quad\quad\quad$ ۸ $\quad\quad\quad\quad\quad\quad$ ۲ $\quad\quad\quad\quad$ :ساعت اول

$\quad\quad\quad\quad\quad$ ۹ $\quad\quad\quad\quad\quad\quad$ ۷ $\quad\quad\quad\quad$ :ساعت دوم

$\quad\quad\quad\quad\quad$ ۴ $\quad\quad\quad\quad\quad\quad$ ۱۰ $\quad\quad\quad\quad$ :ساعت سوم

$\quad\quad\quad\quad\quad$ ۳ $\quad\quad\quad\quad\quad\quad$ ۱۱ $\quad\quad\quad\quad$ :ساعت چهارم

$\quad\quad\quad\quad\quad$ ۱ $\quad\quad\quad\quad\quad\quad$ ۵ $\quad\quad\quad\quad$ :ساعت پنجم

$\quad\quad\quad\quad\quad$ $\quad\quad\quad\quad\quad\quad\quad$ ۶ $\quad\quad\quad\quad$ :ساعت ششم


ابزار صفحه