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

using namespace std;

template <class T> void mini(T &l, T r) {l = min(l, r);}
template <class T> void maxi(T &l, T r) {l = max(l, r);}

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(bool a) {
  return a ? "T" : "F";
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = long long;
using ld = long double;

const int N = 101;

int A, B;
int d[N][N];
int a[N][N];

void run() {
  cin >> A >> B;
  for (int i = 1; i <= A; ++i) {
    for (int j = 1; j <= B; ++j) {
      cin >> d[i][j];
    }
  }
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      for (int x = 1; x <= A; ++x) {
        for (int y = 1; y <= B; ++y) {
          maxi(a[i][j], d[x][y] - i * x - j * y);
        }
      }
    }
  }
  for (int x = 1; x <= A; ++x) {
    for (int y = 1; y <= B; ++y) {
      bool ok = 0;
      for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
          if (a[i][j] + i * x + y * j == d[x][y]) {
            ok = 1;
          }
        }
      }
      if (!ok) {
        puts("Impossible");
        return;
      }
    }
  }

  puts("Possible");
  printf("%d %d\n", 2 * N, N * N + (N - 1) * 2);
  for (int i = 0; i + 1 < N; ++i) {
    printf("%d %d X\n", i + 1, i + 2);
    printf("%d %d Y\n", N + i + 2, 1 + N + i);
  }
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      printf("%d %d %d\n", i + 1, j + N + 1, a[i][j]);
    }
  }
  printf("1 %d\n", N + 1);
}

int main() {
  run();
  return 0;
}


Measured memory_bytes: 384
from math import ceil
N = int(input())
A = []
for i in range(N):
    A.append((i, int(input())))
A.sort(key=lambda x:x[1])
B = [0]*N
for i, p in enumerate(A):
    j, _ = p
    B[j] = i
res = 0
for i, b in enumerate(B):
    if (i-b)%2:
        res += 1
print(ceil(res/2))

Measured memory_bytes: 83108
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0] * n
f = 0
for i in range(n):
    c[i] = b[i] - a[i]
    if c[i] >= 0:
        f += c[i] //2
    else:
        f += c[i]

if f >= 0:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 4596
using System;
using System.Collections.Generic;
using System.Linq;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var b = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            int cnt = 0;
            for (int i = 0; i < a[0]; i++)
            {
                var c = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
                int sum = 0;
                for (int j = 0; j < a[1]; j++)
                {
                    sum += c[j] * b[j];
                }
                if (sum > -a[2]) cnt++;
            }
            Console.WriteLine(cnt);
        }
    }
}



Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
int main ()
{

   int n , s=0 ,a;
   cin >> n;
   a=n;
   while(n>0)
   {
       s=s+n%10;
       n=n/10;
   }
   if(a%s==0)
    cout << "Yes";
   else
    cout << "No";

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
  int s = 0;
  string a, b;
  cin >> a >> b;
  for(int i = 0; i < 3; i++){
    if(a[i] == b[i]){
      s++;
    }
  }
  cout << s << "\n";
}

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

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

using namespace std;

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

  cout<<max( {((k-a+1)/2)*(b-a)+((k-a+1)/2>0 ? a :0) + (k-a+1)%2, k+1} );

  return 0;
}


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

//	最大公約数 Greatest Common Divisor O(logN)
template <typename T>
T gcd( T a, T b ) {
	if( b == 0 ) {
		return a;
	} else {
		return gcd( b, a%b );
	}
}

int main( void ) {
    int a, b;
    cin >> a >> b;
    cout << gcd( a, b ) << endl;
}


Measured memory_bytes: 3080
n,m =map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
for i in range(m):
    lis[i].append(i)
lis.sort()
cnt = 1
ans = []
ans.append([lis[0][-1],format(lis[0][0]).zfill(6)+format(1).zfill(6)])
for i in range(m-1):
    if lis[i][0] == lis[i+1][0]:
        cnt += 1
        ans.append([lis[i+1][-1],format(lis[i+1][0]).zfill(6)+format(cnt).zfill(6)])
    else:
        cnt = 1
        ans.append([lis[i+1][-1],format(lis[i+1][0]).zfill(6)+format(cnt).zfill(6)])
ans.sort(key = lambda x:x[0])
for i,x in ans:
    print(x)

Measured memory_bytes: 46008
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
  cin>>n>>k;
  string s;
  cin>>s;
  int i;
  int l=s.length();
  for(i=0;i<l;i++)
  {
	if(i==k-1)
      s[i]=tolower(s[i]);
  }
  cout<<s;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <fstream>
#include <queue>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <sstream>

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

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
#define SORT(c) sort((c).begin(),(c).end())
#define vi(m,a) vector<int> m(a)
#define vti(m,a,i) vector<vector<int>> m(a,vector<int>(i))
#define ALL(it,a) for(auto it = a.begin(); it!=a.end(); it++)
#define Fe(it,a) for(auto &it : a)
#define all(a) begin(a),end(a)

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define WARU 1000000007;

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

