akhauriyash/Code-Regression huggingface dataset:
N = int(input())

A = []
B = []
for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
A.sort()
B.sort()

if N%2:
  ma = A[N//2]
  mb = B[N//2]
  print(max(0, mb-ma+1))
else:
  ma = A[N//2] + A[N//2-1]
  mb = B[N//2] + B[N//2-1]
  print(max(0, mb-ma+1))


Measured memory_bytes: 25368
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>

#define MP make_pair
#define PB push_back
#define in int
#define ll long long
#define ull unsigned long long
#define vc vector
#define SQ(j) (j)*(j)
#define ch first
#define range second
//
//#define ld long double
#define dbl  double
#define pll pair<long long,long long>
#define pii pair<int,int>
#define sz(xxx) ((int)(xxx.size()))
#define all(j) j.begin(), j.end()
#define loop(xxx, yyy) for(int xxx = 0; xxx < yyy; xxx++)
//#define printf(fmt, ...) (0)
//#define HOME
//#define y0 ngacaleiebinvoaeu
//#define y1 gnarpipipaigare
#define j1 adsfndnasfafoasp

//#define printf(...) (0)
#define db(x) if(DEBUG) {cout << #x << " = " << x << endl;}
#define dbCont(x) if(DEBUG) {cout << #x << ": "; for(auto shun: x) cout << shun << ' '; cout<<endl;}

using namespace std;

template<class K, class V>
ostream &operator<<(ostream &out, pair<K, V> &elem) {
    out << "{" << elem.first << "," << elem.second << "}";
    return out;
}

// 4:13

int DEBUG = 0;

using namespace std;

const int N = 100 * 1000 + 5;
const ll MOD = 1000 * 1000 * 1000 + 7;

ll bin_exp(ll base, ll exp){
    if(exp == 0) return 1;

    ll h = bin_exp(base, exp/2);

    h = (h*1ll*h)%MOD;
    if(exp % 2 == 1){
        h = (h*base)%MOD;
    }
    return h;
}

ll inv(ll x){
    return bin_exp(x, MOD-2);
}

ll fct[N];
ll ifct[N];

ll C(ll n, ll k) {
    if (k < 0 || k > n)
        return 0;
    return ((ll) fct[n] * ifct[k] % MOD) * ifct[n - k] % MOD;
}

ll n,k;


ll solve(vc<ll> a){
    dbCont(a);
    sort(all(a));

    map<ll,ll> used;

    map<ll,ll> fi;
    map<ll,ll> li;
    for(int i = 0; i < n; i++) li[a[i]] = i;
    for(int i = n-1; i >= 0; i--) fi[a[i]] = i;

    ll ans = 0;
    loop(i,n){
        if(!used[a[i]]){
            used[a[i]] = 1;
            ll Li = li[a[i]]+1;
            ll Fi = fi[a[i]]+1;

            db(Li);
            db(Fi);
            if(Li >= k){

                db(C(Li, k));
                db(C(Fi,k));
                ll curAns = (C(Li, k) - C(Fi-1,k) + MOD*7ll) % MOD;
                db(curAns);

                ans += (curAns*a[i]) % MOD;
                ans %= MOD;
            }
        }
    }
    return ans;
}

int main() {
    fct[0] = 1;
    ifct[0] = 1;
    for (int l = 1; l < N; ++l) {
        fct[l] = ((ll) fct[l - 1] * l) % MOD;
        ifct[l] = inv(fct[l]);
    }


    cin >> n >> k;
    vc<ll> a;

    a.resize(n);
    loop(i,n){
        cin >> a[i];
    }
    sort(all(a));



    ll mxSum = solve(a);
    db(mxSum);
    loop(i,n) a[i] *= -1;

    ll mnSum = (0-solve(a) + MOD) % MOD;
    db(mnSum);

    ll ans = (mxSum - mnSum + MOD) % MOD;

    cout << ans << endl;

    return 0;
}

/*

7
1 0 0 5 0 0 2

 */

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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define FOR(i, start, end) for(int i = (start); i < (end); i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;


void solve()
{
    int N; cin >> N;
    if(N == 1)
    {
        cout << "Hello World" << endl;
    }
    else
    {
        int A, B; cin >> A >> B;
        cout << A + B << endl;
    }
}

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long int ll;


int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> num(n);
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	sort(num.begin(), num.end(),greater<int>());
	ll ans = 0;
	for (int i = 0; i < k; i++) {
		ans += num[i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
#define int long long
int pre[50],in[50],post[50];
int n,pos,idx;
void dfs(int l,int r){
  if(l>=r) return;
  int root=pre[pos++];
  int m=-1;
  for(int i=l;i<r;i++)
    if(in[i]==root) m=i;
  dfs(l,m);
  dfs(m+1,r);
  post[idx++]=root;
}
signed main(){
  cin>>n;
  for(int i=0;i<n;i++) cin>>pre[i];
  for(int i=0;i<n;i++) cin>>in[i];
  pos=idx=0;
  dfs(0,n);
  for(int i=0;i<n;i++)
    cout<<post[i]<<" \n"[i==n-1];
  return 0;
}


Measured memory_bytes: 3120
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = int64_t;
#define rep(i, j, n) for (int i = j; i < (int)n; ++i)

constexpr int INF = 0x3f3f3f3f;

int main() {
  int n;
  cin >> n;
  vector<vector<int>> g(n, vector<int>(n, INF));
  rep(i, 0, n) {
    string s;
    cin >> s;
    rep(j, 0, n) { g[i][j] = (s[j] - '0' == 1 ? 1 : INF); }
    g[i][i] = 0;
  }

  vector<int> par(n * 2, -1);
  auto root = [&](auto self, int x) {
    if (par[x] < 0) return x;
    return par[x] = self(self, par[x]);
  };
  auto merge = [&](int x, int y) {
    x = root(root, x);
    y = root(root, y);
    if (x == y) return;
    if (par[x] > par[y]) swap(x, y);
    par[x] += par[y];
    par[y] = x;
    return;
  };
  auto same = [&](int x, int y) { return root(root, x) == root(root, y); };

  rep(i, 0, n) {
    rep(j, i + 1, n) {
      if (g[i][j] == 1) {
        merge(i, j + n);
        merge(i + n, j);
      }
    }
  }
  if (same(0, n)) {
    cout << "-1" << endl;
    return 0;
  }

  rep(k, 0, n) rep(i, 0, n) rep(j, 0, n) g[i][j] =
    min(g[i][j], g[i][k] + g[k][j]);

  int ans = 0;
  rep(i, 0, n) rep(j, 0, n) ans = max(ans, g[i][j]);
  cout << ans + 1 << endl;
  return 0;
}


Measured memory_bytes: 3760
#include<stdio.h>
#define MAX 200
int p[6][MAX],stack[6][MAX],indexSTACK[6];
int h,w,c,max;

void STACKpush(int,int);
void colorChange(int,int);
void stackPanelR(int,int);
void stackPanel(int);
void panelR(int);
int panel();

int main(void){
  int i;
  while(1){
    scanf("%d %d %d",&h,&w,&c);
    if(h==0&&w==0&&c==0)break;
    for(i=0;i<h*w;i++)scanf("%d",&p[0][i]);
    printf("%d\n",panel());
  }
  return 0;
}

void STACKpush(int n,int item){
  int j;
  for(j=0;j<indexSTACK[n];j++){
      if(item==stack[n][j])return;
    }
  stack[n][indexSTACK[n]++]=item;
}

void colorChange(int n,int color){
  int i;
  for(i=0;i<w*h;i++)p[n+1][i]=p[n][i];
  for(i=0;i<indexSTACK[n];i++){
    p[n+1][stack[n][i]]=color;
  }
}
void stackPanelR(int n,int point){
  int i,j,nextX,nextY,next;
  int x=point%w;int y=point/w;
  int directionX[4]={-1,0,1,0};//左,上,右,下
  int directionY[4]={0,-1,0,1};
  for(i=0;i<4;i++){
    nextX=x+directionX[i];
    nextY=y+directionY[i];
    if(nextX<0 || nextX>=w)continue;
    if(nextY<0 || nextY>=h)continue;
    next=nextX+nextY*w;
    int judge=1;
    for(j=0;j<indexSTACK[n];j++){
      if(next==stack[n][j])judge=-1;
    }
    if(judge==-1)continue;
    if(p[n][0]==p[n][next]){
      STACKpush(n,next);
      stackPanelR(n,next);
    }
  }
}
void stackPanel(int n){
  indexSTACK[n]=0;
  STACKpush(n,0);
  if(1<w && p[n][0]==p[n][1]){
    STACKpush(n,1);
    stackPanelR(n,1);
  }
  if(1<h && p[n][0]==p[n][w]){
    STACKpush(n,w);
    stackPanelR(n,w);
  }
}

void panelR(int n){
  int i;
  stackPanel(n);
  if(n==5){
    if(indexSTACK[n]>max)max=indexSTACK[n];
    return; 
  }
  for(i=1;i<=6;i++){
    if(p[n][0]==i)continue;
    if(n==4)colorChange(n,c);
    else{
      if(n==3&&i==c)continue;
      colorChange(n,i);
    }
    panelR(n+1);
  }
}

int panel(){
  max=0;
  panelR(0);
  return max;
}

Measured memory_bytes: 612
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def main():
    import sys
    N = int(input())
    fact = factorization(N)
    if fact[0][0] == 1:
        print(0)
        sys.exit()
    ans = 0
    for f, num in fact:
        for i in range(1, num+1):
            if num < i:
                break
            num -= i
            ans += 1
    print(ans)
main()

Measured memory_bytes: 63432
//Author : Sukarna Paul

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/detail/standard_policies.hpp>
#define pi acos(-1)
#define pb push_back
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define MAX 300005
#define INF 0x3f3f3f3f
template <class T> inline T bigmod(T p,T e,T M){ll ret = 1LL;for(; e > 0LL; e >>= 1LL){if(e & 1LL) ret = (ret * p) % M;p = (p * p) % M;}return (T)ret;}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}   // M is prime}

using namespace std;
using namespace __gnu_pbds;

typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update>pref_trie;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;

ll ans[1000006];
void pre(){
    for(int i=1;i<=1000001;i++){
        if(i%3!=0 && i%5!=0)ans[i] = ans[i-1]+i;
        else ans[i]=ans[i-1];
    }
}

int main(){
    IOS
    //freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    n++;
    ll ans = 0;
    for(ll i=1;i<n;i++){
        for(ll j=1;j<n;j++){
            ll g=__gcd(j,i);
            for(ll k=1;k<n;k++){
                ans+= __gcd(k,g);
            }
        }
    }
    cout<<ans<<"\n";
}


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


void solve(long long A, long long B){
    cout << 6 - A - B << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(A, B);
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    String T = sc.next();
    int num = S.length();
    int counts = 0;
    for (int i = 0; i < num; i++) {
      if (S.charAt(i) != T.charAt(i)) {
        counts = counts + 1;
      }
    }
    System.out.println(counts);
  }
}


Measured memory_bytes: 41216
#include<bits/stdc++.h>
using namespace std;
int main()
{
string x; 
cin>>x;
int a=x.size(),ans=0;
  for(int i=0;i<a;i++)
  {
    if(x[i]=='0')
	  ans++;
  }
cout<<a-(max(a-ans,ans)-min(a-ans,ans))<<endl;
return 0;
}

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

int main() {
	int n, k; cin >> n; cin >> k;
	int d = 1;
	for (int i = 0; i < n ; ++i) {
		if (d <= k) {
			d *= 2;
		} else {
			d +=k;
		}
	}
	cout << d << endl;
	return 0;
}

Measured memory_bytes: 256
using namespace std;
#include <bits/stdc++.h>
#define rep(i, s) for (int i = 0; i < s; ++i)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define all(v) (v.begin(), v.end())
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define EPS (1e-7)
#define INF (1e10)
#define PI (acos(-1))
const ll mod = 1000000007;
bool f(string s){
  bool ans=true;
  rep(i,s.size()/2){
    if(s[i]!=s[s.size()/2+i]){
      ans=false;
      break;
    }
  }
  return ans;
}



int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll W,H,x,y;
  cin>>W>>H>>x>>y;
  if(x+x==W&&y+y==H)
    cout<<W*H/2.0<<' '<<1<<endl;
  else
     cout<<W*H/2.0<<' '<<0<<endl;

}
    
  
  


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  int N;
  cin >> N;
  map<int,int> memo;
  rep(i,N){
    int a;
    cin >> a;
    memo[a-1]++;
    memo[a]++;
    memo[a+1]++;
  }

  int mx = 0;
  int mxi = -1;
  FOR(it,memo){
    if(mx < it->second){
      mxi = it->first;
      mx = it->second;
    }
  }

  cout << mx << endl;
  
  return 0;
}


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

int main() {
	int k,s;
	cin>>k>>s;
	int ans=(s+1)*(s+2)/2;
	if(k+1<=s) ans-=(3)*(s-k+1)*(s-k)/2;
	if(2*k+2<=s) ans+=(3)*(s-2*k)*(s-2*k-1)/2;
	if(3*k+3<=s) ans-=(1)*(s-3*k-1)*(s-3*k-2)/2;
	cout<<ans<<'\n';
}

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

#define REP(i,n) for(int i=0;i<(n);i++)
#define REAP(i,a,n) for(int i=(a);i<(n);i++)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define fr first
#define sc second
#define pb push_back
#define All(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> a(n);
    REP(i,n)cin >> a[i];
    sort(All(a));
    ll cou=1,res=0;
    REAP(i,1,n){
        if(a[i-1]==a[i]){
            cou++;
        }else{
            if(cou%2)res++;
            cou=1;
        }
    }
    if(cou%2)res++;
    cout << res << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define Rushia_mywife ios::sync_with_stdio(0);cin.tie(0);
#define rep(i,head,n) for(int i=(head);i<n;i++)
#define int long long
#define F first
#define S second
#define pb push_back
#define p2(n) (1<<(n))
#define lg2(n) __lg(n)
using namespace std;
using pii = pair<long long,long long>;
using ld = long double;
mt19937 mt_rand(time(0));
const int mod = 1000000007;
const int hnum = 998244353;
const ld PI = acos(-1);

int n,m;
int val[10] = {0,2,5,5,4,5,6,3,7,6};
int a[10];
string ans;
string dp[10010];

string maxstr(string x,string y){
    if(x.size()==y.size())
        return max(x,y);
    return (x.size()>y.size() ? x : y);
}

void solve(){
    cin >> n >> m;
    rep(i,0,m){
        cin >> a[i];
        dp[val[a[i]]] = maxstr(dp[val[a[i]]],dp[0]+char(a[i]+'0'));
    }
    rep(i,1,n+1)
        rep(j,0,m)
            if(val[a[j]]<=i&&dp[i-val[a[j]]]!="")
                dp[i] = maxstr(dp[i],dp[i-val[a[j]]]+char(a[j]+'0'));
    cout << dp[n] << '\n';
}

signed main(){
    Rushia_mywife
    solve();
}

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

int main() {
    long long A, B, K;
    cin >> A >> B >> K;

    long long tmp_A = A;
    A = A - K;
    if (A < 0) A = 0;

    K = K - tmp_A;
    if (K > 0) {
        B -= K;
        if (B < 0) B = 0;
        K -= B;
    }

    cout << A << " " << B << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main
{
    public static void main(String arg[])
    {
        Scanner in=new Scanner(System.in);
        int t1[]=new int[1001];
        int t2[]=new int[1001];
        for(;;)
        {
            String s[]=in.nextLine().split(",");
            if(s[0].compareTo("")==0)
                break;
            t1[Integer.valueOf(s[0])]++;
        }
        while(in.hasNext())
        {
            String s[]=in.nextLine().split(",");
            t2[Integer.valueOf(s[0])]++;
        }
        for(int i=0;i<=1000;i++)
        {
            if(t1[i]>0&&t2[i]>0)
                System.out.println(i+" "+(t1[i]+t2[i]));
        }
    }
}


Measured memory_bytes: 26052
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define INF 1<<50LL
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define RFOR(i,a,b) for(long long i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
typedef pair<ll,ll> P;

struct Edge{
  int x,y,cost;
  	bool operator < (const Edge &e) const
	{
		return cost<e.cost;
	}
};

struct Node{
  int x,y,id;
};

int cmpx(Node& a,Node& b){
  return a.x < b.x;
}

int cmpy(Node& a,Node& b){
  return a.y < b.y;
}

vector <Edge>edge;  
vector <Node>node;

const int MAXN = 100100;
int tree[MAXN];
vector <int> child;
ll ans = 0;

int root(int i){
  if(i == tree[i]){
    for(int j = 0; j < child.size(); j++)
      tree[child[j]] = i;
    child.clear(); 
    return i;                   
  }
  else{
    child.push_back(i);
    return i = root(tree[i]);
  }
}

int unit(int x,int y){
  x = root(x);
  y = root(y);
  tree[max(x,y)] = min(x,y);     
}

bool isUnit(int x,int y){
  return root(x) == root(y);
}
  

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

  int n;
  cin >> n;

  REP(i,n){
    int x,y;
    cin >> x >> y;
    node.push_back({x,y,i});
  }
  
  sort(node.begin(),node.end(),cmpx);
  REP(i,n-1){
    edge.push_back({node[i].id,node[i+1].id,abs(node[i+1].x-node[i].x)});
  }
  
  sort(node.begin(),node.end(),cmpy);
  REP(i,n-1){
    edge.push_back({node[i].id,node[i+1].id,abs(node[i+1].y-node[i].y)});
  }
  
  sort(edge.begin(),edge.end());
  
/*  REP(i,edge.size()){
    cout << edge[i].x << " " << edge[i].y << " " << edge[i].cost << endl;
  }*/
  
  REP(i,n) tree[i] = i;
  
  REP(i,edge.size()){
    if(isUnit(edge[i].x,edge[i].y)) continue;
    unit(edge[i].x,edge[i].y);
    ans += edge[i].cost;
  }
  
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 6132
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Windows;

using static Input;
using static Util;
class Program
{
    static int A, B;
    static void INPUT()
    {
        A = NextInt();
        B = NextInt();
    }

    static void OUT()
    {
        Console.WriteLine(A * B);
    }
    static void Main(string[] args)
    {
#if DEBUG  
        //TESTINPUT();
        INPUT();

#else
        INPUT();
#endif
        OUT();
    }

    static void TESTINPUT()
    {
    }

}

public class Input
{
    public const long MOD = 1000000007;
    public const int INF = 1000000007;
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}

class Util
{

}




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

using namespace std;

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

int main() {
    int n;

    while (1) {
        cin >> n;
        if (n == 0) break;

        int s[n]={};
        REP(i, n) cin >> s[i];
        int sum = 0;
        REP(i, n) sum += s[i];
        double ave = 1.0 * sum / n;
        double dist = 0;
        REP(i, n) dist += (ave - s[i]) * (ave - s[i]);
        printf("%lf\n", sqrt(dist / n));
    }
}

Measured memory_bytes: 3144
#include<stdio.h>
int main()
{
  int a,b,c,d;
  scanf("%d %d",&a,&b);
  if(a<b)
    {
      d=a;
      a=b;
      b=d;
    }
  c=a%b;
  while(c!=0)
    {
      a=b;
      b=c;
      c=a%b;
    }
  printf("%d\n",b);

  return 0;
}

Measured memory_bytes: 592
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

bool cmp(const int a, const int b) { return (a > b); }

int main() {
  int N, K, a, sum = 0;
  map<int, int> counter;
  vector<int> cnt;

  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    cin >> a;
    if (counter.count(a) == 0) {
      counter[a] = 1;
    } else {
      counter[a]++;
    }
  }
  for (auto iter = counter.begin(); iter != counter.end(); ++iter) {
    cnt.push_back(iter->second);
  }
  sort(cnt.begin(), cnt.end());
  for (int i = 0; i < (int)cnt.size() - K; i++) {
    sum += cnt[i];
  }
  cout << sum << endl;
}



Measured memory_bytes: 10748
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a,b,d,r;
		double f,a1,b1;
		a=sc.nextInt();
		b=sc.nextInt();
		d=a/b;r=a%b;
		a1=a;b1=b;
		f=a1/b1;
		System.out.print(d+" "+r+" ");
		System.out.printf("%.5f",f);
	}
}



Measured memory_bytes: 26544
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<functional>
using namespace std;
#define ll long long int
#define ld long double
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,
tree_order_statistics_node_update> in_set;
#define rep(n) for(ll i=0;i<(n);i++)
#define jrep(n) for(ll j=0;j<(n);j++)
#define all(a) (a).begin(), (a).end()
#define dpp(a) cout<<(a).first<<" "<<(a).second<<endl;
#define append push_back
#define mod 1000000007
#define ff first
#define ss second
#define ffast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fast ios::sync_with_stdio(0);
ll pw(ll x,ll y,ll p=mod){ll r=1; x=x%p;while(y>0){ if(y&1)r=(r*x)%p;
y=y>>1;x=(x*x)%p;} return r; } vector<ll> uniq(vector<ll> arr)
{vector<ll>brr;sort(all(arr));brr.append(arr[0]);
for(auto i:arr)if(brr.back()!=i)brr.append(i);return brr;}
 
void solve(){
    map<ll,ll> mp; set<ll> st;
    ll h; cin>>h; //st.insert(h); ms[h]=1;
    ll at=0;
    ll cat = 1;
    while(h>0){
        at+=cat;
        cat*=2; h/=2;
    }
    cout<<at<<endl;
}
 
int main(){
    ffast
    ll t=1;
    //cin>>t;
    rep(t) solve();
}
 
 
// *p.find_by_order(n) : nth value (0 indexed)
// p.order_of_key(7): index of 7 (0 indexed)


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[100100];
        for (int i = 0; i < N; ++i) A[i] = sc.nextInt();
        int res = A[0];
        for (int i = 0; i < N; ++i) {
            res = gcd(res, A[i]);
        }
        System.out.println(res);
    }
    private static int gcd(int x, int y) {
        if (y > 0) return gcd(y, x % y);
        return x;
    }
}


