akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

int main(int argc, char const *argv[]) {
	int h,w,d;
	std::cin >> h >> w >> d;
	std::vector<std::vector<int>> a(h,std::vector<int> (w));
	std::vector<std::vector<int>> xy(h*w+1,std::vector<int> (2,0));
	for (size_t i = 0; i < h; i++) {
		for (size_t j = 0; j < w; j++) {
			std::cin >> a[i][j];
			xy[a[i][j]][0] = i;
			xy[a[i][j]][1] = j;
		}
	}
	int q;
	std::cin >> q;
	std::vector<std::vector<int>> lr(q,std::vector<int> (2));
	for (size_t i = 0; i < q; i++) {
		std::cin >> lr[i][0] >> lr[i][1];
	}

	std::vector<int> v(w * h + 1, 0);
	for (size_t i = d; i < v.size(); i++) {
		v[i] = v[i-d] + abs(xy[i][0] - xy[i-d][0]) + abs(xy[i][1] - xy[i-d][1]);
	}

	for (size_t i = 0; i < lr.size(); i++) {
		std::cout << v[lr[i][1]] - v[lr[i][0]] << '\n';
	}
	return 0;
}


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

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

cout << c << " "<< a<<" "<<b << endl;
return 0;
}

Measured memory_bytes: 256
n=int(input())
l=list(map(int,input().split()))
s=0
for i in range(1,n-1):
    if (l[i]>l[i-1] and l[i]<l[i+1]) or (l[i]<l[i-1] and l[i]>l[i+1]):
        s+=1
print(s)

Measured memory_bytes: 3060
#include<cstdio>
#include<cstring>
int a[2001000];
int b[2001000];
int n,L;
void turn(int x)//<=x的是0，>x的是1
{
    for(int i=1;i<=L;i++)
        if(a[i]<=x)
            b[i]=0;
        else
            b[i]=1;
}
int main()
{
    scanf("%d",&n);
    L=(n<<1)-1;
    for(int i=1;i<=L;i++)
        scanf("%d",&a[i]);
    int l=1,r=L,mid;
    while(l<r)
    {
        int flag=0;
        mid=(l+r>>1);
        turn(mid);
        for(int i=1;i<n;i++)
        {
            if(b[n+i]==b[n+i-1])
            {
                if(b[n+i]==0)
                    r=mid;
                else
                    l=mid+1;
                flag=1;
                break;
            }
            if(b[n-i]==b[n-i+1])
            {
                if(b[n-i]==0)
                    r=mid;
                else
                    l=mid+1;
                flag=1;
                break;
            }
        }
        if(!flag)
        {
            if(b[n]^(n&1)^1)
                l=mid+1;
            else
                r=mid;
        }
    }
    printf("%d\n",l);
    return 0;
}


Measured memory_bytes: 5120
import java.util.Scanner;
public class Main
{
	public static void main(String[] args) 
	{
		Scanner in=new Scanner(System.in);
		int N=in.nextInt();
		while(N-->0)
		{
			String s[]=in.next().split(":");
			double S=Double.valueOf(s[0]);
			double L=Double.valueOf(s[1]);
			S=360*(S*60+L)/720.0;
			L=360.0*L/60.0;
			double dif=Math.min(Math.abs(S-L), 360-Math.abs(S-L));
			System.out.println(0<=dif&&dif<30 ? "alert":90<=dif&&dif<=180 ? "safe":"warning");
		}
	}
}

Measured memory_bytes: 12000
#include <iostream>
#include <climits>
#include <vector>

const long long INF = LLONG_MAX - 1000000001; //e+9を足してもオーバーフローしないサイズをINFとする

using namespace std;

template <class T>
bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;

        return true;
    }

    return false;
}

