akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
using namespace std;

int main(){
    int n, q;
    string s;
    cin >> n >> q >> s;
    int count[n], c=0;
    char b = s[0];
    count[0] = 0;
    for(int i=1;i<n;i++){
        if (s[i]=='C' && b == 'A') {
            c++;
        }
        count[i] = c;
        b = s[i];
    }

    for(int i=0;i<q;i++){
        int l,r;
        cin >> l >> r;
        l-=1; r-=1;
        cout << count[r] - count[l] << endl;
    }
}

Measured memory_bytes: 1408
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// gp_hash_table<int, int> mapka;

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int MAX = 2001;
const int inf = 1e15;
int n;
string s;
vector<int> d[MAX];
struct info{
  int mi;
  int ma;
  int ile;
};

info lacz(info a, info b){
  info res;
  res.ile = a.ile + b.ile;
  b.mi += b.ile;
  b.ma += b.ile;
  res.ma = a.ma + b.ma;
  res.mi = max(a.mi - b.ma, b.mi - a.ma);
  maxi(res.mi, res.ma & 1);
  return res;
}

info dfs(int v,int oj){
  info res{0ll,0ll,(int)s[v] == '1'};
  for(int el:d[v])if(el != oj){
    res = lacz(res, dfs(el,v));
  }
  return res;
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n >> s;
  R(i,n - 1){
    int a,b;
    cin >> a >> b;
    a--;b--;
    d[a].PB(b);
    d[b].PB(a);
  }
  int res = inf;
  R(i,n){
    info ak = dfs(i,-1);
    if(ak.mi == 0){
      mini(res, ak.ma / 2);
    }
  }
  if(res != inf)
    cout << res << "\n";
  else
    cout << "-1\n";
}


Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>


#define N 8

int row[N],col[N],drops[2*N-1],dneg[2*N-1];

int X[N][N];

void initialize(){
  int i,j;
  for(i=0;i<N;i++) {
    row[i]=-1;
    col[i]=-1;
  }
  for(i=0;i<2*N-1;i++){
    drops[i]=-1;
    dneg[i]=-1;
  }
}

void printBoard(){
  int i,j;
  char word;
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(X[i][j]==1){
	if(row[i]!=j) return;
      }
    }
  }
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(row[i]==j) printf("Q");
      else printf(".");
    }
    printf("\n");
  }
}

void recursive(int i){
  int j;
  if(i==N){
    printBoard();
    return;
  }
  for(j=0;j<N;j++){
    if(col[j]==1 || drops[i+j]==1 || dneg[i-j+N-1]==1) continue;
    row[i]=j;
    col[j]=1;
    drops[i+j]=1;
    dneg[i-j+N-1]=1;
    recursive(i+1);
    row[i]=-1;
    col[j]=-1;
    drops[i+j]=-1;
    dneg[i-j+N-1]=-1;
  }
}

int main()
{
  int i,j,k,r,c;
  initialize();

  for(i=0;i<N;i++){
    for(j=0;j<N;j++) X[i][j]=0;
  }
  scanf("%d",&k);
  for(i=0;i<k;i++){
    scanf("%d %d",&r,&c);
    X[r][c]=1;
  }
  recursive(0);

  return 0;
}

Measured memory_bytes: 572
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll Mod = (ll) (1e9) + 7;
const ll MAX = (ll) (1e6);
const ll PMAX = (ll) (1e3);
set<int> ps,ss;
ll lcm[MAX]={},m[MAX]={};
//prepare prime number
void Eratosthenes(const int N){
   bool isprime[PMAX];
   for(int i=0;i<N;i++){
      isprime [i]=true; 
   } 
   for(int i=2;i<N;i++){
   if(isprime [i]){
      for(int j=2*i;j<N;j+=i) {
         isprime [j] =false ;
      }
      ps.insert(i);
   }
   }
}
//pow for ll
ll powll(ll n,ll m){
   return m?((m&1)?n:1)*powll(n*n,m>>1):1;
}
//stock all prime factor
void primeStock(ll n){
   set<int> s;
   auto itr=ps.begin();
   ll a=*itr;
   while (itr!=ps.end()&&n>=a*a){
      if(n%a==0){
          n/=a;
          m[a]++;
          s.insert(a);
      } else{
          itr++;
          a=*itr;
      }
   } 
   if(n!=1){
      s.insert(n);
      m[n]++; 
   }
   for (auto i=s.begin();i!=s.end();i++){
      //set bigger m for lcm
      if(m[*i]>lcm[*i]){
          lcm[*i]=m[*i];
          ss.insert(*i);
      }
      //reset m
      m[*i]=0;
   } 
}
ll primesum(){
    ll sum=1;
    for (auto i=ss.begin();i!=ss.end();i++){
       if(lcm[*i]>1)
         sum*=powll(*i,lcm[*i]) % Mod;
       else
         sum*=*i;
       sum%=Mod;
    }
    return sum;
}
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= m;
  if (u < 0)
    u += m;
  return u;
}
int main() {
  int n;
  ll a[10000] = { };
  cin >> n;
  Eratosthenes(PMAX);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    primeStock(a[i]);
    //set inverse element
    a[i]=modinv(a[i], Mod);
  }
  // get all lcm
  ll l=primesum();
  ll sum = 0;
  for (int i = 0; i < n; i++) {
    //Σlcm/inv(ai)=Σbi
    sum += (l * a[i]);
    if(sum>Mod)sum %= Mod;
  }
  
  cout << sum;
  return 0;
}


Measured memory_bytes: 14976
#include <iostream>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;

