akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <cstring>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_set>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll h, ans;
ll dfs(ll a) {
	if (a == 1)return 1;
	return dfs(a / 2) * 2 + 1;
}
int main() {
	ll n;
	cin >> n;
	cout << dfs(n) << endl;
}


Measured memory_bytes: 256
#include<algorithm>
#include<functional>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

typedef unsigned long long ull;
typedef long long ll;

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

using namespace std;

typedef pair<int ,int > P;

int a,b;

void solve()
{
	int n=a+b;

	ostringstream os;

	os<<n;

	cout<<os.str().size()<<endl;

	return ;
}

int main()
{
	while(cin>>a>>b)
	{
		solve();
	}


	return 0;
}

Measured memory_bytes: 1212
H, W, D = [int(x) for x in input().split()]
size = H*W+1
c = [(-1, -1)] * size
p = [0] * size

for y in range(H):
    for x, a in enumerate([int(s) for s in input().split()]):
        c[a] = (x, y)

for a in range(D+1, size):
    p[a] = p[a-D] + abs(c[a][0] - c[a-D][0]) + abs(c[a][1] - c[a-D][1])

Q = int(input())
for i in range(Q):
    L, R = [int(lr) for lr in input().split()]
    print(p[R] - p[L])


Measured memory_bytes: 14304
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>

#define INF (1ll<<60)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;

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

template<class T>bool umax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool umin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using namespace std;

// gcd
int gcd(int a, int b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}
// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);

    return result;
}

// sort big to small
// sort(A,A+N, greater<int>());

// v.front() = -BOUND;
// v.back() = BOUND;

// Iterator
// v.begin
// v.end

