akhauriyash/Code-Regression huggingface dataset:
import sys
readline = sys.stdin.buffer.readline


def main():
    a, b, k = map(int, readline().split())
    if k >= a + b:
        print(0, 0)
    elif k >= a:
        print(0, a + b - k)
    else:
        print(a - k, b)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include<stdio.h>
#define MAX 500

static const int INFTY = (1<<21);

main(){
  int n,i,j,k,c,sum,u,v,minv;
  int A[MAX][MAX];
  int B[MAX],C[MAX],D[MAX];

  scanf("%d",&n);
  for ( i=0 ; i<n ; i++ ){
    for ( j=0 ; j<n ; j++ )
      A[i][j] = INFTY;
  }

  for ( i=0 ; i<n ; i++ ){
    scanf("%d %d",&u,&k);
    for ( j=0 ; j<k ; j++ ){
      scanf("%d %d",&v,&c);
      A[u][v] = c;
    }
  }

  for ( i=0 ; i<n ; i++ ) {
    B[i] = INFTY;
    D[i] = 0;
  }

  B[0] = 0;

  while(1){
    minv = INFTY;
    u = -1;
    for ( i=0 ; i<n ; i++ ){
      if ( minv > B[i] && !D[i] ){
	u = i;
	minv = B[i];
      }
    }
    if ( u == -1 ) break;
    D[u] = 1;
    for ( v=0 ; v<n ; v++ ){
      if ( !D[v] && A[u][v] != INFTY ){
	if ( B[v] > B[u] + A[u][v] ){
	  B[v] = B[u] + A[u][v];
	}
      }
    }
  }

  for ( i=0 ; i<n ; i++ ){
    printf("%d %d\n", i, (B[i]==INFTY?-1:B[i]));
  }

  return 0;
}



Measured memory_bytes: 2032
#include<stdio.h>
int main()
{
  int i,n,a[1000];
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&a[i]);
  }
  for(i=n;i>=1;i--){
    printf("%d",a[i]);
    if(i==1){
      printf("\n");
    }
    else{
        printf(" ");
      }
  }
    return 0;
}



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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(a,b) for(int a=0;a<(b);++a)
#define REP1(i,n) for(int i=1;i<=(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define INF (1<<29)
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;

ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

bool compare_by_a(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
    }else{
        return a.second < b.second;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int H=in();
    int W=in();
    int n[H][W];
    
    queue<vector<int>> que;
    REP(i,H){
        string s=in<string>();
        REP(j,W){
            if(s[j]=='#'){
                n[i][j]=0;
                vector<int>v;v.pb(i);v.pb(j);
                que.push(v);
            }else{
                n[i][j]=-1;
            }
        }
    }
    int ans;ans=0;
    while(!que.empty()){
        int h,w;
        vector<int>  _v;
        _v=que.front();
        h=_v[0];
        w=_v[1];
        que.pop();
        int now;
        now=n[h][w];
        ans=max(ans,now);
        if((w<W-1)&&(n[h][w+1]==-1)){
            n[h][w+1]=now+1;
            _v[0]=h;
            _v[1]=w+1;
            que.push(_v);
        }
        if((w-1>=0)&&(n[h][w-1]==-1)){
            n[h][w-1]=now+1;
            _v[0]=h;
            _v[1]=w-1;
            que.push(_v);
        }
        if((h+1<H)&&(n[h+1][w]==-1)){
            n[h+1][w]=now+1;
            _v[0]=h+1;
            _v[1]=w;
            que.push(_v);
        }
        if((h>0)&&(n[h-1][w]==-1)){
            n[h-1][w]=now+1;
            _v[0]=h-1;
            _v[1]=w;
            que.push(_v);
        }
    }
    print(ans);
    return 0;
}

Measured memory_bytes: 59572
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <list>
#include <stack>
#include <math.h>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

#define ll long long
#define ull unsigned long long

#define	max	1000000007

ll gcd(ll a, ll b) {
	if (a < b)
		swap(a, b);
	while (ll r = a % b)
		a = b, b = r;
	return b;
}

class mod
{
public:
	ll val;

	mod(ll v)
	{
		val = v % max;
	}

	mod()
	{
		val = 0;
	}

	void operator -=(const mod &v)
	{
		val -= v.val;

		if (val < 0)
			val += max;
	}

	void operator +=(const mod &v)
	{
		if (val + v.val >= max)
			val -= max;
		val += v.val;
	}

	void operator +=(ll &v)
	{
		if (val + v >= max)
			val -= max;
		val += v;
	}

	void operator *=(const mod &v)
	{
		val *= v.val;
		val %= max;
	}

	void operator *=(ll &v)
	{
		val *= v;
		val %= max;
	}

