akhauriyash/Code-Regression huggingface dataset:
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>
#define _USE_CMATH_DEFINES

const long INF = (1l << 30);
const long LINF = (1l << 60); //1.15*10^18

class UnionFind{
private:
    std::vector<long> parent;
    std::vector<long> rank;
    std::vector<long> m_size;

public:
    UnionFind(long n);
private:
    long root(long x);
public:
    bool same(long x, long y);
    void unite(long x, long y);
    long size(long x);
};

UnionFind::UnionFind(long n){
    parent = std::vector<long>(n);
    rank = std::vector<long>(n, 0);
    m_size = std::vector<long>(n, 1);
    for(long i = 0; i < n; i++){
        parent[i] = i;
    }
}

long UnionFind::root(long x){
    if(x < 0 || parent.size() <= x){
        printf("UnionFind::root range invalid!\n");
        return -1;
    }
    if(parent[x] == x){
        return x;
    }else{
        long res = root(parent[x]);
        parent[x] = res;
        return res;
    }
}

bool UnionFind::same(long x, long y){
    return root(x) == root(y);
}

void UnionFind::unite(long x, long y){
    x = root(x);
    y = root(y);
    if(x == y){
        return;
    }
    if(rank[x] < rank[y]){
        parent[x] = y;
        m_size[y] += m_size[x];
    }else{
        parent[y] = x;
        m_size[x] += m_size[y];
        if(rank[x] == rank[y]){
            rank[x]++;
        }
    }
}

long UnionFind::size(long x){
    return m_size[root(x)];
}


std::vector<long> solve(){
    long n, m, k;
    scanf("%ld%ld%ld", &n, &m, &k);
    UnionFind uf(n);
    std::vector<long> fr[n];
    for(int i = 0; i < m; i++){
        long a, b;
        scanf("%ld%ld", &a, &b);
        a--;
        b--;
        uf.unite(a, b);
        fr[a].push_back(b);
        fr[b].push_back(a);
    }
    for(int i = 0; i < k; i++){
        long c, d;
        scanf("%ld%ld", &c, &d);
        c--;
        d--;
        fr[c].push_back(d);
        fr[d].push_back(c);
    }
    std::vector<long> ans;
    for(long i = 0; i < n; i++){
        long res = uf.size(i);
        //printf("  %ld, %ld  ", i, res);
        for(int j = 0; j < fr[i].size(); j++){
            long nx = fr[i][j];
            if(uf.same(i, nx)){
                res--;
            }
        }
        //printf("%ld\n", res - uf.size(i));

        ans.push_back(res-1);
    }
    return ans;
}

int main(){
    std::vector<long> ans = solve();
    for(int i = 0; i < ans.size(); i++){
        printf("%ld ", ans[i]);
    }
    printf("\n");
}


Measured memory_bytes: 12536
def main():
    N = int(input())
    H = [int(_) for _ in input().split()]
    H.append(0)

    count = 0
    while True:
        continueCount = 0
        breakFrag = True
        for i in range(0, N+1):
            v = H[i]
            if v >= 1:
                count = count + 1
                H[i] = v - 1
                continueCount = continueCount + 1
                breakFrag = False
            else:
                if continueCount > 1:
                    count = count - (continueCount - 1)
                continueCount = 0
        if breakFrag:
            break
    print(count)





if __name__ == "__main__":
    main()

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

#define DEBUG (0)

int main(void)
{
  long long N,M = 0;
  long long result = 0;
  
  cin >> N >> M;

#if DEBUG
  cout << "N: " << N << " M: " << M << endl;
#endif

  result = (N*(N-1))/2 + (M*(M-1))/2;
  
  cout << result << endl;
  
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#define rep(i, s, g) for (i = s; i < g; i++)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1e18) + 1;

ll power(ll x, ll y)
{
    ll ans = 1;
    while (y)
    {
        if (y & 1)
            ans = (ans * x) % MOD;
        x = (x * x) % MOD;
        y >>= 1;
    }
    return ans;
}

ll comb(ll n, ll k)
{
    ll ans = 1;
    ll i;

    rep(i, 0, k)
    {
        ans *= n - i;
        ans %= MOD;
        ans *= power(i + 1, MOD - 2);
        ans %= MOD;
    }

    return ans;
}

int main(void)
{
    ll n, a, b;
    ll ans = 0;

    cin >> n >> a >> b;

    ans = power(2, n);

    ans = (ans - comb(n, a) - comb(n, b) - 1 + MOD * 3) % MOD;

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
  string s;
  cin>>n;
  cin>>s;
  int maxi=0;
  int x=0;
  for(int i=0;i<n;i++){
  	if(s[i]=='I')x+=1;
    else x-=1;
    //cout<<x<<' ';
    maxi = max(maxi,x);
  	}
  cout<<maxi;
}

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

using namespace std;

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

    int count = 0;
    for(int i = 1; i <= N; i += 2){
        int ans = 0;
        for(int j = 1; j <= N; j++){
            if(i % j == 0) ans++;
        }
        if(ans == 8) count++;
    }

    cout << count << endl;
}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
long long mod = 1000000000+7;

int main(){

	int x,y;
	cin>>x>>y;

	if(2*x<=y && y<=4*x && y%2==0)cout<<"Yes";
	else cout<<"No";
	cout<<endl;

	return 0;
}



Measured memory_bytes: 3632
#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>
#include <stack>
#include <set>
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()