Measured memory_bytes: 50444
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int isSame(char*, char*, int);
int main() {
	char s[1000] = { "" }, ss[1000] = { "" },*T=s, *P=ss;
	int x,xx,i=0;
	scanf("%s", T);
	scanf("%s", P);
	x = strlen(P);
	xx = strlen(T);
	while (i<xx) {
		if (*T == *P) if (isSame(T, P, x)) printf("%d\n", i);
		++i;
		T++;
	}
	return 0;
}

int isSame(char *T, char *P, int x){
	int i;
	for (i = 1; i < x; i++) {
		if (*(P + i) == *(T + i)) continue;
		return 0;
	}
	return 1;
}

Measured memory_bytes: 540
def solve(S, c):
    if S > c//2:
        return c//2
    elif S == c//2:
        return c//2
    if S < c//2:
        cnt = S
        c -= S * 2
        S -= S
        assert S == 0
        assert c > 0
        return cnt + c//4


S, c = [int(x) for x in input().split()]
print(solve(S, c))


# if S < c//2: c が多い
# if S > c//2: c が足りない





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

struct UnionFind {
    vector<int> Parent;
    vector<int> Size;

    UnionFind(int N) : Parent(N), Size(N,1){
        for(int i = 0; i < N; i++) Parent[i] = i;
    }

