akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;
LL add(LL a,LL b){
  return (a+b)%mod;
}

LL sub(LL a,LL b){
  return (a+mod-b)%mod;
}

LL mul(LL a,LL b){
  return ((a % mod) * (b % mod)) % mod;
}

struct edge
{
  int to, cost;
};
typedef vector< vector < edge > > Graph;
int dp[100010]={};
int dpr[100010]={};
template< typename T = LL >
vector< T > Dijkstra(Graph &g, int s,int rev)
{
  typedef pair< T, int > Pi;
	//cout<<g.size()<<" "<<rev<<endl;
  vector< T > min_cost(g.size(), numeric_limits< T >::max());
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;//cost,from
  que.emplace(0, s);
  min_cost[s] = 0;
  while(!que.empty()) {
    Pi p = que.top();
    que.pop();
    if(p.first > min_cost[p.second]) continue;
		//cout<<p.second<<endl;
    for(auto &e : g[p.second]) {
      if(p.first + e.cost > min_cost[e.to]) continue;
			//*
			if(p.first + e.cost == min_cost[e.to]){
				if(rev==0)dp[e.to]=add(dp[p.second],dp[e.to]);
				else dpr[e.to]=add(dpr[p.second],dpr[e.to]);
				continue;
			}else {
				if(rev==0)dp[e.to]=dp[p.second];
				else dpr[e.to]=dpr[p.second];
			}//*/
      min_cost[e.to] = p.first + e.cost;
      que.emplace(min_cost[e.to], e.to);
    }
		//cout<<p.second<<endl;
  }
  return (min_cost);
}

int main(){
	int n,m,s,t;
	vector< vector<edge> > g;
	g.resize(100010);
	cin>>n>>m>>s>>t;
	int u,d,v;
	//cout<<"test"<<endl;
	FOR(i,0,m){
		cin>>u>>v>>d;
		edge ee;
		ee.to=u;
		ee.cost=d;
		g[v].push_back(ee);
		ee.to=v;
		ee.cost=d;
		g[u].push_back(ee);
	}
	//cout<<"test"<<endl;
	dp[s]=1;
	vector <LL> mc=Dijkstra(g, s, 0);
	dpr[t]=1;
	vector <LL> mcr=Dijkstra(g, t, 1);
	/*
	cout<<" tes:"<<dp[t]<<endl;
	cout<<" tesr:"<<dpr[s]<<endl;
	cout<<" mcr:"<<mcr[s]<<endl;//*/

	LL p=dp[t];
	p=mul(p,p);
	//cout<<p<<endl;
	FORQ(i,1,n){
		if(mc[t]%2==0&&mc[i]==mc[t]/2){
			LL pp=mul(dp[i],dpr[i]);
			p=sub(p,mul(pp,pp));
		}
		//cout<<p<<endl;
		for(auto &e : g[i]){
			int toto=e.to,costco=e.cost;
			if(mc[i]+costco+mcr[toto]!=mc[t])continue;
			//cout<<"edge:"<<i<<" "<<toto<<endl;
			if(mc[i]*2<mc[t]&&mc[toto]*2>mc[t]){
				//cout<<"on edge"<<" "<<endl;
				LL pp=mul(dp[i],dpr[toto]);
				p=sub(p,mul(pp,pp));
			}
		}
		//cout<<p<<endl;
	}
	cout<<p <<endl;

    return 0;
}


Measured memory_bytes: 14292
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	int h[n];
	for(int i = 0; i < n;i++)
		cin >> h[i];
	int current = h[0];
	int result = 1;
	for(int i = 1; i < n;i++)
	{
		if(h[i] >= current)
			{
				result++;
				current = h[i];
			}
	}
	cout << result << endl;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        List<Long> list = new ArrayList<Long>();

        for (int i = 0; i < n; i++) {
            long a = scan.nextLong();
            list.add(a);
        }

        Collections.sort(list);
        //System.out.println(list);
        
        long ans = 1l;

        boolean flag = false;
        try {
            for (int i = 0; i < n; i++) {
                long a = list.get(i);
                if (a == 0) {
                    flag = true;
                    break;
                }
                ans *= a;
                if (ans > 1000000000000000000l || ans <= 0) {
                    break;
                }
            }

            if (flag) {
                System.out.println(0);
            } else {
            if (ans > 1000000000000000000l || ans <= 0) {
                //System.out.println(ans);
                System.out.println(-1);
            } else {
                System.out.println(ans);
            }
            }
        } catch (Exception e) {
            System.out.println(-1);
        }
        
    }
}

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

#define MAX 200000
#define SENTINEL 2000000000
typedef long long llong;

int L[MAX / 2 + 2], R[MAX / 2 + 2];

llong merge(int A[], int n, int left, int mid, int right){
	
	int i,j,k;
	llong cnt = 0;
	int n1 = mid - left;
	int n2 = right - mid;
	for(i = 0; i < n1; i++) L[i] = A[left + i];
	for(i = 0; i < n2; i++) R[i] = A[mid + i];
	L[n1] = R[n2] = SENTINEL;
	i = j = 0;
	for(k = left; k < right; k++){
		if( L[i] <= R[j]){
			A[k] = L[i++];
		}else{
			A[k] = R[j++];
			cnt += n1 - i;   // = mid + j - k -1
		}
	}
	return cnt;
}

