akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

N, M = map(int, input().split())

A = [ [0 for _ in range(N)] for _ in range(N) ]
visited = [False] * N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    A[a][b] = 1
    A[b][a] = 1

#print(A)

def dfs(node, count):
    if all(visited):
        return count+1

    for i in range(N):
        if A[node][i] == 0:
            continue
        if visited[i]:
            continue

        visited[i] = True
        count = dfs(i, count)
        visited[i] = False

    return count


visited[0] = True
count = dfs(0, 0)
print(count)


Measured memory_bytes: 3064
#include <stdio.h>
#define NUM 100

void put_array(int array[],int n)
{
	int i;

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

	return;
}

void array_reverse(int array[],int n)
{
	int i;

	for (i = 0; i < n / 2; i++) {
		int temp = array[n - i-1];
		array[n - i-1] = array[i];
		array[i] = temp;
	}
}

void print_array(int array[],int n)
{
	int i;

	for (i = 0; i < n-1; i++) {
		printf("%d ",array[i]);
	}

	printf("%d\n",array[i]);
}

int main(void)
{
	int n;
	int array[NUM] = { 0 };

	scanf("%d", &n);

	put_array(array,n);
	array_reverse(array, n);
	print_array(array, n);

	return 0;
}

Measured memory_bytes: 596
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.HashMap;
import java.util.Collections;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        MakeRectangle solver = new MakeRectangle();
        solver.solve(1, in, out);
        out.close();
    }

    static class MakeRectangle {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            Map<Long, Long> map = new HashMap<>();

            for (int i = 0; i < n; i++) {
                long a = in.nextLong();
                map.put(a, map.getOrDefault(a, 0L) + 1);
            }
            List<Long> list = new ArrayList<>(map.keySet());
            Collections.sort(list, Collections.reverseOrder());

            long a = 0;
            long b = 0;

            for (Long key : list) {
                if (map.get(key) < 2) {
                    continue;
                }
                if (a == 0) {
                    a = key;
                    if (map.get(key) >= 4) {
                        b = key;
                    }
                } else if (b == 0) {
                    b = key;
                }

                if (a > 0 && b > 0) {
                    break;
                }
            }
            out.print(a * b);
        }

    }
}



