akhauriyash/Code-Regression huggingface dataset:
n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)

tl = Array.new(n,0)
tl[0] = 1
nxt = a[0]
for i in 1..(n-1)
  tl[i] = nxt
  nxt = a[nxt-1]
end
ck = Array.new(n+1,0)
en = n-1
for i in 0..(n-1)
  if ck[tl[i]] == 0
    ck[tl[i]] += 1
  else
    lps = tl[i]
    en = i-1
  end
end

mg = 0
if en != n-1
  for i in 0..en
    if tl[i] == lps
      break
    else
      mg += 1
    end
  end
end

if k <= n-1
  puts tl[k]
else
  puts tl[mg + (k-mg) % (en+1-mg)]
end

Measured memory_bytes: 30404
#include<cstdio>
#define r(i,n) for(int i=0;i<n;i++)
int a[999][8],n,t,d[99];char s[999];main(){scanf("%d%s",&n,s);a[0][1]=d[79]=1;d[73]=2;r(i,n)r(j,8)r(k,8)if(j&k&&k>>d[s[i]]&1)a[i+1][k]+=a[i][j]%10007;r(i,8)t+=a[n][i];printf("%d\n",t%10007);}

Measured memory_bytes: 1056
import sys
input = sys.stdin.readline
from collections import deque
N=int(input())
table=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u,v=u-1,v-1
    table[u].append((v,w))
    table[v].append((u,w))
visit=[-1]*N
H=deque()
H.append(0)
visit[0]=0
while H:
    x=H.popleft()
    for y,w in table[x]:
        if visit[y]==-1:
            visit[y]=(visit[x]+w)%2
            H.append(y)
for i in range(N):
    print(visit[i])

Measured memory_bytes: 67632
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<cstring>
#include<sstream>
using namespace std;

typedef long long ll;