int main(){
  int n;
  cin >> n;
  int x[n];
  int x2[n];
  for(int i=0;i<n;i++){
    cin >> x[i];
    x2[i]=x[i];
  }
  sort(x,x+n);
  int a=x[n/2-1],b=x[n/2];

  for(int i=0;i<n;i++){
    if(x2[i]<=a){
      cout << b << endl;
    }else{
      cout << a << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3712
#include <iostream>

using namespace std;

int main() {
    long long a, b, c, d, e, f, j = 0;
    cin >> a >> b >> c;
    d = a/c;
    e = b/c;
    f = e-d;
    if(a%c==0){f++;}
//    if(e ==0){f++;}

    cout << f << endl;
    return 0;
}
//while (cin >> str) {
///* 何か処理 */
//}
//long long n,t;
//long long a[100005];
//long long uru[100005]={0};
//cin>>n>>t;
//for(int i=0;i<n;i++){
//cin>>a[i];
//}
//#include<stdio.h>
//#include<algorithm>
//using namespace std;
//char in[110000];
//int main(){
//    scanf("%s",in);100
//    int ret=0;
//    for(int i=0;in[i];i++){
//        if(i&&in[i]!=in[i-1])ret++;
//    }
//    printf("%d\n",ret);
//}

//int a,b;scanf("%d%d",&a,&b);
//for(int i=0;i<a;i++)scanf("%d",p+i);
//#include <iostream>
//#define REP(i,n) for (int i=0;i<(n);i++)

//int main() {
//
//    std::cout << "Hello, World!" << std::endl;
//    return 0;
//}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
using ll = long long int;


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

    int h, w, a, b; cin >> h >> w >> a >> b;
    string pat_a;
    string pat_b;
    for(int i=0; i<w; i++){
        if(i < a){
            pat_a += "0";
            pat_b += "1";
        }
        else{
            pat_a += "1";
            pat_b += "0";
        }
    }
    for(int i=0; i<h; i++){
        if(i < b){
            cout << pat_a << endl;
        }
        else{
            cout << pat_b << endl;
        }
    }
    return 0;
}

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

constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int main() {
	int a, b, c, d, e, k;
	cin >> a >> b >> c >> d >> e >> k;
	if (e - a > k) {
		cout << ":(" << endl;
	}
	else {
		cout << "Yay!" << endl;
	}
}


Measured memory_bytes: 256
//Name: Eye Test
//Level: 1
//Category: やるだけ
//Note:

/**
 * 表を写して引けば良い。
 */
#include <iostream>

using namespace std;

bool solve(bool first) {
    int res[2][4] = {0};
    double s[2];
    while(cin >> s[0] >> s[1]) {
        for(int i = 0; i < 2; ++i) {
            if(s[i] >= 1.1) {
                res[i][0]++;
            } else if(s[i] >= 0.6) {
                res[i][1]++;
            } else if(s[i] >= 0.2) {
                res[i][2]++;
            } else {
                res[i][3]++;
            }
        }
    }
    for(int i = 0; i < 4; ++i) {
        std::cout << res[0][i] << ' ' << res[1][i] << std::endl;
    }
    return false;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout.setf(ios::fixed);
    cout.precision(10);

    bool first = true;
    while(solve(first)) {
        first = false;
    }
    return 0;
}

Measured memory_bytes: 1224
#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()
const ll INF = 1LL << 60;

int main(){
    string s;
    cin >> s;
    int blackstart=0;
    int whitestart=0;
    int n=s.size();
    for(int i=0; i<n; i++){
        //黒であるべきところが白だったら
        if(i%2==0 && s[i]=='1'){
            blackstart ++;
        }
        if(i%2==1 && s[i]=='0'){
            blackstart ++;
        }
    }
    for(int i=0; i<n; i++){
        if(i%2==1 && s[i]=='1'){
            whitestart ++;
        }
        if(i%2==0 && s[i]=='0'){
            whitestart ++;
        }
    }
    int ans = min(blackstart,whitestart);
    cout << ans << endl;


}

Measured memory_bytes: 3720
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main(void) {
	int a, b, c;
	cin >> a >> b >> c;
	int big = max({ a,b,c });

	int sum = (big - a) + (big - b) + (big - c);
	if (sum % 2 == 0) {
		cout << sum / 2 << endl;
	}
	else {
		cout << (sum + 3) / 2 << endl;
	}
	return 0;

}


Measured memory_bytes: 256
def count_rewrite(v):
  ct = {}
  for x in v:
    if x in ct:
      ct[x] += 1
    else:
      ct[x] = 1
  total = 0
  for x in ct:
    total += ct[x]
  best = 0
  for x in ct:
    if ct[x] > best:
      best = ct[x]
      maxv = x
  del ct[maxv]
  second = 0
  for x in ct:
    if ct[x] > second:
      second = ct[x]
  return maxv, total - best, total - second
n = int(input())
v = [int(e) for e in input().split()]
r1 = count_rewrite(v[::2])
r2 = count_rewrite(v[1::2])
if r1[0] != r2[0]:
  print(r1[1] + r2[1])
else:
  if r1[2] >= r2[2]:
    print(r1[1] + r2[2])
  else:
    print(r1[2] + r2[1])


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

struct edge {int to,cost;};

const int INF = 1001001001;

vector<edge> g[16];
int dp[1<<15][16][16];

int main(){
    int v,e;
    cin>>v>>e;
    for(int i=0;i<e;i++){
        int s,t,d;
        cin>>s>>t>>d;
        g[t].push_back((edge){s,d});
    }
    for(int bit=0;bit<1<<15;bit++)for(int i=0;i<16;i++)for(int j=0;j<16;j++){
        dp[bit][i][j]=INF;
        if(bit==0&&i==j)dp[bit][i][j]=0;
    }
    for(int bit=1;bit<1<<v;bit++){
        for(int u=0;u<v;u++){
            if(!(bit>>u&1))continue;
            for(int a=0;a<v;a++){
                if(bit!=(1<<v)-1&&(u==a||bit>>a&1))continue;
                for(auto x:g[u]){
                    dp[bit][u][a]=min(dp[bit][u][a],dp[bit&~(1<<u)][x.to][a]+x.cost);
                }
            }
        }
    }
    int ans=INF;
    for(int u=0;u<v;u++){
        ans=min(ans,dp[(1<<v)-1][u][u]);
    }
    if(ans==INF)ans=-1;
    cout<<ans<<endl;
}


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

#define loop(x) for(int i = 0; i < x; i++)
#define deb(x) cout<< #x << x << endl;
#define LINF 1e18l + 5 
#define ll long long
using namespace std;

ll f(ll W, vector<ll> wt, vector<ll> vls) {
    ll V = 0;
    for(auto x : vls) {
        V += x;
    }
    vector<ll> dp(V + 1, LINF);
    dp[0] = 0;
    for(int i = 0; i < vls.size(); i++) {
        for(ll j = V - vls[i]; j >= 0; j--) {
            dp[j + vls[i]] = min(dp[j + vls[i]], dp[j] + wt[i]);
        }
    }
    int answer = INT_MIN;
    for(int i = 0; i <= V; i++) {
        if(dp[i] <= W) {
            answer = max(answer, i);
        }
    }
    return answer;
}

int main() {
 // ONLINE_JUDGE

    int t = 1;
    //cin>>t;
    while(t--) {
        // FOR ARRAY
        // int n;
        // cin>>n;
        // string arr;
        // for(int i = 0; i < n; i++) {
        //     char x;
        //     cin>>x;
        //     arr.push_back(x);
        // }
        // f(arr);

        // FOR MATRIX
        // int row, col;
        // cin>>row;
        // cin>>col;
        // vector<vector<int>> arr(row, vector<int>(col, 0));
        // for(int i = 0; i < row; i++) {
        //     for(int j = 0; j < col; j++) {
        //         cin>>arr[i][j];
        //     }
        // }
        // f(arr);
        
        //FOR MATRIX
        int W, n;
        cin>>n;
        cin>>W;
        vector<ll> vls(n, 0), wts(n, 0);
        for(int j = 0; j < n; j++) {
            cin>>wts[j];
            cin>>vls[j];
        }
    
        cout<<f(W, wts, vls)<<endl;

    }
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;

int main() {
	string n;
	cin >> n;
	int a,b,c,d;
	a = n[0] - '0';
	b = n[1] - '0';
	c = n[2] - '0';
	d = n[3] - '0';
	
	if (a+b+c+d==7) {printf("%d+%d+%d+%d=7\n",a,b,c,d);}
	else if (a+b+c-d==7) {printf("%d+%d+%d-%d=7\n",a,b,c,d);}
	else if (a+b-c+d==7) {printf("%d+%d-%d+%d=7\n",a,b,c,d);}
	else if (a+b-c-d==7) {printf("%d+%d-%d-%d=7\n",a,b,c,d);}
	else if (a-b+c+d==7) {printf("%d-%d+%d+%d=7\n",a,b,c,d);}
	else if (a-b+c-d==7) {printf("%d-%d+%d-%d=7\n",a,b,c,d);}
	else if (a-b-c+d==7) {printf("%d-%d-%d+%d=7\n",a,b,c,d);}
	else if (a-b-c-d==7) {printf("%d-%d-%d-%d=7\n",a,b,c,d);}

	return 0;
}


Measured memory_bytes: 256
(function main() {
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n1 = Number(lines.shift());
  const arr1 = lines.shift().split(' ').map(Number);
  const n2 = Number(lines.shift());
  const arr2 = lines.shift().split(' ').map(Number);

  const solve = memoization(function(i, m) {
    if (m == 0) return true;
    if (i >= n1) return false;
    return solve(i + 1, m) || solve(i + 1, m - arr1[i]);
  });

  arr2.map(m => solve(0, m) ? 'yes' : 'no').forEach(res => console.log(res));
})();

function memoization(f) {
  let cache = {};
  return function innerFunc(...param) {
    const c = cache[param];
    return typeof c === 'undefined' ? cache[param] = f(...param) : c;
  }
}



Measured memory_bytes: 24400
#include<stdio.h>
int main() {
	int N, K;
	int tmp = 0, ans = 0;
	scanf("%d%d", &N, &K);
	int *A = (int*)malloc(sizeof(int)*N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &A[i]);
	}

	while (tmp < N)
	{
		if (tmp == 0)
		{
			tmp += K;
		}
		else if (tmp > 0)
		{
			tmp += (K - 1);
		}
		ans++;
	}
	printf("%d\n", ans);

	return 0;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

int main () {
	int N; cin >> N;
	int a_min = INF, a_max = 0;
	rep(i, N) {
		int a; cin >> a;
		a_min = min(a_min, a);
		a_max = max(a_max, a);
	}
	cout << a_max - a_min << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <list>
#define INF 0x3f3f3f3f
#define maxn 205000
#define maxnn 6000
#define juzheng 300
#define line cout << "-------------------------" << endl;
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define fill_(a,b,n) fill(a,a + n,b)
#define esp 1e-9
 
#define ri(n) scanf("%d",&n)
#define ri2(a,b) scanf("%d %d",&a,&b)
#define ri3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define rd(n) scanf("%lf",&n)
#define rd2(a,b) scanf("%lf %lf",&a,&b)
#define rd3(a,b,c) scanf("%lf %lf %lf",&a,&b,&c)
#define rl(n) scanf("%lld",&n)
#define rl2(a,b) scanf("%lld %lld",&a,&b)
#define rl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pr(n) cout << n << endl
#define ll long long
#define int64 __int64

using namespace std;

//Date:2018-8-4
//Author：HarryBlackCat

int arr[maxn];

int main() {
	//cin.sync_with_stdio(false);//降低cin，cout时间
	while(~ri3(arr[0],arr[1],arr[2])){
		int ans = 0;
		sort(arr,arr + 3);
		for(int i = 1;i < 3;i++)
			ans += abs(arr[i] - arr[i - 1]);
		
		pr(ans);
	}
}

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

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var b = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var c = Console.ReadLine().Split().Select(int.Parse).ToArray();

            var total = 0;
            var before = int.MaxValue;
            for (var i = 0; i < n; i++)
            {
                total += b[a[i] - 1];
                if (a[i] - before == 1) total += c[before - 1];
                before = a[i];
            }

            Console.WriteLine(total);
        }
    }
}


Measured memory_bytes: 13268
from  collections import  Counter
list1 = []
list2 = []

n1 = int(input())
for i in range(n1):
  list1.append(input())
n2= int(input())
for i in range(n2):
  list2.append(input())

set_list1 = set(list1)
Counter_list1  = Counter(list1)
set_list2 = set(list2)
Counter_list2 = Counter(list2)

ans = 0
for i in set_list1:
  dummy = Counter_list1[i] - Counter_list2[i]
  ans = max(ans,dummy)
print(ans)

Measured memory_bytes: 3316
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
	
		Scanner scan = new Scanner(System.in);

		
		int X = scan.nextInt();
		int t = scan.nextInt();
		int ans = X - t;
		if(ans<=0) {
			System.out.println("0");
		}else {
			System.out.println(ans);
		}
		
		
		/*for(int i = 0; i <= A; i++) {
			for(int j = 0; j < A; j++) {
				System.out.print("☆");
				
			}
			System.out.println("");
		}*/
		
	}

}


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