Measured memory_bytes: 64408
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int n;
    int k;
    int cnt = 0;

    vector< vector<int> > vvi;

    vvi.resize(11);

    vvi[0] = { 0,2,4,7,9 };
    vvi[1] = { 1,4,6,8,10 };
    vvi[2] = { 1,3,5,7,9 };
    vvi[3] = { 0,2,4,6,9 };
    vvi[4] = { 1,3,6,8,10 };
    vvi[5] = { 0,3,5,7,9 };
    vvi[6] = { 0,2,4,6,8 };
    vvi[7] = { 1,3,5,8,10 };
    vvi[8] = { 0,2,5,7,9 };
    vvi[9] = { 2,4,6,8,10 };
    vvi[10] = { 1,3,5,7,10 };

    if (scanf("%d %d", &n, &k) < 2) return 0;

    int div = 0;
    int mod = 0;

    div = (n - 2) / 11;
    mod = (n - 2) % 11;

    cnt = div * 5;

    int start = 0;
    start = div * 11 + 1;

    for(int i = start; i < start + mod; i++)
    {
        if (binary_search(
                vvi[(i - 1) % 11].begin()
              , vvi[(i - 1) % 11].end(), k)) {
            cnt++;
        }
    }

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


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REP2(i, x, n) for (int i = x; i < (n); i++)
#define ALL(n) begin(n), end(n)
const long long INF = numeric_limits<long long>::max();
int main()
{
    int H, A;
    cin >> H >> A;
    int d = H / A;
    int m = H % A;
    if (m == 0)
        cout << d << endl;
    else
        cout << d + 1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define int long long

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

typedef pair<int, int> pint;

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front

#define MOD (1000 * 1000 * 1000 + 7)

struct Edge{int from, to, cost; };

int log2(int n) {
    int i = 1;
    int j = 0;

    while (i <= n) {
        i *= 2;
        j++;
    }

    return j;
}

int pow2(int n) {
    return 1 << n;
}

signed main() {
    int L;
    cin >> L;

    int N = log2(L);
    vector<Edge> edges;

    REPS(i, N-1) {
        edges.pb(Edge{i, i+1, 0});
        edges.pb(Edge{i, i+1, 1 << (N-i-1)});
    }

    if (L != pow2(N-1)) {
        int left = pow2(N-1);
        int right = L-1;

        while (left <= right) {
            int num = right - left + 1;
            int l = log2(num) - 1;

            edges.pb(Edge{1, N-l, left});
            left += 1 << l;
        }
    }

    cout << N << " " << SZ(edges) << endl;
    for (Edge &e: edges) {
        cout << e.from << " " << e.to << " " << e.cost << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import sys
import operator

for line in sys.stdin:
    a, op, b = line.strip().split()

    if op == '?':
        break

    a, b = map(int, [a, b])
    op = {
        '+': operator.add,
        '-': operator.sub,
        '*': operator.mul,
        '/': operator.floordiv
    }[op]

    print(op(a, b))



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

int main(){
    long long m, d, c;
    cin >> m;
    long long sum = 0, sum1 = 0, sum2 = 0;
    for (int i = 0; i < m; i++)
    {
        cin >> d >> c;
        sum2 += c;
        sum1 += d*c;
    }
    while (sum1 >= 10)
    {
        sum += sum1 / 10;
        sum1 -= 9 * (sum1 / 10);
    }
    
    sum += sum2 - 1;
    cout << sum << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int price[5], i, j, sum = 4000;

  for(i = 0 ; i < 5 ; i++){
    scanf("%d",&price[i]);
  }
  for(i = 0 ; i < 3  ; i++){
    for(j = 3 ; j < 5 ; j++){
      if(sum > price[i]+price[j])
	sum = price[i] + price[j];
    }
  }
  printf("%d\n",sum-50);
  return 0;
}

Measured memory_bytes: 592
package main

import (
    "fmt"
    "os"
    "bufio"
    "strings"
    "strconv"
    "sort"
)

func main() {
    var fp *os.File = os.Stdin
    reader := bufio.NewReaderSize(fp, 1024)

    line := readLine(reader)
    line = readLine(reader)
    arr := strings.Split(line, " ")
    var arr_num []int

    for _, v := range arr {
        num, _ := strconv.Atoi(v)
        arr_num = append(arr_num, num)
    }

    sort.Sort(sort.Reverse(sort.IntSlice(arr_num)))

    arr_num_sum := 0
    for k, v := range arr_num {
        if k != 0 {
            arr_num_sum += v
        }
    }

    if arr_num[0] < arr_num_sum {
        fmt.Println("Yes")
    } else {
        fmt.Println("No")
    }
}

func readLine(reader *bufio.Reader) string {
    buf := make([]byte, 0, 1024)

    for {
        l, p, _ := reader.ReadLine()

        buf = append(buf, l...)

        if !p {
            break
        }
    }

    return string(buf)
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
int main() {
	int n;
	scanf("%d", &n);
	vector<int> X(n), Y(n), id(n);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", &X[i], &Y[i]);
		id[i] = i;
	}
	vector<pair<int, pair<int, int>>> edges;
	sort(id.begin(), id.end(), [&](int a, int b) {
		return X[a] < X[b];
	});
	for (int i = 0; i + 1 < n; ++i) {
		edges.push_back({min(abs(X[id[i]] - X[id[i + 1]]), abs(Y[id[i]] - Y[id[i + 1]])), {id[i], id[i + 1]}});
	}
	sort(id.begin(), id.end(), [&](int a, int b) {
		return Y[a] < Y[b];
	});
	for (int i = 0; i + 1 < n; ++i) {
		edges.push_back({min(abs(X[id[i]] - X[id[i + 1]]), abs(Y[id[i]] - Y[id[i + 1]])), {id[i], id[i + 1]}});
	}
	sort(edges.begin(), edges.end());
	vector<int> par(n);
	iota(par.begin(), par.end(), 0);
	function<int(int)> getRoot = [&](int a) {
		if (par[a] == a) return a;
		return par[a] = getRoot(par[a]);
	};
	ll ans = 0;
	for (int i = 0; i < edges.size(); ++i) {
		int a, b;
		tie(a, b) = edges[i].second;
		int pa = getRoot(a), pb = getRoot(b);
		if (pa == pb) continue;
		par[pa] = pb;
		ans += edges[i].first;
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 6004
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 2e5;

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

	int n;
	cin>>n;
	map<string,vector<pair<int,int>>> stor;
	for(int i=1;i<=n;i++)
	{
		string s;
		int p;
		cin>>s>>p;
		stor[s].push_back({p,i});
	}

	for(auto& s:stor)
	{
		sort(stor[s.first].begin(),stor[s.first].end(),greater<pair<int,int>>());
		for(auto v:s.second)
			cout<<v.second<<'\n';
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

int main()
{
  long n;
  vector<long> k(5);
  cin >> n;
  for (int i = 0; i < 5; i++)
  {
    cin >> k[i];
  }

  cout << fixed << setprecision(0) << ceil((double)n / *min_element(k.begin(), k.end())) + 4 << endl;

  return 0;
}

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

int main() {
	int n, c;
	cin >> n >> c;

	int all = 0;

	vector<int> p(c);
	for(int i = 0; i < c; ++i) {
		cin >> p[i];
		all += p[i];
	}

	if (all % (n + 1) == 0) cout << all / (n + 1) << endl;
	else cout << all / (n + 1) + 1 << endl;
}



Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

typedef long long ll;
#define READ(a) int a; cin >> a;
#define READARR(a, n) int a[(n) + 1] = {}; FOR(i, 1, (n)) {cin >> a[i];}
#define READMAT(a, n, m) int a[n + 1][m + 1] = {}; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll mod = 1e9 + 7;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	READ(a);
	READ(b);
	int c = __gcd(a, b), sqr = sqrt(c);
	
	set <int> s = {1};
	FOR (i, 2, min(sqr, c))
	{
	    if (c % i) continue;
	    s.insert(i);
	    while (c % i == 0) c /= i;
	}
	
	s.insert(c);
	cout << s.size();
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  int n;
  scanf("%d",&n);
  
  if ( n%10 ==1 ||  n%10 == 6 ||  n%10 == 8 ||  n%10 == 0 ){
  	printf("pon");
  }
  else if (n%10 == 3){
  	printf("bon");
  }
  else {
	printf("hon");
  }
return 0;
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std ;
int n, w;
std::vector<pair<int,ll>> inp;
vector<vector<ll>> dp;

ll knapsack(int i=0,int curr_wt = w)
{
    if(i == n) return 0;
    if(dp[i][curr_wt] == -1)
    {
        ll ans = knapsack(i+1,curr_wt);
        if(curr_wt - inp[i].first >=0)
        {
            ans = max (ans , knapsack(i+1,curr_wt - inp[i].first) + inp[i].second);
        }
        dp[i][curr_wt] = ans;
        return ans;
    }
    else return dp[i][curr_wt];
}

ll bottoms_up_knapsack ()
{
    for(int i=0;i<=w;i++)
    {
        dp[0][i] = 0;
    }
    for(int i=0;i<=n;i++)
    {
        dp[i][0] = 0;
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=w;j++)
        {
            ll ans = dp[i-1][j];
            if(j-inp[i-1].first>=0)
            {
                ans = max(ans,dp[i-1][j-inp[i-1].first] + inp[i-1].second);
            }
            dp[i][j] = ans;
        }
    }
    return dp[n][w];
}

int main()
{
    cin>>n>>w; 
    inp.resize(n);
    
    for(int i=0;i<n;i++)
    {
        cin>>inp[i].first;
        cin>>inp[i].second;
    }
    dp.assign(n+1,vector<ll> (w+1,-1));
    cout<<bottoms_up_knapsack()<<endl;
    /*for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=w;j++)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/
}

Measured memory_bytes: 83080
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0 ; i < n ; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        int ans = 0;
        for (int i = 0 ; i < n ; i++) {
            if ((long) x[i] * x[i] + (long) y[i] * y[i] <= (long) d * d) {
                ans ++;
            }
        }
        System.out.println(ans);
    }

}


Measured memory_bytes: 61480
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include<algorithm> 
#include <iomanip>
#include <math.h>
#include <iostream>
#include <bitset>
#include <map>

#define db double
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define maxn 5005
#define mod 998244353
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define vv(z,a,b) vector<vector<int>>z(a,vector<int>(b))
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(c) begin(c),end(c)
#define pp pair<int,int>
#define fix(n) fixed << setprecision(n)
#define gmax(a,b) __gcd(a,b)
#define gmin(a,b) a/__gcd(a,b)*b
using namespace std;
//obj;
class binary{
public:
    bool isOK(int index, int key,vi a) {
    if (a[index] >= key) return true;
    else return false;
}
int binary_search(int key,vi a) {
   
    int ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    int ok = (int)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* ok と ng のどちらが大きいかわからないことを考慮 */
    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;

        if (isOK(mid, key,a)) ok = mid;
        else ng = mid;
    }
    return ok;
}
}obj;

int main(){
int n;cin>>n;
if(n>=30)cout<<"Yes"<<endl;
else cout<<"No"<<endl;


return 0;

 }


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

typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

#define pi pair<int,int>
#define pl pair<lld,lld>

#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define mem0(x) memset(x,0,sizeof(x))
#define fillnum(x,n) fill(begin(x),end(x),n)
#define asort(x) sort(x.begin(),x.end())
#define dsort(x,t) sort(x.begin(),x.end(),greater<t>())
#define vuniq(x) x.erase(unique(x.begin(), x.end()), x.end())

#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)

int main() {
    ll A,B,C;
    cin >> A >> B >> C;
    cout << max(0LL,C-(A-B)) << endl;
}

Measured memory_bytes: 3548
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>

typedef long long ll;
using namespace std;

typedef pair<int,int> P;

void seek_lcs(int a,int b,int dp[10+1][10+1],int* num,int* base,vector<int>& idx){
	if(a==0 || b==0){
		return;
	}

	if(num[a] == base[b]){
		seek_lcs(a-1,b-1,dp,num,base,idx);
		idx.push_back(num[a]);
	}
	else{
		if(dp[a-1][b] >= dp[a][b-1]){
			seek_lcs(a-1,b,dp,num,base,idx);
		}
		else{
			seek_lcs(a,b-1,dp,num,base,idx);
		}
	}

}

int main()
{
	int T;
	int l[10];
	int v1,v2;
	while(~scanf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d",
		l,l+1,l+2,l+3,l+4,l+5,l+6,l+7,l+8,l+9,&v1,&v2)){
			double lb=0.0;
			double ub=1000000000;

			int sum = 0;
			for(int i=0;i<10;i++) sum+=l[i];
			for(int i=0;i<100;i++){
				double md = (ub+lb)/2.0;
				if((md/3600.0)*v1 +(md/3600.0)*v2 > sum) ub = md;
				if((md/3600.0)*v1 +(md/3600.0)*v2 < sum) lb = md;
			}

			double dist_t = v1*lb/3600.0;

			double dist_l = 0;
			for(int i=0;i<10;i++){
				dist_l += (double)l[i];
				if(dist_l >= dist_t){
					cout << i+1 << endl;
					break;
				}
			}
			//printf("%f\n",ub);
			//printf("%f\n",lb);
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define int long long
using namespace std;
bool b[123546];
int ans[123456];
signed main() {
	int n, m; cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a; cin >> a;
		b[a] = 1;
	}
	ans[0] = 1;
	for (int i = 1; i <= n; i++) {
		if (b[i])ans[i] = 0;
		else if (i == 1)ans[i] = 1;
		else ans[i] = ans[i - 1] + ans[i - 2];
		ans[i] %= 1000000007;
	}
	cout << ans[n] << endl;
	cin >> n;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

int main()
{
   int n,k;
   cin >> n >> k;
   double ans = 0;
   for(int i = 1;i <= n ; i++)
   {
      int j = 0;
      for(j;;j++)
      {
         if(k<=(i<<j))break;
      }
      ans += 1.0/(n*(1<<j));
   }
  printf("%.10lf\n",ans);
   return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<queue>
using namespace std;
typedef pair<int, int> P;

int w, h;
int yoko[30][29], tate[29][30];
bool used[30][30];
int counter[30][30];

bool isOut(int x, int y) {
  if (x < 0 || y < 0 || x >= w || y >= h) return true;
  return false;
}

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

int main() {
  while (1) {
    scanf("%d%d", &w, &h);
    if (w == 0) break;
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) used[i][j] = false, counter[i][j] = 0;
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w - 1; j++) scanf("%d", &yoko[i][j]);
      if (i == h - 1) break;
      for (int j = 0; j < w; j++) scanf("%d", &tate[i][j]);
    }
    queue<P> que;
    que.push(P(0, 0));
    used[0][0] = true;
    counter[0][0] = 1;
    while (!que.empty()) {
      P p = que.front(); que.pop();
      int x = p.first, y = p.second;
      for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (isOut(nx, ny) || used[ny][nx]) continue;
        if (i == 0 && yoko[y][x] == 1) continue;
        if (i == 1 && tate[y][x] == 1) continue;
        if (i == 2 && yoko[y][x-1] == 1) continue;
        if (i == 3 && tate[y-1][x] == 1) continue;
        que.push(P(nx, ny));
        used[ny][nx] = true;
        counter[ny][nx] = counter[y][x] + 1;
      }
      if (used[h - 1][w - 1]) break;
    }
    printf("%d\n", counter[h - 1][w - 1]);
  }
}



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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;

int main() {
    int h, w;
    cin >> h >> w;

    vector<int> s(26, 0);
    string a;
    REP(i, h) {
        cin >> a;
        REP(j, w) {
            s[a[j] - 'a']++;
        }
    }

    if (h * w == 1) {
        cout << "Yes" << endl;
        return 0;
    }
    REP(i, (h / 2) * (w / 2)) {
        bool ok = false;
        REP(j, 26) {
            if (s[j] >= 4) {
                s[j] -= 4;
                ok = true;
                break;
            }
        }
        if (!ok) {
            cout << "No" << endl;
            return 0;
        }
    }
    if (h % 2 == 1 && w % 2 == 1) {
        REP(i, h / 2 + w / 2) {
            bool ok = false;
            REP(j, 26) {
                if (s[j] >= 2) {
                    s[j] -= 2;
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                cout << "No" << endl;
                return 0;
            }
        }
        REP(i, 26) {
            if (s[i] == 1) {
                cout << "Yes" << endl;
                return 0;
            }
        }
        cout << "No" << endl;
    } else if (h % 2 == 1) {
        REP(i, w / 2) {
            bool ok = false;
            REP(j, 26) {
                if (s[j] >= 2) {
                    s[j] -= 2;
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                cout << "No" << endl;
                return 0;
            }
        }
        cout << "Yes" << endl;
    } else if (w % 2 == 1) {
         REP(i, h / 2) {
            bool ok = false;
            REP(j, 26) {
                if (s[j] >= 2) {
                    s[j] -= 2;
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                cout << "No" << endl;
                return 0;
            }
        }
        cout << "Yes" << endl;
    } else {
        cout << "Yes" << endl;
    }
}


Measured memory_bytes: 256
import Data.List

countCharactersInString :: String -> Char -> Int
countCharactersInString s c = length $ filter (== c) s

f :: Int -> Int -> Int -> String
f na nb nc 
  | x+1 < y || x+1 < z || y+1 < z = "NO"
  | otherwise = "YES"
    where
      [x, y, z] = sort [na, nb, nc]

main = do
  s <- getLine
  let na = countCharactersInString s 'a'
  let nb = countCharactersInString s 'b'
  let nc = countCharactersInString s 'c'
  putStrLn $ f na nb nc


Measured memory_bytes: 7164
/**
* Think twice, code once.
* 1.integer overflow(maybe even long long overflow : (a+b >= c) -> (a >= c-b)
* 2.runtime error
* 3.boundary condition
* ---------------------------------------------------------------------------------------
* Author : zzy
* Date : 2020-03-23-03.25.36 Sunday
*/
#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
#define SZ(x) ((int)(x).size())

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const i64 maxn = 3100;
const i64 mod = 998244353;
i64 dp[maxn][maxn], n, s, a[maxn], ans=0;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif

    cin >> n >> s;
    for1(i, n) cin >> a[i];
    ms(dp, 0);
    for (int i = 1; i <= n; ++i) {
//        for (int j = s; j >= a[i]; --j) dp[j] = (dp[j]+dp[j-a[i]])%mod;
//        dp[a[i]] = (dp[a[i]]+i)%mod;
//        ans = (ans+dp[s])%mod;
        for (int j = 0; j <= s; ++j) {
            dp[i][j] = dp[i-1][j];
        }
        for (int j = a[i]; j <= s; ++j) {
            dp[i][j] = (dp[i-1][j]+dp[i-1][j-a[i]])%mod;
        }
        dp[i][a[i]] = (dp[i][a[i]]+i)%mod;
        ans = (ans+dp[i][s])%mod;
    }
    cout << ans << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


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

int main () {
    int n, m, l;
    long long a[100][100], b[100][100], c[100][100];
    for (int i=0; i<100; i++) {
        for (int j=0; j<100; j++) {
            a[i][j] = 0;
            b[i][j] = 0;
        }
    }

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

    for (int i=0; i<n; i++) {
        for (int j=0; j<l; j++) {
            c[i][j] = 0;
            for (int k=0; k<m; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<l; j++) {
            if (j) cout << " ";
            cout << c[i][j];
        }
        cout << endl;
    }
    return 0;
}

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

#define int long long
#define DEBUG(x) cerr <<#x<<":"<<x<<endl;
#define DEBUG2(x, y) cerr <<#x<<":"<<x<<" "<<#y<<":"<<y<<endl;
#define DEBUG3(x, y, z) cerr <<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl;
#define DEBUGVC(x) cerr <<#x<<": "; for(auto a:x) cerr << a <<" "; cerr << endl;
#define DEBUGMP(x) cerr <<#x<<":"<<endl; for(auto a:x) cerr << a.first <<" "<< a.second << endl;
#define MAX_N (1000006)
#define INF (1LL << 60)
const int MOD = 998244353LL;

/* x^nを高速に求める */
int mod_pow(int x, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res = res*x%MOD;  // 最下位ビットが立ってる時にx^(2^i)を掛ける
		x = x*x%MOD;              // xを順次二乗していく
		n >>= 1;    // 右ビットシフト
	}
	return res;
}

signed main(){
    int N;
    cin >> N;
    vector<int> D(N);
    int f=0;
    for(int i=0; i<N; i++) {
        cin >> D[i];
        if(D[i]==0) f++;
    }
    if(D[0]!=0 || f!=1) {
        cout << 0 << endl;
        return 0;
    }

    map<int,int> mp;
    for(int i=0; i<N; i++) mp[D[i]]++;

    int ans=1;
    for(auto it: mp){
        //DEBUG2(it.first, it.second);
        if(it.first <= 1) continue;
        int pr = it.first-1;
        for(int i=0; i<it.second; i++){
            ans *= mp[pr];
            ans %= MOD;
        }
    }

    cout << ans%MOD << endl;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int P = 1e4 + 5;
char s[N];
ll cnt[P];

ll binpow(ll a, ll b, ll p) {
	a %= p;
	ll res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res % p;
}

int main()
{
	int n, p;
	scanf("%d%d%s", &n, &p, s);
	if (p == 2 || p == 5) {
		ll ans = 0;
		for (int i = 0; i < n; i++) {
			if ((s[i] - '0') % p == 0) ans += i + 1;
		}
		printf("%lld\n", ans);
		return 0;
	}
	ll cur = 0;
	cnt[0] = 1;
	for (int i = n - 1; i >= 0; i--) {
		cur = (cur + (s[i] - '0') * binpow(10, n-i-1, p)) % p;
		cnt[cur]++;
	}
	ll ans = 0;
	for (int i = 0; i < p; i++) {
		ans += cnt[i] * (cnt[i] - 1) / 2;
	}
	printf("%lld\n", ans);
	return 0;
}

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

#define ll long long
#define mod 1000000007

using namespace std;

ll power(ll x, ll N){
	ll res = 1;
	for(ll i=1; i<=N; i++){
		res*=x;
		res%=mod;
	}
	return res;
}


int main(){
	ll N;
	cin>>N;

	ll total = power(10, N);
	ll noZero = power(9, N);
	ll noNine = power(9, N);
	ll neitherZeroNorNine = power(8, N);

	ll ans = total - noNine - noZero + neitherZeroNorNine;
	ans%=mod;
	ans = (ans+mod)%mod;
	cout<<ans;

	return 0;
}

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


int main(){
  int N;
  cin>>N;
  vector<int> A(N);
  for(int i =0;i<N;i++){
   cin>>A.at(i);
}
  bool a =false;
  int sum =0;
  for(int i =0;i<1000000000;i++){
    for(int j=0;j<N;j++){
      if(A.at(j)%2!=0){
        a = true;
        break;
      }else{
        A.at(j)/=2;
    }
    }
    if(a){
      break;
    }
  sum++;
  }
  cout<<sum<<endl;
}

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

import sys

DEBUG = False

def solve():
    return


def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().rstrip().split(sep)]

def read_int():
    return int(sys.stdin.readline())

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    chars = set(list(sys.stdin.readline().rstrip()))
    if len(chars) > 1:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
import sys
input = sys.stdin.readline # 改行コード「\n」を呼んでしまうため、文字数など、注意！！

n = int(input())
ans = 0

for i in range(1, n+1,2):
    cnt = 0
    for j in range(1,i+1):
        # print(i,j)
        if i % j == 0:
            cnt += 1
        if cnt == 8:
            ans += 1
            break
    # print(cnt)

print(ans)

Measured memory_bytes: 3060
#include<stdio.h>
int main(void)
{
  int n,m,i,res,a;
  int sum = 0;

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

  for(i=0;i<m;i++){
    scanf("%d",&a);
    sum+=a;
  }

  res=n-sum;

  if(res>=0)
  printf("%d",res);

  else
    printf("%d",-1);

  return 0;
}


Measured memory_bytes: 1732
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=5005;
const ll mod=1e9+7;
ll f[maxn][maxn][2],g[maxn][2],fac[maxn];
int sz[maxn],fz[maxn],n,fa[maxn];
vector<int>G[maxn];
namespace {
	inline ll Add(const ll &x,const ll &y) {
		ll res=x+y;
		if(res>=mod)
			res-=mod;
		return res;
	}
	inline ll Sub(const ll &x,const ll &y) {
		ll res=x-y;
		if(res<0)
			res+=mod;
		return res;
	}
	inline ll Mul(const ll &x,const ll &y) {
		return x*y%mod;
	}
}
inline void dp(int u) {
//	cout<<"!!!"<<u<<endl;
	f[u][0][0]=1;
	for(int p=0;p<(int)G[u].size();++p) {
		int v=G[u][p];
//		cout<<"???"<<v<<endl;
		if(v==fa[u])
			continue;
		fa[v]=u;
		dp(v);
		sz[u]+=sz[v];
//		cout<<u<<" "<<v<<" "<<sz[u]<<" "<<sz[v]<<endl;
		memset(g,0,sizeof g);
		for(int i=fz[u];~i;--i)
			for(int j=fz[v];~j;--j)
				g[i+j][0]=Add(g[i+j][0],Mul(f[u][i][0],f[v][j][0])),
				g[i+j][0]=Add(g[i+j][0],Mul(f[u][i][1],f[v][j][1])),
				g[i+j][1]=Add(g[i+j][1],Mul(f[u][i][0],f[v][j][1])),
				g[i+j][1]=Add(g[i+j][1],Mul(f[u][i][1],f[v][j][0]));
		for(int i=fz[u]+fz[v];~i;--i)
			f[u][i][0]=g[i][0],f[u][i][1]=g[i][1];
		fz[u]+=fz[v];
	}
	sz[u]++;
	if(u>1)
		for(int i=fz[u];~i;--i)
			f[u][sz[u]][0]=Add(f[u][sz[u]][0],Mul(f[u][i][1],(sz[u]-i)&1?0:fac[(sz[u]-i)>>1])),
			f[u][sz[u]][1]=Add(f[u][sz[u]][1],Mul(f[u][i][0],(sz[u]-i)&1?0:fac[(sz[u]-i)>>1]));
	fz[u]++;
}
int main() {
	fac[0]=1;
	for(int i=1;i<=5000;++i)
		fac[i]=Mul(fac[i-1],(i<<1)-1);
	read(n);
	for(int i=1,x,y;i<n;++i) {
		read(x),read(y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	fa[1]=0;
	dp(1);
	ll ans=0;
	for(int i=1;i<=n+1;++i)
		ans=Add(ans,Mul(f[1][i-1][0],(n-i+1)&1?0:fac[(n-i+1)>>1])),
		ans=Sub(ans,Mul(f[1][i-1][1],(n-i+1)&1?0:fac[(n-i+1)>>1]));
//	printf("%lld\n",f[1][sz[1]][0]+f[1][sz[1]][1]);
	writeln(ans);
}

Measured memory_bytes: 391040
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define el endl
#define INF LONG_LONG_MAX
#define NINF LONG_LONG_MIN
#define sz size()
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));
#define nn " " 
#define bg begin()
#define en end()
#define mod 1000000007
using namespace std;

int main()
{
    ll n;
    cin>>n;
    ll a[n][3],i,j;
    for(i=0;i<n;i++)
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    ll dp[n][3];
    dp[0][0]=a[0][0];
    dp[0][1]=a[0][1];
    dp[0][2]=a[0][2];
    for(i=1;i<n;i++)
    {
        for(j=0;j<3;j++)
        {
            dp[i][j]=a[i][j]+max(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3]);
        }
    }
    ll x=0;
    for(i=0;i<3;i++)
        x=max(dp[n-1][i],x);
    cout<<x;
}

Measured memory_bytes: 4992
//-- In The Name of God --
#include<bits/stdc++.h>
using namespace std;


#define      mod     1e9+7
#define      pai     acos(-1)
#define      ff      first
#define      ss      second
#define      ll      long long
#define      pb      push_back
#define      mp      make_pair
#define      endl    "\n"
#define      fii     freopen("input.txt","r",stdin);
#define      foo     freopen("output.txt","w",stdout);
#define      fast    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);

const   ll   mx=1e5+100;

int main()
{
    fast;
    ll i,j,a,b,c,d,n,m,t;
    cin>>n;
    ll l=1,r=9;
    if(n%1==0||n%2==0||n%3==0||n%4==0||n%5==0||n%6==0||n%7==0||n%8==0||n%9==0)
    {
        if(n%1==0&&((n/1)>=l&&(n/1)<=r))
        {
            cout<<"Yes"<<endl;
        }
        else if(n%2==0&&((n/2)>=l&&(n/2)<=r))
        {
            cout<<"Yes"<<endl;
        }
        else if(n%3==0&&((n/3)>=l&&(n/3)<=r))
        {
            cout<<"Yes"<<endl;
        }
        else if(n%4==0&&((n/4)>=l&&(n/4)<=r))
        {
            cout<<"Yes"<<endl;
        }
        else if(n%5==0&&((n/5)>=l&&(n/5)<=r))
        {
            cout<<"Yes"<<endl;
        }
        else if(n%6==0&&((n/6)>=l&&(n/6)<=r))
        {
            cout<<"Yes"<<endl;
        }
        else if(n%7==0&&((n/7)>=l&&(n/7)<=r))
        {
            cout<<"Yes"<<endl;
        }
        else if(n%8==0&&((n/8)>=l&&(n/8)<=r))
        {
            cout<<"Yes"<<endl;
        }
        else if(n%9==0&&((n/9)>=l&&(n/9)<=r))
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }

    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}



Measured memory_bytes: 3652
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, T: int, t: "List[int]"):

    tot = 0
    for i in range(N-1):
        if t[i+1]-t[i] >= T:
            tot += T
        else:
            tot += t[i+1]-t[i]
    print(tot+T)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    t = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, T, t)


if __name__ == '__main__':
    main()


Measured memory_bytes: 27196
// finish date: 2018/04/21

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
#define ll double
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vvd vector<vector<double>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define bigmod 1000000007
#define INF 1050000000
#define pii pair<int,int>


int main() {
    int N;
    cin >> N;
    char c;
    map<char, int> mp;
    rep(i, N) {
        cin >> c;
        mp[c]++;
    }
    if (mp.size() == 3) cout << "Three" << endl;
    else cout << "Four" << endl;


    return 0;
}

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

bool strCmp(string a, string b){
    //* a is part of S
    int n = a.size();
    if(n==0) return true;
    bool isGood = true;
    for(int i=0; i< n; i++){
        if(a[i]!='?'&& a[i] != b[i]){
            isGood = false; 
            break;
        }
    }
    return isGood;
}

void solve(string S, string T){
    int n = S.size(), m=T.size();
    bool isGood = false;
    if (n<m){
        cout << "UNRESTORABLE" << endl;
        return;
    }
    for(int i= n-m; i>= 0; i--){
        if(strCmp(S.substr(i, m), T)){
            S.replace(i, m, T);
            isGood = true;
            break;
        }
    }
    if (!isGood) {
        cout << "UNRESTORABLE" << endl;
        return;
    }
    for(int i=0; i< n; i++){
        if(S.at(i)=='?') S.at(i) = 'a';
    }
    cout << S << endl;
    return;
}
int main(){
    string S, T;
    cin >> S;
    cin >> T;
    solve(S, T);
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			String line = sc.nextLine();
			int[] carray = new int[line.length()];
			for(int i = 0 ;i<line.length();i++){
				carray[i] = Character.getNumericValue(line.charAt(i));
			}
			for(int i=line.length();i>0;i--){
				int array[] = new int[i-1];
				for(int j = 0 ; j < i-1;j++){
					array[j] = (carray[j] + carray[j+1])%10;
				}
				if(i ==2){
					System.out.println(array[0]);
					break;
				}
				carray = array;
			}
					
		}
	}

}

