akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static Scanner sc = new Scanner(System.in);
    public static long[] stone;
    public static void main(String[] args) throws Exception {
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int p = sc.nextInt();
            if (n == 0 && p == 0) break;
            stone = new long[n];
            long cup = p;
            int pos = 0;
            while (true) {
                if (cup > 0) {
                    stone[pos]++;
                    cup--;
                } else {
                    cup += stone[pos];
                    stone[pos] = 0;
                }
                if (stone[pos] == p) break;
                pos++;
                if (pos == n) pos = 0;
            }
            System.out.println(pos);
        }
    }
}

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

int main()
{
  int N;
  long H[100001];
  cin >> N;

  rep(i,N) cin >> H[i];

  reverse(H, H+N);

  rep(i,N-1){
    if(H[i+1] <= H[i]) continue;
    if(H[i+1]-1 == H[i]) {
        H[i+1]--;
        continue;
    }
    else {
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes"  << endl;
}

Measured memory_bytes: 1024
N=int(input())
L=list(map(int,input().split()))

ans=0

L.sort()

for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if L[i]!=L[j] and L[j]!=L[k] and L[k]!=L[i] and L[k]<L[i]+L[j]:
        ans+=1

print(ans)

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

N=int(input())
A=list(map(int,input().split()))

from collections import Counter
C=Counter([A[i]-i for i in range(N)])

ANS=0

for i in range(N):
    C[A[i]-i]-=1
    ANS+=C[-2*i-(A[i]-i)]

print(ANS)

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
    map<int,int>mp;
    set<int>AC;
    int cnt1 = 0, cnt2 = 0;
    for(int i = 0 ; i < m ; i++){
        int add;
        cin >> add;
        string s;
        cin >> s;
        if(s[0]=='A'){
            if(!AC.count(add)){
                AC.insert(add);
                cnt2 += mp[add];
            }  
        }
        else{
            mp[add]++;
        }
    }
    cout << AC.size() <<' '<<cnt2<<'\n';
}

Measured memory_bytes: 9600
#include <iostream>
#include <string>
#include <algorithm>
#include <utility> 
#include <unordered_set>
#include <vector>
#include <list> 
#include <string>
#include <iterator> 
#include <deque>
#include <array>
#include <forward_list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <bitset>
#include <numeric>
using namespace std;


const long double PI = 3.14159265358979323846264338327950;
const int N = 2*1e5;

template <class T>
T gcd(T a, T b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int arr[N];
bool vis[N+1];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> arr[i];
	int x = arr[0];
	int ans =1;

	for (int i = 1; i < n; ++i) {
		if (arr[i] < x)
			++ans;
		
		x = min(x, arr[i]);
	}

	cout << ans << '\n';
}


Measured memory_bytes: 4388
//
//  main.cpp
//  A - Frog 1
//
//  Created by Hashizo on 2019/06/12.
//  Copyright © 2019 Hashizo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <regex>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define REPLACE(s, f, t) regex_replace(s, regex(f), t)

int main(int argc, const char * argv[]) {
	int n;
	cin >> n;

	int footHold[n];
	int dp[n+1];
	
	REP(i, n){
		cin >> footHold[i];
	}

	dp[0] = 0;
	dp[1] = abs(footHold[0]-footHold[1]);

	FOR(i, 2, n) {
		if((dp[i-1] + abs(footHold[i-1]-footHold[i]))  <
		   (dp[i-2] + abs(footHold[i-2]-footHold[i]))) {
			dp[i] = (dp[i-1] + abs(footHold[i-1]-footHold[i]));
		}
		else {
			dp[i] = (dp[i-2] + abs(footHold[i-2]-footHold[i]));
		}
	}
	
	cout << dp[n-1] << endl;
	return 0;
}


Measured memory_bytes: 1024
import heapq

N, M = map(int, input().split())

lst = []
nf = M

for i in range(1, int(M**0.5 + 1)):
    if nf % i == 0:
        lst.append(-i)
        if i * i != nf: lst.append(-nf//i)

heapq.heapify(lst)
while lst:
    hq = -heapq.heappop(lst)
    if M // hq >= N:
        break
print(hq)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) for(int i=(n)-1;0<=i;--i)
#define each(e,v) for(auto&& e:(v))
#define all(v) begin(v),end(v)
#define dump(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
using vint = vector<int>;
using ll = long long;
using vll = vector<ll>;
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }
void yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }

