akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

using namespace std;

int main (){
int k,A[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
};
  cin >> k;
  
  cout << A[k-1];
  
  


return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

template< class T >
struct CumulativeSum2D {
  vector< vector< T > > data;

  CumulativeSum2D(int W, int H) : data(W + 1, vector< int >(H + 1, 0)) {}

  void add(int x, int y, T z) {
    ++x, ++y;
    if(x >= data.size() || y >= data[0].size()) return;
    data[x][y] += z;
  }

  void build() {
    for(int i = 1; i < data.size(); i++) {
      for(int j = 1; j < data[i].size(); j++) {
        data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
      }
    }
  }

  T query(int sx, int sy, int gx, int gy) {
    return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
  }
};

char c[11][1123];

int main() {
    lint h, w, k;
    cin >> h >> w >> k;

    CumulativeSum2D<int> cum(w, h);
    for(lint i=0; i<h; i++)
    for(lint j=0; j<w; j++) {
        char c;
        cin >> c;
        cum.add(j, i, c-'0');
    }
    cum.build();

    lint ans = 1e18;
    lint base = 2;
    lint exp = h+1;
    for(lint poly = 0, mx = pow(base, exp); poly < mx; poly++) {
        lint tmp = poly;
        vector<lint> coef;
        for(lint i=0; i<exp; i++) {
            coef.push_back(tmp % base);
            tmp /= base;
        }

        #define print(...) {for(auto x: __VA_ARGS__) cout<<x<<" ";}
        #define debug(...) {cout<<#__VA_ARGS__": ";print(__VA_ARGS__);cout<<endl;}
        // debug(coef);

        vector<lint> hs;
        hs.push_back(0);
        for(lint i=0; i<exp; i++) {
            if(coef[i])  hs.push_back(i);
        }
        hs.push_back(h);

        lint cand = 0;
        cand += count(coef.begin(), coef.end(), 1);

        lint left = 0;
        for(lint right=0; right<=w; right++) {
            for(lint j=0; j+1<hs.size(); j++) {
                lint top = hs[j];
                lint bottom = hs[j+1];
                // debug({left, right});
                // debug({top, bottom});
                // debug({cum.query(left, top, right, bottom)});
                if(cum.query(left, top, right, bottom) > k) {
                    if(left == right-1)  goto CANNOT;
                    left = right-1;
                    cand++;
                    break;
                }
            }
        }
        ans = min(ans, cand);
        // cout << cand << endl;
        CANNOT:
            cand = 1e18;
    }

    cout << ans << endl;
}

Measured memory_bytes: 384
#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N],b[N],c[N],A,B,C;
int a1[N],b1[N],c1[N],n;
ll sum[N];
int ans1[N];
inline int findc(int x)
{
	int l=1,r=C,ans=0;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (x<=c[mid])l=mid+1;
		else r=mid-1,ans=mid;
	}
	return ans;
}
inline int findb(int x)
{
	int l=1,r=B,ans=0;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (x<=b[mid])l=mid+1;
		else r=mid-1,ans=mid;
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	fo(i,1,n)scanf("%d",&a[i]);
	fo(i,1,n)scanf("%d",&b[i]);
	fo(i,1,n)scanf("%d",&c[i]);
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	sort(c+1,c+1+n);
	A=B=C=n;
	for(int i=1,j=1;i<=n;i++)
	{
		while (c[j]<=b[i]&&j<=C)j++;
		ans1[i]=n-j+1;//printf("%d\n",ans1[i]);
	}
	fo(i,1,n)sum[i]=sum[i-1]+ans1[i];
	ll ans=0;
	for(int i=1,j=1;i<=A;i++)
	{
		while (b[j]<=a[i]&&j<=B)j++;
		ans=ans+1ll*(sum[B]-sum[j-1]);
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 2688
import queue
h,w = map(int,input().split())
sij = [input() for i in range(h)]

if sij[0][0] == '#' or sij[h-1][w-1] == '#':
    print(-1)
    exit()

q = queue.Queue()

q.put([0,0])

vx = [0,1,0,-1]
vy = [1,0,-1,0]

check = [0]*(h*w)
check[0] = 1

while not q.empty():
    x,y = q.get()
    for i in range(4):
        nx = x+vx[i]
        ny = y+vy[i]
        if nx >= 0 and nx <= w-1 and ny >= 0 and ny <= h-1:
            if check[ny*w+nx] == 0 and sij[ny][nx] == '.':
                q.put([nx,ny])
                check[ny*w+nx] = check[y*w+x] + 1
                if ny == h-1 and nx == w-1:
                    check[ny*w+nx] = check[y*w+x] + 1
                    break
kuro = 0

for i in range(h):
    for j in range(w):
        if sij[i][j] == '#':
            kuro += 1
if check[-1] == 0:
    print(-1)
    exit()
print(h*w-kuro-check[-1])

Measured memory_bytes: 45288
#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const ll MOD=1000000007;
const ll INF=1000000010;
const ll LINF=4000000000000000010;
const double EPS=1e-9;
int dx[5]={0,1,0,-1,0};
int dy[5]={1,0,-1,0,0};
int main(){
    string s;cin>>s;
    int n=s.length();
    string t;cin>>t;
    bool ans=false;
    for(int i=0;i<n;i++){
        bool f=true;
        for(int j=0;j<n;j++){
            if(s[(j+i)%n]!=t[j])f=false;
        }
        ans|=f;
    }
    if(ans){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=4000;
typedef long long ll;
const int mod=998244353;
int f[maxn+5][maxn+5];
int R[maxn+5],B[maxn+5];
char s[maxn+5];
int n;
void upd(int &x,int y)
{
    x=(x+y)%mod;
}
int main()
{

    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;++i)
        if(s[i]=='0') R[i]=2;
        else if(s[i]=='1') R[i]=B[i]=1;
        else if(s[i]=='2') B[i]=2;
    for(int i=1;i<=2*n;++i) R[i]+=R[i-1],B[i]+=B[i-1];
    f[0][0]=1;
    for(int i=0;i<2*n;++i)
        for(int j=0;j<=2*n;++j)
        {
            if(f[i][j]==0) continue;
            int rr=0,bb=0;
            if(s[i+1]=='0') rr=2;
            if(s[i+1]=='1') rr=bb=1;
            if(s[i+1]=='2') bb=2;
            //rr+=j;
            //if(i<=n) bb+=2*i-j;else bb+=2*n-j;
            int k=R[i]+B[i]-j-i;
            if(j+rr-1>=0&&j+rr-1<=2*n)
                upd(f[i+1][j+rr-1],f[i][j]);
            if(k+bb-1>=0&&k+bb-1<=2*n)
                upd(f[i+1][j+rr],f[i][j]);
        }
    /*for(int i=1;i<=2*n;++i)
        for(int j=0;j<=min(2*i,2*n);++j)
    {
        int rr=j;
        int bb=min(2*i,2*n)-rr;
        printf("%d %d %d : %d\n",i,rr,bb,f[i][j]);
    }*/
    cout<<f[2*n][0];
    return 0;
}


Measured memory_bytes: 60544
// AOJ 1076 Time Manipulation
// 2018.2.3 bal4u

#include <stdio.h>

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0;
	int c = getchar_unlocked();
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
	while (c >= '0');
	return n;
}

int main()
{
	int n, m, f;

	while (n = in()) {
		m = in();

		f = 0;
		while (m--) {
			if (in() == 1) f = 1;
		}

		if (f) puts("0.0000000000");
		else printf("%.10lf\n", n/2.0);
	}
	return 0;
}


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

int main()
{
    int i,n;
    double p = 0.0, p1 = 0.0, p2 = 0.0, p3 = 0.0, p_infinity = 0.0, x[100], y[100];

    scanf("%d",&n);
    for(i = 0; i < n; i++)
        scanf("%lf", &x[i]);
    for(i = 0, p1 = 0, p2 = 0, p3 = 0, p_infinity = 0; i < n; i++)
    {
        scanf("%lf", &y[i]);
        p = fabs(x[i] - y[i]);
        p1 += p;
        p2 += pow(p,2);
        p3 += pow(p,3);
        if(p > p_infinity)
            p_infinity = p;
    }
    printf("%lf\n%lf\n%lf\n%lf\n", p1, sqrt(p2), cbrt(p3), p_infinity);
    return 0;
}



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

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

using namespace std;

const double inf=1e8;

int d[31][31];
int t[10];
double dist[31][1<<8];

int n,m,p,a,b;

typedef tuple<double,int,int> state;
void dijkstra(){
	rep(i,m)rep(j,(1<<n)) dist[i][j]=inf;
	state init=make_tuple(0.0,a,0);
	dist[a][0]=0;
	priority_queue<state,vector<state>,greater<state>>q;
	q.push(init);
	while(!q.empty()){
		double cost;
		int cur,mask;
		tie(cost,cur,mask)=q.top();q.pop();
		rep(i,m){
			if(d[cur][i]==inf) continue;
			rep(j,n){
				if(mask&(1<<j)) continue;
				int ncur=i,nmask=mask|(1<<j);
				double ncost=cost+1.0*d[cur][ncur]/(t[j]);
				if(dist[ncur][nmask]>ncost){
					dist[ncur][nmask]=ncost;
					q.push(make_tuple(ncost,ncur,nmask));
				}
			}
		}
	}
	double ans=inf;
	rep(i,1<<n) ans=min(ans,dist[b][i]);
	cout.precision(10);
	if(ans==inf)
		cout << "Impossible" << endl;
	else
		cout << fixed << ans << endl;
}

int main(void){
	while(cin >> n >> m >> p >> a >> b){
		a--,b--;
		if(n==0) break;
		rep(i,n) cin >> t[i];
		rep(i,m)rep(j,m) d[i][j]=inf;
		rep(i,p){
			int x,y,z;
			cin >> x >> y >> z;
			x--,y--;
			d[x][y]=d[y][x]=z;
		}
		dijkstra();
	}
	return 0;
}

Measured memory_bytes: 2756
S = input()

length = len(S)
dp = [[0] * 13 for _ in range(length + 1)]
dp[0][0] = 1
mul = 1
INF = 10 ** 9 + 7

for i in range(length):
    
    x = S[- (i + 1)]
    
    if x == "?":
        
        for j in range(13):
            
            for k in range(10):
            
                dp[i + 1][(k * mul + j) % 13] += dp[i][j]
                dp[i + 1][(k * mul + j) % 13] %= INF
                
    else:
        
        c = int(x)
        
        for j in range(13):
            
            dp[i + 1][(c * mul + j) % 13] += dp[i][j]
            dp[i + 1][(c * mul + j) % 13] %= INF
            
    mul = (mul * 10) % 13
    
print(dp[length][5])

Measured memory_bytes: 64404
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <math.h>

#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
template<class T> using hset = unordered_set<T>;
template<class Key, class T> using hmap = unordered_map<Key, T>;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool isOutOfBounds(int y, int x, int h, int w) {
    return y < 0 || y >= h || x < 0 || x >= w;
}

int main() {
    hset<int> prime;
    for (int i=2; i<=1000000; i++) prime.insert(i);
    for (int i=2; i<=1000000; i++) {
        if (prime.find(i) != prime.end()) {
            for (int j=2; i*j<=1000000; j++) prime.erase(i*j);
        }
    }

    int a, d, n;
    while (cin >> a >> d >> n) {
        if (a == 0) break;
        a -= (a == 1) ? 0 : d;
        while (n > 0) {
            a += d;
            if (prime.find(a) != prime.end()) n--;
        }

        cout << a << endl;
    }

    return 0;
}

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

const int inf = 2e9;

int main(){
  int n;
  cin >> n;
  int umax = -inf, umin = inf;
  int vmax = -inf, vmin = inf;

  
  rep(i, n){
    int x, y;
    cin >> x >> y;
    int u = x - y;
    int v = x + y;
    umax = max(umax, u);
    umin = min(umin, u);
    vmax = max(vmax, v);
    vmin = min(vmin, v);
  }
  
  int ans = max(umax - umin, vmax - vmin);
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3604
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using pii = pair<int, int>;
const int MOD = (int)1e9 + 7, INF = (1 << 27); const ll INFLL = (1LL << 55);
#define FOR(i,a,b) for(int (i)=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
template<typename T, typename U> inline void chmax(T &x, U y) { if (x < y) x = y; }
template<typename T, typename U> inline void chmin(T &x, U y) { if (x > y) x = y; }

int n;

ll f[200010] = {0}; // f(n) = (n!) % mod
ll mod = MOD;

// 繰り返し二乗法 O(log n)
ll mod_pow(ll x, ll n) {
    ll res = 1LL;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x*x % mod;
        n >>= 1;
    }
    return res;
}

ll mod_inv(ll x) {
    return mod_pow(x, mod - 2) % mod;
}

// nCr % mod
ll comb(int n, int r) {
    return (((f[n] * mod_inv(f[r])) % mod) * mod_inv(f[n - r])) % mod;
}

void comb_test() {
    // O(w+h) で階乗テーブルをつくる
    //f[0] = f[1] = 1;
    //for (int i = 2; i <= 500 - 2; ++i) f[i] = (i * f[i - 1]) % mod;
    //assert(comb(4, 2) == 6);
    //assert(comb(6, 2) == 15);
    //assert(comb(6, 4) == 15);
    //assert(comb(11, 2) == 55);
    //cout << "ok" << "\n";

    //vector<int> a = {6,9,4,2,11};
    //rep(i, 12) {
    //    cout << i << ": " << comb(12, i) << endl;
    //}
}

int main() {
    //comb_test(); return 0;
    scanf("%d", &n);
    vector<int> a(n);
    rep(i, n) scanf("%d", &a[i]);
    if (n <= 2) {
        printf("%d %d\n", a[0], a[1]);
        return 0;
    }

    auto n = *max_element(a.begin(), a.end());
    int mid = n / 2;
    int dm = 1145141919;
    int r = 0;
    for (auto i : a) if (i != n) {
        int df = abs(mid - i);
        if (df < dm) {
            dm = df;
            r = i;
        }
    }

    cout << n << " " << r << endl;

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    ll h, w;
    cin >> h >> w;
    ll res;
    if (h == 1 || w == 1) res = 1;
    else if (h % 2 && w % 2) res = h * w / 2 + 1;
    else res = h * w / 2;
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3668
import math
def main():
    global N, A
    N = int(input())
    sizes = list(map(int, input().split()))
    A = list(zip(list(range(1, N+1)), sizes))  # color, size
    A.sort(key=lambda x:x[1])
    print(N - binary_search_for_integer(N-1, -1))

def binary_search_for_integer(ok, ng):
    while math.fabs(ok-ng) > 1:
        mid = (ok+ng)//2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

def solve(x):  # x=index
    if x != 0:
        size = sum([a[1] for a in A[:x]]) + A[x][1]
    else:
        size = A[x][1]

    for i in range(1, N-x):
        if A[x+i][1] <= 2*size:
            size += A[x+i][1] 
        else:
            return False

    return True


if __name__ == "__main__":
    main()


Measured memory_bytes: 21212
#include<vector>
#include<cmath>
#include<algorithm>

const double INF = 1e9;
const double EPS = 1e-9;

struct Point {
    Point() :x(INF), y(INF) {}
    Point(double x, double y) :x(x), y(y) {}
    double x, y;
};
struct Compare {
    bool f;
    Compare(bool f = false) :f(f) {}
    bool operator()(const Point& lhs, const Point& rhs) const {return f ? lhs.y < rhs.y : lhs.x < rhs.x;}
};
double distance(const Point& lhs, const Point& rhs) {return std::hypot(lhs.x - rhs.x, lhs.y - rhs.y);}

struct Result {
    double d;
    Point p1, p2;
    Result() :d(INF) {}
    Result(double d, const Point p1, const Point p2) :d(d), p1(p1), p2(p2) {}
};
bool operator<(const Result& lhs, const Result& rhs) {return lhs.d < rhs.d;}

Result closest_pair_recursion(const std::vector<Point>::const_iterator& begin, const std::vector<Point>::const_iterator& end) {
    int size = end - begin;
    if(size <= 1) return Result();

    auto mid = begin + size / 2;
    Result r = std::min(closest_pair_recursion(begin, mid), closest_pair_recursion(mid, end));

    auto left = std::lower_bound(begin, end, Point(mid->x - r.d - EPS, mid->y), Compare());
    auto right = std::upper_bound(left, end, Point(mid->x + r.d + EPS, mid->y), Compare());
    std::vector<Point> y_sorted(left, right);
    std::sort(y_sorted.begin(), y_sorted.end(), Compare(true));

    for(auto i = y_sorted.begin(); i != y_sorted.end(); ++i) {
        for(auto j = i + 1; j != y_sorted.end(); ++j) {
            if(j->y - i->y >= r.d) break;
            if(distance(*i, *j) >= r.d) continue;
            r = Result(distance(*i, *j), *i, *j);
        }
    }
//     // y 座標の差が r.d 以上になる点を予め計算：微妙に遅い
//     for(auto i = y_sorted.begin(); i != y_sorted.end(); ++i) {
//         auto top = std::upper_bound(i + 1, y_sorted.end(), Point(i->x, i->y + r.d + EPS), Compare(true));
//         for(auto j = i + 1; j != top; ++j) {
//             if(distance(*i, *j) >= r.d) continue;
//             r = Result(distance(*i, *j), *i, *j);
//         }
//     }

    return r;
}
Result closest_pair(std::vector<Point> point) {
    std::sort(point.begin(), point.end(), Compare());
    return closest_pair_recursion(point.begin(), point.end());
}

////////////////////////////////////////////////////////////////////////////////
#include<iostream>
#include<iomanip>
using namespace std;

int main() {
    int n;
    vector<Point> v;
    for(cin >> n; n > 0; --n) {
        double x, y;
        cin >> x >> y;
        v.push_back(Point(x, y));
    }
    auto res = closest_pair(v);
    cout <<setprecision(12) << fixed << res.d << endl;
}

Measured memory_bytes: 5764
#include <bits/stdc++.h>
using namespace std;
typedef long long int lo;

int main(){
    lo n,k;
    cin >> n >> k;
    lo arr[n+1];
    lo dp[n+1];
    memset(dp,0,sizeof dp);
    for(lo i = 1;i <=n;i++) cin >> arr[i];
    arr[0] = 0;
    dp[1] = 0;
    dp[0] = 1e9;
    for(lo i = 2;i <= n;i++){
        lo minim = 1e9;
        for(lo j = 1;j <= k and j <= i;j++){
            minim = min(minim, abs(arr[i-j]-arr[i]) + dp[i-j]);
        }
        dp[i] = minim;
        cerr << dp[i] << " " << i << endl;
    }
    cout << dp[n];
}

Measured memory_bytes: 1792
#include <iostream>
using namespace std;

int main() {
	int n,C;cin>>n>>C;;
	int c[n][n];
	int d[C][C];
	for(int i=0;i<C;i++){
		for(int j=0;j<C;j++){
			cin>>d[i][j];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>c[i][j];
			c[i][j]--;
		}
	}
	int ch[3][C];
	for(int i=0;i<3;i++){
		for(int j=0;j<C;j++){
			ch[i][j]=0;
		}
	}
	for(int k=0;k<C;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				ch[(i+j)%3][k]+=d[c[i][j]][k];
			}
		}
	}
	int ans=-1;
	for(int i=0;i<C;i++){
		for(int j=0;j<C;j++){
			for(int k=0;k<C;k++){
				if((i!=j)*(j!=k)*(k!=i)){
					int temp=ch[0][i]+ch[1][j]+ch[2][k];
					if((ans==-1)+(ans>temp))ans=temp;
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#include <atcoder/maxflow.hpp>

#define foreach(i,v) for(auto&& i: v)
#define all(x) (x).begin(), (x).end()

typedef std::vector< std::string > VS;
typedef std::vector<int> VI;
typedef long long ll;

template <class C> C& mini(C& a, C b) { if (b < a) a = b; return a; }
template <class C> C& maxi(C& a, C b) { if (a < b) a = b; return a; }

using namespace std;

template <typename T> void read(T& x) { x.read(); }
template <typename T> void read(vector<T>& v) { for (T& x: v) read(x); }
template <typename X, typename Y> void read(pair<X, Y>& p) { read(p.first); read(p.second); }
template <> void read(int& x) { scanf("%d", &x); }
template <> void read(unsigned int& x) { scanf("%u", &x); }
template <> void read(long long& x) { scanf("%lld", &x); }
template <> void read(unsigned long long& x) { scanf("%llu", &x); }
template <typename T> void readv(vector<T>& v) { int N; read(N); v.resize(N); read(v); }
template <typename T, typename ...Ts> void read(T& x, Ts&... args) { read(x); read(args...); }

char A[128][128];

int main(int argc, const char* argv[]) {
    int N, M;
    scanf("%d %d\n", &N, &M);
    for (int i = 0; i < N; i++)
        scanf("%s\n", A[i]);
    int nm = N * M;
    atcoder::mf_graph<int> G(nm+2);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            if (j < M && A[i][j] == '.' && A[i][j+1] == '.') {
                int src = i * M + j, dst = i * M + j + 1;
                if ((i ^ j) & 1)
                    swap(src, dst);
                G.add_edge(src, dst, 1);
            }
            if (i < N && A[i][j] == '.' && A[i+1][j] == '.') {
                int src = i * M + j, dst = (i + 1) * M + j;
                if ((i ^ j) & 1)
                    swap(src, dst);
                G.add_edge(src, dst, 1);
            }
            if ((i ^ j) & 1) {
                G.add_edge(i * M + j, nm+1, 1);
            } else {
                G.add_edge(nm, i * M + j, 1);
            }
        }

    auto flow = G.flow(nm, nm+1);
    printf("%d\n", flow);

    for (auto e: G.edges()) {
        if (e.flow && e.from < nm && e.to < nm) {
            int r1 = e.from / M;
            int c1 = e.from % M;
            int r2 = e.to / M;
            int c2 = e.to % M;
            if (r1 == r2)
                A[r1][min(c1, c2)] = '>', A[r2][max(c1, c2)] = '<';
            else
                A[min(r1, r2)][c1] = 'v', A[max(r1, r2)][c2] = '^';

        }
    }

    for (int i = 0; i < N; i++)
        printf("%s\n", A[i]);

    return 0;
}

Measured memory_bytes: 5648
n = gets.to_i
as = gets.split.map(&:to_i).sort
div = as[1]
until div == 0
  flag = 0
  as.each do |a|
    if a % div != 0
      flag += 1
    end
    break if flag > 1
  end
  if flag <= 1
    puts div
    break
  else
    div -= 1
  end
end


Measured memory_bytes: 10112
n = int(input())
x = list(map(int, input().split()))
x.sort()
sigmaList = list()
for p in range(x[0], x[n - 1] + 1):
    sigma = 0
    for i in range(n):
        sigma += (x[i] - p) ** 2
    sigmaList.append(sigma)
print(min(sigmaList))


Measured memory_bytes: 2940
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;



int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	string S;
	cin >> S;
	int n = S.size() - 2;
	while (n) {
		if (S.substr(0, n / 2) == S.substr(n / 2, n / 2)) {
			cout << n << "\n";
			return 0;
		}
		n -= 2;
	}

	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main{
    static MyReader in = new MyReader();
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args){
        long A, B;
        {long[] a = in.ll(); A = a[0]; B = a[1];}
        if(B < A){
            long tmp = A;
            A = B;
            B = tmp;
        }

        long g = gcd(A, B);

        int ans = 1;
        double C = Math.sqrt(g+1);
        if(g%2 == 0){
            ans++;
            while(g%2 == 0)
                g /= 2;
        }
        if(g%3 == 0){
            ans++;
            while(g%3 == 0)
                g /= 3;
        }
        for(int i = 5, j = 7; i < C ; i += 6, j += 6){
            if(g%i == 0){
                ans++;
                while(g%i == 0)
                    g /= i;
            }
            if(j < C){
                if(g%j == 0){
                    ans++;
                    while(g%j == 0)
                        g /= j;
                }
            } else break;
        }
        if(g != 1){
            ans++;
        }
        out.println(ans);

        out.flush();
    }

    static long gcd(long a, long b){
        long r;
        while((r = b%a) > 0){
            b = a;
            a = r;
        }
        return a;
    }

    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }

        String s(){
            try{return readLine();}catch(IOException e){return "";}
        }

        String[] ss(){
            return s().split(" ");
        }

        int i(){
            return Integer.parseInt(s());
        }

        int[] ii(){
            String[] ss = ss();
            int[] ii = new int[ss.length];
            for(int j = 0; j < ss.length; j++) ii[j] = Integer.parseInt(ss[j]);
            return ii;
        }

        long l(){
            return Long.parseLong(s());
        }

        long[] ll(){
            String[] ss = ss();
            long[] ll = new long[ss.length];
            for(int j = 0; j < ss.length; j++) ll[j] = Long.parseLong(ss[j]);
            return ll;
        }
    }
}


Measured memory_bytes: 22868
#include <bits/stdc++.h>
   
using namespace std;
#define ll long long
#define ld long double
#define pll pair<long long,long long>
#define vll vector<long long>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define deb(x) cout << #x << "=" << x << endl
#define F(i,a,b) for(ll i=a;i<=b;i++)
#define RF(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) F(i,0,n-1)cin>>a[i]
#define vi vector<int>
#define out(a,n) F(i,0,n-1)cout<<a[i]<<" ";cout<<endl
#define mod 1000000007
#define int long long
set < ll> primes;
 
int n,m;

bool isvalid(int x,int y)
{
    return (x>=0 && x<n && y>=0 && y<m);
}
int dx[]={0,0,1,-1,-1,1,1,-1};
int dy[]={1,-1,0,0,-1,1,-1,1};
void Sieve(ll n) 
{ 
    bool prime[n+1];
	for(ll i=0;i<n+1;++i)
		prime[i]=true;
    for (ll p=2;p*p<=n;++p) 
    {
        if (prime[p] == true) 
        {  
            for (ll i=2*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    }  
    for(ll p=2; p<=n; p++) 
       if (prime[p]) 
		primes.insert(p);  
}

ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
        return gcd(b % a, a); 
} 
ll powermod(ll x, ll y){
    if(y==0)
    return 1;
        
    if(y%2==0)
    return (powermod(x,y/2)*powermod(x,y/2))%mod;
    else
    return (((powermod(x,y/2)*powermod(x,y/2))%mod)*x)%mod;
}

 
 

int32_t main()
{
	ios::sync_with_stdio(false);
    cin.tie(NULL);
  
    int n,x,y;
    cin>>n>>x>>y;
    
    vector<int>v[n+1];
    for(int i=1;i<n;i++)
    {
        v[i].pb(i+1);
        v[i+1].pb(i);
    }
    v[x].pb(y);
    v[y].pb(x);
    
    
    
    set<pair<int,int>>s;
    
    int dist[n+1];
   
   
    
    int vis[n+1]={0};
    int ans[n+1]={0};
    
    for(int ind=1;ind<n;ind++){
    
     for(int i=0;i<=n;i++)dist[i]=INT_MAX;
    
     s.insert({0,ind});
     dist[ind]=0;
     memset(vis,0,sizeof vis);
     
    while(!s.empty())
    {
        auto p=*s.begin();
        s.erase(s.begin());
        int w=p.ff,x=p.ss;
        if(vis[x])continue;
        
        vis[x]=1;
        
        for(int i:v[x])
        {
            if(dist[i]>dist[x]+1)
            {
                dist[i]=dist[x]+1;
                s.insert({dist[i],i});
            }
        }
    }
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<dist[i]<<" ";
    // }
   
   for(int i=ind+1;i<=n;i++)
   {
       ans[dist[i]]++;
   }
   // cout<<dist[5]-dist[3]<<'\n';
    
    
    }
    for(int i=1;i<n;i++)
    {
        cout<<ans[i]<<'\n';
    }
    
    
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int pn,zn,nn;
long long k;
vector<int>pos,neg;
long long solve_neg() {
	long long l=-1e18,r=-1;
	while(l<=r) {
		long long m=l+r>>1,num=0;
		for(int i=0,j=0;i<pn;i++) {
			while(j<nn&&1ll*pos[i]*neg[j]<=m) j++;
			num+=j;
		}
		if(num<k) l=m+1;
		else r=m-1;
	}
	return l;
}
long long solve_pos() {
	long long l=1,r=1e18;
	k-=1ll*pn*nn+1ll*pn*zn+1ll*nn*zn+1ll*zn*(zn-1)/2;
	while(l<=r) {
		long long m=l+r>>1,num=0;
		for(int i=pn-1,j=0;i>=0;i--) {
			while(i>j&&1ll*pos[i]*pos[j]<=m) j++;
			num+=min(i,j);
		}
		for(int i=0,j=nn-1;i<nn;i++) {
			while(i<j&&1ll*neg[i]*neg[j]<=m) j--;
			num+=min(nn-i-1,nn-j-1);
		}
		if(num<k) l=m+1;
		else r=m-1;
	}
	return l;
}
int main() {
	int n;
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=0;i<n;i++) {
		int a;
		cin>>a;
		if(a>0) pos.push_back(a);
		else if(a==0) zn++;
		else neg.push_back(a);
	}
	pn=pos.size();
	nn=neg.size();
	sort(pos.begin(),pos.end());
	sort(neg.begin(),neg.end());
	if(1ll*pn*nn>=k) cout<<solve_neg()<<endl;
	else if(1ll*pn*nn+1ll*pn*zn+1ll*nn*zn+1ll*zn*(zn-1)/2>=k) cout<<0<<endl;
	else cout<<solve_pos()<<endl;
	return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h> 
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define maxnkp make_pair
#define fi first
#define se second
#define eps 1e-6
using namespace std;
typedef long long ll;
const int mods = 998244353;
const int maxn = 2e5+10;

ll n;

inline long long read() {
    long long tmp=0, fh=1; char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') fh=-1; c=getchar();}
    while (c>='0'&&c<='9') tmp=tmp*10+c-48, c=getchar();
    return tmp*fh;
}
ll dep,a,b,thr;

ll qpow(ll n,ll b){
	if(b<0) return 0;
	ll res =1;
	while(b){
		if(b&1) res=res*n;
		n=n*n;
		b>>=1;
	}
	return res;
} 

int main() {
	cin>>n;
	thr = floor(log10(n));
	if(thr==0){
		cout<<n<<endl;
		return 0;
	}
	ll ans = 0;
	ll x = n/qpow(10,thr);
	ll y = n%10;
	ll k = n-x*qpow(10,thr);
	k/=10;
	F(i,1,n){
		dep = floor(log10(i));
		a=i/(qpow(10,dep));
		b=i%10;
		if(b==0) continue;
		if(a==b) ans++;
		ans+=(qpow(10,thr-1)-1)/9;
		if(b<x){
			ans+=qpow(10,thr-1);
		}
		else if(b>x){
			continue;
		}
		else{
			ans+=k;
			if(a<=y) ans++;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 640
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    int i,j,k,n,m,x,y;
    scanf("%d%d",&n,&m);
    n--;
    m--;
    j=n/2;
    k=n-j;
    x=m/2;
    y=m-x;
    printf("%d\n",j*x+j*y+k*x+k*y);
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
using namespace std;

int main()
{
    int sum=0;
    string no;
    cin >> no;
    for(int i=0;i<no.length();i++){
        sum=sum+(int)no[i]-48;
    }
    if(sum%9==0)    cout << "Yes\n";
    else    cout << "No\n";
}

Measured memory_bytes: 3460
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ll n;
	cin >> n;
	vector<string>status = { "AC", "WA", "TLE", "RE" };
	vector<ll> cnt(4, 0);
	for (ll i = 0; i < n; ++i) {
		string s;
		cin >> s;
		for (ll j = 0; j < 4; ++j) {
			if (s == status[j])++cnt[j];
		}
	}
	for (ll i = 0; i < 4; ++i) {
		cout << status[i] << " x " << cnt[i] << endl;
	}
}


Measured memory_bytes: 3628
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
public class Main {
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		Deque<Integer> deq = new ArrayDeque<Integer>(N);
		
		for (int i = 0; i < N; i++) {
			if (i % 2 == N % 2) {
				deq.offerLast(sc.nextInt());
			} else {
				deq.offerFirst(sc.nextInt());
			}
		}
		
		deq.forEach(num -> {
			System.out.print(num + " ");
		});
	}
}

Measured memory_bytes: 98472
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        long[] A = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        int min = int.MaxValue;
        for(int i = 0; i < N; i++)
        {
            for (int j = 0; ; j++)
            {
                if (A[i] % 2 == 0)
                    A[i] >>= 1;
                else
                {
                    if (j < min)
                        min = j;
                    break;
                }
            }
        }
        Console.WriteLine(min);

    }
}


Measured memory_bytes: 13380
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

ll mpow(ll a, ll b){
	if(b==0){
		return 1;
	}else if(b%2==0){
		ll memo = mpow(a,b/2);
		return memo*memo%MOD;
	}else{
		return mpow(a,b-1) * a % MOD;
	}
}

ll gcd(ll a, ll b){
	if(b==0){
		return a;
	}else{
		return gcd(b, a%b);
	}
}

int main(void){
	/*priority_queue<int,vector<int>,greater<int>> sho, sho_del;
	priority_queue<int> ko;
	int n;
	cin>>n;
	int a;
	vector<int> A;
	rep(i,n){
		cin>>a;
		A.push_back(a);
	}

	rep(i,n){
		if(i == 0){
			sho.push(A[i]);
			ko.push(A[i]);
			continue;
		}
		if(ko.top() < A[i]){
			int max = ko.top();
			ko.pop();
			ko.push(A[i]);
			sho_del.push(max);
		}else if(ko.top() == A[i]){

		}
	}*/

	int n;
	cin>>n;
	int a;
	vector<int> A;
	rep(i,n){
		cin>>a;
		A.push_back(a);
	}

	vector<int> ko;
	rep(i,n){
		if(i == 0){
			ko.push_back(A[i]);
			continue;
		}
		if(ko[ko.size()-1] >= A[i]){
			ko.push_back(A[i]);
			continue;
		}
		int l = -1;
		int r = ko.size() - 1;
		while(r-l > 1){
			int chu = (l+r)/2;
			if(ko[chu] < A[i]){
				r = chu;
			}else{
				l = chu;
			}
		}
		ko[r] = A[i];
	}
	//cout<<ko[0]<<" "<<ko[1]<<endl;
	cout<<ko.size()<<endl;
	return 0;
}


Measured memory_bytes: 1528
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  string s; cin >> s;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '7') {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3128
import java.util.*;

public class Main{
    public static void main(String[] argc){
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();

        int num = Integer.parseInt(a + b);
        int sq = (int)Math.sqrt(num);

        if(sq*sq == num){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 21716
q = int(input())
Q = [[int(i) for i in input().split()] for j in range(q)]
p = 10 ** 6 + 3

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(p - 1, p)
invf = invfact(p - 1, f, p)

for x, d, n in Q:
    if d == 0:
        print(pow(x, n, p))
        continue
    
    inv_d = pow(d, p - 2, p)
    d_n = pow(d, n, p)
    x_over_d = x * inv_d % p

    if x_over_d == 0 or x_over_d + n - 1 >= p:
        print(0)
        continue

    print(d_n * f[x_over_d + n - 1] * invf[x_over_d - 1] % p)

Measured memory_bytes: 135092
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int x[400];

int main(){
    int n;
    cin >> n;
    ll ans = 1;
    REP(i,n){
        ll t;
        cin >> t;
        ans *= t / __gcd(t,ans);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll,ll> pll;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
#define MOD 1000000007
#define ARRAY_MAX 100005

const int INF = 1e9+7;



typedef struct union_find{

    vector<ll> pa;//親
    vector<ll> ra;//木の深さ
    vector<ll> siz;
    //n要素で初期化
    void init(ll n){
        pa.resize(n);
        ra.resize(n);
        siz.resize(n);
        for(ll i = 0;i < n;i++){
            pa[i] = i;/*各ノードに番号を振る,この時par[x]=xとなる時は木の根となる*/
            ra[i] = 0LL;/*各ノード自体の高さは0*/
            siz[i] = 1LL;
        }
    }
    //木の根を求める
    ll find(ll x){
        if(pa[x] == x){
            return x;/*根ならそのノードの番号を返す*/
        }else{
            return pa[x] = find(pa[x]);/*根でないならさらにノードの根を探す*/
        }
    }

    //xとyの属する集合を併合する
    void unite(ll x,ll y){
        x = find(x);//xの根の番号を探す
        y = find(y);//yの根の番号を探す
        if(x == y){//一致すればつながっている
            return;
        }
        pa[y] = x;
        siz[x] += siz[y];
        /*if(ra[x] < ra[y]){//xの高さが低いなら高いほうにつなぐ、そして高さは大きい方(y)になる
        }else{
            pa[y] = x;//yの高さが低いなら高いほうにつなぐ、そして高さは大きいほう(x)になる
            siz[x] += siz[y];
            if(ra[x] == ra[y]){//高さが一致しているなら併合の高さは1増える
                ra[x]++;
            }
        }*/
    }

    //xとyが同じ集合に属するか判定
    bool same(ll x,ll y){
        return find(x) == find(y);//同じ集合なら1、違うなら0が返る
    }
}UF;


int main(){

    ll n,m;
    cin >> n >> m;
    UF tree;
    tree.init(n);

    vector<ll> a(m),b(m);
    for(ll i = 0;i < m;i++){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
    vector<ll> ans;
    ans.push_back((n*(n-1))/2);

    ll tmp = (n*(n-1))/2;

    for(ll i = m-1;i >= 0;i--){

        /*****************/
        if (tree.same(a[i], b[i])) {
          ans.push_back(ans[int(ans.size()) - 1]);
          continue;
        }
        /*****************/

        if(tmp == 0){
            ans.push_back(0);
            continue;
        }
        ll diff1 = tree.siz[tree.find(a[i])];
        ll diff2 = tree.siz[tree.find(b[i])];
        tree.unite(a[i],b[i]);
        //a←bにつなげる
        if(diff1 == 1LL && diff2 == 1LL){
            //両方1個ずつしかない場合
            tmp--;
        }else{
            ll node = tree.siz[tree.find(a[i])];//つなげた後のノードの個数
            tmp = tmp - ((node*(node-1))/2  - (diff1*(diff1-1))/2 - (diff2*(diff2-1))/2 );
        }
        ans.push_back(tmp);
    }

    for(int i = ans.size()-2;i >= 0;i--){
        cout << ans[i] << endl;
    }


    return 0;
}


Measured memory_bytes: 6132
def f(N):
    l = 0
    NN = N
    while True:
        l += 1
        NN //= 10
        if NN < 10:
            break
    m = N / sum(map(int,list(str(N))))
    num = -1
    for d in range(0,l+2):
        x = (10 ** (d+1)) * int(N/(10**(d+1))+1) - 1
        sx = sum(map(int,list(str(x))))
        value = x/sx
        if value < m:
            m = value
            num = d
    if num == -1:
        return N
    else:
        return (10 ** (num+1)) * int(N/(10**(num+1))+1) - 1

K = int(input())

N = 1
ans = [1]

while len(ans) < K:
    N = f(N+1)
    ans.append(N)

for i in ans:
    print(i)


Measured memory_bytes: 3188
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
using namespace std;

int main(){
	//cin.tie(0);
	//ios::sync_with_stdio(false);
	int n,weight;
	cin>>n>>weight;
	vector<int> v(n),w(n);
	vector<vector<int>> a(weight+1);
	rep(i,weight+1){
		a[i].resize(n+1);
	}
	rep(i,n){
		cin>>v[i]>>w[i];
	}
	rep(i,weight+1){
		rep(j,n+1){
			if(i==0 || j==0){
				a[i][j]=0;
			}else{
				if(i-w[j-1]>=0){
					a[i][j]=max(a[i-w[j-1]][j-1]+v[j-1],a[i][j-1]);
				}else{
					a[i][j]=a[i][j-1];
				}
			}
		}
	}
	cout<<a[weight][n]<<endl;
}

Measured memory_bytes: 7060
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    long long int n;
    cin >> n;
    long long int t = floor(n / 3);
    long long int f = floor(n / 5);
    long long int ft = floor(n / 15);
    long long int res = n * (n + 1) / 2 - 3 * t * (t + 1) / 2 - 5 * f * (f + 1) / 2 + 15 * ft * (ft + 1) / 2;
    cout << res;
    return 0;
}

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

int main(){
    int em;
    cin >> em;

    vector<int> data(em);
    vector<int> num(em + 1);

    for (int i = 2; i <= em; i++){
         cin >> data.at(i-1);
    }

    for (int i = 2; i <= em; i++){
        num.at(data.at(i-1))++;
    }

    for (int i = 1; i <= em; i++){
        cout << num.at(i) << endl;
    }
}

Measured memory_bytes: 4844
n = int(input())
arr = input()

turn_cnt = []
east_cnt = 0
total_east = arr.count("E")

for i in range(n):
    left_turn = i - east_cnt
    s = arr[i]
    if s == "E":
        east_cnt += 1
    right_turn = total_east - east_cnt
    turn_cnt.append(left_turn + right_turn)

print(min(turn_cnt))


Measured memory_bytes: 15520
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define divup(a,b) ( ( (a) + ( (b) - 1u) ) / (b) ) // a/b の余り切り上げ
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
ll mod = 1000000007;


signed main(){
    ll n;
    cin>>n;
    vector<ll> a(n);
    vector<ll> b(n);
    vector<ll> c(n);
    rep(i,n) cin>>a[i];
    rep(i,n) cin>>b[i];
    rep(i,n) cin>>c[i];
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    sort(c.begin(),c.end());
    ll bm=0,am=0;
    vector<pair<ll,ll>> bp(n);
    vector<pair<ll,ll>> ap(n);
    ll j1=0,j2=0;
    rep(i,n){
        bp[i].first=b[i];
        auto kt =  upper_bound(c.begin(),c.end(),b[i]);
        bp[i].second = n-(kt-c.begin());
    }
    vector<ll> bs(n);
    rep(i,n){
        if(i==0) bs[n-1-i] = bp[n-1-i].second;
        else bs[n-1-i] = bp[n-1-i].second + bs[n-i];
    }
    rep(i,n){
        ap[i].first=a[i];
        auto kt =  upper_bound(b.begin(),b.end(),a[i]);
        ap[i].second = bs[kt-b.begin()];
        
    }
    ll s=0;
    rep(i,n){
        s += ap[i].second;
    }
    cout<<s<<endl;
}


Measured memory_bytes: 6528
S = input()

res = []
tmp = []
for s in S:
    if s == 'A' or s == 'C' or s == 'G' or s == 'T':
        tmp.append(s)
    else:
        res.append(len(tmp))
        tmp = []
res.append(len(tmp))
print(max(res))


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

int main() {
  char c;
  cin >> c;
  
  if(    ( c == 'a' )
      || ( c == 'e' )
      || ( c == 'i' )
      || ( c == 'o' )
      || ( c == 'u' )
    ){
    cout << "vowel" << endl;
  }
  else{
    cout << "consonant" << endl;
  }
}


Measured memory_bytes: 3600
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <complex>
#include <numeric>
#include <string.h>
#include <random>
#include <cmath>
#define rep(i,n) for (int i = 0; i < (int)n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<pl, ll> pll;
double PI = 3.141592653589793238462643383279;
const double EPS = 1e-9;
const ll MOD = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

template<typename T>
struct segtree{
    #define SEG_N (1<<17) //
    T dat[2*SEG_N];
    T unit;

    void init(T unit_) {
        unit = unit_;
        rep(i,2*SEG_N) dat[i] = unit;
    }

    T get(int k){
        k += SEG_N-1;
        T ret = dat[k];
        while(k > 0){
            k = (k-1)/2;
            ret = min(ret, dat[k]);
        }
        return ret;
    }

    void update(int a, int b, T v, int k = 0, int l = 0, int r = SEG_N) {
        if(r <= a || b <= l) return;
        if(a <= l && r <= b) {
            dat[k] = min(dat[k], v);
            return;
        }
        update(a, b, v, k*2+1, l, (l+r)/2);
        update(a, b, v, k*2+2, (l+r)/2, r);
        return;
    }
};

ll N, M;
pll E[100000];
segtree<ll> seg;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    rep(i,M) {
        cin >> E[i].first.first >> E[i].first.second >> E[i].second;
        E[i].first.first--;
        E[i].first.second--;
    }
    sort(E, E+M);
    seg.init(linf);
    seg.update(0, 1, 0);
    rep(i,M) {
        seg.update(E[i].first.first, E[i].first.second+1, seg.get(E[i].first.first)+E[i].second);
    }
    ll ans = seg.get(N-1);
    if (ans == linf) ans = -1;
    cout << ans << endl;
}

Measured memory_bytes: 4608
n, m = map(int, input().split())
a = [input() for i in range(n)]
b = [input() for i in range(m)]

for x in range(n-m+1):
    for y in range(n-m+1):
        for i in range(m):
            if b[i] != a[y+i][x:x+m]:
                break
        else:
            print('Yes')
            exit()
print('No')

Measured memory_bytes: 3064