akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<int,int> P;
const LL mod=1000000007;
const LL LINF=1LL<<62;
const LL INF=1<<17;

vector<LL> fact;
vector<LL> inver(200001);

LL combi(int n,int r){
    if(n<r||n<0||r<0) return 0;
    return fact[n]%mod*inver[n-r]%mod*inver[r]%mod;
}

LL hcombi(int n,int r){
    return combi(n+r-1,r); 
}

LL fpow(LL a, LL n){
    LL x = 1;
    while(n > 0){
        if(n&1){
            x=x*a%mod;
        }
        a=a*a%mod;
        n >>= 1;
    }
    return x;
}

void set_combi(){
    LL s=1;
    fact.push_back(1);
    for(int i=1;i<=200000;i++){
        s*=i;
        s%=mod;
        fact.push_back(s);
    }
    inver[200000]=fpow(fact[200000],mod-2);
    for(int i=199999;i>=0;i--){
        inver[i]=inver[i+1]*(i+1)%mod;
    }
}

vector<LL> divi(LL K){
    vector<LL> v;
    for(int i=1;i*i<=K;i++){
        if(K%i) continue;
        v.pb(i);
        v.pb(K/i);
    }
    sort(ALL(v));
    v.erase(unique(ALL(v)),v.end());
    return v;
}

vector<LL> t;
vector<LL> s;
LL N,M;

LL dfs(int k,LL sum,LL c){
    if(c>N||sum==0) return 0;
    if(sum==1){
        return 1;
    }
    if(k==t.size()-1) return 0;
    LL ret=0;
    for(int i=0;i<=s[s.size()-k-1];i++){
        if(i&&sum%t[t.size()-k-1]) break;
        if(i==0) ret+=combi(N-c,i)*dfs(k+1,sum,c);
        else{
            sum/=t[t.size()-k-1];
            ret+=combi(N-c,i)*dfs(k+1,sum,c+i);
        }
        ret%=mod;
    }
    return ret%mod;
}



int main(){
    cin >> N >> M;
    t=divi(M);
    set_combi();
    for(int i=1;i<t.size();i++){
        LL c=0;
        LL k=M;
        for(int c=0;k;c++){
            if(k%t[i]){
                s.pb(c);
                break;
            }
            k/=t[i];
        }
    }
    cout << dfs(0,M,0)%mod << endl;
    return 0;
}


Measured memory_bytes: 3968
#!/usr/bin/env ruby
x = gets.chomp.to_i

ans_a = 0
ans_b = 0
-119.upto(120) do |a|
  -118.upto(119) do |b|
    if a ** 5 - b ** 5 == x
      ans_a = a
      ans_b = b
    end
  end
end

puts "#{ans_a} #{ans_b}"


Measured memory_bytes: 14380
#include <iostream>
#include <map>
#define REP(i, n) for (int i = 0; i < n; ++i)
using namespace std;

int main() {
	int n; cin >> n;
  string s[105];
  map<string, int> mp;
	REP(i,n) cin >> s[i], mp[s[i]]++;
	int m; cin >> m;
  string t;
	while(m--) cin>>t, mp[t]--;
  int mx = 0;
	REP(i,n) mx = max(mx, mp[s[i]]);
	cout << mx << endl;
}

Measured memory_bytes: 256
def not_so_diverse(N: int, K: int, A: int) -> int:
    freq = [0] * N
    for a in A:
        freq[a - 1] += 1

    return sum(sorted(freq, reverse=True)[K:])


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [int(s) for s in input().split()]
    ans = not_so_diverse(N, K, A)
    print(ans)


Measured memory_bytes: 25604
n,m=map(int,input().split())
xs = [int(input()) for _ in range(m)]

broken = [False] * (n + 1)
for x in xs:
    broken[x] = True

cache = [-1] * (n + 1)

def solve(pos, n, broken, cache):
    if pos > n or broken[pos]:
        return 0
    if pos == n:
        return 1
    res = cache[pos]
    if res >= 0:
        return res
    res = solve(pos+1, n, broken, cache) + solve(pos+2, n, broken, cache)
    cache[pos] = res = res % 1000000007
    return res

for tmp in range(n,0,-1):
    solve(tmp,n,broken,cache)

print(solve(0,n,broken,cache))


Measured memory_bytes: 8616
word = input()
word_list = []
for i in range(len(word)):
    word_list.append(word[i])
many_list = []
def how_many():
    how = 0
    first = word_list[0]
    while(True):
        try:
            word_list.remove(first)
            how +=1
        except:
            break
    many_list.append(how)
while(True):
    try:
        how_many()
    except:
        break

for i in range(len(many_list)):
    many_list[i] = many_list[i] % 2

if 1 in many_list:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define LL long long
const int MAXN = 505;
using namespace std;
 
int N, K, a[MAXN], b[MAXN];
 
