akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#if __cplusplus >= 201103L
#include <chrono>
using namespace std::chrono;
#endif
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#ifdef LOCAL
#define prln(x) (cout << #x << ' ' << x << endl)
#define pr(x) (cout << #x << ' ' << x << ' ' )
#define prv(x) (cout << x << ' ')
#else
#define prln(x) 
#define pr(x)
#define prv(x)
#endif
#define clr(x) memset((x), 0, sizeof((x)))
#define clr1(x) memset((x), -1, sizeof((x)))
#define endl "\n"
#define pi acos(-1)
#define rep(i, st, ed) for (int i = (st); i <= (ed); ++i)
#define rep0(i, st, ed) for (int i = (st); i < (ed); ++i)
#define per0(i, st, ed) for (int i = (st); i > ed; --i)
#define per(i, st, ed) for (int i = (st); i >= ed; --i)
#define chmin(a, b) (a = a > b ? b : a)
#define chmax(a, b) (a = a < b ? b : a)
template<class T> void _sf(T &x) {cin >> x;}
void _sf(int &x) {scanf("%d", &x);}
void _sf(ll &x) {scanf("%lld", &x);}
void _sf(double &x) {scanf("%lf", &x);}
void _sf(char &x) {scanf(" %c", &x);}
void _sf(char *x) {scanf("%s", x);}
void sf() {}
template <class T, class...U> void sf(T & head, U&... tail) { _sf(head); sf(tail...);}
template<class T> void _out(const T &x) { cout << x; }
void _out(const int &x) { printf("%d", x); }
void _out(const ll &x) { printf("%lld", x); }
void _out(const double &x) { printf("%.16f", x); }
void _out(const char &x) { putchar(x); }
void _out(const char *x) { printf("%s", x); }
template<class T,class U> void _out(const pair<T,U> &x) {_out(x.F); putchar(' '); _out(x.S);}
template<class T> void _out(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _out(*i++)) if (i != x.cbegin()) putchar(' '); }
void out() {}
template<class T, class... U> void out(const T &head, const U &... tail) { _out(head); putchar(sizeof...(tail) ? ' ' : '\n'); out(tail...); }
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


int main(){
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    ll n, a, b;
    sf(n, a, b);
    ll tot = a + b;
    if (a == 0) {
        out(0);
        return 0;
    }
    ll now = n / tot;
    now *= a;
    ll m = n % tot;
    if (m <= a) now += m;
    else now += a;
    out(now);
    return 0;
}

Measured memory_bytes: 256
n, q = gets.chomp!.split(" ").map!(&:to_i)
s = gets.chomp!
l = Array.new(0, q)
r = Array.new(0, q)

q.times do |i|
    l[i], r[i] = gets.chomp!.split(" ").map!(&:to_i)
end

memo = { -1 => 0 }
(n - 1).times do |i|
    if s[i] == 'A' && s[i + 1] == "C"
        memo[i] = memo[i - 1] + 1 
    else
        memo[i] = memo[i - 1]
    end
end
memo[n-1] = memo[n-2]
memo[n] = memo[n-1]

#require 'pp'
#pp memo

q.times do |i|
    puts memo[r[i] - 2] - memo[l[i] - 2]
end


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

int main()
{
	int n;
	cin>>n;
	string str;
	char c;
	cin>>str;
	set<string> s;
	c=str[str.length()-1];
	s.insert(str);
	int flag=1;
	for(int i=1;i<n;i++){
		cin>>str;
		if(c!=str[0]||s.count(str))
			flag=0;
		s.insert(str);
		c=str[str.length()-1];
	}
    if(flag==0)
    	cout<<"No";
	else
		cout<<"Yes";
} 



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
int main(){
        long long N,A[100000],B[100000],SumA=0,SumB=0,C[100000],rest=0,result=0;
        std::cin >> N;
        for(int i=0; i<N; i++) {
                std::cin >> A[i];
                SumA+=A[i];
        }
        for(int i=0; i<N; i++) {
                std::cin >> B[i];
                SumB+=B[i];
                C[i]=A[i]-B[i];
        }
        if(SumA<SumB) {
                std::cout << -1;
                return 0;
        }
        std::sort(C,C+N);
        int i=0,j=N-1;
        while(C[i]<0) {
                rest+=C[j];
                result++;
                while(rest>0&&C[i]<0) {
                        rest+=C[i];
                        result++;
                        i++;
                }
                j--;
        }
        if(rest<0) std::cout <<result+1;
        else std::cout << result;
        return 0;
}


Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner scan=new Scanner(System.in);
		double r=scan.nextDouble();
		double S=Math.PI * r * r;
		double L=2*Math.PI*r;
		System.out.printf("%f %f\n",S,L);
		
	}
}


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

int main() {
    int N;
    cin >> N;
    const int INF = INT_MAX;
    vector<int> B(N, INF);
    rep (i, N-1) cin >> B[i];

    int sum = B[0];
    rep (i, N - 1) sum += min(B[i], B[i+1]);
    cout << sum << endl;

    return 0;
}


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

#define pi(x) cout<<x;
#define ps(x) cout<<x<<" ";
#define pnl(x) cout<<x<<"\n";
#define for0(n) for(i=0;i<n;i++)
#define for1(n) for(i=1;i<=n;i++)
#define m(x) memset(x,0,sizeof x);
#define nl cout<<"\n";
#define mp make_pair
#define pb push_back
#define fr first
#define se second
#define Inf 1e16

 
int main(){
ll test,i,j,xy,flag=0,n,u,count,d,o1=0,o2=0,s,e,l,r,x,y,m,z,max1,x1,y1,k,x2,y2,z1,sum,f,min1;
cin>>n;
count=0;
flag=0;
for(i=0;i<n;i++){
	cin>>x>>y;
	if(x==y){
		count++;
	}else{
		if(count>=3){
			flag=1;
		}
		count=0;
		
	}
}
  if(count>=3){
    flag=1;
  }
if(flag==0){
	cout<<"No";
}else{
	cout<<"Yes";
}
return 0;
}

