akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define speed() cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false)
// #define exit(a, b) return cout << a, b;
 
// debugger
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#define debug(stuff) cout << #stuff << ": " << stuff <<endl
#define debugc(stuff) cout << #stuff << ": "; for(auto x: stuff) cout << x << " "; cout << endl;
// 
 
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define all(v) v.begin(), v.end() 
 
#define print(stuff) cout << stuff << endl
#define printc(stuff) for(auto x: stuff) cout << x << " "; cout << endl;
#define printPrec(stuff) cout << fixed << setprecision(15) << stuff << endl;
#define len length
#define ret0 return 0
#define ret return 
 
 
#define ll long long
#define ld long double
#define fi first
#define endl '\n'
#define se second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fill(ar, x) memset(ar, x, sizeof ar)
 
#define vl vector<ll> 
#define sl set<ll>
#define pll pair<ll, ll>
#define mll map<ll, ll> 
#define pq priority_queue<ll>
 
// typedef tree<ll,null_type,less<ll>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set;
 
#define inf (long long int) 1e18
#define eps 0.000001
#define mod 1000000007
#define mod1 998244353
#define MAXN (ll)1e6
#define N (1ll<<10)

ll ceil(ll a,ll b){
    return a/b+(a%b!=0);
}
void solve(){
    ll x;
    cin>>x;
    loop(i,0,MAXN){
        ll y = x - 100*i;
        if(ceil(y, 5) <= i && y >= 0){
            print(1);
            ret;
        }
    }
    print(0);
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
 
    ll t = 1;
    // cin>>t;
    while(t--){
        solve();
    }
        
   
}


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

using namespace std;
using LL = long long;

const int MOD = 1e9+7;

class Edge{
public:
    LL from,to, value;
    Edge(int f,int t, int c){
        from = f;
        to = t;
        value = c;
    }
};

