COVID_19 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Devendra Singh
Testers: Lavish Gupta, Tejas Pandey
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

There is a theatre with N rows and M seats in each row. We need to find the maximum number of seats that can be occupied with the following conditions:

  • No adjacent seats in the same row can be occupied

  • No two adjacent rows can be occupied

EXPLANATION:

  • Clearly, the optimal way to allocate the seats would be to select the rows as row 1, row 3, \dots and in each row we select the seats as seat 1, seat 3, \dots

  • Then, total number of rows selected will be \lfloor \frac{N+1}{2} \rfloor and the number of seats in each row would be \lfloor \frac{M+1}{2} \rfloor.

  • Therefore, the total number of seats selected will be \lfloor \frac{N+1}{2} \rfloor \cdot \lfloor \frac{M+1}{2} \rfloor.

TIME COMPLEXITY:

O(1) for each test case.

SOLUTION:

Editorialist's solution 
#include <bits/stdc++.h>
using namespace std;

int main()
{
      int tests;
      cin >> tests;
      while (tests--)
      {
            int n, m;
            cin >> n >> m;

            int ans = ((n + 1) / 2) * ((m + 1) / 2);
            cout << ans << endl;
      }
      return 0;
}
Tester's solution 
// validating input
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 100;
const int MAX_N = 100;
const int MAX_Q = 100000;
const int MAX_val = 1000000000;
const int MAX_SUM_N = 100000;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll p = 1000000007;
ll sum_nk = 0 ;


void solve()
{   
    int m = readIntSp(1 , MAX_N) ;
    int n = readIntLn(1 , MAX_N) ;

    int ans = (m+1)/2 ;
    ans *= ((n+1)/2) ;

    int flag = (n%2 == 1) + (2*(m%2 == 1)) ;
    cerr << "flag = " << flag << endl ;
    cout << ans << endl ;
    return ;
}
 
signed main()
{
    //fast;
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif
    
    int t = 1;
    
    t = readIntLn(1,MAX_T);

    for(int i=1;i<=t;i++)
    {    
        solve() ;
    }
    
    assert(getchar() == -1);
    // assert(sum_n <= MAX_SUM_N);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    // cerr<<"Sum of lengths : " << sum_n << '\n';
    // cerr<<"Maximum length : " << max_n << '\n';
    // cerr << "Sum of product : " << sum_nk << '\n' ;
    // cerr<<"Total operations : " << total_ops << '\n';
    // cerr<<"Answered yes : " << yess << '\n';
    // cerr<<"Answered no : " << nos << '\n';
}

Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile: