akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;


map<ll ,ll > res;
void prime_factor(ll n){
    for(ll i=2;i*i<=n;i++){
        while(n%i==0){
            res[i]++;
            n/=i;
        }
    }
    if(n!=1) res[n]++;
    return;
}

ll phi(ll n){
    ll phi=n;
    for(auto i:res){
        phi*=(i.first-1);
        phi/=i.first;
    }
    return phi;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n;
    cin>>n;
    prime_factor(n);
    cout<<phi(n)<<endl;
    return 0;
}


Measured memory_bytes: 3176
#include <iostream>
#include<algorithm>
#define int long long
using namespace std;
int re(int i){return (i/2)*2;}
int solve(int i,int j,int l){
    return re(i)+re(j)+re(l);
}
signed main(void){
    // Your code here!
    int i,ans,tmp,j,l;
    cin >>i>>ans>>tmp>>j>>l;
    int ans0=ans+solve(i,j,l);
    int ans1=ans;
    if(i>=1 and j>=1 and l>=1){
        ans1+=3+solve(i-1,j-1,l-1);
    }
    cout <<max(ans0,ans1)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
ll a[114514],b[114514],c[114514],d[114514];
ll cntA[114514],cntB[114514];
ll cnTA[114514],cnTB[114514];
signed main(){
	ll q;
	string s,t;
	cin>>s>>t>>q;
	rep(i,q)cin>>a[i]>>b[i]>>c[i]>>d[i];
	ll n=s.size(),m=t.size();
	rep(i,n){
		if(s[i]=='A'){
			cntA[i+1]=cntA[i]+1;
			cntB[i+1]=cntB[i];
		}
		else {
			cntA[i+1]=cntA[i];
			cntB[i+1]=cntB[i]+1;
		}
	}
	rep(i,m){
		if(t[i]=='A'){
			cnTA[i+1]=cnTA[i]+1;
			cnTB[i+1]=cnTB[i];
		}
		else {
			cnTA[i+1]=cnTA[i];
			cnTB[i+1]=cnTB[i]+1;
		}
	}
	rep(i,q){
		ll aa=cntA[b[i]]-cntA[a[i]-1];
		ll bb=cntB[b[i]]-cntB[a[i]-1];
		ll cc=cnTA[d[i]]-cnTA[c[i]-1];
		ll dd=cnTB[d[i]]-cnTB[c[i]-1];
		ll memoa=cc-aa,memob=dd-bb;
		if(abs(memoa-memob)%3==0)puts("YES");
		else puts("NO");
	}
}

Measured memory_bytes: 7680
#include <bits/stdc++.h>
using namespace std;
// define #Asukaminato is cute
#define ll long long
#define rep(i, m) for (int i = 0; i < (int)(m); i++)
const int inf = 1000000000; // 10^9 Ten to the power of nine.


int main(){
	int H,W,M[102][102]={0};
	bool A[102][102]={0};
	char s;
	cin>>H>>W;
	for(size_t i=0;i<=H+1;i++)for(size_t j=0;j<=W+1;j++){
		if(i==0||i==H+1||j==0||j==W+1)M[i][j]=H*W;
		else{
			cin>>s;
			A[i][j]= (s!='#');
			if(i==1&&j==1){M[i][j]=!A[i][j];}
			else M[i][j]=min(M[i-1][j]+(A[i-1][j]&&!A[i][j]),M[i][j-1]+(A[i][j-1]&&!A[i][j]));
		}}
	
	cout<<M[H][W]<<endl;
	return 0;}

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

bool koike(const string &S, const string &T) {
    set<char> yuriko;
    for (auto c : S) yuriko.insert(c);
    for (auto c : T) if (!yuriko.count(c)) return true;
    return false;
}

int main() {
    string S, T;
    cin >> S >> T;
    int N = S.length(), M = T.length();
    if (koike(S, T)) { printf("-1\n"); return 0; }
    vector<vector<int>> A(30);
    vector<int> use(30, 0);
    for (int i = 0; i < N; i++) {
        int k = S[i] - 'a';
        A[k].push_back(i+1);
    }
    
    long long ans = 0;
    long long now = 0;
    for (int i = 0; i < M; i++) {
        int k = T[i] - 'a';
        int ng = use[k]-1, ok = (int)A[k].size();
        while (abs(ok-ng) > 1) {
            int mid = (ok+ng)/2;
            if (A[k][mid] > now) ok = mid;
            else ng = mid;
        }
        if (ok == A[k].size()) {
            for (auto &u : use) u = 0;
            ans += (N - now); now = 0; ok = 0;
        }
        ans += (A[k][ok] - now);
        now = A[k][ok];
        use[k]++;
        //cout << now << " " << ans << endl;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1216
#include<stdio.h>
int main(){
	int a,b,i,j;
	while(1){
		scanf("%d %d",&a,&b);
		if(a==b && a==0) break;
		for(i=0;i<a;i++){
			for(j=0;j<b;j++){
				if(i%2==0){
					if(j%2==0){
						printf("#");
					}else{
						printf(".");
					}
				}else{
					if(j%2==0){
						printf(".");
					}else{
						printf("#");
					}
				}
			}
			printf("\n");
		}
		printf("\n");
	}
}


Measured memory_bytes: 2048
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int x;
  cin >> x;
  vector<bool> dp(x+1);
  dp[0] = true;
  for (int i = 100; i <= x; i++) {
    for (int j = 0; j <= 5; j++) {
      if (dp[i-j-100]) {
        dp[i] = true;
        break;
      }
    }
  }
  if (dp[x])
    cout << 1 << endl;
  else
    cout << 0 << endl;
  return 0;
}

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

using namespace std;
#define all(x) (x).begin(), (x).end()
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<bool>> vvb;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef pair<int,int> pii;
typedef long long ll;
void debugF(ostream &os) {os << endl;}
template <typename Head, typename... Tail>
void debugF(ostream &os, Head H, Tail... T) { os << " " << H; debugF(os, T...); }
#define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debugF(cout, __VA_ARGS__)
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); os << (i>0 ? " ":"") << v[i++]); os << "\n"; return os;}

