akhauriyash/Code-Regression huggingface dataset:
n = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(n)]

for i in range(n-1, -1, -1):
    j = i + 1
    ball = B[i::j]
    if sum(ball) % 2 != A[i]:
        B[i] = 1

print(sum(B))

B_ball = [str(i+1) for i in range(n) if B[i] == 1]
print(" ".join(B_ball))

Measured memory_bytes: 19516
#include <bits/stdc++.h>
#include <limits.h>
#include <algorithm>  
#include <numeric>
#include <sys/resource.h>
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define endl '\n'
using ll = long long;
 
const int precision = 15;
const int modulo =  1000000007; // 10^9 + 7
const ll lmodulo =  1000000007; // 10^9 + 7
 
const double EPS = 1e-9;
const ll inf = 1e18;


void increaseStack() {
	const rlim_t kStackSize = 50 * 1024 * 1024;   // min stack size = 50 MB
	struct rlimit rl;
	int result;

	result = getrlimit(RLIMIT_STACK, &rl);
	if (result == 0) {
		if (rl.rlim_cur < kStackSize) {
			rl.rlim_cur = kStackSize;
		    result = setrlimit(RLIMIT_STACK, &rl);
		    if (result != 0) {
		    	fprintf(stderr, "setrlimit returned result = %d\n", result);
		    }
		}
	}
}

void solve() {
	ll d;
	string k;

	cin >> k >>  d;

	vector<vector<int>> dp(d, vector<int>(2));
	// dp[sum%d][isSmaller]
	dp[0][0] = 1;
	for (int i = 0; i < k.size(); ++i) {
		vector<vector<int>> tmpDp(d, vector<int>(2));
		auto curD = k[i] - '0';
		for (auto s = 0; s < d; ++s) {
			for (auto small : {0, 1}) {
				for (auto digit = 0; digit <= 9; ++digit) {
					if (digit > curD and !small) break;
					auto pSum = (s + digit) % d;
					auto isSmaller = small or (digit < curD);
					auto & curDp = tmpDp[pSum][isSmaller];

					curDp += dp[s][small];
					if (curDp >= lmodulo) {
						curDp -= lmodulo;
					}
				}	
			}			
		}
		swap(dp, tmpDp);
	}

	auto ret = dp[0][0] + dp[0][1];
	ret %= lmodulo;
	ret --;
	if (ret < 0) ret = lmodulo - 1;
	cout << ret;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout.precision(precision);
  cout.setf(ios_base::fixed);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

#define MAX_N   100

#define swap(type, x, y)        do{type t = x; x = y; y = t; } while(0)

int main(void){
    int n,i;
    int a[MAX_N];
    int count = 0;
    
    scanf("%d", &n);
    
    for(i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    
    for(i = 0;  i < n/2; i++){
        swap(int, a[i], a[n-1-i]);
    }
    
    printf("%d", a[0]);
    for(i = 1; i < n; i++)
        printf(" %d", a[i]);
    putchar('\n');
    
    return 0;
}

Measured memory_bytes: 600
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int[] f = new int[31];
		for (int i = 0; i < 28; i++)
			f[s.nextInt()] = 1;
		for (int i = 1; i <= 30; i++)
			if (f[i] == 0)
				System.out.println(i);
	}
}

Measured memory_bytes: 11000
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		if (n == 1) {
			System.out.println("Hello World");
		} else {
			int a = sc.nextInt();
			int b = sc.nextInt();
			System.out.println(a + b);
		}
		sc.close();
	}
}


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

int main(){
    int N, ans=0, tmp=0;
    cin >> N;
    int a[2][N];
    

    for(int i=0; i<2; i++){
	for(int j=0; j<N; j++){
	    cin >> a[i][j];
	}
    }
    int flag = 0;
    for(int i=0; i<N; i++){
	tmp = 0;
	flag = 0;
	for(int j=0; j<N; j++){
	    tmp += a[flag][j];
	    if(i == j){
		flag++;
		tmp += a[flag][j];
	    }		
	}
	ans = max(ans, tmp);
    }
    cout << ans << endl;

}



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

int main() {
    int s;
    cin >> s;
    int l = s / 100, r = s % 100;
    bool yymm = r > 0 && r <= 12, mmyy = l > 0 && l <= 12;

    if (yymm && !mmyy) {
        cout << "YYMM" << endl;
    } else if (mmyy && !yymm) {
        cout << "MMYY" << endl;
    } else if (mmyy && yymm) {
        cout << "AMBIGUOUS" << endl;
    } else {
        cout << "NA" << endl;
    }
}

Measured memory_bytes: 256
#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>;
const int INF=1001001001;

int main() {
  int n;
  cin>>n;
  vector<vector<P>> g(n);
  rep(i,n-1){
    int u,v,w;
    cin>>u>>v>>w;
    u--;v--;
    g[u].emplace_back(P(v,w%2));
    g[v].emplace_back(P(u,w%2));
  }
  vector<int> dist(n,INF);
  dist[0]=0;
  queue <int> q;
  q.push(0);
  while(!q.empty()){
    int now=q.front();
    q.pop();
    for (auto to:g[now]){
      int t1=to.first;
      int t2=to.second;
      if (dist[t1]!=INF) continue;
      dist[t1]=dist[now]+t2;
      q.push(t1);
    }
  }
  rep(i,n){
    cout<<dist[i]%2<<endl;
  }
}


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

using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;

#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
 
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}

void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
////////////////////////////



int main(){fastio
    ll n,k,s;cin>>n>>k>>s;
    ll ma=(ll)1E9;
    if(s==ma){
        rep(i,1,k)cout<<ma<<" ";
        rep(i,k+1,n)cout<<1<<" ";
        cout<<endl;
    }else{
        rep(i,1,k)cout<<s<<" ";
        rep(i,k+1,n)cout<<ma<<" ";
        cout<<endl;
    }
    
    return 0;
}


