akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    long long a, b, c;
    scanf("%lld%lld%lld", &a, &b, &c);
    if (c - a - b <= 0)
    {
        printf("No");
        return 0;
    }
    long long l = 4 * a * b, r = a * a + b * b + c * c - 2 * a * c - 2 * b * c + 2 * a * b;
    if (l < r)
        printf("Yes");
    else
        printf("No");
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
/*template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;

#define LOCAL 0
#define dbg(x) cout << #x << " is " << x << "\n"
#define gll(x) scanf("%d",&x)
#define gll2(x,y) scanf("%d%d",&x,&y)
#define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define gllarr(arr,n) f(i,n) gll(arr[i]);
#define sz(x) ((int)x.size())
#define s(x) sort(x.begin(),x.end())
#define all(v) v.begin(),v.end()
#define rs(v) { s(v) ; r(v) ; }
#define r(v) {reverse(all(v));}
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e16;
const ld eps = 1e-12;
const ll N = (int)1e5 + 5;
const ll LOGN = 19;
const ld PI = 3.14159265358979323846;
inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (LOCAL) {
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
    }
    int a, b, c;
    cin>>a>>b>>c;
    int ans = min(c, b/a);
    cout<<ans;
    return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define br cout << endl;
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>;
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;}

// 0 false, 1 true 
// stringの数字をint型にしてアスキーコードになったら -48する
// 切り上げ　ceil(a)
// コンパイル　g++ -std=c++17 a.cpp

int main() {
    string s, t;
    cin >> s >> t;
    ll a, b;
    cin >> a >> b;
    string u;
    cin >> u;
    if(s == u){
        a--;
    }else{
        b--;
    }
    cout << a << " " << b << endl;
    

}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int n, a[100010];
    int odd = 0;

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i]%2) odd++;
    }

    if (odd%2) cout << "NO" << endl;
    else cout << "YES" << endl;
}


Measured memory_bytes: 640
#include <stdio.h>

int main(void)
{
    int X,A;

    scanf("%d",&X);
    scanf("%d",&A);

    if(A>X){
        printf("0\n");
    }else if(X>A){
        printf("10\n");
    }else if(X==A){
        printf("10\n");
    }

    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  int n,mx=-1,a;
  cin>>n;
  vector<int> A(n);
  for(int i=0;i<n;i++){
    cin>>A[i];
    if(mx<A[i]){
      mx=A[i];
      a=i;
    }
  }
  int b=0;
  if(b==a)b=1;
  for(int i=0;i<n;i++)
    if(abs(A[b]-mx/2)>abs(A[i]-mx/2))
      b=i;
  cout<<A[a]<<' '<<A[b]<<endl;
}

Measured memory_bytes: 4044
#include<bits/stdc++.h>
#define lint long long
#define st first
#define nd second

using namespace std;

//int t;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//cin>>t;
	//while(t--){}
	int a,b;
	int k;
	cin>>k>>a>>b;
	int nm = a+k-1;
	nm -= (nm%k);

	if(nm <=b)
		cout<<"OK\n";
	else 
		cout<<"NG\n";

	return 0;	
}



Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;

int main(){
	int N;
	cin >> N;
	int C[N];
	for(int i=0; i<N; i++) cin >> C[i];
	vector<int> B;
	B.push_back(C[0]);
	for(int i=1; i<N; i++){
		if(C[i] != C[i-1]) B.push_back(C[i]);
	}
	ll dp[B.size()];
	dp[0] = 1;
	int last[200001];
	for(int i=0; i<200001; i++) last[i] = -1;
	last[B[0]] = 0;
	for(int i=1; i<B.size(); i++){
		if(last[B[i]] == -1){
			dp[i] = dp[i-1];
		}else{
			dp[i] = (dp[i-1] + dp[last[B[i]]]) % mod;
		}
		last[B[i]] = i;
	}
	cout << dp[B.size()-1] << endl;
}

Measured memory_bytes: 4340
#include <bits/stdc++.h>
#include <string>
#include <math.h>
using namespace std;
int main()
{
  int a=0,b=0,c=0,d=0,e=0,f=0,i=0,j=0;
  int sum=0,num=0,count=0,ans=0,min=0,max=0;
  double d1=0,d2=0,d3=0,d4=0,d5=0,d6=0;
  int a1[999999],a2[999999],a3[999999];
  string s1,s2,s3;
  
  cin>>a>>b;
  
  if(500*a>=b){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}
  
  


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

int main(){
string s;
cin >> s;
int n = s.size();
int cur = 0;
int M = 0;
for (int i = 0;i < n;i++){
  if (s[i] == 'A' or s[i] == 'T' or s[i] == 'G' or s[i] == 'C'){
    cur += 1;
    M = max(M,cur);
  }
  else{
    cur = 0;
  }
}
cout << M << endl;
}

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

bool prime(int x){
  if(x<2) return false;
  int qx=sqrt(x);
  for(int i=2;i<=qx;i++){
    if(x%i==0)
      return false;
  }
  return true;
}

int main(){
  vector<int> A(100000,0);
  for(int i=3;i<100000;i++){
    if(i%2&&prime(i)&&prime((i+1)/2)){
      A[i]++;
    }
    A[i]+=A[i-1];
  }
  int Q,r,l;
  cin>>Q;
  for(int i=0;i<Q;i++){
    cin>>r>>l;
    cout<<A[l]-A[r-1]<<endl;
  }
}

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

struct UnionFind {
        std::vector<int> par; // par[i] represents parent number of i
        std::vector<int> sizes; // sizes[i] represent size of group 

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

    int root(int x) { // find parent of 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の根が同じ(=同じ木にある)時はそのまま
        if (sizes[rx] < sizes[ry]) std::swap(x, y);
        par[ry] = rx; //xとyの根が同じでない(=同じ木にない)時：yの根ryをxの根rx>につける
        sizes[rx] += sizes[ry];
    }

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

    int size(int x) {
            return sizes[root(x)];
    }
};


int main(int, char**) {
	int N, K, L;
	std::cin >> N >> K >> L;
	UnionFind road(N);
	UnionFind train(N);
	
	for (int i=0; i<K; i++) {
		int p, q;
		std::cin >> p >> q;
		p--;
		q--;
		road.unite(p, q);
	}

	for (int i=0; i<L; i++) {
		int r, s;
		std::cin >> r >> s;
		r--;
		s--;
		train.unite(r, s);
	}

	std::map<std::tuple<int, int>, int> con;
	for (int i=0; i<N; i++) {
		int r = road.root(i);
		int t = train.root(i);
		std::tuple<int, int> tu = std::make_tuple(r, t);
		if (con.count(tu) == 0) {
			con[tu] = 1;
		} else {
			con[tu] += 1;
		}
	}
	for (int i=0; i<N; i++) {
		int r = road.root(i);
                int t = train.root(i);
                std::tuple<int, int> tu = std::make_tuple(r, t);
		std::cout << con[tu] << " ";
	}
	std::cout << std::endl;



	return 0;
}


Measured memory_bytes: 15104
/*
  Warn - Don't change next line else you will get WA verdict. Online Judge is configured to give WA if next line is not present.
  Author - Aryan Choudhary (@aryanc403)
 
  const short DEBUG { 0 };
  #define debug(x) if (DEBUG) cout << #x << " = " << x << '\n'
*/