    int root(int A) {
        if (Parent[A] == A) return A;
        return Parent[A] = root(Parent[A]);
    }

    bool merge(int A, int B) {
        A = root(A);
        B = root(B);
        if (A == B) return false;

        if (Size[A] < Size[B]) swap(A, B);

        Size[A] += Size[B];
        Parent[B] = A;
        return true;
    }

    bool issame(int A, int B) { //
        return root(A) == root(B);
    }

    int findsize(int A) {
        return Size[root(A)];
    }
};

vector<vector<int>> friends;

signed main() {
  int n,m,k;
  cin >> n >> m >> k;

  friends.resize(n);
  UnionFind tree(n);
  while(m--) {
    int a,b; cin >> a >> b;
    a--, b--;
    tree.merge(a,b);
    friends[a].push_back(b);
    friends[b].push_back(a);
  }

  vector<int> ans(n);
  for (int i = 0; i < n; i++) {
    ans[i] = tree.findsize(i) - 1 - (int)friends[i].size();
  }

  while(k--) {
    int a,b; cin >> a >> b;
    a--, b--;
    if(tree.issame(a,b)) {
      ans[a]--, ans[b]--;
    }
  }

  for (int i = 0; i < n; i++) {
    cout << ans[i] << (i == n - 1 ? '\n' : ' ');
  }

}

