akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define mp make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pll pair<ll,ll>
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<=n;i++)
ll mod=1000000007;
ll n,k,t,m,q,flag=0;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds; 
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(a) -- no. of elements strictly less than a
// s.find_by_order(i) -- itertor to ith element (0 indexed)
ll min(ll a,ll b){if(a>b)return b;else return a;}
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifdef NOOBxCODER
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #else 
    #define NOOBxCODER 0
    #endif
    //cin>>t;
    t=1;
    while(t--){
        string s;
        cin>>s;
        ll ans=0;
        fo(i,s.size())ans+=s[i]-'0';
        if(ans%9==0)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;





        
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}


Measured memory_bytes: 3972
#include <iostream>
#include <cmath>

long long Pow(int x, int y)
{
	long long z = 1;
	for (int i = 0; i < y; i++){
		z *= x;
	}
	return z;
}

int main()
{
	int x;
	std::cin >> x;
	
	int a, b;
	long long a5;
	a = std::pow(x / 2.0, 1.0 / 5.0);
	while (true) {
		a5 = Pow(++a, 5);
		if (a5 == x) {
			b = 0;
			break;
		}
		if (a5 > x) {
			b = std::pow(a5 - x, 1.0 / 5.0);
			if (Pow(b, 5) == a5 - x) {
				break;
			}
		}
		else {
			b = std::pow(x - a5, 1.0 / 5.0);
			if (Pow(b, 5) == x - a5) {
				b = -b;
				break;
			}
		}
	}
	
	std::cout << a << ' ' << b << std::endl;
	
	return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main(void) {
  int A, B, C, X;
  cin >> A >> B >> C >> X;

  vector<int> MONEY(25001, 0);
  for(int a = 0; a <= A; ++a) {
    for(int b = 0; b <= B; ++b) {
      for(int c = 0; c <= C; ++c) {
        int val = 500 * a + 100 * b + 50 * c;
        MONEY[val]++;
      }
    }
  }
  cout << MONEY[X] << endl;
  return 0;
}

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

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    int ans = 0;
    int da, db;
    rep(i, n) {
        cin >> da >> db;
        if (da == db) cnt++;
        else cnt = 0;
        ans = max(ans, cnt);
    }
    if (ans >= 3) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
//#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int LL;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2

ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define endl "\n"
#define SORT(v) sort(v.begin(),v.end())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define POSL(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define POSU(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
//template<class T>void max(T a,T b){if(a<b)return b;else return a;}
//template<class T>void min(T a,T b){if(a>b)return b;else return a;}
//template<class T>bool Max(T&a, T b){if(a < b){a = b;return 1;}return 0;}
//template<class T>bool Min(T&a, T b){if(a > b){a = b;return 1;}return 0;}

//////////////////////////


int main(){fastio
    ll n;cin>>n;
    dd p[n];rep(i,0,n-1)cin>>p[i];
    dd dp[n+1][n+1];memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    rep(i,1,n){
        rep(j,0,i){
            if(j-1>=0)dp[i][j]+=dp[i-1][j-1]*p[i-1];
            dp[i][j]+=dp[i-1][j]*(1-p[i-1]);
        }
    }
    /*
    rep(i,0,n){
        rep(j,0,n){
            cout<<dp[i][j]<<" ";
        }cout<<endl;
    }cout<<endl;
    */
    dd ans=0;
    rep(j,n/2+1,n){
        ans+=dp[n][j];
    }
    cout<<setprecision(20)<<ans<<endl;
    
    return 0;
}



Measured memory_bytes: 140928
#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 rrep(i,n) for(int i=((int)(n)-1);i>=0;(i)--)
#define rrep1(i,n) for(int i=((int)(n));i>0;(i)--)
#define sz(c) ((int)(c).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> P;
typedef pair<int, pair<int, int> > PP;
const int MAX=1e5+10;
const int MOD=1e9+7;

int N,K;
int a[101];
void input(){
    cin>>N>>K;
    rep1(i,N)cin>>a[i];
}

int dp[101][MAX];
int sum[101][MAX];
void solve(){
    dp[0][0]=1;
    sum[0][0]=0;
    rep1(ca,K+1)sum[0][ca]=1;

    rep1(i,N)rep(ca, K+2){
        dp[i][ca]=(sum[i-1][ca+1]-sum[i-1][max(0,ca-a[i])]+MOD)%MOD;
        sum[i][ca]=(sum[i][ca-1]+dp[i][ca-1])%MOD;
    }
}

void output(){
    cout<<dp[N][K];
}

int main(){
    input();
    solve();
    output();
}

Measured memory_bytes: 79104
#include <iostream>
#include <set>

int main() {
    int N;
    std::set<std::string> items;
    std::cin >> N;

    while(N--){
        std::string item;
        std::cin >> item;
        items.insert(item);
    }

    std::cout << items.size() << std::endl;
    return 0;
}

Measured memory_bytes: 19124
#include <cstdio>
#include <iostream>

using namespace std;

int main() {

	int n;
	scanf("%d", &n);

	int A[n];
	for (int i = 0; i < n; ++i) {
		scanf("%d", &A[i]);
	}
	int L[n];
	L[0] = A[0];
	int length = 1;
	for (int i = 1; i < n; ++i) {
		if (A[i] > L[length - 1]) {
			L[length++] = A[i];
		} else {
			int l = 0;
			int r = length;
			while (l < r) {
				int mid = (l + r) / 2;
				if (L[mid] < A[i]) {
					l = mid + 1;
				} else {
					r = mid;
				}
			}
			L[l] = A[i];
		}
	}
	cout << length << endl;

	return 0;
}

Measured memory_bytes: 3976
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=100000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};


int main() {

	int x;
	int max=0;
	int o=0;
	cin>>x;

	for(int i=1; i<x+1; ++i){
		o=i;
		for(int j=1; j<11; ++j){
			if(o*i>x){
				break;
			}else{
				if(o*i>max){
					max=o*i;
				}
				o=o*i;

			}
		}
	}


	cout<<max<<endl;

	return 0;
}


