akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define Size 600050
using namespace std;
namespace{
	template<class free>
		il void read(free&x){
		x^=x;ri char c;while(c=getchar(),c==' '||c=='\n'||c=='\r');
		ri bool check(false);if(c=='-')check=true,c=getchar();
		while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
		if(check)x=~x+1;
	}
	template<class f1,class...f2>
		il void read(f1&x,f2&...y){
		read(x),read(y...);
	}
}
struct point{
	int next,to;
}ar[Size];
bool is[Size];
int head[Size],art(1);
int son[2][Size],rt[2],a[Size];
il void link(int,int),dfs(int);
int main(){
	int n;read(n);
	for(int i(1),j;i<=n;++i)
		read(j),~j?link(j,i),
			++son[0][j]:rt[0]=i;
	for(int i(1),j;i<=n;++i)
		read(j),~j?link(j+n,i+n),
			++son[1][j]:rt[1]=i+n;
	link(rt[0],rt[1]);
	for(int i(1);i<=n;++i){
		if(son[0][i]+son[1][i]&1)
			return puts("IMPOSSIBLE"),0;
		if(~son[0][i]&1)link(i,i+n),a[i]=art;
	}dfs(1),puts("POSSIBLE");
	for(int i(1);i<=n;++i)
		if(son[0][i]&1)puts("0");
		else puts(is[a[i]]?"-1":"1");
	return 0;
}
il void dfs(int x){
	for(int i(head[x]);i;i=head[x])
		if(head[x]=ar[head[x]].next,!is[i])
			is[i^1]=1,dfs(ar[i].to);
}
il void link(int u,int v){
	ar[++art]={head[u],v},head[u]=art;
	ar[++art]={head[v],u},head[v]=art;
}


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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

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

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

    vector<int> a(5);
    rep (i, 5) {
        cin >> a[i];
    }

    bool flag = false;
    rep (i, 5) {
        if (a[i] % 10) {
            flag = true;
        }
    }

    int digit = 9;
    int tmp = 0;
    int ans = 0;
    if (flag) {
        rep (i, 5) {
            if (a[i] % 10 != 0) {
                digit = min(digit, a[i] % 10);
            }
        }

        rep (i, 5) {
            if (i == tmp) {
                ans += ((a[i]/10)*10+digit);
            } else if (a[i] % 10) {
                ans += ((a[i]/10+1)*10);
            } else {
                ans += a[i];
            }
        }
    } else {
        rep (i, 5) {
            ans += a[i];
        }
    }

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

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a%b)

ans = gcd(A[0], A[1])
if N > 2:
    for i in range(2, N):
        ans = gcd(ans, A[i])

print(ans)

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long A[] = new long[N];
        int count = 1;
        int ans = 0;
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextLong();
        }
        Arrays.sort(A);
        for (int i = 1; i <N; i++) {
            if (A[i - 1] == A[i]) {
                count++;
            } else {
                if (count % 2 == 1) {
                    ans++;
                }
                count = 1;
            }
        }
        if(count%2==1)ans++;
        System.out.println(ans);
    }
}

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

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);
#define Fix( x ) setprecision( x ) << fixed
#define mem( a , x ) memset( a , x , sizeof( a ) )
#define bug( a , b ) cerr<< #a <<" = "<<a<<" , "<< #b <<" = "<<b<<"\n";
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define FOR( i , a , b ) for( int i = a; i <= b; i++ )
#define ROF( i , a , b ) for( int i = a; i >= b; i-- )
#define sz( V ) (int)V.size( )
#define all( V ) V.begin( ),V.end( )
#define Found( S , val ) S.find( val ) != S.end( )
#define Unique( V ) sort( all( V ) ), V.erase( unique( all( V ) ), V.end() )
typedef pair < int , int > ii;
typedef pair < int , ii > iii;
typedef long long int LL;
typedef unsigned long long uLL;
const int inf = (int)1e9;
const LL INF = (LL)1e18;
const int N = 100005;
const int mod = 1000000007;
const double eps = 1e-8;
const double pi = acos( -1.0 );