llong mergeSort(int A[], int n, int left, int right){
	
	int mid;
	llong v1,v2,v3;
	if(left + 1 < right){
		mid = (left + right) / 2;
		v1 = mergeSort(A, n, left, mid);
		v2 = mergeSort(A, n, mid, right);
		v3 = merge(A, n, left, mid, right);
		return v1 + v2 + v3;
	}else return 0;
}

int main(){
	
	int A[MAX], n, i;
	
	cin >> n;
	for(i=0; i<n; i++){
		cin >> A[i];
	}
	
	llong ans = mergeSort(A, n, 0, n);
	cout << ans << endl;
	
	return 0;
}



Measured memory_bytes: 4676
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>//for queue and priority_queue
#include <fstream>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#define endl "\n"
typedef long long ll;
using namespace std;
void Lancer() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
bool isPrime(ll n){
	if (n == 2 || n == 3 || n == 5)
		return true;
	else if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n == 1)
		return false;
	else {
		for (int i = 5; i <= sqrt(n); i += 2){
			if (n%i == 0)
				return false;
		}
		return true;
	}
}

//char arr[57][57];
int main(){
	Lancer();
	ll n, a, b, sum ,res=0, dgt;
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++){
		dgt = i; sum = 0;
		while (dgt)
		{
			sum += (dgt % 10);
			dgt /= 10;
		}
		if (sum >= a && sum <= b)
			res += i;
	}
	cout << res;
	cout << endl;
	return 0;
}


Measured memory_bytes: 3656
/*
 * ID: 0630
 * Problem: Microwave
 */

#include <stdio.h>

int main(void)
{
    int initial, final;
    int t1, t2, t3;

    scanf("%d", &initial);
    scanf("%d", &final);
    scanf("%d", &t1);
    scanf("%d", &t2);
    scanf("%d", &t3);

    int cooking = 0;

    if (initial * final < 0)
        cooking += t2;

    if (initial < 0)
        cooking += final < 0 ? t1 * (final - initial) : t1 * (-initial);
    
    if (final > 0)
        cooking += initial > 0 ? t3 * (final - initial) : t3 * final;

    printf("%d\n", cooking);

    return 0;
}



Measured memory_bytes: 2108
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;

void b_sort(int* a , int n, int* count){
	for(int i=n;i>=0;--i){
		for(int j=0;j<i-1;++j){
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
				(*count)++;
			}
		}
	}
}

int main(){
	int n , cnt=0;
	cin >> n;
	int*a = new int [n];
	for(int i=0;i<n ;++i){
		cin >> a[i];
	}
	b_sort(a , n , &cnt);
	for(int i=0;i<n-1 ; ++i){
		cout << a[i] << " ";
	}
	cout << a[n-1] << endl << cnt << endl;
	return 0; 
}

Measured memory_bytes: 1188
N = int(input())
#s = input()
#S = []
#for i in range(N):
S = input().split(" ")
for i in range(N):
    S[i] = float(S[i])
S.sort()
for i in range(N-1):
    S[i+1] = (float(S[i])+float(S[i+1])) / 2
print(S[N-1])




Measured memory_bytes: 2940
#include<iostream>

using namespace std;


bool Compare(const char*s, const char*p, int i, int sMax) {
	for (int j = 0; p[j] != '\0'; j++) {
		if (s[(i + j) % sMax] != p[j])return false;
	}
	return true;
}

int main() {
	char s[100];
	char p[100];
	int sMax;

	cin >> s >> p;

	for (sMax = 0; s[sMax] != '\0'; sMax++);

	for (int i = 0; i <= sMax; i++) {
		if (Compare(s, p, i, sMax)) {
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 1140
#include<stdio.h>
int main()
{
    int a,b,c,d,e,f;
    double s,t;
    while(scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f)!=EOF)
    {
        s=(double)(c*d-a*f)/(b*d-a*e);
        t=(double)(c-b*s)/a;
        printf("%.3lf %.3lf\n",t,s);

    }
    return 0;
}

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

# define p(s) std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;


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

    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin >> v[i];
        v[i] -= (i+1);
    }
    sort(v.begin(),v.end());

    int med;
    if(v.size()%2==1){
        med = v[(v.size()-1)/2];
    } else {
        med = (v[v.size()/2-1] + v[v.size()/2])/2 ;
    }

    long long int res=0;
    for(int i=0;i<n;i++){
        res += abs(v[i] - med);
    }
    p(res)
} 

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> ii;
#define F first
#define S second
#define sqr(x) (x)*(x)
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,x,y) for(int i=x;i<(y);++i)
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
/* start */

signed main(){
    IOS;
    int n; cin >> n;
    vector<int> a(2*n);
    rep(i,0,2*n) cin >> a[i];
    sort(all(a));
    int ans1 = 0, ans2=0;
    for(int i = 0;i<2*n;i+=2){
        ans1+=a[i];
    }
    for(int i = 1;i+1<2*n;i+=2){
        ans2+=a[i];
    }
    cout << max(ans1,ans2) << "\n";
}

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

