akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <unistd.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
 
long long int INF = 1e18;
const ll fact_table = 5000000;
double Pi = 3.1415926535897932384626;
 
vector<ll> G[550010];
//vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←
 
 
#define p(x) cout<<x<<"\n";
#define el cout<<"\n";
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
 
 
ll mod = 998244353;
//ll mod = 1000000007;
 
ll rui(ll number1,ll number2){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
 
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
 
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
 
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}
 
/*
ll fact[fact_table + 5],rfact[fact_table + 5];
 
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = rui(fact[fact_table],mod - 2);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}
*/
 
ll n,m,num,sum,a,b,c,d,e,g,h,w,i,j,q,r,l;
ll k,ans;
ll x[500005],y[500005],z[500005];
char s[500005];

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

    cin >> n;
    for(int i=0;i<n;i++){
        cin >> x[i];
    }
    for(int i=0;i<n;i++){
        x[i+1] += x[i];
    }
    ll ans = INF;
    for(int i=0;i<n-1;i++){
        ll res1 = x[i];
        ll res2 = x[n-1] - x[i];
        ans = min(ans, abs(res1 - res2));
    }
    p(ans);


    return 0;
}


















Measured memory_bytes: 17280
"""

https://atcoder.jp/contests/agc035/tasks/agc035_d

毎回1枚カードが減り、寄与が2倍になる
両端のカードは消せない → 寄与は1倍のまま

端から2枚目のカードしか選ばなくていいみたいなの無いかな？
端から2枚目を選ぶと、1つは端の寄与になり、もう一つは動の寄与になる
つまり、動の寄与の総和は変化しない
そうでないのを選ぶと、動の寄与に2倍かかる

→ 2**18 になっていい感じのオーダーにはなる

検証：
5枚で真ん中を最初に選ぶべきなのを作れるか？
0,X,Y,Z,0
0,X+Y,Y+Z,0
0,X+2Y+Z,Y+Z
X+2Y+Z,X+3Y+2Z
→2X+3Y+3Z or 3X+3Y+2Z (真ん中を選んだ場合)

0,X,Y,Z,0
X,X+Y,Z,0 → X,X+Y+Z,Z → 2X+Y+Z,X+Y+2Z → 3X+2Y+3Z
2X+Y,X+Y+Z,0 → 3X+2Y+Z,X+Y+Z → 4X+3Y+2Z

すなわち、真ん中を選んだ方がいい場合もある…
最後まで残した数は2倍だけの寄与で済む
最後まで残す数を決め打ちする？
最後の数で左右を分ける
→さらにその区間で最後に残すやつは3倍の寄与で済む

1 4 3 5 2 5 3 4 1
→こんな感じ

あとは分割統治で、
ある点で区切った場合の左右の最小を足して上に返せばよい
計算量は？
長さ1の場合1
2の場合 1+1 = 2
3の場合 2+1+1+2 = 6
4の場合 6+

dp[0] = 0
dp[1] = 1
dp[n] = 2*(dp[n-1]+dp[n-2]…+dp[0])
dp[16] = 9565938 なので十分可能

"""

from sys import stdin

def want(l,r,lb,rb):
    if l > r:
        return 0
    elif l == r:
        return A[l] * (lb+rb)
    
    nmin = float("inf")
    for i in range(l,r+1):
        nmin = min(nmin , A[i]*(lb+rb) + want(l,i-1,lb,lb+rb) + want(i+1,r,lb+rb,rb) )
    return nmin
    

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))

print (A[0] + A[-1] + want(1,N-2,1,1) )


Measured memory_bytes: 98532
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF= 1LL << 60;
#define REP(i,n) for(ll i=0; i<n; i++)
#define FOR(i,a,n) for(ll i=a; i<n; i++)
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int m;
    cin >> m;
    cout << 48-m << endl;
}

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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intll int long long
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main() {
  int n ;
  cin >> n ;
  vector<int> v(n);
  rep(i,n) 
    cin >> v.at(i) ;
  
  sort(all(v)) ;
  
  int ans1 = v.at(n-1);
  int ans2 = INF;
  int key = 0;
  rep(i,n-1){
    if(abs(v.at(i) - (ans1+1)/2) < ans2 ) {
      key = i ;
      ans2 = min(abs(v.at(i) - (ans1+1)/2),ans2);
    }
  }
  
  cout << ans1 << " " <<v.at(key);
  


}


Measured memory_bytes: 640
N, A, B = map(int, input().split())
S = input()

for i in range(len(S)):
    if S[i] == 'a' and A+B >= 1:
        print("Yes")
        if A >= 1:
            A -= 1
        else:
            B -= 1
    elif S[i] == 'b' and B >= 1:
        print("Yes")
        B -= 1
    else:
        print("No")

Measured memory_bytes: 4016
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(12);
    ll K;
    cin >> K;
    if(K%7==0)K /= 7;
    ll asd = 1;
    ll bef = 1;
    ll count = 1;
    if(K % 2 == 0||K % 5== 0){
        count = -1;
    }else{
        while(1){
            if(asd%K == 0)break;
            count++;
            bef = bef*10%K;
            asd += bef;
        }
    }
    cout << count << "\n";
}

Measured memory_bytes: 3644
#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <set>

using namespace std;
const int N = 100;
const int INF = 100000000;
typedef pair<int, int> P;