int main( int argc, char const *argv[] ) {
        fast_io;
        LL n;
        cin >> n;
        LL x = n;
        int sum = 0;
        while( x ) {
            sum += x%10 , x /= 10;
        }
        if( n%sum == 0 ) cout << "Yes" << endl;
        else cout << "No" << endl;
        return 0;
}








Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
mny = 1000
up = True
i = 0
while True:
    if a[i+1] > a[i]:
        cnt = 0
        while a[i + cnt + 1] >= a[i + cnt]:
            cnt += 1
            if i + cnt == n - 1:
                mny += (mny//a[i])*(a[i+cnt] - a[i])
                i += cnt
                break
        if i == n - 1:
            break
        mny += (mny//a[i])*(a[i+cnt] - a[i])
        i += cnt
    else:
        i += 1
    if i == n - 1:
        break
print(mny)

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

n=int(input())  #数値入力 「N」だけの入力のとき
i=0
lst ={}
while i < n: 
    s = input()
    if s not in lst:
        lst[s]=1
    else:
        lst[s]+=1
    i+=1
maxi = max(lst.values())
res = []
for i,j in lst.items():
    if j == maxi:
       res.append(i) 
res.sort()
for i in res:
     print(i)

Measured memory_bytes: 32096
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<vector>

int main() {
   
   int N, K;
   std::cin >> N >> K;
   int m[N];
   int min;
   int sum = 0;
   for (int i = 0; i < N; i++) {
      int tmp;
      std::cin >> tmp;
      sum += tmp;
      m[i] = tmp;
      if (i == 0) min = tmp;
      else if (min > tmp) min = tmp;
   }
   int ans = N;
   K -= sum;
   ans += K / min;
   std::cout << ans << std::endl;
   return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
	int n, a;
	float x, t;
	scanf("%d", &n);
	if (n >= 1 && n <= 50000) {
		x = n / 1.08;
		t = (int)x;
		a = t * 1.08;
		if (a == n) {
			a = t;
			printf("%d", a);
		}
		else {
			t++;
			a = t * 1.08;
			if (a == n) {
				a = t;
				printf("%d", a);
			}
			else {
				printf(":(");
			}
		}

	}
	else {
		printf(":(");
	}

}

Measured memory_bytes: 128
N,K=map(int,input().split())
p=[int(i) for i in input().split()]
q=[(i+1)/2 for i in p]
S=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=S[i]+q[i]
ans=0
for i in range(N-K+1):
    ans=max(ans,S[i+K]-S[i])
print(ans)


Measured memory_bytes: 25188
#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    uint32_t mon_num;
    uint32_t hisatu_num;
    uint32_t max_buf = 0;
    uint32_t max_buf_num = 0;
    uint32_t loopcnt = 1;
    uint64_t last_sum = 0;

    std::cin >> mon_num >> hisatu_num;

    std::vector<uint64_t> mon_hp(mon_num);
    for(int i = 0; i < mon_num; i++){
        std::cin >> mon_hp[i];
    }

    if(hisatu_num >= mon_num){
        std::cout << 0 << std::endl;
        return 0;
    }
    
    std::sort(mon_hp.begin(),mon_hp.end());

    for(int n = 0; n < (mon_num - hisatu_num); n++){
        last_sum += mon_hp[n];
    }

    std::cout << last_sum << std::endl;

    return 0;
}

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

int main() {
    int n,k;
    cin>>n>>k;
    int a[n];
    for (int i=0;i<n;i++)
        cin>>a[i];
    int mn=1e9;
    for (int i=0;i+k-1<n;i++)
        mn=min(mn,min(abs(a[i]),abs(a[i+k-1]))+a[i+k-1]-a[i]);
    cout<<mn<<endl;
    return 0;
}

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

double a[510];
int n;

double solve(){
    vector<double> x;
    x.push_back(a[0]);
    for(int i = 1; i < n; i++){
        double left = a[i];
        rep(j,i){
            double p = a[i]+a[j];
            double q = a[i]-a[j];
            double dx = sqrt(p*p - q*q);
            left = max(left, dx + x[j]);
        }
        x.push_back(left);
    }
    double res = 0;
    rep(i,n) res = max(res, x[i]+a[i]);
    return res;
}

int main(){
    while(cin >> n){
        rep(i,n) cin >> a[i];
        printf("%.10lf\n", solve());
    }
}

Measured memory_bytes: 3348
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1000000000

int main(){
	int n,x;cin>>n>>x;
	vector<int> l(n);for(int i=0;i<n;i++){cin>>l[i];}
	vector<int> d(n+1);d[0]=0;


	int key=n+1;
	for(int i=0;i<n;i++){
		d[i+1]=d[i]+l[i];
		if(d[i+1]>x){key=i+1;break;}
	}

	cout<<key<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,f,b=0,j=0,kaunto;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a.at(i);
    }
    sort(a.begin(),a.end());
    
    
    for(int i=0;i<n;i++){
        
        if(b<a.at(i)){
            b=a.at(i);
            j++;
        }
    }
    cout<<j<<endl;
}

Measured memory_bytes: 3596
A = int(input())

import sys

if A ==1:
    print(0)
    sys.exit()

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(cnt)

    if temp!=1:
        arr.append(1)

    if arr==[]:
        arr.append(1)

    return arr

def counting(x):
    i = 1
    result = 0
    while i<=x:
        result +=1
        x -=i
        i +=1
    return result

arr = factorization(A)

result = 0
for i in range(len(arr)):
    result += counting(arr[i])

print(result)

Measured memory_bytes: 9500
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum += data[i] * data[j];
        }
    }
    for (int i = 0; i < n; i++) {
        sum -= data[i] * data[i];
    }
    cout << sum / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int main(){
    int h,w;
    cin>>h>>w;
    string s[h];
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    ll ans[h][w];
    memset(ans,0,sizeof(ans));
    ans[0][0]=1;
    const int dx[]={1,0};
    const int dy[]={0,1};
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            for(int k=0;k<2;k++){
                int nx=i+dx[k];
                int ny=j+dy[k];
                if(nx<0||h<=nx||ny<0||w<=ny||s[nx][ny]=='#')continue;
                ans[nx][ny]=(ans[nx][ny]+ans[i][j])%MOD;
            }
        }
    }
    cout<<ans[h-1][w-1]<<endl;
}

Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,x,sum=0;
  cin>>n;

  int a[n+1]={0},b[n+1]={0},c[n]={0};

  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 tmp=-2;

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

    if(tmp+1==a[i]){sum+=c[a[i]-2];}

    tmp=a[i];
  }

  cout<<sum;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef double          D;
typedef long long int   LL;
typedef long double     LD;
#define OR              ||
#define AND             &&
#define nl              '\n'
#define S               string
#define inf             INT_MAX
#define SQR(a)          (a) * (a)
#define pb              push_back
#define GCD(a, b)       __gcd(a, b)
#define PI              2.0*acos(0.0)
#define LCM(a, b)       (a * b) / GCD(a, b)
#define mem(a,b)        memset(a,b,sizeof(a))
#define srtv(v)         sort(v.begin(),v.end())
#define T               int t; cin>>t; while(t--)
#define Rep(i,a,b)      for(int i = a; i <= b; i++)
#define rep(i,a,b)      for(int i = a; i >= b; i--)
#define boost		    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inout           freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)

#define si(x)           scanf("%d",&x)
#define pi(x)           printf("%d",x)
#define ss(str)         scanf("%s",str)
#define pl(x)           printf("%lld",x)
#define sl(x)           scanf("%lld",&x)
#define sii(x,y)        scanf("%d %d",&x,&y)
#define sll(x,y)        scanf("%lld %lld",&x,&y)
#define siii(x,y,z)     scanf("%d %d %d",&x,&y,&z)
#define slll(x,y,z)     scanf("%lld %lld %lld",&x,&y,&z)
using namespace std;

