akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm> // std::min
#include <vector>
#include <map>
#include <limits>

// AIZU GRL_1_B Single Source Shortest Path (Negative Edges)
// July 24, 2018

using namespace std;

constexpr long long BIG = numeric_limits<long long>::max();  // guarantee: weights in [-10000, 10000]
// dist[u][i] = least distance from u to src of simple path with length at most i
long long n, src;


map<int, vector<int>> in_nbrs;

int main() {

  cin >> n >> src >> src;  // 2nd input: m (not using)

  long long dist[n][2];
  long long adj[n][n];

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 2; ++j) {
      dist[i][j] = BIG;
    }
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      adj[i][j] = BIG;
    }
  }

  dist[src][0] = 0;

  {
    int u, v;
    long long d;
    while (cin >> u >> v >> d) {
      adj[u][v] = d;
      in_nbrs[v].push_back(u);
    }
  }

  // Bellman-Ford algorithm
  // The least distance from `src` to `u` after `i` edges
  // is the minimum of
  // 1) the least distance from `src` to `u` after `i-1` edges
  //    ie dist[(i-1)%2][u]
  // 2) the least distance from `src` to any in-neighbor `v` of `u`
  //    after `i-1` edges, plus the weight of the edge from `v` to `u`
  for (int i = 1; i < n+1; ++i) {
    for (int u = 0; u < n; ++u) {
      long long tmp = dist[u][(i-1)%2];  // candidate: prior distance to `u`
      for (int v : in_nbrs[u]) {
        auto altcost = dist[v][(i-1)%2] + adj[v][u];  // compare: prior dist to `v` + adj[v][u]
        if (dist[v][(i-1)%2] != BIG)
          tmp = min(tmp, altcost);
      }
      dist[u][i%2] = tmp;
    }
  }

  for (int u = 0; u < n; ++u) {
    if (dist[u][n%2] < dist[u][(n-1)%2]) {
      cout << "NEGATIVE CYCLE\n";
      exit(0);
    }
  }

  for (int u = 0; u < n; ++u) {
    if (dist[u][(n-1)%2] == BIG) {
      cout << "INF\n";
    } else {
      cout << dist[u][(n-1)%2] << endl;
    }
  }
}



Measured memory_bytes: 11076
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
H = 0
H += B[A[0] - 1]
for i in range(1, N):
  H += B[A[i] - 1]
  if A[i] == A[i - 1] + 1:
    H += C[A[i - 1] - 1]
print(H)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vec> mat;
int main(){
    int n,m,a,b;
    vec A[200001];
    cin>>n>>m;
    rep(i,m) cin>>a>>b,A[a].push_back(b),A[b].push_back(a);
    deque<int> ans;
    int num[200001]={0};
    ans.push_back(1);
    ans.push_back(A[1][0]);
    num[1]=1;
    num[A[1][0]]=1;
    while(true){
        int z=1,a;
        for(auto i:A[ans.front()]) if(num[i]==0) z=0,a=i;
        if(z==0){
            ans.push_front(a);
            num[a]=1;
            continue;
        }
        for(auto i:A[ans.back()]) if(num[i]==0) z=0,a=i;
        if(z==0){
            ans.push_back(a);
            num[a]=1;
            continue;
        }
        cout<<ans.size()<<"\n";
        for(auto i:ans) cout<<i<<" ";
        break;
    }
}

Measured memory_bytes: 9728
#include <iostream>
#include <stdio.h>
#include <math.h> 
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <string>
#include <numeric>
#include <bitset>
#include <queue>
#include <map>
#include <typeinfo>

using namespace std;

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

	int n = s.size();

	if (n == 1) {
		cout << 0 << endl;
	}
	else {
		vector<int> anslen10;
		vector<int> anslen01;

		//解1(10101....)の生成
		for (int i = 0; i < n; ++i) {
			if (i % 2 == 0) {
				anslen10.push_back(1);
			}
			else {
				anslen10.push_back(0);
			}
		}

		//解2(01010....)の生成
		for (int i = 0; i < n; ++i) {
			if (i % 2 == 0) {
				anslen01.push_back(0);
			}
			else {
				anslen01.push_back(1);
			}
		}

		//解1と入力の差分を確認
		int cnt10 = 0;
		for (int i = 0; i < n; ++i) {
			string tmp = to_string(anslen10[i]);
			const char* cstr = tmp.c_str();
			if (s[i] != *cstr) {
				cnt10++;
			}
		}

		//解2と入力の差分を確認
		int cnt01 = 0;
		for (int i = 0; i < n; ++i) {
			string tmp = to_string(anslen01[i]);
			const char* cstr = tmp.c_str();
			if (s[i] != *cstr) {
				cnt01++;
			}
		}

		cout << min(cnt10, cnt01) << endl;
	}
}

Measured memory_bytes: 1528
n = gets.to_i
a = gets.chomp.split(" ").map(&:to_i)
a = a.sort
INF = (10 ** 6)
arr = Array.new(INF+1,0)
a.each do |i|
    next if arr[i] == 2 
    sa = i
    until i > 10 ** 6 
        arr[i] += 1 
        i += sa
    end
end
count = 0
a.each do |i|
    count += 1 if arr[i] == 1
end
puts count

Measured memory_bytes: 39852
n = int(input())
s = input()
ma = s[1:].count("E")
maa = ma

for i in range(n-1):
  if s[i] == "W" and s[i+1] == "W":
    ma += 1
  elif s[i] == "E" and s[i+1] == "E":
    ma -= 1
    
  maa = min(maa,ma)
  
print(maa)

Measured memory_bytes: 3700
N = int(input())
A = list(map(int, input().split()))
num_l = [0]*N
bn = 0
for i in range(N, 0, -1):
    nn = 0
    for j in range(2*i, N+1, i):
        nn += num_l[j-1]

    if nn % 2 != A[i-1]:
        num_l[i-1] = 1

M = sum(num_l)
print(M)
if M != 0:
    ans = []
    flg = False
    for i, n in enumerate(num_l):
        if flg:
            print(' ', end='')
        if n == 1:
            print(i+1, end='')
        flg = True

Measured memory_bytes: 8120
#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
 
