akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P>IP;
typedef vector<ll> V;
typedef vector<V> V2;
typedef vector<vector<P> > G;
void g_dir(G &graph, ll a, ll b, ll w = 1){graph[a].push_back(P(b, w));}
void g_undir(G &graph, ll a, ll b, ll w = 1){g_dir(graph, a, b, w);g_dir(graph, b, a, w);}
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}
const ll INF = 1145141919;
const ll MOD = 1000000007;
const ll NUM = 101010;

string s;
ll N, K, ans;
ll imos[111];
ll cnt(ll l, ll r){
    if(l > r)return 0;
    if(l == 0)return imos[r];
    return imos[r] - imos[l - 1];
}

ll ika(ll a, ll x){
    if(x)return 1;
    if(s[0] >= a + '0')return 1;
    return 0;
}

ll ika(ll a, ll x, ll b, ll y){
    if(x)return 1;
    if(s[0] > a + '0')return 1;
    if(s[0] < a + '0')return 0;
    if(cnt(x + 1, y - 1))return 1;
    if(s[y] >= b + '0')return 1;
    return 0;
}

ll ika(ll a, ll x, ll b, ll y, ll c, ll z){
    if(x)return 1;
    if(s[0] > a + '0')return 1;
    if(s[0] < a + '0')return 0;
    if(cnt(x + 1, y - 1))return 1;
    if(s[y] > b + '0')return 1;
    if(s[y] < b + '0')return 0;
    if(cnt(y + 1, z - 1))return 1;
    if(s[z] >= c + '0')return 1;
    return 0;
}

int main(){

    cin >> s;
    cin >> K;
    N = s.size();
    rep(i, N)if(s[i] != '0')imos[i] = 1;
    rep1(i, N)imos[i] += imos[i - 1];
    ll ans = 0;
    if(K == 1){
        rep1(a, 9)rep(x, N)if(ika(a, x))ans++;
    }
    if(K == 2){
        rep1(a, 9)rep(x, N)rep1(b, 9)for(ll y = x + 1; y < N; y++)if(ika(a, x, b, y))ans++;
    }
    if(K == 3){
        rep(x, N)for(ll y = x + 1; y < N; y++)for(ll z = y + 1; z < N; z++)rep1(a, 9)rep1(b, 9)rep1(c, 9)if(ika(a, x, b, y, c, z))ans++;
    }
    

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP2D(a, n, m) REP(i, n) REP(j, m) printf("%d%c", a[i][j], j + 1 == m ? '\n' : ' ')

//------------------------------------------------------------------------------
typedef long long ll;
typedef vector<int> vec;
typedef vector<vec> mat;

const int MOD = 1000000007;

vec apply(mat &A, vec &B) {
  vec C = vec(A.size());
  REP(i, A.size()) REP(j, B.size())
    C[i] = (C[i] + (ll) A[i][j] * B[j]) % MOD;
  return C;
}

int dot(vec &A, vec &B) {
  int C = 0;
  REP(i, A.size())
    C= (C + (ll) A[i] * B[i]) % MOD;
  return C;
}

//------------------------------------------------------------------------------
ll N;

void solve() {
  mat M = mat(4, vec(4));
  M[0][0] = 1; M[0][1] = 1; M[0][2] = 0; M[0][3] = 1;
  M[1][0] = 1; M[1][1] = 1; M[1][2] = 1; M[1][3] = 0;
  M[2][0] = 1; M[2][1] = 1; M[2][2] = 1; M[2][3] = 0;
  M[3][0] = 1; M[3][1] = 1; M[3][2] = 0; M[3][3] = 1;

  mat dp[2] = { mat(4, vec(4)), mat(4, vec(4)) };
  mat &cur = dp[0], &nxt = dp[1];
  cur[0][3] = 1;
  cur[1][3] = 1;
  cur[2][3] = 1;
  cur[3][3] = 1;

  while (N > 0) {
    nxt[0] = apply(M, cur[0]);
    if (N & 1) {
      nxt[1][0] = dot(M[0], cur[0]);
      nxt[1][1] = dot(M[1], cur[1]);
      nxt[1][2] = dot(M[2], cur[0]);
      nxt[1][3] = dot(M[3], cur[1]);
      nxt[2][0] = dot(M[0], cur[0]);
      nxt[2][1] = dot(M[1], cur[0]);
      nxt[2][2] = dot(M[2], cur[2]);
      nxt[2][3] = dot(M[3], cur[2]);
      nxt[3][0] = dot(M[0], cur[0]);
      nxt[3][1] = dot(M[1], cur[1]);
      nxt[3][2] = dot(M[2], cur[2]);
      nxt[3][3] = dot(M[3], cur[3]);
    } else {
      nxt[1][0] = dot(M[0], cur[1]);
      nxt[1][1] = 0;
      nxt[1][2] = dot(M[2], cur[1]);
      nxt[1][3] = 0;
      nxt[2][0] = dot(M[0], cur[2]);
      nxt[2][1] = dot(M[1], cur[2]);
      nxt[2][2] = 0;
      nxt[2][3] = 0;
      nxt[3][0] = dot(M[0], cur[3]);
      nxt[3][1] = 0;
      nxt[3][2] = 0;
      nxt[3][3] = 0;
    }
    // DUMP2D(nxt, 4, 4);
    // puts("");
    swap(cur, nxt);
    N >>= 1;
  }
  ll ans = (cur[3][0] + cur[3][1] + cur[3][3]) % MOD;
  printf("%lld\n", ans);
}

void input() {
  scanf("%lld", &N);
}

int main() {
  input();
  solve();
  return 0;
}


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

void shift(char x[]){
	int n=strlen(x),i;
	for(i=0;i<n;i++){
		if('a'<=x[i] && x[i]<='y')x[i]++;
		else if(x[i]=='z')x[i]='a';
	}
}

int check(char x[]){
	if(strstr(x,"the")!=NULL)return 1;
	if(strstr(x,"that")!=NULL)return 1;
	if(strstr(x,"this")!=NULL)return 1;
	return 0;
}

int main(void) {
	char text[82];

	while(1){
		if(fgets(text,82,stdin)==NULL)break;
		if(strcmp(text,"")==0)break;

		while(1){
			shift(text);
			if(check(text))break;
		}

		printf("%s",text);
	}

	return 0;
}

Measured memory_bytes: 532
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

alias P = Tuple!(long, "min", long, "max", bool, "odd", bool, "init");

void main()
{
    auto N = readln.chomp.to!int;
    int[][] T;
    T.length = N;
    foreach (_; 0..N-1) {
        auto ab = readln.split.to!(int[]);
        auto A = ab[0]-1;
        auto B = ab[1]-1;
        T[A] ~= B;
        T[B] ~= A;
    }
    auto PS = new P[](N);
    foreach (ref p; PS) {
        p.max = p.min = -1;
    }
    int[] ks;
    auto RS = new long[](N);
    auto K = readln.chomp.to!int;
    foreach (_; 0..K) {
        auto vp = readln.split.to!(int[]);
        auto v = vp[0]-1;
        auto p = vp[1];
        PS[v].min = p;
        PS[v].max = p;
        PS[v].odd = p%2 == 1;
        PS[v].init = true;
        RS[v] = p;
        ks ~= v;
    }

    bool walk(int i, int p) {
        if (p != -1) {
            auto p_min = PS[p].min - 1;
            auto p_max = PS[p].max + 1;
            bool was_same = PS[i].init && PS[i].min == PS[i].max;
            if (!PS[i].init) {
                PS[i].min = p_min;
                PS[i].max = p_max;
                PS[i].odd = !PS[p].odd;
                PS[i].init = true;
            } else if (PS[i].min != PS[i].max) {
                PS[i].min = max(PS[i].min, p_min);
                PS[i].max = min(PS[i].max, p_max);
            } else if (PS[i].min < p_min || PS[i].max > p_max) {
                return false;
            }
            if (p_min > p_max) return false;
            if (PS[i].odd == PS[p].odd) return false;
            if (was_same) return true;
        }

        foreach (j; T[i]) if (j != p) {
            if (!walk(j, i)) return false;
        }

        return true;
    }
    foreach (i; ks) {
        if (!walk(i, -1)) {
            writeln("No");
            return;
        }
    }

    void paint(int i, int p) {
        if (p != -1) {
            auto min_p = RS[p] - 1;
            auto max_p = RS[p] + 1;
            if (PS[i].min <= min_p && min_p <= PS[i].max) {
                RS[i] = min_p;
            } else if (PS[i].min <= max_p && max_p <= PS[i].max) {
                RS[i] = max_p;
            } else {
                throw new Exception("");
            }
        }

        foreach (j; T[i]) if (j != p) {
            paint(j, i);
        }
    }
    paint(ks[0], -1);

    writeln("Yes\n", RS[].to!(string[]).join("\n"));
}

Measured memory_bytes: 30076
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
	bool flag = false;
	int number = 0, num[100][2], n;
	cin >> n;
	for	(int i = 0; i < n; i++) {
		cin >> num[i][0] >> num[i][1];
	}
	for (int i = 0; i < n; i++) {
		if (num[i][1] == num[i][0]) {
			number += 1;
		} else {
			number = 0;
		}
		if (number >= 3) {
			flag = true;
			break;
		}
	}
	cout << (flag ? "Yes" : "No") << endl;
}