Measured memory_bytes: 1280
open System

// input
let readStr () = stdin.ReadLine()

let readInt () = stdin.ReadLine() |> int
let readInts () = stdin.ReadLine().Split() |> Array.map int

// utils

let pair = function
| [|a; b|] -> (a, b)
| _ -> failwith "owatta"

let triple = function
| [|a; b; c|] -> (a, b, c)
| _ -> failwith "owatta"

let flip f a b = f b a  

module Option =
  let getOr defaultValue = function
  | Some x -> x
  | None -> defaultValue

let (N, A, B) = readStr().Split() |> Array.map int64 |> triple

let count n = (n / (A+B)) * A + min (n % (A+B)) A

N |> count |> printfn "%d"

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

ll mod_inverse(ll a, ll mod) {
    ll b = mod, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}

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

    vector<ll> C(N);
    C[0] = 1;
    rep(i, N - 1) {
        C[i + 1] += C[i] + mod_inverse(i + 2, MOD);
    }
    ll ans = 0;
    rep(i, N - 1) {
        ll dis = A[i + 1] - A[i];
        ans += dis * C[i];
        ans %= MOD;
    }
    rep2(i, 1, N) {
        ans *= i;
        ans %= MOD;
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


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

int main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 long long m,n;
 cin>>n>>m;
 if(m==1 or n ==1){
	 cout<<1;
 }
 else{
	 cout<<((m*n+1)/2);
 }
}   

Measured memory_bytes: 256
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}


#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8
static const int INF=1<<24;