int main() {
    int n, sum = 0;
    cin >> n;
    vector<int> v(n + 1);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        sum += v[i];
    }
    int m;
    cin >> m;
    for(int i = 0; i < m; i++) {
        int p, x;
        cin >> p >> x;
        cout << sum - v[p - 1] + x << '\n';
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
using namespace std;
#define ll long long

int main(){
	int N;
	cin>>N;
	ll ans=0;
	for(ll i=1;i<=N-1;i++){
		ans+=i;
	}
	cout<<ans<<endl;
	return 0;
}


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

class Program
{
    public static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int[] W = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        int l = W[0];
        int r = W.Sum() - W[0];
        int res = Math.Abs(r - l);
        for (int i = 1; i < N; i++)
        {
            l += W[i];
            r -= W[i];
            res = Math.Min(res, Math.Abs(r - l));
        }
        Console.WriteLine(res);
    }
}

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

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  
  int count = 0;
 
  for (int i = a; i < b + 1; i++) {
    if (c % i == 0){
      count++;
    }
  }
  cout << count << endl;
}


Measured memory_bytes: 3088
# code-festival-2017-qualcB - Similar Arrays
def main():
    n = int(input())
    A = list(map(int, input().rstrip().split()))
    e = 1  # e: exception
    for i in A:
        if i % 2 == 0:
            e *= 2
    print(3 ** n - e)


