akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
static ArrayList<edge> []adj;
public static int dijkstra(int s)
{
	int inf=100000000;
	int []dist=new int[10];
	Arrays.fill(dist, inf);
	dist[s]=0;
	PriorityQueue<edge> pq=new PriorityQueue();
	pq.add(new edge(s,0));
	while(!pq.isEmpty())
	{
		edge e=pq.poll();
		int from=e.to;
		int w=e.weight;
		if(from==1)
			return w;
		if(dist[from]<w)
			continue;
		for(edge curr:adj[from])
		{
			int total=w+curr.weight;
			if(total<dist[curr.to])
			{
				dist[curr.to]=total;
				pq.add(new edge(curr.to,total));
			}
		}
	}
	return -1;
	
}
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner(System.in);
		int r=sc.nextInt();
		int c=sc.nextInt();
		adj=new ArrayList[10];
		int [][]mp=new int [10][10];
		for(int i=0;i<10;i++)
		{	
			adj[i]=new ArrayList();
			for(int j=0;j<10;j++)
			{	
				mp[i][j]=sc.nextInt();
				adj[i].add(new edge(j,mp[i][j]));
			}	
			
		}
		int []sp=new int [10];
		for(int i=0;i<10;i++)
			if(i!=1)
				sp[i]=dijkstra(i);
		
		long ans=0;
		for(int i=1;i<=r;i++)
			for(int j=1;j<=c;j++)
			{
				int x=sc.nextInt();
				if(x==-1)
					continue;
				ans+=sp[x];
			}
		
		System.out.println(ans);
		
	}
	
	
	
	
	
	
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
		
		public double nextDouble() throws IOException
		{
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if(x.charAt(0) == '-')
			{
				neg = true;
				start++;
			}
			for(int i = start; i < x.length(); i++)
				if(x.charAt(i) == '.')
				{
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				}
				else
				{
					sb.append(x.charAt(i));
					if(dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg?-1:1);
		}
		
		public boolean ready() throws IOException {return br.ready();}


	}

}
class edge implements Comparable<edge>
{
	int weight;int to;
	public edge(int x,int y)
	{
		to=x;weight=y;
	}
	public int compareTo(edge p)
	{
		return weight-p.weight;
	}
}

Measured memory_bytes: 25684
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define MOD 1000000007
#define INF 1000000000000000007LL

const int N = 200005;
 
// it's swapnil07 ;)
 
#ifdef SWAPNIL07
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif


bool vis[N];

void solve(){
    int n, m; cin>>n>>m;
    assert(n<=200002);
    int si = 1;
    int ei = n;
    int i = 0;
    vector<pii> vect;
    while(i<m){
        int v1 = ei-si;
        int v2 = n-v1;
        if(!vis[v1] && !vis[v2] && v1!=v2){
            vect.pb({si, ei});
            vis[v1] = true;
            vis[v2] = true;
            si++;
            ei--;
            i++;
        }
        else{
            si++;
        }
    }
    for(pii p: vect){
        cout<<p.F<<" "<<p.S<<"\n";
    }
}


signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}





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

#define int long long



#define x first.first
#define y first.second
#define z second.first
#define r second.second

#define dis first
#define a second.first
#define b second.second

vector<int> par, siz;

void init(int X){
  par.resize(X);
  siz.resize(X);
  
  for(int i = 0; i < X; i++){
    par[i] = i;
    siz[i] = 1;
  }
}

int find(int X){
  return X==par[X]?X:X = find(par[X]);
}

void unite(int X, int Y){
  X = find(X);
  Y = find(Y);

  if(X == Y) return ;

  if(siz[X] > siz[Y]){
    par[Y] = X;
    siz[X] += siz[Y];
  } else {
    par[X] = Y;
    siz[Y] += siz[X];
  }
}

bool same(int X, int Y){
  return find(X) == find(Y);
}

long double dist(long double c, long double d, long double e, long double f, long double g, long double h){
  long double i = (c - f), j = (d - g), k = (e - h);
  long double res;

  res = sqrt(i*i + j*j + k*k);

  return res;
}

signed main(){
  cout<<fixed<<setprecision(3);

  while(true){
    vector<pair<pair<long double, long double>, pair<long double, long double>>> in;
    vector<pair<long double,pair<int,int>>> edge;
    long double ans = 0;
    int n;

    cin>>n;

    if(!n) break;

    in.resize(n);

    for(int i = 0; i < n; i++){
      //long double x, y, z, r;

      cin>>in[i].x>>in[i].y>>in[i].z>>in[i].r;
      
    }
    init(n);
  
    for(int i = 0; i < n; i++){
      for(int j = i+1; j < n; j++){
        long double d = dist(in[i].x,in[i].y,in[i].z,in[j].x,in[j].y,in[j].z);
        long double o = d - in[i].r - in[j].r;

        if(o < 0.0) {
          o = 0;
          unite(i, j);
        }
        //edge.push_back({max(0.0, d - in[i].r - in[j].r),{i,j}});
        //edge.push_back(make_pair(max(0.0, d - in[i].r - in[j].r), make_pair(i, j)));
        edge.push_back(make_pair(o, make_pair(i, j)));
      }
    }

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

  
    for(int i = 0; i < edge.size(); i++){
      if(!same(edge[i].a, edge[i].b)){
        unite(edge[i].a, edge[i].b);
        ans += edge[i].dis;
      }
    }


    cout<<ans<<endl;
  }
  return 0;
}



Measured memory_bytes: 3488
import java.util.Scanner;
import java.util.ArrayList;

