akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
using namespace std;
int N, A, B, C;
vector<int> l(8);

int dfs(int a_length, int b_length, int c_length, int a_count, int b_count, int c_count, int depth)
{
  if (depth == N)
  {
    if ((a_count + b_count + c_count) < 3)
      return INT32_MAX;
    if (a_length == 0 || b_length == 0 || c_length == 0)
      return INT32_MAX;
    return abs(A - a_length) + abs(B - b_length) + abs(C - c_length) + (a_count - 1) * 10 + (b_count - 1) * 10 + (c_count - 1) * 10;
  }
  int res1 = dfs(a_length + l[depth], b_length, c_length, a_count + 1, b_count, c_count, depth + 1);
  int res2 = dfs(a_length, b_length + l[depth], c_length, a_count, b_count + 1, c_count, depth + 1);
  int res3 = dfs(a_length, b_length, c_length + l[depth], a_count, b_count, c_count + 1, depth + 1);
  int res4 = dfs(a_length, b_length, c_length, a_count, b_count, c_count, depth + 1);
  return min(min(res1, res2), min(res3, res4));
}

int main()
{
  cin >> N >> A >> B >> C;
  for (int i = 0; i < N; i++)
    cin >> l[i];
  int ans = dfs(0, 0, 0, 0, 0, 0, 0);
  cout << ans << endl;
  return 0;
}

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

