akhauriyash/Code-Regression huggingface dataset:
using System;

namespace BrickBreak
{
    class Program
    {
        static void Main(string[] args)
        {
            var count = int.Parse(Console.ReadLine());
            var nums = Console.ReadLine().Split(' ');

            var next = 1;
            foreach (var num in nums)
            {
                if (num == next.ToString())
                {
                    next++;
                }
            }
            var k = next - 1;
            if (k == 0)
            {
                Console.WriteLine(-1);
            }
            else
            {
                Console.WriteLine(count - k);
            }

        }
    }
}


Measured memory_bytes: 35292
n = int(input())
a = list(map(int,input().split()))
import collections
c = collections.Counter(a)
ans = 0
for i in list(c.values()):
    ans += i*(i-1)//2
for i in range(n):
    print(ans - c[a[i]]*(c[a[i]]-1)//2 + (c[a[i]]-1)*(c[a[i]]-2)//2)
    

Measured memory_bytes: 26268
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#pragma GCC optimize("Os")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(int i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcountll(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
using namespace std;
ll gcd(ll a, ll b)
{
    return (b?gcd(b,a%b):a);
}
ll P(ll B, ll power, ll modulo)
{
    ll ans=1LL;
    while(power>0LL)
    {
        if(power%2LL==1LL)
        {
            ans=(ans*B)%modulo;
        }
        B=(B*B)%modulo;
        power/=2LL;
    }
    return ans;
}
bool isPrime(ll n)
{
    if(n<=1LL)
    {
        return false;
    }
    if(n<=3LL)
    {
        return true;
    }
    if(n%2==0LL || n%3==0LL)
    {
        return false;
    }
    for(ll i=5LL; (i*i)<=n; i+=6LL)
    {
        if(n%i==0LL || n%(i+2LL)==0LL)
        {
            return false;
        }
    }
    return true;
}
void vok()
{
    FAST
    FO
    FI
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("error.txt","w",stderr);
    #endif
}
int main()
{
    vok();
    int l,r,d;
    IN l>>r>>d;
    int ans=0;
    loop(i,l,r+1)
    {
        if(i%d==0)
        {
            ans++;
        }
    }
    OUT ans<<endl
    return 0;
}

Measured memory_bytes: 3644
import java.util.Scanner;

class Main {

    String Name;
    int V;
    boolean T;

    Main(String Name, int V, boolean T) {
        this.Name = Name;
        this.V = V;
        this.T = T;
    }

    public static void main(String[] args) {
        Scanner Input = new Scanner(System.in);
        int N = Input.nextInt();
        Main A[] = new Main[N];
        for (int I = 0; I < N; I++) {
            A[I] = (new Main("B" + I, Input.nextInt() - 1, false));
        }
        int C = 1;
        boolean TF = false;
        int X = A[0].V;
        A[0].T = true;
        while (!TF) {

            if (A[X].Name.equals("B1")) {
                System.out.println(C);
                TF = true;
            } else if (A[X].T) {
                System.out.println("-1");
                TF = true;
            }

            A[X].T = true;
            X = A[X].V;
            C++;
        }

    }

}
//<<< Copying >>> Alert
//If(PersonCopy){System.out.print("You Are Not Learning");


Measured memory_bytes: 68428
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif

#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define debug(x) cerr << #x << " = " << x << endl;

const int MOD=1e9+7;
const int INF=1<<29;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" ";}
inline int powerexp(int a,int b,int m=MOD){int res=1;while(b){if(b&1)res=res*a%m;a=a*a%m,b>>=1;}return res%m;}
inline int modinv(int a){return powerexp(a,MOD-2,MOD);}
inline int lcm(int a,int b){int g=__gcd(a,b);return a/g*b;}

//-------------------< start here >-------------------------//
int calc(string s){
   int n=(int)s.length();
   int ans=-INF;
   for(int i=1;i<n;i++){
	    int cnt=0;
	    for(char c='a';c<='z';c++){
		    bool left=false,right=false;
		    for(int j=0;j<i;j++){if(s[j]==c)left=true;}
		    for(int j=i;j<n;j++){if(s[j]==c)right=true;}
		    if(left && right){
			   cnt++;	
			}	
		 } 
	 ans=max(ans,cnt);
	  }
	return ans;
}
void solve(){
      string s;
      int n;
      cin>>n;
      cin>>s;
      int ret=calc(s);
      cout<<ret<<endl;
}
//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
   IOS;
   solve();
   #ifdef LOCAL_DEFINE
   cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
   #endif
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
struct cc
{
	int x,y;
	bool operator<(cc w)const{return x<w.x;}
}pos[200007];
vector<int> ans;
int main()
{
	int x1,y1,x2,y2,x,y,n,xs=1,ys=1,pp=0;
	scanf("%d%d",&x1,&y1);
	scanf("%d%d",&x2,&y2);
	if(x1>x2)xs=-1,x1*=-1,x2*=-1;
	if(y1>y2)ys=-1,y1*=-1,y2*=-1;
	scanf("%d",&n);
	for(int i=0;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		x*=xs,y*=ys;
		if(x<x1||x2<x||y<y1||y2<y)continue;
		pos[pp++]={x,y};
	}
	sort(pos,pos+pp);
	for(int i=0;i<pp;++i){
		int v=pos[i].y;
		if(!ans.size()||v>ans[ans.size()-1])ans.push_back(v);
		else *std::lower_bound(ans.begin(),ans.end(),v)=v;
	}
	double val=0;
	if(std::min(y2-y1,x2-x1)+1==ans.size()){
		val+=10*acos(-1)-20;
		ans.pop_back();
	}
	val+=(y2-y1+x2-x1)*100.-(20-acos(-1)*5)*ans.size();
	printf("%.15f",val);
	return 0;
}