ll kyori(int a, int b, int c) {
	int k = max(a, b);
	int l = min(a, b);
	return(min(abs(k - l), abs(k - l - c)));
}

int main() {
	set<string> ss;
	string str;
	cin >> str;
	int count;
	cin >> count;

	rep(i, str.length()) {
		rep(k, str.length()) {
			if (k > count)
				break;
			ss.insert(str.substr(i,k + 1));
		}
	}

	int current = 0;
	ALL(it, ss) {
		current++;
		if (count == current) {
			cout << *it << endl;
			break;
		}
	}

}



Measured memory_bytes: 2176
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
VI a;
VVI egs;
VI wn;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n;
  cin>>n;
  a.resize(n);
  wn.resize(n);
  egs.resize(n);
  forn(i,n)
    cin>>a[i];
  in ta,tb;
  forn(i,n-1){
    cin>>ta>>tb;
    --ta;
    --tb;
    egs[ta].PB(tb);
    egs[tb].PB(ta);
  }
  map<in,VI> v;
  forn(i,n)
    v[a[i]].PB(i);
  VI tp;
  in u;
  fors(it,v){
    tp=it->second;
    forv(i,tp){
      u=tp[i];
      if(wn[u])
	continue;
      wn[u]=-1;
      forv(j,egs[u]){
	if(!wn[egs[u][j]] && a[egs[u][j]]!=a[u])
	  wn[egs[u][j]]=1;
      }
    }
  }
  forn(i,n)
    if(wn[i]==1)
      cout<<i+1<<" ";
  cout<<endl;
  return 0;
}


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

int main(){
  int A,B;
  scanf("%d%d",&A,&B);
  if (A==1) A=14;
  if (B==1) B=14;
  if (A==B) printf("Draw\n");
  else printf("%s\n",A>B?"Alice":"Bob");
}


Measured memory_bytes: 256
import collections


class RollingHash:
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod

        self.hash = [0]
        self.power = [1]
        for c in s:
            self.hash.append((self.hash[-1] * base + ord(c)) % mod)
            self.power.append(self.power[-1] * base % mod)

    def get(self, left, right):
        h = self.hash[right] - self.hash[left] * self.power[right - left]
        return (h + self.mod) % self.mod


n = int(input())
s = input().rstrip()
rh = RollingHash(s, base=10**4 + 7, mod=10**9 + 7)


def check(diff):
    d = collections.defaultdict(list)
    for i in range(n - diff + 1):
        h = rh.get(i, i + diff)
        d[h].append(i)
    for l in d.values():
        if max(l) - min(l) >= diff:
            return True
    return False


lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)

Measured memory_bytes: 47964
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char I[1000],*p;
int A,t,o;

int c(int t)
{
	if(t==1){o++;return t;}
	else if(t>10)return 10;
	return t;
}

int main()
{
	for(;gets(I);)
	{
		p=strtok(I," ");
		o=0;
		A=c(atoi(p));
		if(A==0)return 0;
		for(;(p=strtok(NULL," "))!=NULL;)
			A+=c(atoi(p));
		for(;o--;)
			if(A+10<=21)
				A+=10;
		printf("%d\n",A>21?0:A);
	}
	return 0;
}

Measured memory_bytes: 524
X, N = map(int, input().split())
P = list(map(int, input().split()))

for i in range(X, 1000):
    if i not in P:
        a = i
        break
b = 0
for i in range(X, -1, -1):
    if i not in P:
        b = i
        break

if a-X < X-b:
    print(a)
else:
    print(b)

Measured memory_bytes: 9184
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
struct Item {
	int v, w;
	Item() :v(0), w(0) {}
	Item(int v, int w) :v(v), w(w) {}
	bool operator<(const Item &p)const {
		return w == p.w ? v < p.v : w < p.w;
	}
	Item operator+=(const Item &p) {
		v += p.v;
		w += p.w;
		return *this;
	}
	Item operator+(const Item &p) {
		Item x(*this);
		x += p;
		return x;
	}
};
istream &operator >> (istream &is, Item &p) {
	is >> p.v >> p.w;
	return is;
}
ostream &operator<<(ostream &os, Item p) {
	os << p.v << " " << p.w;
	return os;
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, W; cin >> N >> W;
	vector<Item> item(N); rep(i, 0, N) { cin >> item[i]; }
	int n1 = N / 2, n2 = N - n1;
	vector<Item>a, b;
	rep(bits, 0, 1 << n1) {
		Item x;
		rep(j, 0, n1)if (bits&(1 << j))x += item[j];
		a.push_back(x);
	}
	rep(bits, 0, 1 << n2) {
		Item x;
		rep(j, 0, n2)if (bits&(1 << j))x += item[n1 + j];
		b.push_back(x);
	}
	sort(all(b));
	int m(1);
	rep(i, 1, b.size()) {
		if (b[m - 1].v < b[i].v)b[m++] = b[i];
	}
	int ans(0);
	rep(i, 0, a.size()) {
		if (a[i].w > W)continue;
		chmax(ans, a[i].v + prev(upper_bound(b.begin(), b.begin() + m, Item(INF, W - a[i].w)))->v);
	}
	cout << ans << endl;
	return 0;
}

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