using namespace std;
#define rep(i,a,b) for (ll i = a; i < b; i++)
#define rrep(i,a,b) for (ll i = a; i >= b; i--)
#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
 
using namespace std;
#define rep(i,a,b) for (ll i = a; i < b; i++)
#define rrep(i,a,b) for (ll i = a; i >= b; i--)
#define l(s) s.length()
#define sort(v) sort(v.begin(), v.end());
#define scan(v,n) rep(i,0,n) {ll k; cin >> k; v.pb(k);}
#define print(v,n) {rep(i,0,n) cout << v[i] << " "; cout << endl;}
#define printstr(s,n) {rep(i,0,n) cout << s[i]; cout << endl;}
#define rev(a) reverse(a.begin(), a.end());
#define pb push_back
typedef long long ll;
typedef long double lld;
typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
 
const ll mxN=3e3;
const ll N=1e9+7;
 
ll dp[mxN+1][mxN+1];

//deque
//assume that we start the game with the array from index l to r. 
// then, dp[l][r] is the max possible difference bw the scores of the player who goes first and the one who goes second
//obviously, for a single element array, the diff is the element itself
// we want dp[0][l-1]
// why reverse loop for variable l and forward loop for r though?
// forward loop outputs only the first element of the array (weird...)

  int main() {
      int T=1;// cin >> T;
      while(T--){
          ll n; cin >> n;
          vi v; scan(v,n);
          rep(i,0,n) dp[i][i]=v[i];
          rep(r,0,n) {
              rrep(l,r-1,0) {
                  dp[l][r]=(v[l]-dp[l+1][r]>v[r]-dp[l][r-1]?v[l]-dp[l+1][r]:v[r]-dp[l][r-1]);
              }
          }
          //print(dp,n+1);
          cout << dp[0][n-1];
      } 
	 return 0;
}


Measured memory_bytes: 49800
A = [int(input()) for _ in range(5)]
tmp = 10

for i in range(5):
    if A[i] % 10 != 0:
        tmp = min(tmp, A[i] % 10)
        A[i] = A[i] // 10 * 10 + 10

print(sum(A) - (10 - tmp))

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main(){
	int a, b, c;
	cin>>a>>b>>c;
	if (b > c){
		swap(c,b);
	}
	if (a > c){
		swap(a,c);
	}
	if (a > b){
		swap(a, b);
	}
	cout << a<<" " << b<<" "<< c<<endl;
return 0;
}



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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
int main()
{
  int k,a,b;cin>>k>>a>>b;
  int i;
  bool ok=false;
  for(i=a;i<=b;i++)
  {
    if(i%k==0)ok=true;
  }
  if(ok)cout<<"OK"<<endl;
  else cout<<"NG"<<endl;
}


Measured memory_bytes: 3604
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

newUF n = VUM.replicate n (-1 :: Int)

root uf x = do
    p <- VUM.read uf x
    if p < 0
        then return x
        else do
            r <- root uf p
            VUM.write uf x r
            return r

same uf x y = liftM2 (==) (root uf x) (root uf y)

unite uf x y = do
    px <- root uf x
    py <- root uf y
    when (px /= py) $ do
        sx <- VUM.read uf px
        sy <- VUM.read uf py
        let (par, chld) = if sx < sy then (px, py)　else (py, px)
        VUM.write uf chld par
        VUM.write uf par (sx + sy) 

main = do
    [n,m] <- getIntList
    pers <- V.replicateM n $ do
        (k:ls) <- getIntList
        return ls
    let langs = V.create $ do
            vec <- VM.replicate (m+1) []
            forM_ [0..n-1] $ \p -> do
                forM_ (pers V.! p) $ \l -> do
                    VM.modify vec (p:) l
            return vec
    
    let ufvec = VU.create $ do
            uf <- newUF n
            forM_ [1..m] $ \l -> do
                if length (langs V.! l) >= 2 then do
                    let (a:as) = langs V.! l 
                    mapM_ (unite uf a) as
                else return ()
            return uf
    let ans = length . filter (< 0) $ VU.toList ufvec
    putStrLn $ if ans == 1 then "YES" else "NO"

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

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

int n,D[100001];

int main() {
	cin >> n;
	
	For(i,1,n) 
	  cin >> D[i];
	  
	long long res = 0;
	For(i,1,n-1)
	   For(j,i+1,n) 
	      res += D[i] * D[j];
	
	cout << res;

	return 0;
}


Measured memory_bytes: 256
from collections import defaultdict
import bisect

N, M = [int(i) for i in input().split()]

PY = []
PYd = defaultdict(list)

for i in range(M):
    x, y = [int(i) for i in input().split()]
    PYd[x].append(y)
    PY.append((x,y))
    
for i in PYd.keys():
    PYd[i].sort()
    
for p,y in PY:
    str_p = str(p).zfill(6)
    index = str(bisect.bisect(PYd[p], y)).zfill(6)
    print(str_p+index)

Measured memory_bytes: 35544
//ITP1-10-D: Distance 2
//2019.05.20

#include <stdio.h>
#include <math.h>

int main(void){

  int n;
  scanf("%d\n", &n);
  double x[n], y[n];
  double tmp;
  double dp, d1, d2, d3, dinf;
  double max_d = 0;

  for (int i = 0; i < n; i++) scanf("%lf", &x[i]);
  for (int i = 0; i < n; i++) scanf("%lf", &y[i]);

  for (int p = 1; p < 4; p++) {
    tmp = 0;
    for (int i = 0; i < n; i++) {
      dp = pow(fabs(x[i]-y[i]), p);
      tmp = tmp + dp;
      if (p == 1 && max_d < dp) {
        max_d = dp;
      }
    }
    switch (p) {
      case 1:
        d1 = tmp;
        break;
      case 2:
        d2 = pow(tmp, 0.50000000000000);
        break;
      case 3:
        d3 = pow(tmp, 0.33333333333333);
        break;
    }
  }
  dinf = max_d;
  printf("%lf\n%lf\n%lf\n%lf\n", d1, d2, d3, dinf);

  return 0;
}



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

using namespace std;