int main()
{
    int a;
    int ans = 0;
    rep(i, 3) {
        cin >> a;
        ans += a;
    }
    if (ans >= 22) cout << "bust" << endl;
    else cout << "win" << endl;
    return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int c[3][3];
	rep(i, 0, 3) rep(j, 0, 3) cin >> c[i][j];

	rep(a1, 0, 101) {
		int b1 = c[0][0] - a1;
		if(b1 < 0) break;
		rep(a2, 0, 101) {
			int b2 = c[1][1] - a2;
			if(b2 < 0) break;
			rep(a3, 0, 101) {
				int b3 = c[2][2] - a3;
				if(b3 < 0) break;
				if((a1 + b2) == c[0][1] && (a1 + b3) == c[0][2] && (a2 + b1) == c[1][0] && (a2 + b3) == c[1][2] && (a3 + b1) == c[2][0] && (a3 + b2) == c[2][1]) {
					cout << "Yes" << endl;
					return 0;
				}
			}
		}
	}
	cout << "No" << endl;
		
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
 
public class Main {
 
    void solve() throws IOException {
        int N = ni();
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = ni();
        }
        int[] b = new int[N];
        for (int i = 0; i < N; i++) {
            b[i] = ni();
        }
        long inca = 0;
        long incb = 0;
        for (int i = 0; i < N; i++) {
            if(a[i] < b[i]) inca += (b[i] - a[i])/2;
            if(b[i] < a[i]) incb += a[i] - b[i];
        }
        if(inca>=incb) out.println("Yes");
        else out.println("No");
    }

    final int mod = 1000000007;
    final BigInteger MOD = BigInteger.valueOf(mod);

    int mul(int x, int y){
        int val = (int)((x * 1L * y) % mod);
        return val>=0 ? val : val+mod;
    }
    int add(int x, int y) {
        x += y;
        if(x < 0) x += mod;
        if(x>=mod) x -= mod;
        return x;
    }
    int sub(int x, int y){
        x = add(x,mod-y);
        if(x < 0) x += mod;
        if(x>=mod) x -= mod;
        return x;
    }
    String ns() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine(), " ");
        }
        return tok.nextToken();
    }
 
    int ni() throws IOException {
        return Integer.parseInt(ns());
    }
 
    long nl() throws IOException {
        return Long.parseLong(ns());
    }
 
    double nd() throws IOException {
        return Double.parseDouble(ns());
    }
 
    String[] nsa(int n) throws IOException {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = ns();
        }
        return res;
    }
 
    int[] nia(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = ni();
        }
        return res;
    }
 
    long[] nla(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = nl();
        }
        return res;
    }
 
    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;
 
    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        tok = new StringTokenizer("");
        Main main = new Main();
        main.solve();
        out.close();
    }
}

Measured memory_bytes: 38312
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int s;
	cin>>s;
	
	int mod = s%100;// for month
	int ans = s/100;// for year
	
	if((mod>=1) && (mod<=12))
	{
		if((ans>=1) && (ans<=12))
		{
			cout<<"AMBIGUOUS"<<endl;
			
		}
		else if((ans==0) || (ans>12)) 
		{
			cout<<"YYMM"<<endl;
		}
	}
	else if(mod==0||mod>12)
	{
		if((ans>=1) && (ans<=12))
		{
			cout<<"MMYY"<<endl;
		}
		else if((mod==0) || (mod>12))
		{
		    cout<<"NA"<<endl;
		}
	}
	return 0;
}
		
		


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

const int N = 100099;
bool ok;
int n, r;
ll a[N], c[N];
vi g[N];

void f(int u, int p) {
    if(!ok)return;
    if(sz(g[u]) == 1) {
        c[u] = a[u];
        return;
    }
    ll & T = c[u];
    ll s = 0, ma = 0;
    each(v, g[u]) if(v!=p){
        f(v, u);
        s += c[v];
        smax(ma, c[v]);
    }
    T = 2 * a[u] - s;
    if(ma > a[u] || T < 0 || a[u] > s)ok = false;
}

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

    while(cin >> n) {
        ok = true;
        rep(i, n)cin >> a[i], g[i].clear();
        rep(i, n - 1) {
            int u, v; cin >> u >> v;
            u--; v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        if(n == 2) {
            cout << (a[0] == a[1] ? "YES" : "NO") << endl;
            continue;
        }
        r = -1;
        rep(i, n)if(sz(g[i]) != 1)r = i;
        
        f(r, -1);
        if(c[r] != 0)ok = false;
        cout << (ok ? "YES" : "NO") << endl;
    }
}

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

int main() {
  string s;
  cin >> s;
  vector<string> w = {"Sunny", "Cloudy", "Rainy"};
  
  for(int i = 0; i < 3; i++){
    if(s == w.at(i)) cout << w.at((i+1) % 3) << endl;
  }
}


Measured memory_bytes: 256
import java.util.*;
import static java.lang.Integer.*;
//import static java.lang.Long.*;
//import static java.lang.Math.*;
import static java.lang.System.*;
import java.io.PrintWriter;

public class Main {
	public static void main(String[] args) {
		int i,j, k;
		Scanner sc = new Scanner(in);
		int n = parseInt(sc.next());
		sc.close();
		int[] so = {3*5*7, 3*5*11, 3*5*13, 3*3*3*5, 3*3*3*7};
		int cnt=0;
		for (i = 0; i < so.length; i++) {
			if(so[i] <= n)cnt++;
		}
		out.println(cnt);
	}
}


Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> vector<T> makev(T* b, T* e) {
    vector<T> vec;
    for (auto i = b; i != e; ++i) vec.push_back(*i);
    return vec;
}
struct err {
    err& operator <<(string s) { cerr << s; return *this; }
    template<class T1, class T2> err& operator <<(pair<T1, T2> x) { return *this << "(" << x.first << ", " << x.second << ")"; }
    template<class T> typename enable_if<is_scalar<T>::value == 1, err&>::type operator <<(T a) { cerr << boolalpha << a; return *this; }
    template<class T> typename enable_if<is_scalar<T>::value == 0, err&>::type operator <<(T a) {
        *this << "{";
        for (auto i = begin(a); i != end(a); ++i)
            *this << ", " + 2 * (i == begin(a)) << *i;
        return *this << "}";
    }
};
#define aty(...) "[ " << #__VA_ARGS__ << " : " << __VA_ARGS__ << " ]\n"




