akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

queue<pii> nextNode;
string s;
int H, W; ll ans; char grid[22][22];
bool visited[22][22]; ll dis[22][22];
int moves[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> H >> W;
    for (int i = 1; i <= H; i++) {
        cin >> s;
        for (int j = 1; j <=W ; j++) {
            grid[i][j] = s[j-1]=='#';
        }
    }
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if(grid[i][j]) continue;
            for(int k = 1; k<= H; k++)for(int l = 1; l<=W; l++)visited[k][l] = false;
            nextNode.push({i, j}); visited[i][j] = true;
            dis[i][j] = 0;
            while(!nextNode.empty()){
                pii cur = nextNode.front(); nextNode.pop();
                for (int k = 0; k < 4; k++) {
                    pii newmove = {cur.first+moves[k][0], cur.second+moves[k][1]};
                    if(newmove.first<1 || newmove.second <1 || newmove.first>H || newmove.second>W) continue;
                    if(visited[newmove.first][newmove.second] || grid[newmove.first][newmove.second]) continue;
                    nextNode.push(newmove);
                    visited[newmove.first][newmove.second] = true;
                    dis[newmove.first][newmove.second] = dis[cur.first][cur.second]+1;
                    ans = max(ans, dis[newmove.first][newmove.second]);
                }
            }
        }
    }
    cout << ans <<'\n';
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;
//const int mod = 998244353;

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

bool in(int y, int x) { return 0 <= y && y < h && 0 <= x && x < w; }

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

    while (1)
    {
        cin >> w >> h;
        if (w == 0 && h == 0)
            break;
        vector<string> s(h);
        rep(i, h) cin >> s[i];
        queue<P> que;
        int vis[30][30] = {};
        rep(i, h) rep(j, w) if (s[i][j] == '@')
        {
            que.push({i, j});
            vis[i][j] = 1;
        }
        int ans = 1;
        while (!que.empty())
        {
            P p = que.front();
            que.pop();
            int y = p.first, x = p.second;
            rep(i, 4)
            {
                int ny = y + dy[i], nx = x + dx[i];
                if (!in(ny, nx) || vis[ny][nx] || s[ny][nx] == '#')
                    continue;
                vis[ny][nx] = 1;
                ans++;
                que.push({ny, nx});
            }
        }
        cout << ans << endl;
    }
}



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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 2e5+50;
const int M = 1e6;
const ll oo = 1e18;
const int mod = 1e9+7;

ll dp[404][404],a,pre[404];

ll sum(int l,int r){
	ll res = pre[r];
	if(l)res -= pre[l-1];
	return res;
}

int main(){
	for(int i=0;i<404;i++)for(int j=0;j<404;j++)dp[i][j] = 1e18;
	int n;
	cin>>n;
	ll s = 0;
	for(int i=0;i<n;i++){
		cin>>a;
		pre[i] = a;
		if(i)pre[i] += pre[i-1];
		for(int l = i;l>=0;l--){
			if(i == l){
				dp[l][i] = 0;
			}else{
				for(int r=l;r<i;r++){
					dp[l][i] = min(dp[l][i],dp[l][r] + dp[r+1][i] + sum(l,i));
				}
			}
		}
	}
	cout << dp[0][n-1] << endl;
}

Measured memory_bytes: 1536
import java.util.Scanner;

public class Main
{
	
	public static void main(String... args)
	{
		Scanner scan = new Scanner(System.in);
		int f = scan.nextInt();
		long tmp = 1;
		for(int i = 1; i <= f; i++)
		{
			tmp *= i;
		}
		System.out.println(tmp);
	}

}

Measured memory_bytes: 17148
#include<cstdio>
#include<algorithm>
int n,K,Q,flag[200100],val[200100],A[200100],b[200100],ans=0x3f3f3f3f;
using std::sort;
struct node{
	int val,id;
	bool operator<(node b)const{
		return val<b.val;
	}
}a[200100];
int main(){
	scanf("%d%d%d",&n,&K,&Q);
	for(int i=1;i<=n;i++)
		scanf("%d",&val[i]),a[i].val=val[i],a[i].id=i;
	sort(a+1,a+n+1);
	flag[0]=flag[n+1]=1;
	for(int i=1;i<=n-Q+1;i++){
		flag[a[i-1].id]=1;
		int cnt=0;
		for(int j=1,sum=0;j<=n+1;j++)
			if(!flag[j])A[++sum]=val[j];
			else{
				if(sum==0)continue;
				sort(A+1,A+sum+1);
				for(int k=1;k<=sum-K+1;k++)
					b[++cnt]=A[k];
				sum=0;
			}
		if(cnt<Q)break;
		sort(b+1,b+cnt+1);
		ans=std::min(ans,b[Q]-b[1]);
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 3288
q = int(input())
ans = ''
alphabet = 'zabcdefghijklmnopqrstuvwxy'
while True:
    r = q%26
    q = q//26 - 1 if r==0 else q//26
    ans = ans + alphabet[r]
    if q<=0:
        break
ans = ans[::-1]
print(ans)

Measured memory_bytes: 9164
#include<bits/stdc++.h>
#define mins(a,b) a=min(a,b)
#define maxs(a,b) a=max(a,b)
template < typename T > std::string to_string( const T& n )
  {
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
  }
using namespace std;

const long long INF=9000000000000000;
int main(){
  int a,b,t;
  cin>>a>>b>>t;
  cout<<(t/a)*b<<endl;
}


Measured memory_bytes: 764
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)

struct INIT{
    INIT(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);
        cout << fixed << setprecision(13);
    }
}INIT;