int n, q, l, r;
string s;
int main() {
	cin >> n >> q >> s;
	vector<int> a(n+1);
	for (int i = 1; i < n; i++) {
		a.at(i+1) = a.at(i);
		if (s.at(i - 1) == 'A'&&s.at(i) == 'C') {
			a.at(i + 1) += 1;
		}
	}
	for (int i = 0; i < q; i++) {
		cin >> l >> r;
		cout << a.at(r) - a.at(l) << endl;
	}
	return 0;
}

Measured memory_bytes: 1408
#include "math.h"
#include <algorithm>
#include <complex>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define ifor(i, a, b) for (int i = (a); i < (b); i++)
#define rfor(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
typedef long double ld;
typedef long long int lli;
typedef complex<double> P;
const double eps = 1e-11;
int vex[4] = {1, 0, -1, 0};
int vey[4] = {0, 1, 0, -1};
typedef vector<double> Vec;
typedef vector<int> vec;
typedef vector<Vec> MAT;
typedef vector<vec> mat;
lli MOD = 1000000007;
int main()
{
    int N;
    cin >> N;
    lli ans = 0;
    lli sum = 0;
    lli A[100005];
    rep(i, N)
    {
        cin >> A[i];
        if (A[i])
            sum += A[i];
        else {
            ans += sum / 2;
            sum = 0;
        }
    }
    cout << ans + sum / 2 << endl;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <math.h>
int main(void){
  int x,costmin=1E9,i,j;
  scanf("%d",&x);
  for(i=1;i<=1E9;i++){
    int sum=(i*(i+1))/2;
    if(sum>=x) {printf("%d",i);return 0;}
  }
  return 0;
}

Measured memory_bytes: 128
N, M, C = list(map(int, input().split()))
b = list(map(int, input().split()))
sum = 0
cnt = 0
for i in range(N):
    a = list(map(int, input().split()))
    for j in range(M):
        sum += a[j]*b[j]
    if sum + C > 0 :
        cnt += 1
    sum = 0
print(cnt)


Measured memory_bytes: 3060
#include "bits/stdc++.h"
#include <math.h>
#include <time.h>
using namespace std;
const long long mod = 1000000007;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
bool dbg = false;
long long gcd(long long a, long long b){
   if (a % b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a % b));
   }
}
long long lcm(long long a, long long b){
   return (a / gcd(a, b))* b;
}
//---------------------------------------------------------------------------------------------------
/*ここからいじる*/
//---------------------------------------------------------------------------------------------------

void solve(){
}
int main(){
    vector<int>data(3);
    cin >> data.at(0) >> data.at(1) >> data.at(2);
    sort(data.begin(), data.end());
    if((data.at(0) == data.at(1) && data.at(1) != data.at(2)) || (data.at(0) != data.at(1) && data.at(1) == data.at(2))){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}



Measured memory_bytes: 256
def dsf(i,sum1,ans):
    if i == 4:
        if ans == 7:
            print(sum1 + "=7")
            exit()
    else:
        dsf(i+1,sum1+"+"+abcd[i],ans + int(abcd[i]))
        dsf(i+1,sum1+"-"+abcd[i],ans - int(abcd[i]))


abcd = input()
dsf(1,abcd[0],int(abcd[0]))

Measured memory_bytes: 9200
N = gets.chomp.to_i
w = gets.chomp.split(" ").map(&:to_i)

def sum(ary)
  a = 0
  ary.map{|e|
    a += e
  }
  a
end


ans = sum(w)

for t in 1...N do
  ans = [ans, ( sum(w[t+1..N-1]) - sum(w[0..t]) ).abs ].min
end

puts ans


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

using namespace std;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);
const int limit = 100010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())
#define debug(x) cout << #x << ":" << x << endl;
#define debug2(x) for(auto a : x) cout << a << " "; cout << endl;
//------------------------------------------------------

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

    ll n;
    cin >> n;
    ll a[n][n];
    bool delete_e[n][n] = {};
    ll ans = 0;

    rep(i, n) rep(j, n) {
        cin >> a[i][j];
        ans += a[i][j];
    }

    rep(i, n) rep(j, n) rep(k, n) {
        if (a[i][j] > a[i][k] + a[k][j]) {
            printf("-1\n");
            return 0;
        } else if (i != k && j != k && a[i][j] == a[i][k] + a[k][j]) {
            delete_e[i][j] = true;
        }
    }

    rep(i, n) rep(j, n) if (delete_e[i][j]) ans -= a[i][j];
    cout << ans / 2 << endl;
    return 0;
}


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

int main(void)
{
   int i, f, j;
   char s[100000], a;

   scanf("%s",s);

   a='a';
   for(i=0;i<=26;i++){
      j=0;
      for(f=0;f<strlen(s);f++)
         if(s[f]==a)
            j++;
      if(j==0){
         printf("%c\n",a);
         return 0;
      }
      a='a'+i;
   }
   printf("None\n");
   return 0;
}

Measured memory_bytes: 1796
#include <iostream>
#include <vector>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
int N, T;
int main() {
	vector<int> c;
	vector<int> t;
	cin >> N >> T;
	REP(i, N) {
		int cs,ts;
		cin >> cs >> ts;
		c.push_back(cs);
		t.push_back(ts);
	}
	int cost = 1001;
	REP(i, N) {
		if ( T >= t[i]) {
			if (cost > c[i]){
				cost = c[i];
			}
		}
	}
 
 
	if (cost == 1001) {
		cout << "TLE" << endl;
	}
	else {
		cout << cost << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<functional>
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<string>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int inf=2147483647,dx[]={-1,0,1,0},dy[]={0,-1,0,1};// 上 左 下 右
const int N=100005,M=1000005,K=200005,mod=1000000007;
const long long llinf=9223372036854775807ll;
//int & long long
int n,m,a,b,ans[N];
vector<int> v[N];
bool u[N];
queue<int> q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a); 
	}
	cout<<"Yes\n";
	q.push(1);
	u[1]=true;
	while(q.size())
	{
		int l=q.size();
		for(int i=1;i<=l;i++)
		{
			int x=q.front();
			q.pop();
			for(int j=0;j<v[x].size();j++)
				if(!u[v[x][j]])
					u[v[x][j]]=true,q.push(v[x][j]),ans[v[x][j]]=x;
		}
	}
	for(int i=2;i<=n;i++)
		cout<<ans[i]<<'\n';
	return 0;
}

