akhauriyash/Code-Regression huggingface dataset:
# coding: utf-8


def main():
    N = int(input())
    S = input()
    S = [-1 if x == "R" else (0 if x == "G" else 1) for x in S]

    n_right_RGB = [None] * N

    n_r = 0
    n_g = 0
    n_b = 0
    for i in range(N):
        if S[i] == -1:
            n_r += 1
        elif S[i] == 0:
            n_g += 1
        else:
            n_b += 1
    
    for i in range(N):
        if S[i] == -1:
            n_r -= 1
        elif S[i] == 0:
            n_g -= 1
        else:
            n_b -= 1

        n_right_RGB[i] = [n_r, n_g, n_b]
    
    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            if S[i] == -1 and S[j] == 0:
                ans += n_right_RGB[j][2]
                if 2*j-i < N and S[2*j-i] == 1:
                    ans -= 1
            elif S[i] == -1 and S[j] == 1:
                ans += n_right_RGB[j][1]
                if 2*j-i < N and S[2*j-i] == 0:
                    ans -= 1
            elif S[i] == 0 and S[j] == 1:
                ans += n_right_RGB[j][0]
                if 2*j-i < N and S[2*j-i] == -1:
                    ans -= 1
            elif S[i] == 0 and S[j] == -1:
                ans += n_right_RGB[j][2]
                if 2*j-i < N and S[2*j-i] == 1:
                    ans -= 1
            elif S[i] == 1 and S[j] == -1:
                ans += n_right_RGB[j][1]
                if 2*j-i < N and S[2*j-i] == 0:
                    ans -= 1
            elif S[i] == 1 and S[j] == 0:
                ans += n_right_RGB[j][0]
                if 2*j-i < N and S[2*j-i] == -1:
                    ans -= 1
    
    return ans


print(main())


Measured memory_bytes: 69796
N = input()
dp = [[0]*2 for _ in range(1001000)]
dp[0][1] = 1
for i in range(len(N)):
    d = int(N[i])
    dp[i+1][0] = min(dp[i][0] + d, dp[i][1] + 10-d)
    dp[i+1][1] = min(dp[i][0] + d + 1, dp[i][1] + 10-d-1)  # もらいすぎている状態を維持する
ans = dp[len(N)][0]
print(ans)


Measured memory_bytes: 162388
#include "bits/stdc++.h"

using namespace std;

#define ll         long long int
#define eb         emplace_back

static const int maxn = 2e5 + 5;

struct information
{
      ll h, d;
      information(ll h = 0, ll d = 0) : h(h), d(d) {}
      inline bool operator < (const information &p) const
      {
            return h < p.h;
      }
};

int N;
ll height[maxn];
ll score[maxn];
ll dp[maxn];

inline void divideConquer(int l, int r)
{
      if (l >= r) return;
      int mid = (l + r) / 2;
      divideConquer(l, mid);
      vector <information> vec;
      for (int i = l; i <= mid; i++)  vec.eb(height[i], dp[i]);
      sort(vec.begin(), vec.end());
      int n = vec.size();
      vector <ll> prefixMax(n);
      ll maxi = -1;
      for (int i = 0; i < n; i++)
      {
            if (vec[i].d > maxi) maxi = vec[i].d;
            prefixMax[i] = maxi;
      }
      for (int i = mid+1; i <= r; i++)
      {
            ll h = height[i];
            auto it = lower_bound(vec.begin(), vec.end(), h) - vec.begin();
            --it;
            if (it >= 0 && it < n)
            {
                  dp[i] = max(dp[i], score[i] + prefixMax[it]);
            }
      }
      divideConquer(mid+1, r);
}

int main()
{
      scanf("%d", &N);
      for (int i = 1; i <= N; i++) scanf("%lld", height + i);
      for (int i = 1; i <= N; i++) scanf("%lld", score + i);
      for (int i = 1; i <= N; i++) dp[i] = score[i];
      divideConquer(1, N);
      ll maxi = -1;
      for (int i = 1; i <= N; i++) if (dp[i] > maxi) maxi = dp[i];
      printf("%lld", maxi);
}


Measured memory_bytes: 9788
#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, k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i,n) cin >> h.at(i);
    sort(h.begin(), h.end());
    int dmin = 1e9;
    rep(i,n-k+1) {
        int d = h.at(i+k-1) - h.at(i);
        dmin = min(dmin, d);
    }
    cout << dmin << endl;
    return 0;
}

Measured memory_bytes: 3680
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    ABs = [tuple(map(int, input().split())) for _ in range(N)]

    def isOK_LE(X, thre):
        num = 0
        for A, B in ABs:
            if A <= X:
                num += 1
        return num >= thre

    def isOK_GE(X, thre):
        num = 0
        for A, B in ABs:
            if X <= B:
                num += 1
        return num >= thre

    def binS_LE(isOK, thre):
        ng, ok = 0, 10**9+1
        while abs(ok-ng) > 1:
            mid = (ng+ok) // 2
            if isOK(mid, thre):
                ok = mid
            else:
                ng = mid
        return ok

    def binS_GE(isOK, thre):
        ng, ok = 10**9+1, 0
        while abs(ok-ng) > 1:
            mid = (ng+ok) // 2
            if isOK(mid, thre):
                ok = mid
            else:
                ng = mid
        return ok

    if N % 2:
        num = (N+1)//2
        mn = binS_LE(isOK_LE, num)
        mx = binS_GE(isOK_GE, num)
#        print('mn:', mn, '/ mx:', mx)
#        print(mx-mn)
        return mx-mn+1
    else:
        num = N//2
        mn1 = binS_LE(isOK_LE, num)
        mx1 = binS_GE(isOK_GE, num+1)
        mn2 = binS_LE(isOK_LE, num+1)
        mx2 = binS_GE(isOK_GE, num)
#        print('mn1:', mn1, '/ mx1:', mx1)
#        print('mn2:', mn2, '/ mx2:', mx2)
        mn = mn1+mn2
        mx = mx1+mx2
