sgc109

/*
https://community.topcoder.com/stat?c=problem_statement&pm=11434

풀이1과 거의 동일한데 재귀함수의 구현 형태가 조금 다르다 풀이1 이 더 빠를것 같지만 이렇게도 생각해 볼 수 있을 것 같아서 써본다.
처음에 길이 N인 덩어리가 있는데 이걸 길이가 1인 덩어리 까지 나누어 가는 과정을 생각해보자. 각각의 소인수들의 지수들을 모두 더한 값을 S라고해보자
이 S가 최대한 나눌 수 있는 횟수일 것이고, 그렇다면 답은 아무리 커도 저 값보다 작거나 같을 것이다. 왜냐하면 길이가 1인 덩어리로 나눠 버리면
우리가 가져가고자 하는 칸은 무조건 가져갈 수가 있기 때문이다. 그렇다면 나누는 순서에 대한 모든 경우의 수를 보면서 매 순간 순간 마다 중간에 
맨 왼쪽 칸과의 최소거리 + 지금까지 나눈 횟수의 최소값을 구하면 이게 답이될 것이다.

*/

sgc109

/*
https://community.topcoder.com/stat?c=problem_statement&pm=11379

이 문제는 N개의 상한이 주어지고 그 상한보다 작거나 같은 수들을 N개 선택하여 그 N개의 합과 OR 이 같은 경우의 수를 구하는 문제이다.
조금만 생각해보면 상한보다 작거나 같은 N개의 수를 2진수로 표현했을 때 각각의 비트가 겹치지 않는 수들의 조합을 구하라는 말과 동치임을 알 수 있다.
그렇다면 우선 상한읜 최대 10^18 이니까 64개의 비트면 충분히 표현 가능할 것이다. 그렇다면 63번째 비트부터 차례로 내려가면서 각각의 상한을 넘지
않도록 어떤 수에게 1을 줄 것인지를 결정하면 된다.(물론 아무 수에게도 1을 안줘도됨) 어떤 수에게 1을 줄 것인지 결정하는 부분은 그냥 
재귀 함수 내에서 반복문으로 구현하면 되는데 문제는 각각의 수마다 상한을 넘는지 넘지 않는지를 체크 해줘야 하는데 어떤 수에게 1을 주면 수가 변하기
때문에 그에 대한 정보가 인자로 필요하다. 그런데 모든 수를 인자로 주기엔 O(64*10^19) 개의 공간이 필요하므로 힘들다.
좀만 생각해보면 상한을 2진수로 표현했을 때 특정 자리가 1인데 그 자리에 이 수에게 1을 주지 않으면 그 아래 자리에 아무리 1을 줘도 절대 상한을 

sgc109

/*
https://community.topcoder.com/stat?c=problem_statement&pm=11443

주어진 문자열을 팰린드롬으로 만드는 dp 문제이다.
부분문제를 정의하자면
dp(i,j) : S[i:j] 를 팰린드롬으로 만들기위한 최소 비용

점화식을 생각해보면 양 끝에서 부터 한글자 혹은 두글자씩 매치시키면서 양쪽 끝을 한칸 씩 좁혀나가는 식으로 구성할 수가 있다.
어떻게 이게 가능하냐면 왼쪽끝 글자를 l, 오른쪽끝 글자를 r 이라고 했을때 l은 r과 매치시킬 수도있고 오른쪽에 새 글자를 만들어서 그것과 
매치시킬 수도있고 r을 삭제하고 r의 왼쪽 글자에대해 재귀적으로 선택할수가있다. 그렇기 때문에

sgc109

/*
https://community.topcoder.com/stat?c=problem_statement&pm=11461

dp 문제이다. 꽤나 익숙한 유형중 하나이다. 어떠한 수가 있으면 맨윗자리부터 내려오면서 조건을 만족하는 가능한 숫자들의 경우의 수를 구하는문제로
보통 문제에서 주어진 상한이나 하한을 보면서 특정 자리수가 상한보다 낮아지거나 하한보다 높아지는순간 그 뒷자리는 크기에대해 전혀 신경을 쓰지 않아도 되므로
그에 대한 메모를 bool 형태로 memoization 해주면된다. 이 문제에서는 하한과 상한 두개 모두 있으므로 두개를 함께 따져주며 계산을 하면되고
4나 7을 제외한 수가 최대 한번만 나올 수있다는 조건도 있으므로 지금까지 4나 7을 제외한 수가 나왔는지 안나왔는지도 함께 memoization 해주면된다
단 아직 앞에 leading zero만 나왔을땐 4나7이 아닌수가 나왔다고 세면 안되기 때문에 이것도 memoization 해준다. 즉 bool형태의 memoization 을 4개해주고
현재 몇자리까지 봐줬는지를 하나봐주면되는데 10^16까지니까 최대 17정도될것이다.
그리고 지금까지는 이진수에 대해서 이렇게 윗자리부터 따져주며 세는것을 많이 봤었는데 십진수에 대해서는 처음본것같다.

sgc109

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)

sgc109

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)

sgc109

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define fastio() ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int inf = 0x3c3c3c3c;
const ll infl = 0x3c3c3c3c3c3c3c3c;

sgc109

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define fastio() ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int inf = 0x3c3c3c3c;
const ll infl = 0x3c3c3c3c3c3c3c3c;

sgc109

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define fastio() ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int inf = 0x3c3c3c3c;
const ll infl = 0x3c3c3c3c3c3c3c3c;

sgc109

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define fastio() ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int inf = 0x3c3c3c3c;
const ll infl = 0x3c3c3c3c3c3c3c3c;