akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <functional> //sort(A,A.end(),greater<int>());降順ソート
#include <queue>
#include <stack>
#include <vector>

#define INF 10 << 10

typedef long long int llint;

vector<llint> come;

int main() {
	llint n, t;
	cin >> n >> t;
	for (llint i = 0; i < n; ++i) {
		llint temp;
		cin >> temp;
		come.push_back(temp);
	}

	llint x = 0;
	llint now = come[0];
	for (llint i = 1; i < n; ++i) {
		if (now + t >= come[i]) {
			x += come[i] - now;
		}
		else {
			x += t;
		}
		now = come[i];
	}

	cout << x + t << endl;

	return 0;
}


Measured memory_bytes: 2420
s = input()
l = len(s)
for i in range(l-1):
    if s[i] == s[i+1]:
        print(str(i+1) + " " + str(i+2))
        exit(0)

    elif i != l - 2:
        if s[i] == s[i+2]:
            print(str(i+1) + " " + str(i+3))
            exit(0)


print("-1 -1")


Measured memory_bytes: 3188
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>

using namespace std;

//	(long)√n を計算する。O(logn)で計算するから速いよ
//	実は double sqrt(double x) を使った方が高速だけど、計算誤差が気になる...
//	l_sqrtは整数のまま計算してるから誤差の心配はないよ
long l_sqrt(long n) {
	if (n <= 0) { return 0; }

	if (n > 256) {
		long k = l_sqrt(n / 4) * 2;
		while ((k + 1) * (k + 1) <= n) { k++; }
		return k;
	}
	else {
		for (int i = 16; i >= 1; i--) {
			if (i * i <= n) { return i; }
		}
	}
	return 0;
}

int main() {
	long S; cin >> S;
	long a = l_sqrt(S);
	long X2 = a;
	long Y1 = S / a;
	if (S > X2 * Y1) {
		if (X2 < Y1) {
			X2++;
		}
		else {
			Y1++;
		}
	}
	long T = X2 * Y1 - S;
	long X1 = T;
	long Y2 = 1;

	cout << "0 0 " << X1 << " " << Y1 << " " << X2 << " " << Y2 << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
 
const int INF = 1e9;
const int mod = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1.0);

int main()
{
    int n;
    cin >> n;
    vector<int> h(n);
    for(int i = 0; i < n; i++) cin >> h[i];
    
    int cnt = 0,flag = 1;
    while(flag){
        flag = 0;
        for(int i = 0; i < n; i++){
            if(h[i] != 0){
                for(int j = i; j < n && h[j] != 0; j++) h[j]--;
                cnt++; flag = 1;
                break;
            }
        }
    }

    cout << cnt << endl;

    return 0;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
    ll ans=0;
    ll n;cin >>n;
    map<ll,int>mp;
    for (ll i = 1; i*i<=n; ++i) {
        if(n%i==0){
            mp[i]++;
            mp[n/i]++;
        }
    }
    for(auto u:mp){
//        cout <<u.first<<endl;
        ll d=n/u.first;
//        cout <<d<<endl;
        if(mp[d]){
//            cout <<d<<endl;
            if(d-1>u.first) {
                ans += d - 1;
            }
        }
    }
    cout <<ans <<endl;
    return 0;
}

Measured memory_bytes: 640
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

enum P = 998244353L;
long[(10^^5)*2+50] F, RF;

long pow(long x, long n) {
    long y = 1;
    while (n) {
        if (n%2 == 1) y = (y * x) % P;
        x = x^^2 % P;
        n /= 2;
    }
    return y;
}

long inv(long x)
{
    return pow(x, P-2);
}

void init()
{
    F[0] = F[1] = 1;
    foreach (i, ref x; F[2..$]) x = (F[i+1] * (i+2)) % P;

    {
        RF[$-1] = 1;
        auto x = F[$-1];
        auto k = P-2;
        while (k) {
            if (k%2 == 1) RF[$-1] = (RF[$-1] * x) % P;
            x = x^^2 % P;
            k /= 2;
        }
    }
    foreach_reverse(i, ref x; RF[0..$-1]) x = (RF[i+1] * (i+1)) % P;
}

long comb(N)(N n, N k)
{
    if (k > n) return 0;
    auto n_b = F[n];    // n!
    auto nk_b = RF[n-k]; // 1 / (n-k)!
    auto k_b = RF[k];    // 1 / k!

    auto nk_b_k_b = (nk_b * k_b) % P; // 1 / (n-k)!k!

    return (n_b * nk_b_k_b) % P;  // n! / (n-k)!k!
}

void main()
{
    init();
    auto nmk = readln.split.to!(long[]);
    auto N = nmk[0];
    auto M = nmk[1];
    auto K = nmk[2];

    long r;
    foreach (k; N-1-K..N) {
        long x = comb(N-1, k);
        (x *= M) %= P;
        (x *= pow(M-1, k)) %= P;
        r = (r + x + P) % P;
    }
    writeln(r);
}

Measured memory_bytes: 5884
defmodule Main do
  def main do
    s =
      IO.read(:line)
      |> String.trim
    a = String.slice(s, 0..2)
    b = String.slice(s, 1..3)
    if a == "000" or a == "111" or a == "222" or a == "333" or a == "444" or a == "555" or a == "666" or a == "777" or a == "888" or a == "999" or b == "000" or b == "111" or b == "222" or b == "333" or b == "444" or b == "555" or b == "666" or b == "777" or b == "888" or b == "999" do
      IO.puts("Yes")
    else
      IO.puts("No")
    end
  end
