akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll h,w,k,dp[30][30],L,rans,MAX,dp2[30][30];
string S;
vector<ll> v;
ll f(ll cnt){
    ll ans=0;
    for(int i=0;i<h;i++){
        ll cnt1=0;
        ll cnt2=1;
        for(int j=1;j<w;j++){
            if(dp[i][j-1]==dp[i][j])cnt2++;
            else{
                if(cnt2>=k){
                    ans+=pow(2,cnt)*cnt2*dp[i][cnt1];
                    for(int ii=0;ii<cnt2;ii++)dp[i][cnt1+ii]=0;
                    cnt1=j;
                    cnt2=1;
                }
                else{
                    cnt1=j;
                    cnt2=1;
                }
            }
        }
        
        if(cnt2>=k){
            ans+=pow(2,cnt)*cnt2*dp[i][cnt1];
            for(int ii=0;ii<cnt2;ii++)dp[i][cnt1+ii]=0;
        }
    }
    return ans;
}
void f2(void){
    for(int i=0;i<w;i++){
        ll tmp=0;
        v={};
        for(int j=h-1;j>=0;j--){
            if(dp[j][i]!=0)v.push_back(dp[j][i]);
            else tmp++;
        }
        while(tmp--)v.push_back(0);
        for(int j=h-1;j>=0;j--){
            dp[j][i]=v[h-1-j];
        }
    }
    return ;
}
void ini(void){
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            dp[i][j]=dp2[i][j];
        }
    }
}
int main(void){
    cin>>h>>w>>k;
    for(int i=0;i<h;i++){
        cin>>S;
        for(int j=0;j<w;j++){
            dp2[i][j]=S[j]-'0';
            dp[i][j]=S[j]-'0';
        }
    }
    for(int i=1;i<h;i++){
        for(int j=0;j<w;j++){
            
            ini();
            ll cnt=0;
            rans=0;
            dp[i][j]=0;
            //cout<<i<<" "<<j<<endl;
            
            while(1){
                
    
    
    
                f2();
                
                
                
                /*for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cout<<dp[i][j];
        }
        cout<<endl;
    }
    cout<<endl;*/
                
                
                
                
                L=f(cnt);
                //cout<<L<<endl;
                if(L==0)break;
                rans+=L;
                cnt++;
                
            }
            MAX=max(rans,MAX);
            //cout<<MAX<<endl;
        }
    }
    cout<<MAX<<endl;
}


Measured memory_bytes: 256
import java.math.BigInteger;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String x = sc.nextLine();
        int input = Integer.parseInt(x);

        
        BigInteger ten = new BigInteger("10");
        BigInteger nine = new BigInteger("9");
        BigInteger eight = new BigInteger("8");
        BigInteger wari = new BigInteger("1000000007");

        //BigDecimal tenBeki =  ten.pow(input);
        //BigDecimal nineBeki =  nine.pow(input).multiply(new BigDecimal(2));
        //BigDecimal eightBeki =  eight.pow(input);

        BigInteger answer = ten.pow(input).
        subtract(nine.pow(input).multiply(new BigInteger("2"))).add(eight.pow(input));
        answer = answer.remainder(wari);
        System.out.println(answer);
    }
}


Measured memory_bytes: 88716
#include <bits/stdc++.h>

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  int c = max(a, b);
  cout << fixed << setprecision(12) << c*c*c*4.0*acos(-1)/3.0 << endl;
  return 0;
}



Measured memory_bytes: 3272
#include <bits/stdc++.h>
    using namespace std;
    int N,K;
    int INF = INT_MAX;
    int h[100105];
    long cost[100105];
     
    int main(){
        cin >> N >> K;
        for(int i = 1; i <= N; ++i){
            cin >> h[i];
            cost[i] = INF;
        }
        
        cost[1] = 0;
        
        for(int i = 1; i <= N; ++i){   
            for(int j = 1; j <= K; ++j){
                cost[i + j] = min(cost[i + j],cost[i] + abs(h[i+j]-h[i]));
            }
        }
        
        cout << cost[N] << endl;
        
    }

Measured memory_bytes: 1408
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		long[][] D = new long[V][V];
		long[][] W = new long[V][V];
		for (int i = 0; i < V; ++i) {
			Arrays.fill(D[i], INF);
			Arrays.fill(W[i], INF);
			W[i][i] = 0;
			D[i][i] = 0;
		}
		for (int i = 0; i < E; ++i) {
			int s = sc.nextInt();
			int t = sc.nextInt();
			long d = sc.nextLong();
			D[s][t] = d;
		}
		W = mul(pow(D, V), W);
		boolean nega = false;
		for (int i = 0; i < V; ++i) {
			nega |= W[i][i] < 0;
		}
		if (nega) {
			System.out.println("NEGATIVE CYCLE");
			return;
		}
		for (int i = 0; i < V; ++i) {
			for (int j = 0; j < V; ++j) {
				System.out.print((W[i][j] >= INF ? "INF" : W[i][j]) + (j == V - 1 ? "\n" : " "));
			}
		}

	}

	long[][] pow(long[][] a, long n) {
		long[][] ret = new long[a.length][a.length];
		for (int i = 0; i < n; ++i) {
			Arrays.fill(ret[i], INF);
			ret[i][i] = 0;
		}
		for (; n > 0; n >>= 1, a = mul(a, a)) {
			if (n % 2 == 1) {
				ret = mul(ret, a);
			}
		}
		return ret;
	}

	long INF = Long.MAX_VALUE / 10;

	long[][] mul(long[][] a, long[][] b) {
		int n = a.length;
		long[][] ret = new long[n][n];
		for (int i = 0; i < n; ++i) {
			Arrays.fill(ret[i], INF);
		}
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				for (int m = 0; m < n; ++m) {
					if (ret[i][j] >= INF && (a[i][m] >= INF || b[m][j] >= INF))
						ret[i][j] = INF;
					else
						ret[i][j] = Math.min(ret[i][j], a[i][m] + b[m][j]);
				}
			}
		}
		return ret;
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