	ll modinv(ll a)
	{
		ll b = max, u = 1, v = 0;
		while (b)
		{
			ll t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		u %= max;
		if (u < 0)
			u += max;
		return u;
	}

	void operator /=(const mod &v)
	{
		val *= modinv(v.val);
		val %= max;
	}

	void operator /=(ll &v)
	{
		val *= modinv(v);
		val %= max;
	}
};

//	for priority queue
//	priority_queue<ipair, vector<ipair>, greater<ipair>>
using ipair = pair<int, pair<int, int>>;
bool operator>(const ipair a, const ipair b) { return a.first > b.first; };
bool operator<(const ipair a, const ipair b) { return a.first < b.first; };

int main()
{
	int x, n;
	cin >> x >> n;
	vector<int> p(n);
	for (int i = 0; i < n; i++)
		cin >> p[i];
	sort(p.begin(), p.end());

	int r = 0;
	int k = 0;
	for (int i = 1; i <= 101; i++)
	{
		while (k < n && p[k] < i)
			k++;
		bool ok = false;
		if (k >= n || p[k] != i)
			ok = true;
		if (ok && abs(i - x) < abs(r - x))
			r = i;
	}

	printf("%d", r);

	return 0;
}


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

long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

long long lcm(long a, long b) { return a * b / gcd(a, b); }

int main() {
  long long a, b, c, d, r, tmp, ans = 0;

  cin >> a >> b >> c >> d;

  if (c < d) {
    tmp = c;
    c = d;
    d = tmp;
  }

  r = lcm(c, d);

  a--;

  ans += b - b / c;
  ans -= a - a / c;
  ans += b - b / d;
  ans -= b - a / d;
  ans -= b - b / r;
  ans += b - a / r;

  cout << ans;

  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int compare_int(const void *a, const void *b)
{
  return *(int *)a - *(int *)b;
}

int main(void)
{
  int i, j;
  int ii[200000];
  int ilen[100];
  int min, max=0;
  int K, N;
  int cnt, maxcnt;


  scanf("%d %d\n", &K,&N);
//  printf("k %d  n %d\n",K,N);
  for (i = 0; i < N; i++){
    scanf("%d\n", &ii[i]);
  }
	max =ii[0]-0 + K - ii[N-1];
//    printf("max %d\n",max);

  for (i = 0; i < N-1; i++){
    if(ii[i+1]-ii[i] > max){
      max = ii[i+1]-ii[i];
    }
//    printf("i %d  ii %d max %d\n",i,ii[i],max);
  }
    printf("%d\n",K-max);

  return 0;
}


Measured memory_bytes: 896
a, b, c, x, y = gets.split.map(&:to_i)

if a + b < 2 * c
  puts a * x + b * y
elsif x > y
  puts 2 * c * y + [a, 2 * c].min * (x - y)
else
  puts 2 * c * x + [b, 2 * c].min * (y - x)
end

Measured memory_bytes: 3836
import numpy as np

N = int(input())
childs = np.array([int(input()) for _ in range(N)])
max_num = 0
discount_index = 0

for x in range(len(childs)):
    if max_num < childs[x]:
        max_num = childs[x]
        discount_index = x

childs[discount_index] = int(childs[discount_index]/2)


print(childs.sum())

Measured memory_bytes: 18264
#include<bits/stdc++.h>
using namespace std;
int main(){
    map<string,int>Map;
    int N;
    cin >> N;
    vector<string>s(N);
    for(int i = 0; i < N; i++) {
        cin >> s[i];
        Map[s[i]]++;
    }
    int M;
    cin >> M;
    vector<string>t(M);
    int ans = 0;
    int cnt = 0;
    for(int i = 0; i < M; i++) {
        cin >> t[i];
        Map[t[i]]--;
    }
    for(int i = 0; i < N; i++) {
        if(Map[s[i]] > cnt) {
            cnt = Map[s[i]];
            ans = max(ans,cnt);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int x,y,r;
  int temp;
  scanf("%d %d",&x,&y);
  
  if(x < y){
    temp = x;
    x = y;
    y = temp;
  }
  while(y > 0){
    r = x % y;
    x = y;
    y = r;
  }
  printf("%d\n",x);
  return 0;
}


Measured memory_bytes: 2080
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vii vector<vi>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;

int main(){
	 //cin.tie(0);
	//ios::sync_with_stdio(false);
	//std::cout << std::fixed;
	//std::cout << std::setprecision(12);
	//std::cout << std::defaultfloat;
	int n;
	cin>>n;
	vector<pii> v(n);
	vector<int> ans(n,0);
	map<int,int> mp;
	FOR(i,0,n){
		int vv;
		cin>>vv;
		v[i]=MP(vv,i);
	}
	sort(v.begin(),v.end());
	FOR(i,0,2){
		int v2=v[n-1-i].ST;
		int idx=v[n-1-i].ND;
		FOR(i,0,n){
			if(idx!=i)ans[i]=max(ans[i],v2);
		}
	}
	FOR(i,0,n){
		cout<<ans[i]<<endl;
	}




	return 0;
}


Measured memory_bytes: 3968
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1e5+5;
const long long inf=9223372036854775807;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
   	long long n;
   	cin>>n;
   	long long a1=inf,b1=inf,a2=-inf,b2=-inf,ans;
   	for(long long i=1;i<=n;i++)
   	{
   		long long x,y;
   		cin>>x>>y;
   		a1=min(a1,x+y),a2=max(a2,x+y);
   		b1=min(b1,x-y),b2=max(b2,x-y);
	}
	ans=max(a2-a1,b2-b1);
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3640
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include <climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define INF 1e9+7
#define LLINF 1e18
using namespace std;
const int MOD = 1e9 +7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    int n=stoi(s);
    bool can1=0,can2=0;
    if(n/100>=1 && n/100<=12) can1=1;
    if(n%100>=1 && n%100<=12) can2=1;
    if(can1 && can2) cout<<"AMBIGUOUS"<<endl;
    else if(can1) cout<<"MMYY"<<endl;
    else if(can2) cout<<"YYMM"<<endl;
    else cout<<"NA" <<endl; 
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

#define FOR(i,a,b) for(int i=(a); i<int(b); ++i)
#define RFOR(i,a,b) for(int i=(b)-1; i>=int(a); --i)
#define rep(i,n) FOR(i,0,n)
#define rep1(i,n) FOR(i,1,int(n)+1)
#define rrep(i, n) RFOR(i, 0, n)
#define rrep1(i, n) RFOR(i, 1, int(n) + 1)
#define all(c) begin(c), end(c)
#define al(d) d.begin(),d.end()

template <typename T>
void putv(vector<T>& V){
	// cout << "The elements in the vector are: " << endl;
	for(auto x: V)
		cout << x << " ";
	cout << endl;
}
template <class T>
vector<T> getv(int n){
	vector<T> vec;
	rep(i,n){
		T input;
		cin >> input;
		vec.emplace_back(input);
	}
	return vec;
}

int main(){
	int N;
	cin >> N;
	vector<int> a = getv<int>(N);
// putv(a);
	for(int i=0; i<N; ++i){
		a[i] /= 400;
		if(a[i]>8)
			a[i] = 8;
	}

	int cntr = 0;
	for(auto x:a)
		if(x>7)
			cntr++;
// cout << cntr << endl; 

// putv(a);
	sort(a.begin(),a.end());
	a.erase(unique(a.begin(), a.end()), a.end());
// putv(a);

	int num = a.size();
	// if(num == 1)
	// 	if(cntr)
	// 		cout << "1 1" <<endl;
	if(cntr>0)
		if(num > 1)
			cout << a.size()-1 << ' ' << a.size()-1+cntr <<endl;
		else
			cout << a.size() << ' ' << a.size()-1+cntr <<endl;
	else
		cout << a.size() << ' ' << a.size() <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
//constexpr ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
constexpr ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)

class mll
{
public:
  ll x;
  constexpr mll(ll x = 0) : x((x % MOD + MOD) % MOD) {}
  constexpr mll operator-() const
  {
    return mll(-x);
  }
  constexpr mll& operator+=(const mll& a)
  {
    x += a.x;
    if (x >= MOD)
      x -= MOD;
    return *this;
  }
  constexpr mll& operator-=(const mll& a)
  {
    x += MOD - a.x;
    if (x >= MOD)
      x -= MOD;
    return *this;
  }
  constexpr mll& operator*=(const mll& a)
  {
    x *= a.x;
    x %= MOD;
    return *this;
  }
  constexpr mll operator+(const mll& a) const
  {
    mll ret(*this);
    ret += a;
    return ret;
  }
  constexpr mll operator-(const mll& a) const
  {
    mll ret(*this);
    ret -= a;
    return ret;
  }
  constexpr mll operator*(const mll& a) const
  {
    mll ret(*this);
    ret *= a;
    return ret;
  }
  constexpr mll pow(ll t) const
  {
    mll ret = 1;
    mll a = *this;
    while (t > 0)
    {
      if (t % 2 == 1)
        ret *= a;
      
      a *= a;
      t /= 2;
    }
    return ret;
  }
  constexpr mll inv() const
  {
    return pow(MOD - 2);
  }
  constexpr mll& operator/=(const mll& a)
  {
    return (*this) *= a.inv();
  }
  constexpr mll operator/(const mll& a) const
  {
    mll ret(*this);
    ret /= a;
    return ret;
  }
};
ostream& operator<<(ostream& os, const mll& m)
{
  os << m.x;
  return os;
}

int main()
{
  ll N, S;
  cin >> N >> S;
  vector<ll> A(N);
  for (ll i = 0; i < N; i++)
  {
    cin >> A.at(i);
  }

  vector<vector<vector<mll>>> dp(N + 1, vector<vector<mll>>(S + 1, vector<mll>(3, 0)));
  dp.at(0).at(0).at(0) = 1;
  for (ll i = 0; i < N; i++)
  {
    ll a = A.at(i);
    for (ll j = 0; j <= S; j++)
    {
      dp.at(i + 1).at(j).at(0) += dp.at(i).at(j).at(0);
      dp.at(i + 1).at(j).at(1) += dp.at(i).at(j).at(0);
      dp.at(i + 1).at(j).at(1) += dp.at(i).at(j).at(1);
      if (j == S)
        dp.at(i + 1).at(j).at(2) += dp.at(i).at(j).at(1);
      dp.at(i + 1).at(j).at(2) += dp.at(i).at(j).at(2);

      if (j + a > S)
        continue;

      dp.at(i + 1).at(j + a).at(1) += dp.at(i).at(j).at(0);
      dp.at(i + 1).at(j + a).at(1) += dp.at(i).at(j).at(1);
      if (j + a == S)
      {
        dp.at(i + 1).at(j + a).at(2) += dp.at(i).at(j).at(1);
        dp.at(i + 1).at(j + a).at(2) += dp.at(i).at(j).at(0);
      }
    }
  }
  cout << dp.at(N).at(S).at(2) << endl;
  
  /*
  for (ll i = 0; i <= N; i++)
  {
    for (ll j = 0; j <= S; j++)
    {
      cerr << "(";
      for (ll k = 0; k < 3; k++)
      {
        cerr << dp.at(i).at(j).at(k) << ((k == 2) ? ") " : ", ");
      }
    }
    cerr << endl;
  }
  //*/
}

Measured memory_bytes: 493056
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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() {
  string s;
  cin >> s;
  int ans = 0;
  rep (i, s.size()) {
    if (s[i] == '1') ans++;
  }
  P(ans);
  return 0;
}



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

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define pb emplace_back
#define mp make_pair
#define endl '\n'
#define f first
#define s second

#ifdef SEREZHKA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) { cerr << _s << " = " << _h << "\n"; }

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;
    
    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;
    
    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7ll;
const ll LINF = INF * INF;
const int MAXN = static_cast<int>(1e6) + 17;

int n, k, ans;
int g[MAXN], d[MAXN];
vector<int> G[MAXN];

bool read() {
    if (!(cin >> n >> k))
        return false;

    forn (i, n) {
        cin >> g[i];
        --g[i];
    }

    return true;
}

int dfs(int v) {
    int H = 0;

    for (auto to : G[v])
        H = max(H, dfs(to) + 1);

    if (H == k - 1 && g[v] != 0)
        return ++ans, -1;

    return H;
}

void solve() {
    fill(d + 1, d + n, INF);

    if (g[0] != 0) {
        ans = 1;
        g[0] = 0;
    }

    forn (i, n - 1)
        G[g[i + 1]].pb(i + 1);

    dfs(0);
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    
    while (read())
        solve();
    
    return 0;
}



Measured memory_bytes: 34688
#include <bits/stdc++.h>
#define f first
#define s second
#define fore(i,a,b) for(int i = (a), ThxMK = (b); i < ThxMK; ++i)
#define pb push_back
#define all(s) begin(s), end(s)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(s) int(s.size())
#define ENDL '\n'
using namespace std;
typedef long double ld;
typedef long long lli;
typedef pair<lli,lli> ii;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define deb(x) cout << #x": " << (x) << endl;

const int N = 3e3+5;
const lli INF = 1e18+10;
const lli MOD = 1e9+7;
const ld EPS = 1e-9;

lli SUM(lli a,lli b){
	return (a+b + MOD)%MOD;
}

lli MUL(lli a, lli b){
return (a*b)%MOD;
}


lli lg(lli u){
	lli i = 0;
	while((1LL<<i)<u)i++;
	return i;
}

// ---- コーディングはここから！ ('-')7


int main(){_
	int n; cin>>n;
	map<string,lli>ms;
	lli mx = INF;
	auto ispalindrome=[&](string s){
		int p =sz(s);
		fore(i,0,p/2)if(s[i]!=s[p-i-1])return false;
		return true;
	};
	fore(i,0,n){
		string sa; lli x;
		cin>>sa>>x;
		 if(ms.count(sa))ms[sa]=min(x,ms[sa]);
		 else ms[sa]=x;
	}
	vector<string>s,rev;
	vl v;
	for(auto &[a,b]:ms){
		s.pb(a);
		v.pb(b);
	}
	n = sz(s);
	fore(i,0,n)rev.pb(s[i]);
	fore(i,0,n)reverse(all(rev[i]));
	typedef pair<string,string> ss;
	map<ss,lli>dp;
	priority_queue<pair<lli,ss>,vector<pair<lli,ss>>,greater<pair<lli,ss>>>q;
	fore(i,0,n){
		q.push({v[i],{s[i],""}});
		q.push({v[i],{"",rev[i]}});
		dp[{s[i],""}]=v[i];
		dp[{"",rev[i]}]=v[i];
	}
	while(!q.empty()){
		auto [b,a]=q.top(); q.pop();
		if(dp[a]<b)continue;
		auto &[sl,sr]=a;
		if(sr.empty()){
			int id = -1;
			for(auto &i:rev){
				bool add=1;
				id++;
				int z1 = sz(i), z2=sz(sl);
				fore(j,0,min(z1,z2))if(i[j]!=sl[j])add=0;
				if(!add)continue;
				string aux = "";
				ss help;
				if(z1>=z2){
					fore(j,z2,z1)aux+=i[j];
					help={"",aux};
				}
				else{
					fore(j,z1,z2)aux+=sl[j];
					help={aux,""};
				}
				if(!dp.count(help) or dp[help]>b+v[id])dp[help]=b+v[id], q.push({dp[help],help});
			}
		}
		else{
			int id = -1;
			for(auto &i:s){
				bool add=1;
				id++;
				int z1 = sz(i), z2=sz(sr);
				fore(j,0,min(z1,z2))if(i[j]!=sr[j])add=0;
				if(!add)continue;
				string aux = "";
				ss help;
				if(z1>=z2){
					fore(j,z2,z1)aux+=i[j];
					help={aux,""};
				}
				else{
					fore(j,z1,z2)aux+=sr[j];
					help={"",aux};
				}
				if(!dp.count(help) or dp[help]>b+v[id])dp[help]=b+v[id], q.push({dp[help],help});
			}
		}
	}
	//for(auto [a,b]:dp)cout<<a.f<<"-"<<a.s<<" "<<b<<ENDL;

	for(auto &[a,b]:dp)if((ispalindrome(a.f) and sz(a.f)) or (ispalindrome(a.s) and sz(a.s)))mx =min(mx,b);
	if(dp.count({"",""}))mx = min(mx, dp[{"",""}]);
	cout<<(mx==INF?-1:mx)<<ENDL;

}


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

public class Main {

	private static int pow2(int n) {
		return n*n;
	}
	public static void main(String[] args) {

	Scanner sca = new Scanner(System.in);
	int n = sca.nextInt();
	int[] xi = new int[n];
	for(int i = 0; i < n; i++) {
		xi[i] = sca.nextInt();
	}

	Arrays.sort(xi);
	int start = xi[0];
	int end = xi[n-1];
	int min = 1000000;
	int loop = 0;

	for(int i = start; i <= end; i++) {
		loop = 0;
		for(int j = 0; j < n; j++) {
			loop += pow2(xi[j] - i);
		}
		if(min > loop) {
			min = loop;
		}
	}
	System.out.println(min);

	// 後始末
	sca.close();
	}
}

Measured memory_bytes: 23764
import itertools
import bisect
n, m = list(map(int, input().split()))
al = list(map(int, input().split()))
al.sort()
ub = al[-1]*3
lb = -1
while lb + 1 < ub:
    target = (ub+lb)//2
    tmp = 0
    for a in al:
        sa = target - a
        # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
        i = bisect.bisect_left(al, sa)
        tmp += (n-i)
    if (tmp >= m):
        lb = target
    else:
        ub = target

target = lb
rui_al = [0] + list(itertools.accumulate(al))
ans = 0
tmp = 0
for a in al:
    sa = target - a
    # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
    i = bisect.bisect_left(al, sa)
    tmp += (n-i)
    ans += (rui_al[-1] - rui_al[i])
    ans += a*(n-i)


if tmp > m:
    ans -= (tmp-m)*target
print(ans)


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

int n;
int m2;
std::string s;
std::map<string, int> m;
std::vector<string> v;
int main() {
    m2 = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s;
        m[s]++;
        if (m[s] > m2) {
            m2 = m[s];
        }
    }
    for (auto& t: m) {
        if (t.second == m2) {
            v.push_back(t.first);
        }
    }
    std::sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i] << std::endl;
    }
}

Measured memory_bytes: 26868
#include <iostream>

bool is_prime(int x) {
  if (x < 2)
    return false;
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0)
      return false;
  }
  return true;
}