std::vector<bool> Eratosthenes( int N )
{
    std::vector<bool> is_prime(N + 1, true);
    std::vector<int> P;
    for( int i = 2; i <= N; i++ )
    {
        if( is_prime[ i ] )
        {
            for( int j = 2 * i; j <= N; j += i )
            {
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    is_prime[0] = false;
    is_prime[1] = false;
    return is_prime;
}

int main(){
    vector<bool> is_prime = Eratosthenes(1e6);
    int a,b,n;
    while(cin >> a >> b >> n){
        if(a == 0)return 0;
        int cnt = 0;
        int ans;
        int i = 0;
        while(cnt < n){
            if(is_prime[i * b + a]){
                ans = i * b + a;
                cnt++;
            }
            i++;
        }
        cout<<ans<<endl;
    }
}



Measured memory_bytes: 3468
#include <bits/stdc++.h>
#define ll long long

using namespace std;

string s;
ll k;

int main() {
   // freopen("a.in", "r", stdin);
 //  freopen("a.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> s >> k;
    int i = 0;
    k --;
    while(i < s.size() && i < k && s[i] == '1')
        i ++;
    cout << s[i];
    return 0;
}


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

using namespace std;

const int maxn=1e2+5;

int p[maxn],dp[maxn][maxn],n;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>p[i-1]>>p[i];
    }
    for(int i=1;i<=n;i++){
        dp[i][i]=0;
    }
    for(int l=2;l<=n;l++){
        for(int i=1;i<=n-l+1;i++){
            int j=i+l-1;
            dp[i][j]=(1<<21);
            for(int k=i;k<=j-1;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]);
            }
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}
/*
6
30 35
35 15
15 5
5 10
10 20
20 25
*/



Measured memory_bytes: 3212
#include<stdio.h>
int dp[101][4][4];
int main(void)
{
	int N,K,A,B,S[101],i,j,k,l,x=0;
	scanf("%d%d",&N,&K);
	for(i=1;i<=N;i++){
		S[i]=0;
	}
	for(i=1;i<=K;i++){
		scanf("%d%d",&A,&B);
		S[A]=B;
	}
	for(i=0;i<=N;i++){
		for(j=1;j<=3;j++){
			for(k=1;k<=3;k++){
				dp[i][j][k]=0;
			}
		}
	}
	dp[0][1][2]=1;
	for(i=0;i<N;i++){
		if(S[i+1]!=0){
			for(j=1;j<=3;j++){
				for(k=1;k<=3;k++){
					if(dp[i][j][k]!=0){
						if(i==1||S[i+1]!=j||k!=j){
							dp[i+1][S[i+1]][j]+=dp[i][j][k];
							dp[i+1][S[i+1]][j]%=10000;
						}
					}
				}
			}
		}
		else{
			for(j=1;j<=3;j++){
				for(k=1;k<=3;k++){
					if(dp[i][j][k]!=0){
						for(l=1;l<=3;l++){
							if(i==1||j!=k||l!=k){
								dp[i+1][l][j]+=dp[i][j][k];
								dp[i+1][l][j]%=10000;
							}
						}
					}
				}
			}
		}
	}
	/*for(i=0;i<=N;i++){
		for(j=1;j<=3;j++){
			for(k=1;k<=3;k++){
				printf("%d ",dp[i][j][k]);
			}
			printf(" | ");
		}
		printf("\n");
	}*/
	for(i=1;i<=3;i++){
		for(j=1;j<=3;j++){
			x+=dp[N][i][j];
			x%=10000;
		}
	}
	printf("%d\n",x);
	return 0;
}

Measured memory_bytes: 2724
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
template<typename T=ll>inline T in(istream&is=cin){T ret;is>>ret;return ret;}
template<typename T>inline auto vec2(typename vector<T>::size_type h,typename vector<T>::size_type w,T v=T()){return vector<vector<T>>(h,vector<T>(w,v));}

int main()
{
    ll n=in(),k=in();
    n%=k;
    cout<<min(n,k-n)<<endl;
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;

static const int MOD = 1000000007;

long long fib[100];
vector<pair<long long, long long>> p[100];

int main() {
        fib[0] = fib[1] = 1;
        for (int k = 2; k <= 90; k ++) {
                fib[k] = fib[k - 1] + fib[k - 2];
                for (int j = 2; j <= k + 1; j ++) {
                        long long a = 1, b = 1;
                        for (int x = 2; x <= k; x ++) {
                                long long c = a + b;
                                if (x == j) c += a;
                                b = a;
                                a = c;
                        }
                        p[k].emplace_back(a, a + b);
                        p[k].emplace_back(a + b, a);
                }
        }
        int q;
        cin >> q;
        while (q --) {
                long long x, y;
                cin >> x >> y;
                if (x > y) swap(x, y);
                if ((x == 1) || (x == 2 && y == 2)) {
                        cout << 1 << ' ' << x * y % MOD << endl;
                        continue;
                }
                int k = 0;
                while (fib[k + 1] <= x && fib[k + 2] <= y) k ++;
                long long ans = 0;
                for (auto pp : p[k]) if (x >= pp.first && y >= pp.second) {
                        ans = (ans + 1 + (y - pp.second) / pp.first) % MOD;
                }
                cout << k << ' ' << ans << endl;
        }
        return 0;
}



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

#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=200005;
int n,m,l,r,ptl,ptr;
int a[maxn];
bool pre[maxn];

bool check(int x){
	rep(i,2*n+2)pre[i]=false;
	pre[0]=true;
	r=2*n+1;
	ptr=2*n;
	REP(i,n){
		while(ptr>=1&&a[i]+a[ptr]>x)ptr--;
		r=min(r,ptr+i-1);
		if(2*i<=r)pre[2*i]=true;
	}
	if(pre[2*n])return true;
	l=0;r=2*n+1;ptl=ptr=1;
	for(int i=2*n;i>=n+1;i--){
		while(ptl<=2*n&&a[ptl]+a[i]<m)ptl++;
		while(ptr<=2*n&&a[ptr]+a[i]<=m+x)ptr++;
		l=max(l,ptl-(2*n-i));
		r=min(r,ptr-1-(2*n-i));
		if(2*i-2*n-1>=l&&2*i-2*n-1<=r&&pre[2*i-2*n-2])return true;
	}
	return false;
}

int main(){
	scanf("%d%d",&n,&m);
	REP(i,2*n)scanf("%d",&a[i]);
	sort(a+1,a+1+2*n);
	int l=-1,r=m-1;
	while(r-l>1){
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid;
	}
	printf("%d\n",r);
	return 0;
}

Measured memory_bytes: 1280
#include <vector>
#include <iostream>
#include <algorithm>

int main(){
  int n;
  while(std::cin>>n&&n){
    std::vector<int> s(n);
    std::vector<int> news(n);
    for(int &x:s) std::cin>>x;
    int count;
    for(count=0;;++count){
      for(int i=0;i<n;++i)
        news[i]=std::count(s.cbegin(),s.cend(),s[i]);
      if(news==s)break;
      s=news;
    }
    std::cout<<count<<std::endl;
    for(int i=0;i<n;++i)
      std::cout<<news[i]<<((i!=n-1)?' ':'\n');
  }
  return 0;
}

Measured memory_bytes: 1216
#include<stdio.h>
#include<stdlib.h>
#define max 2000001


int main(){
    int  A[max+1],B[max+1];

   int C[max+ 1],n,i;
   
  scanf("%d",&n);

 

  for ( i = 0; i <= max; i++ ) C[i] = 0;

  for ( i = 0; i < n; i++) {
    
    scanf("%d", &A[i + 1]);
    
    C[A[i + 1]]++;
    
  }

  for ( i = 1; i <= max; i++ ) C[i] = C[i] + C[i - 1];

  for( i = 1; i <= n; i++){
    
    B[C[A[i]]] = A[i];
    
    C[A[i]]--;
    
  }

  for( i = 1; i<= n; i++ ){
    
    if ( i > 1)printf(" ");
    
    printf("%d", B[i]);
    
  }
  
  printf("\n");

  return 0;
}



Measured memory_bytes: 25132
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <map>

int main(void) {
	std::string s;

	std::cin >> s;

	int ans = 1000000;
	for (size_t i = 0; i < s.length() - 2; i++) {
		ans = std::min(ans, std::abs(753 - ((s[i] - '0') * 100 + (s[i + 1] - '0') * 10 + (s[i + 2] - '0'))));
	}

	std::cout << ans << std::endl;

	return 0;
}

Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

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

int main(){
  int N;
  cin >> N;
  vector<int> A(N + 1);
  for(int i = 1; i <= N; i++){
    cin >> A.at(i);
  }

  sort(A.begin(), A.end());

  vector<int> B(10000000);

  for(int i = 1; i <= N; i++){
    int x = A.at(i);
    for(int j = 1; j <= A.back() / A.at(i); j++){
      B.at(x * j)++;
    }
  }
  int ans = 0;
  for(auto i = 1; i <= N; i++){
    if(B.at(A.at(i)) == 1) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 43120
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define __builtin_popcount __builtin_popcountll

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 (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
    os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
    os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const map<S, T> &t) {
    os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


int T, n, m;

int main(int argc, char *argv[]){
    ios::sync_with_stdio(false);
    while(cin >> n >> m){
        vector<ll> dp(100001, (1ll << 60));
        dp[0] = 0;
        REP(i, n) {
            int w, v; cin >> w >> v;
            RREP(j, 100001 - v) {
                chmin(dp[j + v], dp[j] + w);
            }
        }
        RREP(j, 100001) {
            if (dp[j] <= m) {
                cout << j << endl;
                break;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define len(x) ((ll)(x).size())
#define debug(var) cout << "[" << #var << "]\n" << var << "\n"
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;
const double EPS = 1e-9;

template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1)
      s << ' ';
  }
  return s;
}

template <typename T>
ostream& operator<<(ostream& s, const vector<vector<T>>& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i];
    if (i != len - 1)
      cout << '\n';
  }
  return s;
}

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

__attribute__((constructor)) void initial() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

signed main() {
  int N;
  cin >> N;
  vector<int> x(N), y(N);
  rep(i, N) {
    cin >> x[i] >> y[i];
  }


  int ans = N;
  rep(i, N) {
    rep(j, N) {
      if (i == j)
        continue;
      int p = x[i] - x[j];
      int q = y[i] - y[j];
      int temp = N;
      rep(ii, N) {
        rep(jj, N) {
          if (ii == jj)
            continue;
          if (x[ii] - x[jj] == p && y[ii] - y[jj] == q)
            temp--;
        }
      }
      chmin(ans, temp);
    }
  }
  cout << ans << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a[3],i;
  for(i=0;i<3;i++)
  {
   cin>>a[i]; 
  }
  sort(a,a+3);
  
  if((a[0]==5)&&(a[1]==5)&&(a[2]==7))
  {
    
        cout<<"YES";
  }
  
  else
  {
    cout<<"NO";
  }
  return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef pair<string , int> s_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
//#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
const int64 INF = 1LL << 58;
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 (a>b) { a=b; return 1; } return 0; }
template<typename T> void remove(T & vector, unsigned int index){vector.erase(vector.begin() + index);}


int main() {
  int N, M, D;
  cin >> N >> M >> D;
  double ret = 1.0 * (N - D) * (M - 1) / N / N;
  if(D == 0) cout << fixed << setprecision(10) << ret << endl;
  else cout << fixed << setprecision(10) << ret * 2 << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<char>> s(h, vector<char>(w));
    rep(i, h) {
        string tmp_s;
        cin >> tmp_s;
        rep(j, w) {
            s[i][j] = tmp_s[j];
        }
    }
    int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
    int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
    rep(i, h) rep(j, w) {
        if ( s[i][j] == '.' ) {
            int cnt = 0;
            rep(k, 8) {
                int serch_y = i + dx[k];
                int serch_x = j + dy[k]; 
                if ( serch_y < 0 || serch_y >= h || serch_x >= w || serch_x < 0 ) continue;
                if ( s[serch_y][serch_x] == '#' ) ++cnt;
            }
            s[i][j] = (char)(cnt+'0');
        }
    }
    rep(i, h) {
        rep(j, w) cout << s[i][j];
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(x) begin(x),end(x)
using namespace std;
typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    if(n%2 == 0)
    {
        double nn = n/2;
        cout << nn/n<<endl;
    }
    else
    {
        double nn = (n/2)+1;
        cout << nn/n << endl;
    }
    return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
/***** MAIN *****/
signed main() {
  int n;
  cin >> n;
  int nums[n];
  map<int, int> mp;
  REP(i,n) {
    cin >> nums[i];
    ++mp[nums[i]];
  }
  int ans = 0;
  REPOBJ(itr, mp) {
    if(itr->second % 2 != 0) ++ans;
  }
  cout << ans;
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 5376
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    string S;
    cin >> S;
    if (S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) cout << "Bad" << endl;
    else cout << "Good" << endl;
}

Measured memory_bytes: 256
// ######      ###      #######    #######    ##     #     #####        ###     ##### //
// #     #    #   #          #        #       # #    #    #     #      #   #     ###  //
// #     #   #     #        #         #       #  #   #   #       #    #     #    ###  //
// ######   #########      #          #       #   #  #   #           #########    #   //
// #     #  #       #     #           #       #    # #   #    ####   #       #    #   //
// #     #  #       #    #            #       #     ##   #    #  #   #       #        //
// ######   #       #   #######    #######    #      #    #####  #   #       #    #   //

// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> ppl;
#define ain(a,n) for(ll i=0;i<(n);++i)  cin>>(a)[i];
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define loop(i,n) for(ll i=0;i<(n);++i)
#define FOR(i,a,b) for(ll i=(a);i<=(b);++i)
#define FORD(i,a,b) for(ll i=(a);i>=(b);--i)
#define cases ll T=0;cin>>T;while(T--)
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define END "\n"
#define pb push_back
#define mp make_pair
#define go(c,itr) for(auto itr=(c).begin(); itr!=(c).end(); ++itr)
// #define back(c,itr) for(auto itr=(c).rbegin(); itr!=(c).rend(); ++itr)
#define PI 3.14159265359
#define inf 9e18
#define MOD 1000000007
#define MODU 998244353
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define MAXN 1000005
#define BLOCK 555
const string alpha = "abcdefghijklmnopqrstuvwxyz";
const ll N = 200005;
const long double epsilon = 1e-9;
ll binexp(ll a, ll b, ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
ll modinvfermat(ll a, ll m)
{
    return binexp(a, m - 2, m);
}
void task(bool flag)
{
    if (flag)
        cout << "YES\n";
    else
        cout << "NO\n";
}
ll lcm(ll a, ll b)
{
    return ((1LL * a * b) / (__gcd(a, b)));
}

signed main() {
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
    fast
    string s, t;
    cin >> s >> t;
    ll n = s.length(), m = t.length();
    ll ans = inf;
    loop(i, n - m + 1)
    {
        ll curr = 0;
        for (ll j = 0; j < m; ++j)
        {
            if (s[i + j] != t[j])
                ++curr;
        }
        ans = min(ans, curr);
    }
    cout << ans << END;




// #ifndef ONLINE_JUDGE
//     cout << "\nTime Elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " sec\n";
// #endif
    return 0;
}

Measured memory_bytes: 3660
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <random>
#include <iomanip>
#include <unordered_set>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<pair<ll,ll> > vpll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef vector<vll> vvll;
typedef map<int,int> mii;
typedef set<int> si;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define arep(i,v) for(auto i : v)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define fi first
#define se second
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
template <class T> inline void dump(T &v){irep(i, v){cout<<*i<<((i==--v.end())?'\n':' ');}}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("yes"):fin("no");}
inline void Yn(const bool b){b?fin("Yes"):fin("No");}
inline void YN(const bool b){b?fin("YES"):fin("NO");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
constexpr ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
constexpr double EPS = 1e-9;

vector<ll> enum_div(ll n) {
    vector<ll> ret;
    for(ll i = 1 ; i*i <= n ; ++i){
        if(n%i == 0) {
            ret.push_back(i);
            if(i != 1 && i*i != n){
                ret.push_back(n/i);
            }
        }
    }
    return ret;
}

int main() {
    ll n;
    cin>>n;
    vll v=enum_div(n);
    ll ans=LLINF;
    rep(i,v.size()){
        chmin(ans,v[i]-1+n/v[i]-1);
    }
    fin(ans);
}








Measured memory_bytes: 384
//{{{
#include <bits/stdc++.h>
using namespace std;
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop,~))(__VA_ARGS__)
#define loop(n) rep2(_loop_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define repN(a) repX a
#define repX(a0,a1,a2,x,...) x
#define foreach(x,a) for(auto &x:a)
typedef long long ll;
const int MOD = 1e9+7;
//}}}

int main(){
	int a, b;
	cin >> a >> b;
	int ans = a - 1 + (a <= b);
	cout << (ans) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int a[3];
	
	for (int i = 0; i < 3; i++)
	{
		cin >> a[i];
	}

	sort(a, a + 3);
	cout << a[0] + a[1] << endl;

	return 0;
}

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

#define ll       long long
#define ull      unsigned ll
#define pii      pair<int, int>
#define pll      pair<ll, ll>
#define mp       make_pair
#define ff       first
#define ss       second
#define sz(x)    (int) x.size()
#define all(v)   v.begin(), v.end()

template <typename T> inline void smin(T &a, T b) {a = a < b ? a : b;}
template <typename T> inline void smax(T &a, T b) {a = a > b ? a : b;}

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl;}
template<typename T, typename... Args> void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ", ";
    err(++it, args...);
}

template <typename T> inline void Int(T &n) {
    n = 0; int f = 1; register int ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) n = (n << 3) + (n << 1) + ch - '0';
    n = n * f;
}

template <typename T, typename TT> inline void Int(T &n, TT &m) { Int(n); Int(m); }
template <typename T, typename TT, typename TTT> inline void Int(T &n, TT &m, TTT &l) { Int(n, m); Int(l); }

const int mod = (int) 1e9 + 7;

inline int add(int a, int b) {a += b; return a >= mod ? a - mod : a;}
inline int sub(int a, int b) {a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b) {return (ll) a * b % mod;}

const int inf = (int) 2e9 + 5;
const ll  Inf = (ll) 2e18 + 5;
const int N   = (int) 2e5 + 5;

const double pi = acos(-1.0);

std::vector<int> g[N];
int sz[N];

void dfs(int u, int p = -1) {
	sz[u] = 1;
	for(int v : g[u]) {
		if(p != v) {
			dfs(v, u);
			sz[u] += sz[v];
		}
	}
}

int solve() {
   int x; Int(x);
   double ans = 2.0 * pi * x;
   printf("%.10f\n", ans);
    return 0;
}

int main() {
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int test = 1, tc = 0;
    //Int(test);
    //cin >> test;
    while (test--) {
        //printf("Case %d: ", ++tc);
        solve();
    }
    return 0;
}


Measured memory_bytes: 8412
N = int(input())
h = list(map(int,input().split()))
dp = [0]*(N+1)
# dp[i+1]はindexでiの足場までのコストの最小値
# dp[N]は求める値
dp[2] = abs(h[1]-h[0])
for i in range(2,N):
    dp[i+1] = min(dp[i] + abs(h[i]-h[i-1]),dp[i-1] + abs(h[i]-h[i-2]))
print(dp[N])

Measured memory_bytes: 13980
import math
import itertools

def solve(N:int,M:int,Q:int,ABCD:list) -> int:
    ans = 0
    elements = [i for i in range(1,M+1)] # 数列Aにあり得る要素
    # 条件を満たす数列Aを作成
    for A in itertools.combinations_with_replacement(elements,N):
        total = 0 # 現在の数列の得点を格納する変数
        for a,b,c,d in ABCD:
            if(A[b-1] - A [a-1] == c): # 条件を満たしていたら得点を追加
                total+=d
        ans = max(ans,total) # 最高得点を更新
    return ans



def main():
    N ,M,Q = map(int,input().split())
    ABCD = []
    for _ in range(Q):
        ABCD.append(list(map(int,input().split())))
    # solve()
    print(solve(N,M,Q,ABCD))
if __name__ == '__main__':
   main()

Measured memory_bytes: 67204
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text.RegularExpressions;
namespace AtCoder_Core
{
    class Program
    {
        static void Main(string[] args)
        {
            var line1 = Console.ReadLine().Trim().Split(' ').Select(b => decimal.Parse(b)).ToArray();

            decimal N = line1[0];
            decimal K = line1[1];
            decimal ans = 0;
            decimal min = N;
            if (N % K == 0)
            {
                ans = 0;
            }

            else
            {
                N = N % K;
                while (true)
                {
                    if (Math.Abs(N - K) >= min)
                    {
                        ans = N;
                        break;
                    }

                    N = Math.Abs(N - K);
                    if (min > N)
                    {
                        min = N;
                    }

                }
            }

            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13396
#include <stdio.h>
#include <string.h>

int prime[1000000];

int main(void) {
	long i,j,n,count;

	while(scanf("%ld",&n)!=EOF) {
		count=0;
		memset(prime,0,sizeof(prime));
		for(i=2;i<=n;i++) {
			if(prime[i]) {
				continue;
			}
			for(j=i*2;j<=n;j+=i) {
				prime[j]=1;
			}
		}
		for(i=2;i<=n;i++) {
			count+=!prime[i];
		}
		printf("%ld\n",count);
	}
	return 0;
}

Measured memory_bytes: 4508
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <cmath>

int main(void){
    std::string a,b;
    std::cin >> a >> b;

    std::string c = a + b;

    int d = std::stoi(c);

    for(int i = 0; i <= 350; i++){
        if(d == i*i){
            std::cout << "Yes";
            return 0;
        }
    }

    std::cout << "No";
    return 0;
}



Measured memory_bytes: 256
def rren(): return list(map(int, input().split()))


a = ["1 3 5 7 8 10 12".split(), "4 6 9 11".split(), ["2"]]

x, y = rren()
flag = False
for i in range(3):
    if(str(x) in a[i] and str(y) in a[i]):
        flag = True

if(flag):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
int main(){
    int h,w;
    cin >> h >> w;
    char s[h][w];
    int i,j;
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            cin >> s[i][j];
        }
    }
    for(i=0;i<w+2;i++){
        cout << '#';
    }
    cout << endl;
    for(i=0;i<h;i++){
        cout << '#';
        for(j=0;j<w;j++){
            cout << s[i][j];
        }
        cout << '#' << endl;
    }
    for(i=0;i<w+2;i++){
        cout << '#';
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef __int128 lll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=200005;
ll s[N],a[N],ans,n,x;

int main(){
	read(n),read(x);
	rep(i,1,n){
		read(a[i]),s[i]=s[i-1]+a[i];
		ans+=5*a[i]+x;
	}
	rep(k,1,n-1){
		ll res=k*x;
		for(int p,i=n,c=1;i;i=p,c++){
			p=max(i-k,0);
			res+=max(5,c*2+1)*(s[i]-s[p]);
			if(res>ans) break;
		}
		ans=min(ans,res);
	}
	cout<<ans+1ll*n*x<<endl;
	return 0;
}

Measured memory_bytes: 3328
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	int c[3][3];
	int a[3], b[3];
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> c[i][j];
		}
	}
	a[0] = 0;
	for (int i = 0; i < 3; i++) {
		b[i] = c[0][i];
	}
	for (int i = 1; i < 3; i++) {
		a[i] = c[i][0] - b[0];
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (a[i] + b[j] != c[i][j]) {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int solvesunzo(int,int);
int n,Atw[50];

int main(){
  int q,i,Mtw;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&Atw[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&Mtw);
    if(solvesunzo(0,Mtw))printf("yes\n");
    else printf("no\n");
  }

  return 0;
}

int solvesunzo (int i, int m){
  if(m==0)return 1;
  if(i>=n)return 0;
  int res=solvesunzo(i+1,m)||solvesunzo(i+1,m-Atw[i]);
  return res;
}



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

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

	int* array = new int[n];
	for(int i=0; i<n; i++) {
		cin >> array[i];
	}

	int min = array[0], max = array[0];
	long sum = 0;
	for(int i=0; i<n; i++) {
		if(array[i] < min) min = array[i];
		if(array[i] > max) max = array[i];
		sum += array[i];
	}

	cout << min << " " << max << " " << sum << endl;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define td(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left sefude
#define right sefudermano
typedef long long ll;
typedef pair<int,int> pii;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
    if(b==0LL) return 1LL;
    if(b==1LL) return mod(a,m);
    ll k = mod(exp(a,b/2,m),m);
    if(b&1LL){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}



const int N = 500100;
const int M =1e9 + 7;
// long long?

ll fat[N],inv[N];
inline ll C(int n,int k){
  if(k>n)return 0;
  return mod(fat[n]*mod(inv[k]*inv[n-k],M),M);
}
inline ll P(int n,int k){
  if(k>n)return 0;
  return mod(fat[n] * inv[n-k],M);
}
void init(){
  fat[0] = inv[0] = 1;
  for(int i=1;i<N;i++){
    fat[i] = (1LL*fat[i-1]*i)%M;
  }
  inv[N-1] = exp(fat[N-1],M-2,M);
  for(int i=N-2;i>=0;i--){
    inv[i] = (inv[i+1]*(i+1))%M;
  }
}
int32_t main(){
  fastio;
  int n,m;
  init();
  cin >> n >> m;
  ll res=0;
  for(int k=0;k<=n;k++){
    ll cur = C(n,k) * P(m,k) %M * P(m-k,n-k) %M * P(m-k,n-k)  %M;

    if(k&1)res=mod(res - cur,M);
    else res = mod(res + cur,M);
  }
    cout << res << endl;
  // Math -> gcd it all
  // Did u check N=1? Did you switch N,M?
} 

Measured memory_bytes: 11428
#include <stdio.h>
int A[101],n,sum;
void bs(int key,int left,int right){
    if(left > right)
        return;
    int mid;
    mid=(left+right)/2;
    sum++;
    if(key == A[mid])
        return;
    if(key > A[mid])
        left=mid+1;
    else
        right=mid-1;
    bs(key,left,right);
}
int main(void){
    int n,k,i;
    for(;sum=0,scanf("%d",&n),n;){
        for(i=0;i<n;i++){
            scanf("%d",&A[i]);
        }
        scanf("%d",&k);
        bs(k,0,n-1);
        printf("%d\n",sum);
    }
    return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  ll a, b, k;
  cin >> a >> b >> k;

  rep(i, k) {
    if (i%2) {
      if (b%2) {
        b--;
      }
      a += b/2;
      b -= b/2;
    } else {
      if (a%2) {
        a--;
      }
      b += a/2;
      a -= a/2;
    }
  }
  cout << a << " " << b << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
    constexpr int INF = 2147483647;
    constexpr long long int INF_LL = 9223372036854775807;
    constexpr int MOD = 1000000007;
    using namespace std;
    typedef long long int ll;
    typedef unsigned long long int ull;
     
    bool isOK(ll k, vector<ll>& A, ll M) {
    	ll cnt = 0;
    	for (int i = A.size()-1; i >= 0; i--) {
    		auto itr = lower_bound(A.begin(), A.end(), k - A[i]);
    		cnt += (A.end() - itr);
    	}
    	return cnt >= M;
    }
    //最小の幸福度をもたらす握手のスコア
    ll calcMinScore(vector<ll> A, ll M, ll N) {
    	ll ng = A.back()+A.back()+1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    	ll ok = A[0]+A[0]-1; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
     
    	/* ok と ng のどちらが大きいかわからないことを考慮 */
    	while (abs(ok - ng) > 1) {
    		ll mid = (ok + ng) / 2;
     
    		if (isOK(mid, A, M)) ok = mid;
    		else ng = mid;
    	}
    	return ok;
    }
    int main() {
    	ll N, M;
    	cin >> N >> M;
    	vector<ll> A(N), S(N+1,0);
    	for (int i = 0; i < N; i++) {
    		cin >> A[i];
    	}
    	sort(A.begin(), A.end());
    	for (int i = 0; i < N; i++) {
    		S[i + 1] = S[i] + A[i];
    	}
     
    	ll ms = calcMinScore(A, M, N);
    	ll ans = 0;
    	ll tmp = 0;
    	for (int i = A.size() - 1; i >= 0; i--) {
    		ll cnt;
    		auto itr = upper_bound(A.begin(), A.end(), ms - A[i]);
    		cnt = (A.end() - itr);
    		tmp += cnt;
    		ans += A[i] * cnt + S[N]-S[N-cnt];
    	}
    	if(tmp<M)ans += (M-tmp)*ms;
    	cout << ans << endl;
    }

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

#define ll long long
#define d long double

#define scf(n) scanf("%d",&n)
#define lscf(n) scanf("%lld",&n)
#define dscf(n) scanf("%Lf",&n)
#define pri(n) printf("%d ",(int)n)
#define lpri(n) printf("%lld ",n)
#define dpri(n) printf("%Lf ",n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define dprin(n) printf("%Lf\n",n)

#define rep(i,ini,n) for(ll i=ini;i<(int)n;i++)
#define all(x) x.begin(),x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define bitcount(n) __builtin_popcount(n)
#define tc   int tt; scf(tt); while(tt--)
#define gcd __gcd
#define inf INT_MAX
#define ninf INT_MIN

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define PI 3.14159265358979323846264

const ll M =1e9+7;
const int N = 1e6+7;


int main()
{
    string s;
    cin>>s;
    ll sum=0;
    rep(i,0,s.size())
    {
        sum+=(s[i]-'0');
    }
    if(sum%9==0)
    printf("Yes");
    else
    {
        printf("No");
    }
    
return 0;
}

Measured memory_bytes: 3844
#include<bits/stdc++.h>
using namespace std;
vector<int> p;

struct UnionFind{
  vector<int> r,k,s;
  UnionFind(int n){
    for(int i=0; i<n; ++i) r.push_back(i);
    k=vector<int>(n,0);
    s=vector<int>(n,0);
  }
  int root(int a){
    if(r[a]==a) return a;
    return r[a]=root(r[a]);
  }
  void unite(int a,int b){
    a=root(a);
    b=root(b);
    if(a==b) return;
    if(k[a]<k[b]) swap(a,b);
    k[a]+=k[b];
    r[b]=a;
  }
  int made(int n){
    if(n--==0) return 0;
    return same(n,p[n])+made(n);
  }
  bool same(int a,int b){
    return root(a)==root(b);
  }
};
int main(void){
  int n,m; cin>>n>>m;
  p.resize(n);
  for(int i=0; i<n; ++i) {cin>>p[i]; --p[i];}
  UnionFind UF(n);
  for(int i=0; i<m; ++i){
    int a,b;
    cin>>a>>b;
    UF.unite(a-1,b-1);
  }
  cout<<UF.made(n)<<endl;
  return 0;
}

Measured memory_bytes: 4976
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		long start = System.currentTimeMillis();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		String[] flds = line.split(" ");
		int n = Integer.parseInt(flds[0]);
		int a = Integer.parseInt(flds[1]);
		int b = Integer.parseInt(flds[2]);
		int cnt = 0;
		for (int i=0; i<n; i++) {
			line = br.readLine();
			int t = Integer.parseInt(line);
			if (a <= t && t < b) {
				;
			} else {
				cnt++;
			}
		}
		System.out.println(cnt);
		long end = System.currentTimeMillis();
		//System.out.println((end-start) + "ms");
	}

}


Measured memory_bytes: 8148
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n;
	cin >> n;
	int ma = 0;
	vector<int> av(n);
	for (auto& a : av) {
		cin >> a;
		ma = max(a, ma);
	}

	vector<int> cv(ma + 1, 0);
	for (auto& a : av) {
		int b = a;
		while (b <= ma) {
			++cv[b];
			b += a;
		}
	}

	int ret = 0;
	for (auto& a : av) {
		if (cv[a] == 1) {
			++ret;
		}
	}
	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 7848
from operator import itemgetter
n,m=map(int,input().split())
x=[]
for i in range(m):
    a,b=map(int,input().split())
    x.append([a,b])
x=sorted(x, key=itemgetter(1))
en=x[0][1]
count=1
for i in range(1,m):
    if en<=x[i][0]:
        en=x[i][1]
        count+=1
print(count)

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

#define MOD 1000000007

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


template <class T>
ostream &operator<<(ostream &o, const vector<T>&obj) {
    o << "["; for (int i = 0; i < (int)obj.size(); ++i) o << (i > 0 ? ", " : "") << obj[i]; o << "]"; return o;
}
template <class T>
ostream &operator<<(ostream &o, const vector<vector<T>>&obj) {
    o << "[" << endl; for (int i = 0; i < (int)obj.size(); ++i) o << "  " << obj[i] << endl; o << "]"; return o;
}
template <class T, class U>
ostream &operator<<(ostream &o, const pair<T, U>&obj) {
    o << "(" << obj.first << ", " << obj.second << ")"; return o;
}
template <class T, class U>
ostream &operator<<(ostream &o, const map<T, U>&obj) {
    o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}
template <class T>
ostream &operator<<(ostream &o, const set<T>&obj) {
    o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}
template <class T>
ostream &operator<<(ostream &o, const multiset<T>&obj) {
    o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}
template <class T>
ostream &operator<<(ostream &o, const queue<T>&obj) {
    queue<T> obj_cp = obj;
    bool first = true;
    o << "{";
    while (!obj_cp.empty()) { o << (!first ? ", " : "") << obj_cp.front(); obj_cp.pop(); first = false; }
    o << "}"; return o;
}

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

int main(int argc, char const *argv[]) {
    string s, t;
    cin >> s >> t;
    
    int ans = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] != t[i]) {
            ans += 1;
        }
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 3844
n,a,b,k=map(int,input().split())
m=998244353
I=[0]*n
for i in range(n):
  I[i]=pow(i+1,m-2,m)
c=[0]*(n+1)
c[0]=1
for i in range(1,n+1):
  c[i]=(c[i-1]*(n-i+1)*I[i-1])%m
q=0
for i in range(n+1):
  j=(k-i*a)//b
  if (k-i*a)%b or j<0 or j>n:continue
  q=(q+c[i]*c[j])%m 
print(q%m)

Measured memory_bytes: 73796
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <utility>
#define mp make_pair
#define f first
#define s second
#define dm(x) cerr << #x << " = " << x << endl;
using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
typedef pair<long,long> pp;

pp dp[1001][1001];
int p[1001],w[1001];
int W, N;

pp operator+(pp a,pp b)
{
  pp ret(a.f+b.f, a.s+b.s);
  return ret;
}

//i番目以降でj以下の重さで価値を最大化。 {最大の価値, その時の重さ}
pp calc(int i,int j)
{
  pp ret;
  if(dp[i][j].f>=0) return dp[i][j];
  if(i==N) ret=mp(0,0);
  else if(j<w[i]) ret=calc(i+1,j);
  else{
    pp a=calc(i+1,j);
    pp b=calc(i+1,j-w[i]) + mp(p[i],w[i]);
    if(a.f>b.f) ret = a;
    else if(a.f<b.f) ret = b;
    else{
      if(a.s > b.s) ret = b;
      else ret = a;
    }
  } 
  return dp[i][j] = ret;
}

int main()
{
  int n=1;
  while(scanf("%d", &W),W){
    scanf("%d", &N);
    rep(i,N) scanf("%d, %d",p+i, w+i);
    // rep(i,N) printf("%d: p:%d w:%d\n",i , p[i], w[i]);
    rep(i,N+1) rep(j,W+1) {dp[i][j]=mp(-1,-1);}
    pp ret=calc(0,W);
    // printf(","); rep(j,W+1) printf("%d,",j); printf("\n");
    // rep(i,N+1){
    //   printf("%d,",i);
    //   rep(j,W+1)
    //     printf("%d,",calc(i,j).f);
    //   printf("\n");
    // }
    // rep(i,N+1){
    //   printf("%d,",i);
    //   rep(j,W+1)
    //     printf("%d,",calc(i,j).s);
    //   printf("\n");
    // }
    
    printf("Case %d:\n%ld\n%ld\n", n++, ret.f, ret.s);
  }
  return 0;
}

Measured memory_bytes: 8776
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N, A, B, P, a = 0, b = 0, c = 0;
	cin >> N >> A >> B;
	for (int i = 0; i < N; ++i) {
		cin >> P;
		if (A >= P) ++a;
		else if (B >= P) ++b;
		else ++c;
	}
	cout << min({ a, b, c });
}

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

using ll = int64_t;
#define int ll

#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(), x.end()

using pi = pair<int, int>;
using vi = vector<int>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  REP(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}

void printSpace() { printf(" "); }

void printEoln() { printf("\n"); }

void print(ll x, int suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1)
    printEoln();
  if (suc == 2)
    printSpace();
}

string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}