Measured memory_bytes: 61384
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <bitset>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
clock_t __my_start_clock = clock();
#else
#define eprintf(...)
#endif

#define TIMESTAMP(x) eprintf("["#x"] Time : %.3lf s.\n", (clock() - __my_start_clock)*1.0/CLOCKS_PER_SEC)
#define TIMESTAMPf(x,...) eprintf("[" x "] Time : %.3lf s.\n", __VA_ARGS__, (clock() - __my_start_clock)*1.0/CLOCKS_PER_SEC)

using namespace std;

#ifdef LOCAL
static struct __timestamper {
  string what;
  __timestamper(const char* what) : what(what){};
  __timestamper(const string& what) : what(what){};
  ~__timestamper(){
    TIMESTAMPf("%s", what.data());
	}
} __TIMESTAMPER("end");
#else 
struct __timestamper {};
#endif

typedef long long ll;
typedef long double ld;

char s[300000];

int main() {
#ifdef LOCAL
  freopen("b.in", "r", stdin);
  freopen("b.out", "w", stdout);
#endif

  while (scanf("%s", s) == 1) {
    ll ans = 0;
    int cur_a = 0;
    for (int i = 0; s[i]; i++) {
      if (s[i] == 'A') {
        cur_a++;
      } else if (s[i] == 'B' && s[i + 1] == 'C') {
        ans += cur_a;
        i += 1;
      } else {
        cur_a = 0;
      }
    }
    printf("%lld\n", ans);
  }

  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;


int main() {
    int N;
    vector<int> L;
    cin>>N;
    
    
    for (int i=0; i<N; i++) {
        int x;
        cin>>x;
        L.push_back(x);
    }
    
    
    int max=0;
    for (int i=0; i<N; i++) {
        if(L[i]>max){
            max=L[i];
        }
    }
   
    int sum= std::accumulate(L.begin(), L.end(), 0);
    if(max<sum-max){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
from collections import deque

def bfs(queue, visited):
    while len(queue) > 0:
        dest = queue.popleft()
        for i in G[dest]:
            if visited[i] == -1:
                visited[i] = visited[dest] + 1
                queue.append(i)
    return visited


n,x,y = map(int, input().split())

G = {}
G[0]=[1]

for i in range(n-1):
    G[i+1] = [i]
    if i==0:
        continue
    G[i].append(i+1)
G[x-1].append(y-1)
G[y-1].append(x-1)

dis_table=[]
for i in range(n):
    visited = [-1]*n
    queue = deque()
    visited[i]=0
    queue.appendleft(i)
    dis_table.append(bfs(queue, visited))

ans = [0]*(n-1)
for i in range(1,n):
    for j in range(0,i):
        ans[dis_table[i][j]-1]+=1

for i in ans :
    print(i)



Measured memory_bytes: 80220
#include <iostream>
#include <vector>
#include <algorithm>
// #include <set>
// #include <string>
// #include <cmath>
// #include <map>
// #include <iomanip>

#define MOD 1000000007

using namespace std;
typedef unsigned long long ull;
// typedef long long ll;

// void p() {
//     cout << "\n";
// }
// template<class Head, class... Body>
// void p(Head head, Body... body) {
//     cout << head << ",";
//     p(body...);
// }

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "[";
    for (const auto i : v) {
        os << i << " ";
    }
    os << "]";
    return os;
}


int main(int argc, char const *argv[]) {
    int A, B, C;
    cin >> A >> B >> C;
    if (C >= A && C <= B) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
using ll=long long;
using namespace std;

int main(){
    int N,M;
    cin>>N>>M;
    vector<int> s(M);
    vector<int> c(M);
    for(int i=0;i<M;i++){
        cin>>s[i]>>c[i];
    }
    
    int st=1;
    for(int i=1;i<N;i++){
        st*=10;
    }
    int ed=st*10;
    if(N==1){
        st=0;
    }
    int ans=-1;
    for(int i=st;i<ed;i++){
        vector<int> a;
        int tmp=i;
        if(tmp==0){
            a.push_back(0);
        }
        while(tmp!=0){
            a.push_back(tmp%10);
            tmp/=10;
        }
        int flag=1;
        for(int j=0;j<M;j++){
            if(a[N-s[j]]!=c[j]){
                flag=0;
                break;
            }
        }
        if(flag){
            ans=i;
            break;
        }
    }
    cout<<ans<<endl;


    return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

int road[51];
int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	int n, m;
	cin >> n >> m;

	for(int i=0; i<m; i++){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		road[a]++;
		road[b]++;
	}
	for(int i=0; i<n; i++){
		cout << road[i] << endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	std::vector<int>a(3), b(3);
	rep(i, 3) in >> a[i] >> b[i];

	std::vector<int>cnt(5);
	rep(i, 3)
	{
		++cnt[a[i]];
		++cnt[b[i]];
	}
	out << ((cnt[1] > 2 || cnt[2] > 2 || cnt[3] > 2 || cnt[4] > 2) ? "NO" : "YES") << std::endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int64_t H, W;

    cin >> H >> W;

    if (H % 3 == 0 || W % 3 == 0)
    {
        cout << 0 << endl;
        return 0;
    }

    int64_t result = min(H, W);

    for (int i = 0; i < 2; i++)
    {
        for (int ww = 1; ww < W; ww++)
        {
            int64_t a0 = H * ww;
            int64_t a1 = H / 2 * (W - ww);
            int64_t a2 = H * W - a0 - a1;

            int64_t aMax = max(a0, max(a1, a2));
            int64_t aMin = min(a0, min(a1, a2));
            result = min(result, aMax - aMin);
        }

        swap(H, W);
    }

    cout << result << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>

#include<cstring>

#define ll long long
using namespace std;
long long power(ll x, ll n) {
  if (n == 0) return 1;
  ll temp = power(x, n / 2);
  if (n % 2 == 0) return temp * temp;
  else return x * temp * temp;

}
ll max(ll a, ll b) {
  return a > b ? a : b;

}

ll max(ll a, ll b, ll c) {
  return max(max(a, b), c);
}
ll min(ll x, ll y) {
  return x + y - max(x, y);
}
ll min(ll x, ll y, ll z) {
  return min(min(x, y), z);

}

void swap(int * a, int * b) {
  int t = * a;
  * a = * b;
  * b = t;
}

bool f(ll x, ll y) {
  return x > y;

}

int main() {
  ll n;
  cin >> n;
  cin.ignore();
  string s;
  cin >> s;
  ll total = (n * (n - 1) * (n - 2)) / 6;

  s = 'a' + s;

  ll r, b, g;
  r = b = g = 0;
  for (ll i = 1; i <= n; i++) {
    if (s[i] == 'R') r++;
    if (s[i] == 'B') b++;
    if (s[i] == 'G') g++;
  }

  ll count1 = (r * (r - 1) * (r - 2)) / 6 + (b * (b - 1) * (b - 2)) / 6 + (g * (g - 1) * (g - 2)) / 6;
  ll count2 = ((r * (r - 1)) * (b + g)) / 2 + ((b * (b - 1)) * (r + g)) / 2 + ((g * (g - 1)) * (b + r)) / 2;
  ll count3 = 0;

  for (ll i = 1; i <= n; i = i + 2) {
    for (ll k = i + 2; k <= n; k = k + 2) {
      ll j = (i + k) / 2;
      if ((s[i] != s[j]) && (s[i] != s[k]) && (s[j] != s[k])) count3++;

    }

  }
  for (ll i = 2; i <= n; i = i + 2) {
    for (ll k = i + 2; k <= n; k = k + 2) {
      ll j = (i + k) / 2;
      if ((s[i] != s[j]) && (s[i] != s[k]) && (s[j] != s[k])) count3++;

    }

  }
  cout << total - count1 - count2 - count3;

  return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n;
	cin >> n;
	map<string, int> a;
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		string b;
		cin >> b;
		sort(b.begin(), b.end());
		a[b]++;
	}
    for (auto& p : a) {
    	int c = p.second;
		ans += (long long)c * (c - 1) / 2;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 11136
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;

int main(){
    int n;cin>>n;
    if(n<1000)cout<<"ABC"<<endl;
    else cout<<"ABD"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 17;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x1f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

char in[805][805];
int dis[805][805];
int main() {
	int H, W, K, i, j;
	scanf("%d %d %d", &H, &W, &K);
	for (i = 0; i < H; i++) scanf("%s", in[i]);

	int sx, sy;
	for (i = 0; i < H; i++) for (j = 0; j < W; j++) if (in[i][j] == 'S') sx = i, sy = j;
	
	memset(dis, 0x3f, sizeof(dis));
	dis[sx][sy] = 0;
	vector <pii> Vu;
	Vu.emplace_back(sx, sy);
	for (i = 0; i < Vu.size(); i++) {
		for (j = 0; j < 4; j++) {
			int x = Vu[i].first + "1102"[j] - '1';
			int y = Vu[i].second + "0211"[j] - '1';
			if (x >= 0 && x < H && y >= 0 && y < W && dis[x][y] == INF && in[x][y] != '#') {
				dis[x][y] = dis[Vu[i].first][Vu[i].second] + 1;
				Vu.emplace_back(x, y);
			}
		}
	}

	int ans = INF;
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			if (dis[i][j] > K) continue;
			int t = min((i + K - 1) / K, (H - 1 - i + K - 1) / K);
			t = min(t, min((j + K - 1) / K, (W - 1 - j + K - 1) / K));
			ans = min(ans, 1 + t);
		}
	}
	return !printf("%d\n", ans);
}

Measured memory_bytes: 13548
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
if n%2:
    print(n//2)
else:
    print(n//2-1)

Measured memory_bytes: 38484
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#define  rep(i,a,b)for(int i=a;i<b;++i)
#define  rrep(i,a,b)for(int i=a;i>b;--i)
#define  yesno(flag)if(flag)cout<<"Yes"<<endl; else cout<<"No"<<endl;
using namespace std;
typedef long long ll;
const ll INF=100000000000LL;
const ll r197=1000000007;
typedef pair<int,int>P;
vector<P> v1[100001];
int main() {
	int n,a,b[100000]={};
	cin>>n;
	rep(i,0,n){
		cin>>a;
		b[a]++;
	}
	bool k=false;
	int h=n/2;
	if(n%2>0&&b[0]!=1)k=true;
	if(n%2==0&&b[0]>0)k=true;
	rep(i,1,n){
		if(n%2>0&&i%2>0&&b[i]>0)k=true;
		if(n%2>0&&i%2==0&&b[i]!=2)k=true;
		if(n%2==0&&i%2>0&&b[i]!=2)k=true;
		if(n%2==0&&i%2==0&&b[i]>0)k=true;
	}
	if(k)cout<<0<<endl;
	else{
		ll ans=1;
		rep(i,0,h)ans=(ans*2)%r197;
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define range(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) range(i, 0, a)
using namespace std;

int main() {
    int a, sum = 0;
    rep (i, 5) cin >> a, sum += max(a, 40);
    cout << sum / 5.0 << endl;
    return 0;
}


Measured memory_bytes: 3276
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define all(x) x.begin(),x.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG

signed main() {
	int a=100;
    int X;
	cin>>X;
	int count=0;
	while(true){
		if(X<=a){
			break;
		}
		
		a*=1.01;
		count++;
	}
	cout<<count<<endl;
	

}


Measured memory_bytes: 3652
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>




int main(int argc, const char * argv[]){
    
    //Input
    char input[2000];
    char cmp[2000];
    int len;
    int cmp_len;
    int i, j,k;
    
    fgets(input, 2000, stdin);
    fgets(cmp, 2000, stdin);
    
    len = strlen(input) - 1;
    cmp_len = strlen(cmp) - 1;
    
    for(i=0; i < len; i++){
        k= 0;
        while(
              k < cmp_len
              &&
              i + k < len
              &&
              *(input + i + k) == *(cmp + k)
              )
        {
            k++;
        }
        if(k == cmp_len){
            printf("%d\n", i);
        };
        
    }
    
    return 0;
}

Measured memory_bytes: 524
#include <iostream>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
#include <numeric> // accumulate(begin,end,初期値)
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <set>
#include <cmath>

typedef long long ll;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<x<<endl
#define rep(i,n) for(int i = 0;i < ((int)(n));++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SUM(vec) accumulate(all(vec),0)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define test(a) cout<<#a<<':'<<a<<endl

const ll INF = 1e9+7;

// 各桁の和
template<typename T>inline T digit(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;}
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);}
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;}
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;}


class tree{
public:
  tree* par;
  vector<tree*> chi;
  int cnt;
};


int main() {
  cin.tie(0); ios::sync_with_stdio(0);
  int a,b;cin>>a>>b;
  int now = 1;
  int ans = 0;
  while(now < b){
    --now += a;
    ++ans;
  }
  print(ans);
  return 0;
}

Measured memory_bytes: 256
memo=[-1]*87
def lucas(n):

    if n==0:
        return 2
    if n==1:
        return 1
    if memo[n]!=-1:
        return memo[n]
    else:
        memo[n]=lucas(n-1)+lucas(n-2) 
        return memo[n]
print(lucas(int(input()))) 

Measured memory_bytes: 3060
#include <fstream>
#include <algorithm>
#include <iostream>

using namespace std;

long long N, G, i, j, mx;
long long p[105], P, w[105], a[100005], b[100005];

int main() {
    //ifstream cin("rucsac.in");
    cin >> N >> G;
    for (i = 1; i <= N; i++) {
        cin >> w[i] >> p[i];
        P += p[i];
    }
    for (i = 1; i <= P; i++)
        b[i] = 1000000000;
    //cout << P << " ";
    b[0] = 0;
    for (i = 1; i <= N; ++i) {
        for (j = 0; j <= P; ++j) {
            if (p[i] > j)a[j] = min(b[j], w[i]);
            else {
                a[j] = min(b[j], b[j - p[i]] + w[i]);
                if (a[j] <= G) {
                    mx = max(mx, j);
                }
            }
        }
        //cout << "\n";

        for (j = 0; j <= P; ++j) {
            b[j] = a[j];
          //  if (a[j] >= 1000000000)cout << "inf ";
          //  else cout << a[j]<<" ";
            //cout<<"("<<j<<") ";
        }
       // cout<<"|||\n";
    }
    cout << mx;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
  
int main(){
    static int n,t,s,a,b,dp[3000+2][3000+2]={0};
    scanf("%d%d%d",&n,&t,&s);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        for(int j=1;j<=t;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(j>=b&&!(j-b<s&&j>s))dp[i][j]=max(dp[i][j],dp[i-1][j-b]+a);
        }
    }
    printf("%d\n",dp[n][t]);
}

Measured memory_bytes: 36372
#include <iostream>

using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    for (int i = 0; i < W + 2; ++i) {
        cout << "#";
    }
    cout << endl;
    for (int j = 0; j < H; ++j) {
        char c;
        cout << "#";
        for (int k = 0; k < W; ++k) {
            cin >> c;
            cout << c;
        }
        cout << "#" << endl;
    }
    for (int i = 0; i < W + 2; ++i) {
        cout << "#";
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 200000
#define Pr pair<int,int>
#define X first
#define Y second 
int n;
long long ans;
int a[MAXN+1],b[MAXN+1];
priority_queue <Pr> Q;
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&b[i]);
		if(b[i]!=a[i]){
			Q.push(Pr(b[i],i));
		}
		if(b[i]<a[i]){
			printf("-1\n");
			return 0;
		}
	}
	while(!Q.empty()){
		int val=Q.top().X,pos=Q.top().Y,pval;
		Q.pop();
		if(!Q.empty()){
			pval=min(Q.top().X,max(b[(pos-1+n)%n],b[(pos+1)%n]));
		}else pval=max(b[(pos-1+n)%n],b[(pos+1)%n]);
		int dec=b[(pos-1+n)%n]+b[(pos+1)%n];
		int step=min(((val-pval)/dec)+1,(val-a[pos])/dec);
		b[pos]-=step*dec;
		//printf("%d %d\n",pos,b[pos]); 
		ans+=step;
		if(step<=0||a[pos]>b[pos]){
			printf("-1\n");return 0;
		}
		if(a[pos]<b[pos])Q.push(Pr(b[pos],pos));
	}
	printf("%lld",ans);
}

Measured memory_bytes: 3700
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>

#include <time.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384

using namespace std;
using ll =long long;
using P = pair<int,int>;

#define MAX_N 200001

ll N;
ll A[MAX_N];
ll Ans = 0;

int main(int argc, const char * argv[]) {
    
    cin >> N;
    
    rep(i, N){
        cin >> A[i];
    }
    
    sort(A, A+N);
    reverse(A, A+N);
    
    Ans += A[0];
    for(int i=2; i<N; i++){
        Ans += A[i/2];
    }
    
    cout << Ans << endl;
    
    return 0;
}

/*
clock_t start = clock();
clock_t end = clock();
cout << "duration = " << (double)(end - start) / CLOCKS_PER_SEC;
*/


Measured memory_bytes: 4720
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod %
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
    int cnt = 0;
    int n, m, c; cin >> n >> m >> c;
    vector<int> b(m); rep(i,m) cin >> b.at(i);
    vector<vector<int>> a(n, vector<int>(m));
    rep(y,n)rep(x,m) cin >> a.at(y).at(x);

    rep(i,n){
        int sumx = 0;
        rep(j,m){
            sumx += a.at(i).at(j) * b.at(j);
        }
        sumx += c;
        if(sumx > 0){ cnt++; }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
  string s, t;
  cin >> s >> t;
  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());
  if (s < t) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
fn main() {
    solve();
}
pub fn solve() {
    let mut buf = String::new();
    let handle = std::io::stdin();
    handle.read_line(&mut buf).unwrap();
    let n: isize = buf.trim().parse().unwrap();
    match n {
        25 => println!("{}", "Christmas"),
        24 => println!("{}", "Christmas Eve"),
        23 => println!("{}", "Christmas Eve Eve"),
        22 => println!("{}", "Christmas Eve Eve Eve"),
        _ => {},
    }
}

Measured memory_bytes: 4352
#include<stdio.h>
#include<math.h>

typedef struct{
  double x;
  double y;
} Point;

void kock(int,Point,Point);

int main(void){
  int n;
  Point p1={0,0},p2={100,0};
  
  scanf(" %d",&n);

  printf("%f %f\n",p1.x,p1.y);
  kock(n,p1,p2);
  printf("%f %f\n",p2.x,p2.y);
  
  return 0;
}

void kock(int n, Point p1, Point p2){
  Point s,u,t;
  
  if(n == 0)return;

  s.x = (2*p1.x + 1*p2.x)/3;
  s.y = (2*p1.y + 1*p2.y)/3;
  t.x = (1*p1.x + 2*p2.x)/3;
  t.y = (1*p1.y + 2*p2.y)/3;

  u.x = (t.x - s.x)*cos(M_PI/3) - (t.y - s.y)*sin(M_PI/3) + s.x;
  u.y = (t.x - s.x)*sin(M_PI/3) + (t.y - s.y)*cos(M_PI/3) + s.y;

  kock(n-1, p1, s);
  printf("%f %f\n",s.x,s.y);
  kock(n-1, s, u);
  printf("%f %f\n",u.x,u.y);
  kock(n-1, u, t);
  printf("%f %f\n",t.x,t.y);
  kock(n-1, t, p2);
}



Measured memory_bytes: 2112
#include <bits/stdc++.h>
#define SZ(c)       int(c.size())
#define FOR(i,a,b)  for (int i=a; i<(b); ++i)
#define DOWN(i,a,b) for (int i=(a)-1; i>=(b); --i)
using namespace std;
using i64 = long long;

i64 solve(int x,int y) {
  if (x==y) { return -1; }
  if (x%y!=0) { return x; }
  for (int i=1; i<y; ++i) {
    i64 z=i64((y/x)+i)*x;
    if (z%y!=0) { return z; }
  }
  return -1;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout<<fixed<<setprecision(10);

  int x,y;
  cin>>x>>y;
  cout<<solve(x,y)<<endl;

  return 0;
}


Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

long calc(int K, int[] a) {
    long ans = long.max;
    int n = cast(int) a.length;
    auto buf = new int[n];
    auto mask = new bool[n];
    for (int i = 1; i < (1 << n); i++) {
        // a[0] は必ず見えてしまうのでビットを立てる
        if (!(i & (1 << 0))) continue;

        mask[] = false;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                mask[j] = true;
            }
        }
        if (mask.count(true) != K) continue;

        buf[] = a[];
        if (K > 1) {
            for (int j = 0; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (mask[j] && mask[k]) {
                        // j と k の間にある壁は j より低くする
                        int h = buf[j];
                        for (int m = j; m < k; m++) {
                            h = max(h, buf[m]);
                        }

                        buf[j] = h;
                        buf[k] = max(h + 1, buf[k]);
                        break;
                    }
                }
            }
        }

        // ラストのビットの壁を一番高くする(それより後ろの壁は見えなくする)
        int h = 0;
        for (int j = n - 1; j >= 0; j--) {
            h = max(h, buf[j]);
            if (mask[j]) {
                buf[j] = h;
                break;
            }
        }

        long cost = 0;
        for (int j = 0; j < n; j++) {
            cost += buf[j] - a[j];
        }
        ans = min(ans, cost);
    }
    return ans;
}