int main() {
    int n, m; cin >> n >> m;
    vint a(n);
    rep(i, n) cin >> a[i];
    vector<pair<int, int>> cb(m);
    rep(i, m) {
        int b, c; cin >> b >> c;
        cb[i] = make_pair(c, b);
    }
    sort(all(a));
    sort(all(cb)); reverse(all(cb));
    int cnt = 0;
    rep(i, m) {
        int b = cb[i].second;
        int c = cb[i].first;
        rep(j, b) {
            if(a[cnt] < c) {
                a[cnt] = c;
                cnt++;
            } else {
                break;
            }
        }
    }
    ll sum = accumulate(all(a), 0LL);
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
#define INF      (int)1e9
#define MOD      ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef pair<int,int> pii;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
template<class Type> void line(const Type &a){int cnt=0;for(auto &elem:a){if(cnt++)cout<<' ';cout<<elem;}cout<<endl;}

int main(){
	int a,b;
	cin>>a>>b;
	
	cout<<6-a-b<<endl;
}


Measured memory_bytes: 256
import heapq

n,m = map(int,input().split())

a = [0] * n
b = [0] * n
info = [[] for _ in range(m+1)]

for i in range(n):
    a[i], b[i] = map(int,input().split())
    if a[i] <= m:
        info[a[i]].append(b[i])

l = []
count = 0

for j in range(1,m+1):
    for x in info[j]:
        heapq.heappush(l,-x)
    if l != []:
        count += -heapq.heappop(l)

print(count)


Measured memory_bytes: 22976
//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<numeric>
#include<bitset>
#include<limits>
#include<unordered_map>
#include<functional>
using namespace std;

#define rep(i,s,n) for(int i=s;i<n;i++)
#define dow(i,n,s) for(int i=n-1;i>=s;i--)
#define all(a) a.begin(),a.end()
#define Sort(a) sort(all(a))
#define Qsort(a,size) qsort(a,size,sizeof(*a),compare_int)
#define DEBUG
typedef pair<int,int> II;
typedef unsigned long ul;
typedef long long ll;
typedef unsigned long long ull;
bool compare_int(const void *a,const void *b) { return *(int *)a-*(int *)b; }
bool compare_by_second(II a,II b) { return a.second!=b.second?a.second<b.second:a.first<b.first; }

const int INF = 1e+9;
const int MAX_S = 17;

string s;
int ans,M = 0,L = 0;
vector<int> Mi;

//void solve();

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

  rep(i,0,s.size()) {
    if(s[i] =='*') { Mi[Mi.size()-1] = Mi[Mi.size()-1]*(s[i+1]-'0'); i++; }
    else if('0' <= s[i] && s[i] <= '9') Mi.push_back(s[i] - '0');
  }
  rep(i,0,Mi.size()) M+=Mi[i];

  rep(i,0,s.size()) {
    if(s[i] == '*') { L*=(s[i+1] - '0'); i++; }
    else if(s[i] == '+') { L+=(s[i+1] - '0'); i++; }
    else L = (s[i] - '0');
  }

  //cout<<"M-->"<<M<<" , L-->"<<L<<endl;

  if(ans == M && ans == L) { cout<<"U"<<endl; return 0; }
  if(ans != M && ans != L) { cout<<"I"<<endl; return 0; }
  if(ans == M) { cout<<"M"<<endl; return 0; }
  cout<<"L"<<endl; return 0;

}



Measured memory_bytes: 3212
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef pair<int, int> pi;