int main(int argc, char *argv[]) {
  int x;
  std::cin >> x;

  int ans = x;
  while (!is_prime(ans))
    ++ans;

  std::cout << ans << std::endl;
}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include<string>
#include <numeric>
#include<math.h>
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    int a,b,c;
    cin>>a>>b>>c;
    cout<<(a*b)/2<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<vector>
using namespace std;
int main(void){
    int N=0;
    int ans=1;
    int top=0;
    cin >> N;
    vector<int> l(N);
    for(int  i=1; i <= N ; i++){
        cin >> l[i];
    }
    top=l[1];
    for(int i=2; i <= N ; i++){
            if(top<=l[i]){
                top=l[i];
                ans++;
            }
    } 
    cout << ans << endl;
}

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

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef long double ld;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 1000000007;

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

  LL W, H;
  cin >> H >> W;
  vector<string> ss(H);

  vector<string> s(601,"");

  REP(i,H){
    cin >> ss[H-i-1];
  }
  
  REP(i,601){
    REP(j,601){
      if(i<ss.size()&&j<ss[i].size()){
        if(ss[i][j]=='#'){
          s[i] += "#";
        }else{
          s[i] += ".";
        }
      }else{
          s[i] += ".";
      }
    }
  }

  LL max = 0;

  for (ld dy = 0; dy <= 1; dy += 1.0/600.0/50.0){    
    ld y = 0;
    LL xx = 0;
    LL yy = 0;

    LL cnt = s[0][0]=='#'?1:0;
    LL now = s[0][0];
    REP(i, H)
    {
      y += dy;
      if(y>=1){
        y -= 1;
        cnt += s[xx][yy] != s[xx][yy + 1] ? 1 : 0;
        cnt += s[xx][yy + 1] != s[xx + 1][yy + 1] ? 1 : 0;
        yy++;
      }
      else
      {
        cnt += s[xx][yy]!=s[xx+1][yy] ? 1 : 0;
      }
      xx++;
    }
    if(max<cnt){
      max = cnt;
    }
  }

  for (ld dy = 0; dy <= 1; dy += 1.0/600.0/50.0){    
    ld y = 0;
    LL xx = 0;
    LL yy = 0;

    LL cnt = s[0][0]=='#'?1:0;
    LL now = s[0][0];
    REP(i, W)
    {
      y += dy;
      if(y>=1){
        y -= 1;
        cnt += s[yy][xx] != s[yy + 1][xx] ? 1 : 0;
        cnt += s[yy + 1][xx] != s[yy + 1][xx + 1] ? 1 : 0;
        yy++;
      }
      else
      {
        cnt += s[yy][xx]!=s[yy][xx+1] ? 1 : 0;
      }
      xx++;
    }
    if(max<cnt){
      max = cnt;
    }
  }

  cout << max / 2 + 1 << endl;
}



