akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

int gcd(int m,int n){
	if(n>m)return gcd(n,m);
	else{
		if(m%n==0){
			return n;
		}else{
			return gcd(n,m%n);
		}
	}
}

bool matching(vector<vector<pair<int,int> > >& edges,int u,vector<int>& match,vector<bool>& visited){
	if(u<0)return true;
	for(int i=0;i<edges[u].size();i++)if(!visited[edges[u][i].second]){
		visited[edges[u][i].second] = true;
		if(matching(edges,match[edges[u][i].second],match,visited)){
			match[edges[u][i].first] = edges[u][i].second;
			match[edges[u][i].second] = edges[u][i].first;
			return true;
		}
	}
	return false;
}


void solve(int m,int n){
	vector<int> blue(m),red(n);
	for(int i=0;i<m;i++){
		cin >> blue[i];
	}
	for(int i=0;i<n;i++){
		cin >> red[i];
	}
	vector<vector<pair<int,int> > >edges;
	for(int i=0;i<m;i++){
		vector<pair<int,int> > edge;
		for(int j=0;j<n;j++){
			if(gcd(blue[i],red[j])>1){
				edge.push_back(make_pair(i,m+j));
			}
		}
		edges.push_back(edge);
	}
	vector<int> match(m+n,-1);
	int ans = 0;
	for(int i=0;i<m;i++){
		vector<bool> visited(m+n);
		if(matching(edges,i,match,visited))ans++;
	}
	cout << ans << endl;
	return;
}


int main(){
	int m,n;
	while(1){
		cin >> m >> n;
		if(m==0&&n==0)break;
		solve(m,n);
	}
	return 0;
}

Measured memory_bytes: 3800
/*
 _____ ____ _____   ___   ___   ___   ___ 
|_   _/ __ \_   _| |__ \ / _ \ |__ \ / _ \
  | || |  | || |      ) | | | |   ) | | | |
  | || |  | || |     / /| | | |  / /| | | |
 _| || |__| || |_   / /_| |_| | / /_| |_| |
|_____\____/_____| |____|\___/ |____|\___/ 
*/
#include <bits/stdc++.h>
#include <fstream>
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (a); i > (b); i--)
#define a(x) (x.begin(), x.end())
#define ar(x) (x.rbegin(), x.rend())
#define pb push_back
#define Pb() pop_back()
#define ll long long int
#define ull unsigned long long int
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sc scanf
#define scin(x) sc("%d", &(x))
#define scln(x) sc("%lld", &(x))
#define pf prllf
#define ms(a, b) memset(a, b, sizeof(a))
#define mp make_pair
#define db double
#define EPS 10E-10
#define ff first
#define ss second
#define sqr(x) (x) * (x)
#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<ll>>
#define DBG pf("HI\n")
#define MOD 1000000007
#define CIN                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)
#define RUN_CASE(t, T) for (__typeof(t) t = 1; t <= T; t++)
#define CASE(t) prllf("Case %d: ", t)
#define CASEL(t) prllf("Case %d:\n", t)
#define intlimit 2147483647
#define longlimit 9223372036854775807
#define infinity (1 << 28)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a) * (b) / gcd(a, b))
#define PI 2 * acos(0.0)
// assert(x==y); gives run time when false
using namespace std;
int main()
{
    CIN;
    int n,m;
    cin >> n >> m;
    vi vis(n,0),vis2(n,0);
    int sum1 = 0,sum2 = 0;
    rep(i,0,m){
        int a;
        string g;
        cin >> a >> g;
        a--;
        if(g == "WA"){
            if(!vis[a]){
                vis2[a]++;
            }
        }else if(g == "AC"){
            if(!vis[a]){
                vis[a]++;
                sum1++;
                sum2+=vis2[a];
            }
        }
    }
    cout << sum1 << " " << sum2;
}

Measured memory_bytes: 1024
import java.util.*;
import java.io.*;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int w = scan.nextInt();
    int h = scan.nextInt();
    int n = scan.nextInt();
    int xmax = w;
    int xmin = 0;
    int ymax = h;
    int ymin = 0;

    for(int i = 0; i < n; i++){
      int x = scan.nextInt();
      int y = scan.nextInt();
      int a = scan.nextInt();
      if(a == 1){
        xmin = Math.max(xmin, x);
      }else if(a == 2){
        xmax = Math.min(xmax, x);
      }else if(a == 3){
        ymin = Math.max(ymin, y);
      }else{
        ymax = Math.min(ymax, y);
      }
    }

    if(xmax-xmin>0 && ymax-ymin>0){
      System.out.println((xmax-xmin)*(ymax-ymin));
    }else{
      System.out.println(0);
    }

  }
}


Measured memory_bytes: 22740
#include<bits/stdc++.h>
using namespace std;
#define ll int64_t
#define f first
#define sec second
#define pb push_back
#define pf push_front
#define po pop_back
#define fast ios_base::sync_with_stdio(false)
#define vi vector<ll>
#define vii vector< pair<ll,ll> >
#define pi pair<ll,ll>
#define map map<ll,ll>
#define set set<ll>
#define tostr to_string
#define toint stoi
#define gcd __gcd