Measured memory_bytes: 3620
import itertools

N,M = list(map(int,input().split(" ")))

# graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**20
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]
edges = []
for i in range(M):
    a,b,c = list(map(int,input().split(" ")))
    cost[a][b] = c
    cost[b][a] = c
    edges.append((a,b,c))
for i in range(1,N+1):
    cost[i][i] = 0
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j])

ans = 0
for k,edge in enumerate(edges):
            a,b,c = edge
            if  cost[a][b] !=c:
                ans += 1
print(ans)


Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n;
int a[maxn];
set<int> s;
int main(){
    //freopen("input.txt", "r", stdin);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {        
        cin >> a[i];
        s.insert(a[i]);
    }
    sort(a+1, a+1+n);
    int mx = a[n], mn;
    cout << mx << " ";
    int dif = 1e9+5;
    double half = mx/2.0;
    for(int i = 1; i <= n; i++){
        if(fabs(half - a[i]) < dif){
            dif = fabs(half - a[i]);
            mn = a[i];
        }
    }
    cout << mn << "\n";
    return 0;
}

Measured memory_bytes: 5376
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try(Scanner scanner = new Scanner(System.in)) {
			String data = scanner.nextLine();
			String[] arr = data.split(" ");
			long a = Long.parseLong(arr[0]);
			long b = Long.parseLong(arr[1]);
			long c = Long.parseLong(arr[2]);
			long d = Long.parseLong(arr[3]);

			List<Long> xList = new ArrayList<Long>() {
				{
					add(a);
					add(b);
				}
			};

			List<Long> yList = new ArrayList<Long>() {
				{
					add(c);
					add(d);
				}
			};

			long ans = -1 * Long.MAX_VALUE;
			for (Long x : xList) {
				for (Long y : yList) {

					ans = Math.max(ans, x * y);

				}
			}

			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 35696
#include "bits/stdc++.h"
using namespace std;

const int N = 210;
int sum[N];

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

    int max = 0;
    for (int i = 1; i <= n; ++i) {
        if (s[i - 1] == '(') sum[i]++;
        else sum[i]--;
        sum[i] += sum[i - 1];
        max = min(max, sum[i]);
    }

    if (max < 0) {
        max *= -1;
        s = string(max, '(') + s;
        n = s.size();
    }

    memset(sum, 0, sizeof sum);
    for (int i = 1; i <= n; ++i) {
        if (s[i - 1] == '(') sum[i]++;
        else sum[i]--;
        sum[i] += sum[i - 1];
    }

    if (sum[n] > 0) s = s + string(sum[n], ')');
    cout << s << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rep(i,n) for (int i=0;i<(n);i++)
typedef long long ll;
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	string s;
	cin>>s;
	rep(i,s.size()) cout<<"x";
	return 0;
}


Measured memory_bytes: 256
n = int(input())
dict1 = {}
ans = 0

# nを素因数分解したリストを返す
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

for i in range(1,n+1):
    t = prime_decomposition(i)
    for j in t:
        if j in dict1:
            dict1[j] += 1
        else:
            dict1[j] = 1

dict1_sorted = sorted(dict1.items(), key=lambda x:x[0])

li = []
for i in dict1_sorted:
    if i[1] >= 2:
        li.append(i)

m = len(li)

for i in li:
    if i[1] >= 74:
        ans += 1
    else:
        break

for i in li:
    for j in li:
        if i[0] != j[0]:
            if i[1] >= 2 and j[1] >= 24:
                ans += 1
            if i[1] >= 4 and j[1] >= 14:
                ans += 1

ans2 = 0

for i in li:
    for j in li:
        for k in li:
            if i[0] != j[0] and j[0] != k[0] and k[0] != i[0]:
                if i[1] >= 2 and j[1] >= 4 and k[1] >= 4:
                    ans2 += 1

ans += ans2 // 2

print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>

using namespace std;

int main(void) {
    string S;
    cin >> S;

    int sum = 0;
    for (auto c: S) {
        sum += c - 48;
    }

    cout << (sum % 9 ? "No":"Yes") << endl;
    
    return 0;
}

Measured memory_bytes: 3732
#include<iostream>
#include<string>
using namespace std;
int main(){
	int n;
	cin >>n;
	while(n--){
		string a,b,c;
		cin >>a>>b;
		int x = a.size(),y = b.size(),t = 0,max = (x>y)?x:y;
		for(int i=0; i<max; i++){
			if(i<x && i<y){t = (int)a[x-i-1]+(int)b[y-i-1]-2*'0'+t/10;}
			else if(i<x){t = (int)a[x-i-1]-'0'+t/10;}
			else if(i<y){t = (int)b[y-i-1]-'0'+t/10;}
			c+=(char)(t%10)+'0';
		}
		if(t/10){c+='1';}
		if(c.size() > 80){cout<<"overflow";}
		else{for(int i=c.size()-1; i>=0; i--){cout<<c[i];}}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdlib>
using namespace std;
int main(){
      int w,n,fx,fy,tx,ty,solve=0,i=1;
      cin>>w>>w>>n>>tx>>ty;
      for(;i<n;i++){
            fx=tx,fy=ty;
            cin>>tx>>ty;
            solve+=((tx-fx)*(ty-fy)>0)?max(abs(tx-fx),abs(ty-fy)):(abs(tx-fx)+abs(ty-fy));
      }
      cout<<solve<<endl;
}

Measured memory_bytes: 1160
using System;
using System.Collections.Generic;
public class ABC142B {
    public static void Main() {
        int N, K, ans = 0;
        string[] str = Console.ReadLine().Split(' ');
        N = int.Parse(str[0]);
        K = int.Parse(str[1]);
        str = Console.ReadLine().Split(' ');
        for (int i = 0; i < str.Length; i++) {
            int h = int.Parse(str[i]);
            if (h >= K) ans++;
        }
        
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 15456
n,m,x = map(int,input().split())


cal = [list(map(int,input().split())) for _ in range(n)]


from itertools import product
ans = float("inf")

for bits in product([0, 1], repeat=n):
    ansl = [0 for _ in range(m+1)]
    for idx, bit in enumerate(bits):
        for i in range(m+1):
            ansl[i] += bit * cal[idx][i]
    for i in range(1, m+1):
        if ansl[i] < x:
            break
    else:
        ans = min(ansl[0], ans)
    continue
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Measured memory_bytes: 68568
#include<iostream>
using namespace std;
int main(){
int a[3],k;
cin >> a[0] >> a[1] >> a[2] >> k;
int ans=-100;
int b=-1;
for(int i=0;i<3;i++){
if(a[i]>ans){
ans=a[i];
b=i;
}}
for(int i=0;i<k;i++)
ans*=2;
for(int i=0;i<3;i++)
if(i!=b)ans+=a[i];
cout << ans;
return 0;
}

Measured memory_bytes: 256
num = int(input())
table = [input().split() for _ in range(num)]

score_taro = 0
score_hanako = 0

for duel in table:
    if duel[0] > duel[1]:
        score_taro += 3
    elif duel[0] < duel[1]:
        score_hanako += 3
    else:
        score_taro += 1
        score_hanako += 1
        
print(score_taro, score_hanako)


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

using namespace std;

int main(){

    int A, B, H, M;
    cin >> A >> B >> H >> M;

    double theta;
    theta = 8.0 * atan(1.0) * abs( static_cast<double>(M) / 60.0 - static_cast<double>( H * 60 + M ) / 720.0 );
    if(theta > 4.0 * atan(1.0) ) theta = 8.0 * atan(1.0) - theta;

    printf("%15.14f\n", sqrt(A*A + B*B - 2*A*B*cos(theta)) );

    return 0;
}


Measured memory_bytes: 4152
#include<string>
#include<iomanip>
#include<iostream>
#include<math.h>
using namespace std;
#define NUM 100001

int main() {
	int N, M;
	int *LR1;
	LR1 = new int[NUM]();
	int *LR2;
	LR2 = new int[NUM]();
	int *gate;
		gate =new int [NUM]();
	
	cin >> N >> M;

	int left = 0;
	int right = N+1;

	for (int i = 1; i <= M; i++) {
		cin >> LR1[i] >> LR2[i];
		if (LR1[i] > left)
			left = LR1[i];
		if (LR2[i] < right)
			right = LR2[i];
	}

	if (left > right)
		cout << 0 << endl;
	else
	cout << right - left +1 << endl;

	return 0;
}

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

#define endl "\n"

using namespace std;
using ll = long long;

const ll MOD = 1e9+7;

int main(){
    int h,w;
    cin>>h>>w;
    char a[h][w];
    int num[26] = {};

    bool ok = true;

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>a[i][j];
            num[a[i][j] - 'a']++;
        }
    }

    for(int i=0;i<h/2;i++){
        for(int j=0;j<w/2;j++){
            for(int k=0;k<26;k++){
                if(num[k]>=4){
                    num[k] -= 4;
                    break;
                }
            }
        }
    }

    if(h%2==1 && w%2==0){
        for(int i=0;i<w/2;i++){
            for(int j=0;j<26;j++){
                if(num[j]>=2){
                    num[j] -= 2;
                    break;
                }
            }
        }
    }
    if(h%2==0 && w%2==1){
        for(int i=0;i<h/2;i++){
            for(int j=0;j<26;j++){
                if(num[j]>=2){
                    num[j] -= 2;
                    break;
                }
            }
        }
    }
    if(h%2==1 && w%2==1){
        for(int i=0;i<h/2;i++){
            for(int j=0;j<26;j++){
                if(num[j]>=2){
                    num[j] -= 2;
                    break;
                }
            }
        }
        for(int i=0;i<w/2;i++){
            for(int j=0;j<26;j++){
                if(num[j]>=2){
                    num[j] -= 2;
                    break;
                }
            }
        }
        for(int i=0;i<26;i++){
            if(num[i]>=1){
                num[i] -= 1;
                break;
            }
        }
    }

    for(int i=0;i<26;i++){
        if(num[i] > 0) ok =false;
    }

    if(ok) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mn(a, b) (a < b ? a : b)
#define mx(a, b) (a > b ? a : b)
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
#define base 331

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int const MAXn = 4e2 + 2;

ll dp[MAXn][MAXn];
ll arr[MAXn];

int main(){

    //freopen(".in","r",stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++)
            dp[i][j] = 1e17;
    }
    for(int i = 1; i <= n; i++){
        cin>>arr[i];
        arr[i] += arr[i - 1];
    }
    for(int d = 2; d <= n; d++){
        for(int i = 1; i + d - 1 <= n; i++){
            int j = i + d - 1;
            for(int k = i; k < j; k++){
                dp[i][j] = mn(dp[i][j], dp[i][k] + dp[k + 1][j] + arr[j] - arr[i - 1]);
            }
        }
    }
    cout<<dp[1][n];
    return 0;
}


Measured memory_bytes: 1536
N,X,Y = map(int,input().split())
cc = [0]*(N-1)
for i in range(1,N+1):
  for j in range(i+1,N+1):
    cc[min(j-i,abs(X-i)+1+abs(Y-j))-1] += 1
for i in cc:
  print(i)


Measured memory_bytes: 9260
import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;


public class Main {
	 static class FastReader 
	    { 
	        BufferedReader br; 
	        StringTokenizer st; 
	       
	  
	        public FastReader() 
	        { 
	            br = new BufferedReader(new
	                     InputStreamReader(System.in)); 
	        } 
	  
	        String next() 
	        { 
	            while (st == null || !st.hasMoreTokens()) 
	            { 
	                try
	                { 
	                    st = new StringTokenizer(br.readLine()); 
	                } 
	                catch (IOException  e) 
	                { 
	                    e.printStackTrace(); 
	                } 
	            } 
	            return st.nextToken();
	            
	        } 
	  
	        int nextInt() 
	        { 
	            return Integer.parseInt(next()); 
	        } 
	  
	        long nextLong() 
	        { 
	            return Long.parseLong(next()); 
	        } 
	  
	        double nextDouble() 
	        { 
	            return Double.parseDouble(next()); 
	        } 
	  
	        String nextLine() 
	        { 
	            String str = ""; 
	            try
	            { 
	                str = br.readLine(); 
	            } 
	            catch (IOException e) 
	            { 
	                e.printStackTrace(); 
	            } 
	            return str; 
	        }

			public Character charAt(int i) {
				// TODO Auto-generated method stub
				return null;
			} 
	    } 
	 static int divisors(long x) {
		    long limit = x;
		    int numberOfDivisors = 0;

		    if (x == 1) return 1;

		    for (int i = 1; i < limit; ++i) {
		        if (x % i == 0) {
		            limit = x / i;
		            if (limit != i) {
		                numberOfDivisors++;
		            }
		            numberOfDivisors++;
		        }
		    }

		    return numberOfDivisors;
		} 
	public static void main(String[] args)throws IOException  {
		FastReader s=new FastReader();		
		int k = s.nextInt();
		int n = s.nextInt();
		int[] ar = new int[n];
		for(int i=0;i<n;i++) {
			ar[i]=s.nextInt();
		}
		int c=ar[n-1]-ar[0];
		for(int i=1;i<n;i++) {
			c=Math.min(c,(k-ar[i]+ar[i-1]));
		}
		
		System.out.println(c);
	}
}

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

int translate(char c);

int main()
{
    string line;
    while(cin >> line)
    {
        int buffer = 0;
        int number = 0;
        for(int i=0; i<line.size()-1; i++)
        {
            int current_val = translate(line[i]);
            int next_val = translate(line[i+1]);
            buffer += current_val;
            if(current_val > next_val)
            {
                number += buffer;
                buffer = 0;
            }
            else if(current_val < next_val)
            {
                number -= buffer;
                buffer = 0;
            }
            else
            {
                /* Nop */
            }
        }
        number += buffer;
        number += translate(line[line.size()-1]);
        cout << number << endl;
    }
    return 0;
}

int translate(char c)
{
    int ret_val = 0;
    if(c == 'I')
    {
        ret_val = 1;
    }
    else if(c == 'V')
    {
        ret_val = 5;
    }
    else if(c == 'X')
    {
        ret_val = 10;
    }
    else if(c == 'L')
    {
        ret_val = 50;
    }
    else if(c == 'C')
    {
        ret_val = 100;
    }
    else if(c == 'D')
    {
        ret_val = 500;
    }
    else if(c == 'M')
    {
        ret_val = 1000;
    }
    else
    {
       /* Nop */  
    }
    return ret_val;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int64_t> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);    
  }
  int64_t ans = 10000000000000000;
  for (int tmp = 0; tmp < (1 << N); tmp++) {
    bitset<15> s(tmp);
    int64_t M = 0;
    int C = 0;
    int64_t H = 0;
    for (int i = 0; i < N; i++) {
      if (a.at(i) > M) {
        C++;
        M = a.at(i);
      }
      else if (s.test(i)) {
        C++;
        M++;
        H += (M - a.at(i));
      }
    }
    if (C == K) {
      ans = min(ans, H);
    }
  }
  cout << ans << endl;      
}

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