Measured memory_bytes: 10056
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Dice
{
	int d[6];
	void roll(char c){
		if(c == 'S'){
			int b = d[0];
			d[0] = d[4];
			d[4] = d[5];
			d[5] = d[1];
			d[1] = b;

		}
		if(c == 'N'){
			int b = d[0];
			d[0] = d[1];
			d[1] = d[5];
			d[5] = d[4];
			d[4] = b;
		}
		if(c == 'W'){
			int b = d[0];
			d[0] = d[2];
			d[2] = d[5];
			d[5] = d[3];
			d[3] = b;
		}
		if (c == 'E'){
			int b = d[0];
			d[0] = d[3];
			d[3] = d[5];
			d[5] = d[2];
			d[2] = b;
		}
		if(c == 'R'){
			int b = d[1];
			d[1] = d[2];
			d[2] = d[4];
			d[4] = d[3];
			d[3] = b;
		}
	}

	int top(){
		return d[0];
	}
	int right(){
		return d[2];
	}
	int left(){
		return d[3];
	}
	int front(){
		return d[1];
	}
};

int main()
{	
	Dice dc;
	for(int i=0; i<6 ;i++){
		cin >> dc.d[i]; 
	}
	int n; cin >> n;
	while(n--){
		int a,b; cin >> a >>b;
		if(dc.left() == a) dc.roll('E');
		if(dc.right() == a) dc.roll('W');
		while(dc.top() != a) dc.roll('N');
		while(dc.front() != b) dc.roll('R');
		cout << dc.right() << endl;
	}
	return 0;
}


Measured memory_bytes: 3036
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f(n) for (int i = 0; i < n; i++)
#define fo(i, x, n) for (int i = x; i < n; i++)
#define fb(i, x, n) for (int i = n - 1; i >= x; i--)
#define w(t)  \
    int t;    \
    cin >> t; \
    while (t--)

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

