akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define NREP() for(ll i = 0; i < n; i++)
#define MREP() for(ll j = 0; j < m; j++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define IPT(t, x) t ipt; cin >> ipt; x.push_back(ipt);
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

const static ll MOD = 1e9 + 7;
ll n, cnt, ans, tmp, sum, a, b, c, d, k, m, h, w, q, x, y;
string s, t;

int main() {
    cin >> x;

    for (ll a = -1e3; a <= 1e3; ++a) {
        for (ll b = -1e3; b <= 1e3; ++b) {
            ll a5 = pow(a, 5);
            ll b5 = pow(b, 5);
            if (a5 - b5 == x) {
                MSG(to_string(a) + " " + to_string(b))
                exit(0);
            }
        }
    }
}


Measured memory_bytes: 4132
#!/usr/bin/env python3
INF = float("inf")
n, *d = map(int, open(0).read().split())
p = sorted(zip(*[iter(d)]*2), key=sum)
M, a = -INF, 0
for X, L in p:
    l, r = X-L, X+L
    if M <= l:
        a += 1
        M = r
print(a)

Measured memory_bytes: 25868
#include "bits/stdc++.h"
using namespace std;

class WeightedUF
{
	public:
	vector<int> data;
	vector<int> diff_weight;

	WeightedUF(int s):data(s,-1),diff_weight(s,0){}

	//y-x=w
	bool unite(int x,int y,int w)
	{
		w+=weight(x);
		w-=weight(y);
		x=find(x);
		y=find(y);
		bool isunion=(x!=y);
		if(isunion)
		{
			if(data[x]>data[y])
			{
				swap(x,y);
				w=-w;
			}
			data[x]+=data[y];
			data[y]=x;
			diff_weight[y]=w;
		}
		return isunion;
	}

	int find(int x)
	{
		if(data[x]<0)
			return x;
		else{
			int par=data[x];
			data[x]=find(data[x]);
			diff_weight[x]+=diff_weight[par];
			return data[x];
		}
	}
	int weight(int x)
	{
		find(x);
		return diff_weight[x];
	}
	bool same(int x,int y)
	{
		return find(x)==find(y);
	}
};

int main()
{
	while(1)
	{
		int n,m;
		cin>>n>>m;
		if(n==0)
			break;
		WeightedUF u=WeightedUF(n);
		for(int i=0;i<m;i++)
		{
			char q;
			cin>>q;
			if(q=='!')
			{
				int a,b,w;
				cin>>a>>b>>w;
				a--;b--;
				u.unite(a,b,w);
			}else{
				int a,b;
				cin>>a>>b;
				a--;b--;
				if(!u.same(a,b))
					cout<<"UNKNOWN"<<endl;
				else
					cout<<u.weight(b)-u.weight(a)<<endl;
			}
		}
	}
	return 0;
}


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

#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define MOD 1000000007

#define trace1(x)                    cout <<#x<<": "<<x<< endl;
#define trace2(x, y)                 cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)              cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)           cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;

typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    ll i,j,n,m,h,w;
    cin>>n>>h>>w;
    cout<<(n-h+1)*(n-w+1);
    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>

int fib(int);

int dp[45]={0};

int main(){
  int n;
  scanf("%d",&n);
  printf("%d\n",fib(n));
  return 0;
}

int fib(int n){
  if(n==0 || n==1){
    return dp[n]=1;
  }
  else{
    if(dp[n]==0) return dp[n]=fib(n-1)+fib(n-2);
    else return dp[n];
  }
}



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

parents = list(range(n + 1))
ranks = [0 for _ in range(n + 1)]


def find(x):
    if parents[x] == x:
        return x
    parents[x] = find(parents[x])
    return parents[x]


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if ranks[x] < ranks[y]:
        parents[x] = y
    else:
        parents[y] = x
        if ranks[x] == ranks[y]:
            ranks[x] += 1