int32_t main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= 9; ++i) {
        for (int j = 1; j <= 9; ++j) {
            if (i * j == n) {
                return !printf("Yes\n");
            }
        }
    }
    printf("No\n");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2,t3;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;

ll n,m,x;
vector<vector<ll>> vec(12,vector<ll>(12,0));
vector<ll> c(12);
ll ans = INFLONG;

void dfs(ll num,ll cost,vector<ll> arr){
  //cout << num << endl;
  if(num == n){
    bool can = true;
    rep(i,m){
      if(arr[i] < x){
        can = false;
      }
    }
    if(can){
      chmin(ans,cost);
    }
    return;
  }
  dfs(num+1,cost,arr);
  rep(i,m){
    arr[i] += vec[num][i];
  }
  dfs(num+1,cost + c[num],arr);
}

int main(){
  cin >> n >> m >> x;
  rep(i,n){
    cin >> c[i];
    rep(j,m){
      cin >> vec[i][j];
    }
  }
  vector<ll> arr(m,0);
  dfs(0,0,arr);
  if(ans == INFLONG){
    ans = -1;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3632
class ModInt:
    def __init__(self, num, mod):
        self.num = num
        self.mod = mod

    def __str__(self):
        return str(self.num)

    def __repr__(self):
        return "ModInt(num: {}, mod: {}".format(self.num, self.mod)

    def __add__(self, other):
        ret = self.num + other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __sub__(self, other):
        ret = self.num - other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __mul__(self, other):
        ret = self.num * other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def pow(self, times):
        pw = pow(self.num, times, self.mod)
        return ModInt(pw, self.mod)

    def inverse(self):
        return self.pow(self.mod - 2)

    def __truediv__(self, other):
        num = self * other.inverse()
        return ModInt(num, self.mod)


h, w, a, b = map(int, input().split())
mod = 10 ** 9 + 7

power = [ModInt(1, mod)]
inv = [ModInt(1, mod).inverse()]


def comb(n, r):
    return power[n] * inv[r] * inv[n-r]


for i in range(1, h + w - 1):
    power.append(power[-1] * ModInt(i, mod))
    inv.append(power[-1].inverse())

ans = ModInt(0, mod)
for wi in range(b, w):
    ans += comb(h - a - 1 + wi, wi) * comb(a - 1 + w - wi - 1, a - 1)

print(ans)


Measured memory_bytes: 81516
import math
n = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))

print("{0:.6f}".format(sum([math.fabs(x[i]-y[i]) for i in range(n)])))
print("{0:.6f}".format(math.sqrt(sum([math.fabs(x[i]-y[i])**2 for i in range(n)]))))
print("{0:.6f}".format(math.pow(sum([math.fabs(x[i]-y[i])**3 for i in range(n)]), 1/3)))
print("{0:.6f}".format(max([math.fabs(x[i]-y[i]) for i in range(n)])))


Measured memory_bytes: 5724
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#include<map>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
using namespace std;
typedef pair<int, int> pii;
#define MAX 99999999
int main(){
    int n;
    while(cin>>n,n){
        vector<pii>v(1000,pii(0,0));
        rep(i,n){
            pii temp;
            cin>>temp.first>>temp.second;
            v[i]=temp;
        }
        int m; cin>>m;
        rep(i,m){
            pii temp;
            cin>>temp.first>>temp.second;
            v[n+i]=temp;
        }
        vi dp(10000,0);
        sort(v.begin(),v.begin()+n+m);
        int ans=0;
            rep(i,n+m){
                dp[i]=1;
                rep(j,i){
                    if(v[j].first<v[i].first&&v[j].second<v[i].second){
                        dp[i]=max(dp[i],dp[j]+1);
                    }
                    ans=max(ans,dp[i]);
                }
            }
        cout<<ans<<endl;
    }
    
}

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