Measured memory_bytes: 4012
#include "bits/stdc++.h"
using namespace std;
const int MM = 100002;
int N, M, in[MM], dp[MM], ans; vector<int> adj[MM]; queue<int> q;
int main(){
    scanf("%d %d", &N, &M);
    for(int i=1, x, y; i<=M; i++){
        scanf("%d %d", &x, &y);
        adj[x].push_back(y); in[y]++;
    }
    for(int i=1; i<=N; i++){
        if(in[i] == 0) { q.push(i); in[i]--; }
    }
    while(!q.empty()){
        int u = q.front(); q.pop(); ans = max(ans, dp[u]);
        for(int v: adj[u]){
            dp[v] = max(dp[v], dp[u]+1); 
            if(--in[v] == 0) q.push(v);
        }
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 6528
/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.08.20 03:41:51
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

int main() {
    int n;cin >> n;
    int k;cin >> k;
    vector<ll> sum(n+1,0),best(n+1,0);
    for (int i = 0; i < n; i++) {
        int a;cin >> a;
        sum[i + 1] = sum[i] + a;
        best[i + 1] = best[i] + max(a,0);
    }
    ll ans = 0;
    //cerr << sum << endl;
    //cerr << best << endl;
    for (int i = 0; i < n-k+1; i++) {
        ans = max(ans,best[i] + best[n] - best[i+k] + max(0LL,sum[i+k] - sum[i]));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4840
#include <stdio.h>

int main(){
  int x=0,y=0;
  while(1){
    scanf("%d %d",&x,&y);
    if(x==0&&y==0) break;
    if(x<y) printf("%d %d\n",x,y);
    else printf("%d %d\n",y,x);
  }
}

Measured memory_bytes: 2564
#include <bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
const long long INF = 1LL << 60;
using pll = pair<long long, long long>;

int main() {
  // 標準入力が早くなる。Cスタイルの入出力とC++スタイルの入出力を混合させてはならない。
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  string N;
  cin >> N;

  char target = N[N.length() - 1];

  if (target == '3') {
    cout << "bon" << endl;
  } else if (target == '0' || target == '1' || target == '6' || target == '8') {
    cout << "pon" << endl;
  } else {
    cout << "hon" << endl;
  }

  return 0;
}


Measured memory_bytes: 3608
#include<stdio.h>
long max1(long a,long b){
  return a>b?a:b;
}
long max(long a,long b,long c){
  return max1(max1(a,b),c);
}
long min1(long a,long b){
  return a<b?a:b;
}
long min(long a,long b,long c){
  return min1(min1(a,b),c);
}
int main(){
  long h,w,s1,s2,s3,s4;
  long x=100000;
  long y=100000;
  scanf("%ld %ld",&h,&w);
  for(long i=1;i<h;i++){
    s1=max(w*i,(w/2)*(h-i),(w-w/2)*(h-i))-min(w*i,(w/2)*(h-i),(w-w/2)*(h-i));
    s2=max(w*i,w*((h-i)/2),w*(h-i-(h-i)/2))-min(w*i,w*((h-i)/2),w*(h-i-(h-i)/2));
    x=min(s1,s2,x);
  }
  for(long i=1;i<w;i++){
    s3=max(h*i,(h/2)*(w-i),(h-h/2)*(w-i))-min(h*i,(h/2)*(w-i),(h-h/2)*(w-i));
    s4=max(h*i,h*((w-i)/2),h*(w-i-(w-i)/2))-min(h*i,h*((w-i)/2),h*(w-i-(w-i)/2));
    y=min(s3,s4,y);
  }
  printf("%ld",min1(x,y));
}

Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
  ll N,X,T;
  cin>>N>>X>>T;
  if(N%X==0) {
cout<<N/X*T<<endl;
  }
  else {
cout<<(N/X+1)*T<<endl;
  }
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i<(int)n; ++i)
#define rfor(i, n) for (int i = n-1; i>=0; --i)
#define rmod(x, y) (((x%y)+y)%y)
#define pb(x) push_back(x)
using namespace std;
typedef vector<int>::iterator vit;
typedef unsigned int uint;
typedef unsigned short ushort;
typedef long long ll;
const int MAXN = 1024;

//OPERATORS


//GLOBALS


//FUNCTIONS


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s; cin >> s;
	bool bn = false;
	for(int i = 0; i < s.size()-1; i++){
		if(s[i+1] != s[i]) bn = true;
	}
	if(bn) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}


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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) (v.begin(),v.end())
#define COUT(x) cout<<(x)<<"\n"



int main(){
    ll x;
    cin >> x;
    ll count = 0;
    ll t = 100;
    for(int i=1;;i++){
        t *= 1.01;
        count++;
        if(t>=x)break;
    }
    COUT(count);
    return 0;
}

Measured memory_bytes: 3632
// #include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)

#define CHMAX(a,b) a=max((a),(b))

int n,m;
int a[5000];
int b[5000][200];
int mx[200];

int main(){
  scanf("%d%d",&n,&m);
  REP(i,n-1)scanf("%d",a+i);
  REP(i,n)REP(j,m)scanf("%d",&b[i][j]);
  // REP(i,n-1)a[i]=1;
  // REP(i,n)REP(j,m)b[i][j]=1;

  ll ans = 0;
  REP(l,n){
    ll lensum = 0;
    REP(j,m)mx[j]=b[l][j];
    ll ysum = 0;
    REP(j,m)ysum+=mx[j];
    CHMAX(ans,ysum-lensum);

    FOR(r,l+1,n){
      lensum += a[r-1];
      REP(j,m)CHMAX(mx[j],b[r][j]);
      ysum = 0;
      REP(j,m)ysum += mx[j];
      CHMAX(ans,ysum-lensum);
    }

  }
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 4352
//dice
#include<stdio.h>
int dice[6];
void swap(int a, int b, int c, int d){
    int temp;

    temp = dice[a];
    dice[a] = dice[b];
    dice[b] = dice[c];
    dice[c] = dice[d];
    dice[d] = temp;
}

int main(void) {
	int n,i,r;
	char s[8];
	while(1){
		scanf("%d",&n);
		if(n==0){
			break;
		}
		r=1;
		dice[0] = 1;
		dice[1] = 2;
		dice[2] = 3;
		dice[3] = 5;
		dice[4] = 4;
		dice[5] = 6;
		for(i=0;i<n;i++){
			scanf("%s",s);
			if(s[0]=='N'){
				swap(0, 1, 5, 3);
			}else if(s[0]=='E'){
				swap(0, 4, 5, 2);
			}else if(s[0]=='W'){
				swap(0, 2, 5, 4);
			}else if(s[0]=='S'){
				swap(0, 3, 5, 1);
			}else if(s[0]=='R'){
				swap(1, 2, 3, 4);
			}else{
				swap(1, 4, 3, 2);
			}
			r+=dice[0];
		}
		printf("%d\n",r);
	}
	return 0;
}

Measured memory_bytes: 2576
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int sum = 0;
		int[] x = new int[n];
		for (int i = 0; i < n; i++) {
			int j = kb.nextInt();
			x[i] = j;
		}

		for (int j = 1; j <= 100; j++) {
			int sum2 = 0;
			for (int i = 0; i < n; i++) {
				sum2 += (int) Math.pow(x[i] - j, 2);
			}
			if (j == 1)
				sum = sum2;
			if (sum > sum2)
				sum = sum2;
		}
		System.out.println(sum);
		kb.close();
	}

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	for (auto& x : A) cin >> x;

	vector<int> b(N);
	if (N % 2 == 0) {
		for (int i = 0; i < N; i += 2) {
			b[N/2 + i/2] = A[i];
		}
		for (int i = 1; i < N; i += 2) {
			b[N/2-1 - i/2] = A[i];
		}
	} else {
		for (int i = 0; i < N; i += 2) {
			b[N/2 - i/2] = A[i];
		}
		for (int i = 1; i < N; i += 2) {
			b[N/2+1 + i/2] = A[i];
		}
	}

	for (int i = 0; i < N; ++ i) {
		if (i) cout << " ";
		cout << b[i];
	}
	cout << endl;
}