Measured memory_bytes: 2936
#include <bits/stdc++.h>
#define len(x) (int) (x.size())
using namespace std;
typedef long long ll;

// O(sqrt(num))
vector<pair<ll, ll>> find_prime_factors(ll num) {
    vector<pair<ll, ll>> ans;
    ll exponent = 0;
    while(num % 2 == 0) {
        num /= 2;
        exponent++;
    }
    if(exponent != 0)
        ans.push_back({2, exponent});
    
    for(ll i = 3; i * i <= num; i+= 2) {
        exponent = 0;
        while(num % i == 0) {
            num /= i;
            exponent++;
        }
        if(exponent != 0)
            ans.push_back({i, exponent});
    }

    if(num > 1) // Importante: caso em que n é primo
        ans.push_back({num, 1});
    
    return ans;
}

int main(){
    ll N;
    cin >> N;
    vector<pair<ll, ll>> factors = find_prime_factors(N);

    ll ans = 0;
    for(auto f : factors) {
        ll aux = 1, j = 1;
        for(ll i = 1; i <= f.second; i += j) {
            aux *= f.first;
            N /= aux;
            ans++;
            j++;
        }
    }
    cout << ans << '\n';
    
    return 0;
}

// 2^6
// 1, 2, 3


Measured memory_bytes: 3640
#include <iostream>
using namespace std;
int main(){
    int N, A[3][3], b;
    bool flag = false;
    for (int i=0; i<3; i++){
        for (int j=0; j<3; j++){
            cin >> A[i][j];
        }
    }
    cin >> N;
    for (int k=0; k<N; k++){
        cin >> b;
        for (int i=0; i<3; i++){
            for (int j=0; j<3; j++){
                if (A[i][j] == b) A[i][j] = 0;
            }
        }
    }
    for (int i=0; i<3; i++){
        if (A[i][0]==0 && A[i][1]==0 && A[i][2]==0) flag = true;
        else if (A[0][i]==0 && A[1][i]==0 && A[2][i]==0) flag= true;
    }
    if (A[0][0]==0 && A[1][1]==0 && A[2][2]==0) flag = true;
    else if (A[0][2]==0 && A[1][1]==0 && A[2][0]==0) flag= true;
    
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pi acos(-1)
#define ll long long
#define pii pair<ll,ll>
#define debug(a) cout<<a<<'\n'
#define maxn 100009 /// Still trying to be normal
#define MOD 1000000007
#define F first
#define S second
#define rep(i, a, b) for(ll i = a; i < (b); ++i)
#define per(i, b, a) for(ll i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
using namespace std;
const ll INF = 1e17 + 9;

ll soma(ll a,ll b){
    if(a+b>MOD) return a+b-MOD;
    else return a+b;
}
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll sub(ll a,ll b){
    return (a-b+MOD)%MOD;
}
ll fastpow(ll a,ll b){
    ll ans=1;
    for(;b>=1;b/=2){
        if(b&1)ans=mult(ans,a);
        a=mult(a,a);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,k;
    cin>>n>>k;
    ll ans=0;
    // cout<<fastpow(2,3)<<endl;
    rep(i,k,n+2){
        ll dentro=soma(n,soma(sub(n,i),1));
        ll qtd=i;
        ll inverse=fastpow(2,MOD-2);
        ll res1=mult(mult(dentro,qtd),inverse);
        // cout<<i<<" "<<res1<<" "<<dentro<<" "<<qtd<<endl;
        ll dentro2=soma(0,sub(i,1));
        ll qtd2=i;
        ll res2=mult(mult(dentro2,qtd2),inverse);
        ans=soma(ans,soma(sub(res1,res2),1));
        // cout<<ans<<endl;
    }
    cout<<ans<<'\n';
    return 0;   
}           


Measured memory_bytes: 3612
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 200010
using namespace std;
struct edge{
	int l,r;
}c[maxn];
bool cmp(edge a,edge b)
{
	if(a.l==b.l) return a.r>b.r;
	return a.l<b.l;
}
struct tree{
	int l,r,mi;
	tree *ls,*rs;
	tree()
	{
		ls=rs=NULL;
		l=r=0;
		mi=0x3f3f3f3f;
	}
	void update()
	{
		mi=min(ls->mi,rs->mi);
	}
	void build(int lx,int rx)
	{
		l=lx;r=rx;
		if(l==r) {
			mi=(l==0?0:0x3f3f3f3f);
			return;
		}
		int mid=(l+r)>>1;
		(ls=new tree)->build(lx,mid);
		(rs=new tree)->build(mid+1,rx);
		update();
	}
	void modify(int pos,int num)
	{
		if(l==r) {
			mi=min(mi,num);
			return;
		}
		int mid=(l+r)>>1;
		if(pos<=mid) ls->modify(pos,num);
		else rs->modify(pos,num);
		update();
	}
	int query(int lx,int rx)
	{
		if(l==lx&&r==rx) return mi;
		int mid=(l+r)>>1;
		if(lx>mid) return rs->query(lx,rx);
		else if(rx<=mid) return ls->query(lx,rx);
		else return min(ls->query(lx,mid),rs->query(mid+1,rx));
	}
}*xtr;
int n,q,b[maxn];
int main()
{
	scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;++i) scanf("%d",&b[i]),ans+=(1-b[i]);
	scanf("%d",&q);
	for(int i=1;i<=q;++i)
	scanf("%d%d",&c[i].l,&c[i].r);
	sort(c+1,c+q+1,cmp);
	(xtr=new tree)->build(0,n);
	int p=1;
	for(int i=1;i<=n;++i)
	{
		for(;c[p].l==i;++p)
		xtr->modify(c[p].r,xtr->query(i-1,c[p].r));
		xtr->modify(i,xtr->query(i-1,i-1)+(b[i]==0?-1:1));
	}
cout<<ans+xtr->query(n,n);
return 0;
}





Measured memory_bytes: 21376
import random
import time
import copy
import math
start=time.time()
d=int(input())
c=list(map(int,input().split()))
s=[]
cli=[]
for i in range(d+1):
  ch=[]
  for j in c:
    ch.append(i*j)
  cli.append(ch)
for i in range(d):
  s.append(list(map(int,input().split())))
last=[0]*26
solution=[]
score=0
for day in range(1,d+1):
  co=[]
  dla=[]
  down=0
  for (i,j) in zip(last,c):
    down+=(day-i)*j
  for (i,j) in zip(last,c):
    dla.append(down-(j*(day-i)))
  for con in range(26):
    co.append(s[day-1][con]-dla[con]*c[con])
  choice=co.index(max(co))
  score+=co[choice]
  last[choice]=day
  solution.append(choice)

stemp=10000
etemp=1
def tem():
  return stemp-((stemp-etemp)*(time.time()-start)/1.9)
while time.time()-start<1.9:
  
  sc=0
  sol=copy.deepcopy(solution)
  for x in [random.randrange(d) for i in range(5)]:
    sol[x]=random.randrange(26)
  last=[0]*26
  for (day,i) in zip(range(1,d+1),sol):
    sc+=s[day-1][i]
    last[i]=day
    for (i,j) in zip(last,range(26)):
      sc-=cli[i][j]
  try:
    prob = math.exp((sc-score)/tem())
  except:
    prob=0
  #print("{} {}".format(sc,prob))
  if prob>random.random():
    solution=copy.deepcopy(sol)
    score=sc
for i in solution:
  print(i+1)
#print(sco)

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

int main()
{
  int x;
  cin >> x;
  // x以上の数値について、xの平方根以下の素数で割り切れないxが、x以上の最小の素数
  while (true)
  {
    int n = sqrt(x);
    bool is_prime = true;

    for (int i = 2; i < n; i++)
    {
      if (x % i == 0)
      {
        is_prime = false;
        break;
      }
    }

    if (is_prime)
      break;

    x++;
  }

  cout << x << endl;
}


Measured memory_bytes: 256
let f n k =
  let rec g n' tmp =
    if n' = 0 then tmp
    else if tmp < k then g (n' - 1) (tmp * 2)
    else g (n' - 1) (tmp + k)
  in
  g n 1

let () = Scanf.scanf "%d\n%d" f |> Printf.printf "%d\n"

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <stdlib.h>
#include <cstdlib>
using namespace std;


int main(){
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	
	// a * c
	// a * d
	// b * c
	// b * d;
	long long a_c =  (long long)a * c;
	long long a_d =  (long long)a * d;
	long long b_c =  (long long)b * c;
	long long b_d =  (long long)b * d;
	long long ans = a_c;
	if( ans < a_d ) ans = a_d;
	if( ans < b_c ) ans = b_c;
	if( ans < b_d ) ans = b_d;
		
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3608
A = {}

N = input()
for i in range(N):
  s = raw_input()
  if s not in A:
    A[s] = 0
  A[s] += 1
M = input()
for i in range(M):
  t = raw_input()
  if t not in A:
    A[t] = 0
  else:
    A[t] -= 1
print max(A.values()+[0])


Measured memory_bytes: 2568
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <thread>
#include <tuple>
#include <limits>

using namespace std;

int main() {
  int m, d;
  scanf("%d%d", &m, &d);
  int ans = 0;
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= d; j++) {
      if (j >= 10) {
        int d10 = j / 10;
        int d1 = j % 10;
        if (d1 >= 2 && d10 >= 2 && d1*d10 == i) {
          ans++;
        }
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
int main()
{
    int A,B,C;
    scanf("%d%d%d",&A,&B,&C);
    if((A == B) && (A != C))printf("Yes\n");
    else if((B == C) && (B != A))printf("Yes\n");
    else if((C == A) && (C != B))printf("Yes\n");
    else { printf("No\n"); }
    return 0;
}

Measured memory_bytes: 128
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

const ll INF = 1LL << 50;

const ll mod = 1000000007;

int main() {
  ll m, k;
  cin >> m >> k;

  ll ttm = 1 << m;

  if (ttm <= k) {
    puts("-1");
    return 0;
  }

  if (m == 0) {
    if (k == 0) {
      puts("0 0");
      return 0;
    } else {
      puts("-1");
      return 0;
    }
  }

  if (m == 1) {
    if (k == 0) {
      puts("0 0 1 1");
      return 0;
    } else {
      puts("-1");
      return 0;
    }
  }

  rep(i, ttm){
    if(i != k){
      printf("%lld ", i);
    }
  }
  printf("%lld ", k);
  rep(i, ttm){
    if(ttm - 1 - i != k){
      printf("%lld ", ttm - 1 - i);
    }
  }
  printf("%lld\n", k);

  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;


signed main() {
 string s,t;
 cin>>s>>t;
 int p[s.size()],q[t.size()];
 if(s[0]=='A')p[0]=1;
 else p[0]=2;
 for(int i=1;i<s.size();i++){
   if(s[i]=='A')p[i]=p[i-1]+1;
   else p[i]=p[i-1]+2;
 }
 if(t[0]=='A')q[0]=1;
 else q[0]=2;
 for(int i=1;i<t.size();i++){
   if(t[i]=='A')q[i]=q[i-1]+1;
   else q[i]=q[i-1]+2;
 }
int Q,a,b,c,d,x,y;
cin>>Q;
for(int i=0;i<Q;i++){
  cin>>a>>b>>c>>d;
  x=p[b-1];
  if(a>1)x-=p[a-2];
  y=q[d-1];
  if(c>1)y-=q[c-2];
  //cerr<<x<<' '<<y;
  if(x%3==y%3)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}
return 0;
}


Measured memory_bytes: 2432
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
int main(){
  
  map<int,int> cnt;
  int n;
  cin >> n;
  //vector<int> data(n);
  rep(i,0,n){
      cnt[i] = 0;
  }
  rep(i,0,n-1){
      int a;
      
      cin >> a;
      
    cnt.at(a-1)++;
      
      
  }
    rep(i,0,n){
        cout << cnt.at(i) << endl;
    }
  
  return 0;
}

Measured memory_bytes: 13008
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define N 110000
#define INF 0x3f3f3f3f
#define _for(i, a, b) for (int i = (a); i < (b); ++i)

typedef long long ll;

int a[N], dif[N];

int main() {
    int n, m;
    while (scanf("%d%d", &m, &n) != EOF) {
        int res = 0;
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        sort(a, a + n);
        for (int i = 0; i < n - 1; ++i) dif[i] = a[i + 1] - a[i];
        n = n - 1; m = m - 1;
        sort(dif, dif + n);
        for (int i = 0; i < n - m; ++i) res += dif[i];
        printf("%d\n", res);
    }
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector< vector< double > > dp(n + 1, vector< double > (n + 1));
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        double prob;
        cin >> prob;
        dp[i][0] = dp[i - 1][0] * (1 - prob);
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j - 1] * prob + dp[i - 1][j] * (1 - prob);
        }
    }
    double ans = 0.0;
    for (int i = 0; i <= n; i++) {
        if (i >= n / 2 + 1) ans += dp[n][i];
    }
    cout.precision(9);
    cout << fixed << ans << "\n";
}

Measured memory_bytes: 73652
import java.util.*;

public class Main {

    public static void main(String[] args) {
        final long MOD = (long) (1e9) + 7;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();

        long ans = modpow(2, n, MOD);
        long nCa = 1;
        long prod_a = 1;
        for (long i = 1; i <= a; i++) {
            nCa = (nCa * (n - i + 1)) % MOD;
            prod_a = (prod_a * i) % MOD;
        }
        nCa = (nCa * modinv(prod_a, MOD)) % MOD;

        long nCb = 1;
        long prod_b = 1;
        for (long i = 1; i <= b; i++) {
            nCb = (nCb * (n - i + 1)) % MOD;
            prod_b = (prod_b * i) % MOD;
        }
        nCb = (nCb * modinv(prod_b, MOD)) % MOD;

        ans = (ans - 1 - nCa - nCb + 3 * MOD) % MOD;

        System.out.println(ans);
    }

    static long modpow(long a, long n, long MOD) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                res = (res * a) % MOD;
            }
            a = (a * a) % MOD;
            n >>= 1;
        }

        return res;
    }

    static long modinv(long a, long MOD) {
        return modpow(a, MOD - 2, MOD);
    }
}



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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
ll A[101010];

int ok(int v) {
	if(v<0) return 0;
	ll sum=0;
	int i;
	for(i=0;i<N;i++) {
		if(i<=v) sum+=A[i];
		else {
			if(A[i]>sum*2) return 0;
			sum+=A[i];
		}
	}
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	
	int mi=N-1;
	for(i=19;i>=0;i--) if(ok(mi-(1<<i))) mi-=1<<i;
	
	cout<<N-mi<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,n) for(int i=(int)(n-1);i>=0;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define print(x) cout << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<int, P> PIP;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;
typedef set<int> S;

#define INF INT_MAX/3
#define MAX_N 1000000001

string dfs(string s) {
  string ss = "", tmp;
  int i = 0;
  while(i < s.length()) {
    if (s[i] == '[') {
      int flag = 1, j = i;
      while(j < s.length() && flag != 0) {
        j++;
        if (s[j] == '[') flag++;
        else if (s[j] == ']') flag--;
      }

      tmp = dfs(s.substr(i + 1, j - i - 1));
      reverse(all(tmp));
      ss += tmp;
      i = j;
    } else if (s[i] == '+' || s[i] == '-') {
      int flag = 0, j = i;
      while(j < s.length() && s[j] == '+' || s[j] == '-') {
        if (s[j] == '+') flag++;
        else if (s[j] == '-') flag--;
        j++;
      }

      if (s[j] == '?') ss += 'A';
      else ss += (char)((s[j] - 'A' + flag + 104) % 26 + 'A');
      i = j;
    } else {
      if (s[i] == '?') ss += 'A';
      else ss += s[i];
    }

    i++;
  }

  return ss;
}


int main(){
  cin.sync_with_stdio(false);
  string s;
  while(cin >> s, s[0] != '.') {
    cout << dfs(s) << endl;
  }

  return 0;
}

Measured memory_bytes: 3144
#!/usr/bin/env python3
#ABC44 C

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

n,a = map(int, input().split())
X = list(map(int,input().split()))
Y = list(map(lambda x:x-a, X))
d = defaultdict(int)
d[0] = 1
for y in Y:
    for k,v in list(d.items()):
        d[k+y] += v
print(d[0]-1)



Measured memory_bytes: 3572
#include<bits/stdc++.h> 
using namespace std; 
int main() { 

int a,b,c,d,a1,a2; 

scanf("%d%d%d%d" , &a,&b,&c,&d) ; 


a1= a*b; 
a2=c*d; 

if ( a1 >= a2 ) { 
 printf("%d" , a1 ) ;
 
} 
else { 
printf("%d" , a2) ;
}


return 0;
}

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

int main() {
	ios_base::sync_with_stdio( false );

	int n;
	cin >> n;

	deque<int> a;
	bool b = n & 1;

	for( int i = 0; i < n; ++i ) {
		int x;
		cin >> x;

		if( b ) {
			a.push_front( x );
		}
		else {
			a.push_back( x );
		}

		b = !b;
	}

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

	return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int run();
int main() {
#ifdef home
    freopen("i", "r", stdin);
    freopen("d", "w", stderr);
#endif
    cout.precision(15);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    run();
    return 0;
}

int run() {
    int a[10]={0};
    for(int i=1;i<=4;i++){
        int x;
        cin>>x;
        if(x<=9 && x>=1)
            a[x]=1;
    }
    bool ans=true;
    ans&=(a[1]);
    ans&=(a[4]);
    ans&=(a[7]);
    ans&=(a[9]);
    if(ans){
        cout<<"YES";
    }else cout<<"NO";



}








































Measured memory_bytes: 256
#include<algorithm>
#include<cstdio>
#define N 200000
using namespace std;
int a[N],b[N],i,l,m,n,r,x;
inline bool check(int o)
{
	for(i=0;i<n-o;i++)b[i]=a[o+i]-m;
	for(i=0;i<o;i++)b[n-o+i]=a[i];
	for(i=0;i<<1<n;i++)if(b[i]+b[n-i-1]<0)return false;
	return true;
}
int main()
{
	scanf("%d%d",&n,&m),r=n<<=1;
	for(i=0;i<n;i++)scanf("%d",a+i);
	for(sort(a,a+n);l<r;)check(l+r>>1)?r=l+r>>1:l=l+r+2>>1;
	for(check(l),i=0;i<n;i++)x=max(x,b[i]+b[n-i-1]);
	return 0*printf("%d\n",x);
}

Measured memory_bytes: 1664
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

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

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

    int n, q;
    cin >> n >> q;
    vector<vector<int>> graph(n);
    for(int i = 0; i < n - 1; ++i){
        int a, b;
        cin >> a >> b;
        --a, --b;
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }
    vector<int> c(n, 0);
    for(int i = 0; i < q; ++i){
        int p, x;
        cin >> p >> x;
        --p;
        c[p] += x;
    }
    auto dfs = [&](auto&& self, int from = 0, int par = -1, int S = 0) -> void {
        c[from] += S;
        S = c[from];
        for(int to : graph[from]){
            if(to == par)   continue;
            self(self, to, from, S);
        }
        return;
    };
    dfs(dfs);
    for(int i = 0; i < n; ++i){
        cout << c[i];
        cout << ((i == n - 1) ? '\n' : ' ');
    }
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

struct UnionFind {
    vector<int> par, rank, _size;
    UnionFind(int n):par(n), rank(n), _size(n, 1) { for (int i = 0; i < n; ++i) par[i] = i; }
    int find(int x) {
        if (par[x] == x) return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (rank[x] > rank[y]) swap(x, y);
        par[x] = y; _size[y] += _size[x];
        if (rank[x] == rank[y]) rank[y]++;
    }
    int size(int x) { return _size[find(x)]; }
    bool same(int x, int y) { return find(x) == find(y); }
};

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

    vector<int> A(M), B(M);
    rep(i, M) {
        cin >> A[i] >> B[i];
        A[i]--, B[i]--;
    }

    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());

    UnionFind uf(N);

    vector<ll> ans;
    ans.push_back((ll)N * (N-1) / 2);

    rep(i, M) {
        int a = A[i], b = B[i];

        ll res = ans.back();
        if (!uf.same(a, b)) {
            res -= (ll)uf.size(a) * uf.size(b);
        }
        ans.push_back(res);

        uf.unite(a, b);
    }

    repr(i, M) cout << ans[i] << endl;
}

Measured memory_bytes: 4212
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

pub trait InputValue {
    fn parse(s: &str) -> Self;
}

pub fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

pub fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

pub fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

// ===

fn main() {
    let (d, n): (i32, i32) = read();

    let mut div100 = 1;
    for i in 0..d {
        div100 *= 100;
    }

    let mut left = n;
    for i in 1..2000000 {
        if i % div100 == 0 && i % (div100 * 100) != 0 {
            left -= 1;
            if left == 0 {
                println!("{}", i);
                break;
            }
        }
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()

ll N, X;
vector<ll> memo(51, -1);
vector<ll> num(51);

ll dfs(int level) {
    if (memo[level] != -1 && X >= num[level]) {
        X -= num[level];
        return memo[level];
    }
    ll ret = 0;
    X--; // bun
    if (X > 0) ret += dfs(level - 1);
    if (X > 0) {
        // patty
        X--;
        ret++;
    }
    if (X > 0) ret += dfs(level - 1);
    if (X > 0) {
        // bun
        X--;
        memo[level] = ret;
    }
    return ret;
}

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

    memo[0] = 1;
    num[0] = 1;
    for (int i = 1; i <= 50; i++) num[i] = 2 * num[i-1] + 3;

    cin >> N >> X;
    cout << dfs(N) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=100010;
namespace T{
	const int E=N<<1;
	int to[E],bro[E],head[N],e=0;
	inline void init(){
		memset(head,-1,sizeof(head));
	}
	inline void ae(int u,int v){
		to[e]=v,bro[e]=head[u],head[u]=e++;
	}
	inline void add(int u,int v){
		ae(u,v),ae(v,u);
	}
	int dfs(int x,int fa){
		int cnt=0;
		for(int i=head[x],v;~i;i=bro[i]){
			if((v=to[i])!=fa){
				int tmp=dfs(v,x);
				if(tmp==-1)return -1;
				cnt+=tmp;
			}
		}
		return cnt<=1?1-cnt:-1;
	}
}
inline bool Main(){
	int n=ni;
	T::init();
	for(int i=1;i<n;T::add(ni,ni),i++);
	return T::dfs(1,0);
}
int main(){
	puts(Main()?"First":"Second");
	return 0;
}

Measured memory_bytes: 2176
// B

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll mod=1e9+7;
#define pa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};

int main(){
  int N,A[100001];
  cin>>N;
  for (int i(0);i<N;i++) cin>>A[i];
  sort(A,A+N);
  int cnt(1);
  int ans(0);
  for (int i(1);i<=N;i++){
    if(A[i] == A[i-1]){
      cnt++;
    }else{
      if (A[i-1] > cnt){
        ans += cnt;
      }else{
        ans += cnt - A[i-1];
      }
      cnt = 1;
    }
  }
  cout << ans << endl;
}




Measured memory_bytes: 640
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

surplus = []
short = []

for i in range(n):
    if a[i] > b[i]:
        surplus.append(a[i]-b[i])
    elif b[i] > a[i]:
        short.append(b[i]-a[i])

surplus = sorted(surplus)
taken = False
cnt = 0
for i in range(len(short)):
    cost = short.pop()
    cnt += 1

    while cost > 0:
        if len(surplus) == 0:
            print(-1)
            exit()

        take = min(cost, surplus[-1])
        cost -= take
        surplus[-1] -= take

        if not taken:
            taken = True
            cnt += 1

        if surplus[-1] == 0:
            surplus.pop()
            taken = False

print(cnt)

Measured memory_bytes: 24256
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[n+1];
        for(int i=1; i<=n; i++) {
            int b = sc.nextInt();
            a[b] = i;
        }
        for(int i=1; i<=n; i++) {
            System.out.print(a[i]);
            if(i != n) System.out.print(" ");
        }
        System.out.println();
    }
}

Measured memory_bytes: 59844
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1000000000;

int N, M;

int main() {

int sum = 0;

    cin >> N >> M;
    vector<int> A(N, INF);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sum += A[i];
    }

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

if (A[M - 1] >= (double)sum / (double)(4 * M)) {
    printf("Yes\n");
} else {
     printf("No\n");
}

return 0;

}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
    char ch = getchar();
    int x = 0, flag = 1;
    for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
    for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x * flag;
}
void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x >= 10) write(x / 10);
    putchar(x % 10 + 48);
}