void mainmain(){
	int n,m,a;
	while(cin>>n>>m>>a,n||m||a){
		vector<vint> bo;
		initvv(bo,2000,n+1);
		// int bo[2000][n+1]={0};
		rep(i,2000){
			rep(j,n+1){
				bo[i][j]=j;
			}
		}
		rep(i,m){
			int x,y,z;
			cin>>x>>y>>z;
			bo[1500-x][y]=z;
			bo[1500-x][z]=y;
		}
		int pos=a;
		rep(i,2000){
			pos=bo[i][pos];
		}
		cout<<pos<<endl;
	}
}



}
main() try{
    mainmain();
}
catch(...){
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define Abs(x)((x) < 0 ? (x) * -1 : (x))

#define rep(x, y) for ((x) = 0; (x) < (y); (x)++)
#define repin(x, y) for ((x) = 0; (x) <= (y); (x)++)
#define nep(x, y) for ((x) = (y) - 1; 0 <= (x); (x)--)
#define nepi(x, y, z) for ((x) = (y) - 1; (z) <= (x); (x)--)
#define repi(x, y, z) for ((x) = (z); (x) < (y); (x)++)
#define repiin(x, y, z) for ((x) = (z); (x) <= (y); (x)++)
#define reps(x, y, z) for ((x) = 0; (x) < (y); (x) += (z))
#define repis(x, y, z, s) for ((x) = (z); (x) < (y); (x) += (s))
#define repit(x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define nepit(x) for (__typeof((x).rbegin()) it = (x).rbegin(); it != (x).rend(); it++)

#define All(x) (x).begin(),(x).end()

#define Mem0(x) memset(x, 0, sizeof(x))
#define Mem1(x) memset(x, -1, sizeof(x))

#define Unique(v) v.resize(unique(All(v)) - v.begin())

#define peq(p0, p1)(p0.first == p1.first && p0.second == p1.second)

#define End '\n'
#define Out(x) cout<<(x)<<End
#define OutP(p, sep, end) cout<<p.first<<sep<<p.second<<end

template<typename T> inline bool Max(T &x, const T &y) { return x < y ? x = y, 1 : 0; }
template<typename T> inline bool Min(T &x, const T &y) { return x > y ? x = y, 1 : 0; }
template<typename T> using V = vector<T>;
template<typename T> using VV = V<V<T> >;

#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lb std::lower_bound
#define ub std::upper_bound

#define lbi(v, x) lb(All(v), (x))-v.begin()
#define ubi(v, x) ub(All(v), (x))-v.begin()

static const ll MOD = 1e9 + 7;
static const double PI = 3.141592653589793;

#define LOCAL 0

int main()
{
#if LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#endif

    cin.tie(0);
    ios::sync_with_stdio(false);
	//std::cout.precision(18);

    string s;

	cin >> s;

	s[3] = '8';

	Out(s);
	
	return 0;
}


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

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vector<int> > Mat;
typedef tuple<int, int, int, int> T;

const int MOD = (int)1e9+7;
const int INF = (int)1e9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

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

    int ans = 0;
    rep(i, N){
        if(H <= A[i] && W <= B[i]) ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define si(X) scanf("%d", &(X))
#define sll(X) scanf("%lld",&(X))
#define INFL 0x3f3f3f3f3f3f3f3fLL
ll gcd(ll a,ll b){
	if(b==0)
	return a;
	return gcd(b,a%b);
}
string toBin(ll a) {
	string res = "";
	while (a) {
		res += char((a & 1) + '0');
		a >>= 1;
	}
	reverse(res.begin(), res.end());
	return res;
}
const int mod = 1e9+7;
ll expo(ll base,ll pow){
    ll ans = 1;
    while(pow!=0){
        if(pow&1==1){
            ans = ans*base;
            ans = ans%mod;
        }
        base *= base;
        base%=mod;
        pow/=2;
    }
    return ans;
}
ll inv(ll x){
    return expo(x,mod-2);
}
bool isPal(string ss){
    int len = ss.length();
    for(int i = 0 ; i<len/2 ; i++){
	int comp = len-i-1;
	if(ss[i]!=ss[comp])
		return false;
	}
    return true;
}
double pi = 3.141592653589793238462643;
double error = 0.0000001;
/* -------Template ends here-------- */

const int M = 10001;
int n;
ll x;
ll arr[M];
ll b[2001][2001];
vector<ll> vec;
int main(){
    //freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);

    si(n);  sll(x);
    int ind = -1;
    ll mi = 1e12;

    for(int i = 0 ; i<n ; i++){
        sll(arr[i]);
    }
    // do for k = 0;
    ll ans = 1e18;
    ll temp = 0;
    for(int i = 0 ; i<n ; i++){
        b[0][i] = arr[i];
        temp += b[0][i];
    }
    ans = min(ans , temp);

    for(int k = 1 ; k<n ; k++){
        temp = 0;
        for(int i = 0 ; i<n ; i++){
            int tt = i - k;
            if(tt<0)
                tt += n;
            b[k][i] = min(b[k - 1][i] , arr[tt]);
            temp += b[k][i];
        }
        temp += k*x;
        ans = min(ans , temp);
    }
    cout<<ans;








}














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

const long long inf=1000000000000000000ll;
long long ans,v[111];
int lx[111],rx[111],ly[111],ry[111],n,x[111],y[111],m,a[331],b[331];
char s[331][3];

namespace flow
{
	struct node{int to,next,c; long long val;}e[200010];
	int n,cnt,hd[410],q[100010],l,r,x,la[410];
	long long dis[410];
	bool inq[410];
	void init(int N)
	{
		n=N,cnt=1;
		for (int i=1; i<=n; i++) hd[i]=0;
	}
	void addedge(int x,int y,int c,long long v)
	{
		e[++cnt]=(node){y,hd[x],c,v},hd[x]=cnt;
		e[++cnt]=(node){x,hd[y],0,-v},hd[y]=cnt;
	}
	pair<int,long long> solve()
	{
		int f=0;
		long long ans=0;
		while (1)
		{
			dis[1]=0,q[l=r=1]=1,inq[1]=1,la[1]=0;
			for (int i=2; i<=n; i++) inq[i]=0,dis[i]=inf,la[i]=0;
			while (l<=r)
			{
				x=q[l++];
				for (int i=hd[x]; i; i=e[i].next)
					if (e[i].c&&dis[e[i].to]>dis[x]+e[i].val)
					{
						dis[e[i].to]=dis[x]+e[i].val,la[e[i].to]=i;
						if (!inq[e[i].to]) inq[e[i].to]=1,q[++r]=e[i].to;
					}
				inq[x]=0;
			}
			if (dis[n]==inf) break;
			x=n; int nw=1000000000;
			while (la[x]) nw=min(nw,e[la[x]].c),x=e[la[x]^1].to;
			x=n,f+=nw;
			while (la[x]) e[la[x]].c-=nw,e[la[x]^1].c+=nw,ans+=e[la[x]].val*nw,x=e[la[x]^1].to;
		}
		return make_pair(f,ans);
	}
}

int main()
{
	scanf("%d",&n),ans=0;
	for (int i=1; i<=n; i++) scanf("%d%d%lld",&x[i],&y[i],&v[i]);
	scanf("%d",&m);
	for (int i=1; i<=m; i++) scanf("%s%d%d",s[i],&a[i],&b[i]);
	for (int i=1; i<=n; i++)
	{
		flow::init(i*2+n*2+2);
		for (int j=1; j<=i; j++) lx[j]=ly[j]=1,rx[j]=ry[j]=100;
		for (int j=1; j<=m; j++)
			if (s[j][0]=='U') {if (b[j]<i) ry[i-b[j]]=min(ry[i-b[j]],a[j]-1);} else
			if (s[j][0]=='D') {if (b[j]<i) ly[b[j]+1]=max(ly[b[j]+1],a[j]+1);} else
			if (s[j][0]=='L') {if (b[j]<i) lx[b[j]+1]=max(lx[b[j]+1],a[j]+1);} else
			if (s[j][0]=='R') {if (b[j]<i) rx[i-b[j]]=min(rx[i-b[j]],a[j]-1);}
		for (int j=2; j<=i; j++) lx[j]=max(lx[j],lx[j-1]),ly[j]=max(ly[j],ly[j-1]);
		for (int j=i-1; j; j--) rx[j]=min(rx[j],rx[j+1]),ry[j]=min(ry[j],ry[j+1]);
		for (int j=1; j<=i; j++) 
		{
			flow::addedge(1,j+1,1,0);
			for (int k=1; k<=n; k++)
				if (x[k]>=lx[j]&&x[k]<=rx[j]) flow::addedge(j+1,k+i+1,1,0);
			flow::addedge(j+i+2*n+1,i*2+n*2+2,1,0);
			for (int k=1; k<=n; k++)
				if (y[k]>=ly[j]&&y[k]<=ry[j]) flow::addedge(k+i+n+1,j+i+2*n+1,1,0);
		}
		for (int j=1; j<=n; j++) flow::addedge(j+i+1,j+i+n+1,1,-v[j]);
		pair<int,long long> nw=flow::solve();
		if (nw.first==i&&-nw.second>ans) ans=-nw.second;
	}
	return printf("%lld\n",ans),0;
}

Measured memory_bytes: 640
#!/usr/bin/env python3

import sys
import math
import itertools

def main():
    a, b, c = map(int, sys.stdin.readline().split())

    if (a == b and a != c) or (a == c and a != b) or (b == c and a != b):
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
while str = gets do
	a = str.split(" ")
	b = Array.new
	a.each do |_a|
		begin
			b.push Float(_a)
		rescue
			n1,n2 = b.pop,b.pop
			if _a == '+'
				b.push n2+n1

			elsif _a == '-'
				b.push n2-n1
			elsif _a == '*'
				b.push n2*n1
			elsif _a == '/'
				b.push n2/n1
			end
		end
	end
	puts b.pop
end

Measured memory_bytes: 6132
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
  string S;
  cin >>S;
  rep(i,S.size()) {
if (S.at(i)=='1') {
S.at(i)='9';
}
    else if (S.at(i)=='9') {
S.at(i)='1';
    }
  }
  cout << S << endl;
}

Measured memory_bytes: 256
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

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

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=1e5+5;
const int mod=1e9+7;

int n,k,h[N],dp[N];
signed main(){
    FastIO;
    cin>>n>>k;
    rep(i,1,n) cin>>h[i];
    rep(i,2,n){
        dp[i]=2e9;
        rep(j,1,k){
            if(i-j>0) dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
        }
    }
    cout<<dp[n];
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf1 INT_MAX
#define inf2 LLONG_MAX
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define sbit __builtin_popcount
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define rit(it,x) for(auto it=x.begin();it!=x.end();it++)
#define cases(t) int t; cin>>t; rep(casn,1,t+1)
#define fill(a,b) memset(a,b,sizeof(a))
#define dbg(x) cerr<<#x<<" "<<x<<endl;
#define dbga(arr,n) cerr<<#arr<<": "; rep(tt,0,n)cerr<<arr[tt]<<" "; cerr<<endl;
#define infile ifstream fin; fin.open("input.txt")
#define outfile ofstream fout; fout.open("output.txt")
#define vec vector<int>
#define pii pair<int,int>
#define plii pair<ll,int>
#define pll pair<ll,ll>
#define p_queue priority_queue< plii,vector< plii >,greater< plii > > 
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sp(x) setprecision(x)
#define si(x) scanf("%d",&x)
#define sc(x) scanf("%c",&x)
#define sl(x) scanf("%lld",&x)
#define sst(x) scanf("%s",x)
#define pl(x) printf("%lld\n",x)
#define pi(x) printf("%d\n",x)
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search

inline ll binex(ll a,ll b)
{
    ll ans=1,temp=a%mod;
    while(b!=0){
        if(b&1) ans=(ans*temp)%mod;
        temp=(temp*temp)%mod;
        b=b>>1;
    }
    return ans;
}

inline double solve(int n,double arr[])
{
    double dp[n+1][n];
    fill(dp,0);
    dp[0][0]=1-arr[0]; dp[1][0]=arr[0];
    rep(i,1,n) dp[0][i]=dp[0][i-1]*(1-arr[i]);
    rep(i,1,n+1){
        rep(j,1,n) dp[i][j]=(1-arr[j])*dp[i][j-1]+arr[j]*dp[i-1][j-1];
    }
    
    /*rep(i,0,n+1){
        rep(j,0,n) cerr<<dp[i][j]<<" "; cerr<<endl;
    }*/
    
    ld ans=0;
    rep(i,0,(n/2)+1) ans+=dp[n-i][n-1];
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin>>n;
    double arr[n];
    rep(i,0,n) cin>>arr[i];
    cout<<fixed<<sp(10)<<solve(n,arr)<<endl;
}

Measured memory_bytes: 70528
#include <stdio.h>

int main(void)
{
	long long int A[100][100], B[100][100], C[100][100] = {0};
	int n, m, l;
	int i, k, j;

	scanf("%d %d %d", &n, &m, &l);

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			scanf("%lld", &A[i][j]);
		}
	}

	for (i = 0; i < m; i++)
	{
		for (j = 0; j < l; j++)
		{
			scanf("%lld", &B[i][j]);
		}
	}

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < l; j++)
		{
			for (k = 0; k < m; k++)
			{
				C[i][j] += A[i][k] * B[k][j];
			}

			printf("%lld", C[i][j]);

			if (j < l - 1)
			{
				printf(" ");
			}
		}

		printf("\n");
	}

	return 0;
}


Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
const ll INF = 1 << 21;
const ll MOD = 1e9 + 7;