Measured memory_bytes: 3840
#include<bits/stdc++.h>
using namespace std;
int n,ans,a[111];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if((i&1)&&(a[i]&1))ans++;
	}
	cout<<ans;
}

Measured memory_bytes: 3596
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>

using namespace std;

const int MAX = 16;
const double per = 1.0/4.0;
char s,t,b;
int n;
int nex[9][9] = {{1,3,0,0},{0,2,4,1},{1,5,2,2},{0,4,6,3},{1,3,5,7},{2,4,8,5},{3,7,6,6},{4,6,8,7},{5,7,8,8}};
double dp[MAX][9];

void init(char c){
  memset(dp,0,sizeof(dp));
  dp[0][c-'A'] = 1.0;
}

vector<int> get(int pos){
  vector<int> V;

  for(int i = 0; i < 4; i++)
    if(nex[pos][i] == b-'A') V.push_back(pos);
    else V.push_back(nex[pos][i]);

  return V;
}

void solve(){
  for(int i = 0; i < n; i++)
    for(int j = 0; j < 9; j++){
      vector<int> V = get(j);
      for(int k = 0; k < V.size(); k++)
	dp[i+1][V[k]] += dp[i][j]*per;
    } 
}

int main(){
  while(cin >> n && n){
    cin >> s >> t >> b;
    init(s);
    solve();
    printf("%.8f\n",dp[n][t-'A']);
  }
  return 0;
}

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