class State{
public:
  int x, y, cost;
  State(int y, int x, int cost) : y(y), x(x), cost(cost) {}
};

int w, h, s, t;
int dist[11][N][N];
int dy[2][6] = {{-1, -1, 0, 1, 1, 0},{-1, -1, 0, 1, 1, 0}};
int dx[2][6] = {{-1, 0, 1, 0, -1, -1},{0, 1, 1, 1, 0, -1}};
vector<P> cs;

void bfs(int sy, int sx, int p){
  for(int i=0;i<h;i++) for(int j=0;j<w;j++) dist[p][i][j] = INF;
  queue<State> que;
  que.push(State(sy, sx, 0));
  dist[p][sy][sx] = 0;
  while(!que.empty()){
    State u = que.front(); que.pop();
    for(int i=0;i<6;i++){
      int ny = u.y + dy[u.y%2][i];
      int nx = u.x + dx[u.y%2][i];
      if(ny<0 || ny>=h) continue;
      if(nx<0 || nx>=w) continue;
      if(dist[p][ny][nx] != INF) continue;
      dist[p][ny][nx] = u.cost+1;
      que.push(State(ny, nx, u.cost+1));
    }
   }
}

int solve(){
  int res = 0;
  bfs(cs[s].first, cs[s].second, s);
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      bool f = false;
      int valm = INF, col;
      for(int k=0;k<=s;k++){
        if(valm > dist[k][i][j]){
          f = false;
          valm = dist[k][i][j];
          col = k;
        }else if(valm == dist[k][i][j]) f = true;
      }
      if(!f && col == s) res++;
    }
  }
  return res;
}

main(){
  while(cin >> w >> h && (w|h)){
    cs.clear();
    int x, y;
    cin >> s;
    for(int i=0;i<s;i++){
      cin >> x >> y;
      cs.push_back(P(y-1, x-1));
    }
    for(int i=0;i<cs.size();i++) bfs(cs[i].first, cs[i].second, i);
    int ans = 0;
    cin >> t;
    for(int i=0;i<t;i++){
      cin >> x >> y;
      cs.push_back(P(y-1, x-1));
      ans = max(ans, solve());
      cs.pop_back();
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) *b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};


///////////////////////////


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

	vector<ll> a(3*N + 1);

	repn(i, 3 * N) { cin >> a[i]; }

	sort(++a.begin(), a.end());

	ll ans = 0;

	repn(i, N) {
		ans += a[N + 2 * i - 1];
	}

	cout << ans;

	system("PAUSE");

}





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

#define LEN 100005

typedef struct pp {
    char name[100];
    int t;
} P;

P Q[LEN];
int head, tail, n;

void enqueue(P x){
    Q[tail] = x;
    tail = (tail + 1) % LEN;
}

P dequeue(){
    P x = Q[head];
    head = (head + 1) % LEN;
    return x;
}

int min(int a, int b){
    return a < b ? a : b;
}

int main(){
    int elaps = 0, c;
    int i, q;
    P u;
    
    scanf("%d%d", &n, &q);

    for(i=1; i<=n; i++){
        scanf("%s", Q[i].name);
        scanf("%d", &Q[i].t);
    }

    head = 1;
    tail = n + 1;

    while( head != tail ){
        u = dequeue();
        c = min(q, u.t);
        u.t -= c;
        elaps += c;
        if( u.t > 0 ) enqueue(u);
        else {
            printf("%s %d\n", u.name, elaps);
        }
    }

    return 0;
}



Measured memory_bytes: 11912
#include<bits/stdc++.h>
typedef  long long int ll;
typedef long double ld;
#define pb  push_back
#define vll vector<ll>
#define mll map<ll,ll>
// Maths
const double PI = 2*acos(0.0);
#define gcd(a,b)   __gcd((a),(b))
#define lcm(a,b)   ((a)/(__gcd((a),(b)))*(b))
#define log(x,b)   (log(x)/log(b))
#define INF         LLONG_MAX
#define ln  INT_MAX
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
int main(){
ll n;
cin>>n;
ll a[n],x,c=0;

for(int i=0; i<n; i++){
    cin>>a[i];
}
x=a[0];
for(int i=1; i<=n; i++){
if(x>a[i]){ c++;}
x=min(x,a[i]);
}
cout<<c+1<<endl;

return 0;

}


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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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; }

const ll INF = 1e9+10;
const ll MOD = 1e9+7;
const ll LINF = 1e18;




signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  char c; cin>>c;
  if(c<='Z') cout<<"A"<<endl;
  else cout<<"a"<<endl;
}

Measured memory_bytes: 3624
#include <stdio.h>
int main()
{   long long a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(a%2==1||b%2==1||c%2==1){
        printf("0");
        return 0;
    }
    long long ha=a/2,hb=b/2,hc=c/2;
    long long ans=1;
    while(ha%2==hb%2&&hb%2==hc%2&&ha%2==hc%2){
        a=hb+hc;
        b=ha+hc;
        c=ha+hb;
        ha=a/2;
        hb=b/2;
        hc=c/2;
        ans++;
        if(ans>10000000){
            printf("-1");
            return 0;
        }
    }
    printf("%ld",ans);

    return 0;
}


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