int main() {
    int N,K;
    long long ans=0;
    cin >> N >>K;

    rep(i,N){
        int x;
        cin >> x;
        ans+=2*min(abs(x),abs(K-x));
    }


    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(void) {
  double v, t, y, floor;

  while (scanf("%lf", &v) != EOF) {
    t = v / 9.8;
    y = 4.9 * t * t;
    floor = (5 + y) / 5;

    printf("%.0f\n", ceil(floor));
  }

  return 0;
}

Measured memory_bytes: 652
# 2019/07/10

from heapq import heappop,heappush

n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for i in range(m):
    u,v,c=map(int,input().split())
    edge[u].append((c,v))
    edge[v].append((c,u))


def prim(s):
    d=[float('inf')]*n
    visited=[False]*n
    d[s]=0
    visited[s]=True
    que=[]
    for e in edge[s]:
        heappush(que,e)
    while que:
        c,v=heappop(que)
        if visited[v]:continue
        d[v]=c
        visited[v]=True
        for cost,vtx in edge[v]:
            if visited[vtx]:continue
            hq=(cost,vtx)
            heappush(que,hq)
    return d


print(sum(prim(0)))
    
    


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

int main() {
  int N;
  cin >> N;
  
  int N3, N2, N1, N0;
  
  N3 = N/1000;
  N2 = (N%1000)/100;
  N1 = ((N-N3*1000)%100)/10;
  N0 = ((N-N3*1000-N2*100)%10);
  
  if (N3==N2&&N2==N1) {
	cout << "Yes" << endl;
  }
  else if (N2==N1&&N1==N0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

memory = {}

def expectation(x):
    if x in memory:
        return memory[x]
    else:
        return x * (1 + x) / (2 * x)

def solve(N: int, K: int, P: "List[int]"):
    largest = 0
    if K == 1:
        largest = expectation(max(P))
        print(largest)
        return

    for i, p in enumerate(P[:-K+1]):
        if i == 0:
            summation = 0
            for k in range(K):
                summation += expectation(P[i + k])
            if summation > largest:
                largest = summation
        else:
            summation -= expectation(P[i-1])
            summation += expectation(P[i + K - 1])
            if summation > largest:
                largest = summation

    print(largest)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, P)

if __name__ == '__main__':
    main()


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

int n, q, c[500005], l[500005], r[500005], p[500005], bit[500005], ans[500005];
vector <int> v;

bool cmp(int x, int y){
    return r[x] <= r[y];
}
void update(int x, int d){
    while (x <= n){
        bit[x] += d;
        x += x & (-x);
    }
}
int query(int x){
    int ret = 0;
    while (x){
        ret += bit[x];
        x -= x & (-x);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> c[i];
    }
    for (int i = 0; i < q; i++){
        cin >> l[i] >> r[i];
        v.push_back(i);
    }
    int pos = 0;
    sort(v.begin(), v.end(), cmp);
    for (auto i:v){
        for (int j = pos+1; j <= r[i]; j++){
            if (p[c[j]]) update(p[c[j]], -1);
            update(j, 1);
            p[c[j]] = j;
        }
        pos = r[i];
        ans[i] = query(r[i])-query(l[i]-1);
    }
    for (int i = 0; i < q; i++){
        cout << ans[i] << "\n";
    }
}


Measured memory_bytes: 17536
n = int(input())

dp = [10**6 for _ in range(10**6)]
dp[0] = 0

for i in range(1,n+1):
    j6 = 1
    while 0 <= i-j6:
        dp[i] = min(dp[i-j6]+1,dp[i])
        j6 *= 6
    j9 = 1
    while 0 <= i-j9:
        dp[i] = min(dp[i-j9]+1,dp[i])
        j9 *= 9
print(dp[n])

Measured memory_bytes: 147964
# coding: utf-8
# Your code here!
S = input()

bef = int(S[:2])
aft = int(S[2:])

if 1 <= bef and bef <= 12 and 1 <= aft and aft <= 12:
    print("AMBIGUOUS")
elif 0 <= bef and bef <= 99 and 1 <= aft and aft <= 12:
    print("YYMM")
elif 1 <= bef and bef <= 12 and 0 <= aft and aft <= 99:
    print("MMYY")
else:
    print("NA")

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

int main() {
    vector<vector<int>> c(3, vector<int>(3));
    for (auto& e : c) for (auto& f : e) cin >> f;

    string ans = "Yes";
    for (int i = 0; i + 1 < 3; i++) {
        vector<int> v = { c[0][i+1] - c[0][i], c[1][i+1] - c[1][i], c[2][i+1] - c[2][i] };
        vector<int> w = { c[i+1][0] - c[i][0], c[i+1][1] - c[i][1], c[i+1][2] - c[i][2] };
        for (auto& e : { v, w }) {
            if (adjacent_find(begin(v), end(v), not_equal_to<>()) != end(v)) ans = "No";
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#define MOD 1000000007LL
using namespace std;

int main(){
	long long int x, y;
	cin >> x >> y;
	long long int min = 4000000001;
	if(y >= x && min > (y - x)) min = (y - x);
	if(y + x >= 0 && min > (y + x + 1)) min = (y + x + 1);
	if(x + y <= 0 && min > (1 - x - y)) min = (1 - x - y);
	if(x >= y && min > (2 + x - y)) min = (2 + x - y);
	cout << min << endl;
	return 0;
}

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


int main() {
  long double n;
  cin >> n;
  long double d;
  cin>>d;
  long ans=(long)n*d;
  
    cout<<ans<<endl;
  
  
  
}







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

bool prime(int x)
{
	for(int i=2;i*i<=x;i++)
    {
      if(x%i==0)
        	return false;
    }
  	return true;
}

int main()
{
  int n;
  cin>>n;
  while(!prime(n))
  {
    n++;
  }
  cout<<n;
  return 0;
}

Measured memory_bytes: 256
N,Q = map(int, input().split())
S = str(input())
# N,Q=8,3
# S = "ACACTACG"
L = [0] * len(S) #ACのAの個数を保持
i = 0
sum_i = 0
while i < len(S)-1:
    if S[i] == "A":
        if S[i+1] == "C":
            L[i] = sum_i
            sum_i += 1
            L[i+1] = sum_i
            i += 2
        elif S[i+1] == "A":
            L[i] = sum_i
            i += 1
        else:
            L[i] = sum_i
            L[i+1] = sum_i
            i += 2
    else:
        L[i] = sum_i
        i += 1
L[len(S)-1] = sum_i
for _ in range(Q):
    l, r = map(int, input().split())
    print(L[r-1] - L[l-1])


Measured memory_bytes: 6084
#include <iostream>
#include <array>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef  pair<int,int> P;
typedef long long LL;
typedef vector<LL> VEC;


const LL INF=1<<30;
const LL MOD=1000000007;

LL gcd(LL a,LL b){
    if(b==0)return a;

    return gcd(b,a%b);
}

LL kaijo(LL n){
    LL ans=1;
    for(LL i=1;i<=n;++i){
        (ans*=i)%=MOD;
    }
    return ans;
}


int main(){
    LL n;
    cin>>n;
    LL a[200500];
    LL x=0,y=0;
    for(LL i=0;i<n;++i){
        cin>>a[i];
        y+=a[i];
    }
    LL ans=INF;
    x+=a[0];
    y-=a[0];
    if(n==2)cout<<abs(a[0]-a[1])<<endl;
    else{
    for(LL i=1;i<n-1;++i){
        y-=a[i];
        x+=a[i];
        ans=min(ans,abs(x-y));
    }
    cout<<ans<<endl;
}
}

Measured memory_bytes: 1792
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc  = new Scanner (System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if(a==b){
            System.out.println(a+b);
        }
        else if(a>b){
            System.out.println(a+(a-1));
        }
        else{
            System.out.println(b+(b-1));
        }
    }
}

Measured memory_bytes: 35452
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
signed main(){
    int r,d,st;cin>>r>>d>>st;
    rep(i,10){
        st=st*r-d;
        cout<<st<<endl;
    }
    return 0;

}

Measured memory_bytes: 256
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
X = [list(map(int, input().split())) for _ in range(Q)]

ctr = {}
for i in range(H):
    for j in range(W):
        ctr[A[i][j]] = (i, j)

memo = [0] * (H * W + 1)
for n in range(D + 1, H * W + 1):
    i, j = ctr[n - D]
    x, y = ctr[n]
    memo[n] = abs(x - i) + abs(y - j) + memo[n - D]

for l, r in X:
    print(memo[r] - memo[l])


Measured memory_bytes: 82012
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("filed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let l:f64 = read();
    println!("{}", (l/3.0).powf(3.0));
}

Measured memory_bytes: 2828
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define endl "\n"
#define pii pair<int,int> 
#define ff first
#define ss second
#define mii map<int,int>
#define si set<int>
#define sti stack<int>
#define qi queue<int>
#define vi vector<int>
#define pq priority_queue<int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int M=1e9+7;

int32_t main(){
    IOS;
    int n;
    cin>>n;
    string s;
    cin>>s;
    bool ok=0;
    if(s.size()%2==0){
        if(s.substr(0,n/2)==s.substr(n/2,n/2)) ok=1;
    }   
    if(ok) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

int dp[101010];
vector<int> v[101010];

int rec(int x){
    if(dp[x]!=-1)return dp[x];
    dp[x]=0;
    for(auto to:v[x]){
        dp[x]=max(rec(to)+1,dp[x]);
    }
    return dp[x];
}

int main(){
    int n,m;
    cin>>n>>m;
    rep(i,m){
        int x,y;
        cin>>x>>y;
        --x;--y;
        v[x].push_back(y);
    }
    rep(i,n)dp[i]=-1;
    int ans=0;
    rep(i,n)ans=max(ans,rec(i));
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 7424
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
    using namespace std;
 
    int main(){
      int n,m;
      cin >> n >> m;
      cout << (n-1)*(m-1) << endl;
      return 0;}

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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll N, Q, S, T;
ll A[200005];
ll val[200005];
ll D[200005];

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

	cin >> N >> Q >> S >> T;

	cin >> A[0];

	ll def = 0;

	for (int i = 1;i <= N;i++){
		cin >> A[i];
		ll d = A[i] - A[i-1];
		D[i] = d;
		ll tmp;
		if(d <= 0) tmp = T * (-d);
		else tmp = S * (-d);
		def += tmp;
		val[i] = tmp;
	}


	for (int i = 0;i < Q;i++){
		ll L, R, X;
		cin >> L >> R >> X;

		ll ans = def;

		if(L != 0){
			ll d = D[L]+X;
			D[L] += X;
			ans -= val[L];
			ll tmp;
			if(d <= 0) tmp = T * (-d);
			else tmp = S * (-d);
			ans += tmp;
			val[L] = tmp;
		}
		if(R != N){
			ll d = D[R+1]-X;
			D[R+1] -= X;
			ans -= val[R+1];
			ll tmp;
			if(d <= 0) tmp = T * (-d);
			else tmp = S * (-d);
			ans += tmp;
			val[R+1] = tmp;
		}
		def = ans;
		cout << ans << endl;
	}

	return 0;

}



Measured memory_bytes: 7872
//
// Created by yamunaku on 2019/09/07.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> mti;
typedef vector<ll> vl;
typedef vector<vector<ll>> mtl;

int main(){
    int n;
    cin >> n;
    cout << n *n*n << endl;
    return 0;
}


Measured memory_bytes: 764
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1)/ (y))
#define MOD 1000000007ULL

u64 N, X, L;


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

    cin >> N >> X;

    int ans = 1;
    u64 d = 0;
    rep (i, N)
    {
        cin >> L;
        d += L;
        if (X < d) break;
        ++ans;
    }


    cout << ans << "\n";

    return 0;
}



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

int main() {
  int q_num, total_time = 0;
  cin >> q_num;
  vector<int> time(q_num);

  for(int i=0; i < q_num; i++) {
    cin >> time[i];
    total_time += time[i];
  }

  int drink_type;
  cin >> drink_type;
  vector<int> ans(drink_type);

  for(int i = 0; i < drink_type; i++) {
    int p, x;
    cin >> p >> x;
    ans[i] = total_time + (x - time[p-1]);
  }

  for(int a : ans) cout << a << endl;
}

Measured memory_bytes: 3560
#include <stdio.h>
#include <string.h>
int juge(char *,char *);
const int MAX = 1000 + 10 ;
char a[MAX];
char b[MAX];
int main()
{
	
	int count1[52];
	int count2[26];
	scanf("%s",a);
	scanf("%s",b);
	int i;
	int flag=1;
	int flag1=0;
	for(i=0;i<strlen(a);i++)
	{
		int j;
		flag=1;
		for(j=0;j<strlen(a);j++)
		{
			if(a[(j+i)%strlen(a)]!=b[j])
			{
				flag=0;
				break;
			}
		}
		if(flag)
		{
			flag1=1;
			break;
		}
		
	}
	if(flag1)
	{
		printf("Yes");
	}
	else
	{
		printf("No");
	}
	return 0;
}


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

// TYPEDEF
// ----------------------------------------
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> Pair;
typedef vector<ll> vll;
typedef vector<vector<ll>> Graph;
typedef vector<string> vs;
typedef vector<pair<ll, ll>> Pll;
typedef queue<ll> qll;

// REPEAT
// ----------------------------------------
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REPA(i,a) for(ll i=0;i<(ll)(a.size());i++);
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define COUT(a) cout << (a) << endl;
#define ENDL(a) cout << endl;
#define COUTA(i,a) for(ll i=0;i<(ll)(a.size());i++) {cout << (a)[i] << " ";} cout << endl;

// UTIL
// ----------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define RSORT(a) sort((a).rbegin(), (a).rend())

// DEBUG
// ----------------------------------------
#ifdef _DEBUG
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
#else
#define debug(x)
#endif

template <typename T>
void debugV(const vector<T> v) {
#ifdef _DEBUG
  rep(i, v.size()) {
    cout << i << ":" << v[i] << " ";
  }
  cout << endl;
#else
  (void)v;
#endif
}

// BIT FLAG
// ----------------------------------------
const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000
const unsigned int BIT_FLAG_8 = (1 << 8); // 0000 0001 0000 0000
const unsigned int BIT_FLAG_9 = (1 << 9); // 0000 0010 0000 0000
const unsigned int BIT_FLAG_10 = (1 << 10); // 0000 0100 0000 0000
const unsigned int BIT_FLAG_11 = (1 << 11); // 0000 1000 0000 0000

// CONST
// ----------------------------------------
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr double PI=3.14159265358979323846; // or M_PI
constexpr int MOD = 1000000007;


void Main() {
  ll n, m;
  cin >> n >> m;
  ll left = 1, right = n;
  REP(i, m) {
    ll l, r;
    cin >> l >> r;
    if (left < l) {
      left = l;
    }
    if (r < right) {
      right = r;
    }
  }
  ll ans = right - left + 1;
  if (ans < 1) {
    COUT(0);
  }
  else {
    COUT(ans);
  }

}



int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}

/*
4 2
1 3
2 4
*/


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

#include <bits/stdc++.h>

using namespace std;

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

void d_err() {
    cerr << endl;
}

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

template <typename T>
void print(T x) {
    cout << x << endl;
}

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

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

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


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

    int N;
    cin >> N;

    map<char, ll> m;
    REP(i, N) {
        string s; cin >> s;
        m[s[0]]++;
    }

    vector<char> v = {'M','A','R','C','H'};

    ll ans = 0;
    REP(i, 5) FOR(j, i + 1, 5) FOR(k, j + 1, 5) {
        ans += m[v[i]] * m[v[j]] * m[v[k]];
    }

    print(ans);


}