Measured memory_bytes: 10296
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
char s[110];
int main()
{
    int n, ans = 0, x = 0;
    scanf("%d",&n);
    scanf(" %s",s);
    for(int i=0;i<n;i++)
    {
        if(s[i] == 'I') x++;
        else    x--;
        ans = max(ans, x);
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  int sum=0;
  for(int i=0;i<a;i++){
    sum+=i;
  }
  for(int i=0;i<b;i++){
    sum+=i;
  }
  cout<<sum<<endl;
 return 0; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    const long double pi = acos(-1.0L);
    long double a, b, h, m;
    cin >> a >> b >> h >> m;
    long double theta = 2.0 * pi * m / 60.0 - 2.0 * pi * (h / 12.0 + m / 60.0 / 12.0);
    long double ret   = a * a + b * b - 2 * a * b * cos(theta);
    cout << fixed << setprecision(15) << sqrt(ret) << "\n";
    return 0;
}

Measured memory_bytes: 4176
/******

AUTHOR : RUDRANSH TRIPATHI, IIIT NAGPUR, CCID(rt24) & CFID(rsgt24)

MOTTO : Use criticism as fuel and you will never run out of energy.
        AIM : TO BECOME A BETTER CODER
        INTROSPECT + COURSE CORRECTIONS = CATALYST FOR SUCCESS
        Every moment is an opportunity to better yourself
        
*******/

#include<bits/stdc++.h>
using namespace std;
const int M = 1e9 + 7;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define int long long
#define pb push_back
#define mp make_pair
#define d(x) cout<<x<<"\n"

int32_t main(void)
{
    fastio
    int t=1;
    cin>>t;
    int w=t;
    string ar[t];
    int i=0;
    while(t--)
    {
        string temp;
        cin>>temp;
        ar[i]=temp;
        i++;
    }
    
    string x="AC",y="WA",z="TLE",q="RE";
    int c1=0,c2=0,c3=0,c4=0;
    for(int i=0;i<w;i++)
    {
        if(ar[i]=="AC")
        c1++;
        if(ar[i]=="WA")
        c2++;
        if(ar[i]=="TLE")
        c3++;
        if(ar[i]=="RE")
        c4++;
    }
    
    cout<<"AC"<<" x "<<c1<<"\n";
    cout<<"WA"<<" x "<<c2<<"\n";
    cout<<"TLE"<<" x "<<c3<<"\n";
    cout<<"RE"<<" x "<<c4<<"\n";
    
    return 0;
}

Measured memory_bytes: 6776
# 入力の取得
k, s = map(int, input().split())

# 処理
count = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if 0 <= z <= k:
            count += 1

# 結果出力
print(count)

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

/*
top  red
bottom  cyan
north  green
south  magenta
east  blue
west  yellow
*/
class Dice{
public:
	vector<int> dice;
	Dice(){
		dice.resize(6);
		dice[0] = 'r';
		dice[1] = 'm';
		dice[2] = 'b';
		dice[3] = 'y';
		dice[4] = 'g';
		dice[5] = 'c';
	}
	Dice(vector<int> from){ dice = from; }
	void west(){
		int to[] = {3,2,6,1,5,4};
		doRotate(to);
	}
	void north(){
		int to[] = {2,6,3,4,1,5};
		doRotate(to);
	}
	void doRotate(int to[6]){
		vector<int> tmp = dice;
		for(int i = 0 ; i < 6 ; i++) tmp[i] = dice[to[i]-1];
		dice = tmp;
	}
};

struct NODE{
	Dice d;
	int x,y,now,cost;
};
bool operator < (const NODE &a,const NODE &b){
	if( a.cost != b.cost ) return a.cost > b.cost;
	if( a.x != b.x ) return a.x < b.x;
	if( a.y != b.y ) return a.y < b.y;
	if( a.now != b.now ) return a.now < b.now;
	return a.d.dice < b.d.dice;
	
}


char c[31][31];

int main(){
	int H,W;
	while( cin >> W >> H && H ){
		
		int sx,sy;
		for(int i = 0 ; i < H ; i++){
			for(int j = 0 ; j < W ; j++){
				cin >> c[i][j];
				if( c[i][j] == '#' ){
					sx = j;
					sy = i;
					c[i][j] = 'w';
				}
			}
 		}
		
		string v;
		cin >> v;
		int dx[] = {0,1,0,-1};
		int dy[] = {1,0,-1,0};
		priority_queue<NODE> Q;
		Q.push({Dice(),sx,sy,0,0});
		map<NODE,bool> done;
		while( Q.size() ){
			NODE q = Q.top(); Q.pop();
			if( q.x < 0 || q.y >= H || q.x >= W || q.x < 0 ) continue;
			if( c[q.y][q.x] == 'k' ) continue;
			
			if( c[q.y][q.x] != 'w' ){
				if( c[q.y][q.x] != v[q.now] || q.d.dice[0] != v[q.now]){
					continue;
				}else{
					q.now++;
				}
			}
			NODE dummy = q;
			dummy.cost = 0;
			if( done[dummy]++ ) continue;
			if( q.now == v.size() ){
				cout << q.cost << endl;
				goto ok;
			}
			// west
			{
				NODE ne = q;
				ne.x--;
				ne.d.west();
				ne.cost++;
				Q.push(ne);
			}
			// east
			{
				NODE ne = q;
				ne.x++;
				ne.d.west();ne.d.west();ne.d.west();
				ne.cost++;
				Q.push(ne);
			}
			// north
			{
				NODE ne = q;
				ne.y--;
				ne.d.north();
				ne.cost++;
				Q.push(ne);
			}
			// south
			{
				NODE ne = q;
				ne.y++;
				ne.d.north();ne.d.north();ne.d.north();
				ne.cost++;
				Q.push(ne);
			}
		}
		cout << "unreachable" << endl;
		ok:;
	}
}

Measured memory_bytes: 9316
N = gets.to_i
x = [0]+gets.split.map(&:to_i)
def factorial(n)
  a = 1
  for i in 1..n
    a = a*i%(10**9+7)
  end
  a
end
ans = 1
stack = []
for i in 1..N
  stack.push(x[i])
  k = stack.length
  if (x[i] < 2*k-1) && (i<N)
    stack.pop
    ans = ans*k%(10**9+7)
  end
end
puts (ans*factorial(stack.length))%(10**9+7)

Measured memory_bytes: 10116
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int ans = 0;
  for(int i=1; i<=n; i++) {
    string s = to_string(i);
    if(s.size()%2 != 0) {
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3720
/**
 * author:    Ziel
 * created:   23.04.2020 20:19:46
**/

// ~zaletaet~

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#define fi first
#define se second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

using ll = long long;
using ull = unsigned long long;
// using big = __int128_t; // -10^38...10^38
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

const ll N = 1e5 + 123, MOD = 1e9 + 7, oo = 1e9 + 9, INF = 1e18 + 9;
const double EPS = 1e-9, PI = acos(-1); // 3.14159265358979323846
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}, dy[] = {0, 0, 1, -1, 1, -1, -1, 1};

main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	
    int n, s;
    cin >> n >> s;
    vector<int> w(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    vector<vector<ll>> dp(n + 1, vector<ll>(s + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= s; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[n][s];
    
	return 0;
}

/*
	Raise your standard.
*/


Measured memory_bytes: 80256
#include<iostream>

using namespace std;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a == 7 && b == 5 && c == 5)
		cout << "YES"<<endl;
	else if (a == 5 && b == 7 && c == 5)
		cout << "YES"<<endl;
	else if (a == 5 && b == 5 && c == 7)
		cout << "YES"<<endl;
	else
		cout << "NO"<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
#include <math.h>
#include <string.h>
#include <map>
#include <bitset>

#define Z class
#define ln cout<<'\n'
#define ll long long
#define ld long double
#define rep(i, n) for(int i = 0; i < (n); ++i)
//ASCII a=97, A=65
// int H[N]; rep(i,N) scanf("%d", &H[i]);
// int max_x = *std::max_element(x.begin(), x.end());
// int min_y = *std::min_element(y.begin(), y.end());
// sort(vec.begin(), vec.end()); std::greater<>()
// reverse(vec.begin(), vec.end());
// scanf("%s",s);
// printf("%d\n",end-start+1);
// ceil (a + (b - 1)) / b

//===== グラフ受け取り =====//
/*
    int N, M; cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);

        // 無向グラフの場合は以下を追加
        // G[b].push_back(a);
    }
    
    // == 重み付きグラフ == //
    
    struct Edge {
        int to; 
        int weight; 
        Edge(int t, int w) : to(t), weight(w) { }
    };
    using Graph = vector<vector<Edge>>;
    int main() {
        int N, M; cin >> N >> M;
        Graph G(N);
        for (int i = 0; i < M; ++i) {
            int from, to, weight;
            cin >> from >> to >> weight;
            G[from].push_back(Edge(to, weight));
        }
    }
*/    

using namespace std;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
using pll = pair<long long, long long>;

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<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}

ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
const long long INF = 1LL << 60;

int main(){
    ll A,B,C,D; cin >> A >> B >> C >> D;
    ll C_cracker = (B / C - A / C);
    if(A%C==0) C_cracker++;
    ll D_cracker = (B / D - A / D);
    if(A%D==0) D_cracker++;
    ll CD_LCD = C * D / GCD(C,D);
    ll CD_LCD_cracker = B / CD_LCD - A / CD_LCD;
    if(A%CD_LCD==0) CD_LCD_cracker++;
    cout << B - A + 1 - (C_cracker + D_cracker - CD_LCD_cracker) << endl;
}






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

vector<int>vec[100005];
int visited[100005]={0};
int p[100005]={0};

int dfs(int v,int d)
{
	visited[v]=1;
	for(int j=0;j<vec[v].size();j++)
	{
		if(!visited[vec[v][j]])
		{
			p[v]=max(p[v],dfs(vec[v][j],v));
		}
		else
			p[v]=max(p[v],p[vec[v][j]]+1);
	}
	
	return p[v]+1;
}

int main() {
	// your code goes here
	int maxi=0;
	int n,m;
	cin>>n>>m;
	int a,b;
	p[0]=-1;
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		vec[a].push_back(b);
	}
	
	for(int i=1;i<=n;i++)
	{
		dfs(i,0);
	}
	
	for(int i=1;i<=n;i++)
	{
		maxi=max(maxi,p[i]);
		
	}
	cout<<maxi;
	return 0;
}

Measured memory_bytes: 8576
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ll long long
inline ll read()
{
	ll x=0,w=0;char ch=getchar();
	while(!isdigit(ch))w|=ch=='-',ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return w?-x:x;
}
int n;
int main()
{
    n=read();reg int i,x,y=1;
    for(i=1;i<=n;++i)
    {
        x=read();
        if(x==y)++y;
    }
    if(y==1)puts("-1");
    else cout<<n-y+1;
	return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <utility>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <functional>
#include <stdlib.h>
using namespace std;
signed main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<int> bin[200004];
	vector<int> toutatu;
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		if (a == 1)toutatu.push_back(b);
		if (b == 1)toutatu.push_back(a);
		bin[a].push_back(b);
		bin[b].push_back(a);
	}
	int judge = 0;
	for (int i = 0; i < toutatu.size(); i++) {
		for (int j = 0; j < bin[toutatu[i]].size(); j++) {
			if (bin[toutatu[i]][j] == n) { judge = 1; break; }
		}
	}
	if (judge == 1)cout << "POSSIBLE";
	else cout << "IMPOSSIBLE";
	return 0;
}