Measured memory_bytes: 256
def get_cost(l, r):
    # 区間[l, r]の結合を分解し切るコスト
    if memo[l][r] < INF: return memo[l][r]
    if r == l: return 0

    t = INF
    for m in range(l, r):
        t = min(t, get_cost(l, m) + get_cost(m + 1, r))
    memo[l][r] = t + (c_sum[r] - c_sum[l - 1])
    return memo[l][r]


N = int(input())
a = list(map(int, input().split()))

c_sum = [0]
for aa in a:
    c_sum.append(c_sum[-1] + aa)
# 累積和

INF = float('inf')

memo = [[INF for _ in range(N + 1)] for _ in range(N + 1)]
# 区間[l, r]の結合を分解し切るコスト

print(get_cost(1, N))

Measured memory_bytes: 50012
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const long long mod = 1000000007;
const long long inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m;
    cin>>n>>m;
    cout<<(n-1)*(m-1)<<endl;
    return 0;
}


Measured memory_bytes: 256
def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[0]*l for _ in range(K+1)]
        dp2[0] = [10**13]*l
        t = [[0]*l for _ in range(K)]
        for i in range(K):
            for j in range(l):
                t[i][j] = dp[i][j]+a[j]
        min_s = [[10**13]*l for i in range(K+1)]

        for i in range(K):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(dp[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]

        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])

        for i in range(K+1):
            temp = 10**13
            for j in range(l):
                temp = min(temp, dp[i][j]+max(h-s[j], 0))
            dp2[i][dh] = min(dp2[i][dh], temp)
        dp = dp2
    print(min([min(i) for i in dp]))


main()

Measured memory_bytes: 141704
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N, K; string S;  
	cin >> N >> K >> S; 
	int same = 0; 
	for(int i = 0; i < N-1; i++){
		if(S[i] == S[i+1]) same ++; 
	}
	cout << min(same + 2 * K, N-1) << endl; 
}

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

int N, M, L;
int P[100], T[100], V[100];
double dp[101][52];
double tim[101][52];
double small[52][52];

int main()
{
  cin >> N >> M >> L;
  for(int i = 0; i < N; i++) {
    cin >> P[i] >> T[i] >> V[i];
  }

  
  for(int i = 0; i < N; i++) {
    memset(small, 0, sizeof(small));
    small[0][0] = 1.0;
    for(int j = 0; j < M; j++) {
      for(int k = 0; k <= j; k++) {
        small[j + 1][k + 1] += small[j][k] / 100.0 * P[i];
        small[j + 1][k]     += small[j][k] / 100.0 * (100 - P[i]);
      }
    }
    for(int j = 0; j <= M; j++) {
      tim[i][j] = (V[i] == 0 ? 1e18 : 1.0 * L / V[i] + j * T[i]);
      dp[i][j] = small[M][j];
    }
  }
  cout << fixed << setprecision(10);
  
  for(int i = 0; i < N; i++) {
    double ret = 0;
    for(int j = 0; j <= M; j++) {
      double per = dp[i][j];
      for(int k = 0; k < N; k++) {
        if(i == k) continue;
        double qur = 0.0;
        for(int l = 0; l <= M; l++) {
          if(tim[i][j] < tim[k][l]) qur += dp[k][l];
        }
        per *= qur;
      }
      ret += per;
    }
    cout << ret << endl;
  }
}

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

using namespace std;
using Graph = vector<vector<int>>;
int main(){

long long n;cin >> n;
vector<long long> a(n);
long long b[n+1],ch[n+1],noch[n+1],minus[n+1];
b[0]=0;ch[0]=0;noch[0]=0;minus[0]=0;
for (long long i = 0; i <=n; ++i)
{
    b[i]=0;
}
for (long long i = 0; i < n; ++i)
{
    long long num;
    cin >> num;
    a[i]=num;
    b[num]++;
}
long long ans=0;

for (long long i = 1; i <= n; ++i)
{
  ch[i]=b[i]*(b[i]-1)/2;
  noch[i]=(b[i]-2)*(b[i]-1)/2;
  minus[i] = ch[i]-noch[i];
  ans+=ch[i];
  
}

for (long long i = 0; i < n; ++i)
{
    long long res;
    res = ans- minus[a[i]];
    cout << res<<"\n";
}

return 0;
}




Measured memory_bytes: 10368
//Robot Arms

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define irep(i,a) for(auto i = a.begin(); i != a.end(); ++i)
#define nvarep(n,a) ll n;cin>>n;vector<ll>a(n);rep(i,0,n)cin>>a[i]
#define vecrep(n,a,type) vector<type>a(n);rep(i,0,n)cin>>a[i]
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
using p = pair<ll, string>;
using garph = vector<vector<ll>>;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

signed main (){
    int n;cin>>n;
    vector<tuple<int,int,int>>a(n);
    rep(i,0,n){
        int q,w,e;cin>>w>>e;
        q=w+e;
        a[i]=make_tuple(q,w,e);
    }
    sort(range(a));
    int lst=-inf,ans{};
    rep(i,0,n){
        if((get<1>(a[i])-get<2>(a[i]))>=lst){
            ans++;
            lst=get<0>(a[i]);
        }
    }
    cout<<ans<<nnn;
    return 0;
}

Measured memory_bytes: 5632
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    while(true){
        int n;
        cin >> n;
        if(n == 0)
            break;
        
        vector< pair<double, string> > v(n);
        for(int i=0; i<n; i++){
            string l;
            int p, a, b, c, d, e, f, s, m;
            cin >> l >> p >> a >> b >> c >> d >> e >> f >> s >> m;
            v[i].first = -(double)(m * f * s -p) / (double)(a + b + c + m*(d + e));
            v[i].second = l;
        }
        sort(v.begin(), v.end());
        for(int i=0; i<n; i++){
            cout << v[i].second << endl;
        }
        cout << '#' << endl;
    }
  
    return 0;
}

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