Measured memory_bytes: 3608
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner scan=new Scanner(System.in);
    int x=scan.nextInt();
    int[] num=new int[x];
    for(int a=0; a<x; a++){
      num[a]=scan.nextInt();
    }
    Arrays.sort(num);
    double Ans=num[0];
    for(int a=1; a<x; a++){
      Ans=(Ans+num[a])/2;
    }
    System.out.println(Ans);
  }
}

Measured memory_bytes: 22868
from collections import deque
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edges[a].append((b,i))
  edges[b].append((a,i))
ans=[0]*(n-1)
q=deque()
next_v=edges[0]
for c,(u,i) in enumerate(next_v):
  q.append((u,i,c+1))
  ans[i]=c+1
while q:
  up,_,cp=q.popleft()
  next_v=edges[up]
  cnt=1
  for u,i in next_v:
    if ans[i]>0:
      continue
    if cnt==cp:
      cnt+=1
    ans[i]=cnt
    q.append((u,i,cnt))
    cnt+=1
print(max(ans))
for i in ans:
  print(i)
  


Measured memory_bytes: 40160
#include <bits/stdc++.h>
#ifdef HIRO
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef queue<int> qi;
typedef queue< pair<int, int> > qp;
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
#define gt(T) greater<T>()
#define sum(v) accumulate(v.begin(), v.end(), 0)
#define uni(v) do{ \
  sort(v.begin(), v.end()); \
  decltype(v)::iterator result = unique(v.begin(), v.end()); \
  v.erase(result, v.end()); \
}while(0)
#define fi(init, n) for(int i = init; i < n; ++i)
#define fj(init, n) for(int j = init; j < n; ++j)
#define fk(init, n) for(int k = init; k < n; ++k)
#define zero(x) memset(x, 0, sizeof(x))
#define negative(x) memset(x, ~0, sizeof(x))
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}
template<typename T>
int finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) return 1;
	else return 0;
}
ll frac(ll n){
	if (n == 0) return 1;
	return (n * frac(n - 1)) % MOD;
}

