akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<string.h>
int N;
int parent[100002];
int sibling[100002];
int degree[100002];
 
int Depth(int i) {
  if(parent[i] == -1) return 0;
  return Depth(parent[i]) + 1;
}
  
int Height(int i) {
  int j, x, y;
 
  x = 0;
 
  for(j = 0; j < N; j++) {
    if(parent[j] == i) {
      y = Height(j) + 1;
      if(y > x) x = y;
    }
  }
 
  return x;
}
 
int main() {
  int i, j, depth;
  int id, left, right;
 
  scanf("%d", &N);
  for(i = 0; i < N; i++) {
    parent[i] = -1;
    sibling[i] = -1;
    degree[i] = 0;
  }
  for(i = 0; i < N; i++) {
    scanf("%d %d %d", &id, &left, &right);
 
    if(left != -1) {
      parent[left] = id;
      sibling[left] = right;
      degree[id]++;
    }
 
    if(right != -1) {
      parent[right] = id;
      sibling[right] = left;
      degree[id]++;
    }
  }
   
  for(i = 0; i < N; i++) {
    depth = Depth(i);
 
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ", i, parent[i], sibling[i], degree[i], depth, Height(i));
 
    if(depth == 0) {
      printf("root\n");
    }
 
    else if(degree[i] == 0) {
      printf("leaf\n");
    }
 
    else {
      printf("internal node\n");
    }
  }
 
  return 0;
}

Measured memory_bytes: 620
# include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
# define pb push_back
# define pii pair < int, int >
# define F first
# define S second
# pragma GCC optimize("unroll-loops")
# pragma GCC optimize("Ofast")
# define int long long int
# define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N=2e5+100,inf=1e15,mod=998244353 ;

ll a[N];
ll par[N];
ll f[N];
int32_t main(){
    ll n,m;
    cin >> n >> m;
    string s;
    cin >> s;
    reverse(s.begin(),s.end());
    for (int i=0;i<s.size();i++){
        if (i==0){
            par[i]=s[i]-'0';
        }
        else{
            par[i]=par[i-1]+s[i]-'0';
        }
    }
    vector <int> ans;
    ll cnt=0;
    if (s[0]=='1' || s[n]=='1'){
        cout << -1;
        return 0;
    }
    while(cnt!=n){
        ll z=min(n,cnt+m);
        while(z>cnt && s[z]=='1'){
            z--;
        }
        if (z==cnt){
            cout << -1;
            return 0;
        }
        ans.pb(z-cnt);
        cnt=z;
    }
    reverse(ans.begin(),ans.end());
    for (int i=0;i<ans.size();i++){
        cout << ans[i] << " ";
    }
}


Measured memory_bytes: 4088
#include <stdio.h>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>

#define MOD_ANS 1000000000 + 7
#define MOD 13

template <typename T, size_t N>class _S {

private:
	void SW(T& a, T& b) {
		T t = std::move(a);
		a = std::move(b);
		b = std::move(t);
	}

public:
	void SMAP(T(&a)[N], T(&b)[N]) {
		for (std::size_t i = 0; i < N; ++i) {
			SW(a[i], b[i]);
		}
	}
};
int main() {


	std::string s;
	std::cin >> s;
	std::vector<int> av(MOD), pre(MOD);
	pre[0] = 1;

	for (auto& c : s) {

		std::fill(av.begin(), av.end(), 0);

		if (c == '?')for (int i = 0; i < MOD; ++i)for (unsigned long j = 0; j < 10; ++j)(av[(i * 10 + j) % MOD] += pre[i]) %= MOD_ANS;
		else for (int i = 0; i < MOD; ++i)(av[(i * 10 + c + 4) % MOD] += pre[i]) %= MOD_ANS;

		std::swap(av, pre);
	}

	std::cout << pre[5] << std::endl;

	return 0;
}

Measured memory_bytes: 512
n,m=map(int,input().split())
stu=[]
chk=[]
for i in range(n):
    tmp,tmp1=map(int,input().split())
    stu.append([tmp,tmp1])
for i in range(m):
    tmp,tmp1=map(int,input().split())
    chk.append([tmp,tmp1])
for student in stu:
    dist = [abs(j[0]-student[0])+abs(j[1]-student[1]) for j in chk]
    print(dist.index(min(dist))+1)

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

int main() {
  int N, K;
  scanf("%d%d", &N, &K);

  int ans = 0;
  for (int i = 0; i < N; i++) {
    int height = 0;
    scanf("%d", &height);
    if (height >= K) ans++;
  }

  printf("%d", ans);
  return 0;
}


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

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

int main() {
    ll a,b,x;
    cin >> a >> b >> x;
    if(a==0) cout << b/x +1 << endl;
    else cout << b/x - (a-1)/x << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(void){
    long long s;
    cin>>s;
    long long a,b,c,d;
    if(s<=1000000000) cout<<s<<" 0 0 1 0 0"<<endl;
    else if(s==1000000000000000000) cout<<1000000000<<" 0 0 1000000000 0 0"<<endl;
    else{
        a=s/1000000000;
        b=s%1000000000;
        cout<<a+1<<" "<<1000000000-b<<" "<<1<<" "<<1000000000<<" 0 0"<<endl;
    }
}


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

int main()
{
    char a[4];
    while(cin>>a)
    {
        int a1=a[0]-'0';
        int a2=a[1]-'0';
        int a3=a[2]-'0';
        int a4=a[3]-'0';
        if(a1+a2+a3+a4==7)
            printf("%d+%d+%d+%d=7\n",a1,a2,a3,a4);
        else if(a1-a2+a3+a4==7)
            printf("%d-%d+%d+%d=7\n",a1,a2,a3,a4);
        else if(a1+a2-a3+a4==7)
            printf("%d+%d-%d+%d=7\n",a1,a2,a3,a4);
        else if(a1+a2+a3-a4==7)
            printf("%d+%d+%d-%d=7\n",a1,a2,a3,a4);
        else if(a1-a2-a3+a4==7)
            printf("%d-%d-%d+%d=7\n",a1,a2,a3,a4);
        else if(a1-a2-a3-a4==7)
            printf("%d-%d-%d-%d=7\n",a1,a2,a3,a4);
        else if(a1-a2+a3-a4==7)
            printf("%d-%d+%d-%d=7\n",a1,a2,a3,a4);
        else if(a1+a2-a3-a4==7)
            printf("%d+%d-%d-%d=7\n",a1,a2,a3,a4);


    }
}


Measured memory_bytes: 256
//abc062_a.cpp
//Sat Oct 20 22:07:22 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int n,m;
	cin >> n >> m;

	if (n==1 || n==3 || n==5 || n==7 || n==8 || n==10 || n==12){
		n = 100;
	}else if (n==2){
		n = 102;
	}else {
		n = 101;
	}

	if (m==1 || m==3 || m==5 || m==7 || m==8 || m==10 || m==12){
		m = 100;
	}else if (m==2){
		m = 102;
	}else {
		m = 101;
	}

	if (n == m){
		cout << "Yes" << endl;
	}else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
n,A,B,C=map(int,input().split())
l=[int(input()) for i in range(n)]
INF=10**9

def dfs(cur,a,b,c):
  if cur==n:
    return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c)>0 else INF
  else:
    ret0=dfs(cur+1,a,b,c)
    ret1=dfs(cur+1,a+l[cur],b,c)+10
    ret2=dfs(cur+1,a,b+l[cur],c)+10
    ret3=dfs(cur+1,a,b,c+l[cur])+10
    return min(ret0,ret1,ret2,ret3)