end


Measured memory_bytes: 31112
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <ll, pair<ll,ll>> P;

const ll MOD=1000000007;
ll N,Q;
vector<P> X;
set<ll> D;
vector<ll> DD;
unordered_map<ll, ll> ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N>>Q;
    X.resize(N);
    rep(i,0,N){
        cin>>X[i].sc.fr>>X[i].sc.sc>>X[i].fr;
    }
    sor(X);
    DD.resize(Q);
    rep(i,0,Q){
        ll d;
        cin>>d;
        D.insert(d);
        DD[i]=d;
    }
    rep(i,0,N){
        ll s=X[i].sc.fr, t=X[i].sc.sc, x=X[i].fr;
        s-=x; t-=x;
        for(auto itr=D.lower_bound(s); itr!=D.lower_bound(t); ++itr){
            ans[*itr]=x;
        }
        D.erase(D.lower_bound(s),D.lower_bound(t));
    }
    rep(i,0,Q){
        if(D.count(DD[i])) cout <<-1<<"\n";
        else cout <<ans[DD[i]]<<"\n";
    }
}

Measured memory_bytes: 23612
#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 EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())
#define CLR(a) memset((a), 0, sizeof(a))
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

//using LL = long long;
using namespace std;

const int dy[] = {0, 0, 1, -1};
const int dx[] = {1, -1, 0, 0};
const double EPS = 1e-10;
const double PI = acos(-1.0);

struct Stack{
    Stack(){
        top = 0;
    }

    int top;
    int byFull = 1000;
    int v[1000];

    bool is_Empty(){
        if (top == 0) return true;
        else return false;
    }
    bool is_Full(){
        if (top >= byFull-1) return true;
        else return false;
    }
    void push(int x){
        if(is_Full())return;
        else {
            top++;
            v[top] = x;
        }
    }
    int pop(){
        if(is_Empty())return 0;
        else {
            top--;
            return v[top+1];
        }
    }
};

int calc(int x,string op,int y){
  if(op=="+")return x+y;
  if(op=="-")return x-y;
  if(op=="*")return x*y;
  else return 0;
}


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

    Stack s;

    int numA, numB;
    string str;
    while(cin >> str){

        if(str=="+"||str=="-"||str=="*"){
            numA=s.pop();
            numB=s.pop();
            s.push(calc(numB,str,numA));
        }else{
            numA=0;

            for(int i=0;i<(int)str.size();i++){
                numA*=10;
                numA+=str[i]-'0';
            }

        s.push(numA);
        }
    }

  cout<<s.pop()<<endl;
     
}


Measured memory_bytes: 3172
#include <bits/stdc++.h>
#define rep(i,n) for ((i)=1;(i)<=(n);(i)++)
#define per(i,n) for ((i)=n;(i)>=(1);(i)--)
using namespace std;
int q,s1,s2,mod=1e9+7;
long long a,b,f[205];
void dfs(long long x,long long y,int dep)
{
	if(dep+1==s1)
	{
		if(x<=a&&y<=b) s2=(s2+(a-x)/y)%mod;
		if(x<=b&&y<=a) s2=(s2+(b-x)/y)%mod;
		return;
	}
	while(x+y<=f[dep+3])
	{
		x+=y;
		dfs(y,x,dep+1);
	}
}
int main()
{
	int i;f[0]=f[1]=1;for(i=2;i<=200;i++) f[i]=f[i-1]+f[i-2];
	scanf("%d",&q);
	while(q--)
	{
		scanf("%lld%lld",&a,&b);if(a>b) swap(a,b);
		if(a==1){printf("1 %lld\n",b%mod);continue;} 
		if(a==2&&b==2){puts("1 4");continue;}
		s1=s2=0;while(f[s1+1]<=a&&f[s1+2]<=b) s1++;
		dfs(1,1,0);printf("%d %d\n",s1,s2);
	}
	return 0;
}

Measured memory_bytes: 3968
K, N = map(int, input().split())
List = list(map(int, input().split()))
max = 0

for i in range(N-1):
    langth = List[i+1] - List[i]
    if langth > max:
        max = langth

langth = 0

langth = K - (List[N - 1] - List[0])
if langth > max:
    max = langth

print(K-max)





Measured memory_bytes: 26444
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n,x = na()
m = [0]*n
wa = 0
r = float("inf")
for i in range(n):
    m = ni()
    if r > m:
        r = m
    wa += m

no = (x - wa) // r
print(n + no)


Measured memory_bytes: 3060
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    ll x, y;
    cin >> x >> y;
    if (x % y == 0) {
        cout << -1 << endl;
    }
    else {
        cout << x << endl;
    }
    return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define    bit(a)          __builtin_popcount(a)
