akhauriyash/Code-Regression huggingface dataset:
N = int(input())
A = list(map(int, input().split()))

die = True
for i in range(N-1):
    if A[i] < A[i+1]:
        die = False
        break
if die:
    print(1000)
    exit()

ud = [(0, A[0])]
for i in range(N-1):
    if A[i] < A[i+1]:
        ud.append((1, A[i+1]))
    elif A[i] > A[i+1]:
        ud.append((-1, A[i+1]))

hold = 0
hand = 1000
for i in range(len(ud)-1):
    if ud[i][0] == 0 and ud[i+1][0] == 1:
        buy = hand // ud[i][1]
        hold += buy
        hand -= buy * ud[i][1]
    if ud[i][0] == 0 and ud[i+1][0] == -1:
        pass
    if ud[i][0] == -1 and ud[i+1][0] == 1:
        buy = hand // ud[i][1]
        hold += buy
        hand -= buy * ud[i][1]
    if ud[i][0] == -1 and ud[i+1][0] == -1:
        pass
    if ud[i][0] == 1 and ud[i+1][0] == 1:
        pass
    if ud[i][0] == 1 and ud[i+1][0] == -1:
        hand += hold * ud[i][1]
        hold = 0

if hold:
    hand += hold * ud[-1][1]
    hold = 0

print(hand)

Measured memory_bytes: 62032
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define for1(i, m, n) for(int i = m;i < n;i++)
#define ll long long
#define endl '\n'
using namespace std;


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
    int n;
    cin >> n;
    if (n % 10 == 0) {
        cout << 10 << endl;
    } else {
        int sum = 0;
        while(n > 0) {
            sum += n % 10;
            n /= 10;
        }
        cout << sum << endl;
    }
	return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
jewels = list(map(int, input().split())) + [0]
ans = 0
for get in range(1, min(N, K)+1):
  put = min(get, K-get)
  for left in range(get+1):
    right = get - left
    values = jewels[:left] + jewels[N-right:]
    sum_v = sum(values)
    minus_values = list(filter(lambda x: x<0, values))
    minus_values.sort()
    cnt = 0
    for v in minus_values:
      if cnt < put:
        sum_v -= v
        cnt += 1
      else:
          break
    ans = max(ans, sum_v)
print(ans)


Measured memory_bytes: 3064
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main
{
    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA
    {
        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            double afterTax = (double) in.nextInt();
            double beforeTaxUp = Math.ceil(afterTax / 1.08);
            double beforeTaxDown = Math.floor(afterTax / 1.08);

            if (Math.floor(beforeTaxDown * 1.08) == afterTax)
            {
                out.print((int) beforeTaxDown);
            } else if (Math.floor(beforeTaxUp * 1.08) == afterTax)
            {
                out.print((int) beforeTaxUp);
            } else
            {
                out.print(":(");
            }
        }

    }
}



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

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

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

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