int main()
{
    int x,y;
    sii(x,y);

    bool ans=false;

    for(int i=1;i<=x;i++)
    {
        int crane=i*2;
        int tort=(x-i)*4;

        if(crane+tort==y)
        {
            ans=true;
            break;
        }
    }

    for(int i=1;i<=x;i++)
    {
        int tort=i*4;
        int crane=(x-i)*2;

        if(crane+tort==y)
        {
            ans=true;
            break;
        }
    }

    if(ans)
        printf("Yes");
    else
        printf("No");


    return 0;
}


Measured memory_bytes: 3820
#include <bits/stdc++.h>
using namespace std;
int main(){
    int W,H,x,y,z;
    cin >> W >> H >> x >> y >> z;
    if(x<1 || y<1){
        cout << "No" << endl; 
    }
    else if(x-z<0){
    cout << "No" << endl;
    }
    else if(x+z>W){
        cout << "No" << endl;
    }
    else if(y-z<0){
        cout << "No" << endl;
    }
    else if(y+z>H){
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }
}


Measured memory_bytes: 3112
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define INF 1000000000
#define mod 1000000007

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
	int N;
	cin>>N;
	int a[50][26]={0};
	REP(i,N){
		string s;
		cin>>s;
		REP(j,s.size()){
			a[i][s[j]-'a']++;
		}
	}
	int ans[26];
	REP(i,26)ans[i]=INF;
	REP(j,26){
		REP(i,N){
			ans[j]=min(ans[j],a[i][j]);
		}
	}
	bool f=true;
	REP(i,26){
		if(ans[i]>=INF)ans[i]=0;
		else f=false;
	}
	if(f){
		cout<<" "<<endl;
		return 0;
	}
	REP(i,26){
		REP(j,ans[i]){
			char c=i+'a';
			cout<<c;
		}
	}
	cout<<endl;
	return 0;
}
	

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define endl  "\n"
#define ll long long
#define int long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cin.exceptions(cin.failbit);cout.tie(NULL);
using namespace std;
bool isPrime(int n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i += 6)
    {
        if ((n % i == 0) || (n % (i + 2) == 0))
            return false;
    }
    return true;
}

int32_t main()
{
	int n,m,k;
	cin >> n >> m >> k;
	char a[n][m];
	int row[n]={0},col[m]={0};
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin >> a[i][j];
			if(a[i][j]=='#')
			{
				row[i]++;
				col[j]++;
				cnt++;
			}
		}
	}
	int temp[m]={0};
	for(int i=0;i<m;i++)
	{
		temp[i]=col[i];
	}
	int x=cnt-k;
	int ans=0;

	for(int i=0;i<((int)pow(2,n));i++)
	{
		int z=i;
		vector<int> v;
		for(int j=0;j<n;j++)
		{
			if((z&1))
			v.push_back(1);
			else
			v.push_back(0);
			
			//cout << "raj";
			z=z/2;
		}
		//cout << "ewrf";
		int s=0;
		for(int j=0;j<v.size();j++)
		{
			if(v[j]==1)
			s+=row[j];
		}
		
		
		for(int j=0;j<v.size();j++)
		{
			if(v[j]==1)
			{
				for(int k=0;k<m;k++)
				{
					if(a[j][k]=='#')
					{
						col[k]--;
					}
				}
			}
		}
		
		
		for(int ii=0;ii<(int)(pow(2,m));ii++)
		{
			vector<int> final;
			int y=ii;
			
			int p=s;
			for(int jj=0;jj<m;jj++)
			{
				if((y&1))
				final.push_back(1);
				else
				final.push_back(0);
				
				y=y/2;
			}
			
			
			for(int jj=0;jj<final.size();jj++)
			{
				if(final[jj]==1)
				p+=col[jj];
			}
			
			if(p==x)
			ans++;
			
			
			
		}
		for(int raj=0;raj<m;raj++)
			{
				col[raj]=temp[raj];
			}
			
			
		
	}
	
	cout << ans;
	
//	for(int i=0;i<n;i++)
//	{
//		int s=0;
//		for(int j=i;j<n;j++)
//		{
//			s+=row[j];
//			for(int k=i;k<=j;k++)
//			{
//				for(int p=0;p<m;p++)
//				{
//					if(a[k][p]=='#')
//					{
//						col[p]--;
//					}
//				}
//			}
//			
//			
//			for(int ii=0;ii<m;ii++)
//			{
//				int p=s;
//				for(int jj=ii;jj<m;jj++)
//				{
//					p+=col[jj];
//					if(p==x)
//					{
//						//cout << i << " " << j << " " << ii << " " << jj << endl;
//						ans++; 
//					}
//				}
//			}
//			
//			for(int p=0;p<m;p++)
//			{
//				col[p]=temp[p];
//			}
//		}
//	}
	//cout << ans;
	
}



Measured memory_bytes: 4064
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>

using namespace std;
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }


void solve(void)
{
  int N,D,A;
  cin>>N>>D>>A;
  vector<pair<int,int> > vp (N); 
  for (int i = 0; i < N; i++)
  {
    cin>>vp[i].first>>vp[i].second;
    vp[i].second *=-1;
  }
  sort(ALL(vp));
  vector<int> X (N+1,0);
  vector<int> H (N+1,0);
  for (int i = 0; i < N; i++)
  {
    X[i] = vp[i].first;
    H[i] = -1*vp[i].second;
  }
  int ANS = 0;
  int index = 0;
  H[N] = INF;
  X[N] = INF;
  vector<int> SUM(N+2,0);
  while(index < N)
  {
    
    int pos = X[index];
    int end = distance(X.begin(),upper_bound(ALL(X),pos + 2*D));
    int num = (max(0LL,H[index] - SUM[index]))/A +(int)((max(0LL,H[index]-SUM[index]))%A > 0);
    SUM[index] += num*A;;
    SUM[end] -= num*A;
    ANS += num;

    SUM[index+1] += SUM[index];    
    index++;

  // DEBUG(SUM);
  }
  cout<<ANS<<endl;
  
  
  return;
}

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

  std::cout << std::fixed;
  std::cout << std::setprecision(15);
  solve();

  return 0;
}