Measured memory_bytes: 26164
//#include <bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<cstring>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<iterator>
#include<algorithm>
#include<bitset>

#define Filein(N) freopen("N", "r", stdin)
#define Fileout(N) freopen("N", "w", stdout)
#define sci(x) scanf("%d", &x)
#define sci2(x,y) scanf("%d%d", &x,&y)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll(x) scanf("%lld",&x)
#define scd(x) scanf("%lf", &x)
#define scstr(x) scanf("%s", x)
#define pfi(x) printf("%d", x)
#define pfll(x) printf("%lld", x)
#define pfd(x) printf("%f", x)
#define pfstr(x) printf("%s", x)
#define ps printf(" ")
#define pn printf("\n")
#define pfdt printf("..")

#define For(var,start,end) for(int var=start; var<=end;var++)
#define rFor(var,start,end) for(int var=start; var>=end; var--)
#define TestCase int testcase, cs=1; cin>>testcase;while(testcase--)
#define Trav(var,container) for(auto var:container)

#define mkp make_pair
#define pb push_back
#define fi first
#define se second

#define px(x) cout<<"X -> "<<x<<endl;
#define py(x) cout<<"Y = "<<x<<endl;
#define pz(x) cout<<"Z >> "<<x<<endl;
#define pstr(x) printf("%s\n",x);

