akhauriyash/Code-Regression huggingface dataset:
def main():
    cnt = 0
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i in range(1, n+1):
        if same(i, p[i-1]):
            cnt += 1
    print(cnt)

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def unite(x, y):
    x = root(x)
    if x != root(y):
        par[x] = y

def same(x, y):
    return root(x) == root(y)

if __name__ == "__main__":
    n, m = map(int, input().split())
    par = list(range(n+1))
    p = list(map(int, input().split()))
    main()

Measured memory_bytes: 122164
import std.stdio;
import std.string;
import std.conv;
import std.array;

void main() {
  auto ops =
    ["+": (double x, double y) => x + y,
     "-": (double x, double y) => x - y,
     "*": (double x, double y) => x * y,
     "/": (double x, double y) => x / y];
  while(true) {
    string line = readln.chomp;
    if (stdin.eof) break;
    string[] content = line.split(" ");
    double[] state = [];
    while(content.length > 0) {
      string value = content.front;
      content.popFront;
      if (value in ops) {
        double a = state[$ - 2];
        double b = state[$ - 1];
        state.popBack;
        state.popBack;
        state ~= ops[value](a, b);
      }
      else {
        state ~= value.to!(double);
      }
    }
    writefln("%8f", state[0]);
  }
}

Measured memory_bytes: 1152
///In the name of GOD
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 2e6 + 10;
const ll Mod = 1e9 + 7;
ll n, m, k, ans;
ll F[MXN], I[MXN], p26[MXN], p25[MXN];
string s;
ll power(ll a, ll b){
    return (!b ? 1 : power(a * a % Mod, b / 2) * (b & 1LL ? a : 1) % Mod);
}
ll inv(ll x){
    return power(x, Mod - 2);
}
ll C(ll cn, ll cr){
    if(cr < 0 || cr > cn) return 0;
    return (F[cn] * I[cr] % Mod) * I[cn - cr] % Mod;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    F[0] = I[0] = p26[0] = p25[0] = 1;
    for(ll i = 1; i < MXN; i ++) F[i] = F[i - 1] * i % Mod;
    for(ll i = 1; i < MXN; i ++) I[i] = I[i - 1] * inv(i) % Mod;
    for(ll i = 1; i < MXN; i ++) p26[i] = p26[i - 1] * 26LL % Mod;
    for(ll i = 1; i < MXN; i ++) p25[i] = p25[i - 1] * 25LL % Mod;
    cin >> k >> s, n = s.size(), m = n + k;
    for(ll i = n; i <= m; i ++){
        ll now = p25[i - n] * p26[m - i] % Mod;
        now = now * C(i - 1, n - 1) % Mod;
        ans = (ans + now) % Mod;
    }
    cout << ans << '\n';
    return 0;
}
/*!
    I CHOOSE TO HAVE FAITH,
    BECAUSE WITHOUT THAT,
    I HAVE NOTHING....
    ITS THE ONLY THING THAT'S KEEPING ME GOING.
*/
//! N.N