public class Main{
    public static void main(String[] args) {
        int five = 0;
        int seven = 0;

        String[] numbers = new Scanner(System.in).nextLine().split(" ");
        for(String num: numbers){
            if(num.equals("5")){
                five++;
            }else if(num.equals("7")){
                seven++;
            }
        }

        if(five == 2 && seven == 1){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
}

Measured memory_bytes: 9428
package main

import "fmt"

func main() {
	var x, y int
	g1 := []int{1, 3, 5, 7, 8, 10, 12}
	g2 := []int{4, 6, 9, 11}
	fmt.Scan(&x, &y)
	if x == 2 || y == 2 {
		fmt.Println("No")
		return
	}
	var xg1, yg1 bool
	for _, v := range g1 {
		if x == v {
			xg1 = true
		}
		if y == v {
			yg1 = true
		}
	}
	if xg1 && yg1 {
		fmt.Println("Yes")
		return
	}
	var xg2, yg2 bool
	for _, v := range g2 {
		if x == v {
			xg2 = true
		}
		if y == v {
			yg2 = true
		}
	}
	if xg2 && yg2 {
		fmt.Println("Yes")
		return
	}
	fmt.Println("No")
}


Measured memory_bytes: 512
n = int(input())

A = list(map(int, input().split()))

sum_A = sum(A)

total = 0

for i in range(n):
    sum_A = sum_A - A[i]
    total += (sum_A * A[i]) % (10**9 + 7)
    total %= (10**9 + 7)
print(total)

Measured memory_bytes: 94104
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  ll N, K;
  cin>>N>>K;
  ll A[N+1];
  A[0] = 0;
  for(ll i=1;i<=N;++i) cin>>A[i];
  for(ll i=1;i<=N;++i) {
    A[i] += A[i-1];
    A[i] %= K;
  }
  for(ll i=0;i<=N;++i) {
    A[i] = (A[i] - i%K + K)%K;
  }
  map<ll, ll> amap;
  for(ll i=0;i<min(K, N+1);++i) amap[A[i]]++;
  ll ans = 0;
  for(ll i=0;i<N;++i) {
    amap[A[i]]--;
    ans += amap[A[i]];
    if(i+K<=N) amap[A[i+K]]++;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 17652
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>

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

using namespace std;
typedef long long int ll;
const int INF = 100000000;

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

    bool ans = true;
    rep(i, s.size()) {
        // 奇数文字目
        if (i % 2 == 0 &&
            s[i] != 'R' && s[i] != 'U' && s[i] != 'D') {
            ans = false;
            break;
        }
        // 偶数文字目
        if (i % 2 != 0 &&
            s[i] != 'L' && s[i] != 'U' && s[i] != 'D') {
            ans = false;
            break;
        }
    }
    if (ans == true) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (a, b, x) = readIntList()
    printYesOrNo(
            x >= a && x <= a + b
    )
}

fun printYesOrNo(flag: Boolean) {
    println(if (flag) "YES" else "NO")
}

fun readIntList(): List<Int> = readLine()!!.split(' ').map { it.toInt() }

fun readInt(): Int = readLine()!!.toInt()

fun err(print: Any) {
    System.err.println(print)
}

Measured memory_bytes: 36384
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<stdio.h>
#include<cstdio>

int v[1500001];
char s[1500001],t[500002];
void Zalgorithm(int N){
  int i=1,j=0,k=0;
  while(i<N){
    while(i+j<N&&s[i+j]==s[j])++j;
    if(!(v[i]=j)){
      ++i;
      continue;
    }
    k=1;
    while(v[k]+k<j){
      v[i+k]=v[k];
      ++k;
    }
    i+=k;
    j-=k;
  }
}
int i,j,K,que[500001],bf,ans,size;
int main(){
  int N,ng=500001,mid;
  std::fgets(t,1000000,stdin);
  std::fgets(s,1000000,stdin);
  while(ng-K>1){
    mid=(ng+K)>>1;
    (s[mid]?K:ng)=mid;
  }
  while(t[i]!='\n'){
    s[K+i]=t[i];++i;
  }
  N=i;
  i+=K;
  int M=N+(K<<1);
  while(i<M){
    s[i++]=t[j++];
    j*=j<N;
  }
  Zalgorithm(M);
  M=K%N;
  for(i=0;i<N;++i){
    if(v[i+K]<K)que[size++]=(i+M)-(i+M>=N)*N;
  }
  for(i=0;i<N;++i){
    if(i==size){
      puts("-1");
      return 0;
    }
    if(v[que[i]+K]>=K){
      que[size++]=que[i]+M-(que[i]+M>=N)*N;
      if(bf<=i){
        bf=size-1;
        ++ans;
      }
    }
  }
  printf("%d\n",ans);
}

Measured memory_bytes: 9984
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

/*
*/

template<int MOD>
struct ModInt {
	static const int Mod = MOD;
	unsigned x;
	ModInt() : x(0) { }
	ModInt(signed sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }

	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
	ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }

	ModInt inverse() const {
		signed a = x, b = MOD, u = 1, v = 0;
		while (b) {
			signed t = a / b;
			a -= t * b; std::swap(a, b);
			u -= t * v; std::swap(u, v);
		}
		if (u < 0) u += Mod;
		ModInt res; res.x = (unsigned)u;
		return res;
	}
};
typedef ModInt<1000000007> mint;

ll n,a[100010];
ll b[3]={};
mint ans=1;

int main(void){
	cin>>n;
	rep(i,n)cin>>a[i];
	rep(i,n){
		ll t=0;
		rep(j,3){
			if(b[j]==a[i]){
				if(t==0)b[j]++;
				t++;
			}
		}
		ans*=t;
	}
	cout<<ans.get()<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(void){
	int n;
	char word[100][15];
	char last = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%s", word[i]);
	for(int i = 0; i < n - 1; i++){
		if(word[i][strlen(word[i]) - 1] != word[i + 1][0]){
			printf("No\n");
			return 0;
		}
		for(int j = 0; j < i; j++){
			if(strcmp(word[i], word[j]) == 0){
				printf("No\n");
				return 0;
			}
		}
	}
	for(int i = 0; i < n - 1; i++){
		if(strcmp(word[i], word[n - 1]) == 0){
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}


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

using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,n,m) for(ll i=n; i>(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define cinv(v,n,m) FOR(i,n,m) cin>>v.at(i)
#define coutv(v,n,m) FOR(i,n,m) cout<<v.at(i) <<" "
#define cout(n) cout<<fixed<<setprecision(n)
int main(){
  ll a,b;
  cin>>a>>b;
  string res = "Odd";
  if(a*b%2==0) res="Even";
  cout<<res<<endl;
}


Measured memory_bytes: 256
/*
  Author: @yash_31
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
#define ll long long int
#define eb emplace_back
#define fatafat ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
#define ft first
#define sd second
#define mkpr make_pair
#define deb(x) std::cout<<#x<<":"<<x<<endl;
#define whole(x) (x).begin(),(x).end()
#define revwhole(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define fbo find_by_order
#define ook order_of_key
#define init0(x) memset(x,0,sizeof(x));

using namespace std; 
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> gharKaSet;
 
const int maxlimit=2e5+2;
const ll inf=1e18;
//TTBDC

int main()
{
  fatafat
  string s,t;
  cin>>s>>t;
  int ns=s.length(),nt=t.length();
  int lcs[ns+1][nt+1];
  memset(lcs,0,sizeof(lcs));
  for(int i=0;i<=ns;i++){
    for(int j=0;j<=nt;j++){
      if(i==0 || j==0){lcs[i][j]=0;continue;}
      else if(s[i-1]==t[j-1])lcs[i][j]=lcs[i-1][j-1]+1;
      else lcs[i][j] = max(lcs[i][j-1],lcs[i-1][j]);
    }
  }
  string res="";
  int x=ns,y=nt;
  while(x!=0 && y!=0){
    if(s[x-1]==t[y-1]){res+=s[x-1];x--;y--;}
    else {
      if(lcs[x-1][y]>lcs[x][y-1]){x--;}
      else y--;
    }
  }
  reverse(whole(res));
  cout<<res;
  return 0;
}

Measured memory_bytes: 38820
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<set>
#include<cstring>
#include<iomanip> //cout << fixed << setprecision(15) << x << endl;

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define P pair<int, int>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
/* -- template -- */

P dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int main() {
    int H, W; cin >> H >> W;
    string S[H]; rep(i, H) cin >> S[i];
    ll ans = 0;
    vector<vector<int>> dist(H, vector<int>(W, INF));
    for(int i = 0; i < H; ++i) {
        for(int j = 0; j < W; ++j) {
            if(S[i][j] == '.') continue;
            if(dist[i][j] != INF) continue;
            dist[i][j] = 0;
            ll cnt = 0, tmpans = 0;
            queue<P> Q;
            Q.push(mp(i, j));
            while(!Q.empty()) {
                P q = Q.front(); Q.pop();
                if(S[q.first][q.second] == '#')++cnt;
                for(int k = 0; k < 4; ++k) {
                    int h = q.first + dir[k].first, w = q.second + dir[k].second;
                    if(h < 0 || h >= H || w < 0 || w >= W) continue;
                    if(dist[h][w] != INF) continue;
                    if(S[h][w] == ((dist[q.first][q.second] % 2 == 0) ? '#' : '.')) continue;
                    Q.push(mp(h, w));
                    dist[h][w] = dist[q.first][q.second] + 1;
                    if(dist[q.first][q.second] % 2 == 0) ++tmpans;
                }
            }
            ans += cnt * tmpans;
        }
    }
    cout << ans << endl;
}


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

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define IMOD 1000000007 
#define irep(i,n) for(int i = 0; i < (int)(n); i++)
#define irep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define lrep(i,n) for(long long  i = 0; i < (long long)(n); i++)
#define lrep2(i,a,n) for(long long i = (long long)(a); i <= (long long)(n); i++)

#define irrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define irrep2(i,a,n) for(int i = (int)(n); i >= (int)(a); i--)

typedef long long ll;
typedef std::vector<char> v_char;
typedef std::vector<v_char > v2_char;
typedef std::vector<double> v_double;
typedef std::vector<v_double > v2_double;
typedef std::vector<int> v_int;
typedef std::vector<v_int > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<v_ll > v2_ll;
typedef std::vector<std::string> v_string;
typedef std::vector<v_string > v2_string;
typedef std::vector<bool> v_bool;
typedef std::vector<v_bool > v2_bool;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, int> pii;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

using namespace std; 

int main(void)
{
    ll n;
    cin >> n;
    
    int even = 0, odd = 0;

    irep(i, n) {
        int tmp;
        cin >> tmp;
        if(tmp%2) { 
            if(odd) {
                odd--;
                even++;
            } else {
                odd++;
            }
        } else {
            if(even) {
                even++;
            }
        }
    }
    if(odd) { 
        cout << "NO";
    } else {
        cout << "YES";
    }
    return 0;
}   
/** atcoder **/



Measured memory_bytes: 256
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
s=I()
sl=[s]
i=1
while True:
    t=s
    if s%2==0:
        s=t//2
    else:
        s=3*t+1
    
    if s in sl:
        print(len(sl)+1)
        break
    else:
        sl.append(s)

Measured memory_bytes: 3060
#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
#define fst first
#define snd second
using ll = long long;
using I = pair<int, int>;
const int D = 16;

int S(ll n) {
  int s = 0;
  while (n > 0) {
    s += n % 10;
    n /= 10;
  }
  return s;
}

ll f(ll n) {
  vector<ll> cand = {n};
  for (ll p = 1; p <= n; p *= 10) {
    int d = (n / p) % 10;
    for (int i = d + 1; i <= 9; i++) {
      ll x = (n / p) - d + i;
      x = x * p + p - 1;
      cand.push_back(x);
    }
  }
  ll p = 1, q = 0;
  for (ll x : cand) {
    ll s = S(x);
    if (p * s > x * q || (p * s == x * q && p > x)) {
      p = x;
      q = s;
    }
  }
  return p;
}

int main() {
  int K;
  while (cin >> K) {
    vector<ll> res;
    res.push_back(1);
    while (res.size() < K) {
      ll n = res.back();
      res.push_back(f(n + 1));
    }
    for (ll x : res) cout << x << endl;
  }
  return 0;
}


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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define log_2(a) (log((a)) / log(2))
#define ln '\n'

using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1e9 + 7;
static const int SIZE = 200005;

const int dx[] = {0, -1, 1, 0};
const int dy[] = {-1, 0, 0, 1};

vector<LL> Div(LL n) {
    vector<LL> ret;
    for(LL i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);
            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    int N;
    cin >> N;
    int X;
    cin >> X;
    int a;
    cin >> a;
    if(N == 1) {
        cout << abs(X - a) << endl;
        return 0;
    }

    vector<int> v(N);
    v[0] = a;
    int t1 = abs(a - X), t2 = INF;
    for(int i = 1; i < N; ++i) {
        cin >> v[i];
        if(t1 > abs(v[i] - X)) {
            t2 = t1;
            t1 = abs(v[i] - X);
        } else if(t2 > abs(v[i] - X)) {
            t2 = abs(v[i] - X);
        }
    }
    sort(all(v));

    for(int i = 0; i < N - 1; ++i) {
        t1 = __gcd(t1, abs(v[i + 1] - v[i]));
    }

    if(t2 != INF) {
        for(int i = 0; i < N - 1; ++i) {
            t2 = __gcd(t2, abs(v[i + 1] - v[i]));
        }
    } else {
        t2 = 0;
    }
    cout << max(t1, t2) << endl;
    return 0;
}


Measured memory_bytes: 3696
#include <iostream>

using namespace std;
typedef long long LL;
const int mod=1000000007;

int main(){
  int N, K;
  cin >> N >> K;
  int a[110];
  for(int i=0; i<N; i++) cin >> a[i];
  LL dp[110][100010];
  LL sum[110][100010];
  dp[0][0]=1;
  for(int i=0; i<=N; i++){
    dp[i][0]=1;
    sum[i][0]=1;
  }
  for(int i=0; i<=K; i++) sum[0][i]=1;
  for(int i=1; i<=N; i++){
    for(int j=1; j<=K; j++){
      if(j<=a[i-1]) dp[i][j]=sum[i-1][j];
      else dp[i][j]=sum[i-1][j]-sum[i-1][j-a[i-1]-1];
      if(dp[i][j]>mod) dp[i][j]%=mod;
      sum[i][j]=sum[i][j-1]+dp[i][j];
    }
  }
  cout << dp[N][K] << endl;
  
  return 0;
}

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

using namespace std;

/* g++ -g -fsanitize=address -lasan -std=c++11 -Dfoo_ */

/* freopen("input.txt", "rt", stdin); */
/* freopen("output.txt", "wt", stdout); */

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

string s;

void jump(const int i, const int j, VI& A)
{
    A[i] = 1;
    FOR(x,i,j) if (A[x]) {
        FOR(d,1,3) if (x+d <= j && s[x+d] != '#') {
            A[x+d] = 1;
        }
    }
}

int main()
{
#ifdef foo_
    freopen("foo", "rt", stdin);
#endif
    ios::sync_with_stdio(false);
    int n,a,b,c,d; 
    while (cin >> n >> a >> b >> c >> d >> s) {
        s = ' ' + s;
        VI A(n+1), B(n+1);
        jump(a,c,A);
        jump(b,d,B);
        bool ans = A[c] && B[d];
        if (ans && c > d) {
            ans = false;
            FOR(i,1,n+1)
                ans |= A[i-1] && B[i] && A[i+1];
        }
        cout << (ans ? "Yes" : "No") << endl;
    }
    return 0;
}


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

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a,s,d,f;
    cin >> a >> s >> d >> f;
    
    int z, x;
    z = max(a, d);
    x = min(s, f);
    auto ans = max(0, x - z);
    
    cout << ans << endl;
}


Measured memory_bytes: 256
A,B,C,D,E,F=map(int,input().split())
wDP=[False]*(F+1)
wDP[0]=True
water=[]
for i in range(1,(F//100)+1):
    if(i>=B and wDP[i-B]):
        wDP[i]=True
    elif(i>=A and wDP[i-A]):
        wDP[i]=True
for i in range(F+1):
    if(wDP[i] and i!=0):
        water.append(i*100)
A,B=A*100,B*100
water=list(set(water))
ans=[water[0],0]
mconc=0
for x in water:
    up=min(x*E//100,F-x)
    sDP=[0]*(up+1)
    for i in range(1,up+1):
        if(i>=D):
            sDP[i]=max(sDP[i-1],sDP[i-C]+C,sDP[i-D]+D)
        elif(i>=C):
            sDP[i]=max(sDP[i-1],sDP[i-C]+C)
        else:
            sDP[i]=sDP[i-1]
    conc=100*sDP[-1]/(x+sDP[-1])
    if(conc>=mconc):
        mconc=conc;ans[0]=x+sDP[-1];ans[1]=sDP[-1]
print(*ans)


Measured memory_bytes: 3188
n,q = input().split()
n = int(n)
q = int(q)

queue = []

class process:
    def __init__(self,a,b):
        self.name = a
        self.time = b


for i in range(n):
    a,b = input().split()
    b = int(b)
    queue.append(process(a,b))

def enqueue(proc):
    global queue
    queue.append(proc)

def dequeue():
    global queue
    return queue.pop(0)

def isEnpty():
    global queue
    return len(queue) != 0


def RoundRobinScheduling():
    now_time = 0
    while  isEnpty(): 
        now_process = dequeue()
        if now_process.time - q > 0:
            now_process.time = now_process.time - q
            enqueue(now_process)
            now_time = now_time + q
        else:
            now_time = now_time + now_process.time
            print(now_process.name,end=" ")
            print(now_time)


RoundRobinScheduling()



Measured memory_bytes: 17400
#include <stdio.h>
int main(void){
    int n;
    scanf("%d",&n);
    
    int ab[n];
    int i,j;
    for(i=0;i<n;i++){
        scanf("%d",&ab[i]);
    }
    
    int tmp,max;
    int pa=0;
    int pb=0;
    
    for(j=0;j<n;j++){
        max=0;
        for(i=0;i<n;i++){
            if(ab[i]>max){
                max=ab[i];
                tmp=i;
            }
        }
        ab[tmp]=0;
        if(j%2==0){
            pa+=max;
        }else{
            pb+=max;
        }
    }
    
    printf("%d\n",pa-pb);
    return 0;
}


Measured memory_bytes: 128
def is_palindrome(text):
  mid = len(text) // 2
  # 奇数の場合
  if len(text) % 2 == 1:
    if text[:mid] == text[mid+1:][-1::-1]:
      return True
    else:
      return False
  # 奇数の場合
  else:
    if text[:mid] == text[mid:][-1::-1]:
      return True
    else:
      return False

s = input()

mid = len(s) // 2

front = s[:mid]       # 前半
back  = s[mid+1:]     # 後半
if is_palindrome(s) and is_palindrome(front) and is_palindrome(back):
  print("Yes")
else:
  print("No")


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

int main(){
  int r,g,b;
  cin >> r >> g >> b;
  if((r * 100 + g * 10 + b) % 4  == 0) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


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

struct team {
  char name;
  int win, lose;
};

bool cmp(const team& a, const team& b) {
  if (a.win != b.win) return a.win > b.win;
  return a.lose < b.lose;
}

int main() {
  int n;
  while (cin >> n, n) {
    char t;
    int r;
    vector<team> v(n);
    for (int i = 0; i < n; i++) {
      cin >> t;
      v[i].name = t;
      for (int j = 0; j < n - 1; j++) {
        cin >> r;
        if (r == 0) v[i].win++;
        else if (r == 1) v[i].lose++;
      }
    }
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < n; i++) {
      cout << v[i].name << "\n";
    }
  }
}



Measured memory_bytes: 3120
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
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; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

ll n, p;
string s;

ll modpow(ll m, ll p, ll mod) {
    if (p == 0) return 1;
    ll tmp = modpow(m, p / 2, mod);
    if (p & 1) return (tmp * tmp % mod) * m % mod;
    else return tmp * tmp % mod;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> p >> s;
    if (p == 2) {
        ll ans = 0;
        for (int i = 0; i < n; i++) {
            if (!((s[i] - '0') & 1)) {
                ans += i + 1;
            }
        }
        cout << ans << '\n';
    } else if (p == 5) {
        ll ans = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0' || s[i] == '5') {
                ans += i + 1;
            }
        }
        cout << ans << '\n';
    } else {
        reverse(ALL(s));
        vll accs(s.size() + 1, 0);
        for (ll i = 0; i < s.size(); i++) {
            ll p10 = modpow(10, i, p);
            accs[i + 1] = (accs[i] + (s[i] - '0') * p10 % p) % p;
        }

        vll cnp(p, 0);
        ll ans = 0;
        for (ll i = 0; i < s.size() + 1; i++) {
            ans += cnp[accs[i]];
            cnp[accs[i]]++;
        }
        cout << ans << '\n';
    }
    return 0;
}


Measured memory_bytes: 2196
import sys
import itertools

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *H = map(int, read().split())
H.sort(reverse=True)
while len(H) > 1:
    x = H.pop()
    y = H.pop()
    H.append((x+y)/2)
print(H[0])


Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#define INF 1000000000
#define nmax 500005
using namespace std;

int n;
int cnt = 0;
int a[nmax];

void merge(int left, int mid, int right){
  int n1 = mid -left;
  int n2 = right - mid;
  int l[nmax];
  int r[nmax];

  int i, j;
  
  for(i = 0; i < n1; i++) l[i] = a[left + i];
  for(i = 0; i < n2; i++) r[i] = a[mid + i];

  l[n1] = INF;
  r[n2] = INF;

  i = 0;
  j = 0;

  for(int k = left; k < right; k++){
    if(l[i] <= r[j]) a[k] = l[i++];

    else a[k] = r[j++];

    cnt++;
    
  }
}

void mergeSort(int left, int right){
  if(left+1 < right){
    int mid = (left + right) / 2;

    mergeSort(left, mid);
    mergeSort(mid, right);
    merge(left, mid, right);
  }
}

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

  mergeSort(0, n);

  for(int i = 0; i < n; i++){
    if(i) cout << " ";

    cout << a[i];
  }

  cout << endl;
  cout << cnt << endl;
  

  return 0;

}



Measured memory_bytes: 6904
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ww = sc.nextInt();
        // 0は使わない
        int[] w = new int[n + 1];
        int[] v = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        long dp[][] = new long[n + 1][100001];

        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < 100001; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        dp[0][0] = 0;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < 100001; j++) {
                if (j - v[i] >= 0) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        for (int i = 100000; i >= 0; i--) {
            if (dp[n][i] <= ww) {
                System.out.println(i);
                return;
            }
        }

        sc.close();
    }
}

Measured memory_bytes: 129436
#include <bits/stdc++.h>
using namespace std;
int main(){
    int K,S,ans=0;
    cin>>K>>S;
    for(int x=0;x<=K;x++){
        for(int y=0;y<=K;y++){
            if(S-x-y>=0&&S-x-y<=K) ans++;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
        using namespace std;
        #define tani_nachi_ke  ios_base::sync_with_stdio(false); cin.tie(NULL);
        #define M_PI 3.14159265358979323846
        #define data data_
        #define ff first
        #define ss second
        #define pb push_back
        #define ld long double
        #define int long long
        #define print(t) cout << "Case #" << t << ": ";
        int32_t main()
        {
            tani_nachi_ke  
            
            int const mod = 1e9 + 7;
            int n,k;
            cin >> n >> k;
            int ans = 0;
            for(int i = k; i <= n+1; i++)
            {
                ans += ((i*(2*n-i+1))/2 - (i*(i-1))/2 + 1);
                // cout << ans << endl;
                ans %= mod;
            }
            cout << ans << '\n';






           return 0;
        }
          

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define PIL pair<int,LL>
#define PLI pair<LL,int>
#define PIII pair<int,PII>
#define PLL pair<LL,LL>
#define PLII pair<LL,PII>
#define VI vector<int>
#define VL vector<LL>
#define VPII vector<PII>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
#define EPS 0.00000000001
#define PI acos(-1)
#define loop(i,b,n) for(int i=b;i<n;++i)
#define rev_loop(i,b,n) for(int i=b;i>=n;--i)
using namespace std;

const int MOD = 1e9 + 7;
const LL MX = 1e9;
const LL INF = 1e9;

int main()
{
    //ofstream out("output.txt");
    //ifstream in("input.txt");
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

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

    return 0;
}


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

#define endl "\n"
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define f first
#define se second
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define PI 3.14159265358979323846264338327950L


typedef long long ll;

const ll MOD =1e9+7;


char grid1[51][51];
char grid2[51][51];

void solve(){
    int N,M;
    cin>>N>>M;
    int cnt=0;
    for(int i=0;i<N;++i)cin>>grid1[i];
    for(int i=0;i<M;++i)cin>>grid2[i];
    bool flag=0;
    for(int row1=0;row1<=N-M;++row1){
        for(int col1=0;col1<=N-M;col1++){
            if(row1+M-1>=N||col1+M-1>=N)continue;
            bool ok=1;
            for(int row2=0;row2<M;++row2){
                for(int col2=0;col2<M;col2++){
                    if(grid1[row1+row2][col1+col2]!=grid2[row2][col2])
                        ok=0;
                }
            }
            if(ok){
                cout<<"Yes"<<endl;
                return;
            }
        }
    }
    cout<<"No"<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _172A
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = long.Parse(Console.ReadLine() ?? string.Empty);
            double value = a + Math.Pow(a, 2) + Math.Pow(a, 3);
            Console.WriteLine(Convert.ToUInt64(value));
        }
    }
}


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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

signed main(){

  string o,e;
  cin>>o>>e;

  REP(i,0,o.size()){
    cout<<o[i];
    if(i>=e.size())break;
    cout<<e[i];
  }
  cout<<endl;


  
  return 0;
}

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

using _i64 = int64_t;
using _u64 = uint64_t;
using _f64 = double;

#define endl "\n"

#define _for(i, start, end) for(_i64 i = (_i64)start; i < (_i64)end; ++i)
#define _rep(i, number) _for(i, 0, number)
#define _foreach(e, data) for(auto& e : data)
#define _all(data) data.begin(), data.end()

template<typename type>
_i64 _size(const type& data) { return static_cast<_i64>(data.size()); }
template<typename type, size_t size>
_i64 _size(const type (&)[size]) { return static_cast<_i64>(size); }

enum _flag : bool { able = true, disable = false };

struct _time {
    _time(_flag flag) { check = flag; if(!check) { return; } gettime(start); }
    ~_time() {
        if(!check) { return; }; gettime(end);
        _i64 elapse = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cout << endl << "Time: " << elapse << " ms" << endl;
    }
    private:
    using _timer = chrono::time_point<chrono::system_clock>;
    _timer start, end; bool check;
    void gettime(_timer& time) { time = chrono::system_clock::now(); }
};

struct _ini { _ini() { ios::sync_with_stdio(false); cin.tie(nullptr); } } _ini;

int main() {
    {
        _time time(disable);
        _i64 d, ans;
        while(cin >> d) {
            ans = 0;
            _for(i, 1, 600 / d) { ans += pow(d * i, 2) * d; }
            cout << ans << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3160
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

int main() {
	ll		b,c,h,i,j,k,l,m,n,x,y;
	ll		ans = 0;
	string	s;
	vector<int>	a(5);
	for(i=0;i<5;i++) cin >> a[i];
	cin >> k;
	if (a[4]-a[0] > k) cout << ":(" << endl;
	else cout << "Yay!" << endl;
	return 0;
}


Measured memory_bytes: 3580
#include <cstdio>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	if(a==b&&a!=c)
		cout << "Yes";
	else if(a==c&&a!=b)
		cout << "Yes";
	else if(b==c&&a!=b)
		cout << "Yes";
	else
		cout << "No";

	return 0;
}


Measured memory_bytes: 256
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]

point = [K] * N
point = [j - Q for j in point]

for i in range(Q):
    point[A[i] - 1] += 1

for i in range(N):
    print("Yes") if point[i] > 0 else print("No")

Measured memory_bytes: 11820
i = input().split(" ")
a, b, k = int(i[0]), int(i[1]), int(i[2])

list = []
n = -1
for x in range(1, 101):
    if a%x == 0 and b%x == 0:
        list.append(x)
        n += 1

print(list[n-k+1])

Measured memory_bytes: 3060
//Author:  Pranta
//Date:    2020-Aug-15
//Problem: C_Walking_Takahashi
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
using namespace std;
void solve()
{
   ll x,k,d,ans=0;
   cin>>x>>k>>d;
   x=abs(x);
   ll div=x/d;
   if(k<=div){
       x-=(d*k);
   }
   else
   {
       ll extra =k-div;
       if(extra%2){
          x-=d*(div+1);
       }
       else {
           x-=d*div;
       }
   }
    cout<<abs(x);
}
int main()
{
    fast;
    int t;
    solve();
}

Measured memory_bytes: 3656
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int main(void)
{
	int n;

	cin >> n;
	while (n-- != 0)
	{
		int A[10] = {}, B[10] = {}, C[10] = {}, countb = 0, countc = 0;
		bool f = true;
		for (int i = 0; i < 10; i++)
		{
			cin >> A[i];
		}
		B[countb++] = A[0];
		for (int i = 1; i < 10; i++)
		{
			if (B[countb - 1] < A[i]) B[countb++] = A[i];
			else if (countc == 0) C[countc++] = A[i];
			else if (B[countb - 1] > A[i] && C[countc - 1] < A[i]) C[countc++] = A[i];
			else f = false;
		}
		//for (int i = 0; i < sizeof(B) / sizeof(*B); i++) cout << "B" << i << " =" <<B[i] << endl;
		//for (int i = 0; i < sizeof(C) / sizeof(*C); i++) cout << "C" << i << "=" << C[i] << endl;
		if (f == true) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* clang-format off */
#define MOD 1000000007
#define INF 1000000000
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
#define __DEBUG__
#ifdef __DEBUG__
#define CH_P(a) cout <<"check_point("<<#a<<")" << "\n";
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#endif
#ifndef __DEBUG__
#define CH_P(a) 
#define DEBUG(x) 
#define DEBUGS(v) 
#endif
#define TIMER_S(start) chrono::system_clock::time_point start = chrono::system_clock::now();
#define TIMER_E(end) chrono::system_clock::time_point end = chrono::system_clock::now();
#define TIME(start, end) cout << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count()) << "ms" << "\n";
/* clang-format on */

int main() {
  double a,v,b,w,t;
  cin >> a >> v >> b >> w>>t;
  if(w>=v)cout << "NO" << "\n";
  else if(t>=abs(a-b)/(v-w))cout << "YES" << "\n";
  else cout << "NO" << "\n";
  return 0;
}


Measured memory_bytes: 3720
#include<cstdio>
#include<algorithm>
using namespace std;

int a[5000],dp[5011][5011];

int main(){
  int n,k,l,r,mid,flag;
  scanf("%d %d",&n,&k);
  for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
  sort(a,a+n);
  l=0;
  r=n-1;
  while(l<=r){
    for(int i=0;i<=n;i++)
      for(int j=0;j<=k;j++){
        if(j==0)
          dp[i][j]=1;
        else
          dp[i][j]=0;
      }
    mid=(r+l)/2;
    for(int i=0;i<n;i++){
      for(int j=0;j<=k;j++){
        if(dp[i][j]){
          dp[i+1][j]=1;
          if(i!=mid&&j+a[i]<=k)
            dp[i+1][j+a[i]]=1;
        }
      }
    }
    flag=0;
    for(int i=max(k-a[mid],0);i<k;i++)
      if(dp[n][i])
        flag=1;
    if(flag)
      r=mid-1;
    else
      l=mid+1;
  }
  printf("%d\n",r+1);
}

Measured memory_bytes: 98176
import Control.Applicative
import Control.Monad
main = solve

solve = do
    ns <- fmap (read :: String -> Int) . words <$> getLine
    let h = ns !! 0
        w = ns !! 1
    drawRectangle h w

drawRectangle :: Int -> Int -> IO ()
drawRectangle h w
    | h == 0 && w == 0 = return ()
    | otherwise = do
        mapM_ (\x -> putStrLn $ createBlock x w h) [1..h]
        putStrLn ""
        solve

createBlock :: Int -> Int -> Int -> String
createBlock x w h
    | x == 1 || x == h || (w - 2) <= 0 = replicate w '#'
    | 0 < (w - 2) = '#' : (replicate (w - 2) '.') ++ "#"

Measured memory_bytes: 4176
#include<bits/stdc++.h>
#define ll long long
#define sort(a) sort(a.begin(), a.end())
#define loop(n) for(ll i = 0; i<n; i++)
using namespace std;

ll zeros(ll n){ 
    ll count = 0; 
    for (ll i = 5; n/i >= 1;i *= 5)count+=n/i; 
    return count; 
} 

int main(){
    ll n; cin>>n; 
    if(n&1){
        cout<<0;
        return 0;
    }
    ll s = n/2;
    ll count = zeros(s);
    cout<<count;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int limN = 105;
typedef pair<int,int> pii;
#define x first
#define y second

int area(pii a, pii b, pii c) {
    return a.x*b.y + b.x*c.y + c.x*a.y -
        (a.y*b.x + b.y*c.x + c.y*a.x);
}

int sgno(int x) {
    if(x==0)
        return x;
    return x<0? -1 : 1;
}

int N ;
pii ptos[limN];

bool funca(int proh) {
    for(int i=0; i<N; i++) {
        if(sgno(area(ptos[(i+N-1)%N], ptos[i], ptos[(i+1)%N])) == proh)
            return false;
    }
    return true;
}

int main() {
    scanf("%d", &N);
    for(int i=0; i<N; i++)
        scanf("%d%d", &ptos[i].x, &ptos[i].y);
    printf("%d\n", (funca(1) || funca(-1))? 1 : 0);
}



Measured memory_bytes: 3224
package main

import (
	"fmt"
)

func main() {
	mod := 1000000007
	var s int
	fmt.Scan(&s)

	dp := make([]int , s+1)
	dp[0] = 1
	for i := 1; i < s+1; i++{
		for j := 0; j < (i-3)+1; j++ {
			dp[i] += dp[j]
			dp[i] = dp[i]%mod
		}
	}
	fmt.Println(dp[s])

}

Measured memory_bytes: 1780
#include <stdio.h>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#define R register
namespace IO{
	char buf[1<<15],*S,*T;
	inline char gc(){
		if (S==T){
			T=(S=buf)+fread(buf,1,1<<15,stdin);
			if (S==T) return EOF;
		}return *S++;
	}
	inline int read(){
		R int x; R bool f; R char c;
		for (f=0; (c=gc())<'0'||c>'9'; f=c=='-');
		for (x=c^'0'; (c=gc())>='0'&&c<='9'; x=(x<<3)+(x<<1)+(c^'0'));
		return f?-x:x;
	}
}
#define MN 200005
std::priority_queue<int,std::vector<int>,std::greater<int> > pq;
struct sth{
	int l,r;
	inline bool operator < (const sth &a)const{
		return l<a.l;
	}
}a[MN];
int n,m,r[MN],lb,ans,cnt;
int main(){
	n=IO::read(),m=IO::read();
	for (R int i=1; i<=n; ++i)
		a[i].l=IO::read(),a[i].r=IO::read(),++r[a[i].r];
	std::sort(a+1,a+n+1);
	for (R int i=1,j=1; i<=m&&j<=n; ++i){
		for (;a[j].l<i&&j<=n;++j)
			if (!pq.empty()&&a[j].r>pq.top()) pq.pop(),pq.push(a[j].r);
		if (j>n) break;pq.push(a[j].r);++j;lb=i;
	}while(!pq.empty()) --r[pq.top()],pq.pop();
	ans=r[m+1];
	for (R int i=m; i>lb; --i){
		++cnt;
		if (cnt<r[i]) ans+=r[i]-cnt,cnt=0;
		else cnt-=r[i];
	}for (R int i=lb; i; --i)
		if (cnt<r[i]) ans+=r[i]-cnt,cnt=0;
		else cnt-=r[i];
	printf("%d\n",ans);return 0;
}

Measured memory_bytes: 3832
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define D(x) cerr << #x << " = " << (x) << '\n'
using ll = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s, t;
	cin >> s >> t;
	int n = sz(s), m = sz(t);
	s = '#' + s;
	t = 't' + t;
	vector<vector<int>> dp(n + 1, vector<int>(m + 1));
	for(int i = 1; i <= n; ++ i) {
		for(int j = 1; j <= m; ++ j) {
			if(s[i] == t[j]) dp[i][j] = 1 + dp[i - 1][j - 1];
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			dp[i][j] = max(dp[i][j], dp[i][j - 1]);
		}
	}
	string ans;
	while(n && m) {
		if(s[n] == t[m]) ans.push_back(s[n]), --n, --m;
		else {
			if(dp[n][m] == dp[n - 1][m]) --n;
			else --m;
		}
	}
	reverse(all(ans));
	cout << ans << '\n';
}


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

int rec(int n, int s, int num)
{
  if (n == 0 && s == 0) return 1;
  if (n == 0 || num == 10) return 0;

  return rec(n, s, num + 1) + rec(n - 1, s - num, num + 1);
}

signed main()
{  
  int n, s;
  
  while (cin >> n >> s, n || s) {
    cout << rec(n, s, 0) << endl;
  }

  return (0);
}

Measured memory_bytes: 3072