akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;

#define DE 1
#define FI first
#define SE second
#define PB push_back
#define MP make_pair
#define ALL(s) (s).begin(),(s).end()
#define REP(i,n) for (int i = 0; i < (int)(n); ++i)
#define EACH(i,s) for (typeof((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl

template<class T1, class T2> ostream& operator<<(ostream &s, pair<T1,T2> P){return s<<'<'<<P.first<<", "<<P.second<<'>';}
template<class T> ostream& operator<<(ostream &s, vector<T> P) {s<<"{ ";for(int i=0;i<P.size();++i){if(i>0)s<<", ";s<<P[i];}return s<<" }"<<endl;}
template<class T1, class T2> ostream& operator<<(ostream &s, map<T1,T2> P) {s<<"{ ";for(typeof(P.begin()) it=P.begin();it!=P.end();++it){if(it!=P.begin())s<<", ";s<<'<'<<it->first<<"->"<<it->second<<'>';}return s<<" }"<<endl;}



int n, m;
int a[200], b[200];

int main() {
    //freopen( "/Users/macuser/Documents/Programming/Contest/input.in", "r", stdin );
    
    while (cin >> n >> m) {
        if (n == 0) break;
        
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        
        int A = 0, B = 0;
        for (int i = 0; i < n; ++i) {cin >> a[i]; A += a[i];}
        for (int i = 0; i < m; ++i) {cin >> b[i]; B += b[i];}
    
        int dis = B-A;
        
        if (dis % 2 != 0) cout << -1 << endl;
        else {
            int Min = 1000000;
            int MinA = -1, MinB = -1;
            
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (!(dis&1) && b[j] - a[i] == dis/2 && a[i] + b[j] < Min) {
                        Min = a[i] + b[j];
                        MinA = i;
                        MinB = j;
                    }
                }
            }
        
            if (MinA == -1) cout << -1 << endl;
            else cout << a[MinA] << " " << b[MinB] << endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 1160
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

int main(){
	double x1,x2,xp,y1,y2,yp,slope,ansx,ansy;
	int q;
	bool X_FLG = false,Y_FLG = false;

	scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
	scanf("%d",&q);

	if(y1 == y2){
		X_FLG = true;
	}else if(x1 == x2){
		Y_FLG = true;
	}else{
		slope = (y2-y1)/(x2-x1);
	}

	for(int i=0;i<q;i++){
		scanf("%lf %lf",&xp,&yp);
		if(X_FLG){
			ansx = xp,ansy=y1;
			printf("%.10lf %.10lf\n",2*ansx-xp,2*ansy-yp);
		}else if(Y_FLG){
			ansx = x1,ansy = yp;
			printf("%.10lf %.10lf\n",2*ansx-xp,2*ansy-yp);
		}else{
			ansx = (yp*(x2-x1)*(y2-y1)+xp*(x2-x1)*(x2-x1)-y1*(y2-y1)*(x2-x1)+x1*(y2-y1)*(y2-y1))/((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1));
			ansy = ((x1-x2)*ansx+yp*(y2-y1)+xp*(x2-x1))/(y2-y1);
			printf("%.10lf %.10lf\n",2*ansx-xp,2*ansy-yp);
		}

	}

	return 0;
}


Measured memory_bytes: 2724
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
        int b = sc.nextInt();
        String s = " ";
        for(int i=b-a+1;i<=b+a-1;i++){s+=String.valueOf(i) + " ";}
		System.out.println(s);
	}
}


Measured memory_bytes: 23252
x = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

divisors = make_divisors(x)

for divisor in divisors:
  for a in range(1000):
    b = a - divisor
    if (a**5 - b**5 == x):
      print(a, b)
      break

Measured memory_bytes: 68032
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define P pair<int,int>
#define PI 3.141592653589793
const int INF = 1001001001;
const ll MX = 1e18;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) {
		cin >> a[i];
	}

	map<int, int> m;
	sort(a.begin(), a.end());
	int ans = 0;
	
	rep(i, n) {
		vector<int> div;
		int p = a[i];
		bool ok = false;
		for (int j = 1; j * j <= p; j++) {
			if (p % j == 0) {
				div.push_back(j);
				div.push_back(p/j);
			}
		}
		rep(j, div.size()) {
			if (m[div[j]] != 0) {
				ok = true;
				break;
			}
		}
		m[a[i]] = 1;
		if (ok) continue;
		if (i != n - 1 && a[i] == a[i + 1]) continue;
		ans++;
		//cout << i << endl;
	}
	cout << ans << endl;
}


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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define show(x) cout << #x << " = " << x ln
#define dbg(x) cout<<#x"="<<x ln

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

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

int a, b, c, d;

int main() {
	cin >> a >> b >> c >> d;
	cout << max(a*b, c*d) << ln;
}

Measured memory_bytes: 256
n = int(input())
W = []
for _ in range(n):
    w = input()
    if w in W:
        print('No')
        exit()
    W.append(w)

for i in range(n-1):
    if W[i][-1] != W[i+1][0]:
        print('No')
        exit()
print('Yes')

Measured memory_bytes: 38384
#include<iostream>
#include<cstdio>
#define M 1000001
using namespace std;

void call(int n){
    int i = 1;
    while(true){
        int x = i;
        if (x % 3 == 0){
            cout << " " << i;
            i ++;
        }else{
            while (true){
                if (x % 10 == 3){
                    cout << " " << i;
                    i ++;
                    break;
                }else{
                    x /= 10;
                    if(x == 0){
                        i ++;
                        break;
                    }
                }
            }
        }
        if (i > n){
            cout << endl;
            break;
        }
    }
    
}

int main(){
    int n;
    cin >> n;
    call(n);
    return 0;
}


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


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