const int N = (int)3e5;

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 lpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}
  else return lpow(a,b-1) * a;
}
ll gcd(ll a, ll b){
  if(b==0) return a;
  else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
  if(kaijo_memo.size() > n) return kaijo_memo[n];
  if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
  while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
  return kaijo_memo[n];
}
vector<ll> gyaku_kaijo_memo;
ll gyaku_kaijo(ll n){
  if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n];
  if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1);
  while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) % MOD);
  return gyaku_kaijo_memo[n];
}

ll nCr(ll n, ll r){
  if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く？不安.
  if(n < r || r < 0) return 0;
  ll ret = 1;
  ret *= kaijo(n); ret %= MOD;
  ret *= gyaku_kaijo(r); ret %= MOD;
  ret *= gyaku_kaijo(n-r); ret %= MOD;
  return ret;
}


int main(void){
  ll a,b;
  cin>>a>>b;
  if(a > 9 || b > 9){
    cout<<-1<<endl;
  }else{
    cout<<a*b<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std; 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string k;
    int d;
    cin>>k>>d;
    //dp[i][j][k] represents how many numbers with i digits have
    //their sum of digits modulo d equal to j and whether the 
    //bound on the ith digit is tight or not, if it's not tight
    //the current digit can take numbers from 0 to 9 else it 
    //can digits only from 0 to k[i]
    int dp[k.size()+1][d][2];  
    memset(dp,0,(k.size()+1)*d*sizeof(dp[0][0]));
    dp[0][0][0] = 1;
    dp[0][0][1] = 0;
    for(int i=1;i<=k.size();i++){
        for(int j=0;j<d;j++){
            for(int m=0;m<2;m++){
                for(int l=0;l<=9;l++){
                    if(l>(k[i-1]-'0')&&!m)break;
                    dp[i][(j+l)%d][m||(l<(k[i-1]-'0'))]=(dp[i][(j+l)%d][m||(l<(k[i-1]-'0'))]+dp[i-1][j][m])%mod;
                    
                }
            }
        }
    }
    int ans = (dp[k.size()][0][0]+dp[k.size()][0][1]-1+mod)%mod;
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 8064
s=input()
n=len(s)
ans=[0]*n
r=0
l=0
for i in range(n-1):
    if s[i]=='R':
        r+=1
    if s[i]=='L':
        l+=1
    if s[i]=='L' and s[i+1]=='R': 
        if (r+l)%2==0:
            ans[i-l+1]=(r+l)//2
            ans[i-l]=(r+l)//2
            r=0
            l=0
        else:
            ans[i-l+1]=(r+l)//2+l%2
            ans[i-l]=(r+l)//2+r%2
            r=0
            l=0
l+=1
if (r+l)%2==0:
    ans[n-l]=(r+l)//2
    ans[n-l-1]=(r+l)//2
else:
    ans[n-l]=(r+l)//2+l%2
    ans[n-l-1]=(r+l)//2+r%2

for i in range(n):
    print(ans[i], end=' ')


Measured memory_bytes: 4864
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
using ll = long long;
using namespace std;

int main(){
	ll n;
	cin>>n;
	ll a[110000];
	rep(i,0,n)cin>>a[i];
	sort(a,a+n);
	bool p=true;
	if(n%3==0){
		if(a[0]!=a[n/3-1] || a[n/3]!=a[2*n/3-1] || a[2*n/3]!=a[n-1])p=false;
		if(a[n/3]!=(a[0]^a[n-1])) p=false;
	}
	else if(a[n-1]!=0) p=false;
	if(p)cout<<"Yes";
	else cout<<"No";
}


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

int main(){
  //string s; cin>>s;
  int a,b,c; cin>>a>>b>>c;
  cout<<(a*(a-1)+b*(b-1))/2;
  //cout<<c<<" "<<a<<" "<<b<<endl;
  //cout<<(s[2]==s[3]&&s[4]==s[5]?"Yes":"No");

}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include <cstdlib>
#include <math.h>
#include<algorithm>
#include <map>
using namespace std;

int main(int argc,char** argv)
{

	int a[3];
	cin >> a[0] >>a[1] >> a[2];
	sort(a,a+3);
	cout << a[2]*10+a[0]+a[1]<<endl;
	return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

int N;
vector<ll> A;
vector<char> opt;

ll sum[100010];
int nxt[100010];
ll rsum[100010];

void chmax(ll &a,ll b){
    if(a<b) a=b;
}

int main(){
  cin>>N;
  A.resize(N);
  opt.resize(N);
  cin>>A[0];
  opt[0]='+';
  for(int i=1;i<N;i++){
      cin>>opt[i];
      cin>>A[i];
  }

  for(int i=0;i<=N;i++) nxt[i]=N;
  for(int i=N-1;i>=0;i--){
      nxt[i]=nxt[i+1];
      if(opt[i]=='-') nxt[i]=i;
  }

  for(int i=0;i<N;i++){
      if(i>0) sum[i]=sum[i-1];
      if(opt[i]=='+') sum[i]+=A[i];
      else sum[i]-=A[i];
  }

  for(int i=N-1;i>=0;i--){
      rsum[i]=rsum[i+1];
      rsum[i]+=A[i];
  }

  ll ans=sum[N-1];
  for(int i=0;i<N;i++){
      if(opt[i]=='+') continue;
      ll res=sum[i-1]+rsum[nxt[i+1]];
      ll minus=abs(rsum[i]-rsum[nxt[i+1]]);
      res-=minus;
      ans=max(ans,res);
  }

  cout<<ans<<endl;


  return 0;
}


Measured memory_bytes: 3072
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			int N=sc.nextInt();//にんじんの個数
			int K=sc.nextInt();//保持できるにんじんの数
			int k=0;//保持しているにんじんの数
			int T=sc.nextInt();//加速できる時間
			int U=sc.nextInt();//普通の速さ
			int V=sc.nextInt();//加速の速さ
			int boost=0;//加速で進む距離
			int L=sc.nextInt();//スタ－トからゴールまでの距離
			int[] D=new int[N+1];//にんじんが置かれている場所
			for(int i=1; i<=N; i++) {
				D[i]=sc.nextInt();
			}
			int index=1;
			double ans=0;
			for(int i=0; i<L; i++) {
				if(index<=N && i==D[index]) {
					if(k < K)	k++;
					else		boost=V*T;
					index++;
				}//とりあえず保持する
				if(boost==0 && k>0) {
					k--;
					boost=V*T;
				}//加速範囲でないときにんじん使う
				if(boost==0) {
					ans+=1.0/U;
				}//普通のとき
				else {
					ans+=1.0/V;
					boost--;
				}//加速のとき
				
			}
			System.out.println(ans);
			
			

		}
	}
}


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main()
{
  int N;
  string S;
  int K;
  cin >> N >> S >> K;
  char c = S[K - 1];
  REP(i, N)
  {
    if (S[i] != c)
      cout << "*";
    else
      cout << S[i];
  }
  cout << '\n';
  return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<char, ll> pcl;

#define m0(x) memset(x, 0, sizeof(x))
#define all(x) x.begin(), x.end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define asort(x) sort(all(x));
#define dsort(x, t) sort(x.begin(), x.end(), greater<t>());
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define MINS(m, s) m.insert(mp(s, 1));
#define MFIN(m, s) m.find(s) != m.end()
#define mp make_pair
#define pb push_back
#define INF (1 << 29)
const int mod = 1000000007;

int main() {
    ll a;
    long double b;
    cin >> a >> b;
    cout << (ll)((long double)a * b) << endl;
    return 0;
}

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

string S,T;

void solve(){
  if(S==T){
    cout<<"IDENTICAL"<<endl;
    return;
  }

  vector<string> a,b;
  vector<string> x,y;
  bool flag=false;
  string tmp;
  string rest="";
  for(int i=0;i<S.size();i++){
    if(S[i]=='"'){
      if(flag){
        flag=false;
        a.push_back(tmp);
      }else{
        flag=true;
        tmp="";
        x.push_back(rest);
        rest="";
      }
    }else if(flag) tmp+=S[i];
    else rest+=S[i];
  }
  if(rest!="") x.push_back(rest);

  flag=false;
  rest="";
  for(int i=0;i<T.size();i++){
    if(T[i]=='"'){
      if(flag){
        flag=false;
        b.push_back(tmp);
      }else{
        flag=true;
        tmp="";
        y.push_back(rest);
        rest="";
      }
    }else if(flag) tmp+=T[i];
    else rest+=T[i];
  }
  if(rest!="") y.push_back(rest);

  if(a.size()==b.size()){
    bool ok=true;
    for(int i=0;i<a.size();i++){
      if(a[i]==b[i]) continue;
      else{
        if(ok) ok=false;
        else{
          cout<<"DIFFERENT"<<endl;
          return;
        }
      }
    }

    bool close=false;
    if(x.size()==y.size()){
      close=true;
      for(int i=0;i<x.size();i++){
        if(x[i]==y[i]) continue;
        else close=false;
      }
    }

    if(close){
      cout<<"CLOSE"<<endl;
      return;
    }
  }

  cout<<"DIFFERENT"<<endl;
}

int main(){
  while(1){
    cin>>S;
    if(S==".") break;
    cin>>T;
    solve();
  }

  return 0;
}



Measured memory_bytes: 3216
#include<iostream>
#include<cstdio>
#include <stdio.h>
#include<algorithm>
#include<cstring>
#include <string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>
#include<bits/stdc++.h>
#include <set>
#define ll   long long
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#define inf 0x3f3f3f
#define pi 3.1415926535898
using namespace std;
const int N=2e5+10;
const int mod=1e9+7;
char s[20000];
int vis[35][35];
int n;
int main()
{
    cin>>n;
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        int len=strlen(s);
        int num=0,x=0,y=0;
        ll ans=0;
        int j=0;
        for(;j<len;j++)
        {
            if(s[j]=='.')
            {
                break;
            }
            ans=ans*10+s[j]-'0';
        }
        for(j++;j<len;j++)
        {
            ans=ans*10+s[j]-'0';
            num++;
        }
        while(ans%2==0)
        {
            ans=ans/2;
            x++;
        }
        while(ans%5==0)
        {
            ans=ans/5;
            y++;
        }
        x=min(x,18);
        y=min(y,18);
        for(int i=max(-9,num-x);i<=18;i++)
        {
            for(int j=max(-9,num-y);j<=18;j++)
            {
                sum+=vis[i+9][j+9];
            }
        }
        vis[x-num+9][y-num+9]++;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3648
import java.util.*;

class Main {
    public static void main(String... args) {
        int A = IN.nextInt();
		int B = IN.nextInt();
        puts((A * B) % 2 == 1 ? "Yes" : "No");
    }
    static final Scanner IN = new Scanner(System.in);
    static <T> void puts(T arg) { System.out.println(arg); }
}


Measured memory_bytes: 21716
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC073_C
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var A = new List<long>();
            for (int i = 0; i < N; i++)
            {
                A.Add(long.Parse(Console.ReadLine()));
            }
            A.Sort();
            var count = 1;
            var ansCount = 0;
            for (int i = 0; i < N; i++)
            {
                if (i == N - 2)
                {
                    if(A[i] == A[i + 1])
                    {
                        count++;
                        if (count % 2 == 0)
                        {
                            break;
                        }
                        else
                        {
                            ansCount++;
                            break;
                        }
                    }

                    if (count % 2 != 0)
                    {
                        ansCount += 2;
                        break;
                    }
                    else
                    {
                        ansCount++;
                        break;
                    }
                }

                if (A[i] != A[i + 1])
                {
                    if (count % 2 == 0)
                    {
                        count = 1;
                        continue;
                    }
                    else
                    {
                        count = 1;
                        ansCount++;
                        continue;
                    }
                }
                else
                {
                    count++;
                    continue;
                }
            }

            Console.WriteLine(ansCount);
        }
    }
}


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

  int N;
  int A[210];

