akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <queue>
#include <set>

using namespace std;

typedef pair<string, int> P;

bool hantei (string a) {
	for (int i = 1; i < a.size(); i++) {
		if (a[0] == a[i]) {
		} else {
			return false;
		}
	}
	return true;
}

int main() {
	string a;
	string abc = "rgb";
	while (getline(cin, a)) {
		if (a[0] == '0') {
			break;
		}
		queue<P> q;
		q.push(P(a, 0));
		bool han = true;
		int t;
		set<string> s;
		if (hantei(a)) {
			han = false;
			cout << 0 << endl;
		}
		while (!q.empty()) {
			P p = q.front();
			q.pop();
			string pp = p.first;
			for (int i = 0; i < pp.size()-1; i++) {
				if (!han) {
					break;
				}
				if (pp[i] == pp[i+1]) {
				} else {
					string qq = pp;
					int v, w;
					for (int j = 0; j < abc.size(); j++) {
						if (abc[j] == pp[i]) {
							v = j;
						}
						if (abc[j] == pp[i+1]) {
							w = j;
						}
					}
					qq[i] = qq[i+1] = abc[3-(v+w)];
					if (hantei(qq)) {
						han = false;
						cout << p.second+1 << endl;
						break;
					}
					if (s.find(qq) == s.end()) {
						s.insert(qq);
						q.push(P(qq, p.second+1));
					}
				}
			}
		}
		if (han) {
			cout << "NA" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 2472
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
*$* WRITER:kakitamasziru/OxOmisosiru *$*
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#ifdef LOCAL_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
//#include <unordered_set> //unordered_set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
#include <bitset> // bitset
#define endl "\n";
using namespace std;

const long long INF = 100100100100100;
const int MOD = 1000000007;
const int inf = 1001001001;
typedef pair<int,int> P;

//Solve N^M. This, mod_pow use Iterative Square Method.
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}

int gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b ;
}



int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int A,B,C,K;cin >> A >> B >> C >> K;
    int sousa = 0;
    if(A >= B){
        for(int i = 0;i<7;i++){
            B *= 2;
            sousa++;
            if(B > A) break;
        }
    }
    if(B >= C){
        for(int i = 0;i<7;i++){
            C *= 2;
            sousa++;
            if(C > B)break;
        }
    }
    if(sousa <= K) {
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    
}

Measured memory_bytes: 3636
/* Dsingh_24 */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define ios	    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

#define N  100005

int main()
{
	ios
	ll n,i,j;
	cin>>n;
	vector<pii>ans;
	for(i=1;i<=n;i++){
		for(j=i+1;j<=n;j++){
			if(n%2){
				if(j==n-i)continue;
				ans.pb({i,j});
			}else{
				if(j==n-i+1)continue;
				ans.pb({i,j});
			}
		}
	}
	cout<<ans.size()<<"\n";
	for(auto i:ans)cout<<i.F<<" "<<i.S<<"\n";
	return 0;
}

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

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

int main(void) {
    string s;
    int ans = 0;

    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s;
    REP(i, s.length()) {
        if (s[i] == '1') {
            ans++;
        }
    }

    cout << ans << "\n";
    return 0;
}

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

int main() {
  int x, y;
  cin >> x >> y;
  vector<int> A{0,1,3,1,2,1,2,1,1,2,1,2,1};
  if (A.at(x)==A.at(y)) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using p = pair<ll, bool>;
using vp = vector<p>;

int main(){
    int n;
    cin >> n;
    vl a(n);
    for (int i = 0; i < n;i++){
        cin >> a[i];
    }
    ll sum1 = 0;
    ll num1 = 0;
    ll sum2 = 0;
    ll num2 = 0;
    for (int i = 0; i < n; i += 2)
    {
        if(a[i]>0){
            sum1 += a[i];
            num1++;
        }
    }
    for (int i = 1; i < n; i += 2)
    {
        if(a[i]>0){
            sum2 += a[i];
            num2++;
        }
    }
    if(sum1 ==0 && sum2 ==0){
        ll max = a[0];
        int k = 0;
        for (int i = 0; i < n; i++)
        {
            if(a[i] > max){
                max = a[i];
                k = i;
            }
        }
        cout << max << endl;
        cout << n - 1 << endl;
        for (int i = 0; i < k; i++)
        {
            cout << 1 << endl;
        }
        for (int i = 0; i < (n - k -1 );i++){
            cout << n-k-i << endl;
        }
        return 0;
    }
    vp b(n);
    for (int i = 0; i < n;i++)
    {
        b[i].first = a[i];
        b[i].second = false;
    }
    if (sum1 > sum2)
    {
        for (int i = 0; i < n; i += 2){
            if(a[i]>0){
                b[i].second = true;
            }
        }
    }
    else{
        for (int i = 1; i < n; i += 2){
            if(a[i]>0){
                b[i].second = true;
            }
        }
    }
    vi ans;
    while (b.size() > 1)
    {
        for (int i = 0; i < b.size();i++){
            if (i == 0 || i == b.size() - 1)
            {
                if(!b[i].second){
                    ans.push_back(i);
                    b.erase(i + b.begin());
                    break;
                }
            }
            else if(b[i-1].second && !b[i].second && b[i+1].second){
                ans.push_back(i);
                b.erase(i +1+ b.begin());
                b.erase(i + b.begin());
                break;
            }
            else if(!b[i-1].second && !b[i].second && !b[i+1].second){
                ans.push_back(i);
                b.erase(i +1+ b.begin());
                b.erase(i + b.begin());
                break;
            }
        }
    }
    cout << max(sum1, sum2) << endl;
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size();i++){
        cout << ans[i]+1 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{   int n,i=1,j=1,b[100001];
    cin>>n;int a[n];
    for(i=1;i<=n;i++)
     {cin>>a[i];
     b[a[i]]=i;}
     for(i=1;i<=n;i++){
        cout<<b[i]<<" ";
     } }


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50;
char s[N];

int main() {
	cin>>s;
    char cur = s[0];
  	if(s[1] == cur && s[2] == cur){
		cout<<"No"<<endl;
    }else {
    	cout<<"Yes"<<endl;
    }
    return 0;
}


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

int main()
{
    int n;

    cin >> n;


    string s, t;

    cin >> s >> t;


    string s1;


    for(int i=0; i<n; i++)
    {

        s1.push_back(s[i]);
        s1.push_back(t[i]);
    }

    cout << s1 << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int ans = getWays(n);
		System.out.println(ans);
	}

	static int getWays(int n) {
		return n*n*n;
	}

}


Measured memory_bytes: 21844
#include <iostream>
#include <string>

using namespace std;

int main() {
    string str;
    cin >> str;
    str += 'R';
    int size=str.length(), i, ans[size], tmp[2]={0}, flag=0, checkpoint=0;
    for(i=0; i<size; i++) {
        ans[i] = 0;
        if(str[i]=='R'){
            if(flag) {
                // cout << tmp[0] << ' ' << tmp[1] << ' ' << checkpoint << endl;
                if((tmp[0]+tmp[1])%2==0){
                    ans[checkpoint] = (tmp[0]+tmp[1])/2;
                    ans[checkpoint+1] = (tmp[0]+tmp[1])/2;
                } else if(tmp[0]<tmp[1]){
                    if((tmp[1]-1)%2) {
                        ans[checkpoint] = (tmp[0]+tmp[1])/2 + 1;
                        ans[checkpoint+1] = (tmp[0]+tmp[1])/2;
                    } else {
                        ans[checkpoint] = (tmp[0]+tmp[1])/2;
                        ans[checkpoint+1] = (tmp[0]+tmp[1])/2 + 1;
                    }
                } else {
                    if((tmp[0]-1)%2) {
                        ans[checkpoint] = (tmp[0]+tmp[1])/2;
                        ans[checkpoint+1] = (tmp[0]+tmp[1])/2 + 1;
                    } else {
                        ans[checkpoint] = (tmp[0]+tmp[1])/2 + 1;
                        ans[checkpoint+1] = (tmp[0]+tmp[1])/2;
                    }
                }
                tmp[0] = 1;
                tmp[1] = 0;
                flag = 0;
            } else {
                tmp[0] += 1;
            }
        } else {
            if(flag) {
                tmp[1] += 1;
            } else {
                checkpoint = i-1;
                flag = 1;
                tmp[1] += 1;
            }
        }
    }

    for(i=0; i<size-1; i++) {
        cout << ans[i] << ' ';
    }
    cout << endl;

    return 0;
    
}

Measured memory_bytes: 1152
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll MOD=1e9+7;
static const int MAX = 100;
static const int INF = (1<<23);
template<class T> T gcd(T a, T b){return b? gcd(b,a%b) : a;}
template<class T> T lcm(T a,T b){return a / gcd(a,b)*b;}

int main(){
     ll h,n;
     cin>>h>>n;

     vector<pair<ll,ll>> v;
     rep(i,n){
         ll a,b;
         cin>>a>>b;
         v.push_back({a,b});
     }
     ll dp[n+1][2*h+1];
     rep(i,n+1){
         rep(j,2*h+1){
             dp[i][j]=MOD;
         }
     }
     dp[0][0]=0;


     for(int i=0;i<n;i++){
         dp[i][0]=0;
         for(int j=0;j<=h;j++){
             dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
             if(j+v[i].first<=h){
                 ll ne =dp[i][j]+v[i].second;
                 ll ne2=dp[i+1][j]+v[i].second;
                 dp[i+1][j+v[i].first]=min({ne,dp[i][j+v[i].first],ne2});
             }else{
                 ll ne =dp[i][j]+v[i].second;
                 ll ne2=dp[i+1][j]+v[i].second;
                 dp[i+1][h]=min({ne,dp[i+1][h],ne2});
//                 if(j==8&&i==0){
//                     cout<<ne<<" "<<ne2<<" "<<endl;
//                     cout<<dp[i+1][h]<<endl;
//                 }
             }

         }
     }
//    rep(i,n+1){
//        rep(j,2*h){
//            cout<<dp[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    ll ans = dp[n][h];
//     for(ll i=h;i<=2*h;i++){
//         if(ans>dp[n][i])ans=dp[n][i];
//     }

     cout<<ans<<endl;





return 0;
}


Measured memory_bytes: 156672
#include<iostream>
#include<vector>
using namespace std;
int main(void){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int y,m,d;
		cin>>y>>m>>d;
		int ans;
		if(m%2==0&&y%3!=0){
			d=19-d;
		}else{
			d=20-d;
		}
		if(y%3==0){
			m=(10-m)*20;
		}else{
			m=((11-m)/2)*19+((10-m)/2)*20;
		}
		y=999-y;
		
		
		ans=((y+2)/3)*5+y*195+m+d+1;
		cout<<ans<<endl;
	}
	return 0;
}


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

using namespace std;

int main(){
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cout.setf(ios::fixed); cout.precision(17);
  int n;
  cin >> n;
  for(int i = n; ;i++){
    string s = to_string(i);
    set<char> z;
    for(int j = 0; j < s.size(); j++){
      z.insert(s[j]);
    }
    if(z.size() == 1){
      cout << s << "\n";
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
# ABC128 D
from collections import deque

N,K=map(int,input().split())
V=list(map(int,input().split()))
V=V[:]+V[:]
def check(k):
    res=0
    # 連続する k(K,K-1,...)個の宝石をとる
    # K-k個まで捨ててよい
    for i in range(k+1):
        if k<N:
            v=V[N-k+i:N-k+i+k]
        else:
            v=V[:N]
        v.sort(reverse=True)
        for i in range(K-k):
            if not v:
                break
            if v[-1]<0:
                v.pop()
            else:
                break
        res=max(res,sum(v))
        if not k<N:
            break
    return res

res=0
for k in range(min(N,K)+1):
    res=max(res,check(k))
print(res)

Measured memory_bytes: 73944
h = 0
w = 0
dataset = []

while True:
    h, w = map(int, input().split())
    if (h > 0 and h <= 300) and (w > 0 and w <= 300):
        listed = []
        listed.append(h)
        listed.append(w)
        dataset.append(listed)
    else:
        break

for listed in dataset:
    h = listed[0]
    w = listed[1]

    for i in range(h):
        for j in range(w):
            print("#", end="")
        print()
    print()

Measured memory_bytes: 9008
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>


int main() {
	int n; long long int a, b; std::cin >> n >> a >> b;
	std::vector<long long int> towns(n); for (auto& t : towns) std::cin >> t;
	long long int result = 0;
	for (auto i = 1; i < n; ++i) {
		result += std::min((towns[i] - towns[i - 1]) * a, b);
	}
	std::cout << result << std::endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n % 2 == 0) cout << n / 2 - 1 << endl;
    else cout << n / 2 << endl;

    return 0;
}

Measured memory_bytes: 256
N,M,K = map(int,input().split())
A = []

for y in range(1,N+1) :
    for x in range(1,M+1) :
        a = y*x + (N-y)*(M-x)
        A.append(a)
        A.append(N*M-a)
if K in A :
    print("Yes")
else :
    print("No")
#print(sorted(list(set(A))))

Measured memory_bytes: 82180
a = list(input().split())
stack = list()

num = 0
for i in a:
    if i.isdigit():
        stack.append(i)
        num += 1
        continue
    elif i == '+':
        ans = int(stack[num-2]) + int(stack[num-1])
    elif i == '-':
        ans = int(stack[num-2]) - int(stack[num-1])
    elif i == '*':
        ans = int(stack[num-2]) * int(stack[num-1])
    elif i == '/':
        ans = int(stack[num-2]) / int(stack[num-1])
    stack.pop()
    stack.pop()
    stack.append(ans)
    num -= 1

print(stack[0])



Measured memory_bytes: 5596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,a,b) for(int i=a;i<b;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
#define debug(x) cerr << x << endl
#define Complex complex<double>
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

int main() {
    int n;
    cin >> n;
    int dp[n]={};
    vector<pii> x(n);
    rep(i,n){
        int p,q;
        cin >> p >> q;
        x[i]=mp(p,q);
    }
    sort(all(x));
    int lasx=-mod;
    int del=0;
    rep(i,n){
        int len=x[i].F-lasx;
        if(len-x[i].S<0){
            del++;
            chmin(lasx,x[i].F+x[i].S);
        }
        else lasx=x[i].F+x[i].S;
    }
    cout << n-del;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
typedef long long ll;
cs int N = 1e5 + 50;
int n, q, fa[N], sz[N]; ll m;
int u[N], v[N], c;
int fnd(int x){ return x == fa[x] ? x : fa[x] = fnd(fa[x]); }
void mrg(int x, int y){
    x = fnd(x), y = fnd(y);
    if(x == y) return;
    fa[x] = y, sz[y] += sz[x];
}
int main(){
    #ifdef FSYolanda
    freopen("1.in","r",stdin);
    #endif
	scanf("%d%lld%d",&n,&m,&q);
    for(int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
    for(int i = 1, x, y, z; i <= q; i++){
        scanf("%d%d%d", &x, &y, &z); ++x, ++y;
        if(z == 0) mrg(x, y);
        else u[++c] = x, v[c] = y;
    } if(m == n - 1){
        if(c) return puts("No"), 0;
        else return puts("Yes"), 0;
    } 
    for(int i = 1; i <= c; i++){
        if(fnd(u[i]) == fnd(v[i])) 
        return puts("No"), 0;
    } ll lm = 0; int ct = 0;
    for(int i = 1; i <= n; i++)
    if(i == fnd(i)) lm += sz[i] - 1, ++ct;
    lm += 1ll * ct * (ct - 1) >> 1;
    if(m <= lm) puts("Yes");
    else puts("No"); return 0;
}


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

int main() {
  int N;
  cin >> N;
  
  int D, X;
  int A[N];
  cin >> D >> X;
  for (int i=0; i<N; i++) {
    cin >> A[i];
  }
  
  int count=0;
  for (int i=0; i<N; i++) {
    for (int j=0, k=0; j<D; j++) {
      if (j==k*A[i]) {
        count++;
        k++;
      }
    }
  }
  
  cout << count+X << endl;
  
  return 0;
}

Measured memory_bytes: 3612
n = gets.chomp.to_i
a_ary = gets.chomp.split(" ").map(&:to_i)
b_ary = gets.chomp.split(" ").map(&:to_i)
c_ary = gets.chomp.split(" ").map(&:to_i)
sum = b_ary.inject(:+)
a_ary.each.with_index do |a,i|
  next if i == 0
  if a == a_ary[i-1] +1
    ci = a-2
    ci = 0 if ci < 0
    sum += c_ary[ci]
  end
end
puts sum

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

Scanner sc= new Scanner(System.in);
int X =sc.nextInt();

int tho = X/500;
int A =X-500*tho;
int five = A/5;
  
int ans=tho*1000+five*5;

System.out.println(ans);
}
}

Measured memory_bytes: 21844
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(ReadLine());
        var L = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

        var sortedL = L.OrderByDescending(x => x).ToArray();
        var max = sortedL[0];
        var sumWithoutMax = sortedL[1..].Sum();
        var ans = (max < sumWithoutMax) ? "Yes" : "No";

        WriteLine(ans);
    }
}


Measured memory_bytes: 28452
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);++(i))
#define REP1(i,n) for((i)=1;(i)<=(int)(n);++(i))