int main(){

    std::string s;
    std::size_t n;
    std::cin >> s >> n;

    for(size_t i = 0; i < n; i++){
        std::string op;
        std::size_t a, b;
        std::cin >> op >> a >> b;

        if(op == "print"){
            std::cout << s.substr(a, b - a + 1) << std::endl;
        }else if(op == "reverse"){
            std::reverse(s.begin() + a, s.begin() + b + 1);
        }else{
            std::string tmp;
            std::cin >> tmp;
            s.replace(a, b - a + 1, tmp);
        }
    }

    return 0;
}



Measured memory_bytes: 3216
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>
#include <sstream>
#include <fstream>
#include <climits>

typedef long long int64;

int main(void) {
  int64 mod = 1000000007;
  int64 n, k;
  std::cin >> n >> k;
  int64 sum = 0;
  for (int64 i = k; i <= n + 1; i++) {
    int64 min = (i - 1) * i / 2;
    int64 max = n * (n + 1) / 2 - (n - i) * (n - i + 1) / 2;
    int64 num = max - min + 1;
    sum += num;
  }
  std::cout << sum % mod << std::endl;
  return 0;
}


Measured memory_bytes: 3588
def readinput():
    n=int(input())
    a=list(map(int,input().split()))
    q=int(input())
    bcList=[]
    for _ in range(q):
        bcList.append(list(map(int,input().split())))
    return n,a,q,bcList

def main(n,a,q,bcList):
    hist=[0]*(10**5+1)
    for v in a:
        hist[v]+=1

    sum=0
    for i in range(1,10**5+1):
        sum+=i*hist[i]

    for b,c in bcList:
        sum=sum+hist[b]*(c-b)
        hist[c]+=hist[b]
        hist[b]=0
        print(sum)


if __name__=='__main__':
    n,a,q,bcList=readinput()
    main(n,a,q,bcList)



Measured memory_bytes: 32192
#include<bits/stdc++.h>
#include<iostream>
#include<utility>
#include<algorithm>
#include<string>
using namespace std;

int main(){
    int N;
    cin >> N;
    pair<pair<string,int>,int> pairs[N];

    for(int i=0;i<N;i++){
        string name;
        int score;
        cin >> name >> score;
        pairs[i] = make_pair(make_pair(name,-score),i);
    }
    sort(pairs,pairs+N);

    for(int i=0;i<N;i++)
        cout << pairs[i].second + 1 << endl;
}

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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()

