محدودیت زمان: ۳ ثانیه محدودیت حافظه: ۵۱۲ مگابایت آی مجری که به فکر بچهها است، تصمیم…
- User
محدودیت زمان: ۳ ثانیه محدودیت حافظه: ۵۱۲ مگابایت آی مجری که به فکر بچهها است، تصمیم گرفته برای اولین بار آنها را به سینما ببرد. آی مجری میداند که اگر یکی از بچهها هنگام دیدن فیلم ناراحت باشد، فیلم را به کام همه تلخ خواهدکرد. به همین دلیل میخواهد همه راحت باشند. و اگر چنین چیزی امکان نداشت اصلا به سینما نروند. یکی از بچهها ناراحت است اگر فردی جلوی او(نزدیک تر به پردهی سینما و همستون با او) نشسته باشد و قدش از او بلندتر باشد. همچنین به دلیل این که آنها خیلی خوشقلب هستند اگر بینندهی دیگری غیر از آنها هم نتواند فیلم را به خوبی ببیند(فرد بلندتری جلویش نشسته باشد)، ناراحت میشوند.
همهی انسانها در سه دستهی قدی دستهبندی میشوند:
۱) انسانهای کوتاه(تا ۱۹۰ سانتیمتر)
۲) انسانهای معمولی(۱۹۱-۱۹۸سانتیمتر)
۳) انسانهای بلند(۱۹۹ به بالا)
در واقع افرادی نمیتوانند درست ببینند که یک نفر از دستهی بلندتر جلوی آنها نشسته باشد.
صندلیهای سینما r r ردیف و c c ستون دارند که در ردیف آخر نزدیک ترین آدمها به پردهی سینما نشستهاند.
قبل از رسیدن بچهها تعدادی بیننده به سالن سینما رفته اند و در جاهای دلخواه خود نشستهاند و نمیتوان جای آنها را تغییر داد. شما باید یک ترتیب دلخواه از نشستن همهی بچهها در سینما خروجی دهید که همگی راحت باشند و یا این که بگویید بهتر است اصلا به سینما نروند و به جای آن به پارک بروند.
ورودی در سطر اول ورودی دو عدد طبیعی r r و c c آمدهاست، که به ترتیب نمایانگر تعداد ردیفها و ستونهای سینماست.
سپس در r r سطر بعدی در هر کدام c c کاراکتر آمدهاست که به این نحو معنی میشوند:
۱) جای خالی: #
۲) انسان کوتاه: s
۳)انسان معمولی: n
۴)انسان بلند: t
در سطر بعدی سه عدد طبیعی و کوچکتر از یک میلیون میآید که به ترتیب نشاندهندهی تعداد بچههای کوتاه، معمولی و بلند است که آی مجری میخواهد با خود به سینما بیاورد. 1 ≤ r , c ≤ 1000 1≤r,c≤1000
خروجی اگر حالتی وجود نداشت، "Let's go to the park" را چاپ کنید. در غیر این صورت باید یک جدول مانند ورودی چاپ کنید که همهی بچهها نیز در جاهای خالی آن نشستهاند. اگر چند حالت وجود داشت، به دلخواه یکی را چاپ کنید.
مثال ورودی نمونه ۱ 3 3
#s# n## 2 1 1 Plain text خروجی نمونه ۱ t## ns# nss Plain text قبل از رسیدن آی مجری و بچهها دو نفر با قدهای کوتاه و متوسط روی صندلیها نشستهاند. فرد با قد متوسط در نزدیک ترین فاصله به پرده نشستهاست.
آی مجری ۴ نفر را با خود برده است. دو نفر با قد کوتاه، یک نفر با قد متوسط و یک نفر با قد بلند. یک حالت دلخواه از نشستن بچهها را در خروجی میبینید.
ورودی نمونه ۲ 4 4
##tn nt#s ##t# 4 3 2 Plain text خروجی نمونه ۲ Let's go to the park write code in c++
- Assistant
#include <iostream> #include <vector> #include <string> using namespace std; typedef pair<int, int> pii; int main() { int r, c; cin >> r >> c; vector<string> grid(r); for (int i = 0; i < r; ++i) { cin >> grid[i]; } int ns, nn, nt; cin >> ns >> nn >> nt; // Create seating grid with proper indexing // We need to reverse rows to match the seating from back to front vector<vector<char>> seating(r, vector<char>(c)); for (int i = 0; i < r; ++i) { seating[r - i - 1] = vector<char>(grid[i].begin(), grid[i].end()); } vector<pii> seats_min1; // seats with min_category == 1 vector<pii> seats_min2; // seats with min_category == 2 vector<pii> seats_min3; // seats with min_category == 3 int nt_initial = nt; int nn_initial = nn; int ns_initial = ns; int s1 = 0, s2 = 0, s3 = 0; int R = r; int C = c; // For each column for (int j = 0; j < C; ++j) { int tallest_category_so_far = 0; // Process from front (row 0) to back (row r-1) for (int i = 0; i < R; ++i) { char seat = seating[i][j]; if (seat == '#') { // Empty seat int min_category = tallest_category_so_far; pii pos = make_pair(i, j); if (min_category == 3) { seats_min3.push_back(pos); s3++; } else if (min_category == 2) { seats_min2.push_back(pos); s2++; } else { seats_min1.push_back(pos); s1++; } } else { int height_category = 0; if (seat == 's') height_category = 1; else if (seat == 'n') height_category = 2; else if (seat == 't') height_category = 3; else { // Invalid character cout << "Let's go to the park" << endl; return 0; } if (height_category < tallest_category_so_far) { // Person cannot see, impossible cout << "Let's go to the park" << endl; return 0; } tallest_category_so_far = max(tallest_category_so_far, height_category); } } } // Step 1: Assign kids of category 3 to seats with min_category == 3 if (nt >= s3) { nt -= s3; } else { cout << "Let's go to the park" << endl; return 0; } // Step 2: Assign kids of category 2 and remaining category 3 to seats with min_category == 2 int nn_used = min(nn, s2); int s2_remaining = s2 - nn_used; nn -= nn_used; if (nt >= s2_remaining) { nt -= s2_remaining; } else { cout << "Let's go to the park" << endl; return 0; } // Step 3: Assign remaining kids to seats with min_category == 1 int total_remaining_kids = ns + nn + nt; if (s1 >= total_remaining_kids) { // Proceed } else { cout << "Let's go to the park" << endl; return 0; } // Now assign the kids to the seats // Create seating plan // For seats_min3, assign 't' for (auto pos : seats_min3) { seating[pos.first][pos.second] = 't'; } // For seats_min2, assign 'n' and 't' int idx = 0; // Assign 'n's for (; idx < seats_min2.size() && nn_initial > 0; ++idx, --nn_initial) { seating[seats_min2[idx].first][seats_min2[idx].second] = 'n'; } // Assign 't's for (; idx < seats_min2.size(); ++idx) { seating[seats_min2[idx].first][seats_min2[idx].second] = 't'; } // For seats_min1, assign 's', 'n', 't' idx = 0; // Assign 's's for (; idx < seats_min1.size() && ns > 0; ++idx, --ns) { seating[seats_min1[idx].first][seats_min1[idx].second] = 's'; } // Assign 'n's for (; idx < seats_min1.size() && nn > 0; ++idx, --nn) { seating[seats_min1[idx].first][seats_min1[idx].second] = 'n'; } // Assign 't's for (; idx < seats_min1.size() && nt > 0; ++idx, --nt) { seating[seats_min1[idx].first][seats_min1[idx].second] = 't'; } // The rest of empty seats remain empty // Output the seating grid // Remember to invert the seating grid to match the input format for (int i = R - 1; i >= 0; --i) { for (int j = 0; j < C; ++j) { cout << seating[i][j]; } cout << endl; } return 0; }