akhauriyash/Code-Regression huggingface dataset:
// Problem : B - Bishop
// Contest : Panasonic Programming Contest 2020
// URL : https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);
#define endl "\n"
#define debug(x) cerr<<#x<<" = "<<(x)<<endl;

typedef vector<int> vi;

int32_t main()
{
	IOS;
	int h, w;
	cin >> h >> w;
	if(h == 1 or w == 1)
		return cout << 1 << endl, 0;
	int p = (h*w+1)/2;
	cout << p << endl;
	return 0;
}


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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

typedef long long ll;
typedef long double R;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

// Problem Specific Parameter:

int main() {
  int n; cin >> n;
  ll minCost = 100000000;
  vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = -100; i <= 100; i++) {
    ll cost = 0;
    for(int j = 0; j < n; j++) {
      cost += (ll)pow(a[j] - i, 2);
    }
    minCost = min(minCost, cost);
  }
  cout << minCost << endl;

  return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split(" ")))
mod = 10 ** 9 + 7

ans = 0
for i in range(61):
    zero, one = 0, 0
    for j in range(N):
        if (A[j] >> i) & 1 == 0:
            zero += 1
        else:
            one += 1
    ans += zero * one * (1 << i)
    ans %= mod
print(ans)

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

ll N;
vector<ll> V(1000);

void print(ll x) {
	cout << "node " << x << ": key = " << V[x] << ", ";
	if (x > 1) {
		cout << "parent key = " << V[x / 2] << ", ";
	}
	if (x * 2 <= N) {
		cout << "left key = " << V[x * 2] << ", ";
	}
	if (x * 2 + 1 <= N) {
		cout << "right key = " << V[x * 2 + 1] << ", ";
	}
	cout << endl;
}

int main() {
	cin >> N;
	for (ll i = 1; i < N + 1; i++)
		cin >> V[i];
	for (ll i = 1; i < N + 1; i++) {
		print(i);
	}
}



Measured memory_bytes: 3120
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


int N;
int[] A, B;

int[][] G;
int[] cols;
void dfs(int u, int p, int c) {
  cols[u] = c;
  foreach (v; G[u]) {
    if (v != p) {
      dfs(v, u, c ^ 1);
    }
  }
}

void main() {
  try {
    for (; ; ) {
      N = readInt();
      A = new int[N - 1];
      B = new int[N - 1];
      foreach (i; 0 .. N - 1) {
        A[i] = readInt() - 1;
        B[i] = readInt() - 1;
      }
      
      G = new int[][N];
      cols = new int[N];
      cols[] = -1;
      foreach (i; 0 .. N - 1) {
        G[A[i]] ~= B[i];
        G[B[i]] ~= A[i];
      }
      dfs(0, -1, 0);
      debug {
        writeln("cols = ", cols);
      }
      
      int[][] rs;
      if (cols.count(0) <= N / 3) {
        rs = [[0], [1, 2, 0]];
      } else if (cols.count(1) <= N / 3) {
        rs = [[1, 2, 0], [0]];
      } else {
        rs = [[1, 0], [2, 0]];
      }
      
      auto vals = new DList!int[3];
      foreach (x; 1 .. N + 1) {
        vals[x % 3].insertBack(x);
      }
      auto ans = new int[N];
      foreach (u; 0 .. N) {
        foreach (r; rs[cols[u]]) {
          if (!vals[r].empty) {
            ans[u] = vals[r].front;
            vals[r].removeFront;
            goto found;
          }
        }
        assert(false);
       found:
      }
      foreach (u; 0 .. N) {
        if (u > 0) write(" ");
        write(ans[u]);
      }
      writeln();
    }
  } catch (EOFException e) {
  }
}


Measured memory_bytes: 22012
import numpy as np


N, D = list(map(int, input().split()))
X = [list(map(int, input().split())) for i in range(N)]

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        dis = np.linalg.norm(np.array(X[i]) - np.array(X[j]))
        if dis - int(dis) < 0.00000001:
            ans += 1
print(ans)


Measured memory_bytes: 12500
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cstdio>
#pragma warning(disable:4996)
using namespace std;
 
long long dp[2005][2005];
const int MOD = 1e9 + 7;
 
 
long long combi(int i, int j)
{
	long long &ret = dp[i][j];
	if (ret != -1)return ret;
	if (j > i)return 0;
	if (j == 0)return 1;
	
	return ret = (combi(i - 1, j - 1) + combi(i - 1, j)) % MOD;
	
}
 
int main()
{
	int N, K;
	scanf("%d %d", &N, &K);
	int blue = K;
	int red = N - K;
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= K; i++) 
		cout << (combi(blue - 1, i - 1)*combi(red + 1, i))%MOD << '\n';
	
}

Measured memory_bytes: 31744
X, Y, Z, K = gets.split(' ').map(&:to_i)
a = gets.split(' ').map(&:to_i)
b = gets.split(' ').map(&:to_i)
c = gets.split(' ').map(&:to_i)

e = []
score = []

a.each do |i|
  b.each do |j|
    e.push(i + j)
  end
end