int main() {
  int A,B; cin >> A >> B;
  int ans= 0;
  if ( A == B ) {
    ans = A+B;
  } else if ( A < B ) {
      ans = B+B-1;
      
  } else if ( A > B ) {
    ans = A+A-1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define MAX_V 100005



int main(void){
	ll a,b;
	cin>>a>>b;
	ll ans = 0;
	if(a%2 == 1){
		ans ^= a;
		ans ^= 1;
	}
	if(b%2 == 0){
		ans ^= b;
	}
	a += 4 * (ll)((b-a)/ 4);
	while(a!=b+1){
		ans ^= a%2;
		a++;
	}
	cout<<ans<<endl;

	return 0;
}

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

int main(void){
	int H,W,D;
            int temp;
	cin>>H>>W>>D;
	int A[90000],dist[D][H*W/D+1];
	for(int i=0;i<H;i++){
    	for(int j=0;j<W;j++){
          cin>>temp;
      	  A[temp] = i*300+j;
        }
    }
    for(int i=0;i<D;i++){
        int cnt = 1;
        dist[i][0] = 0;
    	for(int j=i+D;j<H*W+1;j+=D){
          dist[i][cnt] = abs(A[j-D]/300-A[j]/300)+abs(A[j-D]%300-A[j]%300)+dist[i][cnt-1];
          cnt++;
        }
    }
  	int Q;
    cin>>Q;
	for(int i=0;i<Q;i++){
      int L,R;
      cin>>L>>R;
      cout<<dist[R%D][R/D]-dist[L%D][L/D]<<endl;
    }
}


Measured memory_bytes: 1792
from itertools import combinations_with_replacement

def main():
    N,M,Q=map(int,input().split())
    abcd_lst=[list(map(int,input().split())) for _ in range(Q)]
    num=list(range(1,M+1))
    ans=0
    for A in list(combinations_with_replacement(num, N)):
        tmp=0
        for ai,bi,ci,di in abcd_lst:
            if A[bi-1]-A[ai-1]==ci:
                tmp+=di
                ans=max(ans,tmp)
    print(ans)

main()


Measured memory_bytes: 21628
#include <cstdio>
#include <cstring>
#include <iostream>

#define int long

using namespace std;

const int MAX_D = 101;
const int MAX_N = 10;
const int MAX_S = 1000;
int memo[MAX_D + 1][MAX_N + 1][MAX_S + 1];

int sum_of_integers(int d, int n, int s)
{
	if (memo[d + 1][n][s] != -1) return memo[d + 1][n][s];
	if (n == 0) return s == 0;
	if (s < 0) return 0;
	int res = 0;
	for (int i = d + 1; i <= 100; i++) res += sum_of_integers(i, n - 1, s - i);
	return memo[d + 1][n][s] = res;
}

signed main(){
	memset(memo, -1, sizeof(memo));
	int n, s;
	while (cin >> n >> s, n || s){
		cout << sum_of_integers(-1, n, s) << endl;
	}
	return 0;
}

Measured memory_bytes: 9940
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  long long t,ans=0,s[100001],g[100001],sum[100002]={};
  cin>>t>>n;
  for(int i=0;i<n;i++)
    cin>>s[i]>>g[i];
  s[n]=g[n]=(1e16);
  for(int i=1;i<=n;i++)sum[i]=sum[i-1]+g[i-1]-s[i-1];
  int j=0;
  for(int i=0;i<n;i++)
    for(;j<=n;j++)
      if(s[i]+t<s[j]){ans=max(ans,sum[j]-sum[i]);break;}
      else if(s[i]+t<g[j]){ans=max(ans,sum[j]-sum[i]+s[i]+t-s[j]);break;}
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3516
// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);
#define _GLIBCXX_DEBUG//only for debugging
#include <bits/stdc++.h>
#include <chrono>
#include <ext/rope>
#define VALHALLA ios_base::sync_with_stdio(false);cin.tie(0);cout<<fixed<<setprecision(13);
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define debug(x) std::cerr << #x << ": " << (x) << '\n';
#define sz(x) (int)x.size()
#define fast(map_name) map_name.reserve(1024);map_name.max_load_factor(0.25);
using namespace std;
using namespace __gnu_cxx;
typedef long long int ll;
typedef pair<int,int> ii;
typedef complex<double> point;
const double epsilon=1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/* VARIABLE DECLARATION START */


/*  FUCNTION TEMPLATE STARTS  HERE */

double dot(point a,point b){ return (conj(a)*b).real() ; }
double cross(point a,point b){ return (conj(a)*b).imag() ; }
double dist(point a, point b){ return abs(a-b); }
struct neal {
static uint64_t splitmix64(uint64_t x)
 {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const
 {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
}
};
struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return (size_t) x.first * 37U + (size_t) x.second;
  }
};
bool isprime(ll n) {
    if (n == 2 || n == 3) return true;
    if (n < 2 || n % 2 == 0 || n % 3 == 0) return false;
    for (ll i = 6; (i - 1) * (i - 1) <= n; i += 6) {
        if (n % (i - 1) == 0 || n % (i + 1) == 0) {
            return false;
        }
    }
    return true;
}
inline ll exp(ll a, ll b, ll mod) {
    ll n = 1;
    ll p = a;
    while (b > 0) {
        if (b % 2 == 1) {
            n *= p;
            n %= mod;
        }
        p *= p;
        p %= mod;
        b /= 2;
    }
    return n;
}

inline bool comp(double a,double b)
{
  return (fabs(a-b)<epsilon);
}
ll gcd(ll u, ll v) {
  ll r;
  while (0 != v) {
    r = u % v; u = v; v = r;
  }
  return u;
}

/*  FUCNTION TEMPLATE ENDS HERE */
int main()
{
   VALHALLA
   int n,l;
   cin>>n>>l;
   vector<string> v(n);
   for(int i=0;i<n;++i)
   {
    cin>>v[i];
   }
   sort(all(v));
   for(auto &x:v)
   {
    cout<<x;
   }
   cout<<endl;
   
   
   


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
template<typename T> using V = vector<T>;
using ll = long long;
using Vi = V<int>;  using VVi = V<Vi>;
template<typename T> inline int sz(T &x) { return x.size(); }
inline int cLog2(const ll x) { assert(x > 0); return (x == 1) ? 0 : 64-__builtin_clzll(x-1); } // ceil(log2(x))
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;


using mint = modint998244353;
using Vm = V<mint>; using VVm = V<Vm>;
istream &operator>>(istream &is, mint &a) { int v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const mint &a) { return os << a.val(); }


template<typename T> struct Factorial {
  int MAX;
  vector<T> fac, finv;
  Factorial(int m = 1) : MAX(m), fac(m+1, 1), finv(m+1, 1) {
    rep2(i, 2, MAX+1) fac[i] = fac[i-1] * i;
    finv[MAX] /= fac[MAX];
    drep2(i, MAX+1, 3) finv[i-1] = finv[i] * i;
  }
  T binom(int n, int k) {
    if (k < 0 || n < k) return 0;
    return fac[n] * finv[k] * finv[n-k];
  }
  T perm(int n, int k) {
    if (k < 0 || n < k) return 0;
    return fac[n] * finv[n-k];
  }
};
Factorial<mint> fc;


int main() {
  int n; cin >> n;
  fc = Factorial<mint>(2*n+2);
  Vi cnt(int(1e5)+10);
  rep(i, 2*n) {
    int h; cin >> h;
    ++cnt[h];
  }
  Vi c;
  for (auto e : cnt) if (e) c.push_back(e);
  int m = sz(c);

  Vm dfc(n+1, 1);
  rep(i, n) dfc[i+1] = dfc[i] * (2*i+1);

  int M = 1<<cLog2(m);
  VVm p(2*M, Vm(1, 1));
  rep(i, m) {
    int b = c[i] / 2;
    p[M+i].assign(b+1, 0);
    rep(j, b+1) p[M+i][j] = dfc[j] * fc.binom(c[i], 2*j);
  }

  drep2(i, M, 1) p[i] = convolution(p[2*i], p[2*i+1]);

  mint ans = 0;
  rep(i, sz(p[1])) {
    mint res = p[1][i] * dfc[n-i];
    if (i&1) ans -= res;
    else ans += res;
  }

  cout << ans << '\n';
}


Measured memory_bytes: 19444
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>   
#include <stdio.h>    
 
using namespace std;
     
#define F first
#define S second
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define al 0x3F3F3F3F
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;
const int N = (int)2e5 + 123;
const ll inf = (ll)3e18 + 1;

const double pi = acos (-1.0);
const double eps = 1e-7;
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int w, h, x, y;

inline void boost () {                    
   ios_base :: sync_with_stdio (NULL);
   cin.tie (NULL), cout.tie (NULL);          
}                                                     

inline void Solve () {
   cin >> w >> h >> x >> y;
   cout << fixed << setprecision (9) << 1.0 * w * h / 2.0 << ' ' << (w % 2 == 0 && h % 2 == 0 && w / 2 == x && h / 2 == y);

}                                     

main () {                                       
// freopen (".in", "r", stdin);    
// freopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
// cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}


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

int main(){
  int a[4],b[4];
  int hit,blow;

  while(cin>>a[0]>>a[1]>>a[2]>>a[3]){
    cin>>b[0]>>b[1]>>b[2]>>b[3];
    hit = blow = 0;

    for(int i=0;i<4;i++)
      if(a[i] == b[i])
	hit++;
    for(int i=0;i<4;i++)
      for(int j=0;j<4;j++)
	if(a[i] == b[j])
	  blow++;

    blow -= hit;

    cout << hit << ' ' << blow << endl;
  }


  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  double n; cin >> n;
  double count = 0;
  double ans = 0;
  for(int i = 1;i < n+1;i++){
    if(i % 2 == 1){
      count++;
    }
  }
  ans = count / n;
  cout << ans << endl;
}


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

#define F first
#define S second
#define vsort(v) sort((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;

int main(int argc, const char * argv[]) {
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b) {
        cout << c << endl;
    }else if(a == c){
        cout << b << endl;
    }else{
        cout << a << endl;
    }
    return 0;
}


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

#define FOR(i, a, b) for (int (i) = (a); (i) < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " " << x << endl
#define eb emplace_back
#define _ << " " <<
typedef long long ll;
typedef std::pair<int, int> ii;
#define X first
#define Y second
#define double long double
typedef double db;
using namespace std;

const int MaxN = 200100;
const int Mod = 1e9 + 7;

int N;
int a[MaxN];

void solve() {
  sort(a, a + N);
  int mid = a[N / 2];
  ll ret = 0;
  REP(i, N) ret += abs(a[i] - mid);
  cout << ret << endl;
}

void load() {
  cin>>N;
  REP(i, N) { cin>>a[i]; a[i] -= (i + 1); };
  
}

int main(){
  ios_base::sync_with_stdio(false);
  load();	
  solve();
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int table[512][512];

int vy[] = {0, -1};
int vx[] = {1, 0};

int main() {
    int h, w; cin >> h >> w;

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

    vector<string> vc;

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (table[i][j] % 2 == 0) continue;
            for (int k = 0; k < 2; ++k) {
                if (i - vy[k] < 0 || i - vy[k] >= h) continue;
                if (j + vx[k] < 0 || j + vx[k] >= w) continue;
                ++table[i - vy[k]][j + vx[k]];
                --table[i][j];
                string str = to_string(i+1) + " " + to_string(j+1) + " " + to_string(i - vy[k] + 1) + " " + to_string(j + vx[k] + 1);
                vc.push_back(str);
                break;
            }
        }
    }

    cout << vc.size() << endl;
    for (string str: vc) cout << str << endl;

    return 0;
}

Measured memory_bytes: 6128
// Gaurav Aggarwal

/*
useful stl
array<ll,size> ar;         //size(),front(),back(),fill(),empty()
deque<ll> d                //push_back(),push_front(),pop_front(),pop_back()
vector<ll> v(size,val);    //push_back(),*max_element(v.begin(),v.end()),accumulate(v.begin(),v.end(),0)
stack<ll> g;               //push(),pop(),top(),size(),empty()         LIFO
queue<ll> q;               //push(),size(),front(),back(),empty()      FIFO
priority_queue<ll> pq
*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> ipair;
typedef pair<long,long> lpair;
#define scan(x) do{while((x=getchar_unlocked())<'0'); for(x-='0'; '0'<=(_=getchar_unlocked()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define For(i, a, b) for(__typeof (a) i=a; i<=b; i++)
#define mod 1000000007
#define PI 3.141592653589793238462643383279502884 
#define debug1(a) cout<<a<<"\n";
#define debug2(a,b) cout<<a<<" "<<b<<"\n";
#define debug3(a,b,c) cout<<a<<" "<<b<<" "<<c<<"\n";
#define debug_arr(a,n) {for(__typeof (n) i=0; i<n; ++i) {cout<<a[i]<<" ";}}
#define inp_arr(a,n) for(__typeof (n) i=0; i<n; ++i) {cin>>a[i];}
#define beg_arr(a,n) for(__typeof (n) i=0; i<n; ++i) {a[i] = 0;}

ll power(ll x, ll y) 
{ 
    ll res = 1;   
    while (y > 0) { 
        if (y & 1) 
            res = (res*x)%mod; 
        y = y>>1;
        x = (x*x)%mod; 
    } 
    return res%mod; 
}

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

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

    int n;
    cin>>n;
    string a,b,c;
    cin>>a>>b>>c;
    ll ans = 0;
    for(int i=0;i<n;++i) {
        if(a[i] != b[i] and b[i]!=c[i] and c[i] != a[i])
            ans += 2;
        else if(a[i] == b[i] and b[i] == c[i])
            ans += 0;
        else
            ans += 1;
    }
    cout<<ans;

    return 0;
}

Measured memory_bytes: 256
N_,K = map(int,input().split())
A = sorted(list(map(int,input().split())))
mod = int(1e9+7)
if N_ == 1 or N_ == 2:
    print(0)
    exit()

"""
https://www.planeta.tokyo/entry/5195/
"""
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10**9+7
N = 10**5+1  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0
for i in range(N_):
    ans += cmb(i,K-1,mod)*A[i]

for j in range(N_):
    ans -= cmb(N_-j-1,K-1,mod)*A[j]

print(ans%mod)

Measured memory_bytes: 21196
n, m, x, y = map(int, input().split())
x_list = [int(i) for i in input().split()]
y_list = [int(i) for i in input().split()]
x_list.append(x)
y_list.append(y)
max_x = max(x_list)
min_y = min(y_list)
if (min_y - max_x) > 0:
    print("No War")
else:
    print("War")

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
	string s;
	cin>>s;
	cout<<(((s.size()%2)^(s[s.size()-1]==s[0]))?"First":"Second")<<endl;
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#define int long long
using namespace std;
 
int n, k;
 
signed main() {
	int j, i;
	int ans = 0;
	
	cin >> n >> k;
	for (j = 2; j <= 6; j++) {
		for (i = 2; ; i++) {
			int num = (i * 7 + j - 7);
			int ssum = num * 9;
			if (ssum % 11 == k) break;
		}
		if (i >= n) continue;
		ans += (n - 1 - i) / 11 + 1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

template<typename V>
void rotate(const V &s, V &t) {
  if (!s.size()) return;
  int h = s[0].size(), w = s.size();
  rep(i, h) rep(j, w) t[j][h - i - 1] = s[i][j];
}

void solve() {
  vs s(8);
  rep(i, 8) cin >> s[i];
  loop(i, 1, 4) {
    cout << i * 90 << endl;
    vs t(8, string(8, ' '));
    rotate(s, t);
    s = t;
    rep(i, 8) cout << s[i] << endl;
  }
}

Measured memory_bytes: 3116
#include <cstdio>
#include <iostream>
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
using namespace std;

int main() {
	int n;
	int i = 1;
	while(scanf("%d", &n), n) {
		cout << "Case " << i << ": " << n << endl;
		i++;
	}
	return 0;
}

Measured memory_bytes: 1208
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>

#define INF (1ll<<60)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;

#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)

template<class T>bool umax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool umin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using namespace std;

// gcd
int gcd(int a, int b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}
// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);

    return result;
}

// sort big to small
// sort(A,A+N, greater<int>());

// v.front() = -BOUND;
// v.back() = BOUND;

// Iterator
// v.begin
// v.end

int main() {
    string ans="Yes";
    long long N;
    long long digit_sum=0;
    cin >> N ;
    long long temp=N;
    
    while(temp>0){
        digit_sum+=temp%10;
        temp/=10;
    }

    if(N%digit_sum) ans="No";
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
//#include <bits/stdc++.h>
using namespace std;
 
int main() {
    vector<int> arr(4);
    for(int i = 0;i < 4; i++) {
        cin >> arr[i];
    } 

    int a = arr[0];
    int b = arr[1];
    int c = arr[2];
    int k = arr[3];

    int ans = 0;

    if(k <= a) {
        cout << k << '\n';
        return 0;
    } else {
        ans += a;
        k -= a;
    }

    if(k <= b) {
        cout << ans << '\n';
        return 0;
    } else {
        k -= b;
    }

    ans -= k;
    cout << ans << '\n';
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char a[100];
	cin>>a;
	int c=0;
	for(int i=0;i<strlen(a);i++)
	{
		if((i+1)%2==1){
		if(a[i]=='R' || a[i]=='U' || a[i]=='D')
			c+=1;
	
	}
	
	if((i+1)%2==0)
	{
	if(a[i]=='L' || a[i]=='U' || a[i]=='D')
	c+=1;

}
}
if(c==strlen(a))
	cout<<"Yes";
else
cout<<"No";
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define MIN(a,b) ((a) < (b) ? (a) : (b))
struct node {
  int id;
  int cap;
  struct node *next;
};
struct node **list;
int **flow, *visit, *delta, *prev, *queue;
void Insert(int, int);
int Maxflow(int, int, int);
int main(void)
{
  int i, x, y, v, e, s, t, maxflow = 0;
  scanf("%d %d %d", &x, &y, &e);
  v = x + y + 2;
  list = (struct node**)malloc(sizeof(struct node*) * v);
  flow = (int**)malloc(sizeof(int*) * v);
  visit = (int*)malloc(sizeof(int) * v);
  delta = (int*)malloc(sizeof(int) * v);
  prev = (int*)malloc(sizeof(int) * v);
  queue = (int*)malloc(sizeof(int) * v);
  for (i = 0; i < v; i++) {
    list[i] = NULL;
    flow[i] = (int*)calloc(v, sizeof(int));
  }
  for (i = 0; i < e; i++) {
    scanf("%d %d", &s, &t);
    Insert(0, s + 1);
    Insert(x + t + 1, v - 1);
    Insert(s + 1, x + t + 1);
  }
  while (Maxflow(0, v - 1, v)) {
    int n = v - 1;
    do {
      flow[prev[n]][n] += delta[v-1];
      flow[n][prev[n]] -= delta[v-1];
      n = prev[n];
    } while(n);
    maxflow += delta[v-1];
  }
  printf("%d\n", maxflow);
  for (i = 0; i < v; i++) {
    free(list[i]);
    free(flow[i]);
  }
  free(list);
  free(flow);
  free(visit);
  free(delta);
  free(prev);
  free(queue);
}
void Insert(int a, int b)
{
  struct node *p = (struct node*)malloc(sizeof(struct node));
  p->id = b;
  p->cap = 1;
  p->next = list[a];
  list[a] = p;
  p = (struct node*)malloc(sizeof(struct node));
  p->id = a;
  p->cap = 0;
  p->next = list[b];
  list[b] = p;
}
int Maxflow(int s, int t, int size)
{
  struct node *n;
  int i, reached = 0, head = 0, tail = 0;
  for (i = 0; i < size; i++) {
    visit[i] = 0;
    delta[i] = INT_MAX;
    prev[i] = -1;
  }
  visit[s] = 1;
  queue[tail++] = s;
  do {
    i = queue[head++];
    for (n = list[i]; n != NULL; n = n->next) {
      int v = n->id;
      if (!visit[v] && flow[i][v] < n->cap) {
        queue[tail++] = v;
        visit[v] = 1;
        prev[v] = i;
        delta[v] = MIN(delta[i], n->cap - flow[i][v]);
        if (v == t) reached = 1;
      }
    }
  } while (head != tail && !reached);
  return reached;
}


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

using namespace std;

using ll = long long;

bool judge(vector<int> vec, int n) {
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    if (vec.size() != n) return false;
    {
        int g = vec[0];
        for (int x : vec) g = __gcd(g, x);
        if (g != 1) return false;
    }

    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (vec[i] > 30000) return false;
        sum += vec[i];
    }

    for (int i = 0; i < n; i++) {
        if (__gcd(sum - vec[i], vec[i]) == 1) {
            cout << "ng" << endl;
            return false;
        }
    }
    return true;
}

vector<int> solve(int n) {
    vector<int> res;
    if (n == 3) {
        res = {2, 5, 63};
    } else {
        for (int i = 0; i <= 4999; i++) {
            int x = (3 * i + 1) * 2;
            if (x <= 30000) res.push_back(x);
            x = (3 * i + 2) * 2;
            if (x <= 30000) res.push_back(x);
            x = (4 * i + 1) * 3;
            if (x <= 30000) res.push_back(x);
            x = (4 * i + 3) * 3;
            if (x <= 30000) res.push_back(x);
            if (n - (int)res.size() <= 3) {
                break;
            }
        }

        int m = n - res.size();
        for (int i = 1; i <= m; i++) {
            res.push_back(6 * i);
        }
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> ans = solve(n);
    //assert(judge(ans, n));
    cout << ans[0];
    for (int i = 1; i < n; i++) {
        cout << " " << ans[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 640
N=int(input())
t=[0]
x=[0]
y=[0]
for _ in range(N):
    a,b,c=map(int,input().split())
    t.append(a)
    x.append(b)
    y.append(c)

for i in range(N):
    X=abs(x[i+1]-x[i])+abs(y[i+1]-y[i])
    T=abs(t[i+1]-t[i])
    if X>T or X%2!=T%2:
        print("No")
        break
else:
    print("Yes")


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

int main(){
  	int A,B;
	string s;
  	cin>>A>>B>>s;
  	if(s[A]!='-'){cout<<"No"<<endl;return 0;}
	for(int i=0;i<s.size();++i){
    	if(i!=A&&s[i]=='-'){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)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  ll n, k;
  cin >> n >> k;
  vector<vector<ll>> a(60, vector<ll>(n, 0));
  rep(i, n) {
    cin >> a[0][i];
    a[0][i]--;
  }

  reps1(i, 60) {
    rep(j, n) {
      a[i][j] = a[i-1][a[i-1][j]];
    }
  }

  ll now = 0;
  for(int i = 59; 0 <= i; i--) {
    ll l = (1ll << i);
    if(l <= k) {
      now = a[i][now];
      k -= l;
    }
  }

  cout << now + 1 << endl;

  return 0;
}


Measured memory_bytes: 98548
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

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

int main()
{
  string s;
  cin >> s;
  int f = stoi(s.substr(0, 2)), l = stoi(s.substr(2, 2));
  string ans = "";
  bool lm = l > 0 && l < 13;
  if (f > 0 && f < 13)
  {
    ans = lm ? "AMBIGUOUS" : "MMYY";
  } else {
    ans = lm ? "YYMM" : "NA";
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    int n;
    cin >> n;
    vvi edges(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    bool ok                     = true;
    function<int(int, int)> dfs = [&](int c, int p) {
        int tot = 0;
        for (auto &v : edges[c]) {
            if (v == p)
                continue;
            tot += dfs(v, c);
        }
        if (tot == 1) {
            return 0;
        } else if (tot == 0) {
            return 1;
        } else {
            ok = false;
            return tot;
        }
    };
    int ret = dfs(0, -1);
    if (ret != 0)
        ok = false;
    cout << (ok ? "Second" : "First") << "\n";
    return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define All(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()   //reverse
#define strall(v) (v).cbegin(),(v).cend() //const_itterator
#define IN(a, b, x) (a<=x&&x<b)
using namespace std;
using ll = long long;
using Pair = pair<int,int>;
using Graph = vector<vector<ll>>;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename t, typename u, typename Comp=less<>>
bool chmax(t& xmax, const u& x, Comp comp={}) { if(comp(xmax, x)) { xmax = x; return true; } return false;}
template<typename t, typename u, typename Comp=less<>>
bool chmin(t& xmin, const u& x, Comp comp={}) { if(comp(x, xmin)) { xmin = x; return true;} return false;}
const int INF = 1e9;
const ll infl = ll(1e18)+5;

/*
*ios::sync_with_stdio(false);
*cin.tie(0);
*/
int main(){
  int N;
  cin >> N;
  vector<ll> L(N);
  int ans = 0;
  rep(i,N) cin >> L[i];
  set<string> se;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      for(int k=j+1;k<N;k++){
        if(L[i] != L[k] && L[j] != L[k] && L[i] != L[j]){
         vector<ll> tmp = {L[i],L[j],L[k]};
         sort(All(tmp));
         if(abs(tmp[0]-tmp[1]) < tmp[2] && tmp[2] < (tmp[0]+tmp[1])){ ans++;
         }
        }
      }
    }
    
  }
  cout << ans << endl;
}