ll dp[100001][3];
int main(int argc, char** argv) {
#ifdef HIRO
  string quiz(argv[1]);
  string id(argv[2]);
  string filename("input/" + quiz + "/" + id + ".txt");
  ifstream fin(filename);
  if (fin.peek() == ifstream::traits_type::eof()) {
    cout << "No input.";
    return 0;
  }
  ifstream cin(filename);
  std::cin.rdbuf(cin.rdbuf());
#endif
  ll ans = 0;
  ll n;
  cin >> n;
  // ll n, m;
  // cin >> n >> m;
  // ll n, m, k;
  // cin >> n >> m >> k;
  int x;
  fi(1, n + 1) {
    fj(0, 3) {
      cin >> x;
      fk(0, 3) {
        if(j == k) continue;
        dp[i][j] = max(dp[i][j], dp[i - 1][k] + x);
      }
    }
    // cin >> a >> b >> c;

  }
  cout << *MAX(dp[n], dp[n] + 3);
  // cout << ans << endl;
  return 0;
}



Measured memory_bytes: 2560
'use strict';

function Main(input) {
  let N = Number(input);

  const func = () => {
    if(N < 4) {
      console.log('No');
    } else if (N % 4 === 0) {
      console.log('Yes');
    } else if (N % 7 === 0) {
      console.log('Yes');
    } else {
      N -= 4;
      func();
    }
  };

  func();



};

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());

Measured memory_bytes: 21064
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<map>
#include<set>
#include<string>
#include<cctype>
#include<cmath>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
#define debug(x) cerr << #x << " = " << x << endl
#define MAXN 3000010
using namespace std;
int read(){
	int x = 0, f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
	for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0'; return x * f;
}

int n;