const int Maxn = 200009, Maxc = 2009, Mod = (int)1e9 + 7;
int n, a[Maxn], b[Maxn], fac[Maxn], invFac[Maxn];
LL dp[Maxc * 2][Maxc * 2];
inline pair<int, int> getPos(int x, int y) { return make_pair(x + 2000, y + 2000); }

int fpm(int base, int tims) {
	int r = 1;
	while (tims) {
		if (tims & 1) r = 1ll * r * base % Mod;
		base = 1ll * base * base % Mod;
		tims >>= 1;
	}
	return r;
}

void init() {
	n = read();
	rep (i, 1, n) a[i] = read(), b[i] = read();
	rep (i, 1, n) {
		pair <int, int> s = getPos(-a[i], -b[i]);
		dp[s.first][s.second] += 1;
	}

	fac[0] = 1;
	rep (i, 1, Maxn - 1) fac[i] = fac[i - 1] * 1ll * i % Mod;
	invFac[Maxn - 1] = fpm(fac[Maxn - 1], Mod - 2);
	drep (i, Maxn - 2, 0) invFac[i] = invFac[i + 1] * (i + 1ll) % Mod;
}

int C(int n, int m) {
	if (n < m) return 0;
	return fac[n] * 1ll * invFac[m] % Mod * invFac[n - m] % Mod;
}