int main() {
  int n;
  cin >> n;
  vi h(n);
  rep(i, n) cin >> h[i];

  int dp[2][n+1];
  rep(i, n+1) rep(j, 2) dp[j][i] = 0;
  dp[0][0] = 0;
  dp[0][1] = dp[1][1] = abs(h[0] - h[1]);

  // printf("%d %d %d\n", 0, dp[0][0], dp[1][0]);
  // printf("%d %d %d\n", 0, dp[0][1], dp[1][1]);
  for(int i=2;i<n;i++){
    dp[0][i] = min(dp[0][i-1], dp[1][i-1]) + abs(h[i] - h[i-1]);
    dp[1][i] = min(dp[0][i-2], dp[1][i-2]) + abs(h[i] - h[i-2]);
    // printf("%d %d %d\n", i, dp[0][i], dp[1][i]);
  }
  cout << min(dp[0][n-1], dp[1][n-1]) << endl;
  return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<vector<ll> > mat;

ll m=1e9+7;

ll p(ll a,ll b)
{
	ll r=1;
	while(b)
	{
		if(b%2)r=(r*a)%m;
		a=(a*a)%m;
		b/=2;
	}
	return r;
}

ll ncr(ll n,ll r)
{
	ll ans=1;
	rep(i,1,r)
	{
		ans=(ans*(n-i+1))%m;
		ans=(ans*p(i,m-2))%m;
	}
	return ans;
}

int main()
{ios_base::sync_with_stdio(false);
ll n,a,b;
cin>>n>>a>>b;
ll ans=p(2,n)-ncr(n,a)-ncr(n,b)-1;
ans%=m;
ans=(ans+m)%m;
ol(ans);
return 0;
}



Measured memory_bytes: 256
from math import factorial

mod = 10**9+7
N = int(input())
x = [0] + list(map(int, input().split()))
ans = 0
inv = [0] + [pow(i, mod-2, mod) for i in range(1, N)]

for k in range(2, N):
    ans = (ans + x[k] * (1 - inv[k])) % mod

for k in range(1, N-1):
    ans = (ans - x[k] * (1 - inv[N-k])) % mod

for k in range(1, N):
    ans = (ans + (x[N] - x[k]) * inv[N-k]) % mod

ans = ans * factorial(N-1) % mod

print(ans)


Measured memory_bytes: 15020
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<list>
#include<map>
#include<set>
#include<string>
#include <sstream>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>

using namespace std;


int main(){
  long ii,jj,kk;
  vector<int> arr[1000];

  int n,q,c,t,x;
  cin >> n >> q;

  for(ii=0;ii<q;ii++){
    cin >> c;
    switch(c){
    case 0:
      cin >> t >> x;
      arr[t].push_back(x);
      break;
    case 1:
      cin >> t;
      for(jj=0;jj<arr[t].size();jj++){
        if( jj !=(arr[t].size()-1)){
          cout << arr[t][jj] << " ";
        }
        else{
          cout << arr[t][jj];
        }
      }
      cout << endl;
      break;
    case 2:

      cin >> t;
      arr[t].clear();
      break;
    }
  }
  
  return 0;
}



Measured memory_bytes: 5852
import math
def main():
	n, m = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	
	d = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
	num2match = {key:val for key, val in d.items() if key in nums}
	
	dp = [-1 for i in range(n + 1)]
	dp_keta = [0 for i in range(n + 1)]

	dp[0] = 0
	val_set = list(set(num2match.values()))
	match2num = {v:max([int(key) for key, val in num2match.items() if val == v]) for v in val_set}

	cnt = 0
	for i in range(2, n + 1):
		for val in val_set:
			#print(val)
			cnt += 1
			if i >= val and dp[i - val] >= 0:
				tmp = match2num[val] * (10 ** dp_keta[i - val]) + dp[i - val]
				dp[i] = max(dp[i], tmp)
				dp_keta[i] = max(dp_keta[i], dp_keta[i - val] + 1)

	#print(num2match)
	#print(match2num)
	#print(dp)
	#print(dp)
	print(int(dp[n]))
	#print(cnt)
 
if __name__ == '__main__':
	main()

Measured memory_bytes: 15128
import fractions
a,b,c,d=map(int,input().split())
a=a-1
ac,ad,bc,bd=a//c,a//d,b//c,b//d

f=fractions.gcd(c,d)
f=c*d//f
acd,bcd=a//f,b//f
print((b-a)-(bc-ac)-(bd-ad)+(bcd-acd))

Measured memory_bytes: 5344
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>

using namespace std;

int main()
{
   
    long long x, y, sum=0, res=0;

    long long arr[200005];

    cin >> x >> y;

    for (int i = 0; i < x; i++) {

        cin >> arr[i];

        sum += arr[i];
    }

    if (y >= x) {
        cout << 0;

        return 0;

    }


    sort (arr, arr + x);

    x = x - 1;

    for (int i = 0; i < y; i++) {

        res += arr[x];

        x--;

    }


    cout << sum - res;

  
}

Measured memory_bytes: 1792
sx, sy, tx, ty = map(int, input().split())
dy = ty - sy
dx = tx - sx
ans = dy*'U' + dx*'R' + dy*'D' + dx*'L'
ans += 'L' + (dy+1)*'U' + (dx+1)*'R' + 'D'
ans += 'R' + (dy+1)*'D' + (dx+1)*'L' + 'U'
print(ans)


Measured memory_bytes: 9180
#include <stdio.h>

int main(void) {
	int a, b, c, i, j, n; 
	scanf("%d", &j);
	for(i= 1; i <= j ;i++){
		scanf("%d%d", &a, &b);
		c = a / b;
		if (a % b==0){
			n = b;
		}
		else{
			n = a - c * b;
		}
		printf("%d\n", n);
	}
	
	return 0;
}

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

int main(){
    string s;
    cin>>s;
    int c[26]={0};
    for(int i=0;i<s.size();i++) c[s[i]-97]++;
    
    for(int i=0;i<26;i++){
        if(c[i]%2==1){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 384
import math
def py():
    print("yes")
def pn():
    print("no")
def iin():
    x = int(input())
    return x

neko = 0
nya = 0
nuko = 0

n = iin()
s = input()
for i in s:
    if i == 'I':
        neko += 1
    elif i == 'D':
        neko -= 1
    if nuko < neko:
        nuko = neko
print(nuko)

Measured memory_bytes: 9140
def gcd(a,b):
    if a<b:
        a,b=b,a
    if b==0:
        return a
    return gcd(b,a%b)

def lcm(a,b):
    return a//gcd(a,b)*b

n=int(input())
a=list(map(int,input().split()))
b=1
for i in a:
    b=lcm(b,i)
print(b)



Measured memory_bytes: 5600
/* Manish Pant - insider_pants */

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
    #include "debug.h"
#endif

#define F first
#define S second
#define endl "\n"
#define pb push_back
typedef long long ll;
typedef long double ldob;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ldob EPI = 1e-12;
int n;
vector<pll> v;

bool ok1(ll mid)
{
    ll half = v[n >> 1].F + mid - 1;
    ll cnt1 = 0, cnt2 = 0;
    for(int i = 0; i < n; i++)
    {
        ll a = v[i].F, b = v[i].S;
        if(b < half)
            continue;

        if(a > half)
            cnt1++;
        else 
            cnt2++;
    }
    ll req = (n >> 1);
    if(cnt1 + cnt2 > req && cnt2 > 0)
        return 1;
    else 
        return 0;
}

bool big(ldob a, ldob b)
{
    // a > b ? 1 : 0
    if(fabs(a - b) > EPI && a > b)
        return true;
    return false;
}

bool ok2(ll mid)
{
    ldob half = ldob(v[n >> 1].F + v[(n >> 1) - 1].F) / 2.0 + ldob(mid) / 2.0;
    ll cnt1 = 0, cnt2 = 0;
    for(int i = 0; i < n; i++)
    {
        ldob a = v[i].F, b = v[i].S;
        if(big(half, b))
            continue;
        if(big(a, half))
            cnt1++;
        else
            cnt2++;
    }

    ll req = (n >> 1);
    if(cnt1 + cnt2 > req)
        return 1;
    else
        return 0;
}

bool comp(pll &a, pll &b)
{
    return make_pair(a.S, a.F) < make_pair(b.S, b.F);
}

void solve()
{
    sort(v.begin(), v.end());
    // ll s = 1, e = 2e9 + 5;
    // ll ans = 1;
    // while(s <= e)
    // {
    //     ll mid = (s + e) >> 1;
    //     if((n & 1 ? ok1(mid) : ok2(mid)))
    //     {
    //         ans = mid;
    //         s = mid + 1;
    //     }
    //     else
    //         e = mid - 1;
    // }
    // cout << ans << endl;

    if(n & 1)
    {
        ll ans = v[n >> 1].F;
        sort(v.begin(), v.end(), comp);
        ans = v[n >> 1].S - ans + 1;

        cout << ans << endl;
    }
    else
    {
        ldob ans = ldob(v[n >> 1].F + v[(n >> 1) - 1].F) / 2.0;
        sort(v.begin(), v.end(), comp);
        ldob temp = ldob(v[n >> 1].S + v[(n >> 1) - 1].S) / 2.0;
        ans = temp - ans;
        ans *= 2.0;
        ans++;
        cout << ll(ans) << endl;
    }
}

int main()
{
    fast();
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        ll a, b; cin >> a >> b;
        v.pb({a, b});
    }
    solve();
}

Measured memory_bytes: 7424
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
using namespace std;


int main(){

	int H,R;

	scanf("%d %d",&H,&R);
	R *= -1;

	if(H > R){
		printf("1\n");
	}else if(H == R){
		printf("0\n");
	}else{
		printf("-1\n");
	}

    return 0;
}

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

int64_t modpow(int64_t a, int64_t n, const int64_t mod)
{
    int64_t result = 1;
    while (n) {
        if (n & 1) result = result * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return result;
}

int main()
{
    const static int64_t mod = 1e+9 + 7;
    int64_t N;
    cin >> N;
    int64_t cnt = modpow(10, N, mod);
    cnt -= modpow(9, N, mod);
    cnt %= mod;
    cnt -= modpow(9, N, mod);
    cnt %= mod;
    cnt += modpow(8, N, mod);
    cnt %= mod;
    if (cnt < 0)
        cnt += mod;
    cout << cnt << endl;
}



Measured memory_bytes: 3620
function main(_stdin) {
    const stdin = _stdin.trim().split('\n');
    const n = Number(stdin.shift());
    const S = stdin.shift().trim().split(' ').map(Number);
    const q = Number(stdin.shift());
    const T = stdin.shift().trim().split(' ').map(Number);

    let C = 0;
    for(const t of T){
        C += S.includes(t)
    }
    console.log(C);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));



Measured memory_bytes: 17568
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
 
const int INF = 1e9;
const int mod = 1e9+7;

int main()
{
    int n;
    cin >> n;
    int sum = 0;  
    vector<int> a(n+10);
    a[0] = a[n+1] = 0;    
    for(int i = 1; i <= n + 1; i++){
        if(i != n + 1) cin >> a[i];
        sum += abs(a[i-1]-a[i]);
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        cout << sum + abs(a[i-1]-a[i+1]) - (abs(a[i-1]-a[i])+abs(a[i]-a[i+1])) << endl;
    }

    return 0;
}

Measured memory_bytes: 1664
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs():
    from collections import deque

    que = deque()
    cnt = 1
    memo = {}
    for i in range(1, 10):
        que.append(str(i))
        memo[cnt] = str(i)
        cnt += 1
    while que:
        x = que.popleft()
        last = int(x[-1])
        if last != 0:
            que.append(x+str(last-1))
            memo[cnt] = x + str(last-1)
            cnt += 1
        que.append(x+str(last))
        memo[cnt] = x+str(last)
        cnt += 1
        if last != 9:
            que.append(x+str(last+1))
            memo[cnt] = x + str(last+1)
            cnt += 1
        if cnt > K:
            return memo

K = INT()

res = bfs()
print(res[K])


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

#define ll long long
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define M 1000000007
#define pb push_back
#define mp make_pair

#define f(i,n) for(int i=0;i<n;i++)
#define bf(i,n) for(int i=n-1;i>=0;i--)

#define all(v) v.begin(), v.end()
#define p0(a) cout<<a<<" "<<'\n'
#define p1(a) cout<<a<<'\n'
#define p2(a,b) cot<<a<<" "<<b<<'\n'
#define p3(a,b,c) cout<<a<<" "<<b<<" "<<c<<'\n'
#define p4(a,b,c,d) cout<<a<<" "<<b<<" "<<c<<" "<d<<'\n'

#define bl '\n'


int main() {
	// your code goes here
	FIO;
	ll test = 1;
	//cin>>test;
	while(test--){
	    int a,b,c,k;
	    cin>>a>>b>>c>>k;
	    int cnt = 0;
	   while(b<=a){
	       cnt++;
	       b = b*2;
	   }
	   while(c<=b){
	       cnt++;
	       c = c*2;
	   }
	   if(cnt<=k) cout<<"Yes"<<endl;
	   else cout<<"No"<<endl;
	    
	    
	}
	return 0;
}


Measured memory_bytes: 3652
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd); FUNC(printde);
#endif

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            int num = i * m + j * n - 2 * i * j;
            if(num == k){
                cout << "Yes" << '\n';
                return 0;
            }
        }
    }
    cout << "No" << '\n';
}