const ll mod = 998244353;

ll expMod(ll a, ll b, ll mod){
    ll ans = 1;
    while(b){
        if(b&1) ans = (ans*a)%mod;
        a = (a*a)%mod;
        b >>= 1;
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n , k, m;
    cin >> n >> m >> k;
    ll cmb = 1; // C(n-1,i)
    ll ans = 0;
    
    for(int i=0;i<=k;i++){
        ll cr = (m*expMod(m-1, n-i-1,mod))%mod;
        cr = (cr*cmb)%mod;
        ans += cr;
        ans %= mod;

        //C(n-1,i+1) = C(n-1,i) * (n-1 - (i+1) + 1) / (i+1)
        cmb = (cmb*(n-1-(i+1)+1))%mod;
        cmb *= expMod(i+1, mod-2, mod);
        cmb %= mod;
    }

    cout << ans << "\n";

    return 0;
}

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

int n,ans=0;
int a[100005],b[100005],c[100005];

int p[100005][205];

signed main()
{
	cin>>n;
	n++;
	for (int i=1;i<=n;i++)  cin>>a[i];
	
	b[1]=1,c[n]=a[n];
	for (int i=2;i<=n;i++)  b[i]=(b[i-1]-a[i-1])*2;
	for (int i=n-1;i>=1;i--)  c[i]=c[i+1]+a[i];
	for (int i=1;i<=n;i++)  ans+=min(b[i],c[i]);
	for (int i=1;i<=n;i++)
	{
		if (a[i]>b[i])  return cout<<-1<<endl,0;
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 5932
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String S = sc.next();

		if(S.matches("2017.*")) {
			System.out.println(S.replace("2017", "2018"));
		}
		else{
			System.out.println(S);
		}
	}
}


Measured memory_bytes: 22868
#include<iostream>
#include<algorithm>
#define rep(i,s,n) for(int i=s;i<n;i++)
#define Z 20000
using namespace std;
int d[Z+1];
int main(){
	int n,m,k,r,l;
	while(true){
		cin>>n>>k>>m>>r;
		if(!(n+m+k+r))break;
		rep(i,0,Z)d[i]=0;
		k=1,l=n;
		rep(i,0,Z)d[i]+=k/l,k%=l,k*=10;
		if(m)rep(i,1,n){k=1,l=i*n;rep(j,0,Z)d[j]+=k/l,k%=l,k*=10;}
		for(int i=Z;i>0;i--)d[i-1]+=d[i]/10,d[i]%=10;
		cout<<d[0]<<".";
		rep(i,1,r+1)cout<<d[i];
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 3032
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,j,cnt,a,b;
    char ar[105][105],c;
    while(cin>>a>>b)
    {
        for(i=1; i<=a; i++)
        {
            for(j=1; j<=b; j++)
            {
                cin>>c;
                ar[i][j]=c;

            }
        }
        for(i=1;i<=2*a;i++)
        {
            for(j=1;j<=b;j++)
            {
                printf("%c",ar[(i+1)/2][j]);
            }
            printf("\n");
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define int long long
#define quickie ios_base::sync_with_stdio(false); cin.tie(NULL);
#define rep(i, a, b) for(int i=a; i<b; i++)
#define rep1(i, a, b) for(int i=a; i<=b; i++)
#define repp(i, a, b) for(int i=b-1; i>=a; i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define db double
#define mi map<int, int>
#define vi vector<int>
#define MI(x) power(x, mod-2)
#define test int t; cin >> t;
#define mod 1000000007LL
#define pi 3.141592653589
//#define mod 998244353 
using namespace std;

int power(int x, int y) ;
int gcd(int a, int b) ;

/*___________________________TEMPLATE END______________________________*/

signed main() {
    quickie
    int n ;
    cin >> n ;
    int a[n] ;
    rep(i, 0, n) {
        cin >> a[i] ;
    }
    sort(a, a+n) ;
    int p = a[0] ;
    if(p == 0) cout << 0 << "\n" ;
    else {
        int f = 0 ;
        rep(i, 1, n) {
            p *= a[i] ;
            if(p <= 0 || p > 1000000000000000000) {
                f = 1 ;
                break ;
            }
        }
        if(f == 1) cout << "-1\n" ;
        else cout << p << "\n" ;
    }
} 

int power(int x, int y) {
    int res = 1; x %= mod;
    while (y > 0) {
        if (y & 1)
            res = (res*x) % mod;
        y = y>>1;
        x = (x*x) % mod;
    }
    return res%mod;
}

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


Measured memory_bytes: 4452
#include<bits/stdc++.h>
#define re register
inline int read(){
	re int t=0;
	re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0'){
		t=(t<<3)+(t<<1)+v-48;
		v=getchar();
	}
	return t;
}
using namespace std;
int n,p[2002],x,y;
signed main(){
	n=read();x=read();y=read();
	for(re int i=1;i<=n;++i)for(re int j=i+1;j<=n;++j)++p[min(j-i,abs(i-x)+1+abs(j-y))];
	for(re int i=1;i<n;++i)printf("%d\n",p[i]);
}

Measured memory_bytes: 256
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

Bsize = 700

def Mo_argsort(LR):
    L = LR[:, 0]
    R = LR[:, 1]
    key1 = L // Bsize
    key2 = np.where(key1 & 1, -R, R)
    key = (key1 << 32) + key2
    return np.argsort(key)

def main(A, LR):
    N = len(A)
    Q = len(LR)
    ind = Mo_argsort(LR)
    count = np.zeros(N + 1, np.int64)
    ans = 0

    def add(x):
        nonlocal ans
        if not count[x]:
            ans += 1
        count[x] += 1

    def rem(x):
        nonlocal ans
        count[x] -= 1
        if not count[x]:
            ans -= 1

    answers = np.empty(Q, np.int64)
    nl, nr = 0, 0
    for i in ind:
        l, r = LR[i]
        l -= 1
        # 区間 [l, r) に対する計算
        while nl > l:
            nl -= 1
            add(A[nl])
        while nr < r:
            add(A[nr])
            nr += 1
        while nl < l:
            rem(A[nl])
            nl += 1
        while nr > r:
            nr -= 1
            rem(A[nr])
        #  答を求めて ans[i] に格納する
        answers[i] = ans
    return answers

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i4 = numba.int32
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    Mo_argsort = cc_export(Mo_argsort, (i8[:,:],))
    main = cc_export(main, (i8[:], i8[:, :]))
    cc.compile()

from my_module import main

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64).reshape(Q, 2)

ans = main(A, LR)
print('\n'.join(map(str, ans.tolist())))


Measured memory_bytes: 102108
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;++i){
		cin>>a[i];
		if(a[i]%2==0){
			if(a[i]%3!=0 && a[i]%5!=0){
				cout<<"DENIED";
				return 0;
			}
		}
	}
	cout<<"APPROVED";
	return 0;
} 

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

using namespace std;

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

    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    bool exists = false;
    for (int i = 0; i < n && !exists; i++) {
        for (int j = i; j < n && !exists; j++) {
            vector<int> sorted(n);
            for (int k = 0; k < n; k++) {
                sorted[k] = k + 1;
            }

            int w = sorted[i];
            sorted[i] = sorted[j];
            sorted[j] = w;

            bool equals = true;
            for (int k = 0; k < n && equals; k++) {
                if (p[k] != sorted[k]) {
                    equals = false;
                }
            }

            if (equals) {
                exists = true;
            }
        }
    }

    cout << (exists ? "YES" : "NO") << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){

  int N;
  scanf("%d",&N);
  char S[N];
  scanf("%s",S);
  int i, count=0;
  for(i=0;i<N;i++){
    if(S[i]=='A'){
      if(S[i+1]=='B'){
	if(S[i+2]=='C'){
	  count+=1;
	}
      }
    }
  }
  printf("%d",count);

  return 0;
}