Measured memory_bytes: 8064
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#define INF 0x3f3f3f3f
#define mod 1000000009
#define e  2.718281828459045
#define eps 1.0e18
#define PI acos(-1)
#define lowbit(x) (x&(-x))
#define memset(x,y) memset(x,y,sizeof(x))
#define lson i << 1,l,m
#define rson i << 1 | 1,m + 1,r
#define ll long long
using namespace std;
priority_queue <int> q;
const int N = 3e5+5;
int a[N];
int main(){
	ios::sync_with_stdio(false);
	ll n;
	ll a,b;
	cin>>n>>a>>b;
	ll ans=n/(a+b)*a;
	if(n%(a+b)>a) ans+=a;
	else ans+=n%(a+b);
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>

using namespace std;

typedef long long ll;

int main() {
	int n, m, l; cin >> n >> m >> l;
	ll a[100][100];
	ll b[100][100];
	for (int y = 0; y < n; ++y) {
		for (int x = 0; x < m; ++x) {
			cin >> a[y][x];
		}
	}
	for (int y = 0; y < m; ++y) {
		for (int x = 0; x < l; ++x) {
			cin >> b[y][x];
		}
	}
	for (int y = 0; y < n; ++y) {
		for (int x = 0; x < l; ++x) {
			if (x) cout << " ";

			ll c = 0;
			for (int k = 0; k < m; ++k) {
				c += a[y][k] * b[k][x];
			}
			cout << c;
		}
		cout << endl;
	}
}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

const int64 mod = 1e9+7;

int main(void){
	int32 N, x;
	cin >> N >> x;
	vector<int32> v(2*N);
	if(x == 1 || x == 2*N-1){
		cout << "No" << endl;
		return 0;
	}
	bool used[212345] = {};
	int32 in = 1;
	if(x == 2){
		v[N] = x;
		v[N-1] = 2*N-1;
		v[N+1] = 1;
		used[x] = used[2*N-1] = used[1] = 1;
		if(N > 2){
			v[N+2] = 2*N-2;
			used[2*N-2] = 1;
		}
		FOR(i, 1, N-1){
			while(used[in]) in++;
			v[i] = in;
			used[in] = 1;
		}
		FOR(i, N+3, 2*N){
			while(used[in]) in++;
			used[in] = 1;
			v[i] = in;
		}
	}else{
		v[N] = x;
		v[N+1] = 2*N-1;
		v[N-1] = 1;
		used[x] = used[2*N-1] = used[1] = 1;
		if(N > 2){
			v[N+2] = 2;
			used[2] = 1;
		}
		FOR(i, 1, N-1){
			while(used[in]) in++;
			used[in] = 1;
			v[i] = in;
		}
		FOR(i, N+3, 2*N){
			while(used[in]) in++;
			used[in] = 1;
			v[i] = in;
		}
	}
	cout << "Yes" << endl;
	FOR(i, 1, 2*N){
		cout << v[i] << endl;
	}
}

Measured memory_bytes: 3328
q = int(input())

def solve(a,b):
    if a == b:
        return 2*a-2
    if b < a:
        return solve(b, a)

    lb, ub, ab = a, 2*b, a*b
    while ub-lb > 1:
        mid = (lb+ub)//2
        """
        1<= k <= xとした時の
        k(x+1-k)の最大値を取るのはk = (x+1)//2の時
        !!!k(x-k)ではない!!!
        これだとk=xで0になってしまう
        """
        maxp = (mid+1)//2*(mid+1-(mid+1)//2)
        if maxp < ab:
            lb = mid
        else:
            ub = mid
    #高橋くんが1つ使っているので1引く
    return lb-1

for _ in range(q):
    a, b = map(int, input().split())
    t = solve(a,b)
    print(t)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
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; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    double A, B, H, M;
    static const double pi = 3.141592653589793;
    cin >> A >> B >> H >> M;

    H *= 30;
    H += M * 0.5;
    M *= 6;
    double diff = abs(H - M);
    diff = min(diff, 360 - diff);

    double AA = A * A;
    double BB = B * B;
    double ans = AA + BB - 2 * A * B * cos(diff * (pi / 180.0));
    ans = sqrt(ans);
    printf("%.10lf\n", ans);
    return 0;
}