int main()
{
    fast;
    ll n,i;string s;
    cin>>n>>s;

    string s1=" ",s2=" ";
    if(n%2!=0)
    {
        cout<<"No"<<endl;
        return 0;
    }
    for( i=0;i<n/2;i++)
    s1+=s[i];

    for( i=i;i<n;i++)
    s2+=s[i];


    if(s1==s2)
     cout<<"Yes"<<endl;
    else
     cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

ll dp[1<<16];

int main() {
    int n; cin >> n;
    vvint a(n,vint(n));
    rep(i,n)rep(j,n) cin >> a[i][j];
    for (int s = 1; s < 1<<n; s++) {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (s>>i & s>>j & 1) dp[s] += a[i][j];
            }
        }
        for (int t = s; t > 0; t = (t-1)&s) {
            if (t == s) continue;
            chmax(dp[s],dp[t]+dp[t^s]);
        }
    }
    cout << dp[(1<<n)-1] << endl;
}

Measured memory_bytes: 768
import sys
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([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

n=int(input())
if n==1:
  print(0)
  sys.exit()
arr = factorization(n)
res = 0
for st in arr:
  tmp =0
  for i in range(1,40):
    tmp += i
    if st[1] >= tmp:
      res += 1
    else:
      break
print(res)

Measured memory_bytes: 63256
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = 0
count = 0
n=int(input())
A=[int(input()) for i in range(n)]
A.sort()
if n%2==1:
    if A[n//2]-A[n//2-1]<=A[n//2+1]-A[n//2]:
        A.insert(0,A[n//2+1])
    else:
        A.append(A[n//2])
    n+=1
tmp=A[n//2]
for i in range(n//2):
    ans+=abs(tmp-A[i+n//2])
    tmp = A[i+n//2]
    # print(tmp)
    ans+=abs(tmp-A[i])
    tmp=A[i]
    # print(tmp)
print(ans)

# print(A)

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

int main(){
  int n;
  int i;

  scanf("%d", &n);
  vector <int> l(n);

  for(i = 0;i < n;i++) scanf("%d", &l[i]);

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

  int j;

  int ans = 0;

  for(i = 0;i < n;i++){
    for(j = 0;j < i;j++){
      int ab = l[i] + l[j];
      int left = i + 1;
      int right = lower_bound(l.begin(),l.end(),ab) - l.begin();
      ans += max(0,right - left);
    }
  }

  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] matrix1 = new int[n][m];
        int[] matrix2 = new int[m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                matrix1[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < m; i++) {
            matrix2[i] = Integer.parseInt(br.readLine());
        }
        int[] sum = dot(matrix1, matrix2, n, m);
        for (int i = 0; i < n; i++) {
            System.out.println(sum[i]);
        }
    }

    static int[] dot(int[][] matrix1, int[] matrix2, int n, int m) {
        int[] sum = new int[n];
        Arrays.fill(sum, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sum[i] += (matrix1[i][j] * matrix2[j]);
            }
        }
        return sum;
    }
}

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

int main() {
    constexpr int64_t N = 5;
    vector<int64_t> x(N);
    for (int64_t& X : x) {
        cin >> X;
    }

    for (int64_t i = 0; i < N; i++) {
        if (x[i] == 0) {
            cout << i + 1 << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
const int INF = 100100100;
typedef long long ll;
 
int main() {
   int x,y,z,k,s;
   cin >> k >> s;
   
   int ans=0;
   for(int x=0;x<=k;x++){
      for(int y=0;y<=k;y++){
         int z=s-x-y;
         if(z>=0 && z<=k)
         ans++;
      }
   }

   cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
template <class T> void chmax(T& x, T y) { if (x < y) x = y; }
bool win(int x, int y) { return x == (y + 2) % 3; }
int main() {
    int N, K; cin >> N >> K;
    int S[3]; cin >> S[0] >> S[1] >> S[2];
    string T; cin >> T;
    vector<int> U(N);
    for (int i = 0; i < N; i++) {
        U[i] = (T[i] == 'r' ? 0 : T[i] == 's' ? 1 : 2);
    }
    Int ans = 0;
    for (int i = 0; i < K; i++) {
        int A[3][2] = {};
        int t = 0;
        for (int j = i; j < N; j += K) {
            for (int k = 0; k < 3; k++) {
                for (int l = 0; l < 3; l++) {
                    if (k == l) continue;
                    chmax(A[l][t], A[k][!t] + (win(l, U[j]) ? S[l] : 0));
                }
            }
            t = !t;
        }
        ans += max({ A[0][!t], A[1][!t], A[2][!t] });
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <ctype.h>
#include <numeric>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1e9 + 7;
const int INF = 1e9;

int dx4[4] = { 0, -1, 1, 0 };
int dy4[4] = { -1, 0, 0, 1 };
int dx8[8] = { 0, -1, 1, 0, -1, 1, -1, 1 };
int dy8[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };

int main() {
  int n; cin >> n;
  vector<int> jpy;
  vector<double> btc;
  double tmp;
  string type;
  for (int i = 0; i < n; ++i) {
    cin >> tmp >> type;
    if (type == "BTC") {
      btc.push_back(tmp);
    } else {
      jpy.push_back(int(tmp));
    }
  }
  int jpysum = accumulate(jpy.begin(), jpy.end(), 0);
  double btcsum = accumulate(btc.begin(), btc.end(), 0.0);
  btcsum *= 380000.0;
  cout << jpysum + btcsum << endl;;
  return 0;
}


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

typedef long long ll;
typedef long double ld;
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353
#define Graph vector<vector<int>>

int main() {
    string S; cin >> S;
    int ans = 0;
    for (int i = 0; i < S.size(); i++) {
        if (S.at(i) == '+') ans++;
        else ans--;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }

const int maxN = 500000 + 233;
const int maxA = (1 << 20) + 233;
const LL P = 1000000007;
int n, a[maxN];
LL f[maxA], g[maxA];

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	a[0] = 0;
	for(int i = 1; i <= n; ++i) cin >> a[i], a[i] ^= a[i - 1];
	// odd length
	memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g));
	f[0] = 1;
	for(int i = 1; i < n; ++i) {
		LL x = f[a[i] ^ a[n]], y = g[a[i] ^ a[n]];
		(f[a[i]] += y) %= P;
		(g[a[i]] += x) %= P;
//		printf("%d: g[%d] += %lld\n", i, a[i], x);
	}
	LL ans = f[0];
//	display(a[n]); display(ans);
	// even length
	if(a[n] == 0) {
		memset(f, 0, sizeof(f)); // sum
		memset(g, 0, sizeof(g)); // sum * cnt
		LL cnt = 0;
		for(int i = 1; i < n; ++i) {
			LL fun = f[a[i]] * cnt - g[a[i]] + 1;
//			printf("fun %d = %lld\n", i, fun);
			fun = (fun % P + P) % P;
			cnt += (a[i] == 0);
			(f[a[i]] += fun) %= P;
			(g[a[i]] += fun * cnt) %= P;
			(ans += fun) %= P;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 18688
#include <bits/stdc++.h>
#include <atcoder/dsu>
#include <atcoder/fenwicktree>

using namespace std;
using namespace atcoder;
using ll = long long;

int main() {
  int n, q;
  cin >> n >> q;
  fenwick_tree<ll> fw(n);
  for(int i = 0; i < n; i++) {
    ll y;
    cin >> y;
    fw.add(i, y);
  }
  for(int i = 0; i < q; i++) {
    bool num;
    cin >> num;
    if(!num) {
      int p;
      ll x;
      cin >> p >> x;
      fw.add(p, x);
    }
    else {
      int l, r;
      cin >> l >> r;
      cout << fw.sum(l, r) << endl;
    }
  }
}

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

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SIZE = 1e5 * 3 + 10;
vector <ll> vec;
ll q;

int main() {
	fastInp;

	ll n, k;
	cin >> n >> k;

	if (k < n) {
		n %= k;
	}
	cout << min(min(min(abs(k - n), abs(k - (abs(k - n)))), n), abs(k - abs(k - (abs(k - n)))));
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
void swap(int *A, int p, int r){
  int x=A[p];
  A[p]=A[r];
  A[r]=x;
}
int partition(int *A, int p, int r){
  int x=A[r];
  int i=p-1, j;
  for(j=p; j<r; ++j){
	if(A[j]<=x){
	  ++i;
	  swap(A, i, j);
	}
  }
  swap(A,i+1, r);
  return i+1;
}
int main(){
  int n;
  int i;
  scanf("%d", &n);
  int A[n];
  for(i=0; i<n; ++i){
	scanf("%d", &A[i]);
  }
  int q=partition(A, 0, n-1);
  
  for(i=0; i<n; ++i){
	if(i==q)
	  printf("[%d]", A[i]);
	else 
	  printf("%d", A[i]);
	if(i!=n-1)
	  printf(" ");
  }
  printf("\n");
  return 0;
}



Measured memory_bytes: 2100
#include <bits/stdc++.h>
using namespace std;
#define modulo 998244353
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 100000000


int main(){
	
	int k[12] = {1,3,1,2,1,2,1,1,2,1,2,1};
	
	int x,y;
	cin>>x>>y;
	
	if(k[x-1]==k[y-1]){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	
	
	
	
    return 0;
}



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

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

typedef struct node * Node;
#define NIL NULL

Node root;

Node treeSearch(Node u, int k){
  while(u != NIL && k != u->key){
    if(k < u->key) u = u->left;
    else u = u->right;
  }
  return u;
}

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

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x;
    if(z->key < x->key) x = x->left;
    else x = x->right;
  }

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

void inorder(Node u){
  if(u == NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(Node u){
  if(u == NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } 
  }

  return 0;
}




Measured memory_bytes: 20452
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long int n,k,a,b;
    cin>>n>>k;
    multimap<long long int, long long int> map;
    std::deque<long long int> deq;
    for (long long int i=0;i<n;i++) {
        cin>>a>>b;
        map.emplace(a,b);
        deq.emplace_back(a);
    }
    sort(deq.begin(),deq.end());
    long long int sum=0;
    long long int tmp;
    int flag=0;
    for (long long int j=0;j<n;j++) {
        if (j==0) {
            auto p=map.equal_range(deq[0]);
            for (auto itr=p.first;itr!=p.second;itr++) {
                sum+=itr->second;
                if (sum>=k) {
                    cout<<itr->first<<endl;
                    flag=1;
                    break;
                }
            }
            tmp=deq[0];
        } else {
            if (deq[j]!=tmp) {
                auto q=map.equal_range(deq[j]);
                for (auto itr2=q.first;itr2!=q.second;itr2++) {
                    sum+=itr2->second;
                    if (sum>=k) {
                        cout<<itr2->first<<endl;
                        flag=1;
                        break;
                    }
                }
                tmp=deq[j];
            }
        }
        if (flag==1) {
            break;
        }
    }
}

Measured memory_bytes: 7424
#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)
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<typename T> inline void InputV(vector<T>& A, int N) {rep(i,N) cin >> A.at(i);}
//C++14 (GCC 5.4.1)
int main() {
    int N;
    cin >>N;

    vector<int> a(N),b(N),c(N);
    rep(i,N) cin >> a.at(i)>>b.at(i)>>c.at(i);
    
    //-----------------------------------
    int Ans=0;
    //cm_aは前日bcをして今日aをしたとき幸福の最大値
    vector<int> cm_a(N,0),cm_b(N,0),cm_c(N,0);
    cm_a.at(0)=a.at(0);
    cm_b.at(0)=b.at(0);
    cm_c.at(0)=c.at(0);
    repd(i,1,N){
        cm_a.at(i)=cm_b.at(i-1)+a.at(i);
        chmax(cm_a.at(i),cm_c.at(i-1)+a.at(i));
        cm_b.at(i)=cm_c.at(i-1)+b.at(i);
        chmax(cm_b.at(i),cm_a.at(i-1)+b.at(i));
        cm_c.at(i)=cm_a.at(i-1)+c.at(i);
        chmax(cm_c.at(i),cm_b.at(i-1)+c.at(i));
    }
    Ans=max(cm_a.at(N-1),max(cm_b.at(N-1),cm_c.at(N-1)));


    cout << Ans <<endl;
}

Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int main() {

	long long n,i,j,k,sum=0,count=0,ans=0,x,c,d,mx=0,mn=1000000;
    cin>>n>>k>>d;
    mx=max(n,k);
    if(d%mx==0)
    cout<<d/mx;
    else
    cout<<d/mx+1;
	return 0;
}


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

#define all(x) (x).begin(),(x).end()
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)

typedef long long ll;
const ll MOD = 1e9 + 7;
const ll inf = 1LL<<60;
const double eps = 1e-9;

ll gcd(ll a, ll b)
{
    if (a < b) {
        a ^= b;
        b ^= a;
        a ^= b;
    }
    
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}

int main()
{
    ll a, b;
    cin >> a >> b;

    cout << lcm(a, b) << endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define swap(a, b, type) { type _tmp = a; a = b; b = _tmp; }
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	int A, B, K, cnt = 0;
	vector<int> d;

	cin >> A >> B >> K;

	repc(i, 1, min(A, B)) {
		if (A % i == 0 && B % i == 0) {
			cnt++;
			d.push_back(i);
		}
	}
	cout << d[cnt - K] << endl;

	return 0;
}


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

#define Fast ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define FO freopen("in.txt", "r", stdin)
#define FC freopen("out.txt", "w", stdout)
#define aise cout<<"aise"<<endl
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define ll long long
#define all(x) x.begin(), x.end()
#define mset(v, a) memset(v, a, sizeof(v))
#define pll pair< ll, ll >
#define pdd pair< double, double >
#define ff first
#define ss second
#define pi acos(-1.0)
#define mxN 2010
#define inf 1e14
#define MOD 1000000007

ll dx[]={0,0,1,-1,1,1,-1,-1};
ll dy[]={1,-1,0,0,1,-1,1,-1};

ll lcm(ll x, ll y)
{

    return (x/__gcd(x,y)*y);
}

int main()
{
    ll n;
    cin >> n;
    vector<ll> v;
    for(ll i = 0; i < n; i++)
    {

        ll x;
        cin >> x;
        v.pb(x);
    }
    ll ans = v[0];
    for(ll i = 1; i < n; i++)
    {

        ans = lcm(ans,v[i]);
    }
    cout << ans;
}


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

static const int N = 100;
static const int INFTY = (1 << 21);

int n, M[N][N];
int d[N];

void bfs(int s)
{
    std::queue<int> q;
    q.push(s);
    for (int i = 0; i < n; i++)
    {
        d[i] = INFTY;
    }
    d[s] = 0;
    int u;
    while (!q.empty())
    {
        u = q.front();
        q.pop();
        for (int v = 0; v < n; v++)
        {
            if (M[u][v] == 0)
            {
                continue;
            }
            if (d[v] != INFTY)
            {
                continue;
            }

            d[v] = d[u] + 1;
            q.push(v);
        }
    }
    for (int i = 0; i < n; i++)
    {
        std::cout << i + 1 << " " << ((d[i] == INFTY) ? (-1) : d[i]) << std::endl;
    }
}

int main() 
{
    int u, k, v ;
    std::cin >> n ;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            M[i][j] = 0 ;
        }
        
    }
    for (int i = 0; i < n; i++)
    {
        std::cin >> u >> k ;
        u--;
        for (int j = 0; j < k; j++)
        {
            std::cin >> v ;
            v-- ;
            M[u][v] = 1 ;
        }
        
    }
    
    bfs(0) ;
    return 0 ;
}


Measured memory_bytes: 3128
#include<bits/stdc++.h>
using namespace std;
long long n,m;
unsigned long long ans=0; 
int main()
{
    
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        long long a;
        cin>>a;
        ans+=a;
    }
    if(ans>n)
    {
        cout<<"-1";
        return 0; 
    }
    else
    {
        cout<<n-ans;
        return 0;
    }
    return 0;
}

Measured memory_bytes: 3636
#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;
ll INF = 1145141919454519;

int main() {

    ll N, K;
    cin >> N >> K;

    vector<ll > dp(N+1, -1);
    dp[0] = 1;

    for(ll i = 0; i < N; i++){
        if(dp[i] == -1) continue;
        dp[i+1] = min(2 * dp[i], dp[i]+K);
    }

    cout << dp[N] << endl;

}

Measured memory_bytes: 256
# ABC 157: B – Bingo
A = [input().split() for _ in range(3)]
N = int(input())
b = [input() for _ in range(N)]

for ball in b:
    for i in range(3):
        for j in range(3):
            if A[i][j] == ball:
                A[i][j] = '0'
                break

isBingo = 'No'

for i in range(3):
    if A[i][0] + A[i][1] + A[i][2] == '000':
        isBingo = 'Yes'
        break

for j in range(3):
    if A[0][j] + A[1][j] + A[2][j] == '000':
        isBingo = 'Yes'
        break

if A[0][0] + A[1][1] + A[2][2] == '000' or A[2][0] + A[1][1] + A[0][2] == '000':
    isBingo = 'Yes'

print(isBingo)

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

int solve(int root, int N, int K, const vector<vector<int>> &Es){
    if (K == 1) return N - 2;
    if (K == 2){
        int ans = 0;
        for (const auto &e : Es) ans = max(ans, (int)e.size());
        return N - ans - 1;
    }
    int k = K / 2;
    vector<int> depth(N, -1);
    depth[root] = 0;
    vector<int> parent(N, -1);
    parent[root] = root;
    vector<int> child(N, 0);
    vector<int> childKp1(N, 0);
    vector<bool> closed(N, false);
    vector<int> stack = {root};
    while (not stack.empty()){
        int v = stack.back();
        if (closed[v]){
            stack.pop_back();
            childKp1[parent[v]] += childKp1[v];
            child[parent[v]] += child[v] + 1;
            continue;
        }
        for (int u : Es[v]){
            if (depth[u] != -1) continue;
            depth[u] = depth[v] + 1;
            parent[u] = v;
            if (depth[u] == k + 1){
                ++childKp1[v];
                continue;
            }
            stack.push_back(u);
        }
        closed[v] = true;
    }
    int cum = 1;
    int maxKp1 = 0;
    for (int v : Es[root]){
        cum += child[v] + 1;
        maxKp1 = max(maxKp1, childKp1[v]);
    }
    int ans = N - cum;
    if (K & 1) ans -= maxKp1;
    return ans;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    vector<vector<int>> Es(N, vector<int>());
    for (int i = 0; i != N - 1; ++i){
        int a, b;
        cin >> a >> b;
        Es[a - 1].push_back(b - 1);
        Es[b - 1].push_back(a - 1);
    }
    int ans = N;
    for (int v = 0; v != N; ++v){
        ans = min(ans, solve(v, N, K, Es));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		if(n * a < b) {
			System.out.println(n * a);
		} else {
			System.out.println(b);
		}
	}

}


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

#define ll long long


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

    cin >> ws;


   string s;
   getline(cin,s);
    int x=s.size();
    if(x>k){
   for(int i=0;i<k;i++){
    cout<<s[i];
   }
   cout<<"...";

    }
    else {
        cout<<s;
    }

}



Measured memory_bytes: 3600
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}

int main(){
    std::ios::sync_with_stdio(false);
    string s;
    cin >> s;

    int start_from_b = 0;
    int start_from_w = 0;

    for(int i=0;i<s.length();++i)
    {
        if(s[i] == '0') {
            //black
            if((i%2) == 0)
            {
                start_from_w++;
            }
            else
            {
                start_from_b++;
            }
        }
        else
        {
            if((i%2) == 0)
            {
                start_from_b++;
            }
            else
            {
                start_from_w++;
            }
        }
    }
    cout << min(start_from_b, start_from_w) << endl;
}

Measured memory_bytes: 512
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BTAKOYAKIFESTIVAL2019 solver = new BTAKOYAKIFESTIVAL2019();
        solver.solve(1, in, out);
        out.close();
    }

    static class BTAKOYAKIFESTIVAL2019 {
        public void solve(int testNumber, FastReader s, PrintWriter out) {
            int n = s.nextInt();
            int[] arr = s.nextIntArray(n);
            int ans = 0;
            int sumTillNow = 0;
            for (int i = 0; i < n; i++) {
                ans += (arr[i] * sumTillNow);
                sumTillNow += arr[i];
            }
            out.println(ans);
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int[] nextIntArray(int n) {
            int[] array = new int[n];
            for (int i = 0; i < n; ++i) array[i] = nextInt();
            return array;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 23380
#!/usr/bin/env python
# coding: utf-8

import math

def main():
    n, k = list(map(int, input().split()))
    cand = []
    tk = k
    tn = n
    while tk > 0.5:
        if int(tk) == tk:
            cand.append(max(0, tn-tk+1))
            tn = min(tn, tk-1)
        else:
            cand.append(max(0, tn-int(tk)))
            tn = min(tn, int(tk))
        tk /= 2
    ans = sum(cand[i] * pow(2, len(cand)-i) for i in range(len(cand)))
    print(ans/(n*pow(2, len(cand))))


if __name__ == '__main__':
    main()


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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    int k, s;
    cin >> k >> s;
    ll ans = 0;
    rep(i, k+1) rep(j, k+1) {
        if (s-(i+j)<=k && i+j<=s) ++ans;
    }
    cout << ans << endl;
    return 0;
}


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

string get_s(string s){
  string res = "";

  res += s[0];
  for(int i = 1; i < s.size(); i++){
    if(s[i-1] == 'a' || s[i-1] == 'i' || s[i-1] == 'u' || s[i-1] == 'e' || s[i-1] == 'o'){
      res += s[i];
    }
  }
  return res;
}
int main(){

  string tmp;
  string air[55];
  string name[55];
  int n;
  while(cin >> n, n){
    for(int i = 0; i < n; i++){
      cin >> tmp;
      air[i] = get_s(tmp);
    }
    int flag = 0;
    for(int k = 1; k <= 50; k++){
      for(int i = 0; i < n; i++){
        if(air[i].size() < k){
          name[i] = air[i];
        }else{
          name[i] = air[i].substr(0, k);
        }
      }
      for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
          if(name[i] == name[j]) flag = 1;
        }
      }
      if(flag == 0){
        cout << k << endl;
        break;
      }
      if(flag = 1 && k == 50){
        cout << "-1" << endl;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register

using namespace std;
const int N=2000+10,mod=1e9+7;
il int rd()
{
  int x=0,w=1;char ch=0;
  while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
  if((x*=w)==-1) exit(0);
  return x;
}
int n,kk,f[N][N],fac[N*N],iac[N*N];
il int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;}return an;}
il int C(int n,int m){return m<0||n<m?0:1ll*fac[n]*iac[m]%mod*iac[n-m]%mod;}

int main()
{
  n=rd(),kk=rd();
  fac[0]=1;
  for(int i=1;i<=n*kk;++i) fac[i]=1ll*fac[i-1]*i%mod;
  iac[n*kk]=fpow(fac[n*kk],mod-2);
  for(int i=n*kk;i;--i) iac[i-1]=1ll*iac[i]*i%mod;
  f[0][0]=1;
  for(int i=1;i<=n;++i)
	for(int j=0;j<=i;++j)
	  f[i][j]=(f[i-1][j]+(j?(1ll*f[i][j-1]*(n-j+1)%mod*C(n-i+(n-j+1)*(kk-1)-1,kk-2)%mod):0))%mod;
  printf("%d\n",kk>1?f[n][n]:1);
  return 0;
}


Measured memory_bytes: 47488
n = input()
if n[-1] == "2" or n[-1] == "4" or n[-1] == "5" or n[-1] == "7" or n[-1] == "9":
    print("hon")
elif n[-1] == "0" or n[-1] == "1" or n[-1] == "6" or n[-1] == "8":
    print("pon")
else:
    print("bon")

Measured memory_bytes: 9056
ans = []
num = gets.chomp.to_i
(1..num).each do |i|
  if i % 3 == 0
    ans << i
  elsif i % 10 == 3
    ans << i
  else
    j = i
    while j / 10 > 0
      j /= 10
      if j % 10 == 3
        ans << i
        break
      end
    end
  end
end

print "\s"
puts ans.join("\s")

Measured memory_bytes: 8816
#include "bits/stdc++.h"

#define rep(i,n) for(int i = 0;i<n;i++)
#define cint(a) int a; cin >> a;
#define cstr(str) string str; cin >> str;


using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;

int main(void) {

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

	int l, r,d;
	cin >> l >> r >> d;
	int cnt = 0;
	for (; l <= r; l++) {
		if (l % d == 0) cnt++;
	}

	cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstdlib>
using namespace std;

int main(){
	typedef pair<int,int> pii;
	vector<pii>::iterator it;
	int n, m, k, x, d, h, i, j;
	for(; cin >> n >> m, n; ){
		vector<pii> st[151];
		for( i = 1; i <= n; i++ ){
			for( cin >> k; k--; ){
				cin >> x >> d;
				st[i].push_back( pii( x, d ) );
			}
		}

		int dp[158][151][10];
		fill( **dp, *dp[158], 1e9 );
		for( i = st[1].size(); i--; ){
			dp[m][1][i] = 0;
		}
		for( i = st[2].size(); i--; ){
			dp[m-1][2][i] = 0;
		}

		for( h = 2; h <= n; h++ ){
			for( i = m; i >= 0; i-- ){
				for( j = st[h].size(); j--; ){
					for( k = st[h-1].size(); k--; ){
						x = dp[i][h-1][k]
						  + ( st[h][j].second + st[h-1][k].second )
						  * abs( st[h][j].first - st[h-1][k].first );
						dp[i][h][j] = min( dp[i][h][j], x );
					}
					for( k = st[h-2].size(); k--; ){
						x = dp[i+1][h-2][k]
						  + ( st[h][j].second + st[h-2][k].second )
						  * abs( st[h][j].first - st[h-2][k].first );
						dp[i][h][j] = min( dp[i][h][j], x );
					}
				}
			}
		}
		x = 1e9;
		for( i = m; i >= 0; i-- ){
			for( j = st[n].size(); j--; ){
				x = min( x, dp[i][n][j] );
			}
		}
		for( i = m; i > 0; i-- ){
			for( j = st[n-1].size(); j--; ){
				x = min( x, dp[i][n-1][j] );
			}
		}
		
		cout << x << endl;
	}
}

Measured memory_bytes: 1868
n = int(input())
A = list(map(int, input().split()))

def gcd(a, b):
    while b != 0:
        c = a%b
        a = b
        b = c
    return a

for i in range(1, n):
    A[i] = gcd(A[i-1], A[i])
print(A[-1])

Measured memory_bytes: 85232
import fractions
import sys
from functools import reduce
import math

input = sys.stdin.readline


def main():
    n, q = input_list()
    s = input()
    cumulative_sum = [0]
    i = 0
    for index, sv in enumerate(s):
        if index >= len(s)-1:
            continue
        if s[index] + s[index+1] == 'AC':
            i += 1
            cumulative_sum.append(i)
        else:
            cumulative_sum.append(i)
    for _ in range(q):
        l, r = input_list()
        print(cumulative_sum[r-1] - cumulative_sum[l-1])


def get_camulative(l):
    import itertools
    # 累積和
    return [0] + list(itertools.accumulate(l))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()


Measured memory_bytes: 79892
(*
ocamlfind ocamlopt -package batteries -linkpkg main.ml -o a.out
*)
open Batteries

let lst = 
        List.init 5 (
                fun _ -> 
                        Scanf.sscanf (read_line ()) "%d" (
                                fun n -> n
                        )
        )
        |> List.sort (fun el1 el2 ->
                let d1 = (10 * ((el1 / 10) + 1) - el1) mod 10 in
                let d2 = (10 * ((el2 / 10) + 1) - el2) mod 10 in
                        if d1 = d2 then
                                0
                        else
                        if d1 < d2 then
                                -1
                        else
                                1

        )

let rec f lst =
        match lst with
                  [] -> 0
                | first :: [] -> first
                | first :: rest -> 
                        let r = f rest in
                                if first mod 10 = 0 then
                                        first + r
                                else
                                        let d = (10 * ((first / 10) + 1)) in
                                                d + r

let () =
        f lst
        |> Printf.printf "%d\n"


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp> 
//using namespace __gnu_pbds; 
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int> >, rb_tree_tag,tree_order_statistics_node_update>
#define standardVar ll n,m,i,j,k,num,num1,num2,flag=0
#define nn <<"\n"
#define __ <<" "<<
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define ittr(x,v) for(auto x=v.begin();x!=v.end();x++)
#define itr(x,n) for(x=0;x<n;x++)
#define itrab(x,a,b) for(x=a;x<b;x++)
#define itpr(v) ittr(x,v)cout<<*x<<" "; cout nn
#define itppr(v) ittr(x,v)cout<<(*x).ff<<" "<<(*x).ss<<"  "; cout nn
#define pi 3.14159265359
#define dTor(x) ((x)*pi)/180.0
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef map<ll,ll> ml;
typedef set<ll> sl;
typedef string str;
typedef pair<ll, ll> pl;
typedef vector< pl > vpl;
typedef map<pl,ll> mpl;
typedef set< pl > spl;
typedef vector<str> vst;
typedef vector<vl> vvl;

const ll M=1000000007;
const ll N=998244353;

ll power(ll x, ll y, ll p){     //MODULAR EXPONENTIATION
    ll res=1;
    x=x%p;
    if(x==0)
        return 0;
    while(y>0){
        if(y&1)
            res=(res*x)%p;
        y=y>>1;
        x=(x*x)%p;
    }
    return res;
}
ll inv(ll x, ll m){             //FERMAT INVERSE
    return power(x,m-2,m);
}
struct comp{                    //COMPARISON ON PAIRS
    template<typename T>        
    bool operator()(const T &a, const T &b){
        if (a.ff==b.ff)
            return (a.ss<b.ss);
        else
            return (a.ff<b.ff);
    }
};
bool mod(const pair<ll,ll> &a, const pair<ll,ll> &b){   //COMPARATOR FOR PAIRS (SORTING)
    if(a.ff!=b.ff)
        return (a.ff<b.ff);
    else
        return (a.ss<b.ss);
}
void sieve(vl &prime){          //SIEVE OF ERATOSTHENES
    ll maxN=1e6;
    vector<bool> pr(maxN+1,1);
    for(int i=2;i*i<=maxN;i++)
        if(pr[i]==1)
            for(int j=i*i;j<=maxN;j+=i)
                pr[j]=0;
    for(ll i=2;i<=maxN;i++)
        if(pr[i]==1)
            prime.pb(i);
}
bool isValid(ll i, ll j, ll n, ll m){   //CHECKS FOR OVERFLOW
    if(i>=0&&i<n&&j>=0&&j<m){
        return true;
    }
    return false;
}

//MAIN FUNCTION STARTS HERE

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    standardVar;
    cin>>n;
    str s;
    cin>>s;
    ll l=0,r=n-1;
    ll c=0;
    while(l<r){
        while(s[l]!='W'&&l<n){
            l++;
        }
        while(s[r]!='R'&&r>=0){
            r--;
        }
        if(l<r){
            c++;
            l++;
            r--;
        }
    }
    cout<<c nn;
    return 0;
}

Measured memory_bytes: 3768
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long
#define pb push_back
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define inp(n) for(i=0;i<n;i++) cin>>A[i];
#define inz(A) memset(A,0,sizeof(A))
#define lb lower_bound
#define ub upper_bound
#define all(v) v.begin(),v.end()
#define T 1000000
#define F first
#define S second
#define pi pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define vp vector<pair< int,int> >
#define mpi map<pair<int,int> ,int>
#define mip map<int, pair<int,int> >
#define inf INT_MAX
#define inf1 LONGLONG_MAX
#define sz(v) v.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define deb(x) cout<<#x<<"is "<<x<<endl;
#define lower(s) transform(all(s),s.begin(),::tolower)
#define endl "\n"
vector<int>adj [T];
			/*brownsands IIITA*/
int power(int a,int x){a%=mod;
              int res=1;
		while(x>0){
		if(x&1)
		res=res*a%mod;
		a=a*a%mod;
                    x>>=1;  }
		return res;}
void solve()
{    int n,i,ans=0,j,x,cnt=0,p; mii m;
   cin >> n;int A[n+5];
   for(i=0;i<n;i++)
   {  cnt=0;
      cin >> A[i];x=A[i];
      while(x%2==0)
      {
         x=x/2;
         cnt++;
      }
      m[2]=max(m[2],cnt);
      for(j=3;j*j<=x;j+=2)
      {
         if(x%j == 0)
         {  cnt=0;
            while(x%j ==0)
            {
               x=x/j;
               cnt++;
            }
            m[j]=max(m[j],cnt);
         }
      }
      if(x!=1)
      m[x]=max(m[x],1LL);
   }
  // for(auto it:m)cout << it.F<<" "<<it.S<<endl;
  int l=1;
   for(auto i:m)
   {
      l=(l * power(i.F,i.S))%mod;
   }
   //cout << l <<" " 
   for(i=0;i<n;i++)
   {
      ans+=(l * power(A[i],mod-2));
      ans%=mod;
   }
   cout << ans;
}
signed main()
{
   boost
        int test=0,t;
		//cin>>t;
		t=1;
		while(test++ <t){
            //cout<<"Case "<<test<<": ";
            solve();
            //cerr << "\nTime : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n";
               }		
} 

Measured memory_bytes: 24448
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using lint = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

struct Point
{
    int x, y;
    int a;

    bool operator < (const Point& other)
    {
        return this->a < other.a;
    }
    bool operator <= (const Point& other)
    {
        return this->a < other.a;
    }
    bool operator > (const Point& other)
    {
        return this->a > other.a;
    }
    bool operator >= (const Point& other)
    {
        return this->a >= other.a;
    }

};

int main()
{
    int W, H, N;
    cin >> W >> H >> N;
    vector<Point> p(N);
    rep (i, N) { cin >> p[i].x >> p[i].y >> p[i].a; }

    int max1, max2, max3, max4;
    max1 = max3 = -1;
    max2 = max4 = 1000;
    rep (i, N)
    {
        switch(p[i].a)
        {
        case 1:
            chmax(max1, p[i].x);
            break;
        case 2:
            chmin(max2, p[i].x);
            break;
        case 3:
            chmax(max3, p[i].y);
            break;
        case 4:
            chmin(max4, p[i].y);
            break;
        }
    }

    if (max2 != 1000)
    {
        W = max2;
    }
    if (max1 != -1)
    {
        W -= max1;
    }
    if (max4 != 1000)
    {
        H = max4;
    }
    if (max3 != -1)
    {
        H -= max3;
    }

    if (W > 0 && H > 0)
    {
        cout << W * H << "\n";
    }
    else
    {
        cout << 0 << "\n";
    }

    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
long long s(long long n,long long x)
{
if(n%x==0)
return {2*(n/x)*x-x};
else{return {2*(n/x)*x+s(x,n%x)};
}
}
int main()
{
long long n,i;
scanf("%lld%lld",&n,&i);
printf("%lld",s(n-i,i)+n);
}

Measured memory_bytes: 128