#define N 100010

int main()
{
   long long n,m,h[N],ma[N];
   cin >> n >> m;
   
   for(long long i=1;i<=n;i++)
   {
      cin >> h[i];
	  ma[i]=0;
   }
   
   for(long long i=0;i<m;i++)
   {
      long long a,b;
	  cin >> a >> b;            
	  ma[a]=max(ma[a],h[b]);
	  ma[b]=max(ma[b],h[a]);
   }
   
   long long ans=0;
   for(long long i=1;i<=n;i++)
   {
      ans += h[i]>ma[i];   
   }
   
   cout << ans << endl;
}

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

typedef long long ll;
#define all(x) (x).begin(),(x).end()

int factorial(int n) {
    int t = 1;
    for (int i = 1; i <= n; i++) {
        t *= i;
    }
    return t;
}

double cal_dist(vector<int> pos, vector<int> x, vector<int> y) {
    double dist = 0.0;
    for (int i = 0; i < (int)x.size()-1; i++) {
        dist += sqrt( (x[pos[i]] - x[pos[i+1]]) * (x[pos[i]] - x[pos[i+1]]) + (y[pos[i]] - y[pos[i+1]]) * (y[pos[i]] - y[pos[i+1]]) );
    }
    return dist;
}

void solve(){
    int N;
    cin >> N;

    vector<int> pos;
    for (int i = 0; i < N; i++) {
        pos.push_back(i);
    }

    vector<int> x, y;
    for (int i = 0; i < N; i++) {
        int X, Y;
        cin >> X >> Y;
        x.push_back(X);
        y.push_back(Y);
    }
    int perm = factorial(N);

    double dist = 0.0;
    do {
        dist += cal_dist(pos, x, y);
    } while(next_permutation(all(pos)));

    cout << setprecision(12) << dist / perm << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>){
    // a(1n) b(0b) c(-1n) k(calc)
    var (a, b, c ,k) = nextIntList()
    
    var num = 0
    
    for(i in 1..k){
        if(a > 0){
            num += 1
            a-=1
            continue
        }
        if(b > 0){
            b-=1
            continue
        }
        if(c > 0){
            num -=1
        }
    }
    println(num)



}
fun next() = readLine()!!
fun nextIntList() = next().split(" ").map{ it.toInt() }




