akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
  int n,l;
  cin >> n >> l;
  int a[n];
  for(int i=0;i<n;i++) cin >> a[i];
  int len=0;
  int place=-1;
  for(int i=0;i<n-1;i++){
    if(a[i]+a[i+1]>len){
      place=i;
      len=a[i]+a[i+1];
    }
  }
  if(len<l){
    cout << "Impossible" << endl;
  }
  else{
    cout << "Possible" << endl;
    for(int i=1;i<=place;i++){
      cout << i << endl;
    }
    for(int i=n-1;i>place+1;i--){
      cout << i << endl;
    }
    cout << place+1 << endl;
  }
}

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

int main(void){
    int n,ans=0 ;
    cin >> n ;
    int a[n],x[n][n],y[n][n];
    for (int i=0; i<n; i++){
        a[i]=0;
        for (int j=0; j<n; j++){
            x[i][j]=0 ;
            y[i][j]=0 ;
        }
    }
    for (int i=0; i<n; i++){
        cin >> a[i] ;
        for (int j=0; j<a[i]; j++){
            cin >> x[i][j] >> y[i][j] ;
            x[i][j]-- ;
        }
    }
    bool test[n],flag=true ;
    for (int i=0; i<(1<<n); i++){
        int count=0 ;
        flag=true ;
        for (int j=0; j<n; j++){
            if (i&(1<<j)){
                test[j]=true ;
                count++ ;
            } else {
                test[j]=false ;
            }
        }
        for (int j=0; j<n; j++){
            if (test[j]==true){
                for (int k=0; k<a[j]; k++){
                    if (test[x[j][k]]!=y[j][k]){
                        flag=false ;
                    }
                }
            }
        }
        if (flag==true){
            ans=max(ans,count);
        }
    }
    cout << ans << endl ;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args ) throws Exception {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B=  sc.nextInt();
    int coin=0;
    
    for(int i=0;i<2;i++){
     if(A>B){
      coin+=A;
       A-=1;
     }else{
        coin+=B;
       B-=1;
    }
  }System.out.println(coin);
}
}



Measured memory_bytes: 21844
n = int(input())
numList = list(map(int, input().split()))

flag = True
cnt = 0

while flag:
    for i in range(len(numList)):
        if numList[i] % 2 == 1:
            flag = False
            cnt -= 1
            break
        numList[i] /= 2

    cnt += 1
print(cnt)

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

long long calc(int n, int c1, int c2, int s1, int s2, const vector<int>& options,
               int d, int nt, int ot) {
  int b1(d-1), a1(d+1), b2(d-1), a2(d+1);
  while (b1 >= 0 && options[b1] != nt) b1--;
  while (b2 >= 0 && options[b2] != ot) b2--;
  while (a1 < n && options[a1] != nt) a1++;
  while (a2 < n && options[a2] != ot) a2++;
  int x1(d-b1-1), y1(a1-d-1), z1(a1-b1-1), x2(d-b2-1), y2(a2-d-1), z2(a2-b2-1);
  int diff1 = z1*(z1+1)/2-x1*(x1+1)/2-y1*(y1+1)/2;
  int diff2 = z2*(z2+1)/2-x2*(x2+1)/2-y2*(y2+1)/2;
  return (long long) diff1 * c1 - (long long) diff2 * c2 + s1 - s2;
}

int main() {
  int n;
  cin >> n;
  vector<int> c(26);
  vector<array<int, 26>> s(n);
  
  vector<int> last(26, -1);
  
  for (int i = 0; i < 26; ++i)
    cin >> c[i];
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < 26; ++j)
      cin >> s[i][j];
  
  long long total(0);
  vector<int> options(n);
  
  for (int i = 0; i < n; ++i) {
    int neg(0), test(-1);
    for (int j = 0; j < 26; ++j) {
      neg -= c[j] * (i - last[j]);
    }
    
    int max_score = -1e9;
    for (int j = 0; j < 26; ++j) {
      int ss = s[i][j] + neg + c[j] * (i - last[j]);
      if (ss > max_score) {
        max_score = ss;
        test = j;
      }
    }
    total += max_score;
    options[i] = test;
    last[test] = i;
  }
  /* reversed: 109149564 */
  /* sorted: */
  /* stocahstic */
  for (int t = 1; t <= 1500; ++t) {
    for (int dd = 0; dd < n; ++dd) {
      for (int tt = 0; tt < 26; ++tt) {
        if (tt == options[dd]) continue;
        int ot = options[dd];
        long long ns = calc(n, c[tt], c[ot], s[dd][tt], s[dd][ot],
                            options, dd, tt, ot);
        //cout << ns << endl;
        if (ns > 0) {
          total += ns;
          options[dd] = tt;
    	}
      }
    }
  }
  for (const int& i: options) cout << i + 1 << endl;
  
  return 0;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)1e5 + 7;
const int MOD = (int)1e9 + 7;
const ll infint = (ll)4e16 + 3;
const ll inf = (ll)1e18;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s;
	cin >> s;
	ll t = 0, sm = 0, n = s.size();
	for (int i = 0; i < n; i++)
		if(s[i] == 'B')
			t++, sm += i;
	ll sm2 = 0;
	for (int i = n - 1; i >= n - t; i--)
		sm2 += i;
	cout << sm2 - sm;
}



Measured memory_bytes: 720
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
int a[1000][1000],n,m,s[1000][1000],z;
char v[1000][1000];
int main()
{
    cin>>n>>m;
    memset(v,'.',sizeof(v));
    //memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
    	cin>>v[i][j];
    	//if(v=='*')a[i][j]=918293849;
    	//else
    	//a[i][j]=0;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(v[i][j]=='#'){cout<<'#';continue;
            }
            z=0;
            if(v[i-1][j]=='#')z++;
            if(v[i-1][j-1]=='#')z++;
            if(v[i][j-1]=='#')z++;
            if(v[i+1][j-1]=='#')z++;
            if(v[i+1][j]=='#')z++;
            if(v[i+1][j+1]=='#')z++;
            if(v[i][j+1]=='#')z++;
            if(v[i-1][j+1]=='#')z++;
            cout<<z;
        }
        cout<<endl;
    }
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
// #define fore(i,a) for(auto &i:a)
// #define all(x) (x).begin(),(x).end()
// #pragma GCC optimize ("-O3")
// using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
// typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
// template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
// template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