void solve() {
	rep (i, 0, 4000)
		rep (j, 0, 4000) 
			(dp[i][j] += ((i > 0 ? dp[i - 1][j] : 0) + (j > 0 ? dp[i][j - 1] : 0)) % Mod) %= Mod;

	LL ans = 0;
	rep (i, 1, n) (ans += dp[2000 + a[i]][2000 + b[i]]) %= Mod;
	rep (i, 1, n) (ans += Mod - C(2 * (a[i] + b[i]), 2 * a[i])) %= Mod;

	cout << ans * 1ll * invFac[2] % Mod << endl;
}

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

	init();
	solve();

#ifdef Qrsikno
    debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
    return 0;
}



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

int main()
{
  i64 m;
  cin >> m;
  vector<pair<i64, i64>> d(m);
  for (i64 i = 0; i < m; i++)
    cin >> d[i].first >> d[i].second;
  i64 sum = 0, sumc = 0;
  for (i64 i = 0; i < m; i++)
  {
    sum += d[i].first * d[i].second;
    sumc += d[i].second;
  }
  cout << (sumc - 1) + (sum - 1) / 9 << endl;
  return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int n;
  scanf("%d",&n);
  ll ans=0;
  FOR(i,1,n) ans += i;
  cout << ans << endl;
}


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