e.sort.reverse[0, K].each do |i|
  c.each do |j|
    score.push(i + j)
  end
end

score.sort.reverse[0, K].each do |i|
  puts i
end

Measured memory_bytes: 109804
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e9

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;


ll a, b, ptr, truth[4001];
stack <ll> honest;
char ans;

int main()
{
	cin >> a >> b;
	if(a==0){
		cout << "! ";
		for(int i = 0; i < b; i++){
			cout << "0";
		}
		cout << endl;
		fflush(stdout);
		return 0;
	}
	if(a<=b){
		cout << "Impossible\n";
		fflush(stdout);
		return 0;
	}
	else{
		while(ptr<a+b){
			if(honest.empty()){
				honest.push(ptr);
			}
			else{
				cout << "? " << honest.top() << " " << ptr << endl;
				fflush(stdout);
				cin >> ans;
				if(ans=='Y'){
					honest.push(ptr);
				}
				else{
					honest.pop();
				}
			}
			ptr++;
		}
		ll x = honest.top();
		truth[x]=1;
		for(int i = 0; i < a+b; i++){
			if(i!=x){
				cout << "? " << x << " " << i << endl;
				fflush(stdout);
				cin >> ans;
				truth[i]=(ans=='Y');
			}
		}
		cout << "! ";
		for(int i = 0; i < a+b; i++){
			cout << truth[i];
		}
		cout << endl;
		fflush(stdout);
		return 0;
	}
}


Measured memory_bytes: 724
//Mahir Ratanpara (DA-IICT)
#include<bits/stdc++.h>
using namespace std;
#define Ff(i,a,n) for(i=a;i<n;i++)
#define Fr(i,a,n) for(i=a;i>n;i--)
#define ll long long
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
typedef pair<ll, ll>	pa;
typedef vector<ll>		vc;
typedef vector<pa>		vp;
typedef vector<vc>		vvc;
int mpow(int base, int exp); 
void ipgraph(int m);
void dfs(int u, int par);
const int mod = 1000000007;
const int N = 3e5, M = N;
//=======================

vc g[N];
ll a[N];

int main() {
    FAST;
    ll t, i, j, k, p, q, r, x, y, u, n, m;
    cin>>n>>m;
    cout<<min(n%m,m-n%m);
    
    return 0;
}

int mpow(int base, int exp) {
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
  }
  return result;
}

void ipgraph(int n, int m){
	int i, u, v;
	while(m--){
		cin>>u>>v;
		g[u-1].pb(v-1);
		g[v-1].pb(u-1);
	}
}

void dfs(int u, int par){
	for(int v:g[u]){
		if (v == par) continue;
		dfs(v, u);
	}
}

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

int main() {
	int n,a,b;
	cin >> n >> a >> b;
	
	int count=0;
	
	int t[n];
	for(int i=0; i<n; i++){
		cin >> t[i];
		if(t[i]<a || t[i]>=b){count++;}
	}
	
	cout << count <<endl;
	
	return 0;
}

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

#define rep(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ROF(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define all(a) (a).begin(),(a).end()
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
#define SUM(a) accumlate(all(a),0)
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef long long ll;

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


Measured memory_bytes: 256
while True:
    a, op, b = input().split()
    a = int(a)
    b = int(b)
    if op == '?':
        break
    elif op == '+':
        print(a+b)
    elif op == '-':
        print(a-b)
    elif op == '*':
        print(a*b)
    elif op == '/':
        print(a//b)


Measured memory_bytes: 5592
//#include <boost/multiprecision/cpp_dec_float.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <algorithm>
#include <bitset>
#include <iomanip>
using namespace std;
//namespace mp = boost::multiprecision;
//using llll = mp::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
//using Real = mp::number<mp::cpp_dec_float<1024>>;
using ll = long long;
const double EPS = 1e-10;
const ll MOD = 7+(1e+9);

int main(){
  ll n;
  double ans=0;
  cin>>n;
  vector<ll>v(n,0);
  ll t=1;
  for(ll i=0;i<n;i++){
    cin>>v[i];
    t*=v[i];
  }
  for(ll i=0;i<n;i++){
    ans+=(double)1/v[i];
  }
  ans=(double)1/ans;
  std::cout << std::fixed;
  cout<<setprecision(8)<<ans<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String s = in.nextLine();

        System.out.println( "Sunny".equals(s) ? "Cloudy" : "Cloudy".equals(s) ? "Rainy" : "Sunny" );

    }

}


Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>


int main() {
    int k, q; std::cin >> k >> q;
    std::vector<long long> d(k), dm(k);
    for (int i = 0; i < k; i++) std::cin >> d[i];
    while (q--) {
        long long n, x, m; std::cin >> n >> x >> m;
        x %= m;
        for (int i = 0; i < k; i++) dm[i] = d[i] % m == 0 ? m : d[i] % m;
        long long sum = std::accumulate(dm.begin(), dm.end(), 0LL);
        long long len = (n - 1) / k;
        long long y = x + sum*len
            + std::accumulate(dm.begin(), dm.begin() + (n - 1) % k, 0LL);
        long long ng = y / m;
        std::cout << n - 1 - ng << std::endl;
    }
    return 0;
}


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