void print(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

void print(vi &v)
{
    f(v.size())
    {
        cout << v[i] << " ";
    }
    cout << endl;
}
bool vis[100005];
vector<long long>v[100050];
void dfs(long long x)
{
    int i;
    vis[x]=true;
    for(i=0; i<v[x].size(); i++)
    {
        if (vis[v[x][i]]==false)
            dfs(v[x][i]);
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long a, b, n,k,i,s=0;
    cin >>n>>k;
    for(i=0; i<k; i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1; i<=n; i++)
    {
        if (vis[i]==false)
        {
            s++;
            dfs(i);
        }
    }
    cout<<s-1;


    //cerr<< "Time Killed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}


Measured memory_bytes: 10336
import copy
n = int(input())
lst1 = list(map(int,input().split()))
lst2 = []
c = copy.deepcopy(lst1)

c.sort()

Kth = c[n//2] #上の方

med_low = Kth
med_high = c[n//2-1]

for i in range(n):
    if lst1[i] < Kth:
        print(med_low)
    else:
        print(med_high)

Measured memory_bytes: 121080
n, m = list(map(int, input().split()))
def factorial(x):
    f = 1
    for i in range(1, x+1):
        f *= i
    return f
ans = 0
if n < 2 and m < 2:
    ans = 0
    print(ans)
elif n < 2:
    ans = int(factorial(m) / (factorial(2) * factorial(m - 2)))
    print(ans)
elif m < 2:
    ans = int(factorial(n) / (factorial(2) * factorial(n - 2)))
    print(ans)
else:
    ans = int(factorial(m) / (factorial(2) * factorial(m - 2)) + factorial(n) / (factorial(2) * factorial(n - 2)))
    print(ans)


Measured memory_bytes: 3064
//include
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const long long INF = 1000000007;
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
// chmax chmin
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; }

long long mul_modp(long long a, long long b, long long p){
    // a*b mod p
    return ((a % p) * (b % p)) % p;
}

int main(void){
    int N; cin >> N;
    string s1,s2; cin >> s1 >> s2;

    ll ans;
    int init, ptn;
    if(s1[0] == s2[0]){ans = 3; init=1; ptn=0;}
    else{ans = 6; init=2; ptn=1;}

    FOR(i,init,N){
        if(s1[i] == s2[i]){
            if(ptn) ans = mul_modp(ans, 1, INF);
            else ans = mul_modp(ans, 2, INF);
            ptn = 0;
        }
        else{
            if(ptn) ans = mul_modp(ans, 3, INF);
            else ans = mul_modp(ans, 2, INF);
            ptn = 1;
            i++;
        }
    }
    cout << ans << endl;

    return 0;
}

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

#define int long long
#define counter(m)     for(int i=0;i<m;i++)
#define gcd            __gcd
#define endl           "\n"
#define pb             emplace_back
#define setbits(x)     __builtin_popcountll(x)
#define zrobits(x)     __builtin_ctzll(x)
#define mod            1000000007
#define mod2           998244353
#define maxe           *max_element
#define mine           *min_element
#define inf            1e18
#define deci(x, y)      fixed<<setprecision(y)<<x
#define w(t)           int t; cin>>t; while(t--)
#define nitin          ios_base::sync_with_stdio(false); cin.tie(NULL)
#define PI             3.141592653589793238
using namespace std;

int32_t main() {
    nitin;
    int a,b,c;
    cin>>a>>b>>c;
    int k;
    cin>>k;
    if(k%2==0)
        cout<<a-b<<endl;
    else
        cout<<b-a<<endl;
}

Measured memory_bytes: 3552
H, W, K = map(int, input().split())
C = [list(input()) for i in range(H)]

count = 0

for row in range((1 << H) - 1):
    for col in range((1 << W) - 1):
        black = 0
        for i in range(H):
            for j in range(W):
                if ((row >> i) & 1) == 0 and ((col >> j) & 1) == 0:
                    if C[i][j] == '#':
                        black += 1
        if black == K:
            count += 1

print(count)


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

					#define mp make_pair
					#define pb push_back
					#define sqr(x) (x) * (x)
					#define sors(s) sort(s.begin(), s.end())
					#define F first
					#define S second

					using namespace std;
					typedef long long ll;
					ll n, k, s, a[222], b[222], c[222], d[222];
					int main()
					{
						cin >> n;
						for(int i = 1; i <= n; i++)
							cin >> a[i];
						for(int i = 1; i <= n; i++)
							cin >> b[i];
						for(int i = 1; i < n; i++)
							cin >> c[i];
						for(int j = 1; j <= n; j++)
						{
							int i = a[j], q = a[j-1];
						 	s += b[i];
							d[i] = 1;
						 	if(d[i-1] == 1 && i - q == 1)
							 	s += c[i-1];	  	
						}	
						cout << s;
					}


Measured memory_bytes: 256
#include <iostream>

int main (void) {
  int A, B; std::cin >> A >> B;
  int answer;
  
  if (A==1 && B==2 || A==2 && B==1) { 
   answer=3;
  }
  else if (A==1 && B==3 || A==3 && B==1) {
    answer=2;
  }
  else if (A==2 && B==3 || A==3 && B==2) {
    answer=1;
  }
  std::cout<<answer<<std::endl;
  return 0;
}

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

int main(){
  int wholeSecond;
  int hour, minute, second;
  cin >> wholeSecond;
  
  second = wholeSecond % 60;
  minute = (wholeSecond / 60) % 60;
  hour = wholeSecond / 3600;
  
  cout << hour << ':' << minute << ':' << second << endl;
  return 0;
}

Measured memory_bytes: 3048
#!/usr/bin/env python3
#ABC86 C

n = int(input())

nt,nx,ny = 0,0,0
f = 1
for _ in range(n):
    t,x,y = map(int,input().split())
    if t - nt < abs(nx - x) + abs(ny - y):
        f = 0
    s = abs(nx - x) + abs(ny - y) - (t - nt)
    if s % 2 == 1:
        f = 0
    nt,nx,ny = t,x,y
if f:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 47064
#include<stdio.h>

int main()
{
	int S, h, m, s;
	scanf("%d", &S);
	h = S/3600;
	m = S%3600 / 60;
	s = S%3600%60;
	printf("%d:%d:%d\n", h, m, s);
	return 0;
} 


Measured memory_bytes: 2756
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <iomanip>

using namespace std;    
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int main() {

    ll x, y;
    cin >> x >> y;

    if(x % y == 0){
        cout << -1 << endl;
    }
    else{
        cout << x << endl;
    }
    
}

Measured memory_bytes: 256
import collections

N = int(input())
S = input()
A = ''
B = S
ans = 0
for i in range(N):
  A += B[0]
  B = B[1:]
  C = collections.Counter(A)
  D = 0
  for w in C:
    if w in B:
      D += 1
  if D > ans:
    ans = D
print(ans)

Measured memory_bytes: 39728
import collections

N=int(input())
S=[]
for i in range(N):
    S.append(input())

counter=collections.Counter(S)

print('AC x {}'.format(counter['AC']))
print('WA x {}'.format(counter['WA']))
print('TLE x {}'.format(counter['TLE']))
print('RE x {}'.format(counter['RE']))

Measured memory_bytes: 16608
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define br cout << endl;
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>;
template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true;} return false;}

// 0 false, 1 true 
// stringの数字をint型にしてアスキーコードになったら -48する
// 切り上げ　ceil(a)


int main() {
    string s;
    cin >> s;
    int n = stoi(s);
    int size = s.size();

    vector<ll> vec(100);

    rep(i,n){
        string tmp = to_string(i+1);
        ll first = tmp.at(0) - 48;
        ll last = tmp.at(tmp.size()-1) - 48;
        vec.at(10*first + last)++;
    }

    ll ans = 0;
    for(ll i = 1; i < 10; i++){
        for(ll j = 1; j < 10; j++){
            ans += vec.at(i*10 + j) * vec.at(j*10 + i);
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
using namespace std;
string henkan(string x)//??§?????????????????°?°????????????????
{
    int len = x.length();
     
    for(int i = 0; i < len; i++){
        if('A' <= x[i] && x[i] <= 'Z'){
            x[i] += 32;
        }
    }
    return x;
}

void print_answer(int num)
{
	printf("%d\n", num);
}
int main(void)
{
	string W;//??????
	string T;//??????
	
	getline(cin, W);
	
	string x;
	x = W;
	W = henkan(W);
	
	int num = 0;
	while(x!= "END_OF_TEXT"){
		cin >> T;
		
		x = T;
		T = henkan(T);
		
		if(W == T){
			num++;
		}
	}
	
	print_answer(num);
	
	return 0;
}

Measured memory_bytes: 3240
#include "bits/stdc++.h"
using namespace std;

int main() {
	int N, L;
	string ans;
	cin >> N >> L;
	vector<string> s(N);
	for (int i = 0; i < N; i++) cin >> s[i];

	sort(s.begin(), s.end());

	for (int i = 0; i < N; i++) {
		ans += s[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def factorial(n):
    if n == 0:
        return 1
    else:
        return factorial(n-1)*n


def solve(N: int, P: "List[int]", Q: "List[int]"):

    def rec(A):
        if len(A) == 1:
            return 1
        else:
            n = len(A)
            B = [0]*(n-1)
            for i, a in enumerate(A[1:]):
                if A[0] < a:
                    B[i] = a-1
                else:
                    B[i] = a
            return (A[0]-1)*factorial(n-1)+rec(B)

    print(abs(rec(P)-rec(Q)))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    Q = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P, Q)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
N = int(input())
A = []
B = []

for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

ctr = 0

for i in reversed(range(N)):
    if (A[i] + ctr) % B[i] == 0: continue
    ctr += B[i] - ((A[i] + ctr) % B[i])

print(ctr)

Measured memory_bytes: 56792
//:Ditttoo
#include<bits/stdc++.h>
#define int long long int 
using namespace std;
int32_t main()
{
	int n;
	cin>>n;
	double p[n+1];
	for(int i=1;i<=n;i++)
		cin>>p[i];

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

	for(int i=1;i<=n;i++){
		for(int j=0;j<i+1;j++){
			if(j>0){
				h[i][j] = h[i-1][j-1] * p[i] + h[i-1][j] * (1-p[i]);
			}
			else { 
				h[i][j] =  h[i-1][j] * (1-p[i]);
			}
		}
	}

	double res = 0;

	for(int i=n/2 + 1 ;i<=n;i++){
		res += h[n][i] ;
	}
	printf("%.14f",res);
	return 0;
}        

Measured memory_bytes: 70528
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define vl vector
using namespace std;
int main()
{
    ll n,a,b;
    cin>>n>>a>>b;
    ll rem=n%(a+b);
    rem=min(a,rem);
    n/=(a+b);
    n*=a;
    n+=rem;
    cout<<n;
}

Measured memory_bytes: 256
n=int(input())
p=list(map(str,input().split()))
q=list(map(str,input().split()))


import itertools

f=list(itertools.permutations(p))

newf=[]

for i in range(len(f)):
    ff=""
    for ii in range(n):
        ff+=f[i][ii]
    newf.append(ff)

newf=[int(i) for i in newf]
newf.sort()

pp=""
for i in p:
    pp+=i
p=int(pp)
qq=""
for i in q:
    qq+=i
q=int(qq)


a=newf.index(p)
b=newf.index(q)
print(abs(a-b))

Measured memory_bytes: 12532
import java.util.Scanner;

public class Main {

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

            int a = X / 100;
            int b = X % 100;

            if (b <= a * 5) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
    }

}


Measured memory_bytes: 23764
n, k = map(int, input().split())
MOD =10**9+7

memo = [[{} for j in  range(n+1)] for i in range(n+1)]

def fdp(cur_N, remain, min_k, MOD=10**9+7):
    if cur_N <= 1:
        if remain == 0 and min_k == 0:
            return 1
        if remain == 1 and min_k == 2:
            return 1
        else:
            return 0
    if cur_N < remain:
        return 0
    if min_k < 0:
        return 0
    if min_k in memo[cur_N][remain]:
        ret = memo[cur_N][remain][min_k]
        return ret
      
    temp1 = fdp(cur_N-1, remain, min_k - 2*remain) %MOD
    temp2 = fdp(cur_N-1, remain+1, min_k -2*remain) %MOD
    temp3 = fdp(cur_N-1, remain-1, min_k-2*remain) % MOD
    score = (temp1*(2*remain+1))%MOD +(temp2*(remain+1)*(remain+1))%MOD+temp3
    score = score % MOD
    memo[cur_N][remain][min_k] = score
    return score
ret = fdp(n, 0, k)
print(ret)

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

typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1e9+7,inf=mod*mod*3ll;;
#define rep(i,N) for(ll i=0; i<(N); i++)
#define rep1(i,N) for(ll i=1; i<(N); i++)
#define pb push_back

ll N;
ll A[200005];
ll dp[200005];
ll ans;
map<ll,ll> mp;

int main(){

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

cin>>N;
rep1(i,N+1) cin>>A[i];

dp[1]=0; mp[1+A[1]]++;
rep1(i,N+1){
	if(i==1) continue;
	dp[i]=mp[i-A[i]];
	mp[i+A[i]]++;
}

rep1(i,N+1){
ans+=dp[i];
}

cout<<ans<<endl;


}
	


Measured memory_bytes: 29444
import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
a.sort()
b.sort()
c.sort()
for i in range(n):
  ans += bisect.bisect_left(a, b[i]) * (n - bisect.bisect_right(c, b[i]))
print(ans)

Measured memory_bytes: 23328
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(void)
{
    int N;
    cin >> N;
    int count = 0, flug = 0;
    vector<long long> num(N);
    for (int i = 0; i < N; ++i)
        cin >> num[i];
    do
    {
        for (int i = 0; i < N; ++i)
        {
            if (num[i] % 2 == 1)
            {
                flug = 1;
                break;
            }
        }
        if (flug == 0)
        {
            for (int i = 0; i < N; ++i)
                num[i] /= 2;
            count++;
        }

    } while (flug == 0);
    cout << count << "\n";
}

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

#define ll long long
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    int s,w;
    cin >> s >> w;
    if(w>=s) cout << "unsafe" << endl;
    else cout << "safe" << endl;
}   

Measured memory_bytes: 3636
import sys
sys.setrecursionlimit(10**7)


n,u,v=map(int, input().split())
u-=1
v-=1

graph = [[] for _ in range(n+1)]
# for i in range(n-1):
#     a, b=map(int, input().split())
#     graph[a-1].append(b-1)
#     graph[b-1].append(a-1)

ab=[list(map(int, input().split())) for _ in range(n-1)]
for a,b in ab:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

dist=[[-1, -1] for _ in range(n)]
dist[v][0]=0
dist[u][1]=0

def dfs1(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][0]==-1:
            dist[vvv][0]=dist[v][0]+1
            dfs1(graph,vvv)

def dfs2(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][1]==-1:
            dist[vvv][1]=dist[v][1]+1
            dfs2(graph,vvv)

dfs1(graph,v)
dfs2(graph,u)
dist.sort(reverse=True)

for i in range(10**6):
    if dist[i][0]-dist[i][1]>=1:
        print(dist[i][0]-1)
        break


Measured memory_bytes: 124796
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
   
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
   
const int MAX_N=1<<17;

const ll INF=1e9;
    
ll mn[2*MAX_N-1], part[2*MAX_N-1];
bool mada[2*MAX_N-1];
int m;
   
void init(int n){
    m=1;
    while(m<n) m*=2;
}
  
void eval(int k, int l, int r){
    if(mada[k]){
        mn[k]+=part[k];
        if(k<m-1){
            part[2*k+1]+=part[k];
            part[2*k+2]+=part[k];
          mada[2*k+1]=1; mada[2*k+2]=1;
        }
        mada[k]=0;
      part[k]=0;
    }
}
    
void add(int a, int b, ll x, int k, int l, int r){
	eval(k, l, r);
	if(r<=a || b<=l) return;
    if(a<=l && r<=b){
        part[k]=x;
      mada[k]=1;
        eval(k, l, r);
    }else{
        add(a, b, x, k*2+1, l, (l+r)/2);
        add(a, b, x, k*2+2, (l+r)/2, r);
        mn[k]=min(mn[2*k+1], mn[2*k+2]);
    }
}
    
ll find(int a, int b, int k, int l, int r){
	eval(k, l, r);
    if(b<=l || r<=a){
        return INF;
    }
    if(a<=l && r<=b){
        return mn[k];
    }else{
        return min(find(a, b, 2*k+1, l, (l+r)/2), find(a, b, 2*k+2, (l+r)/2, r));
    }
}
   
int main()
{
    int n, q;
    cin>>n>>q;
    init(n);
    for(int i=0; i<q; i++){
        int tp;
        cin>>tp;
        if(tp==0){
            int s, t; ll x;
            cin>>s>>t>>x;
            add(s, t+1, x, 0, 0, m);
        }else{
            int s, t;
            cin>>s>>t;
            cout<<find(s, t+1, 0, 0, m)<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 6472
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <limits>
#include <string>
#include <algorithm>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include "math.h"
#include "assert.h"

using namespace std;

#define ll long long

#define BUFF ios::sync_with_stdio(false)
#define epsilon 1e-07
#define pi 2 * acos(0.0);
#define mod 1000000007   // 1e9+7
#define cerr if(false)cerr
#define watch(x) cerr << #x << " = " << x << endl;

#define inf std::numeric_limits<int>().max();

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int ans = 1;
	char c = s[0];
	for(int i=1; i<n; i++) {
		if (s[i] != c) {
			ans++;
			c = s[i];
		} 
	}
	cout << ans << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define x first
#define y second
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
#define pb push_back
#define rep(i, a, b) for(int i = a; i < b; i++)
#define mem(i) memset((i), (-1), (sizeof(i)))
#define all(i) (i).begin(), (i).end()
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;

int n, m, ans;
int w[104], v[104];
ll dp[104][100005];

int main()
{
	fastio;
	cin >> n >> m;
	rep(i, 1, n + 1) cin >> w[i] >> v[i];

	fill(&dp[0][0], &dp[99][100004] + 1, 1e18);
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= 100000; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j - v[i] >= 0) dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
			if (dp[i][j] <= m) ans = max(ans, j);
		}

	cout << ans << '\n';
	return 0;
}

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

using namespace std;

int dp[1000001];
int kind[31];


const int MAX_SIZE = 10000;
const int MAX_PRIME = 1000000;


int prime[MAX_PRIME+1];
bool isPrime[MAX_PRIME+1];
int p;

void erats(){
	// primeXgðú»
	fill(isPrime,isPrime+MAX_PRIME,true);
	p = 0;
	isPrime[0] = isPrime[1] = false;

	for(int i = 2; i <= MAX_PRIME; i++){
		if(isPrime[i]){
			prime[p++] = i;
		}
		else
			continue;

		// Óé¢É©¯é
		for(int j = 2*i; j <= MAX_PRIME; j+=i){
			isPrime[j] = false;
		}
	}
}


int main(){

	int n;
	int x;
	erats();
	while(cin>>n>>x&&!(n==0&&x==0)){
		for(int i = 0; i < n; i++){
			cin>>kind[i];
		}
		// eàzÌ¥¢ûª½íÞ é©ðßé
		//fill(dp,dp+1000001,0);
		dp[0]=1;
		int maxCost=-1;

		//for(int j = 0; j < n; j++){
		//	for(int i = kind[j]; i <= x; i++){
		//		dp[i]+=dp[i-kind[j]];
		//	}
		//}

		for(int i = 1; i <= x; i++){
			dp[i]=0;
			for(int j = 0; j < n; j++){
				if(i-kind[j]>=0){
					dp[i]+=dp[i-kind[j]];
				}
			}
			if(dp[i]&&(isPrime[i])){
				maxCost=i;
			}
		}
		//for(int i = 0; i <= x; i++){
		//	if(dp[i]&&isPrime[i])
		//		maxCost=i;
		//}


		if(maxCost==-1)
			cout<<"NA"<<endl;
		else
			cout<<maxCost<<endl;
	}

	return 0;
}

Measured memory_bytes: 6056
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define mp make_pair
#define pb push_back
#define x first
#define y second

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

int a[110],b[110],ans[110];

int main()
{

	int n,m;scanf("%d%d",&n,&m);
	int l1=0,l2=0;
	for (int i=1;i<=m;i++)
	{
		int x;scanf("%d",&x);
		if (x%2==1) a[++l1]=x; else b[++l2]=x;
	}
	if (l1>2) {puts("Impossible");return 0;}
	int cnt=0;
	if (l1==1)
	{
		if (a[1]>1) ans[++cnt]=a[1]-1;
		printf("%d ",a[1]);
		for (int i=1;i<=l2;i++) printf("%d ",b[i]);puts("");
		for (int i=1;i<=l2;i++) ans[++cnt]=b[i];
		ans[++cnt]=1;
	}
	else
		if (l1==0)
		{
			if (l2==1)
			{
				printf("%d\n",b[1]);
				ans[++cnt]=1;ans[++cnt]=b[1]-1;
			}
			else
			{
				ans[++cnt]=b[1]-1;
				for (int i=1;i<=l2;i++) printf("%d ",b[i]);puts("");
				for (int i=2;i<=l2;i++) ans[++cnt]=b[i];
				ans[++cnt]=1;
			}
		}
		else
			if (l1==2)
			{
				if (a[1]>1) ans[++cnt]=a[1]-1;
				printf("%d ",a[1]);
				for (int i=1;i<=l2;i++) printf("%d ",b[i]);
				printf("%d\n",a[2]);
				for (int i=1;i<=l2;i++) ans[++cnt]=b[i];
				ans[++cnt]=a[2]+1;
			}
	printf("%d\n",cnt);
	for (int i=1;i<=cnt;i++) printf("%d ",ans[i]);
	return 0;
}


Measured memory_bytes: 128
# -*- coding: utf-8 -*-

""" 2次元DP """

N,A = map(int, input().split())
xN = list(map(int, input().split()))
X = max(max(xN), A)
# 全てのxから-Aすることで、合計=0,平均=0を求める形にする
yN = [int(i)-A for i in xN]

# 二つ目の添え字はマイナスを取りうるので工夫する
dp = [[0] * (2*N*X+1) for j in range(N+1)]
# 基準点を0じゃなくて真ん中(N*X)にする
dp[0][N*X] = 1

ans = 0
for i in range(1,N+1):
    for t in range(2*N*X+1):
        # 範囲外ならそのまま
        if t - yN[i-1] < 0 or t - yN[i-1] > 2*N*X:
            dp[i][t] = dp[i-1][t]
        # 範囲内なら前の値を足す
        elif 0 <= t - yN[i-1] <= 2*N*X:
            dp[i][t] = dp[i-1][t] + dp[i-1][t - yN[i-1]]
# 1枚も選ばないパターンを引く
print(dp[N][N*X]-1)

Measured memory_bytes: 5604
#include <bits/stdc++.h>
#define MOD 1000000007
 
using namespace std;
string s;

int main(){

cin>>s;

int len=s.size();
if(len==2){
    if(s[0]==s[1]) cout<<1<<" "<<2<<endl; 
    else cout<<-1<<" "<<-1<<endl; 
    return 0;
}

if(len%2==0){
    for(int i=0; i<len-3; i++){
        if(s[i]==s[i+1]||s[i]==s[i+2]){
            cout<<i+1<<" "<<i+3<<endl; return 0;
        }
    }
    for(int i=1; i<len-2; i++){
        if(s[i]==s[i+1]||s[i]==s[i+2]){
            cout<<i+1<<" "<<i+3<<endl; return 0;
        }
    }
}else{
    for(int i=0; i<len-2; i++){
        if(s[i]==s[i+1]||s[i]==s[i+2]){
            cout<<i+1<<" "<<i+3<<endl; return 0;
        }
    }
}

cout<<-1<<" "<<-1<<endl;

return 0;
 
}

Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#define NIL NULL

struct node {
	int key;
	struct node *right, *left, *parent;
};

typedef struct node Node;

Node *root;

void insert(int);
void print_i(Node *);
void print_p(Node *);
Node *find(int);
void delete (Node *);
Node *Minimum(Node *);
Node *getSuccessor(Node *);

int main() {
	int i;
	int n, k;
	char com[32];
	Node *u;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%s", com);

		if (com[0] == 'i') {
			scanf("%d", &k);
			insert(k);
		} else if (com[0] == 'p') {
			print_i(root);
			printf("\n");
			print_p(root);
			printf("\n");
		} else if (com[0] == 'd') {
			scanf("%d", &k);
			delete (find(k));
		} else {
			scanf("%d", &k);
			if (find(k) != NIL) {
				printf("yes\n");
			} else {
				printf("no\n");
			}
		}
	}
}

void insert(int k) {
	Node *y = NIL;
	Node *x = root;
	Node *z;

	z = (Node *)malloc(sizeof(Node));
	z->key = k;
	z->left = NIL;
	z->right = NIL;

	//場所決め
	while (x != NIL) {
		y = x;
		if (z->key < x->key) {
			x = x->left;
		} else {
			x = x->right;
		}
	}
	z->parent = y;
	if (y == NIL) {
		root = z;
	} else {
		if (z->key < y->key) {
			y->left = z;
		} else {
			y->right = z;
		}
	}
}

void print_i(Node *s) {
	if (s == NIL) return;
	print_i(s->left);
	printf(" %d", s->key);
	print_i(s->right);
}
void print_p(Node *s) {
	if (s == NIL) return;
	printf(" %d", s->key);
	print_p(s->left);
	print_p(s->right);
}

Node *find(int k) {
	Node *s = root;
	while (s != NIL && k != s->key) {
		if (k < s->key) {
			s = s->left;
		} else {
			s = s->right;
		}
	}
	return s;
}

void delete (Node *z) {
	Node *y;  //削除対象
	Node *x;  // yの子

	//削除する節点を決める
	if (z->left == NIL || z->right == NIL) {
		y = z;
	} else {
		y = getSuccessor(z);
	}

	// yの子を決める
	if (y->left != NIL) {
		x = y->left;
	} else {
		x = y->right;
	}

	if (x != NIL) {
		x->parent = y->parent;
	}

	if (y->parent == NIL) {
		root = x;
	} else {
		if (y == y->parent->left) {
			y->parent->left = x;
		} else {
			y->parent->right = x;
		}
	}

	if (y != z) {
		z->key = y->key;
	}

	free(y);
}

Node *getSuccessor(Node *x) {
	if (x->right != NIL) {
		return Minimum(x->right);
	}
	Node *y = x->parent;
	while (y != NIL && x == y->right) {
		x = y;
		y = y->parent;
	}
	return y;
}

Node *Minimum(Node *s) {
	while (s->left != NIL) {
		s = s->left;
	}
	return s;
}


Measured memory_bytes: 20520
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define pie 3.142857143
#define ll long long int
#define fr(i,a,n) for(ll i=a;i<n;i++)
#define vi vector<int>
#define vlli vector<ll>
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fv(i,a) for(auto i:a)
#define sz(a) int((a).size())
#define all(c) (c).begin(),(c).end()
#define frv(i,c) for(auto i = c.begin(); i != c.end(); i++)

void solve()
{
	int n;
	cin >> n;
	vi d(3, 0);

	fr(t, 0, n)
	{
		int a[3];
		fr(i, 0, 3)
		cin >> a[i];
		vi x(3, 0);

		fr(j, 0, 3)
		{
			fr(k, 0, 3)
			{
				if (k != j)
				{
					x[j] = max(x[j], a[j] + d[k]);
				}
			}
		}
		d = x;
	}
	int l = 0;
	fr(i, 0, 3)
	{
		l = max(l, d[i]);
	}
	cout << l << endl;

}


int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen ("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	//cin>>t;
	t = 1;
	while (t--)
	{
		solve();
	}


	return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
vector<int64_t> prime_factorize(int64_t N) {
    vector<int64_t> res;
    for (int64_t a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        int64_t b = N / a;
        res.emplace_back(a);
        res.emplace_back(b);
    }

    // 最後に残った数について
    if (N != 1) res.emplace_back(N);
    return res;
}

int main()
{
    int64_t N;
    cin >> N;
    int64_t min_ = INT64_MAX;
    vector<int64_t> vec = prime_factorize(N);
    for (int64_t i=0; i<vec.size(); i++) {
            int64_t n = vec[i];
            int64_t b = N / n;
            int64_t score = (n - 1) + (b - 1);
            if (min_ > score) {
                min_ = score;
            }
    }

    cout << min_ << endl;
    return 0;
}

Measured memory_bytes: 3752