const string YES = "Yes";
const string NO = "No";

void solve(std::vector<std::vector<long long>> A, long long N, std::vector<long long> b){
  rep(i, b.size()){
    rep(j, 3){
      rep(k, 3){
        if(A[j][k] == b[i]) A[j][k] = -1;
      }
    }
  }
  bool flag = false;
  rep(i, 3){
    bool f = true;
    rep(j, 3){
      f &= A[i][j] == -1;
    }
    flag |= f;
  }
  rep(i, 3){
    bool f = true;
    rep(j, 3){
      f &= A[j][i] == -1;
    }
    flag |= f;
  }
  if(A[0][0] == -1 && A[1][1] == -1 && A[2][2] == -1) flag = true;
  if(A[0][2] == -1 && A[1][1] == -1 && A[2][0] == -1) flag = true;
  if(flag) cout << YES << endl;
  else cout << NO << endl;
}

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

int main(){
    std::vector<std::vector<long long>> A(3, std::vector<long long>(3));
    for(int i = 0 ; i < 3 ; i++){
        for(int j = 0 ; j < 3 ; j++){
            scanf("%lld",&A[i][j]);
        }
    }
    long long N;
    scanf("%lld",&N);
    std::vector<long long> b(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&b[i]);
    }
    solve(std::move(A), N, std::move(b));
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;
#define MAXN 100000
#define ll long long
#define Trav(p) for(rint u = first[p], v; ~u; u = e[u].nex)
#define rint register int
#define gc() getchar()
inline ll read(ll ans = 0, rint sgn = ' ', rint ch = gc())
{
	for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
	for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
	return sgn-'-'?ans:-ans;
}
#define BUF_SIZE 1000000
#define _END fwrite(_Ob,1,_O-_Ob,stdout), _O = _Ob
#define Outc(a) (*_O++ = a)
char _Ob[BUF_SIZE+5], *_O = _Ob, _Os[25], *_Ot;
template <typename T> inline void Out(T x)
{
	if(!x){Outc('0'); return;} if(x < 0) Outc('-'), x = -x;
	for(_Ot = _Os; x; *_Ot++ = x%10+'0', x /= 10);
	for(; _Ot != _Os; Outc(*--_Ot)); if(_O-_Ob >= BUF_SIZE-50) _END;
}
int first[MAXN+5], fa[MAXN+5], sz[MAXN+5], tot, cen = -1, n; ll s[MAXN+5], w[MAXN+5], sw;
struct Edge{int to,nex; ll w; Edge(){} Edge(int _to, int _nex, ll _w){to=_to,nex=_nex,w=_w;}}e[(MAXN<<1)+5];
inline void Add(int a, int b){e[tot] = Edge(b,first[a],0), first[a] = tot++, e[tot] = Edge(a,first[b],0), first[b] = tot++;}
void DFS(int p){sz[p] = 1; Trav(p) if((v=e[u].to)-fa[p]) fa[v] = p, DFS(v), sz[p] += sz[v];}
void DFS_w(int p, int fa, ll d){sw += d; Trav(p) if((v=e[u].to)-fa) DFS_w(v,p,d+e[u].w);}
int main()
{
	n = read(), memset(first+1,-1,n<<2); for(rint i = 1; i < n; Add(read(),read()), i++); DFS(1); for(rint i = 1; i <= n; s[i++] = read());
	for(rint i = 0, u, v; i < tot; u = e[i].to, v = e[i^1].to, fa[u]==v?u^=v^=u^=v:0, e[i^1].w = e[i].w = w[i>>1] = (sz[v]<<1)!=n?(s[u]-s[v])/((sz[v]<<1)-n):(cen=i>>1,0), i += 2);
	if(~cen){int u = e[cen<<1].to, v = e[cen<<1|1].to; fa[u]==v?u^=v^=u^=v:0, DFS_w(u,0,0); w[cen] = (s[u]-sw)/sz[v];} for(rint i = 0; i < n-1; Out(w[i]), Outc('\n'), i++); _END; return 0;
}

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

using namespace std;

void solve(int n, int x) {
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      for (int k = j + 1; k <= n; k++) {
        if (i + j + k == x) ans++;
      }
    }
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  for (;;) {
    int n, x;
    cin >> n >> x;
    if (n + x == 0) {
      return 0;
    }
    solve(n, x);
  }
  return 0;
}


Measured memory_bytes: 3188
//#pragma GCC optimize("03,unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include<bits/stdc++.h>
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pb           push_back
#define ff           first
#define ss           second
#define gcd(a, b)    __gcd(a, b)
#define lcm(a, b)    ((a)*((b)/gcd(a,b)))
#define all(v)       v.begin(),v.end()
#define lllim        2147483648
#define Pi           2*acos(0.0)
#define sci(n)	     scanf("%d",&n)
#define scii(n,m)    scanf("%d%d",&n,&m)
#define scl(n)       scanf("%lld",&n)
#define scll(n,m)    scanf("%lld%lld",&n,&m)
#define pii          pair<int,int>
#define pll 	     pair<ll,ll>
#define mem(a,b)     memset(a, b, sizeof(a))
#define fill_(a,b)   fill(a,a+n,b);
#define MOD          1000000007
#define fast_cin     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define filein       freopen("input.txt","r", stdin)
#define D(x)         cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define case		 int t,cas=1;cin>>t;while(t--)
#define rep(i,a,n)   for(int i=a;i<n;i++)
#define rev(i,n,a)   for(int i=n;i>=a;i--)

/*------------------------------Graph Moves----------------------------*/
//const int fx[]= {+1,-1,+0,+0};
//const int fy[]= {+0,+0,+1,-1};
//const int fx[]= {+0,+0,+1,-1,-1,+1,-1,+1};  // Kings Move
//const int fy[]= {-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/

template<class T> void ckmin(T& a, const T& b) {
    a= b < a? b:a;
}
template<class T> void ckmax(T& a, const T& b) {
    a= b > a? b:a;
}