int main() {
  cin >> N;
   for (int i = 0; i < N; ++i) cin >> A[i];
  
  int res = 0;
  
  while (true) {
    bool exist_odd = false;
    for (int i = 0; i < N; ++i) {
      if (A[i] % 2 != 0) exist_odd = true;
    }
    
    if (exist_odd) break;
    
    for (int i = 0; i < N; ++i) {
      A[i] /= 2;
    }
    ++res;
  }
  
  cout << res << endl;
}
  

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

using namespace std;
int n,h,tic = 0,p[1<<20];
const int mod = 1000000007;
long long ans,tick[1<<20],val[1<<20];
inline void AddTag(int now,long long bas) {
	bas *= now;
	bas %= mod;
	if (now >= (1<<h)) {
		now = p[now-(1<<h)+1]+(1<<h)-1;
		while (now > 1) {
			if (tick[now>>1] < tic)
				val[now>>1] = 0,tick[now>>1] = tic;
			bas *= now;
			bas %= mod;
			(val[now>>1] += bas) %= mod;
			now >>= 1;
		//	cout << now << " " << val[now] << endl;
		}
		return ;
	}
	AddTag(now<<1,bas);
	AddTag((now<<1)+1,bas);
}
inline void calcAns(int now,long long bas) {
	bas *= now;
	bas %= mod;
	if (now >= (1<<h)) {
		now = p[now-(1<<h)+1]+(1<<h)-1;
		long long tmp = bas*now%mod,caled = 0;
		while (now > 1) {
			//caled *= now;
			//caled %= mod;
			caled *= now;
			caled %= mod;
			now >>= 1;
			tmp *= now;
			tmp %= mod;
			if (tick[now] == tic) {
				//cout << now << " " << tmp << " " << val[now] << " " <<caled << endl;
				(ans += tmp*(val[now]-caled)) %= mod;
				caled = val[now];
			}
		}
		return ;
	}
	calcAns((now<<1),bas);
	calcAns((now<<1)+1,bas);
}
inline void dfs(int now) {
	if (now >= (1<<h))
		return ;
	tic++;
	AddTag(now<<1,now);
	calcAns((now<<1)+1,1);
	//cout << ans << endl;
	dfs(now<<1);
	dfs((now<<1)+1);
}
char s[1010];
char t[1010];
int main() {
	int  D,T,S;
	cin >> s >> t;
	int ls = strlen(s),lt = strlen(t);
	int ans = lt;
	for (int i = 0;i+lt-1 < ls; i++) {
		int cnt = 0;
		for (int j = 0;j < lt; j++) {
			if (s[i+j] == t[j])
				cnt++;
		}
		ans = min(ans,lt-cnt);
	}
	cout << ans << endl;
	return 0;
}
/*
5
6 14 15 7 12 16 5 4 11 9 3 10 8 2 13 1
4
1 2 3 4 5 6 7 8
*/

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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}