#pragma warning(disable:4996)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")

#include<iostream>
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
#define PI 3.1415926535897932384626433832795
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

//const lli [3] ={ 999119999L,1000000007L,1000992299L};
//const lli [3] ={ 97L,101L,103L};
//const lli  = chrono::high_resolution_clock::now().time_since_epoch().count();
clock_t time_p=clock();
void aryanc403()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}

class CMP
{
public:
    bool operator()(lli a , lli b) //For min priority_queue .
    {
        return ! ( a <= b );
    }
};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    map<lli,lli> ::iterator jt;
    jt=m.find(x);
    if(jt==m.end())         m.insert(mp(x,cnt));
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    map<lli,lli> ::iterator jt;
    jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli INF = 0xFFFFFFFFFFFFFFFL;
const lli mod = 1000000007L;

    lli T,n,i,j,k,l,r;
    mytype cnt,in;
    lli m;
    string s;
    vi a;
    vi :: iterator it;
    //priority_queue < lli , vector < lli > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
// cin>>T;while(T--)
{

    cin>>n;
    a.clear();a.reserve(n);
    
    fo(i,n)
    {
        cin>>in>>s;
        if(s=="JPY")
            cnt+=in;
        else
            cnt+=380000*in;
    }
    cout<<std::fixed<<std::setprecision(35)<<cnt<<endl;
}   aryanc403();
    return 0;
}

Measured memory_bytes: 256
using System;

namespace AtCoder.ABC081 {
    class B {
        static void Main() => Solve();

        static void Solve() {
#if DEBUG
            global::Common.ChangeStdIn();
#endif
            var N = int.Parse(Console.ReadLine());
            var ints = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

            var ans = 0;
            bool endFlg = false;
            while (!endFlg) {
                for (int i = 0; i < N; i++) {
                    if (ints[i] % 2 == 1) {
                        endFlg = true;
                        break;
                    } else {
                        ints[i] /= 2;
                    }
                }

                if (!endFlg) {
                    ans++;
                }
            }

            Console.WriteLine(ans);
        }
    }
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
    return string(1, val);
}