Measured memory_bytes: 128
include Math
line = gets
x_price_per_liter = line.to_i

line = gets
y_basic_price = line.to_i

line = gets
y_basic_limit = line.to_i

line = gets
y_external_price_per_liter = line.to_i

line = gets
joi_used_amout = line.to_i

x_price = joi_used_amout * x_price_per_liter

y_price = 0
if joi_used_amout > y_basic_limit
  external_liter = joi_used_amout - y_basic_limit
  y_price = y_basic_price + external_liter * y_external_price_per_liter
else
  y_price = y_basic_price
end
if x_price < y_price
  puts x_price
else
  puts y_price
end

Measured memory_bytes: 8636
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
# define ll int64_t
# define str string
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define PI 3.141592653589793
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
using namespace std;



#define INF 2000000000
#define MAX_V 10



bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<ll,ll> a,pair<ll,ll> b){
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll modpow(ll a,ll n,ll mod1) {
    ll res=1;
    while(n>0){
        if(n&1) res=res*a%mod1;
        a = a*a%mod1;
        n >>= 1;
    }
    return res;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) x*=i;
    return x;
}

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

ll func(ll a,ll b,ll& ans_x,ll& ans_y){
    if(b == 0){
        ans_x = 1;
        ans_y = 0;
        return a;
    }else{
        ll ret = func(b,(a%b),ans_y,ans_x);
        ans_y -= (a/b)*ans_x;
        return ret;
    }
}

vector<bool> IsPrime;

ll sieve(ll max){
    ll sum=0;
    if(max+1 > IsPrime.size()){     // resizeで要素数が減らないように
        IsPrime.resize(max+1,true); // IsPrimeに必要な要素数を確保
    }
    IsPrime[0] = false; // 0は素数ではない
    IsPrime[1] = false; // 1は素数ではない

    for(ll i=2; i<=max; ++i) // 0からsqrt(max)まで調べる
        if(IsPrime[i]) {
            sum++;
            for(size_t j=2; i*j<=max; ++j) IsPrime[i*j] = false;
        }
    return sum;
}



ll lcm(ll a,ll b){
   return a/gcd(a,b)*b;
}
const ll MAX = 5100000;
const ll MOD = 1000000007;
 
ll fac[MAX], finv[MAX], inv[MAX];
 
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

using graph = vector<vector<ll>>;
pair<pair<ll,ll>,ll> p[100010];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    while(scanf("%d",&n)!=EOF){
        cout<<sieve(n)<<endl;
    }
    return 0;
}



Measured memory_bytes: 3320
x,n, = map(int,input().split())
p = list(map(int,input().split()))

i = 0
ans = []
flag = 0
while True:
    if (x + i) not in p:
        ans += [x+i]
        flag = 1
    if (x - i) not in p:
        ans += [x-i]
        flag = 1
    if flag == 0:
        i += 1
    else:
        break