print(dfs(0,0,0,0))

Measured memory_bytes: 3064
s = int(input())
n = []
for i in range(s):
    n.append(input())
a = n.count('AC')
b = n.count('WA')
c = n.count('TLE')
d = n.count('RE')
   
A = str(a)
B = str(b)
C = str(c)
D = str(d)
        
AC = 'AC x ' + A
WA = 'WA x ' + B
TLE = 'TLE x ' + C
RE = 'RE x ' + D

print(AC)
print(WA)
print(TLE)
print(RE)

Measured memory_bytes: 16184
;;;; queue
(defstruct queue
  (entrance nil)
  (exit nil))

(defun enqueue (item queue)
  (let ((cell (list item)))
    (if (queue-entrance queue)
        (setf (cdr (queue-entrance queue)) cell)
        (setf (queue-exit queue) cell))
    (setf (queue-entrance queue) cell)))

(defun dequeue (queue)
  (when (queue-exit queue)
    (prog1 (pop (queue-exit queue))
      (unless (queue-exit queue)
        (setf (queue-entrance queue) nil)))))

;;;; main
(let* ((n (read))
       (q (read))
       (e (make-array (list (1+ n)) :initial-element nil))
       (chk (make-array (list (1+ n)) :initial-element nil))
       (ans (make-array (list (1+ n)) :initial-element 0)))
  (loop :for i :from 1 :to (1- n)
        :for a := (read)
        :for b := (read)
        :do (push b (aref e a))
        :do (push a (aref e b)))
  (loop :for j :from 1 :to q
        :for p := (read)
        :for x := (read)
        :do (incf (aref ans p) x))
  ;
  (let ((q (make-queue)))
    (enqueue 1 q)
    (loop :while (queue-exit q)
          :for x := (dequeue q)
          :do (unless (aref chk x)
                (setf (aref chk x) t)
                (loop :for y :in (aref e x)
                      :do (unless (aref chk y)
                            (incf (aref ans y) (aref ans x))
                            (enqueue y q))))))
  (loop :for i :from 1 :to (1- n)
        :do (format t "~A " (aref ans i)))
  (format t "~A~%" (aref ans n)))


Measured memory_bytes: 89524
#include <bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(), (v).end()

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

  int max_a = -1, min_a = 1<<30;
  map<int, int> mp;
  for (int i = 0; i < N; ++i) {
    int a; cin >> a;
    mp[a]++;
    max_a = max(max_a, a);
    min_a = min(min_a, a);
  }

  int ans = -1;
  for (int i = min_a; i <= max_a; ++i) {
    ans = max(ans, mp[i]+mp[i+1]+mp[i+2]);
  }

  cout << ans << endl;
}

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

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

    int ans=0;
    rep(i,n){
        int cnt=0;

        for(char c='a';c<='z';c++){
            bool left=false,right=false;

            rep(j,i) if(s[j]==c) left=true;
            
            for(int j=i; j<n; j++) if(s[j]==c) right=true;

            if(left && right) cnt++;
        }

        if(ans<cnt) ans=cnt;
    }

    cout << ans << endl;
    
}


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

#define pi 3.141592653589
#define repeat(i,n) for(int i=0;i<n;i++)