int main() {
    //clock_t start = clock();
    ios::sync_with_stdio(false); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    char a, b; cin >> a >> b;
    if ((a == 'H' && b == 'H') || (a == 'D' && b == 'D')) {
    	cout << 'H' << endl;
    } else {
    	cout << 'D' << endl;
    }
    //clock_t stop = clock();
    //cout << (double)(stop-start)/CLOCKS_PER_SEC << " (s)" << endl;
    return 0;
}


Measured memory_bytes: 256
let m = 1000000007
let ( +^ ) x y = (x + y) mod m
let ( *^ ) x y = (x * y) mod m

let () =
  let l = read_line () in
  let dp = Array.make_matrix (String.length l + 1) 2 0 in
  dp.(0).(0) <- 1;
  for i = 0 to String.length l - 1 do
    match l.[i] with
    | '0' ->
        dp.(i + 1).(0) <- dp.(i).(0);
        dp.(i + 1).(1) <- 3 *^ dp.(i).(1)
    | '1' ->
        dp.(i + 1).(0) <- 2 *^ dp.(i).(0);
        dp.(i + 1).(1) <- 3 *^ dp.(i).(1) +^ dp.(i).(0)
  done;
  Printf.printf "%d\n" @@ Array.fold_left ( +^ ) 0 dp.(String.length l)