Measured memory_bytes: 3628
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
N = int(sys.stdin.readline())
S = list(map(int, sys.stdin.readline().split()))


def solve():
    counts = Counter(S)
    nums = list(sorted(counts.keys(), reverse=True))
    if counts[nums[0]] > 1:
        return False

    # 木の深さをもって深いやつから使っていく
    trees = [-i for i in range(1, N + 1)]
    heapq.heapify(trees)

    for n in nums[1:]:
        cnt = counts[n]
        if cnt > len(trees):
            return False
        uses = []
        for _ in range(cnt):
            t = -heapq.heappop(trees)
            uses.append(t)
        # 使ったら t-1 個の木に分解する
        for t in uses:
            for i in range(1, t):
                heapq.heappush(trees, -i)
    return True


if solve():
    print('Yes')
else:
    print('No')


Measured memory_bytes: 45344
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve():
    N = int(input())
    A = list(map(int, input().split()))

    for a in A:
        if a % 2 == 0:
            if a % 5 != 0 and a % 3 != 0:
                print("DENIED")
                return
    print("APPROVED")


def main():
    solve()


if __name__ == '__main__':
    main()


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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

int n;
int a[100010];
typedef pair<int, int> P;
P p[100010];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        p[i] = P(a[i], i);
    }
    sort(p + 1, p + 1 + n);
    for (int i = 1; i <= n; i++)
    {
        cout << p[i].second << endl;
    }
}


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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> v;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        v.push_back(make_pair(a, b));
    }
    sort(v.begin(), v.end());
    long long ans = 0;
    for (int i = 0; i < n && m; ++i) {
        int cnt = min(m, v[i].second);
        ans += 1ll * v[i].first * cnt;
        m -= cnt;
    }
    cout << ans << endl;
    return 0;
}


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