using namespace std;

int main(void)
{
    int cc;
    int dd;

    cin >> cc;
    cin >> dd;

    if(cc < dd)
        cout  << "a < b"  << endl;
    else if(cc > dd)
        cout  << "a > b" << endl;
    else
        cout  << "a == b" << endl;


   return 0;
}



Measured memory_bytes: 3104
#include <bits/stdc++.h>
//#include <stdio.h>
using namespace std;
#define vsort(vec) sort(vec.begin(), vec.end())
#define vreverse(vec) reverse(vec.begin(), vec.end())
using ll =long long;
const ll INF =1001001001;

//最大公約数
ll gcd(ll a, ll b){
   if (a%b==0){
       return(b);
   }else{
       return(gcd(b,a%b));
   }
}
//最小公倍数
ll lcm(ll a, ll b){
   return a*b/gcd(a,b);
}
/*
//素数判定
ll isprime(ll n){
  bool prime=true;
  for(int i=2;i<n;i++){
    if(n%i==0){
      prime=false; break;
    }
  }
if(prime){cout<<n<<" is prime"<<endl;
         }else{cout<<n<<" is not prime"<<endl;}
}
*/
//階乗　20くらいが限界
ll factorial(ll n){
  ll a=1;ll b=n;
  for(int i=0;i<n;i++){
    a*=b;
    b--;
  }
  return a;
}

//組み合わせ　nCr
ll comb(ll a,ll b){
  ll c;
  c=factorial(a)/(factorial(a-b)*factorial(b));
  return c; 
}




/*10億7。　　　100000007
2*2行列 H*W
vector<vector<int>> vec(H,vector<int>(W));
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
cin>>vec[i][j];
  }
}

文字列→数列
string S;int A=atoi(S.c_str());
数列→文字列
int A;string S=to_string(A);
数字判定　isdigit(a)
pair宣言　pair<int,int> p(5,7);
ソート　sort(vec.begin(),vec.end());
*/

int main(){
cout<<fixed<<setprecision(10);
//cin.tie(0); ios::sync_with_stdio(false);

ll A,B,M;
  cin>>A>>B>>M;
  vector<ll> vecA(A);
  vector<ll> vecB(B);
  vector<ll> vecAp(A);
  vector<ll> vecBp(B);
  for(int i=0;i<A;i++){
    cin>>vecA[i];
    vecAp[i]=vecA[i];
  }
  for(int i=0;i<B;i++){
    cin>>vecB[i];
    vecBp[i]=vecB[i];
  }
  
  vector<vector<ll>> vecM(M,vector<ll>(3));
  for(int i=0;i<M;i++){
for(int j=0;j<3;j++){
cin>>vecM[i][j];
  }
}
  ll m=10000000;
  ll PP;
  vsort(vecAp);
  vsort(vecBp);
  m=vecAp[0]+vecBp[0];
      
  ll ans=m;
  ll val;
  for(int i=0;i<M;i++){
      val=vecA[vecM[i][0]-1]+vecB[vecM[i][1]-1]-vecM[i][2];
    ans=min(ans,val);
    val=1000000;
  }
  
  cout<<ans<<endl;
  
  
}




Measured memory_bytes: 8832
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
// struct edge { int u, v; ll w; };

int INF = INT_MAX;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

struct edge { int u, v, c, f; };

struct ford_fulkerson {
	int N;
	vector<vector<int> > G;
	vector<edge> E;
	ford_fulkerson(int N) : N(N), G(N) {}
	void add_edge(int u, int v, int c) {
		int i = E.size();
		G[u].push_back(i);
		G[v].push_back(~i);
		E.push_back(edge{u, v, c, 0});
	}
	int dfs(int u, int t, int d, vector<bool>& vis) {
		if (u == t) return d;
		if (vis[u] || !d) return 0;
		vis[u] = true;
		for (int i: G[u]) {
			int v, c;
			if (i >= 0) v = E[i].v, c = E[i].c - E[i].f;
			else v = E[~i].u, c = E[~i].f;
			int _d = dfs(v, t, min(d, c), vis);
			if (!_d) continue;
			if (i >= 0) E[i].f += _d;
			else E[~i].f -= _d;
			return _d;
		}
		return 0;
	}
	int max_flow(int s, int t) {
		int f = 0;
		for (;;) {
			vector<bool> vis(N);
			int d = dfs(s, t, INF, vis);
			if (!d) break;
			f += d;
		}
		return f;
	}
};

int main() {
	int N, M; cin >> N >> M;
	ford_fulkerson G(N);
	while (M--) {
		int u, v, c; cin >> u >> v >> c;
		G.add_edge(u, v, c);
	}
	cout << G.max_flow(0, N - 1) << endl;
}

Measured memory_bytes: 3192
import numpy as np
from copy import deepcopy
from heapq import heappop, heappush
from bisect import bisect_left, bisect
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations

H, W, K = map(int, input().split())
c = np.zeros((W, H))

