akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

ll s2l(string s) {
  int pi = s.size();
  rep(i, s.size()) if (s[i] == '.') pi = i;
  ll res = 0;
  rep(i, pi) res = 10 * res + (ll)(s[i] - '0');
  rep(i, 9) {
    res *= 10;
    if (pi+i+1 < s.size()) res += (ll)(s[pi+i+1] - '0');
  }
  return res;
}

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) {
    string s;
    cin >> s;
    a[i] = s2l(s);
  }
  // rep(i, n) cout << a[i] << endl;

  vector<vector<ll>> fact(19, vector<ll>(19, 0));
  rep(ai, n) {
    int i = 0, j = 0;
    while (a[ai] % 2 == 0 && i < 18) {
      a[ai] /= 2;
      ++i;
    }
    while (a[ai] % 5 == 0 && j < 18) {
      a[ai] /= 5;
      ++j;
    }
    ++fact[i][j];
  }

  // rep(i, 19) {
  //   rep(j, 19) printf("%d ", fact[i][j]);
  //   printf("\n");
  // }

  ll ans = 0;
  rep(i1, 19) rep(j1, 19) rep(i2, 19) rep(j2, 19) {
    if (19*i1+j1 > 19*i2+j2) continue;
    if (i1 + i2 < 18 || j1 + j2 < 18) continue;
    // ll ans0 = ans;
    if (i1 == i2 && j1 == j2) ans += fact[i1][j1] * (fact[i2][j2] - 1) / 2;
    else ans += fact[i1][j1] * fact[i2][j2];
    // if (ans0 != ans) printf("%d %d %d %d, %lld, %lld\n", i1, j1, i2, j2, ans0, ans);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4852
n, m, c = gets.split(" ").map(&:to_i)
ary_b = gets.split(" ").map(&:to_i)

ary = []
n.times do
  ary << gets.split(" ").map(&:to_i)
end

clu = 0
ac = 0

ary.each do |x|
    m.times do |i|
        clu += x[i] * ary_b[i]
    end
    if clu + c > 0
        ac += 1
    end
    clu = 0
end

puts ac

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n, k;
    cin >> n >> k;
    int ans = 0;
    while (n > 0) {
        n /= k;
        ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
module mod1
integer(8) :: time
end module mod1


program aaa
use mod1
implicit none
integer(8) :: tt(100)=0
integer :: i,j,k,n

read(*,*) n
do i=1,n
	read(*,*) tt(i)
enddo

time = tt(1)


if(n>=2) then
	do i=2,n
		call saishou(time,tt(i))
	enddo
endif

write(*,*) time


contains
	subroutine saishou(x,y)

		implicit none
		integer(8) :: x,y,x0,y0,r,tmp,koubai
	
		x0 = x
		y0 = y
		
		if(x < y) then
			tmp = x
			x = y
			y = tmp 
		endif

		r = mod(x,y)

		do while (r .ne. 0) 
			x = y
			y = r
			r = mod(x,y)
		enddo
		
		time = x0 / y * y0

	end subroutine
	
end program

Measured memory_bytes: 896
/*****************
 *   I<3   C++   *
 *  IWANT ANYAC  *
 * ILOVEPROGRAM! *
 *IT'SINTERESTING*
 * ILOVEPROGRAM! *
 *  INCONTESTS   *
 *   GETSCORE    *
 *    ACCODE     *
 *     LETS      *
 *      GO       *
 *****************/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define LL long long
#define pb push_back
#define pob pop_back
#define mp make_pair
#define FILL(a,v) memset((void*)a,v,sizeof(a))
#define FILL0(a) FILL(a,0)
#define FILL1(a) FILL(a,-1)
#define ALL(a) (a).begin(),(a).end()
#define Inf 1e9
#define Mod 1000000007
#define foreach(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define FOR(i,x) for(int i=0;i<x;i++)
#define RFOR(i,x) for(int i=x-1;i>=0;i--)
#define FFOR(i,a,b) for(int i=a;i<b;i++)
#define FRFOR(i,a,b) for(int i=a-1;i>=b;i--)
#define SZ(a) ((int)(a).size())
#define FI first
#define SE second
#define OVER(a) return puts(a),0
#define fastio ios::sync_with_stdio(0)
#define filei(f) freopen(f,"r",stdin)
#define fileo(f) freopen(f,"w",stdout)
#define MASK(a) (1<<(a))
#define MASKX(x,a) ((x)<<(a))
#define BIT(a,b) ((a>>b)&1)
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long UINT;
typedef unsigned int Uint;
typedef long long INT;
typedef pair<INT,INT> PII;
typedef stringstream sst;
typedef istringstream iss;
typedef vector<int> vint;
typedef vector<INT> VINT;
typedef vector<pii> vpii;
typedef vector<PII> VPII;
typedef priority_queue<int> pqi;
typedef priority_queue<INT> PQI;
typedef priority_queue<pii> pqp;
typedef priority_queue<PII> PQP;
typedef priority_queue<int,vint,greater<int> > xqi;
typedef priority_queue<INT,VINT,greater<INT> > XQI;
typedef priority_queue<pii,vpii,greater<pii> > xqp;
typedef priority_queue<PII,VPII,greater<PII> > XQP;

int n,fromst;
vector<int> jian,nei[100007];
int dis[100007],cnt[100007];

int dfs(int la,int a)
{
	int cn=1;
	jian.push_back(a);
	if(a==n-1)fromst=jian[(SZ(jian)+1)/2];
	for(int i=0;i<SZ(nei[a]);i++)
		if(nei[a][i]!=la)
			cn+=dfs(a,nei[a][i]),dis[nei[a][i]]=dis[a]+1;
	jian.pop_back();
	cnt[a]=cn;
	return cn;
}

int a,b;

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n-1;i++)
	{
		scanf("%d%d",&a,&b);
		nei[a-1].push_back(b-1);
		nei[b-1].push_back(a-1);
	}
	dfs(-1,0);
	string mark;
	if(cnt[fromst]>=(n+1)/2)mark="Snuke";
	else mark="Fennec";
	cout<<mark<<endl;
	return 0;
}

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