int main() {
  int N;
  cin >> N;
  
  int a, b, c, d;
  
  a = N % 10;
  b = (N - a) %100;
  c = (N - a - b * 10) % 1000;
  d = (N - a - b * 10 - c * 100) % 10000;

	if( (a == b && b == c) || (b == c && c == d)) {
    cout << "Yes" << endl;
    }
	else{
      cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){

	int in[2]={0};
	
	int i;
	int count=0;
	int rev=0,num=0;
	scanf("%d %d",&in[0],&in[1]);
	
	
	for(i=in[0];i<=in[1];i++){
		
		num=i;
		rev=0;
		while(num>0){
			rev=rev*10+num%10;
			num/=10;
		}
		
		if(i==rev){
			count++;
		}
	}
	
	printf("%d",count);	
	
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int N; cin >> N;

	int x = 800 * N;
	int y = 200 * (N / 15);

	cout << x - y << endl;

	return 0;
}

Measured memory_bytes: 256
N=int(input())
c0,c1,c2,c3=0,0,0,0
for i in range(N):
  s=input()
  if s=="AC":
    c0=c0+1
  elif s=="WA":
    c1=c1+1
  elif s=="TLE":
    c2=c2+1
  else:
    c3=c3+1
print("AC x", c0)
print("WA x", c1)
print("TLE x", c2)
print("RE x", c3)

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

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

    vector<string> sn;
    vector<long long> tn;
    for (int i = 0; i < n; i++) {
        string s;
        long long t;
        cin >> s >> t;
        sn.push_back(s);
        tn.push_back(t);
    }
    cin >> x;

    bool find = false;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
       if (find) {
           ans += tn.at(i);
       }
       if (sn.at(i) == x) {
           find = true;
       }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    A,B = inputMap()
    
    ans = A - (2*B)
    
    print(max(0,ans))
    
if __name__ == "__main__":
	main()


Measured memory_bytes: 40048
#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 <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define PI 3.141592653589793238
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define fi first
#define se second
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
typedef complex<double> com;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

typedef pair<string, string> S;

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	int n;
	string s;
	cin >> n >> s;
	map<S, int> mp;
	rep(i, (1 << n)) {
		string x = "", y = "";
		rep(j, n) {
			if ((i >> j) & 1) x += s[j];
			else y += s[j];
		}
		reverse(all(x)); reverse(all(y));
		mp[S(x, y)]++;
	}
	int ans = 0;
	rep(i, (1 << n)) {
		string x = "", y = "";
		rep(j, n) {
			if ((i >> j) & 1) x += s[j + n];
			else y += s[j + n];
		}
		ans += mp[S(x, y)];
	}
	cout << ans << endl;
}

Measured memory_bytes: 87040
#include<iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <math.h>

using namespace std;

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

	int Ans = max(10 * a + b + c, a + 10 * b + c);
	Ans = max(a + b + 10 * c, Ans);

	cout << Ans;


	return 0;
}


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

int main(){
	ll a,v;	cin>>a>>v;
 	ll b,w;	cin>>b>>w;
  	double t;	cin>>t;
  if(v>w){
  	double temp=abs(b-a)*(1.0);
    int tm=v-w;
   	double p=(temp/tm);
    if(p<=t){
    	cout<<"YES"<<endl;
    }
    else{
    	cout<<"NO"<<endl;
    }
  }
  else{
  	cout<<"NO"<<endl;
  }
  return 0;
}


Measured memory_bytes: 3724
#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdio>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;

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

typedef long long ll;

const int Inf = 100100100;
const double EPS = 1e-9;

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

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s, year, month;
    cin >> s;
    year = s.substr(0, 4);
    month = s.substr(5, 2);
    int ye, mo;
    ye = stoi(year);
    mo = stoi(month);

    if (ye >= 2019 && mo >= 5) {
      cout << "TBD" << '\n';
    } else {
      cout << "Heisei" << '\n';
    }

    return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main{
    
    public static void main(String args[]) throws IOException{
	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

	int n=Integer.parseInt(br.readLine());

	Node node[]=new Node[n];
        for(int i=0;i<n;i++){
	    node[i]=new Node(-1);
	}

	for(int i=0;i<n;i++){
	    String str[]=br.readLine().split(" ");
	    int id=Integer.parseInt(str[0]);
	    int left=Integer.parseInt(str[1]);
	    int right=Integer.parseInt(str[2]);
	    node[id].left=left;
	    node[id].right=right;

	    if(left!=-1)
		node[left].parent=id;
	    if(right!=-1)
		node[right].parent=id;
	}

	for(int i=0;i<n;i++){
	    System.out.print("node "+i+": ");
	    System.out.print("parent = "+node[i].parent+", ");
	    System.out.print("sibling = "+node[i].getSibling(node,i)+", ");
	    System.out.print("degree = "+node[i].getDegree()+", ");
	    System.out.print("depth = "+node[i].getDepth(node)+", ");
	    System.out.print("height = "+node[i].getHeight(node,i)+", ");
	    System.out.print(node[i].isType());
	    System.out.print("\n");
	}
    }
}
class Node{

    int parent;
    int left=-1;
    int right=-1;
    
    public Node(int parent){
	this.parent=parent;
    }
    public String isType(){
	if(parent==-1){
	    return "root";
	}else if(left==-1&&right==-1){
	    return "leaf";
	}else{
	    return "internal node";
	}
    }

    public int getSibling(Node node[],int id){
	if(parent==-1)
	    return -1;
	if(node[parent].left==id){
	    return node[parent].right;
	}else{
	    return node[parent].left;
	}
    }

    public int getDegree(){
	if(left==-1&&right==-1){
	    return 0;
	}else if((left!=-1&&right==-1)||(left==-1&&right!=-1)){
	    return 1;
	}else{
	    return 2;
	}
    }

    
    
    public int getDepth(Node node[]){
	int pID=parent;
	int count=0;
	while(pID!=-1){
	    pID=node[pID].parent;
	    count++;
	}
	return count;
    }