//    ;w = N * h * n / (4*h*n - N*n - N*h);
    for (ll h = 1; h <= 3500; h++) {
        for (ll n = 1; n <= 3500; n++) {
            if ((4*h*n - N*(n+h)) > 0) {
                ll w = N*h*n / (4*h*n - N*(n+h));

                if (4*h*n*w == N*(n*w+h*w+h*n)) {
                    printf("%lld %lld %lld\n", h, n, w);
                    return 0;
                }
            }
        }
    }

    return 0;
}




Measured memory_bytes: 256
s=input()
n=len(s)
i=0
k=0
bef=""
while n>i:
    if bef!=s[i]:
        k+=1
        bef=s[i]
    else:
        if i==n-1:
            break
        i+=1
        bef+=s[i]
        k+=1
    i+=1
print(k)


Measured memory_bytes: 3500
#include <iostream>
#include <vector>
#include <map>
using namespace std;

void erasec(vector<int>& c,int i,int j){
	int a,b;
	if(i>j){
		a=i,b=j;
	}else if(j>i){
		a=j,b=i;
	}else{
		return;
	}
	vector<int>::iterator it = c.begin();
	advance(it,a);
	it = c.erase(it);
	it = c.begin();
	advance(it,b);
	it = c.erase(it);
}

int solve(const vector<int>& c,map<vector<int>,int> &history){
	//vector<int> ex1;
	//vector<int> ex2;
	int min = (20>c.size())?c.size():20;
	for(int i=0;i<c.size();++i){
		for(int j=0;j<=1;++j){
			for(int k=-1;k<=1;++k){
				if(j==0&&k==0) continue;
				if(0<=i+j*4+k && i+j*4+k<c.size() && (i+j*4+k)%4-i%4<=1 && (i+j*4+k)%4-i%4>=-1){
					if(c[i] == c[i+j*4+k]){
						map<vector<int>,int>::iterator it = history.find(c);
						if(it != history.end()){
							if(it->second < min) min = it->second;
							continue;
						}else{
							vector<int> v(c.size());
							copy(c.begin(),c.end(),v.begin());
							erasec(v,i,i+j*4+k);
							int a = solve(v,history);
							history.insert( map<vector<int>, int>::value_type(v,a));
							if(a < min) min = a;
						}
					}
				}
			}
		}
	}
	return min;
}

int main(void){
	int n;
	cin >> n;
	for(int a=0;a<n;++a){
		vector<int> in;
		map<vector<int>,int> history;
		for(int i=0;i<20;++i){
			int input;
			cin >> input;
			in.push_back(input);
		}
		cout << solve(in,history) << "\n";
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
using p=pair<int,int>;
#define int long long
#define rep(i,N) for(int i=2;i<N;i++)

signed main(){
  int N;
  cin>>N;
  int A[87];
  A[0]=2;A[1]=1;
  rep(i,87){
    A[i]=A[i-1]+A[i-2];
  }
  int ans=A[N];
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

#define MOD 1000000007

using ll = long long;
const int limit = 60;
using edge = struct {int from; int to;};

ll depth[limit];
vector<edge> bridge;

int main(void) {
    char a,b;
    cin >> a >> b;
    
    cout << ((a<b) ? "<" : (a==b) ? "=" : ">") << endl;
    return 0;
}



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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;

struct string_hasher {
  const ll mod = 1e9 + 7;
  const ll prime = 2641;
  string s; int n;
  vector<ll> H, P;
  string_hasher() {}
  void init(string s) {
    this->s = s;
    this->n = s.length();

    H.resize(n+10);
    P.resize(n+10, 1);
    for (int i=0; i<n; i++) {
      H[i+1] = (H[i]*prime+(s[i]-'a'))%mod;
      P[i+1] = (prime*P[i])%mod;
    }

  }

  ll get(int l, int r) {
    assert(l>=0 && r>=0 && l<n && r<n);
    ll res = H[r+1] - (P[r-l+1]*H[l])%mod;
    res %=mod;
    res += mod;
    return res%mod;
  }

  // Check if s[l1..r1] == s[l2...r2]. Assumes substr2 starts ahead of substr1.
  ll substr_equal(ll l1, ll r1, ll l2, ll r2) {
    assert(r1>=l1 && r2>=l2 && l2>=l1);
    ll h1 = get(l1,r1);
    ll h2 = get(l2,r2);

    bool res = ((h1-h2)%mod) == 0;
    // bool naive = (s.substr(l1,r1-l1+1) == s.substr(l2,r2-l2+1));
    // assert(res == naive);
    return res;
  }
};


string s; int n;
string_hasher H;
bool badl[maxn], badr[maxn];

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

  cin>>s; n = s.length();
  H.init(s);

  {

    int minp = n;
    for (int l=1; l<n; l++) {
      if (n%l) continue;
      bool bad = true;
      for (int j=0; j<n; j++) {
	if (s[j] != s[j%l]) {
	  bad = false;
	}
      }
      if (bad) {
	minp = l; break;
      }
    }

    if (minp == n) {
      // s isn't periodic
      cout<<1<<endl;
      cout<<1<<endl;
      return 0;
    }

    if (minp == 1) {
      //aaaa
      cout<<n<<endl;
      cout<<1<<endl;
      return 0;
    }
  }



  for (int l=1; l<n; l++) {
    int x0=0; int y0=l-1;
    for (int i=l; i+l<=n; i+=l) {
      if (H.substr_equal(x0,y0,i,i+l-1)) {
	badl[i+l-1] = true;
      } else {
	break;
      }
    }
  }

  for (int l=1; l<n; l++) {
    int x0=n-l; int y0=n-1;
    for (int i=n-l-1; i-l+1>=0; i-=l) {
      if (H.substr_equal(i-l+1,i,x0,y0)) {
	badr[i-l+1] = true;
      } else {
	break;
      }
    }
  }

  // for (int i=0; i<10; i++) {
  //   cout<<badl[i]<<" ";
  // }
  // cout<<endl;
  // for (int i=0; i<10; i++) {
  //   cout<<badr[i]<<" ";
  // }
  // cout<<endl;

  cout<<2<<endl;
  int ans = 0;

  for (int i=0; i<n-1; i++) {
    if (!badl[i] && !badr[i+1]) ans++;
  }
  cout<<ans<<endl;  

  return 0;
}




Measured memory_bytes: 10032
using System;
using System.Linq;
using System.Numerics;
using System.Collections.Generic;

namespace ForAtcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string t = Console.ReadLine();
            long count = 0;
            for (var i = 0; i < s.Length; i++)
            {
                if (s.Substring(i, 1) != t.Substring(i, 1)) count++;
            }
            Console.WriteLine(count);
        }
    }
}