Measured memory_bytes: 256
import std.stdio;
import std.ascii;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;

void main() {
    int M, N;
    string[] F;
    bool input() {
        scanf("%d %d\n", &M, &N);
        if (M == 0 && N == 0) return false;
        F = new string[N];
        foreach (i; 0 .. N) {
            F[i] = readln.chomp;
        }
        return true;
    }
    int tobinary(in string s) {
        char[] t = cast(char[])(s.dup);
        int Ret = 0;
        t.reverse;
        foreach (i; 0 .. t.length) {
            Ret += ((t[i] == '1' ? 1 : 0) << i);
        }
        return Ret;
    }
    void solve() {
        int[] G = new int[N];
        foreach (i; 0 .. N) {
            G[i] = tobinary(F[i]);
        }
        int INF = int.max / 2;
        auto memo = new int[][](1 << M, 1 << M);
        foreach (i; 0 .. (1 << M)) memo[i][] = -1;
        int dfs(int used, int gid) {
            int C = 0;
            if (memo[used][gid] >= 0) return memo[used][gid];
            foreach (i; 0 .. N) {
                if ((G[i] & used) == gid) {
                    C++;
                }
            }
            if (C == 0) return INF;
            if (C == 1) return 0;
            int Ret = INF;
            foreach (i; 0 .. M) {
                if (used & (1 << i)) continue;
                int x = dfs(used | 1 << i, gid);
                int y = dfs(used | 1 << i, gid | 1 << i);
                //writeln([x, y]);
                Ret = min(Ret, max(x, y) + 1);
            }
            static if (false){ 
                writeln("C: ", C, 
                    " used: ", format("%0" ~ M.to!string ~ "b", used),
                    " gid: ", format("%0" ~ M.to!string ~ "b", gid),
                    " --> ", Ret);
            }
            return memo[used][gid] = Ret;
        }
        writeln(dfs(0, 0));
    }
    while (input) solve;
}

Measured memory_bytes: 38276
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <iomanip>
#include <math.h>
#include <algorithm>
#define hmm "\n"
#define test() int t; cin>>t; while(t--)
#define ll long long int
#define ull unsigned long long
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
void solve()
{
    ll c=0,n;cin>>n;
    string s; cin>>s;

    for(int i=0; i<n-2; i++){
        if(s.substr(i,3)=="ABC")
            c++;
    }
    cout<<c<<hmm;
}
int main()
{
    fastIO
    //test()
    solve();
}