int main() {
	ll	N;
	cin >> N;
	ll	happy;	
	happy = 0;
	happy += (N / 500) * 1000;
	N %= 500;
	happy += (N / 5) * 5;
	cout << happy << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define BUF (200005)

int N,M;
int D[BUF];
int T[BUF];
void input(void){
	cin >> N;
	for(int i=1;i<=N;i++ ) cin >> D[i];
	cin >> M;
	for(int i=1;i<=M;i++ ) cin >> T[i];
}

int main(void){
	input();

	if(N<M){ 
		cout << "NO" << endl;
		return 0;
	}

	sort(D+1,D+N+1);
	sort(T+1,T+M+1);

	int pn=1,pm=1;
	for(int i=1;i<=N;i++){
	//	cout << D[i] << " " << T[pm] << endl;
		if(T[pm]==D[i]){
			pm++;
		}else if(T[pm]<D[i]){
			cout << "NO" <<endl;
			return 0;
		}		

		if(pm>M){
			cout << "YES" << endl;
			return 0;
		}
	}

	cout << "NO" << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include<iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

const int maxn=100000;

int main(){
    
    int ans=INF;
    int n,h;
    cin >> n>>h;
    int a[maxn],b[maxn];
    
    rep(i,n){
        cin>>a[i]>>b[i];
    }
    
    sort(a,a+n);
    sort(b,b+n);
    
    for(int i=n-1;i>=0;i--){
        int sub=0;
        int H=h;
        int mind=a[i];
        for(int j=n-1;j>=0;j--){
            if(mind<b[j]){
                sub++;
                H=H-b[j];
            }
            
            if(H<=0)break;
            
            
            if(mind>=b[j]||j==0){
                if(H%mind==0)sub+=H/mind;
                else sub+=H/mind+1;
                break;
            }
        }
        if(ans>sub)ans=sub;
        else break;
    }
    
    cout << ans<<endl;
    
    return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vii vector<vi>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;

int main(){
  int h,w,k;
  cin>>h>>w>>k;
  vii b(h,vi(w,0));
  int t=0;
  FOR(i,0,h){
    string s;
    cin>>s;
    int c=0;
    FOR(j,0,w){
      if(s[j]=='#'){
        t++;
        c=t;
      }else{
      }
      b[i][j]=c;
    }
  }
  vi ff(h,0);
  FOR(i,0,h){
    int f=0,c=0;
    FOR(j,0,w){
      if(b[i][j]!=0){
        if(f==0){
          c=b[i][j];
        }
        ff[i]=f=1;
      }
    }
    if(f){
      FOR(j,0,w){
        if(b[i][j]==0){
          b[i][j]=c;
        }
      }
    }
  }
  FOR(i,1,h){
    if(ff[i]==0&&ff[i-1]==1){
      FOR(j,0,w){
        b[i][j]=b[i-1][j];
      }
      ff[i]=1;
    }
  }
  FORD(i,h-1,0){
    if(ff[i]==0&&ff[i+1]==1){
      FOR(j,0,w){
        b[i][j]=b[i+1][j];
      }
      ff[i]=1;
    }
  }

  FOR(i,0,h){
    FOR(j,0,w){
        cout<<b[i][j]<<" ";
    }
    cout<<endl;
  }

}


Measured memory_bytes: 1152
def main():
    A, B, C, K = map(int,input().split())

    ans = 0
    if K <= A:
        ans = K
        return ans
    else:
        ans = A
        K -= A

    if K <= B:
        return ans
    else:
        K -= B

    ans += K*(-1)

    return ans

print(main())


Measured memory_bytes: 9096
def main():
    X, K, D = map(int, input().split())
    X = X if X >= 0 else -X
    if X == 0:
        if K % 2 == 0:
            ans = 0
        else:
            ans = D
    elif X > 0:
        if X - K*D < 0:
            a = X % D
            b = a - D
            k = X // D
            if (K - k) % 2 == 0:
                ans = abs(a)
            else:
                ans = min(abs(b), abs(a + D))
        else:
            ans = X - K*D

    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9200
#include<iostream>

using namespace std;

int main(){
    int N;
    cin >> N;
    int A[N];
    for(int i=0;i<N;i++) cin >> A[i];
    int ans[N];
    for(int i=0;i<N;i++) ans[A[i]-1]=i+1;
    for(int i=0;i<N;i++) cout << ans[i] << " ";
    cout << endl;

    return 0;
}

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

int main(void){
  int a[3];
  cin >> a[0] >> a[1] >> a[2];
  sort(a, a+3, greater<int>());

  cout << a[0]*10 + a[1] + a[2] << endl;
  
  return 0;
}

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

int main(void)
{
  int i,j,ans,len,key,row[32];
  char left[16]={"qwertasdfgzxcvb"};
  char right[12]={"yuiophjklnm"};

  for(;;){
    char str[33];
    scanf("%s", str);
    if(strcmp(str,"#")==0) break;
    len=strlen(str);
    ans=0;

    for(i=0;i<len;i++){
      for(j=0;j<15;j++){
	if(str[i]!=left[j]&&j<14) continue;
	if(str[i]==left[j]){
	  row[i]=0;
	  break;
	}
	if(str[i]!=left[j]&&j==14) row[i]=1;
      }
    }
    for(i=1;i<len;i++){
      if(row[i]!=row[i-1]) ans++;
    }
    printf("%d\n", ans);
  }
  
  return 0;
}


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

int main()
{
    int n;
    cin>>n;
    double k;
    cin>>k;
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        double a,b;
        cin>>a>>b;
        double p=0;
        p=a*a;
        p+=b*b;
        p=sqrt(p);
        if(p<=k)cnt++;
    }
    cout<<cnt<<endl;
}


Measured memory_bytes: 3744
a, b = map(int,input().split())
while a != 0:
    cnt = 1
    while cnt <= a:
        if cnt%2 == 1:
            if b%2 == 0:
                print('#.'*(b//2))
            else:
                print('#.'*(b//2)+'#')
        else:
            if b%2 == 0:
                print('.#'*(b//2))
            else:
                print('.#'*(b//2)+'.')
        cnt += 1
    print()
    a, b = map(int,input().split())


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

bool ary[60010];
int main(){
	vector<int> prm;
	for(int i=2;i<=60000;i++){
		if(!ary[i]){
			prm.push_back(i);
			for(int j=i+i;j<=60000;j+=i){
				ary[j]=true;
			}
		}
	}
	int N,ma,mi;
	vector<int>::iterator it;
	while(cin>>N){
		it=upper_bound(prm.begin(),prm.end(),N);
		ma=(*it);
		while((*it)>=N) it--;
		mi=(*it);
		cout<<mi<<" "<<ma<<endl;
	}
	return 0;
}

Measured memory_bytes: 3176
#include <bits/stdc++.h>
using namespace std;
#define long int64_t

int main() {
	ios_base::sync_with_stdio( false );

	int N;
	cin >> N;

	vector<long> a( N+1 ), b( N+1 );

	for( int i = 1; i <= N; ++i ) {
		int t;
		cin >> t;

		a[i] = a[i-1] + t;
	}

	for( int i = 1; i <= N; ++i ) {
		b[i] = a[N] - a[i-1];
	}

	long ans = LLONG_MAX;
	for( int i = 1; i < N; ++i ) {
		ans = min( ans, abs( a[i] - b[i+1] ) );
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3456
N = int(input())
l0 = [[int(i) for i in input().split()] for _ in range(N)]
l1 = [0] * N
l2 = [0] * N
for cnt, val in enumerate(l0):
    l1[cnt] = val[0] + val[1]
    l2[cnt] = val[0] - val[1]
l1.sort()
l2.sort()
print(max(l1[-1] - l1[0], l2[-1] - l2[0]))


Measured memory_bytes: 59068
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define hell1 1e9+7
#define hell2 1e9+9
#define pi 3.1415926535
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define eps 0.000001
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define ll long long
#define ld long double 
#define no_of_digits(n) floor(log10(n)) + 1
#define see(x) cout << (#x) << " is " << (x) << endl
#define INF 1e9

using namespace std;

ll mult(ll a,ll b, ll p=hell1){   return ((a%p)*(b%p))%p; }
ll multbig(ll a,ll b,ll mod=hell1){   if(a==0 or b==0) return 0;if(a==1 or b==1) return (a*b)%mod;ll cur=multbig(a,b/2,mod);cur=(2*cur)%mod;if(b%2) cur=(cur+a)%mod;return cur;
}
ll add(ll a, ll b, ll p=hell1){ if(a>=p) a%=p; if(b>=p) b%=p; if(a+b>p) return (a + b)%p; else return a+b;}
ll sub(ll a, ll b, ll p=hell1){return (a%p - b%p + p)%p;}
ll fpow(ll n, ll k, ll p = hell1) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = mult(r,n,p); n = mult(n,n,p);} return r;}
ll inv(ll a, ll p = hell1) {return fpow(a, p - 2, p);}
ll inv_euclid(ll a, ll m = hell1){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}
int isPowerof2(ll x) { return (x && !(x & x-1)); } 
ll log2(ll x) { ll res = 0; while (x >>= 1) res++; return res; } 

// max({a, b, c, d})

vector<ll>adj[200005];
ll update[200005];
ll ans[200005];

int binaryToDecimal(string n) 
{ 
    string num = n; 
    int dec_value = 0; 
  
    // Initializing base value to 1, i.e 2^0 
    int base = 1; 
  
    int len = num.length(); 
    for (int i = len - 1; i >= 0; i--) { 
        if (num[i] == '1') 
            dec_value += base; 
        base = base * 2; 
    } 
  
    return dec_value; 
} 

bool isPerfectSquare(long double x) 
{   
  // Find floating point value of  
  // square root of x. 
  long double sr = sqrt(x); 
  
  // If square root is an integer 
  return ((sr - floor(sr)) == 0); 
} 

int main()
{
    ll l, r;
    cin >> l >> r;

    if((l-1)/2019 != r/2019) cout << 0 << "\n";
    else
    {
        l = l%2019;
        r = r%2019;
        ll ans = INF;
        for(ll i=l;i<r+1;i++)
        {
            for(ll j=i+1;j<r+1;j++)
            {
                ans = min(ans, (i*j)%2019);
            }
        }

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




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

int memo[1000005], freq[1000005];
void sieve(int N)
{
	for(int i = 2; i <= N; i++)
		memo[i] = i;
		
	for(int i = 2; i * i <= N; i++)
	{
		if(memo[i] != i)
			continue;
			
		for(int j = i * i; j <= N; j += i)
			memo[j] = i;
	}
}

void primeFac(int x)
{
	int factor = 0, count = 0;
	while(x > 1)
	{
		if(memo[x] != factor)
		{
			freq[factor] += count;
			
			factor = memo[x];
			count = 1;
		}
		
		x /= memo[x];
	}
	
	freq[factor] += count;
}

int main()
{
	sieve(1000000);
	
	int N;
	scanf("%d", &N);
	
	int GCD = -1;
	for(int i = 1; i <= N; i++)
	{
		int Ai;
		scanf("%d", &Ai);
		primeFac(Ai);
		
		if(GCD == -1)
			GCD = Ai;
			
		else
			GCD = __gcd(GCD, Ai);
	}
	
	bool isPairwise = true;
	for(int i = 2; i <= 1000000; i++)
	{
		if(freq[i] >= 2)
		{
			isPairwise = false;
			break;
		}
	}
	
	if(isPairwise)
		printf("pairwise coprime");
		
	else if(GCD == 1)
		printf("setwise coprime");
		
	else
		printf("not coprime");
}


Measured memory_bytes: 11564
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template<u32 M = 1000000007>
struct modint{
    u32 val;
    modint(): val(0){}
    template<typename T>
    modint(T t){t %= (T)M; if(t < 0) t += (T)M; val = t;}

    modint pow(ll k) const {
        modint res(1), x(val);
        while(k){
            if(k&1) res *= x;
            x *= x;
            k >>= 1;
        }
        return res;
    }
    template<typename T>
    modint& operator=(T t){t %= (T)M; if(t < 0) t += (T)M; val = t; return *this;}
    modint inv() const {return pow(M-2);}
    modint& operator+=(modint a){val += a.val; if(val >= M) val -= M; return *this;}
    modint& operator-=(modint a){if(val < a.val) val += M-a.val; else val -= a.val; return *this;}
    modint& operator*=(modint a){val = (u64)val*a.val%M; return *this;}
    modint& operator/=(modint a){return (*this) *= a.inv();}
    modint operator+(modint a) const {return modint(val) +=a;}
    modint operator-(modint a) const {return modint(val) -=a;}
    modint operator*(modint a) const {return modint(val) *=a;}
    modint operator/(modint a) const {return modint(val) /=a;}
    modint operator-(){return modint(M-val);}
    bool operator==(const modint a) const {return val == a.val;}
    bool operator!=(const modint a) const {return val != a.val;}
    bool operator<(const modint a) const {return val < a.val;}
};
using mint = modint<MOD>;

template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }

template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }

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

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    auto dp = make_v(n+1, m+1, mint(0));
    dp[0][0] = 1;
    mint ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if(s[i] == t[j]){
                dp[i+1][j+1] += dp[i][j];
            }
            dp[i+1][j] += dp[i][j];
        }
        ans += dp[i+1].back();
    }
    cout << ans.val << "\n";
    return 0;
}


Measured memory_bytes: 6760
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;

int main() {
    
    ll k,a,b;
    cin >> k >> a >> b;
    if(a+2 >= b or k <= a){
        cout << k+1 << endl;
    }else{
       cout << a + (b-a)*((k-a+1)/2) + (k-a+1)%2 << endl;
    }
}




Measured memory_bytes: 256
module IntSet = Set.Make (struct type t = int let compare = compare end)

let rec tabulate n f = 
  let rec loop acc m =
    if m < n then loop (f m :: acc) (m + 1)
    else List.rev acc in
  loop [] 0

let rec solve ds = function
  | 0 -> (0, false)
  | n ->
      let m, n = n mod 10, n / 10 in
      if IntSet.mem m ds then
        match solve ds n with
        | (n, false) -> (10 * n + m, false)
        | (n, true) -> (10 * n + IntSet.min_elt ds, true)
      else
        tabulate 10 (fun n -> n)
        |> List.filter (fun n -> IntSet.mem n ds && m < n)
        |> (function
            | [] -> (10 * fst (solve ds (n + 1)) + IntSet.min_elt ds, true)
            | m :: _ ->
                match solve ds n with
                | (n, false) -> (10 * n + m, true)
                | (n, true) -> (10 * n + IntSet.min_elt ds, true))

let () =
  let n, k = Scanf.scanf "%d %d\n" (fun n k -> n, k) in
  let ds =
    IntSet.diff
      (IntSet.of_list (tabulate 10 (fun k -> k)))
      (IntSet.of_list (tabulate k (fun _ -> Scanf.scanf "%d " (fun d -> d)))) in
  Printf.printf "%d\n" (fst (solve ds n))


Measured memory_bytes: 384
N,M = map(int,input().split())
SP = [input().split() for _ in range(N)]
CP = [input().split() for _ in range(M)]

for i in range(N):
  a = int(SP[i][0])
  b = int(SP[i][1])
  k = 0
  md = abs(int(CP[0][0])-a)+abs(int(CP[0][1])-b)
  for j in range(M):
    x = abs(int(CP[j][0])-a)+abs(int(CP[j][1])-b)
    if x < md:
      md = x
      k = j
  print(k+1)

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

#define F first
#define S second
#define MP make_pair
#define PB emplace_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

using namespace std;

const int N = 1e6+100;

long long int a[N];

int main () {
    IOS;
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++ ) {
        cin >> a[i];
    }
    long long int ans = 0, mx = 0;
    for(int i = 0 ; i < n ; i++ ) {
        mx = max(mx, a[i]);
        ans += mx - a[i];
    }
    cout << ans;
}


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

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;
const ll MOD = 1000000007;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	int n, m;
	cin >> n >> m;

	vector<ll> a(n);
	map<ll, ll, greater<ll>> cards;
	for (auto &v : a) {
		cin >> v;
		cards[v]++;
	}

	for (int i = 0; i < m; i++) {
		ll b, c;
		cin >> b >> c;
		cards[c] += b;
	}

	ll cardsScore = 0;
	ll cardsNum = 0;
	for (auto p : cards) {
		if (cardsNum >= n) {
			break;
		}

		if (cardsNum + p.second > n) {
			// over
			cardsScore += (n - cardsNum) * p.first;
			break;
		}

		cardsNum += p.second;
		cardsScore += p.second * p.first;
	}

	cout << cardsScore << endl;
	return 0;
}


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

int main() {
  int N, j, k, l, m = 10000;
  cin >> N;
  for (int i = 0; i < N; i++){
    int A;
    cin >> A;
    l = 0;
    k = A;
    j = k % 2;
     if (j == 1){
      m = 0;
      break;
     }
     while (j == 0){
       k /= 2;
       j = k % 2;
       l++;
     }
    if (l < m)
      m = l;
  }
  cout << m  << endl;
}

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

int S(int a){
	int ans = 0;
	while(a > 0){
		ans += a % 10;
		a /= 10;
	}
	return ans;
}

int min(int a, int b){
	if(a * S(b) <= b * S(a)){
		return a;
	}
	else{
		return b;
	}
}

int f(int N){
	int i, j, d, lO, ans = N;
	for(i = 0, lO = 1; i < 16; i++, lO *= 10){
		d = (N / lO) % 10;
		for(j = 1; d + j <= 10; j++){
			ans = min(ans, ((N / lO) + j) * lO - 1);
		}
	}
	return ans;
}

signed main(){
	int K, N = 1, i;
	scanf("%lld", &K);
	for(i = 0; i < K; i++){
		printf("%lld\n", N);
		N = f(N + 1);
	}
	return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

char S[202020];
int N;

int main()
{
	scanf("%s", S);
	N = strlen(S);

	i64 ret = 0;
	int nb = 0;
	for (int i = 0; i < N; ++i) {
		if (S[i] == 'B') ++nb;
		else ret += nb;
	}

	printf("%lld\n", ret);

	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main() {
  
  int N;
  cin >> N;
  int sum = 0;
  
  for(int i = 0 ; i < N ; i++){
    
    int num;
    cin >> num;
    
    if(num != i+1){
      sum++;
    }
    
  }
  
  if(sum <= 2){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}
    


Measured memory_bytes: 256
Uses sysutils;
var a,b:longint;
    c:string;
    s:ansistring;
begin
    read(s);
    a:=strtoint(copy(s,1,pos(' ',s)-1));
    c:=copy(s,pos(' ',s)+1,1);
    b:=strtoint(copy(s,pos(' ',s)+3,length(s)-pos(' ',s)-2));
    if c='+' then
        writeln(a+b)
    else
        writeln(a-b);
end.

Measured memory_bytes: 1376
package main

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

func main() {
	n := getInt()
	k := getInt()
	for i := 0; i < n; i++ {
		getInt()
	}

	ans := 1
	ans += (n - 2) / (k - 1)
	fmt.Println(ans)
}

func myAns() {
	n := getInt()
	k := getInt()
	x := k - 1

	i := -1
	for j := 1; j <= n; j++ {
		if tmp := getInt(); tmp == 1 {
			i = j
		}
	}

	count := ((i-1)+x-1)/x + ((n-i)+x-1)/x
	if ((i-1)%x+(n-i)%x <= x) && ((i-1)%x > 0 && (n-i)%x > 0) {
		count--
	}

	fmt.Println(count)
}

// -----------------------------------------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
}

func getInt() int {
	i, err := strconv.Atoi(getString())
	if err != nil {
		panic(err)
	}
	return i
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}


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

    int main() {
        int n,k;
        cin >> n >> k;
        vector<int> h(n);
        rep(i,n) cin >> h[i];

        int ans=0; // ジェットコースターに乗ることができる人数（出力する値）
        rep(i,n) if(h[i] >= k) ++ans;
        cout << ans << endl; // 答えを出力する
        return 0;
    }

Measured memory_bytes: 640
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;
LL p = 1000000007ll;

int main(void)
{
  LL n;
  cin >> n;
  map<char,LL> m;
  m['F'] = 1;
  m['M'] = 2;
  LL l = 0, r = n;
  string s;
  cout << l << endl;
  cin >> s;
  if(!m[s[0]]) return 0;
  LL mode = m[s[0]]%2;
  cout << r-1 << endl;
  cin >> s;
  if(!m[s[0]]) return 0;
  for(;;) {
    LL piv = (r+l)/2;
    cout << piv << endl;
    cin >> s;
    if(!m[s[0]]) return 0;
    if((m[s[0]]+piv)%2 == mode) l = piv;
    else r = piv;
  }
  return 0;
}


Measured memory_bytes: 852
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int n;
  cin>>n;
  double arr[n+1];
  for(int i=1;i<=n;i++)
    cin>>arr[i];
  
  double dp[n+1][n+1];
  dp[0][0]=1.000000000000000000;
  
  for(int i=1;i<=n;i++)
  {
    dp[i][0]=dp[i-1][0]*(1-arr[i]);
    
  }
  for(int j=1;j<=n;j++)
    dp[0][j]=0.0000000000000;
  
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      dp[i][j]=dp[i-1][j-1]*arr[i]+dp[i-1][j]*(1-arr[i]);
    }
  }
  double ans=0.000000000000;
  for(int j=(n/2)+1;j<=n;j++)
 	ans+=dp[n][j];
  
  cout<<setprecision(10)<<ans<<endl;
  
  return 0;
}

Measured memory_bytes: 70528
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin >> n;
	int h, w;
	cin >> h >> w;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		if (a >= h and b >= w) {
			ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner scan=new Scanner(System.in);
    int num=scan.nextInt();
    String sli=scan.next();
    int Ans=1;
    for(int a=1; a<num; a++){
      if(!(String.valueOf(sli.charAt(a)).equals(String.valueOf(sli.charAt(a-1))))){
        Ans++;
      }
    }
    System.out.println(Ans);
  }
}

Measured memory_bytes: 34288
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define ALL(a)  (a).begin(),(a).end()
 
const ll mod = 1000000007;
const ll LINF = 1e13;
const ll LLINF = 1e18;
const ll ALPHABET = 26;
 
template <class T>
void Swap(T& r, T& l) {
  T tmp = r;
  r = l;
  l = tmp;
}
 
template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
  for (T& x : vec) is >> x; //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいい
  return is;
}


int main(){
    ll n;
    cin >>n;
    vector<ll> d(n);
    cin >> d;
    ll ans = 0;

    for (ll i = 0; i < n; i++){
        for (ll j = i+1; j < n; j++){
            ans+= d[i]*d[j];
        }   
    }
    cout << ans;


}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
#define REP(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;
const ll MOD = 1000000007;
using namespace std;

int main(){
    int n; cin >> n;
    string s; cin >> s;
    int ans = n;
    vector<int> wt(n+1, 0); //wt[i] = 0からi-1 で東を向いている人
    REP(i, n) wt[i+1] = wt[i] + (s[i] == 'E');
    REP(i, n){
        int cnt = 0;
        //左側にいる人
        if(i) cnt += i - wt[i];
        //右側にいる人
        cnt += wt[n] - wt[i+1];
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1796
#include <iostream>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#define myfor(i,N) for(i=0;i<N;i++)
#define myforFL(i,f,l) for(i=f;i<l;i++)
#define myforInv(i,N) for(i=N;i>=0;i--)
#define myforFLInv(i,f,l) for(i=f;i>l;i--)
#define MAXDIF 126 //pow(pow(10.,9.),1./5.)*2
using namespace std;

int main(){
	long X,i,j;
	cin >> X;
	myforFL(i,-63,127){
		myforFL(j,i,127){
			if(pow(j,5) - pow(i,5) == X){
				cout << j << " " << i << endl;
				return 0;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

#define all(v)   v.begin(), v.end()
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define THINK_TWICE_CODE_ONCE cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define isOdd(n)    (n&1)
#define LLMAX LLONG_MAX
#define LLMIN LLONG_MIN
#define IMN INT_MIN
#define IMX INT_MAX
#define pow(n, m) power((ll)n, (ll)m)
#define numOfDigits(n)  ((n)? (ll)(log10(n)+1) : 1)
#define mem(x, val)    memset(x, val, sizeof(x))
#define MOD 1000000007

typedef long long ll;
typedef long double ld;
typedef double dd;
typedef string str;
typedef pair<int, int> pii;

ll n, s;
ll func(ll b, ll n){
    if(n < b)   return n;
    return func(b, n / b) + (n % b);
}
int main()
{
    THINK_TWICE_CODE_ONCE
    //freopen("test cases\\.txt", "r", stdin) ;
    cin>>n>>s;
    if(n==s) return cout<<s+1, 0;
    for(ll i = 2; i<=1e6; i++){
        if(func(i, n)==s)
            return cout<<i, 0;
    }
    ll ans = -1, d = n-s;
    for(ll i = 1; i*i<=d; i++){
        if(d%i==0){
            if(func(i+1, n)==s)
                if(~ans) ans = min(ans, i+1);
                else ans = i + 1;
            if(func(d/i + 1, n)==s)
                if(~ans) ans = min(ans, d/i + 1);
                else ans = d/i + 1;
        }
    }
    cout<<ans;
	return 0;

}


Measured memory_bytes: 256
_,*s=open(0);t=".";b=t*101;q=range(101);i=0
for s in s:
 a=[i];i+=1
 for x,y,z,c in zip(b,t+s,s,q):a+=min(c+(t==x>z),a[-1]+(t==y>z)),
 b,q=s,a[1:]
print(a[-2])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
int main(){
    ll n;cin>>n;
    vi id(1000001);
    vi v(n);
    rep(i,n)cin>>v[i];
    rep(i,n)id[v[i]]++;
    ll ans=0;
    rep(i,n){
        bool ok=true;
        id[v[i]]--;
        REP(j,1,sqrt(v[i])+1){
            if(v[i]%j==0){
                if(id[v[i]/j]||id[j])ok=false;
            }
        }
        if(ok)ans++;
        id[v[i]]++;
    }
    out(ans);
}

Measured memory_bytes: 12828
#include "bits/stdc++.h"
#define PRECISION(x) cout << fixed << setprecision(x)
#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define ALLR(X) (X).rbegin(), (X).rend()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second

using namespace std;
 
template<class T> void max_self(T & a, const T & b) { if(a < b) a = b; }
template<class T> void min_self(T & a, const T & b) { if(a > b) a = b; }
typedef long long LL;
const int INF = 1e9 + 7;
const double PI = acos(-1.0);
const double EPS = (1e-9);



int main(){
  FAST_IO  
  
  int a, b, c, d; cin >> a >> b >> c >> d;
  if(a + b > c + d) cout << "Left\n";
  else if (a + b < c + d) cout << "Right\n";
  else cout << "Balanced\n";

  return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
stack = []
root = -1
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == -1:
    root = i
deg[root] += 1
dp = [[] for i in range(n+1)]
num = [0]*(n+1)
while stack:
  x = stack.pop()
  if dp[x]:
    num[x] = sum(dp[x])+1
  else:
    num[x] = 1
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(num[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
for i in range(1,n+1):
  if num[i] != n:
    dp[i].append(n-num[i])
ans = 0
mod = 10**9+7
def inv(x):
  return pow(x,mod-2,mod)
inv2 = inv(2)
inv2n = inv(pow(2,n,mod))
for i in range(1,n+1):
  if len(dp[i]) > 1:
    ans += 1
    ans -= inv2
    ans += inv2n*(len(dp[i])-1)
    for val in dp[i]:
      ans -= pow(2,val,mod)*inv2n
      ans %= mod
print(ans)

Measured memory_bytes: 130216
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define N 100010
using namespace std;
int main()
{
    int a,b,n;
    long long x1,x2,sum,ans,m;
    scanf("%d",&n);
    scanf("%d %d",&a,&b);
    x1=a,x2=b;
    for(int i=0;i<n-1;i++)
    {
        scanf("%d %d",&a,&b);
        sum=x1/a;
        if(x1%a!=0)
            sum++;
        ans=x2/b;
        if(x2%b!=0)
            ans++;
        m=max(sum,ans);
        x1=a*m,x2=b*m;
    }
    printf("%lld",x1+x2);
    return 0;
}


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

int main() {
  char a,b;
  cin >> a >> b;
  if((a=='H'&& b=='H') || (a=='D' && b=='D')){
    cout << "H" << endl;
  }else{
    cout << "D" << endl;
  }
}


Measured memory_bytes: 256
#include <queue>
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <iomanip>
#include <cstdio>
#define rep(i, n) for(long long i = 0;(i) < (n);(i)++)
using namespace std;
using ll = long long;
const ll mod = 1000000007;



//貪欲
int main()
{
	ll N, K, R, S, P;
	string T;
	cin >> N >> K >> R >> S >> P;
	cin >> T;
	//高橋君の出した手、-1だったら勝てない手
	vector<ll> takahashi(N);
	ll ans = 0;
	for (ll i = 0; i < N; i++)
	{
		if (i < K)
		{
			if (T[i] == 'p') ans += S;
			if (T[i] == 's') ans += R;
			if (T[i] == 'r') ans += P;
		}
		else if (T[i] != T[i - K] || takahashi[i - K] == -1)
		{
			if (T[i] == 'p') ans += S;
			if (T[i] == 's') ans += R;
			if (T[i] == 'r') ans += P;
		}
		else if (T[i] == T[i - K]) takahashi[i] = -1;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1280
a=[int(input())]
cnt=0
flag=True
while flag:
  cnt+=1
  if a[cnt-1]%2:
    a.append(3*a[cnt-1]+1)
  else:
    a.append(a[cnt-1]//2)
  for i in range(cnt):
    if a[i]==a[cnt]:flag=False

print(cnt+1)

Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define ALL(a) begin(a),end(a)
#define ifnot(a) if(not (a))
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;

// #define int ll
#ifdef _MSC_VER
const bool test = true;
#else 
const bool test = false;
#endif

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
#define INF (1 << 28)
ull mod = (int)1e9 + 7;
//.....................
const int MAX = (int)2e5 + 5;

int N;
int p[MAX];
int a[MAX];
int b[MAX];

int main() {
	cin >> N;
	rep(i, N) {
		cin >> p[i];
		p[i]--;
	}
	rep(i, N) {
		a[i] = b[N-1-i] = i * (int)(4.5e4) + 1;
	}
	rep(i, N) {
		a[p[i]] += i / 2;
		b[p[i]] += i / 2 + i % 2;
	}
	rep(i, N - 1) cout << a[i] << " ";
	cout << a[N - 1] << endl;	
	
	rep(i, N - 1) cout << b[i] << " ";
	cout << b[N - 1] << endl;

	return 0;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
#define FOR(i,a,b) for(long long int i=a;i<b;i++)
#define sz(s) (long long int)(s).size()
#define pb push_back
#define mp make_pair
const ll inf = 1000000000;
const ll MOD = 1000000007;

int main(void){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);   
    cout.tie(NULL);
    register ll i,j,k,x,y,m,n,t,q,temp,sum=0,count=0,f=1,W;
    cin>>n>>W;
    ll v[n], w[n];
    for(i=0;i<n;i++){
    	cin>>w[i];
    	cin>>v[i];
    }
    ll dp[n+1][W+1], visited[n+1] = {0};
    for(i=0;i<=n;i++){
    	for(j=0;j<=W;j++){
    		if(i == 0)dp[i][j] = 0;    		
    		else if(j == 0)dp[i][j] = 0;
    		// else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    		else dp[i][j] = dp[i-1][j];
    		if(w[i-1] <= j){
    			x = dp[i-1][j - w[i-1]] + v[i-1];
    			dp[i][j] = max(dp[i][j], x);    			
    			// if(dp[i][j] == x)v[i-1] = -1000000;
    		}
 		}   	
    }
    // for(i=0;i<=n;i++){
    // 	for(j=0;j<=W;j++){
    // 		cout<<dp[i][j]<<" ";
    // 	}
    // 	cout<<"\n";
    // }
    cout<<dp[n][W];
}    

Measured memory_bytes: 79232
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int cnt=0,sum=0;
	if(n>=105)
	{
		if(n%2==0)
			n--;
		for(int i=105;i<=n;i+=2)
		{
			for(int j=3;j<i-1;j+=2)
			{
				if(i%j==0)
				cnt++;
			}
			if(cnt==6)
			sum++;
			cnt=0;
		}
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define puba push_back
#define ff first
#define ss second
#define bend(_x) begin(_x), end(_x)
#define szof(_x) ((int) (_x).size())
#define TASK_NAME ""

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7;
const ll INFL = 1e18 + 123;
const double PI = atan2(0, -1);
mt19937 tw(960172);
ll rnd(ll x, ll y) { static uniform_int_distribution<ll> d; return d(tw) % (y - x + 1) + x; }


int amount[26];
char field[105][105];
char buf[105];

int main() {
    //freopen(TASK_NAME ".in", "r", stdin);
    //freopen(TASK_NAME ".out", "w", stdout);
    cerr << fixed << setprecision(15);
    cout << fixed << setprecision(15);
    
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < m; ++j) {
            amount[buf[j] - 'a']++;
        }
    }
    
    int num = 0;
    if (n % 2 == 1 && m % 2 == 1) {
        int cnt = 0;
        for (int i = 0; i < 26; ++i) {
            if (amount[i] % 2 == 1) {
                ++cnt;
                --amount[i];
            }
        }
        if (cnt != 1) {
            cout << "No\n";
            return 0;
        }
        num = n + m - 2;
    } else if (n & 1) {
        num = m;
    } else if (m & 1) {
        num = n;
    }

    for (int i = 0; i < 26; ++i) {
        if (amount[i] & 1) {
            cout << "No\n";
            return 0;
        }
    }

    num /= 2;

    for (int i = 0; i < 26; ++i) {
        if (amount[i] % 4 == 2) {
            --num;
            amount[i] -= 2;
        }
    }
    
    if (num < 0 || num % 2 != 0) {
        cout << "No\n";
        return 0;
    }

    cout << "Yes\n";

    #ifdef LOCAL
        cerr << "time: " << clock() << endl;
    #endif
    return 0;
}

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

long long s[400][30]; 
const int Shurui=26;//今回は26種類
int Date;//今回は1年間なので365日
double Seigenjikan=1.8;//実行時間

int main() {
  clock_t start = clock();
  cin >>Date;
  vector<int>c(Shurui);
  vector<int>last(Date,0);//前回の日にち
  vector<int>t(Date,0);//開催する順番
  for(int i=0;i<Date;i++)t[i]=rand()%Shurui;//とりあえずの値
  long long wa=0;
  for(int i=0;i<Shurui;i++){
    cin>>c[i];
    wa+=c[i];
  }
  for(int i=0;i<Date;i++){
    for(int j=0;j<Shurui;j++){
      cin>>s[i][j];
    }
  }
  long long kotae=0;
  long long hikukazu=0;
  long long atai=0;
  for(int i=0;i<Date;i++){
    atai=0;
    for(int j=0;j<Shurui;j++){
      if(s[i][t[i]]-c[j]*(i+1-last[t[i]])>atai){
        t[i]=j;
        atai=s[i][t[i]]-c[j]*(i+1-last[t[i]]);
      }
    }
  }
  for(int i=0;i<Date;i++){
    atai=0;
    atai=s[i][t[i]];
    hikukazu+=wa-c[t[i]]*(i+1-last[t[i]]);
    last[t[i]]=i+1;
    kotae+=atai-hikukazu;
    //cout<<kotae<<endl;
  }  
  clock_t end = clock();
  double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
  while(time<Seigenjikan){
    int d=rand()%Date;
    int q=rand()%Shurui;
    int old=t[d];
    t[d]=q;
    long long new_kotae=0;
    hikukazu=0;
    for(int i=0;i<Date;i++){
      atai=0;
      atai=s[i][t[i]];
      hikukazu+=wa-c[t[i]]*(i+1-last[t[i]]);
      last[t[i]]=i+1;
      new_kotae+=atai-hikukazu;
    }
    if(new_kotae<kotae){
      t[d]=old;
    }else{
      kotae=new_kotae;
    }
    end = clock();
    time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
  }
  for(int i=0;i<Date;i++){
    cout<<t[i]+1<<endl;
  }
  return 0;
}

Measured memory_bytes: 3740
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define FORR(I,A,B) for(ll I = (B-1); I >= (A); --I)
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(1){
		ll n;
		cin >> n;
		if(n==0)break;
		ll maxk = 0;
		ll mink = INF;
		ll ans = 0;
		FOR(i,0,n){
			ll k;
			cin >> k;
			maxk = max(maxk,k);
			mink = min(mink,k);
			ans += k;
		} 
		ans -= (maxk+mink);
		cout << ans/(n-2) << endl;
	}
}


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

using namespace std;
#define ll long long
#define N 1000000007
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

int main() {
	string s;
	int n,k;
	cin>>n>>k>>s;
	s[k-1]=tolower(s[k-1]);
	cout<<s;
	return 0;
}


Measured memory_bytes: 256
def input_array():
	return list(map(int,input().split()))
  
n=int(input())
D=[input_array() for i in range(n)]

count=0
for d in D:
	if d[0]==d[1]:
		count+=1
	else:
		count=0

	if count==3:
		break
if count==3:
	print("Yes")
else:
	print("No")

Measured memory_bytes: 9200
from copy import copy

H,W,K=map(int,input().split())
S=[[0]*W for _ in range(H)]

for y in range(H):
    T=input()

    for x in range(W):
        if T[x]=="#":
            S[y][x]=1


C=[[0]*W for _ in range(H)]
T,P=1,-1
for y in range(H):
    F=False
    M=0
    for x in range(W):
        if S[y][x]==1:
            F=True
            for k in range(M,x+1):
                C[y][k]=T
            T+=1
            M=x+1

    if M!=W:
        for k in range(M,W):
            C[y][k]=T-1

    if F:
        for l in range(P+1,y):
            C[l]=copy(C[y])
        P=y

for l in range(P+1,H):
    C[l]=copy(C[P])

G=[" ".join(map(str,x)) for x in C]
print("\n".join(G))

Measured memory_bytes: 77016
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define f(a, b, c, d) for(ll a = b; a < c; a += d)

void solve()
{
	ll n, x, t;
	cin >> n >> x >> t;
	ll ans = ceil(n / (1.0 * x));
	cout << ans * t;
}

signed main()
{

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	ll t = 1;
	//cin >> t;
	while (t--)
		solve();
}

Measured memory_bytes: 3756
#include <iostream>
#include <vector>

using namespace std;

int main(){
  int N;
  cin >> N;
  int f = 0;
  for(int a = 0; a * 4 <= N; a++){
    for(int b = 0; a * 4 + b * 7 <= N; b++){
      if(a * 4 + b * 7 == N) f = 1;
    }
  }
  if(f)cout << "Yes";
  else cout << "No";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,m;cin>>n>>m;
    vector<pair<long long,int>> A(n);
    for(int i=0;i<n;i++){
        long long a;int b;cin>>a>>b;
        A[i]=make_pair(a,b);
    }
    sort(A.begin(),A.end());
    long long res=0;
    int now=0;
    for(int i=0;i<n;i++){
        pair<long long,int> p=A[i];
        long long a;int b;a=p.first;b=p.second;
        if(now+b>=m){
            res+=a*(m-now);
            cout<<res<<endl;
            return 0;
        }else{
            res+=a*(long long)b;
            now+=b;
        }
    }
}


Measured memory_bytes: 1792
#include <iostream>
    #include <string>
    #include <vector>
    #include <math.h>
    using namespace std;
     
    int main() {
    	int x1,y1,x2,y2;
    	cin>>x1>>y1>>x2>>y2;
    	int a=x2-x1;
    	int b=y2-y1;
    	int x3,y3,x4,y4;
    	x3=x2-b;
    	y3=y2+a;
    	x4=x3-a;
    	y4=y3-b;
    	cout<<x3<<" "<<y3<<" "<<x4<<" "<<y4<<endl;
    }

Measured memory_bytes: 256