Measured memory_bytes: 36932
N=input()
n=int(N)
a=int(N[-1])
if a==2 or a==4 or a==5 or a==7 or a==9:
  print("hon")
elif a==0 or a==1 or a==6 or a==8:
  print("pon")
elif a==3:
  print("bon")

Measured memory_bytes: 9064
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
int main(){
    Hello
    int one = 0, zero = 0;
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '1') one++;
        else zero++;
    }
    cout << min(one, zero) * 2;
    return 0;
}

Measured memory_bytes: 3740
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<=n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define pb(x) push_back(x)
#define eb(x,y) emplace_back(x,y)
#define MOD 1000000007
#define MAX 1000000001
#define INF 1410065408
#define EPS 1e-9
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct edge{int from, to; ll cost;};

map<Pll, ll> memo;

ll comb(ll n, ll r){
    if(n == r || r == 0){
        return 1;
    }else if(r == 1){
        return n;
    }else if(memo[Pll(n, r)] != 0){
        return memo[Pll(n, r)];
    }else{
        ll tmp = comb(n-1, r-1) + comb(n-1, r);
        memo[Pll(n, r)] = tmp;
        return tmp;
    }
}

signed main(){
    ll n, p;
    cin >> n >> p;
    ll a[2] = {0, 0};
    rep(n){
        ll tmp;
        cin >> tmp;
        a[tmp%2]++;
    }
    ll ans = 0;
    if(p == 0){
        ll tmp = 0;
        if(a[1] >= 2) for(ll i=2;i<=a[1];i+=2){
            tmp += comb(a[1], i);
        }
        ans += pow(2, a[0]) * (tmp+1);
    }else{
        ll tmp = 0;
        for(ll i=1;i<=a[1];i+=2){
            tmp += comb(a[1],i);
        }
        ans += pow(2, a[0]) * tmp;
    }
    cout << ans;
    return 0;

}


Measured memory_bytes: 512
#include <stdio.h>

char str[12];
int n;

// 0~ len-1まで決まっている。 d種類まで使っている 
void foo(int len, int d){
    if(len == n){
        printf("%s", str);
        return;
    }
    else
    {
        for (int i = 0; i < d; i++)
        {
            str[len] = 'a'+i;
            foo(len+1, d);
        }
        str[len] = 'a'+ d;
        foo(len+1, d+1);
    }
    
}

int main(void) {
    
    int i;
    
    scanf("%d", &n);

    str[n] = '\n';
    str[n+1] = '\0';

    foo(0, 0);

    return 0;
}



Measured memory_bytes: 1408
/*
Author : Xinyuan
*/
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef long long int ll;
const int INF = 1e9 + 7;
const int mod = 1e9 + 7;
ll powmod(ll a, ll b) {
    ll res = 1;
    a %= mod;
    assert(b >= 0);
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
int nxt() {
    int x;
    scanf("%d", &x);
    return x;
}

int main() {
    int x = nxt(), n = nxt();
    set<int> s;
    for (int i = 0; i <= 101; i++) s.insert(i);
    REP(i, n) {
        int a = nxt();
        s.erase(a);
    }
    int ans = 0, diff = INF;
    for (int a : s) {
        if (abs(a - x) < diff) {
            diff = abs(a - x);
            ans = a;
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mod 1000000007
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define forn(i,a,b) for(int i=a;i<(int)b;i++)
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<(a+b-1)/b<<"\n";
    return 0;
}

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

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

    for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] == s[i + 1]) {
            cout << i + 1 << " " <<  i + 2 << endl;
            return 0;
        } else if (i < s.size() - 2 && s[i] == s[i + 2]) {
            cout << i + 1 << " " << i + 3 << endl;
            return 0;
        }
    }
    
    cout << "-1 -1" << endl;
}

Measured memory_bytes: 512
import math
 
k = int(input())
sum = 0
 
for a in range(k - 2):
  for b in range(a + 1, k - 1):
    for c in range(b + 1, k):
      sum += 6 * math.gcd(a + 1, math.gcd(b + 1, c + 1))
      
for a in range(k - 1):
  for b in range(a + 1, k):
    sum += 6 * math.gcd(a + 1, b + 1)
    
sum += k * (k + 1) // 2
      
print(sum)

Measured memory_bytes: 9204
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;

int main(){
  int N;
  cin >> N;
  int H[N];
  for(int i=0;i<N;i++){
    cin >> H[i];
  }
  vector<int> height;
  for(int i=0;i<N;i++){
    int hei = 0;
    for(int j=i;H[j]>=H[j+1] && j+1<N;j++){
      hei++;
    }
    i+=hei;
    height.push_back(hei);
  }
  sort(height.begin(),height.end());
  int last = height.size() - 1;
  cout << height[last] << endl;
  return 0;
}


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