using namespace std;
using ll = long long;
using vi = vector <int>;
using mpii = map<int,int>;
using mpll = map<ll,ll>;
using si = set<int>;
using sll = set<ll>;
using sll = set<ll>;
using vll= vector<ll>;

#define INF 1000000000
#define LINF 4000000000000000000
#define pi  (2*acos(0))
#define Mod 1000000007

 int main(){
  int n;
  sci(n);
  int left = n%1000;
  if(left==0) {
    printf("0\n");
    return 0;
  }
  int ans = 1000-left;
  pfi(ans);





    return 0;
}







Measured memory_bytes: 3788
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner scanner = new Scanner(System.in);
        String S = scanner.next();
        int count = 0;
        int max = 0;
        
        for(int i=0; i<S.length(); i++){
            if(S.charAt(i)=='A'||S.charAt(i)=='G'||S.charAt(i)=='C'||S.charAt(i)=='T'){
                count++;
                if(max<=count){
                   max = count; 
                }
            }else{
                count = 0;
            }
        }
        
        System.out.println(max);
    }
}


Measured memory_bytes: 21844
package main
import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
)

func GCD(a, b int) int {
  if a < b { a, b = b, a }
  if b == 0 { return a }
  return GCD(b, a % b)
}

func KMP(S, P string) []int {
  M := len(P)
  PMT := make([]int, M + 1)
  PMT[0] = -1
  for i, j := 2, 0; i <= M; {
    if P[i - 1] == P[j] {
      PMT[i] = j + 1
      i++
      j++
    } else if 0 < j {
      j = PMT[j]
    } else {
      i++
    }
  }
  K := make([]int, 0)
  for i, j := 0, 0; i + j < len(S); {
    if S[i + j] == P[j] {
      j++
      if j == M {
        K = append(K, i)
        i += M - PMT[M]
        j = PMT[j]
      }
    } else {
      i += j - PMT[j]
      if 0 < j { j = PMT[j] }
    }
  }
  return K
}