#define    all(x)           x.begin(), x.end()
#define    minv(v)         *min_element(all(v))
#define    maxv(v)         *max_element(all(v))
#define    unq(v)           sort(all(v)),v.erase(unique(all(v)),v.end())
#define    w(x)             while(x--)
#define    rep(i,a,b)       for(i=a;i<=b;i++)
#define    ll               long long
#define    pb               push_back
#define    vii              vector<int>
#define    vll              vector<ll>
#define    vcc              vector<char>
#define    sii              set<int>
#define    sll              set<ll>
#define    scc              set<char>
#define    li               list<int>
#define    pii              pair<int,int>
#define    pll              pair<ll,ll>
#define    mii              map<int,int>
#define    mll              map<ll,ll>
#define    fill(arr,x)      memset(arr,x,sizeof(arr))
#define    gcd(a,b)         __gcd(a,b)
#define    lcm(a,b)        (a*(b/gcd(a,b)))
#define    srtc(a,b)        sort(a,a+b,greater<int>())
#define    pi               acos(-1.00)
#define _ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
/*
//find the position of 0 or 1 in binary representation
int zero(int n)
{
    int i=1,pos=0;
    while(n)
    {
        if(n%2==0)pos=i;
        n/=2;
        i++;
    }
    return pos;
}
*/
//--------------Graph Moves--------------------------------------
const int dx[] = {+1,-1,+0,+0};
const int dy[] = {+0,+0,+1,-1};
//const int dx[] = {+0,+0,+1,-1,-1,+1,-1,+1}; ///King's move
//const int dy[] = {-1,+1,+0,+0,+1,+1,-1,-1}; ///king's Move
//const int dx[] = {-2,-2,-1,-1,+1,+1,+2,+2}; ///knight's move
//const int dy[] = {-1,+1,-2,+2,-2,+2,-1,+1}; ///knight's move
//---------------------------------------------------------------
int t,n,m;
int parent[200005];
int ra[200005];
string s;
void make_set()
{
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
        ra[i]=1;
    }
}
int find_par(int n)
{
    if(n == parent[n]) return n;
    return parent[n] = find_par(parent[n]);
}
void conect(int a,int b)
{
    int u=find_par(a);
    int v=find_par(b);
    parent[u]=v;
    if(u!=v)ra[v]+=ra[u];
}
int main()
{
    _ios;
    cin>>n>>m;
    make_set();
    w(m)
    {
        int x,y;
        cin>>x>>y;
        conect(x,y);
    }
    int ans=-1;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,ra[i]);
    }
    cout<<ans<<endl;
    return 0;
}





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

int t[510][510];

int main(int argc, char const *argv[])
{
	int N, M, Q; cin >> N >> M >> Q;
	vector<int> l(M), r(M);
	rep(i, M) cin >> l[i] >> r[i];

	rep(i, M) t[l[i]][r[i]]++;
	rep(i, 510) rep(j, 509) t[i][j + 1] += t[i][j];
	rep(j, 510) rep(i, 509) t[i + 1][j] += t[i][j];
	
	rep(i, Q) {
		int p, q; cin >> p >> q;
		printf("%d\n", t[q][q] + t[p - 1][p - 1] - t[p - 1][q] - t[q][p - 1]);
	}
	return 0;
}

Measured memory_bytes: 3456
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }

  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    int a = Integer.parseInt(sc.next());
    int b = Integer.parseInt(sc.next());
    pw.println(a * b);
  }
}


Measured memory_bytes: 35676
function Main(input) {
   	var inputArray = input.split("\n");
	var X=inputArray[0];
	
	var amari=X%100;
	var kaisu=0;
	
	for(var i=5;i>=1;i--){
		kaisu=kaisu+parseInt(amari/i);
		amari=amari%i;
		//console.log(i);
	}
	
	if(kaisu<=parseInt(X/100)){
		console.log("1");
	}else{
		console.log("0")
	}
}
     
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
#include <cstdio>

int main() {
    int W, H, x, y, r;
    scanf("%d%d%d%d%d", &W, &H,&x, &y, &r);

    if(x <= W - r && x  >= r && y >= r && y <= H - r) {
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }
}


Measured memory_bytes: 2680
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int n,a,b,ans=0,t,sum;
	cin>>n>>a>>b;
	for(int i=a; i<=n ; i++)
	{
		t=i;
		sum=0;
		while(t)	{sum+=t%10;t/=10;} 
		if(sum>=a && sum<=b)	ans+=i;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
n = int(input())
s = set()
q = []
for i in range(n):
    x,l = map(int, input().split())
    s.add(x-l)
    s.add(x+l)
    q.append([x-l,x+l])

d = sorted(s)
dd = {j:i for i,j in enumerate(d)}
#print(dd)
m = len(d)
q.sort(key=lambda x: x[1])
DP = [0]*(m+1)

cur = 0
for i in range(m):
    DP[i] = max(DP[i-1], DP[i])
    while cur < n and dd[q[cur][1]] == i:
        DP[i] = max(DP[i], DP[dd[q[cur][0]]]+1)
        cur += 1
    #print(DP)
print(DP[m-1])

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

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vl = V<ll>;
using VVl = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pll = P<ll, ll>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Msi = M<string, int>;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

const double PI = acos(-1);
const ll MOD = 1e9+7;

int n;
string s;

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

    char bef = s[0];
    int idx = 1;
    int res = 0;
    while (idx < s.size()) {
        if (bef != s[idx]) {
            s.erase(idx-1, 2);
            res += 2;
            bef = idx >= 2 ? s[idx-2] : s[0];
            idx = idx >= 2 ? idx - 1 : idx;
        } else {
            bef = s[idx];
            idx++;
        }
    }
    std::cout << res << '\n';

    return 0;
}