int main(){
    ll N;
    cin >> N;
    ll ans = 1;
    for(ll i=1;i<=N;i++){
        ans *= i;
        ans %= MOD;
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
int n,m,q,lfx,lfy,rix,riy;
char a[maxn][maxn];
int sumn[maxn][maxn],suml[maxn][maxn],sumh[maxn][maxn];
int read()
{
	int ch=0,x=0;while(ch=getchar(),ch<'0'||ch>'9');
	while(x=x*10+ch-48,ch=getchar(),ch>='0'&&ch<='9');
	return x;
}
int main()
{
	n=read();m=read();q=read();
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	cin>>a[i][j];
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		sumn[i][j]=sumn[i-1][j]+sumn[i][j-1]-sumn[i-1][j-1]+(a[i][j]=='1');
		sumh[i][j]=sumh[i-1][j]+sumh[i][j-1]-sumh[i-1][j-1]+(a[i][j]=='1'&&a[i-1][j]=='1');
		suml[i][j]=suml[i-1][j]+suml[i][j-1]-suml[i-1][j-1]+(a[i][j]=='1'&&a[i][j-1]=='1');
	}
	for(int i=1;i<=q;i++)
	{
		lfx=read();lfy=read();rix=read();riy=read();
		int N=sumn[rix][riy]-sumn[rix][lfy-1]-sumn[lfx-1][riy]+sumn[lfx-1][lfy-1];
		int M=suml[rix][riy]-suml[rix][lfy]-suml[lfx-1][riy]+suml[lfx-1][lfy]+sumh[rix][riy]-sumh[lfx][riy]-sumh[rix][lfy-1]+sumh[lfx][lfy-1];
		printf("%d\n",N-M);
	}
	return 0;
}

Measured memory_bytes: 52864
#include <iostream>
#include <string>
#include <algorithm>

#include <vector>
#include <cmath>

using namespace std;

#define int long long

int dp[101][3][2]={};

inline int che(int ret)
{
    return ret >= 0 ? ret : 0;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int ans = 0;
    int day=0,dec=0;
    cin >> day>>dec;
    
    int ind,ink;
    
    for(int i=0;i<3;++i)
        dp[0][i][0] = 1;
    
    for(int i=0;i<dec;++i)
    {
        cin >> ind >> ink;
        ink--;
        ind--;
        for(int k=0;k<3;++k)
        {
            if(k!=ink)
            {
                dp[ind][k][0] = dp[ind][k][1] = -1;
            }
        }
    }
    //dp
    for(int i=0;i<day;++i)
    {
        for(int k = 0;k<3;++k)
        {
        //    cout << i <<":" <<k << " "<<dp[i][k][0] << " " << dp[i][k][1] <<endl;
            if(dp[i][k][0]!=-1)
            {
                dp[i][k][0] %= 10000;
                dp[i][k][1] %= 10000;
                
                if(dp[i+1][(k+1)%3][0] >= 0) dp[i+1][(k+1)%3][0] += dp[i][k][0];
                if(dp[i+1][(k+2)%3][0] >= 0) dp[i+1][(k+2)%3][0] += dp[i][k][0];
                
                if(dp[i+1][k][1] >= 0) dp[i+1][k][1] += dp[i][k][0];
                
                if(dp[i+1][(k+1)%3][0] >= 0) dp[i+1][(k+1)%3][0] += dp[i][k][1];
                if(dp[i+1][(k+2)%3][0] >= 0) dp[i+1][(k+2)%3][0] += dp[i][k][1];

            }
        }
    }
    for(int i = 0;i< 3;++i)
    {
        for(int k = 0;k < 2;++k)
        {
            ans = (ans+che(dp[day-1][i][k]));
        }
    }
    cout << ans%10000 << endl;
    return 0;
}

Measured memory_bytes: 3180
n,y=map(int,input().split())
y=y/1000
ans=(-1,-1,-1)
for i in range(1+n):
    for j in range(n-i+1):
        if i*10+j*5+(n-i-j)==y and n-i-j>=0:
            ans=(i,j,n-i-j)
print(*ans)


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

int main(){
    int N,t;
    cin >> N;
    vector<pair<int, int> > A;
    REP(i,N){
        cin >> t;
        A.push_back(make_pair(t,i));
    }
    sort(A.begin(),A.end());
    int ans = 0;
    REP(i,N){
        if(i%2==0 && A[i].second%2==1){
            ans += 1;
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
	int i = 0;
	int a,b,r;
	string op;
	while (i == 0) {
		cin >> a >> op >> b;
		if (op == "?") {
			i = 1;
		}else{
			if (op == "+") {
				r = a + b;
			} else if (op == "-") {
				r = a - b;
			} else if (op == "*") {
				r = a * b;
			} else if (op == "/") {
				r = a / b;
			}
			cout << r << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3152
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <functional>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define REP(i, n) for (int i = 1; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000000;

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    vector<int> cnt(10, 0);
    ++cnt[A];
    ++cnt[B];
    ++cnt[C];
    if (cnt[5] == 2 && cnt[7] == 1) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}


Measured memory_bytes: 3620
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
# include <cstdlib>
# include <tuple>
# include <array>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using D = double;
constexpr int INF = 2147483647;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr double HDINF = 50000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_num(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define RALL(qpqpq)           (qpqpq).rbegin(),(qpqpq).rend()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define RFOR(i,tptpt,ypypy)  for(LL i=(tptpt);i>=(ypypy);i--)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

const int MOD = 1e9 + 7;

string t, b;
LL dp[101010];
int main() {
	cin >> t >> b;
	dp[0] = 1;
	REP(i, t.size()) {
		for (int j = b.size() - 1; j >= 0; j--) {
			if (t[i] == b[j]) {
				dp[j + 1] += dp[j];
				dp[j + 1] %= MOD;
			}
		}
	}
	cout << dp[b.size()] << endl;
}


Measured memory_bytes: 3236
#include <bits/stdc++.h>
#include <math.h>
#include <vector>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
/*vector<Type> v;
vector<Type> v();
vector<Type> v(n);
vector<Type> v(n, d);
vector<vector<Type>> vv;
vector<vector<Type>> vv();
vector<vector<Type>> vv(n);
vector<vector<Type>> vv(n, vector<Type>(m));
vector<vector<Type>> vv(n, vector<Type>(m, d));*/

int main() {
  int k,x;
  cin >> k>> x;
  if(500*k>=x){
    cout<<"Yes";
  }else{
    cout<<"No";
  }
  return 0;
}


Measured memory_bytes: 3636
import java.util.stream.*;
import java.io.*;

public class Main {

  static int n;
  static int[] a, ans;
  
  public static void main(String[] args) throws Exception {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String[] in = br.readLine().split(" ");
    n = Integer.parseInt(in[0]);

    in = br.readLine().split(" ");
    a = Stream.of(in).mapToInt(Integer::parseInt).toArray();

    br.close();

    ans = new int[n];

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

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

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

#define ll long long int
ll mod=1e9+7;

int main()
{
    /* Faster input ouput */
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);

    /* To read input from a file and output to a file */
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    
    ll t = 1;
    // cin >> t;
    while(t--)
    {        
        ll n,i,j;
        cin >> n;
        ll ans = n%1000;
        ans = (1000 - ans) % 1000;
        cout << ans << '\n';
    }
    
    return 0;
}

Measured memory_bytes: 3620
import java.util.*;
public class Main {
  public static void main(String[] args){

    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int C = sc.nextInt();
    int D = sc.nextInt();

    if ((A * B) < (C * D)) {
      System.out.println(C * D);
    } else {
      System.out.println(A * B);
    }

  }
}

Measured memory_bytes: 22612
from collections import Counter
N = int(input())
lis = ["".join(sorted(list(input()))) for _ in range(N)]
keys, values = zip(*Counter(lis).most_common())
values = list(filter(lambda x: x >= 2, values))

sums = 0
for k in values:
  sums += ((k - 1) * (k)) / 2
  
print(int(sums))

Measured memory_bytes: 25572
n = int(input())
h = list(map(int, input().split()))

cnt = 0
ans = 0

for i in range(n - 1):
    if h[i] >= h[i + 1]:
        cnt += 1
    else:
        if cnt > ans:
            ans = cnt
        cnt = 0

if cnt > ans:
    ans = cnt

print(ans)


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

int main() {
	int x; cin >> x;
	int tmp = x;
	int fx=0;
	while(tmp>0) {
		fx += tmp%10;
		tmp/=10;
	}
	if(x%fx==0) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 2147483647
#define inf 1000000007
#define SYOU(x) setprecision(x)
#define abs(x,y) (max(x,y)-min(x,y))
#define mp make_pair
#define fi first
#define se second
using namespace std;
int i[111100];
vector<pair<int ,int> > ii;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long a,b,c,d=1,e=1,f=0,g=1,h=1,j;
  string s,w;
  cin >>s>>w;
  if(s>w) cout <<'>'<<'\n';
  else{
    if(s<w) cout <<'<'<<'\n';
    else cout <<'='<<'\n';
  }
  return (0);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) x.begin(),x.end()
#define dmp(x) cerr<<#x<<":"<<x<<endl
typedef pair<int,int> P;
typedef pair<int,P> PP; 
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
const int MOD = 1e9+7;

signed main(){
  int n;
  cin>>n;
  cout<<3*n*n<<endl;
  return 0;
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/dp/tasks/dp_g

#include "algorithm"
#include "iostream"
#include "set"
#include "vector"
#define rep(i, from, to) for (ll i = from; i < (to); ++i)
using namespace std;
typedef long long ll;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T>
inline bool chmax(T& a, T b);
template <typename T>
inline bool chmin(T& a, T b);
void print_ints(vector<ll> v);
template <typename T>
void drop(T a);

VL ls;  // そのノードから出る最長パス
VVL edges;

ll get_longest(ll u) {
  if (ls[u] > 0) {
    return ls[u];
  }

  ll max = -1;

  for (auto v : edges[u]) {
    chmax(max, get_longest(v));
  }

  ll res = 1 + max;
  ls[u] = res;

  return res;
}

void solve() {
  ll N, M;
  cin >> N >> M;

  edges.assign(N, VL(0));

  rep(i, 0, M) {
    ll from, to;
    cin >> from >> to;
    from--;
    to--;
    edges[from].push_back(to);
  }

  ls.assign(N, -1);

  ll res = 0;
  rep(i, 0, N) { chmax(res, get_longest(i)); }

  cout << res << endl;
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

void print_ints(vector<ll> v) {
  rep(i, 0, v.size()) {
    if (i > 0) {
      cout << " ";
    }

    cout << v[i];
  }

  cout << endl;
}

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}


Measured memory_bytes: 8576
//include
//------------------------------------------
#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);
const LL MOD = 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;

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

	VI prime;
	for (int i = 2; i < 500; i++) {
		bool p = true;
		for (int j = 2; j < int(sqrt(i)) + 1; j++) {
			if(i % j == 0) {
				p = false;
			}
		}
		if (p) {
			prime.push_back(i);
		}
	}

	map<int,int> mp;
	for (int i = 2; i < n + 1; i++) {
		bool p = true;
		for (auto&& j : prime) {
			for(int k = 1;; k++) {
				if(i % int(pow(j,k)) == 0) {
					mp[j]++;
					p = false;
				}
				else {
					break;
				}
			}
		}
		if (p) {
			mp[i]++;
		}
	}
  
	LL ans = 1;
	for (auto&& var : mp) {
		dump(var.first);
		dump(var.second);
		ans = ans * (var.second + 1);
		ans = ans % MOD; 
	}


	cout << ans << endl;
	return 0;
}


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

int main() {
    int n;
    cin >> n;
    switch (n) {
        case 1:
            cout << "Hello World" << endl;
            break;
        case 2:
            int a, b;
            cin >> a >> b;
            cout << a + b << endl;
            break;
    }
    return 0;
}


Measured memory_bytes: 256
from __future__ import print_function
import sys
import numpy as np

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

N,Q = map(int,input().split())  # Nは文字列Sの長さ．Qは質問の個数．
S = input()
S=S+"0"

cnt=np.zeros(100000,dtype='int')
now_x=0
for i in range(1,N):
    if S[i-1]=='A' and S[i]=='C':
        cnt[i]=now_x+1
        now_x=cnt[i]
    else:
        cnt[i]=now_x

for i in range(Q):
    left,right=map(int,input().split())
    left-=1
    right-=1
    print(cnt[right]-cnt[left])
    #
    #
    #
    #
    #
    #
    #
    #
    #
    #
    #
    #
    #
    #
    #
    #


Measured memory_bytes: 15716
#include <bits/stdc++.h>
 
using namespace std;
 
#define int 	long long
#define endl	"\n"
#define mod		1000000007
#define IOS		ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

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

	cout << a * b << endl;
 	

	/*while(t--) {
		

	}*/
 
	return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif

// $ cp-batch Triangle | diff Triangle.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address Triangle.cpp && ./a.out

/*
 
 7/21/2019
 
 5:00-6:06 give up
 6:50-7:08 AC
 
 I tried to construct S by a*(a+x)-1*y where 0<=x<=1
 However 1e9*a-1*b in the editorial is even simpler!
 
 https://img.atcoder.jp/agc036/editorial.pdf
 
 */

LL S;

LL isqrt(LL x) {
  assert(x>0);
  LL y=(LL)(sqrtl((long double) x)+0.5);
//  while(y*y<x) ++y;
//  while(y*y>x) --y;
  return y;
}

void pr(LL a, LL b, LL c, LL d) {
  assert(a<=1e9&&b<=1e9&&c<=1e9&&d<=1e9);
  assert(a*d-b*c==S);
  println("%lld %lld %lld %lld %lld %lld", 0LL,0LL,a,b,c,d);
}
void solve() {
  LL a=1e9;
  LL d=S/a;
  while(a*d<S) ++d;
  dump(a,d,a*d);
  assert(a*d>=S);
  LL c=a*d-S;
  pr(a,1,c,d);
}

void solve_org() {
  LL a=isqrt(S);
  dump(a,a*a,S);
  LL d=a;
  while(a*d<S) ++d;
  if(a*d==S) {
    pr(a,0,0,d);
    return;
  }
  dump(a,d,a*d,S);
  LL bc=a*d-S;
  pr(a,bc,1,d);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout<<setprecision(12)<<fixed;
  
  cin>>S;
  solve();
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int N;

    cin >> N;

    int ans[N + 1];

    // ansの初期化
    for(int i = 1; i <= N; i++) {
        ans[i] = 0;
    }

    for(int i = 0; i < N - 1; i++) {
        int num;
        cin >> num;
        ans[num]++;
    }

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

    return 0;
}

Measured memory_bytes: 4416
#include <stdio.h>
#include <math.h>

int main(void) {
  double x1, y1, x2, y2, xp, yp, d, x2p, y2p;
  scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
  x2 -= x1, y2 -= y1;
  d = sqrt(x2 * x2 + y2 * y2);
  x2p = x2 / d, y2p = y2 / d;
  int q, i;
  scanf("%d", &q);
  for(i = 0; i < q; ++i) {
    scanf("%lf%lf", &xp, &yp);
    xp -= x1, yp -= y1;
    double ip = xp * x2 + yp * y2;
    printf("%.12f %.12f\n", -xp + 2 * (ip / d * x2p) + x1, -yp + 2 * (ip / d * y2p) + y1);
  }
  return 0;
}


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

#define all(A) begin(A), end(A)
#define sz(A) int(A.size())

using namespace std;

typedef long long ll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  ll n;
  cin >> n;
  vector <ll> div;
  for (ll d = 1; d * d <= n; d++) {
    if (n % d == 0) {
      if (d != 1) div.push_back(d);
      if (d != n / d) div.push_back(n / d);
    }
  }
  ll ans = 0;
  for (ll d: div) {
    ll m = d - 1;
    if (n % m == n / m) {
      ans += m;
    }
  }
  cout << ans << endl;
  return (0);
}


Measured memory_bytes: 384
# https://atcoder.jp/contests/abc157/tasks/abc157_d
import sys

#Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)

n,m,k = map(int,input().split())
friend = [0 for _ in range(n)]
block = [[] for _ in range(n)]
uf = UnionFind(n)

for i in range(m):
    a,b = map(int,input().split())
    friend[a - 1]+=1
    friend[b - 1]+=1
    uf.union(a - 1,b - 1)
for i in range(k):
    c,d = map(int,input().split())
    block[c - 1].append(d - 1)
    block[d - 1].append(c - 1)

for i in range(n):
    ans = uf.size(i) - friend[i] - 1
    for b in block[i]:
        if uf.same(i,b):
            ans-=1
    sys.stdout.write(str(ans) + " ")
print("")

Measured memory_bytes: 26176
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <utility>
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

int main() {
    int n, m; cin >> n >> m;
    vector<pair<ll, ll> > in;
    for(int i = 0; i < n; ++i){
    	int x, y;
    	cin >> x >> y;
    	in.pb(make_pair(x, y));
    }
    sort(in.begin(), in.end());
    ll sum = 0;
    for(int i = 0; i < n; ++i){
    	if(in[i].second >= m){
    		sum = sum + in[i].first * m;
    		m = 0;
    	}
    	else{
    		sum = sum + in[i].first * in[i].second;
    		m = m - in[i].second;
    	}
    }
    cout << sum << endl;
	return 0;
} 

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pil = pair<int, long>;
#define fix10 cout << fixed << setprecision(10);
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define MOD 1000000007
#define INF 1e17

struct edge{
  int from;
  int to;
  long cost;
};

int main(){
  int n,m;
  cin >> n >> m;
  vector<edge> edges(m);
  rep(i,m){
    cin >> edges.at(i).from >> edges.at(i).to >> edges.at(i).cost;
    edges.at(i).from--;
    edges.at(i).to--;
  }
  vector<long> d(n,-1*INF);
  d.at(0) = 0;
  rep(i,n){
    rep(j,m){
      struct edge e;
      e = edges.at(j);
      if(d.at(e.to) < d.at(e.from) + e.cost){
        d.at(e.to) = d.at(e.from) + e.cost;
        if(i == n-1 && e.to == n-1){
          cout << "inf" << endl;
          return 0;
        }
      }
    }
  }
  cout << d.at(n-1) << endl;
}

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

bool is_prime(const unsigned n){
    switch(n){
        case 0: // fall-through
        case 1: return false;
        case 2: // fall-through
        case 3: return true;
    } // n > 3 が保証された

    if(n%2 == 0) return false;
    if(n%3 == 0) return false;
    // 2と3の倍数でないので6の倍数ではないことが保証された

    if(n%6 != 1 && n%6 != 5) return false;
    // 6の倍数前後の数(素数かもしれない数)であることが保証された

    // 6の倍数前後の数を使って試し割りをする
    for(unsigned i=5;i*i<=n;i+=6){
        if(n%i     == 0) return false; // 6n-1
        if(n%(i+2) == 0) return false; // 6n+1
    }

    return true;
}

int main(){
    int Q; cin >> Q;
    //vector<pair<int,int> > P(Q);
    set<int> st;
    for(int i = 3; i < 1e5 + 1; i += 2) 
    if(is_prime(i) && is_prime((i+1)/2)) st.insert(i);
    rep(i, 0, Q){
        int l, r; cin >> l >> r;
        cout << distance(st.lower_bound(l),st.upper_bound(r)) << endl;
    }
    return 0;

}

Measured memory_bytes: 640
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define X 0
#define Y 1

using namespace std;

int n,vect[3000][2];
bool map[5001][5001];

bool getmap(int x,int y)
{
	if(x < 0 || x > 5000 || y < 0 || y > 5000)
	{
		return false;
	}
	else
	{
		return map[x][y];
	}
}

int main(void)
{
	while(1)
	{
		memset(vect,0,sizeof(int[3000][2]));
		memset(map,0,sizeof(bool[5001][5001]));
		cin >> n;
		if(n == 0)
			exit(0);
		for(int i = 0;i < n;i++)
		{
			cin >> vect[i][X] >> vect[i][Y];
			map[vect[i][X]][vect[i][Y]] = true;
		}
		int maxsize = 0;
		for(int p1 = 0;p1 < n;p1++)
		{
			for(int p2 = 0;p2 < n;p2++)
			{
				if(p1 != p2)
				{
					int vect_x = vect[p2][X] - vect[p1][X];
					int vect_y = vect[p2][Y] - vect[p1][Y];
					if((getmap(vect[p2][X]-vect_y,vect[p2][Y]+vect_x) && getmap(vect[p1][X]-vect_y,vect[p1][Y]+vect_x)) || 
					(getmap(vect[p2][X]+vect_y,vect[p2][Y]-vect_x) && getmap(vect[p1][X]+vect_y,vect[p1][Y]-vect_x)))
					{
						maxsize = max((vect_x*vect_x)+(vect_y*vect_y),maxsize);
					}
				}
			}
		}
		cout << maxsize << endl;
	}
}

Measured memory_bytes: 27360
#include <bits/stdc++.h> 
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
#define MAX 100005
#define DEBUG 0 
#define LIMIT (LONG_MAX / 10)
#define POSITIVE_LAST_D (LONG_MAX % 10)
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;

int main(){
    char c;
    cin>>c;
    cout<<static_cast<char>(c+1)<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
#include <sstream>
typedef long long ll;
ll a,b,c,d;

ll gcd(ll a,ll b){
	c=1;
	while(c>0){
		if(a<b){switch(a,b);}
		c=a%b;
		a=b;
		b=c;
	}
	return a;
}
ll lcm(ll a,ll b){
    d=a*b/gcd(a,b);
	return d;
}

int main(){
int f,i;
while(cin>>a>>b){
	f=gcd(a,b);
	i=lcm(a,b);
	cout<<f<<" "<<i<<endl;
}
}

Measured memory_bytes: 3060
#include<stdio.h>

int main(void)
{
  int i, x;

  while(scanf("%d", &x) != EOF)
  {
    if(x != 0)
    {
      i++;
      printf("Case %d: %d\n", i, x);
    }
    else
    {
      break;
    }
  }

  return 0;
}



Measured memory_bytes: 2000
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18
#define PI 3.14159265358979

using namespace std;

int main(void){
  ll n, k;

  cin >> n >> k;
  
  vector<ll> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  sort(a.begin(), a.end());


  ll l = -1e18 - 1, r = 1e18 + 1, mid;
  while(l + 1 < r){
    mid = (l + r)/2;

    ll num = 0;
    for (int i = 0; i < n; i++){
      ll left, right, m;
      if (a[i] > 0){
        if (a[i] * a[0] > mid){
          left = -1;
        }
        else {
          left = 0;
          right = n;
          while(left + 1 < right){
            m = (left + right)/2;
            if (a[i] * a[m] <= mid)
              left = m;
            else
              right = m;
          }
        }
        num += left + 1;
      } else if (a[i] < 0){
        if (a[i] * a[n-1] > mid){
          right = n;
        }
        else {
          left = -1;
          right = n - 1;
          while(left + 1 < right){
            m = (left + right)/2;
            if (a[i] * a[m] <= mid)
              right = m;
            else
              left = m;
          }
        }

        num += n - right;
      }
      else{
        if (mid >= 0)
          left = n - 1;
        else
          left = -1;

        num += left + 1;
      }
      if (a[i] * a[i] <= mid)
        num--;

    }

    if (num/2 >= k)
      r = mid;
    else
      l = mid;
  }
 

  cout << r << endl;

  return 0;
}


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

int main()
{
    int n;
    string s;
    cin>>n;
    cin>>s;
    int c=0;
    if(n%2!=0)
    cout<<"No"<<endl;
    else
    {
        for(int i=0;i<n/2;i++)
        {
            if(s[i]!=s[i+n/2])
            c++;
            
        }
        if(c==0)
        cout<<"Yes"<<endl;
        else
        cout<<"No"<<endl;
    }
    return 0;
}


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

int main()
{
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    int u[100005], v[100005];
    u[0] = v[0] = 0;
    for(int i = 1; i <= n; i++) u[i] = u[i - 1] + s[i - 1] - 'A' + 1;
    for(int i = 1; i <= m; i++) v[i] = v[i - 1] + t[i - 1] - 'A' + 1;
    int q;
    cin >> q;
    while(q--){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if((u[b] - u[a - 1]) % 3 == (v[d] - v[c - 1]) % 3) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}


Measured memory_bytes: 4496
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define mkp make_pair
#define pb push_back
#define ff first
#define ss second
#define debug1(a) cout<<a<<endl;
#define debug2(a,b) cout<<a<<' '<<b<<endl;
#define debug3(a,b,c) cout<<a<' '<<b<<' '<<c<<endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,a,b)for(int i=a;i<b;i++)
#define repre(i,a,b)for(int i=a;i<=b;i++)
#define clr1(arr) memset(arr,-1,sizeof(arr));
#define clr0(arr) memset(arr,0,sizeof(arr));
#define pi pair<int,int>
#define pii pair<int,pi>
#define aint(v) v.begin(),v.end()
#define pq priority_queue
#define mpq priority_queue<int,vector<int>,greater<int> >
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> orderedSet;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> orderedMSet;
//*p.find_by_order(index) return value at index
//p.order_of_key(key) return index
/*
2d pointer array
int **dp;
in main function
int row,col;
dp=new int*[n];
rep(i,n)dp[i]=new int[m]
*/
int power(int x,int y);
bool isPrime(int n);
int modInv(int a,int b);
int gcdExtended(int a,int b,int *x,int* y);
int mpower(int a,int b,int p);

int32_t main()
{
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  fastio
  int n;
  cin>>n;
  int temp=n/2;
  int ans=n-temp;
  double res=(double)ans/(double)n;
  cout<<res<<endl;

  return 0;
}

int modInv(int a, int m){
int x, y;
int g = gcdExtended(a, m, &x, &y);
int res = (x%m + m) % m;
return res;
}

int gcdExtended(int a, int b, int *x, int *y){
if (a == 0){
    *x = 0, *y = 1;
    return b;
}
int x1, y1;
int gcd = gcdExtended(b%a, a, &x1, &y1);
*x = y1 - (b/a) * x1;
*y = x1;
return gcd;
}

int mpower(int x, int y, int p){
int res = 1;
x = x % p;
while(y > 0){
    if(y & 1) res = (res*x) % p;
    y = y>>1;
    x = (x*x) % p;
}
return res;
}

int power(int x, int y){
int res = 1;
while (y > 0){
    if (y & 1) res = res*x;
    y = y>>1;
    x = x*x;
}
return res;
}

bool isPrime(int n){
if (n <= 1)  return false;
if (n <= 3)  return true;
if (n%2 == 0 || n%3 == 0) return false;
int p=sqrt(n);
for(int i=5;i<=p;i=i+6)
    if (n%i == 0 || n%(i+2) == 0)
        return false;
return true;
}


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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int main(){
	int K,a,b;cin>>K>>a>>b;
	if(b/K*K>=a)puts("OK");
	else puts("NG");
}

Measured memory_bytes: 3636
for i in range(5):
    a=int(input())
    if a == 0:
        break
    b=1000-a
    if b > 500:
        c=b-(500*(b//500))
        d=c-(100*(c//100))
        e=d-(50*(d//50))
        f=e-(10*(e//10))
        g=f-(5*(f//5))
        print((b//500)+(c//100)+(d//50)+(e//10)+(f//5)+g)
    elif b > 100:
        g=b-(100*(b//100))
        h=g-(50*(g//50))
        i=h-(10*(h//10))
        j=i-(5*(i//5))
        print((b//100)+(g//50)+(h//10)+(i//5)+(j))
    elif b > 50:
        k=b-(50*(b//50))
        l=k-(10*(k//10))
        m=l-(5*(l//5))
        print((b//50)+(k//10)+(l//5)+(m))
    elif b > 10:
        n=b-(10*(b//10))
        o=n-(5*(n//5))
        print((b//10)+(n//5)+(o))
    elif b > 5:
        p=b-(5*(b//5))
        print((b//5)+(p))
    else:
        print(b)


Measured memory_bytes: 5600
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()
#define INF 9999999

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


int main(void){
	int n,m,c,s,g;
	while(cin>>n>>m>>c>>s>>g, n){
		s--; g--;
		ll rail[200][200];
		REP(i,n+1) REP(j,n+1) rail[i][j] = INF;
		vector<pair<pii, pii> > rr;
		REP(i,m){
			int xx, yy, dd, cc;
			cin >> xx >> yy >> dd >> cc;
			xx--; yy--; cc--;
			rr.push_back(pair<pii,pii>(pii(xx,yy),pii(dd,cc)));
		}
		vector<int> p(c);
		REP(i,c) cin >> p[i];
		REP(i,c){
			vector<int> q(p[i]);
			vector<int> r(p[i]);
			REP(j,p[i]-1)	cin >> q[j];
			q[p[i]-1] = INF;
			REP(j,p[i]) cin>>r[j];
			ll cost[30000];
			cost[0] = 0;
			int id = 0;
			REP(k, 30000){
				if(!k) continue;
				if(k > q[id]) id++;
				cost[k] = cost[k-1] + r[id];
			}

			ll railpart[200][200];
			REP(k,n+1) REP(l,n+1) railpart[k][l] = INF;

			REP(j,m){
				pii xy = rr[j].first, dc = rr[j].second;
				if(dc.second == i){
					railpart[xy.first][xy.second] = min(dc.first, (int)railpart[xy.first][xy.second]);
					railpart[xy.second][xy.first] = min(dc.first, (int)railpart[xy.second][xy.first]);
				}
			}

			REP(k,n){
				REP(x,n){
					REP(y,n){
						railpart[x][y] = min(railpart[x][y], railpart[x][k] + railpart[k][y]);
					}
				}
			}

			REP(x,n){
				REP(y,n){
					if(railpart[x][y] == INF) continue;
					railpart[x][y] = cost[railpart[x][y]];
				}
			}

			REP(x,n){
				REP(y,n){
					rail[x][y] = min(railpart[x][y], rail[x][y]);
				}
			}
		}
		
		REP(k,n){
			REP(x,n){
				REP(y,n){
					rail[x][y] = min(rail[x][y], rail[x][k] + rail[k][y]);
				}
			}
		}
		/*
		REP(x,n){
			REP(y,n){
				cout << rail[x][y] << ":";
			}cout << endl;
		}cout << endl << endl;
		*/
		if(rail[s][g] == INF) cout << "-1" << endl;
		else cout << rail[s][g] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 2132
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    vvint cld(n);
    vector<pair<int, int>> par(n, make_pair(-1,0)); //parent, hight;
    vint pn(n);
    REP(i,n-1+m){
        int a,b;
        cin >> a >> b;
        a--; b--;
        cld[a].pb(b);
        pn[b]++;
    }
    queue<int> q;
    REP(i,n){
        if(pn[i]==0){
            q.push(i);
            par[i] = make_pair(-1,0);
            break;
        }
    }
    while(!q.empty()){
        int x = q.front();
        q.pop();
        auto now = par[x];
        for(int i : cld[x]){
            pn[i]--;
            auto next = par[i];
            if(next.se<now.se+1){
                par[i]=make_pair(x, now.se+1);
            }
            if(pn[i]==0){
                q.push(i);
            }
        }
    }
    REP(i,n){
        cout << par[i].fi+1 << endl;;
    }
    return 0;
}

Measured memory_bytes: 7424
#include <bits/stdc++.h>
#include <atcoder/all>

#define rep(i,n)  for(int i = 0; i < (int)(n); i++)
#define sz(x)     ((int)(x).size())
#define all(x)    (x).begin(),(x).end()

using ll = long long;

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); }

int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int n, m; std::cin >> n >> m;
  atcoder::dsu uf(n);
  rep(i,m) {
    int a,b; std::cin >> a >> b; a--,b--;
    uf.merge(a,b);
  }

  std::set<int> s;
  rep(i,n) s.insert( uf.leader(i) );
  std::cout << sz(s) - 1 << std::endl;

  return 0;
}



Measured memory_bytes: 7552
#include <stdio.h>

int gcd(int p, int q){
  if (p % q == 0) return q;
  else return gcd(q,p%q);
}

int main(void){
  int k;
  int sum = 0;

  scanf("%d",&k);

  for (int a = 1; a <= k; a++){
    for (int b = 1; b <= k; b++){
      for (int c = 1; c <= k; c++){
          sum += gcd(a,gcd(b,c));
      }
    }
  }

  printf("%d",sum);

  return 0;
}

Measured memory_bytes: 1728
package main

import "fmt"

func main() {
	var L, R int64
	fmt.Scan(&L, &R)

	w := R - L + 1
	if w%2019 == 0 {
		fmt.Println(0)
		return
	}

	var ans int64
	ans = 2020
	for i := L; i <= R; i++ {
		for j := i + 1; j <= R; j++ {
			ans = min(ans, ((i%2019)*(j%2019))%2019)
			if ans == 0 {
				fmt.Println(0)
				return
			}
		}
	}
	fmt.Println(ans)
}

func min(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}


Measured memory_bytes: 512
from decimal import*
from fractions import*
import math
import functools

s=input()
k=input()
k=(int)(k)

n=len(s)
dp=[[[0 for mind in range (2)] for j in range(k+5)] for i in range(n+5)]

dp[0][0][0]=1
for i in range(n):
    for j in range(2):
        for cnt in range(k+1):
            pre_num=1
            if(j!=0):
                pre_num=9
            else:
                pre_num=(int)(s[i])
            for digit in range(pre_num+1):
                cur=j
                if(digit<pre_num): 
                    cur=1
                dp[i+1][cnt+(digit!=0)][cur]+=dp[i][cnt][j]
sum=dp[n][k][0]+dp[n][k][1]
print(sum)


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

int main() {
  int m,n;
  cin >> n >> m;
  int left=-1;
  int right=n+2;
  rep(i,m){
    int t_left, t_right;
    cin >> t_left >> t_right;
    left = max(left, t_left);
    right = min(right, t_right);
  }
  cout << max(right - left +1,0) << endl;
  
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!

from collections import deque

H, W = map(int, input().rstrip().split(' '))

field = [[0] * W for _ in range(H)]
d = deque()
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            field[i][j] = 1
            d.append([i, j, 0])

max_dist = 0
while len(d) > 0:
    cur_h, cur_w, dist = d.popleft()
    for i, (dh, dw) in enumerate([[0, 1], [0, -1], [1, 0], [-1, 0]]):
        if (cur_h + dh) >= 0 and (cur_h + dh) < H and (cur_w + dw) >= 0 and (cur_w + dw) < W:
            if field[cur_h+dh][cur_w+dw] == 0:
                field[cur_h+dh][cur_w+dw] = 1
                d.append([cur_h+dh, cur_w+dw, dist+1])
                max_dist = max(max_dist, dist+1)

print(max_dist)


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

class Program
{
    static void Main(string[] args)
    {
        var N = decimal.Parse(Console.ReadLine()) - 1;

        var list = new List<decimal>();

        var i = 1;

        var current = N;

        while (true)
        {
            if ((i != 1 && current / 26 > 1) || (i == 1 && current/ 26 >= 1))
            {
                if (i == 1 || current % 26 != 0)
                {
                    list.Add(current % 26);
                }
                else
                {
                    list.Add(26);
                }
                var div = (current % 26 == 0 ? 26 : current % 26);
                if(i == 1)
                {
                    div = current % 26;
                }

                current = (current - div) / 26;
            }
            else
            {
                if (i == 1 || current % 26 != 0)
                {
                    list.Add(current % 26);
                }
                else
                {
                    list.Add(26);
                }
                break;
            }
            i++;
        }

        var ans = "";

        for(var j = list.Count - 1; j > -1; j--)
        {
            var n = 97;
            if(j != 0) {
                n -= 1;
            }
            ans += (char)(list[j] + n);
        }

        Console.WriteLine(ans);
        Console.ReadLine();

    }
}

Measured memory_bytes: 17752
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <iomanip>
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 998244353;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }  

int main(){
    int n;
    cin >> n;
    
    vector<int> A(n);
    vector<int> B(n);
    vector<int> C(n-1);

    for(int i=0; i<n; i++)
        cin >> A[i];
    for(int i=0; i<n; i++)
        cin >> B[i];
    for(int i=0; i<n-1; i++)
        cin >> C[i];
    
    int sol=0;
    
    for(int i=0; i<n; i++){
        sol+=B[A[i]-1];
        if(i>=1 && A[i-1] == A[i]-1)
            sol+=C[A[i-1]-1];
    }
    cout << sol;
}

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

int main(void) {
    int i, N;
    long long A, B, T, X1, X2;

    scanf("%d%lld%lld", &N, &A, &B);
    T = 0;
    scanf("%lld", &X1);
    for (i=1;i<N;i++) {
        scanf("%lld", &X2);
        if (A*(X2-X1) < B) T += A*(X2-X1);
        else T += B;
        X1 = X2;
    }

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

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
ll a,b,c,d,e,f,g;
int main(){
	cin>>a>>b>>c>>d>>e>>f>>g;
	ll ans=0;
	ans+=b*2;
	int x=a%2+d%2+e%2;
	if(x==3){
		a--,d--,e--;
		ans+=6;
	}
	if(x==2){
		if(a==0||d==0||e==0){
		}else{
			ans+=2;
		}
	}
	ans+=(d/2)*4;
	ans+=(e/2)*4;
	ans+=(a/2)*4;
	cout<<ans/2<<endl;
}


Measured memory_bytes: 256
from collections import deque


H, W = map(int, input().split())
A = [list('#' * (W + 2))]
q = deque()
A_append = A.append
q_append = q.append
for _ in range(H):
    a = input()
    A_append(list('#' + a + '#'))
A.append(list('#' * (W + 2)))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if A[i][j] == '#':
            q_append([i, j, 0])

ans = 0

while len(q) != 0:
    p = q.popleft()
    for k in range(4):
        y = p[0] + dy[k]
        x = p[1] + dx[k]
        c = p[2]
        ans = max(ans, c)
        if A[y][x] == '.':
            A[y][x] = '#'
            q_append([y, x, c + 1])

print(ans)


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

int main(){
	int A, B, sum=0;
	cin >> A >> B;
	for (int i=0; i<2; i++){
		if (A >= B){
			sum += A;
			A   -= 1;
		}
		else{
			sum += B;
			B   -= 1;
		}
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#include "math.h"
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
int n;
int g[15][15];
int main(){
    int n;
    cin >> n;

    REP(i,n){
        REP(j,n){
            g[i][j] = -1;
        }
    }

    REP(i,n){
        int a; cin >> a;

        REP(j,a){
            int x,y; cin >> x >> y;
            x --;
            g[i][x] = y;
        }
    }
    int ans = 0;
    REP(i,1 << n){
        vector<int> v(n);
        REP(j,n){
            if(i >> j & 1) v[j] = 1;
        }
        bool fl = true;
        
        REP(j,n){
            if(v[j]){
                REP(k,n){
                    if(g[j][k] == -1) continue;
                    if(g[j][k] != v[k]) fl = false;
                }
            }
        }
        if(fl) ans = max(ans, __builtin_popcount(i));
    }

    cout << ans <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a, b;
  cin >>  a >> b;
  int n = b;
  int c = 0;
  while(n >0){
    n /= 10;
    c++;
  }
  float sq = sqrt(a * pow(10,c) + b);
  if(ceil(sq) == floor(sq)){
    cout << "Yes" << endl;
  }
  else{cout << "No" << endl;}
  
  
  return 0;
}

Measured memory_bytes: 256