Measured memory_bytes: 66748
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
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;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
ll n,k;
ll sum[200010];
template<typename T>
struct BIT {
int n;
vector<T> d;
BIT(int n=0):n(n),d(n+1) {}
void add(int i, T x=1) {
for (i++; i <= n; i += i&-i) {
d[i] += x;
}
}
T sum(int i) {
T x = 0;
for (i++; i; i -= i&-i) {
x += d[i];
}
return x;
}
};
int main(){
    BIT<ll> bit(200010);
    cin>>n>>k;
    vl a(n);rep(i,n)cin>>a[i];
    rep(i,n){
        a[i]-=k;
        sum[i+1]=sum[i]+a[i];
    }
    vl v;
    rep(i,n+1)v.pb(sum[i]);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    ll ans=0;
    for(int i=0;i<=n;i++){
        auto it=lower_bound(v.begin(),v.end(),sum[i])-v.begin();
        ans+=bit.sum(it);
        //cout<<bit.sum(it)<<endl;
        bit.add(it,1);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 7156
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
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;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ll x,y,a,b,c;
    cin >> x >> y >> a >> b >> c;
    vector<ll> p(a),q(b),r(c);
    rep(i,a) cin >> p[i];
    rep(i,b) cin >> q[i];
    rep(i,c) cin >> r[i];
    vector<ll> ans;
    sort(all(p));
    sort(all(q));
    sort(all(r));
    reverse(all(p));
    reverse(all(q));
    reverse(all(r));
    rep(i,x) ans.pb(p[i]);
    rep(i,y) ans.pb(q[i]);
    rep(i,c) {
        if(i > x+y-1) break;
        ans.pb(r[i]);
    }
    sort(all(ans));
    reverse(all(ans));
    ll sum = 0;
    rep(i,x+y) sum += ans[i];
    cout << sum << endl;
}

Measured memory_bytes: 8688
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#define MOD 1000000007

typedef long long ll;
using namespace std;

int main(void) {
    ll a,b,c,k;
    cin >> a >> b >> c >> k;
    if(k%2){
        if(b-a<=1E18 && b-a>=-1E18){
            cout << b-a << endl;
        }else{
            cout << "Unfair" << endl;
        }
    }else{
        if(a-b<=1E18 && a-b>=-1E18){
            cout << a-b << endl;
        }else{
            cout << "Unfair" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define typeof(x) __typeof__(x)
#define int long long int
#define double long double
#define mod(x) ((x % MOD) + MOD) % MOD
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);--i)

#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SZ(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) UB(c,x)-LB(c,x)
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (s).find(e)!=(s).end()
#define PB push_back
#define MP make_pair
#define vec vector

#define dump(x)  cerr << #x << " = " << (x) << endl;

using namespace std;

typedef pair<int,int> P;
struct edge { int to, cost; };

const int INF = 1e18;
const int MOD = 1e9+7;

template<typename T> ostream& operator << (ostream& s, const vector<T>& v) {
   s << "[";
   for (int i = 0; i < v.size(); i++) { s << v[i]; if (i < v.size() - 1) s << " "; }
   s << "]";
   return s;
}
template<typename T1, typename T2> ostream& operator << (ostream& s, const pair<T1,T2>& p) {
   s << "(" << p.first << "," << p.second << ")";
   return s;
}
template<typename T1, typename T2> ostream& operator << (ostream& s, const map<T1,T2>& m) {
   s << "{";
   for (auto i = m.begin(); i != m.end(); ++i) {
      s << i->first << ":" << i->second;
      if (next(i) != m.end()) s << ", ";
   }
   s << "}";
   return s;
}

vector<bool> isprime;
void init_isprime(int N)
{
   isprime = vector<bool>(N+1, true);
   isprime[0] = isprime[1] = false;
   for(int i = 2; i <= N; i++) {
      if (isprime[i]) {
         for (int j = 2; i*j <= N; j++) {
            isprime[i*j] = false;
         }
      }
   }
}
void factorize(map<int,int>& fact_n, int M)
{
   int tmpM = M;
   for(int i = 2; i < isprime.size(); i++) {
      if (!isprime[i]) continue;
      while (tmpM % i == 0) {
         fact_n[i]++;
         tmpM /= i;
      }
   }
   if (tmpM != 1) fact_n[tmpM]++;
}

signed main()
{
   int N; cin >> N;
   init_isprime(N);
   map<int,int> fact_n;
   rep(i, 1, N+1) {
      factorize(fact_n, i);
   }
   dump(fact_n)

   int a = 0, b = 0, c = 0, d = 0, e = 0;
   int n;
   EACH(i, fact_n) {
      n = i->second;
      if (n >= 3*5*5-1) {
         a++;
      } else if (n >= 5*5-1) {
         b++;
      } else if (n >= 3*5-1) {
         c++;
      } else if (n >= 5-1) {
         d++;
      } else if (n >= 3-1) {
         e++;
      }
   }
   int ans = a +                                                              // 75
            (a+b)*(c+d+e) + (a+b)*(a+b-1) +                                   // 25,3
            (a+b+c)*d + (a+b+c)*(a+b+c-1) +                                   // 15,5
            (a+b+c+d)*(a+b+c+d-1)/2*e + (a+b+c+d)*(a+b+c+d-1)*(a+b+c+d-2)/2;  // 5,5,3
   cout << ans << endl;

   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define cel(n, k) ((n-1)/k+1)
#define sets(a) memset(a, -1, sizeof(a))
#define clr(a) memset(a, 0, sizeof(a))
 
 
#define fr(i, n) for(int i=0; i<n;i++)
#define fr1(i, n) for(int i=1; i<=n;i++) 
 
#define readf(f) freopen(f, "r", stdin)
#define writef(f) freopen(f, "w", stdout)
 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define nl "\n"
 
void file(){
	readf("in.txt");
    writef("out.txt");
}
 
template< class T > T sq(T x) { return x * x; }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
 
typedef long long ll;
typedef pair<int,int> pii;

 
int main()
{
	//file();
 
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
	int n, ans = 0, x, a[100005], k;
	long long dp[100005];

	cin>>n>>k;

	fr(i,n){
		dp[i] = LLONG_MAX;
		cin>>a[i];
	}
    
    dp[0] = 0;

    dp[1] = abs(a[1]-a[0]);
 	for(int i = 2; i < n; i++){
 		for(int step = 1; step <= k; step++){
 			if(i-step >= 0){
 				dp[i] = min(dp[i-step] + abs(a[i]-a[i-step]), dp[i]);
 			}
 		}
 		
 	}

 	cout<<dp[n-1]<<nl;

    return 0;
 
}

Measured memory_bytes: 1408
#include <iostream>
#include <string>

#define rep(i, n) for (int i = 0; i < n; i++)

using namespace std;

int n;
int s[102];
void solve() {
    int mini = 10000;
    int maxi = -1;
    int ans = 0;
    rep(i, n) {
        if (s[i] < mini) mini = s[i];
        if (s[i] > maxi) maxi = s[i];
        ans += s[i];
    }
    ans -= mini;
    ans -= maxi;

    cout << ans / (n - 2) << endl;
}

int main() {
    while (cin >> n) {
        if (n == 0) break;
        rep(i, n) cin >> s[i];
        solve();
    }
}

Measured memory_bytes: 3040
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		int N = S.length();
		int cnt = 0;
		String str = "keyence";
		for(int i = 0; i < 7; i++) {
			if(S.substring(i, i + 1).equals(str.substring(i, i + 1))) {
				cnt++;
			} else {
				break;
			}
		}
		if(cnt == 7) {
			System.out.println("YES");
			return;
		}
		
		for(int i = 0; i < 7; i++) {
			if(S.substring(N - 1 - i, N - i).equals(str.substring(6 - i, 7 - i))) {
				cnt++;
				if(cnt == 7) break;
			} else {
				break;
			}
		}
		if(cnt == 7) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}


Measured memory_bytes: 21844
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, X, Y = MAP()
x = LIST()
y = LIST()
for i in range(max(x)+1, min(y)+1):
	if X < i <= Y:
		print("No War")
		break

else:
	print("War")

Measured memory_bytes: 5652
#include<bits/stdc++.h>
#define maxn 100005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long
#define ld long double
#define debug(x) cerr<<#x<<": "<<x<<endl
#define fgx cerr<<"--------------"<<endl
#define dgx cerr<<"=============="<<endl

using namespace std;
struct vc{
	ld x,y;
	vc operator*(const ld b){vc t;t.x=x*b,t.y=y*b;return t;}
};
struct pt{
	ld x,y;
	pt operator+(const vc b){pt t;t.x=x+b.x,t.y=y+b.y;return t;}
	vc operator-(const pt b){vc t;t.x=x-b.x,t.y=y-b.y;return t;}
};

inline int read(){
	int x=0,f=1; char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}

inline ld cross(vc a,vc b){return a.x*b.y-a.y*b.x;}
inline pt get(){pt t;t.x=read(),t.y=read();return t;}
inline vc nl(vc a){vc b;b.x=-a.y,b.y=a.x;return b;}
inline pt glt(pt a,pt b,pt c,pt d){
	vc u=b-a,v=d-c,w=a-c;
	ld t=cross(v,w)/cross(u,v);
	return a+u*t;
}

int main(){
	pt p1=get(),p2=get();
	int Q=read();
	while(Q--){
		pt p=get(); vc a=p1-p2,b=nl(a);
		pt p0=p+b,res=glt(p1,p2,p,p0);
		vc t=res-p; pt ans=res+t;
		printf("%.10Lf %.10Lf\n",ans.x,ans.y);
	}
	return 0;
}



Measured memory_bytes: 3208
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define PB push_back
#define ll long long
#define pii pair<LL,LL>
#define MEM(x,y) memset(x,y,sizeof(x))
#define bug(x) cout<<"debug "#x" is "<<x<<endl;
#define FIO ios::sync_with_stdio(false);
#define ALL(x) x.begin(),x.end()
#define LOG 20
#define lson(x) ((x)<<1)
#define rson(x) ((x)<<1|1)
const int maxn=2e5+10;
ll n,p;
ll a[maxn];
ll ans=0,mod;
ll add(ll a,ll b){return (a+b)%mod;};
ll mul(ll a,ll b){return (a*b)%mod;};
ll sub(ll a,ll b){return (a-b+mod)%mod;};
ll ksm(ll r,ll d){
    ll res=1;
    while(d){
        if(d&1)res=mul(res,r);
        r=mul(r,r);
        d>>=1;
    }
    return res;
}
ll di(ll a,ll b){return mul(a,ksm(b,mod-2));}

int main(){
    string s;
	cin>>n>>p>>s;
	for(int i=1;i<=n;i++)a[i]=s[i-1]-'0';
	mod = p;
	if(p==2){
	    for(int i=1;i<=n;i++)if(a[i]%2==0) ans+=i;
        cout<<ans<<endl;
	}
	else if(p==5){
	    for(int i=1;i<=n;i++)if(a[i]%5==0) ans+=i;
	    cout<<ans<<endl;
	}
	else{
        a[n+1]=0;
        map<ll,ll> h;
        //h[0]=1;
        for(int i=n,po=1;i>=1;i--,po=mul(po,10)){
            a[i]=add(mul(a[i],po),a[i+1]);
            ans+=h[a[i]];
            h[a[i]]++;
            if(a[i]==0) ans++;
        }
        cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 2564
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> L;
	for (int i = 0; i < N; ++i) {
		int tmp;
		cin >> tmp;
		L.push_back(tmp);
	}

	int cnt = 0;
	for (int i = 0; i < N - 2; ++i) {
		for (int j = i + 1; j < N - 1; ++j) {
			for (int k = j + 1; k < N; ++k) {
				if (L[i] != L[j] && L[j] != L[k] && L[k] != L[i]) {
					if (L[i] + L[j] > L[k] && L[j] + L[k] > L[i] && L[k] + L[i] > L[j]) {
						cnt++;
					}
				}
			}
		}
	}
	cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include<vector>
#include<algorithm>
#include<complex>
#include<string>
#include<string.h>
using namespace std;
typedef long long int llint;
#define rep(i,n) for(int i=0;i<n;i++)

int main() {
	llint n;
	cin >> n;
	vector<llint>a(n + 1);
	llint x;
	rep(i, n + 1) {
		if (i == 0) {
			a[i] = 0;
		}
		else {
			cin >> x;
			a[i] = a[i - 1] + x;
		}
	}
	sort(a.begin(), a.end());
	llint ans = 0;
	llint cnt = 0;
	rep(i, n) {
		if (a[i] == a[i + 1]) {
			if (cnt == 0) {
				cnt = 1;
			}
			cnt++;
		}
		else {
			ans += cnt*(cnt - 1) / 2;
			cnt = 0;
		}
	}
	ans += cnt*(cnt - 1) / 2;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) ((int)(x).size())
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    string s; cin>>s;
    int ans=0,cnt=0;
    REP(i,SZ(s)){
        if(s[i]=='A' or s[i]=='C' or s[i]=='G' or s[i]=='T') cnt++;
        else cnt=0;
        ans=max(ans,cnt);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long k = sc.nextInt();
		int n = sc.nextInt();
		long ans = 0;
		long max = 0;
		long[] a = new long[n];
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextLong();
		}
		for(int i = 0; i < n; i++) {
			if(i < n - 1) {
				ans += a[i + 1] - a[i];
				max = Math.max(max, a[i + 1] - a[i]);
			} else {
				ans += k + a[0] - a[i];
				max = Math.max(max, k + a[0] - a[i]);
			}
		}
		ans -= max;
		System.out.println(ans);

	}

}


Measured memory_bytes: 87616
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(int)(b); i++)
#define PPC(x) __builtin_popcountll((x))
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
using namespace std;

const int maxN = 2420;
char in[maxN];
int cnt[maxN];

int main()
{
	int n;
	scanf ("%d", &n);
	scanf ("%s", in);
	
	FOR(i, 0, n)
		cnt[in[i]]++;
		
	printf("%s\n", cnt['R'] > cnt['B'] ? "Yes" : "No");
	return 0;
}	


Measured memory_bytes: 256
q,h,s,d = map(int, input().split())
n = int(input())

q = 4*q
h = 2*h

min_1 = min(q,h,s)
if n == 1:
    print(min_1)
else:
    if min_1*2 < d:
        print(n*min_1)
    else:
        double = n//2
        v = double*d
        if n%2 == 1:
            v += min_1
        print(v)

Measured memory_bytes: 61804
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct Info{ll nu;int we;}a[1000010];
struct edg{int x,y;}an[1000010];
bool c=true;
int n,si[1000010];
ll su;
bool comp(const Info &a,const Info &b){return a.nu>b.nu;}
bool comp1(const Info &a,const Info &b){return a.we<b.we;}
int find(ll x){
	int l=1,r=n,mid;
	while (l+1<r){
		mid=(l+r)/2;
		if (a[mid].nu<x) r=mid;else l=mid;
	}
	if (a[r].nu==x) return r;
	if (a[l].nu==x) return l;
	return 0;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){cin>>a[i].nu;a[i].we=i;}
	sort(a+1,a+n+1,comp);
	for (int i=1;i<=n;i++) si[i]=1;
	for (int i=1;i<n;i++){
		int x=find(a[i].nu-n+si[i]*2);
		if (x==0) c=false;
		else{
			si[x]+=si[i];
			an[i].x=a[i].we;an[i].y=a[x].we;
		}
		su+=si[i];
	}
	if (su!=a[n].nu)c=false;
	sort(a+1,a+n+1,comp1);
	if (c){
		for (int i=1;i<n;i++) cout<<an[i].x<<' '<<an[i].y<<endl;
	}else{
		cout<<"-1"<<endl;
	}
	return 0;
}