static const int N = 1e5;
static const int NIL = -1;

int n, m, q;
vector<int> G[N];
int color[N];

void dfs(int r, int c)
{
    stack<int> S;
    S.push(r);
    color[r] = c;
    while(!S.empty()) {
        int u = S.top();
        S.pop();
        rep(i, G[u].size()) {
            int v = G[u][i];
            if (color[v] == NIL) {
                color[v] = c;
                S.push(v);
            }
        }
    }
}

void assigncolor()
{
    int id = 1; // 同じidがcolorに格納されているときは同じ連結成分にある
    // 初期化
    rep(i, n) {
        color[i] = NIL;
    }
    rep(u, n) {
        if (color[u] == NIL) { // 初期化されていた場合
            dfs(u, id++);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    rep(i, m)
    {
        int s, t;
        cin >> s >> t;
        G[s].push_back(t);
        G[t].push_back(s);
    }

    assigncolor();

    cin >> q;
    rep(i, q)
    {
        int s, t;
        cin >> s >> t;
        if (color[s] == color[t]) {
            puts("yes");
        } else {
            puts("no");
        }
    }
    return 0;
}


Measured memory_bytes: 8944
import java.util.Scanner;

public class Main {
	private static Scanner sc=new Scanner(System.in);
	private static int times=sc.nextInt();
	private static long power;
	public static void main(String[] args){
		power=1;
		for(int i=1;i<=times;i++){
			power=(power*i)%1000000007;
		}
		System.out.println(power);
	}
}

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const ll MOD = 1e9 + 7;
const int MX = 1e5 + 5;

int n;
ll ans;

ll mexp(ll a, ll b) {
	ll res = 1;
	a %= MOD;
	while (b > 0) {
		if (b & 1) {
			res = res * a % MOD;
		}
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}


int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	vector<ll> a(n);
	for (auto& i : a) cin >> i;
	ll factor = 0;
	rep(i, 1, n) {
		factor += mexp(i, MOD - 2);
		factor %= MOD;
		ans += factor * (a[i] - a[i - 1]);
		ans %= MOD;
	}
	
	rep(i, 1, n) {
		ans = ans * i % MOD;
	}
	cout <<  ans;
}


Measured memory_bytes: 3988
import java.util.*;

public class Main {
    static int modP = 1000000007;
    static long inf  = Long.MAX_VALUE;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n   = in.nextInt();
        int m   = in.nextInt();
        List<E> edges = new ArrayList<>();
        for(int i = 0; i < m; i++) {
            int a = in.nextInt()-1;
            int b = in.nextInt()-1;
            long c = -in.nextInt();
            E e = new E(a, b, c);
            edges.add(e);
        }

        long[] dist = new long[n];
        Arrays.fill(dist, inf);
        dist[0] = 0;
        for(int i = 0; i < n-1; i++) {
            for(E e : edges) {
                if(dist[e.from] != inf && dist[e.from] + e.w < dist[e.to]) {
                    dist[e.to] = dist[e.from] + e.w;
                }
            }
        }

        long ans = -dist[n-1];

        for(int i = 0; i < n; i++) {
            for(E e : edges) {
                if(dist[e.from] != inf && dist[e.from] + e.w < dist[e.to]) {
                    dist[e.to] = dist[e.from] + e.w;
                }
            }
        }

        if(ans < -dist[n-1]) {
            print("inf");
        }else{
            print(ans);
        }

    }

    static void print(String s) {
        System.out.println(s);
    }

    static void print(int i) {
        System.out.println(i);
    }

    static void print(long i) {
        System.out.println(i);
    }
}

class E {
    int from, to;
    long w;
    E(int from, int to, long w) {
        this.from = from;
        this.to = to;
        this.w = w;
    }
}


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

long long N;
vector<long long> tree[100005];

long long dfs(long long cur){
	long long ans = 0;
	if(tree[cur].size() == 0){
		return 0;
	}
	vector<long long> chs;
	for(long long i = 0; i < tree[cur].size(); i++){
		chs.push_back(dfs(tree[cur][i]));
	}
	sort(chs.begin(), chs.end());
	long long ret = 0;
	for(long long i = 0; i < chs.size(); i++){
		ret = max(ret, chs[i] + (long long)chs.size() - i);
	}
	return ret;
}

int main(){
	cin >> N;
	for(long long i = 1; i < N; i++){
		long long a;
		cin >> a;
		a--;
		tree[a].push_back(i);
	}

	cout << dfs(0) << endl;
}



Measured memory_bytes: 13568
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a, b;
  cin >> a >> b;
  string ans;
  vector<string> vec(a);
  for (int i = 0; i < a; i++) cin >> vec.at(i);
  sort(vec.begin(), vec.end());
  for (int i = 0; i < a; i++) ans += vec.at(i);
  cout << ans << endl;
}