int main(){
    string s; cin >> s;
    int n = s.length();
    rep(i, (n-1)/4){
        if(s[i] != s[(n-1)/2-i-1]){
            cout << "No" << endl;
            return 0;
        }
    }
    rep(i, n){
        if(s[i] != s[n-i-1]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
double sum = 0;
int n;

double dp[30001][3001];

int main(){
  int i,j;
  double p[3000];
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%lf",&p[i]);
  dp[0][0] = 1-p[0];
  dp[0][1] = p[0];

  for(i=0;i<n-1;i++){
    for(j=0;j<=i+1;j++){
      dp[i+1][j] += dp[i][j]*(1-p[i+1]);
      dp[i+1][j+1] += dp[i][j]*(p[i+1]);
    }
  }
  /*
  for(i=0;i<n+1;i++){
    for(j=0;j<n+1;j++){
      printf("%f ", dp[i][j]);
    }
    printf("\n");
  }*/
  double res=0;
  for(i=(n/2)+1;i<n+1;i++){
    res += dp[n-1][i];
  }

  printf("%.10f\n", res);

  return 0;


}


Measured memory_bytes: 70144
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys

D = int(sys.stdin.readline())
c = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
s = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(D)) # multi line with multi param
t = tuple(int(sys.stdin.readline()) for _ in range(D)) # multi line with single param

sat = 0
last = [0]*26
for d in range(D):
    j = t[d]-1
    sat = sat + s[d][j]
    last[j] = d+1
    sat = sat - sum(c[i]*(d+1-last[i]) for i in range(26))
    print(sat)

Measured memory_bytes: 68280
import java.util.Scanner;
import java.util.*;

public class Main{

   static boolean Sosu(int p){
        int count=0;
        if(p==1) return false;
        else if(p==2) return true;
        else {
            for (int i=2;i<Math.sqrt(p)+1;i++){
            if(p%i==0) count++;
        }
        if(count==0) return true;
        else return false;
    }
   }
    public static void main(String[] args){
        int count=0;
        ArrayList<Integer> list =new ArrayList<Integer>();
        Scanner sc = new Scanner(System.in);
        int a= sc.nextInt();
        for(int i=0;i<a;i++){
        int b =sc.nextInt();
        list.add(b);
        }
        for(int i=0;i<list.size();i++){
            if(Sosu(list.get(i))==true) count++; 
        }
        System.out.println(count);
        }
}




Measured memory_bytes: 42696
import java.util.Scanner;

public class Main {

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

            int x = 1;
            int c = 0;
            for (int i = 0; i < N; i++) {
                int a = sc.nextInt();
                if (a == x) {
                    x++;
                } else {
                    c++;
                }
            }

            if (c == N) {
                c = -1;
            }

            System.out.println(c);
        }
    }

}


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

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template <typename T> using pq = priority_queue<T>;
template <typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template <typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for (ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for (auto &i : mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template <class T> ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template <class T> istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template <class T> ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    string s;
    cin>>s;
    ll n = s.size();
    ll sum = 0;
    rep(i, n) {
        sum += s[i] - '0';
    }
    if (sum%9==0) cout << "Yes" << '\n';
    else cout << "No" << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}


Measured memory_bytes: 3684
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli long long int
#define ulli unsigned long long int
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pf pop_front()
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define loopl(i,a,b) for(lli i=a;i<b;i++) 
#define loop(i,a,b) for(int i=a;i<b;i++)
#define mod 1000000007
#define inf 100000000000000000
#define lld long double
#define pll pair<long long int,long long int>
#define vll vector<lli>
#define eps 0.000001
#define endl '\n'
#define mo 998244353
 
using namespace std ;
 
#define MAXN 300005
 
typedef tree<lli,null_type,less<lli>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;

vector<pll> v[100000 + 5];

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

    loopl(i,0,n-1)
    {
        lli x,y,w;
        cin>>x>>y>>w;
        v[x].pb({y,w});
        v[y].pb({x,w});
    }

    lli col[n+1]={0} ;
    bool vis[n+1]={0};

    vis[1]=1;
    col[1]=1;

    queue<pll> q;

    q.push({1,0});

    while(!q.empty())
    {
        pll x = q.front();
        q.pop();
        vis[x.ff]=1;

        if(x.ss%2 == 0)
            col[x.ff] = 1;

        for(auto y:v[x.ff])
        {
            if(!vis[y.ff])
                q.push({y.ff,x.ss + y.ss});
        }
    }

    loopl(i,1,n+1)
    cout<<col[i]<<endl;


}

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