print(min(ans))


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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 10000000000
#define MOD 1000000007
using ll = long long;
using pint = pair<int,int>;
using pll = pair<ll,ll>;
using Graph = vector<vector<int>>;

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


Measured memory_bytes: 3640
#include <iostream>

using namespace std;

int bubbleSort(int A[], int N) {
  bool flag = true;
  int swapn = 0;

  while (flag) {
    flag = false;
    for (int i = N - 1; i > 0; i--) {
      if (A[i] < A[i - 1]) {
        int swap = A[i];
        A[i] = A[i - 1];
        A[i - 1] = swap;
        flag = true;
        swapn++;
      }
    }
  }

  return swapn;
}

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

  int swapn = bubbleSort(A, N);

  for (int i = 0; i < N; i++) {
    if (i == N - 1) {
      cout << A[i] << endl;
    } else {
      cout << A[i] << " ";
    }
  }
  cout << swapn << endl;

  return 0;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
 
int main() {
	int n;
	cin >> n;
	double value[100];
	rep(i, n) cin >> value[i];
	sort(value, value+n);

	double ans = (value[0] + value[1]) / 2;
	for (int i = 2; i < n; i++) {
		ans = (ans + value[i]) / 2;
	}
	cout << setprecision(6);
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
struct graph{
    int ob;
    int di;
};
int main(){
    int N;
    cin >> N;
    vector<int> a(N), b(N), c(N);
    vector<vector<graph>> d(N + 1, vector<graph>(0));
    for (int i = 1; i <= N - 1; i++){
        cin >> a.at(i) >> b.at(i) >> c.at(i);
        graph g = {b.at(i), c.at(i)}, h = {a.at(i), c.at(i)};
        d.at(a.at(i)).push_back(g);
        d.at(b.at(i)).push_back(h);
    }
    
    
    int Q, K;
    cin >> Q >> K;
    vector<int> x(Q + 1), y(Q + 1);
    for (int i = 1; i <= Q; i++){
        cin >> x.at(i) >> y.at(i);
    }
    
    vector<int64_t> KY(N + 1, INF);
    KY.at(0) = 0;
    d.at(0).push_back({K, 0});
        stack<int> q;
        
        
        q.push(0);
        while (!q.empty()){
            int st = q.top();
            q.pop();
            //cout << "st " << st << endl;
            
            for(int i = 0; i < d.at(st).size(); i++){
                int st_1 = d.at(st).at(i).ob;
                int ky_1 = d.at(st).at(i).di;
                if (KY.at(st_1) != INF) continue;
                else{
                    q.push(st_1);
                    KY.at(st_1) = KY.at(st) + ky_1;
                    //cout << "KYst_1 " << KY.at(st_1) << " KYst " << KY.at(st) << endl;
                }
            }
        }
    
    for (int i = 1; i <= Q; i++){
        cout << KY.at(x.at(i)) + KY.at(y.at(i)) << endl;
    }
    
}



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

int main(void){
    int n ;
    cin >> n ;
    char s[n+2] ;
    cin >> s ;
    int ans = n ;
    for (int i=1; i<n; i++){
        if (s[i]==s[i-1]){
            ans--;
        }
    }
    cout << ans << endl ;
}

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

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

    for(int a,q,i=1; i <=9; i++) {
        q = N / i;
        a = N % i;
        if(a == 0 && 1 <= q && q <= 9) {
            cout << "Yes" << endl;
            return 0;
        } 
    }
    cout << "No" << endl;
    return 0;
}

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

int N, D;
int X, Y;
long double l;
int c = 0;

int main(){
    cin >> N >> D;
    for(int i = 0; i < N; i++){
        cin >> X >> Y;
        l = pow(pow(X, 2)+pow(Y, 2), 0.5);
        //cout << l << endl;
        if(l <= D){
            c++;
        }
    }

    cout << c << endl;
    return 0;
}

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::bitset;

#define rep(i,n)    for(int i=0; i<(int)n; i++)
#define reps(i,s,e) for(int i=s; i<(int)e; i++)
#define coutd(i) cout << std::fixed << std::setprecision(i)
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;

template<class T>
using Graph = vector<vector<T>>;

const int INT_BIG = 1<<28;

int main() {
    int H, W;
    cin >> H >> W;
    int N;
    cin >> N;

    int xIndex = 0;
    int yIndex = 0;
    Graph<int> canvas(W, vint(H, 0));
    rep(i, N) {
        int num;
        cin >> num;
        rep(j, num) {
            canvas[xIndex][yIndex] = i+1;
            if (yIndex % 2 == 0) {
                xIndex++;
            } else {
                xIndex--;
            }
            if (xIndex == W) {
                xIndex = W - 1;
                yIndex++;
            } else if (xIndex == -1) {
                xIndex = 0;
                yIndex++;
            }
        }
    }

    rep(i, H) {
        rep(j, W) {
            if (j == 0) {
                cout << canvas[j][i];
            } else {
                cout << " " << canvas[j][i];
            }
        }
        cout << endl;
    }
}

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

string S;

int main() {
    cin >> S;
    long N = S.length();
    int odd = 0, even = 0;
    for (int i = 0; i < N; i++) {
        if (i & 1) {
            if (S[i] == '0') {
                odd++;
            } else {
                even++;
            }
        } else {
            if (S[i] == '1') {
                odd++;
            } else {
                even++;
            }
        }
    }
    cout << min(even, odd) << endl;
}





Measured memory_bytes: 512
N,M = map(int,(input().split()))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

l = make_divisors(M)

for i in l:
    if M//i >=N:
        print(i)
        break