Measured memory_bytes: 7168
#include<stdio.h>

int main()
{
	int h[1000];
	int w[1000];
	int num=0;
	int i,j,k;
	
	//input
	while(1){
		scanf("%d %d",&h[num],&w[num]);
	//	printf("%d %d\n",h[num],w[num]);
		if(h[num]==0&&w[num]==0) break;
		num++;		
	}
	
	
	//output
	for(i=0;i<num;i++){
		for(j=0;j<h[i];j++){
			for(k=0;k<w[i];k++)
				printf("#");
			printf("\n");
		}
		printf("\n");
	}
	
	return 0;
}


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


signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);

    int n,m;
    while(cin>>n>>m){
        if(n==0) break;
        int h[n+1]={},w[m+1]={};
        int now=0;

        for(int i=1;i<=n;i++){
            cin>>h[i];
            int t=h[i];
            h[i]+=now;
            now+=t;
        }
        now=0;
        for(int i=1;i<=m;i++){
            cin>>w[i];
            int t=w[i];
            w[i]+=now;
            now+=t;
        }
        int ans=0;
        n++,m++;
        map<int,int> mp;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                mp[h[j]-h[i]]++;
            }
        }
        for(int i=0;i<m;i++){
            for(int j=i+1;j<m;j++){
                ans+=mp[w[j]-w[i]];
            }
        }
        cout<<ans<<endl;
    }

}