Measured memory_bytes: 256
MOD=10**9+7
cnt=0; sum=0; prev=nil; can=true; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def desc(ar) ar.sort!{|x,y|y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end

def C(a,b) b==0||a==b ? 1 : (b=a-b if a/2<b;(a-b+1..a).inject(:*)/(1..b).inject(:*)) end

def puts_yesno(can) puts(can ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def debug(k,v) puts "#{k}:#{v}" end
########### ( ˘ω˘ )ｽﾔｧ… ###########
a=gs
b=gs
c=gs
puts a[0]+b[1]+c[2]

Measured memory_bytes: 1788
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

double dp[3010][3010];

int main() {
    int n; cin >> n;
    dp[0][0] = 1;
    vector<double> p(n);
    rep(i,n) cin >> p[i];

    rep(i,n) {
        for (int j = 0; j<=i; ++j) {
            dp[i+1][j+1] += p[i] * dp[i][j];
            dp[i+1][j] += (1-p[i]) * dp[i][j];
        }
    }
    double ans = 0;
    for (int i = (n+1)/2; i<=n; ++i) {
        ans += dp[n][i];
    }
    printf("%.12lf\n",ans);
    return 0;
}






















Measured memory_bytes: 69120
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    set<int>s;
    set<int>::iterator it;
    set<int>h;
    set<int>c;
    set<int>d;
    int t,x;
    char ch;
    cin>>t;
    while(t--)
    {
        cin>>ch>>x;
        if(ch=='S')
        {
            s.insert(x);
        }
        else if(ch=='H')
        {
            h.insert(x);
        }
        else if(ch=='C')
        {
            c.insert(x);
        }
        else if(ch=='D')
        {
            d.insert(x);
        }
    }
    //cout<<endl;
    int cnt=1;
    while(cnt<=13)
    {
        it=s.begin();
        if(!s.empty() && *it==cnt)
        {
            s.erase(*it);
        }
        else
        {
            cout<<"S"<<" "<<cnt<<endl;
        }
        cnt++;

    }
    cnt=1;
    while(cnt<=13)
    {
        it=h.begin();
        if(!h.empty() && *it==cnt)
        {
            h.erase(*it);
        }
        else
        {
            cout<<"H"<<" "<<cnt<<endl;
        }
        cnt++;

    }
    cnt=1;
    while(cnt<=13)
    {
        it=c.begin();
        if(!c.empty() && *it==cnt)
        {
            c.erase(*it);
        }
        else
        {
            cout<<"C"<<" "<<cnt<<endl;
        }
        cnt++;

    }
    cnt=1;
    while(cnt<=13)
    {
        it=d.begin();
        if(!d.empty() && *it==cnt)
        {
            d.erase(*it);
        }
        else
        {
            cout<<"D"<<" "<<cnt<<endl;
        }
        cnt++;

    }
    return 0;


}





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

int main()
{
	ll int x,c=0;
	cin>>x;
	double a=100;
	while(a<x)
	{
		c++;
		a=a*1.01;
		a=(ll int)a;
			}
	cout<<c<<endl;
	
} 




Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define num 1000000007
//#define num 998244353
#define REP(i,a,n) for(ll i=a;i<n;i++)
#define inarr(i,a,n,A) for(ll i=a;i<n;i++) { cin>>A[i]; }
#define vll vector<long long>
#define pii pair <int,int>
#define pll pair<long long, long long>
#define vpii vector< pair <int,int>>
#define vpll vector< pair<long long, long long>>
//#define max(a,b) ((a>b)?a:b)
//#define min(a,b) ((a>b)?b:a)
#define max3(a,b,c) ((a>b)?(a>c)?a:c:(b>c)?b:c)
#define min3(a,b,c) ((a<b)?(a<c)?a:c:(b<c)?b:c)
#define avg(a,b) ((a)+(b))/2
#define pb push_back
#define pob pop_back
#define sf int flag=0     //Remember semicolon
// #define assmin(a,b) if(b<=a) { a=b; }
// #define assmax(a,b) if(b>=a) { a=b; }
#define f first
#define s second
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
#define all(x) x.begin(), x.end()
#define M_PI 3.14159265358979323846
#define epsilon (double)(0.00000000001)
#define side 1e9
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
ll mod(ll a, ll b)
{
	if(a%b<0)
	{
		return a%b + b;
	}
	return a%b;
}
 
 
ll mod_exp(ll a, ll b, ll c)
{
	ll res=1;
	a=a%c;
	while(b>0)
	{
		if(b%2==1)
		{
			res=(res*a)%c;
		}
		b/=2;
		a=(a*a)%c;
	}
	return res;
}
ll mymod(ll a,ll b)
{
    return ((a%b)+b)%b;
}
bool prime[200001];
void SieveOfEratosthenes() 
{ 
    memset(prime, true, sizeof(prime)); 
    prime[1]=false;
    for (int p=2; p*p<=200000; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=200000; i += p) 
                prime[i] = false; 
        } 
    } 
    return;
}
ll powe[200005];
void power()
{
    powe[0]=1;
    REP(i,1,200005)
    {
        powe[i]=mymod(2*powe[i-1],num);
    }
}
ll gcdExtended(ll,ll,ll *,ll *);
ll modInverse(ll a, ll m) 
{ 
    ll x, y; 
    ll g = gcdExtended(a, m, &x, &y); 
        ll res = (x%m + m) % m;
        return res;
} 
ll gcdExtended(ll a, ll b, ll *x, ll *y) 
{ 
    if (a == 0) 
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
    ll x1, y1; 
    ll gcd = gcdExtended(b%a, a, &x1, &y1); 
    *x = y1 - (b/a) * x1; 
    *y = x1; 
    return gcd; 
}
struct node
{
	vpll adj;
    ll biggest;
    ll op;
    ll size;
};