Measured memory_bytes: 38640
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
ll N;
vector<ll> vs;
map<ll,int> mp;
vector<int> G[1<<19];
int dp[1<<19];
int I;
void dfs(ll x){
	int id=I;
	mp[x]=id;
	for(ll v:vs){
		if(v>x) break;
		if(x%v==0){
			ll nx=x/v;
			if(!mp.count(nx)){
				I++;
				dfs(nx);
			}
			G[mp[nx]].pb(id);
		}
	}
}
int main(){
	cin>>N;
	rep1(i,18){
		rep(j,1<<i){
			ll v=0;
			rep(k,i){
				if((j>>k)&1) v=v*10+2;
				else v=v*10+8;
			}
			vs.pb(v);
		}
	}
	sort(all(vs));
	dfs(N);
	if(!mp.count(1)){
		puts("-1");
		return 0;
	}
	rep(i,1<<19) dp[i]=-1e9;
	dp[mp[1]]=0;
	for(auto p:mp){
		ll x=p.fs;
		int v=p.sc;
		for(int u:G[v]) chmax(dp[u],dp[v]+1);
	}
	if(dp[0]==0) dp[0]=-1;
	cout<<dp[0]<<endl;
}

Measured memory_bytes: 21432
import sys
import bisect


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()
    count = 0
    # for i in range(N - 2):
    #     for j in range(i + 1, N - 1):
    #         if L[i] == L[j]:
    #             continue
    #         a = bisect.bisect_right(L[j + 1:], L[j])
    #         b = bisect.bisect_left(L[j + 1:], L[i] + L[j])
    #         count += b - a

    for j in range(1, N-1):
        rem = L[j+1:]
        for i in range(j):
            if L[i] == L[j]:
                break
            a = bisect.bisect_right(rem, L[j])
            b = bisect.bisect_left(rem, L[i] + L[j])
            count += b - a


    print(count)


if __name__ == "__main__":
    main()


Measured memory_bytes: 73572
#include<stdio.h>
int main(void)
{
	int a,b,c,d,p,x,y,n,m;
	scanf("%d %d %d %d %d",&a,&b,&c,&d,&p);
	x=0;
	y=0;
	x=a*p;
	if(p<c){
		y=b;
	}
	else{
		y=(p-c)*d+b;
	}
	if(x<y){
		printf("%d\n",x);
	}
	else{
		printf("%d\n",y);
	}
	return 0;
}


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

int main(){
	string s, t;
	cin >> s >> t;
	vector<int> sc(26, -1), tc(26, -1);
	rep(i, s.size()){
		int ss = s[i] - 'a';
		int tt = t[i] - 'a';
		if(sc[ss] == -1){
			sc[ss] = tt;
		}else{
			if(sc[ss] != tt){
				cout << "No" << endl;
				return 0;
			}
		}
		
		if(tc[tt] == -1){
			tc[tt] = ss;
		}else{
			if(tc[tt] != ss){
				cout << "No" << endl;
				return 0;
			}
		}
	}
	
	cout << "Yes" << endl;
	
	return 0;
}

Measured memory_bytes: 776
import java.util.*;

public class Main {
    static long mod = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long r = sc.nextLong();
        long d = sc.nextLong();
        long x = sc.nextLong();
        for (int i = 0; i < 10; ++i) {
            x = r * x - d;
            System.out.println(x);
        }

    }
}


Measured memory_bytes: 21972
import sys
A,B = [int(n) for n in input().split()]
# N = int(input())
# S = str(input())
# T = str(input())
ans = 0
for s in range(A,B+1):
    s = str(s)
    rs = s[::-1]
    if(s == rs):
        ans +=1
print(ans)


Measured memory_bytes: 2940
n = int(input())
s = input()
e = [0]*n
w = [0]*n
ans = float("inf")
for i in range(n-1):
  if s[i] == "W":
    e[i+1] += 1
  e[i+1] += e[i]

for i in range(1,n):
  if s[n-i] == "E":
    w[n-i-1] += 1
  w[n-i-1] += w[n-i]

print(min([e[i] + w[i] for i in range(n)]))  



Measured memory_bytes: 39232
#include <iostream>
#include <iomanip>
#include <string>
#include <limits.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <cstdlib>

using namespace std;