// single add, single read, range sum
struct BIT {
	size_t n;
	size_t n2;
	std::vector<int> data;
	BIT (size_t n) {
		this->n = n;
		for (n2 = 1; n2 < n; n2 *= 2);
		data.resize(n + 1);
	}
	inline void add(size_t index, int value) {
		for (int i = index + 1; (size_t) i <= n; i += i & -i) data[i] += value;
	}
	inline int sum(size_t r) const { // sum of [0, r]
		int res = 0;
		for (int i = r + 1; i; i -= i & -i) res += data[i];
		return res;
	}
};

size_t lower_bound(const BIT &tree, const std::vector<int> &a, int value) {
	/*
	std::cerr << "lower_bound call" << std::endl;
	for (auto i : a) std::cerr << i << " ";
	std::cerr << std::endl;
	for (size_t i = 1; i <= tree.n; i++)
		std::cerr << tree.data[i] << " ";
	std::cerr << std::endl;*/
	// do lower_bound in a[i] => a[i] + tree.sum(i) in O(logN) time
	if (a.back() + tree.sum(a.size() - 1) < value) return a.size();
	int l = 0;
	int r = tree.n2;
	int cur_sum = 0;
	while (r - l > 1) {
		size_t mid = l + (r - l) / 2;
		if (mid >= a.size()) {
			r = mid;
			continue;
		}
		int cur = a[mid - 1] + cur_sum + tree.data[mid];
		if (cur >= value) r = mid;
		else l = mid, cur_sum += tree.data[mid];
	}
	// std::cerr << "lower_bound result : " << l << std::endl;
	return l;
}