    public int getHeight(Node node[],int id){
	int Lheight=0;
	int Rheight=0;
	
	if(node[id].left==-1&&node[id].right==-1){
	    return 0;
	}else{
	    int l=node[id].left;
	    if(l!=-1){
		Lheight=getHeight(node,l)+1;
	    }
	    int r=node[id].right;
	    if(r!=-1){
		Rheight=getHeight(node,r)+1;
	    }
	}
	return Math.max(Lheight,Rheight);
    
    }
}



Measured memory_bytes: 24424
n, m, k = map(int, input().split())
#Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
par = [-1 for i in range(n)]
l = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    unite(a-1, b-1)
    l[a-1] += 1
    l[b-1] += 1
for i in range(k):
    c, d = map(int, input().split())
    if same(c-1, d-1):
        l[c-1] += 1
        l[d-1] += 1
for i in range(n):
    print(size(i) - l[i] - 1, end=" ")

Measured memory_bytes: 11384
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007

signed main(){

    int A;
    string B;

    cin>>A>>B;

    int Bint;
    Bint=(B[0]-'0')*100+(B[2]-'0')*10+(B[3]-'0')*1;
    int sum=A*Bint;
    cout<<(int)(sum/100)<<endl;


}


Measured memory_bytes: 3200
/* Akshat Sharma @akshat98 */
#include <iostream>
#include <bits/stdc++.h>
#define IOS  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define mp   make_pair
#define pb   push_back
#define F    first
#define S    second
#define ll   long long
#define MOD  1000000007
#define MAX  1000000001
#define vi 	 vector<int>
#define vl   vector<ll>
#define vpi  vector<pair<int,int> >
#define vpl  vector<pair<ll,ll> >
#define rep(i,a,b) for(i=a;i<b;i++)
#define reqp(i,a,b) for(i=a;i<=b;i++)
#define ren for(i=0;i<n;i++)
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
#define int long long
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;

ll ans=0;
int parent[100005]={0};
int parent_cnt[100005]={0};

void join(ll x,ll y){
	ll px, py;
	ll sx=x;
	ll sy=y;
	while(x!=parent[x]){
		x=parent[x];
	}
	while(y!=parent[y]){
		y=parent[y];
	}

	if(x==y){
		return;
	}
	ll ans1,ans2,ans3;
	ans1=(parent_cnt[x])*(parent_cnt[x]-1)/2;
	ans2=(parent_cnt[y])*(parent_cnt[y]-1)/2;
	
	parent_cnt[x]+=parent_cnt[y];
	// cout<<x<<"__"<<y<<".\n";
	// parent_cnt[y]=0;
	parent[y]=parent[x];
	parent[sx]=parent[x];
	parent[sy]=parent[x];
	
	ans3=parent_cnt[x]*(parent_cnt[x]-1)/2;
	
	ans+=(ans3-ans2-ans1);
}


int32_t main()
{
	// #ifndef ONLINE_JUDGE
//	freopen("input_file.txt", "r", stdin);
	//freopen("output_file.txt", "w", stdout);
	// #endif
	int i,j,k,l,n,test_case,m;
	test_case=1;
	//cin>>test_case;
	while(test_case--){
		cin>>n>>m;
		vi a(m);
		vi b(m);
		rep(i,1,n+1){
			parent[i]=i;
			parent_cnt[i]=1;
		}
		rep(i,0,m){
			cin>>a[i]>>b[i];
		}
		vi vec;
		int temp=n*(n-1)/2;
		vec.pb(temp);
		for(i=m-1;i>=1;i--){
			join(a[i],b[i]);
			vec.pb(temp-ans);
		}
		reverse(ALL(vec));
		for(auto it:vec){
			cout<<it<<"\n";
		}


	}
	
	return 0;
}

Measured memory_bytes: 5364
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
 
// BIT /////////////////////////////////////////////////////////////////////////
template<
	typename T = int
>
class bit{
public:
	T *bit_arr;
	int size;
 
	bit(int n){
		size = n;
		bit_arr = new T[n];
		fill(bit_arr, bit_arr+n, 0);
	}
 
	~bit(){
		delete bit_arr;
	}
 
	T sum(int a){
		T ret = 0;
		while(a){
			ret+=bit_arr[a];
			a-=a&-a;
		}
		return ret;
	}
 
	T sum(int a, int b){
		return sum(b)-sum(a);
	}
 
	T get(int a){
		return sum(a, a+1);
	}
 
	void add(int a, T x){
		a++;
		while(a<size){
			bit_arr[a]+=x;
			a+=a&-a;
		}
	}
 
	void set(int a, T x){
		add(a, x-get(a));
	}
};
typedef bit<ll> bll;
 
#define N 112345
#define LO 18
class sbit{
public:
	bll b;
	sbit() : b(N){
	}
	void add(int l, int r, ll x){
		b.add(l, x);
		b.add(r, -x);
	}
	ll get(int i){
		return b.sum(i+1);
	}
};

ll k;
vector<pair<int, ll> > path[100005];

int f[100005]; // original node index -> on the list
int c[100005]; // size of subtree
int d[100005]; // depth in tree
int p[100005][LO]; // parent doubling
// int dmm[N];
sbit csm, dsm, qry;