int main(){
	n = read();
	for(int j = 7; j >= 0; j--)
		if((1 << j) <= n){
			cout << (1 << j) << endl;
			return 0;
		}
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <string> 
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;
using ll = long long;
using ull = unsigned long long;

#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define REFOR(i, m, n) for(int i = int(n - 1);i >= int(m);i--)
#define REP(i,n) for(int i = 0; i < int(n); i++)
#define REREP(i,n) for(int i = int(n - 1); i >= 0; i--)
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VL vector<ll>
#define VVL vector<vector<ll>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define PAIR pair<int,int>
#define MP make_pair
#define VP vector<pair<int,int>>
#define VS vector<string>
#define MAP map<int,int>
#define QUE queue<int>
#define DEQ deque<int>
#define PQUE priority_queue<int> //5,5,4,3,3,2,...
#define REPQUE priority_queue<int, vector<int>, greater<int>> //1,1,2,3,4,4,5,...
#define SUM(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SORT(obj) sort((obj).begin(), (obj).end()) // 1,2,3,4,5...
#define RESORT(obj) sort((obj).begin(), (obj).end(), greater<int>()) // 5,4,3,2,1...
#define UB(obj,n) upper_bound((obj).begin(), (obj).end(), n) //itr > n
#define LB(obj,n) lower_bound((obj).begin(), (obj).end(), n) //itr>= n

const ll MOD = (ll)1e9 + 7;
const ll INF = (ll)1e17;


void ANS(bool flag){
	cout << ((flag) ? "YES" : "NO") << endl;
}

void Ans(bool flag) {
	cout << ((flag) ? "Yes" : "No") << endl;
}

void ans(bool flag) {
	cout << ((flag) ? "yes" : "no") << endl;
}

int node[100000] = {};

int root(int n) {
	if (node[n] == n) return n;
	else return node[n] = root(node[n]);
}

void unite(int n, int m) {
	if (n > m) swap(n, m);
	n = root(n);
	m = root(m);
	if (n == m) return;
	else node[m] = n;
}


struct edge { int cost, from, to; };

bool operator<(const edge &left, const edge &right){
	return left.cost < right.cost;
}

int main() {
	int N;
	cin >> N;
	multiset<PAIR> stx;
	multiset<PAIR> sty;

	REP(i, N) {
		int x, y;
		cin >> x >> y;
		stx.insert({ x,i });
		sty.insert({ y,i });
	}

	auto itrx = stx.begin();
	PAIR x1 = *itrx;
	itrx++;
	PAIR x2 = *itrx;

	auto itry = sty.begin();
	PAIR y1 = *itry;
	itry++;
	PAIR y2 = *itry;

	multiset<edge> st;
	
	REP(i,N - 1){
		int costx = abs(x2.first - x1.first);
		st.insert({ costx,x1.second,x2.second });

		x1 = x2;
		itrx++;
		x2 = *itrx;

		int costy = abs(y2.first - y1.first);
		st.insert({ costy,y1.second,y2.second });

		y1 = y2;
		itry++;
		y2 = *itry;
	}

	REP(i, N) node[i] = i;
	ll sum = 0;
	for(auto itr = st.begin();itr != st.end();itr++){
		edge e = *itr;
		if (root(e.from) == root(e.to)) continue;
		sum += e.cost;
		unite(e.from, e.to);	
	}
	cout << sum << endl;

	return 0;
}


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

int main() {
    int n;cin>>n;
    int d[n];
    int ans=0;
    for(int i=0;i<n;++i){
        cin>>d[i];
    }
    sort(d,d+n);
    ans=d[n/2]-d[n/2 - 1];

    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE CPP                   #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE OverloadedStrings     #-}
{-# LANGUAGE RecordWildCards       #-}
{-# LANGUAGE TupleSections         #-}
{-# LANGUAGE TypeFamilies          #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bool
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import           Data.Function
import qualified Data.IntMap.Strict          as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Monoid
import           Data.Ord
import           Data.Primitive.MutVar
import qualified Data.Set                    as S
import           Data.Tuple
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import           Debug.Trace
import           Foreign                     hiding (void)
import           Unsafe.Coerce

main :: IO ()
main = do
    [n,k] <- map read.words <$> getLine :: IO [Int]
    xs <- U.unfoldrN n (B.readInt.B.dropWhile isSpace) <$> B.getLine
    print $ solve k xs

solve :: Int -> U.Vector Int -> Int
solve k xs = q + divCeil (U.length zs - r) (k - 1)
  where
    (ys, zs) = U.tail <$> U.span (/= 1) xs
    q = divCeil (U.length ys) (k - 1)
    r = q * (k - 1) - U.length ys

divCeil x y = div (x + y - 1)  y

Measured memory_bytes: 2940
import copy
import heapq

from typing import List, Tuple


def main():
    d, g = map(int, input().split())
    v = []
    for _ in range(d):
        p, c = map(int, input().split())
        v.append((p, c))

    print(ag(v, g))


def ag(v: List[Tuple[int, int]], g: int) -> int:
    rs = []
    # ex. [(3, 500), (5, 800)] -> [(1, 3, 500), (2, 5, 800)]
    v = [(i, p, c) for i, (p, c) in enumerate(v, 1)]

    for j in range(2 ** len(v)):
        cb = []
        for k in range(len(v)):
            if ((j >> k) & 1):
                cb.append(v[k])

        sc = 0
        cnt = 0
        # calc bonus score
        for (i, p, c) in cb:
            sc += i * 100 * p + c
            cnt += p

        vv = [x for x in copy.copy(v) if not x in cb]
        while sc < g:
            if not vv:
                break
            i, p, _ = vv.pop()
            for _ in range(p - 1):
                if sc >= g:
                    break
                sc += i * 100
                cnt += 1

        if sc >= g:
            heapq.heappush(rs, cnt)
    return heapq.heappop(rs)


if __name__ == '__main__':
    main()


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

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define deb(x)	cout << #x << " " << x << endl;

typedef long long int ll;

int main() {

	IOS

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

	cout << (((n+x-1))/x) * t;
	
	return 0;
} 

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

int main() {
    long long a, b, c, d, e, f, g;
    while (cin >> a >> b >> c >> d >> e >> f >> g) {
        long long res = 0;
        long long m = min(a, min(d, e));
        for (long long i = max(m-2, 0LL); i <= m; ++i) {
            long long tmp = i * 3;
            long long na = a - i, nd = d - i, ne = e - i;
            tmp += na/2 * 2;
            tmp += nd/2 * 2;
            tmp += ne/2 * 2;
            res = max(res, tmp);
        }
        cout << res + b << endl;
    }
}














Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a;
	cin >> a;
	int temp = a, sum = 0;
	while(temp)
	{
		sum += temp % 10;
		temp /= 10;
	}
	if(a % sum == 0) printf("Yes");
	else             printf("No");
	return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

#define INF INT_MAX/3
#define REP(i,n) for(int i=0;i<n;i++)


ll A_ij[30][30] = {0};
ll N,M,X;
vector<ll> c_arr;
ll min_cost = INF;

void dfs(int i,vector<ll> rikaido,ll cost){
	//cout<<" i = "<<i<<endl;
	if(i == N){
		//REP(j,M)cout<<"ri = "<<rikaido[j]<<" ";
		//cout<<"------------"<<endl;
		if(all_of(rikaido.begin(),rikaido.end(),[](ll x){
				return x >= X;
				})){
			min_cost = min(cost,min_cost);
			//cout<<min_cost<<endl;
		}
		return;
	}
	vector<ll> new_rikaido(M);
	REP(k,M){
		new_rikaido[k] = rikaido[k] + A_ij[i][k];
	}
	auto new_cost = cost + c_arr[i];
	dfs(i + 1,new_rikaido,new_cost);
	
	dfs(i + 1,rikaido,cost);

}


int main(){
	

	cin>>N>>M>>X;
	c_arr.resize(N);

	REP(i,N){
		cin>>c_arr[i];
		REP(j,M){
			cin>>A_ij[i][j];
		}
	}
	vector<ll> poyo(M,0);

	dfs(0,poyo,0);


//	REP(i,N){
//		REP(j,M){
//			cout<<A_ij[i][j]<<endl;
//		}
//	}


	//bit all search
//	ll cost = 0;
//	ll min_cost = INF;
//	for(int i = 0; i < 1<<N; i++){
//		fill(rikaido.begin(),rikaido.end(),0);
//		cost = 0;
//		//cout<<i<<endl;
//		for(int j = 0; j < N; j++){
//			//cout<<"ij : "<<((i>>j) & 1)<<endl;
//			if( (i>>j & 1) != 0){
//				//cout<<"a"<<endl;
//				REP(k,M){
//					rikaido[k] += A_ij[j][k];
//				}
//				cost += c_arr[j];
//			}
//		}
//		
//		bool flag = true;
//
//		REP(k,M){
//			//cout<<"rika : "<<rikaido[k]<<endl;
//			flag = (rikaido[k] >= X) && flag;
//		}
//		if(flag){
//			//cout<<"cots"<<cost<<endl;
//			min_cost = min(cost,min_cost);
//		}
//	}
	if(min_cost == INF){
		cout<<-1<<endl;
	}else{
		cout<<min_cost<<endl;
	}
	return 0;
}



Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define f(i, n) for(int i = 0; i < n; ++i)
#define pb push_back
#define T int t = 0; cin >> t; while(t--)
#define b_e(a) a.begin(), a.end()
typedef long long ll;
typedef  long double lld;
const ll mod = 1e9 + 7;
const ll mx = 2e3 + 1;
ll mat[10][10];
ll find_first(ll x){
    ll ans;
    while(x > 0){
        ans = x % 10;
        x /= 10;
    }
    return ans;
}

void input(){
    ll n;
    memset(mat, 0LL, sizeof(mat));
    cin >> n;
    for(ll i = 1; i <= n; ++i){
        ll x = find_first(i);
        ll y = i % 10;
        mat[x][y]++;
    }
    ll ans = 0;
    for(ll i = 1; i <= 9; ++i){
        for(ll j = 1; j <= 9; ++j){
            ans  += (mat[i][j] * mat[j][i]);
        }
    }
    cout << ans << endl;
}
int main(){
    input();
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int d=sc.nextInt();
		int g=sc.nextInt();
		long[][] list=new long[d][2];
		for(int i=0; i<d; i++){
			list[i][0]=sc.nextInt();
			list[i][1]=sc.nextInt();
		}
		int ans=Integer.MAX_VALUE;
		for(int i=0; i<1<<d; i++){
			int k=i;
			int point=0;
			int count=0;
			int ant=0;
			int gre=0;
			while(k>0){
				if((k & 1)==1){
					point+=list[count][0]*(long)(count+1)*100+list[count][1];
					ant+=list[count][0];
				}else{
					gre=count;
				}
				k>>=1;
				count++;
			}
			if(g-point>0){
				int ty=0;
				int index=0;
				if(count==d){
					ty=100*(gre+1);
					index=gre;
				}else{
					ty=d*100;
					index=d-1;
					
				}
				int aj=((g-point)%ty)==0?0:1;
				if(aj+((g-point)/ty)>list[index][0]-1){
					continue;
				}else{
					ans=Math.min(ans,ant+aj+((g-point)/ty));
				}
			}else{
				ans=Math.min(ans,ant);
			}
		}
		System.out.println(ans);
	}
}



Measured memory_bytes: 21844
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		long N = long.Parse(Console.ReadLine());
		long[]A = new long[5];
		long min = 99999999999999999;
		for(var i=0;i<5;i++){
			A[i] = long.Parse(Console.ReadLine());
			min = Math.Min(A[i],min);
		}
		long ans = 0;
		ans = (N-1)/min+1+4;
		Console.WriteLine(ans);
	}
}

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

using namespace std;

string s;

long long i,j,k,l,n,m;

set<long long>c;

int main()
{
    cin>>n>>m>>k;
    for(i=1;i<=k;i++){
        if(i+n-1>m)break;
        c.insert(n+i-1);
    }
    for(i=k;i>=1;i--){
        if(m-i+1<n)break;
        c.insert(m-i+1);
    }
    for(auto i:c)cout<<i<<endl;
    return 0;
}


Measured memory_bytes: 256
import sys
input=sys.stdin.readline
import fractions

n = int(input())
a = list(map(int, input().split()))

a.sort()
h = {}
for i in range(a[-1]+1):
    h[i] = 0

for i in a:
    h[i] += 1

ans = 0
for i in range(len(h)):
    x = h[i]
    if i > 0:
        x += h[i-1]
    if i < len(h)-1:
        x += h[i+1]
    ans = max(ans, x)
print(ans)

Measured memory_bytes: 22628
//What is love?

#include <iostream>
#include <stdio.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define FOR(i,n,m) for(int i=n; i<m; i++)
#define ROF(i,n,m) for(int i=n; i>m; i--)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define ri(a) scanf("%d",&a)
#define rii(a,b) scanf("%d %d",&a,&b)
#define riii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define lri(a) scanf("%lld",&a)
#define lrii(a,b) scanf("%lld %lld",&a,&b)
#define ms(obj,val) memset(obj,val,sizeof(obj))
#define debug true
#define dprintf debug && printf
#define all(v) v.begin(),v.end()

const int INF = 0x3f3f3f3f;
const ll INFLL = 1e18;
const int MOD = 1e9+7;
const int MAXN = 2e5+5;


/*--------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------*/

int r,c;
int b[111][111];
int dp[111][111];

int f(int x, int y){
    if(x==r-1 && y==c-1) return b[x][y];
    if(x>=r || y>=c) return INF;
    if(dp[x][y]!=-1) return dp[x][y];

    return dp[x][y] = min(
        f(x+1,y) + (int)(b[x][y] && !b[x+1][y]),
        f(x,y+1) + (int)(b[x][y] && !b[x][y+1])
    );
}

int main(){

    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

    rii(r,c);

    FOR(i,0,r){
        FOR(j,0,c){
            char c;
            cin >> c;
            if(c=='#') b[i][j]++;
        }
    }

    ms(dp,-1);

    printf("%d\n", f(0,0));

    return 0;
}

Measured memory_bytes: 384
<?php
$n = intval(fgets(STDIN));
$minRet = ask(0);
$maxRet = ask($n-1);
$min = 0;
$max = $n-1;
while($min!=$max){
    $mid = intdiv($max+$min, 2);
    $midRet = ask($mid);
    if(($midRet != $minRet) != ($mid - $min) % 2){
        $max = $mid;
        $maxRet = $midRet;
    }else{
        $min = $mid;
        $minRet = $midRet;
    }
}

function ask($a){
    //return dummyResponder($a);//通信相手のエミュレータ
    echo $a,"\n";
    flush();
    $in = trim(fgets(STDIN));
    if($in == "Vacant"){
        exit;
    }elseif($in == "Male"){
        return 1;
    }else{
        return -1;
    }
}
function dummyResponder($a){
    echo $a,"\n";
    return [1,-1,1,-1,1,-1,0,1,-1,1,-1][$a];
}



Measured memory_bytes: 5200
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll inf=1000000000000000000;
int main(){
  ll n,m;cin>>n>>m;
  ll u[m],v[m],s[m];
  vector<pll> g[n];
  for(ll i=0;i<m;i++){
    cin>>u[i]>>v[i]>>s[i];
    u[i]--;
    v[i]--;
    g[u[i]].push_back(make_pair(v[i],s[i]));
    g[v[i]].push_back(make_pair(u[i],s[i]));
  }
  vector<pll> num(n);
  for(ll i=0;i<n;i++)num[i]=make_pair(inf,0);
  num[0]=make_pair(0,0);
  queue<pair<ll,pll>> q;
  q.push(make_pair(0,make_pair(0,0)));
  while(q.size()>0){
    ll atai=q.front().first;pll p=q.front().second;q.pop();
    ll pf=p.first,ps=p.second;
    for(ll i=0;i<g[pf].size();i++){
      ll now=g[pf][i].first;
      if(num[now].first!=inf)continue;
      num[now]=make_pair(g[pf][i].second-atai,(ps+1)%2);
      q.push(make_pair(g[pf][i].second-atai,make_pair(now,(ps+1)%2)));
    }
  }
    ll m1=inf,m2=inf;
    for(ll i=0;i<n;i++){
      if(num[i].second==0){
        m1=min(m1,num[i].first);
      }
      else{
        m2=min(m2,num[i].first);
      }
    }
    if(m2<=0){
      cout<<0<<endl;
      return 0;
    }
    m1=-m1;
    if(m2-m1-1<=0){
      cout<<0<<endl;
    return 0;
    }
  if(m==n-1){
    cout<<m2-m1-1<<endl;
    return 0;
  }
  ll de=inf;
  for(ll i=0;i<m;i++){
    ll nu=num[u[i]].second,nv=num[v[i]].second;
    ll a=num[u[i]].first,b=num[v[i]].first;
    if(nu==0){
      if(nv==0){
        if((s[i]-a-b)%2==1){
          cout<<0<<endl;
          return 0;
        }
        ll e=(s[i]-a-b)/2;
        if(e<=m1||e>=m2){
          cout<<0<<endl;
          return 0;
        }
        if(de!=inf&&e!=de){
          cout<<0<<endl;
          return 0;
        }
        de=e;
      }
      else{
        if(a+b!=s[i]){
          cout<<0<<endl;
          return 0;
        }
      }
    }
    else{
      if(nv==0){
        if(a+b!=s[i]){
          cout<<0<<endl;
          return 0;
        }
      }
      else{
        if((a+b-s[i])%2==1){
          cout<<0<<endl;
          return 0;
        }
        ll e=(a+b-s[i])/2;
        if(e<=m1||e>=m2){
          cout<<0<<endl;
          return 0;
        }
        if(de!=inf&&e!=de){
          cout<<0<<endl;
          return 0;
        }
        de=e;
      }
    }
  }
  if(de==inf){
    cout<<m2-m1-1<<endl;
  }
  else{
    cout<<1<<endl;
  }
}
                             
  
  
    

Measured memory_bytes: 13552
n, m = list(map(int, input().split()))
# a = list(map(int, input().split()))
# data = [list(map(int, input().split())) for i in range(n)]
# n = int(input())
# n, m = list(map(int, input().split()))
# ab_sorted = sorted(ab, key=lambda x: x[0])
s = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
data = []
for i in range(2**n):
    swich = []
    for j in range(n):
        if((i >> j) & 1):
            swich.append(1)
        else:
            swich.append(0)
    data.append(swich)

ans = 0
flag = True
for i in range(2**n):
    flag = True
    for j in range(m):
        count = 0
        for k in range(1, len(s[j])):
            if data[i][s[j][k]-1] == 1:
                count += 1
        if count % 2 != p[j]:
            flag = False
    if flag:
        ans += 1
print(ans)


Measured memory_bytes: 3188
S = input()
K = int(input())
a = list(set(S))
a.sort()

k = []
l = 0
while l < len(a):
    for i in range(len(S)):
        if S[i] == a[l]:
            for j in range(1,6):
                if i+j <= len(S):
                    k.append(S[i:i+j])
                else:
                    break
    l += 1

k = list(set(k))
k.sort()
print(k[K-1])

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

using namespace std;

vector<int> F(45, -1);

int fib(int n)
{
  if (!n || n == 1) return F[n] = 1;
  if (F[n] != -1) return F[n];

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

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

  cout << fib(n) << endl;

  return 0;
}

Measured memory_bytes: 1200
K, N = map(int, input().split())
A = list(map(int, input().split()))

D = [None] * N
last = A[-1] - K
for i, a in enumerate(A):
  diff = (a - last, i)
  D[i] = diff
  last = a

i = max(D)[1]
if i == 0:
  print(A[i - 1] - A[i])
else:
  print(K - A[i] + A[i - 1])


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

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

using namespace std;
using lint=long long;

class mint{
	static const int MOD=1e9+7; // 998244353;
	int x;
public:
	mint():x(0){}
	mint(long long y){ x=y%MOD; if(x<0) x+=MOD; }

	mint& operator+=(const mint& m){ x+=m.x; if(x>=MOD) x-=MOD; return *this; }
	mint& operator-=(const mint& m){ x-=m.x; if(x<   0) x+=MOD; return *this; }
	mint& operator*=(const mint& m){ x=1LL*x*m.x%MOD; return *this; }
	mint& operator/=(const mint& m){ return *this*=inverse(m); }
	mint operator+(const mint& m)const{ return mint(*this)+=m; }
	mint operator-(const mint& m)const{ return mint(*this)-=m; }
	mint operator*(const mint& m)const{ return mint(*this)*=m; }
	mint operator/(const mint& m)const{ return mint(*this)/=m; }

	friend mint inverse(const mint& m){
		int a=m.x,b=MOD,u=1,v=0;
		while(b>0){ int t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); }
		return u;
	}

	friend istream& operator>>(istream& is,mint& m){ long long t; is>>t; m=mint(t); return is; }
	friend ostream& operator<<(ostream& os,const mint& m){ return os<<m.x; }
	int to_int()const{ return x; }
};

mint pow(mint m,long long k){
	mint res=1;
	for(;k>0;k>>=1,m*=m) if(k&1) res*=m;
	return res;
}

map<lint,int> prime_factorize(lint a){
	map<lint,int> res;
	if(a%2==0){
		int cnt=0;
		do{ cnt++; a/=2; }while(a%2==0);
		res.emplace(2,cnt);
	}
	for(lint p=3;p*p<=a;p+=2) if(a%p==0) {
		int cnt=0;
		do{ cnt++; a/=p; }while(a%p==0);
		res.emplace(p,cnt);
	}
	if(a>1) res.emplace(a,1);
	return res;
}

int main(){
	int n; scanf("%d",&n);
	vector<int> hist(n+1);
	rep(i,n) for(auto p:prime_factorize(i+1)) hist[p.first]+=p.second;

	mint ans=1;
	rep(i,n+1) ans*=hist[i]+1;
	printf("%d\n",ans.to_int());

	return 0;
}


Measured memory_bytes: 256
#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;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a[3];
    rep(i,0,3)cin >> a[i];
    sort(a,a+3);
    if(a[0] == a[1]){
        print(a[2]);
    }else{
        print(a[0]);
    }
}


Measured memory_bytes: 256