Measured memory_bytes: 12392
#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 int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n;
P pts[12525];
const Real PI = 4.0*atan(1.0);

Real dot(P a, P b){return real(a*conj(b));}
Real cross(P a, P b){return imag(a*conj(b));}

P getPoint(P s, P v1, P t, P v2){
  P n = v2*exp(P(0,PI/2.0));
  Real x = dot(n,t-s) / dot(n,v1);
  return s + v1*x;
}

Real f(Real th, int id){
  return cos(th)*pts[id].real() + sin(th)*pts[id].imag();
}

int main(){
  double rnd = rand() / 65536.0;
  scanf("%d",&n);
  REP(i,n){
    int x,y;
    scanf("%d%d",&x,&y);
    pts[i] = P(x,y) * exp(P(0,rnd));
  }
  vector<double> queries;
  map<double,int> qans;
  REP(i,n){
    P a = pts[i], b = pts[(i+1)%n];
    P v = b-a;
    v *= exp(P(0,-PI/2.0));
    double th = arg(v);
    queries.push_back(th);
    th += PI*2.0/3.0;
    while(th>PI)th -= 2.0*PI;
    queries.push_back(th);
    th += PI*2.0/3.0;
    while(th>PI)th -= 2.0*PI;
    queries.push_back(th);
  }
  sort(ALL(queries));
  // query
  int cur = 0;
  REP(i,n)if(pts[i].real() < pts[cur].real()){
    cur = i;
  }
  REP(i,queries.size()){
    double th = queries[i];
    while(true){
      int ni = (cur + 1) % n;
      if(f(th,cur) < f(th,ni)){
        cur = ni;
      }else{
        break;
      }
    }
    qans[th] = cur;
  }
  // calc
  double ans = 1e25;
  REP(i,n){
    P a = pts[i], b = pts[(i+1)%n];
    P v = b-a;
    v *= exp(P(0,-PI/2.0));
    double th = arg(v);
    int sid = qans[th];
    double th2 = th + PI*2.0/3.0;
    while(th2>PI)th2 -= 2.0*PI;
    int tid = qans[th2];
    double th3 = th2 + PI*2.0/3.0;
    while(th3>PI)th3 -= 2.0*PI;
    int uid = qans[th3];
    P c1 = getPoint(pts[sid], exp(P(0,th+PI/2.0)), pts[tid], exp(P(0,th2+PI/2.0)));
    P c2 = getPoint(pts[sid], exp(P(0,th+PI/2.0)), pts[uid], exp(P(0,th3+PI/2.0)));
    CHMIN(ans, abs(c1-c2));
  }
  printf("%.9f\n",ans);
  return 0;
}