int main()  
{  
	int n;cin>>n;
	vector<vector<int> > act(n,vector<int>(3));
	int aa;
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			cin>>aa;
			act[i][j] = aa;
		}
	}
	
	vector<int> dp(3);
	dp[0] = act[0][0];
	dp[1] = act[0][1];
	dp[2] = act[0][2];
	
	for(int i=1;i<n;i++){
		vector<int> new_act(3,INT_MIN);
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				if(j!=k){
					new_act[k] = max(new_act[k],dp[j] + act[i][k]);
				}
			}
		}
		swap(dp,new_act);	
	} 
	 cout<<max({dp[0],dp[1],dp[2]});
	 
    return 0;  
} 


Measured memory_bytes: 5760
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <numeric>
 
using namespace std;
 
#define eb emplace_back
#define pb push_back
#define MP make_pair
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define rep(i,j,n) for (int i = j; i < n; ++i)
#define repn(i,j,n) for (int i = j; i <= n; ++i)
#define revn(i,j,n) for (int i = j; i >= n; --i)
#define sz(i) i.size()
#define mem(i,v) memset(i,v,sizeof(i))
#define all(v) v.begin(), v.end()
#define endl '\n'
#define int long long
#define INF 1e18
#define ss second
#define ff first

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
//const int mod=1e9+7;
const int mod=998244353;
const int up=1e5+10;
const int MAXN=1e6+10;
int a[2*up],b[2*up];