Measured memory_bytes: 512
/// In The Name Of God

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

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)5e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, k;

int go[100000][10];
int dp[100000];

int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	cin >> n;
	for (int i = 0; i < n; i++) {
		dp[i] = inf;
	}
	for (int i = 1; i <= 9; i++) {
		dp[i % n] = min(dp[i % n], i);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			go[i][j] = (i * 10 + j) % n;
		}
	}
	set < pair <int, int> > st;
	for (int i = 1; i <= 9; i++) {
		st.insert({dp[i % n], i % n});
	}
	while (sz(st)) {
		pair <int, int> v = *st.begin();
		st.erase(st.begin());
		for (int i = 0; i <= 9; i++) {
			int nxt = go[v.s][i];
			if (dp[nxt] > v.f + i) {
				st.erase({dp[nxt], nxt});
				dp[nxt] = v.f + i;
				st.insert({dp[nxt], nxt});
			}
		}
	}
	cout << dp[0];
	ioi
}


Measured memory_bytes: 8320
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
using namespace std;
typedef long long ll;
int main(){
  ll mod = pow(10,9) + 7;
  int n = 0;
  cin >> n;
  string str;
  cin >> str;
  ll res = 0;
  res = 1;
  for(int i = 0;i <= 25;i++){
    ll count = 0;
    for(int j = 0;j <= n - 1;j++){
      if(str[j] == 'a' + i)count++;
    }
    res = (res * (count + 1)) % mod;
  }
  res--;
  if(res < 0)res += mod;
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
main(){
  string O,E;
  cin>>O>>E;
  string s(O.size()+E.size(), '?');
  for(int i=0;i<O.size();++i)s[2*i]=O[i];
  for(int i=0;i<E.size();++i)s[2*i+1]=E[i];
  cout<<s<<endl;
}


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

using namespace std;

typedef long long ll;

ll ans;
ll n,x;

ll gcd(ll a, ll b) {
  if(b == 0) return 0;
  ans += b * (a / b);
  return gcd(b,a % b);
}

int main() {
  cin >> n >> x;

  x = min(x, n - x);

  gcd(n - x, x);

  cout << ans * 3 << endl;
}


Measured memory_bytes: 256
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		PrintWriter pw=new PrintWriter(System.out);
		Scanner sc=new Scanner(System.in);

		int w=sc.nextInt();
		int h=sc.nextInt();
		int n=sc.nextInt();
		int p1=0;//???????????±
		int p2=0;//???????????±
		int move=0;
		int cnt=0;

		for(int i=0;i<n;i++){
			move=sc.nextInt();
			if(move==0){
				p1++;
			}else if(move==1){
				p2++;
			}
			cnt+=cnt(p1,p2,w,h);
		}
		pw.println(cnt);

		sc.close();
		pw.close();
	}


	public static int cnt(int p1,int p2,int w,int h){
		if(p1<w-1){
			if(p2==p1){
				return 1;
			}else{
				return 0;
			}
		}
		if(p1==w-1){
			return 0;
		}
		if(p1>w-1&&p1<w+h-2){
			if(p2+2==p1){
				return 1;
			}else{
				return 0;
			}			
		}
		if(p1==w+h-2){
			return 0;
		}
		if(p1>w+h-2){
			if(p2+4==p1){
				return 1;
			}else{
				return 0;
			}			
		}
		return -1;
	}
}

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

const int maxn = 200010, P = 998244353;
int n, ans, f[maxn], g[maxn][2];
char s[maxn];

int main() {
    scanf("%d %s", &n, s + 1);
    g[0][0] = 1;
    for (int i = 1; i <= n; i++) if (!(n % i)) {
        if (!((n / i) & 1)) continue;
        for (int j = 1; j <= i; j++) {
            g[j][0] = g[j][1] = 0;
            for (int t = 0; t < 2; t++) {
                (g[j][1] += g[j - 1][1]) %= P;
                char c = t + '0';
                if (c <= s[j]) (g[j][c < s[j]] += g[j - 1][0]) %= P;
            }
        }
        bool flag = 1;
        for (int j = i + 1; j <= n; j++) {
            char c = s[j % i == 0 ? i : j % i];
            if (!(((j + i - 1) / i) & 1)) c ^= 1;
            if (c > s[j]) { flag = 0; break; }
            if (c < s[j]) break;
        }
        f[i] = g[i][1];
        if (flag) (f[i] += g[i][0]) %= P;
        for (int j = 1; j < i; j++) if (!(i % j)) {
            f[i] = (f[i] - f[j] + P) % P;
        }
        ans = (ans + 2LL * i * f[i]) % P;
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 5524
#include<bits/stdc++.h>
#define U [1<<17]={}
#define G(a)((c=A[a]+A[P[a]]+C[a])%k?c:0)
#define F(x,z,y)L x(L f){return z;}L y(L
typedef long long L;using namespace std;
map<L,L>T U;L P U,E U,Z U,H U,C U,A U,O U,X U,B U,k,n,a,b,c;char s U;
F(M,f?B[f]+M(f^f&-f):0,D)
a){L d;Z[a]=1;for(map<L,L>::iterator I=T[a].begin();I!=T[a].end();I++)
	d=I->first,d-P[a]?P[d]=a,E[d]=E[a]+1,C[d]=I->second,D(d),Z[a]+=Z[d],!H[a]|Z[H[a]]<Z[d]?H[a]=d:0:0;}
F(K,(a=X[f],n=X[b],a-n?M(O[E[a]<E[n]?a=n,n=b,b=f,n:f])-M(O[a])+G(a)+K(P[a]):abs(M(O[f])-M(O[b]))),S)
x,L i){for(x=G(x)+M(i++)-M(i);i<1e5;i+=i&-i)B[i]+=x;}
main(){for(cin>>n>>k;--n;T[a][b]=T[b][a]=c)cin>>a>>b>>c;
	for(D(b=0);n<*Z;n++)if(!n|H[P[a=n]]-n)for(;!b|a;S(a=H[a],O[a]=b++))X[a]=n;
	for(cin>>a;cin>>s>>a>>b;*s&2?cout<<K(a)<<endl,0:A[a]+=b,S(H[a],O[a]),a&&S(a,O[a]-1));}