template<class T> void read(T& a) {
    std::cin>>a;
}
template<class T> void read(T& a, int sidx,  int eidx) {
    for(int i=sidx; i<eidx; i++)
        std::cin>>a[i];
}



using namespace std;
using namespace __gnu_pbds;

const int maxn=100005;


vector<int>pr;
bool mark[maxn];

void si()
{
    mem(mark,0);
    for(int i=4; i<maxn; i+=2) mark[i]=1;
    for(int i=3; i*i<maxn; i+=2)
    {
        if(!mark[i])
            for(int j=i*i; j<maxn; j+=2*i)
                mark[j]=1;
    }

    pr.pb(2);
    for(int i=3; i<maxn; i+=2)
        if(!mark[i])
            pr.pb(i);
}


void solve()
{
    ll n;
    cin>>n;
    
    int len=0;
    
    string t="";
    
    ll m=n;
   
    while(n>0)
    {
		n-=1;
		t+=(char('a'+(n%26)));
		n/=26;
	}
	reverse(all(t));
	cout<<t<<endl;
	
    
	
}


int main()
{
    fast_cin;
    // si();

    //while(scanf("%d",&n)!=EOF)
//case
    {
		//cas=cas;
        //cout<<""<<cas++<<""<<endl;
        solve();
    }

    return 0;
}


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

int nth_bit(int64_t num, int n){
    return (num >> n) & 1;
}

int pop_count(int bits){
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}


int main(){
    int H, W, K;
    cin >> H >> W >> K;
    string T[10];
    static int S[11][1001];
    for(int i=0; i<H; i++){
        cin >> T[i];
        for(int j=0; j<W; j++) if(T[i][j] == '1') S[i+1][j+1] = 1;
    }
    for(int i=1; i<=H; i++) for(int j=1; j<=W; j++) S[i][j] += S[i-1][j];
    for(int i=1; i<=H; i++) for(int j=1; j<=W; j++) S[i][j] += S[i][j-1];

    int ans = 1e9;
    for(int b=0; b<(1<<(H-1)); b++){
        vector<int> B = {0};
        for(int k=0; k<H-1; k++) if(nth_bit(b, k)) B.push_back(k+1);
        B.push_back(H);
        int sz = B.size();
        int res = sz-2;
        
        int bef = 0;
        while(bef < W){
            int j = bef;
            while(true && j<W){
                bool ok = true;
                for(int i=0; i<sz-1; i++){
                    int sum = S[B[i+1]][j+1] - S[B[i]][j+1] - S[B[i+1]][bef] + S[B[i]][bef];
                    if(sum > K) ok = false;
                }
                if(ok){
                    j++;
                }else{
                    break;
                }
            }
            if(bef == j){
                res = 1e9;
                break;
            }
            if(j < W) res++;
            bef = j;
        }
        ans = min(ans, res);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
class Main {
    static int H;
    static int W;
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	H = sc.nextInt();
	W = sc.nextInt();
	char[][] board = new char[H][W];
	for(int i = 0; i<H; i++) {
	    String str = sc.next();
	    for(int j = 0; j<W; j++) {
		board[i][j] = str.charAt(j);
	    }
	}
	long result = 0;;
	for(int i = 0; i<H; i++) {
	    for(int j = 0; j<W; j++) {
		if(board[i][j] == '#') {
		    long[] part = searchWhite(board,i,j);
		    result += part[0]*part[1];
		}
	    }
	}
	System.out.println(result);

    }

    public static long[] searchWhite(char[][] board, int i, int j) {
	char target = (board[i][j]=='#')? '.': '#';
	long[] cnt = {0,0};
	if(board[i][j] == '.') cnt[0]++;
	else if(board[i][j] == '#') cnt[1]++;
	board[i][j] = '*';
	long[] result;
	if(i+1<H) {
	    if(board[i+1][j] == target) {
		result = searchWhite(board,i+1,j);
		cnt[0] += result[0];
		cnt[1] += result[1];
	    }
	}
	if(i-1>=0) {
	    if(board[i-1][j] == target){
		result = searchWhite(board,i-1,j);
		cnt[0] += result[0];
		cnt[1] += result[1];
	    }
	}
	if(j+1<W) {
	    if(board[i][j+1] == target){
		result = searchWhite(board,i,j+1);
		cnt[0] += result[0];
		cnt[1] += result[1];
	    }
	}
	if(j-1>=0) {
            if(board[i][j-1] == target){
		result = searchWhite(board,i,j-1);
		cnt[0] += result[0];
		cnt[1] += result[1];
	    }
	}
	return cnt;
    }


}

Measured memory_bytes: 52356
// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200, mod = 998244353;

typedef long long ll;

int n, m[3], base, vis[MAX_N], sg[MAX_N];
vector<int> G[MAX_N], sum[3];

int fpow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

int main()
{
    scanf("%d", &n), base = fpow(ll(1e18) % mod, mod - 2);
    for (int rd = 0; rd < 3; rd++)
    {
        scanf("%d", &m[rd]);
        for (int i = 1; i <= n; i++)
            G[i].clear();
        for (int i = 1, u, v; i <= m[rd]; i++)
        {
            scanf("%d%d", &u, &v);
            if (u > v)
                swap(u, v);
            G[u].push_back(v);
        }
        memset(sg, 0, sizeof(sg)), memset(vis, -1, sizeof(vis));
        int cbase = fpow(10, 18 * n);
        for (int i = n; i >= 1; i--)
        {
            for (int v : G[i])
                vis[sg[v]] = i;
            while (vis[sg[i]] == i)
                sg[i]++;
            while (sum[rd].size() <= sg[i])
                sum[rd].push_back(0);
            sum[rd][sg[i]] = (0LL + sum[rd][sg[i]] + cbase) % mod, cbase = 1LL * cbase * base % mod;
        }
    }
    int ans = 0;
    for (int i = 0, siz1 = sum[0].size(); i < siz1; i++)
        for (int j = 0, siz2 = sum[1].size(); j < siz2; j++)
        {
            int k = i ^ j;
            if (k < sum[2].size())
                ans = (0LL + ans + 1LL * sum[0][i] * sum[1][j] % mod * sum[2][k] % mod) % mod;
        }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 9540
#include <stdio.h>

int main(void)
{
	int k,n;
	scanf("%d%d", &k, &n);
	int a[n];
	int i = 0;
	while (i < n)
		scanf("%d", &a[i++]);
	int max = 0;
	i = 1;
	while (i < n)
	{
		if (a[i] - a[i - 1] > max)
			max = a[i] - a[i - 1];
		i++;
	}
	if (max < k - a[n - 1] + a[0])
		max = k - a[n - 1] + a[0];
	printf("%d", k - max);
	return (0);
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define ll long long
int main()
{
    ll n,m;
    cin>>n>>m;
    cout<<abs((n-2)*(m-2));
    return 0;
}


Measured memory_bytes: 256
import math

K = int(input())

CACHE = {}
def gcd_with_memo(i, j):
    if j > i:
        i, j = j, i
    key = str(i) + ":" + str(j)
    if CACHE.get(key):
        return CACHE[key]
    else:
        CACHE[key] = math.gcd(i, j)
        return CACHE[key]

total = 0
r = range(1, K + 1)
for i in r:
    for j in r:
        for k in r:
            total += gcd_with_memo(gcd_with_memo(i, j), k)

print(total)

Measured memory_bytes: 75124
def seachPrimeNum(N):
    max = int(N ** (1/2))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

a = seachPrimeNum(10 ** 6)
n=(int)(input())
ans = 0
sumi = True
if n < 2:
  print(ans)
  sumi = False
else:
  ans = 0
  count = 0
  while(count < 78498):
    temp = 0
    while(n % a[count] == 0):
      n = n // a[count]
      temp += 1
    if temp >= 45:
      ans += 9
    elif temp >= 36:
      ans += 8
    elif temp >= 28:
      ans += 7
    elif temp >= 21:
      ans += 6
    elif temp >= 15:
      ans += 5
    elif temp >= 10:
      ans += 4
    elif temp >= 6:
      ans += 3
    elif temp >= 3:
      ans += 2
    elif temp >= 1:
      ans += 1
    
    count += 1
    temp = 0
    if n < 2:
      print(ans)
      sumi = False
      break
  if count == 78498 and sumi:
      print(1 + ans)
#print(a[-100])

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

int n,k;
int a[200005];

int main(){

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

    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i>k){
            cout<<(a[i]>a[i-k]?"Yes\n":"No\n");
        }
    }

    return 0;
}

Measured memory_bytes: 4432
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
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; }