int main(){
    int a,b;
   
    cin >> a >> b;
    
    if(a < b){
      cout << "a < b" << endl;
    }    
     else if(a > b){
      cout << "a > b" << endl;
    }
     else if(a == b){
      cout << "a == b" << endl;
    }
    else{
      cout << "!?" << endl;
    }
}

Measured memory_bytes: 1160
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int N=205;
int n;
int a[N][N],dp[N][N];
int main() {
  scanf("%d",&n);
  for (int i=1;i<=2;++i) {
    for (int j=1;j<=n;++j) scanf("%d",&a[i][j]);
  }
  for (int i=1;i<=2;++i) {
    for (int j=1;j<=n;++j) {
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
    }
  }
  printf("%d\n",dp[2][n]);
  return 0;
}


Measured memory_bytes: 3764
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>pppp(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}
 
int main() {
  int N;
  cin>>N;
  vector<string>s(N);
  map<string,int>k;
  for(int i=0;i<N;i++){
    cin>>s[i];
    sort(s[i].begin(),s[i].end());
    k[s[i]]++;
  }
  int64_t sum=0;
  for(auto a:k){
    int64_t c=a.second;
    sum+=(c*(c-1)/2);
  }
  cout<<sum<<endl;
  return 0;
}

Measured memory_bytes: 13920
#include <stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b){
	return *(int*)a-*(int*)b;
}
int even(int *a,int*,int n);
int odd(int *a,int*,int n);
int main(int argc, char *argv[])
{
	int n;
	scanf("%d",&n);
	int a[n],b[n],ans,i;
	for(i=0;i<n;i++)
		scanf("%d%d",&a[i],&b[i]);
	qsort(a,n,sizeof(int),cmp);
	qsort(b,n,sizeof(int),cmp);
	if(n%2)
		ans=odd(a,b,n);
	else ans=even(a,b,n);
	printf("%d\n",ans);
}
int odd(int a[],int b[],int n){
	int ans;
	ans=(b[(n+1)/2-1]-a[(n+1)/2-1]);
	if(ans<0)ans*=(-1);
	ans++;
	return ans;
}
int even(int a[],int b[],int n){
	int ans,aa,bb;
	aa=a[n/2-1]+a[(n/2)];
	bb=b[n/2-1]+b[(n/2)];
	ans=bb-aa;
	if(ans<0)ans*=(-1);
	ans++;
	return ans;
}

Measured memory_bytes: 4012
// last.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//
#include<iostream>
using namespace std;

int main()//(int argc, _TCHAR* argv[])
{


	int nian;
	cin >> nian;
	if(nian<1000){
		cout<<"ABC";
	}else{
	
		cout<<"ABD";
	}

	return 0;

}

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

// @author: pashka

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

    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int t1 = h1 * 60 + m1;
    int t2 = h2 * 60 + m2;
    cout << max(t2 - t1 - k, 0) << "\n";
    return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
typedef long long  ll ;
typedef double db;
const double pi = 3.141592654;
#define pb         push_back
#define forab(i,a,b)       for(int i=(a);i<=(b);i++)
#define CIN	ios_base::sync_with_stdio(0); cin.tie(0)
#define pcase(z,x)     printf("Case %ld: %lld\n",z,x)
#define nw	 "\n"
#define mod 1000000007


int main(void)
{
	CIN;
	ll tc,l,k=0,sum=0,x=0,y,z=0,m=1,n=0,ans=0,cnt=0;
	cin>>n;
	while(n--){
		cin>>x;
		if(x%2==0){
			while(x%2==0){
				x/=2;
				sum++;
			}
		}
	}
	cout<<sum;
}

Measured memory_bytes: 3612
n = int(input())
p = list(map(int, input().split()))
ans  = 0
current = max(p)+1
for i in range(n):
  if p[i]  <= current:
    current = p[i]
    ans +=1
  
#  if p[i] == min(p[:i+1]):
#        ans+=1 
                 
print(ans)                 
                 

Measured memory_bytes: 75344
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    A = NLI()
    ans = 0
    for i, a in enumerate(A):
        if i % 2 == 0 and a % 2 == 1:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 9480
#include<bits/stdc++.h>
using namespace std;
#define MAX 100005
#define INF (1e9+1)
 
int n,W;
int dp[MAX];
 
int main(){
  fill(dp,dp+MAX,-INF);
  dp[0]=0;
   
  cin>>n>>W;
  for(int i=0;i<n;i++){
    int v,w,m;
    cin>>v>>w>>m;
 
    for(int k=0;m>0;k++){
      int key= min( m, (1<<k) );
      m-=key;
 
      int nv=key*v;
      int nw=key*w;
      for(int j=W;j>=nw;j--){
        dp[j]=max(dp[j],dp[j-nw]+nv);
      }
 
 
    }
     
  }
  int ans=0;
  for(int i=0;i<=W;i++)
    ans=max(ans,dp[i]);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3480
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int n,a[100000],b[100000],sun;
  cin>>n;
  vector<pair<int ,int> > pp(n);
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
    pp[i] = make_pair(a[i],b[i]);
  }
  sort(pp.begin(),pp.end());
  sun = pp[n-1].second;
  cout<<pp[n-1].first+sun<<"\n";
  return(0);
}


Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main(){
	long a[10000],saidai,saisyou,goukei,n,i,b,c,d,e;
	saidai=-1000000;
	saisyou=1000000;
	goukei=0;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>a[i];
		b=a[i];
		c=a[i];
		goukei=goukei+a[i];
		if(saidai<a[i]){
			swap(saidai,b);
		}
		if(saisyou>a[i]){
			swap(saisyou,c);
		}
	}
	cout<<saisyou<<" "<<saidai<<" "<<goukei<<endl;
	return 0;
}