void solve()
{
    int n,x,y;
    cin>>n;
    repn(i,1,n)
    {
        cin>>a[i]>>b[i];
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);

    if(n%2==1)
    {
        x=a[n/2+1];
        y=b[n/2+1];
    }
    else
    {
        x=a[n/2]+a[n/2+1];
        y=b[n/2]+b[n/2+1];
    }
    cout<<y-x+1<<endl;
}


int32_t main()
{
    int t;
    t=1;
    //sieve();
    //cin>>t;
    while(t--)
    {
        solve();
    }
}



Measured memory_bytes: 6708
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include<unordered_map>

using namespace std;

int main(void)
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << min(a, b) + min(c, d) << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String S = sc.next();
        String[] splitS = S.split("", 0);
        int sum = 0;
        
        for(int i = 0; i < N; i++){
            if(i > 0){
                if(splitS[i].equals(splitS[i-1])){
                    continue;
                }
            }
            sum++;
        }
        
        System.out.println(sum);
    }
}

Measured memory_bytes: 33144
N = int(input())
leN = len(str(N))
counter = 0

for i in range(leN):
    if(i % 2 == 1):
        counter = counter + 10**(i) - 10**(i-1)

if(leN % 2 == 1):
    counter = counter + N - 10**(leN - 1) + 1