int main(){
    int N, K; cin >> N >> K;
    int R, S, P; cin >> R >> S >> P;
    string T; cin >> T;

    vector<char> cnt(N);

    ll res = 0;
    for(int i = 0; i < N; ++i) {
        ll ans = 0;
        if(T[i] == 'r') {
            cnt[i] = 'p';
            ans = P;
        } else if(T[i] == 's') {
            cnt[i] = 'r';
            ans = R;
        } else if(T[i] == 'p') {
            cnt[i] = 's';
            ans = S;
        }

        if(i >= K) {
            if(cnt[i - K] == cnt[i]) {
                cnt[i] = 'a';
                ans = 0;
            }
        }
        res += ans;
        // cout << cnt[i] << " " << cnt[i - K] << " " << (cnt[i] == cnt[i - K]) << " " << T[i] << endl;
        // cout << res << endl;
    }

    cout << res << endl;
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC151C
{
    class Program
    {
        static void Main(string[] args)
        {
            var NK = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            var N = NK[0];
            var K = NK[1];

            var submissions = new List<Tuple<string, string>>();
            for (var i = 0; i < K; i++)
            {
                var ps = Console.ReadLine().Split();
                submissions.Add(Tuple.Create(ps[0], ps[1]));
            }

            int ac = 0, wa = 0;
            foreach (var g in submissions.GroupBy(x => x.Item1))
            {
                if (g.Any(x => x.Item2 == "AC"))
                {
                    ac += 1;
                    wa += g.TakeWhile(x => x.Item2 == "WA").Count();
                }
            }
            Console.WriteLine(ac.ToString() + " " + wa.ToString());
        }
    }
}


Measured memory_bytes: 37540
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int min = n;
        int max = 0;
        for(int i = 0; i<n; i++){
            a[i] = sc.nextInt();
            if(a[i] < min) min = a[i];
            if(a[i] > max) max = a[i];
        }
        
        if(max - min >= 2){
            System.out.println("No");
            return;
        }

        if(min == max){
            if(min == 1 || min == n-1){
                System.out.println("Yes");
                return;
            }
            if(n / min >= 2){
                System.out.println("Yes");
                return;
            }
            System.out.println("No");
        }else{
            int nmin = 0;
            for(int ta: a){
                if(ta == min) nmin++;
            }
            int nmax = n - nmin;

            if(nmin < max && (max - nmin)*2 <= nmax){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
        
    }
}

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

int main() {
  ios::sync_with_stdio(false);
  int N, ans = 0;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i), ans = A.at(i) - ans;
  for (int i = 0; i < N; i++) cout << ans << "\n", ans = A.at(i) * 2 - ans;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using boost::irange;
using boost::sort;
using boost::adaptors::reversed;

int main() {
    string s;
    cin >> s;
    cout << (s == "ABC" ? "ARC" : "ABC") << endl;
}


Measured memory_bytes: 3624
Module Module144B

    Sub Main(ByVal args() As String)
        Dim N As Integer
        Dim i As Integer
        Dim mo As Integer
        Dim quot As Integer

        N = Console.ReadLine()

        For i = 1 To 9
            mo = N Mod i
            quot = Math.Truncate(N / i)

            If quot < 10 And mo = 0 Then
                Console.Write("Yes")
                Return
            End If
        Next

        Console.Write("No")
    End Sub

End Module


Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define se set<ll>
#define vec vector<ll>
#define inf 10000000000000000
bool mark[100005];
vec adj[100005];
ll counter;
vec cnt;
vector<string> forsubs;
ll ans=1000000000000;
ll n;

	

int main()
{    
 

	#ifdef APNA_IO
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
		    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 

ll n;
ll a[102];
ll s[102]={0};
cin>>n;

for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}

for(ll i=1;i<n;i++)
	{
		if(abs(s[n]-s[i]-s[i])<ans)
			ans=abs(s[n]-s[i]-s[i]);
		
	}	

	cout<<ans<<endl;	

}		





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

int main(){
	int x,y;
	cin>>x>>y;
	if(y%2!=0){
		cout<<"No"<<endl;
	}
	else if(y>=x*2&&y<=x*4){
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
}

Measured memory_bytes: 3604
#include<stdio.h>

int main(void)
{
	
	int i, f=0;

	char a[4];
	char b[4];


	scanf("%s",a);
	scanf("%s",b);
	for (i = 0;i < 3;i++)
	{
		if (a[i] == b[i])
			f++;

	}


	printf("%d", f);

	return 0;
}

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

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

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 998244353;

const int CASES = 3;

void solve() {
    ll N; cin >> N;
    vector<ll> D(N);
    vector<ll> vec(N);
    for(int i = 0; i < N; ++i){
        cin >> D[i];
        ++vec[D[i]];
    }
    if(D[0] != 0){
        cout << 0 << endl;
        return;
    }

    ll ans = 1;
    if(vec[0] != 1){
        cout << 0 << endl;
        return;
    }
    for(ll i = 1; i < N; ++i){
        for(int j = 0; j < vec[i]; ++j){
            ans *= vec[i-1];
            ans %= MOD;
        }
        ans %= MOD;
    }

    cout << ans << endl;

    return ;
}

int main() {
    #ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
    #else

    solve();

    #endif
    return 0;
}



Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const int INF = 1 << 28;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

int main() {
    string s;
    cin >> s;
    if (s.size() < 3) {
        cout << 0 << endl;
        return 0;
    }
    ll pos = 0;
    ll ret = 0;
    bool apart = true;
    ll numA = 0;
    ll numBC = 0;
    while (pos < s.size()) {
        if (apart) {
            if (s[pos] == 'A') {
                numA++;
                pos++;
            } else {
                if (numA == 0)
                    pos++;
                else
                    apart = false;
            }
        } else {
            if (s.substr(pos, 2) == "BC") {
                numBC++;
                pos += 2;
            } else {
                if (numBC == 0) {
                    numA = 0;
                    pos++;
                    apart = true;
                    // } else if (numBC == 1) {
                    //     ret += numA * numBC;
                    //     numBC = 0;
                    //     apart = true;
                } else {
                    ret += numA * numBC;
                    // numA = 1;
                    numBC = 0;
                    apart = true;
                }
            }
        }
    }
    ret += numA * numBC;
    cout << ret << "\n";

    return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<int> a(N);

    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    int i = 1, count = 0;
    bool ispossible = false;
    while (true) {
        //cout << "i = " << i << ", a[i-1] = " << a[i-1] << endl;
        if (a[i-1] == 0) {
            break;
        } else if (i == 2) {
            ispossible = true;
            break;
        }
        int prev_i = i;
        i = a[i-1];
        a[prev_i-1] = 0;
        count++;
    }

    if (ispossible) {
        cout << count << endl;
    } else {
        cout << "-1" << endl;
    }

    return 0;
}

Measured memory_bytes: 3760
def prime_numbers(n):
    cnds = [True] * n
    for x in xrange(2, int(n**0.5 + 1)):
        if cnds[x]:
            for m in xrange(2*x, n, x):
                cnds[m] = False
    return [i for i in xrange(2, n) if cnds[i]]

def is_prime(n):
    return all(n % m for m in primes if m < n)

primes = prime_numbers(10**4)
N = input()
print sum(is_prime(input()) for i in range(N))

Measured memory_bytes: 6788
from collections import deque


def dfs(G, C, id, color):
    S = deque()
    S.append(id)
    C[id] = color

    while S:
        u = S.pop()
        #S = S[:-1]  # pop
        for i in range(len(G[u])):
            v = G[u][i]
            if C[v] == -1:
                C[v] = color
                S.append(v)


if __name__ == '__main__':
    # ??????????????\???
    num_of_users, num_of_links = [int(x) for x in input().split(' ')]
    links = []
    for _ in range(num_of_links):
        links.append(list(map(int, input().split(' '))))
    num_of_queries = int(input())
    queries = []
    for _ in range(num_of_queries):
        queries.append(list(map(int, input().split(' '))))

    # ???????????????
    G = [[] for _ in range(100000)]
    C = [-1] * 100000
    for f, t in links:
        G[f].append(t)
        G[t].append(f)

    color = 1
    for id in range(num_of_users):
        if C[id] == -1:
            dfs(G, C, id, color)
        color += 1

    # ???????????????
    for x, y in queries:
        if C[x] == C[y]:
            print('yes')
        else:
            print('no')

Measured memory_bytes: 44076
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>  // std::greater<T>()

using namespace std;

// macro
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (int i=0; i < (int)(n); i++)  // 0 ~ n-1
#define REPN(i, n) for (int i=1; i <= (int)(n); i++)  // 1 ~ n
#define DESCEND greater<int>()  // sort 降順
#define UNIQUE(vec) (vec).erase(unique(ALL((vec))), (vec).end());  // 必ずsortを行なってから

// func declaration
template <class T> void printVec(vector<T>);
template <class T> void calcVec(vector<T>&, int, char);
bool checkMultiple(vector<int>&, int);

// const
const int INF = 10000000;

/*MEMO
辞書順
abc < abcd, atcoder < atlas
*/

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

    int count = 0;
    REP(i, N) {
        int l_i, r_i;
        cin >> l_i >> r_i;
        count += r_i - l_i + 1;
    }
    cout << count << endl;
    
    return 0;
}