using namespace std;

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

int gcd3(int a, int b, int c)
{
  return gcd(gcd(a,b),c);
}

int main(void)
{
  int a;
  cin>>a;
  
  long int result=0;
  rep(i,1,a+1){
    rep(j,1,a+1){
      rep(k,1,a+1){
        result+=gcd3(i,j,k);
      }
    }
  }
  
  
  
  cout<<result<<endl;
  
  return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;


int main()
{
        ll x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        ll  xx=x2-x1;
        ll  yy=y2-y1;
        ll  x3 = x2-(y2-y1);
	    ll  y3 = y2+(x2-x1);
		ll  x4 = x1-(y2-y1);
		ll  y4 = y1+(x2-x1);
		cout<<x3<<" "<<y3<<" "<<x4<<" "<<y4<<endl;

    return 0;
}


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

using namespace std;

const int N = 3100;
int dp[N][N];

int main(){
	string s, t; cin >> s >> t;
	int lens = s.length(), lent = t.length();
	
	for(int i = 1; i <= lens; i++) for(int j = 1; j <= lent; j++){
		if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
		else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
	}
	
	string res = "";
	int i = lens, j = lent;
	while(i > 0 && j > 0){
		if(dp[i][j] == dp[i-1][j]) i--;
		else if(dp[i][j] == dp[i][j-1]) j--;
		else{
			res += s[i-1];
			i--; j--;
		}
	}
	reverse(res.begin(), res.end());
	cout << res;
	return 0;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> A(H, vector<char>(W));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> A.at(i).at(j);
    }
  }

  int cnt = 0;
  cin >> H >> W;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (A.at(i).at(j) == '#') cnt++;
    }
  }

  if (cnt == H + W - 1)
    cout << "Possible" << endl;
  else
    cout << "Impossible" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,ge,shi,bai;
	cin>>n;
	bai=n/100;
	shi=n/10%10;
	ge=n%10;
	if(bai==7||shi==7||ge==7)cout<<"Yes";
	else cout<<"No"; 
	return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define ft first
#define sc second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=1e5+7;
static const ll MOD=1e9+7;
ll max(ll a, ll b) {return a>b?a:b;}
ll min(ll a, ll b) {return a<b?a:b;}



int main(void) {
  ll N;
  cin >> N;
  ll a[MAX];
  ll b[MAX];
  ll i;
  
  for(i=0; i<=N; i++) {
    cin >> a[i];
  }
  
  for(i=0; i<N; i++) {
    cin >> b[i];
  }
  
  ll ans=0;
  for(i=0; i<N; i++) {
    //左
    if(a[i]>0) {
      if(a[i]>b[i]) {
        ans+=b[i];
        b[i]=0;
      }else {
        ans+=a[i];
        b[i]-=a[i];
      }
    }
    
    //右
    if(a[i+1]>0) {
      if(a[i+1]>b[i]) {
        ans+=b[i];
        a[i+1]-=b[i];
      }else {
        ans+=a[i+1];
        a[i+1]=0;
      }
    }
    
  }

  pt(ans);
}
  
  
  
  
  




Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A,B,T;
    cin >> A >> B >> T;
    ll ans = 0;
    rep(i,1,25){
        if(i*A <= T) ans += B;
    }
    print(ans);
    
    
}

Measured memory_bytes: 256
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    w = list(map(int, input().split()))
    s1 = 0
    s2 = sum(w)
    ans = float('inf')

    for wi in w:
        s1 += wi
        s2 -= wi
        ans = min(ans, abs(s2 - s1))

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


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

using namespace std;

#define ll long long

int main(void){
    int N;
    cin >> N;
    vector<pair<int, int>> stu(N);
    for(int i = 0;i < N;++i){
        cin >> stu[i].first;
        stu[i].second = i+1;
    }

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

    for(int i = 0;i < N;++i){
        cout << stu[i].second << " ";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 1664
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int x = scan.nextInt();
		int i = 1;
		while(x != 0) {
			System.out.println("Case " + i + ": " + x);
			x = scan.nextInt();
			i++;
		}
		scan.close();
	}
}


Measured memory_bytes: 41476
import math
from decimal import Decimal
A,B=list(input().split())
A = int(A)
B =int(B.replace('.',''))
# print(A* B)
hoge=str(A  * B)
if int(hoge) >= 100:

    print(int(str(A  * B)[:-2]))
else:
    print(0)


Measured memory_bytes: 9828
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
typedef pair<double,string> p;
int main() {
	int n;
	while (cin >> n, n) {
		p google[60];
		for (int i = 0; i < n; i++) {
			cin >> google[i].second;
			double p, a, b, c, d, e, f, s, m;
			cin >> p >> a >> b >> c >> d >> e >> f >> s >> m;
			google[i].first = (f*s*m - p) / (a + b + c + (d + e)*m);
		}
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				if (google[i].first < google[j].first)swap(google[i], google[j]);
				else if (google[i].first == google[j].first&&google[i].second > google[j].second)swap(google[i], google[j]);
			}
		}
		for (int i = 0; i < n; i++)cout << google[i].second << endl;
		cout << "#\n";
	}
}

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

using namespace std;

int n,m;
vector<int>v[200005];
int ans=0,c=0;
int dp[200005];
int vis[200005];
int mx=0;
void dfs(int node){
    vis[node]=1;
    for(int j=0;j<v[node].size();j++){
            if(!vis[v[node][j]])
            dfs(v[node][j]);
        dp[node]=max(dp[node],dp[v[node][j]]+1);
        mx=max(mx,dp[node]);
    }
    }


int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
    }
   for(int i=1;i<=n;i++){
    if(!vis[i]){
        dfs(i);
    }
   }
   cout<<mx;

    return 0;
}


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

int main()
{
    double a, b;
    double mean;
    int mean_int;

    cin >> a >> b;
    mean = (a + b) / 2;
    mean_int = (a + b) / 2;

    if (mean > mean_int)
    {
        mean = mean_int + 1;
    }
    else
    {
        mean = mean_int;
    }

    cout << mean << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N - 1; i >= 0; i--)