Measured memory_bytes: 3656
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        long[] A = Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();

        long[] A2 = A.ToArray();
        for(int i = 0; i < A2.Length; i++)
        {
            A2[i] = A2[i] - i - 1;
        }

        //A2の各要素からxを引いたときよりもx+1を引いたときのほうが悲しさが減るか否かの判定関数をf(x)とする。
        Func<int, bool> f = (int x) => {
            if(A2.Select(itm => Math.Abs(itm - x)).Sum() > A2.Select(itm => Math.Abs(itm - x - 1)).Sum())
            {
                return true;
            }
            else
            {
                return false;
            }
        };

        //判定関数がfalseからtrueに変わる場所を二分探索
        //引く数が大きすぎるとき、それより引く数を大きくするのが効果的ではないことから、
        //MaxValueのときはf(x)はfalseである。
        //また逆にMinValueのときはtrueである。
        long left = int.MinValue;
        long right = int.MaxValue;

        while(right - left > 1)
        {
            long half = left + (right - left) / 2;

            if(f((int)half) == true)
            {
                left = half;
            }
            else
            {
                right = half;
            }
        }

        //falseとなる最初の値が答えだから、rightが答え。
        Console.WriteLine(A2.Select(itm => Math.Abs(itm - right)).Sum());

    }
    
}



static class MathUtil
{
    public static IEnumerable<IEnumerable<int>> GetPermutation(int n)
    {
        if (n == 0)
        {
            yield return Single(0);
            yield break;
        }

        for (int i = 0; i <= n; i++)
        {
            foreach (var x in GetPermutation(n - 1))
            {
                yield return Single(i).Concat(x.Select(itm => itm < i ? itm : itm + 1));
            }
        }
    }

    private static IEnumerable<int> Single(int x)
    {
        yield return x;
    }

    public static IEnumerable<int> EnumeratePrimeNumbers()
    {
        List<int> primes = new List<int>() { 2 };
        yield return 2;

        for (int i = 3; i < int.MaxValue; i++)
        {
            bool isPrime = true;
            int Sqrt = (int)Math.Sqrt(i) + 1;

            foreach (var prime in primes)
            {
                if (prime > Sqrt)
                {
                    break;
                }
                if (i % prime == 0)
                {
                    isPrime = false;
                    break;
                }
            }

            if (isPrime)
            {
                primes.Add(i);
                yield return i;
            }
        }
    }
}



Measured memory_bytes: 34592
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define show(x) cout << #x << " = " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int main(){
    int n;
    ll x;
    cin >> n >> x;
    ll a[2005];
    ll b[2005];
    rep(i,n){
        cin >> a[i];
        b[i] = a[i];
    }
    ll ans = 1LL << 60;
    rep(num,n){
        ll temp = x*num;
        rep(i,n){
            b[i] = min(b[i],a[(i-num+n)%n]);
            temp+=b[i];
        }
        ans = min(ans,temp);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
A.sort()

tmp=A[0]
for a in A[1:]:
  if a%tmp!=0:
    tmp=a%tmp
    
while 1:
  A_tmp=[a%tmp for a in A if a%tmp!=0]
  if sum(A_tmp)!=0:
    tmp=min(A_tmp)
  else:
    break
print(tmp)

Measured memory_bytes: 15020
n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [0]*m
for i in range(m):
    bc[i] = list(map(int,input().split()))
sortsecond = lambda val : val[1]
bc.sort(key=sortsecond,reverse = True)
a = sorted(a)
i = 0
j = 0
count = 0
while a[i] < bc[j][1]:
    a[i] = bc[j][1]
    i += 1
    if i >= len(a):
        break
    count += 1
    if count == bc[j][0]:
        j += 1
        count = 0
        if j>=m:
            break
print(sum(a))

Measured memory_bytes: 32976
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<unordered_set>
#include<vector>

#define ll long long
#define P pair<int,int>
#define FOR(i,N) for(int i=0;i<(int)N;i++)
#define FORIN(i,a,b) for(int i=a;i<(int)b;i++)
#define ALL(x) (x).begin(),(x).end()
#define LAST(x) (x)[(x).size()-1]
#define GI(name) int (name);scanf("%d",&(name))
#define GI2(name1,name2) int (name1),(name2);scanf("%d %d",&(name1),&(name2))
#define GI3(name1,name2,name3) int (name1),(name2),(name3);scanf("%d %d %d",&(name1),&(name2),&(name3))
#define GVI(name,size) vector<int> (name)(size);FOR(i,(size))scanf("%d",&(name)[i])
#define MOD 1000000007

using namespace std;

string to_hex(int x){
    stringstream ss;
    ss<<hex<<x;
    return ss.str();
}

inline int get_int(){
    int ret;
    scanf("%d",&ret);
    return ret;
}

inline vector<int> get_ints(int n){
    vector<int> ret(n);
    FOR(i,n){
        scanf("%d",&ret[i]);
    }
    return ret;
}

inline string get_str(){
    string ret;
    cin>>ret;
    return ret;
}

bool is_prime(int n){
    int s=sqrt(n)+1;
    for(int i=2;i<=s;++i){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

vector<P> prime_division(int n){
    vector<P> ret;
    int s=sqrt(n)+1;
    int c=0;
    for(int i=2;i<=n;++i){
        if(n%i==0){
            c=0;
            do{
                ++c;
                n/=i;
            }while(n%i==0);
            ret.push_back(P(i,c));
        }
    }
    return ret;
}

struct UnionFind{
    vector<int> data;
    UnionFind(int size){
        data=vector<int>(size,-1);
    }
    bool union_set(int x,int y){
        x=root(x);
        y=root(y);
        if(x!=y){
            if(data[y]<data[x])swap(x,y);
            data[x]+=data[y];
            data[y]=x;
        }
        return x!=y;
    }
    bool find(int x,int y){
        return root(x)==root(y);
    }
    int root(int x){
        return data[x]<0?x:data[x]=root(data[x]);
    }
    int size(int x){
        return -data[root(x)];
    }
};

string to_string(string s){
    return s;
}

template<class T>
string to_string(vector<T> v){
    string ret="{";
    FOR(i,v.size()-1){
        ret+=to_string(v[i])+",";
    }
    if(v.size()>0){
        ret+=to_string(LAST(v));
    }
    ret+="}";
    return ret;
}

void debug_print(){
    cerr<<endl;
}

template<class Head,class... Tail>
void debug_print(Head head,Tail... tail){
    cerr<<to_string(head)<<" ";
    debug_print(tail...);
}

template<class... T>
void debug(T... args){
    cerr<<"["<<__LINE__<<"]: ";
    debug_print(args...);
}

void print(){
    cout<<endl;
}

template<class Head,class... Tail>
void print(Head head,Tail... tail){
    cout<<to_string(head);
    print(tail...);
}

int main(){
    ll N,K;
    cin>>N>>K;
    ll ans=0;
    if(K==0){
        print(N*N);
        return 0;
    }
    for(int i=K+1;i<=N;++i){
        ans+=(N+1)/i*(i-K);
        ans+=max(0LL,i==K+1?0:((N+1)%i-K));//debug(i,ans);
    }
    print(ans);
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int A = sc.nextInt();
    int B = sc.nextInt();
    int C = sc.nextInt();
    int D = sc.nextInt();
    String S = sc.next();
    //C<Dならば、ふぬけが先に動いて到達できるか、そのあとすぬけが到達できるかを考えればよい

    if(C<D){
      if(!isDoubleStone(S,B,D)&&!isDoubleStone(S,A,C)){
        System.out.println("Yes");
        return;
      }else{
        System.out.println("No");
        return;
      }
    }
      
    //C>Dならば、BからDの間で、ふぬけがすぬけに追い越させる隙間が必要
    if(C>D){
      if(!isTripleSpace(S,B,D)){
        System.out.println("No");
        return;
      }
      //隙間があるならあとは到達できるかを独立して考える
      if(!isDoubleStone(S,B,D)&&!isDoubleStone(S,A,C)){
        System.out.println("Yes");
        return;
      }else{
        System.out.println("No");
        return;
      }
    }
  }
  //nからmの間に2連続で石が置いてあるか確認するメソッド
  public static boolean isDoubleStone(String S,int n,int m){
    for(int i=n-1;i<m-1;i++){
      if(S.substring(i,i+2).equals("##")){
        return true;
      }
    }
    return false;
  }
  
  //nからmの間に3連続で隙間が空いているか確認するメソッド
  public static boolean isTripleSpace(String S,int n,int m){
    for(int i=n-2;i<Math.min(m-1,S.length());i++){
      if(S.substring(i,i+3).equals("...")){
        return true;
      }
    }
    return false;
  }
  

  
}

Measured memory_bytes: 41520
package main

import (
	"fmt"
)

func main() {
	var n, cost int
	fmt.Scan(&n)

	values := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&values[i])
	}

	totalCost := 0
	for i := 0; i < n; i++ {
		fmt.Scan(&cost)
		if values[i]-cost > 0 {
			totalCost += values[i] - cost
		}
	}

	fmt.Println(totalCost)
}


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