int main() {
	int n = ri(), m = ri(), v = ri(), p = ri();
	v -= p;
	v = std::max(v, 0);
	int a[n];
	for (auto &i : a) i = ri();
	std::sort(a, a + n);
	int l = -1;
	int r = n;
	while (r - l > 1) {
		// a[m] 
		int mid = l + (r - l) / 2;
		std::vector<int> b;
		for (int i = 0; i < n; i++) if (i != mid) b.push_back(a[i]);
		b.erase(b.end() - (p - 1), b.end());
		auto ok = [&] () {
			for (auto &i : b) {
				if (i > a[mid] + m) return false;
				i = std::min(a[mid] + m - i, m);
			}
			std::reverse(b.begin(), b.end());
			
			int64_t sum = 0;
			for (int i = 1; i < (int) b.size(); i++) {
				sum += b[i - 1];
				// std::max(0, v + i - n) * m
				if (sum < (int64_t) std::max<int64_t>(0, v + i - b.size()) * m)
					return false;
			}
			return true;
		};
		bool res = ok();
		if (res) r = mid;
		else l = mid;
	}
	std::cout << n - r << std::endl;
	
	return 0;
}




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

int main(){
  int N, K;
  cin >> N >> K;
  
  double sum = 0;
  
  for (int i = 1; i <= N; i++) {
    double head_num;
    double tmp;
    if (i < K) {
      head_num = ceil(log2((double) K / i));
      tmp = 1 / pow(2, head_num);
      sum += tmp;
    }
    else {
      sum += 1;
    }
  }
  
  cout << setprecision(10) << fixed << (double) sum / N << endl;
  
  return 0;
}

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

int main() {
  int n, m, x, ans = 100000000;
  cin >> n >> m >> x;

  vector<int> c(n);
  vector<vector<int> > a(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    cin >> c[i];
    for (int j = 0; j < m; j++) cin >> a[i][j];
  }

  for (int i = 0; i < (1 << n); i++) {
    bitset<12> b(i);
    int tmp = 0;
    vector<int> sum(m, -x);
    for (int j = 0; j < n; j++) {
      if (b.test(j)) {
        for (int k = 0; k < m; k++) {
          sum[k] += a[j][k];
        }
        tmp += c[j];
        bool ok = true;
        for (int k = 0; k < m; k++) {
          if (sum[k] < 0) ok = false;
        }
        if (ok) ans = min(ans, tmp);
      }
    }
  }
  if (ans == 100000000)
    cout << -1 << endl;
  else
    cout << ans << endl;
}


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

const int maxn = 201;

int t, n;
long long a[maxn];
char s[maxn];
vector < long long > cur;

signed main () {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 0; i < n; ++i)
			scanf("%lld", &a[i]);
		scanf("%s", &s);
		cur = {0};
		for (int i = n - 1; i >= 0; --i) {
			for (long long x: cur)
				a[i] = min(a[i], a[i] ^ x);
			if (a[i] && s[i] == '1') {
				cur.clear();
				break;
			}
			else if (a[i])
				cur.push_back(a[i]);
		}
		printf("%d\n", int(cur.empty()));
	}
}


Measured memory_bytes: 3784
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <cmath>

using namespace std;

typedef long long    ll;
typedef long double  ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

template <typename T> bool chmax(T &a, T& b) {if (a < b) {a = b; return true;} return false;}
template <typename T> bool chmin(T &a, T& b) {if (a > b) {a = b; return true;} return false;}
#define rep(i, n)      for (int i = 0; i < (int)(n); ++i)
#define rep3(i, m, n)  for (int i = (m); i < (int)(n); ++i)
#define rrep(i, n)     for (int i = (int)(n)-1; i >= 0; --i)
#define rrep3(i, m, n) for (int i = (int)(n)-1; i >= (m); --i)
#define all(x) x.begin(), x.end()
#define rall(x) x.end(), x.begin()
#define mset(x, val) memset(x, (val), sizeof(x))
#define cons(a, b) make_pair((a), (b))
#define car first
#define cdr second

#define endl '\n'
#define INF  0x7f7f7f7f7f7f7f7f
#define INFi 0x7f7f7f7f


ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll solve(ll A, ll B, ll C, ll X) {
  ll res = 0;
  rep(i, A+1)
    rep(j, B+1)
    rep(k, C+1)
    if (500*i + 100*j + 50*k == X) ++res;
  return res;
}

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

  ll A, B, C, X;
  cin >> A >> B >> C >> X;

  auto ans = solve(A, B, C, X);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3152
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//#define g cin.sync();cin.clear();getchar();
#define g ;

int main() {
	vector<int> list;
	int kk = 0;
	cin >> kk; g;

	for (int k = 0; k < kk; k++) {
		int a = 0;
		cin >> a; g;
		list.push_back(a);
	}

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

	int total = 0;
	int counter = 1;

	// 2 6 6
	for (int i = 0; i < list.size() - 1; i++) {
		if (list[i] == list[i + 1]) {
			++counter;
		}
		else {
			if (counter % 2 == 1)++total;

			counter = 1;
		}
	}
	if (counter % 2 == 1)++total;
	printf("%d", total);

	g;
	return 0;
}

Measured memory_bytes: 892
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <memory.h>
#include <stdlib.h>