const ll INF = 1000000000;
//const ll MOD = 1000000007;
const ld PI = (acos(-1));
using Graph = vector<vector<int>>;
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;}
typedef pair<int, int> pair;
bool seen[505][505];

double rad(double a) {return a * 180 / PI;}

//dpTable
//bool dp[100050];
const int MAX = 510000;
const int MOD = 1000000007;

ll RepeatSquaring(ll a, ll n, ll p){
    if(n==0) return 1;
    if(n%2==0){
        ll t = RepeatSquaring(a, n/2, p);
        return t*t % p;
    }
    return (a*RepeatSquaring(a, n-1, p))%p;
}
 
ll nCr(ll n, ll r, ll mod){
    ll mul = 1, div = 1;
    for(ll i = 0; i < r; i++){
        mul *= n - i;
        div *= i + 1;
        mul %= mod;
        div %= mod;
    }   
    return mul * RepeatSquaring(div, mod - 2, mod) % mod;
}

int main(){
    int X,Y;
    cin >> X >> Y;
    if ((X + Y) % 3 != 0) cout << 0 << endl;
    else {
        int A = (2 * X - Y) / 3,B = (2 * Y - X) / 3;
        if (A < 0 || B < 0) cout << 0 << endl;
        else {
            cout << nCr(A + B, A, MOD) << endl;
        }
    }
    return 0;
}

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

using namespace std;

int main() {

	int n, q;
	cin >> n >> q;

	int j = 0;
	vector<vector<int>>Q(n);
	for (int i = 0; i < q; i++) {

		int a;
		cin >> a;

		if (a == 0) {
			int b, c;
			cin >> b >> c;
			Q[b].push_back(c);
		}
		else if (a == 1) {
			int b;
			cin >> b;
			if (!Q[b].empty()) {
				cout << Q[b].front() << endl;

			}
		}
		else if (a == 2) {
			int b;
			cin >> b;
			if (!Q[b].empty()) {
				Q[b].erase(Q[b].begin());
			}
		}
	}


}



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

int main() {
    int num, score, sum, max, min, i;
    while(1){
        cin >> num;
        if(!num)
            break;
        sum=0;
        max=0;
        min=10000;
        for(i=0; i<num; i++){
            cin >> score;
            if(score>max)max=score;
            if(score<min)min=score;
            sum+=score;
        }
        sum-=max;
        sum-=min;
        cout << sum/(num-2) << endl;
    }
    return 0;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IO(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);
const int maxn=1000+7;
int main()
{
   char a[5];
   cin>>a;
   if(a[0]=='9'||a[1]=='9')
   	   cout<<"Yes"<<endl;
   	   else
   	   	   cout<<"No"<<endl;
   	return 0;
}


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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

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 A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

const ll INF = 1e9+7;


int sum_v[2005][2005] = {};
int sum_e[2][2005][2005] = {};
int N, M, Q;
string S[2005];

inline int f(int sum[2005][2005], int x1, int y1, int x2, int y2){
	return sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1];
}

int main(){
	ios_base::sync_with_stdio(false);

	cin >> N >> M >> Q;
	rep(i,N) cin >> S[i];

	rep(i,N) rep(j,M){
		sum_v[i+1][j+1] = sum_v[i+1][j] + sum_v[i][j+1] - sum_v[i][j];
		rep(k,2) sum_e[k][i+1][j+1] = sum_e[k][i+1][j] + sum_e[k][i][j+1] - sum_e[k][i][j];
		if( S[i][j] == '1' ){
			sum_v[i+1][j+1]++;
			if( i>0 && S[i-1][j] == '1' ) sum_e[0][i+1][j+1]++;
			if( j>0 && S[i][j-1] == '1' ) sum_e[1][i+1][j+1]++;
		}
	}

	int ans[Q];
	rep(i,Q){
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int v  = f(sum_v, x1-1, y1-1, x2, y2);
		int e0 = f(sum_e[0], x1, y1-1, x2, y2);
		int e1 = f(sum_e[1], x1-1, y1, x2, y2);
		//cout << v << " " << e0 << " " << e1 << endl;
		ans[i] = v - e0 - e1;
	}

	rep(i,Q) cout << ans[i] << endl;

	return 0;
}

Measured memory_bytes: 53888
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,ll>;
using T = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define prt(v) cout<<v<<"\n";
#define fi(v) get<0>(v)
#define se(v) get<1>(v)
#define th(v) get<2>(v)
#define endl "\n"
template <typename T> bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;


signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    string T;
    cin >> T;
    ll N=T.size();
    ll ans=0;
    for(ll i=0;i<N;++i){
        if(T[i]=='?')T[i]='D';
    }
    for(ll i=0;i<N;++i){
        if(T[i]=='D')ans++;
    }
    for(ll i=0;i<N-1;++i){
        if(T[i]=='P'&&T[i+1]=='D')ans++;
    }prt(T)
    
    return 0;
}


Measured memory_bytes: 3780
#include<stdio.h>
int main()
{
    int x=0,y=0, tmp;
    for (int i=0;;i++){
        scanf("%d%d", &x, &y);
        if ( x == 0 && y == 0 ){
            break;
        }else {
            if ( x>y ){
                tmp = x, x = y, y = tmp;
            }

            printf("%d %d\n", x, y);;
        }       
    }
        return 0;
  }


Measured memory_bytes: 2032
function main()
	H,W,K=map(x->parse(Int,x),split(readline()))
	sx,sy,gx,gy=map(x->parse(Int,x),split(readline()))
	S=readlines()
	D=ones(Int,H,W)*10^9
	D[sx,sy]=1
	Q=[sx=>sy]
	while !isempty(Q)
		x,y=popfirst!(Q)
		for (dx,dy)=(0=>1,0=>-1,1=>0,-1=>0)
			tx,ty=x,y
			E=D[x,y]+1
			for _=1:K
				tx+=dx
				ty+=dy
				if 1<=tx<=H&&1<=ty<=W&&S[tx][ty]=='.'
					if D[tx,ty]>E
						D[tx,ty]=E
						push!(Q,tx=>ty)
					elseif D[tx,ty]<E
						break
					end
				else
					break
				end
			end
		end
	end
	println(D[gx,gy]%10^9-1)