Measured memory_bytes: 5784
#include <stdio.h>
#include <stdlib.h>
#define NIL NULL
#define Yes 7
#define No -7

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node * Node;

Node root;

void insert(int);
void inorder(Node);
void preorder(Node);
Node find(int);
void delete(Node);
Node Mini(Node);
Node getSuc(Node);

int main(){

  int i = 0;
  int n = 0, key = 0;
  char com[7];
  Node u;
  
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    
    scanf("%s",com);
    
    if(com[0] == 'i'){
      scanf("%d",&key);
      insert(key);
    }
    else if(com[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if(com[0] == 'f'){
      scanf("%d",&key);
      if(find(key) != NIL)printf("yes\n");
      else printf("no\n");
    }
    else if(com[0] == 'd'){
      scanf("%d",&key);
      delete(find(key));
    }
    
  }
  
  return 0;
}

void insert(int key){

  Node y = NIL; /* x's parent  */
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = key;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    
    y = x;    /* settei parent */
    
    if(z->key < x->key)x = x->left;   /* move to left child */
    else x = x->right;  /* move to right child */
    
  }

  z->parent = y;

  if(y == NIL)root = z;/* if T is empty  */
  else if(z->key < y->key)y->left = z; /* y'left is z */
  else y->right = z; /* y'right is z */

}