int main()
{
  int n;
  cin >> n;
  int d[n];
  for(int i=0;i<n;++i){
    cin >> d[i];
  }
  
  int ans=0;
  for(int i=0;i<n-1;++i){
    for(int j=i+1;j<n;++j){
      ans+=d[i]*d[j];
    }
  }
  
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include<string.h>
int main(void){

 char S[3];
  scanf("%s",S);
  //printf("%s\n",S);
  if(strcmp(S,"SUN")==0)
    printf("7\n");
  if(strcmp(S,"MON")==0)
      printf("6\n");
  if(strcmp(S,"TUE")==0)
      printf("5\n");
  if(strcmp(S,"THU")==0)
      printf("3\n");
  if(strcmp(S,"FRI" )==0)
      printf("2\n");    
  if(strcmp(S,"SAT" )==0)
      printf("1\n");
  if(strcmp(S,"WED" )==0)
      printf("4\n");
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/detail/standard_policies.hpp>
// using namespace __gnu_pbds;

#pragma GCC optimize("O3")
#ifdef LOCAL
#include "debug_utils.h"
#else
#define print(...) ;
#define printn(...) ;
#endif

#define rep(i, a, b) for(auto i = (a); i < (b); i++)
#define rrep(i, a, b) for(auto i = (a); i > (b); i--)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxi(x, y) x = max(x, y)
#define mini(x, y) x = min(x, y)
#define endl '\n'
#define solve_testcase int T;cin>>T;for(int t=1;t<=T;t++){solve(t);}

long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }

typedef unsigned long long ull;
typedef long long ll;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdd;
typedef vector<long long> vll;

const int MAXN = 1e6 + 10;
void solve(int tt) {}

string s;
int a[MAXN];
int n;

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

    cin>>n;
    cin>>s;
    int ok=0;
    rep(i,0,n){a[i]=s[i]-'1';if(a[i]==1)ok=1;}
    if(ok) rep(i,0,n) a[i]%=2;
    else rep(i,0,n) a[i]/=2;
    // print(ok);
    // printn(a,n);

    int res=ok?1:2,tmp=a[0]^a[n-1],den=n-1,num=1,cur=0;
    rep(i,1,n-1) {
        cur+=__builtin_ctz(den)-__builtin_ctz(num);
        // print(i,cur);
        den--;num++;
        if(!cur) tmp^=a[i];
    }
    cout<<res*tmp<<endl;

    // rep(i,0,n-1) {
    //     rep(j,0,n) {
    //         a[j]^=a[j+1];
    //     }
    //     printn(a,n);
    // }




    return 0;
}





















Measured memory_bytes: 5276
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N, M = map(int, input().split())
    dp = {1:[1,True]}         #dp[i]  iの箱の状態　[x個]赤がいる可能性がある
    for _ in range(2,N+1):
        dp[_] = [1,False]
    for _ in range(M):
        fm, to = map(int, input().split())
        num, state = dp[fm]
        #fmの処理
        dp[fm][0]-=1    #移動
        if dp[fm][0]==0:
            dp[fm][1] = False
        #toの処理
        dp[to][0]+=1    #移動
        dp[to][1]=dp[to][1] or state
    ret = 0
    for _ in range(1,N+1):
        ret += dp[_][1]
    print(ret)

if __name__ == '__main__':
    main()

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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

int n;

double closest_pair(vector<pair<double, double>> &v) {
    sort(v.begin(), v.end());
    double ans = DBL_MAX;
    set<pair<double, double>> box;
    int lt = 0;
    box.insert({v.front().second, v.front().first});
    for (int i = 1; i < n; i++) {
        while (lt < i and v[i].first - v[lt].first > ans)box.erase({v[lt].second, v[lt].first}), lt++;
        for (auto it = box.lower_bound({v[i].second - ans, v[i].first - ans});
             it != box.end() and v[i].second + ans >= it->first; it++) {
            ans = min(ans, sqrt(pow(v[i].first - it->second, 2) + pow(v[i].second - it->first, 2)));
        }
        box.insert({v[i].second, v[i].first});
    }
    return ans;
}

void solve() {
    cin >> n;
    vector<pair<double, double>> v(n);
    for (int i = 0; i < n; i++)cin >> v[i].first >> v[i].second;
    cout << fixed << setprecision(10) << closest_pair(v) << endl;
}

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

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}


Measured memory_bytes: 9232
#include <bits/stdc++.h>
using namespace std;
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