int main(){
   int a, b;
   cin >> a >> b;
   string s;
   string t = to_string(a);
   string u = to_string(b);
   int i;
   if(a == b){
       for(i = 0; i < a; i++){
           s += u;
       }
       cout << s << endl;
       return 0;
   }
   else if(a > b){
       for(i = 0; i < a; i++){
           s += u;
       }
       cout << s << endl;
       return 0;
   }
   else{
       for(i = 0; i < b; i++){
           s += t;
       }
       cout << s << endl;
       return 0;
   }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> a(3);
    rep(i,3) cin >> a[i];
    sort(a.begin(), a.end());
    int ans = 0;
    while(a[0] != a[1] || a[1] != a[2]){
        sort(a.begin(), a.end());
        if(a[0] == a[1]){
            ++a[0];
            ++a[1];
        }
        else{
            a[0] += 2;
        }
        ++ans;
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

int main(){
    long long x; cin >> x;
    long long ans=(x/11)*2;
    long long r=x%11;
    if(r==0) ;
    else if(r<=6) ++ans;
    else ans+=2;
    cout << ans << endl;
    return 0;
}


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

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

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

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

using namespace std;

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

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

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

// Problem Specific Parameter:

int main(void) {
	ll x, t;
	cin >> x >> t;

	const R p = 1.0 * t / 100.0;
	const R q = 1.0 - p;

	R ans = 1.0 * (x / 2) / p;
	if (x % 2 == 1) ans += q / p + 1.0;

	cout.precision(20);
	cout << fixed << ans << endl;

	return 0;
}

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

using namespace std;

void Run() {
  int n;
  cin >> n;
  vector<string> v;
  for (int i = 0; i < n; ++i) {
    string x;
    cin >> x;
    reverse(x.begin(), x.end());
    v.push_back(x);
  }
  sort(v.begin(), v.end(), [&](const string& a, const string& b) {
      return a.size() > b.size();
  });
  vector<vector<int>> trie{vector<int>(26, -1)};
  vector<vector<int>> on{vector<int>(26, 0)};
  static int nodes = 1;
  trie.push_back(vector<int>(26, -1));
  auto Create = [&]() {
    trie.push_back(vector<int>(26, -1));
    on.push_back(vector<int>(26, 0));
    return nodes++;
  };
  auto Insert = [&](const string& s) {
    int cur = 0;
    vector<int> cnt(26);
    for (int i = 0; i < s.size(); ++i)
      ++cnt[s[i] - 'a'];
    for (int i = 0; i < s.size(); ++i) {
      for (int k = 0; k < 26; ++k) {
        on[cur][k] += (cnt[k] > 0 ? 1 : 0);
      }
      int c = s[i] - 'a';
      if (trie[cur][c] == -1) {
        trie[cur][c] = Create();
      }
      cur = trie[cur][c];
      --cnt[c];
    }
  };
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    // check trie
    int node = 0;
    bool ok = true;
    for (int j = 0; j + 1 < v[i].size(); ++j) {
      if (trie[node][v[i][j] - 'a'] == -1) {
        ok = false;
        break;
      }
      node = trie[node][v[i][j] - 'a'];
    }
    if (ok) {
      ans += on[node][v[i].back() - 'a'];
    }
    Insert(v[i]);
  }
  cout << ans << '\n';
}

int main() {
  srand(time(0));
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  Run();
  return 0;
}

Measured memory_bytes: 269556
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
#define ALL(X) X.begin(), X.end()
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef std::pair<LL,LL> PLL;//
typedef std::pair<int,int> PII;//
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)4e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	int A,B;
	cin >> A >> B;
	vector<int> dat(A+B+1,0);
	for(int pos=0;pos<A;++pos){
		dat[pos] = 1;
	}
	for(int pos=0;pos<B;++pos){
		dat[pos + A+1] = 1;
	}
	string str;
	cin >> str;
	for(int pos=0;pos<A+B+1;++pos){
		if( dat[pos] == 0 && str[pos] == '-' ){
			//ok
		}else if( dat[pos] == 1 && '0' <= str[pos] && str[pos] <= '9' ){
			//ok
		}else{
			cout << "No" << endl;
			return;
		}
	}
	cout << "Yes" << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

Measured memory_bytes: 256
def hikaku(s,t):
    cnt=0
    for i in range(len(s)):
        if s[i] == t[i]:
            cnt+=1
    #print(s,t,cnt,len(s),len(s)-cnt)       
    return len(s)-cnt

s=input()
t=input()

cnt=1000
for i in range(len(s)-len(t)+1):  
    cnt = min(cnt,hikaku(s[i:i+len(t)],t))
 
print(cnt)

Measured memory_bytes: 8912
N,K=map(int, input().split())
ans=0
mod=10**9+7
for i in range(K,N+2):
  if i==K:
    MIN=sum(list(range(0,K)))
    MAX=sum(list(range(N,N-K,-1)))
  else:
    MIN+=i-1
    MAX+=N+1-i
  #print(MIN,MAX)
  ans+=(MAX-MIN+1)%mod
  ans%=mod