Measured memory_bytes: 9984
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pl;
#define all(a) (a).begin(),(a).end()
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=(a);i<(b);i++)
#define rrep(i,n) for(ll (i)=(n)-1;(i)>=0;i--)
#define SHOW(x) cout << #x << ": " << x << endl;
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;

int main(){
    ll n,x,ans = 0;
    cin>>n>>x;
    vector<int>a(n);
    rep(i,n)cin>>a[i];
    rep(i,n-1){
        if(a[i] + a[i + 1] > x){
            ll diff = (a[i] + a[i + 1]) - x;
            ans += diff;
            a[i + 1] = max(a[i + 1] - diff,0LL);
        }
    }
    cout<<ans<<endl;
}


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


int main() {
	string s;
	cin >> s;
	bool g = true;
	for (int i = 1; i < 4; i++) {
		if (s[i] == s[i - 1]) g = false;
	}
	cout << (g ? "Good" : "Bad") << endl;
	return 0;
}


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

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

  vector<int> button(N);
  vector<bool> pushed(N);

  for (size_t i = 0; i < N; i++) {
    cin >> button.at(i);
    pushed.at(i) = false;
  }

  int next = 1;
  int count = 0;

  while (1) {
    if (next == 2) {
      cout << count << endl;
      exit(EXIT_SUCCESS);
    }

    if (pushed.at(next-1) == false) {
      pushed.at(next-1) = true;
      next = button.at(next-1);
      count++;
    } else {
      cout << "-1" << endl;
      exit(EXIT_SUCCESS);
    }
  }
}