int main(void)
{
    long long N, W;

    cin >> N >> W;

    vector<long long> w(N), v(N);

    for (int i = 0; i < N; i++)
    {
        cin >> w[i] >> v[i];
    }

    vector<vector<long long>> dp(N + 1, vector<long long>(100001, INF));

    dp[0][0] = 0;

    for (int i = 0; i < N; i++)
    {
        for (int v_i = 0; v_i < 100002; v_i++)
        {
            if (v_i - v[i] >= 0)
            {
                chmin(dp[i + 1][v_i], dp[i][v_i - v[i]] + w[i]);
            }
            chmin(dp[i + 1][v_i], dp[i][v_i]);
        }
    }

    int ans = -1;

    for (int i = 100000; i >= 0; i--)
    {
        if (dp[N][i] <= W && i > ans)
        {
            ans = i;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 80256
#include<iostream>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
typedef long long ll;

int main(){
    int x, y;
    int xx=0, yy=0;
    string ans="Yes";
    cin >> x >> y;
    if(x==2) xx=2;
    if(y==2) yy=2;
    if(x==4 || x==6 || x==9 || x==11) xx=1;
    if(y==4 || y==6 || y==9 || y==11) yy=1;
    if(xx==yy){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
//#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
#include <cstring>
#include <cassert>

using namespace std;

#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(...) DBG2::print(#__VA_ARGS__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(...)
#endif

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

struct Edge {
   int u, v;
};

llong sum1toN(int N) {
   return N * 1LL * (N+1) / 2;
}

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

   int N;
   cin >> N;

   vector<Edge> edges;
   REP(j, N-1) {
      int u, v;
      cin >> u >> v;
      edges.push_back({u, v});
   }

   llong total = 0;
   FOR(i, 1, N)
      total += sum1toN(N - i + 1);
   DEBUG(total);

   llong res = total;
   for (Edge e : edges) {
      int u = e.u, v = e.v;
      if (u > v) swap(u, v);
      res -= u * 1LL * (N-v+1);
   }

   cout << res << endl;

   return 0;
}


Measured memory_bytes: 5300
#include<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#include<math.h>
#include<list>
#include<complex>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,x) unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;


ll const MOD = 1e9 + 7;
ll mod_p(ll x, ll y) {
	x %= MOD;
	y %= MOD;
	return (x + y + MOD) % MOD;
}

ll mod_m(ll x, ll y) {
	x %= MOD;
	y %= MOD;
	return x * y%MOD;
}

ll mod_pow(ll x, ll t) {
	x %= MOD;
	if (t == 0) {
		return 1;
	}
	else {
		ll v = mod_pow(x, t / 2);
		if (t % 2 == 0) {
			return v * v % MOD;
		}
		else {
			return v * v%MOD * x %MOD;
		}
	}
}

ll mod_inv(ll x) {
	return mod_pow(x, MOD - 2);
}

struct edge
{
	long long to; long long len;
	bool operator<(const edge& rhs) const {
		return len > rhs.len;
	}
};

ll const MAX = 1e5 + 5;
ll a[MAX], b[MAX];
ll c[MAX];
bool ord(ll x, ll y) {
	return b[x] + a[x] > b[y] + a[y];
}
int main() {
	ll n; cin >> n;
	REP(i, 1, n) {
		cin >> a[i] >> b[i];
	}
	REP(i, 1, n) {
		c[i] = i;
	}
	SORT_O(c, n, ord);
	ll ans = 0;
	REP(i, 1, n) {
		if (i % 2 == 1) {
			ans += a[c[i]];
		}
		else {
			ans -= b[c[i]];
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
    ios::sync_with_stdio(false);
    int h,n;
    while(cin>>h>>n)
    {
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum+=a[i];
        }
        if(sum>=h)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<double> VD;
#define MP make_pair
#define PB push_back
#define X first
#define Y second
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

LL triangle_area_2 (LL x1, LL y1, LL x2, LL y2, LL x3, LL y3) {
	return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);
	//freopen("In.txt", "w", stdout);
	
	LL S;
	cin >> S;
	LL M = 1000 * 1000 * 1000;
	LL T = M * M - S;	
	
	LL y = T / M;
	LL z = y + 1;
	LL x = T % M;
	
	cout << 0 << ' ' << M - x << ' ';
	cout << M - z << ' ' << 0 << ' ' ;
	cout << M - y << ' ' << M << endl;
	
	//cout << triangle_area_2(0, M - x, M - z, 0, M - y, M) << endl;
	
	cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T> ostream& operator<<(ostream& s,const multiset<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1'000'000'007;
const ll inf=1'000'000'000'000'000'00;
const int INF=1'000'000'000;
const double EPS=1e-10;
const double PI=acos(-1);

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	ll n,x,m;
	cin>>n>>x>>m;
	ll num=x;
	ll cnt=1,sum=x;
	set<ll> st;
	st.insert(num);
	ll lst;
	while(true){
		num=(num*num)%m;
		if(st.count(num)){
			lst=num;
			break;
		}
		cnt++;
		sum+=num;
		st.insert(num);
		if(n==cnt){
			cout<<sum<<endl;
			return 0;
		}
	}
	n-=cnt;
	ll loop=1,lsum=0;
	num=lst;
	while(true){
		num=(num*num)%m;
		lsum+=num;
		if(num==lst) break;
		loop++;
	}
	sum+=(n/loop)*lsum;
	n%=loop;
	num=lst;
	while(n--){
		sum+=num;
		num=(num*num)%m;
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 5900
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9+7;
//const ll MOD = 998244353;
//const ll MOD = 924844033;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

#ifdef DEBUG
#define OUTPUT(x) (output(x), outendl())
#else
#define OUTPUT(x) (void)0
#endif

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
	if(was_output)cout << " ";
	cout << a;
	was_output = true;
}
void outendl(){
	was_output = false;
	cout << endl;
}

//below here

int main(){
	int a,b,c;
	cin >> a >> b >> c;
	int ans = max(0,c-a+b);
	cout << ans << endl;
	return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ll long long
#define Pii pair<int,int>
long long INF = 1e18;
const int MOD = 1e9 + 7;

using namespace std;

Pii vp[300*300+1];
ll vl[300*300+1],answer[100000];

int main(){
    int h,w,d,q;
    scanf("%d %d %d",&h,&w,&d);
    FOR(i,1,h+1){
        FOR(j,1,w+1){
            int a;
            scanf("%d",&a);
            vp[a] = Pii{i,j};
        }
    }

    scanf("%d",&q);
    FOR(i,1,d+1) vl[i] = 0;
    FOR(i,d+1,h*w+1) vl[i] = vl[i-d] + abs(vp[i].first-vp[i-d].first) + abs(vp[i].second-vp[i-d].second);

    REP(i,q){
        int l,r;
        scanf("%d %d",&l,&r);
        answer[i] = vl[r] - vl[l];
    }
    REP(i,q) printf("%lld\n",answer[i]);
    return 0;
}


Measured memory_bytes: 3328
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

struct Node {
    int key;
    Node *next, *prev;
};

Node *nil;

Node* listSearch(int key) {
    Node *cur = nil->next;
    while (cur != nil && cur->key != key) {
        cur = cur->next;
    }
    return cur;
}

void init() {
    nil = (Node *)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}

void printList() {
    Node *cur = nil->next;
    int isf = 0;
    while (1) {
        if (cur == nil) break;
        if (isf++ > 0) printf(" ");
        printf("%d", cur->key);
        cur = cur->next;
    }
    printf("\n");
}

void deleteNode(Node *t) {
    if (t == nil) return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}

void deleteFirst() {
    deleteNode(nil->next);
}

void deleteLast() {
    deleteNode(nil->prev);
}

void deleteKey(int key) {
    deleteNode(listSearch(key));
}

void insert(int key) {
    Node *x = (Node *)malloc(sizeof(Node));
    x->key = key;
    x->next = nil->next;
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
}

int main() {
    int key, n;
    char com[20];
    int np = 0;
    int nd = 0;
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; ++i) {
        scanf("%s%d", com, &key);
        if (com[0] == 'i') {
            insert(key);
            np++;
        } else if (com[0] == 'd') {
            if (strlen(com) > 6) {
                if (com[6] == 'F') deleteFirst();
                else if (com[6] == 'L') deleteLast();
            } else {
                deleteKey(key); nd++;
            }
        }
    }
    printList();

    return 0;
}


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

int main()
{
	
	std::ios::sync_with_stdio(false);cin.tie(0);
	ll n; cin >> n;
	ll ans = n;
	for(ll i = 1; i * i <= n; ++i){
		if(n % i == 0) {
			ans = min(ans, i + n / i - 2);
		}
	}	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vll>;
using vb = vector<bool>;
 
const int INF = 2e9+5;
const ll LLINF = (1LL << 60) + 5;
 
/*
  filippos
  Contest : AtCoder DP contest
  Task : M
*/
 
int main(){
  cin.tie(0), cin.sync_with_stdio(0), cout.tie(0), cout.sync_with_stdio(0);

  const int MOD = 1e9 + 7;
  int n, k; cin >> n >> k;
  vi v(n);
  for(int &i : v)
    cin >> i;

  vvi memo(2, vi(k+1, 0)); 
  // memo[0] is current state,
  // memo[1] is previous

  // previous here means i = n, where (1,0,0...) becomes (1, 1, 1, ..) for prefix sums
  memo[1] = vi(k+1, 1);
  for(int i = n-1; i >= 0; i--){
    for(int j = 0; j <= k; j++){
      memo[0][j] = memo[1][j];
      // to avoid taking more than allowed
      if(j > v[i]) memo[0][j] = (memo[0][j] - memo[1][j - v[i] - 1] + MOD) % MOD;
    }
    partial_sum(memo[0].begin(), memo[0].end(), memo[0].begin(), [&](int x, int y) { return (x + y) % MOD;});
    swap(memo[0], memo[1]);
  }

  // now, previous has answer for i = 0, as prefix sums
  cout << (memo[1][k] - (k ? memo[1][k-1] : 0) + MOD) % MOD;



  return cout << endl, 0;
}

Measured memory_bytes: 1408
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from itertools import permutations


def main():
    N, M = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(M)]
    AB = sorted(AB, key=lambda x: (x[0], x[1]))

    result = 0
    P = permutations(range(2, N + 1), N - 1)

    for i in P:
        li = [1] + list(i)
        if sum(list(sorted(edge)) in AB for edge in zip(li, li[1:])) == N - 1:
            result += 1
    print(result)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
from math import ceil
from decimal import *
n=int(input())
prea=Decimal("1.0")
pret=Decimal("1.0")
for i in range(n):
    
    t,a=map(Decimal,input().split())
    i=max(ceil(prea/a),ceil(pret/t))
    pret,prea=t*i,a*i

print(pret+prea)

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define FORI(i,v) for (auto i = v.begin(); i != v.end(); i++)
#define ALL(v) v.begin(), v.end()
#define CHMIN(x,y) x = min(x, y)
#define CHMAX(x,y) x = max(x, y)
#define YES(b) cout << ((b) ? "YES" : "NO") << endl
#define Yes(b) cout << ((b) ? "Yes" : "No") << endl

ll A;
string B;

int main() {
    cout << fixed << setprecision(15);
    cin >> A >> B;
    cout << ((B[0] - '0') * A * 100 + (B[2] - '0') * A * 10+ (B[3] - '0') * A) / 100 << endl;
}

Measured memory_bytes: 3632
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll n, a[55];
string str[2];
int main(void){
    // Your code here!
    cin >> n >> str[0] >> str[1];
    for (ll i = 0; i < n; i++) {
        if (str[0][i] == str[1][i]) a[i]++;
    }
    ll res = (a[0] ? 3 : 6);
    for (ll i = 0; i < n - 1; i++) {
        if (a[i] && a[i + 1]) res = res * 2 % mod;
        if (a[i] && a[i + 1] == 0) res = res * 2 % mod;
        if (a[i] == 0 && a[i + 1] == 0 && str[0][i] != str[0][i + 1]) res = res * 3 % mod;
    }
    cout << res << endl;
}


Measured memory_bytes: 256
def main():
    from collections import deque

    WHITE = 0
    BLACK = 1

    CHAR = '.', '#'

    H, W = map(int, input().split())
    s = [input() for _ in range(H)]

    h = deque()
    x = CHAR.index(s[0][0])
    h.append((x, 0, 0, x))

    cost = [[H * W] * W for _ in range(H)]
    cost[0][0] = x

    while h:
        cnt, r, c, mode = h.popleft()
        if cnt > cost[r][c]:
            continue
        if r == H - 1 and c == W - 1:
            print(cnt)
            return

        delta = int(mode == WHITE)
        ncnt = cnt + delta

        if r < H - 1:
            if s[r + 1][c] == CHAR[mode]:
                if cnt < cost[r + 1][c]:
                    cost[r + 1][c] = cnt
                    h.appendleft((cnt, r + 1, c, mode))
            else:
                if delta:
                    if ncnt < cost[r + 1][c]:
                        cost[r + 1][c] = ncnt
                        h.append((ncnt, r + 1, c, 1 - mode))
                else:
                    if ncnt < cost[r + 1][c]:
                        cost[r + 1][c] = ncnt
                        h.appendleft((ncnt, r + 1, c, 1 - mode))

        if c < W - 1:
            if s[r][c + 1] == CHAR[mode]:
                if cnt < cost[r][c + 1]:
                    cost[r][c + 1] = cnt
                    h.appendleft((cnt, r, c + 1, mode))
            else:
                if delta:
                    if ncnt < cost[r][c + 1]:
                        cost[r][c + 1] = ncnt
                        h.append((ncnt, r, c + 1, 1 - mode))
                else:
                    if ncnt < cost[r][c + 1]:
                        cost[r][c + 1] = ncnt
                        h.appendleft((ncnt, r, c + 1, 1 - mode))


if __name__ == '__main__':
    main()

# import sys
#
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 43376
fn main() {
  let r: isize = get::val();
  let g: isize = get::val();
  println!("{}", (g-r)+g)
}

#[allow(dead_code)]
mod get {
  use std::io::*;
  use std::str::*;

  pub fn val<T: FromStr>() -> T {
    let mut buf = String::new();
    stdin().read_line(&mut buf).ok();
    buf.trim().parse::<T>().ok().unwrap()
  }

  pub fn vals<T: FromStr>(n: usize) -> Vec<T> {
    let mut vec: Vec<T> = vec![];
    for _ in 0 .. n {
      vec.push(val());
    }
    vec
  }

  pub fn tuple<T1: FromStr, T2: FromStr>() -> (T1, T2) {
    let mut buf = String::new();
    stdin().read_line(&mut buf).ok();
    let mut it = buf.trim().split_whitespace();
    let x = it.next().unwrap().parse::<T1>().ok().unwrap();
    let y = it.next().unwrap().parse::<T2>().ok().unwrap();
    (x, y)
  }

  pub fn tuples<T1: FromStr, T2: FromStr>(n: usize) -> Vec<(T1, T2)> {
    let mut vec: Vec<(T1, T2)> = vec![];
    for _ in 0 .. n {
      vec.push(tuple());
    }
    vec
  }

  pub fn tuple3<T1: FromStr, T2: FromStr, T3: FromStr>() -> (T1, T2, T3) {
    let mut buf = String::new();
    stdin().read_line(&mut buf).ok();
    let mut it = buf.trim().split_whitespace();
    let x = it.next().unwrap().parse::<T1>().ok().unwrap();
    let y = it.next().unwrap().parse::<T2>().ok().unwrap();
    let z = it.next().unwrap().parse::<T3>().ok().unwrap();
    (x, y, z)
  }

  pub fn tuple3s<T1: FromStr, T2: FromStr, T3: FromStr>(n: usize) -> Vec<(T1, T2, T3)> {
    let mut vec: Vec<(T1, T2, T3)> = vec![];
    for _ in 0 .. n {
      vec.push(tuple3());
    }
    vec
  }

  pub fn list<T: FromStr>() -> Vec<T> {
    let mut buf = String::new();
    stdin().read_line(&mut buf).ok();
    buf.trim().split_whitespace().map(|t| t.parse::<T>().ok().unwrap()).collect()
  }

  pub fn lists<T: FromStr>(h: usize) -> Vec<Vec<T>> {
    let mut mat: Vec<Vec<T>> = vec![];
    for _ in 0 .. h {
      mat.push(list());
    }
    mat
  }
}


Measured memory_bytes: 4352
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#include <vector>
#include<set>
#define ls (node << 1)
#define rs ((node << 1) | 1)
typedef long long ll;
using namespace std;
const int MAX = 1e6 + 20;
int pri[MAX];
int is_prii[MAX];
int hass[MAX], pic[MAX];
set<int> t;
void Prime()
{
    for (int i = 2; i < MAX; i++)
    {
        if (!is_prii[i])
            pri[++pri[0]] = i; //纪录素数， 这个pri[0] 相当于 cnt，用来计数
        for (int j = 1; j <= pri[0] && i * pri[j] < MAX; j++)
        {
            is_prii[i * pri[j]] = 1;
            if (i % pri[j] == 0)
                break;
        }
    }
}
int read()
{
    int x = 0, flag = 1;
    char c = getchar();
    while ((c > '9' || c < '0') && c != '-')
        c = getchar();
    if (c == '-')
        flag = 0, c = getchar();
    while (c <= '9' && c >= '0')
    {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return flag ? x : -x;
}
int main()
{
    Prime();
    int n = read();
    int gcdd = 0;
    int flag = 0;
    for (int i = 1; i <= n; i++)
    {
        pic[i] = read();
        gcdd = gcdd == 0 ? pic[i] : __gcd(gcdd, pic[i]);
    }
    for (int j = n; j >= 1; j--)
    {
        int tem = pic[j];
        if (flag == 1)
            break;
        for (int i = 1; pri[i]*pri[i] <= tem; i++)
        {
            if (tem <= 1)
                break;
            if (tem % pri[i] == 0)
            {
                if (t.count(pri[i]))
                {
                    flag = 1;
                    break;
                }
                t.insert(pri[i]);
                while (tem % pri[i] == 0)
                    tem /= pri[i];
            }
        }
        if (tem > 1)
        {
            if (t.count(tem))
            {
                flag = 1;
                break;
            }
            t.insert(tem);
        }
    }
    if (flag == 0)
    {
        puts("pairwise coprime");
    }
    else if (gcdd == 1)
        puts("setwise coprime");
    else
        puts("not coprime");
    return 0;
}

Measured memory_bytes: 11752
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string S,T,U;
    int n,m,i;
    cin>>S>>T;
    cin>>n>>m;
    cin>>U;

     {

        if(U==S)

           cout<<n-1<<" "<<m<<endl;
         else if(U==T)
            cout<<n<<" "<<m-1<<endl;
    }
         return 0;


}


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

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

    flag = false;
    for(int i=1; i<10; i++) {
        for (int j=i; j<10; j++) {
            if (i*j == N) {
                flag = true;
            }
        }
    }

    if (flag) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

}

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

using ll = long long;

vector<int> apps[3];

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

	#ifdef ARTHUR_LOCAL
		ifstream cin("input.txt");
	#endif

	int x,y,a,b,c;
	cin>>x>>y>>a>>b>>c;

	// iterate over #literal red apples?

	priority_queue<int> reds,greens,cols;

	for(int i=0; i<a; i++)
	{
		int a;
		cin>>a;
		reds.push(a);
	}

	for(int i=0; i<b; i++)
	{
		int a;
		cin>>a;
		greens.push(a);
	}

	for(int i=0; i<c; i++)
	{
		int a;
		cin>>a;
		cols.push(a);
	}

	priority_queue<int> cur_red;
	priority_queue<int> cur_green;
	priority_queue<int> cur_col_red;
	ll cur_ans=0LL;
	ll ans=0LL;

	int init = max(0,x-c); // number of reds we use

	for(int i=0; i<init; i++)
	{
		int cur_apple = reds.top();
		reds.pop();

		cur_ans+=cur_apple;
		cur_red.push(-cur_apple);
	}

	for(int i=0; i<x-init; i++)
	{
		int cur_apple = cols.top();
		cols.pop();

		cur_ans+=cur_apple;
		cur_col_red.push(-cur_apple);
	}

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

		if(cols.empty() || (greens.top()>cols.top()))
		{
			cur_apple=greens.top();
			greens.pop();

			cur_ans+=cur_apple;
			cur_green.push(-cur_apple);
		}

		else
		{
			cur_apple=cols.top();
			cols.pop();

			cur_ans+=cur_apple;
			cur_green.push(-cur_apple); // changed from cur_col_green
		}
	}

	ans=max(ans,cur_ans);

	for(int rr=init+1; rr<=x; rr++)
	{
		// add the best red we have

		//cout << cur_ans << endl;
		//cout << reds.top() << endl;

		cur_ans += reds.top();
		reds.pop();

		// remove something coloured

		cur_ans += cur_col_red.top();
		cols.push(-cur_col_red.top());
		cur_col_red.pop();

		// possibly adjust green

		bool change=1;

		while(change)
		{
			change=0;

			if(!cur_green.empty() && !cols.empty())
			{
				// cout << -cur_green.top() << " " << cols.top() << endl;

				if(-cur_green.top() < cols.top())
				{
					change=1;

					// swap these two

					int old_green = -cur_green.top();
					int new_col_green = cols.top();

					cur_ans += new_col_green;
					cur_ans -= old_green;

					cur_green.pop();
					cols.pop();

					cur_green.push(-new_col_green);
					cols.push(old_green);
				}
			}
		}

		ans=max(ans,cur_ans);
		//cout << cur_ans << endl;
	}

	cout << ans << endl;
}

Measured memory_bytes: 2552
#include <iostream>

using namespace std;
int main(){

    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;

    long ans = 0;
    long long min = 100000000000;
    int K = max(X, Y);
    for(int k=0; k<=K; k++){
        ans = 2*C * k + A * max(0, (X-k)) + B * max(0, (Y-k));
        if(min > ans){
            min = ans;
        }
    }
    cout << min << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL<<60;

ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

ll LCM(ll a,ll b){
    return a / GCD(a,b) * b;
}

const int MOD = 1000000007;


//void warshall_floyd(int n){
//    for(int k=0;k<n;k++){
//        for(int i=0;i<n;i++){
//            for(int j=0;j<n;j++){
//                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
//            }
//        }
//    }
//}
//ll calc_digit(ll N) {
//    ll res = 0;
//    while (N) {
//        ++res;
//        N /= 10;
//    }
//    return res;
//}
//ll sum_digit(ll N) {
//    ll res = 0;
//    while (N) {
//        res += N % 10;
//        N /= 10;
//    }
//    return res;
//}


int main(){
    ll n;cin >> n;
    vector<ll> v;
    for(int i = 0;i < n;i++){
        ll x; cin >> x;
        if(x==0){
            cout << 0 << endl;
            return 0;
        }else{
            v.push_back(x);
        }
    }
    ll num = 1;
    for(int i = 0;i < n;i++){
        if(v[i] <=1000000000000000000/num){
            num *=v[i];
        }else{
            cout << -1;
            return 0;
        }
    }
    cout << num;
}



Measured memory_bytes: 4324
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define MOD 1000000007
ll powll(ll a,ll b){ll r=1;rep(i,b){r*=a;}return r;}
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
#define in(a) scanf("%lld", &(a))
#define in2(a,b) scanf("%lld %lld",&(a),&(b))
#define in3(a,b,c) scanf("%lld %lld %lld",&(a),&(b),&(c))
#define ind(a) scanf("%lf", &(a))
#define ins(a) scanf("%s", (a))
#define inc(a) scanf("%c", &(a))
#define put(a) printf("%lld\n", (a))
#define putd(a) printf("%.15f\n", (a))
//      puts(a) printf("%s\n", a) 文字はこっち
//your code here!
int main(void){
    char S[100100];
    ins(S);
    rep(i, strlen(S)) if(!(i%2)) printf("%c", S[i]);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[110],b[110];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    ll n;
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    bool flag=0;
    for(ll i=1;i<=n-2;i++){
        bool f=0;
        for(ll j=i;j<=i+2;j++){
            if(a[j]!=b[j]){
                f=1;
                break;
            }
        }
        if(!f){
            flag=true;
            break;
        }
    }
    if(flag)    cout<<"Yes";
    else{
        cout<<"No";
    }
    return 0;
}


Measured memory_bytes: 3648
#include<cstdio>
#include<iostream>
#include<ctype.h>
#include<string>
using namespace std;
int main(){
	int N, r = 0, b = 0;
	string s;
	cin >> N >> s;
	for(int i = 0; i < N; i++){
		if(s[i] == 'R'){
			r++;
		}
		else{
			b++;
		}
	}
	if(r > b){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}
	return 0;
}

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

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

using namespace std;

using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s, t;
  cin >> s >> t;
  cout << t << s;
  return 0;
}


Measured memory_bytes: 3592
N = int(input())

H = list(map(int, input().split()))

for i in range(N):
    if i == 0:
        H[i] -= 1
        continue

    if i == N - 1:
        if H[i] < H[i - 1]:
            print('No')
            exit()
        else:
            break

    if H[i + 1] - H[i] <= -2:
        print('No')
        exit()

    if H[i + 1] - H[i] <= 0:
        if H[i] > H[i - 1]:
            H[i] -= 1
    elif H[i] < H[i + 1] and H[i - 1] < H[i]:
        H[i] -= 1

    if H[i] < H[i - 1]:
        print('No')
        exit()

print('Yes')


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

int main(){
  int N,W;
  cin >> N >> W;
  int w[N];
  int v[N];
  for(int i=0; i<N; i++){
    cin >> v[i] >> w[i];
  }

  int DP[N+1][W+1];

  for(int j=0; j<=W; j++){
    DP[0][j]=0;
  }

  for(int i=1; i<=N; i++){
    for(int j=0; j<=W; j++){
      if(j<w[i-1]){
        DP[i][j] = DP[i-1][j];
      }else{
        if(DP[i-1][j] > DP[i-1][j-w[i-1]]+v[i-1]){
          DP[i][j] = DP[i-1][j];
        }else{
          DP[i][j] = DP[i-1][j-w[i-1]]+v[i-1];
        }
      }
    }
  }

  cout << DP[N][W] << endl;

  return 0;
}


Measured memory_bytes: 7028
from math import factorial

N, K = [int(_) for _ in input().split()]
# N = 10
MOD = 10 ** 9 + 7

kaijo = [0] * (N + 1)
kaijo[0] = kaijo[1] = 1
for i in range(2, N + 1):
    kaijo[i] = (kaijo[i - 1] * i) % MOD

gyaku = [0] * (N + 1)
gyaku[0] = gyaku[1] = 1

for i in range(2, N + 1):
    # gyaku[i] = (gyaku[i - 1] * pow(i, MOD - 2, MOD)) % MOD
    gyaku[i] = pow(kaijo[i], MOD - 2, MOD)


def calc(n, k):
    # return (kaijo[n] * gyaku[n - k] * gyaku[k]) % MOD
    return factorial(n) // (factorial(n - k) * factorial(k))


def solve():
    for i in range(1, K + 1):
        n = N - K + 1
        k = i
        if k <= n:
            print((calc(n, k) * calc(K - 1, i - 1)) % MOD)
        else:
            print(0)


solve()


Measured memory_bytes: 3444
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
typedef long long ll;
using namespace std;

int main(void){
  int n,k;
	cin>>n>>k;
	if(k==1){
		cout<<0<<endl;
		return 0;
	}
	else{
		cout<<n-k<<endl;
	}
	return 0;
}


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

static const double eps = 1e-8;

inline double euclid(double dx, double dy)
{
  return sqrt(dx*dx + dy*dy);
}

int main()
{
  int n, x[401], y[401], visited[401];

  while (scanf("%d", &n), n) {
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < n; ++i)
      scanf("%d%d", x+i, y+i);

    int curr_x = 0, curr_y = 0;
    int prev_x = 0, prev_y = -1;
    double length = 0;

    for (int i = 0; i < n; ++i) {
      int dx1 = curr_x - prev_x;
      int dy1 = curr_y - prev_y;
      int dist1 = euclid(dx1, dy1);

      double max_cos = -1000;
      double min_dist = 1000;
      int min_index = -1;

      for (int j = 0; j < n; ++j) {
        if (visited[j])
          continue;

        int dx2 = x[j] - curr_x;
        int dy2 = y[j] - curr_y;
        double dist2 = euclid(dx2, dy2);
        double cos = (dx1*dx2 + dy1*dy2) / (dist1 * dist2);

        if (cos - max_cos > eps || (fabs(cos - max_cos) < eps && dist2 < min_dist)) {
          max_cos = cos;
          min_dist = dist2;
          min_index = j;
        }
      }

      prev_x = curr_x;
      prev_y = curr_y;
      curr_x = x[min_index];
      curr_y = y[min_index];
      visited[min_index] = true;
      length += min_dist;
    }

    printf("%.1lf\n", length);
  }
}

Measured memory_bytes: 0
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;

typedef struct coun {

	int ac;
	int wa;
}tsCount;
int main()
{
	
	long N,M;
	cin >> N>>M;
	vector<tsCount> array(N+1);
	char str[3] = "AC";
	char str2[3] = "WA";
	long ACcount = 0;
	long WACount = 0;
	static long num[100001];
	static char c[100001][3];
	
	for (int i=1;i<=M;i++){

		cin >> num[i] >> c[i];
		//すでにACしてる問題はWA,AC判定しない
		if (array[num[i]].ac == 1) {
			continue;
		}
		//初めてのACなのでAC増やす
		if (strcmp(c[i], str) == 0) {
			array[num[i]].ac = 1;
			ACcount++;
		}
		//WAの時。WA数をカウントする
		else {

			array[num[i]].wa++;
		}
	}
	
	//WA数のカウント
	for (int i = 1; i <= N; i++) {

		//ACしている問題のWA数のみカウントする
		if (array[i].ac == 1) {
			WACount += array[i].wa;
		}
	}

	cout << ACcount << " " << WACount;
    return 0;
}


Measured memory_bytes: 2048
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 28 20:51:34 2020

@author: naoki
"""

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

diff = [0]*N

for i in range(N-1):
    diff[i] = A[i+1] - A[i]

diff[-1] = (K - A[-1]) + A[0]

print(K - max(diff))

Measured memory_bytes: 26444
import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        RMQ rmq = new RMQ(n);
        for (int i = 0; i < q; i++) {
            int com = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();
            if(com == 0){
                rmq.update(x, y);
            }else{
                System.out.println(rmq.min(x, y+1, 0, 0, rmq.size));
            }
        }
        sc.close();
    }

}

class RMQ {

    public int n;
    public int size;
    public int[] data;
    private static int DATA_SIZE = 1_000_000;

    public RMQ(int n){
        this.n = n;
        size = 1;
        while(size < n) size *= 2;
        data = new int[DATA_SIZE];
        for (int i = 0; i < DATA_SIZE; i++) data[i] = Integer.MAX_VALUE;
    }

    public void update(int k, int a){
        k += size - 1;
        data[k] = a;
        while(0 < k){
            k = (k - 1) / 2;
            data[k] = Math.min(data[k * 2 + 1], data[k * 2 + 2]);
        }
    }

    public int min(int a, int b, int k, int l, int r){
        if(r <= a || b <= l) return Integer.MAX_VALUE;

        if(a <= l && r <= b) return data[k];

        int vl = min(a, b, k*2+1, l, (l+r)/2);
        int vr = min(a, b, k*2+2, (l+r)/2, r);
        return Math.min(vl, vr);
    }
}



Measured memory_bytes: 114120
N = int(input())
def q(i):
    print(i)
    r = input()
    if r[0]=='V': exit()
    return (r[0]=='M') ^ i%2

X = q(0)
def is_ok(m):
    if m==N: return False
    return q(m)==X
ok = 0
ng = N
while ng-ok > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m

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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

int n;
vector<ll> a;
int first = 1000000009;

ll solve(ll ans, ll sum){
	bool pos;

	if(a[0] > 0){
		pos = true;
	}else{
		pos = false;
	}

	for(int i=1; i<n; i++){
		if(pos && sum + a[i] >= 0){
			ans += sum + a[i] + 1;
			pos = false;
			sum = -1;
		}else if(!pos && sum + a[i] <= 0){
			ans += -(sum + a[i]) + 1;
			pos = true;
			sum = 1;
		}else{
			sum += a[i];
			pos = !pos;
		}
	}

	return ans;
}

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	cin >> n;

	for(int i=0; i<n; i++){
		ll t;
		cin >> t;
		if(first == 1000000009 && t != 0) first = t;
		a.pb(t);
	}

	ll ans1, ans2;
	if(a[0] == 0){
		a[0] = 1;
		ans1 = solve(1, 1);
		a[0] = -1;
		ans2 = solve(1, -1);
	}else{
		ans1 = solve(0, a[0]);
		if(a[0] > 0){
			ll tmp = a[0] + 1;
			a[0] = -1;
			ans2 = solve(tmp, -1);
		}else{
			ll tmp = -a[0] + 1;
			a[0] = 1;
			ans2 = solve(tmp, 1);
		}
	}

	cout << min(ans1, ans2)  << endl;
	
	return 0;
}


Measured memory_bytes: 1528
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
char M[105][105];
int h[105], w[105];
int main(void){
    int i, j, H, W;
    scanf("%d %d", &H, &W);
    for(i=1; i<=H; i++) scanf("%s", M[i]);
    for(i=1; i<=H; i++){
        for(j=0; j<W; j++){
            if(M[i][j]=='#') h[i] = 1;
        }
    }
    for(j=0; j<W; j++){
        for(i=1; i<=H; i++){
            if(M[i][j]=='#') w[j] = 1;
        }
    }
    for(i=1; i<=H; i++){
        for(j=0; j<W; j++){
            if(h[i]==1 && w[j]==1) printf("%c", M[i][j]);
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<n;i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

int N;
vector<vector<ll>> g;

vector<int> bfs(int s){
    vector<int> d(N,INF);
    d[s] = 0;
    queue<int> que;
    que.push(s);
    while(!que.empty()){
        int u = que.front();que.pop();
        for(int v : g[u]){
            if(d[v]!=INF) continue;
            d[v] = d[u]+1;
            que.push(v);
        }
    }
    return d;
}

int main(){
    cin >> N;
    g.resize(N);
    rep(i,N-1){
        int a,b;cin>>a>>b;a--;b--;
        g[a].pb(b);
        g[b].pb(a);
    }

    vector<int> d1 = bfs(0);    // from 0
    vector<int> d2 = bfs(N-1);

    int c1=0,c2=0;
    rep(i,N){
        if(d1[i]<=d2[i])c1++;else c2++;
    }
    if(c1>c2) cout << "Fennec" << endl;
    else cout << "Snuke" << endl;
}


Measured memory_bytes: 7040
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    matrix = [[False]*N for _ in range(N)]
    AB=LLIN_(M)
    for a,b in AB:
        matrix[a][b] = True
        matrix[b][a] = True
    def is_bridge():
        q = [0]
        visited = set()
        while q:
            v = q.pop()
            if v in visited:
                continue
            visited.add(v)
            for to in range(N):
                if matrix[v][to]:
                    if to in visited:
                        continue
                    q.append(to)
        return len(visited) < N
    ans = 0
    for a,b in AB:
        matrix[a][b] = False
        matrix[b][a] = False
        if is_bridge():
            ans += 1
        matrix[a][b] = True
        matrix[b][a] = True
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 64876
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <utility>
#include <complex>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
#define chmin(x,y) x=min(x,y);
int inf=1e9;
unsigned int xor128(){
	static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
	unsigned int t;
	t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
struct node{	//node of RBST
	int val,mn,size;
	node *lch,*rch;
	node(int v){
		val=mn=v;
		size=1;
		lch=0,rch=0;
	}
};
typedef pair<node*,node*> Pnn;
node *root;
//??????????????¢??°???????????????????????¨??????????????????????????????
node *update(node *x){
	x->size=1;
	x->mn=x->val;
	if(x->lch){
		x->size+=x->lch->size;
		chmin(x->mn,x->lch->mn);
	}
	if(x->rch){
		x->size+=x->rch->size;
		chmin(x->mn,x->rch->mn);
	}
	return x;
}
node *merge(node *x,node *y){
	if(x==0) return y;
	if(y==0) return x;
	int m=x->size,n=y->size;
	if(xor128()%(m+n)<m){
		x->rch=merge(x->rch,y);
		return update(x);
	}else{
		y->lch=merge(x,y->lch);
		return update(y);
	}
}
int count(node *x){
	if(x==0) return 0;
	return x->size;
}
Pnn split(node *x,int pos){		//[,pos),[pos,)
	if(x==0) return Pnn(0,0);
	if(pos<=count(x->lch)){
		Pnn tmp=split(x->lch,pos);
		x->lch=tmp.sc;
		return Pnn(tmp.fs,update(x));
	}else{
		Pnn tmp=split(x->rch,pos-count(x->lch)-1);
		x->rch=tmp.fs;
		return Pnn(update(x),tmp.sc);
	}
}
node *insert(node *x,int pos,int val){
	node *p = new node(val);
	Pnn tmp=split(x,pos);
	node *l=merge(tmp.fs,p),*r=tmp.sc;
	return merge(l,r);
}
node *erase(node *x,int pos){
	Pnn tmp=split(x,pos);
	node *l=tmp.fs,*r=split(tmp.sc,1).sc;
	return merge(l,r);
}
void showtree(node *c){
	if(!c) return;
	cout<<"(";
	showtree(c->lch);
	cout<<"-"<< c->val <<"-";
	showtree(c->rch);
	cout<<")";
}
void query0(int b,int c){
	Pnn x=split(root,c);
	Pnn y=split(x.fs,b);
	Pnn z=split(x.sc,1);
//	show(count(z.sc));
	node *t=merge(y.fs,z.fs);
	node *s=merge(y.sc,z.sc);
//	showtree(t);puts("");
//	showtree(s);puts("");
	root=merge(t,s);
}
void query1(int b,int c){
	Pnn x=split(root,b);
	Pnn y=split(x.sc,c+1-b);
//	show(count(y.fs));
	cout<<y.fs->mn<<endl;
	root=merge(x.fs,merge(y.fs,y.sc));
}
void query2(int b,int c){
	root=erase(root,b);
	root=insert(root,b,c);
}
int main(){
	int N,Q;
	cin>>N>>Q;
	rep(i,N){
		int a;
		scanf("%d",&a);
		root=insert(root,i,a);
	}
//	show(count(root));
//	showtree(root);puts("");
	rep(i,Q){
		int a,b,c;
		cin>>a>>b>>c;
		if(a==0) query0(b,c);
		if(a==1) query1(b,c);
		if(a==2) query2(b,c);
//		showtree(root);puts("");
	}
}

Measured memory_bytes: 15676
n = input()
a = map(int, raw_input().split())

l = []
s = 1
count = 0

while(len(a) != 0):

# for j in xrange(0,5):
	for i in xrange(0,len(a)):
		if a[i]%2 == 0 and a[i] != 0:
			l.append(a[i] >> 1)

	count += len(l)
	a = []
	a.extend(l)
	l = []

print count


Measured memory_bytes: 3460