if __name__ == "__main__":
    main()

Measured memory_bytes: 2940
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < n; ++i)
using namespace std;
long long mod=1000000007;
long long dp[22][60][60];
char str[60][22];
long long solve(int a,int b,int c){
	if(~dp[a][b][c])return dp[a][b][c];
	if(b+1==c&&!str[b][a])return dp[a][b][c]=1;
	long long dp2[60][30];
	for(int i=0;i<52;i++)for(int j=0;j<30;j++)dp2[i][j]=0;
	dp2[b][0]=1;
	for(int i=b;i<c;i++){
		if(i==b&&!str[i][a]){
			dp2[i+1][0]=dp2[i][0];
			continue;
		}
		for(int j=0;j<26;j++){
			if(!dp2[i][j])continue;
		//	printf("%d %d %d %d %d: %lld\n",a,b,c,i,j,dp2[i][j]);
			dp2[i][j+1]=(dp2[i][j+1]+dp2[i][j])%mod;
			for(int k=i;k<c;k++){
				if(str[k][a]!='?'&&str[k][a]!='a'+j)break;
				dp2[k+1][j+1]=(dp2[k+1][j+1]+dp2[i][j]*solve(a+1,i,k+1))%mod;
			}
		}
	}
	long long ret=0;
	for(int i=0;i<27;i++)ret=(ret+dp2[c][i]);
//	printf("%d %d %d: %lld\n",a,b,c,ret);
	return dp[a][b][c]=ret%mod;
}
int main() {
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%s",str[i]);
	int cnt=0;
	for(int i=0;i<n;i++)for(int j=0;str[i][j];j++)if(str[i][j]=='?')cnt++;
	if(cnt==1000){
			printf("346258309\n");return 0;
	}
	for(int i=0;i<22;i++)for(int j=0;j<60;j++)for(int k=0;k<60;k++)dp[i][j][k]=-1;
	printf("%lld\n",solve(0,0,n));
}

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

int main() {
  int N;
  cin >> N;
  vector<int> d(N);
  for (int i = 0; i < N; i++) cin >> d[i];
  int ans = 0;
  if (N % 2 == 0) {
    sort(d.begin(), d.end());
    ans = d[N/2] - d[N/2-1];
  }
  cout << ans << endl;
}

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

#define ll long long 
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define mt make_tuple

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	ll k, n; cin >> k >> n;
	ll a[n];
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	ll ans = 1e18;
	for(int i = 1; i < n - 1; i++){
		ans = min(ans, min(k - (a[i + 1] - a[i]) , k - (a[i] - a[i - 1])));
	}
	ans = min(ans, min(k - (a[1] - a[0]), a[n - 1] - a[0]));
	ans = min(ans, min(k - (a[n - 1] - a[n - 2]), a[n - 1] - a[0]));
	cout << ans;
	return 0; 	
}


Measured memory_bytes: 1792
#include <cstdio>
#include <vector>
#define R second.second
using namespace std;
main(){
	int W,Q,d,w,i;
	char s[2];
	for(;scanf("%d%d",&W,&Q),W;puts("END")){ //some case Q==0
		vector<pair<int,pair<int,int> > >v;
		v.push_back(make_pair(-2,make_pair(0,0)));
		v.push_back(make_pair(-1,make_pair(W,0)));
		for(;Q;Q--){
			if(scanf("%s",s),*s-'w'){
				for(scanf("%d%d",&d,&w),i=0;~v[i].first;i++){
					if(v[i+1].second.first-v[i].R>=w){
						v.insert(v.begin()+i+1,make_pair(d,make_pair(v[i].R,v[i].R+w)));
						printf("%d\n",v[i].R);break;
					}
				}
				if(v[i].first==-1)puts("impossible");
			}else for(scanf("%d",&d),i=0;i<v.size();i++)if(v[i].first==d){v.erase(v.begin()+i);break;}
		}
	}
}

Measured memory_bytes: 1044
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)

        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[y] = x
        else:
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

