JMK no matter what

지난번에 연습한 것 오랫동안 포스팅 못하고 있다가, 오늘 연습하려고 들어갔는데 소스코드가 있길래 포스팅.. 미디엄 gray code 처럼 생각해서 잘못했다가 중간에 버리고 하드로 갔는데, 하드는 왜 틀린지도 모르겠고, 미디엄은 생각보다 쉬웠다. T_T 코딩하기 전에 제대로 검증해볼 생각을 안한 탓인 듯.

275 TheNewHouseDiv1

쉽게 볼 수 없는 점수라 긴장 탔는데, 사실 집이 정수좌표 아니면 .5 로 끝나는 좌표에 지어질 수밖에 없다는 것을 귀류법으로 증명할 수 있다.

lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;


struct TheNewHouseDivOne
{
    double distance( vector <int> x, vector <int> y, int k )
    {
        double ret = 1e20;
        double dist[50];
        FOR(i,-100,101) FOR(j,-100,101)
        {
            REP(l,x.sz)
                dist[l] = fabs(x[l] - j * .5) + fabs(y[l] - i * .5);
            sort(dist, dist+x.sz);
            ret = min(ret, dist[k-1]);
        }
        return ret;
    }
};

500 TheLockDivOne

패턴을 찾아내면 그냥 풀 수 있다.

lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef unsigned long long ll;

struct TheLockDivOne
{
    string password( int n, long long k )
    {
        return largest(n, k-1);
    }
    string kth(int n, long long k)
    {
        if(n == 1) return string(1, char('0' + int(k)));
        const ll low = 1ull << (n-1);
        if(k >= low)
        {
            k -= low;
            if(k == 0) return string("1") + kth(n-1, (1ull << (n-1))-1);
            return string("1") + kth(n-1, k-1);
        }
        return string("0") + kth(n-1, k);
    }
    string largest( int n, long long k )
    {
        if(n == 1) return string(1, char('0' + int(k)));
        ll low = 1ull << (n-1);
        if(k >= low)
        {
            k -= low;
            string cand = string("1") + kth(n-1, (1ull << (n-1))-1);
            if(k == 0) return cand;
            cand = max(cand, string("1") + largest(n-1, k-1));
            return cand;
        }
        return string("0") + largest(n-1, k);
    }
};