end
main()

Measured memory_bytes: 233200
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define LINT long long

int main(){
  string S, T;
  cin >> S >> T;

  map<char, char> pair1, pair2;
  for(char s='a'; s <= 'z'; ++s) {
    pair1[s]='0';
    pair2[s] = '0';
  }

  bool ans = true;
  REP(i, S.size()){
      if(pair1[S[i]] == '0' && pair2[T[i]] == '0'){
        pair1[S[i]] = T[i];
        pair2[T[i]] = S[i];
      }
      else if(pair1[S[i]] == T[i] && pair2[T[i]] == S[i]) continue;
      else ans=false;
  }


  cout << (ans? "Yes" : "No") <<endl;
  return 0;
}


Measured memory_bytes: 776
keys = ('a'..'z').to_a
values = Array.new(26){0}
alpha_hash = Hash[*[keys, values].transpose.flatten]
s = gets.strip
until s.nil?
	s.chars do |c|
		if c =~ /[a-zA-Z]/
			c.downcase!
			alpha_hash[c] +=  1 
		end
	end
	s = gets
end

alpha_hash.each do |key, value| 
	puts "#{key} : #{value}"
end


Measured memory_bytes: 6896
#define _USE_MATH_DEFINES

#include <iostream>	//cin, cout
#include <vector>	//vector
#include <algorithm> //sort,min,max,count
#include <string>	//string,getline
#include <ios>		//fixed
#include <iomanip>	//setprecision
#include <utility> //swap, pair
#include <cstdlib>	//abs(int)
#include <cmath>	//sqrt,ceil,M_PI, pow, sin
#include <sstream>	//stringstream,getline
#include <numeric>	//gcd, accumlate
#include <deque>	//deque

using namespace std;

int main() {

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

	if ((A + B) % 2 == 0) {
		cout << (A + B) / 2 << endl;
	}
	else {
		cout << "IMPOSSIBLE" << endl;
	}

	return 0;

}

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

using namespace std;

typedef long long ll;
const int MAX=1e9+7;
int main()
{
    int n,x,ans,sum=0,Max=100005;
    int a[105];
    cin>>n>>x;
    for(int i=0;i<n;i++)
        {cin>>a[i];
            sum+=a[i];}
      x-=sum;
      ans=n;
      sort(a,a+n);
      ans+=x/a[0];
      cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int main(){
	string S; cin>> S;
	int N = S.size();
	int ans = N;
	rp(k, 1, N){
		if(S[k-1] != S[k]){
			ans = min(ans, max(k, N-k));
		}
	}
	cout<< ans <<endl;
}


Measured memory_bytes: 512
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>

using namespace std;

struct Cell {
	int pos, height;
};

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

	int A[H][W];
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			scanf("%d", &A[i][j]);
		}
	}
	int C[H + 1][W + 1];
	for (int i = 0; i <= H; ++i) {
		C[i][W] = 0;
	}
	for (int i = 0; i <= W; ++i) {
		C[0][i] = 0;
	}

	for (int j = 0; j < W; ++j) {
		for (int i = 1; i <= H; ++i) {
			if (A[i - 1][j] == 0) {
				C[i][j] = C[i - 1][j] + 1;
			} else {
				C[i][j] = 0;
			}
		}
	}

	int maxArea = 0;
	for (int i = 1; i <= H; ++i) {
		stack<Cell> S;
		for (int j = 0; j <= W; ++j) {
			if (S.empty() || S.top().height < C[i][j]) {
				Cell c;
				c.height = C[i][j];
				c.pos = j;
				S.push(c);
			} else if (S.top().height > C[i][j]) {
				int prePos = j;
				while (!S.empty() && S.top().height > C[i][j]) {
					Cell pop = S.top();
					S.pop();
					int area = (j - pop.pos) * pop.height;
					maxArea = max(maxArea, area);
					prePos = pop.pos;
				}
				Cell c;
				c.height = C[i][j];
				c.pos = prePos;
				S.push(c);
			}
		}
	}
	cout << maxArea << endl;

	return 0;
}

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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int cnt[110] = {};

// n - 1以上の数がある個数
int num(int n) {
    int res = 0;
    for (int i = 0; i < 110; ++i) {
        if (cnt[i] >= n - 1) res++;
    }

    return res;
}

void prime_factor(int n) {
    for (int i = 2; i * i <= n; ++i) {
        if (n % i != 0) continue;

        int num = 0;

        while (n % i == 0) {
            ++num;
            n /= i;
        }

        cnt[i] += num;
    }

    if (n != 1) cnt[n]++;
}

int main() {

    int n; cin >> n;

    for (int i = 1; i <= n; ++i) {
        prime_factor(i);
    }

    int ans = num(75)
            + num(25) * (num(3) - 1)
            + num(15) * (num(5) - 1)
            + num(5) * (num(5) - 1) * (num(3) - 2) / 2;

    cout << ans << endl;
}

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

#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,lessl<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define int long long
#define double long double

#define all(a)      (a).begin(),(a).end()
#define sz(x)       (int)x.size()

#define ff first
#define ss second
#define mp make_pair

#define pb push_back
#define endl "\n"

#define f(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)

#define bp __builtin_popcountll
#define inf 1e18

const int N = 2e5 + 5;
const int M = 1e9 + 7;

vector<int> v[N];
vector<int> vis(N,0);
int ans=0,cnt=0;
void dfs(int x)
{
	vis[x]=1;
	cnt++;
	for(auto X:v[x])
	{
		if(!vis[X])
			dfs(X);
	}
}
void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int t1,t2;
		cin>>t1>>t2;
		v[t1].pb(t2);
		v[t2].pb(t1);
	}
	for(int i=1;i<=n;i++)
		{
			if(!vis[i])
			{
				dfs(i);
				ans=max(ans,cnt);
				cnt=0;
			}
		}
	
	cout<<ans<<endl;
}