Measured memory_bytes: 33376
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(S: str):
    if S[0:4] == 'YAKI':
        print(YES)
    else:
        print(NO)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  ll n;
  cin>>n;
  
  ll ans=INF;
  for(ll i=1; i*2<=n; i++){
    ll a=i;
    ll b=n-i;
    ll sum=0;
    while(a>0){
      sum+=a%10;
      a/=10;
    }
    while(b>0){
      sum+=b%10;
      b/=10;
    }
    
    ans=min(ans,sum);
    
  }
  
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

int main()
{
	int n, i;
	double xa, ya, ra, xb, yb, rb;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%lf %lf %lf %lf %lf %lf", &xa, &ya, &ra, &xb, &yb, &rb);
		double lr = ra>rb ? ra : rb,
			sr = ra > rb ? rb : ra,
			distance = sqrt(pow(xa - xb, 2) + pow(ya - yb, 2));
		if (distance > ra + rb)
		{
			printf("0\n");
		}
		else if (distance < lr - sr)
		{
			if (lr == ra)printf("2\n");
			else printf("-2\n");
		}
		else
			printf("1\n");
	}
	return 0;
}

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

int main() {
    int K;
    cin >> K;

    vector<ll> ans;
    queue<ll> que;
    for (int i = 1; i <= 9; ++i) {
        que.push(i);
        ans.push_back(i);
    }

    while (ans.size() < 100005) {
        ll n = que.front();
        que.pop();

        ll next = n % 10 - 1;
        if (next >= 0) {
            que.push(n * 10 + next);
            ans.push_back(n * 10 + next);
        }
        next = n % 10;
        que.push(n * 10 + next);
        ans.push_back(n * 10 + next);
        next = n % 10 + 1;
        if (next <= 9) {
            que.push(n * 10 + next);
            ans.push_back(n * 10 + next);
        }
    }

    cout << ans[K - 1] << endl;
}

Measured memory_bytes: 4624
#include<bits/stdc++.h>
using namespace std;
const int md=1e9+7;
int a[200005],c[200005],cc[200005];
long long fac[200005],rev[200005];
long long ccc(long long x,int y)
{
	if(y==1)return x;
	long long ans=ccc(x,y/2);
	if(y&1)return (((ans*ans)%md)*x)%md;else return (ans*ans)%md;
}
void init()
{
	fac[1]=1ll;
	for(int i=2;i<200005;i++)fac[i]=(fac[i-1]*i)%md;	
	for(int i=1;i<=200005;i++)rev[i]=ccc(fac[i],1e9+5);
}
int calc(int x,int y)
{
	if(y>x)return 0;
	else if(x==0||x==y||y==0)return 1;
	else return (((fac[x]*(long long)rev[y])%md)*(long long)rev[x-y])%md;
}
int main()
{
	int n,l,r;
	scanf("%d",&n);
	n++;
	init();
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		if(c[a[i]])
		{
			l=c[a[i]];
			r=i;
		}
		c[a[i]]=i;
	}
	int dis=n-(r-l+1);
	for(int i=1;i<=n;i++)
	{
		int ans=calc(n,i)-calc(dis,i-1);
		ans=(ans+md)%md;
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 5888
#include <bits/stdc++.h>
using namespace std;
#define dg(x) cerr << #x << " = " << x <<endl;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define F first
#define S second
#define forn(i,n) for(int i=0;i<(int)n;i++)
#define fore(i,a,b) for(int i=(int)a;i<=(int)b;++i)
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int main(){
#ifdef LOCAL
    //freopen("h.txt", "r", stdin);
    // freopen("main.out", "w", stdout);
#else
    ios::sync_with_stdio(0), cin.tie(0);
    #define endl '\n'
#endif
    int a,b;
    cin>>a>>b;
        int cnt=0;
        while(b>1){
            cnt++;
            b-=a-1;
        }
        cout<<cnt<<endl;
    return 0;
}

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

using namespace std;

	int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a%b);
	}

int main(){
    int i , j ,l;
    int ij;
    int K;
    cin >> K;
    int sum = 0;
    for(i=1; i<=K; i++){
        for(j=1; j<=K; j++){
            ij = gcd(i, j);
            for(l=1; l<=K; l++){
                sum += gcd(l, ij);
            }
        }
    }
    cout << sum;
    return 0;
}

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

int main() {
    int r, d, x[20];
    cin >> r >> d >> x[0];
    rep(i, 10) {
        x[i+1] = r*x[i] - d;
        cout << x[i+1] << endl;
    }
}

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