for h in range(H):
    s = list(input())
    for w in range(W):
        if s[w] == ".":
            c[w, h] = 0
        else:
            c[w, h] = 1

n = 0

for wt in product([1, 0], repeat=W):
    for ht in product([1, 0], repeat=H):
        d = deepcopy(c)
        for i in range(W):
            if wt[i] == 1:
                d[i, :] = 0
        for i in range(H):
            if ht[i] == 1:
                d[:, i] = 0
        if np.count_nonzero(d) == K:
            n += 1
print(n)
exit()


Measured memory_bytes: 27180
n, k = map(int, input().split())

hl = []
for _ in range(n):
    hl.append(int(input()))

hl.sort()

ans = 10**9+1
for i in range(len(hl)-k+1):
    ans = min(ans, hl[i+k-1]-hl[i])

print(ans)


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

using namespace std;
using ll = long long;

ll N;
ll A[100010];
ll d[100010];

int main(){

    cin >> N;
    ll tot = 0;
    for(int i = 0; i < N; i++){
        cin >> A[i];
        tot += A[i];
    }
    if(tot % (N*(N + 1) / 2) != 0){
        cout << "NO" << endl;
        return 0;
    }
    ll k = tot / (N*(N + 1) / 2);
    for(int i = 0; i < N; i++){
        d[i] = A[(i + 1) % N] - A[i];
        d[i] -= k;
    }
    for(int i = 0; i < N; i++){
        if(d[i] <= 0 && abs(d[i]) % N == 0){
            k -= abs(d[i]) / N;
        }
        else{
            cout << "NO" << endl;
            return 0;
        }
    }

    if(k == 0){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 1792
S = list(input())
case10 = 0
case01 = 0
if len(S) == 0:
    print(0)
    exit()

for i,val in enumerate(S):
    if i % 2 == 0:
        if val == '1':
            case01 += 1
        else:
            case10 += 1
    else:
        if val == '1':
            case10 += 1
        else:
            case01 += 1

print(min(case01,case10))


Measured memory_bytes: 3956
#include <iostream>

int main() {
    long long a, b;
    std::cin >> a >> b;

    if (a > 0) {
        std::cout << "Positive" << std::endl;
    } else if (b < 0) {
        std::cout << (((b - a) % 2 == 1) ? "Positive" : "Negative") << std::endl;
    } else {
        std::cout << "Zero" << std::endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<queue>
#include<string>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<utility>
#include<map>
#include<set>
#include<vector>
#include<functional>

using namespace std;

#ifdef DEBUG
#define dprintf      printf
#define dout(x)      cout<<#x<<" = "<<x<<endl;
#define darray(x,n)    {int i;for(i=0;i<(n);i++)printf(#x"[%d] = %d\n",i,*((x)+i));}
#define dloop(i,s,g) for((i)=(s);(i)<(g);(i)++)
#define drep(i,n)    for((i)=0;(i)<(n);(i)++)
#define dstop()      scanf("%*c")
#else
#define dprintf      (1)?0:printf
#define dout(x)
#define darray(x,n)
#define dloop(i,s,g) if(1){}else
#define drep(i,n)    if(1){}else
#define dstop()
#endif

#define F    first
#define S    second
#define pb   push_back
#define mp   make_pair

#define loop(i,s,g) for((i)=(s);(i)<(g);(i)++)
#define rep(i,n)    for((i)=0;(i)<(n);(i)++)
#define all(x)      (x.begin(),x.end())

//#define int long long;
#ifndef int
#define INF  (0x7fffffff)
#else
#define LINF (0x7fffffffffffffff)
#endif

typedef  long long           ll;
typedef  unsigned            ui;
typedef  unsigned long long  ull;
typedef  pair<int,int>       i_i;
typedef  pair<ll,int>        ll_i;
typedef  pair<ll,ll>         ll_ll;
typedef  pair<double,int>    d_i;
typedef  pair<double,double> d_d;

bool check(int n,int d[10])
{
    while(n>0)
      {
        if(d[n%10]==1)return true;
        n/=10;
      }
    return false;
}
 
signed main()
{    
  int n,k,in,d[10]={};
  int i;
  
  cin>>n>>k;
  rep(i,k)
    {
      cin>>in;
      d[in]=1;
    }

  while((check(n++,d)));
  
  cout<<n-1<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intput(i) cout << i << endl
#define ll long long
#define stringput(s) cout << (string)(s) << endl

int main(){
  string S;
  cin >> S;
  string ans = "No";
  if(S[2] == S[3] && S[4] == S[5]){
    ans = "Yes";
  }
  cout << ans << endl;
}


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

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

typedef long long ll;
const ll MOD = 1e9 + 7;

int main() {
  ll L, R;
  std::cin >> L >> R;

  int ans = 2018;
  if(R - L >= 2018 or R - L + L % 2019 >= 2019) {
    ans = 0;
  } else {
    for(int i = L % 2019; i <= R % 2019; ++i) {
      for(int j = i + 1; j <= R % 2019; ++j) {
        ans = std::min(ans, i * j % 2019);
      }
    }
  }
  std::cout << ans << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int N; cin >> N;
    int a[N], sum = 0;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            sum += a[i] * a[j];
        }
    }
    cout << sum << endl;
	return  0; 
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  int64_t D;
  cin >> N >> D;
  int count =0;
  
  for(int i=0; i<N; i++){
    int64_t X,Y;
    cin >> X >> Y;
    if(X*X + Y*Y <= D*D) count ++;
  }
  
  cout << count << endl;

}

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

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

using namespace std;

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

  int result = 0;
  int x = 0;
  rep(i, n) {
    if (s[i] == 'I') x++;
    if (s[i] == 'D') x--;

    result = max(result, x);
  }
  cout << result << endl;

  return 0;
}

Measured memory_bytes: 256
from statistics import median_low, median_high

n = int(input())
a = [x-(i+1) for i, x in enumerate(list(map(int, input().split())))]


b1 = median_low(a)


b2 = median_high(a)
ans1 = 0
ans2 = 0

for aa in a:
    ans1 += abs(aa-b1)
    ans2 += abs(aa-b2)
print(min(ans1, ans2))


Measured memory_bytes: 27252
DBG = true
n = gets.to_i
h = gets.split.map{|x| x.to_i}
cnt = 0
for i in 1..100
  cnt += 1 if h[0] >= 1
  for j in 1...n
    cnt += 1 if h[j-1] == 0 && h[j] >= 1
  end
  for j in 0...n
    h[j] -= 1 if h[j] >= 1
  end
end
puts "#{cnt}"


Measured memory_bytes: 1788
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <cassert>
#include <bitset>

using namespace std;

using int64 = long long;

/////////////////////
// Code starts here//
/////////////////////


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

    int N, Q;
    string S;

    cin >> S;
    N = S.size();
    cin >> Q;

    bool rev = false;

    deque<char> left, right;

    for (int i = 0; i < Q; i++) {
        int t, f;
        char x;

        cin >> t;

        if (t == 1) {
            rev = !rev;
        } else {
            cin >> f >> x;

            if (f == 1) {
                if (!rev) {
                    left.push_front(x);
                } else {
                    right.push_back(x);
                }
            } else {
                if (!rev) {
                    right.push_back(x);
                } else {
                    left.push_front(x);
                }
            }
        }
    }

    string res;

    if (!rev) {
        for (auto x : left)
            res += x;
        res += S;
        for (auto x : right)
            res += x;
    } else {
        while (!right.empty()) {
            res += right.back();
            right.pop_back();
        }
        reverse(S.begin(), S.end());
        res += S;
        while (!left.empty()) {
            res += left.back();
            left.pop_back();
        }
    }

    cout << res << "\n";
    return 0;
}


Measured memory_bytes: 1328
using System;
class Program{
    static int[] insert(int[] array, int val){
        if(val <= array[2]){
            return array;
        }else if(val <= array[1]){
            array[2] = val;
            return array;
        }else if(val <= array[0]){
            array[2] = array[1];
            array[1] = val;
            return array;
        }else{
            array[2] = array[1];
            array[1] = array[0];
            array[0] = val;
            return array;
        }
    }


    static void Main(){
        int[] array = new int[3];
        //array is array of top 3 height


        int tmp, i;
        for(i=0;i<3;i++){
            array[i] = 0;
        }
        for(i=0;i<10;i++){
            tmp = int.Parse(Console.ReadLine());
            array = insert(array, tmp);
        }
        for(i=0;i<3;i++){
            Console.WriteLine("{0}", array[i]);
        }
    }
}

Measured memory_bytes: 9108
// #pragma GCC optimize ("O2")
// #pragma GCC target("avx2")
#include "bits/stdc++.h"
	
#define PI 3.141592653589793L
#define FAST ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// Use for file I/O;
#define FIN string _fname = "convention2"; \
			string _is = _fname + ".in", _os = _fname + ".out"; \
			freopen(_is.c_str(), "r", stdin); \
			freopen(_os.c_str(), "w", stdout);

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

using namespace std;

const char nl = '\n';

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
 
const ll inf = 1e9;
const ll inf2 = 1e18 + 99LL;
const ld inf3 = 1e14;
const ll mod = 1e9 + 7;
const ld eps = 1e-6;
 
const int logn = 19, maxn = 2e3+5, maxm = 1e5 + 5;

int main() {
	FAST;
	int n;
	cin >> n;
	vector<ll> a(n), b(n);
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		a[i] = x + y;
		b[i] = y - x + inf;
	}
	sort(all(a));
	sort(all(b));
	cout << max(a[n - 1] - a[0], b[n - 1] - b[0]);
}