signed main()
{
	FAST

#ifndef ONLINE_JUDGE
	freopen("input_sublime.txt", "r", stdin);
	freopen("output_sublime.txt", "w", stdout);
#endif

	int t = 1;
	// cin>>t;
	for (int tc = 1; tc <= t; tc++)
	{
		// cout<<"Case #"<<tc<<": ";
		solve();
	}

#ifndef ONLINE_JUDGE
	cout << "\nTime Elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " sec\n";
#endif
}


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

int main() {
	string S;
	cin >> S;
	sort(S.begin(), S.end());
	if (S[0] == S[1] && S[1] != S[2] && S[2] == S[3]) cout << "Yes";
	else cout << "No";
}

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

int main() {
  string S;
  string heisei = "2019/04/30";
  cin >> S;
  int year  = (S[0] - '0') * 1000 +(S[1] - '0') * 100 + (S[2] - '0') * 10 + (S[3] - '0') * 1;
  int month = (S[5] - '0') * 10 + (S[6] - '0') * 1;
  int date  = (S[8] - '0') * 10 + (S[9] - '0') * 1;

  if(year > 2019)
  {
    cout << "TBD" << endl;
    return 0;
  }
  else if(2019 == year)
  {
    if(month > 4)
    {
      cout << "TBD" << endl;
      return 0;
    }
    else if(4 == month)
    {
      if(date > 30)
      {
        cout << "TBD" << endl;
        return 0;
      }
    }
  }

  cout << "Heisei" << endl;

  return 0;  

}

Measured memory_bytes: 256
def partition(A, p, r):
  x = A[r]
  i = p - 1
  for j in range(p, r):
    if A[j] <= x:
      i += 1
      A[i], A[j] = A[j], A[i]
  A[i+1], A[r] = A[r], A[i+1]
  return i+1

def main():
  n = int(input())
  A = list(map(int, input().split()))
  q = partition(A, 0, n-1)

  A[q] = "[%d]"%A[q]
  print(" ".join(map(str, A)))

if __name__ == "__main__":
  main()

Measured memory_bytes: 18364
#include <cstdio>
#include <string>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> PQ;
    char com[10];
    int key;
    
    while(1) {
        scanf("%s", com);
        if(com[0] == 'e' && com[1] == 'n') break;
        else if(com[0] == 'i') {
            scanf("%d", &key);
            PQ.push(key);
        } else {
            printf("%d\n", PQ.top());
            PQ.pop();
        }
    }
    
    return 0;
}


Measured memory_bytes: 6504
#include <cstdio>
#include <cstring>

int mp[128][128];
int t[64][64];
int n, m;
int ax, ay;

using namespace std;

void rotate()
{
	int r[64][64];
	for (int j = m - 1; j >= 0; j--){
		for (int i = 0; i < m; i++){
			r[m - 1 - j][i] = t[i][j];
		}
	}
	
	for (int i = 0; i < m; i++){
		for (int j = 0; j < m; j++){
			t[i][j] = r[i][j];
		}
	}
}

void search(int ty, int tx)
{
	int mx, my;
	mx = my = 128;
	for (int i = ty; i < ty + m; i++){
		for (int j = tx; j < tx + m; j++){
			if (t[i - ty][j - tx] != -1 && t[i - ty][j - tx] != mp[i][j]){
				return;
			}
			if (t[i - ty][j - tx] == mp[i][j] && my == 128){
				my = i;
				mx = j;
			}
		}
	}
	if (my < ay || (my == ay && mx < ax)){
		ax = mx;
		ay = my;
	}
	return;
}

int main()
{
	while (scanf("%d %d", &n, &m) && n){
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				scanf("%d", &mp[i][j]);
			}
		}
		
		for (int i = 0; i < m; i++){
			for (int j = 0; j < m; j++){
				scanf("%d", &t[i][j]);
			}
		}
		
		ax = 128, ay = 128;
		for (int i = 0; i < 4; i++){
			for (int j = 0; j <= n - m; j++){
				for (int k = 0; k <= n - m; k++){
					search(j, k);
				}
			}
			rotate();
		}
		
		if (ax != 128){
			printf("%d %d\n", ax + 1, ay + 1);
		}
		else {
			printf("NA\n");
		}
	}
	
	return (0);
}

Measured memory_bytes: 1120
#include<iostream>
using namespace std;
 
int main(){
  int n,a[100];
  cin>>n;
  for(int i=0;i<n;i++)cin>>a[i];
  for(int i=1;i<n;i++){
    for(int k=0;k<n;k++){
      cout<<a[k];
      if(k==n-1)cout<<endl;
      else cout<<" ";
    }
    int v=a[i],j=i-1;
    while(j>=0&&a[j]>v){
      a[j+1]=a[j];
      j--;
    }
    a[j+1]=v;
  }
  for(int k=0;k<n;k++){
    cout<<a[k];
    if(k==n-1)cout<<endl;
    else cout<<" ";
  }
  return 0;
}



Measured memory_bytes: 3116
#include <bits/stdc++.h>
#define ll long long int

using namespace std;

int main(){
    ll d,t,s;
    double ans;
    cin>>d>>t>>s;
    ans=(double)d/s;
    //cout<<ans<<endl;
    if(ans<=t)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}


Measured memory_bytes: 3628
import math
src = [input() for _ in range(5)]
k_li = []
v_li = []
sum = 0
for s in src:
    if int(s[-1]) != 0:
        k_li.append(int(s[-1]))
        v_li.append(int(s))
    else:
        sum += int(s)
flag = False
if len(k_li)>0:
    m = min(k_li)
    for k,v in zip(k_li,v_li):
        if k == m and flag == False:
            sum += v
            flag = True
        else:
            sum += math.ceil(v/10)*10
print(sum)

Measured memory_bytes: 3064
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> P;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=99999999999999;