func Solve() {
  s := NextLine()
  t := NextLine()
  S, T := len(s), len(t)
  ss := s + s
  for len(ss) < 2 * T { ss += ss }
  K := KMP(ss, t)
  next := make([]int, S)
  for i := range next { next[i]-- }
  for _, k := range K {
    next[k % S] = (k + T) % S
  }
  A := make([]int, S)
  var pre int
  for i, v := range next {
    for v >= 0 {
      if v == i { A[i] = S + 1; break }
      A[i]++
      if A[v] > 0 { A[i] += A[v]; break}
      pre = v
      v = next[v]
      next[pre] = -1
    }
  }
  ans := MaxInt(A...)
  if ans > S { ans = -1 }
  Write(ans)
}

func main() {
  Solve()
  Output()
}

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt(A ...*int) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.Atoi(L[i])
  }
}
func NextIntVec(A *[]int) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]int, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.Atoi(l)
  }
}
func NextFloat(A ...*float64) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.ParseFloat(L[i], 64)
  }
}
func NextFloatVec(A *[]float64) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]float64, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.ParseFloat(l, 64)
  }
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func WriteIntVec(A []int) {
  S := make([]string, len(A))
  for i, a := range A {
    S[i] = strconv.Itoa(a)
  }
  Write(strings.Join(S, " "))
}
func Output() {
  _ = writer.Flush()
}
func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}
func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}
func SumInt(A ...int) int {
  sum := 0
  for _, a := range A {
    sum += a
  }
  return sum
}
func AbsInt(x int) int {
  if x < 0 { x = -x }
  return x
}