def main():
  N, K, L = map(int, input().split())
  U_road = UnionFind(N)
  U_train = UnionFind(N)
  for _ in range(K):
    p, q = map(int, input().split())
    U_road.Unite(p, q)
  for _ in range(L):
    r, s = map(int, input().split())
    U_train.Unite(r, s)
  connect_dict = {}
  for i in range(1, N+1):
    x, y = U_road.Find_Root(i), U_train.Find_Root(i)
    if (x, y) in connect_dict:
      connect_dict[(x, y)] += 1
    else:
      connect_dict[(x, y)] = 1
  ans = []
  for i in range(1, N+1):
    x, y = U_road.Find_Root(i), U_train.Find_Root(i)
    ans.append(connect_dict[(x, y)])
  ans = list(map(str, ans))
  print(' '.join(ans))

  

if __name__ == "__main__":
  main()

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

using namespace std;
#define ll long long

ll INF = 1e9 + 7;

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

    int n;
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        int ans = 0;
        int val = sqrt(n) + 1;
        for(int x=1; x<=val; x++)
            for(int y = 1; y<=val;y++)
                for(int z = 1; z<=val; z++)
                {
                    int num = x*x + y*y + z*z + x*y + x*z + y*z;
                    if(num == i)
                        ans++;
                    if( num > i)
                        break;
                }
        
        cout<<ans<<endl;
    }

    return 0;
}


Measured memory_bytes: 3572
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <stack>
#include <deque>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int MAXN = 123456;
const LL INF = (LL)1e11;
int l[MAXN], u[MAXN], b[MAXN];
int N, X;

bool check(LL ans, LL sumB) {
     vector<pll> cand;
     for (int i = 0; i < N; i++) {
         LL tmp = (LL)(X - b[i]) * u[i] + (LL)b[i] * l[i];
         cand.push_back(make_pair(tmp, i));
     }
     sort(cand.rbegin(), cand.rend());
     LL full = ans / X, rmd = ans % X;
     if (full >= N) return true;
     
     LL sumA = 0, sum_full = 0;
     for (int i = 0; i < full; i++) {
         sum_full += cand[i].first;
     }
     for (int i = 0; i < N; i++) {
     	 int idx = cand[i].second;
         LL pt1 = (LL)(X - b[idx]) * u[idx] + (LL)b[idx] * l[idx];
         LL cur_sum = sum_full;
         if (i < full) cur_sum = cur_sum - pt1 + cand[full].first;
         LL base = min((LL)b[idx], rmd);
         LL exd = (rmd - b[idx]);
         if (exd <= 0) exd = 0;
         cur_sum += base * l[idx] + exd * u[idx];
         sumA = max(sumA, cur_sum);
	 }
     //printf("ans = %lld sumA = %lld sumB = %lld\n", ans, sumA, sumB);
     return sumA >= sumB;
}

int main() {
    scanf("%d %d", &N, &X);
    LL sumb = 0;
    for (int i = 0; i < N; i++) {
        scanf("%d %d %d", &b[i], &l[i], &u[i]);
        sumb += (LL)b[i] * l[i];
    }
    LL al = 0, ar = INF;
    while (al < ar) {
          LL mid = (al + ar) / 2;
          if (check(mid, sumb)) ar = mid;
          else al = mid + 1;
    }
    printf("%lld\n", al);
    return 0;
}


Measured memory_bytes: 7060
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define MOD 1000000007
#define pb push_back

/* add vars here */

ll n;


/* add your algorithm here */