print(counter)

Measured memory_bytes: 2940
#include <stdio.h>

int main (void){
    int a,b,c;
    int i,n;
    
    scanf("%d %d %d",&a,&b,&c);
    n = 0;
    for(i=a; i<=b; i++){
        if(c % i ==0) n++;
    }
    printf("%d\n",n);
    return 0;
}


Measured memory_bytes: 2112
#include<bits/stdc++.h>
using namespace std;
int main () {
  string str;
  cin >> str;
  bool n = true;
  if ( str.size()%2 == 1 ) {
    cout << "No" << endl;
  }
  else {
    for ( int i = 0 ; i < str.size()/2 ; i+=2 ) {
      
      if ( str.at(i) == 'h' && str.at(i+1) == 'i' ){
        continue;
      }
      else {
        n = false;
      }
      i++;
    }  
    
    if (n){
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
}

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

struct range_minimum_query{

  // 管理したい元の配列のサイズ以上の2冪。

  int n;

  // セグメント木(完全二分木)を管理する一次元配列。

  vector<int> segtree;

  // minの単位元としてのINF。値は2^31-1。

  const int INF = 0;

  

  // @param sz 管理したい元の配列のサイズ

  // nをsz以上の2冪にし、セグメント木のサイズを2*n-1、値をINFに初期化する。

  range_minimum_query(int sz){

    for(n = 1; n<sz;) n <<= 1;

    segtree.assign(2*n-1,INF);
  }
    
   // 元の配列の[l,r)のminを求める。

  // @param l,r [l,r)が求めたいminの元の配列での範囲。

  // @param a,b [a,b)が現在見ている頂点の持つminの元の配列における範囲。

  // @param k   セグメント木の現在見ている頂点のindex

  // @return    セグメント木により、求められた[l,r)の最小値。

  // 上からDFSして、[l,r)内の頂点であれば自身の値を返し、そうでなければ単位元を返す。

  // このようにして帰ってきた値を全てminしたものが求めたいものである。

  // デフォルト引数にn(非staticなメンバ変数)を指定できないため、オーバーロードしている。

  int find(int l, int r){

    return find(l,r,0,n,0);

  }

  int find(int l, int r, int a, int b, int k){

    // [a,b)が[l,r)の外側なら、影響のない単位元INFを返す。

    if(b<=l || r<=a) return INF;

    

    // [a,b)が[l,r)の内側なら、その頂点は[l,r)内で最も大きい区間minを持つので、それを返す。

    else if(l<=a && b<=r) return segtree[k];

    

    // どちらでもなければ(解説スライドでの赤線を跨いでいる状態)、もっと細分されたものを確認する必要があるため、子を確認する。

    // 左側の子は[a,(a+b)/2)の区間minを持ち、indexは2*k+1

    // 右側の子は[(a+b)/2,b)の区間minを持ち、indexは2*k+2

    // この２つの[l,r)内の区間minのminを返してやれば良い。

    // 現在見ている頂点が葉に該当する場合は必ず上の２つの条件のどちらかで捕捉されるため考えなくて良い。

    else return find(l,r,a,(a+b)/2,2*k+1)+find(l,r,(a+b)/2,b,2*k+2);

  }

  

  // 指定した頂点とその影響する範囲の値を更新する。  

  // @param i 書き換えたい値の元の配列におけるindex

  // @param x 更新後の値

  void update(int i, int x){

    // 解説スライドの通り、元の配列を持つ最下段の長さをn(2冪)とすると、

    // その上のセグメント木の構造を持つ部分は n/2 + n/4 + n/8 + .. + 1 = n-1(等比級数の公式より)

    // よって、元の配列を最初に更新したいので、元の配列部分のindexに修正するため、n-1を加える。

    i += n-1;

    

    // その頂点をxに更新する。

    segtree[i] = segtree[i]+x;

    // 更新した最下段の情報の影響する範囲を更新する。

    // 具体的には更新した頂点の祖先全てが対象となる。

    while(i>0){

      // 親ノードへと移動

      i = (i-1)/2;

      // 自分の子２つを比較し、小さい方を得る。

      segtree[i] = segtree[2*i+1]+segtree[2*i+2];

    }

  }

};
    

int main(){
    int n,q,l,r,c;
    cin>>n>>q;
    
    
    range_minimum_query rmq(n+1);
    
    
    for(int i=0;i<q;i++){

        cin>>c;
        
        if(c==0){
            cin>>l>>r;
            rmq.update(l,r);
        }
        else{
            cin>>l>>r;
            cout << rmq.find(l,r+1) << endl;
        }
    }
}


Measured memory_bytes: 3828
#include<bits/stdc++.h>
//#include<iostream>
using namespace std;
//type
typedef long long ll;
#define pii pair<int, int>
#define vi vector<int>
//x * y * 1.0 can cause overflow
//constant
#define inf (int)(1e9+7)
#define mod (ll)(1e9+7)
#define eps 1e-10
//omission
#define eb emplace_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define all(v) v.begin(), v.end()
#define ios cin.tie(0); ios::sync_with_stdio(false)
#define FIX(a) cout << fixed << setprecision(a)
#define mp make_pair
//manip
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; }
#define UNIQUE(v) v.erase(unique(v.begin(), v.end(), v.end());
#define fill(x, y) memset(x, y, sizeof(x))
#define ceil(a, b) a / b + !!(a % b)
template<class T> T power_mod(T a, T b) {return b ? power(a * a % inf, b / 2) * (b % 2 ? a : 1) % inf : 1;}
template<class T> T power(T a, T b) {return b ? power(a * a, b / 2) * (b % 2 ? a : 1) : 1;}
#define LB(v, x) (int)(lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (int)(upper_bound(v.begin(), v.end(), x) - v.begin())
template<typename T> T gcd(T a, T b) {if (b == 0) return a; return gcd(b, a % b);}
template<typename T> T lcm(T a, T b) {return a / gcd(max(a, b), min(a, b)) * b;} //先に割る!!
#define outa(a, n) rep(i, n) cout << a[i] << " "; cout << endl
#define out(a) cout << a << endl
#define outv(v) rep(i, SZ(v)) cout << v[i] << " "; cout << endl
//loop
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep3(i, st, n) for (int i = st; i < n; ++i)
//algorithm
//double pointer, l start, how many adds, can be 0 -> init r = l, sum = 0
//bfs, not x, y, i, j
//not !(i % 2), i % 2 == 0
//minimal required terms
//cast caution
//look constraints always

int n;
double dp[301][301][301];

double calc(int i, int j, int k) {
    //out(i << " " << j << " " << k);
    
    //最下層から決定されていくため、後でより良くなることはない
    if (dp[i][j][k] != -1) return dp[i][j][k];
    //最下層
    if (i == 0 && j == 0 && k == 0) return 0.0;
    
    double res = 0.0;
    //i + 1とかあるが、i + j + kは等しいか小さくなる
    if (i) res += calc(i - 1, j, k) * i;
    if (j) res += calc(i + 1, j - 1, k) * j;
    if (k) res += calc(i, j + 1, k - 1) * k;
    res += n;
    res /= (i + j + k);
    
    return dp[i][j][k] = res;
}
int main() {
    fill_n(**dp, 301 * 301 * 301, -1);
    cin >> n;
    int one = 0, two = 0, three = 0;
    rep(i, n) {
        int a; cin >> a;
        if (a == 1) one++;
        else if (a == 2) two++;
        else three++;
    }
    FIX(11);
    out(calc(one, two, three));
    
}
//式の参考のつもりがほぼcopy
//https://qiita.com/drken/items/03c7db44ccd27820ea0d#j-%E5%95%8F%E9%A1%8C---sushi


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

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

  double ans = 0.0;
  for (int i = 1; i <= n; i++) {
    int val = i;
    double prob = 1.0;
    while(val < k) {
      val *= 2;
      prob /= 2.0;
    }
    ans += prob;
  }
  ans /= n;
  cout << fixed << setprecision(10) << ans << '\n';
}