void main() {
    auto nk = readints;
    int k = nk[1];
    auto a = readints;
    writeln(calc(k, a));
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

int main() {
   long int n,q;
   cin>>n;
   
   long int A[n],tot=0;
   map<long int,long int>P;
   for(long int i=0;i<n;++i)
   {
       cin>>A[i];
       tot+=A[i];
       P[A[i]]++;
   }
   
   cin>>q;
   for(long int i=0;i<q;++i)
   {
       long int I,D;
       cin>>I>>D;
       long int temp=tot;
       
       P[D]=P[I]+P[D];
       
       temp+=(D-I)*P[I];
       P[I]=0;
       tot=temp;
       cout<<temp<<endl;
   }
   
 
}

Measured memory_bytes: 10276
#include<bits/stdc++.h>
using namespace std;

#define FAST ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define PER(j,n,a) for (int j=n-1;j>=a;j--)
#define REP(i,a,n) for (int i=a;i<n;i++)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define show(x) cout<<(x)<<endl
#define UM unordered_map
#define PB push_back
#define V vector
#define EPS 1e-8
typedef unsigned long ul;
typedef long long ll;
typedef string str;
/*FIN*/

int main() {
	FAST;
	int h,w,m;
	int a,b,x,y,ans,ans2;
	cin>>h>>w>>m;
	set<int> grid[h];
	V<int> rcnt(h,0),ccnt(w,0);
	REP(i,0,m) {
		cin>>a>>b;
		a--;b--;
		grid[a].insert(b);
		rcnt[a]++;
		ccnt[b]++;
	}
	x=0;
	REP(i,0,h) {
		if(rcnt[i] > rcnt[x])
			x=i;
	}
	y=w-1;
	PER(i,w,0) {
		if(ccnt[i] > ccnt[y])
			y=i;
		if(ccnt[i] == ccnt[y] and grid[x].count(i)==0)
			y=i;
	}
	ans = rcnt[x] + ccnt[y];
	if(grid[x].count(y)==1)
		ans--;

	y=w-1;
	PER(i,w,0) {
		if(ccnt[i] > ccnt[y])
			y=i;
	}
	x=0;
	REP(i,0,h) {
		if(rcnt[i] > rcnt[x])
			x=i;
		if(rcnt[i] == rcnt[x] and grid[i].count(y)==0)
			x=i;
	}
	ans2 = rcnt[x] + ccnt[y];
	if(grid[x].count(y)==1)
		ans2--;
	show(max(ans,ans2));
	return 0;
}



Measured memory_bytes: 33824
#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;

static const int MAX=100;
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;
static const int INF=-1;
int n,adj[MAX+1][MAX+1];
int color[MAX+1],d[MAX+1];
queue<int> Q;

void bfs(){
  for(int i=1;i<=n;i++){
    color[i]=WHITE;
    d[i]=INF;
  }
  d[1]=0;
  color[1]=GRAY;
  Q.push(1);
  while(!Q.empty()){
    int u=Q.front(); Q.pop();
    for(int i=1;i<=n;i++){
      if(adj[u][i] && color[i]==WHITE){
        color[i]=GRAY;
        d[i]=d[u]+1;
        Q.push(i);
      }
    }
    color[u]=BLACK;
  }
}

int main(){
  cin >> n;
  for(int i=1;i<=n;i++){
    int u,k; cin >> u >> k;
    for(int i=1;i<=n;i++) adj[u][i]=0;
    for(int i=0;i<k;i++){
      int v; cin >> v;
      adj[u][v]=1;
    }
  }
  bfs();
  for(int id=1;id<=n;id++)
    printf("%d %d\n",id,d[id]);
}

Measured memory_bytes: 3268
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#define REP(i,n) for(int i=0;i<n;i++)
#define LOOP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
const int MOD=1e9+7;
const int INF=1e10;

signed main(){
  int n;
  cin>>n;
  int ans=0,p=1;
  while(n>=p-1){
    ans++;
    p*=2;
  }
  cout<<ans-1<<endl;
  return 0;
}



Measured memory_bytes: 3100
use std::io::*;
use std::str::FromStr;
use std::collections::HashMap;
use std::collections::BTreeSet;
use std::collections::HashSet;
use std::cmp;
use std::f64::consts;

fn main() {
    let n: i64 = read();
    let mut vec: Vec<(i64,i64,i64)> = Vec::new();

    for i in 0..n-1 {
        let each: (i64,i64,i64) = (read(),read(),read());
        vec.push(each);
    }

    for i in 0..n {
        let mut current_time = 0;

        if i == n-1 {
            println!("{}", 0);
            break;
        }

        let index: usize = i as usize;

        let tsugimade = vec[index].0;
        let first_start = vec[index].1;
        let sonogo = vec[index].2;

        current_time += first_start;
        current_time += tsugimade;

        let mut next_index = index + 1;
        while next_index < n as usize -1 {
            let next_tsugimade = vec[next_index].0;
            let mut next_first_start = vec[next_index].1;
            let next_sonogo = vec[next_index].2;

            if current_time >= next_first_start {
                while next_first_start < current_time {
                    next_first_start+=next_sonogo;
                }
            }

            current_time = next_first_start + next_tsugimade;
            next_index+=1;
        }

        println!("{}", current_time);
    }
}

fn calc_distance(x: i32, y: i32, target_x: i32, target_y: i32) -> i32 {
    let diff_x = (target_x - x).abs();
    let diff_y = (target_y - y).abs();

    return diff_x + diff_y;
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

// 最大公約数
fn gcd(a: i32, b: i32) -> i32 {
    match b {
        0 => a,
        _ => gcd(b, a % b)
    }
}

// 最小公倍数
fn lcm(a: i32, b: i32) -> i32 {
    a * b / gcd(a, b)
}

// 階乗
fn kaijou(n: i32)->i32 {
    if n == 1 {
        return n;
    }
    return n * kaijou(n-1);
}

Measured memory_bytes: 4352
/*
 *    author:  Gary Shih
 *    created: 2020-05-03 22:50:48
 */
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.setf(ios::fixed), cout.precision(9);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> adj(n);
  vector<int> inDegree(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    adj[u].push_back(v);
    ++inDegree[v];
  }
  vector<int> len(n);
  queue<int> q;
  for (int i = 0; i < n; ++i)
    if (!inDegree[i]) {
      q.push(i);
      len[i] = 0;
    }
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    for (int child : adj[now]) {
      --inDegree[child];
      if (!inDegree[child]) {
        len[child] = len[now] + 1;
        q.push(child);
      }
    }
  }
  cout << *max_element(len.begin(), len.end()) << '\n';
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,m,i,j,flag,sum=0,sum1=0,cnt=0,a,b,c;
    string str,s1;
    char ch;
    vector<long long int>vec;
    list<long long int>mylist;
    vector<long long int>::iterator it1;
    list<long long int>::iterator it2;
    cin>>a>>b>>c;
    swap(a,b);
    swap(a,c);
    cout<<a<<" "<<b<<" "<<c<<endl;


}