Measured memory_bytes: 640
#include <ios>
#include <iomanip>
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
 
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)

#define PI (acos(-1))
#define print(x) cout << x << endl
 
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;

int main()
{
    ll N;
    cin >> N;
    print(180 * (N - 2));
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	long long int n, m;
	scanf("%lld %lld", &n, &m);
	long long int i;
	long long int x[100005], y[100005];
	for (i = 0; i < n; i++)
		scanf("%lld", &x[i]);
	for (i = 0; i < m; i++)
		scanf("%lld", &y[i]);
	long long int p = 1e9 + 7;
	long long int X, Y;
	X = Y = 0;
	for (i = 0; i < n - 1; i++)
		X = (X + (x[i + 1] - x[i]) * (i + 1) * (n - i - 1)) % p;
	for (i = 0; i < m - 1; i++)
		Y = (Y + (y[i + 1] - y[i]) * (i + 1) * (m - i - 1)) % p;
	printf("%lld\n", (X * Y) % p);
	return 0;
}

Measured memory_bytes: 1664
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 15 , P = 1e9 + 7;
int n , m , g[N] , f[1 << N] , can[1 << N] , cnt[N][1 << N];
inline void pp(int &x,int d){if((x+=d)>=P)x-=P;}
inline int mul(int a,int b){return ll(a)*b%P;}

int main(){
    cin >> n >> m;
    rep(i,0,m) {
        int x , y;
        cin >> x >> y;
        --x;--y;
        g[x] |= 1 << y;
    }
    rep(i,0,n) rep(j,0,n) rep(k,0,1<<j)
        cnt[i][k|1<<j]=cnt[i][k]+(g[i]>>j&1);
    rep(i,0,1<<n) can[i] = (i & 1) == (i >> 1 & 1);
    f[0] = 1;
    rep(i,1,1<<n) if(can[i]) {
        f[i] = 1;
        for(int s=i;s;s=(s-1)&i){
            if(s==i || !can[s]) continue;
            int t=s^i;
            int tmp=f[s];
            rep(j,0,n) if(s>>j&1) tmp=mul(tmp,(1<<cnt[j][t])-1);
            rep(j,0,n) if(t>>j&1) tmp=mul(tmp,1<<cnt[j][s]);
            pp(f[i],tmp);
        }
    }
    int ans=1;
    rep(i,0,m) ans=ans*2%P;
    pp(ans,P-f[(1<<n)-1]);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2432
import core.bitop;
import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.format;
import std.math;
import std.random;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
  immutable k = readln.chomp.to!long;
  enum N = 50;
  long v = k / N;
  immutable remain = k % N;
  N.writeln;
  stderr.writeln(v, " ", remain);
  foreach (i; 0..N) {
    if (i) {
      write = " ";
    }
    if (i < remain) {
      write = v + N * 2 - remain;
    } else {
      write = v + N - (remain + 1);
    }
  }
  writeln;
}


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

const ll MOD=1e9+7;
const double EPS=1e-9;
const double PI=acos(-1.0);
//const long double PI=acos(-1.0L);

struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}

    Point operator +(const Point &b) const {return Point(x+b.x,y+b.y);}
    Point operator -(const Point &b) const {return Point(x-b.x,y-b.y);}
    Point operator *(const double b) const {return Point(x*b,y*b);}
    Point operator /(const double b) const {return Point(x/b,y/b);}
};

struct Line{
    Point a,b;
    Line(){}
    Line(Point a,Point b):a(a),b(b){}
};