Measured memory_bytes: 36500
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Int int32_t
#define all(c) c.begin(), c.end()
#define FAST ios_base::sync_with_stdio(false) , cin.tie(NULL);
#define pii pair< int , int >
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define bitcnt(n) __builtin_popcountll(n)
#define setpre(n) cout << fixed << setprecision(n)
#define tr(c) for(auto x : c )cout << x << " ";
#define ol(c , s , e ) for(int pos=s; pos<e ; pos++) cout << c[pos] << " ";
#define PI acos(-1l)
const int M = 1000000007;
const int N=3e5+5;
const int INF = 2e18+5;
//#define rohit
#ifdef rohit
template<typename... T >
void bug(T... __VA_ARGS__) {
    ((cerr << __VA_ARGS__ << " ") , ...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", bug(__VA_ARGS__) , cerr << endl;
#endif

void solve(){
    int n;
    cin >>n;
    int a[n] , mx = 0;
    map< int , int >mp;
    map<int , bool> used;
    for(int i=0; i<n ;i++){
        cin >> a[i];
        mx = max(a[i] , mx);
        mp[a[i]]++;
        used[a[i]] = true;
    }
    if(mp.count(1)){
        if(mp[1]==1){
            cout << 1;
        }
        else{
            cout << 0;
        }
        return;
    }
    for(auto x : mp){
        if(x.second > 1) used[x.first] = false;
        for(int i = x.first ; i<=mx ; i+=x.first){
            if(i!=x.first && mp.count(i)){
                used[i] = false;
            }
        }
    }
    int ans =0;
    for(auto x: mp){
        if(used[x.first])
            ans++;
    }
    cout<< ans ;

}


signed main(){
    FAST;
    //TODO: check test cases.
    int tc=1;
//    cin >> tc;
    for(int t = 1 ; t <= tc ; t++){
        solve();
    }
}
/* Extra Cares
 * 1)In graphs or dp problems sometimes long long creates MLE.
 * 2)Check whether int to long long typecasting is commented or not?
 * 3)Check overflows.
*/

Measured memory_bytes: 30068
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    """
    順列を全部試す。計算量O(N!)
    """
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    res = 0
    for pattern in permutations(range(n)):
        if pattern[0] == 0:
            for i in range(n - 1):
                if pattern[i + 1] not in tree[pattern[i]]:
                    break
            else:
                res += 1
    print(res)


def resolve2():
    """
    bit DP。計算量O(2^N*N^2)
    """
    n, m = map(int, input().split())
    edge = [[f_inf] * n for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        edge[a - 1][b - 1] = 1
        edge[b - 1][a - 1] = 1

    dp = [[f_inf] * n for _ in range(1 << n)]
    dp[0][0] = 0
    cnt = [[0] * n for _ in range(1 << n)]
    cnt[0][0] = 1
    for S in range(1 << n):
        for v in range(n):
            for u in range(n):
                if v == u or S & (1 << v) or edge[u][v] == f_inf:
                    continue
                if dp[S | (1 << v)][v] > dp[S][u] + edge[u][v]:
                    dp[S | (1 << v)][v] = dp[S][u] + edge[u][v]
                    cnt[S | (1 << v)][v] = cnt[S][u]
                elif dp[S | (1 << v)][v] == dp[S][u] + edge[u][v]:
                    cnt[S | (1 << v)][v] += cnt[S][u]

    mi = min(dp[-2])
    idx = []
    for i in range(n):
        if dp[-2][i] == mi:
            idx.append(i)

    res = 0
    for j in idx:
        res += cnt[-2][j]
    print(res)


if __name__ == '__main__':
    resolve2()


Measured memory_bytes: 9348
program main
  implicit none
  integer :: n, i, s1, s2, res
  integer, allocatable :: w(:)
  read (*, *) n
  allocate (w(n))
  read (*, *) w(:)
  res = 99999999
  do i = 1, n - 1
    s1 = sum(w(1:i))
    s2 = sum(w(i + 1:n))
    res = min(res, abs(s1 - s2))
  end do
  write (*, "(i0)") res
end program main


Measured memory_bytes: 256
//run: g++ -std=c++14 -o run_sol.exe solution.cpp -DLOCAL_JUDGE
#include<bits/stdc++.h>
#define INF 0x7fffffff
#define INFLL 1e17
#define PI 2*acos(0.0)
#define show(x) cout<< #x <<" is "<< x <<"\n"
using namespace std;

#define FS first
#define SC second
#define PB(t) push_back(t)
#define LEN(t) ((int)t.size())
#define ALL(t) t.begin(),t.end()
#define MP(x, y) make_pair((x), (y))
#define Fill(a,c) memset(&a, c, sizeof(a))
#define POPCOUNT __builtin_popcount

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;

int main() {
    #ifdef LOCAL_JUDGE
        freopen("input.txt", "rt", stdin);
        freopen("output.txt", "wt", stdout);
    #endif

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

    for (int n, m; cin >> n >> m; ) {
        if (n == m) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

return 0;
}

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

int main() {
  vector<bool>data(100001,true);
  vector<int>sum(100001);
  for(int i = 2;i < 100001;i++){
    if(data[i]){
      for(int j = 2*i;j <= 100000;j += i){
        data[j] = false;
      }
    }
  }
  data[0] = false;data[1] = false;
  for(int i = 1;i < 100001;i++){
    int k = (i+1)/2;
    sum[i] = sum[i-1];
    if(data[i] && data[k]) sum[i]++;
  }
  int n;
  cin >> n;
  for(int i = 0;i < n;i++){
    int r,l;
    cin >> l >> r;
    cout << sum[r]-sum[l-1] << endl;
  }
}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
bool flag[200001];
int main()
{
	memset(flag,0,sizeof(flag));
	string c;
	cin>>c;
	int size=c.size();
	for(int i=0;i<size;i++)
	{
		if(!flag[i]&&c[i]=='S')
		{
			for(int j=i+1;j<size;j++)
			{
				if(!flag[j]&&c[j]!='T')
				{
					break;
				}
				else if(!flag[j]&&c[i]=='S'&&c[j]=='T')
				{
					flag[i]=1;flag[j]=1;
					for(int n=1,m=1;n<=i&&j+m<size;)
					{
						while(n<=i&&flag[i-n])
							if(flag[i-n])n++;
						while(j+m<size&&flag[j+m])
							if(flag[j+m])m++;
						if(!flag[i-n]&&!flag[j+m]&&c[i-n]=='S'&&c[j+m]=='T')
						{
							flag[i-n]=1;flag[j+m]=1;
						}
						else
						{
							break;
						}
					}
					break;
				}
			}
		}
	}
	int count=0;
	for(int i=0;i<size;i++)
	{
		
		if(!flag[i]){
			count++;
		}
	}
	cout<<count<<endl;
}


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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

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

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

int n, l;
vector<string> s;

int grundy[1111];
int calc_grundy(int x) {
  int& g = grundy[x];
  if(~g) return g;
  if(x == 0) return g = 0;
  set<int> st;
  st.insert(0);
  int tmp = 0;
  reps(i, 1, x) {
    tmp ^= calc_grundy(x-i);
    st.insert(tmp);
  }
  g = 0;
  while(st.count(g)) ++g;
  return g;
}

struct Trie {
  bool term;
  Trie *nxt[2];
  Trie() {
    term = false;
    nxt[0] = nxt[1] = nullptr;
  }
  void insert(const string& s) {
    Trie *t = this;
    for(int i = 0; i < (int)s.size(); ++i) {
      int v = s[i]-'0';
      if(t->nxt[v] == nullptr) t->nxt[v] = new Trie;
      t = t->nxt[v];
    }
    t->term = true;
  }
};

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  if(0) {
    int l = 1000;
    memset(grundy, -1, sizeof(grundy));
    calc_grundy(l);
    rep(i, l+1) cout << grundy[i] << endl;
  }

  cin >> n >> l;
  resz(s, n);
  rep(i, n) cin >> s[i];

  Trie root;
  rep(i, n) root.insert(s[i]);

  vint h;
  function<void(Trie*, int)> dfs = [&](Trie* t, int d) {
    if(t == nullptr) return;
    int cnt = 0;
    if(t->nxt[0]) dfs(t->nxt[0], d+1), ++cnt;
    if(t->nxt[1]) dfs(t->nxt[1], d+1), ++cnt;
    if(cnt == 1) h.push_back(l-d);
  };
  dfs(&root, 0);
  int ans = 0;
  rep(i, h.size()) {
    int g = 1;
    while(h[i]%(g<<1) == 0) g <<= 1;
    //cout<<h[i]<<" "<<g<<" "<<grundy[h[i]]<<endl;
    ans ^= g;
  }
  cout << (ans ? "Alice" : "Bob") << endl;

  return 0;
}


Measured memory_bytes: 14024
from collections import Counter
N,M = map(int,input().split())
A = list(map(int,input().split()))

ctr = Counter()
ctr[0] = 1

cum = 0
for a in A:
    cum = (cum + a) % M
    ctr[cum] += 1

ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)

Measured memory_bytes: 14920
N, K = map(int, input().split())
L = []
R = []
for i in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
mod = 998244353

dp = [0] * (N + 1)
dpsum = [0] * (N + 1)
"""
dp[i] : iまでの個数
dpsum[i] : iまでのdpの累積和
"""
dp[1] = 1
dpsum[1] = 1
for i in range(2, N + 1):
    for k in range(K):
        r = i - L[k]
        l = i - R[k]
        if r < 0:
            continue
        l = max(1, l)
        dp[i] += (dpsum[r] - dpsum[l - 1]) % mod
    dpsum[i] = (dpsum[i - 1] + dp[i]) % mod

print(dp[N] % mod)



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

int main()
{

	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	long long int a,b,c,k;
	cin>>a>>b>>c>>k;
	long long int ans=0;
	int t=0;
	if(k>=a) {ans=ans+a; k=k-a;}
	else {ans=ans+k;k=0;}

	if(k>=b)k=k-b;
	else k=0;

	if(k>=c){ans=ans-c; k=k-c;}
	else {ans=ans-k;k=0;}

	cout<<ans<<endl;

	return 0;
}

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

int main(){
	long long N, K, counta = 0, countb = 0, f = false, ans = 0;
	
	cin>>N>>K;
	
	if(K%2 == 0) f = true;
	
	for(int i = 1; i <= N; i++){
		if(i%K == 0)counta++;
		else if(f && i%K == K/2)countb++;
	}
	
	cout<<counta*counta*counta+countb*countb*countb<<endl;
	
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main(void){
    int i,l,k;
    int n;
    long long id,c,q;
    long long data_list[4001];
    int id_list[4001];
    bool id_flag;
    bool na_flag;
    
    while(cin>>n,n!=0){
        k=0;
        memset(data_list,0,sizeof(data_list));
        memset(id_list,0,sizeof(id_list));
        for(l=0;l<n;l++){
            cin>>id>>c>>q;
            if(data_list[id]>=1000000)data_list[id]=1000000;
            else{
                data_list[id]+=(c*q);
            }
            id_flag=true;
            for(i=0;i<k+1;i++){
                if(id_list[i]==id){
                    id_flag=false;
                }
            }
            
            if(id_flag){
                id_list[k]=id;
            k++;
            }
        }
        na_flag=true;
        for(l=0;l<k;l++){
            if(data_list[id_list[l]]>=1000000){
                cout<<id_list[l]<<endl;
                na_flag=false;
            }
        }
        if(na_flag){
            cout<<"NA"<<endl;
        }
    }
    return(0);
}

Measured memory_bytes: 1224