int main(void)
{	
	int i,lon;
	char s[100000];
	scanf("%s",s);
	
	lon=strlen(s);
	
	if(lon%2!=0){
		for(i=0;i<lon;i+=2){
			printf("%c",s[i]);
		}
		printf("\n");
	} else{
		for(i=0;i<lon-1;i+=2){
			printf("%c",s[i]);
		}
		printf("\n");
	}
	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Globalization;
using System.Diagnostics;
using static System.Console;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().Solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    Random rnd = new Random();
    Stopwatch sw = new Stopwatch();
    readonly int[] dd = { 0, 1, 0, -1, 0 };
    readonly int mod = 1000000007;
    readonly string alfa = "abcdefghijklmnopqrstuvwxyz";


    void Solve()
    {
        int A = cin.Nextint;
        int B = cin.Nextint;
        int C = cin.Nextint;
        int cnt = 0;

        for (int i = 0; i < 10000000; i++)
        {
            if (A % 2 != 0 || B % 2 != 0 || C % 2 != 0)
            {
                WriteLine(cnt);
                return;
            }
            var a = A / 2;
            var b = B / 2;
            var c = C / 2;
            A = b + c;
            B = a + c;
            C = a + b;
            cnt++;
        }
        WriteLine(-1);
    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] Scan { get { return ReadLine().Split(); } }
    public int[] Scanint { get { return Array.ConvertAll(Scan, int.Parse); } }
    public long[] Scanlong { get { return Array.ConvertAll(Scan, long.Parse); } }
    public double[] Scandouble { get { return Array.ConvertAll(Scan, double.Parse); } }
    public string Next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return Next;
        }
    }
    public int Nextint { get { return int.Parse(Next); } }
    public long Nextlong { get { return long.Parse(Next); } }
    public double Nextdouble { get { return double.Parse(Next); } }
}

Measured memory_bytes: 13264
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;

// chmax, chmin
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 <typename T>
function<T(T, T)> op_max = [](T a, T b) -> T { return max(a, b); };
template <typename T>
function<T(T, T)> op_min = [](T a, T b) -> T { return min(a, b); };

template <typename T>
function<T(T, T)> op_sum = [](T a, T b) -> T { return a + b; };

namespace detail {
template <typename T, std::size_t NDIMS>
struct vector_builder {
  using type = std::vector<typename vector_builder<T, NDIMS - 1>::type>;

  static type make(std::vector<std::size_t> dims, const T& v = {}) {
    const auto vec = std::vector<T>(dims.empty() ? 0 : dims.back(), v);
    if (!dims.empty()) dims.pop_back();
    return vector_builder<std::vector<T>, NDIMS - 1>::make(dims, vec);
  }
};

template <typename T>
struct vector_builder<T, 1> {
  using type = std::vector<T>;

  static type make(std::vector<std::size_t> dims, const T& v = {}) {
    return type(dims.empty() ? 0 : dims.back(), v);
  }
};
}  // namespace detail

template <typename T, typename... SIZE_T>
auto exvector(const T& v, SIZE_T... dims) {
  static_assert(sizeof...(dims) != 0, "invalid dimension");
  std::vector<std::size_t> vec_dims{dims...};
  return detail::vector_builder<T, sizeof...(dims)>::make(vec_dims, v);
}

using namespace std;
//********************  dumps ************************//

template <typename T>
void dump(const T& data, vector<int>& iter) {
  cout << data << " ";
}
template <typename T>
void dump(const vector<T>& data, vector<int>& iter) {
  for (auto elem : data) dump(elem, iter);
  cout << endl;
}

template <typename T>
void dump(const vector<vector<T>>& data, vector<int>& iter) {
  for (auto elem : iter) {
    cout << "[" << elem << "]";
  }
  cout << endl;
  for (int i = 0; i < data.size(); i++) {
    iter.push_back(i);
    dump(data[i], iter);
    iter.pop_back();
  }
  cout << endl;
}

template <typename T>
void dump(const vector<T>& data, int dummy) {
  for (int i = 0; i < data.size(); i++) {
    cout << "[" << i << "] " << data[i] << endl;
  }
}
template <typename T>
void dump(const T& data) {  // T : data, U = base type val.
  vector<int> iter;
  dump(data, iter);
}
///////////////////////////////////////////////