Measured memory_bytes: 3160
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int N, A, B, C;
std::vector<int> l;

ll dfs (int i, int As, int Bs, int Cs){
  if ( i == N ) {
    if ( As != 0 && Bs != 0 && Cs != 0 ) return std::abs(A-As) + std::abs(B-Bs) + std::abs(C-Cs) - 30;
    return std::numeric_limits<int>::max();
  }
  ll rtn0 = dfs(i+1, As+l[i], Bs     , Cs     ) + 10;
  ll rtn1 = dfs(i+1, As     , Bs+l[i], Cs     ) + 10;
  ll rtn2 = dfs(i+1, As     , Bs     , Cs+l[i]) + 10;
  ll rtn3 = dfs(i+1, As     , Bs     , Cs     );
  return std::min( { rtn0, rtn1, rtn2, rtn3 } );
}

int main (void) {
  std::cin >> N >> A >> B >> C;
  l.resize(N);  for(int i=0; i<N; i++) std::cin >> l[i];

  std::cout << dfs(0,0,0,0) << std::endl;
  return 0;
}

Measured memory_bytes: 256
my_bool=True
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]

for i in range(n):
    if i==0:
        if a[i][0]%2!=(a[i][1]+a[i][2])%2:
            my_bool=False
            break
        else:
            if (a[i][1]+a[i][2])>a[i][0]:
                my_bool=False
                break
            
    else:
        if (a[i][0]-a[i-1][0])%2!=((a[i][1]+a[i][2])-(a[i-1][1]+a[i-1][2]))%2:
            my_bool=False
            break
        else:
            if (a[i][0]-a[i-1][0])<((a[i][1]+a[i][2])-(a[i-1][1]+a[i-1][2])):
                my_bool=False
                break
if my_bool:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 27300
import numpy as np

n,a,b=map(int,input().split())