int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> p(n);
    vector<ll> c(n);
    for(ll i=0;i<n;i++){
        cin>>p[i];
        p[i]--;
    }
    for(ll i=0;i<n;i++){
        cin>>c[i];
    }

    vector<P> memo(n);
    vector<ll> visited(n,0);

    for(ll i=0;i<n;i++){
        ll now = i;
        ll score = 0;
        ll roop = 0;
        while(true){
            now=p[now];
            if(visited[now]==2) break;
            if(visited[now]==1){
                visited[now]++;
                memo[now].first=score;
                memo[now].second=roop;
            }else{
                visited[now]++;
                score+=c[now];
                roop++;
            }
        }
    }

    ll ans=-INF;
    for(ll i=0;i<n;i++){
        //cout<<i<<":";
        ll score=memo[i].first;
        ll roop=memo[i].second;
        ll sub=0;
        if(score>=0 && k>roop){
            sub+=score*(k/roop - 1);
            ans=max(ans,sub);
            ll now=i;
            ll f=k%roop + roop;
            while(f){
                now=p[now];
                sub+=c[now];
                ans=max(ans,sub);
                f--;
            }
        }else{
            ll now=i;
            ll f=min(k,roop);
            while(f){
                now=p[now];
                sub+=c[now];
                ans=max(ans,sub);
                f--;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3824
N, M = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(N)]
c = [list(map(int, input().split())) for _ in range(M)]
for i in range(N):
    m = 0
    for j in range(M):
        if abs(s[i][0]-c[m][0]) + abs(s[i][1]-c[m][1]) > abs(s[i][0]-c[j][0]) + abs(s[i][1]-c[j][1]):
            m = j
    print(m+1)


Measured memory_bytes: 70820
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
lr = [[int(i) for i in readline().split()] for _ in range(n)]

from operator import itemgetter
lr.sort(key=itemgetter(1),reverse=True)

a,b = lr.pop()
lr.sort(reverse=True) #L大きい順

if n == 2:
    c,d=lr[0]
    print(d-c+1+b-a+1)
    exit()

#ひとつだけ[a,b]と逆
#print(a,b,lr)
res = 0
for l,r in lr[1:]:
    res = max(res,r-l+1)
#print(res,b,lr[0][0])
ans = res + max(0,b-max(a,lr[0][0])+1)

# [l,r] より右はぜったい逆
c,d = lr[0]
for l,r in lr[1:]:
    res = max(d-c+1,0) + max(b-l+1,0)
    ans = max(ans,res)
    c = max(c,l)
    d = min(d,r)


#[a,b]以外あっち
c = 0
d = 10**9
for l,r in lr:
    c = max(c,l)
    d = min(d,r)
ans = max(ans,max(d-c+1,0)+b-a+1)


print(ans)









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

using namespace std;

int main () {
	int n, m;
  	cin >> n >> m;
  	int s = n - 2 * m;
  
  	if (s <= 0) {
    	cout << "0\n";
    } else {
    	cout << s << "\n";
    }
}

Measured memory_bytes: 256
N = int(input())

for h in range(1,3501):
  for n in range(1,3501):
    if 4*h*n - N*n - N*h != 0:
      w = (N*h*n)/(4*h*n - N*n - N*h)
    else:
      continue
    if w > 0 and w == int(w):
      print(h,n,int(w))
      exit()

Measured memory_bytes: 72948
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var line = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = line[0], X = line[1];

            var array = Console.ReadLine().Split().Select(int.Parse).ToArray();

            var total = 0;
            var count = 1;
            for (var i = 0; i < N; i++)
            {
                total += array[i];
                if (total <= X) count++;
            }

            Console.WriteLine(count);
        }
    }
}


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

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

	std::string S;
	S.reserve(N);
	std::cin >> S;

	std::vector<int> counts;
	counts.reserve(N);

	{
		char prevBit = S[0];

		counts.emplace_back(0);
		for (char bit : S)
		{
			if (bit != prevBit)
			{
				counts.emplace_back(0);
			}

			counts.back()++;
			prevBit = bit;
		}
	}

	for (int i = 1; i < counts.size(); i++)
	{
		counts[i] += counts[i - 1];
	}

	int maxSum = 0;

	if (S[0] == '0')
	{
		maxSum = counts[std::min(2 * K - 1, (int)counts.size() - 1)];
	}

	for (int index = (S[0] == '0'); index < counts.size(); index += 2)
	{
		int sum = counts[std::min(index + 2 * K, (int)counts.size() - 1)];
		if (index - 1 >= 0) { sum -= counts[index - 1]; }

		maxSum = std::max(maxSum, sum);
	}

	std::cout << maxSum << std::endl;
}


Measured memory_bytes: 768
#include <iostream>
#include <cmath>

int main() {
  int N, Y;
  std::cin >> N >> Y;
  
  int c = Y/1000 - N;
  for (int x=0; 9*x<=c; x++) {
    if ( (c-9*x)%4 == 0 ) {
      int y = (c-9*x)/4;
      int z = N - x - y;
      if (y<0 or z<0) continue;
      std::cout << x << " " << y << " " << z << std::endl;
      return 0;
    }
  }
  std::cout << "-1 -1 -1" << std::endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) > (b) ? (b) : (a))
#define abs(x) ((x) > 0 ? (x) : -(x))
#define MOD 1000000007 //10^9 + 7
#define endl printf("\n")
typedef long long ll;

int
main(int argc,char *argv[])
{
  int h, w;
  scanf("%d %d", &h, &w);

  char s[100][101];
  for (int i = 0; i < h; i++) scanf("%s", s[i]);

  for (int i = 0; i < w + 2; i++) printf("#"); endl;
  for (int i = 0; i < h; i++) printf("#%s#\n", s[i]);
  for (int i = 0; i < w + 2; i++) printf("#"); endl;

  return 0;
}

  


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

#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const ll INF = (ll)1<<62;
const ll MOD = 1e9+7;

const double PI = 3.141592653589793238;