int main(){
    string s, t; cin >> s >> t;
    vector<int> alpha1(26, 0), alpha2(26, 0);
    REP(i, 0, s.size()){
        alpha1[s[i]-'a']++;
    }
    REP(i, 0, t.size()){
        alpha2[t[i]-'a']++;
    }
    string a = "";
    REP(i, 0, 26){
        REP(l, 0, alpha1[i]){
            a = a + alpha[i];
        }
    }
    string b = "";
    for(int i = 25; i >= 0; i--){
        REP(l, 0, alpha2[i]){
            b = b + alpha[i];
        }
    }
    if(a < b){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;
//const int mod = 998244353;

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

    while (1)
    {
        int n, m;
        cin >> n >> m;
        if (n == 0)
            break;
        vector<int> G[1010];
        rep(i, m)
        {
            int u, v;
            cin >> u >> v;
            u--, v--;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        vector<int> col(n, 0); //B -> 1, W -> 2, ? -> 0
        col[0] = 1;
        queue<int> que;
        que.push(0);
        bool che = true;
        while (!que.empty())
        {
            int now = que.front();
            que.pop();
            int nxt_col = 3 - col[now];
            rep(i, G[now].size())
            {
                if (col[G[now][i]] != 0)
                {
                    if (col[G[now][i]] != nxt_col)
                        che = false;
                    continue;
                }
                col[G[now][i]] = nxt_col;
                que.push(G[now][i]);
            }
        }
        if (!che)
        {
            cout << 0 << endl;
            continue;
        }
        int num_B = 0;
        rep(i, n) if (col[i] == 1) num_B++;
        int num_W = n - num_B;
        int ans = 0;
        if (num_B % 2 == 0)
            ans++;
        if (num_W % 2 == 0)
            ans++;
        if (num_B == num_W && ans != 0)
            ans--;
        cout << ans << endl;
        if (ans == 2)
            cout << min(num_B / 2, num_W / 2) << endl
                 << max(num_B / 2, num_W / 2) << endl;
        else if (ans == 1)
        {
            if (num_B % 2 == 0)
                cout << num_B / 2 << endl;
            else
                cout << num_W / 2 << endl;
        }
    }
}



Measured memory_bytes: 3164
#include<cstring>
#include<string>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<complex>
#include<sstream>
#include<climits>

#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int MAX_N = 200000;
int N;
int A[MAX_N];
int digit[MAX_N][20];

int main() {
  cin >> N;
  rep(i,N) cin >> A[i];

  for (int k = 0; k < 20; ++k) if (A[0]>>k & 1) digit[0][k] = 1;
  for (int i = 1; i < N; ++i) {
    for (int k = 0; k < 20; ++k) {
      if (A[i]>>k & 1) digit[i][k] += digit[i-1][k]+1;
      else digit[i][k] = digit[i-1][k];
    }
  }

  ll ans = 0;
  for (int l = 0; l < N; ++l) {
    ll tmp = 0;
    int lb = l, ub = N, mid;
    while (ub-lb > 1) {
      mid = (ub+lb)/2;
      bool judge = true;
      for (int k = 0; k < 20; ++k) {
        if (digit[mid][k] - (l != 0 ? digit[l-1][k] : 0) > 1) {
          judge = false;
          break;
        }
      }

      if (judge) lb = mid;
      else ub = mid;
    }
    tmp = lb - l + 1;
    ans += tmp;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 16640
import collections

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for i in range(Q)]

sum_ = sum(A)
counter = dict(collections.Counter(A))
#print(counter)

for i in range(Q):
    b, c = BC[i]
    if not b in counter:
        counter[b] = 0
    if not c in counter:
        counter[c] = 0
    cnt = counter[b]
    sum_ += (c-b)*cnt
    print(sum_)
    counter[b] -= cnt
    counter[c] += cnt

Measured memory_bytes: 40412
// In the name of GOD
 
#include <bits/stdc++.h>
#define ll long long
#define pp pair <int, int>
using namespace std;
const int N = 3e3 + 10, MOD = 1e9 + 7;
const ll INF = 1e18;

void solve() {
	string s;
	cin >> s;
	for (int i = 0; i < s.length(); ++i) {
		if (s[i] == '?')
			s[i] = 'D';
	}
	cout << s;
}

int main () {
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    int tt = 1;
    // cin >> tt;
    for (int tc = 1; tc <= tt; ++tc) {
        solve();
    }
}                                  

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

int main(){
    int a, b;
    cin >> a >> b;
    if((a % 2 == 0 && b % 2 == 1) || (a % 2 == 1 && b % 2 == 0)){
        cout << "IMPOSSIBLE" << endl;
    }else{
        cout << (a + b) / 2 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
// g++ Main.cpp -std=gnu++1y -O2 -I/opt/boost/gcc/include -o main && ./main

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vll = vector<vl>;
using vii = vector<vi>;
using pii = pair<int, int>;

#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i, a, b) for(int (i) = a; (i) < (b);(i)++)
#define MAX(a, b) ((a > b) ? a : b)
#define MIN(a, b) ((a > b) ? b : a)

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


const int MOD = 1e9 + 7;

string a = "3", b = "5", c = "7";

template<class T> bool contain(const std::string& s, const T& v) {
   return s.find(v) != std::string::npos;
}

int k_keta(int k){
  if(k <= 2) return 0;
  int threeK = 1, twoK = 1;
  for(int i = 0; i < k;i++){
    threeK *= 3;
    twoK *= 2;
  }
  return threeK - 3 * twoK + 3;
}




int main(){
  int n;
  cin >> n;
  if(n <= 2){
    cout << 0 << endl;
    return 0;
  }
  vi S(n + 1, 0);
  for(int i = 2; i <= n;i++){
    int tmp = i;
    for(int j = 2; j <= i; j++){
      while(tmp % j == 0){
        tmp /= j;
        S.at(j)++;
      }
    }
  }
  vi data(0);
  for(int i = 2; i <= n;i++){
    if(S.at(i) != 0){
      data.push_back(S.at(i));
    }
  }
  int id24 = 0, id14 = 0,id4 = 0, id2 = 0;
  while(data.at(id24) >= 24){
    id24++;
    id14++;
    id4++;
    id2++;
  }
  while(data.at(id14) >= 14){
    id14++;
    id4++;
    id2++;
  }
  while(data.at(id4) >= 4){
    id4++;
    id2++;
  }
  while(data.at(id2) >= 2){
    id2++;
  }
  int fft = (id4 * (id4 - 1) / 2) * (id2 - 2) ;
  int ftf = id14 * (id4 - 1);
  int ttf = id24 * (id2 - 1);
  if(data[0] >= 74) fft ++;
  cout << fft + ftf + ttf << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a,b,m,x[100010],y[100010],z[100010][3];

int main()
{
    cin>>a>>b>>m;
    for(int i=1;i<=a;i++) cin>>x[i];
    for(int i=1;i<=b;i++) cin>>y[i];
    for(int j=1;j<=m;j++){
        for(int i=0;i<3;i++){
    		scanf("%lld",&z[j][i]);
		}
	}
	int min=0,k=1000000;
    for(int i=1;i<=a;i++){
    	if(x[i]<k) k=x[i];
	}
	min=k;
	k=1000000;
	for(int i=1;i<=b;i++){
		if(y[i]<k) k=y[i];
	}
	min=min+k;
	for(int i=1;i<=m;i++){
		if(x[z[i][0]]+y[z[i][1]]-z[i][2]<min){
			min=x[z[i][0]]+y[z[i][1]]-z[i][2];
		}
	}
	cout<<min<<endl;
	return 0;
}

Measured memory_bytes: 4096
import java.io.*;
import java.util.StringTokenizer;

public class Main {
  private static PrintWriter out;

  public static void main(String[] args) {
    Main main = new Main();
    Runtime.getRuntime().addShutdownHook(new Thread(() -> out.close()));
    try {
      main.run(args);
    } catch (Exception e) {
      e.printStackTrace();
    }
  }

  private void run(String[] arguments) throws Exception {
    MyScanner sc = new MyScanner();
    out = new PrintWriter(new BufferedOutputStream(System.out));

    int N = sc.nextInt();
    String S = sc.next();
    char[] letters = S.toCharArray();

    int ans = 0;
    for (int i = 0; i < N-2; i++) {
      if (S.charAt(i) == 'A' && S.charAt(i+1) == 'B' && S.charAt(i+2) == 'C'){
        ans++;
        i = i + 2;
      }
    }
    out.println(ans);
    out.close();
  }

  /*          
   * Form: http://codeforces.com/blog/entry/7018
   */
  private class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    MyScanner() {
      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: 28628
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        String[] Array = line.split(" ");
        int W = Integer.parseInt(Array[0]);
        int H = Integer.parseInt(Array[1]);
        int x = Integer.parseInt(Array[2]);
        int y = Integer.parseInt(Array[3]);
        int r = Integer.parseInt(Array[4]);
        if((0<=x-r&&x+r<=W)&&(0<=y-r&&y+r<=H)){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 26184
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] x = new int[n], s = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = s[i] = in.nextInt();
        }
        Arrays.sort(s);
        int c1 = s[n/2];
        int c2 = s[n/2 - 1];
        for (int i = 0; i < n; i++) {
            System.out.println(x[i] >= c1 ? c2 : c1);
        }
    }
}


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

using namespace std;

int main()
{
	int t;
	t=1;
	while(t--)
	{
	int l,r,d,i,j;
	
	cin>>l>>r>>d;
	j=0;
	for(i=l;i<=r;i++)
	{
		if(i%d==0)
		{
			j++;
			
		}
		
	}
	
	cout<<j<<endl;
	
	}



}


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

using i64 = long long int;

i64 solve(i64 n, i64 m){
    i64 res = n / m * (3 * m);
    if(n % m == 0)return res;
    else return res + solve(m, n % m);
}

int main(){
    i64 n, x;
    cin >> n >> x;

    cout << solve(max(x, n-x), min(x, n-x)) << 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, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

int main()
{
  int N;
  cin >> N;
  cout << (1000 - N%1000)%1000 << endl;
}

Measured memory_bytes: 3604
def solve(dic, cnt, n):
  if n < 10:
    return cnt

  if n in dic:
    return -1

  dic[n] = True

  s = str(n)
  max_score = 0
  for i in range(1, len(s)):
    a, b = int(s[:i]), int(s[i:])
    max_score = max(max_score, a * b)

  return solve(dic, cnt + 1, max_score)

q = int(input())
for _ in range(q):
  dic = dict()
  print(solve(dic, 0, int(input())))


Measured memory_bytes: 5604
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} //最小公倍数


int main()
{
  int a, b ;
  cin >> a >> b ;
  cout << max(0,a-b*2) <<endl ;


  return 0 ;
}



Measured memory_bytes: 256
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#define ALL(v) begin(v),end(v)
#else
#define ALL(v) (v).begin(),(v).end()
#endif

using namespace std;


namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}
template <class T> inline T &chmin(T &x, const T &y){ return x = min(x, y); }
template <class T> inline T &chmax(T &x, const T &y){ return x = max(x, y); }
template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8

long long powmod(long long x, long long y, long long mod){
	long long a = 1;
	x %= mod;
	while(y){
		if(y & 1){
			a = a * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return a;
}

const int M = 200010;
const LL half = 500000004;
LL fact[M + 1];
LL ifact[M + 1];
LL h2[M + 1];

LL comb(int n, int k){
	return fact[n] * ifact[n - k] % MOD * ifact[k] % MOD;
}

template <class F>
void solve(int b, int w, F func){
	LL sum = 1;
	LL one = 0;
	for(int i = 0; i < b + w; ++i){
		LL res = func(sum * half + one);
		res = (res % MOD + MOD) % MOD;
		printf("%lld\n", res);

		if(i + 1 >= b){
			LL t = comb(i, b - 1);
			sum = (sum - t * h2[i + 1]) % MOD;
		}
		if(i + 1 >= w){
			LL t = comb(i, w - 1);
			t = t * h2[i + 1] % MOD;
			sum = (sum - t) % MOD;
			one = (one + t) % MOD;
		}
	}
}

void mainmain(){
	h2[0] = 1;
	for(int i = 1; i <= M; ++i){ h2[i] = h2[i - 1] * half % MOD; }
	fact[0] = 1;
	for(int i = 1; i <= M; ++i){ fact[i] = fact[i - 1] * i % MOD; }
	ifact[M] = powmod(fact[M], MOD - 2, MOD);
	for(int i = M; i > 0; --i){
		ifact[i - 1] = ifact[i] * i % MOD;
	}

	int b, w;
	scanf("%d%d", &b, &w);
	if(b <= w){
		solve(b, w, [](LL x){ return x; });
	}
	else{
		solve(w, b, [](LL x){ return 1 - x; });
	}
}



}
int main() try{
//	ios::sync_with_stdio(false); cin.tie(0);
	cout << fixed << setprecision(10);
	cerr << fixed << setprecision(4);
	mainmain();
}
catch(...){
	throw;
}


Measured memory_bytes: 6912
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<unordered_map>

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

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

long long int rev_mod(long long int num){
	long long int pow_num = MOD - 2;
	long long int mod_num = MOD;
	long long int pow_cur = num;
	long long int ret = 1;
	while(pow_num > 0){
		if(pow_num % 2 == 1){
			ret *= pow_cur;
			ret %= mod_num;
		}
		pow_cur *= pow_cur;
		pow_cur %= mod_num;
		pow_num /= 2;
	}
	return ret;
}

long long int DP[2][5200] = {};

int main(){
	int N, sz;
	cin >> N;
	string s;
	cin >> s;
	DP[0][0] = 1;
	for(int i = 0; i < N; i++){
		int pos = (i + 1) % 2, pre = i % 2;
		DP[pos][0] = (DP[pre][0] + DP[pre][1]) % MOD;
		for(int j = 1; j < 5100; j++){
			DP[pos][j] = (DP[pre][j - 1] * 2 + DP[pre][j + 1]) % MOD;
		}
	}
	long long int S = DP[N % 2][s.size()];
	for(int i = 0; i < s.size(); i++){
		S *= rev_mod(2);
		S %= MOD;
	}
	cout << S << endl;
  return 0;
}


Measured memory_bytes: 384
n,m,l = map(int, input().split())
A = []
B = []
for _ in range(n):
    A.append(list(map(int, input().split())))
for _ in range(m):
    B.append(list(map(int, input().split())))
    
C = [[0]*l for _ in range(n)]
for i in range(n):
    for j in range(l):
        for k in range(m):
            C[i][j] += A[i][k]*B[k][j]
            
for i in range(n):
    print(*C[i])


Measured memory_bytes: 7044
n, y = map(int, input().split())

for a in range(n+1):
    for b in range(n-a+1):
        if 10000 * a + 5000 * b + 1000 * (n-(a+b)) == y:
            print(a, b, n-(a+b))
            exit()

print("-1 -1 -1")

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

using namespace std;

int a;
int b;

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

    std::vector<int> vec(3);
    vec[0] = a + b;
    vec[1] = a - b;
    vec[2] = a * b;

    int max = *std::max_element(vec.begin(), vec.end());

    cout << max << endl;
}


Measured memory_bytes: 888
#include<cstdio>
#include<algorithm>
const int MaxN=10010;
int N;
struct item{
	int i,x;
	bool operator<(const item&it)const{return x<it.x;}
}a[MaxN*2];
int V[MaxN][2],ch[MaxN*4][2],rt,tot;
int left[MaxN*2],opp[MaxN*2],right[MaxN*2];
int build(int l,int r){
	if(r-l==1)return l;
	int o=tot++,mid=l+r>>1;
	ch[o][0]=build(l,mid);
	ch[o][1]=build(mid,r);
	return o;
}
int dfn[MaxN*4],low[MaxN*4],now,stk[MaxN*4],top,scc[MaxN*4],scnt;
void cmin(int&a,int b){b<a?a=b:1;}
void dfs(int i,int M);
void find(int o,int L,int R,int l,int r,int fr,int M){
	if(l>=r)return;
	if(l==L&&r==R){
		if(!dfn[o])dfs(o,M),cmin(low[fr],low[o]);
		else if(!scc[o])cmin(low[fr],dfn[o]);
	}
	else{
		int Mid=L+R>>1;
		if(r<=Mid)find(ch[o][0],L,Mid,l,r,fr,M);
		else if(l>=Mid)find(ch[o][1],Mid,R,l,r,fr,M);
		else{
			find(ch[o][0],L,Mid,l,Mid,fr,M);
			find(ch[o][1],Mid,R,Mid,r,fr,M);
		}
	}
}
void dfs(int i,int M){
	dfn[i]=low[i]=++now;
	stk[top++]=i;
	if(i<N*2){
		find(rt,0,N*2,left[i],opp[i],i,M);
		find(rt,0,N*2,opp[i]+1,right[i],i,M);
	}
	else for(int c=0;c<2;c++){
		int t=ch[i][c];
		if(!dfn[t])dfs(t,M),cmin(low[i],low[t]);
		else if(!scc[t])cmin(low[i],dfn[t]);
	}
	if(low[i]==dfn[i]){
		scnt++;
		do scc[stk[--top]]=scnt;
		while(stk[top]!=i);
	}
}
bool chk(int M){
	now=top=scnt=0;
	for(int i=0;i<tot;i++)dfn[i]=scc[i]=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<2;j++){
			left[V[i][!j]]=std::lower_bound(a,a+N*2,(item){0,a[V[i][j]].x-M+1})-a;
			right[V[i][!j]]=std::upper_bound(a,a+N*2,(item){0,a[V[i][j]].x+M-1})-a;
			opp[V[i][!j]]=V[i][j];
		}
	}
	for(int i=0;i<N*2;i++)if(!dfn[i])dfs(i,M);
	for(int i=0;i<N;i++)
		if(scc[V[i][0]]==scc[V[i][1]])return 0;
	return 1;
}
int main(){
	scanf("%d",&N);
	for(int i=0,x,y;i<N;i++){
		scanf("%d%d",&x,&y);
		a[i*2]=(item){i,x};
		a[i*2+1]=(item){i,y};
		V[i][0]=V[i][1]=-1;
	}
	std::sort(a,a+N*2);
	for(int i=0;i<N*2;i++)V[a[i].i][V[a[i].i][0]!=-1]=i;
	tot=N*2;
	rt=build(0,N*2);
	int l=0,r=1000000001,mid;
	while(r-l>1)chk(mid=l+r>>1)?l=mid:r=mid;
	printf("%d\n",l);
}

Measured memory_bytes: 9472
#include<stdio.h>

int main(){

	int n,i;

	scanf("%d",&n);

	char str[n];

	scanf("%s",str);
	int cout = 1;

	for(i=1;i<n;i++){
		if(str[i-1] != str[i]){
			cout++;
		}
	}

printf("%d",cout);



	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<queue>
#define _USE_MATH_DEFINES
#include<math.h>
#include<cmath>
#include<ctime>
#include<map>
#include<typeinfo>
#define R(i, n) for(int i = 0;i < n; i++)
#define S(a) scanf("%d", &a)
#define S2(a, b) scanf("%d%d", &a, &b)
#define S3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define SL(a) scanf("%lld", &a)
#define SL2(a, b) scanf("%lld%lld", &a, &b)
#define SL3(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)
#define SA(i, n, a) R(i, n) scanf("%d", &a[i])
#define SAL(i, n, a) R(i, n) scanf("%lld", &a[i])
#define SC(a) scanf("%c", &a)
#define P(a) printf("%d", a)
#define PL(a) printf("%lld", a)
#define PY printf("YES")
#define PN printf("NO")
#define Py printf("Yes")
#define Pn printf("No")
using namespace std;
using ll = long long;
using PR = pair<int, int>;
const ll MOD = 1e+9 + 7;
const int INF = 1e+9;
const double PI = acos(-1);

int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

int main() {
	int n, m;
	string s, t;
	S2(n, m);
	cin >> s >> t;
	ll lcm = (ll)n * m / gcd(n, m);
	map<ll, char> map;
	ll a = 1;
	int i = 0;
	while (a <= lcm) {
		map.insert(make_pair(a, s[i]));
		a += lcm / n;
		i++;
	}
	ll b = 1;
	i = 0;
	while(b <= lcm){
		if (map.find(b) != map.end()) {
			if (map[b] != t[i]) {
				P(-1);
				return 0;
			}
		}
		b += lcm / m;
		i++;
	}
	PL(lcm);
}

Measured memory_bytes: 6144
//
//  main.cpp
//  HelloWorld
//
//  Created by purple on 2020/04/13.
//  Copyright © 2020 Purple. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <cmath>

using namespace std;

int main(int argc, const char * argv[]) {


    int s,w ;
    
    cin >> s >> w;
    
    if(s<=w)
        cout << "unsafe" << endl;
    else
        cout << "safe" << endl;

    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>

using namespace std;

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

	if (N % (2 * D + 1) == 0) {
		cout << N / (2 * D + 1) << endl;
	}
	else {
		cout << N / (2 * D + 1) + 1 << endl;
	}
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std ; 
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fast ios_base:: sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
#define endl "\n"
#define pb push_back
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
#define pii pair<int,int> 
template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }

long long M  = 2019;

int mul(int a, int b){
	int res = ((a%M)*(b%M))%M;
	return res;
}

int add(int a, int b){
	int res = ((a%M)+(b%M))%M;
	return res;
}

int sub(int a, int b){
	int res = ((a%M - b%M) + M)%M;
	return res;
}


signed main(){
    fast;
	string s; cin >> s;
	map <int,int > mp;
	int curr = 0;
	int n = s.size();
	reverse(all(s));
	int k = 1;
	for(int i=0 ; i<n ; i++){
		curr = (curr + (s[i] - '0')*k)%2019;
		mp[curr]++;
		k = k*10;
		k = k%2019;
	}    
	int ans = mp[0];
	for(auto x : mp){
		ans += (x.s*(x.s-1))/2;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3740
#include <iostream>
#include <algorithm>

#define SIZE 100001

using namespace std;

int main() {
    long  long int i,j,k,M,K,Q;
    long  long int X,N,Y,Z,nb;
    long  A[SIZE],B[SIZE],C[SIZE];
    long long int S,delta;

    long D[SIZE]; // occurrences

    cin >> N;
    for (i=0;i<N;i++)
      cin >> A[i];
    S = 0;
    for (i=0;i<SIZE;i++)
      D[i] = 0;
    for (i=0;i<N;i++) {
      S += A[i];
      D[A[i]]++;
    }

    cin >> Q;
    for (i=0;i<Q;i++) {
      cin >> B[i] >> C[i];
      if (D[B[i]]>0) {
        delta = C[i]-B[i];
        S += (delta*D[B[i]]);
        D[C[i]] += D[B[i]];
        D[B[i]] = 0;
      }
      cout << S << endl;
    }

  return 0;

}


Measured memory_bytes: 6772
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  int N,ans=0;
  cin>>N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    int a,b;
    cin>>a>>b;
    A[i]=a+b;
    ans-=b;
  }
  sort(A.begin(),A.end());
  reverse(A.begin(),A.end());
  for(int i=0;i<N;i+=2)
    ans+=A[i];
  cout<<ans<<endl;
}

Measured memory_bytes: 4060
#include <bits/stdc++.h> 
 
using namespace std;
 
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<long, long> PLL;
 
//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a)  (a).begin(),(a).end()
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
const double EPS=1e-10;
 
typedef int Weight;
//typedef
//------------------------------------------
 
typedef int Weight;
//typedef
//------------------------------------------

int main(){
    int N,M;
    cin>>N>>M;
    vector<int>A(N),B(M);
    vector<int>S(N*M+1);
    fill(ALL(S), 0);
    REP(i,N){
        cin>>A[i];S[A[i]]++;
    }
    REP(i,M*N)if(S[i+1]>1){
        cout<<0<<endl;return 0;
    }
    fill(ALL(S), 0);
    REP(i,M){
        cin>>B[i];S[B[i]]++;
    }
    REP(i,M*N)if(S[i+1]>1){
        cout<<0<<endl;return 0;
    }
    SORT(A);SORT(B);
    int now=N*M;
    LL res=1;
    long mod=(long)(1e9+7);
    int num=0;
    REP(cnt,N*M-1){
        LL tmp=1;
        bool flagA=binary_search(ALL(A), now);
        bool flagB=binary_search(ALL(B), now);
        auto itrA=lower_bound(ALL(A),now);
        auto itrB=lower_bound(ALL(B),now);
        if(!flagA&&!flagB){
            // /cout<<A.end()-itrA<<endl;cout<<B.end()-itrB<<endl;
            tmp=(A.end()-itrA)*(B.end()-itrB)-cnt;
        }else if(!flagA&&flagB){
            tmp=A.end()-itrA;
        }else if(flagA&&!flagB){
            tmp=B.end()-itrB;
        }else if(flagA&&flagB){
            tmp=1;
        }
        //cout<<now<<" "<<tmp<<endl;
        res=(res*tmp)%mod;
        now--;
    }
    cout<<res<<endl;
    return 0;
}
/*
2 2
4 2
3 4
*/

Measured memory_bytes: 4096
import sys

def main():
    N = input()
    A = [int(a) for a in input().split()]
    print(counter(A))

def counter(A):
    count = -1
    judge = True
    while judge:
        A_ = []
        for a in A:
            if a%2 == 1:
                judge = False
                break
            else:
                A_.append(int(a/2))
        count += 1
        A = A_
    return count

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define rep(i, f, n) for (int i = (f); i < (int)(n); i++)
#define repe(i, f, n) for (int i = (f); i <= (int)(n); i++)
using namespace std;
using ll = long long;

using pint = pair<int, int>;

const int INF = 1001001001;

int main() {
  int N;
  cin >> N;
  int ma = 0, mi = INF, a;
  rep(i, 0, N) {
    cin >> a;
    ma = max(ma, a);
    mi = min(mi, a);
  }

  cout << abs(ma - mi) << endl;

  return 0;
}


Measured memory_bytes: 3560
#include <stdio.h>

int main(){
  int N,i,j,cnt=0,tmp=0,minj=1,A[100];
  
  scanf("%d",&N);
  
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }

  for(i=0;i<N;i++){
    minj=i;

    for(j=i;j<N;j++){
      
      if (A[j]<A[minj]){
	minj=j;

      }
    }
    if(A[i]!=A[minj]){
	tmp=A[i];   //A[i] と A[minj] を交換
	A[i]=A[minj];
	A[minj]=tmp;
	cnt++;
    }
  }
  
   for(i=0;i<N-1;i++){
    printf("%d ",A[i]);
  }
  printf("%d\n",A[i]);
  printf("%d\n",cnt);

  return 0;

}



Measured memory_bytes: 2124
#include"stdio.h"
#include"cstdio"
#include"string.h"
#include"cstdio"
using namespace std;
typedef long long ll;
int main()
{
	ll k;
	while(scanf("%lld",&k)!=EOF)
	{
		printf("50\n");
		for(ll i=0;i<50;i++)
		printf("%lld ",49-i+(49-i+k)/50);
	}
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
   int a,b;
  cin>>a>>b;
  int n[a+1];
  for(int i=0;i<a;i++)
    cin>>n[i];
  int dp[a+1];
  dp[0]=0;
  dp[1]=abs(n[1]-n[0]);
  for(int i=2;i<a;i++)
  {
    dp[i]=dp[i-1]+abs(n[i]-n[i-1]);
    for (int j=1; j<=b; j++) 
    {
      if (i-j <0) break;
      dp[i]=min(dp[i],dp[i-j]+abs(n[i]-n[i-j]));
    }
  }
  cout<<dp[a-1];
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>                 // [PRIMES]               1777 ~2^10.80
using namespace std;                     //                       10333 ~2^13.33
using ll = long long;                    // seq 1 128 | factor   100333 ~2^16.61
using ld = long double;                  //   | grep -v ' .* '  1300111 ~2^20.31
using vl = vector<ll>;                   //                    10300777 ~2^23.30
using vvl = vector<vl>;                  //                   100400999 ~2^26.58
using pll = pair<ll,ll>;                 //                  1300400999 ~2^30.28
using vpll = vector<pll>;                //                 10200500333 ~2^33.25
using vb = vector<bool>;                 //                100200400777 ~2^36.54
using vs = vector<string>;               //               1200300700111 ~2^40.13
const ll oo = 0x3f3f3f3f3f3f3f3fLL;      //              10200300500777 ~2^43.21
const ld eps = 1e-9;                     //             100200300400777 ~2^46.51
#define sz(c) ll((c).size())             //            1200300400600999 ~2^50.09
#define all(c) begin(c),end(c)           //           10200300400600111 ~2^53.18
#define mp make_pair                     //          100200300400600333 ~2^56.48
#define mt make_tuple                    //         1200300400500800999 ~2^60.06
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define FOR(i,a,b) for(ll i=(a); i<(b); i++)
#define FORD(i,a,b) for(ll i=ll(b)-1;i>=(a);i--)
#define TR(X) ({if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

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

	ll h, w; cin >> h >> w;
	vector<vb> grid(h+1, vb(w+1, false));
	
	FOR(x,1,h+1) {
		FOR(y,1,w+1) {
			char tmp; cin >> tmp;
			if (tmp == '.') {
				grid[x][y] = true;
			}
		}
	}

	vvl dp(h+1, vl(w+1, 0));
	const ll MOD = 1e9 + 7;

	dp[1][1] = 1;
	FOR(x,1,h+1) {
		FOR(y,1,w+1) {
			if (x == 1 && y == 1) continue;

			if (grid[x][y]) {
				dp[x][y] = dp[x-1][y] + dp[x][y-1];
				if (dp[x][y] >= MOD) dp[x][y] -= MOD;
			}
		}
	}

	cout << dp[h][w] << "\n";

	return 0;
}


Measured memory_bytes: 8320
// {{{
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
// }}}

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

static constexpr int mod = (int)1e9 + 7;
static constexpr int inf = 100100100;
static constexpr ll linf = 1e18;
static constexpr double eps = 1e-9;
static constexpr double pi = 3.14159265359;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rrep(i, n) for (ll i = n; i >= 0; --i)
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define pb push_back
#define ist insert
#define fst first
#define snd second


int main() {
    // cin.tie(0);
    // ios_base::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    deque<ll> d;
    rep (i, N) {
        ll v;
        cin >> v;
        d.pb(v);
    }
    ll M = min(N, K);
    ll ans = -linf;
    for (ll a = 0; a <= M; ++a) {
        for (ll b = 0; a + b <= M; ++b) {
            auto q = d;
            vector<ll> v;
            rep (i, a) {
                v.pb(q.front());
                q.pop_front();
            }
            rep (i, b) {
                v.pb(q.back());
                q.pop_back();
            }
            sort(all(v));
            ll c = 0;
            ll tmp = 0;
            for (ll i : v) {
                if (i < 0 && a + b + c < K) {
                    ++c;
                    continue;
                }
                tmp += i;
            }
            ans = max(ans, tmp);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>

using namespace std;

int gcd(int x, int y) {
  int r;

  if (x < y) {
    swap(x, y);
  }

  while (y > 0) {
    r = x % y;
    x = y;
    y = r;
  }

  return x;
}

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

  cout << gcd(a, b) << endl;

  return 0;
}



Measured memory_bytes: 3100
using System;
class abc162_b{
  public static void Main(){
    long n = long.Parse(Console.ReadLine());
    long sum=0;
    for(long i=1; i<=n; i++){
      if(i%3 == 0 || i%5 == 0)
        continue;
      sum += i;
    }
    Console.WriteLine(sum);
  }
}


Measured memory_bytes: 17600
import Data.List (sort)
import Control.Monad.State
import qualified Data.Map as M

main:: IO ()
main = do
    xs <- (map read . words) <$> getLine
    print $ solve xs

-- |
--
-- >>> solve [4,12,20]
-- 3
--
-- >>> solve [14,14,14]
-- -1
solve :: [Int] -> Int
solve as = rec 0 (sort as)
  where

    rec :: Int -> [Int] -> Int
    rec n xs@(xh:xts)
      | any odd xs = n
      | all (== xh) xts = -1
      | otherwise = rec (n+1) (sort $ next xs)

    next :: [Int] -> [Int]
    next xs = map (sum halves - ) halves
      where halves = map (`div` 2) xs


Measured memory_bytes: 508
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int h = sc.nextInt();
        int w = sc.nextInt();

        String[] s = new String[h];

        for (int i = 0; i < h; i++) {
            s[i] = sc.next();
        }

        sc.close();

        for (int i = 0; i < h; i++) {
            System.out.println(s[i]);
            System.out.println(s[i]);
        }

    }
}

Measured memory_bytes: 23504
import sys
import re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []


def main():
    S = s_input()
    T = s_input()

    min = 100000
    for i in range(0,len(S)-len(T)+1):
        count = 0
        for j in range(0,len(T)):
            if(S[i+j] != T[j]):
                count=count+1
        if(count<=min):
            min = count


    print(min)

    return

if __name__ == '__main__':
    main()

Measured memory_bytes: 10328
#include <bits/stdc++.h>
using namespace std;
 
 
 
 
int main() {
string S;
cin >> S;
int moji = S.size();
string ans;
int maxnaga = 0;
for(int i = 0; i < moji; i++){
bool check = 1;
string kari;
 
int naga = 0;
if(S[i] == 'A' || S[i] == 'T' || S[i] == 'C' || S[i] == 'G'){
kari = S[i];
naga++;if(naga > maxnaga){
       maxnaga = naga;
ans = kari;
   }
}
else check = 0;
for(int j = i+1; j < moji; j++){
if(check == 1 && ( S[j] == 'A' || S[j] == 'T' || S[j] == 'C' || S[j] == 'G')){
    kari += S[j];
    naga++;
   if(naga > maxnaga){
       maxnaga = naga;
ans = kari;
   }
}
else check = 0;
 
}
 
 
 
}
cout << maxnaga << endl;
 
}



Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(void)
{
	char s[1001],t[1001];
	int i,j,cnt,mn,len,ln,p;
	scanf("%s",s);
	scanf("%s",t);
	len=strlen(s);
	ln=strlen(t);
	cnt=0;	mn=1001;
	for(i=0;i<len-(ln-1);i++){
		p=i;
		for(j=0;j<ln;j++){
			if(s[p]!=t[j])	cnt++;
			p++;
		}
		if(mn>=cnt)	mn=cnt;
		cnt=0;
	}
	printf("%d\n",mn);
	return 0;
}


Measured memory_bytes: 1700
n,m = map(int,input().split())
l = []
r = []
for i in range(m):
    l0,r0 = map(int,input().split())
    l.append(l0)
    r.append(r0)
ans = min(r)-max(l)+1
if ans >= 0:
    print(ans)
else:
    print(0)

Measured memory_bytes: 10996
/*
      Ashraful Islam Paran
      22-August-2020
      19:49:07
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f(n) for (int i = 0; i < n; i++)
#define fo(i, x, n) for (int i = x; i < n; i++)
#define fb(i, x, n) for (int i = n - 1; i <= 0; i--)
#define w(t) int t; cin >> t; while (t--)



typedef unsigned long long ull;
typedef vector<long long> vi;
#define ull unsigned long long
#define msi map<string, long long>
#define mii map<long long, long long>
const int MX = 2e5 + 5;
const int INF = 1e18;
#define pb push_back
#define endl "\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define all(x) x.begin(), x.end()
#define ff first
#define ss second


int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    // online submission
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin>>n;
    int a[n];
    f(n)
    {
        cin>>a[i];
    }
    int x=*max_element(a,a+n);
    int cnt{0};
    f(n-1)
    {
        if(a[i]>a[i+1])
        {
            cnt+=a[i]-a[i+1];
            a[i+1]+=a[i]-a[i+1];
        }
    }
    cout<<cnt<<endl;
    
    
    
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}

Measured memory_bytes: 5332
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

vector<string> vs;
int main(){
    string s,t,ans;
    int k;
    cin>>s>>k;
    t=s;
    FOR(i,1,6){
        rep(j,s.size())if(i+j<=s.size()){
            vs.pb(s.substr(j,i));
        }
    }
    
    sort(vs.begin(),vs.end());
    vs.erase(unique(vs.begin(),vs.end()),vs.end());
    //for(auto it:vs) cout<<it<<endl;
    cout<<vs[k-1]<<endl;
    return 0;
}

Measured memory_bytes: 1660
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

class Edge{
	int edge;
	int weight;

	Edge(int a ,int b){
		this.edge = a;
		this.weight = b;
	}
}


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		List<List<Edge>> edge = new ArrayList<>();

		for(int i = 0 ; i < N ; ++i){
			edge.add(new ArrayList<>());
		}

		for(int i = 1 ; i < N ; ++i){
			int u = sc.nextInt()-1;
			int v = sc.nextInt()-1;
			int w = sc.nextInt();

			edge.get(u).add(new Edge(v,w));
			edge.get(v).add(new Edge(u,w));

		}

		sc.close();

		int[] colors = new int[N];
		Arrays.fill(colors, -1);
		colors[0] = 0;

		Queue<Integer> queue = new ArrayDeque<>();

		queue.add(0);

		while(!queue.isEmpty()){
			int tmp = queue.poll();
			for(Edge i : edge.get(tmp)){
				//System.out.println(tmp + " " + i.edge + " " + i.weight);
				if(colors[i.edge] >= 0){
					continue;
				}
				//colors[i.edge] = colors[tmp] ^ (i.weight & 1);
				if(i.weight%2 == 0){
					colors[i.edge] = colors[tmp];
				}
				else{
					if(colors[tmp] == 0){
						colors[i.edge] = 1;
					}
					else{
						colors[i.edge] = 0;
					}
				}

				//System.out.println(colors[i.edge]);
				queue.add(i.edge);
			}
		}

		for(int i = 0 ; i < N ; ++i){
			System.out.println(colors[i]);
		}
	}
}


Measured memory_bytes: 107332
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

int main() {
    while (true) {
        int q;
        cin >> q;
        if (q == -1) return 0;
        double x = q / 2.0;
        for ( ; ; ) {
            double res = x * x * x - q;
            if (fabs(res) < 0.00001 * q) break;
            double xnext = x - res / (3 * x * x);
            x = xnext;
        }
        printf("%.6lf\n", x);
    }
}

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

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

#define DIVUP(x, y) (((x) + ((y) - 1)) / (y))
#define DIVOFF(x, y) (((x) + ((y) / 2)) / (y))
#define REMAINDER(x, y) ((x) % (y))

int main() {
  long N, P; scanf("%ld%ld", &N, &P);
  long factor{1};

  if (N == 1) {
    printf("%ld\n", P);
    return 0;
  }

  int count{};
  while (P % 2 == 0) {
    if (++count % N == 0) {
      factor *= 2;
    }
    P /= 2;
  }
  for (long i{3}; i * i <= P; i += 2) {
    count = 0;
    while (P % i == 0) {
      if (++count % N == 0) {
        factor *= i;
      }
      P /= i;
    }
  }

  printf("%ld\n", factor);
  return 0;
}


Measured memory_bytes: 760
n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = n-R-G

lR = 0
lG = 0
lB = 0

rR = R
rG = G
rB = B

ans = 0
for i in range(n):
    if s[i] == "R":
        rR -= 1
        ans += lG*rB
        ans += lB*rG
        lR += 1
    elif s[i] == "G":
        rG -= 1
        ans += lB*rR
        ans += lR*rB
        lG += 1
    else:
        rB -= 1
        ans += lR*rG
        ans += lG*rR
        lB += 1
for i in range(1,n-1):
    x = min(i, n-1-i)
    if s[i] == "R":
        for j in range(1,x+1):
            if (s[i-j] == "G" and s[i+j] == "B") or (s[i-j] == "B" and s[i+j] == "G"):
                ans -= 1
    elif s[i] == "G":
        for j in range(1,x+1):
            if (s[i-j] == "R" and s[i+j] == "B") or (s[i-j] == "B" and s[i+j] == "R"):
                ans -= 1
    else:
        for j in range(1,x+1):
            if (s[i-j] == "R" and s[i+j] == "G") or (s[i-j] == "G" and s[i+j] == "R"):
                ans -= 1

print(ans)

Measured memory_bytes: 68268
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt(), m=sc.nextInt();
		sc.close();
		if(n>1 && m>1) System.out.println((long)(n-2)*(m-2));
		else {
			long ans=(long)n*m;
			if(ans>1) System.out.println(ans-2);
			else System.out.println("1");
		}
	}
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long n, c, t;
    cin >> n >> c;

    vector<long> w;
    vector<long> v;

    long total_value = 0;
    for (int i = 0; i < n; i++) {
        cin >> t;
        w.push_back(t);
        cin >> t;
        v.push_back(t);
        total_value += t;
    }

    vector<vector<long>> dp(n + 1, vector<long>(total_value + 1, c + 1));

    for (int i = 0; i < n + 1; i++) {
        dp[i][0] = 0;
    }

    long ans = 0;
    for (int i = 1; i < n + 1; i++) {
        for (int j = 0; j < total_value + 1; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i - 1])
                dp[i][j] = min(dp[i][j], w[i - 1] + dp[i - 1][j - v[i - 1]]);
        }
    }

    for (int j(0); j < total_value + 1; j++)
        if (dp[n][j] <= c) {
            ans = (long) j;
        }
    cout << ans << endl;
}


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

int main() {
    int K;
    cin >> K;
    vector<int> A = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cout << A[K-1] << endl;
    return 0;
}

Measured memory_bytes: 256
s = input()
invs = s[::-1]

MOD = 10 ** 9 + 7
 
dp = [[0]*13 for _ in range(len(s))]

if invs[0]=='?':
    for i in range(10): # 0~9までは1 10~12は0のまま
        dp[0][i] = 1
else:
    dp[0][int(invs[0])] = 1

mul = 10
for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * mul )%13  ]  += dp[order-1][j]%MOD
        else:
            number = int(invs[order])
            dp[order][(j+number * mul )%13 ]  += dp[order-1][j]%MOD
        dp[order][(j+number * mul )%13 ] %= MOD
    mul *= 10
    mul %= 13
print(dp[-1][5]%MOD)

Measured memory_bytes: 64932