ll find(ll n, ll wt, ll nm)
{
    ll st = 1;
    ll en = nm;
    ll mid = (st) + (en - st)/2;
    while(st<=en)
    {
        if(wt+3*(nm+mid)>=n && wt+2*(nm+mid)<=n)
        {
            return mid;
        }
        else if(wt+3*(nm+mid)<n)
        {
            st = mid+1;
        }
        else
        {
            en = mid-1;
        }
        mid = (st) + (en - st)/2;
    }
    if(wt+3*(nm+mid)>=n && wt+2*(nm+mid)<=n)
    {
            return mid;
     }
    return 0;
}
ll digits(ll a)
{
    ll ans = 0;
    while(a)
    {
        ans++;
        a/=10;
    }
    return ans;
}
bool my(pair<ll, char> p1, pair<ll, char> p2)
{
    return p1.first > p2.first;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll k,a,b;
    cin>>k>>a>>b;
    if(a/k == b/k && a%k!=0 && b%k!=0)
    {
        cout<<"NG\n";
    }
    else
    {
        cout<<"OK\n";
    }
    return 0;
}


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

int main(){

  int n,m,l;
  short a[100][100];
  int b;
  long int c[100][100];

  cin >> n >> m >> l;

  for(int i=0; i<n; i++)
    for(int j=0; j<l; j++)
      c[i][j]=0;

  for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
      cin >> a[i][j];


  for(int i=0; i<m; i++){
    for(int j=0; j<l; j++){
      cin >> b;
      for(int s=0; s<n; s++)
	c[s][j] += b*a[s][i];

    }
  }

  for(int i=0; i<n; i++){
    cout << c[i][0];
    for(int j=1; j<l; j++)
      cout << " " << c[i][j];

    cout << endl;
  }


  return 0;
}

Measured memory_bytes: 1256
fn is_prime(n: usize) -> bool {
    if n <= 1 {
        return false;
    }
    let mut k = 2;
    while k * k <= n {
        if n % k == 0 {
            return false;
        }
        k += 1;
    }
    true
}

fn calc(a: &Vec<usize>, k: usize, n: usize) -> usize {
    if n == 1 {
        return 1;
    }
    if k >= a.len() {
        return 0;
    }
    let mut res = calc(a, k + 1, n);
    for d in 2..(n + 1) {
        if n % d == 0 && d <= a[k] + 1 {
            res += calc(a, k + 1, n / d);
        }
    }
    res
}

fn run() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let n: usize = s.trim().parse().unwrap();
    let mut a = vec![];
    for i in 2..(n + 1) {
        if is_prime(i) {
            let mut c = 0;
            let mut t = n;
            while t >= i {
                c += t / i;
                t /= i;
            }
            a.push(c);
        }
    }
    let ans = calc(&a, 0, 75);
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 4476
N = int(input())
ans = []
M = N + 1 * (N % 2 == 0)
for i in range(1, N + 1):
    for j in range(i + 1, N + 1):
        if i + j == M:
            continue
        ans.append('{} {}'.format(i, j))
print(len(ans))
print('\n'.join(ans))

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int x,y;
    cin>>x>>y;
    if(4*x<y||y%2!=0||x*2>y){
        cout<<"No";
    }
    else
        cout<<"Yes";
}