Measured memory_bytes: 4164
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
int a[20], b[20];
int ans;
void f(int l) {
	if (l > n) {
		int bb = 0;
		for (int i = 1; i <= n; i++) {
			//cout << b[i];
			if (b[i] % 2 == 0) bb = 1; 
		}
		//cout << endl;
		ans += bb;
		/*cout << ans; 
		cout << endl;*/
		return;
	}
	for (int i = -1; i <= 1; i++) {
		b[l] = a[l] + i;
		f(l + 1);
	}
}
int main() {
	cin >> n;
	int temp = 1;
	for (int i = 1; i <= n - 1; i++) {
		temp *= 3;
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	f(1);
	cout << ans;
	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
int bj(int m,int n);
int main()
{
	int a,b,c,min;
	scanf("%d%d%d",&a,&b,&c);
	min=bj(a+b,a+c);
	min=bj(min,b+c);
	printf("%d",min);
		

}
int bj(int m,int n){
	if(m>n)
		return n;
	return m;
}


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

constexpr int kN = int(2E5 + 10);
int w[kN], r[kN];

int main() {
	int n, ans = kN;
	string s;
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		w[i + 1] = w[i] + (s[i] == 'W');
		r[i + 1] = r[i] + (s[i] == 'R');
	}
	for (int i = 0; i <= n; i++) {
		ans = min(ans, max(w[i], r[n] - r[i])); 
	}


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


Measured memory_bytes: 5296
def main():
    w = []
    for i in range(10):
        w.append(int(input()))
    k = []
    for i in range(10):
        k.append(int(input()))
    print(sum(sorted(w, reverse=True)[:3]), sum(sorted(k, reverse=True)[:3]))
        

if __name__ == "__main__":
    main()




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

int main(void)
{
    int k, x, y;
    cin >> k >> x;
    for (int i = 1; i <= k * 2 - 1; i++)
    {
        y = x - k + i;
        if (y > 1000000)
        {
            continue;
        }
        else if (y < -1000000)
        {
            continue;
        }
        else if (i == k * 2 - 1)
        {
            cout << y << endl;
        }
        else
        {
            cout << y << " ";
        }
    }
}

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

int dp[150][70000];
int main(){
	int n,K;cin>>n>>K;
	vector<P>v;
	int sq=0;
	for(int i=1;i*i<=n;i++){
		v.push_back(P(i,i));
		sq=i;
	}
	for(int i=1;i*i<n;i++){
		v.push_back(P(max(sq+1,n/(i+1)+1),n/i));
	}
	sort(v.begin(),v.end());
	dp[0][0]=1;
	rep(i,K){
		int sum=0;
		int s=0;
		for(int j=v.size()-1;j>=0;j--){
			int d=n/v[j].first;
			while(s<v.size()&&v[s].second<=d){
				(sum+=dp[i][s])%=MOD;
				s++;
			}
			dp[i+1][j]=sum*(ll)(v[j].second-v[j].first+1)%MOD;
		}
	}
	int ans=0;
	rep(i,v.size())(ans+=dp[K][i])%=MOD;
	cout<<ans<<endl;
}

Measured memory_bytes: 29176
#include <stdio.h>

int main(void){
    int n,x;
    int i,j,k,count;
    count = 0;
    while(1){
    scanf("%d %d",&n,&x);
    if(n == 0 && x == 0){
        break;
    }
        for(i=1;i<=n;i++){
            for(j=i+1;j<=n;j++){
                for(k=j+1;k<=n;k++){
                    if(i+j+k == x){
                        count++;
                    }
                }
            }
        }
        printf("%d\n",count);
        count = 0;
    }
return(0);
}

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

const int M = 1000005;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a.at(i);
  vector<int> cnt(M);
  
  for (int x :a){
    if (cnt[x] != 0){
      cnt[x] = 2;
      continue;
    }
    for (int i=x; i<M;i+=x) cnt[i]++;
  }
  
  int ans = 0;
  for (int x :a){
    if (cnt[x]==1) ans++;
  }
  cout << ans <<"\n";
  return 0;
 
}

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

const int MAXN = 18;
int n,a[MAXN],b[MAXN],dp[1<<MAXN][MAXN];

int main(){
	cin >> n;
	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;i++){
		for(int j=0;j<(1<<n);j++){
			dp[j][i]=1e9;
		}
	}
	for(int i=0;i<n;i++)dp[1<<i][i]=0;
	// dp[0][0]=0;
	for(int mask=0;mask<(1<<n);mask++){
		for(int i=0;i<n;i++){
			int p = __builtin_popcount(mask);
			int x;
			if(i%2==(p-1)%2)x = a[i];
			else x = b[i];
			for(int j=0;j<n;j++){
				if((mask>>j)&1)continue;
				int y = (j%2==p%2)?a[j]:b[j];
				if(y<x)continue;
				int cost = dp[mask][i]+__builtin_popcount(mask>>j);
				dp[mask|(1<<j)][j] = min(dp[mask|(1<<j)][j],cost);
			}
		}
	}
	int ans = 1e9;
	for(int i=0;i<n;i++)ans = min(ans,dp[(1<<n)-1][i]);
	if(ans>=1e9)ans = -1;
	cout << ans << endl;

	return 0;
}




Measured memory_bytes: 18688
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using o_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define M 1000010

int main(){
	IOS;
	ll n,a,b;cin>>n>>a>>b;
	cout<<min(b,n*a);
	
	
	return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <map>
#include <algorithm>

int testcase_ends() {
  size_t n, m, a;
  scanf("%zu %zu %zu", &n, &m, &a);
  if (n == 0 && m == 0 && a == 0) return 1;

  std::map<std::pair<size_t, size_t>, size_t> line;
  for (size_t i = 0; i < m; ++i) {
    size_t h, p, q;
    scanf("%zu %zu %zu", &h, &p, &q);
    line[{h, p}] = q;
    line[{h, q}] = p;
  }

  for (size_t i = 1000; i >= 1; --i) {
    auto it = line.find({i, a});
    if (it == line.end()) continue;
    a = it->second;
  }
  printf("%zu\n", a);
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}



Measured memory_bytes: 2792
#include<iostream>
using namespace std;
int a[20];
bool n[101];
int main(){
	for(int i=1;i<10;i++)cin>>a[i];
	int N;cin>>N;
	int i;
	while(N--){
		cin>>i;
		n[i]=1;
	}
	bool f=0;
	if(n[a[1]]){
		if(n[a[2]]&&n[a[3]])f=1;
		if(n[a[4]]&&n[a[7]])f=1;
		if(n[a[5]]&&n[a[9]])f=1;
	}
	if(n[a[5]]){
		if(n[a[4]]&&n[a[6]])f=1;
		if(n[a[2]]&&n[a[8]])f=1;
		if(n[a[3]]&&n[a[7]])f=1;
	}
	if(n[a[9]]){
		if(n[a[7]]&&n[a[8]])f=1;
		if(n[a[3]]&&n[a[6]])f=1;
	}
	if(f)cout<<"Yes";
	else cout<<"No";
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
    	//AtCoder Beginner Contest 053
    	//b
    	Scanner sc = new Scanner(System.in);
    	String s = sc.next();
        int x = s.length();
    	String[] arry = s.split("");
    	boolean flag = false;
    	int h = 0;
    	int o = 0;
    	for(int i = 0; i < x; i++){
    		if("A".equals(arry[i]) && flag == false){
    			flag = true;
    			h = i;
    		}
    		if("Z".equals(arry[i])) o = i;
    	}
    	System.out.println(o-h+1);
    }
}

