akhauriyash/Code-Regression huggingface dataset:
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;

#define ll long long
//typedef pair<int,int> Pint;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define revrep(i, n) for(ll i = n-1; i >= 0; i--)
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll Mypow(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}


ll INFL = 1LL << 60;//10^18 = 2^60
int INF = 1 << 30;//10^9
ll MOD  = 1000000007;
//vector<int> dy = {0,0,1,-1};
//vector<int> dx = {1,-1,0,0};



int main(){
  string S; cin >> S;
  int cnt = 0;
  rep(i, S.size()-1){
    if(S[i] != S[i+1]) cnt++;
  }
  cout << cnt << endl;
}


Measured memory_bytes: 512
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#define rep(i,x,y) for(int i=x; i<=y; ++i)

using namespace std;
char s[200005];
int n,nw;
long long ans;

bool check(int A,int B)
{
	rep(i,A+1,B-1) if(s[i]=='#' && s[i+1]=='#') return 0;
	return 1;
}

int main()
{
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=n; i>0; )
	{
		if(s[i]=='C' && s[i-1]=='B') ++nw,i-=2;
		else if(s[i]=='A') ans+=nw,--i;
		else nw=0,--i;
	}
	printf("%lld\n",ans);
	return 0;	
}		

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

    char X, Y;
    cin >> X >> Y;

    if( X > Y){
        cout << ">" << endl;
    }else if(X < Y){
        cout << "<" << endl;
    }else{
        cout << "=" << endl;
    }


    return 0;
}

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