int main() {
  int N;
  cin >> N;
  vector<LL> A(N);
  map<int, int> cnts;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    cnts[A[i]]++;
  }
  LL ans = 0;

  sort(A.begin(), A.end(), greater<LL>());
  for (auto a : A) {
    int k = 1;
    if (cnts[a] == 0) continue;
    while (a >= k) {
      k *= 2;
    }
    cnts[a]--;
    if (cnts[k - a] == 0) {
      cnts[a]++;
    } else {
      cnts[k - a]--;
      ans++;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 20608
function plus(main,arr,loop){
  console.log(arr)
  var persent = arr[0][0];
  var maxper = 0;
  var max = 0
  for(var i=0;arr[i][0]==persent;i++){
    arr[i]= arr[i].map(Number)
    console.log(arr[i])
    if(main[0]-0+arr[i][2]/main[1]-0+arr[i][1]>maxper)
    maxper = (main[0]-0+arr[i][2])/(main[1]-0+arr[i][1])//このへんまで書いた
    max = i;
    main = [main[0]-0+arr[i][2],main[1]-0+arr[i][1],maxper]
  }
  arr.splice(max,1);
  loop--;
  if(loop>0){
  plus(main,arr,loop);
  }else{
  return main;
  }
}
function arrsum(arr){
  var sum = 0;
  for(var i=0;i<arr.length;i++){
    sum+=arr[i];
  }
  return sum;
}
function gettop(arr){
  var persent = arr[0][0];
  var max =[0,0,0];
  for(var i=0;arr[i][0]==persent;i++){
    if(max[1]-0<arr[i][1]-0){
      max[2] = i;
      max[1] = arr[i][1];
      max[0] = arr[i][2];
    }
  }
  return max;
}
function Main(input) {
  input = input.trim()
  input = input.split("\n");
  var arr = input[1].split(" ").map(Number);
  var max = 0;
  var flag = 0;
  var col = [0,0,0,0,0,0,0,0];
  for(var i=0;i<input[0];i++){
    if(arr[i]<3200){
      col[Math.floor(arr[i]/400)] = 1;
      flag=1;
    }else{
      max++;
    }
  }
  if(flag==1){
    var low = arrsum(col);
    max+=low;
    console.log(low+" "+max);
  }else{
    console.log("1 "+max);
  }
}Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int c = sc.nextInt();
        boolean[][] str = new boolean[c][100001];
        boolean[][] end = new boolean[c][100001];
        int[] plus = new int[100001], sub = new int[1000001];
        for(int i = 0; i < n; i++){
            int x = sc.nextInt() - 1, y = sc.nextInt() - 1, z = sc.nextInt() - 1;
            str[z][x] = true;
            end[z][y] = true;
            plus[x]++;
            sub[y+1]++;
        }
        for(int i = 0; i < c; i++){
            for(int j = 0; j < 100001; j++){
                if(str[i][j] && end[i][j]){
                    plus[j]--;
                    sub[j+1]--;
                }
            }
        }
        int tmp = plus[0], ans = plus[0];
        for(int i = 1; i < 100001; i++){
            tmp = tmp + plus[i] - sub[i];
            ans = Math.max(ans, tmp);
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 105124
#define _USE_MATH_DEFINES
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <list>
#include <bitset>
 
using namespace std;
 
typedef pair<long long int, long long int> P;
 
long long int INF = 1e18;
long long int MOD = 1e9 + 7;
 
bitset<4100000> DP;
 
int main(){
	
	int N;
	cin >> N;
	
	int S = 0;
	
	DP[0] = 1;
	
	for(int i = 0; i < N; i++){
		int A;
		cin >> A;
		S += A;
		
		DP |= DP << A;
	}
	
	int mid = S / 2 + S % 2;
	
	for(int i = mid; i <= S; i++){
		if(DP[i]){
			cout << i << endl;
			break;
		}
	}
	
	return 0;
}

Measured memory_bytes: 1792
# coding: utf-8
# Your code here!
import numpy as np
import math

#R= int(input())
N, M = map(int, input().split())

A = map(int, input().split())
count = 0
for a in A:
    count += a
#print(count)
if N-count >= 0:
    print(N-count)
else:
    print('-1')

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

signed main() {
	int n;
	cin >> n;
	vector<int> h(n);
	for (auto &e : h) {
		cin >> e;
	}

	int cnt = 0;

	for (int i = 0; i < n; ++i) {
		bool flag = true;
		for (int j = 0; j < i; ++j) {
			if (h[i] < h[j]) flag = false;
		}
		if (flag) cnt++;
	}

	cout << cnt << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef vector<int> vec;
typedef vector<int64> vec64;
#define ss cout << " ";
#define nn cout << "\n";
#define ct(x) cout << x;
#define cts(x) cout << x << " ";
#define ctn(x) cout << x << "\n";
#define db(x) cout << "> " << #x << ": " << x << "\n";
#define qr queries();
void solve();
void YN(bool b){if (b){ctn("YES");}else{ctn ("NO");}};
void yn(bool b){if (b){ctn("Yes");}else{ctn ("No");}};
void queries(){int n;cin >> n;while (n--)solve();}
// // // // // // // // // // // // // // // // // // // // // // 
/*                  TEMPLATE - VANILLA                         */
// // // // // // // // // // // // // // // // // // // // // //
const int maxn = 200200;

void solve(){

    return;
}


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    if (n >= 400 && n <= 599){
        ctn(8);
    }
    else if (n >= 600 && n <= 799){
        ctn(7);
    } 
    else if (n >= 800 && n <= 999){
        ctn(6);
    } 
    else if (n >= 1000 && n <= 1199){
        ctn(5);
    } 
    else if (n >= 1200 && n <= 1399){
        ctn(4);
    } 
    else if (n >= 1400 && n <= 1599){
        ctn(3);
    } 
    else if (n >= 1600 && n <= 1799){
        ctn(2);
    } 
    else if (n >= 1800 && n <= 1999){
        ctn(1);
    } 
    return 0;
}

Measured memory_bytes: 3656
import java.util.*;
import java.math.*;
import java.awt.geom.*;
import java.io.*;
      
      
public class Main {
	static HashMap<String,Boolean> map;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		ArrayList<ArrayList<Data>> list = new ArrayList<ArrayList<Data>>();
		for(int i = 0; i < n; i++) {
			list.add(new ArrayList<Data>());
		}
		for(int i = 0; i < m; i++) {
			int a = sc.nextInt()-1;
			int b = sc.nextInt()-1;
			for(int j = a; j <= b; j++) {
				list.get(j).add(new Data(i,b));
			}
		}
		for(int i = 0; i < n; i++) {
			Collections.sort(list.get(i));
		}
		int count = 0;
		boolean[] ok = new boolean[n];
		for(int i = 0; i < n; i++) {
			if(ok[i]) continue;
			if(list.get(i).isEmpty()) {
				count = -1;
				break;
			}
			Data tmp = list.get(i).get(0);
			for(int j = i; j <= tmp.a; j++) {
				ok[j] = true;
			}
			count++;
		}
		System.out.println(count==-1?"Impossible":count);
		
		
		
		
		
	}
	static class Data implements Comparable<Data>{
		int id;
		int a;
		Data(int a, int b) {
			this.id = a;
			this.a = b; 
		}
		@Override
		public int compareTo(Data o) {
			return o.a - this.a;
		}
	}
 }

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

using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); ++i)
double const PI = 3.1415926535897932384626433;
using P = pair<int, int>;

int main() {
    int x, a, b;
    cin >> x >> a >> b;
    if (-a + b <= 0)
        cout << "delicious" << endl;
    else if (-a + b <= x)
        cout << "safe" << endl;
    else
        cout << "dangerous" << endl;
    return 0;
}