void dfs(int nw, int par, int dep, int ind){
	// printf("dfs(nw=%d, par=%d, dep=%d, ind=%d)\n", nw, par, dep, ind);
	f[nw]=ind;
	d[ind]=dep;
	p[ind][0]=par;
	for(int i=1; i<LO; i++)
	 	p[ind][i]=p[p[ind][i-1]][i-1];
	int sm=1;
	for(int i=0; i<path[nw].size(); i++){
		pair<int, ll> &pr=path[nw][i];
		if(f[pr.first]==par) continue;
		dfs(pr.first, ind, dep+1, ind+sm);
		csm.add(ind+sm, ind+sm+c[ind+sm], pr.second);
		if(pr.second%k==0){
			dsm.add(ind+sm, ind+sm+c[ind+sm], pr.second);
			// dmm[ind+sm]=pr.second;
		}
		sm+=c[ind+sm];
	}
	c[ind]=sm;
}

int lsc(int x, int y){
	if(d[x]<d[y]) swap(x, y);
	int dif=d[x]-d[y];
	for(int i=0; i<LO; i++)
	 	if(dif&(1<<i)) x=p[x][i];
	// printf(" %d %d\n", x, y);
	if(x==y) return x;
	int ret=0;
	for(int i=LO-1; i>=0; i--){
		// printf("(%d, %d)->(%d, %d)\n", x, y, p[x][i], p[y][i]);
		if(p[x][i]==p[y][i]) ret=p[x][i];
		else{
			x=p[x][i];
			y=p[y][i];
		}
	}
	return ret;
}

ll clc(int x){
	int q;
	while((q=qry.get(x))){
		int y=x;
		for(int i=LO-1; i>=0; i--){
			if(qry.get(p[y][i])==q) y=p[y][i];
		}
		dsm.add(y, y+c[y], -(dsm.get(y)-dsm.get(p[y][0])));
		ll r=csm.get(y)-csm.get(p[y][0]);
		if(r%k==0){
			dsm.add(y, y+c[y], r);
		}
		qry.add(y, y+c[y], -(qry.get(y)-qry.get(p[y][0])));
	}
	return csm.get(x)-dsm.get(x);
}

int main(){
	int n;
	cin >> n >> k;
	for(int i=0; i<n-1; i++){
		int a, b;
		ll c;
		cin >> a >> b >> c;
		path[a].push_back(make_pair(b, c));
		path[b].push_back(make_pair(a, c));
	}
	for(int i=0; i<n; i++) f[i]=-1;
	dfs(0, 0, 0, 0);

	int q;
	cin >> q;
	for(int i=0; i<q; i++){
		string s;
		ll x, y;
		cin >> s >> x >> y;
		if(s[0]=='a'){
			x=f[x];
			if(x){
			 	csm.add(x, x+c[x], y);
				qry.add(x, x+c[x], 1);
			}
			csm.add(x+1, x+c[x], y);
			qry.add(x+1, x+c[x], 1);
		}else{
			x=f[x];
			y=f[y];
			int z=lsc(x, y);
			ll ans=clc(x)+clc(y)-2*clc(z);
			cout << ans << endl;
		}
	}
}

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

int main(){
    int n; cin>>n;
    set<int> s;
    for(int i=0;i<n;i++){
        int d; cin>>d;
        s.insert(d);
    }
    cout<<s.size()<<endl;
}

Measured memory_bytes: 256
N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
    tmp = list(map(int, input().split()))
    C.append(tmp[0])
    A.append(tmp[1:])
ans = float('INF')
level = [0] * M
def DFS(cost, level_list, start):
    global ans
    if min(level_list) >= X:
        ans = min(ans, cost)
        return ans
    # 処理
    for i in range(start, N):
        tmp_cost = cost + C[i]
        tmp_level_list = [x + y for (x, y) in zip(level_list, A[i])]
        DFS(tmp_cost, tmp_level_list, i + 1)
    return ans

ans = DFS(0, level, 0)
if ans != float('INF'):
    print(ans)
else:
    print(-1)

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

int main(){
  int H, W; cin >> H >> W;
  vector<vector<char> > field(H, vector<char> (W));
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> field[i][j];
    }
  }
  vector<vector<int> > dp(110, vector<int> (110, 0));
  for(int i = 1; i < H; i++){
    dp[i][0] = dp[i - 1][0] + (field[i][0] != field[i - 1][0]);
  }
  for(int j = 1; j < W; j++){
    dp[0][j] = dp[0][j - 1] + (field[0][j] != field[0][j - 1]);
  }
  for(int i = 1; i < H; i++){
    for(int j = 1; j < W; j++){
      int x, y;
      x = dp[i][j - 1] + (field[i][j - 1] != field[i][j]);
      y = dp[i - 1][j] + (field[i - 1][j] != field[i][j]);
      dp[i][j] = min(x, y);
    }
  }
  int ans = dp[H - 1][W - 1];
  if(field[0][0] == '.' && field[H - 1][W - 1] == '.') ans /= 2;
  if(field[0][0] == '#' && field[H - 1][W - 1] == '#') ans = ans/2 + 1;
  if(field[0][0] != field[H - 1][W - 1]) ans = (ans + 1)/2;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double LD;
using namespace std;
const int INF = 2147483647;
const int INF2 = 0x3f3f3f3f;
const ll INF64 = 3e18;
const double INFD = 1e30;
const double EPS = 1e-10;
const long double PI = acosl(-1);
const int MOD = 1e9 + 7;
template <typename T>
inline T read() {
    T X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return w ? -X : X;
}
const int MAXN = 2505;
const int MAXV = 60;
int n, m, k;
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
int dr2[8] = {1, 1, 1, -1, -1, -1, 0, 0};
int dc2[8] = {1, 0, -1, 1, 0, -1, 1, -1};
int CASE = 1;