Measured memory_bytes: 6332
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)


Measured memory_bytes: 87124
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc=new Scanner(System.in);
		int A=sc.nextInt();
		int B=sc.nextInt();
		int C=sc.nextInt();
		if(A+B>=C) {
			System.out.println("Yes");
		}
		else {
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 22740
# -*- coding: utf-8 -*-
import sys
from collections import deque
N,K=map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	#隣接リスト
for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)
   
mod=10**9+7
ans=1

#DFS
start=1
Visit=[ 0 for _ in range(N+1) ] #訪問した頂点
q=deque()
q.append((start,K)) #(現在位置、使用できる色の数)
Visit[start]=1

while q:
    fro,k=q.pop()
    ans*=k  #答えに使用できる色の通り数をかける
    ans%=mod
    if fro==1:  #ルートノードの時は
        num=K-1
    else:       #ルートノードじゃない時は
        num=K-2  #K-2色使用できる
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1	#訪問済みVisitに1をセットする。4行上のpopleftの直後でVisitをセットすると同じ頂点がqに入り、TLEする
            q.append((to,num))
            num-=1
print ans

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

int main() {
    string s;
    cin >> s;
    int counter = 0;
    if (s[0] == '1') ++counter;
    if (s[1] == '1') ++counter;
    if (s[2] == '1') ++counter;
    cout << counter << endl;
}