int main() {
    cout << fixed << setprecision(10);
    
    string S, T; cin >> S >> T;
    rep(i, S.size()) {
        if (S[i] != T[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;

const int mod = 1000000007;
int add(int a, int b) { return (a += b) < mod? a : a - mod; }
int sub(int a, int b) { return (a -= b) >=  0? a : a + mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
void adds(int& a, int b) { a = add(a, b); }
void subs(int& a, int b) { a = sub(a, b); }
void muls(int& a, int b) { a = mul(a, b); }
void maxs(int& a, int b) { a = max(a, b); }
void mins(int& a, int b) { a = min(a, b); }
int pwr(int a, ll p) {
    if (p == 0) return 1;
    if (p & 1) return mul(a, pwr(a, p - 1));
    return pwr(mul(a, a), p / 2);
}
int inv(int a) { return pwr(a, mod - 2); }

const int maxn = 1000000;
int f[maxn + 1], fi[maxn + 1];
int ncr(int n, int r)
{
    if (r > n) return 0;
    return mul(f[n], mul(fi[r], fi[n - r]));
}

void precompute()
{
    f[0] = 1;
    for (int i = 1; i <= maxn; ++i)
        f[i] = mul(f[i - 1], i);

    fi[maxn] = inv(f[maxn]);
    for (int i = maxn - 1; i >= 0; --i)
        fi[i] = mul(fi[i + 1], i + 1);
}

int n, k;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    precompute();
    for (int i = 1; i <= k; ++i)
        cout << mul(ncr(n - k + 1, i), ncr(k - 1, i - 1)) << '\n';
}


Measured memory_bytes: 8064
#include <cstdio>
#include <cstring>
int disable[10];
bool check(int num) {
	char s[10];
	sprintf(s,"%d",num);
	int len=strlen(s);
	for(int i=0;i<len;++i) {
		if(disable[s[i]-'0']) return false;
	}
	return true;
}
int main() {
	int n,k,in;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;++i) {
		scanf("%d",&in);
		disable[in]=true;
	}
	while(1) {
		if(check(n)) {
			printf("%d\n",n);
			break;
		}
		++n;
	}
	return 0;
}

Measured memory_bytes: 128
#include <cmath>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <iostream>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdint>
#include <climits>
#include <unordered_set>
#include <sstream>
#include <stack>

using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> t3;

using namespace std;

int main(){
    string a, b;
    cin >> a >> b;
    vector<int> qa(a.length()+1);
    vector<int> qb(b.length()+1);
    qa[0] = qb[0] = 0;
    for (int i=0;i < a.length();i++) qa[i+1]=qa[i]+a[i]-'A'+1;
    for (int i=0;i < b.length();i++) qb[i+1]=qb[i]+b[i]-'A'+1;
    int n;
    cin >> n;
    while(n--)
    {
        int x,y,X,Y;
        cin >> x >> y >> X >> Y;
        if((qa[y]-qa[x-1])%3==(qb[Y]-qb[X-1])%3)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
}

Measured memory_bytes: 1664
while gets
  a, b = $_.split.map(&:to_i)
  break if a == 0 && b == 0
  puts if $<.lineno > 1

  n = a % 4 == 0 ? a : a + (4 - a % 4)
  leap = (n..b).step(4).select{|i| i if i % 100 > 0 || i % 400 == 0}
  puts (leap.empty? ? "NA" : leap)
end

Measured memory_bytes: 6124
import java.io.*;
public class Main {
        static NODE node;
        static NODE root;
        public static void main(String[] args) throws IOException{
                BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); 
                int n=Integer.parseInt(br.readLine());
                
                for(int i=0;i<n;i++){
                        String[] str=br.readLine().split(" ");
                
                        if("print".equals(str[0])) {
                                inorder(root);
                                System.out.println(""); 
                                preorder(root);
                                System.out.println(""); 
                        }
                        else if("insert".equals(str[0])){
                                int key=Integer.parseInt(str[1]);
                                NODE newnode=new NODE();
                                newnode.key=key;
                                insert(newnode);
                        }

                }
        }

        static void inorder(NODE node){
                if(node==null) return;
                inorder(node.left);
                System.out.print(" " + node.key);
                inorder(node.right);
        }
        
        static void preorder(NODE node){                
                if(node==null) return;
                System.out.print(" " + node.key);
                preorder(node.left);
                preorder(node.right);   
        }
        
        static void insert(NODE node){
        if(root==null){
            root = node;
            return;
        }
        NODE tnode = root;
        NODE parent = null;
        while(tnode != null) {
            parent = tnode;
            if(tnode.key > node.key)
                tnode = tnode.left;
            else
                tnode = tnode.right;
        }
        if(parent.key > node.key)
            parent.left = node;
        else
            parent.right = node;
                
        }
}

class NODE{
        int key;
        NODE left;
        NODE right;;
        NODE(){
                key=-1;
                left=null;
                right=null;
        }
}

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

int main(){
	int N, i, h_sum = 0;
	scanf("%d", &N);
	vector<int> h(N, 0), d(N, 0);
	for(i = 0; i < N; i++){
		string sub;
		cin >> sub;
		for(int j = 0; j < sub.size(); j++){
			if(sub[j] == '('){
				h[i]++;
			}
			else{
				h[i]--;
			}
			d[i] = max(d[i], -h[i]);
		}
		h_sum += h[i];
	}
	if(h_sum != 0){
		printf("No\n");
		return 0;
	}
	vector<pair<int, int>> dh_plus(0), dh_minus(0);
	for(i = 0; i < N; i++){
		if(h[i] >= 0){
			dh_plus.push_back(make_pair(d[i], h[i]));
		}
		else{
			dh_minus.push_back(make_pair(d[i] + h[i], -h[i]));
		}
	}
	sort(dh_plus.begin(), dh_plus.end());
	sort(dh_minus.begin(), dh_minus.end());
	int H = 0;
	for(i = 0; i < dh_plus.size(); i++){
		if(dh_plus[i].first > H){
			printf("No\n");
			return 0;
		}
		H += dh_plus[i].second;
	}
	H = 0;
	for(i = 0; i < dh_minus.size(); i++){
		if(dh_minus[i].first > H){
			printf("No\n");
			return 0;
		}
		H += dh_minus[i].second;
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 19124
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		scan.close();
		char[] n=s.toCharArray();
		int i=0;
		int check=1;
		while(i<=s.length()/2) {
			if(Character.getNumericValue(n[i])!=Character.getNumericValue(n[s.length()-1-i])) {
				check=0;
				break;
			}
			i++;
		}
		if(check==1)System.out.println("Yes");
		else System.out.println("No");
	}
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1000000000 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

const int MAX_N = 200020;
map<ll, ll> zip;
ll unzip[MAX_N];

struct BIT{
    int bit[MAX_N + 1];
    int n;

    BIT(const int n): n(n){
        for (int i=0;i<MAX_N;i++) bit[i] = 0;
    }

    int sum(int i){
        int S = 0;
        while(i > 0){
            S += bit[i];
            i -= i & -i;
        }
        return S;
    }

    void add(int i, int x){
        while(i <= n){
            bit[i] += x;
            i += i & -i;
        }
    }

};

ll compress(vector<ll> &x){
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    REP(i, x.size()){
        zip[x[i]] = i;
        unzip[i] = x[i];
    }
    return x.size();
}

int main(){
    ll N, K;
    cin >> N >> K;
    vector<ll> a(N);
    REP(i, N){
        cin >> a[i];
        a[i] -= K;
    }

    vector<ll> b(N+1);
    vector<ll> c(N+1);
    b[0] = 0;
    c[0] = 0;
    REP(i, N){
        b[i+1] = b[i] + a[i];
        c[i+1] = b[i+1];
    }

    BIT bit(MAX_N);
    ll zip_size = compress(b);
    ll res = 0;
    for(int i=N;i>=0;i--){
        res += (bit.sum(N+2) - bit.sum(zip[c[i]]));
        bit.add(zip[c[i]]+1, 1);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 19840
#include<bits/stdc++.h>
#define LL long long int
using namespace std;
int main(void)
{
	int i,j,k,sum,cnt;
	string s;
	cin>>s;
	for(i=0;i<s.size();i++) if((i+1)%2!=0) cout<<s[i];
	cout<<endl;
}

Measured memory_bytes: 512
#include<cstdio>

int main(){
	int n;
	int count = 0;
	scanf("%d",&n);
	int num = n;
	while(n>0){
		int a = n%10;
		n = n/10;
		count += a;
	}

	if(num%count == 0){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
}


Measured memory_bytes: 128
x = int(input())
if x%2 == 0 and x != 2:
    x += 1
if x == 2:
    print(x)
def judge(x):
    for i in range(3,int(x**(1/2))+1,2):
        if x%i == 0:
            return False
    return True

if x >= 3:
    while True:
        if judge(x):
            print(x)
            break
        else:
            x += 2


Measured memory_bytes: 38528
#include<stdio.h>
#include<string.h>

int main()
{
  int K;
  int i,n;
  char S[100];
  scanf("%d",&K);
  scanf("%s",S);
  n=strlen(S);
  if(n>K){
    for(i=0;i<K;i++){
      printf("%c",S[i]);
    }
    printf("...\n");
  }else{
    printf("%s\n",S);
  }
  return 0;
}


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

int a[1000001];

int main(){
	int s,i=1;
	cin >> s;
	a[0]=s;
	while(1){
		if(a[i-1]==4 || a[i-1]==2 || a[i-1]==1){
			cout << i+3 << endl;
			return 0;
		}
		if(a[i-1]%2==0){
			a[i]=a[i-1]/2;
		}else{
			a[i]=(a[i-1]*3)+1;
		}
		i++;
	}
}

Measured memory_bytes: 256
import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("src/aoj0026/input.txt"));
			System.setOut(new PrintStream(new FileOutputStream("src/xxxyyyy/result.txt")));
		} catch (FileNotFoundException e) {
		}
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		

		int [][] table = new int[10][10];
		while(sc.hasNext()) {
			String []ss = sc.next().split(",");
			int col = Integer.parseInt(ss[0]);
			int row = Integer.parseInt(ss[1]);
			int z = Integer.parseInt(ss[2]);
			
			for(int dr = -2; dr <= 2; dr++) 
				for(int dc = -2; dc <= 2; dc++) {
					int nr = row + dr;
					int nc = col + dc;
					if( valid(nr, nc)) {
						if (z == 1) {
							if (abs(dr) + abs(dc) <= 1)
								table[nr][nc]++;
						}
						if (z == 2) {
							if (max(abs(dr), abs(dc)) <= 1)
								table[nr][nc]++;
						}
						if (z == 3) {
							if (abs(dr) + abs(dc) <= 2)
								table[nr][nc]++;
						}
					}
				}
			
		}
		int white = 0;
		int max = 0;
		for(int i = 0; i < 10; i++)
			for(int j = 0; j < 10; j++) {
				max = max(max, table[i][j]);
				if( table[i][j] == 0 ) white++;
			}
		System.out.println(white);
		System.out.println(max);
	}
	
	boolean valid(int r, int c) {
		return 0 <= r && r < 10 && 0 <= c && c < 10;
	}
	
	void debug(Object... os) {
		System.err.println(deepToString(os));
	}
}

Measured memory_bytes: 12000
n=gets.to_i
city_x=[]
city_y=[]

n.times.each do |i|
    city_x[i],city_y[i]=gets.split.map(&:to_i)
end

all_number=[*1..n]
all_pattern=all_number.permutation.to_a
#p city_x
#p city_y

result=[]

for i in 0..all_pattern.length-1
    v=0
    i=all_pattern[i]
    for j in 0..n-2
        x=(city_x[i[j]-1]-city_x[i[j+1]-1])**2
        y=(city_y[i[j]-1]-city_y[i[j+1]-1])**2
        #p x
        #p y
        v+=(x+y)**(0.5)
        #p v
    end
    
    result<<v
end
#p result
p result.inject(:+) / result.length


Measured memory_bytes: 22416
n = int(input())
A = [int(i) for i in ('0 ' + input() + ' 0').split()]
amt = 0

for i in range(n + 1):
    amt += abs(A[i] - A[i + 1])
    
for i in range(1, n + 1):
    ans = amt - (abs(A[i - 1] - A[i]) + abs(A[i] - A[i + 1])) + abs(A[i - 1] - A[i + 1])
    print(ans)

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

using namespace std;

using Value = int32_t;
using C = int32_t;
using D = int32_t;

constexpr Value maxN = 100000;

Value calc(Value const n, C const c, const std::vector<std::vector<D>>& ds,
           const std::vector<std::vector<C>> cs) {
  std::vector<C> css[3];
  for (int i = 0; i < 3; ++i) {
    css[i].reserve((n * n + 2) / 3);
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      css[(i + j) % 3].push_back(cs[i][j] - 1);
    }
  }
  Value ret = INT32_MAX;
  for (int t0 = 0; t0 < c; ++t0) {
    D d0 = 0;
    for (auto csss : css[0]) {
      d0 += ds[csss][t0];
    }
    if (d0 >= ret) {
      continue;
    }
    for (int t1 = 0; t1 < c; ++t1) {
      if (t1 == t0) {
        continue;
      }
      D d1 = d0;
      for (auto csss : css[1]) {
        d1 += ds[csss][t1];
      }
      if (d1 >= ret) {
        continue;
      }
      for (int t2 = 0; t2 < c; ++t2) {
        if (t2 == t0 || t2 == t1) {
          continue;
        }
        D d2 = d1;
        for (auto csss : css[2]) {
          d2 += ds[csss][t2];
        }
        ret = std::min(d2, ret);
      }
    }
  }
  return ret;
}

int main() {
  Value n;
  C c;
  std::cin >> n >> c;
  std::vector<std::vector<D>> ds(c, std::vector<D>(c, 0));
  std::vector<std::vector<C>> cs(n, std::vector<C>(n, 0));
  ;
  for (int i = 0; i < c; ++i) {
    for (int j = 0; j < c; ++j) {
      std::cin >> ds[i][j];
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      std::cin >> cs[i][j];
    }
  }
  auto ret = calc(n, c, ds, cs);
  std::cout << ret << std::endl;
  return 0;
}


Measured memory_bytes: 3200
object Main extends App {
  case class Problem(n: Int, ratio: Long, bonus: Long) {
    val completeScore = n * ratio + bonus
  }
  case class Result(score: Long, count: Int)

  val in = new java.util.Scanner(System.in)
  val D = in.nextInt
  val G = in.nextLong / 100

  val Ps = Array.tabulate(D){i => Problem(in.nextInt, i + 1, in.nextLong / 100)}

  def getAll(halfway: Int): Seq[Int] = {
    val comps: Seq[Result] = (0 until (1 << D)).flatMap {mask =>
      if (((1 << halfway) & mask) != 0) None
      else {
        Some((0 to D).foldLeft(Result(0L, 0)){case (r, i) =>
          if (((1 << i) & mask) == 0) r
          else Result(r.score + Ps(i).completeScore, r.count + Ps(i).n)
        })
      }
    }

    val p = Ps(halfway)
    val halfways: Seq[Result] = (0 to p.n).map {n =>
      if (n == p.n) Result(p.completeScore, n)
      else Result(n * p.ratio, n)
    }

    for {
      c <- comps
      h <- halfways
      if (c.score + h.score >= G)
    } yield c.count + h.count
  }

  println((0 until D).flatMap(getAll).min)
}

Measured memory_bytes: 50680
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;

// Find for every number next smaller number
vector<int> calcNext(const vector<int>& p) {
	int n = p.size();
	vector<int> res(n), sta;
	for (int i = n-1; i >= 0; --i) {
		while(! sta.empty() && p[i] < p[sta.back()]) sta.pop_back();
		if (sta.empty()) res[i] = n;
		else res[i] = sta.back();
		sta.push_back(i);
	}
	return res;
}
// Find for every number previous larger number
vector<int> calcPre(const vector<int>& p) {
	int n = p.size();
	vector<int> res(n), sta;
	for (int i = 0; i < n; ++i) {
		while(! sta.empty() && p[i] > p[sta.back()]) sta.pop_back();
		if (sta.empty()) res[i] = -1;
		else res[i] = sta.back();
		sta.push_back(i);
	}
	return res;
}

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

	int n, k;
	cin >> n >> k;

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

	vector<int> nxt = calcNext(p);
	vector<int> pre = calcPre(p);
	vector<vector<int>> rev_nxt(n);
	for (int i = 0; i < n; ++i) {
		if (nxt[i] != n) rev_nxt[nxt[i]].push_back(i);
	}

	vector<pair<int, int>> offs;
	priority_queue<int> as; // First j in [i, i+k) s.t. nxt[j] is in [i, i+k)
	priority_queue<pair<int, int>> bs; // Last j in [i, i+k) s.t. pre[j] is in [i, i+k)
	for (int i = 0; i < n; ++i) {
		bs.push({i, pre[i]});
		for (int j : rev_nxt[i]) {
			as.push(-j);
		}
		while(! as.empty() && -as.top() <= i-k) as.pop();
		while(! bs.empty() && bs.top().second <= i-k) bs.pop();

		if (i-k+1 >= 0) {
			int a = (as.empty() ? -1 : -as.top());
			int b = (bs.empty() ? -1 : bs.top().first);
			offs.push_back({a, b});
		}
	}
	sort(offs.begin(), offs.end());
	offs.erase(unique(offs.begin(), offs.end()), offs.end());
	cout << offs.size() << '\n';
}




















Measured memory_bytes: 14196
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;

ll mod_pow(ll a, ll n) {
	if (n == 0) return 1;
	if (n % 2 == 0) {
		ll tmp = mod_pow(a, n / 2);
		return (tmp * tmp) % MOD;
	}
	return (a * mod_pow(a, n - 1)) % MOD;
}

vector<ll> fact;
vector<ll> inv_fact;

void comb_init(int n) {
	fact.resize(n + 1);
	inv_fact.resize(n + 1);
	fact[0] = inv_fact[0] = 1;
	for (int i = 1; i <= n; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
		inv_fact[i] = (inv_fact[i - 1] * mod_pow(i, MOD - 2)) % MOD;
	}
}

ll comb(int n, int k) {
	if (n < k) return 0;
	ll ret = fact[n];
	(ret *= inv_fact[k]) %= MOD;
	(ret *= inv_fact[n - k]) %= MOD;
	return ret;
}

int main() {
	int n, k;
	cin >> n >> k;
	ll ans = 0;
	comb_init(k);
	for (int i = 0; i <= k; i++) {
		ll x = mod_pow(k - i, n);
		(x *= comb(k, i));
		if (i % 2 == 0) (ans += x) %= MOD;
		else (ans += MOD - x) %= MOD;
	}
	cout << ans << endl;
 }


Measured memory_bytes: 3108
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define rep(i, a, b) for (register ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (register ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (int i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter cout << endl
#define siz(x) ((int)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <int, int> pii ;
typedef vector <int> vi ;
typedef vector <pii> vii ;
typedef queue <int> qi ;
typedef queue <pii> qii ;
typedef set <int> si ;
typedef map <int, int> mii ;
typedef map <string, int> msi ;
const int maxn = 2e6 + 10 ;
const int inf = 0x3f3f3f3f ;
const int iinf = 1 << 30 ;
const ll linf = 2e18 ;
const ll mod = 1e9 + 7 ;
const double eps = 1e-7 ;
template <class T> void read(T &a)
{
	int f = 1 ; a = 0;
	char ch = getchar() ;
	while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
	while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
	a *= f;
}

ll n;

ll a, b, c;

ll ans;

ll power(ll a, ll b)
{
	ll ret = 1;
	for(; b; b >>= 1, (a *= a) %= mod) if(b & 1) (ret *= a) %= mod;
	return ret;
}

ll fac[maxn], fa[maxn], fb[maxn], inv[maxn], invc, invab[maxn];

void init()
{
	ll N = 2000000;
	fac[0] = fa[0] = fb[0] = invab[0] = 1;
	invab[1] = power(a + b, mod - 2);
	rep(i, 2, N) invab[i] = invab[i - 1] * invab[1] % mod;
	rep(i, 1, N) fac[i] = fac[i - 1] * i % mod, fa[i] = fa[i - 1] * a % mod, fb[i] = fb[i - 1] * b % mod;
	inv[N] = power(fac[N], mod - 2);
	per(i, N, 1) inv[i - 1] = inv[i] * i % mod;
	invc = power(100 - c, mod - 2);
	return ;
}

signed main()
{
	scanf("%lld", &n);
	scanf("%lld %lld %lld", &a, &b, &c);
	init();
	rep(m, n, 2 * n - 1) (ans += fac[m - 1] * inv[n - 1] % mod * inv[m - n] % mod * (fa[n] * fb[m - n] % mod + fa[m - n] * fb[n] % mod) % mod * m % mod * invc % mod * 100 % mod * invab[m] % mod) %= mod;
	printf("%lld\n", ans);
	return 0;
}

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

#define pb            push_back
#define mp            make_pair
#define ins           insert
#define endl          '\n'
#define all(x)        x.begin(),x.end()
#define debug(X)      { cerr<<endl<<(#X)<<" = "<<(X)<<endl; }
//#define cerr if(0)cerr

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;


int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,i,P,Q;
    vi p,q,r;

    cin>>n;
    for (i=0; i<n; ++i) {
        cin>>P;
        p.pb(P);
    }
    
    for (i=0; i<n; ++i) {
        cin>>Q;
        q.pb(Q);
    }

    r=p;
    sort(all(r));
    
    int a=1,b=1;
    i=1;
    do {
        if (p==r)
            a=i;
        if (q==r)
            b=i;
        ++i;
    } while (next_permutation(all(r)));
    cout<<abs(a-b)<<endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import *
from itertools import permutations

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
c = 0

for t in permutations(range(1, N+1)):
    if list(t)==P:
        a = c
    
    if list(t)==Q:
        b = c
    
    c += 1

print(abs(a-b))

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

int main() {
  int N, K;
  cin >> N >> K;
  int x;
  int dist = 0;
  for (int i=0; i<N; i++){
    cin >> x;
    if (x > K - x ){
      dist += K - x;
    }else{
      dist += x;
    }
  }
  dist *= 2;
  cout << dist << endl;
}


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

int main(){
	string S;cin >> S;
	S[3] = '8';
	cout << S << endl;
}


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

#define PI 3.14159265358979323846264338327950288419

using namespace std;

int n, l[100005], r[100005];
bool visited[100005];
int pos;
long long ans;

pair<int, int> left_pts[100005];
pair<int, int> right_pts[100005];
int left_ptr, right_ptr;

void go_left(int &pos, long long &cans){
	while(true){
		pair<int, int> cur = right_pts[right_ptr];
		if(visited[cur.second]){
			right_ptr++;
		}else{
			if(pos > cur.first){
				cans += pos - cur.first;
				pos = cur.first;
			}
			visited[cur.second] = true;
			return;
		}
	}
}

void go_right(int &pos, long long &cans){
	while(true){
		pair<int, int> cur = left_pts[left_ptr];
		if(visited[cur.second]){
			left_ptr--;
		}else{
			if(pos < cur.first){
				cans += cur.first - pos;
				pos = cur.first;
			}
			visited[cur.second] = true;
			return;
		}
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d %d", &l[i], &r[i]);
		left_pts[i] = {l[i], i};
		right_pts[i] = {r[i], i};
	}
	sort(left_pts + 1, left_pts + n + 1);
	sort(right_pts + 1, right_pts + n + 1);
	
	// LRLR...
	long long ans1 = 0;
	memset(visited, false, sizeof(visited));
	pos = 0;
	left_ptr = n;
	right_ptr = 1;
	for(int i = 1; i <= n; i++){
		if(i & 1){
			go_left(pos, ans1);
		}else{
			go_right(pos, ans1);
		}
	}
	ans = ans1 + abs(pos);
	
	// RLRL...
	
	long long ans2 = 0;
	memset(visited, false, sizeof(visited));
	pos = 0;
	left_ptr = n;
	right_ptr = 1;
	for(int i = 1; i <= n; i++){
		if(i & 1){
			go_right(pos, ans2);
		}else{
			go_left(pos, ans2);
		}
	}
	ans = max(ans, ans2 + abs(pos));
	
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 2688
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
S = LS2()

from collections import defaultdict

d_left = defaultdict(int)
d_right = defaultdict(int)

for i in range(2**N):
    left_red = ''
    left_blue = ''
    right_red = ''
    right_blue = ''
    for j in range(N):
        if (i >> j) & 1:
            left_red += S[j]
        else:
            left_blue += S[j]
    for j in range(2*N-1,N-1,-1):
        if (i >> (j-N)) & 1:
            right_red += S[j]
        else:
            right_blue += S[j]
    d_left[(left_red,left_blue)] += 1
    d_right[(right_red,right_blue)] += 1

ans = 0
for key in d_left.keys():
    ans += d_left[key]*d_right[key]

print(ans)


Measured memory_bytes: 281020
import numpy as np
N, M = map(int, input().split())
shop = []
for _ in range(N):
    shop.append(list(map(int, input().split())))
i = 0
num = 0
ans = 0
shop = sorted(shop)
while num < M:
    ans += shop[i][0] * shop[i][1]
    num += shop[i][1]
    i += 1
ans -= (num - M) * shop[i -1][0]
print(ans)

Measured memory_bytes: 37700
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
typedef long long ll;
using namespace std;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)
int main()
{
    ll n;
    cin >> n;
    int ans = max((int)to_string(n).size(),1);
    for (ll i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ans = min(ans, max((int)to_string(n / i).size(), (int)to_string(i).size()));
        }
    }
    cout << ans << endl;
    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

vector<int> v[200005];
bool used[200005];
string s;

bool solve(int p, int z) {
  if(used[p]) return true;
  used[p] = true;
  bool ok = false;
  rep(i, 0, v[p].size()) {
    if(v[p][i] == z) continue;
    if(v[v[p][i]].size()) {
      if(solve(v[p][i], p)) ok = true;
    }
  }
  return ok;
}

void korosu(int p) {
  bool a = false, b = false;
  rep(j, 0, v[p].size()) {
    if(!v[v[p][j]].size()) continue;
    if(s[v[p][j]] == 'A') a = true;
    else b = true;
  }
  vector<int> vv;
  if(a && b) return;
  else vv = v[p], v[p] = {};
  rep(i, 0, vv.size()) {
    if(v[vv[i]].size()) korosu(vv[i]);
  }
}

signed main() {
  int n, m;
  cin >> n >> m >> s;

  rep(i, 0, m) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    v[a].pb(b);
    v[b].pb(a);
  }
  rep(i, 0, n) {
    bool a = false, b = false;
    rep(j, 0, v[i].size()) {
      if(!v[v[i][j]].size()) {
        continue;
      }
      if(s[v[i][j]] == 'A') a = true;
      else b = true;
    }
    if(a && b) continue;
    korosu(i);
  }
  
  rep(i, 0, n) {
    if(used[i]) continue;
    if(solve(i, 200004)) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}


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

int main()
{
    long long n, a[5], res=4, mn=1e17;
    cin>>n;
    for(int i=0; i<5; i++) cin>>a[i];
    for(int i=0; i<5; i++)
        mn=min(mn, a[i]);

    res+=((n%mn)?((n/mn)+1):(n/mn));

    cout<<res<<endl;

    return 0;
}


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

//type
#define ll long long
typedef pair<int, int> P;
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007    //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first      //pairの一つ目の要素
#define S second     //pairの二つ目の要素
#define Z class
// OTHER
// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) { return x * x; }
#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))
// loop
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= ll(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= ll(b); i--)
#define FORA(i, I) for (const auto &i : I)

// vector
#define ALL(x) x.begin(), x.end()

// output
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n", (x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define ln cout << '\n'
template <Z A>
void pr(A a)
{
  cout << a;
  ln;
}
template <Z A, Z B>
void pr(A a, B b)
{
  cout << a << ' ';
}

int ans = 0;
bool check = 0;
string s;
int N = 0;
vector<int> v(N);
int a, b;
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

int main()
{
  int x;
  cin >> a >> b >> x;
  if (a <= x && (a + b) > x)
    YES();
  else
    NO();

  return 0;
}

Measured memory_bytes: 3636
#include <stdio.h>
#include <vector>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

vector<int> dat[4];
const char names[4][8] = { "meiji", "taisho", "showa", "heisei" };

int main() {
    dat[0].push_back(1868); dat[0].push_back(9); dat[0].push_back(8);
    dat[1].push_back(1912); dat[1].push_back(7); dat[1].push_back(30);
    dat[2].push_back(1926); dat[2].push_back(12); dat[2].push_back(25);
    dat[3].push_back(1989); dat[3].push_back(1); dat[3].push_back(8);
    int y, m, d;
    while (scanf("%d%d%d", &y, &m, &d) != EOF) {
        vector<int> v;
        v.push_back(y); v.push_back(m); v.push_back(d);
        if (v < dat[0]) puts("pre-meiji");
        else {
            int cur = 0;
            while (cur < 3 && v >= dat[cur+1]) cur++;
            printf("%s %d %d %d\n", names[cur], y-dat[cur][0]+1, m, d);
        }
    }
    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
#define e_b emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  ll N,D;
  cin >> N >> D;
  int ans=0;
  for(int i=0;i<N;i++){
    ll x,y;
    cin >> x >> y;
    ll tmp=x*x + y*y;
    if(tmp<=D*D)  ans++;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long N,A,B; 
  cin>>N>>A>>B;
  long long kotae=N/(A+B)*A;
  long long amari=N%(A+B);
  if(A==0){
    cout<<0<<endl;
    return 0;
  }
  if(amari==0){
    cout<<kotae<<endl;
  }else {
    if(amari<=A){
      cout<<kotae+amari<<endl;
    }else{
      cout<<kotae+A<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  lint k, n; cin >> k >> n;
  vector<lint> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  vector<lint> v;
  for (int i = 1; i < n; i++) {
    v.push_back(a[i] - a[i - 1]);
  }
  v.push_back(k - a[n - 1] + a[0]);
  sort(RALL(v));
  cout << k - v[0] << endl;
  return 0;
}


Measured memory_bytes: 4980
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string>
#include<vector>
#include<cstdint>

// ==========================

using namespace std;

// ==========================
//ライブラリ

//aからbまでの合計
int total(int a,int b) {
	int ans = 0;
	for (int i = a; i <= b; i++) {
		ans += i;
	}
	return ans;
}

// ==========================
//マクロ
#define rep(i,n) for(int i=0;i<n;i++)

// ==========================
//本文
int main() {
	string s;
	cin >> s;
	string ans = s;
	reverse(s.begin(), s.end());
	if (s.at(0) == 's')ans += "es";
	else ans += "s";
	cout << ans << endl;
	return 0;
}

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

#define vec              vector<int>
#define vecll            vector<ll>
#define vecd             vector<double>
#define vecst            vector<string>
#define vecb             vector<bool>
#define v2(v,n,m,init)   vector<vector<int>>  v(n, vector<int>(m, init))
#define vb2(v,n,m,init)  vector<vector<bool>> v(n, vector<bool>(m, init))
#define vll2(v,n,m,init) vector<vector<ll>>   v(n, vector<ll>(m, init))

#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define arrst(var, n)    vecst var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define uniqueall(v)     v.erase(unique(v.begin(), v.end()), v.end());
#define pb(var)          push_back(var)
#define prt(var)         cout << (var) << "\n"
#define prtd(n, var)     cout << fixed << setprecision(n) << (var) << "\n"
#define prtfill(n, var)  cout << setw(n) << setfill('0') << (var);
#define prt2(v1, v2)     cout << (v1) << " " << (v2) << "\n"
#define prt3(v1, v2, v3) cout << (v1) << " " << (v2) << " " << (v3) << "\n"
#define prtall(v)        rep(i,v.size()){cout<<v[i]<<(i!=v.size()-1?" ":"\n");}
template <typename T>
bool chmax(T &a, const T& b){if(a<b){a=b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T& b){if(a>b){a=b; return true;} return false;}
//----------------------------------------------------------------

int main(void) {
  int n, a;
  cin >> n >> a;
  prt(n*n-a);

}


Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int mod = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);


ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


ll GCD(ll a,ll b){
  ll r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return b;
}


ll LCM(ll a,ll b){
  ll c=a,d=b,r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return c/b*d;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

vector<pair<char,ll>> runlength(string s,vector<pair<char,ll>> p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
    return p;
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
  return p;
}



/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  ll n,k;
  cin>>n>>k;
  string s,t;
  rep(i,k){
    cin>>t;
    s+=t;
  }
  while(string::npos!=to_string(n).find_last_of(s)) n++;
  cout<<n<<endl;
}

Measured memory_bytes: 256
/*input
3 3
abc


*/
#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;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
typedef long long int ll;
#define ld long double
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define sz(_a) (ll)(_a.size())
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
const ll maxn=100005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;

ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}
int main() {
    int a;
    cin>>a;
    cout<<a*a*a;
}

Measured memory_bytes: 256
# include"stdio.h"
int main(){
    int n;
    scanf("%d",&n);
    long long int t[n],a,b,r,min,max,tmp;
    for(int i=0;i<n;i++)
        scanf("%lld",&t[i]);
    min=t[0];
    for(int i=0;i<n-1;i++){
        a=min;
        b=t[i+1];
        if(a<b){
            tmp=a;
            a=b;
            b=tmp;
        }
        r=a%b;

        while(r!=0){
            a=b;
            b=r;
            r=a%b;
        }
        max=b;
        min=min/max*t[i+1];
    }
    printf("%lld\n",min);
}


Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	if(n >= 3200){
		cout << s << endl;
	}
	else{
		cout << "red" << endl;
	}
	return 0;
 } 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long int llint;
typedef pair<ll, ll> pa;
#define MM 1000000000
#define MOD MM+7
#define MAX 101000
#define MAP 110
#define initial_value -1
#define Pair pair<int,int>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define INF (1 << 29) //536870912
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int n;
void add(int s){
}
int main(){
    cin >> n;
    vector<int> a(0),b(n);
    for(int i = 0; i < n; i++){
        cin >> b[i];
        if(b[i] > i+1){
            cout << -1 << endl;
            return 0;
        }
    }
    while(b.size()){
        bool tmp = false;
        for(int i = b.size()-1; i >= 0; i--){
            if(b[i] == i+1){
                a.push_back(i+1);
                b.erase(b.begin() + i);
                tmp = true;
                break;
            }
        }
        if(!tmp){
            cout << -1 << endl;
        }
    }
    for(int i = n-1; i >= 0; i--){
        cout << a[i] << endl;
    }
}

 


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

class practice_priority_queue
{
	int h;
	vector<int> a;

public:
	practice_priority_queue() :h(0)
	{
		int max_size = 2000000;
		a.reserve(max_size);
		for (int i = 0; i < max_size; i++) a.push_back(0);
	}

	void maxHeapify(int i)
	{
		int l = 2 * i;
		int r = 2 * i + 1;
		int largest = i;
		if (1 <= l && l <= h && a[i] < a[l]) largest = l;
		if (1 <= r && r <= h && a[largest] < a[r]) largest = r;

		if (largest != i) {
			swap(a[i], a[largest]);
			maxHeapify(largest);
		}
	}

	int extract()
	{
		if (h < 1) return INT_MIN;
		int maxv = a[1];
		a[1] = a[h--];
		maxHeapify(1);
		return maxv;
	}

	void insert(int key)
	{
		a[++h] = key;
		int i = h;
		while (1 < i && a[i / 2] < a[i]) {
			swap(a[i / 2], a[i]);
			i = i / 2;
		}
	}
};



int main()
{
	practice_priority_queue ppq;
	while (true) {
		string cmd;
		cin >> cmd;
		if (cmd == "insert") {
			int key;
			cin >> key;
			ppq.insert(key);
		}
		else {
			if (cmd == "extract") cout << ppq.extract() << endl;
			else break;
		}
	}
}


Measured memory_bytes: 10616
import java.util.*;

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

        Scanner sc = new Scanner(System.in);
        
        int a = sc.nextInt();
        int b = sc.nextInt();
        int ave = (a + b) / 2;

        if( (a + b) % 2 == 1 ) ave++;
        
        System.out.println(ave);
    }
}
 

Measured memory_bytes: 23124
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false) cin.tie(NULL) cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define f first 
#define s second
#define int long long
using namespace std;

const int nax=1e5+5;
vector<int>adj[nax];
const int mod=1e9+7;
const int inf=1e18+7;

signed main(){
	int n;
	cin>>n;
	int ans=0;
	if(n%2!=0) ans=n/2 +1 ;
	else ans=n/2;
	cout<<ans<<endl;
	return 0;
}



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

struct Edge { int to, id;};

vector<vector<Edge>> g;
vector<int> ans;

void dfs(int v, int c=-1, int p=-1) {
  int k = 1;
  for(auto i:g[v]) {
    int u = i.to, ei = i.id;
    if (u == p) continue;
    if (k == c) ++k;
    ans[ei] = k; ++k;
    dfs(u,ans[ei],v);
  }
}

int main() {
  int n;
  cin >> n;
  g.resize(n);
  ans = vector<int>(n-1);
  rep(i,n-1) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    g[a].push_back((Edge){b,i});
    g[b].push_back((Edge){a,i});
  }
  dfs(0);
  int mx = 0;
  rep(i,n) mx = max(mx, int(g[i].size()));
  cout << mx << endl;
  rep(i,n-1) {
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 8320
def main():
    from math import gcd
    from functools import reduce, lru_cache

    n, *a, = map(int, open(0).read().split())
    m = max(a)

    d = [0] * (m + 1)
    d[1] = 1
    for i in range(2, m + 1):
        for j in range(i, m + 1, i):
            if d[j] == 0:
                d[j] = i

    @lru_cache()
    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    f = 0
    g = a[0]
    for i in range(n):
        x = a[i]
        ps = primes(x)
        g = gcd(g, x)
        if b & ps:
            f = 1
            break
        b |= ps
    if f > 0 and gcd(g, reduce(gcd, a[i:])) != 1:
        f = 2

    ans = ["pairwise coprime", "setwise coprime", "not coprime"][f]
    print(ans)


if __name__ == '__main__':
    main()


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

using namespace std;

main(){
	int a,b,c,d,e,f=0;
	cin >> a >> b >> c >> d >> e;
	if (a<40){
	a=40;}
	if (b<40){
	b=40;}
	if (c<40){
	c=40;}
	if (d<40){
	d=40;}
	if (e<40){
	e=40;}
	f=(a+b+c+d+e);
	f=f/5;
	printf("%d\n",f);
}


Measured memory_bytes: 3124
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

typedef long long ll;

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

// const int C ;
// const int M = 1000000007;

int N;
int M;
int K[100010];
vector<int> L[200100];
bool visited[200100];

int main () {
  cin >> N >> M;
  for (auto i = 0; i < N; i++) {
    cin >> K[i];
    for (auto j = 0; j < K[i]; j++) {
      int l;
      cin >> l;
      L[i].push_back(l+100010);
      L[l+100010].push_back(i);
    }
  }
  fill(visited, visited+200100, false);
  stack<int> S;
  S.push(0);
  while (!S.empty()) {
    int now = S.top();
    S.pop();
    if (!visited[now]) {
      visited[now] = true;
      for (auto x : L[now]) {
        if (!visited[x]) S.push(x);
      }
    }
  }
  for (auto i = 0; i < N; i++) {
    if (!visited[i]) {
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;  
}


Measured memory_bytes: 9464