using namespace std;

typedef long long ll;
int n;
int arr[100100];
int chk[100100];

ll res = 1, MOD = 1000000007;

int main() {
	int i;
	bool flag = true;

	scanf("%d",&n);
	for (i=n-1;i>=1-n;i-=2) chk[abs(i)]++;
	for (i=0;i<n;i++) {
		scanf("%d",&arr[i]);
		chk[arr[i]]--;
		if (chk[arr[i]]<0) flag = false;
	}
	if (!flag) {
		printf("0\n");
		return 0;
	}
	for (i=0;i<n/2;i++) res = res*2%MOD;
	printf("%lld\n",res);

    return 0;
}


Measured memory_bytes: 1024
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int N = sc.nextInt();

   String[] a = new String[N];
   for(int i=0;i<N;i++) a[i] =sc.next();
   
   boolean four = false;
   for(int i=0;i<N;i++) 
   {
     if(a[i].equals("Y"))
     {
       four = true;
       break;
     }
   }
   if(four) System.out.println("Four");
   else System.out.println("Three");
 }
}

Measured memory_bytes: 21844
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    vector<long long int > s;
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        if(n==0)
        {
            long long int tem;
            cin>>tem;
            s.push_back(tem);
        }
        else if(n==1)
        {
            int tem;
            cin>>tem;
            cout<<s[tem]<<endl;;
        }
        else
        {
            s.pop_back();
        }
    }
}