int main(){
  vector<int>A(5);
  for(int i=0;i<5;i++){
    cin >> A[i];
  }
  int k;
  cin >> k;
  bool C=true;
  sort(A.begin(),A.end());
  reverse(A.begin(),A.end());
  for(int i=0;i<5;i++){
    for(int j=4;j>i;j--){
      if(A[i]-A[j]>k){
        C=false;
        break;
      }
    }
    if(C==false){
      cout << ":(" << endl;
      break;
    }
  }
  if(C==true){
    cout << "Yay!" << endl;
  }
}


Measured memory_bytes: 3612
#include<iostream>
using namespace std;
#define int long long
const int CN = 2e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, x[CN], y[CN], mx = -INF, mn = INF, ans = -INF;
inline int read() { char c = getchar(); int sign = 1; int x = 0; while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); } return x * sign; }

signed main()
{
    ios :: sync_with_stdio(false);
  
    n = read();
    for(int i = 1; i <= n; i++) x[i] = read(), y[i] = read();
    for(int i = 1; i <= n; i++) mx = max(mx, x[i] + y[i]), mn = min(mn, x[i] + y[i]);
    ans = max(ans, mx - mn);
    mx = -INF, mn = INF;
    for(int i = 1; i <= n; i++) mx = max(mx, x[i] - y[i]), mn = min(mn, x[i] - y[i]);
    ans = max(ans, mx - mn);
    cout << ans;
}


Measured memory_bytes: 6780
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

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

    int front_white = 0;
    int front_black = 0;

    for (int i = 0; i < s.size(); i++)
    {
        const char fw_ch = (i % 2 == 0 ? '1' : '0');
        const char fb_ch = (i % 2 == 0 ? '0' : '1');

        if (fw_ch != s[i])
        {
            front_white++;
        }
        if (fb_ch != s[i])
        {
            front_black++;
        }
    }
    cout << min<int>(front_white, front_black) << endl;
}


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

using namespace std;

int main()
{
	string buf;
	int num = 0;
	while ( getline(cin, buf) ) {
		int tmp_num = 0;
		bool num_mode = false;
		while ( !buf.empty() ) {
			if ( '0' <= buf[0] && buf[0] <= '9' ) {
				tmp_num *= 10; tmp_num += buf[0] - '0';
				num_mode = true;
			}
			else if (num_mode) {
				num += tmp_num; tmp_num = 0;
				num_mode = false;
			}
			buf.erase( buf.begin() );
		}
		num += tmp_num;
	}
	
	cout << num << endl;
	
	return 0;
}

Measured memory_bytes: 3136
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;
/* ---------------------------------------------------------------------------------------------------- */