Measured memory_bytes: 59776
import sys
def input(): return sys.stdin.readline().strip()

i  = lambda: int(input())
s  = lambda: input()

str_m = {}
for _ in range(i()):
  S = ''.join(sorted(s()))
  if S in str_m:
    str_m[S] += 1
  else:
    str_m[S] = 1

count = 0
for n in str_m.values():
  count += n * (n-1) // 2

print(count)

Measured memory_bytes: 17848
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
static const ll MAX = 1000000000000000;
static const int NIL = -1;
using namespace std;
const long double EPS = 0.0000000001;
const long double PI = (acos(-1));

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")


long double cal(long double a, long double b, long double theta){
    if(theta > PI/2.0 - EPS){
        return 0.0;
    }

    long double ret;
    if(a*tan(theta) >= b){
        return b*b/tan(theta)*a/2.0;
    }else{
        return a*a*b - a*a*a*tan(theta)/2.0;
    }
}

int main() {

    ll a,b,x; cin >> a >> b >> x;

    long double ok = PI/2.0;
    long double ng = 0.0;
    rep(i,100000){
        long double mid = (ok + ng)/2.0;
        if(cal(a,b,mid) < x) ok = mid;
        else ng = mid;
    }
    cout << fixed << setprecision(10) << ok/PI*180 << endl;
    return 0;
}