bool test(int m) {
//	cout << "Test " << m << '\n';
	LL sum = 0;
	for (int i = 0; i < N; i++) {
		b[i] = a[i] % m;
		sum += b[i];
	}
	
	LL pref = 0;
	sort(b, b + N);
	for (int i = 0; i < N - 1; i++) {
		pref += b[i];
		LL cost = max((LL) (N - i - 1) * m - sum + pref, pref);
//		cout << "Get " << cost << '\n';
		if (cost <= K) {
			return true;
		}
	}
	
	return false;
}
 
int main() {
	//ios_base::sync_with_stdio(0); cin.tie(0);
	
	int sum = 0;
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		sum += a[i];
	}
	
	int ans = 1;
	for (int i = 1; i * i <= sum; i++) {
		if (sum % i == 0) {
			if (test(i)) ans = max(ans, i);
			if (test(sum / i)) ans = max(ans, sum / i);
		}
	}
	
	cout << ans << '\n';
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
using ll=long long;
 
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m);i>=(int)(n);--i)
#define rrep(i,m) RREP(i,m,0)
const int MOD=1e9+7;
 
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> void fail(T v){cout << v << endl;exit(0);}
 
void solve(){
    int a,b;
    cin>>a>>b;
    cout << max(0,a-2*b) << endl;
}
 
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};
long double eps = 1e-9;
long double pi = acos(-1);



signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    ll a;
    double b;
    cin>>a>>b;
    cout << a* (ll)(b*100+eps)/100 << endl;

}


Measured memory_bytes: 3732
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;






int main(){
  
  string s,t; 
  cin >> s >> t;
  bool a = true;
  for(int i=0; i<s.size(); i++){
   if(s[i]!=t[i]) a=false;
  }
  
  if(a) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  
  return 0;
  
  
}
  
  


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


ll T, n, x;

ll solve(ll h, ll w) {
	if (h == 0 || w == 0) return 0;
	if (h > w) {
		return w - h + solve(w, h);
	}
	ll ans = w + ((w-1) / h) * h * 2;
	ll ow = w;
	w %= h;
	if (w == 0) w = h;
	ans += w;
	return ans + solve(h - w, w);

}

int main(int argc, char *argv[]){
	ios::sync_with_stdio(false);
	cin >> n >> x;
	ll ans;
	if (x * 2 < n) {
		ans = n + x + solve(n - 2*x, x);
	} else {
		ans = n - x + solve(n - x, x);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt(), w = sc.nextInt(), k = sc.nextInt();
		char[][] a = new char[h][w];
		for (int i = 0; i < h; i++) {
			String s = sc.next();
			for (int j = 0; j < w; j++) {
				a[i][j] = s.charAt(j);
			}
		}
		int ans = 0;
		int max_row = 1<<h, max_col = 1<<w;
//		System.out.println(max_row);
		for (int i = 0; i < max_row; i++) {
			for (int j = 0; j < max_col; j++) {
				int cnt = 0;
				for (int r = 0; r < h; r++) {
					if (((1 << r) & i) == 0) continue;
					for (int c = 0; c < w; c++) {
						if (((1 << c) & j) == 0) continue;
//						if (i == 1 && j == 4) System.out.format("%d %d %c\n", r, c, a[r][c]);
						if (a[r][c] == '#') cnt++;
					}
				}
//				System.out.format("%d %d %d\n", i, j, cnt);
				if (cnt == k) {
					ans++;
				}
			}
		}
		System.out.println(ans);
	}

}



Measured memory_bytes: 35268
n = gets.to_i
a = gets.split.map { |i| i.to_i }
q = gets.to_i
m = gets.split.map { |i| i.to_i }

def solve(i, m, a)
  return true if m == 0
  return false if i >= a.length
  return solve(i+1, m, a) || solve(i+1, m-a[i], a)
end

m.each do |mi|
  if solve(0, mi, a)
    puts "yes"
  else
    puts "no"
  end
end

Measured memory_bytes: 8656
#include <stdio.h>
int main(){
  int n;
  scanf("%d",&n);
  
  switch (n%10){
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
      printf("hon");
      break;
    case 0:
    case 1:
    case 6:
    case 8:
      printf("pon");
      break;
    case 3:
      printf("bon");
      break;
  }
  return 0;
}

Measured memory_bytes: 1732
import sys
f = sys.stdin

while True:
    n = int(f.readline())
    if n == -1:
        break
    location = 1 + 0j
    for i in range(1, n):
        location += (location * 1j) / abs(location)
    print('{:.2f}'.format(location.real))
    print('{:.2f}'.format(location.imag))

Measured memory_bytes: 7672
#include<iostream>
#include<algorithm>