int main(){
	int n, x;
	
	
	while (cin >> n >> x)
	{
		int cnt = 0;
		if (n == 0 && x == 0) break;
		for (int i = 1; i <= n - 2; i++)
		{
			for (int j = i + 1; j <= n - 1; j++)
			{
				for (int k = j + 1; k <= n; k++)
				{
					if (i + j + k == x) cnt++;
				}
			}
		}
		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int main() {
    int N,K;
    cin >> N >> K;
    
    ll ans = 0;
    for(int b=K+1;b<=N;++b){
        ans += ((b-K)*(N/b));
        if(N%b >= K) ans+=(N%b - K + 1);
    }
    if(K==0) ans-=N;
    cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
x = input()

memo = [-1] * (n+10)
def calc(x):
    if(memo[x] != -1):
        return memo[x]
    if(x==0):
        return 0
    cnt = 0
    x2 = x
    while(x2 > 0):
        cnt += (x2&1)
        x2 //= 2
    next = x%cnt
    memo[x] = 1 + calc(next)
    return memo[x]

cnt0 = x.count('1')
if(cnt0 == 0):
    ans = [1] * n
    print('\n'.join(map(str,ans)))
    exit()
if(cnt0==1):
    ans = [0] * n
    for i in range(n):
        ans1 = 1 + ( x[-1] == '1')
        if(x[i]=='0'):
            if(i==n-1):
                ans[i] = 2
            else:
                ans[i] = ans1
        else:
            ans[i] = 0
    print('\n'.join(map(str,ans)))
    exit()

rem_p = [0] * n
rem_m = [0] * n
rem_p[0] = 1
rem_m[0] = 1%(cnt0-1)

for i in range(1,n):
    rem_p[i] = (2*rem_p[i-1])%(cnt0+1)
    rem_m[i] = (2*rem_m[i-1])%(cnt0-1)

x_p = 0
x_m = 0
for i in range(n):
    if(x[n-1-i] == '1'):
        x_p += rem_p[i]
        x_m += rem_m[i]
x_p %= (cnt0+1)
x_m %= (cnt0-1)

ans = [0] * n
for i in range(n):
    if(x[i]=='1'):
        first = (x_m - rem_m[n-1-i])%(cnt0-1)
        ans[i] = calc(first) + 1
    else:
        first = (x_p + rem_p[n-1-i])%(cnt0+1)
        ans[i] = calc(first) + 1

print('\n'.join(map(str,ans)))

Measured memory_bytes: 102028
while True:
    h,w = map(int, input().split())
    
    if h == 0 and w == 0:
        break
    for i in range(h):
        if i == 0 or i == h-1:
            print('#' * w)
        else:
             print('#'+'.'*(w-2)+'#')
    print() 


Measured memory_bytes: 5612
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<string>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<climits>
using namespace std;
#define REP(i, j) for(int i = 0; i < j; i++)
#define FOR(i, j, k) for(int i = k; i < j; i++)
#define P pair<int, int>
const int INF = INT_MAX / 2;

int main(){
    int n;
    while(cin >>n && n){
        string str; cin >>str;
        stringstream ss;
        REP(i, n){
            int cnt = 1, s = str.size();
            char bef = str[0];
            FOR(j, s, 1){
                if(bef == str[j]) cnt += 1;
                else{
                    ss <<cnt <<bef;
                    cnt = 1;
                    bef = str[j];
                }
            }
            ss <<cnt <<bef;
            str = ss.str();
            ss.str("");
        }
        cout <<str <<endl;
    }
    return 0;
}

Measured memory_bytes: 1376
s = input()
n = len(s)

def dfs(i, f):
    if i == n - 1:
        return sum(list(map(int, f.split("+"))))

    return dfs(i + 1, f + s[i + 1]) + dfs(i + 1, f + "+" + s[i + 1])
    
print(dfs(0, s[0]))

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

int main()
{
	int N = 0, K = 0, X = 0, Y = 0,T=0;
	cin >> N >> K >> X >> Y;
	for (int i = 0; i <N; i++)
	{
		if (i >= K)
		{
			T = T + Y;
		}
		else
		{
			T = T + X;
		}
	}
	cout << T;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>

using namespace std;

const int MAX = 21;
const int INF = (1<<25);

int in;
int data[MAX];
int mindif;

void dfs(int i, int sum){
  if(i==in){
    mindif = min(mindif,abs(sum));
    return;
  }
  dfs(i+1,sum+data[i]);
  dfs(i+1,sum-data[i]);
}

int main(){
  while(cin >> in && in){
    for(int i = 0; i < in; i++) cin >> data[i];
    mindif = INF;
    dfs(0,0);
    cout << mindif << endl;
  }
  return 0;
}

Measured memory_bytes: 864
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<math.h>
#include<stdlib.h>
using namespace std;
//#define int long long
typedef pair<int, int> pii;
typedef pair<int, pii > piii;
typedef pair<double, double> pdd;
typedef pair<int, char> pic;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define mk make_pair
#define INF (1 << 30)
#define INFL (1ll << 60ll)
#define mod 1000000007

int N, M;
int K[111];
int s[111][111];
int p[111];

signed main(){
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        cin >> K[i];
        for(int j = 0; j < K[i]; j++){
            cin >> s[i][j];
            s[i][j]--;
        }
    }
    for(int i = 0; i < M; i++){
        cin >> p[i];
    }
    int ans = 0;
    for(int bit = 0; bit < (1 << N); bit++){
        bool flag = true;
        for(int i = 0; i < M; i++){
            int cnt = 0;
            for(int j = 0; j < K[i]; j++){
                if(bit & (1 << s[i][j])){
                    cnt++;
                }
            }
            if(cnt % 2 != p[i])flag = false;
        }
        if(flag)ans++;
    }
    cout << ans << endl;


    return 0;
}

/*

*/

Measured memory_bytes: 256
MOD = 10**9+7
MAXN = 5*(10**5)+5
fact = [1]
ifact = [1]
for i in range(MAXN):
    fact.append(fact[-1] * (i+1) % MOD)
    ifact.append(pow(fact[-1], MOD-2, MOD))
def nCr(n, r):
    return fact[n] * ifact[r] * ifact[n-r] % MOD

def nPr(n, r):
    return fact[n] * ifact[n-r] % MOD

n, m = map(int, input().split())
ans = 0
for k in range(n+1):
    # tmp = pow(nPr(m-k, n-k), 2, MOD) * nPr(m, k) * nCr(n,k) % MOD
    # tmp = nPr(m-k, n-k) * nPr(m, n) * nCr(n,k) % MOD
    tmp = nPr(m-k, n-k) * nCr(n,k) % MOD
    if k%2:
        ans -= tmp
    else:
        ans += tmp
ans = (ans * nPr(m, n) + MOD) % MOD
print(ans)


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

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

  if ((a == 7 && b == 5 && c == 5) || (a == 5 && b == 7 && c == 5) || (a == 5 && b == 5 && c == 7)) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

  return 0;
}

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


int main() {
	string s;
	cin >> s;
	int q; cin >> q;
	string t;
	rep(i, q) {
		int ti; cin >> ti;
		if (ti == 1) {
			swap(s, t);
		}
		else {
			int f; cin >> f;
			string c; cin >> c;
			if (f == 1) {
				t += c;
			}
			else {
				s += c;
			}
		}
	}
	reverse(t.begin(), t.end());
	cout << t + s << endl;
	return 0;
}



Measured memory_bytes: 1312
// warm heart, wagging tail,and a smile just for you!
//
//                            ▒█████▒▒
//                             ██████████▒
//                             ▒████████████▒
//                            ██████████████████
//                           ████████████████████▒
//                          ▒██████████████████████▒
//                          ▒███████████████████████
//                      ▒████▒▒▒▒▒▒█████████████████▒
//                    ███▒▒▒▒▒▒██████████████████████▒▒▒
//                  ▒██▒▒███████████████████████▒▒▒▒▒██████
//                 ▒█████████████████████████▒▒▒▒▒▒█████████▒
//                 ▒█████████████████████▒▒▒▒▒▒██████████████
//                  ▒████         ████▒▒▒▒▒████         ████▒
//              ▒█████▒    ████    ▒▒▒▒███████    ████    ██████▒
//            ▒██▒▒▒▒▒    ██████    █████████    ██████    ██▒▒▒██▒
//           █████████   ████████   █████████   ████████   ▒▒▒▒█████
//          ▒█████████    ██████    ████████▒    ██████    █████████
//          ▒██████████    ████    █████▒▒▒▒▒▒    ████    ██████████
//           ████████████        ▒▒▒▒▒▒▒████████        ███████████▒
//       ▒██████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒███████████████████████████████████▒
//     ███▒▒▒▒▒▒▒▒▒▒▒▒█████████████████████████████████████████▒▒████████▒
//   ▒▒▒▒▒▒▒▒▒██████████████                         ███████▒▒▒▒███████████
//   █████████████████████████                     ███████▒▒▒██████████████▒
//   █████████████████████████████             ███████▒▒▒██████████████████▒
//   ██████████████████████████████████████████████████████████████████████
//    ██████████████████████████████████████████████████████████████████▒
//      ▒█████████████████▒▒▒▒▒▒▒██████████████████████████████████▒▒▒
//
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

mat ans(550,vec(550,-1));

void solve(int l, int r, int lev){
  int mid = (l+r)/2;
  //cout << l SP r << endl;
  if(r-l <= 1) return;
  FOR(i,l,mid){
    REP(j,r-mid) ans[i][j+mid] = ans[j+mid][i] = lev;
  }
  solve(l,mid,lev+1);
  solve(mid,r,lev+1);
  return;
}

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

  int n;
  cin >> n;

  solve(0,n,1);

  REP(i,n-1){
    FOR(j,i+1,n) cout << ans[i][j] << " ";
    cout << endl;
  }

  // REP(i,10){
  // REP(j,10){ cout << ans[i][j] <<" ";} cout << endl;}

  return 0;
}

Measured memory_bytes: 2944
import sys
def side(p1,p2):
  global D
  y1,x1=p1
  y2,x2=p2
  dy=y2-y1
  dx=x2-x1
  for p3 in D[::-1]:
    y3,x3=p3
    if p1==p3 or p2==p3:continue
    if (x3-x1)*dy-dx*(y3-y1)<0:return 0
  else:return 1

while 1:
  n=input()
  if n==0:break
  D=sorted([list(input()) for i in range(n)])
  p=p1=D[0]
  D1=D[:]
  while True:
    for p2 in D1:
      if p1!=p2 and side(p1,p2):break
    p1=p2
    D1.remove(p2)
    if p2==p:break
  print len(D1)

Measured memory_bytes: 4276
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int a[3], l[10];

const int INF = (int) 1e9;

int dfs(int i, int sa, int sb, int sc) {
    if (i == n) {
        if (sa == 0 || sb == 0 || sc == 0) return INF;
        return abs(sa - a[0]) + abs(sb - a[1]) + abs(sc - a[2]);
    }

    int ret = dfs(i + 1, sa, sb, sc);
    int ret1 = dfs(i + 1, sa + l[i+1], sb, sc) + (sa > 0?10:0);
    int ret2 = dfs(i + 1, sa, sb + l[i+1], sc) + (sb > 0?10:0);
    int ret3 = dfs(i + 1, sa, sb, sc + l[i+1]) + (sc > 0?10:0);

    ret = min(ret, ret1);
    ret = min(ret, min(ret2, ret3));

    return ret;
}

int main() {
    cin >> n >> a[0] >> a[1] >> a[2];
    for (int i = 0; i < n; ++i) {
        cin >> l[i];
    }

    int ans = dfs(-1, 0, 0, 0);

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define long long ll
#define maxn  200015

int head[maxn*2];
int ans[maxn*2];

struct edge
{
	int up;
	int to;
	int dis;
}t[maxn*2];

int tot=0;
inline void join(int from,int to)
{
	tot++;
	t[tot].up = head[from]; 	//父节点
	t[tot].to = to;	//开子节点
	head[from] = tot; 
}

bool vis[maxn*2];
void dfs(int idx)
{
	vis[idx] = 1;
	for (int i = head[idx];~i;i = t[i].up)
	{
		int y = t[i].to;
		if(!vis[y]) 
		{
			ans[y] += ans[idx];
			dfs(y);	
		}
	}
}

int main()
{
	int n,m;
	cin >> n >> m;
	memset(head,-1,sizeof(head));
	for (int i=1;i<=n-1;i++)
	{
		int x,y;
		cin >> x >> y;
		join(x,y);
		join(y,x); 
	}
	for (int i=1;i<=m;i++)
	{
		int x,y;
		cin >> x >> y;
		ans[x] += y;
	}
	dfs(1);
	for (int i=1;i<=n;i++)
	{
		cout << ans[i] << " ";
	}
	
	return 0;
}

Measured memory_bytes: 16640
import java.util.Scanner;

public class Main {

	static boolean[] passed;
	static int N;
	static int[][] adj;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		int M = sc.nextInt();
		adj = new int[N][N];
		passed = new boolean[N];

		int a, b;
		for (int i = 0; i < M; i++) {
			a = sc.nextInt() - 1;
			b = sc.nextInt() - 1;
			adj[a][b] = 1;
			adj[b][a] = 1;
		}

		passed[0] = true;
		System.out.println(dfs(0));
	}

	static int dfs(int node) {
		boolean allPassed = true;
		for(int i = 0; i < N; i++) {
			allPassed = allPassed && passed[i];
		}
		if(allPassed) {
			return 1;
		}

		int ret = 0;

		for(int i = 0; i < N; i++) {
			if(adj[node][i] < 1) continue;
			if(passed[i]) continue;

			passed[i] = true;
			ret += dfs(i);
			passed[i] = false;
		}

		return ret;
	}
}

Measured memory_bytes: 23252
#include <bits/stdc++.h>
#define REP(i, n) for (long long i = 0; i < (long long)n; i++)
//#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Vl = vector<ll>;
using vi = vector<int>;
using Graph = vector<vi>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll MOD = 1e9 + 7;
  ll N, K;
  cin >> N >> K;
  ll ans = 0;
  for (ll i = K; i <= N + 1; i++) {
    ll min = ((i - 1) * i) / 2;
    ll max = ((2 * N - i + 1) * i) / 2;
    ans += max - min + 1;
    ans = ans % MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3640
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;

int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    for(size_t i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int max_i = max_element(a.begin(), a.end()) - a.begin();
    ll max_elem = a[max_i];
    ll max_div2 = max_elem / 2;
    int ret = -1;
    ll min_diff_from_div2 = max_elem;
    for(int i = 0; i < n; i++)
    {
        if (i == max_i)
            continue;
        ll temp = abs(a[i] - max_div2);
        if (temp < min_diff_from_div2){
            ret = i;
            min_diff_from_div2 = temp;
        }
    }
    cout << max_elem << " " << a[ret] << endl;
    
    return 0;
}

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

int main(){
	int w,h, x,y ,r;
	cin >>w >> h >>  x >> y >> r;
	if(x-r>=0&&y-r>=0&&x+r<=w&&y+r<=h)cout << "Yes"<< endl;
	else cout << "No"<<endl;
	
	}

Measured memory_bytes: 1160
fn main() {
    let stdin = std::io::stdin();
    let (n, m) = {
        let mut buf = String::new();
        stdin.read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace().map(|x| x.parse::<usize>().unwrap());
        (iter.next().unwrap(), iter.next().unwrap())
    };
    let link = {
        let mut l = vec![vec![0; m]; n];
        for i in 0..m {
            let mut buf = String::new();
            stdin.read_line(&mut buf).unwrap();
            for s in buf
                .split_whitespace()
                .skip(1)
                .map(|x| x.parse::<usize>().unwrap())
            {
                l[s - 1][i] = 1;
            }
        }
        l
    };
    let p = {
        let mut buf = String::new();
        stdin.read_line(&mut buf).unwrap();
        buf.split_whitespace()
            .map(|x| x.parse::<usize>().unwrap())
            .collect::<Vec<usize>>()
    };
    let mut valid = 0;
    for switch in 0..(2u32).pow(n as u32) {
        let mut state = p.clone();
        for i in 0..n {
            if switch & (2u32).pow(i as u32) != 0 {
                for j in 0..m {
                    state[j] += link[i][j];
                }
            }
        }
        if state.iter().all(|x| x % 2 == 0) {
            valid += 1;
        }
        //println!("{:?}", state);
    }
    println!("{}", valid);
}


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

int main()
{
    int a = 0;
    string S, T;
    cin >> S >> T;
    for (int i = 0; i < S.size(); i++)
    {
        if(S.at(i)!=T.at(i))
        {
            a++;
        }
    }
    cout << a << endl;
}


Measured memory_bytes: 3808
k,n = map(int,input().split())
distance_list = list(map(int,list(input().split())))

distance_list.sort()

interval_list = []

a = 0
for i in  range(n):
    interval_list.append(distance_list[i] - a)
    a = distance_list[i]

b = k - distance_list[n-1]

interval_list[0] = interval_list[0] + b

interval_list.sort()

ans = 0
for i in range(n-1):
    ans = ans + interval_list[i]

print(ans)

Measured memory_bytes: 25836
h, w, k = map(int, input().split())
dp = [1] + [0] * (w - 1)
mod = 1000000007

def mul(a, b):
    newmatrix = [[0] * w for _ in range(w)]
    for i in range(w):
        for j in range(w):
            newmatrix[i][j] = sum(a[i][k] * b[k][j] for k in range(w)) % mod
    return newmatrix

matrix = [[0] * w for _ in range(w)]
for b in range(1 << (w - 1)):
    valid = True
    for i in range(w - 1):
        if (b >> i) & 3 == 3:
            valid = False
    if valid:
        for i in range(w):
            if (b >> i) & 1 != 0:
                matrix[i][i + 1] += 1
            elif i > 0 and (b >> (i - 1)) & 1 != 0:
                matrix[i][i - 1] += 1
            else:
                matrix[i][i] += 1

ret = [[1 if i == j else 0 for i in range(w)] for j in range(w)]
while h > 0:
    if h & 1 == 1:
        ret = mul(ret, matrix)
    matrix = mul(matrix, matrix)
    h //= 2

print(ret[0][k - 1])


Measured memory_bytes: 39280
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
    cin >> s;
    for(int i = 0 ; i < (int)s.size() - 1 ; i++){
        if(s[i] == 'A' && s[i + 1] == 'C'){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}

Measured memory_bytes: 256
N = int(input())
li = [input() for _ in range(N)]
ac = 0
wa = 0
tle = 0
re = 0
for i in range(N):
    if li[i] == 'AC':
        ac += 1
    if li[i] == 'WA':
        wa += 1
    if li[i] == 'TLE':
        tle += 1
    if li[i] == 'RE':
        re += 1
print("AC x " + str(ac))
print("WA x " + str(wa))
print("TLE x " + str(tle))
print("RE x " + str(re))

Measured memory_bytes: 16308
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);


ll comb(ll n,ll k){
    if(k<0 || n<k)return 0;
    if(k==0 || n==k)return 1;
    if(k==1)return n;
    if(k==2)return (n*(n-1))/2;
    return (n*(n-1)*(n-2))/6;
}

string s;
ll n;
ll memo[200][5];

ll hoge(ll i,ll x){
    if(memo[i][x]!=0)return memo[i][x];
    if(n-i<x)return memo[i][x]=0;
    string t;
    t=s[i];
    ll a=stoll(t);
    if(i==n-1){
        if(x==1){
            return memo[i][x]=a;
        }else{
            return memo[i][x]=0;
        }
    }
    if(a==0){
        return memo[i][x]=hoge(i+1,x);
    }else if(a==1){
        if(x==1){
            return memo[i][x]=1+comb(n-i-1,x)*pow(9,x);
        }
        return memo[i][x]=hoge(i+1,x-1)+comb(n-i-1,x)*pow(9,x);
    }else{
        if(x==1){
            memo[i][x]=comb(n-i-1,x-1)*pow(9,x-1)*(a-1)+comb(n-i-1,x)*pow(9,x)+1;
        }
        return memo[i][x]=comb(n-i-1,x-1)*pow(9,x-1)*(a-1)+comb(n-i-1,x)*pow(9,x)+hoge(i+1,x-1);
    }
}

int main(){
    cin>>s;
    ll k;cin>>k;
    n=s.size();
    ll ans=hoge(0,k);
    cout<<ans<<endl;
    
    return 0;
}



Measured memory_bytes: 256
//BISMILLAHHIR RAHMANIR RAHIM
#include<bits/stdc++.h>
using namespace std;
typedef long long int            ll;
typedef unsigned long long int   ull;
#define min3(a,b,c)              min(a,min(b,c))
#define F                        first
#define S                        second
#define PB                       push_back
#define MP                       make_pair
#define PI                       2*acos(0.0)
#define MOD                      998244353
int main()
{
    int ara[3],mn=1e6,sum=0;
    for(int i=0; i<3; i++)cin>>ara[i];
    for(int i=0; i<3-1; i++){
        for(int j=i+1; j<3; j++){
            sum+=ara[i]+ara[j];
            mn=min(mn,sum);
            sum=0;
        }
    }
    cout<<mn<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()

int main() {
    int r,g,b,n;
  cin>>r>>g>>b>>n;
  ll count=0;
  rep(i,n/r+1){
    rep(j,(n-r*i)/g+1){
      if((n-r*i-j*g)%b==0) count++;
    }
  }
  cout<<count<<endl;
return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int N;
        int K;
        int[] Hi = null;
        try (Scanner sc = new Scanner(System.in)) {
            N = sc.nextInt();
            K = sc.nextInt();
            Hi = new int[N];
            for (int i = 0; i < N; i++) {
                Hi[i] = sc.nextInt();
            }
        }
        Arrays.sort(Hi);
        if(K > 0){
            if(K > Hi.length){
                K = Hi.length;
            }
            Arrays.fill(Hi,Hi.length-K,Hi.length ,0);
        }
        long result = 0;
        for(int attack : Hi){
            result += attack;
        }
        System.out.println(result);
    }
}


Measured memory_bytes: 85208
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int gcd(int a,int b);
int compare(const void* a, const void* b);

int main(void){
    int N;
    int M;
    int add;
    int i,j,k,ret;
    long h;
    long H[100000];
    long Hr[100000];
    int start[100000];  //M番目の道の始点
    int end[100000];    //M番目の道の終点
    int result[100000];
    long max = 0;
    ret = 0;

    scanf("%d %d",&N,&M);
    //高さ入力
    for(i = 0 ; i < N; i++){
        scanf("%ld",&h);
        H[i] = h;                
        Hr[i] = h;
    }
    //ルート情報入力
    //見晴らしがよくない展望台はH=0にする
    for(i = 0 ; i < M ; i++){
        scanf("%d %d",&(start[i]),&(end[i]));
        start[i]--;
        end[i]--;        
        if( H[start[i]] < H[end[i]]){   // endのほうが大きい場合
            //startは見晴らしがよくない
            Hr[start[i]] = 0;
        }else if( H[start[i]] > H[end[i]]){
            Hr[end[i]] = 0;
        }  //等しい場合は両方0
        if (H[start[i]] == H[end[i]]){
            //printf("hoge\n");
            Hr[start[i]] = 0;
            Hr[end[i]] = 0;
        }
    }
    for(i=0;i<N;i++){
        if(Hr[i]>0){
            ret++;
        }else{
//            printf("%d : %ld\n",i,H[i]);
        }
    }
    printf("%d\n",ret);
    return 0;
    //↓全探索ではTLE
    // いい展望台か調べる
    for(i = 0 ; i < N ; i++){
        //startになっている道がある？
        max = H[i];
        add = 1;
        for ( j = 0 ; j < M ; j++){
            if (start[j] == i){
                if (H[end[j]] >= max){  //H[i]より標高が高い？
                    add = 0;
                    //break;
                }
            }
            if (end[j] == i){
                if (H[start[j]] >= max){  //H[i]より標高が高い？
                    add = 0;
                    //break;
                }
            }

        }
        ret += add;
    }
    printf("%d\n",ret);
    return 0;

}
int compare(const void* a, const void* b){
    return strcmp(a, b);
}
// 最大公約数
int gcd(int a,int b){
    int c;
    int tmp;
    if(b > a){  //bがaより大きい場合bとaを入れ替える
        c = a;
        a = b;
        b = c;
    }
    tmp = a % b;
    while(tmp!=0){
        a = b;
        b = tmp;
        tmp = a % b;
    }
    return b;
}


Measured memory_bytes: 4048
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;

int main(){
  int expe[3][301],cost[301];
  int dp[301];
  int n,m,ans;
  string str;
  while(cin >> n >> m){
    for(int i=0;i<n;i++){
      cin.ignore();
      getline(cin,str);
      cin >> cost[i] >> expe[0][i] >> expe[1][i] >> expe[2][i];
    }
    ans=0;
    for(int k=0;k<3;k++){
      memset(dp,0,sizeof(dp));
      for(int i=0;i<n;i++){
	for(int j=1;j<=m;j++){
	  for(int z=j;z>=0;z-=cost[i]){
	    if(z-cost[i] >= 0){
	      dp[z-cost[i]] = max(dp[z-cost[i]],dp[z]+expe[k][i]);
	    }
	  }
	}
      }
      ans = max(ans,*max_element(dp,dp+m+1));
    }
    cout << ans << endl;
  }
}

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

typedef long long lint;

int M[1000100],n,S[1000100],m;
lint sumA=0,sumB=0;

int main(){
	cin>>n;
	for(int i=0;i<n;i++) S[i]=3;
	for(int i=0;i<n;i++){
		char ch;
		cin>>ch;
		if(ch=='D') S[i]=2;
		if(ch=='M') S[i]=1;
		if(ch=='C') S[i]=0;
	}
	for(int i=0;i<n;i++){
		if(S[i]==1) M[i]++;
		if(i!=0) M[i]+=M[i-1];
	}
	cin>>m;
	for(int i=0;i<m;i++){
		int k;
		lint sumA=0,ans=0;
		cin>>k;
		queue <int> Q;
		for(int j=0;j<n;j++){
			if(Q.front()+k<j+1&&Q.size()>0){
				sumA-=M[Q.front()];
				Q.pop();
			}
			if(S[j]==0) ans+=Q.size()*M[j]-sumA;
			if(S[j]==2){
				Q.push(j);
				sumA+=M[j];
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 12184
#include<stdio.h>
#include<memory.h>
#include<algorithm>
#include<vector>
using namespace std;
char str1[3001];
char str2[3001];
int dp[3001][3001];
int dir[3001][3001];

void print(int len1, int len2)
{
    if(len1 == 0 || len2 == 0)return;
    if(dir[len1][len2] == 1)
    {
        print(len1-1, len2-1);
        printf("%c", str1[len1-1]);       
    }
    else if(dir[len1][len2] == 2)
    {
        print(len1-1, len2);
    }
    else print(len1, len2-1);
}

int main()
{
    int N, W;
    //freopen("input.txt", "r", stdin);
    scanf("%s%s", str1, str2);
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    for(int i=0; i<=max(len1, len2); i++)
    {
        dp[i][0] = dp[0][i] = 0;
    }
    for(int i=0; i<len1; i++)
    {
        for(int j=0; j<len2; j++)
        {
            if(str1[i] == str2[j])
            {
                dp[i+1][j+1] = dp[i][j] + 1;
                dir[i+1][j+1] = 1;
            }
            else
            {
                if(dp[i][j+1] > dp[i+1][j])
                {
                    dp[i+1][j+1] = dp[i][j+1];
                    dir[i+1][j+1] = 2;
                }
                else
                {
                    dp[i+1][j+1] = dp[i+1][j];
                    dir[i+1][j+1] = 3;
                }                
            }            
        }
    }
    print(len1, len2);
    printf("\n");
    return 0;
}

Measured memory_bytes: 70528
import java.util.*;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {
	int N;
	int[] A;
	int breakNum = 0;

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		Main ins = new Main(in);
		ins.calc();
		ins.showResult();
	}

	Main(BufferedReader in) throws IOException {
		N = Integer.parseInt(in.readLine());
		String[] tokens = in.readLine().split(" ");
		A = new int[N];
		for (int i = 0; i < N; ++i) {
			A[i] = Integer.parseInt(tokens[i]);
		}
	}

	void calc() {
		int target = 1;
		for (int i = 0; i < N; ++i) {
			if (target != A[i]) {
				// 壊す
				++breakNum;
			} else {
				// 壊さない
				++target;
			}
		}
		if (breakNum == N) {
			// だめだった
			breakNum = -1;
		}
	}

	void showResult() {
		System.out.println(breakNum);
	}
}


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

int gcd(int x, int y);

const int INF = 1001001001;

//mint�p�̕ϐ� (10��9��)
const int mod = 1000000007;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) :x((x% mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream & is, const mint & a) { return is >> a.x; }
ostream& operator<<(ostream & os, const mint & a) { return os << a.x; }

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > miti(n, vector<int> (0));
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        miti[a - 1].emplace_back(b - 1);
        miti[b - 1].emplace_back(a - 1);
    }
    vector<int> dist(n, INF);
    queue<int> room;
    vector<int> pre(n, -1);
    room.push(0);
    while (!room.empty()) {
        int num = room.front();
        room.pop();
        for (int r : miti[num]) {
            if (dist[r] != INF) continue;
            dist[r] = dist[num] + 1;
            pre[r] = num;
            room.push(r);
        }
    }

    cout << "Yes" << endl;
    rep(i, n) {
        if (i == 0) continue;
        cout << pre[i] + 1 << endl;
    }
    return 0;
}

/*���C�u�����ő����*/
//���[�O���b�h�̌ݏ��@
int gcd(int x, int y) {
    int num[3];
    num[0] = (x > y) ? x : y;
    num[1] = (x <= y) ? x : y;
    num[2] = num[0] % num[1];

    while (num[2]) {
        num[0] = num[1];
        num[1] = num[2];
        num[2] = num[0] % num[1];
    }

    return num[1];
}


Measured memory_bytes: 10560
//by xxj
#include<bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ll long long
#define pii pair<int,int>
#define lowbit(x) x&-x
const int inf=1e9+7;
const double eps=1e-10;
const ll linf=1e18+7;
const ll hh=523;
//const int mod=;
ll cf[200007];
//int cfa[200007];
int a[100007];
ll ans[200007];
vector<pii> add;
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++){
        scanf("%d",a+i);
    }
    ll sum=0;
    for (int i=1;i<n;i++){
        int x=a[i-1],y=a[i];
        if (y<x){
            y+=m;
        }
        sum+=y-x;
        add.push_back(mp(x+1,1));
        add.push_back(mp(y+1,0));
        cf[y+1]-=(y-x);
//		cout<<y<<' '<<y-x<<endl;
    }
//	cout<<sum<<endl;
    sort(add.begin(),add.end());
    int cnt=0;
    int j=1;
    for (int i=0;i<add.size();i++){
        int p=add[i].fst;
        for (int k=j;k<=p;k++){
            cf[k]+=cnt;
        }
        j=p+1;
        int t=add[i].snd;
//		cout<<p<<' '<<t<<endl; 
        if (t==1){
            cnt++;
        }
        else{
            cnt--;
        }
    }
//	cout<<cnt<<endl;
    for (int k=j;k<=2*m;k++){
        cf[k]+=cnt;
    }
//	for (int i=0;i<=2*m;i++){
//		cout<<cf[i]<<' ';
//	}
//	puts("");
    ans[0]=0;
    for (int i=1;i<=2*m;i++){
        ans[i]=ans[i-1]+cf[i];
    }
    ll mn=linf;
    for (int i=1;i<=m;i++){
        ans[i]+=ans[i+m];
//		ans[i]=sum-ans[i];
//		cout<<ans[i]<<endl;
        mn=min(sum-ans[i],mn);
    }
    printf("%lld\n",mn);
    return 0;
}
/*
input:
4 6
1 5 1 4
*/


Measured memory_bytes: 5488
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int A, B;
    cin >> A >> B;
    cout << 6 - A - B << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  int ans=0;
  for(int i=0;i<s.size();i++){
    if(s[i]!='J') continue;
    else{
      int now=i+1;
      int J=1,O=0,I=0;
      int flag1=1,flag2=0;
      while(s[now]=='J'){
	//cout<<now<<endl;
	J++;
	now++;
      }
      while(s[now]=='O' && flag1){
	//cout<<now<<endl;
	O++;
	now++;
	flag2=1;
      }
      if(J<O){
	i=now-1;
	continue;
      }
      while(s[now]=='I' && flag2){
	//cout<<now<<endl;
	I++;
	now++;
      }
      if(O>I){
	i=now-1;
	continue;
      }
      ans=max(ans,min(I,min(O,J)));
      // cout<<ans<<endl;
      i=now-1;
      //cout<<i<<endl;
      //cout<<s[i]<<endl;
    }
  }
  cout<<ans<<endl;
  return 0;
}
	  