LL a, b;

int main(){
    cin >> a >> b;
    LL g = gcd(a, b);
    set<int> st;
    st.insert(1);
    LL cur = 2;
    LL lim = sqrt(g);
    if(lim * lim < g)lim++;
    while(g > 1 && cur <= lim){
        if(g % cur == 0){
            st.insert(cur);
            while(g % cur == 0)g /= cur;
        }
        cur++;
    }
    st.insert(g);
    cout << (int)st.size() << endl;
}

Measured memory_bytes: 384
N,M,X=map(int,input().split()) #AtCoder Beginner Contest 167(C問題)
import numpy as np
Q=[]
list1 = [list(map(int,input().split())) for i in range(N)]
for i in range(1,2**len(list1)):
    list2 = []
    for j in range(len(list1)):
        if (i >> j) &1 == 1:
            list2.append(list1[j])
    Q.append(list2) #5~10行目でビット全探索を行い、変数Qに本の買い方の組合せを格納する。
R=[]

for q in range(0,len(Q)):
    Q[q]=np.array(Q[q])
    r=np.sum(Q[q], axis=0)
    R.append(r)
R=np.array(R) #10行目で得た組合せについて、本の値段とアルゴリズムの理解度の和をそれぞれ取り、行列にする。
S=R[:,1:] #アルゴリズムの理解度のみの行列を作る。
T=[]
for g in range(0,len(S)):
    if all(i >= X for i in S[g]): #Sのなかでアルゴリズムの理解度がすべてX以上の行のみ取り出す。
        T.append(R[g])
    else:
        T=T
if len(T)>0:
    T=np.array(T)
    T=T[T[:,0].argsort(), :] #本の値段の合計が安い順にする。
    print(T[0][0])
else:
    print(-1)
#AtCoder Beginner Contest 167(C問題) 以上

Measured memory_bytes: 32040
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    char X, Y; cin >> X >> Y;
    cout << (X < Y ? '<' : X > Y ? '>' : '=') << endl;

    return 0;
}


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

using namespace std;

int W, H;
int col, cnt;
char M[50][50];
bool used[50][50];

#define BLACK (1)
#define WHITE (2)

int in(int x, int y) {
  return 0 <= x && x < W && 0 <= y && y < H;
}

void dfs(int x, int y) {
  // 周りが一つの色かフィールド外だけで構成されると領域にカウント
  if(M[y][x] != '.') return;
  used[y][x] = true;
  cnt ++;
  
  const int dx[] = {-1, 1, 0, 0};
  const int dy[] = {0, 0, -1, 1};
  
  for(int i=0; i<4; i++) {
    int nx = x + dx[i], ny = y + dy[i];
    if(in(nx, ny) && !used[ny][nx]) {
      if(M[ny][nx] == 'B') col |= BLACK;
      if(M[ny][nx] == 'W') col |= WHITE;
      if(M[ny][nx] == '.') dfs(nx, ny);
    }
  }
}