using namespace std;
int main(){
    string s1,s2,s3;
    cin>>s1>>s2>>s3;
    transform(s1.begin(), s1.end(),s1.begin(), ::toupper);
    transform(s2.begin(), s2.end(),s2.begin(), ::toupper);
    transform(s3.begin(), s3.end(),s3.begin(), ::toupper);
    cout<<s1[0]<<s2[0]<<s3[0]<<endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
typedef pair<int, int> P;
string a[1000];
int dp[1000][1000];
int main() {
	int H, W;
	cin >> H >> W;
	for (int i = 0; i < H; i++) cin >> a[i];
	dp[0][0] = 1;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (a[i][j] == '#') continue;
			if (j + 1 < W && a[i][j + 1] != '#') (dp[i][j + 1] += dp[i][j]) %= MOD;
			if (i + 1 < H && a[i + 1][j] != '#') (dp[i + 1][j] += dp[i][j]) %= MOD;
		}
	}
	cout << dp[H - 1][W - 1] << endl;
}


Measured memory_bytes: 5248
from numpy import *;i=int32;p=input;q=searchsorted;N=int(p());A=i(p().split());B=i(p().split());c=0;
for k in range(1,30):
  a,b=sort(hstack((A%(1<<k),A%(1<<k)-2**k))),B%(1<<k);c+=(sum(q(a,2**k-b)-q(a,2**(k-1)-b)))%2<<k-1
print(c)


Measured memory_bytes: 37060
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;

int main() {
	vector<int> anss;
	while (true) {
		int t, d, l;
		cin >> t >> d >> l;
		if (t == 0 && d == 0 && l == 0)break;
		int a;
		int tmp = 0;
		int ans = 0;
		for (int i = 0; i < t;i++) {
			cin >> a;
			if (a >= l) {
				tmp = i + d;
			}
			if (tmp <= i) {
				ans++;
			}
		}
		anss.push_back(t - 1 - ans);
	}
	for (int i = 0; i < anss.size(); i++) {
		if (anss[i] < 0) {
			cout << 0 << endl;
		}
		else {
			cout << anss[i] << endl;
		}
	}
	return 0;
}


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


int main() {
  ll n, d;  cin >> n >> d;
  vector<ll> v(n);
  rep (i, n) {
    ll x, y;  cin >> x >> y;
    v[i] = pow(x, 2) + pow(y, 2);
  }
  
  sort(all(v));
  auto itr = upper_bound(all(v), pow(d, 2));
  int count = itr - v.begin();

  cout << count << endl;
}

Measured memory_bytes: 4840
#include <bits/stdc++.h>
#define FLASH ios_base::sync_with_stdio(0);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";
#define MAXN 200010

using namespace std;

ll n,d,a;
vector<pair<ll,ll> >massiv;

ll lazy[MAXN];

int main(){
FLASH;
cin>>n>>d>>a;
for(ll i=1;i<=n;i++)
{
 ll x,y;
 cin>>x>>y;
 massiv.pb(mp(x,y));
}
sort(all(massiv));

ll ans=0;
for(ll i=0;i<n;i++)
{
  ll xp=massiv[i].second-lazy[i];
  ll nac=i;
  ll konec=n-1;
  ll maxx=0;
  if(xp>0)
  {
   while(nac<=konec)
   {
    ll mid=nac+(konec-nac)/2;
    if(massiv[mid].first-massiv[i].first<=2*d)
    {
	  maxx=max(maxx,mid);
	  nac=mid+1;	
    }  
    else konec=mid-1;
   }	
   ll kol;
   if(xp%a==0)kol=xp/a;
   else kol=xp/a+1;
   ans+=kol;
   lazy[i]+=a*kol;
   lazy[maxx+1]-=a*kol;
  }
  lazy[i+1]+=lazy[i];
}


cout<<ans<<endl;


return 0;
} 


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

int main(){
int N;
cin>>N;
vector<int>A(N);

for(int i=0;i<N;i++){
   cin>>A[i];
}
vector<int>B=A;
sort(B.rbegin(),B.rend());

for(int i=0;i<N;i++){
   int a=B[0];
   if(B[0]==A[i]){
      a=B[1];
   }
   cout<<a<<endl;

}

return 0;
}

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