int sgn(double a) {return (a>EPS)-(a<-EPS);}
int sgn(double a,double b) {return sgn(a-b);}

double dot(const Point &a,const Point &b) {return (a.x*b.x+a.y*b.y);}
double cross(const Point &a,const Point &b) {return (a.x*b.y-a.y*b.x);}
double norm(const Point &p) {return dot(p,p);}
double abs(const Point &p) {return sqrt(norm(p));}

Point projection(const Point &p,const Line &l){
    double r=dot(p-l.a,l.b-l.a)/norm(l.b-l.a);
    return l.a+(l.b-l.a)*r;
}

Point reflection(const Point &p,const Line &l){
    return p+(projection(p,l)-p)*2;
}

//1:Counter_Clockwise -1:Clockwise
//2:a-b-c -2:c-a-b 0:a-c-b
int ccw(const Point &p,const Point &q){
    int s=sgn(cross(p,q));
    if(s!=0) return s;
    if(dot(p,q)<0) return -2;
    if(norm(p)<norm(q)) return 2;
    return 0;
}
int ccw(const Point &a,const Point &b,const Point &c){return ccw(b-a,c-a);}

bool isParallel(const Line &l,const Line &r){
    if(sgn(cross(l.b-l.a,r.b-r.a))==0) return true;
    return false;
}
bool isOrthogonal(const Line &l,const Line &r){
    if(sgn(dot(l.b-l.a,r.b-r.a))==0) return true;
    return false;
}

int main(){
    int Q;
    cin>>Q;

    for(int q=0;q<Q;q++){
        Point P1,P2;
        cin>>P1.x>>P1.y>>P2.x>>P2.y;
        Point P3,P4;
        cin>>P3.x>>P3.y>>P4.x>>P4.y;

        Line L1(P1,P2);
        Line L2(P3,P4);
        if(isParallel(L1,L2)) cout<<"2"<<endl;
        else if(isOrthogonal(L1,L2))cout<<"1"<<endl;
        else cout<<"0"<<endl;
    }

    return 0;
}



Measured memory_bytes: 3232
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
# from bisect import *
# from collections import *
# from heapq import *
# import functools
# import itertools
# import math
INF = 500000
MOD = 10**9+7

s, t = input().split()
print(t+s)


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

int main(){
   char s[3],s2[3];
   for(int i=0;i<3;i++)cin>>s[i];
   for(int i=0;i<3;i++)cin>>s2[i];
   if(s[0]==s2[2] && s[1] == s2[1] && s[2] == s2[0]){
      cout << "YES";
   }else{
      cout << "NO";
   }

   return 0;
}

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

bool palindrome(string s){
    string t(s.rbegin(),s.rend());
    return s == t;
}

int main(){
    string s;
    cin>>s;
    int n=s.size();
    if(palindrome(s) && palindrome(s.substr(0,(n-1)/2)) && palindrome(s.substr((n+1)/2))){
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
}


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

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

using namespace std;

typedef long long ll;

int A,B,C;
ll K;

int main(){
	cin>>A>>B>>C>>K;
	if (K%2){
		cout<<B-A<<endl;
	}else{
		cout<<A-B<<endl;
	}
	return 0;
}

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

using namespace std;
typedef long long ll;
const int N = 2010;
const int MOD = 924844033;
int _w;

void add_mod( int &a, int b ) {
	a += b;
	a -= a >= MOD ? MOD : 0;
}

int n, k;
int f[N], fn;

void mul( int *a, int n, int *b, int m ) {
	static int t[N];
	for( int i = 0; i <= n+m; ++i ) t[i] = 0;
	for( int i = 0; i <= n; ++i )
		for( int j = 0; j <= m; ++j )
			add_mod( t[i+j], int(1LL * a[i] * b[j] % MOD) );
	for( int i = 0; i <= n+m; ++i )
		a[i] = t[i];
}

int tmp[N], tn, g[N][N][2], vis[N];
void solve1() {
	f[0] = 1, fn = 0;
	for( int i = 1; i <= n; ++i )
		if( !vis[i] ) {
			tn = 0;
			for( int j = i; j <= n; j += k+k ) {
				vis[j] = 1;
				tmp[tn++] = j;
			}
			for( int a = 0; a <= tn; ++a )
				for( int b = 0; b <= tn; ++b )
					g[a][b][0] = g[a][b][1] = 0;
			g[0][0][0] = 1;
			for( int a = 0; a < tn; ++a )
				for( int b = 0; b < tn; ++b ) {
					if( tmp[a] > k )
						add_mod( g[a+1][b+1][0], g[a][b][0] );
					add_mod( g[a+1][b][0], g[a][b][0] );
					add_mod( g[a+1][b][0], g[a][b][1] );
					add_mod( g[a+1][b+1][1], g[a][b][0] );
					add_mod( g[a+1][b+1][1], g[a][b][1] );
				}
			int last = tmp[tn-1] + k <= n;
			for( int j = 0; j <= tn; ++j ) {
				tmp[j] = g[tn][j][0];
				if( last )
					add_mod( tmp[j], g[tn][j][1] );
			}
			mul(f, fn, tmp, tn), fn += tn;
		}
}

int fac[N];
void solve2() {
	fac[0] = 1;
	for( int i = 1; i <= n; ++i )
		fac[i] = int(1LL * fac[i-1] * i % MOD);
	for( int i = 0; i <= n; ++i )
		f[i] = int(1LL * f[i] * fac[n-i] % MOD);
	int ans = 0;
	for( int i = 0; i <= n; ++i )
		if( i & 1 ) {
			ans = (ans - f[i] + MOD) % MOD;
		} else {
			ans = (ans + f[i]) % MOD;
		}
	cout << ans << endl;
}

int main() {
	cin >> n >> k;
	solve1(), solve2();
	return 0;
}


Measured memory_bytes: 16128
#include <iostream>
using namespace std;
int main () {
  int r, c;
  cin >> r >> c;

  int **a = new int *[r+1];
  for (int i = 0; i <= r; i++) {
    a[i] = new int[c+1];
  }
  for (int i=0; i< r; i++) {
    for (int j = 0; j < c; j++) {
      cin >> a[i][j];
      a[i][c] = 0;
      a[r][j] = 0;
    }
  }

  for (int i=0; i<r; i++) {
    for (int j=0; j<c; j++) {
      cout << a[i][j] << " ";
      a[i][c] += a[i][j];
      a[r][j] += a[i][j];
    }
    cout << a[i][c];
    cout << endl;
  }
  for (int j=0; j<c; j++) {
    cout << a[r][j] << " ";
    a[r][c] += a[r][j];
  }
  cout << a[r][c] << endl;
  delete [] a;
  return 0;
}

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

int main(int argc, char const *argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int a,b;
	cin>>a>>b;
	if (a==b) {
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}
	return 0;
}

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

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


    int n ; cin >> n ;

    string s; cin >> s;

    int res = 0 ;

    for(int i = 0 ; i < n - 2 ; i++){
       if(s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') res ++ ;
    }

    cout << res << endl ;


    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass
{
    static void Main()
    {
        var abcd = ReadLine().Split().Select(long.Parse).ToArray();
        var a = abcd[0]-1;
        var b = abcd[1];
        var c = abcd[2];
        var d = abcd[3];
        var lcm = LCM(c, d);
        WriteLine(b-a -(b/c - a/c + b/d - a/d - (b/lcm-a/lcm)));
    }
    static long Gcd(long a,long b)
    {
        return b == 0 ? a : Gcd(b, a % b);
    }
    static long LCM(long a, long b)
        => a / Gcd(a, b) * b;
}


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

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    const ll m = 1e9;
    ll S; cin >> S;
    ll x2 = (m - (S % m))%m;
    ll y2 = (S+x2)/m;
    assert(m*y2-x2 == S);
    cout << 0 << ' ' << 0 << ' ' << x2 << ' ' << y2 << ' ' << m << ' ' << 1 << '\n';

}



Measured memory_bytes: 256
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <complex>

#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,n) for(int i=0;i<(n); i++)

using namespace std;
typedef long long ll;
const int MAX_N = 110;
const int MAX_V = 100100;
const ll INF = 1LL<<62;

ll dp[MAX_N][MAX_V];
int main(){
cin.tie(0);
ios::sync_with_stdio(0); //この2行はより速度を向上させる
// 追加２, 以降 cin の入力元が 'input.txt' になる
//提出時に消す！！
//std::ifstream in("sample.txt");
//std::cin.rdbuf(in.rdbuf());

int N,W;
cin >> N >> W;

vector<ll> w(N),v(N);
rep(i,N) cin >> w[i] >> v[i];

rep(i,MAX_N){
    rep(j,MAX_V){
        dp[i][j]=INF;
    }
}
dp[0][0] = 0;
rep(i,N){
    rep(j,MAX_V){
        if(j-v[i] >= 0){
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]]+w[i]);
        }
        dp[i+1][j] = min(dp[i+1][j],dp[i][j]);
    }
}
ll ans = 0;
rep(i,MAX_V){
    if(dp[N][i] <= W){
        ans = i;
    }
}
cout << ans << endl;