Measured memory_bytes: 3600
#include<stdio.h>
int sl(int a[],int n){
	int i,min,j,s,c = 0;
	for(i = 0;i < n;i++){
		min = i;
		for(j = i;j < n;j++){
			if(a[j]<a[min]){
				min = j;
			}
			
		}
		if(a[i]!=a[min]){
			
			s = a[i];
			a[i] = a[min];
			a[min] = s;
			c++;
		}
		
	}
	return c;


}
int main (void){
	
	int n,i,c;
	scanf("%d",&n);
	int a[n];
	
	for(i = 0;i < n;i++){
		scanf("%d",&a[i]);
	}
	c = sl(a,n);
	
	for(i = 0;i < n-1; i++){
		printf("%d ",a[i]);
	}
	printf("%d\n",a[n-1]);
	printf("%d\n",c);
	
}


Measured memory_bytes: 2040
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


def read():
    X, N = map(int, input().strip().split())
    P = list(map(int, input().strip().split()))
    return X, N, P


def solve(X, N, P):
    if N == 0:
        return X
    k = 0
    v = 10**5
    for i in range(102, -102, -1):
        if i in P:
            continue
        if v >= abs(X - i):
            v = abs(X - i)
            k = i
    return k


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Measured memory_bytes: 9212
#include <bits/stdc++.h>
using namespace std;
 
#define DEBUG(x) cerr << #x << ": " << x << endl;
#define ll long long
 
int main() {
    int n, k;
    cin >> n >> k;
 
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
 
    sort(v.begin(), v.end(), greater<int>());
 
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += v[i];
    }
 
    cout << sum << endl;
 
    return 0;
}

Measured memory_bytes: 256
from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
B = [0 for _ in range(N+1)]
cnt = 0
cur = 0
delta = 0
flag = 0
while cur<N:
    x = X[cur][0]
    h = X[cur][1]+delta
    if h%A==0:
        n = h//A
    else:
        n = h//A+1
    ind = bisect_right(X,[x+2*D,10**9+1])
    B[cur] += -n*A
    B[ind] += n*A
    cnt += n
    flag = 0
    for i in range(cur,N):
        delta += B[i]
        B[i] = 0
        if X[i][1]+delta>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = N
print(cnt)

Measured memory_bytes: 56788
#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<map>
#include<utility>
#include<cmath>
#include<tuple>
#include<string>
#include<bitset>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
using namespace std;
typedef long long ll;

int main(){
    int h,w; cin>>h>>w;
    if(h==1||w==1){
        cout<<1<<endl;
        return 0;
    }
    cout<<(1LL*h*w+1)/2<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <limits>
#include <iomanip>
#include <queue>
#include <cmath>
#include <math.h>
#include <string>
#include <math.h>
#define PI 3.14159265359
using namespace std;
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; }
const long long INF = 1LL << 60;
using pll = pair<long long, long long>;

int main() {

	// 標準入力が早くなる。Cスタイルの入出力とC++スタイルの入出力を混合させてはならない。
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	vector<int> A(N);

	for (int i = 0; i < N; i++)
	{
		cin >> A.at(i);
	}

	sort(A.begin(), A.end(), greater<int>());


	int sum = accumulate(A.begin(), A.end(), 0);

	if (A.at(M - 1) * 4 * M < sum) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
s = gets.chomp.chars
q = gets.to_i

as = []
bs = []
f = 0
q.times do
  qq = gets.split
  if qq[0] == "1"
    f += 1
  else
    if (qq[1] == "1" && f.even?) || (qq[1] == "2" && f.odd?)
      as << qq[2]
    else
      bs << qq[2]
    end
  end
end

if f.odd?
  s.reverse!
  bs.reverse!
  puts (bs + s + as).join
else
  as.reverse!
  puts (as + s + bs).join
end

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

#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define read()          freopen("fibsubseq.in","r",stdin)
#define write()         freopen("fibsubseq.out","w",stdout)
#define sf(n)           scanf("%d",&n)
#define sfd(n)          scanf("%lf",&n)
#define sl(x)           scanf("%I64d",&x)
#define sfl(n)          scanf("%lld", &n)
#define sfc(n)          scanf(" %c",&n)
#define sful(n)         scanf("%llu",&n)
#define ull             unsigned long long int
#define endll           printf("\n")
#define pf              printf
#define pi              acos(-1.0)
#define eps             1e-10
#define mem(a,b)        memset(a,b,sizeof(a))
#define pb              push_back
#define xx              first
#define yy              second
#define pii             pair<int, int>
#define pll             pair<ll, ll>
#define MP make_pair
#define ll              long long
#define uniq(a)      a.erase(unique(a.begin(), a.end()), a.end())

bool Check(unsigned int  N,int pos){return (bool)(N & (1LL<<pos));}
ll  Set(unsigned int N,int pos){    return N=N | (1LL<<pos);}
#define cnd tree[idx]
#define lnd tree[idx<<1]
#define rnd tree[(idx<<1)+1]
#define lndp (idx<<1),(b),((b+e)>>1)
#define rndp ((idx<<1)+1),(((b+e)>>1)+1),(e)
#define inf 1999999999
#define MX 100005
#define mod  1000000007
#define mod1 1000000009
#define var    int ii,i,j,k,z=0,c=0,t,x,y,l,r,mid
//int dx[8]={0,0,1,1,-1,-1,1,-1};  //8 direction
//int dy[8]={1,-1,1,-1,1,-1,0,0};

bool chk(int x,int pos){return (bool)(x&(1<<pos));}
int Set(int x,int pos){return x=x|(1<<pos);}
int clr(int x,int pos){return x=x&~(1<<pos);}

ll n,m,dp[10005][105][2];
string s;

ll fn(ll pos,ll d,ll small)
{
    if(pos==n)return d==0;
    ll &z=dp[pos][d][small];
    if(z!=-1)return z;
    z=0;
    ll k=s[pos]-48;
    if(small)k=9;
    for(ll i=0;i<=k;i++)
    {
        z+=fn(pos+1,(d+i)%m,small|(i!=k));
        if(z>mod)z%=mod;
    }
    return z;
}

int main()
{
    ll var;
    cin>>s;
    n=s.size();
    sfl(m);
    mem(dp,-1);
    z=fn(0,0,0);
    cout<<(z-1+mod)%mod<<endl;
}


Measured memory_bytes: 17408
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define ln '\n'
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
typedef long long ll;
typedef unsigned long long ull; 
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

const double PI = acos(-1.0);
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int R; cin >> R;
    cout << fixed << setprecision(5) << PI*R*2 << ln;

}