int main(){
    int N,X;
    cin>>N>>X;
    int m[100],wa=0,mini=1001;
    for(int i=0;i<N;i++){
        cin>>m[i];
        wa+=m[i];
        if(m[i]<mini){mini=m[i];}
    }

    int ans=N;
    X-=wa;
    ans+=X/mini;
    cout<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
class Program
{
    public static void Main()
    {
        var S = Console.ReadLine().Select(e => e - '0').ToArray();
        long L = S.Length;
        long[] a = new long[L + 1];
        long ans = 0;
        long mul = 1;
        for(long i = L - 1; i >= 0; i--)
        {
            a[i] = (a[i + 1] + S[i] * mul) % 2019;
            mul = mul * 10 % 2019;
        }
        int[] b = new int[2019];
        foreach(var e in a)
        {
            b[e]++;
        }
        for (int i = 0; i < 2019; i++)
        {
            ans += (long)b[i] * (b[i] - 1) / 2;
        }
            Console.WriteLine(ans);
    }
}

Measured memory_bytes: 30480
s = input()
l = len(s)
for i in range(l)[::-1]:
    if s[i] == 'W':
        break
    l -= 1
ans = 0
l -= 1
for i in range(l)[::-1]:
    if s[i] == 'B':
        ans += l-i
        l -= 1
print(ans)

Measured memory_bytes: 3500
#include <stdio.h>
int main(void){
int a,b,c;
while(1)
{
    scanf("%d %d %d",&a,&b,&c);
    if(a==-1&&b==-1&&c==-1)break;
    if(a==-1||b==-1)printf("F\n");
    else if(a+b>=80)printf("A\n");
    else if(a+b>=65 && a+b<80)printf("B\n");
    else if(a+b>=50 && a+b<65)printf("C\n");
    else if(a+b>=30 && a+b<50){
    if (c>=50)printf("C\n");
    else printf("D\n");
    }
    else if(a+b<30)printf("F\n");
}
return 0;
}

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

int main() {
  int x, a;
  cin >> x;
  a = 0;
  
  while(x > 0){
    
    if(x % 2 == 0){
      x /= 10;
    }
    
    else{
      x -= 1;
      x /=10;
      a++;
    }
    
  }
  
  cout << a << endl;
}

Measured memory_bytes: 256
a=int(input())
b=int(input())
c=int(input())
q=int(input())
ans=0
for i in range(a+1):
  for k in range(b+1):
    for p in range(c+1):
      if 500*i+100*k+50*p==q:
        ans+=1
print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9)
#define INFLL ((LL)1e18)
#define ALL(x) (x).begin(),(x).end()
#define CTOI(x) (x - 'A') 
#define ctoi(x) (x - 'a')
#define BIT(x) (1 << (x))
using namespace std;
int main(){
    int N;
    cin >> N;
    map<string, int> m;
    vector<int> fast(N+1, INF);
    vector<vector<PII> > road(N+1);
    vector<vector<string > > strs(N);
    REP(i, N){
        string str;
        cin >> str;
        if(str == "goto"){
            strs[i].push_back(str);
            cin >> str;
            strs[i].push_back(str.substr(0, str.size()-1));
        }else{
            strs[i].push_back(str);
            m[str.substr(0, str.size()-1)] = i;
        }
    }
    REP(i, N){
        if(strs[i][0]=="goto"){
            road[i].push_back(PII(m[strs[i][1]], 0));
            road[i].push_back(PII(i+1, 1));
        }else{
            road[i].push_back(PII(i+1, 0));
        }
    }
    priority_queue<PII, vector<PII>, greater<PII> > que;
    que.push(PII(0, 0));
    fast[0]=0;
    while(!que.empty()){
        PII d = que.top();
        que.pop();
        if(fast[d.second] != d.first)continue;
        for(auto &i:road[d.second]){
            int numf = d.first + i.second;
            if(fast[i.first] > numf){
                fast[i.first] = numf;
                que.push(PII(numf, i.first));
            }
        }
    }
    cout << fast.back() << endl;
    return 0;
};



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

using namespace std;
#define mp make_pair
#define pb push_back
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n, q;
vector<LL> st;
vector<LL> cnt;
LL ans[100005] = {};

int main() {
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &q);
    st.pb(n);
    forn(i, q) {
        LL x;
        scanf("%lld", &x);
        while (!st.empty() && st.back() >= x) {
            st.pop_back();
        }
        st.pb(x);
    }
    forn(i, st.size()) cnt.pb(0);
    cnt.back() = 1;
    while ((int)st.size() > 1) {
        LL b = st.back();
        st.pop_back();
        LL c = cnt.back();
        cnt.pop_back();
        while (b > st[0]) {
            int lo = 0, hi = (int)st.size() - 1, mid;
            while (lo < hi) {
                mid = (lo + hi + 1) >> 1;
                if (st[mid] > b) {
                    hi = mid - 1;
                } else {
                    lo = mid;
                }
            }
            cnt[lo] += c * (b / st[lo]);
            b %= st[lo];
        }
        if (b > 0) {
            ans[b] += c;
        }
    }
    ans[st[0]] += cnt[0];
    for (int i = n - 1; i >= 1; --i) {
        ans[i] += ans[i + 1];
    }
    for (int i = 1; i <= n; ++i) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}


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

int main(){
  long long a, b, k;
  cin >> a >> b >> k;
  for(int i = 0; i < k; i++){
    if(i % 2 == 0){
      if(a % 2 == 1) a--;
      b += a / 2;
      a -= a / 2;
    }else{
      if(b % 2 == 1) b--;
      a += b / 2;
      b -= b / 2;
    }
  }
  cout << a << " " << b << endl;
}