int main() {
    int n; cin >> n; int cnt = 0; int arr[n]; for (int i = 0; i < n; i ++) cin >> arr[i];
    sort(arr, arr + n);
    for (int i = 0; i < n; i ++) {
        for (int j = i+1; j < n; j ++) {
            for (int k = j+1; k < n; k ++) {
                if (arr[i] == arr[j] || arr[i] == arr[j] || arr[j] == arr[k])continue;
                if (arr[i] + arr[j] > arr[k]) cnt++;
            }
        }
    } cout << cnt << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long double LD; 
typedef long long ll; 
#define int ll 
#define ff(i,a,b) for (int i = a; i < b; i++) 
#define bf(i,a,b) for (int i = a; i >= b; i--) 
#define all(v) v.begin(),v.end() 
#define show(a) for(auto xyz:a)cout<<xyz<<" ";cout<<endl;
#define F first 
#define S second
#define lb lower_bound   
#define ub upper_bound
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define one cout<<-1<<endl;
#define pi 3.141592653589793238
#define mod 1000000007
int ans=0;
void solve(){
    int x,k,d;
    cin>>x>>k>>d;
    x=abs(x);
    if(x>0){
        if(k>x/d){
            if((k-x/d)%2==0)
            ans=abs(x-x/d*d);
            else
            ans=abs(x-(x/d+1)*d);
        }
        else{
            ans=abs(x-k*d);
        }
    }
    else{
        if(k%2==0)
        ans=0;
        else
        ans=d;
    }
    cout<<ans;
}
signed main() {
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}


Measured memory_bytes: 3648
import bisect
from decimal import Decimal
N, *A = open(0).read().split()
N = int(N)
c = [[0, 0] for _ in range(N)]
for i, a in enumerate(A):
    if '.' in a:
        p, q = a.split('.')
        q += '0' * (9 - len(q))
    else:
        p = a
        q = '0' * 9
    a = int(p + q)
    while True:
        if a % 2:
            break
        c[i][0] += 1
        a //= 2
    while True:
        if a % 5:
            break
        c[i][1] += 1
        a //= 5
c.sort()

#cum[i][j]:c[x][1]>=i (j<=x)となるようなxの個数
cum = [[0] * (N + 1) for _ in range(19)]
for i in range(19):
    for j in range(N - 1, -1, -1):
        cum[i][j] = cum[i][j + 1]
        if c[j][1] >= i:
            cum[i][j] += 1
ans = 0
for i, c2c5 in enumerate(c):
    c2, c5 = c2c5
    if c2 > 9 or (c2 == 9 and c5 >= 9):
        i2 = i + 1
    else:
        i2 = bisect.bisect_left(c, [18 - c2, -1])
    ans += cum[18 - c5][i2]
print(ans)


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

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

    vector<int> sunuke(N);

    for(int i = 0; i < K; i++) {
        int d, s;
        cin >> d;
        for(int j = 0; j < d; j++) {
            cin >> s;
            s--;
            sunuke.at(s)++;
        }
    }

    int ans = 0;
    for(int i = 0; i < N; i++) {
        if(sunuke.at(i) == 0) {
            ans++;
        }
    }

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

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
struct ss
{
	string s;
	int num;
}e[100001];
int main()
{
	int m,n;
	int sum=1;
	bool flag;
	string s1;
	cin>>m;
	cin>>s1;
	e[1].s=s1;
	e[1].num=1;
	for(int i=2;i<=m;i++)
	{
		cin>>s1;
		int flag=0;
		for(int j=1;j<=sum;j++)
		{
			if(e[j].s==s1)
			{
			e[j].num++;
			flag=1;
		    } 	    
		}
		if(!flag)
		{
			e[++sum].s=s1;
			e[sum].num=1;
		}
	}
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s1;
		for(int j=1;j<=sum;j++)
		{
			if(s1==e[j].s)
			e[j].num--;
		}
	}
	int maxx=0;
	for(int i=1;i<=sum;i++)
	{
		if(e[i].num>maxx)
		maxx=e[i].num;
	}
    if(maxx>=0)
    cout<<maxx;
    else
    cout<<0;
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define R(i,n)for(int i=0;i<=n;++i)
using namespace std;
int k,s,res=0;
int main(){
  cin>>k>>s;
  R(x,k)R(y,k)if(0<=s-(x+y) && k>=s-(x+y))++res;
  cout<<res<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<vector>
#include<array>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

int main(){
    int N;cin>>N;
    mat c(10,vec(10,0));
    for(int i=1;i<=N;i++){
        int j=i;
        int a,b;
        a=j%10;
        while(j>=10){
            j/=10;
        }
        b=j;
        c[b][a]++;
    }
    int ans=0;
    for(int i=1;i<10;i++){
        ans+=c[i][i]*c[i][i];
        for(int j=i+1;j<10;j++){
            ans+=2*c[i][j]*c[j][i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
  int a;
  scanf("%d",&a);
  int b[a];
  for(int z=0;z<a;z++){
    scanf("%d",&b[z]);
  }
  int ans=0;
  int ans2=0;
  int p=0;
  ans=b[0];
  for(int ac=0;ac<a;ac++){
    for(int c=0;c<a;c++){
      if(ans<b[c]){
        ans=b[c];
        p=c;
      }
    }
    b[p]=-1;
    if(ac%2!=1){ans2+=ans;
    }else {ans2-=ans;}
    ans=0;
  }
  printf("%d\n",ans2);
  return 0;
}

Measured memory_bytes: 128
$A = gets.chomp.chars
$B = gets.chomp.chars
$C = gets.chomp.chars

def game(player, player_hand)
  return player if player_hand.empty?
  case player_hand.shift
  when "a" then
    game("A", $A)
  when "b" then
    game("B", $B)
  when "c" then
    game("C", $C)
  end
end

puts game("A", $A)

Measured memory_bytes: 14408
const fs = require('fs');

function main(input) {
  var arr = input.split('\n');
  var n = parseInt(arr[0], 10);
  var d = arr.slice(1, -1).map(n => parseInt(n, 10));
  d.sort((a, b) => b - a);

  var cur = Infinity;
  var cnt = 0;
  for (var i = 0; i < n; i++) {
    (d[i] < cur) ? cnt++ : null;
    cur = d[i];
  }
  console.log(cnt);
}

input = fs.readFileSync('/dev/stdin', 'utf8');
main(input);

Measured memory_bytes: 21192
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define pi 3.14159265359
#define all(i) i.begin(),i.end()
using namespace std;
const long long INF=1e9+7;
const string alp="abcdefghijklmnopqrstuvwxyz"; //26
const string ALP="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;


int main() {
  ll N;
  cin>>N;
  ll ans=N;
  bool j=true,ju;
  while(j){
    ju=true;
    for(int i=2;i*i<=ans;i++){
      if(ans%i==0){
        ju=false;
      }
    }
    if(ju){
      j=false;
    }
    else{
      ans++;
    }
  }
  cout<<ans<<endl;
}


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

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

  int ans = -1;
  for (int m = 0; m < pow(2, D); m++) {
    int num = 0, score = 0, rest_max = -1;
    for (int i = 0; i < D; i++) {
      if (m >> i & 1) {
        score += 100 * (i+1) * P[i] + C[i];
        num += P[i];
      } else {
        rest_max = i;
      }
    }
    if (score < G) {
      int needed = (G - score + ((rest_max + 1) * 100) - 1) / ((rest_max + 1) * 100);
      if (P[rest_max] <= needed) {
        continue;
      }
      num += needed;
    }
    if (ans == -1) {
      ans = num;
    } else {
      ans = min(ans, num);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
using namespace std;
int n,m,a[100];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		if(i!=a[i])
			m++;
	if(m<=2)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
}

Measured memory_bytes: 256
fun intList() = readLine()?.split(" ")?.map(String::toInt) ?: TODO()
fun main(args: Array<String>) {
    val (a, b) = intList()
    val s = readLine() ?: return
    when {
        s.take(a).contains("-")
                || s[a] != '-'
                || s.takeLast(b).contains("-")
        -> {
            println("No")
        }
        else -> {
            println("Yes")
        }
    }
}


Measured memory_bytes: 37892
///*
#include<stdio.h>
#include<stdlib.h>

#include<iostream>
using namespace std;

typedef struct gbhome {
	int cost;
	int time;
}gbh;

int main() {

	int n, time;
	int i, j;
	gbh *poi, smallest;

	cin >> n;
	cin >> time;
	//scanf_s("%d", &n);

	poi = new gbh[n];
	//poi = (gbh*)malloc(sizeof(gbh)*n);

	for (i = 0; i < n; i++) {
		cin >> poi[i].cost >> poi[i].time;
		//scanf("%d %d", &poi[i].cost, &poi[i].time);
	}

	
	for (i = 0; i < n; i++) {
		for (j = 0; j < n - 1; j++) {
			if (poi[j].time > poi[j + 1].time) {
				gbh fake = poi[j];
				poi[j] = poi[j + 1];
				poi[j + 1] = fake;
			}
		}
	}
	

	smallest = poi[0];

	for (i = 0; i < n; i++) {
		
		if (poi[0].time > time) {
			cout << "TLE";
			return 0;
		}

		if (poi[i].time > time) {
			break;
		}
		else if (smallest.cost > poi[i].cost) {
			smallest = poi[i];
		}

	}

	cout << smallest.cost;

	return 0;

}
//*/

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e16;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<vector<int>> grid(3,vector<int>(3));
    rep(i,3) rep(j,3) cin >> grid[i][j];
    bool ok = 1;
    rep(i,1,3){
        int a = grid[i][0]-grid[i-1][0];
        rep(j,1,3){
            if (a != grid[i][j]-grid[i-1][j]) ok = 0;
        }
    }
    Yes(ok);
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  int i, j, k;
  while(1){
  int n, x, c=0;
  scanf("\n%d %d", &n, &x);
  if(n == 0 && x == 0){return 0;}
  else {
    for (i=1; i<=n; i++){
      for (j=i+1; j<=n; j++){
	for (k=j+1; k<=n; k++){
	  if(i+j+k==x){c=c+1;break;}
	}
      }
    }
  }
  printf("%d\n", c);
  }
}

Measured memory_bytes: 600
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

ll ans = 0;
int N,M,Q;
struct query{
	int a;
	int b;
	int dis;
	int score;
};
vector<query> que(60);

void dfs(vector<int> a){
	int siz = a.size();
	if(siz==N){
		ll e_ans = 0;
		rep(i,Q){
			if(a[que[i].b]-a[que[i].a] == que[i].dis){
				e_ans += que[i].score;
			}
		}
		ans = max(ans, e_ans);
		return ;
	}
	for(int i = a[siz-1]; i<=M; ++i){
		vector<int> b = a;
		b.push_back(i);
		dfs(b);
	}
	return ;
}

int main(){
	cin>>N>>M>>Q;
	rep(i,Q){
		cin>>que[i].a; --que[i].a;
		cin>>que[i].b; --que[i].b;
		cin>>que[i].dis;
		cin>>que[i].score;
	}
	for(int i = 1; i<=M; ++i){
		vector<int> a = {i};
		dfs(a);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>

using namespace std;

int main()
{
  long long a, b, c ,d, s;
  cin >> a >> b >> c >> d;
  s = max(a*c, max(a*d, max(b*c, b*d)));
  cout << s << endl;
  return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

void Main(){
    int n, k;
    cin >> n >> k;
  set<int> st;
  rep(i,k){
    int d;
    cin >> d;
  	rep(k,d){
    	int s;
      	cin >> s;
      	st.insert(s);
    }
  }
    cout << n - st.size() << endl;
	return;
}

int main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(long long i=s;i<n;i++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
const double pi = acos(-1.0);
const ll mod = pow(10,9) + 7;
const ll INF = pow(2,31) - 1;

ll gcd(ll x,ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

ll lcm(ll x,ll y)
{
    x /= gcd(x,y);
    y /= gcd(x,y);
    return (x*y);
}

int main()
{
    ll n,m;
    cin >> n >> m;

    if(m == 0){
        if(n == 1){
            cout << 0 << endl;
            return 0;
        } 


        rep(i,n){
            if(i == 0)cout << 1;
            else cout << 0;
        }cout << endl;
        return 0;
    }

    if(n == 1){
        ll ans = -1;
        rep(i,m){
            ll s,c;
            cin >> s >> c;
            if(ans == -1)ans = c;
            else if(c != ans){
                cout << -1 << endl;
                return 0;
            }
        }
        cout << ans << endl;
        return 0;
    }


    vll d(n,-1);
    rep(i,m){
        ll s,c;
        cin >> s >> c;
        s--;
        if(s == 0 && c == 0){
            cout << -1 << endl;
            return 0;
        }

        if(d[s] == -1)d[s] = c;
        else if(d[s] != -1 && d[s] != c){
            cout << -1 << endl;
            return 0;
        }
    }

    rep(i,n){
        if(d[i] == -1)cout << ((i == 0)?1:0);
        else cout << d[i];
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long int
#define vi vector<int>
#define vvll vector<ll>
#define vll(a) vector<ll> a(MAXN)
#define pb push_back
#define fo(a) for(auto&a1:(a))
#define fd(a,b) for(int i=(a);i>=(b);i--)
#define fk(a,b) for(int k=(a);k<(b);k++)
#define fj(a,b) for(int j=(a);j<(b);j++)
#define f(a,b) for(ll i=(a);i<(b);i++)
#define forni(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define fdk(a,b) for(int k=(a);k>=(b);k--)
#define fdj(a,b) for(int j=(a);j>=(b);j--)
#define ri(n) scanf("%d",&(n));
#define rll(n) scanf("%lld",&(n));
#define T(t) int t;scanf("%d",&(t));while((t)--)
#define MAXN2 10000005
#define pll pair<ll,ll>
#define PI 3.14159265
#define mset(a) memset((a),0,sizeof((a)))
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);
#define sortv(a) sort(a.begin(),a.end())
#define v2d vector<vvll>
#define v3d vector<v2d>
#define max_value(a,b) a=max(a,b)
#define min_value(a,b) a=min(a,b)
using namespace std;
const ll MAXN=205;
const ll mod=1e9+7;
vector<ll> tr[MAXN];
bool vis[MAXN];
int main()
{
	ll n,x,t;
	cin>>n>>x>>t;
	cout<<((n+x-1)/x)*t<<"\n";
    return 0;
}


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

int main(){

    string s;

    cin >> s;
    if(s[0] == '1'){
        int flag = 1;
        for(int i=1; i<s.length(); i++){
            if(s[i] != '0'){
                flag = 0;
                break;
            }
        }
        if(flag == 1){
            cout << 10 << endl;
            return 0;
        }
    }

    int res = 0;
    for(int i=0; i<s.length(); i++){
        res += s[i] - '0';
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define pb push_back 
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define INF (1<<30)
#define MOD 1000000007
using ll = long long;
using namespace std;

int main() {
    string s;
    cin >> s;
    cout << s[0] << s.length() - 2 << s[s.length()-1] << endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<set>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f, mod=1000000007;
bool isprime[1000005];
int prime[1000005], cnt=0, ans[1000005];
inline int read()
{
    int x=0,f=1; char ch=getchar();
    for (; ch<'0' || ch>'9'; ch=getchar()) if (ch=='-') f=-1;
    for (; ch>='0' && ch<='9'; ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}

void init(int n)
{
    memset(isprime, true, sizeof(isprime));
    isprime[0]=0; isprime[1]=0;
    for (int i=2; i<=n; i++)
    {
        if (isprime[i])  prime[++cnt]=i;
        for (int j=1; j<=cnt && i*prime[j]<=n; j++)
        {
            isprime[i*prime[j]]=false;
            if (!(i%prime[j])) break;
        }
    }
}

int power(int x, int t)
{
    int res=1;
    while (t)
    {
        if (t&1) res*=x;
        x*=x; t>>=1;
    }
    return res;
}

signed main()
{
    init(1000000); int res=1;
    int n=read(), p=read();
    for (int i=1; i<=cnt; i++)
        {while (p%prime[i]==0) p/=prime[i], ans[i]++;}
    for (int i=1; i<=cnt; i++)
        res*=power(prime[i], ans[i]/n);
    if (n==1 && p>1) res*=p;
    printf("%lld\n",res);
    return 0;
}


Measured memory_bytes: 6656
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,k;
int b[55];
int p[55];
int main(void){
  cin >> n >> k;
  for(int i = 0; i < k; i++){
    int m;
    cin >> m;
    for(int j = 0; j < m; j++){
      int a;
      cin >> a;
      b[a] = i;
      p[a] = 0;
    }
  }
  int r;
  cin >> r;
  for(int i = 0; i < r; i++){
    int x,y;
    cin >> x >> y;
    if(b[x] == b[y]) p[x] = p[y] = 1;
  }
  int res = 0;
  for(int i = 0; i <= n; i++){
    res += p[i];
  }
  cout << res << endl;
}

Measured memory_bytes: 1160
package main

import (
	"fmt"
)

func main() {
	var S, T string
	fmt.Scan(&S, &T)

	var A, B int
	fmt.Scan(&A, &B)

	var U string
	fmt.Scan(&U)

	if S == U {
		fmt.Println(A - 1, B)
	} else {
		fmt.Println(A, B - 1)
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
#define _GLIBCXX_DEBUG
#define ll long long
#define rep(i,n) for (ll i = 0; i < n; i++)
#define vl vector<ll>
#define vpl vector<pair<ll,ll>>
#define vvl vector<vector<ll>> //a(縦行,vector<ll>(横列));
#include<algorithm>//__gcd(a,b)
#include <iostream>
#include <vector>
#include <cstdlib>
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 long long INF = 1LL << 60;

int main(){
    ll n;cin>>n;
    vl a(n);rep(i,n)cin>>a[i];
    ll b=1;

rep(i,n){
if(a[i]==b)b++;
}

if(b==1)cout<<-1<<endl;
else{cout<<n-b+1<<endl;}
}

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

int main(void){
    int a, b, i;
    cin >> a >> b;
    int cnt = 0;
    for(i = a; i <= b; i++){
        if(i/10000 == i%10 && (i-(i/10000)*10000)/1000 == (i%100)/10){
            cnt++;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
from math import factorial

N = int(input())
S = list(input())

MOD = 10 ** 9 + 7

def swap(char):
    if char == 'W':
        return 'B'
    else:
        return 'W'

cnt = 0
for i in range(2 * N):
    if i % 2 == 0:
        S[i] = swap(S[i])
    if S[i] == 'B':
        cnt += 1

if cnt != N or S[0] == 'B' or S[-1] == 'W':
    print(0)
else:
    rest_W = 0
    ans = 1
    for i in range(2 * N):
        if S[i] == 'W':
            rest_W += 1
        if S[i] == 'B':
            ans *= rest_W
            ans %= MOD
            rest_W -= 1
    ans = (ans * factorial(N) % MOD)
    print(ans)


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


Measured memory_bytes: 2100
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

const int B = 40;
ll ct[B][2]={};

int n;
ll k;

ll f(int d){
    return 1LL<<d;
}

ll dp[B][2];
ll dfs(int d, int s){
    if(d==-1) return 0;
    if(dp[d][s]>=0) return dp[d][s];

    ll ret = 0;
    if(s==0){
        if(k>>d&1){
            // 0
            ret = max(ret, dfs(d-1,1)+f(d)*ct[d][1]);
            // 1
            ret = max(ret, dfs(d-1,0)+f(d)*ct[d][0]);
        }
        else{
            // 0
            ret = max(ret, dfs(d-1,0)+f(d)*ct[d][1]);
        }
    }
    else{
        // 0,1
        ret = max(ret, dfs(d-1,1)+f(d)*max(ct[d][0],ct[d][1]));
    }
    return dp[d][s] = ret;
}

int main(){
    cin >>n >>k;

    rep(i,n){
        ll a;
        cin >>a;

        rep(j,40){
            int b = a>>j&1;
            ++ct[j][b];
        }
    }

    memset(dp,-1,sizeof(dp));
    cout << dfs(39,0) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1000000007;
const long double PI=3.14159265358979;


ll dp[101][100001];


int main() {
  ll N,W;
  cin>>N>>W;
  vector<pair<ll,ll>> item(100);
  for(int i=0;i<N;i++){
    cin>>item[i].first>>item[i].second;
  }
  for(int i=0;i<=W;i++){
    dp[0][i]=0;
    for(int j=0;j<N;j++){
      if(item[j].first>i){
        dp[j+1][i]=dp[j][i];
       // cout<<dp[j+1][i]<<" ";
        continue;
      }
      dp[j+1][i]=max(dp[j][i],dp[j][i-(item[j].first)]+item[j].second);
      //cout<<dp[j+1][i]<<" ";
    }
  }
  cout<<dp[N][W];
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "cycle"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 2e3 + 5;

vi g[MAXN];

int used[MAXN];

int dis[MAXN][MAXN];

int anc[MAXN][MAXN], top[MAXN];

void dfs(int s){
	used[s] = 1;
	anc[s][top[s]++] = s;
	REP(i, 0, SZ(g[s])){
		int to = g[s][i];
		if (!used[to]){
			dfs(to);
			REP(j1, 0, top[s]){
				int v1 = anc[s][j1];
				REP(j2, 0, top[to]){
					int v2 = anc[to][j2];
					dis[v1][v2] = dis[v2][v1] = dis[s][v1] + dis[to][v2] + 1;
				}
			}
			REP(j, 0, top[to]){
				int v = anc[to][j];
				anc[s][top[s]++] = v;
			}
		}
	}
}

void solve(){
	int n, k, a, b;
	cin >> n >> k;
	REP(i, 1, n){
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs(1);
	
	/*REPN(i, 1, n){
		REPN(j, 1, n){
			printf("%d ", dis[i][j]);
		}
		putchar('\n');
	}*/
	
	int ans = n;
	if (k & 1){
		REP(s, 1, n){
			REP(i, 0, SZ(g[s])){
				int to = g[s][i];
				int cur = 0;
				REPN(j, 1, n){
					if (dis[s][j] > k / 2 && dis[to][j] > k / 2){
						cur++;
					}
				}
				ans = min(cur, ans);
			}
		}
	} else {
		REPN(i, 1, n){
			int cur = 0;
			REPN(j, 1, n){
				if (dis[i][j] > k / 2){
					cur++;
				}
			}
			ans = min(cur, ans);
		}
	}
	cout << ans << endl;
}	

int main(){

	//freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();	
	}
}

Measured memory_bytes: 28800
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
typedef long long ll;
using namespace std;
const int INF = 1000000007;
int N;
vector<int> G[202];
int color[200];
int L[201];
int d[201][201];

bool dfs(int v, int c){
  color[v] = c;
  rep(i, G[v].size()){
    if(color[G[v][i]]==c) return false;
    if(color[G[v][i]]==0 && !dfs(G[v][i], -c)) return false;
  }
  return true;
}

void warshall_floyd() {
  rep(k, N){
    rep(i, N){
      rep(j, N) d[i][j] =min(d[i][j], d[i][k]+d[k][j]);
    }
  }
}

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

  cin >> N;
  char a;
  rep(i, N){
    rep(j, N){
      cin >> a;
      if (a == '1'){
        G[i].push_back(j);
        d[i][j] = 1;
      } else {
        d[i][j] = INF;
      }
    }
  }

  if (!dfs(0, 1)){
    cout << -1 << endl;
    return 0;
  }

  warshall_floyd();
  int ans = 0;
  rep(i, N){
    rep(j, N) {
      if (i==j) continue;
      ans = max(ans, d[i][j]);
    }
  }

  cout << ans+1 << "\n";
  return 0;
}


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

int main()
{
    string str;
    cin>>str;
    long long int sum=0;
    for(int i=0;i<str.size();i++)
    {
        sum+=str[i]-'0';
    }
    if(sum%9==0)
    cout<<"Yes";
    else
    cout<<"No";
}

Measured memory_bytes: 3712
from collections import deque
s = input()
q = int(input())
result_q = deque(s)
t = False
for _ in range(q):
    List=[i for i in input().split()]
    if List[0] == '1':
        if t:
            t = False
        else:
            t = True
    else:
        if List[1] == '1': # F=1
            if t: # 反転時
                result_q.append(List[2])
            else:
                result_q.appendleft(List[2])
        else:
            if t: # 反転時
                result_q.appendleft(List[2])
            else:
                result_q.append(List[2])
if t:
    result_q.reverse()
for s in list(result_q):
    print(s, end="")


Measured memory_bytes: 96540
#include<stdio.h>

int main(){
    int n, i, j, k, l, m, A[100][100] = {0};
    
    scanf("%d", &n);
    for (i = 0; i < n; i++){
        scanf("%d %d", &k, &m);
        for (j = 0; j < m; j++){
            scanf("%d", &l);
            A[k-1][l-1] = 1;
        }
    }
    
    for(i = 0; i < n; i++){
        for(j = 0; j < n - 1; j++){
            printf("%d ", A[i][j]);
        }
        printf("%d\n", A[i][n-1]);
    }
    
    return 0;
}


Measured memory_bytes: 2144
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define FIR first
#define SEC second
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}

const int mod=998244353;

struct node {
	ll S0,S1;
	int len;
	friend bool operator < (node A,node B) {
		if(A.len!=B.len) return A.len<B.len;
		if(A.S0!=B.S0) return A.S0<B.S0;
		return A.S1<B.S1;
	}
	void encode(int *s,int n) {
		len=n,S0=S1=0;
		for(int i=0;i<min(len,64);++i)
			if(s[i+1]) S0|=1ll<<i;
		for(int i=0;i<len-64;++i)
			if(s[i+64+1]) S1|=1ll<<i;
	}
	void decode(int *s,int &n) {
		n=len;
		for(int i=0;i<min(len,64);++i)
			s[i+1]=S0>>i&1;
		for(int i=0;i<len-64;++i)
			s[i+64+1]=S1>>i&1;
	}
};

map<node,int> f,g;

void dfs(node S) {
	if(f.count(S)) return;
	int s[110],t[110],n;
	S.decode(s,n);
	if(n==1) {
		f[S]=g[S]=s[1]+1;
		return;	
	}
	
	int rf=0,rg=0;
	for(int i=1;i<n;++i) {
		node L,R;
		for(int j=1;j<=i;++j) t[j]=s[j]; L.encode(t,i),dfs(L);
		for(int j=i+1;j<=n;++j) t[j-i]=s[j]; R.encode(t,n-i),dfs(R);
		
		rg=(rg+1ll*f[L]*g[R])%mod;
	}
	
	for(int i=1;i<n;++i) if(n%i==0) {
		for(int j=1;j<=i;++j) t[j]=1;
		
		for(int j=1;j<=n;j+=i)
			for(int k=j;k<j+i;++k)
				t[k-j+1]&=s[k];
		node T; T.encode(t,i),dfs(T);
		rf=(rf+g[T])%mod;
	}
	rg=(rg+rf)%mod;
//	for(int i=1;i<=n;++i) cout<<s[i]; cout<<" -- "<<rf<<' '<<rg<<endl;
	f[S]=rf,g[S]=rg;
}

char str[110];
int s[110];

int main() {
	scanf("%s",str+1);
	int n=strlen(str+1);
	for(int i=1;i<=n;++i) s[i]=str[i]-'0';
	node S; S.encode(s,n),dfs(S);
	printf("%d",g[S]);
	return 0;
}

Measured memory_bytes: 9728
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from itertools import chain
from functools import reduce
from collections import OrderedDict, Counter, deque
import operator

import numpy as np

N, M, C = map(int, input().split())
B = np.array(list(map(int, input().split())))
ans = 0
for _ in range(N):
    A = np.array(list(map(int, input().split())))
    if sum(A * B) + C > 0:
        ans += 1
print(ans)

Measured memory_bytes: 21644
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] arrA = new long[n];
		long[] arrB = new long[n];
		for (int i = 0; i < n; i++) {
			arrA[i] = sc.nextInt();
			arrB[i] = sc.nextInt();
		}
		long count = 0;
		for (int i = n - 1; i >= 0; i--) {
			long mod = (arrA[i] + count) % arrB[i];
			if (mod > 0) {
				count += arrB[i] - mod;
			}
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 87808
package main

import (
  "fmt"
)

func main() {
  var N int
  fmt.Scan(&N)
  if N % 2 == 0 {
    fmt.Println(N / 2, N, N)
  } else if N % 3 == 0 {
    fmt.Println(N / 3, 2 * N, 2 * N)
  } else {
    w := 0
    for h := 1; h <= 3500; h++ {
      for n := 1; n <= 3500; n++ {
        if 4 * h * n - N * (h + n) <= 0 {
          continue
        }
        if N * h * n % (4 * h * n - N * (h + n)) != 0 {
          continue
        }
        w = N * h * n / (4 * h * n - N * (h + n))
        fmt.Println(h, n, w)
        break
      }
      if w != 0 {
        break
      }
    }
  }
}

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

int main(){
	int a,b,c;
	cin >>a >> b >> c;
	if ((a==b && a!=c) || (b==c && a!=c) || (a==c && a!=b))	cout << "Yes";
	else cout << "No";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}



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

  string s; cin >> s;

  ll N = s.size()/2;
  if(s.size() % 2)  N++;
  string atcoder;
  rep(i,s.size()){
    if(i<N) atcoder += "g";
    else atcoder += "p";
  }

  ll ans = 0;
  rep(i,s.size()){
    if(atcoder[i] == 'p' && s[i] == 'g')
      ans++;
    if(atcoder[i] == 'g' && s[i] == 'p')
      ans--;
  }
  cout << ans << endl;
  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector < pair<ll, ll > > vp;
typedef vector <string> vs;
typedef vector <char> vc;
typedef list <ll> lst;

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

#define Endl endl

map<string, string> mp, mpg, mpa;


/*--------------------template--------------------*/


int main() {
    string t;
    vs v;
    cin >> s >> t;
    if (t.size() > s.size()) {
        cout << "UNRESTORABLE" << Endl;
        return 0;
    }
    REP(i, s.size() - t.size()+1) {
        REP(j, t.size()) {
            string a;
            if (j == t.size() - 1) {
                if (s[i + j] == t[j] || s[i + j] == '?') {
                    REP(k, i) {
                        a.push_back(s[k]);
                    }
                    REP(k, t.size()) {
                        a.push_back(t[k]);
                    }
                    FOR(k, i + t.size(), s.size()) {
                        a.push_back(s[k]);
                    }
                    v.push_back(a);
                    a.clear();
                }
            }

            if (s[i+j] == t[j] || s[i+j] == '?') {
                continue;
            } else {
                break;
            }
        }
    }
    if (v.size() == 0) {
        cout << "UNRESTORABLE" << Endl;
    } else {
        sort(ALL(v));
        REP(i, v[0].size()) {
            if (v[0][i] != '?') {
                cout << v[0][i];
            } else {
                cout << 'a';
            }
        }
    }
    
    


}

Measured memory_bytes: 256