int main(){
	double a, b, h, m;
	cin>>a>>b>>h>>m;
	double d1 = 30*h+0.5*m;
	double d2 = 6*m;
	double diff = fabs(d1-d2);
	if(diff>180)
		diff = 360-diff;
	double radd = diff*PI/180;
	double ans = sqrt(a*a + b*b - 2*a*b*cos(radd));
	cout<<setprecision(12)<<fixed<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 4292
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int price[]={10,50,100,500};
int have[4],ans[4],use[4];
int sml=1e9;
int x;

void solve(int cur){
	if(cur==4){
		int sum=0;
		for(int i=0;i<4;i++)	sum+=use[i]*price[i];
		sum-=x;
		if(sum<0)	return;
		int ret=0;
		for(int i=0;i<4;i++)	ret+=have[i]-use[i];
		ret+=sum/500;	sum%=500;
		ret+=sum/100;	sum%=100;
		ret+=sum/50;	sum%=50;
		ret+=sum/10;
		if(ret<sml){
			sml=ret;
			for(int i=0;i<4;i++)	ans[i]=use[i];
		}
	}
	else{
		for(int i=0;i<=have[cur];i++){
			use[cur]=i;
			solve(cur+1);
		}
	}
}

int main(){
	bool fst=true;
	while(true){
		cin>>x;
		if(x==0)	break;
		if(!fst)	cout<<endl;
		for(int i=0;i<4;i++)	cin>>have[i];
		sml=1e9;
		solve(0);
		for(int i=0;i<4;i++){
			if(ans[i]==0)	continue;
			cout<<price[i]<<" "<<ans[i]<<endl;
		}
		fst=false;
	}
	return 0;
}

Measured memory_bytes: 3092
k = int(input())
lunlun = [i+1 for i in range(9)]

def generate_lunlun(p):
    last = p % 10
    if last - 1 >= 0:
        yield p * 10 + last - 1
    yield p * 10 + last
    if last + 1 <= 9:
        yield p * 10 + last + 1
        

p = 0
while len(lunlun) < k:
    for new_lunlun in generate_lunlun(lunlun[p]):
        lunlun.append(new_lunlun)
    p += 1
        
print(lunlun[k-1])

Measured memory_bytes: 7168
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
 
/*** Template Begins ***/
 
typedef unsigned long long    ll;
typedef pair<ll,ll>  pll;
typedef pair<ll, pair<int, int> > plll;
typedef vector<long long>  vll;
typedef vector<pll>  vp;
typedef long double ld;
#define pb           push_back
#define INF          INT_MAX/10
#define F            first
#define S            second
#define mp           make_pair
// #define ios          ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define hell         1000000007
// #define h 998244353
#define all(a)       (a).begin(),(a).end()
ll power(ll x, ll y, ll p)
{
  ll res = 1;
  x = x % p;
  while (y > 0)
  { 
    if (y & 1) 
      res = (res*x) % p;
    y = y>>1;
    x = (x*x) % p;
  } 
  return res; 
} 
const int MAXN = 2e5+5;

// Debug //
#define trace(x)                 cerr << #x << ": " << x << endl;
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
// #define trace6(a, n,i;b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// Constants //
 
/*** Template Ends ***/
string s;
ll n;
string t;
ll cache[105][4][2];
ll solve(ll index,ll k,ll flag)
{
  // cout<<t<<endl;
  if(k==0)
  {
    // cout<<t<<" ";
    return 1;
  }
  if(index==n)
  {
    if(k)
      return 0;
    else
    {
      // trace(t);
      return 1;
    }
  }

  if(cache[index][k][flag]!=-1)
    return cache[index][k][flag];
  cache[index][k][flag]=0;
  ll limit,i,newk=k,newflag=flag;
  if(flag)
    limit = 9;
  else
    limit = s[index]-'0';
  for(i=0;i<=limit;i++)
  {
    newflag = flag;
    newk=k;
    if(i!=0)
      newk = k-1;
    if(i<limit)
      newflag=1;
    // trace3(index+1,newk,newflag);
    // t.push_back(i+'0');
    cache[index][k][flag] += solve(index+1,newk,newflag);
    // t.pop_back();
  }
  return cache[index][k][flag];
}
void solve()
{
  cin>>s;
  n = s.length();
  ll k,i,j;
  cin>>k;
  memset(cache,-1,sizeof(cache));
  cout<<solve(0,k,0);
}
int main()
{ 
  // ios;
  // fxreopen("inputt.txt", "w", stdout);
  ll t;
  // cin >> t;
  t=1;
  while(t--)
    solve();
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define base 950527
#define base2 1777771
#define N 1001
using namespace std;
typedef unsigned long long ull;
ull a[N][N],b[N][N],A[N][N],tmp[N][N],ans;


void Reverse(int p){for(int i=0;i<p;i++)reverse(b[i],b[i]+p);}

void rol_90(int p){
  for(int i=0;i<p;i++)
    for(int j=0;j<p;j++) tmp[p-j-1][i]=b[i][j];
  
  for(int i=0;i<p;i++)
    for(int j=0;j<p;j++) b[i][j]=tmp[i][j];
}

ull ctoi(char ch){
  if('A'<=ch&&ch<='Z') return ch-'A';
  if('a'<=ch&&ch<='z') return 26+ch-'a';
  if(isdigit(ch)) return 52+ch-'0';
  if(ch=='+') return 62;
  return 63;
}

void in(int w,int h,ull tmp[1001][1001]){
  string str[1001];
  for(int i=0;i<h;i++) cin>>str[i];
  
  for(int i=0;i<h;i++)
    for(int j=0;j<(int)str[i].size();j++)
      for(int k=0;k<6;k++)tmp[i][6*j+5-k]=(ctoi(str[i][j])>>k)&1;
}

set <ull> S;
void roll_hs(int w,int h,int p){
  ull target=0;
  for(int i=0;i<p;i++){
    ull k=0;
    for(int j=0;j<p;j++)k=k*base+b[i][j];
    target=target*base2+k; 
  }
  
  if(S.count(target))return;
  S.insert(target);
  
  for(int i=0;i<h;i++){
    ull k=0,l=1;
    for(int j=0;j<w;j++){
      k=k*base+a[i][j];
      if(j-p>=0) k-=l*a[i][j-p];
      else l*=base;
      A[i][j]=k;
    }
  }

  for(int j=p-1;j<w;j++){
    ull k=0,l=1;
    for(int i=0;i<h;i++){
      k=k*base2+A[i][j];
      if(i-p>=0) k-=l*A[i-p][j];
      else l*=base2;
      if(target==k&&i>=p-1)ans++;
    }
  }
}

int main(){
  while(1){
    int w,h,p;
    cin>>w>>h>>p;
    if(!w&&!h&&!p)break;
    in(w,h,a),in(p,p,b);

    ans=0,S.clear();
    for(int i=0;i<4;i++){
      rol_90(p),roll_hs(w,h,p); 
      Reverse(p),roll_hs(w,h,p),Reverse(p);
    }
    cout <<ans<<endl;
  }
  return 0;
}

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

int main() {
  long n,a,zenhan=0,kohan=0,ans=-9999999999999999;
  cin >> n;
  priority_queue<long> a1;
  vector<long> a2(n);
  priority_queue<long> a3;
  vector<long> a1max(n+1);
  vector<long> a3min(n+1);
  for(long i=0;i<n;i++) {
    cin >> a;
    zenhan+=a;
    a1.push(0-a);
  }
  for(long i=0;i<n;i++) cin >> a2[i];
  for(long i=0;i<n;i++) {
    cin >> a;
    kohan+=a;
    a3.push(a);
  }
  a1max[0]=zenhan;
  a3min[0]=kohan;
  for(long i=0;i<n;i++) {
    a1.push(0-a2[i]);
    a=0-a1.top();
    a1.pop();
    zenhan+=a2[i]-a;
    a1max[i+1]=max(a1max[i],zenhan);
  }
  for(long i=0;i<n;i++) {
    a3.push(a2[n-i-1]);
    a=a3.top();
    a3.pop();
    kohan+=a2[n-i-1]-a;
    a3min[i+1]=min(a3min[i],kohan);
  }
  for(long i=0;i<=n;i++) {
    ans=max(ans,a1max[i]-a3min[n-i]);
  }

  cout << ans << endl;
}

Measured memory_bytes: 4852
#include <bits/stdc++.h>
#define ok cout<<"ok"<<endl
#define dbg(x) cout<<(#x)<<" is "<<x<<endl
using namespace std;
typedef long long ll;
const int N=100009;
int palindrome(string s)
{
   string rs=s;
   reverse(rs.begin(),rs.end());

   if(s==rs) return 1;
   else return 0;
}
int main()
{
  string s,s1="",s2="";
  cin>>s;
  int i,len=s.size(),n;
  n=(len-1)/2;
  for(i=0; i<n; i++)
  {
     s1+=s[i];
  }

  for(i=(len+3)/2-1; i<len; i++)
  {
     s2+=s[i];
  }

   if(palindrome(s) && palindrome(s1) && palindrome(s2))
   {
     cout<<"Yes"<<endl;
   }
   else
    cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;
int n;
int x[8], y[8];
double dist(int i,int j){
    double dx=(x[i]-x[j])*(x[i]-x[j]);
    double dy=(y[i]-y[j])*(y[i]-y[j]);
    return sqrt(dx+dy);
}
int main(void){
    int n; cin >> n;
    for(int i=0;i<n;i++){
        cin >> x[i] >> y[i];
    }
    double ans = 0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            ans += dist(i,j)*2.0/n;
        }
    }
    printf("%.10f\n",ans);
}
/*
sum = S[i<j]dist(i,j)*2(n-1)!/n!
*/


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, a) for (int i = 0; i < (a); i++)
#define int long long
using namespace std;

