akhauriyash/Code-Regression huggingface dataset:
#problems3
n,s=map(int,input().split())
a=1
lists=list(map(int,input().split()))
visited=[False for i in range(n+1)]
data=[]
now=a
flag=True
while flag:
    now=lists[now-1]
    if visited[now]==False:
        visited[now]=True
        data.append(now)
    else:
        data.append(now)
        flag=False


#data=[...(loop)...]
looping=0
for i in range(len(data)):
    if data[i]==data[-1]:
        mod=i
        index=i
        looping=data[i:-1]
        loop=len(data)-1-index
        break

U=(s-mod)%loop
if s<=mod:
    print(data[s-1])
elif s>mod:
    print(looping[U-1])


    


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

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

using ll = long long;

bool isOk(char c){
 if(c=='A') return true;
 if(c=='C') return true;
 if(c=='G') return true;
 if(c=='T') return true;
 return false;
}

int main() {
	string s;
 cin>>s;
 int n = s.size();
 int maxx = 0;
 int now = 0;
 rep(i,n) {
  if(isOk(s[i])) {
   now++;
  } else {
   if(maxx < now) maxx = now;
   now = 0;
  }
 }
 if(maxx < now) maxx = now;
 cout<<maxx<<endl;
	return 0;
}


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

int main(){
    int h,w;
    cin >> h >> w;
    vector<string> ss(h);
    for(int i=0;i<h;i++){
        cin >> ss[i];
    }
    for(int i=1;i<h-1;i++){
        for(int j=1;j<w-1;j++){
            if(ss[i][j]=='#'){
                if(ss[i-1][j]=='.'&&ss[i+1][j]=='.'&&ss[i][j-1]=='.'&&ss[i][j+1]=='.'){
                    // cout << i << " " << j << endl;
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
S = [int(n) for n in input()]
l = len(S)
ans = 0
for i in range(l):
	for j in range(l-i):
		if i+j == l-1:
			t = 1
		else:
			t = 2
		ans += S[i]*10**j*2**(l-j-t)
print(ans)


Measured memory_bytes: 3064
A, B, C, D, E, F = map(int, input().split())

water_set = set()
sugar_set = set()

for a in range(0, F+1, 100*A):
    for b in range(0, F+1, 100*B):
        if a + b <= F:
            water_set.add(a + b)

for c in range(0, F+1, C):
    for d in range(0, F+1, D):
        if c + d <= F//2 + 1:
            sugar_set.add(c + d)

water_set.remove(0)
water_list = list(water_set)
sugar_list = list(sugar_set)

cons = -1
water_ans = 0
sugar_ans = 0
for water in water_list:
    for sugar in sugar_list:
        if water + sugar <= F and sugar * 100 <= E * water:
            if 100 * sugar / (water + sugar) > cons:
                cons = 100 * sugar / (water + sugar)
                water_ans = water
                sugar_ans = sugar

print(water_ans + sugar_ans, sugar_ans)


Measured memory_bytes: 3188
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		long a = scanner.nextInt();
		long b = scanner.nextInt();
		scanner.close();
		
		System.out.println((a / b) + " " + (a % b) + " " + String.format("%.5f", (double) a / b));
	}

}



Measured memory_bytes: 26524
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

int main()
{
  int k,x;
  cin>>k>>x;
  int mn=max(-1000000, x-k+1);
  int mx=min(1000000,x+k-1);
  FOR(i,mn,mx+1) {
    if(i>mn) cout<<' ';
    cout<<i;
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
typedef long long ll;
int a[200010];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    ll ans = 0;
    const int mod = 1e9 + 7;
    for (int i = k; i <= n + 1; i++)
    {
        ans += 1ll * (n + 1 - i)%mod * i % mod + 1;
        ans %= mod;
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i< (n); i++)
using ll = long long;
using P = pair<int, int>;
int main()
{
    int n,x,t;
    cin >> n >> x >> t;
    int ans = 0;
    ans += n/x * t;
    if(n%x >0) ans += t;
    cout << ans << endl;

return 0;
}

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

struct UnionFind {
	vector<int> p;
	UnionFind(int n) : p(n,-1) {}

	int root(int x) {
		if (p.at(x) < 0)
			return x;
		return p.at(x) = root(p.at(x));
	}

	bool issame(int x, int y) {
		return root(x) == root(y);
	}

	bool merge(int x, int y) {
		x = root(x);
		y = root(y);

		if (x == y)
			return 0;

		if(p.at(x) > p.at(y))
			swap(x,y);
		p.at(x) += p.at(y);
		p.at(y) = x;
		return 1;
	}

	int size(int x) {
		return -p.at(root(x));
	}
};


int main() {
	int N,M,K,A,B;
	cin >> N >> M >> K;

	UnionFind uf(N);
	vector<set<int>> fb(N);

	rep(i,M) {
		cin >> A >> B;
		--A, --B;

		uf.merge(A,B);
		fb.at(A).insert(B);
		fb.at(B).insert(A);
	}

	rep(i,K) {
		cin >> A >> B;
		--A, --B;

		if(uf.issame(A,B)) {
			fb.at(A).insert(B);
			fb.at(B).insert(A);
		}
	}

	rep(i,N)
		cout << uf.size(i)-fb.at(i).size()-1 << " ";
	cout << endl;
}

Measured memory_bytes: 24704
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
int H,W,cnt;
int sx,sy,sd;
long long L;
char grid[maxn][maxn];
int vis[maxn][maxn][4],id[maxn][maxn][4];
int di[][2]={{-1,0},{0,1},{1,0},{0,-1}};
int DIR(char d)
{
    if(d=='S')return 2;
    if(d=='W')return 3;
    if(d=='N')return 0;
    return 1;
}
int move(int &x,int &y,int &d)
{
    int tx,ty;
    for(int i=0;i<4;i++)
    {
        tx=x+di[d][0];
        ty=y+di[d][1];
        if(tx<1||tx>H||ty<1||ty>W||grid[tx][ty]=='#'){d=(d+1)%4;continue;}
        break;
    }
    x=tx,y=ty;
    if(vis[x][y][d])return id[x][y][d];
    vis[x][y][d]=1;
    id[x][y][d]=cnt++;
    return 0;
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d%lld",&H,&W,&L)!=EOF,H+W+L)
    {
        for(int i=1;i<=H;i++)
        {
            scanf("%s",grid[i]+1);
            for(int j=1;j<=W;j++)
            {
                if(grid[i][j]=='.'||grid[i][j]=='#')continue;
                sx=i,sy=j;
                sd=DIR(grid[i][j]);
            }
        }
        memset(vis,0,sizeof(vis));
        memset(id,0,sizeof(id));
        bool flag=true;
        vis[sx][sy][sd]=1;
        id[sx][sy][sd]=1;
        cnt=-1;
        while(L)
        {
            int tv=move(sx,sy,sd);
            if(tv&&flag)
            {
                flag=false;
                L=L%(cnt-tv)+cnt-tv;
            }
            L--;
        }
        char ansd;
        if(sd==0)ansd='N';
        else if(sd==1)ansd='E';
        else if(sd==2)ansd='S';
        else ansd='W';
        printf("%d %d %c\n",sx,sy,ansd);
    }
    return 0;
}

Measured memory_bytes: 1588
n = int(input())
a = [int(input()) for _ in range(n)]
dp = [[a[i] if i==j else max(a[i],a[(i+1)%n]) if (i+1)%n==j else 0 for j in range(n)] for i in range(n)]

for i in range(3 if n%2==0 else 2,n,2):
    for l in range(n):
        r = (l+i)%n

        pat = []
        for x,nextl,nextr in [(l,(l+1)%n,r),(r,l,(r+n-1)%n)]:
            if a[nextl] > a[nextr]:
                nextl = (nextl+1)%n
            else:
                nextr = (nextr+n-1)%n
            pat.append(a[x] + dp[nextl][nextr])

        dp[l][r] = max(pat)

print(max(dp[(i+1)%n][i] for i in range(n)))

Measured memory_bytes: 86800
class UnionFind
  def initialize(n)
    @root = Array.new(n)
    @rank = Array.new(n)
    @size = Array.new(n)
    (0...n).each do |i|
      @root[i] = i
      @rank[i] = 0
      @size[i] = 1
    end
  end

  def find(x)
    if @root[x] == x
      x
    else
      @root[x] = find(@root[x])
    end
  end

  def unite(x, y)
    x_root = find(x)
    y_root = find(y)
    return if x_root == y_root

    if @rank[x_root] < @rank[y_root]
      @root[x_root] = y_root
      @size[y_root] += @size[x_root]
    else
      @root[y_root] = x_root
      @size[x_root] += @size[y_root]
      if @rank[x_root] == @rank[y_root]
        @rank[x_root] += 1
      end
    end
    nil
  end

  def size(x)
    x_root = find(x)
    @size[x_root]
  end

  def same?(x, y)
    find(x) == find(y)
  end
end

N, M = gets.split.map(&:to_i)
ab_list = M.times.map { gets.split.map(&:to_i) }
ans = 0
(0...(ab_list.size)).each do |i|
  a, b = ab_list[i]
  uf = UnionFind.new(N)
  (0...(ab_list.size)).each do |j|
    next if j == i
    _a, _b = ab_list[j]
    uf.unite(_a - 1, _b - 1)
  end
  ans += 1 unless uf.same?(a - 1, b - 1)
end
puts ans


Measured memory_bytes: 3836
import sys
input = sys.stdin.buffer.readline
from collections import Counter
n=int(input())
*a,=map(int,input().split())
C=Counter(a)
ans=sum(a)
for _ in range(int(input())):
	b,c=map(int,input().split())
	ans+=C[b]*(c-b)
	C[c]+=C[b]
	C[b]=0
	print(ans)

Measured memory_bytes: 24800
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=((ll)n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=((ll)a);i<((ll)n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,a,b,c;
    cin>>n>>a>>b>>c;
    vs s(n); cin>>s;
    if(a+b+c==0){
        puta("No");
        return 0;
    }
    
    vl v{a,b,c};
    vector<char> ans;
    vs other{"BC","AC","AB"};
    rep(i,n){
        ll x=s[i][0]-'A';
        ll y=s[i][1]-'A';
        if(/*!v[0] + !v[1] + !v[2] == 2 and */v[x]==0 and v[y]==0){
            puta("No");
            return 0;
        }else{
            if(v[x]<=v[y]){
                if(v[x]==1 and v[y]==1 and i+1!=n and s[i+1]==other[x]){
                    v[x]--;
                    v[y]++;
                    ans.push_back((char)('A'+y));
                }else{
                    v[x]++;
                    v[y]--;
                    ans.push_back((char)('A'+x));
                }
            }else{
                v[x]--;
                v[y]++;
                ans.push_back((char)('A'+y));
            }
        }
    }
    puta("Yes");
    rep(i,n)puta(ans[i]);

    return 0;
}

Measured memory_bytes: 6708
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var items = Console.ReadLine().Split().Select(elem => int.Parse(elem)).ToArray();
            var N = items[0];
            var K = items[1];
            var p = Console.ReadLine().Split().Select(elem => int.Parse(elem)).OrderBy(elem => elem).Take(K).Sum();
            Console.WriteLine(p);
        }
    }
}


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

int main(){
   double d,t,s;
   cin >> d >> t >> s;
   double a = d/s;
   if(a <= t) cout << "Yes" << endl;
   else cout << "No" << endl;
   return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
#define mem(a) memset(a,0,sizeof(a))
#define pd(a) printf("%.10f\n",a)
#define pb(a) push_back(a)
#define in(a) insert(a)
#define pi M_PI
#define R cin>>
#define F first
#define S second
#define C class
#define ll long long
#define ln cout<<'\n'
template<C T>void pr(T a){cout<<a;ln;}
template<C T,C T2>void pr(T a,T2 b){cout<<a<<' '<<b;ln;}
template<C T,C T2,C T3>void pr(T a,T2 b,T3 c){cout<<a<<' '<<b<<' '<<c;ln;}
template<C T>void PR(T a,int n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
bool check(int n,int m,int x,int y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<60,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  int n;
  R n;
  vector<int> a[2],v;
  rep(i,n) {
    int x;
    R x;
    a[i%2].pb(x);
    v.pb(x);
  }
  sort(all(v));
  set<int> s;
  rep(i,n)if(i%2==0)s.in(v[i]);
  int ans=0;
  rep(i,a[0].size()) {
    if(!s.count(a[0][i])) ans++;
  }
  pr(ans);
}

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  Main();return 0;
}


Measured memory_bytes: 3444
#include<cstdio>
using namespace std;
int main(){
  int n,k,x,y;
  scanf("%d %d %d %d",&n,&k,&x,&y);
  if(n<=k)
    printf("%d\n",n*x);
  else
    printf("%d\n",k*x+y*(n-k));
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
using namespace std;
int main (void) {
	int h, w; cin >> h >> w;
	for (int i = 0; i < w+2; i++)
		cout << '#';
	cout << endl;
	for (int i = 0; i < h; i++) {
		string s; cin >> s;
		cout << '#' << s << '#' << endl;
	}
	for (int i = 0; i < w+2; i++)
		cout << '#';
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e9
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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

ll h[100010];
signed main(){
   int n;
   cin>>n;
   REP(i,n) cin>>h[i];
   int cnt=0;
   vector<int> v;
   for (int i = 0; i < n-1; i++)
   {
       if(h[i]>=h[i+1]){
           cnt++;
       }
       else {
           v.push_back(cnt);
           cnt=0;
       }
   }
   v.push_back(cnt);
   sort(ALL(v));
   cout<<v.back()<<endl;
   
   
    return 0;
}

Measured memory_bytes: 2168
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    H, W = Scanner.map_int()
    C = Scanner.int_list_list(10)
    A = Scanner.int_list_list(H)

    for k in range(10):
        for i in range(10):
            for j in range(10):
                C[i][j] = min(C[i][j], C[i][k] + C[k][j])
    ans = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == -1:
                continue
            ans += C[A[h][w]][1]
    print(ans)
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 40792
#include <stdio.h>

void insertionSort(int *,int,int);
void shellSort(int *,int);

int count;

int main()
{
  int i,n;

  /*入力*/
  
  scanf("%d",&n);

  int s[n];

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

  shellSort(s,n);//シェルソート
  
  printf("%d\n",count);//回数表示
  for(i=0;i<n;i++)printf("%d\n",s[i]);//値表示
  return 0;
}

void shellSort(int *s,int n)
{
  int i,g[n],m=0;

  /*漸化式gの定義*/
  
  g[m]=0;
  
  while(1)
    {
      g[m+1]=( 3*(g[m]) )+1;
      if(g[m+1]>n)break;
      m++;
      
    }

  /*m,gを表示*/
  
  printf("%d\n",m);
  
  for(i=m;i>0;i--)
    {
      if(i==1)printf("%d\n",g[1]);
      else printf("%d ",g[i]);
    }

  for(i=m;i>0;i--)
    {
      insertionSort(s,n,g[i]);
    }
}
void insertionSort(int *s,int n,int g)
{
  int i,j,ireru;
  
  for(i=g;i<n;i++)
    {
      ireru=s[i];
      j=i-g;
      
      while(j>=0&&s[j]>ireru)
	{
	  s[j+g]=s[j];
	  j=j-g;
	  count++;
	}
      s[j+g]=ireru;
      }
}
  
      
      
      
  
  



Measured memory_bytes: 5640
import math
from decimal import *

def main():
    A,B,H,M = map(int, input().split())
    t1=30*H+M/2
    t2=6*M
    # if t1==t2:
    #     print(0)
    # else:
    #     c=Decimal(math.sqrt(A*A+B*B-2*A*B*math.cos(math.radians(t1-t2))))
    #     print(c)
    c=Decimal(math.sqrt(A*A+B*B-2*A*B*math.cos(math.radians(t1-t2))))
    print(c)
main()

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    cout << n % k << endl;
    
    return 0;
}



Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0141

"""
import sys
from sys import stdin
input = stdin.readline
from itertools import cycle


def guruguru(n):
    dirs = cycle([(0, -1), (1, 0), (0, 1), (-1, 0)]) #  x, y???????????? (???????????????????????????)

    M = [[' '] * n for _ in range(n)] #  ??????????????¨?????????????????§?????????
    cx = 0                      #  ??????????????°???
    cy = n - 1
    line = 0                    #  ???????????§??????????????????n??¨???????????°??????????????¨??????

    while line < n:
        line += 1
        dx, dy = dirs.__next__() #  ???????????????????????????????????????????????????
        while True:
            M[cy][cx] = '#'

            nx = cx + dx        #  ?¬???????????????¨???????????????
            ny = cy + dy
            if not 0 <= nx < n: #  ??????????????????????????????????????§???????????¢?????????
                break
            if not 0 <= ny < n:
                break
            nnx = nx + dx       #  ?¬?????¬???????????????¨???????????????
            nny = ny + dy
            if 0 <= nny < n and 0 <= nnx < n:
                if M[nny][nnx] != ' ': #  ??????????????????????????????????????¢??????????????????????????£??????????????´??????????????¢?????????
                    break
            cx = nx
            cy = ny

    # ?????????????????????????????????
    for l in M:
        print(''.join(l))


def main(args):
    n = int(input())
    for i in range(n):
        size = int(input())
        guruguru(size)
        if i != (n - 1):        #  ????????\?????????????????????????????????????????\??????
            print()


if __name__ == '__main__':
    main(sys.argv[1:])
    

Measured memory_bytes: 7808
#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;

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

    int k, s;
    cin >> k >> s;
    int ans = 0;
    rep(i, k + 1)
    {
        rep(j, k + 1)
        {
            int n = s - i - j;
            if (0 <= n && n <= k)
                ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#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; }
const ll INF = 1e13;
typedef pair<ll,ll> P;
int main(){
    ll t1,t2;
    ll a1,a2;
    ll b1,b2;
    cin >> t1 >> t2;
    cin >> a1 >> a2;
    cin >> b1 >> b2;
    ll ans = 0;
    if (t1*a1+t2*a2 == t1*b1+t2*b2){
        PRINT("infinity");
    }
    else{
        ll k = abs(t1*a1+t2*a2-t1*b1-t2*b2);
        if (t1*a1+t2*a2 > t1*b1+t2*b2){
            ll a = t1*a1 - t1*b1;
            if (a >= 0) PRINT(0);
            else{
                if (abs(a)%k == 0) PRINT(2*(abs(a)/k));
                else PRINT(2*(abs(a)/k)+1);
            }
        }
        else{
            ll a = t1*b1 - t1*a1;
            if (a >= 0) PRINT(0);
            else{
                if (abs(a)%k == 0) PRINT(2*(abs(a)/k));
                else PRINT(2*(abs(a)/k)+1);
            }
        }
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int mo=1000000007;
const int N=32800;
int b[20],bit[N];
int f[N],n,m;
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		b[x]|=1<<(y-1);
	}
	for (int i=1;i<1<<n;i++)
		bit[i]=(i&1?bit[i>>1]*2+1:bit[i>>1]);
	f[0]=1;
	for (int i=1;i<1<<n;i++)
		if ((i&3)==0||(i&3)==3)
			for (int j=i;j;j=(j-1)&i){
				if ((j&3)!=0&&(j&3)!=3) continue;
				int tmp=1;
				for (int k=0;k<n;k++)
					if (i&(1<<k)){
						if (!(j&(1<<k)))
							tmp=1ll*tmp*bit[b[k+1]&j]%mo;
						else tmp=1ll*tmp*(bit[b[k+1]&(i^j)]+1)%mo;
					}
				f[i]=(f[i]+1ll*f[i^j]*tmp)%mo;
			}
	int ans=1;
	for (int i=1;i<=m;i++)
		ans=2*ans%mo;
	printf("%d",(ans+mo-f[(1<<n)-1])%mo);
}

Measured memory_bytes: 512
N = int(input())
S = input()

tmp = S[1:].count('E')
  
minimum = tmp

for i in range(1, N):
    if S[i-1] == 'W':
        tmp += 1
    if S[i] == 'E':
        tmp -= 1
    minimum = min(tmp, minimum)

print(minimum)


Measured memory_bytes: 3700
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)

// functions
int ceil(int a, int b) {
    return (a + b - 1) / b;
}
int round(int a, int b) {
    return (a + b / 2) / b;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    const int MAX_N = 100;
    int N, a[MAX_N];
    cin >> N;
    int s = 0;
    REP(i, N) {
        cin >> a[i];
        s += a[i];
    }
    int x = round(abs(s), N) * (s > 0 ? 1 : -1);
    int res = 0;
    REP(i, N) {
        int d = a[i] - x;
        res += d * d;
    }
    cout << res << endl;
    return 0;
}


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

const int MOD = 1000000007;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define copy(from, to) copy(from.begin(), from.end(), back_inserter(to))
#define sort(a) sort(a.begin(), a.end())
#define reverse(s) reverse(s.begin(), s.end())
#define p(s) cout << (s) << endl

typedef long long ll;
using namespace std;

template<class T>
void load(vector<T> &v, int n) {
  for (int i = 0; i < n; ++i) {
    T t;
    cin >> t;
    v.push_back(t);
  }
}

template<class T>
T max(vector<T> &v) {
  return *max_element(v.begin(), v.end());
}

template<class T>
T min(vector<T> &v) {
  return *min_element(v.begin(), v.end());
}

void py(bool isUpper = false) {
  if (isUpper) {
    p("YES");
  } else {
    p("Yes");
  }
}

void pn(bool isUpper = false) {
  if (isUpper) {
    p("NO");
  } else {
    p("No");
  }
}

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

  int b[m];
  for (int i = 0; i < m; ++i) {
    cin >> b[i];
  }

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

  int count = 0;
  for (int i = 0; i < n; ++i) {
    int sum = 0;
    for (int j = 0; j < m; ++j) {
      sum += a[i][j] * b[j];
    }
    sum += c;
    if (sum > 0) count++;
  }
  p(count);
}

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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;



int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	while (cin >> n >> m, n) {
		vi v(m, 0);
		REP(i, n) {
			int a, b;
			cin >> a >> b;
			v[a - 1] = max(v[a - 1], b);
		}
		cout << accumulate(ALL(v), 0) << endl;
	}

}


Measured memory_bytes: 3072
#include<stdio.h>
int main(){
  int a,i,F[45];

  scanf("%d",&a);
  F[0] = 1;
  F[1] = 1;

  for(i=2;i<=44;i++){
    F[i] = F[i-2] + F[i-1];
  }
  printf("%d\n",F[a]);
  return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
long long int fact[500005],inv[500005];
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
int main()
{
    long long int i,j,k,z,t,x,y,n,m;
    cin>>n>>m;
    fact[0]=1,inv[0]=1;
    for(i=1;i<=m;i++)
    {
        fact[i]=(i%mod*(fact[i-1]%mod))%mod;
        inv[i]=binpow(fact[i],mod-2,mod);
    }
    x=(fact[m]%mod*inv[m-n]%mod)%mod;
    y=0;
    for(i=0;i<=n;i++)
    {
        if(i&1)
            y=(((y%mod)-((((fact[n]%mod*fact[m-i]%mod)%mod*(inv[i]%mod*inv[m-n]%mod))%mod)*inv[n-i]%mod)%mod)+mod)%mod;
        else
            y=((y%mod)+((((fact[n]%mod*fact[m-i]%mod)%mod*(inv[i]%mod*inv[m-n]%mod))%mod)*inv[n-i]%mod)%mod)%mod;
    }
    //y=(y+mod)%mod;
    //cout<<x<<" "<<y<<endl;
    z=(x%mod*y%mod)%mod;
    cout<<z<<endl;

}


Measured memory_bytes: 11400
def main():
    n = int(input())
    p = list(map(int,input().split()))

    ans = 0

    for i in range(1,n-1):
        tmp = [p[i-1],p[i],p[i+1]]
        tmp.sort()
        if tmp[1] == p[i]:
            ans += 1
    
    print(ans)


if __name__=="__main__":
    main()

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,k;
int main(){
	n=read(),k=read();
	if(k>(n+1)/2){
		return !printf("-1\n");
	}
	int mid=(n+1)/2;
	for(int i=1;i<=mid;++i){
		
		printf("%d %d %d\n",k+(i-1)*2,k+n+mid-i,k+2*n+i-1);
	}
	for(int i=mid+1;i<=n;++i){
		printf("%d %d %d\n",k+(i-mid-1)*2+1,k+2*n-(i-mid),k+2*n+i-1);
	}
	return 0;
}


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

using namespace std;
typedef long long ll;

const ll INF = 1e18;

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

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

  for (int i = 1; i < n; i++) {
    a[i] += a[i - 1];
  }

  ll ans = INF;
  for (int i = 1; i < n; i++) {
    ans = min(ans, abs(2 * a[i - 1] - a[n - 1]));
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1792
w = gets.to_i
gets

d = []

for i in 0 ... w
  d[i] = i+1
end

while gets
  a = $_.split(",").map(&:to_i)
  a[0] += -1
  a[1] += -1
  d[a[0]],d[a[1]] = d[a[1]],d[a[0]]
end

puts d



Measured memory_bytes: 6860
#include<iostream>
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll modinv(ll a, ll m){
  ll b=m,u=1,v=0;
  while(b){
    ll t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  u%=m;
  if(u<0) u+=m;
  return u;
}
int main(){
  ll n,k,ans=0,rt,lt,tmp;
  cin >> n >> k;
  ll a[n];
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  for(int i=0;i<n;i++){
    rt=lt=0;
    for(int j=0;j<n;j++){
      if(i>j&&a[i]<a[j]){
        lt++;
      }else if(i<j&&a[i]<a[j]){
        rt++;
      }
    }
    if(k==1) ans+=lt;
    else ans += ((k)*(2*lt + ((k-1)*(lt+rt))%MOD))%MOD*modinv(2,MOD);
    ans %= MOD;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

ans = float('inf')

for i in range(n):
    if a[i]%2 == 0:
        cnt = 0
        while a[i]%2 == 0:
            a[i] //= 2
            cnt += 1
        ans = min(ans, cnt)

    else:
        print(0)
        exit()
print(ans)

Measured memory_bytes: 38512
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

min_cost = min(a) + min(b)

for i in range(M):
    x, y, c = map(int, input().split())
    min_cost = min(a[x-1] + b[y-1] - c, min_cost)

print(min_cost)

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

int main(void)
{
	int ii, jj, r, c;
	char z;
	long data[101][101];
	

	memset(&data[0][0], (int)0, sizeof(long) * 101 * 101);

	scanf("%d %d", &r, &c);
	for (ii = 0; ii < r; ii++) {
		for (jj = 0; jj < c; jj++) {
			scanf("%ld", &data[ii][jj]);
			scanf("%c", &z);
			data[ii][c] += data[ii][jj];
			data[r][jj] += data[ii][jj];
		}
		data[r][c] += data[ii][c];
	}

	
	for (ii = 0; ii <= r; ii++) {
		for (jj = 0; jj <= c; jj++) {
			printf("%ld", data[ii][jj]);
			if (jj < c) {
				printf(" ");
			}
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 692
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    def bfs(a,b):
        bfs_map = [1 for i in range(n)]
        bfs_map[0] = 0
        q = deque()
        q.append(0)
        s = 1
        while q:
            x = q.pop()
            for y in v[x]:
                if [x,y] != [a,b] and [x,y] != [b,a]:
                    if bfs_map[y]:
                        bfs_map[y] = 0
                        q.append(y)
                        s += 1
        return s
    n,m = LI()
    v = [deque() for i in range(n)]
    l = deque()
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        l.append([a,b])
    ans = 0
    for a,b in l:
        s = bfs(a,b)
        if s < n:
            ans += 1
    print(ans)
#D
def D():
    n,k = LI()
    v = [None for i in range(n)]
    for i in range(n):
        v[i] = LI()
        v[i] = [[None,None]]+[v[i]]
    v.sort(key = lambda x:x[1][1])
    for i in range(n):
        v[i][0][1] = i
    v.sort(key = lambda x:x[1][0])
    for i in range(n):
        v[i][0][0] = i
    po = [[None for i in range(n)] for j in range(n)]
    h = [None for i in range(n)]
    w = [None for i in range(n)]
    for i in range(n):
        po[v[i][0][0]][v[i][0][1]] = v[i][1]
        h[v[i][0][0]] = v[i][1][0]
        w[v[i][0][1]] = v[i][1][1]
    re = [[[[0 for x in range(n)] for y in range(n)] for t in range(n)] for s in range(n)]
    ans = float("inf")
    for s in range(n):
        for t in range(n):
            for y in range(s,n):
                for x in range(t,n):
                    if x == t:
                        re[s][t][y][x] = re[s][t][y-1][x]
                    else:
                        re[s][t][y][x] = max(0,re[s][t][y][x-1]+re[s][t][y-1][x]-re[s][t][y-1][x-1])
                    if po[y][x] != None:
                        re[s][t][y][x] += 1
                    if re[s][t][y][x] >= k:
                        ans = min(ans,(h[y]-h[s])*(w[x]-w[t]))
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()


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

int main()
{
  string T;
  cin >> T;
  
  int N=T.length();
  for(int n=N-1; 0<=n; n--)
  { if(T[n]=='?')
    {
        T[n]='D';
    }
  }
  cout << T << endl;
}

Measured memory_bytes: 3716
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define MOD 1000000007

int x=20000;
int a[20005], b[20005], p[20005];
int n;

void print(int c[20005]){
  for(int i=0;i<n-1;i++){
    cout<<c[i]<<" ";
  }
  cout<<c[n-1]<<endl;
}

int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>p[i]; p[i]--;
    a[i]=1+i*x;
    b[i]=1+(n-i)*x;
  }
  for(int i=0;i<n;i++) a[p[i]]+=i;
  print(a); print(b);
  return 0;
}

Measured memory_bytes: 896
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		List<int>[] E = new List<int>[N];
		for(int i=0;i<N;i++) E[i] = new List<int>();
		
		for(int i=0;i<N-1;i++){
			E[A[i]].Add(i+1);
		}
		
		int[] depth = new int[N];
		depth[0] = 0;
		Queue<int> Q = new Queue<int>();
		Q.Enqueue(0);
		while(Q.Count>0){
			var now = Q.Dequeue();
			foreach(var nxt in E[now]){
				depth[nxt] = depth[now] + 1;
				Q.Enqueue(nxt);
			}
		}
		
		int[] order = Enumerable.Range(0,N).ToArray();
		Array.Sort(depth,order);
		Array.Reverse(order);
		
		int[] dp = new int[N];
		for(int j=0;j<N;j++){
			int now = order[j];
			
			List<int> L = new List<int>();
			foreach(var nxt in E[now]){
				L.Add(dp[nxt]);
			}
			if(L.Count == 0){
				dp[now] = 0;
				continue;
			}
			L.Sort();
			L.Reverse();
//Console.WriteLine("now:{0}" + now + " L:" + String.Join(" ",L));
			for(int i=0;i<L.Count;i++) L[i] += i+1;
			int max = 0;
			for(int i=0;i<L.Count;i++){
				max = Math.Max(L[i],max);
			}
			dp[now] = max;
		}
//Console.WriteLine(String.Join(" ",dp));
		Console.WriteLine(dp[0]);
		
		
		
	}
	
	
	
	
	
	
	int N;
	int[] A;
	public Sol(){
		N = ri();
		A = new int[N-1];
		for(int i=0;i<N-1;i++) A[i] = ri() - 1;
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 19352
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define MOD 1000000007
void fastio(){ios_base::sync_with_stdio(false);cin.tie(NULL);}
ll int power(ll int x, ll int y, ll int p)  
{  
   ll int res = 1;     // Initialize result  
 
    x = x % p; // Update x if it is more than or  
                // equal to p
   
    if (x == 0) return 0; // In case x is divisible by p;
 
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % p;  
 
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}  
ll int dp[2005];
ll int solve(ll int n)
{
  if(n<0)
    return 0ll;
  if(n==0)
    return 1;
  if(dp[n]!=-1)
    return dp[n];
  ll int ans=0;ll int i;
  for(i=3;i<=n;i++)
    {ans+=solve(n-i);ans%=MOD;}
  dp[n]=ans;
  return ans;
}
int main()
{
   ll int T;
T=1;


    while(T--)
    {
      ll int n;
      cin>>n;
      memset(dp,-1,sizeof dp);
      ll int ans =solve(n);
      cout<<ans<<endl;
     
    }

    return 0;
       }

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x, n, min, ans;
  map<int, bool> P;
  cin >> x >> n;
  if (n == 0){
    cout << x << endl;
    return 0;
  }
  for (int i = 0; i < n; i++){
    int p;
    cin >> p;
    P[p] = true;
  }
  min = x;
  ans = 0;
  for (int i = 1; i < 102; i++){
    if (P[i]) {
      continue;
    }
    int diff = abs(x-i);
    if (diff < min) {
      min = diff;
      ans = i;
    }
  }
  cout << ans << endl;
}

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

using namespace std;
int a[1005], b[1005], h, n, dp[20005], res(1e9);
int main() {

    cin >> h >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i] >> b[i];
    for (int i = 1; i <= 20002; ++i)
        dp[i] = 1e9;
    for (int g = 0; g <= h; ++g)
        for (int i = 1; i <= n; ++i)
            if (dp[g] < 1e9)
                dp[g + a[i]] = min(dp[g + a[i]], dp[g] + b[i]);
    for (int i = h; i <= h + 10000; ++i)
        if (dp[i])
            res = min(res, dp[i]);
    cout << res;
    return 0;
}


Measured memory_bytes: 384
#include <cstdio>
#include <set>

using namespace std;

set<int> s;
set<int>::iterator it;

int n;
int m;
int counter1 = 0;
int x;
int i;
int j;

int main(){
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&x);
		s.insert(x);
	}
	scanf("%d",&m);	
	for(i=0;i<m;i++){
		scanf("%d",&x);
		it = s.lower_bound(x);
		if(*it==x) counter1++;
	}
	printf("%d\n",counter1);
	return 0;
}


Measured memory_bytes: 7376
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;

int vis[100009];
typedef pair<int, int> P;


int main()
{
    int k;
    scanf("%d", &k);
    deque<P> q;
    memset(vis, 0, sizeof(vis));
    q.push_back(make_pair(1, 1));
    while(!q.empty())
    {
        P x = q.front(); q.pop_front();
        if(vis[x.first]) continue;
        vis[x.first] = 1;
        if(x.first == 0)
        {
            printf("%d\n", x.second);
            break;
        }
        q.push_front(make_pair(x.first*10 % k, x.second));
        if(vis[(x.first+1)%k]==0&&x.first%10!=9)q.push_back(make_pair((x.first+1) % k, x.second+1));
    }
    return 0;
}


Measured memory_bytes: 1024
#include<cstdio>
#include<cmath>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
	long long pw[32];
	long long n;
	long long i, j, k;
	long long base, val = 1;
	long long input;
	vector<long long> bin[3];
	vector<long long> arr;
	bool all[2];
	bool reverse;
	bool three = false;
	int cnt1 = 0;
	int cnt2;

	for (i = 0; i < 32; i++)
	{
		pw[i] = val;

		val *= 2;
	}

	scanf("%lld", &n);

	for (i = 0; i < n; i++)
	{
		scanf("%lld", &input);

		arr.push_back(input);
	}

	if (n == 3)
	{
		for (i = 0; i < 32; i++)
		{
			bin[0].clear();
			bin[1].clear();

			for (j = 0; j < arr.size(); j++)
			{
				val = arr[j] & pw[i];
				val = !!val;

				bin[val].push_back(arr[j]);
			}

			if (bin[1].size() == 1 || bin[1].size() == 3)
			{
				printf("No\n");

				return 0;
			}
		}

		printf("Yes\n");

		return 0;
	}

	for (i = 0; i < n; i++)
	{
		if (arr[i])
		{
			break;
		}
	}

	if (i == n)
	{
		printf("Yes\n");

		return 0;
	}

	if (n % 3)
	{
		printf("No\n");

		return 0;
	}

	for (i = 0; i < 32; i++)
	{
		bin[0].clear();
		bin[1].clear();

		for (j = 0; j < arr.size(); j++)
		{
			val = arr[j] & pw[i];
			val = !!val;

			bin[val].push_back(arr[j]);
		}

		if (bin[0].size() != n&&bin[0].size() != n / 3)
		{
			printf("No\n");

			return 0;
		}

		if (bin[0].size() == n / 3)
		{
			break;
		}
	}

	if (i >= 31)
	{
		printf("Yes\n");

		return 0;
	}

	base = i;

	for (i = base + 1; i < 32; i++)
	{
		cnt1 = 0;

		all[0] = true;
		all[1] = true;
		reverse = false;

		for (j = 0; j < bin[0].size(); j++)
		{
			val = bin[0][j] & pw[i];

			val = !!val;

			all[!val] = false;

			/*
			if (val)
			{
				printf("No\n");

				return 0;
			}
			*/
		}

		if (!all[0] && !all[1])
		{
			printf("No\n");

			return 0;
		}

		cnt1 += all[1];

		if (three)
		{
			for (k = 1; k <= 2; k++)
			{
				all[0] = true;
				all[1] = true;

				for (j = 0; j < bin[k].size(); j++)
				{
					val = bin[k][j] & pw[i];

					val = !!val;

					all[!val] = false;
				}

				if (!all[0] && !all[1])
				{
					printf("No\n");

					return 0;
				}

				cnt1 += all[1];
			}

			if (cnt1 == 1 || cnt1 == 3)
			{
				printf("No\n");

				return 0;
			}
		}

		else
		{
			all[0] = true;
			all[1] = true;

			cnt2 = 0;

			for (j = 0; j < bin[1].size(); j++)
			{
				val = bin[1][j] & pw[i];

				val = !!val;

				cnt2 += val;

				all[!val] = false;
			}

			if (all[0] && cnt1 || all[1] && cnt1)
			{
				printf("No\n");

				return 0;
			}

			if (!all[0] && !all[1])
			{
				if (!cnt1 || cnt2 != n / 3)
				{
					printf("No\n");

					return 0;
				}

				for (j = bin[1].size() - 1; j >= 0; j--)
				{
					val = bin[1][j] & pw[i];

					if (val)
					{
						bin[2].push_back(bin[1][j]);

						bin[1].erase(bin[1].begin() + j);
					}
				}

				three = true;
			}
		}

		/*
		if (reverse&&all[1])
		{
			printf("No\n");

			return 0;
		}
		*/
	}

	printf("Yes\n");

	return 0;
}

Measured memory_bytes: 2804
N, D  = [int(i) for i in input().split()]
X = int(0)
Y = int(0)
B = int(0)
Z = int(0)
for i in range(N):
  A = []
  A = [int(N) for N in input().split()]
  X = A[0]
  Y = A[1]
  Z = ((X**2+Y**2)**0.5)
  if Z<= D:
    B+=1
print(B)


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

int main() {
    int n; cin >> n;
    int ans = 0;
    int p[n + 1], q[n + 1], l[n + 1];
    for (int i = 0; i < n; i++) cin >> p[i];
    for (int i = 0; i < n; i++) { cin >> q[i]; l[i] = q[i]; }
    int t = 0;
    do {
        for (int i = 0; i < n; i++) {
            if (p[i] != l[i]) break;
            if (i == n - 1) ans = max(t, ans);
        }
        t++;
    } while (next_permutation(l, l + n));

    t = 0;
    do {
        for (int i = 0; i < n; i++) {
            if (p[i] != q[i]) break;
            if (i == n - 1) ans = max(t, ans);
        }
        t++;
    } while (next_permutation(p, p + n));
    cout << ans << endl;
}

Measured memory_bytes: 256
N,W = [int(x) for x in input().split()]
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])
DP = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,W+1):
    for j in range(1,N+1):
        if l[j-1][0] > i:
            DP[j][i] = DP[j-1][i]
        else:
            DP[j][i] = max(DP[j-1][i],DP[j-1][i-l[j-1][0]]+l[j-1][1])
print(DP[N][W])

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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl;
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    int n;
    cin >> n;
    rep(i, n)
    {
        stack<int> b, c;
        int a[10];
        bool flag = 0;
        rep(i, 10) cin >> a[i];

        b.push(a[0]);
        c.push(0);
        for (int i = 1; i < 10; i++)
        {
            int dis1 = a[i] - b.top(), dis2 = a[i] - c.top();
            if (dis1 < 0 && dis2 < 0)
            {
                flag = 1;
                break;
            }
            if (dis1 < dis2 && dis1 > 0)
            {
                b.push(a[i]);
            }
            else
            {
                c.push(a[i]);
            }
        }
        if (flag == 0)
        {
            OP("YES")
        }
        else
        {
            OP("NO")
        }
    }

    return 0;
}


Measured memory_bytes: 3016