Measured memory_bytes: 2052
#include <iostream>
#include <cstdio>
#include <vector>
#include <complex>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <stack>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <cassert>

using namespace std;

typedef long long ll;
typedef ll li;
typedef pair<int,int> PI;
#define EPS (1e-10L)
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define REP(i, n) rep (i, n)
#define F first
#define S second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset((a),0,sizeof(a))
#define FOR(it,a) for(__typeof(a.begin())it=a.begin();it!=a.end();++it)
template<typename T,typename U> ostream& operator<< (ostream& out, pair<T,U>& val){return out << "(" << val.F << ", " << val.S << ")";}
template<class T> ostream& operator<< (ostream& out, vector<T>& val){out << "{";rep(i,SZ(val)) out << (i?", ":"") << val[i];return out << "}";}
void pkuassert(bool t){t=1/t;};
int dx[]={0,1,0,-1,1,1,-1,-1};
int dy[]={1,0,-1,0,-1,1,1,-1};

int T;
int t[1000];
bool vis[120][40];

int day[120];

void solve(){
  CLR(vis);
  rep(i, T) cin >> t[i];
  priority_queue<pair<int,PI> > q;
  int N;
  cin >> N;
  rep(i, 100) day[i] = 23;
  rep(i, N){
    int d,m;
    cin >> d >> m;
    day[d-1] = min(day[d-1],m);
  }
  
  q.push(mp(0,mp(0,0)));
  while(!q.empty()){
    int cc=-q.top().F;
    int cd=q.top().S.F;
    int cs=q.top().S.S;
    q.pop();
    if(cd==100) {
      cout << cc << endl;
      return;
    }
    if(vis[cd][cs]) continue;
    vis[cd][cs] = true;
    q.push(mp(-cc-1,mp(cd,0)));
    if(t[cs]<=day[cd]) q.push(mp(-cc,mp(cd+1,(cs+1)%T)));
  }
}