int main(int argc, char* argv[]){
    char alpha[] = "abcdefghijklmnopqrstuvwxyz";
    string s;
    cin >> s;
    // cout << "s=" << s << endl;
    bool check[26]={};

    for(int i=0; i<26; i++){
    	for(int j=0; j<s.length(); j++){
    		if(alpha[i]==s[j]){
    			check[i]=1;
    			// cout << "check[" << alpha[i] << "]=1"<< endl;
    		}
    	}
    	if (check[i]==0){
    		cout << alpha[i] << endl;
    		break;
    	}
    }

    if(check[25]==1){
    	cout << "None" << endl;
    }

    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <stdlib.h>
using namespace std;

int main(){
  int n, l;
  cin >> n >> l;
  vector<int> hoge(n);
  int minn = 200000000;
  // int mini;
  for (int i = 0; i < n; i++){
    hoge[i] = l + (i + 1) - 1;
    if(abs(minn) > abs(l + (i + 1) - 1)){
      minn = l + (i + 1) - 1;
    }
  }
  
  int sum = accumulate(hoge.begin(), hoge.end(), 0);
  // cout << minn << endl;
  cout << sum - minn << endl;
  // int min = 200000000;
  // for (int i = 0; i < n; i++){
  //   abs(sum - hoge[i])
  // }
  
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  char str[3];
  for(int i=0; i<3; i++){
    scanf("%s",str);
  }
  if((str[0]=='A')&&(str[1]=='A')&&(str[2]=='A')){
    printf("No");
  }else{
    if((str[0]=='B')&&(str[1]=='B')&&(str[2]=='B')){
      printf("No");
    }else{
    printf("Yes");
  }
  }
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn=1e5+100;
const int mod=1e9+7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, m;
string ans[maxn];
vector<pii>v[maxn];
int nlen(int num)
{
    return num?1+nlen(num/10):0;
}
string tostr(int num)
{
    stringstream ss;
    ss<<num;
    string s;
    ss>>s;
    return s;
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int p, y;
        cin>>p>>y;
        v[p].pb({y, i});
    }
    for(int i=1; i<=n; i++)
    {
        sort(all(v[i]));
        string f=tostr(i);
            while(sz(f) < 6)
                f="0"+f;
        for(int j=0; j<sz(v[i]); j++)
        {
            string s=tostr(j+1);
            while(sz(s) < 6)
                s="0"+s;
            ans[v[i][j].y]=f+s;
        }
    }
    for(int i=1; i<=m; i++)
        cout<<ans[i]<<"\n";
    return 0;
}


Measured memory_bytes: 12416
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <list>
#include <cmath>
#include <numeric>
#include <sstream>
#include <iomanip>
using ll = long long;
using namespace std;
#define INF 999999999

int main()
{
    int H, W;
    int h, w;
    cin >> H >> W >> h >> w;
    cout << (H - h) * (W - w) << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


S = li()
if len(S) == 2:
    print(''.join(S))
else:
    S.reverse()
    print(''.join(S))

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <sstream>
#define INF 2000000000
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define ll long long
#define PL pair<long long, long long>
#define P pair<int,int>
#define mk make_pair
#define en endl
#define WHITE 0
#define BLACK 2
#define GRAY 1
#define RE return 0
#define int ll

int now[30];
int inde=0;
int a;

void solve(int sum,int t){
//  cout<<"  sum:  "<<sum<<"   t:  "<<t<<en;
  if(sum==a){
    cout<<now[0];
    for(int i=1;i<inde;i++){
      cout<<" "<<now[i];
    }
    cout<<en;
    return;
  }
  for(int i=t;i>=1;i--){
    if(sum+i<=a){
      now[inde++]=i;
      solve(sum+i,i);
      inde--;
    }
  }
  return ;
}
signed main(){
  while(cin>>a&&a){
    solve(0,a);
  }
}



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

using namespace std;
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))

int main()
{
  int n, data;
  cin >> n;
  int i = 0;
  int a[100];
  while (cin >> data)
  {
    a[i] = data;
    i++;

    if (i == n)
    {
      break;
    }
  }

  std::sort(a, a + n);

  int alice, bob = 0;
  i = 0;
  for (const int *p = a + n; p != a; --p)
  {
    if (i % 2 == 0)
    {
      alice += *(p - 1);
    }
    else
    {
      bob += *(p - 1);
    }
    i++;
  }

  cout << alice - bob << endl;
  return 0;
}

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

void bad(){
  cout<<"Impossible\n";
  exit(0);
}

int A[111];

int main(){
  int N; cin>>N;
  vector<vector<int> > V(N+1);
  rep(i,N){
    cin>>A[i];
    V[A[i]].push_back(i);
  }
  vector<vector<int> > G(N);
  int sum=0;
  bool first=1;
  rep(i,N) if(V[i].size()){
    int n=V[i].size();
    sum+=n;
    if(sum!=N&&sum!=0&&V[i+1].size()==0) bad();
    if(first){
      rep(j,n-1){
        int v=V[i][j], u=V[i][j+1];
        G[v].push_back(u);
        G[u].push_back(v);
      }
      first=0;
    }else{
      int ind=0,nn=V[i-1].size();
      rep(j,n){
        int v=V[i][j], u=V[i-1][ind];
        G[v].push_back(u);
        G[u].push_back(v);
        if(ind<=nn-2) ind++;
      }
    }
  }

  rep(i,N){
    queue<pair<int,int> > q;
    int use[N]={};
    q.push({i,0});
    int ma=0;
    while(q.size()){
      pair<int,int> P=q.front(); q.pop();
      int v=P.first, d=P.second;
      use[v]=1;
      ma=max(ma,d);
      rep(j,G[v].size()) if(use[G[v][j]]==0){
        q.push({G[v][j],d+1});
      }
    }
    if(ma!=A[i]) bad();
  }
  cout<<"Possible\n";
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {

        ModScanner ms = new ModScanner();
        OutputStream outputStream = System.out;
        PrintWriter out = new PrintWriter(outputStream);
        int n = ms.nextInt();
        int w = ms.nextInt();
        int[] wt = new int[n];
        int[] val = new int[n];
        for (int i = 0; i < n; i++) {
            wt[i] = ms.nextInt();
            val[i] = ms.nextInt();
        }

        long[][] dp = new long[n + 1][w + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= w; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (j >= wt[i-1]) {
                    dp[i][j] = Math.max(dp[i][j], val[i-1] + dp[i-1][j - wt[i-1]]);
                }
            }
        }

        out.println(dp[n][w]);
        out.close();
    }


}

class ModScanner {

    BufferedReader br;
    StringTokenizer st;

    public ModScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String nextToken() throws Exception {
        while (st == null || !st.hasMoreElements()) {
            st = new StringTokenizer(br.readLine());

        }
        return st.nextToken();
    }

    String nextString() throws Exception {
        return br.readLine();
    }


    int nextInt() throws Exception, Exception {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }

}