int main()
{
    int n;
    cin>>n;
    int x=n%10;

    if(n%10 == 3)
        cout<<"bon";
    else if(x==0 || x==1 || x==6 || x==8)
        cout<<"pon";
    else
        cout<<"hon";

    return 0;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=998244353;
const int siz=1e5;
const long inf=1e9;
int main(){
	string s; cin>>s;
	s = "00" + s;
	int ans = 0;
	for(int i = s.size()-1; i > 0; i--){
		if(s[i] < '5'){
			ans += s[i] - '0';
		}else if(s[i] == '5' && s[i-1] < '5'){
			ans += 5;
		}else{
			ans += '9' - s[i] + 1;
			int j = i - 1;
			while(j >= 0 && s[j] == '9'){
				s[j] = '0';
				j--;
			}s[j] += 1;
		}
	}cout<<ans<<endl;
}

Measured memory_bytes: 2308
#![allow(non_snake_case)]
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
     };
     ($next:expr, $t:ty) => {
         $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(dead_code)]
const MOD: u64 = 1000000007;


fn main() {
    input!{
        N: usize,
        S: chars
    }
    let S = S;

    let mut white: isize = (&S).into_iter().fold(0, |acc, ch| acc + if *ch == '.' { 1 } else { 0 });
    let mut black: isize = 0;
    let mut ans = white + black;

    for i in 0..N {
        if S[i] == '.' {
            white -= 1;
        } else {
            black += 1;
        }
        ans = min(ans, black + white);
    }

    println!("{}", ans);


}

Measured memory_bytes: 4352
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int r = sc.nextInt();
            if(n == 0 && r == 0) break;
            int[] h = new int[n];
            for(int i=1; i<=n; i++) h[n-i]=i;
            
            while(r-- != 0) {
                int p = sc.nextInt();
                int c = sc.nextInt();
                p -= 1;
                int[] s = new int[p];
                for(int i=0; i<p; i++) s[i] = h[i];
                for(int i=0; i<c; i++) h[i] = h[i+p];
                for(int i=0; i<p; i++) h[i+c] = s[i];
            }
            System.out.println(h[0]);
        }
    }
}



Measured memory_bytes: 38628
//#pragma GCC optimize ("O3")
//#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

int dp[10001];
int AB[10001];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int H = getint(), N = getint();
	rep1(i, 10000) dp[i] = 1e9;
	rep1(i, 10000) AB[i] = 2e9;

	rep(i, N) {
		int a = getint(), b = getint();
		chmin(AB[min(H, a)], b);
	}

	double saikou = 1e20;
	int kotae = 2e9;
	rep1(i, 10000) {
		int k = AB[i];
		if (k < 1e9) {
			int ima = k;
			for (int j = i + i; j <= 10000; j += i) {
				ima += k;
				if (AB[j] >= ima) AB[j] = 2e9;
			}
			chmin(kotae, (H + i - 1) / i * k);
			chmin(saikou, 1.0 * k / i);
		}
	}

	for (int i = 10000; i >= 1; i--) {
		int k = AB[i];
		if (k < 1e9) {
			double kouritu1 = 1.0 * k / i;
			double kouritu2 = 1.0 * kotae / H;
			double are = H * (kouritu2 - saikou) / (kouritu1 - saikou);
			if (are > i) {
				auto dp2 = dp + i;
				int kazu = max(0, H - i);
				for (int j = 0; j < kazu; j++) if (dp2[j] > dp[j] + k) dp2[j] = dp[j] + k;
				for (int j = kazu; j <= H; j++) if (kotae > dp[j] + k) kotae = dp[j] + k;
			}
		}
	}
	printf("%d", kotae);

	Would you please return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

ll f(ll pre, ll cnt) {
    int res = 0;
    if(pre == cnt) pre = 0;
    else {
        if(cnt < pre) res += cnt;
        else res += (cnt - pre);
    }
    
    return res;
}