Measured memory_bytes: 4968
import sys
N = int(input())
point = [[int(i) for i in input().split()] for _ in range(N)]
point.sort(key=lambda x:x[2],reverse=True)
#print(point)
for cx in range(101):
    for cy in range(101):
        H = point[0][2]+abs(cx-point[0][0])+abs(cy-point[0][1])
        OK = True
        for i in range(N):
            if not point[i][2]==max(H-abs(cx-point[i][0])-abs(cy-point[i][1]),0):
                OK = False
                break
        if OK:
            print(cx,cy,H)
            sys.exit(0)

Measured memory_bytes: 41712
package main

import (
	"fmt"
	"sort"
)

// var rdr = bufio.NewReaderSize(os.Stdin, 1000000)

// func readLine() string {
// 	buf := make([]byte, 0, 1000000)
// 	for {
// 		l, p, e := rdr.ReadLine()
// 		if e != nil {
// 			panic(e)
// 		}
// 		buf = append(buf, l...)
// 		if !p {
// 			break
// 		}
// 	}
// 	return string(buf)
// }

type drink struct {
	a int
	b int
}

type A []*drink

func (a A) Len() int           { return len(a) }
func (a A) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a A) Less(i, j int) bool { return a[i].a < a[j].a }

func main() {
	var n, m int
	fmt.Scan(&n, &m)

	var ab A
	for i := 0; i < n; i++ {
		var a, b int
		fmt.Scan(&a, &b)
		ab = append(ab, &drink{a: a, b: b})
	}
	sort.Sort(ab)
	var cost int
	for i := 0; i < n; i++ {
		if m > ab[i].b {
			cost += ab[i].a * ab[i].b
			m -= ab[i].b
		} else {
			cost += ab[i].a * m
			break
		}
	}
	fmt.Println(cost)
}


