Submission #243936

#	Time	Username	Problem	Language	Result	Execution time	Memory
243936		pavel	Cutting a rectangle (LMIO18_staciakampis)	C++14	0 / 100	4 ms	384 KiB

staciakampis

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 100005;
const int INF = 1000000009;

int n;
ll a[MAXN], b[MAXN];
ll area = 0;

bool possible(int k, ll lw, ll lh){
    if(lw == 0 || lh == 0){
        return k == -1;
    }
    return a[k] == lw && b[k] <= lh && possible(k-1, lw, lh - b[k])
        || a[k] == lh && b[k] <= lw && possible(k-1, lw - b[k], lh);
        //|| b[k] == lw && a[k] <= lh && possible(k-1, lw, lh - a[k])
        //|| b[k] == lh && a[k] <= lw && possible(k-1, lw - a[k], lh);
}

int main(){
    scanf("%d", &n);
    for(int i=0;i<n;++i){
        scanf("%lld%lld", &a[i], &b[i]);
        area += a[i] * b[i];
    }
    vector<int> sol;
    if(area % a[n-1] == 0 && possible(n-1, a[n-1], area / a[n-1])){
        sol.push_back(min(a[n-1], area/a[n-1]));
    }
    if(area % b[n-1] == 0 && possible(n-1, b[n-1], area / b[n-1])){
        sol.push_back(min(b[n-1], area/b[n-1]));
    }
    sort(sol.begin(), sol.end());
    sol.erase(unique(sol.begin(), sol.end()), sol.end());
    printf("%d\n", sol.size());
    for(int i:sol){
        printf("%d\n", i);
    }
}

Compilation message (stderr)

staciakampis.cpp: In function 'bool possible(int, ll, ll)':
staciakampis.cpp:20:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     return a[k] == lw && b[k] <= lh && possible(k-1, lw, lh - b[k])
            ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
staciakampis.cpp: In function 'int main()':
staciakampis.cpp:41:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", sol.size());
                    ~~~~~~~~~~^
staciakampis.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
staciakampis.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld", &a[i], &b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 55