int main() {
    int n;
    cin >> n;
    vll a(n);
    rep(i, n) cin >> a[i];
    sort(all(a));

    ll pre = a[0], cnt = 0, ans = 0;
    rep(i, n) {
        if(pre == a[i]) cnt++;
        else {
            ans += f(pre, cnt);
            cnt = 1;
            pre = a[i];
        }
    }
    ans += f(pre, cnt);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
N = int(input())
adj = [[] for _ in range(N)]

for i in range(N-1):
    u,v,w = map(int,input().split())
    u,v = u-1, v-1
    w %= 2
    adj[u].append((v,w))
    adj[v].append((u,w))

color = [None]*N
color[0] = False
stack = [0]

while stack:
    u = stack.pop()
    for v,w in adj[u]:
        if color[v] is None:
            color[v] = (w%2) ^ color[u]
            stack.append(v)

for c in color:
    print(1 if c else 0)

Measured memory_bytes: 35628
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define PI 3.1415926535897932
#define MOD 1000000007;
using namespace std;
long long GCD(long long A,long long B){
  if(B==0){
    return A;
  }
  else{
    return GCD(B,A%B);
  }
}
long long LCM(long long A,long long B){
  long long g=GCD(A,B);
  return A/g*B;
}
long long num_order(long long X){
  long long ans=0;
  while(true){
    if(X==0){
      break;
    }
    else{
      X/=10;
      ans++;
    }
  }
  return ans;
}
int main() {
  
  int X;
  cin>>X;
  
  int i=0;
  
  int sum=0;
  
  
  while(sum<X){
    i++;
    sum+=i;
  }
  
  
  cout<<i<<endl;
}

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


/* エイリアス */
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define endl '\n'

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace


/* 関数マクロ */
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep2(i, n, m) for (ll i = n; i <= m; ++i)
#define rep3(i, n, m) for (ll i = n; i >= m; --i)
#define all(v) v.begin(), v.end()
#define si(v) int(v.size())
#define UNIQUE(v) sort(all(v)), v.erase(unique(all(v)),v.end())


/* 定数 */
const ll mod = 1e9 + 7;
const ll infll = (1LL << 62) - 1;
const ll inf = (1LL << 30) - 1;


/* その他 */
template<class S, class T> inline bool chmax(S &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class S, class T> inline bool chmin(S &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;


signed main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);
  
  int n, k; cin >> n >> k;
  set<int> child;

  rep(i, k) {
    int d; cin >> d;
    rep(j, d) {
      int a; cin >> a;
      child.em(a);
    }
  }

  cout << n - si(child) << endl;
}

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

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

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

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

//constexpr ll mod = 998244353;
constexpr ll mod = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, k; cin >> n >> k;

  vector<int> v(n);
  rep(i, n) cin >> v[i];

  int ret = 0;
  int kk = k;
  for(k=0; k<=kk; k++) {
    for (int i = 0; i <= k && i <= n; i++) {
      for (int j = 0; i + j <= k && i + j <= n; j++) {
        int l = k - i - j;
        //debug(i);
        //debug(j);
        //debugln(l);
        priority_queue<int> que;
        rep(p, i) {
          que.push(v[p]);
        }
        rep(p, j) {
          que.push(v[n - 1 - p]);
        }
        int ans = 0;
        if (l > i + j) continue;
        rep(p, i + j - l) {
          ans += que.top();
          que.pop();
        }
        //debugln(ans);
        chmax(ret, ans);
      }
    }
  }
  cout << ret << endl;
}

Measured memory_bytes: 256
n = int(input())
base_t, a = map(int, input().split())
hs = list(map(int, input().split()))

t = [base_t - 0.006 * x for x in hs]
dif = [abs(ti - a) for ti in t]

for i in range(n):
    if dif[i] == min(dif):
        print(i+1)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define int long long
using namespace std;

template <typename X, typename T>
auto vectors(X x, T a) {
	return vector<T>(x, a);
}

template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
	auto cont = vectors(y, z, zs...);
	return vector<decltype(cont)>(x, cont);
}

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

const double EPS = 1e-3;
typedef vector<double> vd;
typedef vector<vd> mat;

vd simultaneousLinearEquations(const mat &A, const vd &b){
	int n = A.size();
	mat B(n, vd(n + 1));
	rep(i,n) rep(j,n) B[i][j] = A[i][j];
	rep(i,n) B[i][n] = b[i];

	rep(i,n){
		int pivot = i;
		for(int j = i; j < n; j++){
			if(abs(B[i][j]) > abs(B[pivot][i])) pivot = j;
		}
		swap(B[i], B[pivot]);

		if(abs(B[i][i]) < EPS) return vd(); //$B2r$J$7(B or $B0l0U$G$O$J$$(B

		for(int j = i + 1; j <= n; j++) B[i][j] /= B[i][i];
		rep(j,n){
			if(i != j){
				for(int k = i + 1; k <= n; k++) B[j][k] -= B[j][i] * B[i][k];
			}
		}
	}
	vd x(n);
	rep(i,n) x[i] = B[i][n];
	return x;
}

double pow(double n, int x){
	if(x == 0) return 0;
	double res = 1;
	rep(i,n) res *= x;
	return x;
}

bool check(vd& s, int v, int d, double ans){
	//show("check")
	//cout << v << ' ' << d << endl;
	double tmp = pow(v, d);
	rep(i,d){
		//show(ans)
		ans -= tmp * s[i];
		if(v != 0) tmp /= v;
	}
	ans -= s.back();
	//show(ans)
	//printf("%.8lf %.8lf", ans, EPS);
	return ans > -EPS and ans < EPS;
}

signed main(){
	int d;
	while(cin >> d, d){
		vector<pair<int, double>> v(d + 3);
		rep(i,d + 3){
			double a;
			cin >> a;
			v[i] = make_pair(i, a);
		}

		rep(i,d + 3){
			range(j,i + 1,d + 3){
				mat m;
				vd r;
				rep(k,d + 3){
					if(i == k or j == k){
						continue;
					}
					r.emplace_back(v[k].second);

					m.emplace_back(vd());
					double tmp = pow(v[k].first, d);
					rep(j,d){
						m.back().emplace_back(tmp);
						if(v[k].first != 0) tmp /= v[k].first;
					}
					m.back().emplace_back(1);
				}

				auto s = simultaneousLinearEquations(m, r);
				if(s.empty()) continue;
				//show("matrix")
				//rep(i,d + 1){
				//	cout << m[i] << endl;
				//}

				//cout << s << endl;
				bool x = check(s, v[i].first, d, v[i].second);
				bool y = check(s, v[j].first, d, v[j].second);
				//cout << x << ' ' << y << endl;
				//cout << i << ' ' << j << endl;
				if(not x and not y) continue;
				if(not x){
					cout << i << endl;
					goto END;
				}else{
					cout << j << endl;
					goto END;
				}
			}
		}
		assert(false);
		cout << "---" << endl;
END:;

	}
}