Measured memory_bytes: 256
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use proconio::*;
use text_io::*;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    input! {
        n:usize,
        a:[usize;n],
    }

    let &max_num = a.iter().max().unwrap();
    let is_set_wise = a.iter().fold(0, |acc, ai| acc.gcd(ai)) == 1;

    let era = Eratosthenes::new(max_num);
    let mut divisor_counter = vec![0; max_num + 1];

    for ai in a {
        let hm = era.factorization(ai);

        for (k, _v) in hm {
            divisor_counter[k] += 1;
        }
    }

    let is_pair_wise = *divisor_counter.iter().max().unwrap() <= 1;

    let ans = if is_pair_wise {
        "pairwise coprime"
    } else if is_set_wise {
        "setwise coprime"
    } else {
        "not coprime"
    };

    println!("{}", ans);
}

use itertools::Itertools;
use std::collections::HashMap;
use num::Integer;
use rustc_hash::FxHashMap;

/// 二分累乗法
pub fn pow(x: isize, n: usize) -> isize {
    if n == 0 {
        1
    } else if n == 1 {
        x
    } else if n % 2 == 1 {
        x * pow(x, n - 1)
    } else {
        pow(x * x, n / 2)
    }
}

/// エラトステネスの篩
/// 構築 O(N log log N)
/// 素因数分解 O(log N)
/// 素数判定 O(log N)
pub struct Eratosthenes {
    smallest_prime_factors: Vec<usize>,
}