Measured memory_bytes: 21004
fun main(args: Array<String>) {
    val (h, w) = readIntegerList()
    var costMatrix = Array(10) { readLongList().toMutableList() }
    warshallFloyd(costMatrix)
    val aMtrix = Array(h) { readIntegerList() }
    var ans = 0L
    for (row in aMtrix) {
        for (i in row) {
            if (i != -1) {
                ans += costMatrix[i][1]
            }
        }
    }
    println(ans)
}

/** O((costMatrix.size)^3) costMatrix is changed */
fun warshallFloyd(costMatrix: Array<MutableList<Long>>): Array<MutableList<Long>> {
    val indices = costMatrix.indices
    for (k in indices) {
        for (i in indices) {
            for (j in indices) {
                if (costMatrix[i][k] != Long.MAX_VALUE && costMatrix[k][j] != Long.MAX_VALUE) {
                    costMatrix[i][j] = Math.min(costMatrix[i][j], costMatrix[i][k] + costMatrix[k][j])
                }
            }
        }
    }
    return costMatrix
}


fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)


Measured memory_bytes: 41628
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<int> si;
typedef map<string, int> msi;
typedef greater<int> gt;
typedef priority_queue<int, vector<int>, gt> minq;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int main() {
  int N; cin>>N;
  msi mp;
  rep(i,N) {
    string s; cin >>s;
    mp[s]++;
  }
  cout << mp.size() << endl;
  return 0;
}

Measured memory_bytes: 19220
#include <bits/stdc++.h>
#define rep(i, n) for(int i= 0; i < (n); i++)
using ll= long long int;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll mod= 1e9 + 7;



int main(){
  ll a;
  cin >> a;
  cout << a+a*a+a*a*a << endl;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};


bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  ll from=0,unti=0,N,T,t[200002],res=0;
  cin >> N >> T;
  REP(i,N)cin >> t[i];
  t[N] = 9999999999999999;
  REP(i,N+1){
    if(unti < t[i]){
      res += unti - from;
      unti = t[i]+ T;
      from = t[i];
    }else{
      unti = t[i]+T;
    }
  }
  cout << res << endl;
  
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

ll bpow(ll a, ll n,ll mod){
  int i = 0;
  ll res=1;
  while(n){
    if(n & 1)
      res = (res*a) % mod;
    a = (a*a) % mod;
    n >>= 1;
  }
  return res;
}
const int MOD = 1000000007;
mat mul(mat &A, mat &B){
  mat C(A.size(),vec(B[0].size()));
    REP(i,A.size())REP(k,B.size())REP(j,B[0].size()){
    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  }
  return C;
}