Measured memory_bytes: 3308
def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n%2 == 0:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    return True

def is_like_num(n):
    return is_prime(n) and is_prime((n+1)//2)

erast_list =[0]*100001
cnt = 0
for i in range(100001):
    if is_like_num(i):
        cnt+=1
    erast_list[i] = cnt
# print(erast_list[:5])
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
#    print(erast_list[R+1],erast_list[L-1])
    print(erast_list[R+1]-erast_list[L-1])

Measured memory_bytes: 4596
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val=init_val
        # Range Minimum Query
        self.N0 = 2**(N-1).bit_length() #Nを超える最小の2のべき乗
        # 0-indexedで管理(N0-1からはじまる)
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res= left | right
        return res

    def update(self,k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0-1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(self.data[2*k+1], self.data[2*k+2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R-1])
    
            if L & 1:
                s = self._segfunc(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

def chartobit(c):
    return 1<<(ord(c)-97)
n=inp()
s=[chartobit(i) for i in list(input()) if i!="\n"]
st = SegmentTree(0, n)
for i in range(n):
    st.update(i,s[i])
q = inp()
ans = []
for i in range(q):
    mode, first, second = input().split()
    if mode == "1":
        # if second in st.data[int(first) - 1 + st.N0 - 1]:
        #     continue
        st.update(int(first) - 1, chartobit(second))
    else:
        ans.append((st.query(int(first) - 1, int(second))))
for i in ans:
    print(sum(map(int,bin(i)[2:])))

Measured memory_bytes: 113728
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long n = Long.parseLong(br.readLine());
		long i = 1;
		long x = i;
		boolean checkFlg = true;
		while (true) {
			if (checkFlg) {
				x = i;
			}
			if (x % 3 == 0 & checkFlg) {
				System.out.print(" " + i);
				if (++i <= n) {
					checkFlg = true;
					continue;
				} else {
					break;
				}
			}
			
			if (x % 10 == 3) {
				System.out.print(" " + i);
				if (++i <= n) {
					checkFlg = true;
					continue;
				} else {
					break;
				}
			}

			x /= 10;
			if (x != 0) {
				checkFlg = false;
				continue;
			}

			if (++i <= n) {
				checkFlg = true;
				continue;
			} else {
				break;
			}
		}
		System.out.println("");
	}
}

Measured memory_bytes: 26856
#include <math.h>
 #include <limits.h>
 #include <string.h>
 #include <iostream>
 #include <vector>
 #include <algorithm>
 #include <string>

 using namespace std;

 #define ipair pair<int,int>
 #define rep(I,N) for(int I=0; I<N; I++)
 #define rrep(I,N) for(int I=N; I>=0; I--)
 #define repj(i,j,n) for(int i=j;i<n;i++)

 #define PB(a,i) (a).push_back(i)
 #define ALL(a) (a).begin(),(a).end()

 #define OK(i) cout<<"OK "<<i<<endl
 #define Yes cout<<"Yes"<<endl
 #define YES cout<<"YES"<<endl
 #define No cout<<"No"<<endl
 #define NO cout<<"NO"<<endl

 int main() {
   int N;
   std::cin >> N;

   int v[1000];

   rep (i, N) {
     std::cin >> v[i];
   }

   std::sort(v, v + N);

   double ans = v[0];
   repj(i, 1, N) {
     ans = (ans + v[i]) / 2.0;
   }

   printf("%lf\n", ans);

   return 0;
 }


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
#include <numeric>
#include <limits>
#include <type_traits>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
ll gcd(ll a, ll b){if (a%b == 0)  return(b);else  return(gcd(b, a%b));}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
/* map<string,int> */
/* 大文字を小文字に変換 tolower*/
/* 小文字を大文字に変換 toupper*/
/* 辞書順 next_permutation(a.begin(),a.end()) */
 
int main () {
    int a,b;
    cin >> a >>b;
    cout << lcm(a,b) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    char c[1000];
    int i,sum=0,num=0;
    scanf("%s",c);
    for(i=0;i<strlen(c);i++){
        if(c[i]=='C')
            sum=1;
        if(c[i]=='F' && sum==1)
            num=1;
    }
    if(sum==1 && num==1)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long int;
template<typename T> void swap(T *t1, T *t2){ T* tmp=t1; t1=t2; t2=tmp;}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long n, k, q;
    long a[100000];
    long tmp;
    cin >> n >> k >> q;
    for(long i=0; i<n; i++){
        a[i] = 0;
    }
    for(long i=0; i<q; i++){
        cin >> tmp;
        a[tmp-1]++;
    }
    for(long i=0; i<n; i++){
        if(k - (q-a[i]) <= 0){
            cout << "No" << endl;
        }else {
            cout << "Yes" << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1e9)
#define MOD (1e9+7)

/////////////////////////////////////////////////////////

void Main(){
  ll N, M; cin >> N >> M;
  if(2 * N >= M) cout << M / 2 << endl;
  else cout << (N * 2 + M) / 4 << endl;
}

/////////////////////////////////////////////////////////

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  //cout << std::fixed << std::setprecision(15);

  Main();
}


Measured memory_bytes: 256