Measured memory_bytes: 3780
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class D { public static void Main() => (new Solver()).Solve(); }

public class Solver
{
	public void Solve()
	{
		long N = GetLong();
		var cnt = new List<long>();
		var rest = N;
		for(long i = 2; i * i < N; i++)
		{
			long tmp = 0;
			while(rest % i == 0)
			{
				rest /= i;
				tmp++;
			}
			if(tmp != 0)
				cnt.Add(tmp);
		}
		if(rest > 1)
			cnt.Add(1);

		long ans = 0;
		foreach(var c in cnt)
		{
			long n = 1;
			long tmp = c;
			while(tmp >= n)
			{
				tmp -= n;
				n++;
				ans++;
			}
		}
		WriteLine(ans);
	}
}

public static class MyIO
{
	private static string[] args = new string[0];
	private static int cnt = 0;
	private static IEnumerable<string> getArgs(long N) => Range(0, N).Select(_ => getArg());
	private static string getArg()
	{
		if(cnt == args.Length) { args = Console.ReadLine().Split(); cnt = 0; }
		return args[cnt++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => getArgs(N).Select(int.Parse).ToArray();
	public static long[] GetLongs(long N) => getArgs(N).Select(long.Parse).ToArray();
	public static double[] GetDoubles(long N) => getArgs(N).Select(double.Parse).ToArray();
	public static decimal[] GetDecimals(long N) => getArgs(N).Select(decimal.Parse).ToArray();
	public static string[] GetStrings(long N) => getArgs(N).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) < 0) x = y; }
	public static void chmin<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) > 0)	x = y; }
	public static void swap<T>(ref T x, ref T y) { T tmp = x; x = y; y = tmp; }
	public static long rightShift(long x, long y) => (x >> (int)y);
	public static long leftShift(long x, long y) => (x << (int)y);
	public static bool contains(long s, long x) => (rightShift(s, x) & 1L) == 1L;
	public static long gcd(long x, long y) => (y == 0) ? x : gcd(y, x % y);
	public static long lcm(long x, long y) => (x / gcd(x,y)) * y;	
	public static IEnumerable<int> Range(long start, long count) => Enumerable.Range((int)start, (int)count);
	public static void Sort(this List<string> source) => source.Sort(StringComparer.Ordinal);
}


Measured memory_bytes: 27840