int main(int argc, char *argv[])
{
  while(cin >> T && T) solve();
}

Measured memory_bytes: 1220
#include <iostream>
#include <string.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
#include <vector>
#include <map>
using namespace std;

#define cio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define ll long long
#define ii pair < int, int >
#define iii pair < int, ii >
#define INF 987654321
#define LINF 987654321987654321

int main()
{
	cio;
	string s, t;
	cin >> s >> t;

	int ans = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] != t[i])
			ans++;
	}

	cout << ans;
}

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

int main() {
	ll n, x, m; cin >> n >> x >> m;
	vector<ll> cnt;
	ll rem = x;
	ll tmp = m;
	while (tmp--) {
		cnt.push_back(rem);
		rem = rem * rem % m;
		if (find(cnt.begin(), cnt.end(), rem) != cnt.end())
			break ;
	}
	ll mae = distance(cnt.begin(), find(cnt.begin(), cnt.end(), rem));
	ll maeSUM = accumulate(cnt.begin(), cnt.begin() + mae, 0LL);
	ll loop = cnt.size() - mae;
	ll loopSUM = accumulate(cnt.begin() + mae, cnt.end(), 0LL);
	ll res = maeSUM;
	n -= mae;
	ll div = n / loop;
	ll mod = n % loop;
	res += loopSUM * div;
	res += accumulate(cnt.begin() + mae, cnt.begin() + mae + mod, 0LL);
	cout << res << '\n';
    return 0;
}


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