Measured memory_bytes: 7168
#include <stdio.h>

int getAns(int, int a[]);

int main() {
    int n;
    int p[20] = {0};
    
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d ", p + i);
    }
    scanf("%d", p + n - 1);

    printf("%d", getAns(n, p));

    return 0;
}

int getAns(int n, int p[]) {
    int count = 0;

    for (int i = 1; i < n - 1; i++) {
        if (p[i - 1] < p[i] && p[i] < p[i + 1]) {
            count++;
        } else if (p[i - 1] > p[i] && p[i] > p[i + 1]) {
            count++;
        }
    }

    return count;
}



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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n; cin >> n;
	vl a(n);
	FOR(i,0,n) cin >> a[i];

	vl dp(n,oo);
	dp[0] = 0;
	FOR(i,1,n) FOR(j,1,3) if (i >= j) {
		dp[i] = min(dp[i], dp[i-j] + abs(a[i]-a[i-j]));
	}
	cout << dp[n-1] << endl;
}



Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <functional>
#include <stack>
using namespace std;

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

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


template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

int main(){
  vector<vector<int>> data(3,vector<int>(3));
  vector<vector<int>> bo(3,vector<int>(3,0));
  REP(i,3){
    REP(j,3){
      cin>>data[i][j];
    }
  }
  int N;
  cin>>N;
  int tmp;
  REP(i,N){
    cin>>tmp;
    REP(j,3){
      REP(r,3){
        if(data[j][r]==tmp){
          bo[j][r]=1;
        }
      }
    }
  }
  int ans=0;
  tmp=1;
  REP(i,3){
    REP(j,3){
      tmp=tmp*bo[i][j];
    }
    if(tmp==1){
      ans=1;
    }
    tmp=1;
  }
  tmp=1;
  REP(i,3){
    REP(j,3){
      tmp=tmp*bo[j][i];
    }
    if(tmp==1){
      ans=1;
    }
    tmp=1;
  }
  if(bo[0][0]*bo[1][1]*bo[2][2]==1){
    ans=1;
  }
  else if(bo[0][2]*bo[1][1]*bo[2][0]==1){
    ans=1;
  }
  if(ans==1){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }

}