mat pow(mat A,ll n)
{
  mat B(A.size(),vec(A.size()));
  REP(i,A.size()){
    B[i][i] = 1;
  }
  while(n > 0){
    if ( n & 1) B = mul(B,A);
    A = mul(A,A);
    n >>= 1;
  }
  return B;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int n,a[2*maxn],ans;
int main(){
	scanf("%d",&n); n*=2;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	ans=0;
	for (int s=1;s<=n;s++){
		int now=0;
		for (int i=s;i<=n+s;i+=2) now+=min(a[i+1],a[i]);
		ans=max(ans,now);
		a[n+s]=a[s];
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
const int maxn=3e6+7;
struct node{
    int l,r,s;
}pre[maxn];
int n,k,mx,a[maxn];
void build(int k,int l,int r);
void update(int v,int k,int l,int r);
int query(int k,int l,int r);
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        mx=max(mx,a[i]);
    }
    build(1,0,mx);
    int now=0,ans=0;
    for(int i=1;i<=n;i++){
        now=query(1,max(0,a[i]-k),min(mx,a[i]+k))+1;
        ans=max(ans,now);
        update(now,1,a[i],a[i]);
    }
    printf("%d\n",ans);
}

void build(int k,int l,int r){
    pre[k].l=l,pre[k].r=r,pre[k].s=0;
    if(l>=r) return;
    build(k*2,l,(l+r)/2);
    build(k*2+1,(l+r)/2+1,r);
}

void update(int v,int k,int l,int r){
    if(l<=pre[k].l&&pre[k].r<=r){
        pre[k].s=v;
        return;
    }
    int mid=(pre[k].l+pre[k].r)/2;
    if(l<=mid) update(v,k*2,l,r);
    else update(v,k*2+1,l,r);
    pre[k].s=max(pre[k*2].s,pre[k*2+1].s);
}

int query(int k,int l,int r){
    if(l<=pre[k].l&&pre[k].r<=r){
        return pre[k].s;
    }
    int mid=(pre[k].l+pre[k].r)/2;
    int ans1=0,ans2=0;
    if(l<=mid) ans1=query(k*2,l,r);
    if(mid+1<=r) ans2=query(k*2+1,l,r);
    return max(ans1,ans2);
}



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

using namespace std;

int main(void) {
    long h, w, a, b;
    cin >> h >> w >> a >> b;

    if(!(2*a < w && 2*b < h)) {
        cout << "No" << endl;
        return 0;
    }

    for(int j=0; j<h; j++, cout << endl)
        for(int i=0; i<w; i++)
            cout << (char)('0' + ((i < a) ^ (j < b)));
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
typedef long long ll;
using namespace std;
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
int main(void){
    string l;cin>>l;
    mint dp[2][l.size()+1];
    rep(i,2)rep(j,l.size()+1) dp[i][j]=(mint)0;
    dp[0][0]=1;
    dp[1][0]=0;
    rep(i,l.size()){
        char now=l[i];
        if(now=='1'){
            dp[0][i+1]+=dp[0][i]*2;//{a,b}={1,0},{0,1}
            dp[1][i+1]+=dp[0][i];//{a,b}={0,0}
        }else{
            dp[0][i+1]+=dp[0][i];//{a,b}={0,0}
        }
        dp[1][i+1]+=dp[1][i]*3;//{a,b}={0,0},{1,0},{0,1}
    }
    mint res=dp[0][l.size()]+dp[1][l.size()];
    
    cout<<res.x<<endl;
}

Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll maxn = 2e6 + 5;
const ll maxm = 1e3 + 5;
const ll mod = 1e9 + 7;
namespace IO{
    const int SIZE = (1 << 20) + 1;
    char ibuf[SIZE], *iS, *iT, obuf[SIZE],*oS = obuf, *oT = obuf + SIZE - 1;
    char _st[55];
    int _qr = 0;
    inline char gc(){
        return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++) : *iS++);
    }
    inline void qread(){}
    template<class T1, class ...T2>
    inline void qread(T1 &IEE, T2&... ls){
        register T1 __ = 0, ___ = 1;
        register char ch;
        while(!isdigit(ch = gc())) ___ = (ch == '-') ? -___ : ___;
        do{
            __ = (__ << 1) + (__ << 3) + (ch ^ 48);
        }while(isdigit(ch = gc()));
        __ *= ___;
        IEE = __;
        qread(ls...);
        return ;
    }
    inline void flush(){
        fwrite(obuf, 1, oS - obuf, stdout);
        oS = obuf;
        return ;
    }
    inline void putc_(char _x){
        *oS++ = _x;
        if(oS == oT) flush();
    }
    inline void qwrite(){}
    template<class T1, class ...T2>
    inline void qwrite(T1 IEE, T2... ls){
        if(!IEE) putc_('0');
        if(IEE < 0) putc_('-'), IEE = -IEE;
        while(IEE) _st[++_qr] = IEE % 10 + '0', IEE /= 10;
        while(_qr) putc_(_st[_qr--]);
        qwrite(ls...);
        return ;
    }
    struct Flusher_{~Flusher_(){flush();}}io_flusher;
}
using namespace IO;
ll ans, k;
char ch[maxn];
ll inv[maxn], md[maxn];
ll qpow(ll x, ll y){
    ll res = 1;
    while(y){
        if(y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
void init(){
    inv[0] = 1;
    md[0] = 1;
    for(ll i = 1;i <= 2000000;i++){
        inv[i] = inv[i - 1] * qpow(i, mod - 2) % mod;
        md[i] = md[i - 1] * i % mod;
    }
    return ;
}
ll C(ll n, ll m){
    if(n == 0) return 1;
    if(m == 0) return 1;
    return inv[n - m] * md[n] % mod * inv[m] % mod;
}
int main(){
    init();
    cin >> k;
    cin >> (ch + 1);
    ll l = strlen(ch + 1);
    for(ll i = 0;i <= k;i++){
        ll p = k - i;
        // cout << qpow(26, i) << endl;
        ans += qpow(26, i) * C(l + p - 1, l - 1) % mod * qpow(25, p) % mod;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 35832
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <ctype.h>
#include <map>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <cctype>
#include <queue>
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define REP1(j,n) for(int j=0;j<(int)n;++j)
#define REPD(i,n) for(int i=n;i>=0;--i)
#define REPD1(j,n) for(int j=n;j=>0;--j)
#define REPS(i,n) for(int i=1;i<=(int)n;++i)
#define REPS1(j,n) for(int j=1;j<=(int)n;++j)
#define rep(i,a,n) for(int i=a;i<=(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;

int divisor(int x) {
	int cnt = 0;
	for (int i = 1; i <= x; ++i) {
		if (x%i == 0)cnt++;
	}
	return cnt;
}
int main(void) {
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i +=2) {
		if (divisor(i) == 8) ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		string a, b;
		cin >> a >> b;
		if(a.size() < b.size()) swap(a, b);
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());
		string ans;
		bool carryover = false;
		for(int j = 0; j < b.size(); j++){
			int num;
			if(carryover) num = (a[j] - '0') + (b[j] - '0') + 1;
			else num = (a[j] - '0') + (b[j] - '0');
			if(num >= 10) carryover = true;
			else carryover = false;
			ans.push_back(num % 10 + '0');
		}
		for(int j = b.size(); j < a.size(); j++){
			int num;
			if(carryover) num = (a[j] - '0') + 1;
			else num = (a[j] - '0');
			if(num >= 10) carryover = true;
			else carryover = false;
			ans.push_back(num % 10 + '0');
		}
		if(carryover) ans.push_back('1');
		reverse(ans.begin(), ans.end());
		if(ans.size() > 80) cout << "overflow" << endl;
		else cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3152
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.container;
import std.datetime;

void main()
{
	while (1) {
		auto x = readln.chomp.split.map!(to!int);
		if (!x[0]) break;
		auto m = x[1], a = x[2];
		auto lines = new int[][](m, 3);
		foreach (i; 0..m) {
			lines[i] = readln.chomp.split.map!(to!int).array;
		}
		lines = lines.sort!("a[0] > b[0]").array;
		int h;
		foreach (e; lines) {
			if (e[1] == a) {
				a = e[2];
			} else if (e[2] == a) {
				a = e[1];
			}
		}
		a.writeln;
	}
}

Measured memory_bytes: 2396
#include <iostream>
#include <string>
#define int long long

using namespace std;

int N;

signed main()
{
    cin >> N;
    string ans = "";
    while (1)
    {
        // cout << N % 26LL << endl;
        if (N % 26 == 0)
        {
            ans = "z" + ans;
            N--;
        }
        else
        {
            ans = (char)('a' + (N % 26 - 1)) + ans;
        }
        N /= 26LL;
        if (N == 0LL)
            break;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3100
A, B, N = map(int, input().split())

def floor(x):
    out = (A * x)//B - A * (x//B)
    return out

max = 0
#for i in range(N//2, N + 1):
    #if(floor(i) > max):
        #max = floor(i)

if(N < (B-1)):
    max = floor(N)
else:
    max = floor(B-1)

print(max)



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

int main() {
  int n;cin>>n;
  vector<string> s(3);
  rep(i,3)cin>>s[i];
  int ans=0;
  rep(i,n){
    set<char> st;
    rep(j,3){
      st.insert(s[j][i]);
    }
    ans+=st.size()-1;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3612
import numpy as np
import math
from collections import Counter

def cumsum(x):
    return list(np.cumsum(x))

def cumsum_number(N,K,x):
    ans=[0]*(N-K+1)
    number_cumsum = cumsum(x)
    number_cumsum.insert(0,0)
    for i in range(N-K+1):
        ans[i]=number_cumsum[i+K]-number_cumsum[i]
    return ans
"""
int #整数
float #小数

#リスト
list0 = [] #リスト生成
list0 = [1,2,3,4] #初期化
list0 = [0]*10 #[0,0,0,0,0,0,0,0,0,0]
list1= [i for i in range(10)] #>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
list1 = list(map(int, input().split()))　# 複数の入力をリストに入れる
number=[int(input()) for i in range(int(input()))] #複数行の入力をリストに
list1 = list1 + [6, 7, 8] #リストの追加
list2.append(34) #リストの追加　最後に（）内が足される
list.insert(3,10) #リストの追加　任意の位置（追加したい位置,追加したい値）
len(list4) #リストの要素数
max(sa) #list saの最小値
list5.count(2) #リスト(文字列も可）内の2の数
list1.sort() #並び替え小さい順
list1.sort(reverse=True)  #並び替え大きい順
set(list1) #list1内の重複している要素を削除し、小さい順に並べる
sum([2,3,   ,3]) #リストの合計

number=Counter(list) #listを値（文字）ごとにカウントし辞書型で返す [1:4,2:5 …]

abs(a) #aの絶対値
max(a,b) min(a,b) #最大値　最小値
text1 = text1.replace("34","test") #text1内の"34"を"test"に書き換える(文字列内の文字を入れ替える)
sorted(S) #Sを辞書順にソート
exit(0) #強制終了

cumsum(リスト) #累積和をリストで返す
cumsum_number(N,K,x) #N個の数が含まれるリストx内のK個からなる部分和をリストで返す

alphabet={0:"A",1:"B",2:"C",3:"D",4:"E",5:"F",6:"G",7:"H",8:"I",9:"J",
          10:"K",11:"L",12:"M",13:"N",14:"O",15:"P",16:"Q",17:"R",18:"S",19:"T",
          20:"U",21:"V",22:"W",23:"X",24:"Y",25:"Z",}
print(*S,sep="") #リストSを1つずつ出力

math.floor() #切り捨て
math.ceil() #切り上げ
"""
def dist(a,b):
    res = 0
    for i in range(D):
        res += (a[i]-b[i])**2
    res = res**0.5
    return res

N,D=map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
ans = 0

for i in range(N-1):
    for j in range(i+1,N):
        if dist(X[i],X[j]).is_integer():
            ans+=1
print(ans)






Measured memory_bytes: 26940
#include <iostream>
#include<algorithm>
#include<set>
#include<queue>
#include<bitset>
#define rep(i,j,n) for(int i=j;i<n;i++)
using namespace std;
#define int long long
struct edge{long long to,cost;};
typedef pair<int,int>P;
#define inf 1000000007
string alph("abcdefghijklmnopqrstuvwxyz");
vector<int>es[214514];
signed main(){
    int n;cin>>n;
    int hei[114514];
    rep(i,0,n)hei[i]=inf;
    int a[114514];
    int t[114514];
    rep(i,0,n){
        cin>>a[i];
        if(!i||a[i]>a[i-1])hei[i]=a[i];
    }
    int he[114514];rep(i,0,n)he[i]=inf;
    rep(i,0,n)cin>>t[i];
    for(int i=n-1;i>=0;i--){
        if(i==n-1||t[i]>t[i+1])he[i]=t[i];
    }
    rep(i,0,n){
        if(he[i]!=inf&&hei[i]!=inf&&he[i]!=hei[i]){
            cout<<0<<endl;
            return 0;
        }
        else if(he[i]!=hei[i]){
            hei[i]=min(hei[i],he[i]);
        }
    }
    rep(i,0,n)if((a[i]<hei[i]||t[i]<hei[i])&&hei[i]!=inf){
        cout<<0<<endl;return 0;
    }
    int ans=1;
    rep(i,0,n){
        if(hei[i]==inf){
            ans*=min(a[i],t[i]);
            ans%=inf;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

string mul_by_2(string s) {
    char c[30];
    int j = 0;
    int tmp;
    int carry = 0;
    int len = (int)s.length();
    for (int i = len - 1;i > -1;i--) {
        tmp = (s[i] - '0') * 2 + carry;
        c[j++] = tmp % 10+'0';
        carry = tmp / 10;
    }
    if (carry > 0) {
        c[j++] = carry + '0';
    }
    c[j] = '\0';
    string t(c);
    reverse(t.begin(), t.end());
    return t;
}
int main() {
    string x, y;
    cin >> x >> y;
    int cnt = 1;
    int y_len = (int)y.length();
    x=mul_by_2(x);
    while ((x.length()<y_len)|| (x.length()==y_len &&  x.compare(y)<=0)  ) {
        cnt++;
        x = mul_by_2(x);
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 2000000000
#define MOD 1000000007
#define N 3005
#define M 1442255
#define LOG 1000000
#define KOK 31623
#define EPS 0.000000001
using namespace std;

int n,q,ans,tot,x[N],y[N],a[N],dp1[N][N],dp2[N][N],po[N],cur[N][N];

void up(int a,int b) {

	dp1[a][b]=1ll*dp1[a][b]*po[tot-cur[a][b]-1]%MOD;
	dp2[a][b]=1ll*dp2[a][b]*po[tot-cur[a][b]-1]%MOD;

	cur[a][b]=tot;

}

int main() {

	//freopen("input.txt","r",stdin);

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

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	for(int i=1;i<=q;i++) scanf("%d %d",x+i,y+i);

	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) dp1[i][j]=1;

	po[0]=1;

	for(int i=1;i<=q+3;i++) po[i]=po[i-1]*2%MOD;

	tot=1;

	for(int t=q;t>=1;t--,tot++) {

		if(x[t]>y[t]) swap(x[t],y[t]);

		for(int i=1;i<=n;i++) {

			if(i<x[t]) {

				up(i,x[t]);
				up(i,y[t]);

				int t1=dp1[i][x[t]];
				int t2=dp2[i][x[t]];

				dp1[i][x[t]]=(dp1[i][x[t]]+dp1[i][y[t]])%MOD;
				dp2[i][x[t]]=(dp2[i][x[t]]+dp2[i][y[t]])%MOD;

				dp1[i][y[t]]=(dp1[i][y[t]]+t1)%MOD;
				dp2[i][y[t]]=(dp2[i][y[t]]+t2)%MOD;

			}
			else if(i>y[t]) {

				up(x[t],i);
				up(y[t],i);

				int t1=dp1[x[t]][i];
				int t2=dp2[x[t]][i];

				dp1[x[t]][i]=(dp1[x[t]][i]+dp1[y[t]][i])%MOD;
				dp2[x[t]][i]=(dp2[x[t]][i]+dp2[y[t]][i])%MOD;

				dp1[y[t]][i]=(dp1[y[t]][i]+t1)%MOD;
				dp2[y[t]][i]=(dp2[y[t]][i]+t2)%MOD;

			}
			else if(i==x[t]) {

				up(x[t],y[t]);

				int t1=dp1[i][y[t]];

				dp1[i][y[t]]=(dp1[i][y[t]]+dp2[i][y[t]])%MOD;
				dp2[i][y[t]]=(dp2[i][y[t]]+t1)%MOD;

			}
			else if(i<y[t]) {

				up(x[t],i);
				up(i,y[t]);

				int t1=dp2[x[t]][i];
				int t2=dp1[x[t]][i];

				dp1[x[t]][i]=(dp1[x[t]][i]+dp2[i][y[t]])%MOD;
				dp2[x[t]][i]=(dp2[x[t]][i]+dp1[i][y[t]])%MOD;

				dp1[i][y[t]]=(dp1[i][y[t]]+t1)%MOD;
				dp2[i][y[t]]=(dp2[i][y[t]]+t2)%MOD;

			}

		}

	}

	for(int i=1;i<=n;i++) {

		for(int j=i+1;j<=n;j++) {

			dp1[i][j]=1ll*dp1[i][j]*po[tot-cur[i][j]-1]%MOD;
			dp2[i][j]=1ll*dp2[i][j]*po[tot-cur[i][j]-1]%MOD;

			if(a[i]>a[j]) {

				ans=(ans+dp1[i][j])%MOD;

			}
			else if(a[i]<a[j]) {

				ans=(ans+dp2[i][j])%MOD;

			}

			assert((dp1[i][j]+dp2[i][j])%MOD == po[q]);

		}

	} 

	printf("%d",ans);

}


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

int main(){
  string S;
  cin>>S;
  int count=0;
  for(int i=0; i<S.size(); i++){
    if(i%2==0&&(S.at(i)=='R'||S.at(i)=='U'||S.at(i)=='D')){
      count++;
    }
    else if(i%2!=0&&(S.at(i)=='L'||S.at(i)=='U'||S.at(i)=='D')){
      count++;
    }
  }
  cout<<(count==S.size()?"Yes":"No")<<endl;
}

Measured memory_bytes: 3620
MOD = 10 ** 9 + 7
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
dp = [[0] * n for _ in range(2)]
s = [0]
d = [-1] * n
while s:
    p = s.pop()
    if d[p] == -1:
        d[p] = 0
        s.append(p)
        for node in g[p]:
            if d[node] == -1:
                s.append(node)
    else:
        d[p] = 1
        b = 1
        w = 1
        for node in g[p]:
            if d[node] == 1:
                b *= dp[0][node]
                w *= dp[0][node] + dp[1][node]
        dp[0][p] = w % MOD
        dp[1][p] = b % MOD
print((dp[0][0] + dp[1][0]) % MOD)


Measured memory_bytes: 76192
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int sx = sc.nextInt();
		int sy = sc.nextInt();
		int tx = sc.nextInt();
		int ty = sc.nextInt();

		int dx = Math.abs(sx-tx);
		int dy = Math.abs(sy-ty);

		StringBuilder sb = new StringBuilder();

		for(int i=0; i<dy; i++){
			sb.append("U");
		}
		for(int i=0; i<dx; i++){
			sb.append("R");
		}

		for(int i=0; i<dy; i++){
			sb.append("D");
		}
		for(int i=0; i<dx; i++){
			sb.append("L");
		}

		sb.append("L");
		for(int i=0; i<dy+1; i++){
			sb.append("U");
		}
		for(int i=0; i<dx+1; i++){
			sb.append("R");
		}
		sb.append("D");

		sb.append("R");
		for(int i=0; i<dy+1; i++){
			sb.append("D");
		}
		for(int i=0; i<dx+1; i++){
			sb.append("L");
		}
		sb.append("U");

		//Strint str = new String(sb);
		System.out.println(new String(sb));
	}
}

Measured memory_bytes: 10068
import sys,math,itertools,bisect,copy,re

from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint
# 10倍速いらしい
input = sys.stdin.readline

INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

N = int(input())
A = [int(x) for x in input().strip().split()]

m = 0
for a in A:
    m += 1/a
print(1/m)


Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
int dp[N][N], px[N][N], py[N][N];

int main() {
  ios::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);

  string s, t;
  cin >> s >> t;
  
  int n = s.size(), m = t.size();
  memset(dp, 0, sizeof dp);
  memset(px, -1, sizeof px);
  memset(py, -1, sizeof py);

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (s[i-1] == t[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
      else {
        if (dp[i - 1][j] > dp[i][j-1]) px[i][j] = 1, py[i][j] = 0;
        else {
          px[i][j] = 0, py[i][j] = 1;
        }
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }
  
  string ans;
  while (n && m) {
    if (px[n][m] == -1) ans += s[n-1], --n, --m;
    else {
      int nn = px[n][m];
      int mm = py[n][m];
      n -= nn;
      m -= mm;
    }
  }
  
  reverse(ans.begin(), ans.end());
  cout << ans << '\n';
}


Measured memory_bytes: 109496
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int n, m;
int dist[14348907];
int num[17];

int max_cup(int state, int tray){
	// debug(tray);
	for(int i = n; i >= 1; i--){
		if(state / num[i-1] == tray) return i;
		state %= num[i-1];
	}

	return 0;
}

int main(void){
	num[0] = 1;
	for(int i = 1; i <= 16; i++){
		num[i] = num[i-1] * 3;
	}

	while(true){
		int state = 0;
		cin >> n >> m;
		if(n == 0 and m == 0) break;
		for(int i = 0; i < 3; i++){
			int k;
			cin >> k;
			for(int j = 0; j < k; j++){
				int x;
				cin >> x;
				state += i * num[x-1];
			}
		}

		for(int i = 0; i < num[n]; i++) dist[i] = INF;

		queue<int> que;
		que.push(state);
		dist[state] = 0;
		while(not que.empty()){
			int s = que.front();
			que.pop();
			// debug(s);
			if(dist[s] > m) break;

			int M[3];
			for(int i = 0; i < 3; i++){
				M[i] = max_cup(s, i);
				// debug(M[i]);
			}

			if(M[0] < M[1]){
				// debug("a");
				int ns = s - num[M[1]-1];
				if(dist[ns] == INF){
					dist[ns] = dist[s] + 1;
					que.push(ns);
				}
			}else{
				// debug("b");
				int ns = s + num[M[0]-1];
				if(dist[ns] == INF){
					dist[ns] = dist[s] + 1;
					que.push(ns);
				}
			}

			// debug("tes");

			if(M[1] < M[2]){
				// debug("c");
				int ns = s - num[M[2]-1];
				if(dist[ns] == INF){
					dist[ns] = dist[s] + 1;
					que.push(ns);
				}
			}else{
				// debug("d");
				int ns = s + num[M[1]-1];
				if(dist[ns] == INF){
					dist[ns] = dist[s] + 1;
					que.push(ns);
				}
			}
		}

		int res = -1;
		if(min(dist[0], dist[num[n] - 1]) <= m) res = min(dist[0], dist[num[n] - 1]);

		cout << res << '\n';
	}
	return 0;
}


Measured memory_bytes: 59120