impl Eratosthenes {
    pub fn new(n: usize) -> Self {
        let mut smallest_prime_factors = (0..=n).collect_vec();

        for i in 2.. {
            if i * i > n {
                break;
            }

            if smallest_prime_factors[i] != i {
                continue;
            }

            let mut j = i * i;
            while j <= n {
                if smallest_prime_factors[j] == j {
                    smallest_prime_factors[j] = i;
                }

                j += i;
            }
        }

        Self {
            smallest_prime_factors,
        }
    }

    pub fn factorization(&self, mut i: usize) -> FxHashMap<usize, usize> {
        assert_ne!(i, 0);

        let mut factors = FxHashMap::default();

        while i != 1 {
            let divisor = self.smallest_prime_factors[i];
            *factors.entry(divisor).or_insert(0) += 1;

            i /= divisor;
        }

        factors
    }

    pub fn is_prime(&self, i: usize) -> bool {
        i >= 2 && self.smallest_prime_factors[i] == i
    }
}


Measured memory_bytes: 28372
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  int K;
  string S;
  cin >> K >> S;
  if(S.size() <= K) {
    cout << S << endl;
  } else {
    cout << S.substr(0, K) << "..." << endl;
  }
  return 0;
}


Measured memory_bytes: 3644
n,m,k=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edge[a].append(b)
    edge[b].append(a)