Measured memory_bytes: 52424
#include<stdio.h>
 
int main ()
{
     
    int n,m,l,i,t,a,b,k;
    long long A[100][100]={},B[100][100]={},AB[100][100]={};
     
    scanf("%d %d %d",&n,&m,&l);
     
    for(i=0;i<n;i++)
    {
        for(t=0;t<m;t++)
        {
            scanf("%d",&a);
            A[i][t] = a;
        }
    }
     
    for(i=0;i<m;i++)
    {
        for(t=0;t<l;t++)
        {
            scanf("%d", &b);
            B[i][t] = b;
        }
    }
     
    for(i=0;i<n;i++)
    {
        for(t=0;t<l;t++)
        {
            for(k=0;k<m;k++)
            {
                AB[i][t] += A[i][k] * B[k][t];
            }
            printf("%lld", AB[i][t]);
            if(t != l-1)
            {
                printf(" ");
            }
        
            else
            {
                printf("\n");
            }
        }
    }
 
return 0;
}


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

template<typename T>
struct WeightedUnionFind {
    vector<int> data;
    vector<T> ws;
    WeightedUnionFind(int sz) : data(sz, -1), ws(sz) { }
    bool merge(int x, int y, T w) {             // ws(y) = ws(x) + w
        w += weight(x); w -= weight(y);
        if ((x = root(x)) == (y = root(y))) return false;
        if (data[x] > data[y]) swap(x, y), w = -w;
        data[x] += data[y]; data[y] = x; ws[y] = w;
        return true;
    }
    bool is_same(int x, int y) { return root(x) == root(y); }
    T diff(int x, int y) { return weight(y) - weight(x); }
    T weight(int t) { root(t); return ws[t]; }
    int root(int k) {
        if (data[k] < 0) return k;
        int par = root(data[k]);
        ws[k] += ws[data[k]];
        return data[k] = par;
    }
};