Measured memory_bytes: 3596
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

a, b, _ = rm()
print(a*b//2)














Measured memory_bytes: 27212
#include<iostream>
#include<stdio.h>
using namespace std;

int main(){
    int h, w;
    for (int i = 0; ; i++)
    {
        cin>>h>>w;
        if (h == 0 && w == 0)
        {
            break;
        }

        for (int j = 0; j < h; j++)
        {
            for (int k = 0; k < w; k++)
            {
                if (j == 0 or k == 0 or j == (h - 1) or k == (w - 1))
                {
                    cout<<"#";
                }else
                {
                    cout<<".";
                }
                
            }
            cout<<endl;
        }
       cout<<endl; 
    }
}


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

int main()
{
  int ans = 0;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    ans += (b - a) + 1;
  }
  cout << ans << endl;
}


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

#define sorted(vector) sort(vector.begin(),vector.end())
#define vmin(vector) *min_element(vector.begin(),vector.end())
#define vmax(vector) *max_element(vector.begin(),vector.end())
#define vsum(vector) accumulate(vector.begin(),vector.end(),0)
#define append(a) push_back(a)
#define int(a) stoi(a)
#define str(a) to_string(a)
#define bisect_left(vector,a) lower_bound(vector.begin(),vector.end(),a)
#define bisect_right(vector,a) upper_bound(vector.begin(),vector.end(),a)

using namespace std;

int main(void){
    long long n,k,tmp1,tmp2;
    vector<vector<long long>> xy;
    vector<long long> x;
    vector<long long> y;
    vector<long long> ans;

    cin>>n>>k;
    for(int i=0; i<n ; i++){
        cin>>tmp1>>tmp2;
        xy.push_back(vector<long long>{tmp1,tmp2});
        x.push_back(tmp1);
        y.push_back(tmp2);
    }
    sorted(x);
    sorted(y);
    int kcount=0;
    for(int i=0; i<n ; i++){
        for(int j=i; j<n ; j++){
            for(int r=0; r<n ; r++){
                for(int e=r; e<n ; e++){
                    kcount=0;
                    for(int xxyy=0; xxyy<n ; xxyy++){
                        kcount+= ( x[i]<=xy[xxyy][0] and xy[xxyy][0]<=x[j] and y[r]<=xy[xxyy][1] and xy[xxyy][1]<=y[e] );
                    }
                    if (kcount>=k){
                        ans.push_back( (x[j]-x[i])*(y[e]-y[r]) );
                    }
                }
            }
        }
    }
    cout<<vmin(ans)<<endl;
}


Measured memory_bytes: 17772
//package april2020;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FastReader scn = new FastReader();
		
		int n = scn.nextInt();
		
		HashSet<String> hs = new HashSet<String>();
		for(int i=0;i<n;i++) {
			String t = scn.next();
			hs.add(t);
		}
		System.out.println(hs.size());
	}
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }

}


Measured memory_bytes: 72712
//testing solution by:fmota    
#include <bits/stdc++.h>
    using namespace std;
    int main(){
      string s; cin >> s;
      if(s[0] != 'A') cout << "WA" << endl;
      else {
        int cnt = 0;
      	for(int i = 2; i+1 < s.size(); i++) cnt += s[i] == 'C';
        if(cnt != 1) cout << "WA" << endl;
        else {
        	bool bad = false;
         	for(int i = 0; i < s.size(); i++) if(s[i] != 'A' && s[i] != 'C'){
            	if(isupper(s[i])){
                  cout << "WA" << endl;
                  return 0;
                }
            }
          	cout << "AC" << endl;
        }
      }
      return 0;
    }

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

int n;
vector<int> g[110];
int in[110], out[110];