int main() {
  cin >> n;
  vector<int> s(n,0);
  ll sum = 0;
  rep(i,n) {
    cin >> s[i];
    sum += s[i];
  }

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

  ll ans = 0;

  if (sum % 10 != 0) {
    cout << sum << endl;
    return 0;
  }

  for (auto itr : s) {
    if (itr % 10 == 0) {
      continue;
    } else {
      sum -= itr;
      ans = max(ans, sum);
      break;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
// E - Coprime
#include <bits/stdc++.h>
using namespace std;
#define rpd(i,s,e,d) for(int i=(s);i<(int)(e);i+=(d))

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

	int N; cin>>N;
	vector<int> C(1e6+1, 0);
	int g = 0;
	rpd(i, 0, N, 1){ int a; cin>>a; C[a]++; g = gcd(g, a); }

	auto sum_array = [&](int start, int end, int step){
		int c = 0;
		rpd(i, start, end, step) c += C[i];
		return c;
	};

	auto not_pairwise = [&]{
		if(sum_array(2, C.size(), 2) > 1) return true;
		rpd(i, 3, C.size(), 2) if(sum_array(i, C.size(), i) > 1) return true;
		return false;
	};

	cout<< vector<string>{"pairwise","setwise","not"}[(g > 1) + not_pairwise()] <<" coprime\n";
}


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

#define FORE(i, a) for (auto i = a.begin(); i != a.end(); ++i)
#define REPU(i, a, b) for (int i = (a); i < (b); ++i)
#define REPD(i, a, b) for (int i = (a); i > (b); --i)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

vector<string> split(const string &s, char c) {
	vector<string> v; stringstream ss(s); string x;
	while (getline(ss, x, c)) v.push_back(x);
	return v;
}
#define DEBUG(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }
void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << "[DEBUG] " << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

typedef long long ll;
const int MOD = 1000000007;

template<class T, class U> inline T tmin(T a, U b) { return (a < b) ? a : b; }
template<class T, class U> inline T tmax(T a, U b) { return (a > b) ? a : b; }
template<class T, class U> inline void amax(T &a, U b) { if (b > a) a = b; }
template<class T, class U> inline void amin(T &a, U b) { if (b < a) a = b; }
template<class T> T gcd(T a, T b) { while (b != 0) { T c = a; a = b; b = c % b; } return a; }

int main(int argc, char *argv[]) {
	ios_base::sync_with_stdio(false);

	ll a, b, c, k; cin >> a >> b >> c >> k;
	ll ans = a - b;
	if (k & 1) ans = -ans;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
x1,y1,x2,y2=map(int,input().split())

diff = x2-x1,y2-y1

x3,y3 = x2-diff[1],y2+diff[0]
x4,y4 = x1-diff[1],y1+diff[0]

print(*(x3,y3,x4,y4))

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

typedef long long  ll;

ll MOD = 1000000007;
ll INF = 100000000000000000;
int PI = 3.1415926535;

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<tuple<ll,ll,ll>>>;

int main(){
 int N;cin >> N;
 int ans = 0;
 bool frag = 0;
 for(int i = 1;i <= N;i++){
     if(i * 108 / 100 == N){
         ans = i;
         frag = 1;
     }
 }
 if(frag){
     cout << ans << endl;
 }else{
     cout << ":(" << endl;
 }
}

Measured memory_bytes: 256
x1, y1, x2, y2 = map(int, input().split())

x3 = x2+(y1-y2)
y3 = y2-(x1-x2)
x4 = x1+(y1-y2)
y4 = y1-(x1-x2)
print(x3, y3, x4, y4)

Measured memory_bytes: 3060
n,a,b,c = gets.split.map(&:to_i)
ls = []
n.times do
  ls << gets.to_i
end
$n = n
$a = a
$b = b
$c = c
$h = {"a" => a, "b" => b, "c" => c}

$ls = ls
def calc(h)
  sum = 0
  a = 0
  a_count = 0
  b = 0
  b_count = 0
  c = 0
  c_count = 0
  $n.times do |i|
    if h[i] == "a"
      a_count += 1
      a += $ls[i]
    elsif h[i] == "b"
      b_count += 1
      b += $ls[i]
    elsif h[i] == "c"
      c_count += 1
      c += $ls[i]
    end
  end
  if a == 0 || b == 0 || c == 0
    return Float::INFINITY
  end
  sum += (a_count - 1) * 10
  sum += (b_count - 1) * 10
  sum += (c_count - 1) * 10
  sum += ($a - a).abs
  sum += ($b - b).abs
  sum += ($c - c).abs
  sum
end

$ans = Float::INFINITY

def dfs(depth, h)
  if depth == $n
    $ans = [$ans, calc(h)].min
  else
    ["a","b","c","x"].each do |t|
      h[depth] = t
      dfs(depth + 1, h)
    end
  end
end

h = []
dfs(0, h)

puts $ans

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

const int MOD = 1e9+7;

ll dp[100010];

int main(){
  int n, m;
  cin >> n >> m;
  map<int,int> a;
  rep(i,m){
    int A;
    cin >> A;
    a[A]++;
  }
  rep(i,n+1){
    dp[i]=0;
  }
  for(int i = 1; i <= n; i++){
    if(a[i] == 1) dp[i]=0;
    else{
      if(i == 1) dp[i] = dp[i-1] + 1;
      else if(i == 2) dp[i] = dp[i-2] + 1 + dp[i-1];
      else dp[i] = dp[i-2] + dp[i-1];
    }
    dp[i]%=MOD;
  }
  cout<<dp[n]<<endl;
}

Measured memory_bytes: 9036
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
int main() {
  long long k,a,b;
  cin >> k >> a >> b;
  if(b-a>2) {
    if(a-1>k-2) {
      cout << k+1 << endl;
    }
    else {
      cout << (k-a+1)/2*(b-a)+a-1+(k-a+1)%2+1 << endl;
    }
  }
  else {
    cout << k+1 << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define pp pop_back
#define in insert
#define ff first
#define ss second
#define  show for(int j=0;j<v.size();j++) cout<<v[j]<<" ";
#define ld long double
#define e endl
#define bc __builtin_popcount
#define MOD 1000000007
#define INT_SIZE 32
#define me(x) memset(x,0,sizeof(x))
ll fast_expo(ll x,ll p)
{if(p==0) return 1;
else if(p%2==0){ ll t=fast_expo(x,p/2)%MOD;return (t*t)%MOD;} else return (x*(fast_expo(x,p-1))%MOD)%MOD;}
ll fun1(ll arr[], int n, int k)
{
    ll res = 0;
    for (int i=0; i<k; i++)
       res += arr[i];
    ll curr_sum = res;
    for (int i=k; i<n; i++)
    {
       curr_sum += arr[i] - arr[i-k];
       res = max(res, curr_sum);
    }

    return res;
}
int main()
{
    int n,k,i;
    cin>>n>>k;
    ll p[n];
    for(i=0;i<n;i++)
        cin>>p[i];
  ll ans=fun1(p,n,k)+k;
  double pp =(double)ans/2;
  cout<<fixed<<setprecision(10)<<pp<<e;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(a) (a).begin(), (a).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

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

  int n;
  string s;
  cin >> n >> s;

  rep(i,SZ(s)) {
    if (s[i]+n > 'Z') {
      s[i] = s[i]+n-'Z'+'A'-1;
    } else {
      s[i] = s[i]+n;
    }
  }

  cout << s << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define endl '\n'
#define fastio; ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<char> vc;

void solve()
{
    ll x;
    cin>>x;
    int time;
    ll amt=100;
    for(int i=1;;i++)
    {
        amt=amt*1.01;
        if(amt>=x){
            time=i;
            break;
        }
    }
    cout<<time<<endl;
    return;
}

int main()
{
    fastio;
    solve();

    return 0;
}



Measured memory_bytes: 3648
//https://atcoder.jp/contests/dp/tasks/dp_i
#include<bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<double> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    vector<vector<double>> dp(n + 1, vector<double>(n + 1));
    dp[0][0] = 1.0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            dp[i + 1][j + 1] += p[i] * dp[i][j];
            dp[i + 1][j] +=  (1 - p[i]) * dp[i][j];
        }
    }
    double ans = 0;
    for (int i = n / 2 + 1; i <= n; i++) {
        ans += dp[n][i];
    }
    cout.precision(16);
    cout << fixed << ans << endl;
}


Measured memory_bytes: 73772
fun main(args : Array<String>) {
    val (h, w) = readLine()!!.split(" ").map { it.toInt() }
    val cc = Array(10) { readLine()!!.split(" ").map { it.toInt() } }
    val aa = Array(h) { readLine()!!.split(" ").map { it.toInt() } }

    fun findMin(from: Int, min: Int, acc: Int): Int {
        var ret = acc + cc[from][1]

        cc[from].forEachIndexed { idx, i ->
            if (idx == 1) return@forEachIndexed
            if (from == idx) return@forEachIndexed
            if (acc + i >= min) return@forEachIndexed

            ret = Math.min(ret, findMin(idx, min, acc+i))
        }

        return ret
    }

    val minMagics = IntArray(10) {0}

    cc.forEachIndexed { hIdx, cList ->
        if (hIdx == 1) return@forEachIndexed
        minMagics[hIdx] = findMin(hIdx, cc[hIdx][1], 0)
    }

    var magicSum = 0

    aa.forEach { aList ->
        aList.forEach { a ->
            if (a > -1) {
                magicSum += minMagics[a]
            }
        }
    }

    println(magicSum)
}

Measured memory_bytes: 42028
#include<iostream>
#include<vector>
#include<utility>
#include<tuple>
using namespace std;

int H,W;
int a[503][503];

int main(){
  cin>>H>>W;
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      cin>>a[i][j];
    }
  }
  int cnt=0;
  vector<tuple<int,int,int,int> > v;
  for(int i=0;i<=H;i++){
    for(int j=0;j<=W;j++)if(a[i][j]&1){
      if(i<H&&j<W){
        if(a[i+1][j]&1){
          a[i+1][j]++;
          a[i][j]--;
          v.push_back(make_tuple(i,j,i+1,j));
          cnt++;
        }else{
          a[i][j+1]++;
          a[i][j]--;
          v.push_back(make_tuple(i,j,i,j+1));
          cnt++;
        }
      }else if(i<H){
        a[i+1][j]++;
        a[i][j]--;
        v.push_back(make_tuple(i,j,i+1,j));
        cnt++;
      }else if(j<W){
        a[i][j+1]++;
        a[i][j]--;
        v.push_back(make_tuple(i,j,i,j+1));
        cnt++;
      }
    }
  }
  cout<<cnt<<endl;
  int a,b,c,d;
  int n=v.size();
  for(int i=0;i<n;i++){
    tie(a,b,c,d)=v[i];
    cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
  }
  return 0;
}

Measured memory_bytes: 5104
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define debugP int debug_point; cin>>debug_point;
const ll MOD= 1e9 + 7;
template <typename T>
void putv(vector<T>& V){
	// cout << "The elements in the vector are: " << endl;
	for(auto x: V)
		cout << x << " ";
	cout << endl;
}
template <class T>
vector<T> getv(ll n){
	vector<T> Vector_temp;
	rep(i,n){
		T input;
		cin >> input;
		Vector_temp.emplace_back(input);
	}
	return Vector_temp;
}
ll gcd(ll c,ll b){
    while(1){
        if(c%b!=0){
        ll tmp=b;
        b=c%b;
        c=tmp;
        }else{
            return b;
        }
    }
}
/* <3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3*/

ll ex(ll a){
    if(a==1)return 1;
    return a+ex(a-1);
}

int main(){
    ll n,m;
    cin>>n>>m;
    ll ans=0;
    if(n*2<=m){
        ans+=n;
        m-=(n*2);
        n=0;
        ans+=(m/4);
    }else{
        ans+=(m/2);
    }
    
    op(ans);
    return 0;
}

Measured memory_bytes: 256
N = gets.to_i
S = N.times.map{gets.chomp}

S.map! do |s|
  s.chars.sort.join
end

hash = {}

ans = 0

S.each do |s|
  if hash[s].nil?
    hash[s] = 1
  else
    hash[s] += 1
    ans += hash[s] - 1
  end
end

puts ans


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

using namespace std;

#define MAX 110
#define INF 1e9

struct Edge{
    int to,f;
    Edge(int to,int f) : to(to),f(f) {}
};

struct State{
    int v,d,e;
    State(int v,int d,int e) : v(v),d(d),e(e) {}
};

int d[MAX][MAX][1<<4];

int main(){
    int N,M,E,S,T,R,a,b,c;
    vector<Edge> G[MAX];
    cin >> N >> M >> E >> S >> T >> R;
    for(int i = 0 ; i < M ; i++){
        cin >> a >> b;
        G[a].push_back(Edge(b,-1));
        G[b].push_back(Edge(a,-1));
    }
    int bit = 0;
    vector<int> event(N,-1);
    for(int i = 0 ; i < E ; i++){
        cin >> a >> b >> c;
        G[a].push_back(Edge(b,i));
        G[b].push_back(Edge(a,i));
        event[c] = i;
        if(c == S) bit |= 1<<i;
    }
    fill(d[0][0],d[0][0]+MAX*MAX*(1<<4),INF);
    d[S][0][bit] = 0;
    bool ok = false;
    queue<State> Q; Q.push(State(S,0,bit));
    while(!Q.empty()){
        State s = Q.front(); Q.pop();
        int v = s.v,day = s.d,ev = s.e;
        if(v == T){
            ok = true;
            cout << d[v][day][ev] << endl;
            break;
        }
        int ncost = d[v][day][ev] + 1;
        if(ncost < d[S][0][ev]){
            d[S][0][ev] = ncost;
            Q.push(State(S,0,ev));
        }
        for(int i = 0 ; i < (int)G[v].size() ; i++){
            Edge e = G[v][i];
            if(day + 1 > R) continue;
            int nev = ev | (event[e.to] >= 0 ? 1<<event[e.to] : 0);
            if(e.f == -1 || (ev >> e.f & 1)){
                if(ncost < d[e.to][day+1][nev]){
                    d[e.to][day+1][nev] = ncost;
                    Q.push(State(e.to,day+1,nev));
                }
            }
        }
    }
    if(!ok) cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 2056
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import bisect
import math
import fractions
import sys
import copy


def L(): return sys.stdin.readline().split()


def I(): return int(sys.stdin.readline().rstrip())


def S(): return list(sys.stdin.readline().rstrip())


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def IR(n): return [I() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def LIR1(n): return [LI1() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def LR(n): return [L() for _ in range(n)]


alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007


def main():
    K = I()
    ans = 1
    tmp = 7

    if K % 2 == 0 or K % 5 == 0:
        print(-1)
        return

    while tmp % K != 0:
        tmp *= 10
        tmp += 7
        tmp %= K
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 72764
import java.util.Scanner;


public class Main {
	
	public static int Len_LCS(String x, String y) {
		int len_x = x.length();
		int len_y = y.length();
		int i = 1, j = 1;
		int [][] L = new int[len_x+1][len_y+1];
		for(i=1; i<=len_x; i++)
			for(j=1; j<=len_y; j++)
			{
				if(x.charAt(i-1)!=y.charAt(j-1))
					L[i][j] = max(L[i-1][j], L[i][j-1]);
				else
					L[i][j] = 1 + L[i-1][j-1];
			}
		return L[i-1][j-1];
	}

	public static int max(int a, int b){
		return (a>=b) ? a : b;
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int num_pairs = scan.nextInt();
		while (num_pairs-- > 0) {
			String x =  scan.next();
			String y =  scan.next();
//			System.out.println(x);
//			System.out.println(y);
			System.out.println(Len_LCS(x,y));
		}
		scan.close();
	}
}


Measured memory_bytes: 65204
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
  ll n;
  cin >>n;
  ll a[n];
  for(ll i=0;i<n;i++) cin >>a[i];
  ll sum=0;
  ll ans=0,ans1=0;
  for(ll i=0;i<n;i++){
    if(i%2==0){
      sum+=a[i];
      if(sum==0) {
        sum=1;
        ans++;
      }
      if(sum<0) {
        ans+=(abs(sum)+1);
        sum=1;
      }
    }
    else{
      sum+=a[i];
      if(sum==0) {
        sum=-1;
        ans++;
      }
      if(sum>0) {
        ans+=(abs(sum)+1);
        sum=-1;
      }
    }
  }
  sum=0;
  for(ll i=0;i<n;i++){
    if(i%2==1){
      sum+=a[i];
      if(sum==0) {
        sum=1;
        ans1++;
      }
      if(sum<0) {
        ans1+=(abs(sum)+1);
        sum=1;
      }
    }
    else{
      sum+=a[i];
      if(sum==0) {
        sum=-1;
        ans1++;
      }
      if(sum>0) {
        ans1+=(abs(sum)+1);
        sum=-1;
      }
    }
  }
  cout <<min(ans,ans1)<<endl;
}


Measured memory_bytes: 1024
#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() {
  int n, a, b; cin >> n >> a >> b;
  string s; cin >> s;
  int ap = 0, bp = 0;
  vector<bool> r(n);
  rep(i, n) {
    if (s[i] == 'a' && ap + bp < a + b) {
      r[i] = true;
      ap++;
    } else if (s[i] == 'b' && ap + bp < a + b && bp < b) {
      r[i] = true;
      bp++;
    } else {
      r[i] = false;
    }
  }
  rep(i, n) {
    if (r[i] == true) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3732
# -*- coding: utf-8 -*-
A,B,C = map(int,input().split())
AB = B - A
AC = C - A

if (A<B and A<C) or (A>B and A>C):
  AB_a = abs(AB)
  AC_a = abs(AC)
  if AB_a < AC_a:
    print('No')
  else:
    print('Yes')
else:
  print('No')

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
using namespace std;
const int size=4000;
bool visited[size][size];
int distances[size][size];
vector<int> graph[size];
int number, diameter;
/*
template<typename Type>
void showContent(Type inputVector)
{
	for(int i=1; i<=number; ++i)
	{
		for(int j=1; j<=number; ++j)
		{
			cout<<"["<<i<<"]["<<j<<"] <- "<<inputVector[i][j]<<endl;
		}
	}
	return;
}
*/
void dfs(int root, int start, int distance)
{
	//commandsBeforeRecursion.
	visited[root][start]=true;
	distances[root][start]=distance;
	for(int next : graph[start])
	{
		if(!visited[root][next])
		{
			dfs(root, next, distance+1);
		}
	}
	//commandsAfterRecursion.
	return;
}
void usingDFS()
{
	int vertex0, vertex1;
	cin>>number>>diameter;
	for(int i=1; i<number; ++i)
	{
		cin>>vertex0>>vertex1;
		graph[vertex0].push_back(vertex1);
		graph[vertex1].push_back(vertex0);
	}
	for(int point=1; point<=number; ++point)
	{
		dfs(point, point, 0);
	}
	if(diameter%2==0)
	{
		int counter, minValue=4000;
		for(int i=1; i<=number; ++i)
		{
			counter=0;
			for(int j=1; j<=number; ++j)
			{
				if(distances[i][j]>diameter/2)
				{
					++counter;
				}
			}
			minValue=min(minValue, counter);
		}
		cout<<minValue<<endl;
	}
	else
	{
		int counter, minValue=4000, temporaryValue;
		for(int i=1; i<=number; ++i)
		{
			for(int j=1; j<=number; ++j)
			{
				if(distances[i][j]==1)
				{
					counter=0;
					for(int k=1; k<=number; ++k)
					{
						temporaryValue=min(distances[k][i], distances[k][j]);
						if(temporaryValue>diameter/2)
						{
							++counter;
						}
					}
					//cout<<counter<<", ";
					minValue=min(minValue, counter);
				}
			}
		}
		cout<<minValue<<endl;
	}
	return;
}
int main()
{
	usingDFS();
	return 0;
}

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

int N, K;
int l[55];

int main() {
  cin >> N >> K;
  for(int i = 0; i < N; ++i) cin >> l[i];
  
  sort(l, l + N, greater<int>()); // a[0:N] を降順にソート
  int max = 0;
  for(int i = 0; i < K; ++i)
    max += l[i];
  
  cout << max << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s,t;
  int ans=0;
  
  cin>>s>>t;
  for(int i=0;i<s.size();i++){
    if(s[i]!=t[i]) ans++;
  }
  
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3908