Measured memory_bytes: 138136
const MOD: usize = 998244353;
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner(s.lock());
    let n: usize = sc.read();
    let d: Vec<usize> = sc.vec(n);
    if d[0] != 0 {
        println!("0");
        return;
    }
    let mut count = vec![0; n];
    for d in d.into_iter() {
        count[d] += 1;
    }
    if count[0] != 1 {
        println!("0");
        return;
    }

    while let Some(tail) = count.pop() {
        if tail != 0 {
            count.push(tail);
            break;
        }
    }

    let mut ans = 1;
    for i in 1..count.len() {
        let prev = count[i - 1];
        let next = count[i];
        let mut p = 1;
        for _ in 0..next {
            p = (p * prev) % MOD;
        }
        ans *= p;
        ans %= MOD;
    }
    println!("{}", ans);
}

pub struct Scanner<R>(R);

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 6396
import numpy as np
 
N=int(input())
T=list(map(int,input().split()))
V=list(map(int,input().split()))

MAX_V=[0]
for t,v in zip(T,V):
  MAX_V[-1]=min(MAX_V[-1],v)
  for _ in range(t*2):
    MAX_V.append(v)
  #print(MAX_V)
  #print(len(MAX_V))

timelistsize=len(MAX_V)
REAL_V=[0]*timelistsize

#スピードが加速する部分の速度を表現
for i in range(1,timelistsize):
  REAL_V[i]=min(REAL_V[i-1]+0.5,MAX_V[i])

#終了位置から同じようにして減速部分の速度を表現
REAL_V[-1]=0
for i in range(timelistsize-1,0,-1):
  REAL_V[i-1]=min(REAL_V[i]+0.5,REAL_V[i-1])


#0.5秒刻みの速度ができているので、0.5を高さ,0.5秒ごとの速度を上辺,下辺とした台形面積を足す
answer=0
for i in range(timelistsize-1):
  answer+=((REAL_V[i]+REAL_V[i+1])*0.5/2)
print(answer)

'''
tsum=np.sum(t)
print(tsum)
 
Ruisekit=[t[0]]
 
for i in range(1,N):
  Ruisekit.append(t[i]+Ruisekit[i-1])
  
print(Ruisekit)
 
 
 
 
downstart=[]
 
for i in range(N-1):
  if v[i]>v[i+1]:
    downstart.append(t[i]-(v[i]-v[i+1]))
 
print(downstart)
 
velocity=0
downindex=0
 
if downstart:
  nextdownstarttime=downstart[downindex]
 
state='up'
upstarttime=0
upstartspeed=0
answer=0
maxspeed=v[0]
maxspeedindex=0
 
for time in range(1,tsum+1):
  if state=='up':
    velocity+=1
    #print('velocity:',velocity)
    #print('time',time)
  if state=='down':
    velocity-=1
  if time==nextdownstarttime:
    if state=='plane':
      answer+=(time-planestarttime)*speed
    state='down'
    print(state)
    downstarttime=time
    downstartspeed=speed
    downindex+=1
    if downindex<len(downstart):
      nextdownstarttime=downstart[downindex]
  if time==Ruisekit[maxspeedindex]:
    maxspeedindex+=1
    if maxspeedindex<len(v):
      maxspeed=v[maxspeedindex]
  if velocity==maxspeed and state!='plane':
    if state=='up':
      answer+=(time-upstarttime)*(velocity-upstartspeed)*0.5
      answer+=(time-upstarttime)*upstartspeed
    if state=='down':
      answer+=(time-downstarttime)*(downstartspeed-velocity)*0.5
      answer+=(time-downstarttime)*downstartspeed
    
    state='plane'
    planestarttime=time
    speed=velocity
    
  print(answer,time,maxspeed,velocity,state)
''' 

Measured memory_bytes: 13000
from collections import deque

h,w = map(int,input().split())
F = [input() for _ in range(h)]
direct = [[0,1],[1,0]]
que = deque()
que.append([0,0])
INF = 10**5
dp = [[INF]*w for _ in range(h)]


dp[0][0] = 0

while len(que)>0:  
  y,x = que.popleft()    
  for dy,dx in direct:    
    ny = y+dy
    nx = x+dx
    if (0 <= nx < w) and (0 <= ny < h):
      if F[ny][nx] == F[y][x]:         
        if dp[ny][nx] > dp[y][x]:
          dp[ny][nx] = dp[y][x]
          que.append([ny,nx])
      else:                
        if dp[ny][nx] > dp[y][x] + 1 :        
          dp[ny][nx] = dp[y][x] + 1          
          que.append([ny,nx])   


ans = dp[-1][-1]//2
if F[0][0] == '#' or F[-1][-1] == '#':
  ans += 1

print(ans)

Measured memory_bytes: 41712
n = int(input())
xy=[list(map(int,input().split())) for i in range(n)]
import math
def calc(x1, y1, x2, y2, x3, y3):
    try:
        d = 2 * ((y1 - y3) * (x1 - x2) - (y1 - y2) * (x1 - x3))
        x = ((y1 - y3) * (y1 ** 2 - y2 ** 2 + x1 ** 2 - x2 ** 2) - (y1 - y2) * (y1 ** 2 - y3 ** 2 + x1 ** 2 - x3 ** 2)) / d
        y = ((x1 - x3) * (x1 ** 2 - x2 ** 2 + y1 ** 2 - y2 ** 2) - (x1 - x2) * (x1 ** 2 - x3 ** 2 + y1 ** 2 - y3 ** 2)) / -d
        r2 = (x - x1) ** 2 + (y - y1) ** 2
    except:
        return 0,0,-1
    else:
        return x,y,r2
def check(cx,cy,r2):
    for tmp in xy:
        x,y=tmp
        if (x-cx)**2 + (y-cy)**2 > r2:
            return False
    return True