void dfs(int v, int& t) {
    in[v] = ++t;
    for (int nv : g[v]) if (!in[nv]) {
        dfs(nv, t);
    }
    out[v] = ++t;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int u, k;
        cin >> u >> k;
        for (int j = 0; j < k; ++j) {
            int v;
            cin >> v;
            g[u - 1].push_back(v - 1);
        }
    }
    int t = 0;
    for (int i = 0; i < n; ++i) if (!in[i]) {
        dfs(i, t);
    }
    for (int i = 0; i < n; ++i) {
        cout << i + 1 << " " << in[i] << " " << out[i] << endl;
    }
}


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

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

	vector<int> ac(n);
	for(int i = 0; i<n;i++) ac[i] = arr[i];
	sort(ac.begin(),ac.end());

	int nlarge = ac[n - n/2];

	for(int i = 0;i<n;i++){
		if(arr[i] < nlarge) cout<<nlarge<<endl;
		else cout<<ac[n - n/2 - 1]<<endl;
	}

}

Measured memory_bytes: 3712
#include<stdio.h>

int main(void){


int a,b,c;


int tmp;


scanf("%d %d %d",&a,&b,&c);


if(a>b){


tmp=a; 

a=b;

b=tmp;

}


if(a>c){


tmp=a;

 a=c;

c=tmp;

}


if(b>c){


tmp=b;

 b=c;

 c=tmp;

}


printf("%d %d %d\n",a,b,c);


return 0;


}

Measured memory_bytes: 596
import java.util.*;
class Main{
    static Scanner sc=new Scanner(System.in);
    public static void main(String[] args){
        int N = sc.nextInt();
        int M = sc.nextInt();
        int a[] = new int[N];
        double sum = 0;
        for(int i=0;i<N;i++){
            a[i] = sc.nextInt();
            sum = sum+a[i];
        }
        Arrays.sort(a);
        for (int i = 0; i < a.length/2; i++) {
            int temp = a[i];
            a[i]= a[a.length - 1 - i];
            a[a.length - 1 - i]= temp;
        }
        boolean anst = true;
        for(int i=0;i<M;i++){
            if(a[i]<(sum/(4*M))){
                anst = false;
                break;
            }
        }
        if(anst)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

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

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 200010;
const double eps = 1e-6;

int n;
int a[N], b[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) b[i] = a[i];
    sort(a + 1, a + 1 + n);

    int l = a[n / 2], r = a[n / 2 + 1];
    for(int i = 1; i <= n; i++)
        if(b[i] < r) cout << r << endl;
        else cout << l << endl;
    return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define re return
#define pb push_back
#define po pop_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define ss second.second
#define sf second.first
#define ff first.first
#define fs first.second
#define si size
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi 3.14159265359
#define er erase
#define in insert
#define em empty
#define ft front
#define fo(i,n) for(i = 0; i < n; i++)
#define ro(i,n) for(i = n - 1; i >= 0; i--)
#define fr(i,j,n) for(i = j; i < n; i++)
#define rf(i,j,n) for(i=n-1;i>=j;i--)
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;
typedef std::pair<int,int> ii;
typedef std::vector<ii> vii;
typedef std::vector<std::string> vs;
typedef double dl;
typedef long double ld;
typedef long long ll;
typedef std::pair<ll, ll> pll;
typedef std::vector<ll> vll;
#define filename ""
using namespace std;
   const int N=(int)1e5;
   int a[N];
int main()
{
    /*
	freopen(filename".in","r",stdin);
	freopen(filename".out","w",stdout);
	*/
	/*
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    */
    int n,i;
    cin>>n;
    string s;
    cout<<0<<endl;
    cin>>s;
    if (s[0]=='V')
    {
        re 0;
    }
    if (s[0]=='M')
    {
        a[0]=1;
    }
    else
    {
        a[0]=0;
    }
    int z=0;
    int q=a[0];
    int p=0;
    int x=n;
    int c;
    while(z<=x)
    {
        c=(z+x)/2;
        cout<<c<<endl;
        cin>>s;
        if (s[0]=='V')
        {
            re 0;
        }
        if (s[0]=='M')
        {
            a[c]=1;
        }
        else
        {
            a[c]=0;
        }
        if (abs(a[c]-q)==(c-p)%2)
        {
            z=c+1;
            q=a[c];
            p=c;
        }
        else
        {
            x=c-1;
        }
    }
    re 0;
}


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

int main(){
  long long A, B;
  cin >> A >> B;
  long long dif = A - B;
  long long ans;
  if(dif % 2 != 0) cout << "IMPOSSIBLE" << endl;
  else{
    if(A < B){
      ans = A + abs(dif / 2);
      cout << ans << endl;
    }else{
      ans = B + abs(dif / 2);
      cout << ans << endl;
    }
  }
}

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

//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4"

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define int ll
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
 
using namespace std;
 
const int maxn = (int)1e5+100;
const int mod = (int)1e9 + 7;
 
#define inf mod
 
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;   
typedef vector<ll> Vll;               
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;

int n, dp[maxn][2];
vi g[maxn];

void dfs(int v, int p = 0){
  dp[v][0]=dp[v][1]=1;
  for(auto to:g[v])
    if(to!=p){
      dfs(to,v);
      dp[v][0]=dp[v][0]*((dp[to][0]+dp[to][1])%mod)%mod;
      dp[v][1]=dp[v][1]*dp[to][0]%mod;
    }
}
main () {
  cin>>n;
  forn(i,1,n-1){
    int u, v;
    cin>>u>>v;
    g[u].pb(v);
    g[v].pb(u);
  }
  dfs(1);
  cout<<(dp[1][0]+dp[1][1])%mod;
}

Measured memory_bytes: 14208
//CODEFORCES:-
//coded by AMAN BHARTI NIT PATNA
//ALL RIGHTS RESERVED
//ECE 2K18

#include<bits/stdc++.h>
using namespace std;

//#define home
#define TASK "soln"
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define pb push_back
#define ll long long int
#define br cout<<endl;
#define fo for(int i=0;i<n;i++)
#define foo for(int i=1;i<=n;i++)
#define mod 1000000007


void solve(){
    string s,t;
    cin>>s>>t;
    
    int n =s.length(),m =t.length();
    int dp[n+1][m+1];
    memset(dp,-1,sizeof(dp));

    for(int i=0;i<=n;i++)
    {for(int j=0;j<=m;j++){if(i==0||j==0){dp[i][j]=0;continue;}}}

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++){
            if(s[i-1]==t[j-1])dp[i][j] = 1+dp[i-1][j-1];
            else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
    }
    
    string ans ="";

    while(n>0&&m>0){
        if(s[n-1]==t[m-1]){ans.push_back(s[n-1]);n--;m--;}
        else{
            if(dp[n][m-1]>dp[n-1][m])m--;
            else n--;
        }
    }

    for(int i=ans.length()-1;i>=0;i--){cout<<ans[i];}
    br;
}

int main(){
	#ifdef home
        assert(freopen(TASK".in","r",stdin));
        assert(freopen(TASK".out","w",stdout));
    #endif

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // int t;
    // cin>>t;
    // while(t-->0)
    solve();

    #ifdef home
        eprintf("Time: %d ms\n", (int)(clock() * 1000. / CLOCKS_PER_SEC));
    #endif

    return 0;
}

Measured memory_bytes: 38832
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;

int main(void)
{
    string T;
    cin >> T;

    for (int i = 0; i < (int)T.size(); i++)
        if (T[i] == '?')
            T[i] = 'D';

    cout << T << endl;

    return 0;
}


Measured memory_bytes: 3716
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template <class T = int>T in(){
    T x;
    cin >> x;
    return (x);
}

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

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    ll N = in<ll>(),K = in<ll>();
    N %= K;
    cout << min(N,K - N) << "\n";
}