Measured memory_bytes: 3576
#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: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  
  int A=0, B=0, C=0;
  
  cin >> A >> B >> C;
  
  int sum = A+B;
  
  if(sum<C) {
    
    cout << "No" << endl;
    
  } else if(C<=sum) {
    
    cout << "Yes" << endl;
    
  }
  
  return 0;
  
}

Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <regex>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1000000007;

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//myfuncs
//素数判定
template<class T> inline T isPrime(T x) {
	bool ret = true;
	if (x < 2) {
		ret = false;
	}
	for (LL i = 2; i <= sqrt(x); i++) {
		if (x%i == 0) {
			ret = false;
		}
	}
	return ret;
}

//Union FInd
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//main code

int main(int argc, char const* argv[])
{
	int n,m;
	cin >> n >> m;
	vector<int> v[n+1];
	for (int i = 0; i < m; i++) {
		int a,b;
		cin >> a >> b;
		v[a].PB(b);
	}
	for (auto&& i: v[1]) {
		for (auto&& j: v[i]) {
			if (j==n) {
				cout << "POSSIBLE" << endl;
				return 0;
			}
		}
	}
	cout << "IMPOSSIBLE" << endl;
	return 0;
}


Measured memory_bytes: 8576
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 20000;
const int MAX_M = 20000;

/* typedef */

struct Pkt {
  int t, s, d;
  Pkt() {}
  Pkt(int _t, int _s, int _d): t(_t), s(_s), d(_d) {}
  bool operator<(const Pkt& p0) const { return t < p0.t; }
};

/* global variables */

int n, m;
Pkt pkts[MAX_M];
bool ifcts[MAX_N];

/* subroutines */

/* main */

int main() {
  for (;;) {
    cin >> n >> m;
    if (n == 0) break;

    for (int i = 0; i < m; i++) {
      cin >> pkts[i].t >> pkts[i].s >> pkts[i].d;
      pkts[i].s--;
      pkts[i].d--;
    }

    sort(pkts, pkts + m);
    
    memset(ifcts, false, sizeof(ifcts));
    ifcts[0] = true;

    int nifct = 1;
    
    for (int i = 0; i < m; i++) {
      Pkt& pi = pkts[i];
      if (ifcts[pi.s] && ! ifcts[pi.d]) {
	ifcts[pi.d] = true;
	nifct++;
      }
    }

    cout << nifct << endl;
  }

  return 0;
}

Measured memory_bytes: 1424
#include <cstdio>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

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; }

int A, P;

int main()
{
  scanf( "%d%d", &A, &P );

  printf( "%d\n", (3*A+P)/2 );

  return 0;
}

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

int main(){
  int N,K;
  string S,ori;

  cin >>N>>S>>K;

  ori = S;

  for(int i = 0; i < N; i++){
      if(S[i] != ori[K-1]){
          S[i] = '*';
      }
  }

  cout <<S<<endl;
  return 0;
  }

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int tmp = n % 100;
        int tmp2 = n / 100;
        int tmp3 = tmp2 * 5;
        
        if (tmp <= tmp3) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
long long qwq(long long x,long long y)
{
	long long n=x,m=y;
	while(y)
	{
		long long z=x%y;
		x=y;
		y=z;
	}
	return n*m/x;
}
long long solve(long long b,long long c,long long d)
{
	long long tmp1=b/c,tmp2=b/d,tmp3=b/(qwq(c,d));
	return tmp1+tmp2-tmp3;
}
int main()
{
	long long a,b,c,d; 
	cin>>a>>b>>c>>d;
	cout<<(b-a+1)-solve(b,c,d)+solve(a-1,c,d)<<endl;
	return 0;
}

Measured memory_bytes: 256
import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def main():
    A_1 = list(map(int,input().split()))
    A_2 = list(map(int,input().split()))
    A_3 = list(map(int,input().split()))

    A = [A_1,A_2,A_3]
    N = int(input())
    bingo = [[0] * 4 for _ in range(4)]
    for _ in range(N):
        b = int(input())

        for i in range(0,3):
            for j in range(0,3):
                if b == A[i][j]:
                    bingo[i][j] = 1


    for i in range(4):
        if bingo[i][0] == bingo[i][1] == bingo[i][2] == 1:
            print("Yes")
            exit()
        elif bingo[0][i] == bingo[1][i] == bingo[2][i] == 1:
            print("Yes")
            exit()


    if bingo[0][2] == bingo[1][1] == bingo[2][0] == 1:
        print("Yes")
        exit()
    elif bingo[0][0] == bingo[1][1] == bingo[2][2] == 1:
        print("Yes")
        exit()

    print("No")



if __name__ == "__main__":
  main()


Measured memory_bytes: 12476
#include<stdio.h>
int main(){
	int a,b,c,d=0,e,f;
	double ai, ue, o;
	scanf("%d%d%d",&a,&b,&c);
	for(;a<=b;a++){
		if(c%a==0){d++;
		}
	}
		printf("%d\n",d);
	return 0;
}

Measured memory_bytes: 596
import bisect
from itertools import accumulate
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
A_acc = [0]+list(accumulate(A))
L = A_acc[-1]
if L/2 in A_acc:
    print(0)
    exit()
ind = bisect.bisect_left(A_acc, L/2)
left = A_acc[ind-1]
left_anti = L-left
right = A_acc[ind]
right_anti = L - right

l = max(left, left_anti)-min(left, left_anti)
r = max(right, right_anti)-min(right, right_anti)
print(min(l, r))


Measured memory_bytes: 92880