void inorder(Node u){
  
  if(u == NIL)return;
  
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
  
}

void preorder(Node u){
  
  if(u == NIL)return;
  
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
  
}

Node find(int key){
  Node x = root;

  while(x != NIL){
    if(key == x->key)return x;
    if(x->key < key)x = x->right;
    else x = x->left;
  }
  return NIL;
}

void delete(Node z){

  Node x, y;
  
  //削除する対象を節点yとする
  if(z->left == NIL || z->right == NIL)y = z;//z ko nasi or ko 1
  else y = getSuc(z);//z no ko 2 -> z next

  //kimeru y no ko
  if(y->left != NIL)x = y->left;
  else x = y->right;

  if(x != NIL)x->parent = y->parent;

  if(y->parent == NIL)root = x;
  else if(y == y->parent->left)y->parent->left = x;
  else y->parent->right = x;

  if(y != z)z->key = y->key;
  
}

Node getSuc(Node x){

  Node y;
  
  if(x->right != NIL)return Mini(x->right);

  y = x->parent;
  
  while(y != NIL && x == y->right){

    x = y;
    y = y->parent;
    
  }

  return y;
  
}

Node Mini(Node x){

  while(x->left != NIL){
    x = x->left;
  }

  return x;
  
}



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

#define SZ(x) ((int(x.size())))