print(ans)

Measured memory_bytes: 16636
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr int inf=1000000000;
constexpr ll linf=1000000000000000000;

struct UnionFind{
private:
    vector<int> data;
public:
    UnionFind(int n){
        data.assign(n,-1);
    }
    int root(int x){
        if(data[x]<0)return x;
        else return data[x]=root(data[x]);
    }
    bool issame(int x,int y){
        return root(x)==root(y);
    }
    bool merge(int x,int y){
        x=root(x),y=root(y);
        if(x==y)return false;
        if(data[x]>data[y])swap(x,y);
        data[x]+=data[y];
        data[y]=x;
        return true;
    }
    int size(int x){
        return -data[root(x)];
    }
};

int main(){
    ll n,m;
    cin>>n>>m;
    UnionFind uf(n+n);
    rep(i,m){
        int a,b;
        cin>>a>>b;
        --a,--b;
        uf.merge(a+n,b);
        uf.merge(a,b+n);
    }
    if(uf.issame(0,n)){
        cout<<n*(n-1)/2-m<<endl;
    }
    else{
        ll ans=0;
        rep(i,n){
            if(uf.issame(0,i))++ans;
        }
        cout<<ans*(n-ans)-m<<endl;
    }
}


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

constexpr int max_v = 4000000;

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

    bitset<max_v + 1> dp;
    dp[0] = 1;
    for(int i = 0; i < n; ++i) {
        dp = (dp << a[i]) | dp;
    }
    int ans = 0;
    for(int i = (sum + 1) / 2; i <= max_v; ++i) {
        if(dp[i]) {
            ans = i;
            break;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 2176
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> P;
int h, w, d[50][50];
int dy[4]={1, 0, -1, 0}, dx[4]={0, 1, 0, -1};
string s[50];
int main() {
    int m=0;
    cin>>h>>w;
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            d[i][j]=1e5;
            if(s[i][j]=='.')m++;
        }
    }
    queue<P> q;
    q.push(P(0, 0));
    d[0][0]=1;
    while(!q.empty()){
        P p=q.front();
        q.pop();
        int y=p.first, x=p.second;
        for(int i=0;i<4;i++){
            int ny=y+dy[i], nx=x+dx[i];
            if(ny>=0&&ny<h&&nx>=0&&nx<w){
                if(d[ny][nx]==1e5&&s[ny][nx]=='.'){
                    d[ny][nx]=d[y][x]+1;
                    q.push(P(ny, nx));
                }
            }
        }
    }
    if(d[h-1][w-1]==1e5){
        cout<<-1<<endl;
    }else{
        cout<<m-d[h-1][w-1]<<endl;
    }
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   for(int i=0;i<(n);++i)
#define SORT(c)    sort((c).begin(),(c).end())
#define CLR(a)     memset((&a), 0 ,sizeof(a))//clear memory
#define dump(x)    cerr << #x << " = " << (x) << endl;//debug
#define debug(x)   cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define EPS        1e-10//sample:if((double)>=(double)+EPS)
//cin,cout release
//std::cin.tie(0);
//ios::sync_with_stdio(false);

using namespace std;

int row[8]={},col[8]={},lefta[15]={},righta[15]={};
bool X[8][8]={};
void p(){
  rep(i,8)rep(j,8)if(X[i][j]&&(row[i]!=j))return;
  rep(i,8){
    rep(j,8)cout<<(row[i]==j?"Q":".");
    cout<<endl;
  }
}
void dfs(int i){
  if(i==8){p();return;}
  rep(j,8){
    if(col[j]==1||lefta[i+j]==1||righta[i-j+7]==1)continue;
    row[i]=j;
    col[j]=lefta[i+j]=righta[i-j+7]=1;
    dfs(i+1);
    row[i]=col[j]=lefta[i+j]=righta[i-j+7]=0;
  }
}

int main(){
  int k,r,c;
  cin>>k;
  rep(i,k){
    cin>>r>>c;
    X[r][c]=1;
  }
  dfs(0);
  return 0;
}


Measured memory_bytes: 3112
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <unordered_map>
constexpr int MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
using namespace std;
using LL = long long;
 
int dtoN[100001];
int dto1[100001];
vector<int> G[100001];
 
int N;
 
void bfstoN() {
	queue<int> que;
	for (int i = 0; i <= N; i++)dtoN[i] = INF;
	dtoN[1] = 0;
	que.push(1);
	while (que.size()) {
		int p = que.front();
		que.pop();
		for (int i = 0; i < G[p].size(); i++) {
			if (dtoN[G[p][i]] == INF) {
				que.push(G[p][i]);
				dtoN[G[p][i]] = dtoN[p] + 1;
			}
		}
	}
}
 
void bfsto1() {
	queue<int> que;
	for (int i = 0; i <= N; i++)dto1[i] = INF;
	dto1[N] = 0;
	que.push(N);
	while (que.size()) {
		int p = que.front();
		que.pop();
		for (int i = 0; i < G[p].size(); i++) {
			if (dto1[G[p][i]] == INF) {
				que.push(G[p][i]);
				dto1[G[p][i]] = dto1[p] + 1;
			}
		}
	}
}
 
int main() {
	cin >> N;
	int a, b;
	for (int i = 0; i < N-1; i++) {
		cin >> a >> b;
		G[a].emplace_back(b);
		G[b].emplace_back(a);
	}
	bfstoN();
	bfsto1();
	int f = 0, s = 0;
	for (int i = 1; i <= N; i++) {
		if (dtoN[i] <= dto1[i])f++;
		else s++;
	}
	if (f > s)cout << "Fennec" << endl;
	else cout << "Snuke" << endl;
}

Measured memory_bytes: 6656
//header{{{
#include<bits/stdc++.h>
  
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 
 
int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}
//}}}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<pii> rl,maxt;
	vector<int> l(n),r(n);
	int maxv = -INF;
	rep(i,n){
		int a,b;
		cin >> a >> b;
		l[i] = a;
		r[i] = b;
		rl.emplace_back(b,a);
		if(r[i] - l[i] + 1 >= maxv){
			maxv = r[i] - l[i] + 1;
			maxt.emplace_back(i,maxv);
		}
	}
	maxv = 0;
	rep(i,maxt.size()){
		int L = 0;
		int R = 1000000001;
		rep(j,n){
			if(j == maxt[i].first) continue;
			if(L > r[j] || R < l[j]){
				L = R;
				R--;
				break;
			}
			if(L < l[j]) L = l[j];
			if(R > r[j]) R = r[j];
		}
		maxv = max(maxv,maxt[i].second + (R-L+1));
	}
	int tmp = maxv;
	maxv = 0;
	sort(all(rl));
	vector<int> rc;
	rep(i,n){
		rc.emplace_back(rl[i].first);
	}
	vector<int> vecl,vecr;
	int R = rl[0].first;
	int L = rl[0].second;
	vecl.emplace_back(R-L+1);
	for(int i = 1;i < n;++i){
		if(L < rl[i].second) L = rl[i].second;
		vecl.emplace_back(R-L+1);
	}
	R = rl[n-1].first;
	L = rl[n-1].second;
	vecr.emplace_back(R-L+1);
	for(int i = n-2;i >= 0;--i){
		if(R > rl[i].first) R = rl[i].first;
		vecr.emplace_back(R-L+1);
	}
	rep(i,n/2){
		swap(vecr[i],vecr[n-i-1]);
	}
	rep(i,n-1){
		maxv = max(maxv,vecl[i] + vecr[i+1]);
	}
	/*
	cout << '\n';
	rep(i,n){
		cout << vecl[i] << ' ' << vecr[i] << '\n';
	}
	cout << maxv << '\n';
	*/
		
	cout << max(maxv,tmp) << '\n';
	//cout << maxv << ' ' << tmp << '\n';
	return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

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

	ll a[n];
	rep(i, n) cin >> a[i];

	ll ans = 1e11;
	rep(i, n){
		vector<ll> b;
		vector<ll> v;
		rep(j, n){
			if(a[j] >= a[i]) v.push_back(a[j]);
			else{
				if(v.size() >= k){
					sort(v.begin(), v.end());
					int sz = v.size();
					rep(l, min(q, sz-k+1)) b.push_back(v[l]);
				}
				v.erase(v.begin(), v.end());
			}
		}

		if(v.size() >= k){
			sort(v.begin(), v.end());
			int sz = v.size();
			rep(l, min(q, sz-k+1)) b.push_back(v[l]);
		}

		sort(b.begin(), b.end());
		if(b.size() >= q){
			ans = min(ans, b[q-1] - b[0]);
		} 
	}

	cout << ans << endl;
}