int main(){
    int n; cin >> n;
    vector<ll> A(n), index(n); 
    rep(i, n){
        cin >> A[i]; A[i]--;
        index[A[i]] = i;
    }
    int cnt = 0, mx = 0, last = -1;
    rep(i, n){
        if(last < index[i]){
            cnt++;
        }else{
            cnt = 1;
        }
        last = index[i];
        chmax(mx, cnt);
    }
    int res = n - mx;
    cout << res << ln;
}

Measured memory_bytes: 6416
s=input().split()
ans=int(s[0])-int(s[1])
if abs(ans)>10**18:
  print("Unfair")
elif int(s[3])%2==0:
  print(int(s[0])-int(s[1]))
else:
  print(-1*(int(s[0])-int(s[1])))

Measured memory_bytes: 3060
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    divisors.reverse()
    return divisors
n, m = map(int, input().split())
l = make_divisors(m)
for i in l:
    if m / n >= i:
        print(i)
        exit()
print(1)

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

int main(){
  int V=10,t,d[10][10],h,w,ans=0;cin>>h>>w;
  REP(i,V) REP(j,V){
    cin>>t;
    d[i][j]=t;
  }
  REP(k,V) REP(i,V) REP(j,V) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
  REP(i,h*w){
    cin>>t;
    if(t!=-1) ans+=d[t][1];
  }
  cout<<ans;
}



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

typedef long long ll;
const int INF = 1e+8;
string to_c = "0123456789ABCDEF";

// aとbの最大公約数を返す(ユークリッドの互除法)
ll gcd(ll a, ll b){
    return (b > 0)? gcd(b, a%b) : a ;
}

// aとbの最小公倍数を返す
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b ;
}

// 分数型, p : 分子, q : 分母
struct Fraction{
	ll p, q;
	// コンストラクタ
	Fraction(ll p_, ll q_){
		if( p_ == 0 ){ // 分子が 0 のとき
			p = p_;
			q = 1;
		}else if( q_ == 0 ){ // 分母が 0 のとき
			p = INF;
			q = 1;
		}else{
			ll d = gcd(abs(p_),q_);
			p_ /= d;
			q_ /= d;
			p = p_;
			q = q_;
		}
	}
	Fraction(ll a){
		p = a;
		q = 1;
	}
	Fraction operator*(const Fraction& n){
		return Fraction( p * n.p , q * n.q );
	}
	Fraction operator/(const Fraction& n){
		return Fraction( p * n.q , q * n.p );
	}
	Fraction operator+(const Fraction& n){
		return Fraction( p * n.q + n.p * q , q * n.q );
	}
	Fraction operator-(const Fraction& n){
		return Fraction( p * n.q - n.p * q , q * n.q );
	}
	bool operator==(const Fraction& n){
		return (p == n.p && q == n.q);
	}
};
typedef pair<Fraction,int> P;

// 複数の最小公倍数
ll n_lcm(vector<P> &ans){
	ll res = 1;
	for(int i=0 ; i < ans.size() ; i++ ){
		res = lcm(res, ans[i].first.q);
		if( res > 1024 ) return -1;
	}
	return res;
}