from collections import deque
label=[-1]*n

i=0
for start in range(n):
    if label[start]!=-1:
        continue
    else:
        i+=1
        label[start]=i    
    f=deque([start])
    while f:
        v=f.popleft()        
        for e in edge[v]:
            if label[e]==-1:
                label[e]=i
                f.append(e)   

Renketsu=[0]*(n+1)

for i in label:
    Renketsu[i]+=1

Block=[0]*n
for _ in range(k):
    c,d=map(int,input().split())
    c,d=c-1,d-1
    if label[c]==label[d]:
        Block[c]+=1
        Block[d]+=1

ans=[]
for k in range(n):
    ans.append(Renketsu[label[k]]-1 - len(edge[k]) - Block[k])
print(*ans)

Measured memory_bytes: 33872
#import math
#input()
#int(input())
N,M=map(int,input().split())
H = list(map(int,input().split()))
AB=[list(map(int,input().split())) for _ in range(M)]

bad_l = []
for i in range(M):
    h1 = H[AB[i][0]-1]
    h2 = H[AB[i][1]-1]
    if h1 <= h2:
        bad_l.append(AB[i][0])
    if h1 >= h2:
        bad_l.append(AB[i][1])
p = list(set(bad_l))
print(N-len(p))

Measured memory_bytes: 34488
#include <stdio.h>
 