Measured memory_bytes: 384
x = [1,3,5,6,7,8,10,12]
y = [4,6,9,11]
z = [2]
a,b = list(map(int,input().split()))

if ((a in x) and( b in x)) or((a in y) and (b in y)) or ((a in z) and( b in z)):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

int main(){
  int K,X;
  cin>>K>>X;
  cout<<(K*500>=X?"Yes":"No")<<endl;
  return 0;
}


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

using namespace std;

long long a[100005];
long long b[100005];

int main() {

	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	int n;
	cin >> n;
	for (int i = 0; i <= n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> b[i];
	}
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		if (a[i] > b[i]) {
			a[i] -= b[i];
			ans += b[i];
		}
		else {
			if (a[i] + a[i + 1] > b[i]) {
				ans += b[i];
				a[i + 1] = a[i + 1] - (b[i] - a[i]);
			}
			else {
				ans += a[i] + a[i + 1];
				a[i + 1] = 0;
			}
			a[i] = 0;
		}
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 1792
#include<string>
#include<iostream>
using namespace std;
int main(){
	string a;
	cin>>a;
	int num=a.size(),res=0;
	if(num==1){
		cout<<0;
		return 0;
	}
	for(int i=0;i<num-1;i++){
		if(a[i]!=a[i+1]){
			res++;
		}
	}
	cout<<res;
	return 0;
}

Measured memory_bytes: 512
d = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for i in range(d)]