// 16進数2桁を返す.
string to_hex(int x){
	int a = x / 16;
	int b = x % 16;
	string s;
	s.push_back( to_c[a] );
	s.push_back( to_c[b] );
	return s;
}

int main(){
	int T;
	cin >> T;
	for(int t_ = 0 ; t_ < T ; t_++ ){
		int N;
		vector<P> ans;
		cin >> N;
		for(int i=0 ; i < N ; i++ ){
			string R;
			cin >> R;
			
			for(int i=0 ; i < R.size() ; i += 2 ){
				int k = (R[i] - '0') * 16 + (R[i+1] - '0');
				if( k ){
					ans.push_back( P(Fraction(i/2, R.size()/2), k) );
				}
			}
		}
		
		// 音が鳴っていないとき
		if( ans.size() == 0 ){
			cout << "00" << endl;
			continue;
		}
		
		ll L = n_lcm(ans);
		if( L == -1 ){
			cout << "Too complex." << endl;
		}else{
			vector<int> a(L, 0);
			for(int i=0 ; i < ans.size() ; i++ ){
				int k = (ans[i].first * Fraction(L)).p;
				a[k] |= ans[i].second;
			}
			for(int i=0 ; i < L ; i++ ){
				cout << to_hex(a[i]);
			}
			cout << endl;
		}
	}
}

Measured memory_bytes: 1456
#include<bits/stdc++.h>
using namespace std;
int a[200009];
int pnz[200009];
main(){
    int n;
    cin >> n;
    int nz = 0;
    for(int i =1; i <= n; i++){
        cin >> a[i];
        pnz [i] = nz;
        if(a[i] != 0) nz = i;
    }
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        int S = 0,xS=0;
        int j = i;
        while(j > 0){

            S += a[j];
            xS ^= a[j];
            if(S != xS) break;
            j = pnz[j];
        }
        ans += i- j ;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1792
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.lang.Math;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		
		char[] ds = sc.next().toCharArray();
		char[] t = sc.next().toCharArray();
		
		int last = -1;
		
		loop2:for(int i=ds.length-t.length;i>=0;i--){
			boolean can = true;
			loop:for(int j=0;j<t.length;j++){
				if(ds[i+j]=='?'||ds[i+j]==t[j]){
					
				}
				else{
					can = false;
					break loop;
				}
			}
			if(can){
				last = i;
				break loop2;
			}
		}
		
		if(last == -1){
			System.out.println("UNRESTORABLE");
		}
		else{
			for(int i=0;i<ds.length;i++){
				if(ds[i]=='?'){
					ds[i]='a';
				}
			}
			for(int i=0;i<t.length;i++){
				ds[i+last] = t[i];
			}
			
			for(int i=0;i<ds.length;i++){
				System.out.print(ds[i]);
			}
		}
	}
	
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}
	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}
	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}
	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 23124
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        mut a: [usize;n],
    }

    let mut ans = 0;

    for i in 1..n{
        if a[i] < a[i-1]{
            let dx = a[i-1] - a[i];
            a[i] += dx;
            ans += dx;
        }
    }

    println!("{}",ans);
}


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

int main() {
    int N, M; cin >> N >> M;
    vector<int> jouken(N+1, -1);
    for (int i = 0; i < M; i++) {
        int s, c; cin >> s >> c; s--;
        if (jouken[s] != -1 && jouken[s] != c) {
            cout << -1 << endl;
            return 0;
        } else {
            jouken[s] = c;
        }
    }
    for (int i = 0; i < 1000; i++) {
        bool ok = true;
        if (to_string(i).length() == N) {
            for (int j = 0; j < N; j++) {
                if (jouken[j] != -1 && jouken[j] != (to_string(i)[j] - '0')) ok = false;
            }
            if (ok) {
                cout << i << endl;
                return 0;
            }
        }
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cstdint>


int64_t const MOD = 1e9+7;
int const MAXN = 2e5;
int N;

template<int64_t Prime>
struct mod_int {
  int64_t v_;
  mod_int(int64_t x=0) : v_(x) { normalize(); }
  void normalize() { ((v_ %= Prime) += Prime) %= Prime; }
  mod_int operator+=(mod_int const& r){ (v_ += r.v_) %= Prime; return *this; }
  mod_int operator-=(mod_int const& r){ (v_ += Prime - r.v_) %= Prime; return *this; }
  mod_int operator*=(mod_int const& r){ (v_ *= r.v_) %= Prime; return *this; }
  mod_int operator+(mod_int const& r) { mod_int res(*this); return res += r; }
  mod_int operator-(mod_int const& r) { mod_int res(*this); return res -= r; }
  mod_int operator*(mod_int const& r) { mod_int res(*this); return res *= r; }
  mod_int pow(int x) const {
    int64_t res = 1, v = v_;
    while(x > 0) {
      if(x&1) (res *= v) %= Prime;
      x/=2; (v *= v) %= Prime;
    }
    return mod_int(res);
  }
  mod_int inv() const { return pow(Prime-2); }
  //operator int64_t() const { return v_; }
};
typedef mod_int<MOD> mint;

std::vector<int> G[MAXN];

int nc[MAXN];
mint dfs1(int v, int p) {
  int num = 1;
  mint res;
  for(auto c: G[v]) if(c != p) {
    res += dfs1(c, v);
    num += nc[c];
  }
  res += (mint(2).pow(num)-1)*(mint(2).pow(N - num)-1);
  nc[v] = num;
  return res;
}

int main() {
  std::cin >> N;
  for(int i = 0; i < N-1; ++i) {
    int A, B; std::cin >> A >> B; --A; --B;
    G[A].push_back(B);
    G[B].push_back(A);
  }
  mint ans = (dfs1(0, -1) - 1)*mint(2).pow(N).inv();
  ans -= mint(N)*mint(2).inv() - 1;
  std::cout << ans.v_ << std::endl;
  return 0;
}



Measured memory_bytes: 23040