ans=0
def digitSum(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 合計値を返す
    return sum(array)

for i in range(1,n+1):
    k=digitSum(i)
    if(a<=k and k<=b):
        ans+=i

print(ans)


Measured memory_bytes: 12504
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n=ni()
mins=[]
maxs=[]
for i in range(n):
  a,b=nm()
  mins.append(a)
  maxs.append(b)

smn = sorted(mins)
smx = sorted(maxs)

if n%2==1:
  mn = smn[(n+1)//2-1]
  mx = smx[(n+1)//2-1]
  print(round((mx-mn)+1))
else:
  mn = (smn[n//2-1]+smn[n//2])/2.0
  mx = (smx[n//2-1]+smx[n//2])/2.0
  print(round((mx-mn)*2+1))


Measured memory_bytes: 28600
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
using Graph = vector<vector<int>>;
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
struct edge{ll to, cost;};
typedef pair<ll,ll> P;
struct graph{
  ll V;
  vector<vector<edge> > G;
  vector<ll> d;

  graph(ll n){
    init(n);
  }

  void init(ll n){
    V = n;
    G.resize(V);
    d.resize(V);
    rep(i,V){
      d[i] = INF;
    }
  }

  void add_edge(ll s, ll t, ll cost){
    edge e;
    e.to = t, e.cost = cost;
    G[s].push_back(e);
  }

  void dijkstra(ll s){
    rep(i,V){
      d[i] = INF/10;
    }
    d[s] = 0;
    priority_queue<P,vector<P>, greater<P> > que;
    que.push(P(0,s));
    while(!que.empty()){
      P p = que.top(); que.pop();
      ll v = p.second;
      if(d[v]<p.first) continue;
      for(auto e : G[v]){
        if(d[e.to]>d[v]+e.cost){
          d[e.to] = d[v]+e.cost;
          que.push(P(d[e.to],e.to));
        }
      }
    }
  }
};
int main() {
  ll n,k; cin>>n>>k;
  if(k==1) cout << 0 << endl;
  else{
    cout << n-k << endl;}}

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

int main(){
    string s;
    cin>>s;
    int n=s.size();
    vector<int>ans(n);
    int cnt=0;
    rep(i,n){
        if(s[i]=='R')cnt++;
        else{
            ans[i-1]+=(cnt+1)/2;
            ans[i]+=cnt/2;
            cnt=0;
        }
    }
    cnt=0;
    for(int i=n-1; i>=0; --i){
        if(s[i]=='L')cnt++;
        else{
            ans[i+1]+=(cnt+1)/2;
            ans[i]+=cnt/2;
            cnt=0;
        }
    }
    rep(i,n)cout<<ans[i]<<" ";
    cout<<endl;
    return 0;
}

Measured memory_bytes: 3812
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef vector<vector<ll>> mat;
typedef vector<ll> vec;



void solve() {
	ll n, a, b; cin >> n >> a >> b;
	n %= 12;
	rep(i, n) {
		if (i % 2 == 0) {
			a -= b;
		}
		else {
			b+=a;
		}
	}
	cout << a << " " << b << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(4);
	//init();
	solve();
	stop
		return 0;
}



Measured memory_bytes: 3180
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector> 
#include <cstring>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;

const int maxN = 10010; 
const int INF = 1000000000;

int n;
int main()
{
	scanf("%d",&n);
	for(int i=0;i<=10;i++)
	{
		for(int j=0;j<=14;j++)
		{
			if((4*i + 7*j) == n)
			{
				puts("Yes");
				return 0;
			}
		}
	}
	puts("No");
	return 0;
}

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

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

typedef long long ll;

using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<int> a(N + 1, 0);
    REP(i, N)
    {
        cin >> a[i + 1];
    }

    int ans = 0;
    vector<bool> visited(N + 1, false);
    visited[1] = true;
    int next = a[1];
    while(true)
    {
        // 訪問済みのボタンにきたらループしてしまう
        if (visited[next])
        {
            ans = -1;
            break;
        }

        ans++;
        // 最初に2にきたときが最小
        if (next == 2)
        {
            break;
        }
        visited[next] = true;
        next = a[next];
    }

    cout << ans << endl;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>
  
long long inv;
int *B;
  
long long countup(int *A, int p, int r);
  
int main(int argc, char *argv[])
{
  int n, i, j;
  int *A;
  
  inv = 0;
  
  scanf("%d", &n);
  A = (int *)malloc(sizeof(int) * n);
  B = (int *)malloc(sizeof(int) * n);
  for (i = 0; i < n; i++) scanf("%d", &A[i]);
  
  inv = countup(A, 0, n - 1);
  
  printf("%lld\n", inv);
  
  return 0;
}
  
long long countup(int *A, int p, int r)
{
  int q = p + (r-p)/2;
  int i, j, k, tmp;
  long long ct = 0;
  
  if (r - p < 3) {
    for (i = p; i < r; i++) {
      for (j = r; j > i; j--) {
    if (A[j] < A[j-1]) {
      tmp = A[j-1];
      A[j-1] = A[j];
      A[j] = tmp;
      ct++;
    }
      }
    }
    return ct;
  }
  ct += countup(A, p, q);
  ct += countup(A, q+1, r);
  
  i = p;
  j = q + 1;
  for (k = p; k <= r; k++) {
    if (i >= q + 1 || j >= r + 1) {
      if (i >= q + 1) B[k] = A[j++];
      else B[k] = A[i++];
    } else {
      if (A[i] > A[j]) {
    B[k] = A[j];
    ct += q - i + 1;
    j++;
      } else {
    B[k] = A[i];
    i++;
      }
    }
  }
  for (k = p; k <= r; k++) A[k] = B[k];
  return ct;
}

Measured memory_bytes: 3428
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll mod=1e9;
const int inf=0x3f3f3f3f;

int main()
{
	ll a,b,c,d,t;cin>>a>>b>>c>>d>>t;
	if(b<=d) cout<<"NO"<<endl;
	else if((b-d)*t<labs(a-c))
	{
		cout<<"NO"<<endl;
	}
	else cout<<"YES"<<endl;
}

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

int main() {
  int number;
  double kg, m;
  while(scanf("%d%*c%lf%*c%lf",&number,&kg,&m)==3) {
    if(kg/(m*m)>=25) cout << number << endl;
  }
  return 0;
}


Measured memory_bytes: 1232
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true){
			String line[] = br.readLine().split(" ");
			int n = Integer.parseInt(line[0]);
			int m = Integer.parseInt(line[1]);
			if(n==0){break;}

			int[] vote = new int[m];
			Arrays.fill(vote, 0);
			for(int i=0; i<n; i++){
				String poll[] = br.readLine().split(" ");
				for(int j=0; j<m; j++){
					if (poll[j].equals("1")) {vote[j]++;}
				}
			}

			boolean resume = false;
			for(int i=n; i>=0; i--){
				for(int j=0; j<m; j++){
					if (vote[j] == i) {
						if(resume){System.out.print(" ");}
						System.out.print(j+1);
						resume = true;
					}
				}
			}
			System.out.println();
		}
	}
}

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

using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll oo = 1e18;
const ll mod = 1e9+7;
const int INF = 1 << 30;



int main()
{
    ios::sync_with_stdio(0);cin.tie(0);ios_base::sync_with_stdio(0);
    
    int n;
    cin >> n;
    map<string, int> m;
    for (int i = 0; i < n; i ++) {
        string s;
        cin >> s;
        m[s]++;
    }
    
    int mx = -1;
    for (auto t : m)
        mx = max(t.second, mx);

    set <string> ans;
    for (auto t : m)
        mx = max(t.second, mx);
    
    for (auto t : m) {
        if (t.second == mx) {
            ans.insert(t.first);
        }
    }
    for (auto ss : ans) {
        cout << ss << endl;
    }
    
    return 0;
}


Measured memory_bytes: 33280
#include <stdio.h>
#include <iostream>

using namespace std;

int main(){

    long long a, b, c, k;

    cin >> a >> b >> c >> k;

    long long sum = 0;

    if(k <= a){
        sum += 1 * k;
    }
    else if(k <= (a + b)){
        sum += 1 * a;
    }
    else{
        int numOfC = k - (a+b);
        sum += 1*a - 1*numOfC;
    }

    cout << sum << endl;

    return 0;

}

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

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

int getChar(char ch){
  if( ch == 'A' ) return 1;
  else if( ch == 'C' ) return 2;
  else if( ch == 'G' ) return 3;
  else if( ch == 'T' ) return 4;
  else return 0;
}

long long getKey(char str[]){
  long long sum=0, p=1, i;
  for( i = 0 ; i < strlen(str) ; i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ return key % M; }
int h2(int key){ return 1+(key%(M-1)); }

int find(char str[]){
  long long key, i, h;
  key = getKey(str);
  for( i = 0 ; ;  i++ ){
    h = ( h1(key) + i*h2(key)) % M;
    if( strcmp(H[h],str) == 0 ) return 1;
    else if( strlen(H[h]) == 0 ) return 0;
  }
  return 0;
}

int insert(char str[]){
  long long key, i, h;
  key = getKey(str);
  for( i = 0 ; ; i++ ){
    h = ( h1(key) + i * h2(key)) % M;
    if( strcmp(H[h],str) == 0 ) return 1;
    else if( strlen(H[h]) == 0 ){
      strcpy(H[h], str);
      return 0;
    }
  }
  return 0;
}

int main(){
  int i, n, h;
  char str[L], com[9];
  for( i = 0 ; i < M ; i++ ) H[i][0] = '\0';
  scanf("%d", &n);
  for( i = 0 ; i < n ; i++ ){
    scanf("%s %s", com, str);

    if( com[0] == 'i' ){
      insert(str);
    }
    else{
      if( find(str) ){
	printf("yes\n");
      }
      else printf("no\n");
    }
  }
  return 0;
}



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

int main() {

    int a,b;
    cin >> a >> b;

    int mean = (int)ceil((a+b)/2.0);
    cout << mean << endl;
//
//    string ans;
//    if(N <= A){
//        ans = "Yes";
//    }else{
//        ans = "No";
//    }
//    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
memo = {}

def func(i, j):
    if (i, j) in memo:
        return memo[(i, j)]

    count = 0
    n = 1
    while n <= N:
        str_n = str(n)

        if n >= 10 and str_n[0] != str(j):
            n += 10 ** (len(str_n) - 1)
            continue

        if str_n[-1] == str(i) and str_n[0] == str(j):
            count += 1
            n += 10
            continue

        n += 1
    
    memo[(i,j)] = count
    return count

ret = 0
for i in range(1, N+1):
    ret += func(str(i)[0], str(i)[-1])

print(ret)




Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); (i)--)
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
using namespace std;
typedef pair<int, int> P;

int main(){
    int n, W; cin >> n >> W;
    int v[n], w[n]; rep(i, n) cin >> v[i] >> w[i];
    int dp[n+1][10010];
    const int INF = 1000000010;
    rep(i, n+1)rep(j, 10010) dp[i][j] = INF;
    dp[0][0] = 0;
    rep(i, n)rep(j, 10001)if(dp[i][j] < INF){
        dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
        dp[i+1][min(j+v[i], 10005)] = min(dp[i+1][min(j+v[i], 10005)], dp[i][j] + w[i]);
    }
    int ans = 0;
    rep(j, 10001)if(dp[n][j] <= W) ans = j;
    cout << ans << endl;
}


Measured memory_bytes: 7032
class Counting_Sort():
    def __init__(self, N, input_number_list):
        self.N = N
        self.number_list = input_number_list
        self.print_number_list = list()

    def counting_sort(self):
        counting_list = list()
        for i in range(10001):
            counting_list.append(0)
        for i in range(self.N):
            counting_list[self.number_list[i]] += 1
            self.print_number_list.append(0)
        for i in range(1,10001):
            counting_list[i] += counting_list[i-1]
        for i in range(self.N-1,-1,-1):
            self.print_number_list[counting_list[self.number_list[i]]-1] = self.number_list[i]
            counting_list[self.number_list[i]] -= 1

def print_number_list(number_list, N):
    for i in range(N):
        if i != N - 1:
            print(number_list[i],end=' ')
        else:
            print(number_list[i])

def main():
    N = int(input())
    input_number_list = [int(i) for i in input().split()]
    sort = Counting_Sort(N,input_number_list)
    sort.counting_sort()
    print_number_list(sort.print_number_list,N)

if __name__ == "__main__":
    main()


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

int main() {
  int N, L;
  cin >> N >> L;
  vector<string> S(N);
  for (int i = 0; i < N; i++) cin >> S.at(i);
  
  sort(S.begin(), S.end());
  string str = "";
  for (auto s: S) {
    str += s;
  }
  
  cout << str << endl;
}


Measured memory_bytes: 3476
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func reduce(f func(x, y int) int, a []int) int {
	result := a[0]
	for i := 1; i < len(a); i++ {
		result = f(result, a[i])
	}
	return result
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func fill(a []int, x int) {
	for i := 0; i < len(a); i++ {
		a[i] = x
	}
}

func main() {
	N := readInt()
	W := readInt()

	dp := make([]int, W+1)
	fill(dp, -1)
	dp[0] = 0

	for i := 0; i < N; i++ {
		w := readInt()
		v := readInt()
		for j := W - w; j >= 0; j-- {
			if dp[j] == -1 {
				continue
			}
			dp[j+w] = max(dp[j+w], dp[j]+v)
		}
	}
	fmt.Println(reduce(max, dp))
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}


Measured memory_bytes: 2632
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include <cstdlib>

using namespace std;

int main(){

	char a[3];
	int count= 0;
	for(int i = 0; i < 3; i++){
		cin >> a[i];
	}
	for(int i = 0; i < 3; i++){
		if(a[i] == 'o'){
			count ++;
		}
	}
	cout << count*100 + 700 <<endl;

	return 0;
}


Measured memory_bytes: 256
#二分探索
N = int(input())
A = [0] + sorted(map(int,input().split()))

def check(i):
    a = sum(A[:i+1])
    for b in A[i+1:]:
        if a*2>=b:
            a += b
        else:return False
    return True

l = 0
r = N
while l+1<r:
    i = (l+r)//2
    if check(i):
        r = i
    else:
        l = i

print(N-l)

Measured memory_bytes: 14320
#include <stdio.h>
#define MAX 2000001

int A[MAX];
int B[MAX];
int C[MAX];

int n;

void CountingSort(int A[], int B[], int k){
  int i, j;

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

int main(){
  int i;
  int k=0;

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

  CountingSort(A, B, k);

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



Measured memory_bytes: 17372
#include <cstdio>

int h, w;
int road;
char s[8][9];
char st[8][8];

void dfs(int x, int y, int count)
{
  st[y][x] = count;
  const int dir[] = {0, 1, 0};
  for (int i = 0; i < 2; ++i)
  {
    int X = x + dir[i + 1];
    int Y = y + dir[i];
    if (0 <= X && X < w && 0 <= Y && Y < h && st[Y][X] == 0 && s[Y][X] == '#')
    {
      dfs(X, Y, count + 1);
    }
  }
}

int main()
{
  scanf("%d%d", &h, &w);
  for (int i = 0; i < h; ++i)
  {
    scanf("%s", s[i]);
    for (int j = 0; j < w; ++j)
    {
      if (s[i][j] == '#') ++road;
    }
  }
  dfs(0, 0, 1);
  puts(st[h - 1][w - 1] == road ? "Possible" : "Impossible");
  return 0;
}

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

typedef long  long ll;
#define FF first
#define SS second
#define INF 2000000000


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

    int n;
    cin >> n;
    vector<int> perm(n), a(n), b(n);
    for(int i = 0; i < n; ++i){
        perm[i] = i + 1;
    }
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    for(int i = 0; i < n; ++i){
        cin >> b[i];
    }


    map<vector<int>, int> mp;

    int i = 1;
    do{
        mp[perm] = i;
        ++i;
    }
    while(next_permutation(perm.begin(), perm.end()));

    cout << abs(mp[a] - mp[b]) << "\n";

}


Measured memory_bytes: 5248
#include<bits/stdc++.h>
using namespace std;
typedef		long long       ll;
typedef         long double      dl;
typedef     unsigned long long  ull;
#define		pb              push_back
#define		PB              pop_back
#define		nn              "\n"
#define     O_O             ios_base::sync_with_stdio(false); cin.tie(NULL)
#define		all(p)          p.begin(),p.end()
#define		zz(v)           (ll)v.size()
#define		ss              ' '
#define f0(i,b) for(int i=0;i<(b);i++)
#define f1(i,b) for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)
#define rep(i,a,b,c) for(int i=(a);i!=(b);i+=(c))
#define         arrsize(a)      (sizeof(a)/sizeof(a[0]))
//#define       arrsize(a)      (sizeof(a)/sizeof(*a))
#define 	S(a)            scanf("%lld",&a)
#define 	SS(a,b)         scanf("%lld %lld",&a,&b)
#define 	SSS(a,b,c)      scanf("%lld %lld %lld",&a,&b,&c)
#define		gcd(a,b)        __gcd(a,b)
#define		lcm(a,b)        (a*b)/gcd(a,b)
#define		pi              acos(-1.0)
typedef        pair <int, int>   pii;
typedef       pair <ll, ll>      pll;
typedef      vector< pair <ll, ll> >      vpll;
typedef		vector<ll>      vll;
typedef		map<string,ll>      msl;
typedef		map<ll,ll>      mll;
#define yes cout << "YES\n"
#define no cout<<"NO\n"
//memset(ar,-1,sizeof(ar));
//#define sort(x) sort(x.begin(), x.end())
//sort(a,a+n,greater<ll>())
//for (auto it = mp.begin(); it != mp.end(); ++it){}
#define MAX 1000005
#define mod 1000000007



int main()
{
 //O_O ;
   string s;
   cin>>s;
   ll x=s.length()-1;
   if(s[x]=='2'||s[x]=='4'||s[x]=='5'||s[x]=='7'||s[x]=='9')
    cout<<"hon"<<nn;
    else if(s[x]=='0'||s[x]=='1'||s[x]=='6'||s[x]=='8')
    cout<<"pon"<<nn;
    else if(s[x]=='3')
    cout<<"bon"<<nn;



    return 0;
}



Measured memory_bytes: 3624
import itertools


def dbg(s):
    # print(s)
    pass


N = int(input())
Ls = [int(i) for i in input().split()]


def is_ok(i, j, k):
    dbg(f"{i=},{j=},{k=}")
    if not (i != j and j != k and i != k):
        return False
    ls = [i, j, k]
    ls.sort()
    dbg(f"{ls=}")
    return ls[2] < ls[0] + ls[1]


count = 0
for tri in itertools.combinations(Ls, 3):
    if is_ok(tri[0], tri[1], tri[2]):
        count += 1

print(count)


Measured memory_bytes: 9196
/*
 * written by Yaqi Zhang
 * University of Wisconsin-Madison
 * 2020
 */

#include<algorithm>
#include<cstring>
#include<iostream>
#include<map>
#include<set>
#include<stdio.h>
#include<vector>

#define INF 0x3f3f3f3f

using namespace std;


int n, x, y;
const int N = 2e3 + 5;
vector<vector<int>> graph(N);
int counter[N];


void bfs(int start) {
    vector<int> frontier = {start};
    vector<int> level(n + 1, -1);
    level[start] = 0;
    while(!frontier.empty()) {
        vector<int> next_level;
        for(int u : frontier) {
            for(int v : graph[u]) {
                if(level[v] == -1 || level[v] > level[u] + 1) {
                    level[v] = level[u] + 1;
                    next_level.push_back(v);
                }
            }
        }
        swap(next_level, frontier);
    }
    for(int i = start + 1; i <= n; ++i) ++counter[level[i]];
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x >> y;
    memset(counter, 0, sizeof(counter));
    for(int i = 1; i <= n - 1; ++i) {
        graph[i].push_back(i + 1);
        graph[i + 1].push_back(i);
    }
    graph[x].push_back(y);
    graph[y].push_back(x);
    for(int u = 1; u <= n; ++u) bfs(u);
    for(int k = 1; k < n; ++k) {
        // do dfs on each vertex
        // and populate cost array
        cout << counter[k] << endl;
    }
    return 0;

}



Measured memory_bytes: 384
n, m  = map(int, input().split())

if n == 1:
  print(1)
  exit()

f = [0 for i in range(n)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for i in range(n-2)[::-1]:
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

if f[0] != -1 and f[1] != -1:
  print(int((f[0]+f[1])%div_num))
elif f[0] == -1 and f[1] != -1:
  print(int(f[1]%div_num))
elif f[0] != -1 and f[1] == -1:
  print(int(f[0]%div_num))
else:
  print(0)


Measured memory_bytes: 460080