template <typename T>
vector<int> dijkstra(const vector<vector<pair<int,T>>> &G,int s,T inf) {
  vector<int> d(G.size(),inf);
  d[s] = 0;
  using P = pair<T,int>;
  priority_queue<P,vector<P>,greater<P>> que;
  que.emplace(0,s);
  while (!que.empty()) {
    T dd; int v;
    tie(dd,v) = que.top(); que.pop();
    if (d[v] < dd) continue;
    for (auto e : G[v]) {
      if (d[e.first] > d[v]+e.second) {
        d[e.first] = d[v]+e.second;
        que.emplace(d[e.first],e.first);
      }
    }
  }
  return d;
}

int N,M,cap;
string src,dst;
string c[2][3010];
int d[3010];
string s[310];

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  while (cin >> N >> M >> cap, N) {
    vector<string> vs;
    cin >> src >> dst;
    vs.push_back(src);
    vs.push_back(dst);
    REP(i,N) {
      cin >> c[0][i] >> c[1][i] >> d[i];
      vs.push_back(c[0][i]);
      vs.push_back(c[1][i]);
    }
    vector<string> LPG;
    LPG.push_back(src);
    LPG.push_back(dst);
    REP(i,M) {
      cin >> s[i];
      vs.push_back(s[i]);
      LPG.push_back(s[i]);
    }
    UNI(LPG);
    UNI(vs);
    map<string,int> inv_vs,inv_LPG;
    vector<vector<pii>> G(vs.size());
    REP(i,vs.size()) inv_vs[vs[i]] = i;
    REP(i,LPG.size()) inv_LPG[LPG[i]] = i;
    REP(i,N) {
      int v = inv_vs[c[0][i]];
      int u = inv_vs[c[1][i]];
      G[v].emplace_back(u,d[i]);
      G[u].emplace_back(v,d[i]);
    }
    int dis[310][310];
    MINF(dis);
    REP(i,LPG.size()) {
      int v = inv_vs[LPG[i]];
      vector<int> dd = dijkstra<int>(G,v,INF);
      REP(j,LPG.size()) if (dd[inv_vs[LPG[j]]] <= cap*10) {
        dis[i][j] = dis[j][i] = dd[inv_vs[LPG[j]]];
      }
    }
    REP(k,LPG.size()) REP(i,LPG.size()) REP(j,LPG.size()) {
      CHMIN(dis[i][j],dis[i][k]+dis[k][j]);
    }
    int ans = dis[inv_LPG[src]][inv_LPG[dst]];
    cout << (ans == INF ? -1 : ans) << endl;
  }

  return 0;
}


Measured memory_bytes: 5000
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
using namespace std;

#define rep(i,n) for(int i = 0; i < (int)n; i++)
#define dbg(x) cerr << #x << " = " << (x) << endl;
typedef long long ll;
typedef vector<int> vi;

void solve_small(vi);

const int dy[] = {-1, -1, 1, 1}, dx[] = {-1, 0, 0, 1};
map<ll, int> M;
int n, num[5][5];

inline ll hash(const vi &v){
	ll res = 0;
	rep(i,v.size()) res *= 17, res += v[i];
	return res;
}
inline void push(const vi &v, int c, queue<pair<int,vi> > &q){
	ll h = hash(v);
	if(M.count(h) || c > 22) return;
	M[h] = c;
	q.push(make_pair(c+1, v));
}

void pv(const vi &v){
	int k = 0;
	rep(i,n) rep(j,i+1) cerr << v[k++] << (j==i?"\n":" ");
}

int main(){
	
	queue<pair<int,vi> > q;
	vi goal;
	int k = 0;
	rep(i,5) rep(j,i+1){
		num[i][j] = k;
		goal.push_back(++k);
	}
	push(goal, 0, q);
	
	while(!q.empty()){
		vi v = q.front().second;
		int c = q.front().first; q.pop();
		/*
		dbg(c);
		if(c == 2) pv(v);
		*/
		int idx = -1, y, x;
		for(y = 0; y < 5; y++) for(x = 0; x <= y; x++)
			if(v[++idx] == 1) goto OUT;
		OUT:;
		rep(d,4){
			int ny = y + dy[d], nx = x + dx[d];
			if(ny < 0 || nx < 0 || ny >= 5 || nx > ny) continue;
			swap(v[num[ny][nx]], v[idx]);
			push(v, c, q);
			swap(v[num[ny][nx]], v[idx]);
		}
	}
	
	int cs = 0;
	
	while(cin >> n, n){
		
		cout << "Case " << ++cs << ": ";
		
		vi v(n*(n+1)/2);
		k = 0;
		rep(i,n) rep(j,i+1) cin >> v[k++];
		if(n <= 4){
			solve_small(v);
			continue;
		}
		
		ll h = hash(v);
		if(M.count(h)){
			cout << M[h] << endl;
			continue;
		}
		
		queue<pair<int,vi> > q;
		set<ll> s;
		s.insert(h);
		q.push(make_pair(0, v));
		while(!q.empty()){
			v = q.front().second;
			int c = q.front().first; q.pop();
			
			int idx = -1, y, x;
			for(y = 0; y < 5; y++) for(x = 0; x <= y; x++)
				if(v[++idx] == 1) goto OUT2;
			OUT2:;
			rep(d,4){
				int ny = y + dy[d], nx = x + dx[d];
				if(ny < 0 || nx < 0 || ny >= 5 || nx > ny) continue;
				swap(v[num[ny][nx]], v[idx]);
				ll h = hash(v);
				if(M.count(h)){
					cout << M[h] + c + 1 << endl;
					goto END;
				}
				if(!s.count(h)) q.push(make_pair(c+1, v)), s.insert(h);
				swap(v[num[ny][nx]], v[idx]);
			}
		}
		END:;
	}
	return 0;
}