#        print('mn:', mn, '/ mx:', mx)
#        print(mx-mn)
        return mx-mn+1


ans = solve()
print(ans)


Measured memory_bytes: 35940
import heapq
import sys

input = sys.stdin.readline

def dijkstra(s, edge, N):
    d = [float('inf')] * N
    used = [True] * N
    d[s] = 0
    used[s] = False
    edgelist = []
    for a, b in edge[s]:
        heapq.heappush(edgelist, a * (10 ** 6) + b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)

        if not used[minedge%(10 ** 6)]:
            continue
        v = minedge % (10 ** 6)
        d[v] = minedge // (10 ** 6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, (e[0] + d[v]) * (10 ** 6) + e[1])
    return d

def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append([c,b])
        edge[b].append([c,a])
    Q, K = map(int, input().split())
    K -= 1
    d = dijkstra(K, edge, N)
    for _ in range(Q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        print(d[x] + d[y])



if __name__ == "__main__":
    main()

Measured memory_bytes: 94752
#include <bits/stdc++.h>
const int INF=1e9,MOD=1e9+7;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
int dp[3][123456];
//main
signed main(){
  for(int i=0;i<3;i++)for(int j=0;j<123456;j++)dp[i][j]=1;

  int N;cin>>N;
  if(N==1){cout<<2<<endl;return 0;}
  std::vector<set<int>> e(N);
  typedef pair<int,int> P;
  for(int i=0;i<N-1;i++){
    int a,b;cin>>a>>b;a--;b--;
    e[a].insert(b);
    e[b].insert(a);
  }
  queue<int> que;
  for(int i=0;i<N;i++)if(e[i].size()==1)que.push(i);
  while(que.size()){
    int p=que.front();que.pop();
    if(e[p].size()==0){
      cout<<(dp[0][p]+dp[1][p])%MOD<<endl;
      return 0;
    }
    int k;
    for(int a:e[p]){
      dp[0][a]*=dp[0][p]+dp[1][p];dp[0][a]%=MOD;
      dp[1][a]*=dp[0][p];dp[1][a]%=MOD;
      k=a;;
    }
    e[p].erase(k);e[k].erase(p);
    if(e[k].size()<=1)que.push(k);
  }
}


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

using namespace std;

using int64 = long long;
using vint = vector<int>;

#define FOR(i, a, b) for(int64 i=(a); i<(b); i++)
#define ROF(i, a, b) for (int64 i=(a)-1; i>=(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define PRE(i, n) ROF(i, n, 0)

#define ALL(x) (x).begin(),(x).end()
#define OUT(x) cout << (x) << endl;
#define DUMP(x) cerr << (x) << endl;

#define INF INFINITY
#define eps 1e-14

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int calc(int value, int ratio) {
    return value + value * ratio / 100;
}

int main() {
    int x, y, s;

    while (true) {
        cin >> x >> y >> s;
        if (x == 0 and y == 0 and s == 0) break;

        int ret = 0;

        FOR(i, 1, s) {
            int tmp = s - calc(i, x);
            int max_j = max(1, tmp);
            int min_j = max(1, tmp - tmp * x / 100);

            FOR(j, min_j, max_j + 1) {
                if (calc(i, x) + calc(j, x) != s) continue;
                ret = max(ret, calc(i, y) + calc(j, y));
            }
        }
        cout << ret << endl;
    }

    return 0;
}


Measured memory_bytes: 3108
//#define LOCAL

#include <cstdio>

int parent(int i) { return i/2; }
int left(int i) { return i*2; }
int right(int i) { return i*2+1; }

int main()
{
	#ifdef LOCAL
		freopen("E:\\Temp\\input.txt", "r", stdin);
		freopen("E:\\Temp\\output.txt", "w", stdout);
	#endif

	int i, n, A[300];
	scanf("%d", &n);
	for(i=1; i<=n; ++i) scanf("%d", &A[i]);
	
	for(i=1; i<=n; ++i) {
		printf("node %d: key = %d, ", i, A[i]);
		if(parent(i) >= 1) printf("parent key = %d, ", A[i/2]);
		if(left(i) <= n) printf("left key = %d, ", A[i*2]);
		if(right(i) <= n) printf("right key = %d, ", A[i*2+1]);
		printf("\n");
	}

	return 0;
}

Measured memory_bytes: 2612
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    int N, M;
    cin >> N >> M;
    vint a(M), b(M);
    vvint c(M);
    rep(i, M)
    {
        cin >> a[i] >> b[i];
        rep(j, b[i])
        {
            int C;
            cin >> C;
            c[i].push_back(C);
        }
    }
    auto dp = make_v<int>((1 << 12) + 1);
    fill_v(dp, INT_MAX / 2);
    dp[0] = 0;
    for (int i = 0; i < M; i++)
    {
        int now = 0;
        for (int j : c[i])
        {
            now |= (1 << (j - 1));
        }
        for (int bit = 0; bit < (1 << N); bit++)
        {
            chmin(dp[bit | now], dp[bit] + a[i]);
        }
    }
    if(dp[(1 << N) - 1] == INT_MAX/2)
    cout<<-1;
    else
    cout << dp[(1 << N) - 1];
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define EPS 1e-10
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define first_more_idx(ve, num) upper_bound(all(ve), num)-ve.begin() // idx = first_more_idx(ve,num); if(idx = ve.size()) , then not exist
#define first_lessequal_idx(ve, num) lower_bound(all(ve), num)-ve.begin()
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > >
#define pq_pair_ts priority_queue <pair<ll,ll> > // only sort first param
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
ll power(ll x, ll n){if(n == 0) return 1;return  (n%2)? x*power(x, n-1)%MOD : power(x*x%MOD, n/2);}
ll dx[]={0, 0, -1, 1};
ll dy[]={1, -1, 0, 0};// up,down,left right


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

    ll H,W,N;
    cin >> H >> W >> N;
    
    ll ans = min(N/H + (N%H != 0) , N/W + (N%W != 0));
    cout << ans << endl;

    //cout << fixed << setprecision(16) << ans << endl;
    return 0;
}


