akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
//debug
#ifdef grief
#define debug(...) do{\
	fprintf(stderr , "%s - %d : (%s) = " , __PRETTY_FUNCTION__ , __LINE__ , #__VA_ARGS__ );\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> 				void _DO(I&&x){	cerr<<x<<endl;	}
template<typename I,typename...T>	void _DO(I&&x,T&&...tail){	cerr<<x<<" , ";	_DO(tail...);	}
template<typename _a,typename _b> 	ostream& operator << (ostream &_s,const pair<_a,_b> &_p)
{	return _s<<'('<<_p.first<<','<<_p.second<<')';	}
#define IOS
#else
#define debug(...)
#define IOS do{ios_base::sync_with_stdio(0); cin.tie(0);}while(0);
#endif
//type
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef priority_queue<pll,vector<pll>,greater<pll> > heap;
//macro
#define SZ(x) ((ll)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define stp setprecision(30)<<fixed
const ll INF=0x3f3f3f3f3f3f3f3f;
const int NF=0x3f3f3f3f;
const ll MAX=1e5+5,Mlg=__lg(MAX)+2;
const ll MOD=1e9+7;
// ready~ go!
// let's coding and have fun!
// I can't solve this problem!
ll arr[MAX],n,z,w;
ll ma[2010];
ll mi[2010];
ll qmi(int a);
ll qma(int a){
	if(ma[a]!=-1)	return ma[a];
	ll r=abs(arr[0]-arr[a]);
	for(int i=1;i<a;i++)	r=max(qmi(i),r);
	debug(a,r);
	return ma[a]=r;
}
ll qmi(int a){
	if(mi[a]!=-1)	return mi[a];
	ll r=abs(arr[0]-arr[a]);
	for(int i=1;i<a;i++)	r=min(qma(i),r);
	debug(a,r);
	return mi[a]=r;
}
int main(){
	IOS
	string s;	cin>>s;
	cin>>s;
	int ans=700;
	for(char c:s)	if(c=='o')	ans+=100;
	cout<<ans<< '\n';
	return 0;
}

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

typedef long long int ll;
typedef long long unsigned int ull;
typedef long double ld;
typedef vector<int> vr;
typedef pair<int, int> pr;
#define pb push_back
#define ff first
#define ss second
#define INF 1999999999
#define MODA 1000000007
#define PI 3.1415926535897932384626433
#define endl "\n"
//cout << fixed << setprecision(2);


int main()
{

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    vector<ll> ans;
    ans.push_back(a * c);
    ans.push_back(a * d);
    ans.push_back(b * c);
    ans.push_back(b * d);
    /*
    for(auto i : ans){
        cout << i << " ";
    }
    cout << endl;
    */

   // sort(ans.begin(), ans.end());
   // cout << ans[3] << endl;
    ll max_ans = *max_element(ans.begin(), ans.end());
    cout << max_ans << endl;
    return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    int N;
    cin >> N;
    vint b(N);
    vvint pos(N);
    vint ans;
    for (int i = 0; i < N; i++)
    {
        cin >> b[i];
        b[i]--;
        pos[b[i]].push_back(i);
    }
    while (ans.size() < N)
    {
        for (int i = N - 1; i >= 0; i--)
        {
            for (int j = pos[i].size() - 1; j >= 0; j--)
            {
                if (i == pos[i][j])
                {
                    ans.push_back(i + 1);
                    b.erase(b.begin() + i);
                    goto L;
                }
            }
        }
        cout << -1 << endl;
        return 0;
    L:;
        pos.clear();
        pos.resize(N);
        for (int i = 0; i < b.size(); i++)
        {
            pos[b[i]].push_back(i);
        }
    }
    reverse(all(ans));
    for (auto &&i : ans)
    {
        cout << i << "\n";
    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <queue>
#include <numeric>
#include <deque>
#include <cstring>
#include <iterator>
#include <map>
#include <cstdlib>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <complex>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define eb emplace_back
#define el '\n'
typedef  long long  ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;


const int mod=1000000007;
//const int mod=998244353;





int main()
{   ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll t,n,m,k,q,x,a,b,c,d;
    cin>> n >> k;
    if(k>(n-1)*(n-2)/2)
        cout<<-1<<el;
    else{
        cout<<n-1+(n-1)*(n-2)/2-k<<el;
        for(int i=2; i<n+1; i++)
            cout <<1 <<' '<< i<<el;
        b=(n-1)*(n-2)/2-k;
        for(int i=2; i<n; i++){
            for(int j=i+1; j<=n; j++){
                if(b==0)
                    return 0;
                cout <<i <<' ' << j<<el;
                b--;
            }
        }
    }
    
    
    return 0;
}



Measured memory_bytes: 256
def digitSum(n):
    s = str(n)
    array = list(map(int, list(s)))
    return sum(array)

if __name__ == "__main__":
    n = input()
    n = int(n)
    result = digitSum(n)
    if n%result == 0:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 3060
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

data = np.fromstring(read(), np.int64, sep =' ')

N, K = data[:2]
P = np.hstack([[0], data[2:] + 1])

Pcum = P.cumsum()
x = Pcum[K:] - Pcum[0:-K]
print(x.max()/2)

Measured memory_bytes: 18584
import itertools
n=int(input())
S=list(map(str,[input() for i in range(n)]))
d={}
A=['M','A','R','C','H']
for i in A:
    d[i]=0
for i in range(n):
    tmp=S[i][0]
    if tmp=='M' or tmp=='A' or tmp=='R' or tmp=='C' or tmp=='H':
        d[tmp]+=1
c=0
B=[]
for i in A:
    if d[i]!=0:
        B.append(i)
if len(B)<3:
    print(0)
else:
    ans=0
    for i in itertools.combinations(B,3):
        tmp=1
        for j in range(3):
            tmp*=d[i[j]]
        ans+=tmp
    print(ans)

Measured memory_bytes: 10540
#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    std::ios_base::sync_with_stdio(0);
    int64_t n;
    std::cin >> n;
    std::vector<int> B(n+1, 0);
    for (int i=0;i<n;++i)
    {
        int a;
        std::cin >> a;
        B[a]++;
    }
    std::sort(B.begin(), B.end(), std::greater<int>());
    while (B.back() == 0) B.pop_back();

    int div = n;
    int j = 0;
    int sum = n;
    for (int i=1;i<=n;++i)
    {
        while (j < B.size() && B[j] >= div) { sum -= B[j]; ++j; }
        int k = (div == 0 ? i : (j + sum / div));
        if (k >= i || div == 0) std::cout << div << "\n";
        else { --div; --i; }
    }

    return 0;
}

Measured memory_bytes: 2048
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
ans=10**100
for i in range(1,int(n**0.5)+1):
    if n%i==0:
        b=n//i
        tmp=max(len(str(i)),len(str(b)))
        ans=min(tmp,ans)
print(ans)

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

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    ll mod = 1e9 + 7;
    vector<ll> ones(60, 0);
    auto bits = [&](ll n) {
        int idx = 0;
        while (n >> idx > 0) {
            if ((n >> idx) & 1) ones[idx]++;
            idx++;
        }
    };
    for (ll a : A) bits(a);
    ll ans = 0;
    rep(i, 60) {
        ans +=
            ll(((N - ones[i]) * ones[i] % mod) * (ll(pow<ll, ll>(2, i)) % mod));
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
#define _'			'
A[_];long P[_],M=1e9+7,F[_],I[_]={1},X;i,j,k,t;c(a,b)int*a,*b;{t=a[1]-b[1]?:*a-*b;}p(a,b){return b?p(a%M*a%M,b/2)*(b%2?a:1L)%M:1;}f(a,b){return F[a+b]*I[a]%M*I[b]%M;}main(s){for(;++X<_;)I[X]=p(s=F[X]=X*s%M,M-2);for(;~scanf("%d",A+i);)i++-1||gets(P);for(qsort(A,i/2,8,c);j<i;P[j++-1]=X)for(X=f(t=A[++j]-=1,s=A[k=j]-=1);k;X=s<A[k-=2]?X:(X-f(s-A[k],t-A[k+1])*P[k]%M+M)%M);printf("%d",X);}

Measured memory_bytes: 12540
#include <bits/stdc++.h>
#define inf 0xffffff
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const long double PI = acos(-1);
const int maxn=10000005;
const int mod=100000007;
ll qpow(ull a,ull b,int n)
{
	ll ans=1,res=a%n;
	while(b)
	{
		if(b&1) ans=ans*res%n;
		res=res*res%n;
		b>>=1;
	}
	return ans%n;
}

inline ll gcd(ll a,ll b) { return b==0 ? a : gcd(b, a%b);}
inline ll lcm(ll a,ll b) {return a*b/gcd(a, b);}

string s;
int main(int argc, char *argv[]) {
	cin >> s;
	if(s=="ABC") cout << "ARC" << endl;
	else cout << "ABC" << endl;
}


Measured memory_bytes: 3556
S=input()
A=[]
for letter in S:
    A.append(letter)
if ('N' in A and 'S' not in A) or ('S' in A and 'N' not in A) or ('E' in A and 'W' not in A)or ('W' in A and 'E' not in A):
    print('No')
else:
    print('Yes')

Measured memory_bytes: 9020
#include <stdio.h>

int main(void)
{
int S, h, m, s;
scanf("%d", &S);
h = S/3600;
m = (S-h*3600)/60;
s = S-h*3600-m*60;
printf("%d:%d:%d\n", h, m, s); 
return 0;
}

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

using namespace std;

int main() {

    int N, A, B;
    cin >> N >> A >> B;

    string S;
    cin >> S;

    int count = 0;
    int count_B = 0;

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

        if (S[i] == 'a' && count < A + B) {
            count++;
            cout << "Yes" << endl;

        } else if (S[i] == 'b' && count < A + B && count_B < B) {
            count++;
            count_B++;
            cout << "Yes" << endl;

        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}

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

using namespace std;
using lint = long long;

int main() {
    string s;
    lint K;
    cin >> s >> K;

    int n = s.size();
    vector<lint> vt = {1};
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) vt.back()++;
        else vt.push_back(1);
    }

    // すべての文字が同じ場合
    if (vt.size() == 1) {
        cout << vt[0] * K / 2 << endl;
        return 0;
    }

    // 違う文字が含まれる場合
    lint ans = 0;
    for (int x : vt) ans += x / 2;
    ans *= K;
    if (s[0] == s[n - 1]) {
        lint a = vt.front(), b = vt.back();
        ans -= (a / 2 + b / 2 - (a + b) / 2) * (K - 1);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
if __name__ == '__main__':

	s = input()
	flg = False
	
	if s[0] == "A":
		tmp = s[2:-1]
		if tmp.count("C") == 1:
			tmp2 = s.replace("A","")
			tmp2 = tmp2.replace("C","")
			if tmp2.islower() == True:
				flg = True

	if flg == True:print("AC")
	else:		print("WA")


Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define INF         1e9
#define EPS         1e-9
#define REP(i,n)    for(lint i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)   for(lint i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)   for(lint i=(n)-1;i>=0;--i)
#define REPR1(i,n)  for(lint i=(n);i>0;--i)
#define REPC(i,obj) for(auto i:obj)
#define R_UP(a,b)   (((a)+(b)-1)/(b))
#define ALL(obj)    (obj).begin(),(obj).end()
#define SETP        cout << fixed << setprecision(8)
using namespace std;
using lint = long long;
template<typename T = lint>inline T in() { T x; cin >> x; return x; }

signed main() {
	int n = in();
	vector<string>w(n);
	map<string, int>s;
	REP(i, n) {
		w[i] = in<string>();
		++s[w[i]];
		if (i > 0 && w[i].front() != w[i - 1].back() || s[w[i]] > 1) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

//#include "atcoder/all"
//using namespace atcoder;

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h, w;
	cin >> h >> w;
	vector<vector<char>> grid(h+2, vector<char>(w+2, '.'));
	for(int i = 1; i <= h; ++i){
		for(int j = 1; j <= w; ++j){
			cin >> grid[i][j];
		}
	}
	for(int i = 1; i <= h; ++i){
		for(int j = 1; j <= w; ++j){
			if(grid[i][j] == '.') continue;
			bool ok = false;
			rep(k,4){
				if(grid[i+dy[k]][j+dx[k]] == '#') ok = true;
			}
			if(!ok){
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}


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

bool solve(const string& s) {
    stack<int> stk;
    for(char c : s) {
        if(c == '(') stk.push(1);
        if(c == ')') {
            if(stk.empty() || stk.top() != 1) return false;
            stk.pop();
        }
        if(c == '[') stk.push(2);
        if(c == ']') {
            if(stk.empty() || stk.top() != 2) return false;
            stk.pop();
        }
    }
    return stk.empty();
}

int main() {
    while(true) {
        string s;
        getline(cin, s);
        if (s == ".") break;
        cout << (solve(s) ? "yes" : "no") << endl;
    }
}


Measured memory_bytes: 3140
N,K = gets.split.map(&:to_i)
ary = gets.split.map(&:to_i)
expected = []
ary.map do |pi|
  tmp = (1 + pi)
  sum = tmp * (pi / 2)
  sum += tmp / 2 if (tmp % 2 == 0)
  expected << sum.to_f / pi
end
last = N - K
cache = 0
expected[0..(K-1)].each {|elm| cache += elm}
max = cache
for i in (1..last)
  cache -= expected[i - 1]
  cache += expected[i + K-1]
  max = cache if max < cache
end
puts max

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

using namespace std;

int main(){
        int n;
        cin >> n;
        while(n--){
                int m;
                cin >> m;
                int list[8];
                for(int i = 0; i < 8; i++){
                        list[i] = m%10;
                        m /= 10; 
                }   
                sort(list, list+8);
                int _list[8];
                for(int i = 0; i < 8; i++){
                        _list[i] = list[i]-list[7-i];
                }   
                for(int i = 0; i < 7; i++){
                        if(_list[i] < 0){ 
                                _list[i] += 10; 
                                _list[i+1]--;
                        }   
                }   
                int idx = 7;
                while(!_list[idx]) idx--;
                if(idx < 0){ 
                        cout << 0 << endl;
                }else{
                        while(idx+1){
                                cout << _list[idx--];
                        }   
                        cout << endl;
                }   
        }   
}

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

int main(){
  string A,B;
  cin>>A>>B;
  string C;
  for(int i=0;i<A.size()+B.size();i++){
   if(i%2==0){
     C+=A.at(i/2);
   }
    if(i%2==1){
     C+=B.at(i/2);
    }
  }
  cout<<C<<endl;
}

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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define CONCAT(x,y) (x).insert((x).end(),(y).begin(),(y).end())
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define FOR(i,a,b) for (int i=(int)(a);i<(int)(b);++i)
#define FORE(i,a,b) for (int i=(int)(a);i<=(int)(b);++i)
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)
#define REPE(i,n) FOR(i,0,n)

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> VEC;

int main() {
  string S;cin>>S;
  int N = S.size();
  ll K;cin>>K;

  // 全部同じ
  bool same_flag = true;
  REP(i,N) {
    if (S[0] != S[i]) same_flag = false;
  }
  if (same_flag) {
    cout << N*K/2;
    return 0;
  }

  // 頭の連続数と尾の連続数、それ以外で考える
  ll head_cnt=0,tail_cnt=0;
  char headch=S[0],tailch=S[N-1];
  while (S[head_cnt] == headch) head_cnt++;
  while (S[N-1-tail_cnt] == tailch) tail_cnt++;
  ll middle_cnt = 0;
  char prech = S[head_cnt];
  int tmp = 1;
  FOR(i,head_cnt+1,N-tail_cnt) {
    if (S[i] == prech) {
      tmp++;
    } else {
      middle_cnt += tmp/2;
      tmp = 1;
      prech = S[i];
    }
  }
  middle_cnt += tmp/2;

  // 両端が同じなら、その連続数をカウントする
  if (headch == tailch) {
    cout << middle_cnt*K+head_cnt/2+tail_cnt/2+((head_cnt+tail_cnt)/2)*(K-1);
  } else {
    // 両端が違うなら、単純に中身の連続している箇所の長さを調べて、K倍する
    cout << (head_cnt/2+middle_cnt+tail_cnt/2)*K;
  }

  return 0;
}

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

long d;
long c[26];
long s[365][26];
long t[365];
long last[26];
long tmpAdd[26];

long nowAns = -1<<30;

long calcMinus(int day,long* last);
long calcScore();

int main(){
    long time = clock();
    
    nowAns = 0;
    cin >> d;
    for(int i=0;i<26;i++)cin >> c[i];
    for(int i=0;i<d;i++){
        for(int j=0;j<26;j++){
            cin >> s[i][j];
        }
    }
    srand(1);

    


    for(int i=0;i<365;i++){
        t[i] = rand()%26 + 1;
    }
    nowAns = calcScore();

    for(int i=0;i<26;i++){
        last[i] = tmpAdd[i];
    }

   do{
        
        int qq = 1;
        int qqbef = 1;
        int dd = 0;
        
            do{
                dd = rand()%365;
                qqbef = t[dd];
                qq = rand()%26 + 1;
                if(s[dd][qq-1] > s[dd][qqbef-1]){
                    if(rand()%10 == 9)qq = qqbef;
                }else{
                    if(rand()%10 > 0)qq = qqbef;
                }
            }while(qq == qqbef);
        
        t[dd] = qq;
        long tmp = calcScore();
        bool chk = true;
        if(tmp > nowAns){
            if(rand()%100 > 90){
                chk = false;
            }
        }else{
            if(rand()%100 > 1){
                chk = false;
            }
        }

        if(chk){
            for(int i=0;i<26;i++){
                last[i] = tmpAdd[i];
            }
            nowAns = tmp;
        }else{
            t[dd] = qqbef;
        }
    }while(clock() - time  < 2*CLOCKS_PER_SEC-30000);

    for(int i=0;i<d;i++){
        cout << t[i]<<endl;
    }
    
}


long calcMinus(int day,long* tmplast){

    long ans = 0;
    for(int i=0;i<26;i++){
        ans -= c[i] * (day - tmplast[i]);
    }

    return ans;
}

long calcScore(){
    long ans = 0;

    long tmplast[26];
    for(int i=0;i<26;i++){
        tmplast[i] = -1;
    }

    for(int i=0;i<d;i++){
        tmplast[t[i]-1] = i;
        ans += s[i][t[i]-1];
        ans += calcMinus(i,tmplast);
    }

    for(int i=0;i<26;i++){
        tmpAdd[i] = tmplast[i];
    }

    return ans;
    
}

Measured memory_bytes: 3716
#include<iostream>
using namespace std;
int main()
{
    int s, a[10000];
    cin >> s;
    a[0] = s;
    for(int i = 1; i < 10000; i++)
    {
        if(s % 2 == 0)
        {
            s = s / 2;
            a[i] = s;
        }
        else
        {
            s = 3 * s + 1;
            a[i] = s;
        }

        for(int j = 0; j < i; j++)
        {
            if(i != j && a[i] == a[j])
            {
                cout << i + 1;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 3640
#include<stdio.h>
#include<float.h>
#define N 1000

double min( double a , double b ){
	
	if( a < b ){
		return a;
	}else{
		return b;
	}
}

int main( void ){
	
	int n;
	
	scanf( "%d" , &n );
	double p[n] , q[n+1];
	
	for( int i = 0; i < n; i++ ){
		scanf( "%lf" , &p[i]);
	}
	for( int i = 0; i < n+1; i++ ){
		scanf( "%lf" , &q[i]);
	}
	
	double dp[n+1][n+1];
	double psum[n][n];
	double qsum[n+1][n+1];
	
	for( int i = 0; i < n+1; i++ ){
		dp[i][i] = q[i];
	}
	for( int i = 0; i < n; i++ ){
		psum[i][i] = p[i];
		for( int j = i+1; j < n; j++ ){
			psum[i][j] = psum[i][j-1]+p[j];
		}
	}
	for( int i = 0; i < n+1; i++ ){
		qsum[i][i] = q[i];
		for( int j = i+1; j < n+1; j++ ){
			qsum[i][j] = qsum[i][j-1]+q[j];
		}
	}
	for( int i = 1; i < n+1; i++ ){
		for( int j = 0; i+j < n+1; j++ ){
			dp[j][i+j] = DBL_MAX;
			for( int k = 0; k < i; k++ ){
				double tmp = dp[j][j+k]+dp[j+k+1][i+j]+psum[j][i+j-1]+qsum[j][i+j];
				dp[j][i+j] = min( dp[j][i+j] , tmp );
			}
		}
	}
	
	printf( "%f\n" , dp[0][n] );
	
	return 0;
}


Measured memory_bytes: 7740
#include <bits/stdc++.h>
#define ALL(A) (A).begin(),(A).end()
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
 
const ll mod = 1e9+7;
const ll INF = -1*((1LL<<63)+1);
const int inf = -1*((1<<31)+1);
 
using namespace std;
int cnt [100005];
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N,M;
    cin >> N >> M;
    vector<int> ans(N);
    vector<vector<int>> to(N),from(N);
    rep(i,N+M-1){
        int a,b;
        cin >> a >> b;
        a--;b--;
        to[a].push_back(b);
        from[b].push_back(a);
        cnt[b]++;
    }
    int parent = -1;
    rep(i,N) if(cnt[i]==0){
        parent = i;
    }
    queue<int> q;
    q.push(parent);
    ans[parent] = -1;
    int now = parent;
    while(!q.empty()){
        int now = q.front();q.pop();
        for(int i=0;i<to[now].size();i++){
            int next = to[now][i];
            if(from[next].size()==1){
                q.push(next);
                ans[next] = now;
            }else{
                for(int j=0;j<from[next].size();j++){
                    if(from[next][j]==now){
                        from[next].erase(from[next].begin()+j);
                        break;
                    }
                }
            }
        }
    }
    rep(i,N)cout << ans[i] + 1 << endl;
}

Measured memory_bytes: 12544
#include <bits/stdc++.h>    
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//using namespace __gnu_pbds; 
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb  push_back
#define show(x) cout<<(#x)<<" : "<<x<<endl;
#define ll  long long
#define ld  long double
#define fill(a,val) memset(a,val,sizeof(a))
#define mp  make_pair
#define ff  first
#define ss  second
#define pii pair<ll,ll>
#define sq(x) ((x)*(x))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define endl "\n"
#define int long long 
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const ll MOD     = 1000*1000*1000+7;
const ll INF     = 1ll*1000*1000*1000*1000*1000*1000 + 7;
const ll MOD2    = 998244353;
const ll N       = 1000 * 100 + 10;
const ll N2      = 70;
const ld PI  = 3.141592653589793;
//template<class T>using onset=tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);} 
ll power(ll x,ll y,ll p = LLONG_MAX ){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
ll lcm(ll a , ll b){return (a*b)/gcd(a,b);}
void solve(){
  #ifndef ONLINE_JUDGE    
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
  #endif
}
signed main()
{
    fastio();
    //cout<<fixed<<setprecision(20);
    //CHECK for LONG LONG and LONG DOUBLE
    //*comment for all except cc/cf   
    ll n,k; 
    cin>>n>>k; 
    ll a[n];
    for(ll i=0;i<n;i++){
      cin>>a[i];
    }
    sort(a,a+n);
    ll s=0;
    for(ll i=0;i<k;i++){
      s+=a[i];
    }
    cout<<s;
    //printclock;
    return 0;
}
    

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

class Cube{
public:
 int f[6];
 Cube(){}
  void roll_z(){ roll(1, 2, 4, 3);}//
  void roll_y(){ roll(0, 2, 5, 3);}// to W
  void roll_x(){ roll(0, 1, 5, 4);}// to N
  void roll(int i, int j, int k, int l){
   int t =f[i]; f[i] = f[j]; f[j] = f[k]; f[k]= f[l]; f[l]=t;
  }
  void move(char ch){
   if(ch=='E')for (int i= 0; i<3; i++) roll_y();
   if(ch=='W') roll_y();
   if(ch=='N') roll_x();
   if(ch=='S') for(int i=0; i<3; i++)roll_x();
}
};

int main(){
 Cube c;
 string com;

 for(int i=0; i<6; i++) cin >> c.f[i];
 cin >> com;
 for(int i=0; i<com.size(); i++) c.move(com[i]);
 cout << c.f[0] << endl;
return 0;
}


Measured memory_bytes: 3140
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define GYOU_MAX 256


int main(void) {

	int K, S;
	scanf("%d%d", &K, &S);

	int count = 0;
	int z;
	for (int i = 0;; i++) {
		if (i > S||i > K) {
			break;
		}
		for (int j = 0;; j++) {
			if (i + j > S||j > K) {
				break;
			}
			z = S - i - j;
			if (z >= 0 && z <= K) {
				//printf("%d %d %d\n", i, j, z);
				count++;
			}
		}
	}
	printf("%d\n", count);

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#pragma optimize("-O3")
#define int long long int
#define pb push_back
#define f first
#define s second
#define endl '\n'

main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int x;
	cin>>x;
	if(x>=30){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, a, b, c, d;
  string result = "No";
  cin >> N;
  a = N/1000; b = (N/100)%10; c = (N/10)%10; d = N%10;

  if ((a==b && b==c) || (b==c && c==d))
    result = "Yes";

  cout << result << endl;
}

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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    int a[n];
    int cnt=0;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        if(i%2 and a[i]%2) cnt++;
    }
    cout<<cnt<<"\n";
	return 0;
}

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

int main() {
  int x,t;cin>>x>>t;
  int ans = max(x-t,0);
  cout << ans << endl;
}


Measured memory_bytes: 384
#include <stdio.h>
 
int main(){
 
    int a, b, c, d;
    
    printf("\n");
    scanf("%d%d%d%d", &a, &b, &c, &d);
  

     if(b>c&&d>a){
            if(b>c){
                if(b<d){
                    if(a>c){
                        printf("%d", b-a);
                    }
                    else{
                        printf("%d", b-c);
                    }
                }
                else{
                    if(a>c){
                        printf("%d", d-a);
                    }
                    else{
                        printf("%d", d-c);
                    }
                }
            }
            else if(d>a)
            {
               if(b<d){
                    if(a<c){
                        if(b>c){
                            printf("%d", b-c);
                        }
                        else{
                            printf("0");
                        }
                    }
                    else{
                        if(a<c){
                            printf("%d", d-a);
                        }
                        else{
                            printf("%d", d-c);
                        }
                    }
                }//...
                else{//d>a이면서 b=>d
                    if(a>c){
                        printf("%d", d-a);
                    }
                    else{
                        printf("%d", d-c);
                    }
                }
            }
        }
        else{
            printf("0");
        }

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
string sa,sb;
int f[3030][3030],p[3030][3030][2],ans[3030],cnt;
void print(int i,int j)
{
	if(i==-1 || j==-1)
		return ;
	print(p[i][j][0],p[i][j][1]);
	if(sa[i]==sb[j])
		ans[cnt++]=i;
}
int main()
{
	cin>>sa>>sb;
	for(int i=0;i<sa.size();i++)
	{
		for(int j=0;j<sb.size();j++)
		{
			if(sa[i]==sb[j])
			{
				f[i][j]=f[i-1][j-1]+1;
				p[i][j][0]=i-1,p[i][j][1]=j-1;
			}
			else
			{
				if(f[i-1][j]>=f[i][j-1])
				{
					f[i][j]=f[i-1][j];
					p[i][j][0]=i-1,p[i][j][1]=j;
				}
				else
				{
					f[i][j]=f[i][j-1];
					p[i][j][0]=i,p[i][j][1]=j-1;
				}
			}
		}
	}
	print(sa.size()-1,sb.size()-1);
	for(int i=0;i<cnt;i++)
		cout<<sa[ans[i]];
	cout<<endl;
	return 0;
}

Measured memory_bytes: 107648
N = int(input())
 
def query(x):
    print(x, flush=True)
    response = input()
    if response == "Vacant":
        exit()
    return response
 
lb = 0
ub = N - 1

l_query = query(lb)
u_query = query(ub)

while True:
    m = (lb + ub) // 2
    m_query = query(m)
    if (m_query == l_query) == (m % 2 == lb % 2):
        lb = m
        l_query = m_query
    else:
        ub = m

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

int stx, sty, x, y;
string s;
vector<int> v;
bool dp1[2][36000], dp2[2][36000];

int main() {
    ios::sync_with_stdio(false);
    cin >> s >> x >> y;
    int i;
    for (i = 0; i < s.length(); i++) {
        if (s[i] != 'F') {
            break;
        } else {
            stx++;
        }
    }
    for (; i < s.length(); i++) {
        if (s[i] == 'F') {
            if (i == 0 || s[i - 1] == 'T') {
                v.push_back(1);
            } else {
                int tmp = v.back();
                v.pop_back();
                v.push_back(tmp + 1);
            }
        } else if (i > 0 && s[i - 1] == 'T') {
            v.push_back(0);
        }
    }
    int cur1 = 0, cur2 = 0;
    dp1[cur1][stx + 16000] = true;
    dp2[cur2][sty + 16000] = true;
    for (int i = 0; i < v.size(); i++) {
        if (i % 2 == 1) {
            cur1 = 1 - cur1;
            for (int j = 0; j <= 32000; j++) {
                dp1[cur1][j] = false;
            }
            for (int j = 0; j + v[i] <= 32000; j++) {
                if (dp1[1 - cur1][j]) {
                    dp1[cur1][j + v[i]] = true;
                }
            }
            for (int j = v[i]; j <= 32000; j++) {
                if (dp1[1 - cur1][j]) {
                    dp1[cur1][j - v[i]] = true;
                }
            }
        } else {
            cur2 = 1 - cur2;
            for (int j = 0; j <= 32000; j++) {
                dp2[cur2][j] = false;
            }
            for (int j = 0; j + v[i] <= 32000; j++) {
                if (dp2[1 - cur2][j]) {
                    dp2[cur2][j + v[i]] = true;
                }
            }
            for (int j = v[i]; j <= 32000; j++) {
                if (dp2[1 - cur2][j]) {
                    dp2[cur2][j - v[i]] = true;
                }
            }
        }
    }
    if (dp1[cur1][x + 16000] && dp2[cur2][y + 16000]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 512
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//実行時間制約2秒では２×10^8回くらいまで計算できる



int main() {
  ll n,k;
  cin>>n>>k;
  ld sum = 0.0;
  
  vector<ll> ni={1};
  repo(i,20){
  ni.pb((1<<i));
  }
  
  repo(i,n+1) {
    if(i>=k) sum+=1.0;
    else {
      for(ll x:ni){
        if(x*i>=k) {
        sum+=(ld)1/x;
        break;
        }
      }
    }
  }
  
  cout << fixed << setprecision (20);
  cout << (ld)sum/n << endl;
}

Measured memory_bytes: 256
from math import ceil
from collections import defaultdict

h, w = map(int, input().split())
s = [input() for _ in range(h)]

n = h * w
INF = 100 * 100

dp = defaultdict(lambda: INF)
if s[0][0] == "#":
    dp[(1, 1, 1)] = 1
else:
    dp[(1, 1, 0)] = 0

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i-1][j-1] == "#":
            dp[(i, j, 1)] = min(dp[(i, j, 1)], dp[(i-1, j, 0)] + 1, dp[(i-1, j, 1)], dp[(i, j-1, 0)] + 1, dp[(i, j-1, 1)])
        else:
            dp[(i, j, 0)] = min(dp[(i, j, 0)], dp[(i-1, j, 0)], dp[(i-1, j, 1)] + 1, dp[(i, j-1, 0)], dp[(i, j-1, 1)] + 1)

idx = 1 if s[h-1][w-1] == "#" else 0
ans = dp[(h, w, idx)]
ans = ceil(ans / 2)
print(ans)


Measured memory_bytes: 5748
//ΔARC093D
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 50;
int f[111][55];
int main()
{
	int a,b,i,j;
	for(i=1;i<=N;i=i+1)
		for(j=1;j<=N;j=j+1)
			f[i][j]=1;
	cout<<"100 50\n";
	cin>>a>>b;
	a--,b--;
	for(i=1;a&&i<=N;i=i+1)
		for(j=1;a&&j<=N;j=j+1)
			if(i&j&1)
				f[i][j]=0,a--;
	for(i=N+N;b&&i>N;i=i-1)
		for(j=1;b&&j<=N;j=j+1)
			if(i&j&1)
				f[i][j]=1,b--;
	for(i=1;i<=N+N;i=i+1){
		for(j=1;j<=N;j=j+1){
			if(f[i][j])
				cout<<'#';
			else
				cout<<'.';
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}
template<class A,size_t N,class T>void Fill(A(&a)[N],const T&v){fill((T*)a,(T*)(a+N),v);}

const int MOD = 1e9+7; //998244353;

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m=MOD){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m=MOD){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}
//V<ll>Fac,Rac;void setF(int n,int m=MOD){Fac=Rac=V<ll>(++n);Fac[0]=1;FOR(i,1,n)Fac[i]=Fac[i-1]*i%m;Rac[n-1]=modInv(Fac[n-1],m);FORR(i,n-1,1)Rac[i-1]=Rac[i]*i%m;}
//ll comb(int a,int b,int m=MOD){return a<b||b<0?0:Fac[a]*Rac[b]%m*Rac[a-b]%m;}

const int IINF = 1e9+6;
const ll LINF = 1e18;
const int N = 1e5;
int t, a[6], d;
ll n;
map<lll, lll> m;
lll f(lll e){
  if(!e || m[e]) return m[e];
  lll g = e*d, ee;
  for(int h:{2,3,5}){
    ee = e/h;
    mins(g, f(ee)+(e-ee*h)*d+a[h]);
    ee = (e+h-1)/h;
    mins(g, f(ee)+(ee*h-e)*d+a[h]);
  }
  return m[e] = g;
}

main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> t;
  FOR(_, 0, t){
    cin >> n >> a[2] >> a[3] >> a[5] >> d;
    m.clear();
    m[1] = d;
    cout << ll(f(n)) << endl;
  }
}

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

template<typename T>
bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

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

	int a=in(),b=in();
	cout << ((b-a)*(b-a-1)/2-a) << endl;
	return 0;
}


Measured memory_bytes: 256
//To debug :  g++ -g file.cpp -o code
//to flush output : fflush(stdout) or cout.flush()
//cout<<setprecision(p)<<fixed<<var
//use 1LL<<i to for 64 bit shifting , (ll)2 because by default 2 is ll
 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(i=a;i<n;++i)
#define irep(i,n,a) for(i=n;i>a;--i)
#define mod 1000000007
#define pb push_back
#define big 9223372036854775807
#define big1 LONG_MAX
#define big2 ll_MAX
#define big3 1000000000
#define sma1 LONG_MIN
#define sma2 ll_MIN
#define sma3 -1000000000
#define mp make_pair
#define dub double
#define ivec vector<ll>
#define lvec vector<long long>
#define cvec vector<char>
#define svec vector<string>
#define mt make_tuple
#define MOD 998244353
#define pi acos(-1.0)
/*
#define ss second.second
#define ff first.first
#define f first
#define s second
#define sf second.first
#define fs first.second*/
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)


int main()
{

    int v,i;

    rep(i,1,6)
    {
        cin>>v;

        if(v==0)
        {
            cout<<i;
            return 0;
        }

    }




    return 0;
}

Measured memory_bytes: 3628
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

double prob[3007];
double dp[3007], dp_next[3007];
int main()
{
    int N;
    scanf("%d\n",&N);
    for(int i=1; i<=N; i++){ scanf("%lf ",&prob[i]); }

    dp[0]=1.0;
    for(int i=1; i<=N; i++)
    {
        dp_next[0]=dp[0]*(1.0-prob[i]);
        for(int k=1; k<=N; k++)
        {
            dp_next[k]=dp[k-1]*prob[i]+dp[k]*(1.0-prob[i]);
        }
        for(int k=0; k<=N; k++)
        {
            dp[k]=dp_next[k];
        }
    }

    double res=0;
    for(int i=(N+1)/2; i<=N; i++){ res+=dp[i]; }
    printf("%.10lf\n",res);

    return 0;
}

Measured memory_bytes: 256
S = [digit for digit in input()]
s_len = len(S)

pattern1 = [str(i % 2) for i in range(s_len)]
pattern2 = [str(1) if i % 2 == 0 else str(0) for i in range(s_len)]


def get_diff_num(pattern, compared):
    diff_num = 0
    for p, c in zip(pattern, compared):
        if not p == c:
            diff_num += 1
    return diff_num

p1_diff = get_diff_num(pattern1, S)
p2_diff = get_diff_num(pattern2, S)
print(min(p1_diff, p2_diff))

Measured memory_bytes: 16536
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
const long double eps = 1e-12;
#define LONG_INF 1e18
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define MOD 998244353LL
#define seg_size 262144*2
#define REP(a,b) for(long long a = 0;a < b;++a)
int n;
string s;
long long gogo[20000];
int solve(int len) {
	long long dying = 1;
	long long gekoa = 1;
	int itr = 0;
	long long now = 0;
	long long aa = 0;
	for (int q = 0; q < s.length(); ++q) {
		now *= 26LL;
		now += s[q] - 'a';
		now %= MAX_MOD;
		aa *= 26LL;
		aa += s[q] - 'a';
		aa %= MOD;
		if (q >= len) {
			now += (MAX_MOD - ((dying * (s[q - len] - 'a') % MAX_MOD))) % MAX_MOD;
			now %= MAX_MOD;
			aa += (MOD - ((gekoa * (s[q - len] - 'a') % MOD))) % MOD;
			aa %= MOD;
		}
		else {
			dying *= 26LL;
			dying %= MAX_MOD;
			gekoa *= 26LL;
			gekoa %= MOD;
		}
		if (q >= len - 1) {
			gogo[itr] = now * MOD + aa;
			itr++;
		}
	}
	set<long long> nya;
	for (int i = itr - len - 1; i >= 0; --i) {
		nya.insert(gogo[i + len]);
		if (nya.find(gogo[i]) != nya.end()) return true;
	}
	return false;
}
int main() {
	cin >> n >> s;
	int bot = 0;
	int top = s.length();
	while (top - bot > 1) {
		int mid = (top + bot) / 2;
		if (solve(mid) == true) {
			bot = mid;
		}
		else top = mid;
	}
	cout << bot << endl;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
signed main(){
    ll x;cin>>x;
    ll a,b;
    REP(i,-120,120){
        REP(j,-120,120){
            if(i*i*i*i*i-j*j*j*j*j==x)a=i,b=j;
        }
    }
    cout<<a<<' '<<b<<endl;
}

Measured memory_bytes: 3636
import sys
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))

ave = np.sum(a)/n
x = np.abs(a-ave)
m = np.min(x)
for i,s in enumerate(x):
    if s==m:
        print(i)
        sys.exit()

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

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

	int n;
	cin >> n;

	vector<int> arr(n);
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}

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

	double ans = (arr[0] + arr[1]) / 2.0;
	for (int i = 2; i < n; ++i) {
		ans = (ans + arr[i]) / 2.0;
	}

	cout.precision(30);
	cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1e9
#define MOD 1e9+7
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort(ALL(x))
#define SORTR(x) reverse(ALL(x))
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORR(i,a,b) for(ll i=(a);i>=(b);i--)
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define COUT(x) cout<<(x)<<endl
void CIN(){} template <class Head,class... Tail>
void CIN(Head&& head,Tail&&... tail){cin>>head;CIN(move(tail)...);}
#define ICIN(...) int __VA_ARGS__;CIN(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CIN(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CIN(__VA_ARGS__)
#define VECCIN(x) for(auto&youso_: (x))cin>>youso_
#define VECCOUT(x) for(auto&youso_: (x))cout<<youso_<<" ";cout<<endl
template <class T = ll> T IN(){T x;cin>>x;return (x);}
#define YES(n) cout << ((n)?"YES":"NO") << endl
#define Yes(n) cout << ((n)?"Yes":"No") << endl
#define SANKOU(n,a,b) cout << ((n)?(#a):(#b)) << endl
#define dump(x) cout << #x << " = " << (x) << endl;

int main(){
	ICIN(P, Q, R);
	COUT(P+Q+R-max(max(P, Q), R));
}


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

using namespace std;

using ll = int64_t;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = INT_MAX;
constexpr ll L_INF = LLONG_MAX;

//===


using Graph = std::vector<std::vector<int>>;


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

	int N, M;
	cin >> N >> M;
	Graph g(N);
	Vi indeg(N);
	for (int i = 0; i < N - 1 + M; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		g[a].push_back(b);
		++indeg[b];
	}

	Vi ans(N);

	stack<int> st;
	for (int i = 0; i < N; ++i) {
		if (indeg[i] == 0) {
			st.push(i);
			ans[i] = 0;
			break;
		}
	}

	while (!st.empty()) {
		int u = st.top();
		st.pop();
		for (const auto& to : g[u]) {
			--indeg[to];
			if (indeg[to] == 0) {
				ans[to] = u + 1;
				st.push(to);
			}
		}
	}

	for (const auto& ansi : ans) {
		cout << ansi << "\n";
	}


	return 0;
}

Measured memory_bytes: 7040
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mod 1000000007
#define ff first
#define ss second
using namespace std;
/*ll power(ll x,ll y)
{
    ll res=1;
    while(y>0)
    {
        if(y%2==1)
            res=(res*x)%mod;
        x=(x*x)%mod;
        y=y/2;
    }
    return res;
}*/
int main()
{
ll n,c=0;
cin>>n;
ll i;
for(i=1;i<=n;i++)
{
   ll r=0,a=i;
    while(a)
    {
        a=a/10;
        r++;
    }
    if(r%2==1)
        c++;
}
cout<<c<<endl;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)


Measured memory_bytes: 494360
MOD = 10 ** 9 + 7
n = int(input())
s1 = input()
s2 = input()

if s1[0] == s2[0]:
    ans = 3
    pos = 1
else:
    ans = 6
    pos = 2

while pos < n:
    if s1[pos] == s2[pos]:
        if s1[pos - 1] == s2[pos - 1]:
            ans *= 2
            ans %= MOD
        pos += 1
    else:
        if s1[pos - 1] == s2[pos - 1]:
            ans *= 2
        else:
            ans *= 3
        pos += 2
        ans %= MOD
print(ans)


Measured memory_bytes: 9144