akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
 
 
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> PII;
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);
 
//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;


void solve(long long N, long long A, long long B){
    if(A>B)cout<<0<<endl;
    else{
        if(N==1&&A!=B){
            cout<<0<<endl;
        }
        else if(N==1 &&A==B){
            cout<<1<<endl;
        }
        else{
            LL min_ = (A+B)+(N-2)*A;
            LL max_ = (A+B)+(N-2)*B;
            cout<<max_-min_+1<<endl;
        }
    }
    return;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(N, A, B);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <algorithm>
#define forn(a, n) for(int a = 0; a<(int) (n); ++a)
#define rforn(a, n) for(int a = (n)-1; a>=0; --a)
using namespace std;
const int N = 6e5+20;

int main()
{
    int n, m, p;
    cin>>n>>m>>p;
    
    if( max(n, max(m, p)) == 7)
    {
        if( min(n, min(m, p)) == 5 && n+m+p == 5 + max(n, max(m, p)) + min(n, min(m, p)) ) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

Measured memory_bytes: 3556
def str_plus(splus):
    cnt = 0
    start = 0
    for i in range(len(splus)):
        #print(str(splus[i]))
        if(splus[i] == '+'):
            cnt += int(splus[start:i])
            start = i
        elif(i == len(splus)-1):
            cnt += int(splus[start:i+1])

    return cnt

def str_ary_start(s):
    splus = []
    for i in range(len(s)):
        splus.append(s[i])
        if(i != len(s)-1):
            splus.append("")

    return splus


s = input()
ans = 0

for i in range(2**(len(s)-1)):
    splus = str_ary_start(s)
    for j in range(len(s)-1):
        #print(str(i) + ' ' + str(j))
        if((i>>j)&1 == 1):
            splus[j*2+1] = '+'
    #print(splus)
    #print(str_plus("".join(splus)))
    ans += str_plus("".join(splus))

print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) for(int i = 0; i < (n); i++)

/* exchange */
#define chmin(a, b) (a) = min((ll)(a), (ll)(b))
#define chmax(a, b) (a) = max((ll)(a), (ll)(b))

/* output */
#define I(x) cin >> x;
#define D(x) cerr << (x) << " ";
#define BR cerr << "\n";
#define P(x) cout << (x) << endl;
#define FIX cout << fixed << setprecision(10);

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

ll N = 0;
ll ret = 0;

int main(void){
  ll A, B;
  I(A);
  I(B);

  P(A*B);

}


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

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	string s;
	map<string, int> cnt;
	vector<string> str = {"AC", "WA", "TLE", "RE"};
	for (int i = 1; i <= n; ++i)
	{
		cin >> s;
		cnt[s]++;
	}
	for (int i = 0; i < 4; ++i)
	{
		cout << str[i] << " x " << cnt[str[i]] << '\n';
	}
}

Measured memory_bytes: 3660
#include <stdio.h>

int main(void) {
	int count[30]={0};
	int i;
	int dansuu;
	int day;
	int year;
	count[0]=1;
	count[1]=1;
	count[2]=1;
	for(i=0;i<29;i++) {
		if(i+1<30)count[i+1]+=count[i];
		if(i+2<30)count[i+2]+=count[i];
		if(i+3<30)count[i+3]+=count[i];
	}
	while(1) {
		scanf("%d",&dansuu);
		if(dansuu==0)break;
		day=count[dansuu-1]/10;
		if(count[dansuu-1]%10)day++;
		year=day/365;
		if(day%365)year++;
		printf("%d\n",year);
	}
	return 0;
}

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

int main(){
    int N;
    cin >> N;
    int B[N-1];
    for(int i = 0; i < N-1; i++) cin >> B[i];
    
    int ans = B[0] + B[N-2];
    for(int i = 1; i < N-1; i++)
        ans += min(B[i-1], B[i]);

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


Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque,defaultdict

def all_bit_count(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c
  
n = int(readline())
d = defaultdict(int)
cnt = 1

g = [[] * n for i in range(n)]
for i in range(n-1):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)

m = int(readline())
c = []
for i in range(m):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1  
  que = deque()
  que.append((u,0))
  chk = [False]*n
  chk[u] = True
  while que:
      now,L = que.popleft()
      if now == v:
        c.append(L)
        break
      for i in g[now]:
          if not chk[i]:
            chk[i] = True
            mi = min(now,i)
            ma = max(now,i)
            mm = mi*100+ma
            if d[mm] == 0:
              d[mm] = cnt
              cnt += 1
            que.append((i,L|(1<<d[mm])))
                     
import itertools
ans = 1<<(n-1)
for i in range(1,m+1):
  for j in itertools.combinations(c,i):
    K = 0
    for k in j:
      K |= k
    l = all_bit_count(K)
    ans += pow(-1,i)*pow(2,n-1-l)
    
print(ans)

Measured memory_bytes: 74244
import bisect
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
if n == 2:
    print(max(a),min(a))
    exit()
ans_n = a[n-1]
bestr = ans_n//2
kouho = bisect.bisect_left(a,bestr)
if abs(bestr-a[kouho-1]) < abs(bestr-a[kouho]) and abs(bestr-a[kouho-1]) < abs(bestr-a[kouho+1]):
    ans_r = a[kouho-1]
elif abs(bestr-a[kouho]) < abs(bestr-a[kouho+1]):
    ans_r = a[kouho]
else:
    ans_r = a[kouho+1]
print(ans_n, ans_r)


Measured memory_bytes: 14052
#include <cstdio>
#include <set>
using namespace std;
main(){
	int n,i,j,a,b;
	double r,x,y;
	set<pair<int,int> >s;
	for(scanf("%d%lf",&n,&r);n--;){
		scanf("%lf%lf",&x,&y),a=x/r,b=y/r;
		for(i=-1;i<=1;i++)for(j=-1;j<=1;j++)if(s.find(make_pair(a+i,b+j))!=s.end())goto next;
		s.insert(make_pair(a,b));
		next:;
	}
	printf("%d\n",s.size());
}

Measured memory_bytes: 8588
N, M = map(int, input().split())
listA = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
dp = [-1]*10010
dp[0] = 0
for j in range(1, N+1):
	for a in listA:
		if j-c[a] >= 0:
			dp[j] = max(dp[j], dp[j-c[a]]*10+a)
print(dp[N])

Measured memory_bytes: 14516
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <complex>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cwchar>
#include <cwctype>
#include <exception>
#include <locale>
#include <numeric>
#include <new>
#include <stdexcept>
#include <limits>
#include <valarray>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <list>
#include <utility>
#include <bitset>
#include <algorithm>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF=1e9+7;
const ll INFL=1LL<<60;
vector<pii> G1[100005],G2[100005];
ll dis[100005];
bool fin[100005];
ll dp1[100005],dp2[100005];
vector<int> ord;
ll sqrl(ll x){
	x%=INF;
	return x*x%INF;
}
void inc(ll& u,ll v){
	u+=v;
	u%=INF;
}
void dijkstra(int s,int t){
	memset(fin,false,sizeof(fin));
	rep1(k,100000)dis[k]=INFL;
	priority_queue<pair<ll,int> > Q;
	dis[s]=0LL;
	Q.push(MP(0LL,s));
	while(!Q.empty()){
		int v=Q.top().second;
		Q.pop();
		if(fin[v])continue;
		ord.push_back(v);
		fin[v]=true;
		rep(k,G1[v].size()){
			int u=G1[v][k].first,cd=G1[v][k].second;
			if(dis[v]+cd<dis[u]){
				dis[u]=dis[v]+cd;
				Q.push(MP(-dis[u],u));
			}
		}
	}
}
int main(){
	int n,m,s,t;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	rep(k,m){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		G1[u].push_back(MP(v,w));
		G1[v].push_back(MP(u,w));
	}
	dijkstra(s,t);
	rep1(i,n)rep(j,G1[i].size())
	if(dis[i]+G1[i][j].second==dis[G1[i][j].first])
	G2[i].push_back(G1[i][j]);
	dp1[s]=1LL;
	rep(i,ord.size()){
		int cv=ord[i];
		rep(j,G2[cv].size())
		inc(dp1[G2[cv][j].first],dp1[cv]);
	}
	dp2[t]=1LL;
	for(int i=ord.size()-1;i>=0;i--){
		int cv=ord[i];
		rep(j,G2[cv].size())
		inc(dp2[cv],dp2[G2[cv][j].first]);
	}
	ll tot=0LL;
	rep1(i,n){
		if(dis[i]+dis[i]==dis[t])inc(tot,sqrl(dp1[i]*dp2[i]));
		rep(j,G2[i].size()){
			int cu=i,cv=G2[i][j].first;
			if(dis[cu]<dis[t]-dis[cu]&&dis[t]-dis[cv]<dis[cv])inc(tot,sqrl(dp1[cu]*dp2[cv]));
		}
	}
	tot=(dp1[t]*dp2[s]-tot)%INF;
	if(tot<0)tot+=INF;
	printf("%lld\n",tot);
	return 0;
}

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

int main()
{
  string s, t;
  cin >> s >> t;
  
  bool flag = false;
  if (s == t) flag = true;
  for (int i = 0; i < s.size() - 1 && !flag; ++i)
  {
    string temp;
    temp.push_back(s.back());
    s.pop_back();
    s = temp + s;
    if (s == t) flag = true;
  }
  cout << (flag ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

long N;
long W;
long dp[110][100010];
long w[110];
long v[110];
//dpに格納するのは重さの総和
//価値の総和は配列の要素番号
long V = 100010;
const long INF = 10000000000; 
long min(long a, long b)
{
	if (a > b)
		return b;
	return a;
}

int main(int argc, char const *argv[])
{
	scanf("%ld%ld", &N, &W);
	for (int i = 0; i < N; i++) scanf("%ld%ld", w+i, v+i);
	for (int i = 0; i < 110; i++)
	{
		for (int j = 0; j < V; j++)
		{
			dp[i][j] = INF;
		}
	}
	dp[0][0] = 0;
	for (long i = 0; i < N; i++)
	{
		for (long j = 0; j < 100010; j++)
		{
			if (j - v[i] >= 0)
			{
				dp[i+1][j] = min(dp[i+1][j], dp[i][j - v[i]] + w[i]);
			}
			dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
		}
	}
	long res = 0;
	for (long j = 0; j < V; j++){
		if(dp[N][j] <= W) res = j;
	}

	printf("%ld", res);
	return 0;
}


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

using namespace std;

void hawawa()
{
	int n, t;
	int mn = -1;
	long long mx = 0;
	int cnt = 0, cnt2 = 0, mncnt = 0, mxcnt = 0;
	cin >> n >> t;
	t /= 2;
	vector<int> a(n);
	int ans = 0;
	for (auto&& i : a) {
		cin >> i;
		if (mn == -1) mn = i;
		if (mn == i) {
			mncnt++;
		} else if (mn > i) {
			ans += min(mncnt, mxcnt);
			mncnt = 1;
			mxcnt = 0;
			mn = i;
		}
		i -= mn;
		if (mx < i) {
			mxcnt = 1;
			mx = i;
			ans = 0;
		}
		else if (mx == i) {
			mxcnt++;
		}
	}
	ans += min(mncnt, mxcnt);
	cout << ans << "\n";
}

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


Measured memory_bytes: 640
N, K = map(int, input().split())

A = list(map(int, input().split()))

L = []
L.append(1)
f = 1
memo = [-1] * N
memo[0] = 0
cnt = 1

while 1:
    L.append(A[f-1])
    f = A[f-1]
    if memo[f-1] != -1:
        loop = cnt - memo[f-1]
        break
    memo[f-1] = cnt
    cnt += 1

#print(L)
#print(loop)
NL = L[-(loop+1):-1]
#print(NL)

if K <= (len(L) - 1) - loop:
    print(L[K])
else:
    K -= (len(L) - 1) - loop
    a = K % len(NL)
    print(NL[a])


Measured memory_bytes: 32380
#include <bits/stdc++.h>
#define int long long
#define P(x) cout << x << endl
#define D(x) P(#x << ": " << x)
#define F(i,n) for (int i=0; i<(int)(n); i++)
#define DEC(i,n) for (int i=(int)(n); --i>=0;)
#define $(s) (int)((s).size())
#define ALL(v) v.begin(), v.end()
#define V vector
#define pb push_back
using namespace std;
void MI(int &a, int v) {a = min(a,v);}
void MA(int &a, int v) {a = max(a,v);}

int cost(int a[], int n, int parity) {
    int sum=0, c=0;
    F(i,n) {
        sum += a[i];
        //D(sum);
        if ((i+parity) % 2) {
            if (sum <= 0) {
                //P("too small");
                int incr = 1-sum;
                //D(incr);
                sum += incr;
                c += incr;
            }
        } else {
            if (sum >= 0) {
                //P("too large");
                int decr = sum+1;
                //D(decr);
                sum -= decr;
                c += decr;
            }
        }
    }
    //D(c);
    return c;
}

signed main() {
    int n; cin>>n;
    int a[n];
    F(i,n) cin>>a[i];
    P(min(cost(a,n,0), cost(a,n,1)));
}

Measured memory_bytes: 1024
use proconio::fastout;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
use std::collections::HashMap;

#[fastout]
fn main() {
    input! {
        n: usize,
        a: [usize; n],
        q: usize,
    }
    let mut ans = a.iter().sum::<usize>();
    let mut cnt: HashMap<usize, usize> = a.into_iter().fold(HashMap::new(), |mut acc, ai| {
        *acc.entry(ai).or_insert(0) += 1;
        acc
    });

    for _ in 0..q {
        input! {
            bi: usize,
            ci: usize,
        }
        let n = match cnt.remove(&bi) {
            Some(x) => x,
            None => 0,
        };
        *cnt.entry(ci).or_insert(0) += n;
        let diff = ci as isize - bi as isize;
        if diff.is_positive() {
            ans += diff as usize * n;
        } else {
            ans -= diff.abs() as usize * n;
        }
        println!("{}", ans);
    }
}


Measured memory_bytes: 7940
//Bokann ga bokka--nn!!
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int val[10005];
int f[15][10005];
int a,b;
int main(){
	while(1)
	{
		cin >> a >>b;
		if(!a) return 0;
		memset(val,0,sizeof(val));
		
		for(int i=0;i<a;i++)
		{
			for(int j=0;j<b;j++)
			{
			
				cin >> f[i][j];
				val[j]+=1-f[i][j];
			}
		}
		int ret=0;
		for(int i=0;i<(1<<a);i++)
		{
		int res=0;
			bool use[15]={};
			for(int j=0;j<a;j++)
			{
				if(((i>>j) &1))
				{
					use[j]=1;
				}
			}
			
			for(int j=0;j<a;j++)
			{
				if(!use[j]) continue;
				for(int k=0;k<b;k++)
				{
					val[k]+=2*f[j][k]-1;
				}
			}
			for(int k=0;k<b;k++)
			{
				res+=max(val[k],a-val[k]);
			}
			for(int j=0;j<a;j++)
			{
				if(!use[j]) continue;
				for(int k=0;k<b;k++)
				{
					val[k]-=2*f[j][k]-1;
				}
			}
			ret=max(ret,res);
		}
		cout << ret << endl;
	}
}

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

struct RMQ {
    int N, aN;
    vector<int> V;
    void init(int n) {
        aN = n;
        N = 1; while (N < n) N *= 2;
        V.assign(N * 2, aN);
    }
    void upd(int p,int v) {
        p += N; V[p] = min(V[p], v);
        while (p >= 1) {
            p /= 2;
            V[p] = min(V[p * 2], V[p * 2 + 1]);
        }
    }
    int query(int l, int r, int a = 0, int b = 0, int i = -1) {
        if (i == -1) { a = 0; b = N; i = 1; }
        if (r <= a || b <= l) return aN;
        if (l <= a && b <= r) return V[i];
        int q1 = query(l, r, a, (a + b) / 2, i * 2);
        int q2 = query(l, r, (a + b) / 2, b, i * 2 + 1);
        return min(q1, q2);
    }
    int find(int v, int w = 1000000000, int a = 0, int b = 0, int i = -1) {
        if (i == -1) { a = 0; b = N; i = 1; }
        if (!(V[i] <= v)) return aN;
        if (b - a == 1) return a;
        int x = find(v, w, a, (a + b) / 2, i * 2);
        if (x != aN) return x;
        return find(v, min(w, V[i * 2]), (a + b) / 2, b, i * 2 + 1);
    }
};

int main() {
    int N, Q; cin >> N >> Q; N -= 2;
    RMQ X, Y;
    X.init(N); Y.init(N);
    LL ans = LL(N) * N;
    while (Q--) {
        int c, x; cin >> c >> x; x -= 2; x = N - 1 - x;
        if (c == 1) {
            int p = X.query(0, x + 1);
            ans -= p;
            Y.upd(N - p, N - 1 - x);
        }
        if (c == 2) {
            int p = Y.query(0, x + 1);
            ans -= p;
            X.upd(N - p, N - 1 - x);
        }
    }
    cout << ans << endl;
    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int n;
    cin>>n;
    int res = 10000;
    res-=n;
    res%=1000;
    cout<<res<<"\n";
    return 0;
}


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

int min(int p, int q) {
	if (p < q) {
		return p;
	}else{
		return q;
	}
}

const int INF = 1001001001;

int main() {
	int n, m;
	int x;
	cin >> n >> m >> x;
	vector <int> c(n);
	int a[n][m];

	for (int i = 0; i < n; i++) {
		cin >> c.at(i);
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}

	int ans = INF;

	for (int i = 0; i < 1 << n; i++) {
		int cost = 0;
		vector <int> d(m);
		for (int j = 0; j < n; j++) {
			if (i >> j & 1) {
				cost += c[j];
				for (int k = 0; k < m; k++) {
					d[k] += a[j][k];
				}
			}
		}
		bool ok = true;
		for (int i = 0; i < m; i++) {
			if (d[i] < x) {
				ok = false;
			}
		}
		if (ok) {
			ans = min(ans, cost);
		}
	}
	if (ans == INF) {
		cout << -1 << endl;
	}else {
		cout << ans << endl;
	}
	return 0;
}

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

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;

int N, K;
map<int, int> A;
vector<pair<int, int>> B;

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> K;
	for(int i=0; i<N; i++){
		int v;
		cin >> v;
		if(A.count(v)==0){
			A[v] = 1;
		}
		else{
			A[v]++;
		}
	}

	for(auto itr = A.begin(); itr != A.end(); itr++){
		int k = itr->first;
		int v = itr->second;
		B.push_back(make_pair(v, k));
	}
	sort(B.begin(), B.end());

	int ans = 0;
	if(B.size() <= K){
		ans = 0;
	}
	else{
		for(int i=0; i<B.size() - K; i++){
			ans += B[i].first;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 11764
package main

import (
	"fmt"
	"strings"
)

func main() {
	var s string
	fmt.Scan(&s)

	results := strings.Split(s, "")

	won := 0
	for _, result := range results {
		if result == "o" {
			won++
		}
	}

	if won+(15-len(results)) >= 8 {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
#define V vector<int>
#define S set<int>
#define itn int
bool dbg = false;
void solve() {
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int ans = 0, a, b;
    cin >> a >> b;
    if (a == 1 && b == 1) {
        ans = 1000000;
    } else {
        ans += max((4 - a) * 100000, 0ll);
        ans += max((4 - b) * 100000, 0ll);
    }
    cout << ans << endl;
    solve();
    return 0;
}


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

int main()
{
    int k;
    int a[4];
    int s=0;
    for(int i=0;i<3;i++)cin>>a[i];
    sort(a,a+3, greater<int>());
    cin>>k;
    //a[0]=a[0]*k*2;
    for(int i=0;i<k;i++)
    {
        a[0]=a[0]*2;
    }
    for(int i=0;i<3;i++)s+=a[i];
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
#include<list>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {1, 1, 0, -1, -1, 0};
int dx[] = {1, 0, -1, -1, 0, 1};
#define ceil(a, b) a / b + !!(a % b)

int N;
int t[16 + 1][16 + 1];
int dp[(1 << 16)][16 + 1];
int rec(int bit, int v) {
    /*
     cout << endl;
     cout << bit << " " << v << endl;
     */
    //if reached, retrurn self
    if (dp[bit][v] != -1) return dp[bit][v];
    //if 1 bit, return 0 fin
    if (bit == (1 << v)) return dp[bit][v] = t[v][0];
    int res = inf;
    int prev_bit = bit & ~(1 << v);
    int tmp = prev_bit;
    int c = 0;
    while (tmp) {
        c += tmp % 2;
        tmp /= 2;
    }
    int val = t[v][0];
    //if (bit == 3 && v == 1) cout << "46 " << prev_bit << endl;
    rep(u, N) {
        if (!(prev_bit & (1 << u))) continue;
        //if (bit == 3 && v == 1) cout << "49u " << u << endl;
        val = min(val, t[v][u + 1]);
        //if (bit == 3 && v == 1) cout << "51t " << t[v][u + 1] << endl;
    }
    rep(u, N) {
        if (!(prev_bit & (1 << u))) continue;
        //if (bit == 3 && v == 1) cout << "55u " << u << " " << rec(prev_bit, u) << endl;
        if (res > rec(prev_bit, u) + val) {
            res = rec(prev_bit, u) + val;
        }
    }
    return dp[bit][v] = res;
}
bool solve() {
    cin >> N;
    if (N == 0) return 0;
    rep(i, N) rep(j, N + 1) {
        cin >> t[i][j];
    }
    int res = inf;
    rep(bit, (1 << 16)) rep(v, 16) dp[bit][v] = -1;
    rep(v, N) {
        //cout << v << " " << rec((1 << N) - 1, v) << endl;
        if (res > rec((1 << N) - 1, v)) {
            res = rec((1 << N) - 1, v);
        }
    }
    //rep(bit, (1 << N)) {rep(v, N) cout << dp[bit][v] << " "; cout << endl;}
    cout << res << endl;
    return 1;
}
int main() {
    while (solve()) {
        
    }
}





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

struct Card{ char suit,value; };

void bubble(struct Card A[], int N) {
	for (int i = 0;i < N;i++) {
		for (int j = N - 1;j >= i + 1;j--) {
			if (A[j].value < A[j - 1].value) {
				Card t = A[j];
				A[j] = A[j - 1];
				A[j - 1] = t;
			}
		}
	}
}

void selection(struct Card A[], int N) {
	for (int i = 0;i < N;i++) {
		int minj = i;
		for (int j = i;j < N;j++) {
			if (A[j].value < A[minj].value)
				minj = j;
		}
		Card t = A[i];
		A[i] = A[minj];
		A[minj] = t;
	}
}
void print(struct Card A[], int N) {
	for (int i = 0;i < N;i++) {
		if (i > 0)cout << " ";
		cout << A[i].suit << A[i].value;
	}
	cout << endl;
}
//バブルソートと選択ソートの結果を比較
bool isStable(struct Card C1[], struct Card C2[], int N) {
	for (int i = 0;i < N;i++) {
		if (C1[i].suit != C2[i].suit)return false;
	}
	return true;
}

int main() {
	Card C1[100], C2[100];
	int N;
	char ch;
	cin >> N;

	for (int i = 0;i < N;i++) {
		cin >> C1[i].suit >> C1[i].value;
	}

	for (int i = 0;i < N;i++)C2[i] = C1[i];

	bubble(C1, N);
	selection(C2, N);

	print(C1, N);
	cout << "Stable" << endl;
	print(C2, N);
	if (isStable(C1, C2, N)) {
		cout << "Stable" << endl;
	}
	else {
		cout << "Not stable" << endl;
	}
	return 0;
}



Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mod 1000000007
//#define int long long int
unordered_map<string, bool>mp;
string factorial(long long n)
{
	if (n > 1000) {
		cout << " Integer Overflow"
		     << endl;
		return "";
	}

	long long counter;
	long double sum = 0;

	// Base case
	if (n == 0)
		return "1";

	// Calculate the sum of
	// logarithmic values

	for (counter = 1; counter <= n;
	        counter++) {
		sum = sum + log(counter);
	}
	cout << sum << endl;

	// Number becomes too big to hold in
	// unsigned long integers.
	// Hence converted to string
	// Answer is sometimes under
	// estimated due to floating point
	// operations so round() is used
	string result
	    = to_string(round(exp(sum)));

	return result;
}
bool solve(string a, string b)
{
	if (a.compare(b) == 0)
		return true;

	if (a.length() <= 1)  //if a ki length is 1 it means a!=b(becz we checked for equality above so it returns false
		return false;

	string key = a;
	key.push_back(' ');
	key.append(b);
	if (mp.find(key) != mp.end())
		return mp[key];

	int n = a.length();
	bool flag = false;

	for (int i = 1; i < n; i++)
	{
		bool cond_1 = false, cond_2 = false;
		if ((solve(a.substr(0, i), b.substr(n - i, i)) == true) && (solve(a.substr(i, n - i), b.substr(0, n - i)) == true))
			cond_1 = true;

		if ((solve(a.substr(0, i), b.substr(0, i)) == true) && (solve(a.substr(i, n - i), b.substr(i, n - i)) == true))
			cond_2 = true;

		if (cond_1 || cond_2)
		{
			flag = true;
			break;
		}
	}
	return mp[key] = flag;
}
int result(int n, unordered_map<int, int>&m)
{
	if (n <= 2)
		return 1;
	if (m.find(n) != m.end())
		return m[n];

	int ans = result(n - 1, m) + result(n - 2, m);
	return m[n] = ans;

}
int32_t main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin >> s;
	int a = s.size();
	if (s[a - 1] == 's')
	{
		s += 'e';
		s += 's';
	}
	else
	{
		s += 's';
	}
	cout << s;
	return 0;
}

Measured memory_bytes: 3692
#include<bits/stdc++.h>
#define ll long long int
#define loop(i,a,b) for(i=a;i<b;i++)
#define mod 1000000007
#define pb push_back
#define lim 2750131
using namespace std;
int main()
{ll i,ans=0,k;
	char s[101];
	cin>>s;
	cin>>k;
    vector<ll> v;
	ll n=strlen(s);
    ll curr=1;
	loop(i,1,n)
	{if(s[i]!=s[i-1])
		{v.pb(curr);
			curr=1;}
			else
				curr++;}
			v.pb(curr);
          if(v.size()==1)
          ans=(k*n)/2;else{
			loop(i,0,v.size())
			ans+=v[i]/2;
			ans*=k;
			if(s[0]==s[n-1] && (v[0]*v.back())%2)
				ans+=k-1;}
			cout<<ans<<endl;
			return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
#define ALL(x) (x).begin(),(x).end()

int main(){
	string S;
	cin >> S;
	int cnt = 1;
	string now = ""s + S[0];
	int i = 1;
	while(i < S.size()) {
		string tmp = ""s + S[i];
		if(now == tmp) {
			if(i+1 < S.size()) {
				tmp += S[i+1];
				now = tmp;
				i += 2;
				cnt++;
			} else {
				break;
			}
		} else {
			cnt++;
			now = tmp;
			i++;
		}
	}
	cout << cnt << endl;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
#define eps 1e-9
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int main(){
    //~ freopen("file.in", "r", stdin);
    long double n;
    cin>>n;
	for(int i=1;i<=3500;i++)
		for(int j=1;j<=3500;j++){
			long double ii=i;
			long double jj=j;
			long double val=4.0/n-1.0/ii-1/jj;
			long double k=1.0/val;
			if(k<0)
				continue;
			if(k-int(k)<eps){
				cout<<i<<" "<<j<<" "<<int(k)<<endl;
				return 0;
			}
		}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <time.h>
#define ll long long
#define double long double
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define ALL(V) ((V).begin(),(V).end())
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 2019
#define MAX 5100000
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
using namespace std;

ll power(ll a,ll b){
  ll res=1;
  while(b>0){
    if(b&1) res=res*a%MOD;
    a=a*a%MOD;
    b>>=1;
  }
  return res;
}

int main(){
  ll ans=0;
  string S;
  cin>>S;
  
  ll X[200010];
  REP(i,200010) X[i]=0;
  
  for(int i=1; i<=S.size(); ++i){
    X[i]=(X[i-1]+(S.at(S.size()-i)-'0')*power(10,i-1))%MOD;
  }
  
  ll ANS[2019];
  REP(i,2019) ANS[i]=0;
  
  for(int i=0; i<=S.size(); ++i){
    ANS[X[i]]++;
  }
  
  REP(i,2019)  if(ANS[i]>1) ans+=ANS[i]*(ANS[i]-1)/2;
  
  
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 5336
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int INF = 1 << 30;
const double EPS = 1e-10;
const double pi = 3.14159265359;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------

int n;
int t[111];
int m;

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

	cin >> m;
	for (int i = 0;i < m;i++) {
		int p, x;
		cin >> p >> x;
		cout << sum - t[p] + x << endl;
	}

	return 0;
}


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

using namespace std;

const int maxn = 5e5 + 5;
const int inf = 0x3f3f3f3f;

int n, m, head[maxn], cnt, dis[maxn], vis[maxn];
struct Graph{int to, nt, C;}e[maxn << 1];
struct Node {
	int dis, u;
	Node(int Dis = 0, int U = 0){dis = Dis; u = U;}
	bool operator < (const Node &t) const { return dis == t.dis ? u < t.u : dis < t.dis; }
};
set<int>S[maxn];
priority_queue<Node>q;

inline int read() {
	char ch = getchar(); int u = 0, f = 1;
	while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
	while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline void ini(int x, int y, int C) {e[++cnt] = (Graph){y, head[x], C}; head[x] = cnt;}

inline void Dij(int s) {
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	dis[s] = 0; q.push(Node(dis[s], s));
	while(!q.empty()) {
		int now = q.top().u; q.pop();
		if(vis[now])continue; vis[now] = 1;
		for(register int i = head[now]; i; i = e[i].nt) {
			int v = e[i].to, w;
			w = S[now].count(e[i].C) ? 0 : 1;
			if(dis[v] > dis[now] + w) {
				dis[v] = dis[now] + w;
				q.push(Node(-dis[v], v));
				S[v].clear();
				S[v].insert(e[i].C);
			}
			else if(dis[v] == dis[now] + w) S[v].insert(e[i].C);
		}
	}
}

int main(){
	n = read(); m = read();
	for(register int i = 1; i <= m; i++){
		int x = read(), y = read(), C = read();
		ini(x, y, C); ini(y, x, C);
	}
	Dij(1);
	cout << (dis[n] == inf ? -1 : dis[n]);
	return 0;
}


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

int main() {
	map<int, int> mp;
    int n;
    cin >> n;
	for (int i = 0; i < n; i++) {
		int value;
		cin >> value;
		mp[value] = i + 1;
	}

	for (auto it = mp.begin(); it != mp.end(); it++) {
		cout << it->second << " ";
	}
	cout << "\n";
	return 0;
}

Measured memory_bytes: 5504
#include <bits/stdc++.h>
using namespace std;
// long long m=1000000007;
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    long long t,m,n,i=5,j,k,temp,sum=0,flag=0,count=0,mi,x,y;
    cin >> n >> m;
    // if(n==m) cout << "Yes";
    // else cout << "No";
    if(n<=m){
        for(i=0;i<m;i++) cout << n;
    }
    else for(i=0;i<n;i++) cout << m;
}

Measured memory_bytes: 256
import copy
n=int(input())
alis=[]
for i in range(n):
	a,b=map(str,input().split())
	alis.append([a,int(b)])
blis=copy.copy(alis)
blis.sort(key=lambda blis:(blis[0],-blis[1]))
for i in blis:
	print(alis.index(i)+1)


Measured memory_bytes: 3444
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>

using namespace std;
# define ll long long
# define int long long  //comment it out when MLE
//# define endl "\n"
#define gok ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//# define m 163577857
//# define MOD 163577857
# define pi acos(-1)
# define fi first
# define se second
#define REP(i,n) for (int i = 1; i <= n; i++)

const ll mod = 1000000007;
const int K = 2;
//typedef vector<vector<int> > matrix;
int add(int a, int b,int mod) {
    a%=mod;
    b%=mod;
	a += b;
	if (a >= mod) a -= mod;
	if(a<0)
    {
        a += mod;
        a %= mod;
    }
	return a;
}

int mul(ll a, int b,int mod) {
    a%=mod;
    b%=mod;
	a *= b;
	return a % mod;
}
int po(int a,int b,int mod)
{
    if(b==0)
        return 1;
    if(b%2==0)
        return po(mul(a,a,mod),b/2,mod);
    return mul(a,po(mul(a,a,mod),(b-1)/2,mod),mod);
}


ll fact[1000003];
ll inv[1000003];

void fact0()
{
	int i,j;
	fact[0]=1;
	for(i=1;i<=200000;i++)
	{
		fact[i]=i*fact[i-1]%mod;
	}
	inv[0]=1;
	inv[1]=1;
	ll p=mod;
	for (i=2; i<=200000; i++)
		inv[i] = (p - (p/i) * inv[p%i] % p) % p;

	for(i=2;i<=200000;i++)
	{
		inv[i]*=inv[i-1];
		inv[i]%=mod;
	}
}

signed main()
{
    gok
   //fact0();
   string s;
   cin>>s;
   if(s=="ABC")
    cout<<"ARC";
   else
    cout<<"ABC";

















    return 0;
    }


Measured memory_bytes: 3640
S = gets.chomp

diff_min = 9999999999
for i in 0..(S.length - 3)
  diff = [(753 - S[i..(i+2)].to_i).abs, (S[i..(i+2)].to_i - 753).abs].min
  diff_min = diff if diff < diff_min
end
puts diff_min


Measured memory_bytes: 1788
N = int(input())
h = list(map(int, input().split()))

l = 0
flag = 1
count = 0
while l < N-1:
  if h[l] == 0:
    l += 1
  elif h[l] != 0:
    r = l+1
    while h[r] != 0:
      r += 1
      if r == N:
        break
    for k in range(l,r):
      h[k] -= 1
    count += 1
print(count+h[N-1])

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

using namespace std;

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

const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

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;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()

int main(){
    int N;
    cin>>N;
    if(N%2==1){
        N=(N-1)/2;
        cout<<N+1<<endl;
    }else{
        cout<<N/2<<endl;
    }

    return 0;
}

//a=97,z=122

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i, n) for (ll i=0;i<n;i++)
#define ll long long
#define llc(n) ll n; cin >> n;
using namespace std;
int main() {
  llc(n)
  string s,t="Yes";
  cin >> s;
  if (n%2==1) t="No";
  else {
    r(i, n/2) {
      if (s.at(i)!=s.at(n/2+i)) t="No";
    }
  }
  cout << t << endl;
  return 0;
}

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

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

ll GCD(ll a, ll b)
{
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}

ll LCM(ll a, ll b)
{
    return a * b / GCD(a, b);
}

ll next_combination(ll sub)
{
    ll x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1LL) | y;
}

map<ll, int> prime_factor(ll n)
{
    map<ll, int> ret;
    for (ll i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (true)
    {
        ll n, m;
        cin >> n >> m;
        if (n == 0 && m == 0)
        {
            return 0;
        }
        vector<ll> p(m);
        set<ll> se;
        for (ll i = 0; i < m; i++)
        {
            cin >> p[i];
            auto mp = prime_factor(p[i]);
            if (p[i] == 1)
            {
                se.insert(1);
            }
            for (auto hoge : mp)
            {
                se.insert(hoge.first);
            }
        }
        vector<ll> pp;
        for (auto hoge : se)
        {
            // cout << hoge << endl;
            pp.push_back(hoge);
        }
        ll sz = pp.size();
        ll ans = 0;
        ll ans2 = 0;
        // ΣmCk (1<=k<=m)
        for (ll k = 1; k <= sz; k++)
        {
            ll tmp = 0;
            ll tmp2 = 0;
            for (ll bit = (1LL << k) - 1LL; bit < (1LL << sz); bit = next_combination(bit))
            {
                ll rec = 1;
                for (ll i = 0; i < sz; i++)
                {
                    if (bit & (1LL << i))
                    {
                        rec = LCM(rec, pp[i]);
                    }
                }
                ll cnt = n / rec;
                tmp2 += cnt;
                ll sum = (rec + rec * cnt) * cnt / 2;
                tmp += sum;
            }
            ans += tmp * (k % 2 ? 1 : -1);
            ans2 += tmp2 * (k % 2 ? 1 : -1);
        }
        cout << fixed << setprecision(15);
        if (n - ans2 == 0)
        {
            cout << 0.0 << endl;
            continue;
        }
        double res = (double)((1 + n) * n / 2 - ans) / (n - ans2);
        cout << res << endl;
    }
}


Measured memory_bytes: 3248
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <utility>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int iinf = 1 << 29;
const long long linf = 1ll << 61;

#define nnm(x, y) (((y) + (x) % (y)) % (y))
template<typename T> inline T gcd(T x, T y) { if(x < y) swap(x, y); T mod = x % y; if(mod == 0) return y; return gcd(y, mod); }
template<typename T> inline T lmc(T x, T y) { return x / gcd(x, y) * y; }

bool checked[100000];
int N, M;
vector<int> edge[100000];

ll f(int n)
{
	return (ll)n * (ll)(n - 1) / 2;
}

int main(int argc, char* argv[])
{
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		a--; b--;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	queue<int> q;
	q.push(0);
	checked[0] = true;
	int k = 0;
	while (!q.empty()) {
		int v = q.front(); q.pop();
		k++;
		for (int i = 0; i < (int)edge[v].size(); i++) {
			int n = edge[v][i];
			if (checked[n]) continue;
			checked[n] = true;
			q.push(n);
		}
	}

	q.push(1);
	checked[1] = true;
	int l = 0;
	while (!q.empty()) {
		int v = q.front(); q.pop();
		l++;
		for (int i = 0; i < (int)edge[v].size(); i++) {
			int n = edge[v][i];
			if (checked[n]) continue;
			checked[n] = true;
			q.push(n);
		}
	}

	int r = N - k - l;

	ll ans = f(k) + f(l) + f(r) + (ll)r * (ll)max(k, l) - M;
	printf("%lld\n", ans);

	return 0;
}


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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    string s;
    map<string,int> map;
    int mx=0;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        map[s]++;
        if(map[s]> mx)
            mx=map[s];
    }
    for(auto x : map)
    if(mx==x.second)
        cout << x.first <<  endl;
    return 0;
}


Measured memory_bytes: 18688
#include<bits/stdc++.h>
using namespace std;
//#define int long long
int abs(int a,int b){
  int c=max(a,b)-min(a,b);
  return c;
}
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string a;
  int b=1;
  cin>>a;
  for(int i=1;i<4;i++){
    if(a[i-1]==a[i]) b=0;
  }
  if(b) cout<<"Good";
  else cout<<"Bad";
  cout<<"\n";
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int m, f, r;
    while(1){
        scanf("%d %d %d", &m, &f, &r);
        if(m == -1 && f == -1 && r == -1) break;

        if(m == -1 || f == -1) printf("F\n");
        else if((m+f) >= 80) printf("A\n");
        else if((m+f) >= 65 && (m+f) < 80) printf("B\n");
        else if((m+f) >= 50 && (m+f) < 65) printf("C\n");
        else if((m+f) >= 30 && (m+f) < 50){
            if (r == -1) printf("D\n");
            else if(r >= 50) printf("C\n");
            else printf("D\n");
        }
        else if((m+f) < 30) printf("F\n");
    }
}



Measured memory_bytes: 2052
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <tuple>
#include <algorithm>

using namespace std;

int main(){

    int N;
    cin >> N;
    N %= 10;

    switch(N){
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
        cout << "hon" << endl;
        break;
    case 0:
    case 1:
    case 6:
    case 8:
        cout << "pon" << endl;
        break;
    case 3:
        cout << "bon" << endl;
        break;
    default:
        break;
    }

    return 0;
}


Measured memory_bytes: 3636
n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
for i in range(n):
  h[i]=t-h[i]*0.006
d=abs(a-h[0])
c=1
for i in range(1,n):
  if d>abs(a-h[i]):
    c=i+1
    d=abs(a-h[i])
print(c)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n,m,x;
  cin>>n>>m>>x;
  vector<Int> a(m);
  for(Int i=0;i<m;i++) cin>>a[i];

  vector<Int> v(n,0);
  for(Int i=0;i<m;i++) v[a[i]]=1;

  Int s=0,t=0;
  for(Int i=0;i<x;i++) s+=v[i];
  for(Int i=x;i<n;i++) t+=v[i];

  cout<<min(s,t)<<endl;
  return 0;
}


Measured memory_bytes: 256
#define D(x) cout << #x " = " << x << endl
#define DD(x, y) cout << "(" #x ", " #y ") = (" << x << ", " << y << ")" << endl
#define DDD(x, y, z) cout << "(" #x ", " #y ", " #z ") = (" << x << ", " << y << ", " << z << ")" << endl
#define DV(v) for (auto __macro_vi : v){ cout << __macro_vi << " ";} cout << endl;
#define DA(a, n) for (int __macro_i = 0; __macro_i < n; ++__macro_i) { cout << a[__macro_i] << " "; } cout << endl;
#define REP(i, n) for (int i = 0; i < n; ++i)
#define ALL(v) (v).begin(), (v).end()
#include<iostream>
#include<vector>
#include<cassert>
#include<cmath>

using namespace std;

using ll = long long;
const int MOD = 1000000007;
ll dp[100002];
bool broken[100002];
int n, m;
int main()
{
    cin >> n >> m;
    fill(broken, broken + n + 1, false);
    fill(dp, dp + n + 1, 0);
    dp[0] = 1;
    REP(i, m) {
        int ai;
        cin >> ai;
        broken[ai] = true;
    }
    for (int i = 1; i <= n; ++i) {
        dp[i] = 0;
        if (broken[i]) continue;
        if (i - 2 >= 0) dp[i] = (dp[i] + dp[i - 2]) % MOD;
        dp[i] = (dp[i] + dp[i - 1]) % MOD;
    }
    cout << dp[n] << endl;
    // DA(dp, 10);
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b;
  string s;
  string ans = "Yes";
  cin >> a >> b >> s;
  
  if (s[a] != '-'){
    ans = "No";
  }
  for (int i=0;i<a+b+1;i++){
    if (s[i] == '-' && i != a){
      ans = "No";
    }
  }
  cout << ans << endl;
}

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

using namespace std;
using ll = long long;

int main() {
  ll n;
  cin >> n;

  if (n % 2 == 1) {
    cout << 0 << endl;
    return EXIT_SUCCESS;
  }

  ll ans = 0;
  ll b = 10;
  while (b <= 2e18) {
    ans += n / b;
    b *= 5;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3648
rooms = Array.new(4) { Array.new(3) { Array.new(10, 0) } }

num = $stdin.readline.to_i
(1..num).each do |i|
  b, f, r, v = $stdin.readline.split(" ").map {|s| s.to_i}

  rooms[b-1][f-1][r-1] += v
end

rooms.each_with_index do |building, i|
  building.each do |floor|
    floor.each do |room|
      print " #{room}"
    end
    puts
  end
  puts "####################" unless i == rooms.size - 1
end



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

int main() {
    ll L,R; cin >> L >> R; ll ans=20000;
    if(R-L>=2019)cout << 0 << endl;
    else{
    for(ll i=L;i<R;i++){
      for(ll j=i+1;j<=R;j++){
        ans=min(ans,((i%2019)*(j%2019))%2019);
      }
    }
      cout << ans << endl;
    }
        
    return 0;
}



Measured memory_bytes: 256