Measured memory_bytes: 3564
var obj={
C:0,
Cs:1,
D:2,
Ds:3,
E:4,
F:5,
Fs:6,
G:7,
Gs:8,
A:9,
As:10,
B:11
};
var cde=["C","C#","D","D#","E","F","F#","G","G#","A","A#","B"];
var chord=[
[0,4,7],
[0,4,7,10],
[0,4,7,11],
[0,3,7],
[0,3,7,10],
[0,4,6],
[0,4,6,10],
[0,4,6,11],
[0,3,6],
[0,3,6,10],
[0,4,8],
[0,4,8,10],
[0,4,8,11],
[0,3,8],
[0,3,8,10]
];
var name=[
"","7","M7","m","m7",
"(-5)","7(-5)","M7(-5)","m(-5)","m7(-5)",
"(+5)","7(+5)","M7(+5)","m(+5)","m7(+5)"];
var tension={
1:"(-9)",
2:"(9)",
3:"(+9)",
4:"(-11)",
5:"(11)",
6:"(+11)",
8:"(-13)",
9:"(13)",
10:"(+13)"
};
var CHORD={};
chord.forEach(function(v,i){
   CHORD[v.join(",")]=name[i];
   if(/5\)/.test(name[i])!=true){
      for(var k in tension){
         if(v.indexOf(k-0)==-1){
            CHORD[v.concat(k-0).sort(function(a,b){return a-b}).join(",")]=name[i]+tension[k];
        }
      }
   }
});
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
input=input.replace(/\#/g,"s");
var arr=input.trim().split("\n");
var n=arr.shift()-0;
while(n--){
   var ans=[];
   var ary=arr.shift().split(" ");
   ary.shift();
   var NumAry=ary.map(function(v){return obj[v];});
   NumAry.sort(function(a,b){return a-b;});
   NumAry.forEach(function(v,i,array){
      var x=cde[v];
      var minus=0;
      while(v!=0){
         v--;
         minus--;
      }
      var A=array.map(function(value,index){
         return (value+minus<0)?value+minus+12:value+minus;
      });
      A.sort(function(a,b){return a-b;});
      if(CHORD.hasOwnProperty(A.join(","))){
         var NAME=CHORD[A.join(",")];
         if(NAME=="m(-11)"){
            ans.push(x+"(+9)");
            ans.push(x+NAME);
         }else if(NAME=="7"){
            ans.push(x+NAME);
            ans.push(x+"(+13)");
         }else if(NAME=="m7(-11)"){
            ans.push(x+"7(+9)");
            ans.push(x+NAME);
         }else if(NAME=="m7"){
            ans.push(x+NAME);
            ans.push(x+"m(+13)");
         }else{
            ans.push(x+NAME);      
         }
      }
   });
   ans=(ans.length==0)?"UNKNOWN":ans.join(" ");
   console.log(ans);
}

Measured memory_bytes: 20688
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>
#include <cassert>
#include <bitset>

using namespace std;

/* template */

using ll = long long;

void debug_out() { std::cout << std::endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cout << "debug: "; debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif

#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define rrep(i, a, n) for (int i = ((int)(n-1)); i >= (int)(a); i--)
#define Rep(i, a, n) for (long long i = (long long)(a); i< (long long)(n); i++)
#define RRep(i, a, n) for (long long i = ((long long)(n-1ll)); i>=(long long)(a); i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}

struct Edge{
    int to;
    ll weight;
    Edge(int t, ll w) : to(t), weight(w){ }
};

struct edge{
    int from;
    int to;
    ll weight;
    edge(int f,int t,ll w) : from(f), to(t), weight(w){ }
};


using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;
using edges = vector<edge>;

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

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

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

constexpr ll LNF = 1LL<<60;

constexpr int INF = 1e9+7;

const double PI=3.14159265358979323846;


vector<int> dx = {-1,0,1,0,-1,1,-1,1};
vector<int> dy = {0,-1,0,1,1,-1,-1,1};

/* template */

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s,t; cin >> s >> t;
    rep(i,0,s.size()){
        if(s[i]!=t[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
} 

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

using namespace std;

int main(){
  string a, b;
  cin >> a >> b;
  for(int i = 0; i < a.size(); ++i){
    string nk = a.substr(i, a.size() - i) + a.substr(0, i);
    if(nk == b) return 0 * puts("Yes");
  }
  puts("No");
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s); sin>>v; return v;}
template<class T> inline string toString(T x) {ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define EACH(t,i,c) for(t::iterator i=(c).begin(); i!=(c).end(); ++i)
const double EPS = 1e-10;
const double PI = acos(-1.0);

typedef vector<pii> vp;
typedef vector<vp> vvp;
int main(){
	int m,n;
	cin>>m>>n;
	vs f(m);
	const int num_alph='Z'-'A'+1;
	vvp pos(num_alph);
	REP(i,m){
		cin>>f[i];
		REP(j,n){
			if(isalpha(f[i][j])){
				pos[f[i][j]-'A'].push_back(make_pair(i,j));
			}
		}
	}
	FOR(c,0,num_alph){
		sort(ALL(pos[c]));
	}

	REP(c,num_alph){
		if(pos[c].size()){
			if(abs(pos[c][0].first-pos[c][1].first)+abs(pos[c][0].second-pos[c][1].second)<=1){
				pos[c].clear();
			}
		}
	}
	int ans=0;
	bool changed=true;
	while(changed){
		changed=false;
		FOR(c,0,num_alph){
			if(pos[c].size()==0){
				continue;
			}
			bool left_ok=true;
			bool right_ok=true;
			int x_left=pos[c][0].second;
			int x_right=pos[c][1].second;
			if(x_left>x_right)swap(x_left,x_right);
			int y_top=pos[c][0].first;
			int y_bottom=pos[c][1].first;
			FOR(y,y_top,y_bottom+1){
				if(f[y][x_left]!='.'&&f[y][x_left]!='A'+c){
					left_ok=false;
				}
				if(f[y][x_right]!='.'&&f[y][x_right]!='A'+c){
					right_ok=false;
				}
			}
			bool top_ok=true;
			bool bottom_ok=true;
			FOR(x,x_left,x_right+1){
				if(f[y_top][x]!='.'&&f[y_top][x]!='A'+c){
					top_ok=false;
				}
				if(f[y_bottom][x]!='.'&&f[y_bottom][x]!='A'+c){
					bottom_ok=false;
				}
			}
			bool ok=false;
			if(pos[c][0].second<pos[c][1].second){
				ok=((top_ok&&right_ok)||(bottom_ok&&left_ok));
			}else{
				ok=((top_ok&&left_ok)||(bottom_ok&&right_ok));
			}

			if(ok){
				f[pos[c][0].first][pos[c][0].second]='.';
				f[pos[c][1].first][pos[c][1].second]='.';
				pos[c].clear();
				ans+=2;
				changed=true;
			}
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1348
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) *b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};


///////////////////////////


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

	if (a <= 0 && b >= 0) { cout << "Zero"; }
	else if (a > 0) { cout << "Positive"; }
	else if ((b - a) % 2 != 0) { cout << "Positive"; }
	else { cout << "Negative"; }

	system("PAUSE");

}





Measured memory_bytes: 504
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a, b, c, d, tmp, m, h, w, x, y, sum, k, q;

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

  cin >> n >> a >> b;
  if ((b - a) % 2 == 0)
    Cout("Alice");
  else
    Cout("Borys");
  return 0;
}

Measured memory_bytes: 3652
class union_find():
    def __init__(self,n):
        self.n=n
        ##親要素のノード番号を格納。par[x]==xのときそのノードは根
        ##親とはその上にノードなし！！　
        self.par=[i for i in range(n+1)]
        self.rank=[0]*(n+1)

    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]

    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)

        ##木の高さを比較し、低い方から高い方へ辺をはる

        if self.rank[x]<self.rank[y]:
          self.par[x]=y
        else:
          self.par[y]=x
          ##同じなら片方を伸ばす
          if self.rank[x]==self.rank[y]:
            self.rank[y]+=1

    def same(self,x,y):
        return self.find(x) == self.find(y)
      
n,m=map(int,input().split())
uf=union_find(n)
ans=0
s=[]
for _ in range(m):
  a=list(map(int,input().split()))
  s.append(a)
  uf.union(a[0],a[1])
  
  

for e in range(m):
  uf1=union_find(n)
  ch=0
  for d in range(m):
    if d!=e:
      uf1.union(s[d][0],s[d][1])
      
  for i in range(1,n):
    for j in range(i+1,n+1):
      if not uf1.same(i,j):
        ch+=1
  if ch>0:
    ans+=1

    
print(ans)

Measured memory_bytes: 9268
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

ll mod = 1e9 + 7;

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

  ll n, k;
  cin >> n >> k;

  ll h[n];
  REP(i, n) cin >> h[i];

  SORT(h, n);

  ll ans = 1e11;
  REP(i, n - k + 1){
    ll rec = h[i + k - 1] - h[i];
    ans = min(ans, rec);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h> 
#include<cmath>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define deb(x) cerr<<#x<<" "<<x<<"\n"
#define debi cerr<<"hey sparky\n"
#define f first
#define s second
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define newline cout<<"\n"
#define yes cout<<"Yes"<<"\n"
#define no cout<<"No"<<"\n"
#define INF (int)1e5
#define nax (int)1e5+2
using namespace std;
// look for  all edge cases
//search for a pattern


int main(){
	fast;
	int n;
	cin >> n;
	bool ok = false;
	while(n > 1){
		int a = n%10;
		if(a == 7){
			ok = true;
			break;
		}
		
		n /= 10;
	}
	if(ok)
		yes;
	else
		no;
	return 0;
	
}


Measured memory_bytes: 3648
n, m = map(int, input().split())
stu = []
check = []
for i in range(n):
    stu.append(list(map(int, input().split())))

for i in range(m):
    check.append(list(map(int, input().split())))


ans = []

for i in range(n):
    dist = []
    for j in range(m):
        tmp = abs(stu[i][0] - check[j][0]) + abs(stu[i][1] - check[j][1])
        dist.append(tmp)
    mi = dist.index(min(dist))
    ans.append(mi)


for i in range(len(ans)):
    print(ans[i] + 1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000000
#define ll long long

#define maxn 3005
#define pi acos(-1.0)

int n, L;
double ang[maxn];
double x, y;

int main()
{
    cin >> n >> L;
    for (int i = 0; i < n; i++)
    {
        int t;
        scanf("%d", &t);
        ang[i] = 2 * pi * t / L;
    }
    x = y = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j < n; j++)
        {
            double now = ang[(i + j) % n];
            if (now < ang[i])
                now += 2 * pi;
            now = (now + ang[i]) / 2;
            x += cos(now) * (n - j - 1) / n / (n - 1);
            y += sin(now) * (n - j - 1) / n / (n - 1);
        }
    }
    x /= ((n - 2.0) / 6);
    y /= ((n - 2.0) / 6);
    printf("%.15f %.15f\n", x, y);

    return 0;
}

Measured memory_bytes: 384
N = int(input())
A = []
for _ in range(N):
    a = int(input())
    A.append(a - 1)
Flags = [False] * N
Flags[0] = True
now = 0
cnt = 0
for _ in range(N):
    cnt += 1
    next_node = A[now]
    if next_node == 1:
        break
    if Flags[next_node]:
        print("-1")
        exit()
    Flags[next_node] = True
    now = next_node
print(cnt)



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

int main(){
    int K, X;
    cin >> K >> X;
    
    for(int i = -1000000; i <= 1000000; i++){
        if(X-K < i && i < X+K)
            cout << i << " ";
    }
    cout << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>


int main(void)
{
    int N, K, a;
    char c;
    int i, ctr;
    
    
    scanf("%d %d", &N, &K);
    
    
    for(i=0; i<N; i++)
    {
        scanf("%d%c", &a, &c);
    }
    
    if((N-K)%(K-1) == 0)
        ctr = 1+(N-K)/(K-1);
    else
        ctr = 2+(N-K)/(K-1);
    
    printf("%d\n", ctr);

    
    //system("pause");
    
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD 998244353
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 long long INF = 1LL << 60;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
//四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
struct edge{//グラフに使うヤツ
    ll from,to,cost;
};
typedef vector<vector<edge> > G;
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
#define MAX_N 210000
ll a[1100000],ans=0;
bool z[1100000];
void eratosthenes(ll n){
    for(ll i=0;i<n;i++) {
        if (z[a[i]]){
            for(ll j=2*a[i];j<=1100000;j+=a[i]){
                z[j] = false;
            }
        }
    }
}

int main(){
    fill(z,z+1100000,true);
    ll n;
    cin >> n;
    for (ll i=0;i<n;i++){
        cin >> a[i];
    }
    sort(a,a+n);
    for (ll i=1;i<n;i++){
        if (a[i]==a[i-1] and z[a[i]]){
            z[a[i]]=false;
            for(ll j=2*a[i];j<=1100000;j+=a[i]){
                z[j] = false;
            }
        }
    }
    eratosthenes(n);
    for (ll i=0;i<n;i++){
        if (z[a[i]]){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 6220
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import qualified Data.Foldable as Foldable
import qualified Data.Set as Set
import qualified Data.Sequence as Sequence
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
--import Data.Array
import Data.Array.IArray
--import Data.Array.Unboxed
import Data.Array.MArray
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
-- import System.IO.Unsafe
 
readInt = read :: String -> Int
readInteger = read :: String -> Integer
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getInteger = readLn :: IO Integer
getIntegers = map readInteger . words <$> getLine
getDouble = readLn :: IO Double
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
apply4 :: (a -> a -> a -> a -> b) -> [a] -> b
apply4 f [x,y,z,w] = f x y z w
fnBin :: (b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d
fnBin op f g x = op (f x) $ g x
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
modifyArray :: (Ix i, MArray a e m) => a i e -> i -> (e -> e) -> m ()
modifyArray arr ix f = readArray arr ix >>= writeArray arr ix . f
dictCompare :: [a -> a -> Ordering] -> a -> a -> Ordering
dictCompare [] _ _ = EQ
dictCompare (f:fs) x y = let c = f x y in if c==EQ then dictCompare fs x y else c
binMap :: (a -> a -> b) -> [a] -> [b]
binMap f (x:xs@(y:_)) = f x y : binMap f xs
binMap _ _ = []
-- end of templete



main = (+) <$> (sum . tail . sort <$> replicateM 4 getInt) <*> (max <$> getInt <*> getInt) >>= print


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

typedef long long ll;
const int MOD = 1e9 + 7;
typedef vector<ll> vll;
typedef vector<int> vi;

struct city {
    int id;
    int p;
    int y;
    int x;
    city(int id, int p, int y) {
        this->id = id;
        this->p = p;
        this->y = y;
    }
};

static bool cmp(const city& x, const city& y) {
    return x.y < y.y;
}

static bool cmp2(const city& x, const city& y) {
    return x.id < y.id;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<city>> cities(n + 1);
    int pi, yi;
    for (int i = 1; i <= m; ++i) {
        cin >> pi >> yi;
        cities[pi].push_back(city(i, pi, yi));
    }
    for (int i = 1; i <= n; ++i) {
        if (!cities[i].empty()) {
            sort(cities[i].begin(), cities[i].end(), cmp);
            for (int j = 0; j < cities[i].size(); ++j) {
                cities[i][j].x = j + 1;
            }
        }
    }
    vector<city> res;
    res.reserve(m);
    for (int i = 1; i <= n; ++i) {
        if (!cities[i].empty()) {
            for (auto c : cities[i]) {
                res.push_back(c);
            }
        }
    }
    sort(res.begin(), res.end(), cmp2);
    for (auto &c : res) {
        printf("%06d%06d\n", c.p, c.x);
    }
    return 0;

}

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

long int N;
long int A[200007];

long int Subject_amount[200007];

int main(){
    // 入力
    cin >> N;
    for(int i = 1;i < N;i++){
        cin >> A[i];
    }

    for(int i = 1;i < N;i++){
        Subject_amount[A[i] - 1] += 1;
    }

    for(int i = 0;i < N;i++){
        cout << Subject_amount[i] << endl;
    }


    return 0;
}

Measured memory_bytes: 6716
/*  -*- coding: utf-8 -*-
 *
 * b.cc: B: 1 21
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

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

  int n = atoi((a + b).c_str());
  //printf("%d\n", n);

  int k = (int)sqrt(0.5 + n);
  if (k * k == n) puts("Yes");
  else puts("No");
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

int n;

long long a[1000010],b[1000010];

long long k;

bool check(long long x)
{
	long long cnt=0;
	for (int i=1;i<=n;i++)
	{
		if (a[i]*b[i]>x)
		{
			cnt+=(a[i]-x/b[i]);
		} 
	}
	if (cnt>k) return 0;
	else return 1;
}

int comp(int x,int y)
{
	return x>y;
}

int main()
{
	cin>>n>>k;
	for (int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	for (int i=1;i<=n;i++)
	{
		scanf("%lld",&b[i]);
	}
	sort(a+1,a+n+1);
	sort(b+1,b+n+1,comp);
	long long l=0,r=1e12+10,ans=0;
	while (l<=r)
	{
		long long mid=(l+r)>>1;
		if (check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}


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

int a[110000];
int b[110000];
int c[110000];
int dp[110000][3];

int main(){
    ll n;
    cin>>n;
    for(ll i=0; i<n; i++){
        cin>>a[i];
        cin>>b[i];
        cin>>c[i];
    }
    for(ll i=0; i<n; i++){
        for(int j=0; j<3; j++){
            if(i==0){
                if(j==0) dp[i][j] = a[i];
                else if(j==1) dp[i][j] = b[i];
                else dp[i][j] = c[i];
            }
            else{
                for(ll k=0; k<3; k++){
                    if(j == k) continue;
                    else if(j==0) dp[i][j] = max(dp[i-1][k]+a[i], dp[i][j]);
                    else if(j==1) dp[i][j] = max(dp[i-1][k]+b[i], dp[i][j]);
                    else dp[i][j] = max(dp[i-1][k]+c[i], dp[i][j]);
                }
            }
        }
    }
    int ret = 0;
    ret = max(ret, dp[n-1][0]);
    ret = max(ret, dp[n-1][1]);
    ret = max(ret, dp[n-1][2]);
    cout<<ret<<endl;


}



Measured memory_bytes: 2560
//失敗するからこそそこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
// ぜったいあきらめない
#include<bits/stdc++.h>
using namespace std;

#if defined(DAIJOBU)
#include "/home/pavan/debug.hpp"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}

const int MAX_N = 1e5 + 100;

int main() {
	FIO

	int n, r;cin >> n >> r;
	if(n < 10){
		cout << r + 100 * (10 - n);
	}
	else cout << r;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1000005;
const ull base=19260817;
int n,c[maxn][26],sum[maxn][26],sz; char str[maxn];
ull pw[maxn],s[maxn],a[maxn];
map<ull,int> mp;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",str+1); int len=strlen(str+1);
		reverse(str+1,str+len+1);
		for(int j=1;j<=len;j++) s[j]=s[j-1]*base+str[j];
		for(int j=len,k=0;j;j--)
		{
			k|=1ll<<(str[j]-'a');
			if(!mp[s[j-1]]) mp[s[j-1]]=++sz;
			int id=mp[s[j-1]];
			for(int l=0;l<26;l++)
				if(k&(1ll<<l)) sum[id][l]++;
			if(j==len) c[id][str[j]-'a']++;
		}
	}
	ll ans=0;
	for(int i=1;i<=sz;i++)
		for(int j=0;j<26;j++) ans+=(ll)c[i][j]*sum[i][j];
	printf("%lld\n",ans-n);
	return 0;
}

Measured memory_bytes: 212108
#include <stdio.h>
int main(){
	while(1){
int a,b,sum=0;
int x[11][10001],z[11][10001],y[10],max=0;
scanf("%d %d",&a,&b);
if(a==0) break;
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++){
scanf("%d",&x[i][j]);
z[i][j]=x[i][j];
}}
for(y[0]=0;y[0]<=1;y[0]++){
for(y[1]=0;y[1]<=1;y[1]++){
for(y[2]=0;y[2]<=1;y[2]++){
for(y[3]=0;y[3]<=1;y[3]++){
for(y[4]=0;y[4]<=1;y[4]++){
for(y[5]=0;y[5]<=1;y[5]++){
for(y[6]=0;y[6]<=1;y[6]++){
for(y[7]=0;y[7]<=1;y[7]++){
for(y[8]=0;y[8]<=1;y[8]++){
for(y[9]=0;y[9]<=1;y[9]++){
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++){
x[i][j]=z[i][j];
}}
if(y[0]==1){
	for(int i=1;i<=b;i++){
		if(x[1][i]==1){
			x[1][i]=0;
		}else{
			x[1][i]=1;
		}}
}
if(y[1]==1){
	for(int i=1;i<=b;i++){
		if(x[2][i]==1){
			x[2][i]=0;
		}else{
			x[2][i]=1;
		}}
}
if(y[2]==1){
	for(int i=1;i<=b;i++){
		if(x[3][i]==1){
			x[3][i]=0;
		}else{
			x[3][i]=1;
		}}
}
if(y[3]==1){
	for(int i=1;i<=b;i++){
		if(x[4][i]==1){
			x[4][i]=0;
		}else{
			x[4][i]=1;
		}}
}
if(y[4]==1){
	for(int i=1;i<=b;i++){
		if(x[5][i]==1){
			x[5][i]=0;
		}else{
			x[5][i]=1;
		}}
}
if(y[5]==1){
	for(int i=1;i<=b;i++){
		if(x[6][i]==1){
			x[6][i]=0;
		}else{
			x[6][i]=1;
		}}
}
if(y[6]==1){
	for(int i=1;i<=b;i++){
		if(x[7][i]==1){
			x[7][i]=0;
		}else{
			x[7][i]=1;
		}}
}
if(y[7]==1){
	for(int i=1;i<=b;i++){
		if(x[8][i]==1){
			x[8][i]=0;
		}else{
			x[8][i]=1;
		}}
}
if(y[8]==1){
	for(int i=1;i<=b;i++){
		if(x[9][i]==1){
			x[9][i]=0;
		}else{
			x[9][i]=1;
		}}
}
if(y[9]==1){
	for(int i=1;i<=b;i++){
		if(x[10][i]==1){
			x[10][i]=0;
		}else{
			x[10][i]=1;
		}}
}
	for(int k=1;k<=b;k++){
		for(int j=1;j<=a;j++){
		if(x[j][k]==1){
			sum++;
		}
	}
	if(sum>a/2){
		for(int j=1;j<=a;j++){
		if(x[j][k]==1){
			x[j][k]=0;
		}else{
			x[j][k]=1;
		}
	}
	}sum=0;}
for(int i=1;i<=b;i++){
for(int j=1;j<=a;j++){
if(x[j][i]==0){
	sum++;
}}}
if(max<sum){max=sum;}
sum=0;
}}}}}}}}}}
printf("%d\n",max);
max=0;
}
return 0;
}

Measured memory_bytes: 1816
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int p = sc.nextInt();
		int result = (a * 3 + p) / 2;
		System.out.println(result);                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              
	}
}

Measured memory_bytes: 22996
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(str, input().strip())) for _ in range(2)]
    MOD = 10**9 + 7

    D = []
    flag = False
    for i in range(N):
        if A[0][i] != A[1][i] and flag:
            D.append('h')
            flag = False
        elif A[0][i] != A[1][i]:
            flag = True
        else:
            D.append('v')

    if D[0] == 'h':
        ans = 6
    else:
        ans = 3

    for i in range(1, len(D)):
        if D[i-1] == 'v' and D[i] == 'h':
            ans *= 2
        elif D[i-1] == 'v' and D[i] == 'v':
            ans *= 2
        elif D[i-1] == 'h' and D[i] == 'h':
            ans *= 3
        else:
            ans *= 1

    return ans % MOD


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 3064
n = input()
number = []
count = 0
flag = False

number = list(map(int, input().split()))
while flag != True:
    tmp = []
    for n in number:
        if n % 2 == 0:
            tmp.append(n / 2)

        else:
            flag = True
            break

    if flag:
        print(count)
        break

    number = tmp
    count += 1

Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60
int cnt = 0;
vector<vector<int>> G;
void dfs(int n,int rev, vector<int> checked) {
	checked[n] = 1;
	bool f = false;
	for (int i = 0; i < checked.size();i++) {
		if (checked[i] == 0) {
			f = true;
			break;
		}
	}
	if (!f) {
		cnt++;
		return;
	}

	for (auto next : G[n]) {
		if (checked[next] == 1)continue;
		//cout << n << " => " << next << endl;

		dfs(next,n, checked);
	}
}

int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
	int N, M; cin >> N >> M;
	G.resize(N);
	for (int i = 0; i < M;i++) {
		int a, b; cin >> a >> b;
		a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	vector<int> checked(N, 0);
	dfs(0,-1, checked);
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
g = []
d = [0] * (n + 1)
for i in range(n + 1):
    g.append([]);
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u].append([v, w])
    g[v].append([u, w])
q, k = map(int, input().split())
def bfs(u):
    s = []
    s.append(u)
    while s:
        v = s[-1]
        s.pop()
        for go in g[v]:
            if not d[go[0]] and go[0] != u:
                d[go[0]] = d[v] + go[1]
                s.append(go[0])
bfs(k)
while q > 0:
    u, v = map(int, input().split())
    print(d[u] + d[v])
    q -= 1


Measured memory_bytes: 91296
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as U
import Data.Char
import Data.Maybe

readIntN :: Int -> IO (U.Vector Int)
readIntN m = U.unfoldrN m (B.readInt . B.dropWhile isSpace) <$> B.getLine

main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine
  as <- readIntN m
  print $ fromMaybe (-1) $ solve n as

solve :: Int -> U.Vector Int -> Maybe Int
solve n as = if s > n then Nothing else Just (n - s)
  where s = U.sum as


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


int main() {
  int H,W;
  cin>>H>>W;
  vector<vector<char>> p(H,vector<char>(W));
  vector<vector<int>> q(H,vector<int>(W,100000));
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>p.at(i).at(j);
    }
  }
  if(p.at(0).at(0)=='#'){
    q.at(0).at(0)=1;
  }
  else{
    q.at(0).at(0)=0;
  }
  for(int i=0;i<H+W-2;i++){
    int a=max(i-W+1,0),b=min(W-1,i);
    while(a<H&&b>=0){
      if(a!=H-1){
        if(p.at(a).at(b)=='.'&&p.at(a+1).at(b)=='#'){
          q.at(a+1).at(b)=min(q.at(a+1).at(b),q.at(a).at(b)+1);
        }
        else{
          q.at(a+1).at(b)=min(q.at(a+1).at(b),q.at(a).at(b));
        }
      }
      if(b!=W-1){
        if(p.at(a).at(b)=='.'&&p.at(a).at(b+1)=='#'){
          q.at(a).at(b+1)=min(q.at(a).at(b+1),q.at(a).at(b)+1);
        }
        else{
          q.at(a).at(b+1)=min(q.at(a).at(b+1),q.at(a).at(b));
        }
      }
      a++,b--;
    }
  }
  cout<<q.at(H-1).at(W-1)<<endl;
}

Measured memory_bytes: 256
import Data.List
 
splits :: Int -> String -> [(String, String)]
splits 0 s = []
splits n s = splitAt (n-1) s : splits (n-1) s
 
kindMax :: [(String, String)] -> Int
kindMax xs = maximum $ map (kind.(\(s1, s2) -> (sort $ nub s1, sort $ nub s2))) xs
  where kind (s1, s2) = let tmp = s1 ++ s2 in length tmp - length (nub tmp)
 
main = do
  n <- fmap read getLine
  s <- getLine
  print $ kindMax (splits n s)

Measured memory_bytes: 1020
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

vector<int> enum_div(int n){
    vector<int> ret;
    for(int i = 1 ; i*i <= n ; ++i){
        if(n%i == 0){
            ret.push_back(i);
            if(i != 1 && i*i != n){
                ret.push_back(n/i);
            }
        }
    }
    return ret;
}

int main(){
    ll N;
    cin>>N;
    vector<int> A(N);
    REP(i,N)cin>>A[i];
    int cnt=0;
    int num;
    sort(ALL(A));
    REP(i,N){
        if(i>0&&A[i]==A[i-1]) continue;
        if(i+1<N&&A[i]==A[i+1]) continue;
        bool flag=true;
        vector<int> yaku=enum_div(A[i]);
        yaku.push_back(A[i]);
        REP(j,yaku.size()){
            num=yaku[j];
            int idx=binary_search(A.begin(),A.begin()+i,A[i]/num);
            if(idx){
                flag=false;
                break;
            }
        }
        if(flag) cnt++;
    }
    cout<<cnt<<endl;
    
    
}

Measured memory_bytes: 4048
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	int a, b, h;
	cin >> a >> b >> h;
	cout << (a + b) * h / 2 << endl;
}

Measured memory_bytes: 256
#coding : utf-8

if __name__ == '__main__':

    a,b = list(map(int,input().split()))
    tower = []
    for i in range(1000):
        if i == 0:
            tower.append(1)
        else:
            tower.append(tower[i-1]+i+1)
    d = []
    for i in range(999):
        d.append(tower[i+1]-tower[i])
    for i in range(999):
        if b-a == d[i]:
            print(tower[i]-a)


Measured memory_bytes: 3060
# coding: utf-8
D, G = map(int, input().split())
pc = []
for i in range(D):
    p, c = map(int, input().split())
    pc.append([p, c])

ans = []
for i in range(2**D):
    cnt = 0
    tmp = 0
    nokori = set(range(1, D+1))
    for j in range(D):
        if (i >> j) & 1 == 1:
            tmp += pc[j][0] * (100 * (j+1)) + pc[j][1]
            cnt += pc[j][0]
            nokori.discard(j+1)
    if tmp < G:
        use = max(nokori)
        n = min(pc[use-1][0], -(-(G-tmp) // (use * 100)))
        cnt += n
        tmp += n * use * 100
    
    if tmp >= G:
        ans.append(cnt)

print(min(ans))

Measured memory_bytes: 3064
import java.util.*;
import java.io.*;
public class Main  {
    static int maxGCD(int b[], int n) 
	{ 
		int high = 0; 
		for (int i = 0; i < n; i++) 
		{
		    if(b[i]>high)
		    high=b[i];
		}
		int count[]=new int[high + 1]; 
		for (int i = 0; i < n; i++) 
			count[b[i]]++; 
		int c = 0; 
	
		for (int i = high; i >= 1; i--) 
		{ 
			int j = i; 
	
			while (j <= high) 
			{ 
				if (count[j]>0)	 
					c+=count[j];		 
				j += i; 
				if (c == 2)		 
					return i; 
			} 
			c=0; 
		} 
	return 1; 
	}
    static int gcd(int m,int n)
    {
        if(n==0)
        return m;
        else
        return gcd(n,m%n);
    }
    public static void main(String args[]) {
      FastScanner fs=new FastScanner();    
      PrintWriter out=new PrintWriter(System.out);
        
        int n=fs.nextInt();
        int a[]=fs.readArray(n);
        
        int i;
        int sg=gcd(a[0],a[1]);
        for(i=2;i<n;i++)
        {
            sg=gcd(sg,a[i]);
        }
        if(sg!=1)
        {
            out.println("not coprime");
        }
        else
        {
            if(maxGCD(a,n)==1)
            out.println("pairwise coprime");
            else
            out.println("setwise coprime");
        }
        
        out.flush();
        out.close();
    }
	static void ruffleSort(int[] a) {
 		Random random=new Random();
		int n=a.length;
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n), temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
}
        class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		
		String next() {
			while (!st.hasMoreTokens())
				try {
				st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		String nextLine(){
		    String str="";
		    try{
		        str=br.readLine();
		    }catch(IOException e){
		        e.printStackTrace(); }
		    return str;
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}

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

#define ll long long int
ll mod=1e9+7;

int main()
{
    /* Faster input ouput */
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);

    /* To read input from a file and output to a file */
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    
    ll t = 1;
    //cin >> t;
    while(t--)
    {        
        ll n,i,j;
        cin >> n;
        
        ll kyu;
        if(n >= 400 && n<=599)
        {
            kyu = 8;
        }
        else if(n >= 600 && n<=799)
        {
            kyu = 7;
        }
        else if(n >= 800 && n<=999)
        {
            kyu = 6;
        }
        else if(n >= 1000 && n<=1199)
        {
            kyu = 5;
        }
        else if(n >= 1200 && n<=1399)
        {
            kyu = 4;
        }
        else if(n >= 1400 && n<=1599)
        {
            kyu = 3;
        }
        else if(n >= 1600 && n<=1799)
        {
            kyu = 2;
        }
        else
        {
            kyu = 1;
        }

        cout << kyu << '\n';

    }
    
    return 0;
}

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

  const string vowel = "aeiou";
  bool ans = false;

  for(int i = 0; i < 5; i++) {
    if(c == vowel.at(i)) {
      ans = true;
    }
  }

  if(ans == true) {
    cout << "vowel" << endl;
  } else {
    cout << "consonant" << endl;
  }
  return 0;
}

Measured memory_bytes: 3588
N, Q = map(int, input().split())
S = input()
A = []
for i in range(N - 1):
  if S[i] == "A" and S[i+1] == "C":
    A.append(i+1)
lA = len(A)
for i in range(Q):
  l, r = map(int, input().split())
  L1 = -1
  R1 = lA
  while L1 + 1 < R1:
    C1 = (L1 + R1) // 2
    if A[C1] < l:
      L1 = C1
    else:
      R1 = C1
  L2 = -1
  R2 = lA
  while L2 + 1 < R2:
    C2 = (L2 + R2) // 2
    if A[C2] < r:
      L2 = C2
    else:
      R2 = C2
  print(L2 - L1)

Measured memory_bytes: 76632
//#pragma GCC optimize(\"Ofast,no-stack-protector\")
//#pragma GCC target(\"sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx\")
//#pragma GCC target(\"avx,tune=native\")
// Neil

#include<bits/stdc++.h>

using namespace std;

typedef complex<double> base;
typedef long double ld;
typedef long long ll;

#define endl "\n"
#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
const int MAXN=(int)(2e5+5);
const ll MOD=(ll)(1e9+7);
int t;
int arr[MAXN];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin>>n;
    ll s = 0;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        s+=arr[i];
    }
    ll a = (ll)s/n;
    
    if(s%n == 0){
        int cost = 0;
        for(int i=0;i<n;i++){
            cost += 1ll*(arr[i]-a) * (arr[i]-a);
        }
        cout<<cost<<endl;
    }
    else{
        int cost1 = 0, cost2 = 0;
        for(int i=0;i<n;i++){
            cost1 += 1ll*(arr[i]-a) * (arr[i]-a);
        }
        a++;
        for(int i=0;i<n;i++){
            cost2 += 1ll*(arr[i]-a) * (arr[i]-a);
        }
        cout<<min(cost1, cost2)<<endl;
    }
    return 0;
}

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

using namespace std;

int main (){
    ios_base::sync_with_stdio(false);
    int x, a, b;
    cin >> x >> a >> b;
    int da = x - a;
    if (da < 0)
        da = -da;
    int db = x - b;
    if (db < 0)
        db = -db;
    if (da > db)
        cout << "B";
    else
        cout << "A";
    return 0;
}


Measured memory_bytes: 256