Measured memory_bytes: 3620
/*
[arc101] C - Candles
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int MAX_N = 100000;

int N, K;
int x[MAX_N];

ll solve() {
    int ans = 1e9;
    for (int i = 0; i + K <= N; i++) {
        if (x[i] < 0 && x[i + K - 1] < 0) {
            ans = min(ans, -x[i]);
        } else if (x[i] < 0 && x[i + K - 1] >= 0) {
            if (-x[i] > x[i + K - 1]) {
                ans = min(ans, -x[i] + 2 * x[i + K - 1]);
            } else {
                ans = min(ans, -2 * x[i] + x[i + K - 1]);
            }
        } else {
            ans = min(ans, x[i + K - 1]);
        }
    }

    return ans;
}

int main() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> x[i];
    }

    cout << solve() << endl;

    return 0;
}


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


int main(){


    int n, m, c, i, j, t, k;

    int ans = 0;


    cin >> n >> m >> c;


    vector<int> b(m + 1);


    for( i = 1 ; i <= m ; i = i + 1 ){

         cin >> b.at(i);

         }


    for( i = 1 ; i <= n ; i = i + 1 ){

         k = c;

         for( j = 1 ; j <= m ; j = j + 1 ){

              cin >> t;

              k += t * b.at(j);

              }

         if( k > 0 ) ans += 1;

         }
 

    cout << ans << endl;

    return 0;

    }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using vll = vector<ll>;
using vll2 = vector<vector<ll>>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, a;
    cin >> h >> a;
    if (h % a == 0) {
        cout << h / a << endl;
    } else {
        cout << h / a + 1 << endl;
    }
}


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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << "\n";
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define endl "\n"
// gcj print用
#define Case(x) printf("Case #%d: ", x);

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<int>>> vvvl;
typedef vector<PI> vpi;
typedef vector<vector<PI>> vvpi;
typedef vector<vector<vector<PI>>> vvvpi;
typedef vector<PLL> vpl;
typedef vector<vector<PLL>> vvpl;
typedef vector<vector<vector<PLL>>> vvvpl;

int POWINT(int x, int n) {
  int ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

ll POWLL(ll x, int n) {
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

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;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int r, g, b;
  cin >> r >> g >> b;
  if ((g*10+b) % 4 == 0) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

  return 0;
};


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
static const int INF = 2000000000;

int main(){
  int a, b;
  char op;
  cin >> a >> op >> b;
  if (op == '+') cout << a + b << endl;
  else cout << a - b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i < n; i++)
#define elif else if
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
const ll INF = 1e15;

int main(){
    int N, M;
    string S;
    cin >> N >> M >> S;
    vector<int> vec;
    int pos = N;
    while(true){
        if(pos == 0) break;
        bool able = false;
        rep2(i, max(0, pos-M), pos){
            if(S[i] == '0'){
                able = true;
                vec.push_back(pos-i);
                pos = i;
                break;
            }
        }
        if(!able){
            cout << -1 << endl;
            exit(0);
        }
    }
    int n = vec.size();
    for(int i = n-1; i >= 0; i--) cout << vec[i] << endl;
}

Measured memory_bytes: 1144
N, K = map(int, input().split())
A = list(i - 1 for i in map(int, input().split()))
ans = 0
count = 0
X = [-1] * N
Y = - 1
while count < K:
  if X[ans] == -1:
    X[ans] = count
    ans = A[ans]
    count += 1
  else:
    Y = X[ans] + (K - count) % (count - X[ans])
    break
if Y == -1:
  print(ans + 1)
else:
  print(X.index(Y) + 1)


Measured memory_bytes: 32384
#include <iostream>

using namespace std;
 
int main()
{
    int w;
  
    while (cin >> w, w != -1) {
	int ans = 3130;
	w -= 10;
 
	if (w >= 10) {
	    ans -= 10*125;
	    w -= 10;
	} else if (w > 0) {
	    ans -= w*125;
	    w = 0;
	} else {
	    cout << ans << endl;
	    continue;
	}
 
	if (w >= 10) {
	    ans -= 10*140;
	    w -= 10;
	} else if (w > 0) {
	    ans -= w*140;
	    w = 0;
	} else {
	    cout << ans << endl;
	    continue;
	}
     
	if (w > 0) {
	    ans -= w*160;
	} else {
	    cout << ans << endl;
	    continue;
	} 
	cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3072
n,k = map(int,input().split())
h = list(map(int, input().split()))

dp = [0]*n
dp[0] = 0
dp[1] = abs(h[0]-h[1])

for i in range(2,n):
     j = max(0,i-k)
     dp[i] = min([dp[l]+abs(h[i]-h[l]) for l in range(j,i)])

print(int(dp[n-1]))


Measured memory_bytes: 52448
#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
    int n, k;
    scanf("%d %d",&n,&k);
    int h[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&h[i]);
    }

    sort(h, h + n);

    int m = h[k - 1] - h[0];
    for(int i = k - 1; i < n; i++){
        if(m > (h[i] - h[i - k + 1])){
            m = h[i] - h[i - k + 1];
        }
    }
    printf("%d\n",m);
    
    return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
int main(){
	int a, b, c;
	scanf ("%d %d %d",&a, &b, &c);
	if(a>b){
		if(b>=c){
			printf("%d %d %d",c, b, a);
		}else if(b<c && a<=c){
			printf("%d %d %d",b, a, c);
		}else if(b<=c && a>=c){
			printf("%d %d %d",b, c, a);
	}
	}else{
		if(b<=c){
			printf("%d %d %d",a, b, c);
		}else if(b>=c && a<=c){
			printf("%d %d %d",a, c, b);
		}else if(b>c && a>=c){
			printf("%d %d %d",c, a, b);
		}
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 600
#include <iostream>

using namespace std;

const int N = 55;

int x[N];
long long f[N][N * N];

int main() {
  int n, A;
  cin >> n >> A;
  for (int i = 1; i <= n; ++i) {
    cin >> x[i];
  }
  f[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = i - 1; j >= 0; --j) {
      for (int k = N * N - 1; k >= 0; --k) {
        if (k >= x[i]) {
          f[j + 1][k] += f[j][k - x[i]];
        }
      }
    }
  }
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    ans += f[i][A * i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define MAX(X,Y) (*max_element(X,Y))
#define MIN(X,Y) (*min_element(X,Y))
#define NP(X,Y) next_permutation(X,Y)



signed main(){
	int R,D,X;
	cin>>R>>D>>X;
	int last=X;
	for(int i=1;i<=10;i++){
		cout<<R*last-D<<endl;
		last=R*last-D;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

int main() {
  int n, m;
  cin >> n >> m;
  priority_queue<P, vector<P>, greater<P>> que;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    que.push(make_pair(b, a));
  }
  int i = 0, cnt = 0;
  while (!que.empty()) {
    P tp = que.top();
    que.pop();
    if (tp.second >= i) {
      cnt++;
      i = tp.first;
    }
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 1528
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    long long N, A, B;
    cin >> N >> A >> B;

    long long ans;
    if ((B - A) % 2 == 0)
    {
        ans = (B - A) / 2;
    }else
    {
        long long dA, dB;
        dA = A - 1;
        dB = N - B;
        if (dA < dB)
        {
            ans = dA + 1 + (B - A - 1) / 2;
        }else
        {
            ans = dB + 1 + (B - A - 1) / 2;
        }
        
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
s = [["3", "5", "7"]]
for i in range(8):
  t = []
  for x in s[i]:
    t += [x+"3", x+"5", x+"7"]
  s += [t]

n = int(input())
c = 0
for l in s:
  for x in l:
    if len(set(list(x))) == 3 and int(x) <= n:
      c += 1
print(c)

Measured memory_bytes: 5224
#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
 
#define REP(a,b,c) for(ll (a)=(b);(a)<(c);(a)++)
#define PER(a,b,c) for(ll (a)=(b);(a)>=(c);(a)--)
 
ll ii(){ ll x; cin >> x; return x; }
string is(){ string x; cin >> x; return x; }
void oi(ll x){ cout << x; }
void od(ld x){ cout << fixed << setprecision(10) << x; }
void os(string x){ cout << x; }
void oie(ll x){ cout << x << endl; }
void ode(ld x){ cout << fixed << setprecision(10) << x << endl; }
void ose(string x){ cout << x << endl; }
void oe(){ cout << endl; }

ll gcd(ll a, ll b){
    return (a%b)?gcd(b,a%b):b;
}

int main(){
    ll K=ii()+1;
    ll ret=0;
    REP(a,1,K){
        REP(b,1,K){
            REP(c,1,K){
                ll t=gcd(a,b);
                ret+=gcd(t,c);
            }
        }
    }
    oie(ret);
    return 0;
}


Measured memory_bytes: 3624
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;

 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int n = sc.nextInt() ;
    TreeSet<String> pq = new TreeSet<String>();
    for(int i = 0; i < n; i++){
      String comm = sc.nextStr();
      String str = sc.nextStr();
      if(comm.equals("insert")){
        if(!pq.contains(str)){
          pq.add(str);
        }
      }else{
        System.out.println(pq.contains(str) ? "yes" : "no");
      }
    }
  }
 
  
// LinkedList<Integer>[] setsu = new LinkedList[n];
// for(int i = 0; i < n; i++){
//   setsu[i] = new LinkedList<Integer>();
// } 

 //ここからテンプレ
  static class InputReader {
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
      private SpaceCharFilter filter;

      public InputReader(InputStream stream) {
          this.stream = stream;
      }
 
      public int next() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = stream.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextStr() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        StringBuffer str = new StringBuffer();
        do{
          str.append((char)c);
          c = next();
        }while(!isSpaceChar(c));
        return str.toString();
      }

      public int nextInt() {
          int c = next();
          while (isSpaceChar(c))
              c = next();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = next();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = next();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public boolean isSpaceChar(int c) {
          if (filter != null)
              return filter.isSpaceChar(c);
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      public interface SpaceCharFilter {
          public boolean isSpaceChar(int ch);
      }
  }
}

Measured memory_bytes: 172100
fun main(args: Array<String>) {
    while (true) {
        val (n, x) = readLine()!!.split(" ").map { it.toInt() }
        if (n == 0 && x == 0) break
        var count = 0
        for (i in 1..n) {
            for (j in i..n) {
                for (k in j..n) {
                    if (i != j && j != k && i + j + k == x ) count ++
                }
            }
        }
        println(count)
    }
}


Measured memory_bytes: 32076
main = mapM_ (print. solve) . analyze . map read . words =<< getContents
analyze (n:a:b:cs) = let (hs,as) = splitAt n cs in (n,a,b,hs):analyze as
analyze _ = []
solve (n,a,b,hs) = f 0 (maximum $ map (\h->(h+b-1)`div`b) hs) where
  f lo hi
    |lo+1>=hi = hi
    |r>m = f m hi
    |otherwise = f lo m
    where
      m = (lo+hi)`div`2
      r = sum . map g $ hs
      g h = if h<=m*b then 0 else (h-m*b+(a-b)-1)`div`(a-b)

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

int main(){
    int a, b, c,
        cnt = 0;
    cin >> a >> b >> c;
    
    for (int i = a; i < b + 1; i++){
        if(c % i == 0){
            cnt++;
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3104
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));

        }

        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            List<int> nums = new List<int>();
            for(int i = 0; i < N; i++)
            {
                nums.Add(cin.ReadInt);
            }

            nums.Sort((a,b)=>b-a);
            nums = nums.Distinct().ToList();
            WriteLine(nums.Count);
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}

Measured memory_bytes: 13396
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

int N, M;
vector<vector<int>> G;
vector<vector<LL>> dp;

LL dfs1(int v, int p = -1) {
  LL ret = 1;
  for (int i = 0; i < G[v].size(); ++i) {
    int u = G[v][i];
    if (u == p) continue;
    dp[v][i] = dfs1(u, v);
    ret = (ret * (dp[v][i] + 1)) % M;
  }
  return ret;
}

void dfs2(int v, int p = -1, LL add = 0) {
  int n = G[v].size();
  if (n == 0) return;
  for (int i = 0; i < n; ++i) {
    int u = G[v][i];
    if (u == p) {
      dp[v][i] = add;
      break;
    }
  }

  vector<LL> L(n), R(n);
  L[0] = dp[v][0] + 1LL;
  R[n-1] = dp[v][n-1] + 1LL;

  for (int i = 1; i < n; ++i) {
    L[i] = ((dp[v][i] + 1LL) * L[i-1]) % M;
  }
  for (int i = n - 2; i >= 0; --i) {
    R[i] = ((dp[v][i] + 1LL) * R[i+1]) % M;
  }

  for (int i = 0; i < n; ++i) {
    int u = G[v][i];
    if (u == p) continue;

    LL x = 1;
    if (i != 0) x = (x * L[i-1]) % M;
    if (i != n - 1) x = (x * R[i+1]) % M;
    dfs2(u, v, x);
  }
}

int main() {
  N, M; cin >> N >> M;
  G.resize(N);
  for (int i = 0; i < N - 1; ++i) {
    int x, y; cin >> x >> y; --x, --y;
    G[x].push_back(y);
    G[y].push_back(x);
  }

  dp.resize(N);
  for (int v = 0; v < N; ++v) {
    dp[v].resize(G[v].size());
  }

  dfs1(0);
  dfs2(0);

  for (int v = 0; v < N; ++v) {
    LL ans = 1;
    for (LL add : dp[v]) ans = (ans * (add + 1LL)) % M;
    cout << ans << endl;
  }
}


Measured memory_bytes: 25280
#include <iostream>

int main() {
    int s = 0;
    for (int i = 0; i < 3; ++i) {
        int a;
        std::cin >> a;
        s += a;
    }
    std::cout << (s >= 22 ? "bust" : "win") << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include <climits>
#include<fstream>
using namespace std;
//---------------------------------------------------
//library zone!!!!!
typedef long long ll;
typedef long double ld;
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld mod_pow(ld x, ll n, ll p) {
	ld res = 1;
	while (n > 0) {
		if (n & 1) res = res * x;
		x = x * x;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++
signed main() {
	int a,b;
	cin>>a>>b;
	cout<<a*b-a-b+1<<endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int N = 2e5 + 10;
vector<int> a[N];
int tin[N], tout[N];
int idx[N], cnt[N];
int stamp;

void DFS(int u, int parent) {
  idx[stamp] = u;
  tin[u] = stamp++;
  for (auto& v : a[u]) {
    if (v == parent) continue;
    DFS(v, u);
  }
  tout[u] = stamp;
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i < n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    --x; --y;
    a[x].push_back(y);
    a[y].push_back(x);
  }
  stamp = 1;
  DFS(0, -1);

  while (m--) {
    int x, y;
    scanf("%d%d", &x, &y);
    --x;
    cnt[tin[x]] += y;
    cnt[tout[x]] -= y;
  }

  vector<int> ret(n);
  int sum = 0;
  for (int i = 1; i <= n; ++i) {
    sum += cnt[i];
    ret[idx[i]] = sum;
  }

  for (int i = 0; i < n; ++i) {
    printf("%d%c", ret[i], " \n"[i + 1 == n]);
  }
  return 0;
}


Measured memory_bytes: 26368
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;


void main() {
    int N, T;
    scan(N, T);

    auto a = new int[](N);
    auto b = new int[](N);

    foreach (i ; 0 .. N) {
        scan(a[i], b[i]);
    }

    auto dpf = new long[][](N + 1, T);
    foreach (i ; 1 .. N + 1) {
        foreach (j ; 0 .. T) {
            dpf[i][j] = dpf[i - 1][j];
            if (j - a[i - 1] >= 0) chmax(dpf[i][j], dpf[i - 1][j - a[i - 1]] + b[i - 1]);
        }
    }

    auto dpb = new long[][](N + 1, T);
    foreach_reverse (i ; 0 .. N) {
        foreach (j ; 0 .. T) {
            dpb[i][j] = dpb[i + 1][j];
            if (j - a[i] >= 0) chmax(dpb[i][j], dpb[i + 1][j - a[i]] + b[i]);
        }
    }

    long ans;

    foreach (i ; 0 .. N) {
        foreach (j ; 0 .. T) {
            chmax(ans, dpf[i][j] + dpb[i + 1][T - 1 - j] + b[i]);
        }
    }

    writeln(ans);
}






void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


Measured memory_bytes: 146684
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005

int a,b,c;

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> a >> b >> c;
    if(c>b+a+1) cout << 2*b+a+1;
    else cout << b+c;
}


Measured memory_bytes: 256
S = input()

length = len(S)
if length%2 != 0:
    S = S[:-1]
else:
    S = S[:-2]

length = len(S)

notsame = True

while notsame:
    half = int(length/2)
    left = S[0:half]
    right = S[half:length]
    if right == left:
        notsame = False
        print(length)
    else:
        S = S[:-2]
        length = len(S)

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

int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  for(int i=0; i<n; i++) cin >> p[i];
  
  int ans=0;
  for(int i=1; i<n-1; i++) {
    if(p[i]>p[i-1]&&p[i]<p[i+1]||p[i]<p[i-1]&&p[i]>p[i+1]) ans+=1;
  }
  cout << ans << endl;
}

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

#define REP(i, n) for(int i=0;i<(int)n;i++)
typedef long double R;
const R EPS = 1e-10;
struct P{
	R x, y, z;
	P(){}
	P(R x, R y, R z):x(x), y(y), z(z){}
	R norm(){return x*x + y*y + z*z;}
	P operator +(const P &a){return P(a.x+x, a.y+y, a.z+z);}
	P operator -(const P &a){return P(a.x-x, a.y-y, a.z-z);}
	friend istream& operator>>(istream &is, P& p){
		return is >> p.x >> p.y >> p.z;
	}
};

R outp(const P &a, const P &b){
	return a.x*b.x + a.y*b.y + a.z*b.z;
}

int main(){
	while(cin >> n, n){
		vector<P> p(n), v(n);
		vector<R> r(n), vr(n);
		REP(i, n) cin >> p[i] >> v[i] >> r[i] >> vr[i];
		vector<tuple<R, int, int>> ev;
		REP(i, n)REP(j, i){
			R a = (v[i] - v[j]).norm() - (vr[i]+vr[j])*(vr[i]+vr[j]);
			R b = 2*outp(p[i]-p[j], v[i]-v[j]) + 2*(vr[i] + vr[j])*(r[i]+r[j]);
			R c = (p[i] - p[j]).norm() - (r[i]+r[j])*(r[i]+r[j]);
			R d = b*b-4*a*c;
			if(d < -EPS) continue;
			d = max<R>(d, 0);
			REP(k, 2){
				R x = (-b+sqrtl(d)*(k?-1:1))/(2*a);
				if(x > 0) ev.emplace_back(x, i, j);
			}
		}
		vector<R> ans(n);
		REP(i, n) ans[i] = r[i]/vr[i];
		sort(ev.begin(), ev.end());
		for(auto &e : ev){
			R t;int i, j; tie(t, i, j) = e;
			if(ans[i] < t || ans[j] < t) continue;
			ans[i] = ans[j] = t;
		}
		REP(i, n) printf("%.11f\n", (double)ans[i]);
	}
	
	return 0;
}

Measured memory_bytes: 2972
n = int(input())
res = 0
res_array = []
for i in range(1, n+1):
    res += i
    res_array.append(i)
    if res >= n:
        break
diff = res - n
for j in res_array[::-1]:
    if diff -j >= 0:
        diff -= j
        res_array.remove(j)
for k in res_array:
    print(k)


Measured memory_bytes: 3572