int main(){
	long long int n, sum = 0;
	scanf("%lld", &n);
	for (int i=0 ; i<=n ; i++){
		if (i%3 == 0 || i%5 == 0 ){
			continue;
		}
		else {
			sum+=i;
		}
	}
	printf("%lld", sum);
	
	return 0;
}


Measured memory_bytes: 1712
#include<bits/stdc++.h>
using namespace std;
const int maxn=205;
int n,m;
int a[maxn][maxn],sum[maxn][maxn];
int f[maxn][maxn][maxn][15];
inline bool ok(int l,int r,int u,int d)
{
	int s=sum[d][r]-sum[d][l-1]-sum[u-1][r]+sum[u-1][l-1];
	return (s==0)||(s==(d-u+1)*(r-l+1));
}
inline void init()
{
	for(int i=1;i<=n;++i)
		for(int l=1;l<=m;++l)
			for(int r=l;r<=m;++r)
			{
				int U=i-1,D=n,mid;
				while(U<D)
				{
					mid=(U+D+1)>>1;
					if(ok(l,r,i,mid))
						U=mid;
					else
						D=mid-1;
				}
				f[i][l][r][0]=U;
			}
}
inline void solve()
{
	int now=1;
	while(f[1][1][m][now-1]!=n)
	{
		for(int i=1;i<=n;++i)
			for(int l=1;l<=m;++l)
				for(int r=l;r<=m;++r)
				{
					if(f[i][l][r][now-1]==n)
					{
						f[i][l][r][now]=n;
						continue;
					}
					f[i][l][r][now]=f[f[i][l][r][now-1]+1][l][r][now-1];
					if(f[i][l][r][now]==n)
						continue;
					int pL=l,pR=r-1,mid,g=0;
					while(pL<=pR)
					{
						mid=(pL+pR)>>1;
						int x=f[i][l][mid][now-1];
						int y=f[i][mid+1][r][now-1];
						g=max(g,min(x,y));
						if(x<y)
							pR=mid-1;
						else
							pL=mid+1;
					}
					f[i][l][r][now]=max(f[i][l][r][now],g);
				}
		++now; 
	}
	cout<<now-1<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			char ch;
			cin>>ch;
			if(ch=='#')
				a[i][j]=1;
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}
	init();
	solve();
	return 0;
}


Measured memory_bytes: 314884
import math

__DEUBG__ = 1
N = int(input())

def factor(num):
    for i in range(1, 1+int(math.sqrt(num))):
        q, r = divmod(num, i)
        if r == 0:
            yield i, q

minimum = N
for pair in factor(N):
    tmp = max(map(lambda x:len(str(x)), pair))
    if tmp < minimum:
        minimum = tmp

print(minimum)

Measured memory_bytes: 3064
n = int(input())
a = list(map(int, input().split()))

d = [0]*n
for i in a:
    d[i-1] += 1