void solve_small(vi v){
	vi goal = v;
	sort(goal.begin(), goal.end());
	queue<pair<int,vi> > q;
	set<ll> s;
	ll ghash = hash(goal);
	q.push(make_pair(0, v));
	
	//rep(i,v.size())cerr<<v[i]<<(i==v.size()-1?"\n":" ");
	
	while(!q.empty()){
		v = q.front().second;
		int c = q.front().first; q.pop();
		ll h = hash(v);
		if(s.count(h)) continue;
		s.insert(h);
		if(h == ghash){
			cout << c <<endl; return;
		}
		/*
		cerr<<endl;
		int k = 0;
		rep(i,n) rep(j,i+1) cerr << v[k++] << (j==i?"\n":" ");
		*/
		int idx = -1, y, x;
		for(y = 0; y < 5; y++) for(x = 0; x <= y; x++)
			if(v[++idx] == 1) goto OUT3;
		OUT3:;
		rep(d,4){
			int ny = y + dy[d], nx = x + dx[d];
			if(ny < 0 || nx < 0 || ny >= n || nx > ny) continue;
			swap(v[num[ny][nx]], v[idx]);
			if(!s.count(hash(v))) q.push(make_pair(c+1, v));
			swap(v[num[ny][nx]], v[idx]);
		}
	}
}

Measured memory_bytes: 0
# https://atcoder.jp/contests/abc127/tasks/abc127_c



N, M = gets.split.map(&:to_i)
left_max = 1
right_min = N
M.times do |i|
  left, right = gets.split.map(&:to_i)
  left_max = [left, left_max].max
  right_min = [right, right_min].min
end

puts (left_max..right_min).size


Measured memory_bytes: 3836
#include <bits/stdc++.h>
#include <unordered_map>
typedef long long ll;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " \n"[i == n-1];}
#define printp(x,n) for(ll i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
const ll MOD = 1e9 + 7;
typedef pair<ll, ll> lpair;
ll f(ll n){
    return (n*n + 4) / 8;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll K,S;
    cin >> K >> S;
    ll ans = 0;
    rep(x,0,K+1){
        rep(y,0,K+1){
            if(S - x - y >= 0 && S - x - y <= K) ans++;
        }
    }
    print(ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,b,e) for(int i=(b);i<(e);++i)
#define RREP(i,b,e) for(int i=(b)-1;i>=e;--i)
#define rep(i,e) for(int i=0;i<(e);++i)

constexpr int MOD = 1000000007;
constexpr int INF = 1LL << 30;
constexpr long long LLINF = 1LL << 62;
constexpr double EPS = 1e-9;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
  }
} initializer;

template<typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (T &x : vec) is >> x;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[";
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (it != vec.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pa) {
  return os << "(" << pa.first << ", " << pa.second << ")";
}

template<typename Tuple, size_t N>
struct TuplePrinter {
  static void print(const Tuple &t) {
    TuplePrinter<Tuple, N-1>::print(t);
    cout << ", " << get<N-1>(t);
  }
};

template<typename Tuple>
struct TuplePrinter<Tuple, 1> {
  static void print(const Tuple &t) {
    cout << get<0>(t);
  }
};

template<typename... T>
ostream &operator<<(ostream &os, const tuple<T...> &tup) {
  os << "(";
  TuplePrinter<decltype(tup), sizeof...(T)>::print(tup);
  return os << ")";
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &se) {
  os << "{";
  for (auto it = se.begin(); it != se.end(); ++it) {
    if (it != se.begin()) os << ", ";
    os << *it;
  }
  return os << "}";
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &ma) {
  os << "{";
  for (auto it = ma.begin(); it != ma.end(); ++it) {
    if (it != ma.begin()) os << ", ";
    os << it->first << ": " << it->second;
  }
  return os << "}";
}

inline void print(void) { cout<<'\n'; }
template<class T> inline void print(const T &x) { cout<<x<<'\n'; }
template<class T, class... U> inline void print(const T &x, const U&... y) { cout<<x<<" "; print(y...); }
#define dump(...) cout<<#__VA_ARGS__<<": [L_"<<__LINE__<<"]"<<'\n'; print(__VA_ARGS__);cout<<'\n';

template<class T, class U>inline bool chmax(T &a, const U &b) { if(a<b){ a=b; return 1; } return 0; }
template<class T, class U>inline bool chmin(T &a, const U &b) { if(b<a){ a=b; return 1; } return 0; }


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

  set<int> ans;
  map<int, set<int>> lmap, rmap;

  vector<int> ltemp(10, 0), rtemp(10, 0);
  rep(i, n) {
    rep(j, 10) if (ltemp[j] == 1) lmap[i].emplace(j);
    ltemp[s[i]-'0'] = 1;
  }
  RREP(i, n, 0) {
    rep(j, 10) if (rtemp[j] == 1) rmap[i].emplace(j);
    rtemp[s[i]-'0'] = 1;
  }
  rep(i, n) {
    if (lmap[i].size() == 0 || rmap[i].size() == 0) continue;
    for (auto x : lmap[i]) for (auto y : rmap[i]){
      int t = x*100 + (s[i]-'0')*10 + y;
      ans.emplace(t);
    }
  }
  print(ans.size());

  return 0;
}

Measured memory_bytes: 34048
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	int n;
  	cin >> n;
  	map<string, int> m;
  	string s;
  	cin >> s;
  	string temp = s;
  	m[s]++;
  	bool ok = true;
  	for(int i = 0; i < n - 1; i++) {
    	cin >> s;
      	if (temp[temp.size() - 1] != s[0]) {
        	ok = false;
        }
      	m[s]++;
      	temp = s;
    }
  	if (!ok || m.size() != n) {
    	cout << "No";
    }
  	else cout << "Yes";
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int gcd(int a,int b)
{
    int t;
    if(b>a)
    {
        t=b;
        b=a;
        a=t;
    }
    while(t=a%b)
    {
        a=b;
        b=t;
    }
    return b;
}
int main(int argc, const char * argv[])
{
    int n,ans;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        if(i==0)
            ans=t;
        else
            ans=gcd(ans,t);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256