Header Ad

HackerEarth Painting The logo problem solution

In this HackerEarth Painting, The logo problem solution Rahul has set upon the quest for a new logo of his company. He has created the following continuous logo:

    /\
   /  \
  / /\ \
 / /  \ \
/ / /\ \ \
  \ \ \/ / /
   \ \  / /
    \ \/ /
     \  /
      \/
However, his sister, Rashi, likes the following discontinuous design more

   /\
  /  \
 / /\ \
/ /  \ \
  \ \  / /
   \ \/ /
    \  /
     \/
The size of a logo is the longest continuous streak of same characters on an arm.

So, size of 1st logo is 5 while that of 2nd one is 4.

We know that every '/' or '\' character requires exactly 1 unit of paint.

Now, Rahul has X units of paint and would like to draw each of the two favorite logos of himself and his sister, Rashi. So, as to consume it optimally, he wants to know the maximal possible sizes of the two logos that can be drawn such that the difference in sizes of both logos is atmost 1.

Note that it is necessary to be able to draw both the logos. In case, the paint is not enough, output 0 0 instead.


HackerEarth Painting The logo problem solution


HackerEarth Painting The logo problem solution.

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define FF first
#define SS second
#define s(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define sf(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define sc(n) {char temp[4]; ss(temp); n=temp[0];}
#define INF (int)1e9
#define LINF (long long)1e18
#define EPS 1e-9
#define maX(a,b) ((a)>(b)?(a):(b))
#define miN(a,b) ((a)<(b)?(a):(b))
#define abS(x) ((x)<0?-(x):(x))

typedef long long ll;
typedef unsigned long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,PII> TRI;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<ll> vl;
typedef vector<PII> VII;
typedef vector<TRI> VT;

ll n;
int TEST_NO;

void precompute() {
}
void read() {
sl(n);
}
void preprocess() {
}

void solve() {
if(n < 12) {
puts("0 0");
return;
}

int lo = 0, hi = sqrt(n);
int ans = -1, add = -1;
while(lo <= hi) {
ll mid = lo + (hi - lo >> 1);
ll x = 2 * mid + 1;
ll maxx = (x + 1) * (2 * x + 4);
ll minx = (x + 1) * (2 * x);
if(n >= minx) {
ans = x;
if(n >= maxx) add = 1;
else add = -1;
lo = mid + 1;
} else
hi = mid - 1;
}
if(ans != -1) printf("%d %d\n", ans, ans + add);
else puts("0 0");
}
int main() {
int NO_OF_TESTS;
s(NO_OF_TESTS);
precompute();
for (TEST_NO = 1; TEST_NO <= NO_OF_TESTS; ++TEST_NO) {
read();
preprocess();
solve();
}
return 0;
}

Second solution

#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define SET(a,b) memset(a,b,sizeof(a))
#define LET(x,a) __typeof(a) x(a)
#define TR(v,it) for( LET(it,v.begin()) ; it != v.end() ; it++)
#define repi(i,n) for(int i=0; i<(int)n;i++)
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define sortv(a) sort(a.begin(),a.end())
#define all(a) a.begin(),a.end()
#define DRT() int t; cin>>t; while(t--)
#define TRACE
using namespace std;

#ifdef TRACE
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif


typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector< PII > VPII;


LL f(LL x)
{
if(x%2==0)
{
LL k = x/2;
return 4*(k*(k+1));
}
x = (x+1)/2;
return 4*x*x;
}

int main()
{
DRT()
{
LL x; cin>>x;
if(x<12)
{
cout<<0<<" "<<0<<endl;
continue;
}
LL l = 0; LL h = 100000000;
while(h-l>1)
{
LL m = (l+h)/2;
if(f(m) + f(m+1)<=x)
l = m;
else h = m-1;
}
while(f(h) + f(h+1)>x)h--;
if(h%2) cout<<h<<" "<<h+1<<endl;
else cout<<h+1<<" "<<h<<endl;
}
return 0;
}



Post a Comment

0 Comments