ans = 0
for i in range(n):
    ans += int((d[i]*(d[i]-1))/2)

for i in range(n):
    print(ans-(d[a[i]-1]-1))

Measured memory_bytes: 32068
n = int(input())
a = list(map(int,input().split()))

div_count = sum(a)-1
node = 1
ans = 0
for i,ai in enumerate(a):
    ans += node
    
    if ai > node:
        ans = -1
        break
    else:
        div_num = min(node - ai, div_count)
        node = div_num + (node - ai)
        div_count -= div_num

print(ans)

Measured memory_bytes: 20144
#include <stdio.h>
#include <stdlib.h>
int main(){
int n;
  double count=0.0;
  scanf("%d",&n);
  
  for(int i=1;i<=n;i++){
    if(i%2==1){
      count++;   
    }
  }
    double b=count/n;
  printf("%f",b);
}

Measured memory_bytes: 128
n, m, x = map(int,input().split())
CA = [list(map(int, input().split())) for i in range(n)]
ch = [0]*m
res = 10**5*12 + 5
for i in range(2**n):
    money = 0
    ch = [0]*m
    for j in range(n):
        if ((i >> j) & 1):
            money += CA[j][0]
            for k in range(m):
                ch[k] += CA[j][k+1]
    if min(ch) >= x:
        res= min(money,res)
if res == 10**5*12 + 5:
    print(-1)
else:
    print(res)

Measured memory_bytes: 9220
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,x=0,i,j,k;
    cin>>n;
    long long a[n];
    for(i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
     for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(a[i]!=a[j])
            {
                for(k=j+1;k<n;k++)
                {
                    if(a[j]!=a[k] && a[i]!=a[k])
                    {
                        if(a[i]+a[j]>a[k])
                            x++;
                    }
                }
            }
        }
    }
    cout<<x;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

int a, b, c, d;
map<int, int> save;

__int128 go(int n) {
	if(n == 0) return 0;
	if(n == 1) return d;
	if(save.count(n)) return save[n];
	__int128 mn = (__int128) n * d;
	mn = min(mn, go((n + 1) / 2) + (2 - n % 2) % 2 * d + a);
	mn = min(mn, go(n / 2) + n % 2 * d + a);
	mn = min(mn, go((n + 2) / 3) + (3 - n % 3) % 3 * d + b);
	mn = min(mn, go(n / 3) + n % 3 * d + b);
	mn = min(mn, go((n + 4) / 5) + (5 - n % 5) % 5 * d + c);
	mn = min(mn, go(n / 5) + n % 5 * d + c);
	return save[n] = mn;
}

signed main()
{
	IO_OP;

	int t;
	cin >> t;
	while(t--) {
		save.clear();
		int n;
		cin >> n >> a >> b >> c >> d;
		cout << (ll) go(n) << endl;
	}
	
}





Measured memory_bytes: 4336
#line 1 "/workspaces/compro/lib/template.hpp"


#line 1 "/workspaces/compro/lib/io/vector.hpp"
#include <iostream>
#include <vector>

#ifndef IO_VECTOR
#define IO_VECTOR

template <class T> std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
  int size = v.size();
  for (int i = 0; i < size; i++) {
    std::cout << v[i];
    if (i != size - 1)
      std::cout << " ";
  }
  return out;
}

template <class T> std::istream &operator>>(std::istream &in, std::vector<T> &v) {
  for (auto &el : v) {
    std::cin >> el;
  }
  return in;
}

#endif
#line 4 "/workspaces/compro/lib/template.hpp"
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes, T no) { cout << (val ? yes : no) << "\n"; }

void say(bool val, string yes = "Yes", string no = "No") { say<string>(val, yes, no); }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}

// C++ 17に完全移行したら消す
// 最大公約数を求める
template <class T> T gcd(T n, T m) { return n ? gcd(m % n, n) : m; }

// 最小公倍数を求める
template <class T> T lcm(T n, T m) {
  int g = gcd(n, m);
  return n * m / g;
}

// 重複を消す。計算量はO(NlogN)
template <class T> void unique(std::vector<T> &v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
}


#line 2 "main.cpp"

long long solve(int N) {
  ll ans = 0;
  FOR(i, 1, N) { ans += (N - 1) / i; }
  return ans;
  // TODO: edit here
}

// generated by online-judge-template-generator v4.4.0 (https://github.com/kmyk/online-judge-template-generator)
int main() {
  int N;
  std::cin >> N;
  auto ans = solve(N);
  std::cout << ans << std::endl;
  return 0;
}


Measured memory_bytes: 3624
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S min_L(S a,T b){
  return a<=b?a:b;
}
inline void rd(char &c){
  int i;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c = i;
}
inline int rd(char c[]){
  int i;
  int sz = 0;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int N;
char S[1000000+2];
int main(){
  int i;
  int dp1 = 0;
  int dp2 = 1073709056;
  int nx1;
  int nx2;
  N = rd(((S+1)));
  S[0] = 0;
  N++;
  for(i=(1);i<(N);i++){
    S[i] -= '0';
  }
  for(i=(N)-1;i>=(0);i--){
    {
      auto FmcKpFmN = (min_L(dp1 + S[i], dp2 + S[i] + 1));
      auto xr20shxY = (min_L(dp1 + 10 - S[i], dp2 + 9 - S[i]));
      dp1 = FmcKpFmN;
      dp2 = xr20shxY;
    }
  }
  wt_L(dp1);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200217-1

// --- original code ---
// int N;
// char S[1d6+2];
// {
//   int dp1 = 0, dp2 = int_inf;
//   int nx1, nx2;
//   rd(((S+1))@N);
//   S[0] = 0;
//   N++;
//   rep(i,1,N) S[i] -= '0';
// 
//   rrep(i,N){
//     (dp1, dp2) = (
//       min(dp1 + S[i], dp2 + S[i] + 1),
//       min(dp1 + 10 - S[i], dp2 + 9 - S[i])
//     );
//   }
//   wt(dp1);
// }


Measured memory_bytes: 1280