using namespace std;

stack <char> s;
string X;

int main()
{
	cin >> X;
	for (int i = 0; i < X.length(); i++)
	{
		if (X[i] == 'S')
			s.push ('S');
		else
		{
			if (!s.empty() && s.top() == 'S')
				s.pop();
			else
				s.push ('T');
		}
	}
	cout << SZ(s);
	return 0;
}

Measured memory_bytes: 644
#include <iostream>
#include<iomanip>
#include <string>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<math.h>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<cstdlib>
#define INF long long int(1e18+1)
#define MAX 200001
#define rep(i,n,m) for(int i=n;i<m;i++)

using namespace std;

int main() {
	string s, t;
	cin >> s >> t;

	int ans = MAX, x = 0;
	if(s.size()==t.size()){
		rep(i, 0, s.size())if (s[i] != t[i])x++;
		ans = x;
	}
	else {
		rep(i, 0, s.size() - t.size()) {
			x = 0;
			rep(j, 0, t.size()) if (s[i + j] != t[j])x++;
			ans = min(ans, x);
		}
	}
	cout << ans << endl;
}



Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <algorithm>
#include <deque>
using namespace std;
string L(string);
string S(string);
string sa(string,string);
int main(void)
{
	int count;
	string n;

	while(1){
		cin >> n;
		if(n=="0000") break;
		if(n=="1111"||n=="2222"||n=="3333"||n=="4444"||n=="5555"||n=="6666"||n=="7777"||n=="8888"||n=="9999") {
			cout << "NA" << endl;
			continue;
		}
		count=0;
		while(n!="6174"){
			n=sa(L(n),S(n));
			count+=1;
		}
		cout << count << endl;
	}
	return 0;
}
string S(string n)
{
	string s;
	deque<char> dn;
	for(int i=0;i<4;i++) dn.push_back(n[i]);
	sort(dn.begin(),dn.end());
	for(int i=3;0<=i;i--){
		s+=dn[i];
		dn.pop_back();
	}
	return s;
}
string L(string n)
{
	string l;
	deque<char> dn;
	for(int i=0;i<4;i++) dn.push_back(n[i]);
	sort(dn.begin(),dn.end());
	for(int i=0;i<4;i++){
		l+=dn[i];
	}
	return l;
}
string sa(string l,string s)
{
	string n;
	int lnum=0,snum=0,num,b=1;
	for(int i=3;0<=i;i--){
		lnum+=(b*(l[3-i]-'0'));
		snum+=(b*(s[3-i]-'0'));
		b*=10;
	}
	num=lnum-snum;
	for(int i=0;i<4;i++){
		b/=10;
		n+=((num/b)%10+'0');
	}
	//cout << n << endl;
	return n;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define REPD(i,a,b) for (int i=(a);i<=(b);i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef set<int> si;
typedef vector<si> vsi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pi;
typedef queue<int> qi;
typedef queue<pi> qpi;
typedef pair<ll, ll> pll;
typedef queue<pll> qpll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const int mod = 1000000007;
const int INF = 1001001001;
// 小数点　<< fixed << setprecision(0) <<
// sort降順　sort(ALL(),greater<int>());
// 円周率　M_PI
// 文字判定　isupper islower
// 文字変換　
// 順列　do {} while(next_permutation(ALL(X)));
// 最大値　LLONG_MAX
// a内でx以上　auto iter = lower_bound(ALL(a), x);
// a内でxより大きい　auto iter = upper_bound(ALL(a), x);
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};
typedef struct edge se;
typedef vector<edge> ve;
unsigned Euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return Euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int digit_sum(int n) {
  int sum=n%10;
  while(n!=0) {
    n/=10;
    sum+=n%10;
  }
  return sum;
}

vpll PrimeFactorization(ll n) {
  vpll res;
  for (ll i=2; i*i<=n; i++) {
    if(n%i!=0) continue;
    ll ex=0;
    while(n%i==0) {
      ex++;
      n/=i;
    }
    res.push_back(pll(i,ex));
  }
  if(n!=1) res.push_back(pll(n,1));
  return res;
}




int main() {
  char s[200001];
  cin >> s;
  int n=strlen(s);
  int st=0,go=0;
  REP(i,n) {
    if(s[i]=='A') {
      st=i;
      break;
    }
  }
  REP(i,n) {
    if(s[n-1-i]=='Z') {
      go=n-1-i;
      break;
    }
  }
  cout << go-st+1 << endl;
  return 0;
}


Measured memory_bytes: 3780
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;
// ceil() 切り上げ, floor() 切り捨て
// next_permutation(all(x))

int		main(void)
{
	ll n, k;
	cin >> n >> k;

	vpii S(n, pair<int, int>(0, 0));
	for (int i = 0; i < n; i++)
		cin >> S[i].first >> S[i].second;
	sort(all(S));

	ll sum = 0;
	for (int i = 0; i < n; i++)
	{
		sum += S[i].second;
		if (sum >= k)
		{
			cout << S[i].first << endl;
			return 0;
		}
	}
	return 0;
}



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

using namespace std;
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define all(v) v.begin(),v.end()
#define sz(v)  v.size()


void fast() {

    cin.tie(0);
    cin.sync_with_stdio(0);
}



int main() {
    fast();
    ll n;cin>>n;
    map<string,ll>ma;
    vector<string>v;
    for (int i = 0; i <n ; ++i) {
        string s;cin>>s;
        sort(all(s));
        if(!ma[s])v.push_back(s);
        ma[s]++;
    }
    ll ans=0;
    for (int j = 0; j <v.size() ; ++j) {
        ll freq=ma[v[j]];
        ans+=(freq*(freq-1))/2;
    }
    cout<<ans;
}


Measured memory_bytes: 16628