return 0;
}


Measured memory_bytes: 86272
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int a[110];
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=='-'?o=-1:0,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return o*x;
}
int main() {
    int n,x,ans=0;
    cin>>n>>x;
    for(int i=1;i<=n;i++) a[i]=gi();
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
	if(a[i]<=x) x-=a[i],++ans;
    if(ans==n&&x) --ans;
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = sorted(list(map(int,input().split())))
sum = 0
List_sum = []
Counter = []
Count_num = (a[-1] - a[0])+1
for i in range(Count_num):
    Counter.append(a[0]+i)
    if Counter[-1] == a[-1]:
        break
if len(set(a)) == 1:
    print(0)
else:
    for i in Counter:
        for j in a:
            sum += (i-j)**2
        else:
            List_sum.append(sum)
            sum = 0
    else:
        print(min(List_sum))

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

using namespace std;

#define max(a,b) (a>b? a:b)
#define min(a,b) (a<b? a:b)
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define ONLINE_JUDGE

#pragma GCC Optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment (linker,"/stack:200000000")

typedef long long ll;

bool Finish_read;

template<class T>inline void read(T &x){Finish_read=0;x=0;T f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}

const int Maxn=101;
int a[Maxn],n,m,x;

int main() {
#ifndef ONLINE_JUDGE
    FO(FileName)
#endif
    read(n),read(m),read(x);
    memset(a,0,sizeof(a));
    for(unsigned i=1,p;i<=m;++i)
        read(p),a[p]=1;
    a[n]=a[0]=a[x]=0;
    int ans1=0,ans2=0;
    for(unsigned i=0;i<=x;++i)
        ans1+=a[i];
    for(unsigned i=n;i>=x;--i)
        ans2+=a[i];
    writeln(min(ans1,ans2));
    return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    arc068c()
}

fun arc068c() {
    val x = readLine()!!.toLong()

    val answer = if (x <= 6) 1 else if (x <= 11) 2 else 1 + Math.ceil((x - 6).toDouble() / 5.5).toLong()

    println(answer)
}


Measured memory_bytes: 31776
w,h= map(int, raw_input().split())
p =[]
q = []
for i in xrange(w):
    t = input()
    p.append(t)

for i in xrange(h):
    t = input()
    q.append(t)
p =sorted(p,reverse=True)
q =sorted(q, reverse=True)
ac = p[:]
acq = q[:]
i = w-2
while i >=0:
    ac[i] += ac[i+1]
    i -=1
i = h - 2
while i >= 0:
    acq[i] += acq[i + 1]
    i -= 1
c = ac[0] + acq[0]
k = 0
# for i in xrange(h):
i = 0
while i < h:
    # for j in xrange(k,w):
        j = k
        # print i,j
        if j >= w:
            break
        if q[i] > p[j]:
            c += ac[j]
            i += 1
            # break
        else:
            c +=acq[i]
            k +=1
        # c += q[i]
print c

Measured memory_bytes: 15404
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int L = 1;
		int R = N;
		int ans = 0;
		for(int i = 0; i < M; i++) {
			int Li = sc.nextInt();
			int Ri = sc.nextInt();
			L = Math.max(L, Li);
			R = Math.min(R, Ri);
		}
		if(L <= R) {
			ans = R - L + 1;
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 65092
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int main() 
{
  int N; cin >> N;
  N *= 2;
  vector<int> L(N, 0);
  for(int i = 0; i < N; i++) cin >> L[i]; 
  sort(L.rbegin(), L.rend());
  
  int ingredients = 0;
  for(int i = 1; i < N; i+=2) {
    ingredients += L[i];
  }
  
  cout << ingredients << endl;
  
  return 0;
}

Measured memory_bytes: 3576
N = int(input())
cnt = []
def dfs(num):
    if num > N:
        return
    if str(num).count('3') >= 1 and str(num).count('5') >= 1 and str(num).count('7') >= 1:
        cnt.append(num)
    dfs(num * 10 + 3)
    dfs(num * 10 + 5)
    dfs(num * 10 + 7)
dfs(0)
print(len(cnt))


Measured memory_bytes: 3956
#include <iostream>
using namespace std;
int main(){
  string s;
  long long k;
  cin>>s>>k;
  long long n=s.size();
  if(s[0]!=s[n-1]){
    long long sum=0;
    for(int i=0;i<n;i++){
      long long cnt=1;
      while(i+1<n&&s[i]==s[i+1]){
        i++;
        cnt++;
      }
      sum+=cnt/2;
    }
    cout<<sum*k<<endl;
  }else{
    bool f=true;
    for(int i=0;i+1<n;i++){
      if(s[i]!=s[i+1]){
        f=false;
      }
    }
    if(f){
      cout<<n*k/2<<endl;
    }else{
      long long l=0;
      while(s[l]==s[l+1]){
        l++;
      }
      long long r=n-1;
      while(s[r]==s[r-1]){
        r--;
      }
      l++;
      r--;
      long long hoge=n-1-r+l;
      long long sum=0;
      sum+=l/2;
      sum+=(n-1-r)/2;
      while(l<=r){
        long long cnt=1;
        while(s[l]==s[l+1]){
          l++;
          cnt++;
        }
        l++;
        sum+=(cnt/2)*k;
      }
      sum+=(hoge/2)*(k-1);
      cout<<sum<<endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>


int main(){
	int N, m, sum;
	int i, j, counter;
	int sum_r, sum_rr;
	scanf("%d",&N);
	while(N != 0){
		if((N ==1)||(N==2)){
			printf("0\n");
			goto end;
		}
		sum = 0;
		counter = 0;
		m = N/2+1;
		for(i=1; i<=m; i++)
			sum += i;

		sum_r = sum;
		/*printf("m:%d sum:%d\n", m, sum);*/

		for(i=0; i<m; i++){
			sum_r -= i;
			if(sum_r == N){
				counter++;
				/*printf("iroop: %d\n", i);*/
				break;
			}
			if(sum_r < N)
				break;
		}
		sum_r += i--;
		sum_rr = sum_r;
		while(i >= 0){
			for(j=m; j>0; j--){
				sum_rr -= j;
				if(sum_rr == N){
					counter++;
					/*printf("jroop: %d %d\n", i, j);*/
					break;
				}
				if(sum_rr < N)
					break;
			}
			sum_r += i--;
			sum_rr = sum_r;
		}
		printf("%d\n", counter);
		end:
		scanf("%d", &N);
	}
	return 0;
}

Measured memory_bytes: 612
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <assert.h>
#include <numeric>

using namespace std;

#define ll long long
#define rep(i, n) for (i = 0; i < n; i++)

int main()
{
  int N, M;
  cin >> N >> M;
  for (int i = 1; i <= (M + 1) / 2; i++)
  {
    cout << i << " " << N - i + 1 << endl;
  }
  for (int i = 1; i <= M / 2; i++)
  {
    cout << M + 1 - i << " " << M + 1 + i << endl;
  }
}


Measured memory_bytes: 3672
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
#define EPS 1e-10
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main() {
    int p, q;
    while (cin >> p >> q && p){
        vector<string> s(p);
        REP(i,p) cin >> s[i];
        VI ro(p), co(p), so(p), indent(p);
        REP(i,p){
            while (s[i][indent[i]] == '.') indent[i]++;
            if (i < p-1){
                ro[i+1] = ro[i];
                co[i+1] = co[i];
                so[i+1] = so[i];
                REP(j,s[i].length()){
                    if (s[i][j] == '(') ro[i+1]++;
                    if (s[i][j] == ')') ro[i+1]--;
                    if (s[i][j] == '{') co[i+1]++;
                    if (s[i][j] == '}') co[i+1]--;
                    if (s[i][j] == '[') so[i+1]++;
                    if (s[i][j] == ']') so[i+1]--;
                }
            }
        }

        vector<string> t(q);
        REP(i,q) cin >> t[i];
        VI rn(q), cn(q), sn(q);
        REP(i,q){
            if (i < q-1){
                rn[i+1] = rn[i];
                cn[i+1] = cn[i];
                sn[i+1] = sn[i];
                REP(j,t[i].length()){
                    if (t[i][j] == '(') rn[i+1]++;
                    if (t[i][j] == ')') rn[i+1]--;
                    if (t[i][j] == '{') cn[i+1]++;
                    if (t[i][j] == '}') cn[i+1]--;
                    if (t[i][j] == '[') sn[i+1]++;
                    if (t[i][j] == ']') sn[i+1]--;
                }
            }
        }

        VI ans(q,-1);
        FOR(r,1,20) FOR(c,1,20) FOR(s,1,20) {
            bool f = 1;
            REP(i,p){
                if (r*ro[i] + c*co[i] + s*so[i] != indent[i]) f = 0;
            }
            if (!f) continue;
            REP(i,q){
                int x = r*rn[i] + c*cn[i] + s*sn[i];
                if (ans[i] == -2) continue;
                if (ans[i] == -1) ans[i] = x;
                if (ans[i] >= 0 && ans[i] != x) ans[i] = -2;
            }
        }
        REP(i,q){
            if (ans[i] < 0) cout << -1;
            else cout << ans[i];
            if (i < q-1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 3156
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << "\n";
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    string s;
    cin >> s;

    vector<bool> v(26, false);
    REP(i, s.size()) v[s[i] - 'a'] = true;

    REP(i, 26) {
        if(!v[i]) {
            print(char('a' + i));
            return 0;
        }
    }

    print("None");
    
}


Measured memory_bytes: 3748
#include <stdio.h>

main(){
  int m, n, i, count;
  char s[1000005];
  int t[1000005];

  while(1){
    scanf("%d", &n);
    if(n==0) break;
    getchar();

    scanf("%d", &m);
    getchar();

    scanf("%s", s);

    t[0]=t[1]=0;

    for(i=2;i<m;i++){
      if(s[i]=='I'){
	if(s[i-1]=='O' && s[i-2]=='I') t[i]=t[i-2]+1;
	else t[i]=0;
      }
      else t[i]=0;
    }

    count=0;

    for(i=0;i<m;i++){
      if(t[i]>=n) count++;
    }

    printf("%d\n", count);
  }
  return 0;
}

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

using namespace std;
using ll  = long long;
using ii  = pair < int , int >;
using i3  = pair < int , ii >;
using vi  = vector < int >;
using vii = vector < ii >;
using vi3 = vector < i3 >;

const int N = 2e5 + 5;
const ll INF = 1e12;
const double eps = 1e-9 , PI = acos(-1);

int n , m;

void solve(){
    scanf("%d" , &n);
    printf("%d\n" , 3*(n*n));

}

main(){
    int t = 1;
    //scanf("%d" , &t);

    while( t -- ){
            solve();
    }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
int main()
{
    int n,f[200005]= {0};
    cin>>n;
        for (int i=1; i<=n; ++i)
            cin>>f[i];
    if (n%2==0)
    {
        for (int i=n; i>=2; i-=2)
            cout<<f[i]<<" ";
        for (int i=1; i<=n-1; i+=2)
            cout<<f[i]<<" ";
    }
    else
    {
        for (int i=n; i>=1; i-=2)
            cout<<f[i]<<" ";
        for (int i=2; i<=n-1; i+=2)
            cout<<f[i]<<" ";
    }
}


Measured memory_bytes: 2944
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define SZ(x) ((int)x.size()-1)
#define ms(a,b) memset(a,b,sizeof a)
#define F(i,a,b) for (int i=(a);i<=(b);++i)
#define DF(i,a,b) for (int i=(a);i>=(b);--i)
using namespace std;
inline int read(){
	char ch=getchar(); int w=1,c=0;
	for(;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;
	for(;isdigit(ch);ch=getchar()) c=(c<<1)+(c<<3)+(ch^48);
	return w*c;
}
char ch[100];
int main(){
	scanf("%s",ch+1);
	F(i,1,3) cout<<ch[i];
	return 0;
}




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

const ll m = 1e9 + 7;
ll powmod(ll b, ll p, ll m) {
  if (p == 0)
    return 1;
  if (p % 2 == 1)
    return b * powmod(b, p - 1, m) % m;
  else {
    ll t = powmod(b, p / 2, m);
    return t * t % m;
  }
}

int main() {
  int n;
  cin >> n;
  vector<int> diff(n, 0);
  bool valid = 1;

  for (int i = 0; i < n; i++) {
    int temp;
    cin >> temp;
    diff[temp] += 1;
  }

  for (int i = (n % 2 == 0); i < n; i += 2) {
    if (diff[i] != (1 + (i > 0))) {
      valid = 0;
      break;
    }
  }

  if (valid)
    cout << powmod(2, n / 2, m) << endl;
  else
    cout << 0 << endl;
}


Measured memory_bytes: 640
class Line
  attr_accessor :h,:p,:q
  def initialize(h,p,q)
    @h=h
    @p=p
    @q=q
  end
end

loop do
  n,m,a = gets.split.map(&:to_i)
  break if(n|m|a)==0
  ls =[]
  m.times do
    h,p,q = gets.split.map(&:to_i)
    ls << Line.new(h,p,q)
  end
  ls.sort!{|b,c|c.h-b.h}
  ls.each do |line|
    p = line.p
    q = line.q
    if a==p
      a=q
    elsif a==q
      a=p
    end
  end
  p a
end

Measured memory_bytes: 3124
#include <cstdio>
#include <cstdlib>
#include <string>

using namespace std;

string s[100'009];

int main() {
  int n;
  scanf("%d", &n);
  int qt = 0;
  for (int i = 1; i <= 9; ++i) {
    s[qt] = "";
    s[qt] += (char)('0' + i);
    ++qt;
  }
  for (int qh = 0; qh < qt && qt < n; ++qh) {
    int d = (int)(s[qh].back() - '0');
    for (int nd = 0; nd <= 9; ++nd) {
      if (abs(d - nd) > 1) {
        continue;
      }
      s[qt] = s[qh];
      s[qt] += (char)('0' + nd);
      ++qt;
      if (qt == n) {
        break;
      }
    }
  }
  puts(s[n - 1].c_str());
}


Measured memory_bytes: 6912
object Main extends App {
  val amount = Array(500,100,50)
  val in = Iterator.continually(io.StdIn.readLine.toInt)
    .take(4).toArray

  val ans =  for {
    i <- 0 to in(0)
    j <- 0 to in(1)
    k <- 0 to in(2)
    if amount(0)*i + amount(1)*j + amount(2)*k == in(3)
    } yield  true

  println(ans.size)
}

Measured memory_bytes: 29676