int main(){
   int n,m;
   cin>>n>>m;
   vector<pair<ll,ll>> p;
   for(int i=0;i<n;i++){
       int a,b;
       cin>>a>>b;
       p.push_back(make_pair(a,b));
   }
   sort(p.begin(),p.end());
   ll sum=0,ans=0;
   ll j=0;
   while(1){
       if(sum+p[j].second>m){
           ans+=(m-sum)*p[j].first;
           cout<<ans<<endl;
           return 0;
       }
       sum+=p[j].second;
       ans+=p[j].first*p[j].second;
       j++;
   }
   
}


Measured memory_bytes: 2420
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int answer = (n*(n-1))/2 + (m*(m-1))/2;
		System.out.println(answer);
	}

}


Measured memory_bytes: 23252
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

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

    std::vector<int> v(n);

    for(int i = 0; i < n; i++) scanf("%d", &v[i]);

    std::vector<int> v_sorted(v);
    std::sort(v_sorted.begin(), v_sorted.end());

    int f = n / 2 - 1, l = n / 2;
    for(int i = 0; i < n; i++){
        printf("%d\n", (v[i] <= v_sorted[f]) ? v_sorted[l] : v_sorted[f]);
    }

    return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MXX = 1e6 + 5;


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

    for(int i = 0; i<s.size(); i++)
    {
        if(s[i] == 'B')
        {
            s.erase(i, 1);
            if(i>0) {
                s.erase(i-1, 1);
                i--;
            }
            i--;
        }
    }

    cout << s << endl;

    return 0;
}


Measured memory_bytes: 256