int main() {
  
  while(cin >> W >> H && W) {
    for(int i=0; i<H; i++)
      for(int j=0; j<W; j++)
	cin >> M[i][j];
    
    fill(used[0], used[0]+2500, false);
    
    int res[4] = {};
    for(int i=0; i<H; i++)
      for(int j=0; j<W; j++)
	if(!used[i][j]) {
	  col = cnt = 0;
	  dfs(j, i);
	  res[col] += cnt;
	}
    
    cout << res[BLACK] << " " << res[WHITE] << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1316
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<bitset>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=100000+100;
const db pi=acos(-1.0);
#define lowbit(x) ((x)&(-x))
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

inline ll readll()
{
    ll x=0;int f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

int n;
bitset<4004000> f;

int main()
{
    f[0]=1;int s=0;
    n=read();
    rep(i,1,n)
    {
        int x=read();
        f|=(f<<x);s+=x;
    }
    rep(i,(s+1)>>1,s)
    {
        if (f[i]) {printf("%d",i);break;}
    }
    return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i = 0; i < (n); ++i )
#define rep_rev(n,i) for(ll i = n; i >= 0; --i )
using namespace std;
typedef pair<int, int> P;
const long long INF = 1LL << 60;
int dx[2] = {0,1}, dy[2] = {1,0};
ll N,ans;
int main(){
  cin >> N;
  ans = N-1;
  //a*b=Nの被乗算数bの最大はaなのでループは高々sqrt(N)回
  for(int i = 1; i <= sqrt(N); ++i){
      if(N%i == 0 && ans > i+N/i-2) ans = i + N/i-2;
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

#define REP(i, x, n) for(ll i=x; i<(ll)n; ++i)
#define rep(i, x) REP(i, 0, x)
#define all(v) v.begin(), v.end()

int main(){
    ll N;
    cin >> N;
    vll a(N);
    rep(i, N){
        cin >> a[i];
    }
    sort(all(a));
    ll r = N;
    rep(i, N){
        if(a[i]>=0){
            r = i;
            break;
        }
    }
    vector<pair<ll, ll>> s;
    ll c = a[N-1];
    r = max(r, 1ll);
    if(r>=N-1){
        REP(i, 0, N-1){
            s.push_back({c, a[i]});
            c = c - a[i];
        }
    }
    else{
        REP(i, r, N-1){
            s.push_back({a[0], a[i]});
            c = a[0] - a[i];
            a[0] = c;
        }
        c = a[N-1];
        rep(i, r){
            s.push_back({c, a[i]});
            c -= a[i];
        }
    }
    cout << c << endl;
    rep(i, N-1){
        cout << s[i].first << " " << s[i].second << endl;
    }
}


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

int main() {
    int n,m;
    cin >> n >> m;
    if(abs(n-m)>1) {
        cout << 0 << endl;
        return 0;
    }

    ll p=1000000007;
    ll ans=1;
    for(int i = 1; i <= n; i++) {
        ans *= i;
        ans %= p;
    }
    for(int i = 1; i <= m; i++) {
        ans*=i;
        ans %=p;
    }
    if(n==m) {
        ans *= 2;
        ans %= p;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3604
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  string s;
  long long n;
  cin>>n;
  while(n>0){
    n-=1;
    s+=n%26+'a';
    n/=26;
  }
  reverse(s.begin(),s.end());
  cout<<s;
}

Measured memory_bytes: 3132
import bisect
a, b, c, x = map(int, [input() for i in range(4)])
clist = [50*i for i in range(c+1)]
ans = 0
for i in range(a+1):
  for j in range(b+1):
    y = x-i*500-j*100
    insert_index = bisect.bisect_left(clist, y)
    if  insert_index < len(clist):
      if y == clist[insert_index]:
        ans += 1
print(ans)

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

int main(){
	double r;
	while(cin >> r , r != 0.0){
		double pi = M_PI;

		for(int i = 1 ;  ; i++){
			for(int k = -1 ; k < 2 ; k+=2){
				for(int j = 0 ; j < 2 ; j++){
					int nu = (int)( (pi+r*k) * i) + j;
					if(abs(nu - pi*i) <= r*i){
						cout << nu << "/" << i << endl;
						goto exit;
					}
				}
			}
		}
		exit:;
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;
typedef long long ll;
typedef vector<ll> vi;
 
vi solve(ll a,ll b,ll c) {
  double D=b*b-4*a*c;
  if (D < 0) return vi();
  ll rD=sqrt(D+0.1);
  if (rD*rD!=D) return vi();
  ll p=2*a, r=2*a;
  ll q=b+rD, s=b-rD;
  ll gpq = __gcd(p,abs(q)), grs = __gcd(r,abs(s));
  p/=gpq;
  q/=gpq;
  r/=grs;
  s/=grs;
 
  if (p<r || (p==r&&q<s)){
    swap(p,r);
    swap(q,s);
  }
  return vi{p,q,r,s};
}
 
int main() {
  ll a,b,c;
  while (cin >> a >> b >> c && a) {
    vi v=solve(a,b,c);
    if (v.size())
      for(int i=0;i<4;i++)cout<<v[i]<<(i==3?'\n':' ');
    else cout << "Impossible" << endl;
  }
}

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

#define pb push_back
#define fst first
#define snd second
#define ALL(s) s.begin(),s.end()
#define fill(a,c) memset(&a, c, sizeof(a))
#define fore(i,x,y) for(ll i=x;i<y;i++)
#define SZ(x) ((int)(x).size())
#define PI 3.1415926535897932384626433832795
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef long long ll;
using namespace std;

const int MAXN = 2e5 + 5;
vector<int> g[MAXN], h[MAXN];
vector<int> vis(MAXN,0), vis2(MAXN,0), p1(MAXN), p2(MAXN);

void dfs1(int u,int st){
    vis[u] = 1;
    p1[u] = st;
    for(auto e: g[u]){
        if(vis[e]) continue;
        dfs1(e,st);
    }
}

void dfs2(int u,int st){
    vis2[u] = 1;
    p2[u] = st;
    for(auto e: h[u]){
        if(vis2[e]) continue;
        dfs2(e,st);
    }
}

int main() {FIN;
    int n,k,l; cin>>n>>k>>l;
    set<pair<int,int>> st;
    fore(i,0,k){
        int u,v; cin>>u>>v; u--; v--;
        g[u].pb(v); g[v].pb(u);
    }
    fore(i,0,l){
        int u,v; cin>>u>>v; u--; v--;
        h[u].pb(v); h[v].pb(u);
    }

    fore(i,0,n){
        if(!vis[i]){
            dfs1(i,i);
        }
    }

    fore(i,0,n){
        if(!vis2[i]){
            dfs2(i,i);
        }
    }

    map<pair<int,int>,int> ns;
    fore(i,0,n){
        int u = p1[i];
        int v = p2[i];
        ns[{u,v}]++;
    }

    fore(i,0,n){
        int u = p1[i];
        int v = p2[i];
        cout<<ns[{u,v}]<<" ";
    }
    return 0;
}




Measured memory_bytes: 29568
four_w = []
seven_w = []
cross = []

for i in range(1,101):
    if i % 4 == 0:
        four_w.append(i)
    elif i % 7 ==0:
        seven_w.append(i)

for four in four_w:
    for seven in seven_w:
        cross.append(four + seven)

n = int(input())

if n in cross:
    print("Yes")
elif n in seven_w:
    print("Yes")
elif n in four_w:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();

        System.out.println(Math.min(a, b) + Math.min(c, d));
    }

}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
 
int H,W,N;
int M;
int to[500*500];
 
int id[500*500];
 
vector<vint>loop;
 
void findLoop(){
    vector<int>deg(H*W);
    queue<int>que;
    fill_n(id,500*500,-2);
    rep(i,M)deg[to[i]]++;
    rep(i,M)if(deg[i]==0)que.push(i),id[i]=-1;
    while(que.size()){
        int v=que.front();
        que.pop();
        int u=to[v];
        if(--deg[u]==0){
            id[u]=-1;
            que.push(u);
        }
    }
 
    rep(i,M){
        if(id[i]!=-2)continue;
        loop.pb(vint());
        int v=i;
        while(id[v]==-2){
            id[v]=loop.size()-1;
            loop.back().pb(v);
            v=to[v];
        }
    }
}
 
vint T[500*500];
int ans;
 
int dep[500*500];
set<int>ds[500*500];
bool ex[500*500];
void dfs(int v,int d){
    dep[v]=d;
    if(ex[v])ds[v].insert(d);
    for(auto u:T[v]){
        dfs(u,d+1);
        if(ds[v].size()<ds[u].size())swap(ds[v],ds[u]);
        for(auto it=ds[u].begin();it!=ds[u].end();it++){
            if(ds[v].find(*it)!=ds[v].end()){
                chmin(ans,*it-d);
            }
            ds[v].insert(*it);
        }
    }
}
 
bool C(int t){
    for(auto &vs:loop){
        vint cnt(vs.size());
        rep(i,vs.size()){
            for(auto u:ds[vs[i]]){
                if(u>t)continue;
                cnt[(i+t-u)%vs.size()]++;
            }
        }
        rep(i,vs.size())if(cnt[i]>1)return true;
    }
    return false;
}
 
signed main(){
    scanf("%lld%lld%lld",&H,&W,&N);
    M=H*W;
    rep(i,H){
        rep(j,W){
            int a,b;
            scanf("%lld%lld",&a,&b);
            to[i*W+j]=a*W+b;
        }
    }
    vint vs;
    rep(i,N){
        int a,b;
        scanf("%lld%lld",&a,&b);
        vs.pb(a*W+b);
        ex[a*W+b]=1;
    }
 
    findLoop();
 
    rep(i,M){
        if(id[i]!=-1)continue;
        T[to[i]].pb(i);
    }
 
    ans=INT_MAX;
 
    rep(i,M){
        if(id[i]==-1)continue;
        dfs(i,0);
    }
 
    int lb=0,ub=INT_MAX;
    while(ub-lb>1){
        int mid=(ub+lb)/2;
        if(C(mid))ub=mid;
        else lb=mid;
    }
 
    chmin(ans,ub);
    if(ans==INT_MAX)cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 54632
import numpy as np


n, m = map(int,input().split())
a = np.array([list(input()) for i in range(n)])
b = np.array([list(input()) for i in range(m)])
flug = 0

for i in range(n-m+1):
    for j in range(n-m+1):
        if np.all(a[i:i+m, j:j+m] == b):
            flug =1

ans = 'Yes' if flug else 'No'
print(ans)

Measured memory_bytes: 12428
package main

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

var graph [][]edge
var colors []int
var n int

func main() {
	n = nextInt()
	graph = make([][]edge, n+1)
	colors = make([]int, n)
	c := 0
	graph[0] = []edge{edge{node: 1, index: 0}}

	for i := 1; i < n; i++ {
		a := nextInt()
		b := nextInt()
		ea := edge{node: b, index: i}
		eb := edge{node: a, index: i}
		graph[a] = append(graph[a], ea)
		graph[b] = append(graph[b], eb)

		c = max(c, len(graph[a]))
		c = max(c, len(graph[b]))
	}

	// 適当に塗っていく
	colors[0] = 0
	dfs(0, 0)

	fmt.Println(c)
	for i := 1; i < n; i++ {
		fmt.Println(colors[i])
	}
}

type edge struct {
	node  int
	index int
}

func dfs(prev, curr int) {
	var prevColor int
	nextColor := 1
	nexts := graph[curr]

	for i := 0; i < len(nexts); i++ {
		next := nexts[i]
		if next.node == prev {
			prevColor = colors[next.index]
			break
		}
	}

	for i := 0; i < len(nexts); i++ {
		next := nexts[i]
		if next.node == prev {
			continue
		}
		if nextColor == prevColor {
			nextColor++
		}

		colors[next.index] = nextColor
		dfs(curr, next.node)
		nextColor++
	}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}


Measured memory_bytes: 21120
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define PI 3.141592653589793238
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
typedef complex<double> com;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }


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

	int n, k;
	cin >> n >> k;
	n %= k;
	cout << min(n, k - n) << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <valarray>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// namespace
using namespace std;
// type
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using PAIR = pair<int, int>;
using PAIRLL = pair<ll, ll>;
// input
#define INIT              ({ ios::sync_with_stdio(false); cin.tie(0); })
#define VAR(type, ...)    type __VA_ARGS__; var_scan(__VA_ARGS__);
template<typename T>
static void var_scan(T& t)
{
    cin >> t;
}
template<typename T, typename... R>
static void var_scan(T& t, R&... rest)
{
    cin >> t;
    var_scan(rest...);
}
// output
#define OUT(var)          cout << (var)
#define SPC               cout << ' '
#define TAB               cout << '\t'
#define BR                cout << '\n'
#define ENDL              cout << endl
#define FLUSH             cout << flush
// debug
#ifdef DEBUG
#define EPRINTF(fmt, ...) fprintf(stderr, fmt, __VA_ARGS__)
#define DUMP(var)         cerr << #var << '\t' << (var) << '\n'
#define DUMPITERABLE(i) do {                            \
        cerr << #i << '\t';                             \
        for (const auto& it : i) { cerr << it << ' '; } \
        cerr << '\n';                                   \
} while (0)
#define DUMPITERABLE2(i2) do {                          \
        cerr << #i2 << '\t';                            \
        for (const auto& it : i2) {                     \
            for (const auto& it2: it) {                 \
                cerr << it2 << ' ';                     \
            }                                           \
        }                                               \
        cerr << '\n';                                   \
} while (0)
#else
#define EPRINTF(fmt, ...)
#define DUMP(var)
#define DUMPITERABLE(i)
#define DUMPITERABLE2(i)
#endif
// util
// [l, r)
#define REP(i, n)       for (int i = 0; i < (n); i++)
#define RREP(i, n)      for (int i = (n)-1; i >= 0; i--)
#define FOR(i, l, r)    for (int i = (l); i < (r); i++)
#define RFOR(i, r, l)   for (int i = (r)-1; i >= (l); i--)
#define REPLL(i, n)     for (ll i = 0; i < (n); i++)
#define RREPLL(i, n)    for (ll i = (n)-1; i >= 0; i--)
#define FORLL(i, l, r)  for (ll i = (l); i < (r); i++)
#define RFORLL(i, r, l) for (ll i = (r)-1; i >= (l); i--)

static int s;
static int dp[2000+1];

static int solve(int s)
{
    if (s < 3)
        return 0;
    if (dp[s])
        return dp[s];
    int count = 1;
    FOR(i, 3, (s-3)+1) {
        count += solve(s-i);
        count %= 1000000007;
    }
    return dp[s] = count;
}

int main(void)
{
    INIT;
    cin >> s;
    OUT(solve(s));
    ENDL;
    return 0;
}


Measured memory_bytes: 3648
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

const int MAXN=1e5+10;
int a[MAXN];

int main()
{
	int n;
	scanf("%d",&n);
	int sum=n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
/*	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			if (a[i]==a[j])
				sum-=2;
		}
	}*/
	sort(a+1,a+1+n);
	for(int i=n;i>=2;i--){
		if (a[i]==a[i-1]){
			sum-=2;
			i--;
		}
	}
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 640
#define _GLIBCXX_DEBUG
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <map>
using namespace std;
typedef long long ll;
#define ALL(v) (v).begin(), (v).end()
#define SIZE 100001
const int mod = 1e9+7;
const int inf = 1e9;

ll inv[SIZE], fac[SIZE], finv[SIZE];

void comInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE; i++) {
        inv[i] = mod - inv[mod%i] * (mod/i) % mod;
        fac[i] = fac[i-1] * (ll)i % mod;
        finv[i] = finv[i-1] * inv[i] % mod;
    }
}

ll com(int a, int b) {
    if (a < b) return 0;
    return fac[a] * (finv[b] * finv[a-b] % mod) % mod;
}

int main() {
    comInit();
	int N, M;
	cin >> N >> M;
	if (abs(N-M) > 1) {
		cout << 0 << endl;
		return 0;
	}

	ll ans = 1;
	ll bigger = max(N, M);
	ll smaller = min(N, M);
	ans *= fac[bigger];
	ans %= mod;
	if (bigger == smaller) {
		ans *= fac[smaller];
		ans %= mod;
		ans *= 2;
		ans %= mod;
	} else {
		ans *= fac[smaller];
		ans %= mod;
	}
	
	cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

ll modpow(ll a, ll b){
    if(b == 0) return 1;
    else if(b % 2 == 0){
        ll d = modpow(a, b/2) % MOD;
        return (d * d) % MOD;
    }
    else{
        return (a * modpow(a, b-1)) % MOD;
    }
}

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

    int n; cin>>n;
    vector<ll> x(n);
    for(int i=0; i<n; i++) cin>>x[i];

    ll base = 1;
    for(int i=1; i<n; i++){
        base *= i;
        base %= MOD;
    }

    ll ans = 0;
    ll cur = base;
    for(int i=0; i+1<n; i++){
        ll dist = x[i+1] - x[i];
        ans += dist * cur;
        ans %= MOD;
        cur += base * modpow(i + 2, MOD - 2);
        cur %= MOD;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<60;
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; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;
typedef priority_queue<int, vector<int>, greater<int>> PQ;
const int MOD = 1000000007;

int N;
ll K;
vector<int> A, F;


bool isOK(ll mid){
    ll count = 0;
    rep(i,N){
        count += max(0ll, A[i] - mid/F[i]);
    }
    if(K >= count){
        return true;
    }
    else{
        return false;
    }
}

ll binary_search(){
    ll ng = -1;
    ll ok = 1e12;
    while(abs(ok-ng)>1){
        ll mid = (ok+ng) / 2;
        ll count = 0;
        if (isOK(mid)) ok = mid;
        else ng = mid;
    }
    return ok;
}

int main(){
    /*
    int N;
    ll K;
    */
    cin >> N >> K;
    
    //vector<int> A(N), F(N);
    A.assign(N,0), F.assign(N,0);
    rep(i,N) cin >> A[i];
    rep(i,N) cin >> F[i];

    sort(A.begin(), A.end());
    sort(F.rbegin(), F.rend());
    /*
    ll ng = -1;
    ll ok = 1e12;
    while(abs(ok-ng)>1){
        ll mid = (ok+ng) / 2;
        ll count = 0;
        rep(i,N){
            count += max(0ll, A[i] - mid/F[i]);
        }
        if(K >= count){
            ok = mid;
        }
        else{
            ng = mid;
        }
    }
    */
    ll ok = binary_search();
    cout << ok << endl;
}

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

using namespace std;

const int maxn=103;
const int maxw=1e5+5;

long long dp[maxw];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, w;
	cin >> n >> w;
	long long w1, l1;
	for(int i=0; i<n; i++){
		cin >> w1 >> l1;
		for(int j=w; j>=w1; j--){
			dp[j]=max(dp[j], dp[j-w1]+l1);
		}
	}
	cout << dp[w] << '\n';
	return 0;
}

Measured memory_bytes: 1024
import math
import fractions

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

A, B = [int(x) for x in input().split()]

max_gcd = fractions.gcd(A,B)
list_n = factorization(max_gcd)
if list_n == [[1,1]]:
    print(len(list_n))
else:
    print(len(list_n) + 1)

Measured memory_bytes: 5048
#include <bits/stdc++.h>
using namespace std;
using ll=long long;using ull=unsigned ll;
using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;
using P=pair<int,int>;using PL=pair<ll,ll>;
const int INF=1<<30,MOD=1000000007;const ll LINF=1ll<<60;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...) _overload3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n) for(int i=n-1;i>=0;--i)
#define REPARR(i,v) for(int i=0;i<v.size();++i)
#define all(v) (v).begin(),(v).end()
#define uniq(v) sort(all(v));v.erase(unique(all(v)),v.end())
#define bit(n) (1ll<<(n))
template<class T>bool chmax(T&a,const T&b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,const T&b){if(a>b){a=b;return 1;}return 0;}
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define yes(n) cout<<((n)?"yes":"no")<<endl
#define poss(n) cout<<((n)?"":"im")<<"possible"<<endl
#define Poss(n) cout<<((n)?"P":"Imp")<<"ossible"<<endl
template<typename T>ostream&operator<<(ostream&o,const vector<T>&v){for(T i:v)o<<i<<' ';return o;}
template<typename T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<typename T>ostream&operator<<(ostream&o,const set<T>&v){for(T i:v)o<<i<<' ';return o;}
template<typename T,typename U>ostream&operator<<(ostream&o,const pair<T,U>&v){o<<v.first<<' '<<v.second;return o;}

int main(){
    int n;
    cin>>n;
    vi h(n);
    cin>>h;
    int c=0;
    while(true){
        //cerr<<h<<endl;
        int m=*max_element(all(h));
        //cerr<<m<<endl;
        if(m==0)break;
        REP(i,n){
            if(h[i]==m){
                while(i<n && h[i]==m)h[i++]--;
                i--;
                c++;
            }
        }
    }
    cout<<c<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

// I ¨ 1, V ¨ 5, X ¨ 10, L ¨ 50, C ¨ 100, D ¨ 500, M ¨ 1000

int main(void)
{
	char roma[100];
	int ans, i;
	
	while (scanf("%s", roma) != EOF){
		i = strlen(roma);
		ans = 0;
		
		while (-1 <= i){
			if ((roma[i] == 'V') && (roma [i - 1] == 'I')){
				ans += 4;
				i -= 2;
			}
			if (roma[i] == 'I'){
				ans += 1;
			}
			if (roma[i] == 'V'){
				ans += 5;
			}
			if ((roma[i] == 'X') && (roma [i - 1] == 'I')){
				ans += 9;
				i -= 2;
			}
			if (roma[i] == 'X'){
				ans += 10;
			}
			if ((roma[i] == 'L') && (roma [i - 1] == 'X')){
				ans += 40;
				i -= 2;
			}
			if (roma[i] == 'L'){
				ans += 50;
			}
			if ((roma[i] == 'C') && (roma [i - 1] == 'X')){
				ans += 90;
				i -= 2;
			}
			if (roma[i] == 'C'){
				ans += 100;
			}
			if ((roma[i] == 'D') && (roma [i - 1] == 'C')){
				ans += 400;
				i -= 2;
			}
			if (roma[i] == 'D'){
				ans += 500;
			}
			if ((roma[i] == 'M') && (roma [i - 1] == 'C')){
				ans += 900;
				i -= 2;
			}
			if (roma[i] == 'M'){
				ans += 1000;
			}
			i--;
		}
		printf("%d\n", ans);
	}
	
	return (0);
}

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

int main()
{
    int n,k;
    std::cin>>n>>k;
    std::vector<int> v(n);
    for(int i=0;i<n;i++)std::cin>>v[i];
    int res = 1000000000;
    for(int i=0;i<n-k+1;i++){
        int l = v[i];
        int r = v[i+k-1];
        if((l<=0&&r<=0) || (l>=0&&r>=0))res = std::min(res,std::max(std::abs(r),std::abs(l)));
        else res = std::min(res,r - l + std::min(std::abs(l),std::abs(r) ) );
    }
    std::cout<<res<<std::endl;
}

Measured memory_bytes: 640
#include<stdio.h>

int element[20];
int size;

bool check(int nowPos, int val) {
  if(val == 0) {
    return true;
  }
  if(val < 0) {
    return false;
  }
  if(nowPos > size) {
    return false;
  }
  return check(nowPos + 1, val - element[nowPos]) || check(nowPos + 1, val);
}
int main(void) {
  int n, m, target;
  scanf("%d", &n);
  size = n;
  for(int i = 0; i < n; i++) {
    scanf("%d", &element[i]);
  }
  scanf("%d", &m);
  for(int i = 0; i < m; i++) {
    scanf("%d", &target);
    if(check(0, target)){
      printf("yes\n");
    }
    else {
      printf("no\n");
    }
  }
  return 0;
}

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

int main(){
  int H, W;
  cin >> H >> W;

  int c[10][10];
  for(int i = 0; i < 10; i++){
    for(int j = 0; j < 10; j++){
      cin >> c[i][j];
    }
  }

  for(int k = 0; k < 10; k++){
    for(int i = 0; i < 10; i++){
      for(int j = 0; j < 10; j++){
        c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
      }
    }
  }

  long long ans = 0;
  for(int h = 0; h < H; h++){
    for(int w = 0; w < W; w++){
      int a;
      cin >> a;
      if(a != -1){
        ans += c[a][1];
      }
    }
  }
  cout << ans << endl;
          
}


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



/*int main() {
    ll n;
    cin>>n;
    vector<ll> vec(n);
    rep(i,n){
        cin>>vec.at(i);
    }
    ll q;
    cin>>q;
    ll b,c;
    rep(i,q){
        cin>>b>>c;
        ll sum=0;
        rep(k,n){
            if(vec.at(k)==b){
                sum+=c;
                vec.at(k)=c;
            }else{
                sum+=vec.at(k);
            }
        }
        cout<<sum<<endl;


    }

}*/
//8乗9乗が限界らしい
//アイデアとして、
int main() {
    ll n;
    cin>>n;
    map<ll,ll> map;
    ll msum=0;
    rep(i,n){
        int a;
        cin>>a;
        map[a]+=1;
        msum+=a;
    }
    ll q;
    cin>>q;
    rep(i,q){
        ll b,c;
        cin>>b>>c;
        msum=msum-b*map[b]+c*map[b];
        cout<<msum<<endl;
        map[c]=map[c]+map[b];
        map[b]=0;
       
    }
    

}

Measured memory_bytes: 9512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(int i = (int)a; i <= (int)b; i++)
#define DEC(i, a, b) for(int i = (int)a; i >= (int)b; i--)
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<pi, pi> pipi;
#define f first
#define s second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<pii> vpii;
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define disc(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
#define INF (int) 1e9 + 100
#define LLINF (ll) 1e18
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
int n;
int main() {
	fastio; cin >> n;
  cout << (n+999)/1000 * 1000 - n;
}


Measured memory_bytes: 3648
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <cstdio>
#define INF 1000000000
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=(ll)a.size()-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef long double ld;
using namespace std;
 
int main(){
  string s;
  cin >> s;
  bool f = true;
  FOR(i, 1, s.size()){
    if(s[i] != '9') f = false;
  }
  if(f){
    cout << (9*(s.size()-1)) + (s[0] - '0') << endl;
  }
  else if(s.size() != 1){
    cout << (9*(s.size()-1)) + (s[0] - '1') << endl;
  }
  else cout << s << endl;
 	return 0;
}


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

#define pb push_back
#define all(a) begin(a), end(a)
#define deb(x) cout << #x << " = " << x << endl
#define debu(x, y) cout << "( " << #x << ", " << #y << " ) = ( " << x << ", " << y << " )" << endl
//#define int long long
typedef long long ll;
ll mod=1000000007;

template <typename T> vector<T> readVector(int n) { vector<T> res(n); for (int i = 0 ; i < n ; i++) cin >> res[i]; return res; }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt = 1;
    //cin >> tt;
    while(tt--) {
        int d, t, s;
        cin >> d >> t >> s;
        if(d/s < t) {
            cout << "Yes\n";
        } else if(d/s == t && d%s == 0) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <math.h>


typedef long long ll;
using namespace std;

int main()
{
  int a, b;

  cin >> a >> b;

  if(a+b==15) cout << "+" << endl;
  else if(a*b==15) cout << "*" << endl;
  else cout << "x" << endl;
  
  
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace Contest
{
    class Scanner
    {
        private string[] line = new string[0];
        private int index = 0;
        public string Next()
        {
            if (line.Length <= index)
            {
                line = Console.ReadLine().Split(' ');
                index = 0;
            }
            var res = line[index];
            index++;
            return res;
        }
        public int NextInt()
        {
            return int.Parse(Next());
        }
        public long NextLong()
        {
            return long.Parse(Next());
        }
        public string[] Array()
        {
            line = Console.ReadLine().Split(' ');
            index = line.Length;
            return line;
        }
        public int[] IntArray()
        {
            var array = Array();
            var result = new int[array.Length];
            for (int i = 0; i < array.Length; i++)
            {
                result[i] = int.Parse(array[i]);
            }

            return result;
        }
        public long[] LongArray()
        {
            var array = Array();
            var result = new long[array.Length];
            for (int i = 0; i < array.Length; i++)
            {
                result[i] = long.Parse(array[i]);
            }

            return result;
        }
    }

    class Program
    {
        private int S;
        private void Scan()
        {
            Scanner sc = new Scanner();
            S = sc.NextInt();
        }
        public void Solve()
        {
            Scan();
            var hs = new HashSet<int>();
            hs.Add(S);
            for (int i = 2; ; i++)
            {
                if (S % 2 == 0)
                {
                    S /= 2;
                }
                else
                {
                    S = S * 3 + 1;
                }
                if (!hs.Add(S))
                {
                    Console.WriteLine(i);
                    return;
                }
            }


        }

        static void Main(string[] args) => new Program().Solve();
    }
}


Measured memory_bytes: 13396
def main():
        N = int(input())
        A = list(map(int, input().split()))
        ans = 1

        if 0 in A:
                ans = 0
        else:
                for i in range(N):
                        ans = ans*A[i]
                        if ans>10**18:
                                ans = -1
                                break

        return ans


if __name__=="__main__":
        ans = main()
        print(ans)

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

int main()
{
	int n;                     //変数宣言
	cin >> n;                  //持ってるカードの枚数入力

	bool Card[4][13];             //配列宣言
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 13; j++) {
			Card[i][j] = false;   //入力したマークと数字のカードを除外する
		}
	}

	for (int i = 0; i < n; i++) {
		char c;                //マークの変数宣言
		int m;                 //数字の変数宣言
		cin >> c >> m;

		if (c == 'S') {
			Card[0][m - 1] = true; //マークがCの時
		}
		else if (c == 'H') {
			Card[1][m - 1] = true;
		}
		else if (c == 'C') {
			Card[2][m - 1] = true;
		}
		else if (c == 'D') {
			Card[3][m - 1] = true;
		}
	}

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 13; j++) {
			if (!Card[i][j]) {
				if (i == 0) {
					cout << "S ";   //除外されなかったカードのうちマークを定義
				}
				else if (i == 1) {
					cout << "H ";
				}
				else if (i == 2) {
					cout << "C ";
				}
				else if (i == 3) {
					cout << "D ";
				}

				cout << j + 1 << endl;  //数字を表示
			}
		}
	}

	return 0;
}


Measured memory_bytes: 3008
#%%
import copy, math, collections

n = int(input())
a = input().split()

result = []

num_dict = dict(collections.Counter(a))

def calc(x):
    if x >= 2:
        return math.factorial(x) / (math.factorial(x - 2) * 2)
    else:
        return 0

result_dict = {}
result_minus1_dict = {}

for key, value in num_dict.items():
    result_dict[key] = calc(num_dict[key])
    result_minus1_dict[key] = calc(num_dict[key] - 1)

result_all = sum(result_dict.values())

for i in range(len(a)):
    print(int(result_all - result_dict[a[i]] + result_minus1_dict[a[i]]))

# %%


Measured memory_bytes: 124360
#include <stdio.h>

int main(void)
{
	int a, b, i;

	scanf("%d %d", &a, &b);

	if (a >= b) {
		for (i = 0; i < a; i++) {
			printf("%d", b);
		}
		printf("\n");
	}
	else {
		for (i = 0; i < b; i++) {
			printf("%d", a);
		}
		printf("\n");
	}

	return 0;
}

Measured memory_bytes: 128
/*
 * main.cpp
 *
 *  Created on: 2014/03/16
 *      Author: uchiya
 */
#include <iostream>
//#include <string>
//#include <iomanip>

using namespace std;
//#define

int main() {
	int n;
	int tou,kai,heya,ninzu;
	int tatemono[4][3][10]={0};

	cin >> n;
	for(int i=0;i<n;i++){
		cin >> tou >> kai >> heya >> ninzu;
		tatemono[tou-1][kai-1][heya-1] += ninzu;
	}

	for(int i=0;i<4;i++){
		if(i>0) cout << "####################\n";
		for(int j=0;j<3;j++){
			for(int k=0;k<10;k++){
				cout << " " << tatemono[i][j][k];
			}
			cout << "\n";
		}
	}
	return 0;
}

Measured memory_bytes: 1164
//============================================================================
// Name        : abc135B.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<list>
#include<set>
#include<map>

using namespace std;

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

	int count = 0;
	for(int i = N - 1; 0 <= i; --i){
		for(int j = 0; j < i; ++j){
			if(A[i] < A[j]){
				swap(A[i], A[j]);
				++count;
			}
			if(1 < count){
				cout << "NO" << endl;
				return 0;
			}
		}
	}

	cout << "YES" << endl;

	return 0;
}


Measured memory_bytes: 256
def janken(a,b):
  if a==b:
    return 0
  elif a=="g" and b=="p":
    return 1
  else:
    return -1
s=0
S=list(input())
for i in range(len(S)):
  if i%2==0:
    k="g"
    s+=janken(S[i],k)
  else:
    k="p"
    s+=janken(S[i],k)
print(s)

Measured memory_bytes: 72384