struct Q {
	int q, x, s, t;
};

int q, r, l;
vector<int> a;
vector<Q> que;

int cal(int mid){
	int cur = a[mid];
	rep(i,q){
		if(que[i].q == 1){
			if(cur >= que[i].x){
				cur = (cur + que[i].s) * que[i].t;
			}
		}else{
			if(cur <= que[i].x){
				cur = (cur - que[i].s) / que[i].t;
			}
		}
	}
	return cur;
}

bool isOk_max(int mid) {
	int cur = a[mid];
	rep(i,q){
		if(que[i].q == 1){
			if(cur >= que[i].x){
				cur = (cur + que[i].s) * que[i].t;
			}
		}else{
			if(cur <= que[i].x){
				cur = (cur - que[i].s) / que[i].t;
			}
		}
	}
	return cur < r;
}
bool isOk_min(int mid) {
	int cur = a[mid];
	rep(i,q){
		if(que[i].q == 1){
			if(cur >= que[i].x){
				cur = (cur + que[i].s) * que[i].t;
			}
		}else{
			if(cur <= que[i].x){
				cur = (cur - que[i].s) / que[i].t;
			}
		}
	}
	return cur > l;
}

signed main() {
	int n;
	cin >> n >> q >> l >> r;
	r++;
	l--;

	a = vector<int>(n);
	rep(i, n) cin >> a[i];
	sort(a.begin(), a.end());

	que = vector<Q>(q);
	rep(i, q) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		que[i] = {a, b, c, d};
	}

	// 上限を探す
	int ok = -1, ng = n;
	rep(i, 100) {
		int mid = (ok + ng) / 2;
		if (isOk_max(mid))
			ok = mid;
		else
			ng = mid;
	}

	int maxi = ok;

	ok = n, ng = -1;
	rep(i,100){
		int mid = (ok + ng) / 2;
		if (isOk_min(mid))
			ok = mid;
		else
			ng = mid;
	}

	//rep(i,n){ cout << cal(i) << ' '; } cout << endl;

	cout << maxi - ok + 1 << endl;
}



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

#define rep(i,a,n) for (int i = a;i < n;i++)
#define per(i,n,a) for (int i = n-1;i >= a;i--)
 
typedef long long ll;
using namespace std;
 
int main(){
  int x,y,z;

  cin >> x >> y >> z;

  for(int i = 1; ; i++){
    int a = y*i + z*(i+1);

    if(a > x){
      printf("%d\n", i-1);
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include "stdio.h"
#include "stdlib.h"
 
int main(void) {
  int N;
  int A;
  int tmp;
  int num;
  div_t d;
  
  scanf("%d", &N);
  scanf("%d", &A);
  
  d = div( N, 500 );
  
  tmp = 500 * d.quot;
  
  num = N - tmp;
  
  if (num <= A)
  {
    printf("Yes\n");
  }
  else
  {
    printf("No\n");
  }
  
  return 0;
}

Measured memory_bytes: 128