Measured memory_bytes: 256
// Math = ♥
// Sometimes it is people that no one imagines anything of who do things that no one can imagine
// After all this time? Always

#include <bits/stdc++.h>                        // uncomment before submission
//#include <ext/pb_ds/assoc_container.hpp>		// uncomment before submission
//#include <ext/pb_ds/tree_policy.hpp>			// uncomment before submission
//using namespace __gnu_pbds;					// uncomment before submission
using namespace std;
//<---------------------------------------------------Template----------------------------------------------------------->
#define int long long
#define ll long long
#define ld long double
const int INF = 1e15 + 7;
const int MAX = 1e5 + 7;
const int MOD = 1e9 + 7;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;                  // Vector of long long
typedef vector<vi> vvi;                 // Vector of vi
typedef vector<ii> vii;                 // Vector of pairs
typedef vector<vii> vvii;               // Vector of Vector of pairs
typedef vector<bool> vb;                // Vector of bool
#define pq priority_queue               // Max heap (To convert to min heap, use negative sign before every value)
#define ff first                        // For pairs
#define ss second                       // For pairs
#define pb push_back                    // Pushback to vector
#define mp make_pair                    // Makes pairs to be stored as pair
#define all(c) (c).begin(), (c).end()   // Mainly used by me in sorting
// ordered_set adds two new functions to set - (set).find_by_order([kth element based on zero indexing]) and order_of_key()
// order_of_key returns number of elements less that parameter. If element exists, that order is its index
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
//<----------------------------------------------------------------------------------------------------------------------->

int f[MAX][3] = {0};
int a[MAX][3] = {0};

int solve(int i, int j)
{
    if (i < 0)
        return 0;
    if (f[i][j] != 0)
        return f[i][j];

    int x = (j + 1) % 3, y = (j + 2) % 3;
    return f[i][j] = max(solve(i - 1, x) + a[i][j], solve(i - 1, y) + a[i][j]);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i][0] >> a[i][1] >> a[i][2];

    f[n - 1][0] = solve(n - 1, 0);
    f[n - 1][1] = solve(n - 1, 1);
    f[n - 1][2] = solve(n - 1, 2);

    cout << *max_element(f[n - 1], f[n - 1] + 3) << endl;
    return 0;
}


Measured memory_bytes: 9600
def f(x):
    if x == -1:
        return '-'
    else:
        return '+'
a, b, c, d = [int(i) for i in list(input())]
list = [-1, 1]
ans = []
for i in list:
    for j in list:
        for k in list:
                if a + i*b + j*c + k*d == 7:
                    print('{}{}{}{}{}{}{}=7'.format(a, f(i), b, f(j), c, f(k), d))
                    exit()


Measured memory_bytes: 3060