def calc_score(day, contest, score, last):
  t_last = last[:]
  t_last[contest] = day + 1

  contest_score = s[day][contest]
  score += contest_score

  dis = 0
  for i in range(26):
    dis += c[i] * ((day + 1) - t_last[i])
  score -= dis

  return score


score = 0
last = [0 for i in range(26)]
for day in range(d):
  t_score = 0
  for each_contest in range(26):
    each_t_score = calc_score(day, each_contest, score, last)
    if each_t_score > t_score:
      t_score = each_t_score
      contest = each_contest

  score = t_score
  last[contest] = day + 1

  print(contest + 1)

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

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

	if (R < 1200) {
		cout << "ABC" << endl;
	}
	else if (R < 2800) {
		cout << "ARC" << endl;
	}
	else {
		cout << "AGC" << endl;
	}
}






Measured memory_bytes: 3572
returnst ::Int -> Int -> String
returnst x y
  | y==0 = ""
  | y>=0 = show x ++ returnst x (y-1)
main = do
 [a,b] <- map read . words <$> getLine
 if returnst a b > returnst b a then print $ (read $ returnst b a ::Int) else print $ (read $ returnst a b ::Int)

Measured memory_bytes: 508
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
#define FOR(i, a, b)    for(int i = a; i <= b; i++)
#define REP(i, a, b)    for(int i = a; i >= b; i--)
#define maxN       200005
#define inf        (int) 1e9
#define mode       (int) 1000000007
#define ll         long long

using namespace std;

int n, m, cl[maxN];
vector <int> Adj[maxN];

void dfs(int u) {
    cl[u] = 1;
    for(auto &v : Adj[u]) {
        if(cl[v] == 0) {
            dfs(v);
        }
    }
}

void solve() {
    cin >> n >> m;
    FOR(i, 1, m) {
        int u, v;
        cin >> u >> v;
        Adj[u].push_back(v);
        Adj[v].push_back(u);
    }
    int counter = 0;
    FOR(i, 1, n)
        if(cl[i] == 0) dfs(i), counter++;
    cout << counter - 1;
}

int main() {
    //freopen("main.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}


Measured memory_bytes: 12340
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline  #危険！基本オフにしろ！

def BELLMANFORD(point,d,n):
    cost       = {node:-float("inf")for node in range(1,n+1)}
    preference = {node:None         for node in range(1,n+1)}      #最適路のこと 
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
 
    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定
        for now,lis in d.copy().items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
                    negative[now-1]=1
 
    return cost,negative


def main():
    n,m=map(int,input().split())
    d=defaultdict(list)
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append([b,c])
    x,y=(BELLMANFORD(1,d,n))
    if y[n-1]>0:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()


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

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

        long long n,cnt;
	cin >> n; cnt = 0;
	unordered_set<string> a;

	for (int i=0; i<n; ++i) {
		string s; cin >> s;
		if (a.find(s) == a.end()) {
			a.insert(s);
			cnt++;
		}
	}
	cout << cnt << endl;
}


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

int digitsum(int n) {
    int x = 0;

    while(1) {
        if(n == 0) {
            break;
        }
        x += n % 10;
        n /= 10;
    }

    return x;
}

int main() {
    int N;
    cin >> N;
    int m = N/2;
    int t;
    int ans = 10000;
    for(int A = 1; A <= m; A++) {
        int B = N-A;
        t = digitsum(A) + digitsum(B);
        if(t < ans) {
            ans = t;
        }
    }
    
    cout << ans;
    
    cout << endl;
    return 0;
}

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

#define REP(i,n) for(int i = 0; i < (n); ++i)
#define REP1(i,n) for(int i = 1; i <= (n); ++i)
#define RREP(i, n) for(int i = (n) - 1; i >= 0; --i)
#define ALL(a) begin(a), end(a)
#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))
#define X first
#define Y second

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;

constexpr int MOD = int(1e9 + 7);
constexpr int INF = int(1e9 + 1);
constexpr ll LLINF = ll(4 * 1e18 + 1);
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(10);
	int n;
	cin >> n;
	int ans = 0;
	REP1(i, n){
		int yakusuu = 1;
		int tmp = i;
		for(int j = 2; j <= tmp; ++j){
			int cnt = 0;
			while(!(tmp % j))tmp /= j, cnt++;
			yakusuu *= cnt + 1;
		}
		if(yakusuu == 8 && (i % 2))ans++;
	}
	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 2000000
#define INFTY (1<<30)

int H,A[MAX+1];