Measured memory_bytes: 888
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <limits>
#include <cmath>

using namespace std;

int main() {
    size_t n, k;
    cin >> n >> k;
    size_t c = 0;
    while (n > 0) {
        n /= k;
        ++c;
    }
    cout << c << endl;
    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();
		sc.close();

		String s1,s2;

		if(s.length()%2==0) {
			s1 = s.substring(0, s.length()/2);
			s2 = s.substring(s.length()/2, s.length());
		}else {
			s1 = s.substring(0, s.length()/2);
			s2 = s.substring(s.length()/2+1, s.length());
		}

		char[] ch1 = s1.toCharArray();
		char[] ch2 = s2.toCharArray();
		int cnt = 0;
		for(int i = 0;i < ch1.length;i++) {
			if(ch1[i]!=ch2[ch2.length-i-1]) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}

Measured memory_bytes: 23380
fun main (args : Array<String>) {
	val (k, x) = readLine()!!.split(" ")
	val K : Int = k.toInt()
	val X : Int = x.toInt()
	var result : Int = X - (K - 1)
	var str : String = ""
	str += result
	str += " "
	for (i in result..(X + (K - 1)) - 1) {
		result++
		str += result
		str += " "
	}
	println("${str}")
}

Measured memory_bytes: 38640
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int n;
int ansLen;
string ans;
vector<string> v;

int t[10][10];

void update(int *idx,int len){
  string s = v[idx[0]];

  for(int i=1;i<n;i++){
    for(int j=t[idx[i-1]][idx[i]];j<v[idx[i]].length();j++){
      s += v[idx[i]][j];
    }
  }

  if(ansLen > len || ansLen == len && ans > s){
    ansLen = len;
    ans = s;
  }
}

void dfs(int cnt,int *idx,bool *used,int len){
  if(cnt == n){
    if(ansLen >= len){
      update(idx,len);
    }
    return;
  }

  for(int i=0;i<n;i++){
    if(!used[i]){
      int nextLen = len + v[i].length();
      if(cnt != 0){
        nextLen -= t[idx[cnt-1]][i];
      }

      idx[cnt] = i;

      used[i] = true;
      dfs(cnt+1,idx,used,nextLen);
      used[i] = false;
    }
  }
}

int main(){
  while(cin>>n,n){
    v = vector<string>();

    for(int i=0;i<n;i++){
      string s;
      cin>>s;
      v.push_back(s);
    }

    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        if(i == j) continue;
        if(v[j].find(v[i]) != string::npos){
          v.erase(v.begin() + i);
          i--;
          n--;
          break;
        }
      }
    }

    memset(t,0,sizeof(t));

    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        if(i == j) continue;

        for(int k=min(v[i].length(),v[j].length())-1;k>0;k--){
          bool flg = true;
          for(int l=0;l<k;l++){
            if(v[j][l] != v[i][v[i].length()-k+l]){
              flg = false;
              break;
            }
          }
          if(flg){
            t[i][j] = k;
            break;
          }
        }
      }
    }

    ansLen = 999;
    ans = "zzzzzzzzzzzzzzzzzzzzz";

    int idx[n];
    bool used[n];
    memset(used,0,sizeof(used));

    dfs(0,idx,used,0);

    cout<<ans<<endl;
  }
}

Measured memory_bytes: 920
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
int main()
{ 
    int a,b,c;
	while(scanf("%d%d%d",&a,&b,&c)!=EOF)
	{
		if(c>=a&&c<=b)
		printf("Yes\n");
		else
		printf("No\n");
	}
	return 0;
}

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

//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")

#define F first
#define S second
#define MT make_tuple
#define MP make_pair
#define SZ(a) ((int)(a).size())
#define PB push_back
#define LBS 20
#define MOD ((long long)1e9+7) //1e9+9
#define LEFT(i) (2*(i))
#define RIGHT(i) (2*(i)+1)
#define PAR(i) ((i)/2)
#define ALL(a) (a).begin(), (a).end()
#define END(s) {cout << s;return;}

using namespace std;

typedef long long ll;
typedef double rat;
typedef long long bi;
typedef pair<int, int> ii;
typedef std::vector<ii> vii;
typedef std::map<int, int> mii;
typedef bitset<LBS> bis;
typedef std::vector<bis> vbs;

template<class T>
void in(T &a){
  for(auto &x: a)
    cin >> x;
}

template<class T>
void out(T &a, string sep=" "){
  for(auto x: a)
    cout << x<<sep;
  cout << '\n';
}

template<class T>
void err(T &a, string sep=" "){
  for(auto x: a)
    cerr << x <<sep;
  cerr << '\n';
}


int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  map<string,int> msi;
  std::vector<ll> t(n);
  for(int i=0; i<n; i++){
    string s; cin >> s;
    msi[s]=i;
    cin >> t[i];
  }
  string x; cin >> x; ll o=0;
  for(int i=msi[x]+1; i<n; i++)
    o+=t[i];
  cout << o <<"\n";
}


Measured memory_bytes: 256