Measured memory_bytes: 4044
#include <iostream>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	int a,b,c;
	cin>>a>>b>>c;
	if (a+b+c>=22)
	{
		cout<<"bust";
	}
	else
	{
		cout<<"win";
	}
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int i;
  int a[3]={1,0,0},swap;
  char s[4];
  while(scanf("%s",s)!=-1){
    swap=a[s[0]-'A'];
    a[s[0]-'A']=a[s[2]-'A'];
    a[s[2]-'A']=swap;
  }
  for(i=0;i<3;i++){
    if(a[i])
      printf("%c\n",'A'+i);
  }
  return 0;
}

Measured memory_bytes: 0
n=gets.to_i
 
s=10000000000000
a=[]
 flag=0
(1..n**0.5).each do |m|
    if n%m==0
        v=n.div(m)
        if (v-1)+(m-1)<s
            s=(v-1)+(m-1)
       flag=1
        end
        
    end
    next
end
 
if flag==0
p n-1
else
p s
end

Measured memory_bytes: 3836
#include<stdio.h>

int main(void){
    while(1){
        int n;
        scanf("%d",&n);
        if(n == 0)
            break;

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

        int sum = 0,min = 100000,max = -1;
        for(int i = 0;i < n;i++){
            if(min > p[i])
                min = p[i];
            if(max < p[i])
                max = p[i];

            sum += p[i];
        }
        sum -= min + max;

        printf("%d\n",sum / (n - 2));
    }
    return 0;
}

Measured memory_bytes: 2580
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String s = scanner.nextLine();
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') result++;
        }

        System.out.println(result);

    }
}

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

int main(){
    int n;
    cin >> n;
    int k = 111;
    for(int i = 1; i < 10; i++){
        if(k >= n){
            cout << k << endl;
            return 0;
        }
        k += 111;
    }
}

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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const llint INF = 1<<21;
// static const llint MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

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

    int f, b;
    for(int is=0;is<s.size();is++) {
        if(s.at(is)=='A') {
            f = is;
            break;
        }
    }
    for(int is=s.size()-1;is>=1;is--) {
        if(s.at(is)=='Z') {
            b = is;
            break;
        }
    }

    cout << b - f + 1 << endl;
    return 0;
}


Measured memory_bytes: 3708
#include <iostream>
#include <iomanip>
typedef long long ll;
using namespace std;
const  ll INF = 1e9;
const  ll MOD = 1e9 + 7;
#define repi(i,n,init) for(ll i=init;i<(n);i++)

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

Measured memory_bytes: 256