struct FenwickTree {
    FenwickTree() {}
    inline void increase(int r, int c, int x) {
        for (int i = r; i <= n; i += lowbit(i))
            for (int j = c; j <= m; j += lowbit(j)) {
                a[i][j] += x;
                b[i][j] += r * x;
                d[i][j] += c * x;
                e[i][j] += r * c * x;
            }
    }
    inline int getSum(int r, int c) {
        int ans = 0;
        for (int i = r; i; i -= lowbit(i))
            for (int j = c; j; j -= lowbit(j)) {
                ans += a[i][j] * (r + 1) * (c + 1);
                ans -= b[i][j] * (c + 1);
                ans -= d[i][j] * (r + 1);
                ans += e[i][j];
            }
        return ans;
    }
    int a[MAXN][MAXN], b[MAXN][MAXN], d[MAXN][MAXN], e[MAXN][MAXN];
    inline int lowbit(int x) { return x & (-x); }
};

int main() {
#ifdef LOCALLL
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int d;
    scanf("%d%d", &n, &d);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        double dis = sqrt((double)x * x + (double)y * y);
        if (dis <= d) {
            cnt++;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

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

#define fi first
#define se second
#define pb push_back
#define mod(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,a,b) for(int i = a; i < b; i++)
#define forr(i,a,b) for(int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()

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

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll a,b; cin >> a >> b;
	cout << a*b << '\n';
	return 0;
}
/*
__builtin_mul_overflow(x,y,&x)
-fsplit-stack
*/


Measured memory_bytes: 3636
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b){return *(char*)a - *(char*)b;} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b){return strcmp(*(const char **)a, *(const char **)b);} /* aaa,aab.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007

typedef long long int lli;

int main(void) {
  int A, B;
  scanf("%d %d", &A, &B);
  int ans = 6 - (A + B);
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
n, a, b, c = map(int, input().split(' '))
inf = 10**9
l = [int(input()) for _ in range(n)]
result = []

def dfs(counter, A, B, C):
    if counter == len(l):
        return abs(A-a)+abs(B-b)+abs(C-c)-30 if min(A,B,C) > 0 else inf
    p_1 = dfs(counter+1, A+l[counter], B, C) + 10
    p_2 = dfs(counter+1, A, B+l[counter], C) + 10
    p_3 = dfs(counter+1, A, B, C+l[counter]) + 10
    p_4 = dfs(counter+1, A, B, C)
    return min(p_1,p_2,p_3,p_4)

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

Measured memory_bytes: 3064
import string
n = int(input())
cs = string.ascii_lowercase
cm = {cs[i]:i for i in range(len(cs))}
t = 1
def rec(st):
    global t
    if (len(st) >= n):
        print(st)
        t += 1
        return 0
    k = max(cm[st[i]]+1 for i in range(len(st)))
    for c in cs[: k + 1]:
        rec(st+c)
    
    
rec('a')

Measured memory_bytes: 5024
package main

import "fmt"

func main() {
	var a, b, c string
	fmt.Scan(&a, &b, &c)

	if a[len([]rune(a))-1] == b[0] && b[len([]rune(b))-1] == c[0] {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 512
fun main() {
    val n = readLine()!!.toInt()
    val list = readLine()!!.split(" ").map { it.toInt() }
    val group = list
        .asSequence()
        .groupBy { it }
        .map { (key, value) -> key to (value.size > 1) }

    val isDividable = BooleanArray(list.max()!! + 1) { true }
    for ((num, value) in group) {
        if (value) isDividable[num] = false

        for (i in (num * 2) until isDividable.size step num) {
            isDividable[i] = false
        }
    }
    println(list.count { isDividable[it] })
}

Measured memory_bytes: 108820
#include <stdio.h>
int main() {
	int k, s, ans = 0;
	scanf("%d%d", &k, &s);
	for(int x=0;x<=k && x<=s;++x) {
		for(int y=0;y<=k && y+x<=s;++y) {
			if(s-x-y<=k) ++ans;
		}
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 128
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	//文字列から10進数に変換するときはparseIntを使います
	var a = parseInt(input[0], 10);
	var b = parseInt(input[1], 10);
    if(a == 1 && b == 2){
        console.log(3);
    }else if(a == 2 && b == 1){
              console.log(3);
    }else if(a == 3 && b == 1){
              console.log(2);
    }else if(a == 1 && b == 3){
              console.log(2);
    }else{
        console.log(1);
    }
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include <bits/stdc++.h>
using namespace std;
#define PUTS(x) cout << (x) << endl;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
int main() {
    int n;
    cin >> n;
    int m = INT_MAX, ans = 0;
    rep(i, n) {
        int x;
        cin >> x;
        if (x <= m) {
            ans++;
            m = x;
        }
    }
    PUTS(ans);
}


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

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n),x(n);
    for(ll i=0;i<n;i++) x[i] = 0;
    for(ll i=0;i<n;i++) cin >> a[i];
    for(ll i=0;i<n;i++){
        if(i%2==0)  x[0]+=a[i];
        else    x[0]-=a[i];
    }
    for(ll i=1;i<n;i++){
        x[i] = (a[i-1]-(x[i-1]/2))*2;
    }
    for(ll i=0;i<n;i++) cout << x[i] << ' ';
}

Measured memory_bytes: 2944