res = [n * (n - 1) // 2]
nums = [1 for _ in range(n + 1)]
for a, b in reversed(ls):
    aa = find(a)
    bb = find(b)
    if aa == bb:
        res.append(res[-1])
    else:
        res.append(res[-1] - nums[aa] * nums[bb])
        nums[aa] = nums[bb] = nums[aa] + nums[bb]
        unite(aa, bb)
print(*reversed(res[:-1]), sep='\n')

Measured memory_bytes: 39716
program example    
	implicit none

	integer :: N,K,i,j
    integer(8) kari
    integer(8),allocatable :: H(:)
    
    read(*,*) N,K
    
    allocate(H(N))
    
    read(*,*) H(:)
    
    call heapsort(N,H)
   
   	write(*,*) sum(H(:N-K))
    
end program example

subroutine heapsort(n,array)
  implicit none
  integer,intent(in) :: n
  double precision,intent(inout) :: array(1:n)
  
  integer ::i,k,j,l
  double precision :: t
  
  if(n.le.0)then
     write(6,*)"Error, at heapsort"; stop
  endif
  if(n.eq.1)return

  l=n/2+1
  k=n
  do while(k.ne.1)
     if(l.gt.1)then
        l=l-1
        t=array(L)
     else
        t=array(k)
        array(k)=array(1)
        k=k-1
        if(k.eq.1) then
           array(1)=t
           exit
        endif
     endif
     i=l
     j=l+l
     do while(j.le.k)
        if(j.lt.k)then
           if(array(j).lt.array(j+1))j=j+1
        endif
        if (t.lt.array(j))then
           array(i)=array(j)
           i=j
           j=j+j
        else
           j=k+1
        endif
     end do
     array(i)=t
  end do

  return
end subroutine heapsort

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

int main(){
	map<int,int> m;
	for(int i=0;i<3;i++){
		int u,v;cin>>u>>v;
		m[u] += 1;
		m[v] += 1;
	}
	for(auto x: m) if(x.second > 2){
		cout<<"NO"<<endl;
		return 0;
	}

	cout<<"YES"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

#define REP(i, a, b) for ( int i = (a); i < (b); i++ )
#define REVREP(i, a, b) for ( int i = (a); i > (b); i--)
#define DEBUG_INT(var) printf("the value of "#var" is %d\n", var)

using namespace std;

int main(void) {

	int H, W, h, w;
    scanf("%d %d %d %d", &H, &W, &h, &w);

    int ans = W*H - h*W - w*H + w*h; 


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

	return 0;
}


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

struct Node{
    int left,right,parent;
    Node(){
        left=right=parent=-1;
    }
};

int depthnode(Node T[],int D[],int node){
    if(D[node]!=-1)return D[node];
    if(T[node].parent==-1)D[node]=0;
    else D[node]=1+depthnode(T,D,T[node].parent);
    return D[node];
}

int main(){
    int n;cin>>n;
    Node BTree[n];
    int id,l,r,Depth[n],Height[n];
    for(int i=0;i<n;i++){Depth[i]=Height[i]=-1;}
    for(int i=0;i<n;i++){
        scanf("%d %d %d",&id,&l,&r);
        BTree[id].left=l;BTree[id].right=r;
        if(l!=-1)BTree[l].parent=id;
        if(r!=-1)BTree[r].parent=id;
    }
    for(int i=0;i<n;i++){
        if(BTree[i].left==-1&&BTree[i].right==-1){
            int j=i,h=0;
            while(j!=-1){
                Height[j]=max(h,Height[j]);
                j=BTree[j].parent;
                h++;
            }
        }
    }

    for(int i=0;i<n;i++){
        printf("node %d: parent = %d, ",i,BTree[i].parent);
        if(BTree[i].parent!=-1){
        if(BTree[BTree[i].parent].right==i)printf("sibling = %d, ",BTree[BTree[i].parent].left);
        else printf("sibling = %d, ",BTree[BTree[i].parent].right);
        }
        else printf("sibling = -1, ");
        int degree=2;
        if(BTree[i].left==-1)degree--;
        if(BTree[i].right==-1)degree--;
        printf("degree = %d, ",degree);
        printf("depth = %d, ",depthnode(BTree,Depth,i));
        printf("height = %d, ",Height[i]);
        if(BTree[i].parent==-1)printf("root");
        else{
            if(BTree[i].left==-1&&BTree[i].right==-1)printf("leaf");
            else printf("internal node");
        }
        printf("\n");
    }
}


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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

int main() 
{
    int N, K; cin >> N >> K;
    string S; cin >> S;
    rep(i,N){
        if(i == K-1){
            S[i] = tolower(S[i]);
        }
    }
    cout << S << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const long long INF = 1LL << 60;
using Graph = vector<vector<int>>;

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

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

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

int main() {
    int n, m;
    cin >> n >> m;
    int a[n], b[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    int c[m], d[m];
    for (int i = 0; i < m; i++) {
        cin >> c[i] >> d[i];
    }

    for (int i = 0; i < n; i++) {
        int min = 1000000000;
        int nearest;
        for (int j = 0; j < m; j++) {
            int dis = abs(a[i] - c[j]) + abs(b[i] - d[j]);
            if (dis < min) {
                min = dis;
                nearest = j + 1;
            }
        }
        cout << nearest << endl;
    }

    return 0;
}

Measured memory_bytes: 3588
n = int(input())
a = list(map(int,input().split()))
dp = [[0 for i in range(3)] for j in range(n+1)]
for i in range(1,n+1):
  ai = a[i-1]
  dp[i] = dp[i-1][:]
  if i%2:
    dp[i][0] += +ai
    dp[i][1] = max(dp[i-1][0],dp[i-1][1])
  if i%2 == 0:
    dp[i][1] += ai
    dp[i][2] = max(dp[i-1][1],dp[i-1][2])
  if i >= 3 and i%2:
    dp[i][2] += ai
if n%2 == 0:
  print(max(dp[-1][0],dp[-1][1]))
else:
  print(max(dp[-1][1],dp[-1][2]))

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

int main() {
  int N, M;
  cin >> N >> M;
  int D[N];
  for(int n = 0; n < N; ++n) {
    int d; cin >> d;
    D[n] = d;
  }
  int C[M];
  for(int m = 0; m < M; ++m) {
    int c; cin >> c;
    C[m] = c;
  }
  int dp[N + 1][M + 1]; // Move, Halt
  for(int i = 0; i < N + 1; ++i) {
    for(int j = 0; j < M + 1; ++j) {
      dp[i][j] = 1000 * 1000 * 1000 * 2;
    }
  }
  int c = 0;
  dp[0][0] = 0;
  for(int i = 1; i < N + 1; ++i) {
    dp[i][i] = dp[i - 1][i - 1] + C[i - 1] * D[i - 1];
  }
  for(int i = 0; i < M + 1; ++i) {
    dp[0][i] = 0;
  }
  dp[0][0] = 0;
  for(int i = 1; i < N + 1; ++i) {
    for(int j = i; j < M + 1; ++j) {
      dp[i][j] = min(dp[i - 1][j - 1] + C[j - 1] * D[i - 1], dp[i][j - 1]);
    }
  }
  cout << dp[N][M] << endl;
  return 0;
}

Measured memory_bytes: 4324
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
template<class T> inline void chmin(T &a, T b){if(a>=b)a=b;}
template<class T> inline void chmax(T &a, T b){if(a<=b)a=b;}
typedef long long ll;

string s;

int main(){
    cin >> s;
    // Bit 全探索
    REP(bit,1<<3){
        string ans = "";
        int total = s[0] - '0';
        REP(i,3){
            ans += s[i];
            if(bit & (1<<i)){
                ans += "+";
                total += s[i+1] - '0';
            } else {
                ans += "-";
                total -= s[i+1] - '0';
            }
        }
        ans += s[3];
        if(total==7){
            cout << ans + "=7" << endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < m; i++) {
            unionFind.unite(scanner.nextInt() - 1, scanner.nextInt() - 1);
            scanner.next();
        }

        System.out.println(unionFind.parents);
    }

    static class UnionFind {
        int parents;
        private int[] parent;

        UnionFind(int n) {
            parents = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        int root(int n) {
            while (parent[n] != n) {
                n = parent[n] = parent[parent[n]];
            }
            return n;
        }

        void unite(int x, int y) {
            x = root(x);
            y = root(y);
            if (x != y) {
                parents--;
                parent[x] = y;
            }
        }
   }
}


Measured memory_bytes: 83868
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    char S[10];
    for(int i = 0; i < 10; i++)
    {
        S[i] = 'a';
    }
    cin >> S;
    int ans = 0;
    int cnt = 0;
    for(int i = 0; i < 10; i++)
    {
        for(int j = 0; j < 10 - i + 1; j++)
        {
            if(S[i+j] == 'A'
            || S[i+j] == 'C'
            || S[i+j] == 'G'
            || S[i+j] == 'T' ) {
                cnt++;
            } else {
                if (ans < cnt) {
                    ans = cnt;
                }
                cnt = 0;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}

const int maxn = 105;

int n;
char str[maxn];
char op[] = {'k','e','y','e','n','c','e'};

int main()
{
	#ifdef MPS
		fp("1.in","r",stdin);
		fp("1.out","w",stdout);
		double mps = clock();
	#endif
	sf("%s",str+1); n = strlen(str+1);
	if(n == 7)
	{
		fo(k,1,n)
		{
			if(str[k] != op[0]) continue;
			int s = k;
			fo(x,1,6)
			{
				++ s;
				if(s > n || str[s] != op[x]) goto ggx;
			}
			return 0 * pf("YES");
			ggx:;
		}
	}
	fo(i,1,n) fo(j,i,n) if(n-(j-i+1)==7)
	{
		fo(k,1,n) if(k < i || k > j)
		{
			if(str[k] != op[0]) continue;
			int s = k;
			fo(x,1,6)
			{
				++ s;
				while(s >= i && s <= j) ++ s;
				if(s > n || str[s] != op[x]) goto gg;
			}
			return 0 * pf("YES");
			gg:;
		}
	}
	pf("NO");
	D("excution time : %.5f\n",clock()-mps);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

int main(){
	double	x = 0,
		y = 0;
	int	deg = 0;
	int	p, q;
	while(scanf("%d,%d", &p, &q)){
		if(!p && !q) break;
		x += p * sin(deg * M_PI / 180);
		y += p * cos(deg * M_PI / 180);	
		deg += q;
	}
	cout << (int)x << endl;
	cout << (int)y << endl;
	return 0;
}

Measured memory_bytes: 1212
n, k = map(int, input().split())
a = sorted(map(int, input().split()))

if k == 1:
  print('0')
  exit(0)

MAX_NUM = 10**5 + 1
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def combinations(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

s = 0
for i in range(n - k + 1):
  s = (s + (a[-i-1] - a[i]) * combinations(n - i - 1, k - 1)) % MOD

print(s)

Measured memory_bytes: 20244
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(n,v) cout<<#v<<":";for(int i=0;i<n;i++)cout<<v[i]<<" ";cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
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; }


//1~Nまでの登場回数を考える
int main(){
    ll n;
    cin>>n;
    vector<ll> a(n),idx(n+1);
    rep(i,n){
        cin>>a[i];
        idx[a[i]]=i;
    }
    ll ans=0;
    set<ll> used;
    //番兵無し。場合分け
    for(int i=1;i<=n;i++){
        auto ite=used.lower_bound(idx[i]);
        ll nxt;
        ll pre;
        if(ite==used.end()){
            nxt=n-idx[i];
        }
        else{
            nxt=(*ite)-idx[i];
        }
        if(ite==used.begin()){
            pre=idx[i]+1;
        }
        else{
            pre=idx[i]-*prev(ite);
        }
        ans+=nxt*pre*i;
        used.insert(idx[i]);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 12800
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;

ll K;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    ll tmp = 0;
    cin >> K;
    for(int i = 1; i < 2*K; i++){
        tmp = tmp*10+7;
        tmp %= K;
        if(tmp == 0){
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}

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

int main() {
  int n, k;

  cin >> n >> k;

  vector<long> h(n), ans(n);

  for (int i = 0; i < n; i++) cin >> h[i];

  ans[0] = 0;

  for (int i = 1; i < n; i++) {
    ans[i] = 1e64 - 1e63 - 1;
    for (int j = 0; j < k; j++) {
      if (i - j - 1 < 0) break;
      ans[i] = min(ans[i], abs(h[i] - h[i - j - 1]) + ans[i - j - 1]);
    }
  }

  cout << ans[n - 1];

  return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>

using namespace std;

vector<vector<bool> > P;
vector<vector<int> > Ways;

void init(int m) {
    P.clear();
    vector<bool> a(2 * m + 1, false);
    for (int i = 0; i < 2 * m + 1; i++)
        P.push_back(a); 
}

void input_ways(int m) {
    Ways.clear();
    Ways.push_back({0, 1});
    int s, d;
    for (int i = 0; i < m; i++) {
        cin >> s >> d;
        Ways.push_back({s, d});
        Ways.push_back({d, s});
    }
    for (int i = 0; i < 2 * m + 1; i++)
        for (int j = 0; j < 2 * m + 1; j++)
            if (Ways[i][1] == Ways[j][0] && Ways[i][0] != Ways[j][1])
                P[i][j] = true;
}

vector<vector<bool> > product(vector<vector<bool> > a, vector<vector <bool> > b) {
    vector<vector<bool> > result(a.size(), vector<bool>(a[0].size(), false));
    for (int i = 0; i < a.size(); i++)
        for (int j = 0; j < a[0].size(); j++)
            for (int k = 0; k < a[0].size(); k++)
                result[i][j] = result[i][j] || a[k][j] && b[i][k];
    return result;
}

vector<bool> product(vector<vector<bool> > a, vector<bool> b) {
    vector<bool> result(a.size(), 0);
    for (int i = 0; i < a.size(); i++)
        for (int j = 0; j < a[0].size(); j++)
            result[i] = result[i] || a[j][i] && b[j];
    return result;
}

vector<vector<bool> > pow(vector<vector<bool> > matrix, int n) {
    if (n == 1)
        return matrix;
    else if (n % 2 == 0)
        return pow(product(matrix, matrix), n / 2);
    else
        return product(matrix, pow(matrix, n - 1));
}

bool eval(int n, int m, int z) {
    bool result = false;
    vector<bool> start(2 * m + 1, false);
    start[0] = true;
    vector<bool> v = product(pow(P, z), start);
    for (int i = 0; i < v.size(); i++)
        if (v[i] && Ways[i][1] == n)
            result = true;
    return result;
}

int main(){
    int n, m, z;
    while (cin >> n >> m >> z)
        if (n == 0 && m == 0 && z == 0)
            return 0;
        else {
            init(m);
            input_ways(m);
            cout << (eval(n, m, z) ? "yes" : "no") << endl;
        }
}

Measured memory_bytes: 2052
#include <iostream>
#include <algorithm>
#include <cstdint>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>

using namespace std;

int main()
{
    int n,k;
    cin >> n >> k;
    vector<int64_t> vs(n);
    for(auto& v : vs) cin >> v;
    
    int64_t maxvalue = 0;
    vector<int> toback;
    toback.reserve(50);

    const int maxtake = min(n, k);
    for(int a = 0; a <= maxtake; ++a)
    {
        for(int b = 0; b <= maxtake - a; ++b)
        {
            int64_t value = 0;
            toback.clear();
            for(int i = 0; i < n; ++i)
            {
                if(i < a || n - b <= i)
                {
                    value += vs[i];
                    if(vs[i] < 0) toback.push_back(vs[i]);
                }
            }
            sort(begin(toback), end(toback));
            const int maxback = min(k - a - b, (int)toback.size());
            for(int i = 0; i < maxback; ++i)
            {
                value -= toback[i];
            }
            maxvalue = max(maxvalue, value);
        }
    }
    cout << maxvalue << '\n';
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef pair<int,int> P;
int n,m,s,t,A[N],used[N],depth[N];
vector<int> G[N];
vector<P> ans;

void dfs(int x,int d,int prev){
  depth[x]=d;
  for(int i=0;i<G[x].size();i++){
    int nx=G[x][i];
    if(nx==prev)continue;
    if(!used[nx]){
      used[nx]=true;
      dfs(nx,d+1,x);
      if(!A[nx])
	ans.push_back(P(min(x,nx),max(x,nx)));
      A[x]+=A[nx];
    }
    else if(d>depth[nx])A[nx]--,A[x]++;
  }
}

int main(){
  cin>>n>>m;
  for(int i=0;i<m;i++){
    cin>>s>>t;
    G[s].push_back(t);
    G[t].push_back(s);
  }
  used[0]=1;
  dfs(0,0,0);
  sort(ans.begin(),ans.end());
  for(int i=0;i<ans.size();i++)
    cout<<ans[i].first<<' '<<ans[i].second<<endl;
  return 0;
}

Measured memory_bytes: 7296
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {n: u128};

    let sqrt_n = (n as f64).sqrt() as usize + 1;

    let mut dis = std::u128::MAX;

    for i in 1..=sqrt_n {
        if n % i as u128 == 0 {
            let x = n / i as u128;
            dis = std::cmp::min(dis, x + i as u128 - 2)
        }
    }

    println!("{}", dis);
}


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

int main()
{
	long long int N, a[200005],sum  = 0,x = 0,ans = 1000000000000;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> a[i];
		sum += a[i];
	}

	for (int i = 0; i < N-1; i++) {
		sum -= a[i];
		x += a[i];
		ans = min(ans, abs(x - sum));
	}

	cout << ans << endl;

	return 0;
}

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

int main(){
	int D, G; 
	cin >> D >> G;
	vector<int> p(D), c(D);
	for(int i=0;i<D;i++) cin >> p[i] >> c[i];

	int ans = 1e9;
	for(int mask=0;mask<(1<<D);++mask){
		int s=0, num=0, rest_max=-1;
		for(int i=0;i<D;i++){
			if(mask>>i & 1){
				s+=100*(i+1)*p[i]+c[i];
				num+=p[i];
			}else{
				rest_max=i;
			}
		}
		if(s<G){
			int s1=100*(rest_max+1);
			int need=(G-s+s1-1)/s1;
			if(need>=p[rest_max]){
				continue;
			}
			num+=need;
		}
		ans=min(ans,num);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100
#define INF (1<<21)
#define RED 0
#define YELLOW 1
#define BLUE 2

int n,A[MAX][MAX];

void dist()
{
  int i,j,t,min;
  int a[MAX],color[MAX];

  for(i=0;i<n;i++)
    {
      a[i]=INF;
      color[i]=RED;
    }
  a[0]=0;
  color[0]=YELLOW;

  while(1)
    {
      min=INF;
      t=-1;
      for(i=0;i<n;i++)
	{
	  if(min>a[i]&&color[i]!=BLUE)
	    {
	      t=i;
	      min=a[i];
	    }
	}
      if(t==-1) break;
      color[t]=BLUE;
      for(j=0;j<n;j++)
	{
	  if(color[j]!=BLUE && A[t][j]!=INF)
	    {
	      if(a[j]>a[t]+A[t][j])
		{
		  a[j]=a[t]+A[t][j];
		  color[j]=YELLOW;
		}
	    }
	}
    }
  for(i=0;i<n;i++)
    {
      printf("%d",i);
      if(a[i]==INF)printf(" -1\n");
      if(a[i]!=INF)printf(" %d\n",a[i]);
    }
}

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

  int pa,num,t,v;
  for(i=0;i<n;i++)
    {
      scanf("%d %d",&t,&pa);
      for(j=0;j<pa;j++)
	{
	  scanf("%d %d",&v,&num);
	  A[t][v]=num;
	}
    }
  dist();
  return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

int main() {
	string s; cin >> s;
	bool flaga = false;
	bool flagb = false; 
	bool flagc = false;
	for (int i = 0; i < 3; ++i)
	{
		if(s[i]=='a') flaga = true;
		if(s[i]=='b') flagb = true;
		if(s[i]=='c') flagc = true;
 	}
 	if(flaga && flagb && flagc) cout << "Yes" << endl;
 	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  long int member[4000];
  int i;
  int ans[4000];
  int ans_num;
  int n;
  int tmp_e,tmp_p,tmp_q;

  while(1){
    ans_num=0;
    for(i=0;i<4000;i++){
      member[i]=0;
      ans[i]=-1;
    }

    scanf("%d",&n);

    if(n==0)return 0;

    for(i=0;i<n;i++){
      scanf("%d%d%d",&tmp_e,&tmp_p,&tmp_q);
      if(member[tmp_e] != -1){
        member[tmp_e] += tmp_p * tmp_q;
        if(member[tmp_e] >= 1000000){
            ans[ans_num]=tmp_e;
            ans_num++;
            member[tmp_e]=-1;
        }
      }
    }

    if(ans[0] == -1){
      printf("NA\n");
    } else {
      for(i=0;i<ans_num;i++){
        printf("%d\n",ans[i]);
      }
    }

  }
}

Measured memory_bytes: 660
import sys

while 1:
	arr = list(map(int, input().split()))
	H = arr[0]
	W = arr[1]
	
	if H == 0 and W == 0:
		break

	for i in range(H):
		for j in range(W):
			if i % 2 == 0:
				if j % 2 == 0:
					sys.stdout.write('#')
				else:
					sys.stdout.write('.')
			else:
				if j % 2 == 0:
					sys.stdout.write('.')
				else:
					sys.stdout.write('#')
		print()
	print()



Measured memory_bytes: 6304
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
const long long mod = 1e9+7;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

int main(){
    int N;
    cin>>N;
    vi a(N);
    rep(i,N) cin>>a[i];
    sort(ALL(a));
    int mx=a[N-1];
    int mn=a[0];
    int d=mx/2+mx%2;
    debug(mx);
    debug(d);

    if(mn<d){
        cout << "Impossible" << endl;
        return 0;
    }

    if(a[N-2]!=mx){
        cout << "Impossible" << endl;
        return 0;
    }

    if(mx%2==0 and a[1]==d){
        cout << "Impossible" << endl;
        return 0;
    }
    if(mx%2==1 and a[2]==d){
        cout << "Impossible" << endl;
        return 0;
    }


    map<int,int> mp;
    for(int aa:a) mp[aa]++;
    for(int i=(mx%2==0 ? d+1:d);i<=mx;i++){
        cerr << i << endl;
        if(mp[i]<2){
            cout << "Impossible" << endl;
            return 0;
        }
    }



    for(int i=0;i<N;i++){
        if(a[i]<d){
            cout << "Impossible" << endl;
            return 0;
        }
    }
    cout << "Possible" << endl;
}


Measured memory_bytes: 256
def a():
 n, m = [int(i) for i in input().split()]
 for x in range(n+1):
  for y in range(n-x+1):
    z = n-x-y
    
    if 1000*x + 5000*y + 10000*z == m:
      print('%d %d %d'%(z,y,x))
      return
 print('-1 -1 -1')
    
a()

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main() {

  int H,W;
  
  while(H != 0 || W != 0) {
    cin >> H >> W;
    if (H == 0 || W == 0) {
      break;
    }
  for ( int i = 0; i < H; i++ ){
    for ( int j = 0; j < W; j++ ){
        cout << "#";
    }
    cout << endl;
  }
   cout << endl;
}
}
 
    


Measured memory_bytes: 3104
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#include <bitset>
#define INF 2000000000
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define ll long long
#define PL pair<long long, long long>
#define P pair<int,int>
#define mk make_pair
#define en endl;
#define WHITE 0
#define BLACK 2
#define GRAY 1
#define RE return 0;
#define HERE cout<<"    "<<"HERE"<<en

int main(){
  int n;
  cin>>n;
  
  int ans=1;
  int cnt=0;
  for(int i=0;i<n; i++){
    int a;
    cin>>a;
    if(a) cnt++;
    else{
      ans=max(ans,cnt+1);
      cnt=0;
    }
  }
  ans=max(ans,cnt+1);
  
  cout<<ans<<en
}




Measured memory_bytes: 3112
def pri(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i=i+1
    return 1

l=[]
for i in range(2,50000):
    if pri(i):
        l.append(i)
s=5133
ans={}
for i in range(5132):
    for j in range(i,5133):
        a,b=l[i],l[j]
        if a+b>50000:
            break
        if ans.has_key(a+b):
            ans[a+b]+=1
        else:
            ans[a+b]=1
while 1:
    n=int(raw_input())
    if n==0:
        break
    print ans[n] if ans.has_key(n) else 0

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

int main(){
    int n,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                sum+=__gcd(i,__gcd(j,k));
            }
        }
    }
    cout<<sum<<"\n";
    return 0;
}


Measured memory_bytes: 3632
#include<algorithm>
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列
#include <fstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvld;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).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; }


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

    int N;
    cin >> N;

    vll A(N);
    rep(i, N) cin >> A[i];

    ll ans = 0;

    reple(i, 0, 60)
    {
        ll count = 0;
        rep(j, N)
        {
            count += A[j] % 2;
            A[j] /= 2;
        }

        ll tmp = (1LL << i);
        tmp %= MOD;
        tmp *= count;
        tmp %= MOD;
        tmp *= (ll)N - count;
        tmp %= MOD;

        ans += tmp;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 5572
#include<bits/stdc++.h>
using namespace std;
long long Sum,Tmp,Ans=9000000000000000000ll;
long long A[200200];
int main()
{
  int N;
  cin>>N;
  for(int i=0;i<N;i++)
  {
    cin>>A[i];
    Sum+=A[i];
  }
  for(int i=0;i<N;i++)
  {
    Tmp+=A[i];
    Ans=min(Ans,abs(Sum-Tmp-Tmp));
  }
  cout<<Ans<<endl;
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n,m;
int a[N*2];
int ans = 2000000000;
int main(){
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= 2*n; i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+2*n+1);
    int lo = 0, hi = n;
    while (lo+1 < hi){
        //printf("%d %d\n",lo,hi);
        int mid = (lo+hi)/2;
        int cur = 0;
        for (int i = 1; i <= 2*mid; i++){
            cur = max(cur,(a[i]+a[2*mid+1-i])%m);
            if (a[i]+a[2*mid-i+1] >= m){
                hi = mid;
                goto next;
            }
        }
        for (int i = 2*mid+1; i <= 2*n; i++){
            cur = max(cur,(a[i]+a[2*mid+2*n+1-i])%m);
            if (a[i]+a[2*mid+2*n-i] < m){
                lo = mid;
                goto next;
            }
        }
        ans = min(ans,cur);
        hi = mid;
        next:;
    }
    int cur;
    if (lo+1 == hi){
        cur = 0;
        for (int i = 1; i <= 2*hi; i++){
            cur = max(cur,(a[i]+a[2*hi+1-i])%m);
        }
        for (int i = 2*hi+1; i <= 2*n; i++){
            cur = max(cur,(a[i]+a[2*hi+2*n+1-i])%m);
        }
        //printf("%d->%d\n",hi,cur);
        ans = min(ans,cur);
    }

    cur = 0;
    for (int i = 1; i <= 2*lo; i++){
        cur = max(cur,(a[i]+a[2*lo+1-i])%m);
    }
    for (int i = 2*lo+1; i <= 2*n; i++){
        //printf("%d, %d : %d+%d\n",i,2*lo+2*n+1-i,a[i],a[2*lo+2*n+1-i]);
        cur = max(cur,(a[i]+a[2*lo+2*n+1-i])%m);
    }
    //printf("%d->%d\n",lo,cur);
    ans = min(ans,cur);
    printf("%d",ans);



}


Measured memory_bytes: 1024
s = input()
s_reverse = ''.join(list(reversed(s)))
t = ''

while True:
    n = len(t)
    if len(s) <= n:
        if s_reverse == t:
            print('YES')
        else:
            print('NO')
        break
    if s_reverse[n] == 'm':
        t += ''.join(list(reversed('dream')))
    elif s_reverse[n] == 'e':
        t += ''.join(list(reversed('erase')))
    elif s_reverse[n:n+3] == 'rem':
        t += ''.join(list(reversed('dreamer')))
    elif s_reverse[n:n+3] == 'res':
        t += ''.join(list(reversed('eraser')))
    else:
        print('NO')
        break

Measured memory_bytes: 9808
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する


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

    int N,T;
    cin >> N >> T;
    int ans = INF;

    for(int i = 0; i < N; ++i){
        int a,b;
        cin >> a >> b;
        if(b <= T){
            chmin(ans,a);
        }
    }
    if(ans == INF){
        cout << "TLE" << endl;
        return 0;
    }
    cout << ans << endl;
    return 0;
}


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

int main(){
    int a, b;
    int d;
    int r;
    double f;

    cin >> a >> b;

    d = a / b;
    r = a % b;
    f = (double)a/b;

    cout << d << " " << r << " " << fixed << setprecision(8) << f << endl;

}

Measured memory_bytes: 3240
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <math.h>
#include <string.h>
#include <vector>

using namespace std;
int main() {
    int a, b, c, d, e, k;
    string ans;
    cin >> a >> b >> c >> d >> e >> k;
    int maxA = max({a,b,c,d,e});
    int minA = min({a,b,c,d,e});
    if((maxA-minA)<=k){
        ans="Yay!";
    }else{
        ans=":(";
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;



bool operator < (P a, P b){
    return a.first * (b.first + b.second) < b.first * (a.first + a.second);
}
void chmax(P& a, P b){if(a < b) a = b;}

int main(){
    int A, B, C, D, E, F; cin >> A >> B >> C >> D >> E >> F;
    P res = P(0, 100*A);
    for(int a = 0; a <= F; a += 100*A){
        for(int b = 0; a + b <= F; b += 100*B){
            int water = a+b;
            int mx = min(F-water, E*(water/100));
            for(int c = 0; c <= mx; c += C){
                for(int d = 0; c + d <= mx; d += D){
                    int sugar = c + d;
                    P tmp = P(sugar, water);
                    chmax(res, tmp);
                    /*
                    if(res.first*(tmp.first+tmp.second) < tmp.first*(res.first+res.second)){
                        res = tmp;
                    }
                    */
                }
            }
        }
    }
    cout << res.first + res.second << " " << res.first << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int main()
{
  int x;
  vector<int> v;

  while (scanf("%d ", &x) == 1) {
    v.clear();
    int omori = 512;
    while (x > 0) {
      if (x >= omori) {
	x -= omori;
	v.push_back(omori);
      }
      omori /= 2;
      //cout << x << endl;
    }
    for (int i = v.size() - 1; i >= 0; i--) {
      cout << v[i];
      if (i == 0) {cout << endl;}
      else {cout << " ";}
    }
  }
  return 0;
}

Measured memory_bytes: 0
#pragma warning(disable:4996)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <float.h>

#pragma region 定義
typedef long long  ll;
typedef unsigned long long  ull;


#define _itoa(A,N) sprintf(A, "%d", N);

int i_dsort(const void* a, const void* b);
int i_asort(const void* a, const void* b);

int  _gcd(int a, int b);
int  _swp(int* a, int* b);
int _cknum(char* a, int n);
int _atoi(char* s, int len);

int s_asort(const void* a, const void* b);
int s_dsort(const void* a, const void* b);

//昇順
int s_asort(const void* a, const void* b) {
	return(strcmp((char*)a, (char*)b));
}
int s_dsort(const void* a, const void* b) {
	return(strcmp((char*)b, (char*)a));
}

int i_dsort(const void* a, const void* b) {
	return(*(int*)b - *(int*)a);
}
int i_asort(const void* a, const void* b) {
	return(*(int*)a - *(int*)b);
}


int i_gcd(int a, int b);
int i_gcd(int a, int b) {
	if (!b)return a;
	return i_gcd(b, a % b);
}
int i_lcm(int a, int b);
int i_lcm(int a, int b) {
	return (a * b) / i_gcd(a, b);
}
int ll_gcd(ll a, ll b);
int ll_gcd(ll a, ll b) {
	if (!b)return a;
	return ll_gcd(b, a % b);
}
int ll_lcm(ll a, ll b);
int ll_lcm(ll a, ll b) {
	return (a * b) / ll_gcd(a, b);
}

// puts("Yes\n") puts("No\n")
// scanf("%d.%d") 浮動小数点入力を整数２つで得る


//#define pai  3.1415926535 
//#define  _USE_MATH_DEFINES でM_PIが使える

#define deg_rad(X)  (X*(M_PI/180))


int _swp(int* a, int* b)
{
	int tmp;
	tmp = *b; *b = *a; *a = tmp;
	return 0;
}
#define _abs(x) ((x)>0?(x):-(x))
#define _min(x,y) ((x)<(y)?(x):(y))
#define _max(x,y) ((x)<(y)?(y):(x))

int _cknum(char* a, int n) {
	int i;
	char t = '0';

	for (i = 0; i < n; i++) {
		if (a[i] < '0' || a[i]>'9') return 1;
	}
	return 0;
}


int _atoi(char* s, int len) {
	char tmp[20];
	memcpy(tmp, s, len);
	tmp[len] = 0x00;
	return (atoi(tmp));
}

//素因数分解　pf素数が入る　pc 素数の数
//ll _pfact(ll a);
//static ll pf[100000000];
//static ll pc;
//
//ll _pfact(ll a) {
//	long i, r;
//	if (a % 2 == 0) {
//		pf[pc] = 2; pc++;
//		return(_pfact(a / 2));
//	}
//	r = sqrt(a);
//	for (i = 3; i <= r; i += 2) {
//		if (a % i == 0) {
//			pf[pc] = i; pc++;
//			return(_pfact(a / i));
//		}
//	}
//	if (a != 1) {
//		pf[pc] = a; pc++;
//	}
//	return 0;
//
//}

//同じものの最初の文字をNULLにして降順
int _sort(const void* a, const void* b);
int _sort(const void* a, const void* b) {
	char rc;

	rc = strcmp((char*)b, (char*)a);
	if (rc == 0) {
		*(char*)a = 0x00;
		return(1);
	}
	return(rc);
}

#pragma endregion

	
int main(void)
{
	int n,ans,mod;

	scanf("%d", &n);

	mod = n % 1000;
	if (mod) printf("%d\n",(n/1000*1000+1000)-n);
    else printf("0\n");


	return 0;

}

Measured memory_bytes: 1728
#include<stdio.h>
 
int main(){
 
  int a, b, i, N, count=1, min;
  
  scanf("%d", &N);
  
    scanf("%d", &min);
  
  for(i=1;i<N;i++){
     scanf("%d", &a);
    if(min>=a){
    min=a;
    count++;
    }
  }
printf("%d\n", count);
  
  return 0;
 
}

Measured memory_bytes: 128
def main():
    n, k = map(int, input().split())

    d = 1
    while True:
        if n <= (k ** d) - 1:
            print(d)
            return
        d += 1


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


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

int main()
{
  int k;
  cin>>k;
  if(k==2)
  {
    cout<<"-1";
    return 0;
  }
  if(7%k==0)
  {
    cout<<"1";
  	return 0;
  }
  map<int,int> m;
  int p=7%k;
  m[p]=1;
  for(int i=2;i<=1e6;i++)
  {
  	p=((p*(10%k))%k + 7%k)%k;
    if(p ==0)
    {
    	cout<<i;
      return 0;
    }
	if(m.find(p)!=m.end())break;
	m[p]=1;
  }
  cout<<"-1"<<endl;
    return 0;
}



Measured memory_bytes: 50484
#include<iostream>
using namespace std; //宣言することで，std::を省略することができる．
#define MAX 100000
typedef long long llong; //省略という意味

int n,k;

llong T[MAX];
//積載量Pのトラックk台で何個の荷物を詰めるか．
int check(llong P){
    int i = 0;
    for(int j=0;j<k;j++){
        llong s = 0;
        while(s + T[i] <= P){
            s += T[i];
            i++;
            if(i==n)return n;
        }
    }
    return i;
}

int solve(){
    llong left = 0;
    llong right = 100000 * 10000;//荷物の数[n]×1つ中の最大重量[wi]
    llong mid;
    while(right-left > 1){
        mid =(left + right)/2;
        int v = check(mid); //mid==p最大積載量
        if(v>=n)right = mid;
        else left = mid;
    }
    return right;
    }

main(){
    cin >> n >> k;
    for(int i=0; i < n; i++) cin >> T[i];
    llong ans = solve();
    cout << ans << endl;
}


Measured memory_bytes: 3860
#include<bits/stdc++.h>
#define ll long long int 
#define w(x) int x; cin>>x; while(x--)
#define pb push_back
#define mp make_pair
#define mod 1000000007
using namespace std;
int main(){
#ifndef ONLINE_JUDGE 
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll n;
	cin>>n;
	cout<<(n-1)*(n)/2;
}

Measured memory_bytes: 3636
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String strNum = "";
		ArrayList<String> waku = new ArrayList<String>();
		while (true) {
			strNum = br.readLine();
			if ("0 0".equals(strNum)) {
				break;
			}
			for (int i = 0; i < Integer.parseInt(strNum.split(" ")[0]); i++) {
				String line = "";
				if (i == 0 || i == (Integer.parseInt(strNum.split(" ")[0]) - 1)) {
					for (int j = 0; j < Integer.parseInt(strNum.split(" ")[1]); j++) {
						line += "#";
					}
				} else {
					for (int j = 0; j < Integer.parseInt(strNum.split(" ")[1]); j++) {
						if (j == 0 || j == (Integer.parseInt(strNum.split(" ")[1]) - 1)) {
							line += "#";
						} else {
							line += ".";
						}
					}
				}
				waku.add(line);
			}
			waku.add("");
		}
		for (int i = 0; i < waku.size(); i++) {
			System.out.println(waku.get(i));
		}
	}

}

Measured memory_bytes: 65008
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
ll powmod(ll n, ll k, ll m) {
ll r=1;
 for(; k>0; k >>=1) {
   if(k&1) r=(r*n)%m;
   n=(n*n)%m;
 }
  return r;
}

ll fact(ll n) {
ll a=1;
rep(i,n) {
a=a*(n-i);
}
return a;
}

ll pow(ll a, ll b) {
ll x=1;
rep(i,b) {
x=x*a;
}
return x;
}

struct UF{
    vl par;
    UF(ll N):par(N){
        rep(i,N)par[i]=i;
    }
    ll root(ll x){
        if(par[x]==x)return x;
        return par[x]=root(par[x]);
    }
    bool same(ll x,ll y){
        return root(x)==root(y);
    }
    void unite(ll x,ll y){
        x=root(x),y=root(y);
        if(x==y)return;
        par[x]=y;
        return;
    }
};

int main() {
 string S;
  string T;
  cin >>S>>T;
  ll s=S.size();
  ll t=T.size();
  ll ans=INF;
  rep(i,s-t+1) {
    ll aaa=0;
    rep(j,t) {
if(S.at(i+j)!=T.at(j)) {
  aaa++;
}
    }
    
    ans=min(ans,aaa);
  }
  
  
  cout<<ans<<endl;
}


Measured memory_bytes: 3632
# ABC096C - Grid Repainting 2
h, w = list(map(int, input().rstrip().split()))
arr = [list(input().rstrip()) for _ in range(h)]
arr.insert(0, ["."] * (w + 2))
arr.append(["."] * (w + 2))
for i in arr[1:-1]:
    i.insert(0, ".")
    i.append(".")

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if arr[i][j] == "#":
            if arr[i - 1][j] == "#":
                continue
            elif arr[i + 1][j] == "#":
                continue
            elif arr[i][j - 1] == "#":
                continue
            elif arr[i][j + 1] == "#":
                continue
            else:
                print("No")
                break
    else:
        continue
    break
else:
    print("Yes")

Measured memory_bytes: 3064