int main() {
    int n, m; cin >> n >> m;
    WeightedUnionFind<int> wuf(n);
    while (m--) {
        int l, r; cin >> l >> r; l--, r--;
        int d; cin >> d;
        if (wuf.is_same(l, r)) {
            if (wuf.diff(l, r) != d) return !(cout << "No" << endl);
        } else {
            wuf.merge(l, r, d);
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	int D, W;
	while (cin >> D >> W, D) {
		vector<vector<int> > e(D, vector<int>(W));
		for (int i = 0; i < D; ++i)
			for (int j = 0; j < W; ++j)
				cin >> e[i][j];
		int ans = 0;
		for (int u = 0; u < D; ++u) {
			for (int d = u + 2; d < D; ++d) {
				for (int l = 0; l < W; ++l) {
					for (int r = l + 2; r < W; ++r) {
						int mini = 1e9;
						for (int x = u; x <= d; ++x) mini = min({ mini, e[x][l], e[x][r] });
						for (int y = l; y <= r; ++y) mini = min({ mini, e[u][y], e[d][y] });
						bool flag = true;
						int tmp = 0;
						for (int x = u + 1; x < d; ++x) {
							for (int y = l + 1; y < r; ++y) {
								if (e[x][y] >= mini) {
									tmp = 0, flag = false;
									goto en;
								} else tmp += mini - e[x][y];
							}
						}
						en:
						ans = max(ans, tmp);
					}
				}
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3128
n = int(input())
S = list(input())

# aを含む -> 個数通り 含まない-> 1
# bを含む -> 個数通り 含まない-> 1
from collections import defaultdict
d = defaultdict(int)
for s in S:
    d[s] += 1
ans = 1
mod = 10**9 + 7
for k in d.keys():
    ans *= (d[k]+1)
    ans %= mod
ans -= 1
print(ans)

Measured memory_bytes: 9832
N = int(input())
L = list(map(int,input().split()))
count = 0
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if L[i] != L[j] and L[i] != L[k] and L[j] != L[k]:
        if L[i]+L[j] > L[k] and L[i]+L[k] > L[j] and L[j]+L[k] > L[i]:
          count += 1

print(count)

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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
ll K;
ll i, j, k,ans;
ll gcd(ll a,ll b){
    if(b==0)
        return a;
    return gcd(b, a % b);
}
int main(){
    scanf("%lld", &K);
    fornum(i,0,K){
        fornum(j,0,K){
            fornum(k,0,K){
                ans += gcd(gcd(i + 1, j + 1), k + 1);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

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

typedef long long ll;
#define pii pair<int , int>
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAXX 1005

int main()
{
    _FastIO;

    string s , t;
    cin >> s >> t;
    int n = s.size();
    vector<bool> used(50 , false);
    vector<bool> visited(50 , false);
    vector<char> c(50);
    vector<char> ch(50);
    string ans = "Yes";
    for(int i = 0; i < n; i++){
        int x = int(s[i]) - 97;
        int y = int(t[i]) - 97;
        if(!used[x]){
            c[x] = y;
            used[x] = true;
        }
        else{
            if(y != c[x])
                ans = "No";
        }
        if(!visited[y]){
            ch[y] = x;
            visited[y] = true;
        }
        else{
            if(x != ch[y])
                ans = "No";
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;
int main(){
  int A,B,M;
  cin>>A>>B>>M;
  
  vector<int> av(A);
  for(int i =0; i<A;i++){
    cin>>av[i];
  }
  
  vector<int> bv(B);
  for(int i = 0; i<B; i++){
    cin>>bv[i];
  }
  
  vector<int> cv(M);
  for(int i = 0; i<M ; i++){
    int c,d,e;
    cin>>c>>d>>e;
    cv[i]=av[c-1]+bv[d-1]-e;
  }
  sort(cv.begin(),cv.end());
  sort(av.begin(),av.end());
  sort(bv.begin(),bv.end());
  if(cv[0]<=av[0]+bv[0]){
    cout<<cv[0]<<endl;
  }
  else {
    cout<<av[0]+bv[0]<<endl;
  }
}           


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL<<60;
typedef pair<ll, ll> P;

bool same(char &a, char &b){
    return a == '?' || b == '?' || a == b;
}

int main() {
    string a, b, c;
    cin>>a>>b>>c;
    ll C;
    A = a.size();
    B = b.size();
    C = c.size();
    vector<bool> ab(1e+5, true), bc(1e+5, true), ca(1e+5, true);
    const int m = 50000;
    rep(i, A) rep(j, B) if(!same(a[i], b[j])) ab[i - j + m] = false;
    rep(i, B) rep(j, C) if(!same(b[i], c[j])) bc[i - j + m] = false;
    rep(i, C) rep(j, A) if(!same(c[i], a[j])) ca[i - j + m] = false;
    ll ans = A + B + C;
    reps(i, -4001, 4001) reps(j, -4001, 4001){
        //a:0, b:+i, c:+jなので
        if(ab[i + m] && bc[j - i + m] && ca[m - j]){
            ans = min(ans, max({A, B + i, C + j}) - min({0, i, j}));
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cmath>
#include <set>

using namespace std;

struct UnionFind {
    vector<int> par;

    UnionFind(int N) : par(N, -1) {}
    void init(int N) { par.assign(N, -1); }

    int root(int x) { //木の根を求める
        if (par[x] < 0) return x; //根の判定
        else return (par[x] = root(par[x])); //経路圧縮
    }

    bool same(int x, int y) { //xとyが同じ集合か判定
        return root(x) == root(y);
    }

    bool merge(int x, int y) { //xとyの属する集合を併合する
        x = root(x); y = root(y);
        if (x == y) return false; //根が同じ時はそのまま
        if (par[x] > par[y]) swap(x, y); //要素が少ない方をくっつける
        par[x] += par[y];   //子の要素数を根に足す
        par[y] = x;         //根を設定する
        return true;
    }
    int size(int x) {
        return -par[root(x)]; //根は要素を追加するたびに-1が足されるので、-parで同じ集合の要素数がわかる
    }
};
int main()
{
    int n, m, x, y, z;
    cin >> n >> m;
    bool cnt[100010] = {};
    int ans = 0;

    UnionFind a(n+1);

    for (int i = 0; i < m; i++) {
        cin >> x >> y >> z;
        a.merge(x, y);
    }

    for (int i = 1; i <= n; i++) {
        if (cnt[a.root(i)] == 0) {
            ans++;
            cnt[a.root(i)] = 1;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 768
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=5e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  int n,a,f=1;
  cin >> n;
  for(int i=0; i<n; i++) {
    cin >> a;
    if(a%2==0) {
      if(a%3!=0&&a%5!=0) {
        f=0;
      }
    }
  }
  cout << (f?"APPROVED":"DENIED") << endl;
}

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

const int N = 100005, inf = 0x3f3f3f3f;

int n, s, t, p[N], q[N], L[N], R[N], head[N], dis[N], cur[N];
int left[N], right[N], tot = 1, idx;
bool vis[N];

struct edge { int to, nxt, rem; } e[N * 10];

void link(int x, int y, int z, int w = 0) {
	e[++tot] = (edge) { y, head[x], z }, head[x] = tot;
	e[++tot] = (edge) { x, head[y], w }, head[y] = tot;
}

bool bfs() {
	std::memset(dis, 0, idx + 1 << 2);
	std::queue<int> q; q.push(s), dis[s] = 1;
	while (q.size()) {
		int tmp = q.front(); q.pop();
		for (int i = head[tmp]; i; i = e[i].nxt)
			if (e[i].rem && !dis[e[i].to])
				dis[e[i].to] = dis[tmp] + 1, q.push(e[i].to);
	}
	return dis[t] > 0;
}
int dinic(int x, int low) {
	if (x == t || !low) return low;
	int ans = 0, t;
	for (int &i = cur[x]; i; i = e[i].nxt)
		if (e[i].rem && dis[e[i].to] == dis[x] + 1 && (t = dinic(e[i].to, std::min(low, e[i].rem)))) {
			e[i].rem -= t, e[i ^ 1].rem += t, ans += t, low -= t;
			if (!low) break;
		}
	return ans;
}

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n;
	for (int i = 0; i < n; ++i) std::cin >> p[i];
	for (int i = 0; i < n; ++i) std::cin >> q[i];
	for (int i = 0; i < n; ++i) if (!vis[i]) {
		++idx;
		for (int j = i; !vis[j]; vis[j] = 1, j = p[j]) L[j] = idx;
	}
	std::memset(vis, 0, sizeof vis);
	for (int i = 0; i < n; ++i) if (!vis[i]) {
		++idx;
		for (int j = i; !vis[j]; vis[j] = 1, j = q[j]) R[j] = idx;
	}
	t = ++idx;
	int ans = n;
	for (int i = 0; i < n; ++i) if (p[i] != i || q[i] != i) {
		if (p[i] == i) {
			++left[R[i]];
		} else if (q[i] == i) {
			++right[L[i]];
		} else if (p[i] == q[i]) {
			link(L[i], R[i], 1, 1);
		} else {
			link(L[i], R[i], 1);
		}
	} else --ans;
	for (int i = 1; i < idx; ++i) {
		if (left[i]) link(s, i, left[i]);
		if (right[i]) link(i, t, right[i]);
	}
	while (bfs()) std::memcpy(cur, head, idx + 1 << 2), ans -= dinic(s, inf);
	std::cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 11520
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;

ll GCD(ll a, ll b){
    if(b==0) return a;
    else return GCD(b,a%b);
}
 
int main(){
    ll a,b; cin >> a >> b;
    if(a==1) a+=13; if(b==1) b+=13;
    if(a==b) puts("Draw");
    else if(a>b) puts("Alice");
    else puts("Bob");
}


Measured memory_bytes: 256
#!/usr/bin/ruby
# -*- coding: utf-8 -*-
=begin
ITP1_11-A
Structure and Class - Dice I
Time Limit : 1 sec, Memory Limit : 65536 KB
???????????? I

?¬?????±??????????????????????????????????????????¢??????????????\??¬????????§????????????????????°????????????????????????????????????

????????????????????¢??????????????¨????????? 1 ?????? 6 ????????????????????????????????????????????????

??\?????¨??????????????????????????¢?????????????????????????????°?????¨?????¢?????????????????????????????????????????§???????????????????????¢?????°?????????????????????????????????????????\??¬????????§??????????????¶?????????????????¨?????????????????????????????§?????????????????????????????????????????¨????????????
Input

?????????????????¢?????°???????????????????????????????????????????????????????????§?????????????????????

???????????????????????¨????????????????????????????????????????????????????????????????????????????????????????????¨????????? E???N???S???W ????????????????????§??????
Output

???????????????????????????????????????????????????????????¢?????°???????????????????????????????????????
Constraints

    0???

??\?????????????????????????????¢?????°??? ???100
0???
???????????¨????????????????????? ???100

Note

?¶???????????????? Dice III, Dice IV ??§???????????°????????????????????±????????§???????????????????????????????§?????????§?????????????????????????????????
Sample Input 1

1 2 4 8 16 32
SE

Sample Output 1

8

?????¢??? 1, 2, 4, 8, 16, 32 ??¨??????????????????????????? S ??????????????¢???????????????E ??????????????¢????????¨????????¢?????°?????? 8 ??????????????????


Sample Input 2

1 2 4 8 16 32
EESWN

Sample Output 2

32

Note
=end
class Dice
  def initialize(f)
    @face = Array.new(7,"")
    (0.upto(f.length-1)).each {|i| @face[i+1] = f[i]} 
  end

  def dump
    d = @face.dup
    d.shift
    d.join(" ")
  end

  def e
    tmp = @face[1] 
    @face[1] = @face[4]
    @face[4] = @face[6]
    @face[6] = @face[3] 
    @face[3] = tmp
    @face[1]
  end

  def w
    tmp = @face[1] 
    @face[1] = @face[3]
    @face[3] = @face[6]
    @face[6] = @face[4]
    @face[4] = tmp
    @face[1]
  end

  def n
    tmp = @face[1] 
    @face[1] = @face[2]
    @face[2] = @face[6]
    @face[6] = @face[5]
    @face[5] = tmp
    @face[1]
  end

  def s
    tmp = @face[1] 
    @face[1] = @face[5]
    @face[5] = @face[6]
    @face[6] = @face[2]
    @face[2] = tmp
    @face[1]
  end

  def upface
    @face[1]
  end

end

class Main
  def initialize
    fh = STDIN
    fl = fh.gets.chomp.split
    abort "small face data" if fl.length != 6
    d = Dice.new(fl)
    cmd = fh.gets.chomp.split(//)
    cmd.each {|c|
      if c=="E" then
        d.e
      elsif c=="E" then
        d.e
      elsif c=="W" then
        d.w
      elsif c=="N" then
        d.n
      elsif c=="S" then
        d.s
      else
        abort "Unknown cmd=#{c}"
      end
    }
    puts d.upface
  end
end

if $0==__FILE__ then
  Main.new()
end

Measured memory_bytes: 8728
N = int(raw_input())
r = 1.08

candidate = int(N/r)

flag = False
max_value = 0
for i in range(-50, 50):
    value = int((candidate + i)*r)
    if value == N:
        if candidate+i > max_value:
            max_value = candidate+i
        flag = True


if flag == True:
    print max_value
else:
    print ":("


Measured memory_bytes: 2568
a = [1,3,5,7,8,10,12]
b = [4,6,9,11]
c = [2]
x,y = gets.chomp.split.map(&:to_i)
if x == 2 || y == 2
    puts 'No'
elsif a.include?(x) && a.include?(y) || b.include?(x) && b.include?(y)
    puts 'Yes'
else
    puts 'No'
end



Measured memory_bytes: 1788
const main = (input) => {
  input = input.trim().split("\n");
  var p = input.filter((v,i)=>i<5);
  var k = input[5];
  var ans = true;
  for(var i=0;i<=4;i++){
    for(var j=i+1;j<=4;j++){
      if(Math.abs(p[i]-p[j]) > k) ans = false;
    }
  }

  console.log(ans?"Yay!":":(");
}

main(require('fs').readFileSync('/dev/stdin', 'UTF-8'));


Measured memory_bytes: 21064
#include<bits/stdc++.h>
using namespace std ;
const int maxn=2e5+10;
int x[10],y[10];
int main() {
	int n;
	scanf("%d",&n);
	double sum=0;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&y[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			sum+=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		}
	}
	sum*=n-1;
	int q=1;
	for(int i=1;i<=n;i++)q*=i;
	sum/=(n-1)*n;
	printf("%.10f\n",sum);
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func read() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	// sc.Split(bufio.ScanLines)
	sc.Split(bufio.ScanWords)
	n, _ := strconv.Atoi(read())
	s := make([]int, 3)
	for i := 0; i < n; i++ {
		s[0], _ = strconv.Atoi(read())
		s[1], _ = strconv.Atoi(read())
		s[2], _ = strconv.Atoi(read())
		sort.Sort(sort.IntSlice(s))
		if (s[2] * s[2]) == ((s[0] * s[0]) + (s[1] * s[1])) {
			fmt.Println("YES")
		} else {
			fmt.Println("NO")
		}
	}
}



Measured memory_bytes: 1096