ans=float("inf")
eps=10**(-5)
for i in range(n):
    for j in range(i+1,n):
        x1,y1=xy[i]
        x2,y2=xy[j]
        cx=(x1+x2)/2
        cy=(y1+y2)/2

        r2=(cx-x1)**2+(cy-y1)**2
        if check(cx,cy,r2+eps):
            ans=min(ans,math.sqrt(r2))

for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            x1,y1=xy[i]
            x2,y2=xy[j]
            x3,y3=xy[k]
            cx,cy,r2=calc(x1, y1, x2, y2, x3, y3)
            if 0 < r2 and check(cx,cy,r2+eps):
                ans=min(ans,math.sqrt(r2))
print(ans)

Measured memory_bytes: 48216
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int cnt[10][10];
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
        string s = to_string(i);
        cnt[s[0]-'0'][s.back()-'0']++;
    }
    ll sum = 0;
    for(int i = 1; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            sum += (ll)cnt[i][j] * cnt[j][i];
        }
    }
    cout << sum << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c,x;
    cin >> a >> b >> c >> x;
    int ans = 0;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                if(500*i+100*j+50*k==x)ans++;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


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

    const ll INF=1LL<<60;
    vector<ll> dp(100010,INF);

    dp[0] = 0;

    vector<ll> h(N);
    REP(i,N) cin>>h[i];

    REP(i,N){
        if(i+1<N) chmin(dp[i+1], dp[i]+abs(h[i+1]-h[i]));
        if(i+2<N) chmin(dp[i+2], dp[i]+abs(h[i+2]-h[i]));
    }

    cout << dp[N-1] << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);
static const int INF = 1e9+7;
#define REP(i,n) for (int i = 0; i <(n); ++i)
//debug 
#ifdef _DEBUG
#define debug(var)  do{cout << #var << " :";view(var);}while(0)
#else
#define debug(...)
#endif
template<typename T> void view(T e){cout << e << endl;}
template<typename T> void view(const vector<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;}
template<typename T> void view(const vector<vector<T> >& vv){ for(const auto& v : vv){ view(v); } }


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

  bool ok = true;
  REP(i,s.size()){
    if(i != a){
      if(s[i] == '-') ok = false;

    }
    else{
      if(s[i] != '-') ok = false;
    }
  }

  if(ok) cout << "Yes" << endl;
  else cout <<"No" << endl;
  return 0;
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	vector<int> c(n);
	rep(i,n) cin >> a.at(i);
	rep(i,n) cin >> b.at(i);
	rep(i,n) cin >> c.at(i);
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	sort(c.begin(),c.end());
	ll ans=0;
	rep(i,n){
		ll sum=0,l=-1,r=n;
		while(r-l>1){
			int mid=(r+l+1)/2;
			if(a[mid]>=b[i]) r=mid;
			else l=mid;
		}
		sum+=l+1;
		l=-1;
		r=n;
		while(r-l>1){
			int mid=(r+l+1)/2;
			if(c[mid]>b[i]) r=mid;
			else l=mid;
		}
		sum*=n-r;
		ans+=sum;
	}
	cout << ans << endl;
}

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

using namespace std;

int main(){
 string n; cin >> n;
  for(int i = 0; i < 3; i++){
    char res = n[i];
    if( n[i] == '1'){ res = '9';}
    else if(n[i] == '9'){ res = '1';}
    
    n[i] = res;
  }
  
  cout << n << endl;
  
  return 0;
}

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

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

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

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N;
    cin >> N;

    vector<ll> d(N);
    rep (i, N) {
        cin >> d[i];
    }

    sort(d.begin(), d.end());

    if (N%2 == 0) {
        cout << d[N/2] - d[N/2-1] << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(int argc, char const *argv[]) {
  int n;//ball
  int k;//color
  int comb=1;
  int i;
  scanf("%d %d",&n,&k );

  //先頭を一色決めてそこからスタートするパターン
  for(i=1;i < n;i++){
    comb *= (k - 1);
  }
  printf("%d\n", comb * k);
  return 0;
}


Measured memory_bytes: 128
n, k = map(int, input().split())
p = list(map(lambda x: int(x) + 1, input().split()))

s = 0
e = k
t = sum(p[0:k])

ans = 0
while True:
    ans = max(ans, t)
    if e == n:
        break
    t -= p[s]
    t += p[e]
    s += 1
    e += 1

print(ans / 2)


Measured memory_bytes: 97564
import sys

input = sys.stdin.readline


def main():
    A, B, C = map(int, input().split())

    if A == B == C and A % 2 == 0:
        print(-1)
        exit()

    ans = 0
    while True:
        if (A % 2 == 1) or (B % 2 == 1) or (C % 2 == 1):
            break
        ans += 1
        A, B, C = (B + C) // 2, (A + C) // 2, (A + B) // 2

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9188
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5 + 5;

char s[MAXN];

int main(void)
{
	scanf("%s",s+1);
	
	int sum = 0;
	for(int i=1; s[i]; ++i)
		sum = (sum + s[i] - '0') %9;
	if(sum == 0) printf("Yes");
	else printf("No");
	return 0;
}

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

int main() {
    int n; cin >> n;
    string s[n + 1];
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    int m; cin >> m;
    string t[m + 1];
    for (int i = 0; i < m; i++)  {
        cin >> t[i];
    }

    int ans = 0;
    for (int i = 0; i < n ; i++) {
        int cnts = 1, cntt = 0;

        for (int j = 0; j < n; j++) {
            if (i != j && s[i] == s[j]) cnts++;
        }

        for (int j = 0; j < m; j++) {
            if (s[i] == t[j]) cntt++;
        }

        ans = max(ans, cnts - cntt);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256