char *readCharArray() {
  static char buf[3341000];
  static int bufUsed = 0;
  char *ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}

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

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

template <class T> T Sq(const T &t) { return t * t; }

const int mod = 1e9 + 7;

const int maxWH = 2005;
array<array<int, maxWH>, maxWH> grid;

signed main() {
  int h, w;
  std::cin >> h >> w;
  REP(i, w + 2) { grid[0][i] = 1, grid[h + 1][i] = 1; }
  REP(i, h + 2) { grid[i][0] = 1, grid[i][w + 1] = 1; }
  FOR(y, 1, h + 1) {
    string s = readString();
    int x = 1;
    for (auto &c : s) {
      if (c == '#')
        grid[y][x++] = 1;
      else
        grid[y][x++] = 0;
    }
  }
  auto cntVertical = [](int y, int x) {
    int ret = 0;
    for (int i = y - 1; grid[i][x] == 0; i--)
      ret++;
    for (int i = y + 1; grid[i][x] == 0; i++)
      ret++;
    return ret;
  };
  auto cntHorizontal = [](int y, int x) {
    int ret = 0;
    for (int i = x - 1; grid[y][i] == 0; i--)
      ret++;
    for (int i = x + 1; grid[y][i] == 0; i++)
      ret++;
    return ret;
  };
  int ans = 0;
  int horCnt[h + 1], verCnt[w + 1];
  FOR(y, 1, h + 1) FOR(x, 1, w + 1) {
    if (grid[y][x] == 1)
      continue;
    int tmp = 1;
    // vertical
    if (grid[y - 1][x] == 1)
      verCnt[x] = cntVertical(y, x);
    tmp += verCnt[x];
    // horizontal
    if (grid[y][x - 1] == 1)
      horCnt[y] = cntHorizontal(y, x);
    tmp += horCnt[y];
    chmax(ans, tmp);
  }
  print(ans);
}


Measured memory_bytes: 35072