// function
template <class T> void printVec(vector<T> vec) {
    // 1要素ずつ、空白・改行なしで出力
    REP(i, vec.size()) {
        cout << vec.at(i);
    }
    cout << endl;
}

template <class T> void calcVec(vector<T> &vec, int num, char ch) {
    // vec全体への演算
    if (ch == '+') {
        REP(i, vec.size()) {
            vec.at(i) += num;
        }
    } else if (ch == '-') {
        REP(i, vec.size()) {
            vec.at(i) -= num;
        }
    } else if (ch == '*') {
        REP(i, vec.size()) {
            vec.at(i) *= num;
        }
    } else if (ch == '/'){
        REP(i, vec.size()) {
            vec.at(i) /= num;
        }
    } else if (ch == '%') {
        REP(i, vec.size()) {
            vec.at(i) %= num;
        }
    }
}

bool checkMultiple(vector<int> &vec, int num) {
    // vecの中身が、numの倍数かどうかのチェック
    int count = 0;
    REP(i, vec.size()) {
        if (vec.at(i)%num != 0) count++;
    }
    return (count == 0);
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#define REP(i,n) for (int i=0;i<(n);++i)
using namespace std;

int main(){
    int w, a, b;
    cin >> w >> a >> b;

    if(b > a + w) cout << b - (a + w) << endl;
    else if(a > b + w) cout << a - (b + w) << endl;
    else cout << 0 << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define re register
#define ull unsigned ll
using namespace std;
inline int read(){
	int s=0,t=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*t;
}
const int N=17;
const int M=(1<<16)+5;
const int P=1e9+7;
int n,m,U,Ans;
int A[N],sz[M],fac[M],inv[M],dp[N][M];
void Mod(int &x,int y){(x+=y)>=P?x-=P:0;}
bool cmp(int x,int y){return x>y;}
int ksm(int x,int k){
	int res=1;
	while(k){
		if(k&1)res=1ll*res*x%P;
		x=1ll*x*x%P,k>>=1;
	}return res;
}
void Pre(int n){
	for(int S=1;S<=n;S++)sz[S]=sz[S-(S&-S)]+1;
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%P;
	inv[n]=ksm(fac[n],P-2);for(int i=n;i>=1;i--)inv[i-1]=1ll*inv[i]*i%P;
}
int C(int n,int m){return (n<m||m<0)?0:1ll*fac[n]*inv[m]%P*inv[n-m]%P;}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read(),U=(1<<n),Pre(U);
	for(int i=1;i<=m;i++)A[i]=read();
	sort(A+1,A+m+1,cmp),dp[0][0]=1;
	for(int i=1;i<=m;i++)
	for(int S=0;S<U;S++)if(dp[i-1][S]){
		int Num=U-A[i]+1-S;
		Mod(dp[i][S],dp[i-1][S]);
		for(int j=0;j<n;j++)if(!(S>>j&1))
		Mod(dp[i][S|(1<<j)],1ll*dp[i-1][S]*C(Num-1,(1<<j)-1)%P*fac[1<<j]%P);
	}
	for(int S=0;S<U;S++)Mod(Ans,1ll*(sz[S]&1?P-1:1)*dp[m][S]%P*fac[U-S-1]%P);
	printf("%d",1ll*Ans*U%P);
	return 0;
}

Measured memory_bytes: 7996
#pragma GCC optimize "-O3"
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define NumberOfOnes __builtin_popcount
#define LSOne(S) (S & (-S))
#define ll long long
#define two pair<int,int>
#define twoll pair<ll,ll>
#define four pair<two,two>
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define y1 y1922
#define INF 1000000000000000000
#define P 1000000007
#define lmax 1000000000
#define nn 1000003
#define ff first.first
#define fs first.second
#define sf second.first
#define ss second.second
#define f first
#define s second
#define vi vector<int>
#define vll vector<ll>
#define vtwo vector<two>
#define ALL(container) (container).begin(), (container).end()
#define sz(container) (int)(container.size())
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define mid(a,b) (a+b>>1)
#define minN 0
#define maxN 10000000
#define na(x) ((x)<P?(x):(x)-P)
#define ab(a) (-(a)<(a)?(a):-(a))
#define FAST std::ios::sync_with_stdio(false)
#define xRand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rnd rng
#define IT iterator
typedef
tree<
  int,// aq pair<int,int> shegidzlia
  null_type,
  less/*_equal*/<int>,// aqac
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;
// '_equal' mashin ginda roca multiset gchirdeba
template<class key, class value,class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
ordered_map<int, int> my_map;
inline int rin(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
inline int bin(){
	int x=0;char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x;
}
ll m=1000000000;
ll n,s,k;
int main(){FAST;xRand;
cin>>n>>k>>s;
if(s==m){
	for(int i=1;i<=k;i++){
		cout<<m<<" ";
	}
	for(int i=k+1;i<=n;i++){
		cout<<1<<" ";
	}
	cout<<endl;
	return 0;
}
if(k==0){
	while(n--){
		cout<<m<<" ";
	}
	cout<<endl;
	return 0;
}
for(int i=1;i<=n;i++){
	if(i<=k){
		cout<<s<<" ";
	}else{
		cout<<m<<" ";
	}
}
cout<<endl;
	// you should actually read the stuff at the bottom
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?), slow multiset operations
	* do smth instead of nothing and stay organized
	* unordered_map, hash_map, scanf, calculate answer instead of ans*K
*/
/*


                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
                 *   *   * *   *
                  *   *   *   *
                   *   * *   *
                     *  *   *
					   *  *


*/




Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define io  ios_base::sync_with_stdio(false), cin.tie(NULL),cout.tie(NULL)
int mod=998244353;
int power(int a,int b,int m=mod)
{
	if(b==0)	return 1;
	if(b==1)	return a;
	int res=power(a,b/2,m);
	res=(res*res)%m;
	if(b&1)	res=(res*a)%m;
	return res;
}
int modinv(int a,int m=mod){ return power(a,m-2,m);}
int add(int a,int b,int m=mod){	return (a+b)%m;}
int sub(int a,int b,int m=mod){	return (a-b+m)%m;}
int mul(int a,int b,int m=mod){	return (a*b)%m;}

int32_t main()
{
    io;
    int t;
    t=1;
    while(t--)
    {
        int n;
        cin>>n;
        map<string,int> mp;
        for(int i=0;i<n;i++)
        {
            string s;
            cin>>s;
            mp[s]++;
        }
        cout<<"AC x "<<mp["AC"]<<"\n";
        cout<<"WA x "<<mp["WA"]<<"\n";
        cout<<"TLE x "<<mp["TLE"]<<"\n";
        cout<<"RE x "<<mp["RE"]<<"\n";
    }
}


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

int main(void) {

	char str[256];
	char ans[256];
	
	scanf("%s", str);
	
	int i;
	
	for (i = 0; i < strlen(str); i++){
		if (str[i] == '0') {
			strcat(ans, "0");
		} else if (str[i] == '1') {
			strcat(ans, "1");
		} else if (str[i] == 'B') {
			ans[strlen(ans) - 1] = '\0';
		}
	}
	
	printf("%s\n" ,ans);
	
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define PI       3.1415926535897932384626433832795028841971
#define INF 1000000000
#define EPS      1e-10
#define MOD      1000000
using namespace std;
typedef long long ll;
typedef pair<double,double> P;
typedef pair<double,P> PQ;

struct UF{
	int par[100000];
	int rank[100000];
    ll si[100000];

	void init(int n){
		rep(i,n){
			par[i] = i;
			rank[i] = 0;
			si[i] = 0;
		}
	}

	int find(int x){
		if(par[x] == x) return x;
		else return find(par[x]);
	}
    
    ll value(int x, ll ret){
        if(par[x] == x) return ret+si[x];
        else return value(par[x],ret+si[x]);
    }

	void unite(int x, int y, int w){
        ll vx = value(x,0);
        ll vy = value(y,0);
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		if(rank[x] < rank[y]){
			par[x] = y;
            si[x] = vy-w-vx;
		} else{
			par[y] = x;
            si[y] = vx+w-vy;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
} uf;

int n, m;

int main(){
    while(cin >> n >> m){
        if(n == 0 && m == 0) break;
        uf.init(n);
        rep(i,m){
            char hoge;
            int a, b, w;
            cin >> hoge;
            if(hoge == '!'){
                cin >> a >> b >> w;
                a--; b--;
                uf.unite(a,b,w);
                //rep(j,n) cout << uf.si[j] << " ";
                //cout << endl;
            } else{
                cin >> a >> b;
                a--; b--;
                if(!uf.same(a,b)){
                    cout << "UNKNOWN" << endl;
                    continue;
                }
                ll numa = uf.si[a];
                ll numb = uf.si[b];
                while(uf.par[a] != a){
                    a = uf.par[a];
                    numa += uf.si[a];
                }
                while(uf.par[b] != b){
                    b = uf.par[b];
                    numb += uf.si[b];
                }
                //cout << numb << " " << numa << endl;
                cout << numb-numa << endl;
            }
        }
    }
}

Measured memory_bytes: 4488
import * as fs from 'fs';

const readString = (() => {
  const input = fs.readFileSync(0).toString();
  const words = input.split(/[ \n]/);
  let i = 0;
  return () => words[i++] || '';
})();
const readInt = () => parseInt(readString(), 10);
const readBigInt = () => BigInt(readString());

const gcd = (a: bigint, b: bigint) => {
  const _gcd = (a: bigint, b: bigint): bigint => {
    const q = a % b;
    return q === 0n ? b : _gcd(b, q);
  };
  return a > b ? _gcd(a, b) : _gcd(b, a);
};

const abs = (a: bigint) => a > 0n ? a : -a;

(function main() {
  const N = readInt();

  let zero: number = 0;
  const groups: { [k: string]: [number, number] } = {};
  Array.from({ length: N }, () => {
    let A = readBigInt();
    let B = readBigInt();
    if (A === 0n && B === 0n) {
      zero++;
    } else if (A === 0n) {
      groups['0:1'] = groups['0:1'] || [0, 0];
      groups['0:1'][0]++;
    } else if (B === 0n) {
      groups['0:1'] = groups['0:1'] || [0, 0];
      groups['0:1'][1]++;
    } else {
      const n = gcd(abs(A), abs(B));
      A /= n;
      B /= n;
      if (A < 0) {
        A *= -1n;
        B *= -1n;
      }

      if (B > 0) {
        const k = `${A}:${B}`;
        groups[k] = groups[k] || [0, 0];
        groups[k][0]++;
      } else {
        const k = `${-B}:${A}`;
        groups[k] = groups[k] || [0, 0];
        groups[k][1]++;
      }
    }
  });

  const mod = 1000000007;

  let result: bigint = BigInt(1);
  for (const k of Object.keys(groups)) {
    const [xn, yn] = groups[k];

    let tmp: number = 0;
    if (xn) {
      let xx = 1;
      for (let i = 0; i < xn; i++) {
        xx *= 2;
        if (xx > mod) xx %= mod;
      }
      xx -= 1;
      tmp += xx;
      if (tmp > mod) tmp %= mod;
    }

    if (yn) {
      let yy = 1;
      for (let i = 0; i < yn; i++) {
        yy *= 2;
        if (yy > mod) yy %= mod;
      }
      yy -= 1;
      tmp += yy;
      if (tmp > mod) tmp %= mod;
    }

    tmp++;
    if (tmp > mod) tmp %= mod;

    result *= BigInt(tmp);
    if (result > mod) result %= BigInt(mod);
  }

  result += BigInt(zero) + BigInt(mod - 1);
  if (result > mod) result %= BigInt(mod);

  console.log(result.toString());
})();


Measured memory_bytes: 150084
#include<stdio.h>
int main()
{
    int x;
    scanf("%d",&x);
    if(x>=22&&x<=25)
    {
        if(x==25)
        {
            printf("Christmas");
        }
       else if(x==24)
        {
            printf("Christmas Eve");
        }
        else if(x==23)
        {
            printf("Christmas Eve Eve");
        }
        else if(x==22)
        {
            printf("Christmas Eve Eve Eve");
        }
    }
}


Measured memory_bytes: 128
# -*- coding: utf-8 -*-
# A

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

s = input()[:-1]
if s[-1]=='s':
    print(str(s) + 'es')
else:
    print(str(s) + 's')


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

#define REP(i,n) for(ll i=0; i < (n); ++i)
#define REPR(i,n) for(ll i=(n); i >= 0; --i)
#define FOR(i, m, n) for(ll i = (m); i < (n); ++i)

#define INF 1e9
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;
    }
};
int N, M;
vector<int> p, x, y;
int main(){
  cin >> N >> M;
  p.resize(N), x.resize(M), y.resize(M);
  REP(i, N){
    cin >> p[i];
    p[i]--;
  }
  UnionFind uf(N);
  REP(i, M){
    cin >> x[i] >> y[i];
    x[i]--, y[i]--;
    uf.unite(x[i], y[i]);
  }
  int ans =0;
  REP(i, N){
    if(uf.same(p[i], i)){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


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

ll v[1000100];

int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    for(ll i=0 ; i<n ; i++){
        cin >> v[i];
    }
    sort(v, v+n);
    ll ans = 0;
    for(ll i=0 ; i<n-1 ; i++){
        ans += min((v[i+1]-v[i])*a, b);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 1024
N = int(input())
A = list(map(int, input().split()))
s = sum(A)
for i in range(N):
    A[i] *= N
mi = float("inf")
imi = 0
for i, a in enumerate(A):
    if abs(a-s) < mi:
        imi = i
        mi = abs(a-s)
print(imi)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
#define int long long
int n,l,r,a[100001],b[100001],f;
main(){
  cin>>n;
  string s,t;
  cin>>s>>t;
  int ans=n*2;
  r(i,n){
    int c=0;
    for(int j=0;j+i<n;j++){
      if(s[i+j]!=t[j])c++;
    }
    if(!c)ans=min(ans,n*2-(n-i));
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
n, a = map(int, input().split())
x = list(map(int, input().split()))
x = [i - a for i in x]
dic = {0:1}
for i in x:
    for j, k in list(dic.items()):
        dic[i+j] = dic.get(i+j, 0) + k

print(dic[0] - 1)

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

int main(){
    int a[10];
    for(int i=0;i<10;++i){
        cin >> a[i];
    }
    for(int i=0;i<10;++i){
        int j=i;
        int tmp=a[i];
        while (j>=1 && a[j]<a[j-1])
            {
                tmp=a[j-1]; a[j-1]=a[j];a[j]=tmp;
                --j;
            }
    }
        cout << a[9] << endl;
        cout << a[8] << endl;
        cout << a[7] << endl;
}


Measured memory_bytes: 3052
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
#define INF 100000000000
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
typedef pair<ll, double> PD;

int main() {
	int n;
	string s;
	cin >> n >> s;
	int k = s.size();
	for (int i = 0; i < k; i++) {
		int d = s[i] - 'A';
		d += n;
		d %= 26;
		char c='A' + d;
		cout << c;
	}
	cout << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
using namespace std;
int main(){
  int d, n, i, ans=1;
  scanf("%d%d",&d,&n);
  if(d)for (i = 0; i < d; i++) ans *= 100;
  if(n != 100)printf("%d\n",ans * n);
  else printf("%d\n",ans * 101); 
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n,d;
    int x[10][10];
    cin >> n >> d;
    for (int i=0;i<n;i++) {
        for (int j=0;j<d;j++) cin >> x[i][j];
    }

    int ans=0;
    for (int i=0;i<n-1;i++) {
        for (int j=i+1;j<n;j++) {
            int dis=0;
            for (int k=0;k<d;k++) {
                int s=x[i][k]-x[j][k];
                dis+=s*s;
            }
            int sqrt_dis = int(sqrt(dis));
            if (dis==sqrt_dis*sqrt_dis) ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    int map[][], cost[][];

    public void main(Scanner sc) {
        int n = sc.nextInt();
        int c = sc.nextInt();
        cost = new int[c][c];
        for (int i = 0; i < c; i++) {
            for (int j = 0; j < c; j++) {
                cost[i][j] = sc.nextInt();
            }
        }

        map = new int[3][c];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                map[(i + j) % 3][sc.nextInt() - 1]++;
            }
        }

        int ans = 1145141919;
        for (int i = 0; i < c; i++) {
            for (int j = 0; j < c; j++) {
                if (i == j) {
                    continue;
                }

                for (int k = 0; k < c; k++) {
                    if (j == k || k == i) {
                        continue;
                    }
                    ans = Math.min(ans, calc(c, i, j, k));
                }
            }
        }

        System.out.println(ans);
    }

    private int calc(int n, int... colors) {
        int res = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < n; j++) {
                res += map[i][j] * cost[j][colors[i]];
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        new Main().main(sc);
        sc.close();
    }
}


Measured memory_bytes: 81112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100010;
int a,b,n,cnt;
int read(){
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
int main(){
    cin>>a>>b;
    if(b%a==0) cout<<a+b<<endl;
    else cout<<b-a<<endl;
    return 0;
}

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

int main(){
  string S; cin >> S;
  int k=S.size();
  int a=0; int b=0;
  for(int i=0;i<k;i++){
    if(i%2==0 && S.at(i)=='1'){
      a++;
    }
    if(i%2==1 && S.at(i)=='0'){
      a++;
    }
  }
  for(int i=0;i<k;i++){
    if(i%2==0 && S.at(i)=='0'){
      b++;
    }
    if(i%2==1 && S.at(i)=='1'){
      b++;
    }
  }
  cout << min(a, b) << endl;
}
  

Measured memory_bytes: 512
#include <iostream>
#include <vector>

int main() {
  
  std::vector<int> ns = {
    1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
  };
  
  int n;
  std::cin >> n;
  std::cout << ns[n-1];
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct edge{
    int to;
    int cap;
    int rev;
};
struct Dinic{
    int V;
    vector<int> level, used;
    vector<vector<edge>> G;
    Dinic(int N){
        V = N;
        used.resize(V, 0);
        level.resize(V, -1);
        G.resize(V);
    }
    void add(int u, int v, int c){
        edge e1 = {v, c, (int)G[v].size()};
        G[u].push_back(e1);
        edge e2 = {u, 0, (int)G[u].size() - 1};
        G[v].push_back(e2);
    }
    void bfs(int s){
        level.assign(V, -1);
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for(edge e: G[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
    }
    int dfs(int s, int t, int f){
        if(s == t) return f;
        for(int &i = used[s]; i < (int)G[s].size(); i++){
            edge &e = G[s][i];
            if(e.cap > 0 && level[e.to] > level[s]){
                int d = dfs(e.to, t, min(f, e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int solve(int s, int t){
        int flow = 0;
        int INF = 1e9;
        while(1){
            bfs(s);
            if(level[t] < 0) return flow;
            used.assign(V, 0);
            int f;
            while((f = dfs(s, t, INF)) > 0) flow += f;
        }
    }
};

int main(){
    int N;
    cin >> N;
    Dinic Ford(2 * N + 2);
    int can[N][N];//can[i][j] = 1でペアが作れる
    vector<int> a(N), b(N), c(N), d(N);
    for(int i = 0; i < N; i++) cin >> a[i] >> b[i];
    for(int i = 0; i < N; i++) cin >> c[i] >> d[i];
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(a[i] < c[j] && b[i] < d[j]) can[i][j] = 1;
            else can[i][j] = 0;
        }
    }
    for(int i = 0; i < N; i++){
        Ford.add(2 * N, i, 1);
        Ford.add(N + i, 2 * N + 1, 1);
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(can[i][j]) Ford.add(i, N + j, 1);
        }
    }
    int ans = Ford.solve(2 * N, 2 * N + 1);
    cout << ans << endl;
}

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

const int N = 2000;
const int MOD = 1e9 + 7;

int n;
long long k;
int a[N];
long long fr[N],al[N];
long long ans;

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

    cin >> n >> k;

    for(int i = 0;i < n;i++) cin >> a[i];

    for(int i = 0;i < n;i++) 
    {
        for(int j = 0;j < i;j++) if(a[j]>a[i]) fr[i]++;
        for(int j = 0;j < n;j++) if(a[j]>a[i]) al[i]++;
    }

    for(int i = 0;i < n;i++)
    {
        long long each = (fr[i]*k)%MOD;
        long long bf = ((k*(k-1LL))/2LL)%MOD;
        bf = (bf*al[i])%MOD;
        ans = ((each+bf)%MOD+ans)%MOD;
    }

    cout << ans;
}


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

int N = 1000;
int INF = (1<<21);

int main()
{
  int n,x,y,no,sum,mas[N][N],u,v,min,a[N],p[N],vis[N];

  scanf("%d",&n);

  for(x = 0;x < n;x++)
    {
      for(y = 0;y < n;y++)
	{
	  scanf("%d",&no);
	  if(no==-1)mas[x][y] = INF;
	    else mas[x][y] = no;
	}
    }
  for(x = 0;x < n;x++)
    {
      a[x] = INF;
      p[x] = -1;
      vis[x] = 0;
    }

  while(1)
    {
      min = INF;
      u = -1;
      a[0] = 0;
      for(x = 0;x < n;x++)
	{
	  if(min > a[x] && !vis[x])
	    {
	      u = x;
	      min = a[x];
	    }
	}
      if(u == -1)break;
      vis[u] = 1;
      for(v = 0;v < n;v++)
	{
	  if(!vis[v] && mas[u][v] != INF)
	    {
	      if(a[v] > mas[u][v])
		{
		  a[v] = mas[u][v];
		  p[v] = u;
		}
	    }
	}
    }

  sum = 0;

  for(x = 0;x < n;x++)
    {
      if(p[x] != -1)
	sum += mas[x][p[x]];
    }
  printf("%d\n",sum);

  return 0;
}



Measured memory_bytes: 2104
N = int(input())
W = list(map(int, input().split()))
tmp = 1000000
for i in range(N):
    tmp1 = sum(W[:i])
    tmp2 = sum(W[i:])
    if tmp > abs(tmp1 - tmp2):
        tmp = abs(tmp1 - tmp2)
print(tmp)


Measured memory_bytes: 40416
import sys
import math
n = int(input())
ls = []
for i in range(n):
    t, a = [int(i) for i in sys.stdin.readline().split()]
    ls.append((t, a))
_min = 1e-10
_min_a = 1
_min_t = 1
res = []
for l in ls:
    t, a = l
    _sum = t + a
    cnt = max(-(-_min_a//a), -(-_min_t//t))
    _min_a = cnt * a
    _min_t = cnt * t
    _min = cnt * _sum
    res.append(_min)
print(res[-1])

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

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()

#define MOO(i, a, b) for (int i=a; i<b; i++)
#define M00(i, a) for (int i=0; i<a; i++)
#define MOOd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define M00d(i,a) for (int i = (a)-1; i >= 0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _<< " _ " <<

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;
typedef vector<int> vi;
typedef vector<ll> vll;

const ll MOD = 1e9 +7;
ll POW(ll b, ll e) {
	ll res = 1;
	while(e) {
		if(e & 1) {
			res *= b; res %= MOD;
		}
		b *= b; b %= MOD;
		e /= 2;
	}
	return res;
}
ll INV(ll a) {
	return POW(a, MOD-2);
}

int main() { FAST
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	int k;
	string S;
	cin >> k >> S;
	int s = S.size();
	ll all = POW(26, s + k);
	ll base = POW(25, s+k);
	ll back = INV(25);
	ll choose = 1;
	M00(i, s) {
		all -= base*choose; all %= MOD;
		base *= back;
		base %= MOD;
		choose *= (s+k-i); choose %= MOD;
		choose *= INV(i+1); choose %= MOD;
	}
	all %= MOD; all += MOD; all %= MOD;
	cout << all << endl;
}


Measured memory_bytes: 4316