Measured memory_bytes: 3796
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

int main()
{
    int a,b,c;
    cin >>a >>b >>c;

    vector<bool> vis(b,false);

    int now=a%b;
    vis[now]=true;
    while(1)
    {
        (now+=a)%=b;
        if(vis[now]) break;
        vis[now]=true;
    }

    cout << (vis[c]?"YES":"NO") << endl;
    return 0;
}


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

int h, w, k, x[2], y[2];
vector<vector<int> > a;
char c;
queue<pair<int, int> > q;

void R(vector<vector<int> > &a, int h, int w) {
	a.resize(h + 2);
	for(int i = 0; i <= h + 1; ++i) a[i].resize(w + 2);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> h >> w >> k >> x[0] >> y[0] >> x[1] >> y[1];
	R(a, h, w);
	for(int i = 0; i <= h + 1; ++i) {
		for(int j = 0; j <= w + 1; ++j) {
			a[i][j] = -1;
			if(i && j && i <= h && j <= w) {
				cin >> c;
				if(c == '@') a[i][j] = -2;
			}
		}
	}
	a[x[0]][y[0]] = 0;
	q.push({x[0], y[0]});
	while(q.size()) {
		int i = q.front().first, j = q.front().second; q.pop();
		for(int ii = 1; ii <= k; ++ii) {
			int ni = i - ii, nj = j;
			if(!ni || !nj || ni > h || nj > w) break;
			if(a[ni][nj] == -2 || (a[ni][nj] >= 0 && a[ni][nj] <= a[i][j])) {
				break;
			} else if(a[ni][nj] == -1) {
				a[ni][nj] = a[i][j] + 1;
				q.push({ni, nj});
			}
		}
		for(int ii = 1; ii <= k; ++ii) {
			int ni = i, nj = j + ii;
			if(!ni || !nj || ni > h || nj > w) break;
			if(a[ni][nj] == -2 || (a[ni][nj] >= 0 && a[ni][nj] <= a[i][j])) {
				break;
			} else if(a[ni][nj] == -1) {
				a[ni][nj] = a[i][j] + 1;
				q.push({ni, nj});
			}
		}
		for(int ii = 1; ii <= k; ++ii) {
			int ni = i + ii, nj = j;
			if(!ni || !nj || ni > h || nj > w) break;
			if(a[ni][nj] == -2 || (a[ni][nj] >= 0 && a[ni][nj] <= a[i][j])) {
				break;
			} else if(a[ni][nj] == -1) {
				a[ni][nj] = a[i][j] + 1;
				q.push({ni, nj});
			}
		}
		for(int ii = 1; ii <= k; ++ii) {
			int ni = i, nj = j - ii;
			if(!ni || !nj || ni > h || nj > w) break;
			if(a[ni][nj] == -2 || (a[ni][nj] >= 0 && a[ni][nj] <= a[i][j])) {
				break;
			} else if(a[ni][nj] == -1) {
				a[ni][nj] = a[i][j] + 1;
				q.push({ni, nj});
			}
		}
	}
	cout << a[x[1]][y[1]] << endl;
	return 0;
}


Measured memory_bytes: 15060
import sys
n,m=map(int,input().split())
a=[-1 for i in range(n)]

for i in range(m):
    s,c=map(int,input().split())
    s-=1

    if n!=1 and s==0 and c==0:
        print(-1)
        sys.exit()

    if a[s]!=-1 and a[s]!=c:
        print(-1)
        sys.exit()
    else:
        a[s]=c


if n==1 and (a[0]==0 or a[0]==-1):
    print(0)
    sys.exit()

x=""
if a[0]==-1: a[0]=1
for i in range(n):
    if a[i]==-1: a[i]=0
    x+=str(a[i])
print(x)
    


Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<ctime>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<pli> vpli;
typedef vector<vi> mat;
inline ll read(){
	ll Hashimoto=0,Kanna=1;
	char I_Love=getchar();
	while(I_Love<'0'||I_Love>'9'){
		if(I_Love=='-')Kanna=-1;
		I_Love=getchar();
	}
	while(I_Love>='0'||I_Love<='9'){
		Hashimoto=Hashimoto*10+I_Love-'0';
		I_Love=getchar();
	}
	return Hashimoto*Kanna;
}

#define I_Love_Hashimoto_Kanna main
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
#define file freopen("I_Love_Hashimoto_Kanna.out","w",stdout);
#define RE cout<<"I_Love_Hashimoto_Kanna"<<endl;
#define Tone(Kanna) cout<<Kanna<<endl;
#define Tall(Hashimoto,Kanna) for(int I_Love=0;I_Love<Kanna;I_Love++)cout<<Hashimoto[I_Love]<<(I_Love==Kanna-1?"\n":" ");
#define FOR(I_Love,Hashimoto,Kanna) for(int I_Love=Hashimoto;I_Love<Kanna;I_Love++)
#define MP(Hashimoto,Kanna) make_pair(Hashimoto,Kanna)
#define REV(Kanna) reverse(Kanna.begin(),Kanna.end());
#define SORT(Kanna) sort(Kanna.begin(),Kanna.end());
#define inf (int)1e9
#define linf (ll)1e18
#define mod (inf+7)

int a,b;

int I_Love_Hashimoto_Kanna() {
  fastio;
  cin>>a>>b;
  if(a>8||b>8){
  	Tone(":(");
	}
	else {Tone("Yay!");
	}
  
  
  return 0;
}


Measured memory_bytes: 256