void maxHeapify(int i){
  int l,r,largest;
  l = 2 * i;
  r = 2 * i + 1;

  if((l <=H) && (A[l] > A[i])) largest = l;
  else largest = i;
  if((r <= H) && (A[r] > A[largest])) largest = r;

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

int extract(){
  int maxv;
  if(H<1) return -INFTY;
  maxv = A[1];
  A[1] = A[H--];
  maxHeapify(1);
  return maxv;
}

void increaseKey(int i, int key){
  if(key < A[i]) return ;
  A[i] = key;
  while(i>1 && A[i/2] < A[i]){
    swap(A[i],A[i/2]);
    i = i / 2;
  }
}

void insert(int key){
  H++;
  A[H] = -INFTY;
  increaseKey(H,key);
}

int main(){
  int key;
  char com[10];

  while(1){
    scanf("%s",com);
    if(com[0] == 'e' && com[1] == 'n') break;
    if(com[0] == 'i'){
      scanf("%d",&key);
      insert(key);
    }else{
      printf("%d\n",extract());
    }
  }

  return 0;
}



Measured memory_bytes: 6580
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int H, W, n, stx, sty;
char S[N], T[N];
int main()
{
	scanf("%d%d%d%d%d%s%s", &H, &W, &n, &stx, &sty, S, T);
	int nw = sty;
	for (int i = 0; i < n; i++)
	{
		if (S[i] == 'L') nw --;
		if (nw <= 0) return !printf("NO\n");
		if (T[i] == 'R' && nw < W) nw ++;
	}
	nw = sty;
	for (int i = 0; i < n; i++)
	{
		if (S[i] == 'R') nw ++;
		if (nw > W) return !printf("NO\n");
		if (T[i] == 'L' && nw > 1) nw --;
	}
	nw = stx;
	for (int i = 0; i < n; i++)
	{
		if (S[i] == 'U') nw --;
		if (nw <= 0) return !printf("NO\n");
		if (T[i] == 'D' && nw < H) nw ++;
	}
	nw = stx;
	for (int i = 0; i < n; i++)
	{
		if (S[i] == 'D') nw ++;
		if (nw > H) return !printf("NO\n");
		if (T[i] == 'U' && nw > 1) nw --;
	}
	printf("YES\n");
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(ll i=(begin);i>(end);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(),greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=(" <<; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << ")" << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
#define f first
#define s second
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
ll mod = 1000000007;


int main()
{
	// 入力
	ll A, B, K;
	cin >> A >> B >> K;
	ll numdiv = 0;
	ll fact = min(A, B);
	while (numdiv <= K) {
		if (A % fact == 0 && B % fact == 0) numdiv++;
		if (numdiv == K) {
			cout << fact << endl;
			return 0;
		}
		fact--;

	}

	return 0;
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()
ma = max(A)
p = list(range(ma+1))
for x in range(2, int(ma ** 0.5) + 1):
    if p[x] == x:
        for i in range(x + x, ma+1, x):
            p[i] = x

s = [set() for _ in range(N)]
t = set()

for i, x in enumerate(A):
    while x != 1:
        s[i].add(x)
        t.add(x)
        x //= p[x]
l = sum(len(x) for x in s)
print("pairwise coprime" if l == len(t) else "setwise coprime")


Measured memory_bytes: 434156
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll a, b, x;
	cin >> a >> b >> x;
	ll ans = b / x - a / x;
	if (a % x == 0) ans++;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3648
#include <iostream>

using namespace std;
typedef long long LL;

int main() {
    LL N, A, B, ans = 0;
    cin >> N >> A >> B;
    if (A > B) {
        swap(A, B);
    }
    if ((B - A) % 2 == 0) {
        cout << (B - A) / 2 << endl;
    } else {
        ans = min(A - 1, N - B) + 1 + (B - A - 1) / 2;
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 504
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <map>
#include<unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include<bitset>
#include<deque>
#include<string>
#include<list>
#include<iterator>
#include<sstream>
#include <algorithm>
#include <numeric>
#include <math.h>

#define user spaesk
#define lli long long int
#define ld long double
#define ff first
#define ss second
#define lower(a) transform(a.begin(),a.end(),a.begin(),::tolower);

using namespace std;

const int N = 3e5 + 500;
const long long mod = 1e9 + 7;
const long long cmod = 998244353 ;
const long long inf = 1LL << 61;
const int M = 1e6 + 500;
const lli ths = 1LL << 40;
const int NN = 5e3 + 6;

void solve()
{

    lli a, b;
    cin>>a>>b;
    if(b >= a ) {
        cout<<"unsafe";
    }
    else {
        cout<<"safe";
    }
    cout<<"\n";
    return ;
}

/*
*/

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

    int t = 1;
//    cin>>t;
    while(t --)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  int tmp;
  for (int i = 0; i < N ;i++){
    cin >> tmp;
    a.at(i) = tmp;
  }
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  int diff = 0;
  for (int i = 0; i < N ;i++){
    if (i %2 == 0){
      diff += a.at(i);
    }
    else
    {
      diff -= a.at(i);
    }
  }
  cout << diff << endl; 
  }

Measured memory_bytes: 3584