Measured memory_bytes: 888
#include<iostream>
#include<algorithm>
#include<utility>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;
typedef pair<int,int> p;
typedef long long ll;

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

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

int main(){
	ll n,m,k;
	cin>>n>>m>>k;
	ll a[n],b[n];
	rep(i,n)cin>>a[i];
	rep(i,n)cin>>b[i];
	ll ans=0;
	if(k==1){
		rep(i,n)ans=max(ans,a[i]*min(m,b[i])+max(0,m-b[i]));
	}else if(k==2){
		rep(i,n){
			rep(j,n){
				if(i==j)continue;
				ans=max(ans,a[i]*min(m,b[i])+a[j]*min(max(0,m-b[i]),b[j])+max(0,m-b[i]-b[j]));
			}
		}
	}else{
		rep(i,n){
			rep(j,n){
				rep(l,n){
					if((i==j) || (j==l) || (l==i))continue;
					ans=max(ans,a[i]*min(m,b[i])+a[j]*min(max(0,m-b[i]),b[j])+a[l]*min(max(0,m-b[i]-b[j]),b[l])+max(0,m-b[i]-b[j]-b[l]));
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

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

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
	ll a,b,c,d;cin>>a>>b>>c>>d;
	ll ans=(ll)0;
	ans+=b/c+b/d-a/c-a/d;
	if(a%c==(ll)0)ans++;
	if(a%d==(ll)0)ans++;
	if(a%d==(ll)0&&a%c==(ll)0)ans--;
    if(c!=d){
		ans-=b/(lcm(c,d))-a/(lcm(c,d));
	}
	cout<<(b-a+1)-ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <numeric>
#include <set>
#include <list>
#include <bitset>
#include <cstdlib>
using namespace std;

int main()
{
    int N, D, ans = 0;
    cin >> N >> D;
    while (N > 0)
    {
        N -= 2 * D + 1;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <functional>

using namespace std;
static const int INF = 1e9;
typedef pair<int, int> P;

void solve()
{
	int N;
	cin >> N;
	vector<int> a(N);
	int sum = 0;
	for (int i = 0; i < N; ++i)
	{
		cin >> a[i];
		sum += a[i];
	}
	if (sum % N == 0)
	{
		int ave = sum / N;
		int ans = 0;
		for (int i = 0; i < N; ++i)
		{
			ans += (a[i] - ave) * (a[i] - ave);
		}
		cout << ans << endl;
	}
	else
	{
		int ave_floor = sum / N;
		int ave_ceil = ave_floor + 1;
		int diff_floor = 0;
		int diff_ceil = 0;
		for (int i = 0; i < N; ++i)
		{
			diff_floor += (a[i] - ave_floor) * (a[i] - ave_floor);
			diff_ceil += (a[i] - ave_ceil) * (a[i] - ave_ceil);
		}
		cout << min(diff_floor, diff_ceil) << endl;
	}
}

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

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 44
int F[MAX]={0};

int fibonacci(int n){
  if(n==0 || n==1)return F[n]=1;
  
  if(F[n]!=0)return F[n];

  return F[n]=fibonacci(n-2)+fibonacci(n-1);
}


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

  res=fibonacci(n);
  
  printf("%d\n",res);
  return 0;
}



Measured memory_bytes: 2044
#include<iostream>

using namespace std;

int main()
{
    string s, t;
    int a, b;
    string u;

    cin >> s >> t;
    cin >> a >> b;
    cin >> u;

    if (s == u) {
        cout << a - 1 << " " << b << endl;
    } else if (t == u) {
        cout << a << " " << b - 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
typedef double ld;
typedef pair<int,int> p2;
typedef pair<p2,int> p3;
typedef vector<ll> vi;
const ll Mod = 7 + 1e9;
const ll INF32 = 5 + 2e9;
const ll INF64 = 5 + 1e18;
const ll MAX = 5+ 3e3;

int n,m;
string S,T;
int dp[MAX][MAX];
int main()
{
    cin >> S >> T;
    n = S.size();
    m = T.size();
    S = '?' + S;
    T = '?' + T;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            int c1 = dp[i-1][j];
            int c2 = dp[i][j-1];
            int c3 = -1;
            if( S[i] == T[j] )
                c3 = dp[i-1][j-1] +1;
            dp[i][j] = max( max(c1,c2) ,c3 );
        }
    string ans;
    int i = n,j = m;
    while(i && j)
    {
        int c1 = dp[i-1][j];
        int c2 = dp[i][j-1];
        int c3 = -1;
        if( S[i] == T[j] )
            c3 = dp[i-1][j-1] +1;
        //cout << dp[i][j] << ' ' << c1 << ' '  << c2 << ' ' << c3 << endl;
        if( c1 == dp[i][j] )
            i--;
        else if( c2 == dp[i][j] )
            j--;
        else {
            ans += S[i];
            i--;
            j--;
        }
    }
    reverse(ans.begin() ,ans.end());
    cout << ans << endl;
    return 0;
}


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

int main(void){
  int n; cin >> n;
  map<string,int> mp;
  rep(i,n){
    string s; cin >> s;
    mp[s]++;
  }
  int m;cin >> m;
  rep(i,m){
    string s; cin >> s;
    mp[s]--;
  }

  int ans = 0;
  for(auto s : mp){
    string key = s.first;
    int value = s.second;
    ans = max(value,ans);
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
S = input()
N = len(S)
alphabets = "BDEFHIJKLMNOPQRSUVWXYZ"

ans = 0
for width in range(1, N+1):
    for start in range(N-width+1):
        b = True
        char = S[start:start + width]
        # print(char)
        for al in alphabets:
            if al in char:
                b = False
        if b:
            ans = max(ans, len(char))

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define retunr return
#define pb push_back
#define mp make_pair
#define null NULL
#define sc(x) scanf("%d", &x)
#define sc64(x) scanf("%lld", &x)
#define pr(x) printf("%d", (x))
#define pr64(x) printf("%lld", (x))
#define sp putchar(' ')
#define ln putchar('\n')
#define rep(i,l,r) for (int i = l, lim = r;i <= lim; ++i)
#define repr(i,l,r) for (int i = r, lim = l;i >= lim; --i)
#define fi first
#define se second
#define SET(__set, val) memset(__set, val, sizeof __set)
#define fill(a,v,n) memset((a),(v),sizeof(a[0])*(n))
#define copy(a,b,n) memcpy((a),(b),sizeof(a[0])*(n))
#define ALL(x) (x.begin(),x.end())
#define prf(x) printf("%.20f", x)
#define for_each_edge(u) for(int i = point[u];i;i=G[i].n)
typedef unsigned int uint;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define N 100010
#define M 1024
#define MOD 1000000007
void _add(int &a, int b){a = (a+b)%MOD;}
void _sub(int &a, int b){a = (a+MOD-b)%MOD;}
void _mul(int &a, int b){a = (ll)a*b%MOD;}
void _max(int &a, int b){a = max(a,b);}
void _min(int &a, int b){a = min(a,b);}
ll gcd(ll a, ll b){if(!b)return a;return gcd(b,a%b);}
ll pw(ll a, ll b){ll res(1);while(b){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
ll pwM(ll a, ll b, ll mod){ll res(1);while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

const int infi = 2147483647;
const ll infl = 9223372036854775807ll;
const db PI = 3.14159265358979323846;

/*
struct E{
	int v, w, n;
}G[N];
int cnt, point[N];
void adde(int u, int v, int w = 0){
	G[++cnt]=(E){v,w,point[u]},point[u]=cnt;
	G[++cnt]=(E){u,w,point[v]},point[v]=cnt;
}
void Ginit(int n){
	cnt = 0;
	fill(point,0,n+1);
}
*/
/*
struct hh{
	int a, b;
	bool operator < (const hh &x) const{
		if(a==x.a)return b<x.b;
		return a<x.a;
	}
}a[N];
*/
int n, m, k,q;
char S[N], T[N];
int main(){
//	freopen("1", "r", stdin);
	sc(n),sc(m);
	scanf("%s%s",S,T);
	bool ok = 1;
	rep(i,0,n-1){
		ll p = i;
		p *= m;
		if(p%n)continue;
		int j = p/n;
		if(S[i] != T[j]){
			ok = 0;
			break;
		}
	}
	if(ok)
		pr64((ll)m/gcd(n,m)*(ll)n),ln;
	else
		pr(-1),ln;
/*
	int Case;
	sc(Case);
	rep(ca, 1, Case){
	    printf("Case #%d: ", ca);
	}
*/
	return 0;
}


Measured memory_bytes: 384
#include <stdio.h> 
#include <math.h>
int main(void)
{
    double x1, x2, y1, y2;
    double kyori;
    scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
    kyori = sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
    printf("%f\n", kyori);
 
    return 0;
}


Measured memory_bytes: 2056
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

//// < "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\a.txt" > "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\b.txt"


int main() {
	int N, K; cin >> N >> K;
	vector<int>teams(N);
	for (int i = 0; i < K; ++i) {
		int M; cin >> M;
		while (M--) {
			int a; cin >> a;
			a--; teams[a] = i;
		}
	}
	vector<vector<int>>hates(N);
	int R; cin >> R;
	while (R--) {
		int a, b; cin >> a >> b; a--; b--;
		hates[a].push_back(b);
		hates[b].push_back(a);
	}
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		bool flag = false;
		for (int j = 0; j < N; ++j) {
			if (i == j)continue;
			if (teams[i] == teams[j] &&find(hates[i].begin(),hates[i].end(),j) != hates[i].end())flag = true;
		}
		ans += int(flag);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3164
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <utility>
using namespace std;

typedef struct{
	char name[6];
	long num;
}product;

product p[12000000];

int main(){
	long n, now=0;
	
	scanf(" %ld", &n);
	for(long i=0; i<n; ++i){
		char s[6];
		long a;
		scanf(" %s %ld", s, &a);
		 
		bool find=false;
		for(long j=0; j<now; ++j){
			if(strcmp(p[j].name, s)==0){
				find=true;
				p[j].num+=a;
				break;
			}
		}
		
		if(!find){
			strcpy(p[now].name, s);	
			p[now].num=a;
			++now;
		}
	}

	for(long i=0; i<now; ++i){
		for(long j=i; j<now; ++j){
			if(strlen(p[i].name) > strlen(p[j].name)) swap(p[i], p[j]);
		}
	}
	
	for(long i=0; i<now; ++i){
		for(long j=i; j<now; ++j){
			if(strlen(p[i].name) == strlen(p[j].name)){
				for(int k=0; k<strlen(p[i].name); ++k){
					if(p[i].name[k] > p[j].name[k]){
						swap(p[i], p[j]);
						break;
					}
					else if(p[i].name[k] == p[j].name[k]){
						continue;
					}
					else break;
				}		
			}
		}
	}

	
	for(long i=0; i<now; ++i)
		cout << p[i].name << " " << p[i].num << endl;
	
}

Measured memory_bytes: 1224
#include <cstdio>
#include <iostream> 
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
 
using namespace std;
using ll = long long;
 
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define RREP(i, n) for(int i = n - 1; i >= 0; i--)
#define REP2(i, n, k) for(int i = 0; i < n; i += k)
 
 
int main()
{
    int n, a[200005];
    ll sum = 0, ans, k;
 
    scanf("%d", &n);
    REP(i, n){
        scanf("%d", &a[i]);
 
        sum += a[i];
    }
 
    sum -= a[0];
    k = a[0];
    ans = abs(sum - k);
 
    for(int i = 1; i < n - 1; i++){
        k += a[i];
        sum -= a[i];
 
        ans = min(ans, abs(sum - k));
    }
 
    cout << ans << endl;
}

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    int d = 0, d2 = 0;
    REP(i, N) {
        cin >> A[i];
        d += A[i] * pow(-1, i);
    }
    REP(i, N) {
        cout << (d - d2 * 2) * (int)pow(-1, i) << " ";
        d2 = d2 + A[i] * pow(-1, i);
    }
    return 0;
}


Measured memory_bytes: 1664
// AUTHOR : Kishan Srivastav
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define in freopen("input.txt", "r", stdin)
#define out freopen("output.txt", "w", stdout)
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main() {
	ios
#ifndef ONLINE_JUDGE
	in;
	out;
#endif
	int n;
	cin>>n;
	ll arr[n];
	for(int i = 0 ; i < n ; i++){
		cin>>arr[i];
	}
	ll count = 0 ;
	ll ans = 0;
	for (int i = 0; i < n; i++){
		if(arr[i+1] <= arr[i]){
			count++;
    		ans = max(ans, count);;
		}else{
			count = 0;
		}
	}
	//ans = max(ans,count);
	cout<<ans<<endl;

}

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

using namespace std;

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

#define PRINT(str) printf(#str "\n")
#define yOUT PRINT(Yes)
#define nOUT PRINT(No)
#define YOUT PRINT(YES)
#define NOUT PRINT(NO)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
	int n;
	cin >> n;
	map<int, int> mp;

	int n_1 = n;
	mp[n]++;
	FOR(i, 2, 1000000){
		if(n_1 %2 == 0){
			n = n_1/2;
		}
		else{
			n = 3*(n_1)+1;
		}
		mp[n]++;
		for(auto elem : mp){
			if(elem.second == 2){
				cout << i << endl;
				return 0;
			}
		}

		n_1 = n;
	}
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
int H,W;
cin >> H >> W;
for(int i = 0;i < W + 2;i++){
if(i == W + 1){
cout << "#" << endl;}
else cout << "#";}
for(int i= 0; i < H;i++){
string s;
cin >> s;
cout << "#" << s << "#"  << endl;}
for(int i = 0;i < W + 2;i++){
if(i == W + 1){
cout << "#" ;}
else cout << "#";}
}   


Measured memory_bytes: 256
import java.util.*;

public class Main {
public static void main(String[] args) {
		
		Scanner keyboard = new Scanner(System.in); 
		
		int N = keyboard.nextInt();
		String[] S = new String[N];

		for(int i=0; i<N; i++) {
			S[i] = keyboard.next();
		}
		
		int ac = 0; 
		int wa = 0; 
		int tle = 0; 
		int re = 0; 
		
		for(int j=0; j<N; j++) {
			if(S[j].equals("AC")) {
				ac++;
			}else if(S[j].equals("WA")) {
				wa++;
			}else if(S[j].equals("TLE")) {
				tle++;
			}else if(S[j].equals("RE")) {
				re++;
			}
		}
				
									
		System.out.print("AC x ");
		System.out.println(ac);
		System.out.print("WA x ");
		System.out.println(wa);
		System.out.print("TLE x ");
		System.out.println(tle);
		System.out.print("RE x ");
		System.out.println(re);
		keyboard.close();	
		
	}
}


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

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,e=0,o=0;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]&1)
            o++;
        else
            e++;
    }
    ll ans=1ll*pow(1ll*3,1ll*n)-pow(1ll*2,1ll*e);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4088
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define mod 1000000007
#define md 998244353
#define trace(...)
#define ll long long int
#define ld long double
#define fi first
#define se second
#define fr(i,a,b) for(ll i=a;i<=b;i++)
#define frr(i,b,a) for(ll i=b;i>=a;i--)
#define mem(a) memset(a, 0, sizeof(a))
#define vpi std::vector<pair<int,int>>
#define pii pair<int,int>
#define pb push_back
#define sall(v) sort(v.begin(),v.end())
#define all(v) (v.begin(),v.end())
#define minf -10000000
#define ppi 3.141592653589
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;

void solve() {
    int r;cin>>r;
    cout<<2*ppi*r<<endl;
    return ;
}

int main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
    int t;
    // cin>>t;
    t=1;
    while(t--){
        solve();
    }
    
    return 0;
}

Measured memory_bytes: 3804
N,M = (int(x) for x in input().split())
p_arr = []
for _ in range(M):
    p_arr.append(tuple(int(x) for x in input().split()))

P_dict = {}
for i in range(1, N+1):
    P_dict[i] = []

for i, (p, y) in enumerate(p_arr):
    P_dict[p].append((i+1, y))

P_rank_arr = [0]*(M+1)
for k in P_dict.keys():
    P_dict[k].sort(key=lambda x:x[1])
    for n, (i, _) in enumerate(P_dict[k]):
        P_rank_arr[i] = n+1

for i, (n, _) in enumerate(p_arr):
    print("{:06d}{:06d}".format(n, P_rank_arr[i+1]))


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

using namespace std;

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

	string s, t;
	cin >> s >> t;

	int n = s.size();
	int m = t.size();
	int ans = m;
	for(int p = 0; p + m - 1 < n; ++p) {
		int cnt = 0;
		for(int i = 0; i < m; ++i) {
			cnt += (s[i + p] != t[i]);
		}
		ans = min(ans, cnt);
	}

	cout << ans << '\n';

	return 0;
}


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

int main()
{
    int A,B,C;
    cin >> A >> B >> C;
    long long i=A;
    bool isYes = false;

    while(i <= A*B)
    {
        if(i%B==C)
        {
            isYes = true;
            break;
        }
        i += A;
    }
    
    if(isYes) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
using Result = vector<vector<long>>;
const long mod = 1000000007;

int n;
vector<int> G[5000];
long pre[5001];
Result rec(int from, int prev) {
  Result dp = {
    { 0, 1 },
    { 0, 0 }
  };
  for (int to : G[from]) {
    if (to == prev) continue;
    const auto& ep = rec(to, from);
    int a = dp[0].size();
    int b = ep[0].size();
    Result np = {
      vector<long>(a + b - 1),
      vector<long>(a + b - 1)
    };
    
    for (int x : { 0, 1 }) {
      for (int y : { 0, 1 }) {
        for (int i = 0; i < a; ++i) {
          for (int j = 0; j < b; ++j) {
            np[(x + y) % 2][i + j] += dp[x][i] * ep[y][j];
            np[(x + y) % 2][i + j] %= mod;
            np[(x + y + 1) % 2][i] += dp[x][i] * ep[y][j] % mod * pre[j];
            np[(x + y + 1) % 2][i] %= mod;
          }
        }
      }
    }
    dp = move(np);
  }
  return dp;
}

int main() {
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  pre[0] = 1;
  for (int i = 2; i <= n; i += 2) {
    pre[i] = pre[i - 2] * (i - 1) % mod;
  }
  
  auto res = rec(0, -1);
  long sum = 0;
  for (int x : { 0, 1 }) {
    for (int i = 0; i <= n; ++i) {
      long val = res[x][i] * pre[i] % mod;
      sum = (sum + (x ? mod - val : val)) % mod;
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
#define pi acos(-1)
#define ll long long
#define pii pair<ll,ll>
#define debug(a) cout<<a<<'\n'
#define maxn 500009 /// I wanna be the wind
#define MOD 1000000007
#define F first
#define S second
#define rep(i, a, b) for(ll i = a; i < (b); ++i)
#define per(i, b, a) for(ll i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
using namespace std;
const ll INF = 1e17 + 9;
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll fastpow(ll a, ll b){
    ll calc=1;
    for(;b>=1LL;b/=2LL){
        if((b&1LL))calc=mult(calc,a);
        a=mult(a,a);
    }
    return calc;
}
ll soma(ll a,ll b){
    if(a+b>MOD)return a+b-MOD;
    else return a+b;
}
ll subt(ll a,ll b){
    if(a-b<0)return a-b+MOD;
    else return a-b;
}
ll fact[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m;
    cin>>n>>m;
    fact[0]=1;
    rep(i,1,m+5){
        fact[i]=mult(fact[i-1],i);
    }   
    ll tot = mult(fact[m],fastpow(fact[m-n],MOD-2));
    ll ans = 0;
    rep(i,1,n+1){              
        ll div = fastpow(fact[m-n],MOD-2);
        // cout<<i<<'\n';
        ll cni = mult(fact[n],fastpow(mult(fact[i],fact[n-i]),MOD-2));
        ll calc = mult(mult(cni,fact[m-i]),div);
        if(i&1LL)calc = MOD-calc;
        ans = soma(calc,ans);
    }
    cout<<mult(tot,soma(mult(fact[m],fastpow(fact[m-n],MOD-2)),ans))<<"\n";
    return 0;  
}

Measured memory_bytes: 7416
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int INF = 1 << 29;
const ll LL_INF = 1LL << 60;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int N;
const int MAX_N = 100010;
vector<int> A;
ll sum;
int main()
{
    cin >> N;
    A.resize(N);
    for (auto &val : A)
    {
        cin >> val;
    }
    A.push_back(0);
    N = A.size();
    int pre = 0;
    for (int i = 0; i < N; i++)
    {
        sum += abs(A[i] - pre);
        pre = A[i];
    }
    // cerr << sum << endl;
    pre = 0;
    for (int i = 0; i < N - 1; i++)
    {
        int a = abs(A[i] - pre);
        int b = abs(A[i + 1] - A[i]);
        int c = abs(A[i + 1] - pre);
        pre = A[i];
        cout << sum - (a + b) + c << endl;
    }
    // cout << sum - abs(A[N - 2] - A[N - 1]) << endl;
    return 0;
}


Measured memory_bytes: 1656
#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
typedef pair<int, int> P;
const int MAX_N = 100000;
const int MAX_V = 1000000000;
int N;
int X[MAX_N];
int L[MAX_N];
void input(){
    scanf("%d", &N);
    for(int i = 0; i < N; ++i){
        scanf("%d%d", X + i, L + i);
    }
}
P ps[MAX_N];
int solve(){
    for(int i = 0; i < N; ++i){
        ps[i] = P(X[i] + L[i], X[i] - L[i]);
    }
    sort(ps, ps + N);
    int cur = -MAX_V;
    int ans = 0;
    for(int i = 0; i < N; ++i){
        if(cur <= ps[i].second){
            ans++;
            cur = ps[i].first;
        }
    }
    return ans; }
int main(){
    input();
    int ans = solve();
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(i=a;i<b;i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define vi vector < ll  int >
#define CLR(a) memset((a),0,sizeof(a))
#define mp make_pair
#define hell 1000000007
using namespace std;

void solve()
{
 ll i,j=0,r=200,p,q,k,d,y=0,h,flag=0,m=0,n,a=hell,b=hell,id,h1,h2,a1,b1,a2,w,x,u,f,l,c,e,ans=0;
 cin>>n>>m>>k;
 if(n+m+k>21) cout<<"bust";
 else cout<<"win";


}



signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    solve();
}


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

int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif
    /* for writing output to output.txt */
    int n, m; cin >> n >> m;
    long long sum = 0;
    vector <int> a(m);
    for(int i = 0; i < m; i++){
        cin >> a[i];
        sum += a[i];
    }
    if(sum > n) cout << "-1\n";
    else cout << n - sum << endl;

    return 0;
}


Measured memory_bytes: 3668
def mul(A,B):
    C=[[0]*len(B) for i in range(len(A[0]))]
    for i in range(len(A)):
        for j in range(len(B[0])):
            for k in range(len(B)):
                C[i][j]=(C[i][j]+A[i][k]*B[k][j])
    return C

def matpow(vec,n):
    B=[[0]*len(vec) for i in range(len(vec))]
    for i in range(len(vec)):
        B[i][i]=1
    while(n>0):
        if n&1:
            B=mul(B,vec)
        vec=mul(vec,vec)
        n>>=1
    return B

N=int(input())
vec=[[1,1],[1,0]]

vec=matpow(vec,N+1)
print(vec[1][0])


Measured memory_bytes: 5616
#include <stdio.h>
#include<math.h>
 
int main() {
	int cardS[13]={0},cardH[13]={0},cardC[13]={0},cardD[13]={0};
	int mark=0,rank=0,i=0,n=0;
	
	scanf("%d",&n);
	
	for(i=1;i<=n;i++){
		scanf(" %c %d",&mark,&rank);
		
		if(mark=='S'){
			cardS[rank-1]=1;
		}
		else if(mark=='H'){
			cardH[rank-1]=1;
		}
		else if(mark=='C'){
			cardC[rank-1]=1;
		}
		else if(mark=='D'){
			cardD[rank-1]=1;
		}
	}
	
	for(i=1;i<=13;i++){
		if(cardS[i-1]==0){
			printf("S %d\n",i);
		}
	}
	for(i=1;i<=13;i++){
		if(cardH[i-1]==0){
			printf("H %d\n",i);
		}
	}
	for(i=1;i<=13;i++){
		if(cardC[i-1]==0){
			printf("C %d\n",i);
		}
	}
	for(i=1;i<=13;i++){
		if(cardD[i-1]==0){
			printf("D %d\n",i);
		}
	}
	



return 0;
}

Measured memory_bytes: 596
local n, m = io.read("*n", "*n")
local edge = {}
for i = 1, n do edge[i] = {} end
for i = 1, m do
  local u, v = io.read("*n", "*n")
  table.insert(edge[u], v)
end
local s, t = io.read("*n", "*n")

local len = {}
for i = 1, 3 * n do
  len[i] = -1
end
local start_idx = (s - 1) * 3 + 1
len[start_idx] = 0


local taskstate = {}
for i = 1, 3 * n do taskstate[i] = false end
local tasks = {}
local tasknum = 0
local done = 0
local tasklim = 3 * n

local function addtask(idx)
  if not taskstate[idx] then
    taskstate[idx] = true
    tasknum = tasknum + 1
    local taskidx = tasknum % tasklim
    if taskidx == 0 then taskidx = tasklim end
    tasks[taskidx] = idx
  end
end

local function walk(src, dst)
  if len[dst] < 0 or len[src] + 1 < len[dst] then
    len[dst] = len[src] + 1
    addtask(dst)
  end
end

addtask(start_idx)
local mfl = math.floor

while done < tasknum do
  done = done + 1
  local taskidx = done % tasklim
  if taskidx == 0 then taskidx = tasklim end
  local srcidx = tasks[taskidx]
  taskstate[srcidx] = false
  local pos = 1 + mfl((srcidx - 1) / 3)
  local rem = srcidx - (pos - 1) * 3
  local dstrem = rem + 1
  if dstrem == 4 then dstrem = 1 end
  for i = 1, #edge[pos] do
    local dstpos = edge[pos][i]
    local dstidx = (dstpos - 1) * 3 + dstrem
    walk(srcidx, dstidx)
  end
end
local goal_idx = (t - 1) * 3 + 1
local ret = len[goal_idx]
if 0 < ret then ret = math.floor(ret / 3) end
print(ret)


Measured memory_bytes: 22372
#include<bits/stdc++.h>
using namespace std;
int strToInt(string s){
  int ans = 0;
  ans += 100*(int)(s[0]-'0');
  ans += 10*(int)(s[1]-'0');
  ans += (int)(s[2]-'0');

  return ans;
}

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

  vector<int>num(1000,0);
  vector<int>keta1(10,0);
  vector<int>keta2(100,0);
  int i,j,k;
  string t;
  int ans = 0;
  for(i=0;i<n-2;i++){
    t="000";
    if(keta1[(int)(s[i]-'0')]==0){
      keta1[(int)(s[i]-'0')]=1;
      t[0] = s[i];
      for(j=i+1;j<n-1;j++){
        if(keta2[10*(int)(s[i]-'0')+(int)(s[j]-'0')]==0){
          keta2[10*(int)(s[i]-'0')+(int)(s[j]-'0')]=1;
          t[1]=s[j];
          for(k=j+1;k<n;k++){
            t[2]=s[k];
            num[strToInt(t)]++;
          }
        }
      }
    }
  }
  for(i=0;i<1000;i++){
    if(num[i]>0)ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(int argc,const char * argv[])

{
    double r,are,circ;
    
    scanf("%lf", &r);
    
    are = r * r * 3.141592653589;
    circ = (2 * r) * 3.141592653589;
    
    printf("%f %f\n", are, circ);
    return 0;
}


Measured memory_bytes: 2100
N = int(input())
A = [int(i) for i in input().split()]
B = []
for i in range(N):
    B.append(abs(A[i]))

mini = min(B)
cnt = 0
for i in range(N):
    if A[i] < 0:
        cnt += 1

if cnt % 2 == 0:
    ans = sum(B)
else:
    ans = sum(B) - mini * 2
print(ans)


Measured memory_bytes: 66148
N = int(input())
s = []
l = 1
z = 0
for i in range(0,N):
    s.append(str(input()))
for i in range(0,N):
    s[i] = ''.join(sorted(s[i]))
s.sort()
for i in range(0,N-1):
    if s[i] == s[i+1]:
        l += 1
    else:
        z += l*(l-1)/2
        l = 1
z += l*(l-1)/2
print(int(z))


Measured memory_bytes: 63704
#include "bits/stdc++.h"
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long int ll;
int main() {fio; // remove during scanf
	ll a, b, c, k;
	cin >> a >> b >> c >> k;
	if(k % 2) {
		cout << b - a;
	} else {
		cout << a - b;
	}
    return 0;
}

Measured memory_bytes: 256
A, B, C = map(int, input().split())
L = [A, B, C]

if A % 2 != 0 or B % 2 != 0 or C % 2 != 0:
    print(0)
    exit()


def check(n):
    x = 2 ** n
    y = x // 3
    if x % 3 == 1:
        for i in range(3):
            adds = [y] * 3
            adds[i] += 1
            tmp = (A * adds[0] + B * adds[1] + C * adds[2]) / x
            if int(tmp) != tmp:
                return False
    else:
        for i in range(3):
            adds = [y] * 3
            adds[i] += 1
            adds[(i + 1) % 3] += 1
            tmp = (A * adds[0] + B * adds[1] + C * adds[2]) / x
            if int(tmp) != tmp:
                return False
    return True


for i in range(1, 1000):
    if not check(i):
        print(i - 1)
        exit()
print(-1)


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

int main(){
  int N; cin >>N;
  int A[N];
  long long int x[N]; x[0]=0;
  for(int i=0;i<N;i++){
    cin >>A[i];
    x[0] += A[i];
  }

  for(int i=0;2*i<N-1;i++){
    x[0] -= 2*A[2*i+1];
  }

  cout << x[0];
  for(int i=1;i<N;i++){
    x[i] = 2*A[i-1]-x[i-1];
    cout << " " << x[i];
  }

  cout << endl;
  return 0;
}


Measured memory_bytes: 2432
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
#define PI 3.141592653589793


int main(){
  ll N, W;
  cin >> N >> W;
  ll A[N], V[N];
  rep(i, N){
    cin >> A[i] >> V[i];
  }
  ll dp[N+1][100010];
  rep(i, N){
    rep(j, 100005){
      dp[i][j] = inf;
    }
  }
  dp[0][0] = 0;
  rep(i, N){
    rep(j, 100005){
      if(j>=V[i]) dp[i+1][j] = min(dp[i][j-V[i]]+A[i], dp[i][j]);
      else dp[i+1][j] = dp[i][j];
    }
  }
  ll ans;
  rep(i, 100005){
    if(dp[N][i]<=W) ans = i;
  }
  cout << ans << endl;
}

Measured memory_bytes: 79232
#include <cstdio>
#include <functional>
#include <vector>
#include <tuple>
#include <algorithm>
#include <deque>
#include <memory>

using namespace std;

using ll = long long;
int n, m;
int digits[9];
int sticks_for_digits[10] = {-1,2,5,5,4,5,6,3,7,6};
bool called[10000];
bool reachable[10000];

struct Node {
  int value;
  shared_ptr<Node> next;
  Node(int v, shared_ptr<Node> n) : value(v), next(n) {};
  // ~Node() { printf("~Node(%d)\n", value); }
};
struct LinkedList {
  shared_ptr<Node> root;
  int length;
  LinkedList() : length(0) {};
  LinkedList(int v, LinkedList& tail) : length(tail.length+1), root(make_shared<Node>(v, tail.root)) {};
  bool empty()
  {
    return length == 0;
  }
  int size()
  {
    return length;
  }
};
LinkedList nil;
LinkedList cons(int value, LinkedList& list)
{
  return LinkedList(value, list);
}
LinkedList dp[10000];

bool is_left_ge(LinkedList& left, LinkedList& right)
{
  if (left.length > right.length) return true;
  if (left.length < right.length) return false;
  shared_ptr<Node> l = left.root;
  shared_ptr<Node> r = right.root;
  while (!((l == nullptr) && (r == nullptr))) {
    if (l->value > r->value) return true;
    if (l->value < r->value) return false;
    l = l->next;
    r = r->next;
  }
  return true;
}

void solve(int sticks)
{
  if (called[sticks]) return;
  called[sticks] = true;
  LinkedList cur;// = nil;
  //printf("entering solve(%d)\n", sticks);
  //cur.push_back(0);
  for (int i = 0; i < m; i++) {
    int to_consume = sticks_for_digits[digits[i]];
    if (sticks < to_consume) continue;
    solve(sticks-to_consume);
    /*printf("solve(%d) =", sticks-to_consume);
    Node *ptr = dp[sticks-to_consume];
    while (ptr) {
      printf("%d", ptr->value);
      ptr = ptr->next;
    }
    printf("\n");*/
    if (!reachable[sticks-to_consume]) continue;
    LinkedList newlist = cons(digits[i], dp[sticks-to_consume]);
    if (is_left_ge(newlist, cur)) {
      cur = newlist;
    }
  }
  if (cur.length == 0) {
    int c = 0;
    for (int i = 0; i < m; i++) {
      if (sticks_for_digits[digits[i]] == sticks) {
        c = max(c, digits[i]);
      }
    }
    if (c != 0) {
      cur = cons(c, cur);
    }
  }
  else if (cur.length == 1) {
    for (int i = 0; i < m; i++) {
      if (sticks_for_digits[digits[i]] == sticks) {
        cur.root->value = max(cur.root->value, digits[i]);
      }
    }
  }
  if (cur.length != 0) {
    dp[sticks] = cur;
    reachable[sticks] = true;
  }
}

int main()
{
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d", &(digits[i]));
    //int sticks = sticks_for_digits[digits[i]];
    //digits_for_sticks[sticks] = max(digits_for_sticks[sticks], digits[i]);
  }
  reachable[0] = true;
  called[0] = true;
  dp[0] = LinkedList();
  solve(n);
  shared_ptr<Node> ptr = dp[n].root;
  vector<int> ds;
  while (ptr) {
    ds.push_back(ptr->value);
    ptr = ptr->next;
  }
  for (auto d : ds) {
    printf("%d", d);
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
int main(){
	int N, K, output=1;
	scanf("%d %d", &N,&K);
	for(int i=0;i<N;i++){
		(output+K>output*2)?output*=2:output+=K;
	}
	printf("%d\n",output);
	return 0;
}

Measured memory_bytes: 1692
#include<iostream>
using namespace std;
typedef long int li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
#define Please return
#define AC 0


int main(){
  li a,b,c; cin >>a >>b >>c;
  if(a+b>=c) printf("No\n");
  else if(4*a*b < (c-(a+b))*(c-(a+b))){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  if(df)printf("%ld %ld\n",4*a*b,(c-(a+b))*(c-(a+b)));
  Please AC;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int a, b, c, x;
    scanf("%d %d %d\n", &a, &b, &c);
    if(a > b)
    {
        x = a;
        a = b;
        b = x;
    }
    if(b > c)
    {
        x = b;
        b = c;
        c = x;
    }
    if(a > b)
    {
        x = a;
        a = b;
        b = x;
    }

    printf("%d %d %d\n", a, b, c);
    return 0;
}
   

Measured memory_bytes: 600