int main(){
int n;
  cin>>n;
  vector<int> a(n);
  int ans=0;
  for(int i=0;i<n;i++){
    cin>>a[i];
    if( IsPrime(a[i])){
      ans++;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,m,n) for(int i=(m);i<(n);i++)
#define fore(i,a) for(auto &i:a)
#define debug(a,b) cout << "debug : " << a << " , "<< b << endl
using ll=long long;
const ll INF=1LL<<60;
const ll mod=1E9+7;


int main(){
  ll a,b;
  cin >> a >> b;
  auto gcd=[](ll a,ll b){
    ll temp=b;
    while(a%b!=0){
      temp=b;
      b=a%b;
      a=temp;
    }
    return b;
  };
  cout << a*b/gcd(a,b) << endl;
}
    




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
vector<int> prime;
void seive(int x){
    vector<bool> isprime(x,true);
    for(int p=2;p*p<=x;p++){
        if(isprime[p]){
            for(int i=p*p;i<=x;i+=p) isprime[i]=false;
        }
    }
    for(int i=2;i<=x;i++) prime.push_back(i);
}
ll power(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b%2!=0) res=(res*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return res;
}
/*------------------------------------------------------------
------------------------------------------------------------*/
ll ncr(ll n,ll k){
    if(n<k) return 0ll;
    if(k>n-k) k=n-k;
    ll pro=1;
    for(int i=0;i<k;i++){
        pro*=(n-i);
        pro/=(i+1);
    }
    return pro;
}
int main(void){
    ll n;
    boost;
    cin>>n;
    map<string,int> m;
    for(int i=0;i<n;i++){
        string str;
        cin>>str;
        sort(str.begin(),str.end());
        m[str]++;
    }
    ll sum=0;
    for(auto itr:m){
        sum+=ncr(itr.second,2);
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 11264
#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define lli long long int
#define test                lli t;cin>>t;while(t-->0)
#define ainput  int n;cin>>n;int a[n];for(int i=0;i<n;i++){cin>>a[i];}
#define vec vector<lli>v;
vec
#define avinput  int n;cin>>n;int a[n];for(int i=0;i<n;i++){cin>>a[i];v.push_back(a[i]);}
#define vp  for(lli i=0;i<v.size();i++) {cout<<v[i]<<" ";}cout<<endl;
#define vp1  for(lli i=0;i<v1.size();i++) {cout<<v1[i]<<" ";}cout<<endl;
#define vp2  for(lli i=0;i<v2.size();i++) {cout<<v2[i]<<" ";}cout<<endl;
#define vp3  for(lli i=0;i<v3.size();i++) {cout<<v3[i]<<" ";}cout<<endl;
#define vp6  for(lli i=0;i<v6.size();i++) {cout<<v6[i].first<<" "<<v6[i].second<<endl;}
#define ln cout<<endl;
  //cout << fixed << setprecision(10) <<((double)((sum*1.0)/((n*1.0-k*1.0)+1.0))) << endl;
set<lli>s1;
set<lli>s2;
set<string>st2;
vector<lli>v1;
vector<lli>v2;
vector<lli>v3;
vector<lli>v4;
vector<lli>v5;
vector<pair<lli,lli> >v6;
vector<pair<char,int> >v16;
vector<string>v7;
vector<string>v8;
vector<char>v9;
vector<double>v11;
list<lli>l;
//****coding start****
int main()
{
char a;cin>>a;
if(a=='A')cout<<"T"<<endl;
if(a=='T')cout<<"A"<<endl;
if(a=='C')cout<<"G"<<endl;
if(a=='G')cout<<"C"<<endl;
    return 0;
}

Measured memory_bytes: 3568
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int main() {
  int n, x;
  int m[100];
  cin >> n >> x;
  for (int i=0; i<n; ++i) cin >> m[i];

  int ans = 0;
  int min_m = m[0];
  for (int i=0; i<n; ++i) {
    x -= m[i];
    if (min_m > m[i]) min_m = m[i];
    ++ans;
  }

  ans += x/min_m;

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

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <iomanip>
#define f(i,a,b) for(ll i=a;i<b;i++)
#define r(i,a,b) for(ll i=a;i>b;i--)
using namespace std;
typedef long long ll;
typedef long double ld;

int main(){

ll n; cin>>n;
ll x=n;

if(x==1){
  cout << "0" << endl;
  return 0;
}

vector<ll> v;
vector<ll> c;

while(n%2==0){
  v.push_back(2);
  n=n/2;

}


for(ll i=3; i<sqrt(x); i+=2){
  
  while(n%i==0){
    v.push_back(i);
    n=n/i;
    }
  
      if(n==1){
       break;
       }
}

for(ll i=2; i<sqrt(x); i++){

  ll z; z=count(v.begin(),v.end(),i);

    if(z!=0){
     c.push_back(z);
     }
}

ll count=0;
for(ll i=0; i<c.size(); i++){

ll f=c[i];

  for(ll g=1; g<50; g++){
 
    if((g*(g+1)/2)<=c[i]){
     count+=1;
       }else{
        break;
        }
   }
}

if(n!=1){
  count+=1;
}

if(count==0){
  cout << "1" << endl;
   }else{
     cout << count << endl;
}

}


Measured memory_bytes: 3204
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define speed ios_base::sync_with_stdio(0); cin.tie(0);
#define FL(i,a,n) for(ll i=a;i<n;i++)
#define even(x) (((x)%(2))==(0))
#define odd(x) (((x)%(2))==(1))
#define meme(x) memset(x, 0, sizeof(x))

#define pb push_back
#define mp make_pair
#define ff first
#define ss second


int main()
{
    int n;cin>>n;
    string s;cin>>s;
    if(n>=3200)
    cout<<s;
    else
    cout<<"red";
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> apply(const vector<int> &a, const vector<int> &b)
{
	vector<int> r(a.size());

	for (int i = 0; i < b.size(); i++) r[i] = a[b[i]];

	return move(r);
}

vector<int> pow(const vector<int> &a, int k)
{
	vector<int> r(a.size());

	if (k == 0){
		for (int i = 0; i < a.size(); i++) r[i] = i;
	}
	else{
		auto h = pow(a, k / 2);
		r = apply(h, h);
		if (k % 2){
			for (int i = 0; i < r.size(); i++) r[i] = a[r[i]];
		}
	}

	return move(r);
}


int main()
{
	int N, K; scanf ("%d %d", &N, &K);
	vector<int> p(N), q(N), P(N), Q(N);
	for (int i = 0; i < N; i++){
		scanf ("%d", &p[i]); p[i]--;
		P[p[i]] = i;
	}
	for (int i = 0; i < N; i++){
		scanf ("%d", &q[i]); q[i]--;
		Q[q[i]] = i;
	}

	vector<int> r;
	if (K == 1) r = p;
	else{
		int u = (K - 2) / 6;
		vector<int> X = pow(apply(P, apply(q, apply(p, Q))), u);

		vector<int> C;

		if (K % 6 == 0) C = apply(p, Q);
		if (K % 6 == 1) C = apply(q, apply(p, Q));
		if (K % 6 == 2) C = q;
		if (K % 6 == 3) C = apply(q, P);
		if (K % 6 == 4) C = apply(q, apply(P, Q));
		if (K % 6 == 5) C = Q;

		int v = (K + 1) / 6;
		vector<int> Y = pow(apply(q, apply(P, apply(Q, p))), v);

		r = apply(Y, apply(C, X));
	}

	for (int i = 0; i < N; i++) printf ("%d%c", r[i] + 1, i + 1 < N ? ' ' : '\n');

	return 0;
}

Measured memory_bytes: 15104
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VP = vector<P>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

const ll INF = 1LL<<60;

int main(){
    ll h, w;
    cin >> h >> w;
    if (h % 3 == 0 || w % 3 == 0){
        cout << 0 << endl;
        return 0;
    }
    ll ans = INF;
    rep(i, 2){
        for(ll r = 1; r < h; r++){
            ll sq1 = r * w;
            ll sq2 = (h-r) * (w/2);
            ll sq3 = (h-r) * ((w+1) / 2);
            ll mx = max({sq1, sq2, sq3});
            ll mn = min({sq1, sq2, sq3});
            ans = min(ans, mx-mn);
        }
        swap(h, w);
    }

    rep(i, 2){
        for(ll r = 1; r < h; r++){
            ll sq1 = r * w;
            ll sq2 = (h-r) / 2 * w;
            ll sq3 = (h-r+1) / 2 * w;
            ll mx = max({sq1, sq2, sq3});
            ll mn = min({sq1, sq2, sq3});
            ans = min(ans, mx-mn);
        }
        swap(h, w);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3580
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define se second
#define fi first
#define ll long long int
#define INF INT_MAX
#define mod 1000000007
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
int main()
{
    chutiyaap;
    int n,k;cin>>n>>k;
    int vis[n+1]={0};
    map<int,int>mp;
    while(k--)
    {
    	int d;cin>>d;
    	for(int i=0;i<d;i++)
    	{
    		int x;cin>>x;
    		vis[x]++;
    	}
    }
    int cnt=0;
    for(int i=1;i<=n;i++)if(vis[i]==0)cnt++;
    cout<<cnt;
}


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

using namespace std;

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

string line;
int LineSize;

typedef pair<int, int> Pii;

map<Pii, int> memory; // (id, idx) -> num
map<string, int> var_id;
set<string> variables;
map<int, int> var_size;
int id_size;

int find(int l, int r, char ch) {
  
  REP(i,l,r) {
    if(line[i] == ch) return i;
  }
  return -1;
}

bool valid_check(int id, int idx) {
  if(var_size[id] > idx) return true;
  return false;
}

/////////// get_num
int get_num(int st) {
  int ret = 0;
  REP(i, st, LineSize) {
    if(!isdigit(line[i])) break;
    ret *= 10;
    ret += line[i]-'0';
  }
  return ret;
}

//////////// get_idx
int parse(int, int);
int get_idx(int l, int r) {
  
  int kpos = find(l, r, '[');
  
  if(kpos == -1) assert(0);
  
  string str = string(line.begin()+l, line.begin()+kpos);
  
  if(isdigit(str[kpos+1])) {
    return get_num(kpos+1);
  }
  else {
    return parse(kpos+1, r);
  }
  
}

int parse(int l, int r) {
  
  int kpos = find(l, r, '[');
  if(kpos == -1) { return get_num(l); }
  
  string vstr = string(line.begin()+l, line.begin()+kpos);
  int id = var_id[vstr], idx = get_idx(kpos, r);

  if(!valid_check(id, idx)) { throw(0); }
  
  map<Pii, int>::iterator iter = memory.find(Pii(id, idx));
  if(iter == memory.end()) {
    return -1;
  }
  return iter -> second;
}


void dec_val(string s, int sz) {
  variables.insert(s);
  var_id[s] = id_size++;
  var_size[var_id[s]] = sz;
}

void interpret() {
  
  LineSize = line.size();
  
  int eqpos = find(0, LineSize, '=');
  
  if(eqpos == -1) {
    // declare
    int kpos = find(0, LineSize, '[');
    string s = string(line.begin(), line.begin()+kpos);
    int sz = get_num(kpos+1);
    dec_val(s, sz);
  }
  
  else {
    // assign
    int kpos = find(0, LineSize, '[');
    string varstr = string(line.begin(), line.begin()+kpos);
    int id = var_id[varstr];
    int idx = parse(kpos+1, eqpos);
    if(var_size[id] <= idx) { throw(0); }
    
    // rhs parse
    int rhs = parse(eqpos+1, LineSize);
    if(rhs == -1) { throw(0); }
    memory[Pii(id, idx)] = rhs;
  }
  
}

void init()
{
  variables.clear();
  memory.clear();
  var_id.clear();
  var_size.clear();
  id_size = 0;
}

bool get_next_line(string &line)
{
  getline(cin, line);
  if(line == ".") return false;
  return true;
}

int main()
{
  
  while(1) {
    init();
    
    getline(cin, line);
    if(line == ".") break;
    
    int line_cnt = 1;
    bool skip = 0;
    while(1) {
      
      if(!skip) {
	
	try {
	  interpret();
	} catch(...) {
	  cout << line_cnt << endl;
	  skip = 1;
	}
      }
      
      if(!get_next_line(line)) { break; }
      line_cnt++;
    }
    if(!skip) {
      // no bug
      cout << 0 << endl;
    }
    
  }
  
  return 0;
}

Measured memory_bytes: 1332
#include<iostream>
using namespace std;
const int MAXN=105;
int A[MAXN];

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>A[i];
	int res=0;
	for(int i=0;i<n;i++){
		int minn=i;
		for(int j=i+1;j<n;j++){
			if(A[minn]>A[j]){
				minn=j;
			}
		}
		if(minn!=i){
			swap(A[minn],A[i]);
			res++;
		}
	}
	for(int i=0;i<n;i++){
		cout<<A[i];
		if(i!=n-1)cout<<" ";
	}
	cout<<endl<<res<<endl;
	return 0;
}


Measured memory_bytes: 3104
#include<stdio.h>
int main(void){
 int a,b,r,ans,a1,b1;
  double c;
  while(scanf("%d %d",&a,&b)!=EOF){
 
  a1=a,b1=b;
 
  while(1){
    r=a%b;
    if(r==0){
      ans=b;
      break;
    }else{
      a=b;
      b=r;
    }
  }
 
   
  c=(double)(a1)*(double)(b1)/(double)(ans);
 
 
 
 
  printf("%d %.0f\n",ans,c);
  }
  return 0;
}



Measured memory_bytes: 1924
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  const ll mod=1000000007;
  ll dp[2010][2010],i,j;
  ll s;
  cin >> s;
  for(i=0;i<=s;i++){
    for(j=0;j<=s;j++){
      dp[i][j]=0;
    }
  }
  dp[0][0]=1;
  for(i=1;i<=s;i++){
    for(j=0;j<=s;j++){
      if(j<3){
        continue;
      }
      else{
        dp[i][j]+=dp[i-1][j-3]+dp[i][j-1];
        dp[i][j]%=mod;
      }
    }
  }
  ll ans=0;
  for(i=0;i<=s;i++){
    ans+=dp[i][s];
    ans%=mod;
  }
  ans=ans%mod;
  cout << ans << endl;
}

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

int solve(const string& s, int sn) {
  int ans = 0;
  for(int i = 0; i < s.size(); ++i) {
    int n = s[i] - '0';
    if(i % 2 == 0 && n != sn) {
      ans++;
    } else if(i % 2 == 1 && n == sn) {
      ans++;
    }
  }
  return ans;
}

int main() {
  string s;
  cin >> s;
  int s0 = solve(s, 0);
  int s1 = solve(s, 1);
  cout << min(s0, s1) << endl;
  return 0;
}

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

int main()
{
	int X;
	cin >> X;
	vector<bool> dp(X + 1);
	dp[0] = true;
	for (int i = 0; i <= 5; i++) {
		int v = 100 + i;
		for (int j = 0; j + v <= X; j++) if (dp[j]) {
			dp[j + v] = true;
		}
	}
	cout << dp[X] << endl;
	return 0;
}


Measured memory_bytes: 256
from sys import setrecursionlimit, stdin
import numpy as np

readline = stdin.readline
setrecursionlimit(10 ** 6)

def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t
  
def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j

N,M = map(int,readline().split())
parent = - np.ones(N,int)

for _ in range(M):
    A, B = map(lambda x: int(x) - 1, readline().split())
    unite(parent, A, B)

ans = 0
for i in range(N):
    if parent[i] < 0:
        ans += 1
print(ans-1)

Measured memory_bytes: 27664
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, W;
  cin >> N >> W;
  vector<int64_t> w(N), v(N);
  for (int i = 0; i < N; i++) {
    cin >> w.at(i) >> v.at(i);
  }
  vector<vector<int64_t>> DP(N + 1, vector<int64_t>(W + 1, 0));
  DP.at(0).at(0) = 0;
  for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= W; j++) {
      if (j >= w.at(i - 1)) {
        DP.at(i).at(j) =
          max(DP.at(i).at(j), DP.at(i - 1).at(j - w.at(i - 1)) + v.at(i - 1));
      }
      DP.at(i).at(j) = max(DP.at(i).at(j), DP.at(i - 1).at(j));
    }
  }
  cout << DP.at(N).at(W) << endl;
}

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

int main() {
    int N; cin >> N;
    double ans = 0;
    for (int i = 0; i < N; i++) {
        double x; cin >> x;
        string u; cin >> u;
        if (u == "JPY") {
            ans += x;
        } else {
            ans += x * 380000;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3768
#include <stdio.h>
#include <iostream>

int main()
{
    std::string P;
    std::cin >> P;
    
    int d = 0, m = 0;
    for (int i = 0, L = P.length(); i < L; i++) {
        if(P[i] == 'S') d++;
        else if(P[i] == 'T') {
            d--;
            m = (m > d) ? d : m;
        }
    }
    
    std::cout << (m * -2) << std::endl;
    
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<set>
#include<stack>
#include<queue>
#include<string>
#include<algorithm>//min,max,swap,rand,reverse,sort,lower_bound
#include<functional>
#include<vector>
#include<list>
#include<map>
#include<tuple>
#include<cmath>//abs, sin, cos
#include<bitset>
using namespace std;

int main()
{
	int N,t, p,sum=0, cost=0;
	vector<int> C, V;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> t;
		C.push_back(t);
	}
	for (int i = 0; i < N; i++) {
		cin >> p;
		V.push_back(p);
	}

	for (int i = 0; i < N; i++) {
		if (C[i] > V[i]) {
			sum += C[i];
			cost += V[i];
		}
	}

	cout << sum - cost << endl;

	return 0;
}

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

using namespace std;

#define INF ((1<<30)-1)  //int32_t
#define MOD 1000000007
#define MOD2 

#define all(a)  (a).begin(),(a).end()

#define mkp make_pair
#define pb push_back

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

int main(){

    bool flag=false;

    ll ans=0,sum=0;
    
    int n;
    string s;
    cin >>n>>s;
    
    for (int i = 0; i < n; i++)
    {
        if(s[i] == 'R')sum++;
    }
    
    if(sum > n/2)flag=true;

    //cout <<fixed<<setprecision(16)<< << endl;
    //cout << ans << endl;

    if(flag)cout << "Yes" <<endl;
    else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <iomanip>
using namespace std;

int main()
{
    int num;
    cin >> num;
    vector<string> v;
    for(int i=0;i<num;i++){
        string current1;
        cin >> current1;
        vector<string> vec;
        for(int i=0;i<10;i++){
            vec.push_back(current1.substr(i,1));
        }
        sort(vec.begin(),vec.end());
        string current2;
        for(int i=0;i<10;i++){
            current2 += vec[i];
        }
        v.push_back(current2);
    }
    sort(v.begin(),v.end());
    long ans = 0;
    long current = 0;
    for(int i=1;i<num;i++){
        if(v[i]==v[i-1]){
            current ++;
        }else{
            ans += (current * (current + 1))/2;
            current = 0;
        }
    }
    ans += (current * (current + 1))/2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4212
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using P   = pair<ll, ll>;
using mat = vector<vector<ll>>;
typedef string::const_iterator State;
class ParseError {};

void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

const ll INF = 1e16;
const ll MOD = 1e9 + 7;
const ld EPS = 1e-12;

template <typename T>
void dump(T x) { cout << x << endl; }
void dumpf(ld x, int t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
inline ll mod(ll a, ll b) {
	if (a > 0) return a % b;
	if (a % b == 0) return 0;
	ll x = -a / b + 1;
	a += x * b;
	return a % b;
}
ll powm(ll a, ll b, ll c) {
	if (b == 0)
		return 1;
	else if (b % 2 == 0) {
		ll d = powm(a, b / 2, c);
		return (d * d) % c;
	} else
		return (a * powm(a, b - 1, c)) % c;
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
//ll dx[4] = {1, 0, -1, 0};
//ll dy[4] = {0, 1, 0, -1};

struct UnionFind {
  private:
	std::vector<int> rank, par, col;
	int n_;

  public:
	UnionFind(int n) : n_(n) {
		rank.resize(n, 1);
		par.resize(n);
		for (int i = 0; i < n; ++i) {
			par[i] = i;
		}
		col.resize(n, 1);
	}
	int root(int i) {
		while (par[i] != i) {
			i = par[i];
		}
		return i;
	}
	bool isSame(int x, int y) { return root(x) == root(y); }
	void unite(int x, int y) {
		if (isSame(x, y)) return;
		x = root(x), y = root(y);
		if (rank[x] < rank[y]) {
			par[x] = y;
			col[y] += col[x];
		} else {
			if (rank[x] == rank[y]) rank[x]++;
			par[y] = x;
			col[x] += col[y];
		}
	}
	int cnt(int x) {
		x = root(x);
		return col[x];
	}
};

using T = tuple<ll, ll, ll>;

int main() {
	ll n, m;
	while (1) {
		scanf("%lld", &n);
		if (n == 0) break;
		scanf("%lld", &m);
		vector<T> e(m);
		UnionFind uf(n + 1);
		for (int i = 0; i < m; i++) {
			ll a, b, d;
			scanf("%lld,%lld,%lld", &a, &b, &d);
			d	= d / 100 - 1;
			e[i] = make_tuple(d, a, b);
		}
		sort(e.begin(), e.end());
		ll ans = 0;
		for (int i = 0; i < m; i++) {
			ll d, a, b;
			tie(d, a, b) = e[i];
			if (!uf.isSame(a, b)) {
				uf.unite(a, b);
				ans += d;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}



Measured memory_bytes: 3336
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
constexpr int IINF = INT_MAX;

struct edge{
    int to, cap, rev;
};

vector<vector<edge> > G;
vector<bool> used;

void add_edge(int from, int to, int cap){
    G[from].emplace_back((edge){to, cap, int(G[to].size())});
    G[to].emplace_back((edge){from, 0, int(G[from].size())-1});
}

// 増加路の探索
int dfs(int v, int t, int f){
    if(v == t) return f;
    used[v] = true;
    for(auto &e : G[v]){
        if(!used[e.to] && e.cap > 0){
            int d = dfs(e.to, t, min(f, e.cap));
            if(d > 0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t){
    used.resize(G.size());
    int flow = 0;
    while(1){
        fill(used.begin(), used.end(), false);
        int f = dfs(s, t, IINF);
        if(f==0) break;
        flow += f;
    }
    return flow;
}

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

int main() {
    int n, m;
    while(cin >> m >> n, m){
        G.clear();
        G.resize(m+n+2);
        vector<int> a(m), b(n);
        for(int i=0;i<m;i++) cin >> a[i];
        for(int i=0;i<n;i++) cin >> b[i];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(gcd(a[i], b[j]) > 1){
                    add_edge(i,j+m,1);
                }
            }
        }
        for(int i=0;i<m;i++){
            add_edge(n+m,i,1);
        }
        for(int i=0;i<n;i++){
            add_edge(i+m,n+m+1,1);
        }
        cout << max_flow(n+m, n+m+1) << endl;
    }
    return 0;
}



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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MOD (1000000007)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

string s;

void input(){
    cin >> s;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    map<char, int> cnt;
    for(int i=0;i<s.size();i++){
        cnt[s[i]]++;
    }
    if(cnt['a'] == 1 && cnt['b'] == 1 && cnt['c'] == 1) cout << "Yes" << "\n";
    else cout << "No" << "\n";
    return 0;
}

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

using namespace std;

typedef long long ll;
const ll MOD = 998244353;
const ll INF = 1e18;

int main() {
    ll n, m, i, j, k;
    cin >> n;
    vector<ll> d(n);
    for(i=0;i<n;i++){
        cin >> d[i];
        if(i>0 && d[i]==0){
            cout << 0 << endl;
            return 0;
        }
    }
    if(d[0]!=0){
        cout << 0 << endl;
        return 0;
    }
    sort(d.begin(),d.end());
    ll ret = 0;
    ll dp[n+1]={};
    dp[0] = 1;
    ll kyori[n+1]={};
    kyori[0] = 1;
    for(i=1;i<n;i++){
        dp[i] = dp[i-1] * kyori[d[i]-1];
        dp[i] %= MOD;
        kyori[d[i]]++;
    }
    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin>>S;
  cout<<S[0]<<S[1]<<S[2]<<S[3]<<S[4]<<" "<<S[6]<<S[7]<<S[8]<<S[9]<<S[10]<<S[11]<<S[12]<<" "<<S[14]<<S[15]<<S[16]<<S[17]<<S[18];
  
}
    

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

int b[N];
char s[N];
char t[N];
ll f[N];
int used[15];
int cmp1(ll a,ll b)
{
    return b<a;
}

multiset<int> ss;
map<int,int>mp;
int main()
{
    int n;
    cin>>n;
    if(n<=599) cout<<8<<endl;
    else if(n<=799) cout<<7<<endl;
    else if(n<=999) cout<<6<<endl;
    else if(n<=1199) cout<<5<<endl;
    else if(n<=1399) cout<<4<<endl;
    else if(n<=1599) cout<<3<<endl;
    else if(n<=1799) cout<<2<<endl;
    else  cout<<1<<endl;


}


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

int main()
{
  int n;
  cin >> n;
  
  int a[n];
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  
  long double sum = 0.0;
  for(int i = 0; i < n; i++){
    sum += (long double)(1.0 / a[i]);
  }
  
  sum =  (long double)(1.0 / sum);
  
  cout << fixed;
  cout << setprecision(20);
  cout << sum << endl;
}

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

int n, ans, mindiff;
bool color[] = {false, false, false, false, false, false, false, false};

int main() {
	cin >> n;

	for(int i=0, a; i<n; i++){
		cin >> a;
		if(a<=399){
			color[0] = true;
		}
		else if(a>=400 && a<=799){
			color[1] = true;
		}
		else if(a>=800 && a<=1199){
			color[2] = true;
		}
		else if(a>=1200 && a<=1599){
			color[3] = true;
		}
		else if(a>=1600 && a<=1999){
			color[4] = true;
		}
		else if(a>=2000 && a<=2399){
			color[5] = true;
		}
		else if(a>=2400 && a<=2799){
			color[6] = true;
		}
		else if(a>=2800 && a<=3199){
			color[7] = true;
		}
		else{
			ans++;
		}
	}

	for(bool i: color){
		if(i){
			mindiff++;
		}
	}
    
    ans += mindiff;
    if(mindiff==0){
      mindiff++;
    }
	cout << mindiff << ' ' << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1e9 + 7;
const ll INF = LLONG_MAX;
using Tree = vector<pair<int, int>>;
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<int>());
    int ans = -1;
    int res;
    for (int i = 1; i < n; i++)
    {
        int tmp = ans;
        ans = max(ans, min(a[i], a[0] - a[i]));
        if (ans != tmp)
            res = a[i];
    }
    cout << a[0] << " " << res << endl;
}

Measured memory_bytes: 640
//satyaki3794
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
 
ll pwr(ll base, ll p, ll mod){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}
 
 
ll gcd(ll a, ll b){
    if(b == 0)  return a;
    return gcd(b, a%b);
}



int main(){
 
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);

    int n;
    scanf("%d", &n);
    int x = 0;
    deque<int> dq;
    while(n--){
        int z;
        scanf("%d", &z);
        if(x == 0)  dq.push_back(z);
        else    dq.push_front(z);
        x ^= 1;
    }

    if(x == 0){
        while(!dq.empty()){
            printf("%d ", dq.front());;
            dq.pop_front();
        }    
    }
    else{
        while(!dq.empty()){
            printf("%d ", dq.back());;
            dq.pop_back();
        }       
    }
    
    return 0;
}








Measured memory_bytes: 2944
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
long long K;
long long ans[55];
int main(){
	cin>>K;
	long long rou=K/50;
	if (K<50){
		int left=K%50;
		for (int i=1;i<=left;i++){
			ans[i]+=50;
		}
		cout<<50<<endl;
		for (int i=1;i<=50;i++){
			cout<<ans[i]<<" ";
		}
	}
	else{
		for (int i=1;i<=50;i++){
			ans[i]=49+rou;
		}
		int left=K%50;
		for (int i=1;i<=left;i++){
			ans[i]+=51;
		}
		cout<<50<<endl;
		for (int i=1;i<=50;i++){
			cout<<ans[i]-left<<" ";
		}
	}
	return 0;
	
}

Measured memory_bytes: 384
#B - Guidebook AC(ヒント)
N = int(input())
S = []
P = []
for _ in range(N):
    s,p = input().split()
    S.append(s)
    P.append(int(p)*(-1))#負の値にして降順にソートできるようにする

book = list(zip(S,P))
book_sort = sorted(book)
ans = [book.index(i)+1 for i in book_sort]
for j in ans:
    print(j)

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

typedef long long ll;
typedef long double ld;
const ll init = 1e9+7;

#define mkp make_pair
#define pb push_back
#define pq priority_queue
#define minpq priority_queue <int, vector<int>, greater<int> >
#define vi vector <int> 
#define vll vector <ll>
#define pii pair<int,int>

int dp[3010][3010];
string s,t,ans;
vi v(3010,0);

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>s>>t;
	int sz1 = s.length(), sz2=t.length();
	for (int i = 0; i < 3010; ++i)
		for (int j = 0; j < 3010; ++j)
			dp[i][j]=-1;
	int a=sz1,b=sz2;
	for (int i=0; i<=a; i++){ 
	   	for (int j=0; j<=b; j++){ 
	       if (i == 0 || j == 0) dp[i][j] = 0;
	       else if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
	       else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 
	    } 
	}
	string ans;
	while(a>0 && b>0){
		if(s[a-1]==t[b-1]){
			ans += s[a-1]; --a; --b;
		}
		else if(dp[a-1][b]>dp[a][b-1])--a;
		else --b;
	}
	reverse(ans.begin(), ans.end());
	cout<<ans<<endl;
	return 0;
} 

Measured memory_bytes: 36220