akhauriyash/Code-Regression huggingface dataset:
def sort(A):
    global c
    c=0 
    for i in range(0,len(A)-1):
        selection(A,i)
        
    return A

def selection(A,i):
    global c
    min=i
    for j in range(i+1,len(A)):
        if A[min]>A[j]:
            min=j
            
            
    A[i],A[min]=A[min],A[i]
    if not A[i]==A[min]:
        c+=1
    
    
n=int(input())
A=list(map(int,input().split()))

sort(A)
print(' '.join(list(map(str,A))))
print(c)



Measured memory_bytes: 5604
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){

  int N, L;
  cin >> N >> L;
  vector<string> S(N);
  for(int i=0; i<N; i++) cin >> S[i];

  sort((S).begin(), (S).end());
  
  for(int i=0; i<N; i++) cout << S[i];
  cout << "\n";
}


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

ll mod = 1e9 + 7;

int main() {
    int l, r, d;
    cin >> l >> r >> d;
    int ans = 0;
    for(int i=l; i<=r; i++) {
        if(i % d == 0) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3568
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int N = stdIn.nextInt();
        stdIn.close();

        int result = (N % 2 == 0) ? N / 2 : (N + 1) / 2;
        System.out.println(result);
    }
}


Measured memory_bytes: 21588
import java.util.*;
public class Main { 
	static ArrayList<Integer> list = new ArrayList<Integer>();
	static ArrayList<Integer> oddList = new ArrayList<Integer>();
	static int[] dp;
	static int[] odp;
	static int n;
	static int INF = 1 << 22;
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		makeList();		
		dp = new int[1000001];
		odp = new int[1000001];
		Arrays.fill(dp, INF);
		Arrays.fill(odp, INF);
		dp[0] = odp[0] = 0;
		dp();
		oddDp();
		while(true) {
			n = stdIn.nextInt();
			if(n == 0) break;
			int ansA = 0;
			int ansB = 0;
			
			ansA = dp[n];
			ansB = odp[n];
			System.out.println(ansA + " " + ansB);
		}
	}
	public static void dp() {
		for(int i = 0; i <= 1000000; i++) {
			for(int j = 0; j < list.size(); j++) {
				if(i - list.get(j) >= 0) {
					if(dp[i-list.get(j)] + 1 < dp[i]) {
						dp[i] = dp[i-list.get(j)] + 1;
					}
				}
				else {
					break;
				}
			}
		}
	}
	public static void oddDp() {
		for(int i = 0; i <= 1000000; i++) {
			for(int j = 0; j < oddList.size(); j++) {
				if(i - oddList.get(j) >= 0) {
					if(odp[i-oddList.get(j)] + 1 < odp[i]) {
						odp[i] = odp[i-oddList.get(j)]+1;
					}
				}
				else {
					break;
				}
			}
		}
		
	}
	public static void makeList() {
		for(int i = 1; i < 200000; i++) {
			int a = i * (i + 1) * (i + 2);
			if(a % 6 == 0) {
				if(a / 6 > 1000000) break;
				list.add(a / 6);
				if((a / 6) % 2 == 1) {
					oddList.add(a/6);
				}
			}
		}
	}
	
}

Measured memory_bytes: 29292
#include <iostream>
#include <vector>
#include <algorithm>

int main(){
    int n;
    std::vector<int> a;
    std::cin >> n;
    int tmp;
    for(int i = 0; i < 4; i++)
        a.push_back(0);
    for(int i = 0; i < n; i++){
        std::cin >> tmp;
        a.push_back(tmp);
    }
    std::sort(a.begin(), a.end(), std::greater<int>());
    long long h, w;
    size_t i = 0;
    while (1) {
        if(a[i] == a[i+1]){
            h = a[i];
            while (1) {
                if(a[i+2] == a[i+3]){
                    w = a[i+2];
                    break;
                }
                i++;
            }
            break;
        }
        i++;
    }
    std::cout << h * w << std::endl;
    return 0;
}


Measured memory_bytes: 892
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = (1e+9)+7;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
typedef pair<P, int> PP;
int main(){
	int a, b, c; cin >> a >> b >> c;
	cout << min({ a + b,c + b,a + c }) << endl;
	return 0;
}

Measured memory_bytes: 256
a = [int(input()) for i in range(5)]

dic = {}

for i in range(5):
    if str(a[i])[-1] == "0":
        dic.update({i: 0})
    else:
        dic.update({i: int(str(a[i])[-1]) - 10})


min_num = [i for i in dic if dic[i] == min(dic.values())][0]
a_sum = sum(a)
dic.pop(min_num)
print(abs(sum(dic.values())) + a_sum)

Measured memory_bytes: 3064
#include <iostream>
#include <vector> 
#include <string>
#include <set>
#include <unordered_set>
using namespace std;
 
int main() {
	
     vector<vector<int>>  grid(3, vector<int> (3));
     
     for(int i = 0; i < 3; i++) {
     	for(int j = 0; j < 3; j++) {
     		cin >> grid[i][j];
     	}
     }
     int n;
     cin >> n;
     vector<int> bingo(n);
     for(int i = 0; i < n; i++) cin >> bingo[i];
     
	 unordered_set<int> uset;
	 int count = 0;
	 int row = 3;
	 int col = 3;
	 bool done = false;
	 for(int i = 0; i < n; i++) uset.insert(bingo[i]);
	 for(int i = 0; i < 3; i++) {
     	for(int j = 0; j < 3; j++) {
     		
     		// check column by column
     		for(int k = 0; k < 3; k++ ) {
     			if(uset.find(grid[j][k]) != uset.end()) {
     				count++;
     			}
     		}
     		if(count == 3) {
     		   cout << "Yes" << "\n";
     		   return 0;
     		}
     		count = 0;
     		// to check row by row
     		for(int k = 0; k < 3; k++) {
     			if(uset.find(grid[k][j]) != uset.end()) {
     				count++;
     			}
     		}
     		
     		if(count == 3) {
     		   cout << "Yes" << "\n";
     		   return 0;
     		}
     		// to check top uppper left corder 
     		count= 0;
     		for(int k = 0; k < 3; k++) {
     			if(uset.find(grid[row - k - 1][col- k - 1]) != uset.end()) {
     				count++;
     			}
     		}
     		
     		if(count == 3) {
     		   cout << "Yes" << "\n";
     		   return 0;
     		}
     		
     		count = 0;
     		// to check top upper right corner 
     		for(int k = 0; k < 3; k++) {
     			if(uset.find(grid[k][col - k - 1]) != uset.end()) {
     				count++;
     			}
     		}
     		if(count == 3) {
     		   cout << "Yes" << "\n";
     		   
     		   return 0;
     		}
     		count = 0;
     	}
     }
	 cout << "No" << "\n";
	 
  return 0;
}

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

// ?????¬???????????¬??????
#pragma region MACRO
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define PED cout << "\n"
#define rep(i,n) for(int i=0; i<(int)n; ++i)
#define REP(i,x,n) for(int i=x; i<(int)n; ++i)
#define repi(i,n) for(int i=0; i<=(int)n; ++i)
#define REPI(i,x,n) for(int i=x; i<=(int)n; ++i)
#define ILP while(true)
#define FOR(i,c) for(__typeof((c).begin())!=(c).begin(); i!=(c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define mp make_pair
#pragma endregion

// ???
#pragma region TYPE_DEF
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long double> vld;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#pragma endregion

// Effective std
#pragma region ESTD
template<typename C, typename T> int count(C& c, T t) { return count(ALL(c), t); }
template<typename C, typename F> int count_if(C& c, F f) { return count_if(ALL(c), f); }
template<typename C, typename T> void erase(C& c, T t) { remove(ALL(c), t), c.end(); }
template<typename C> void remove(vector<C>& c, unsigned int index) { c.erase(c.begin()+index); }
template<typename C, typename T, typename U> void replace(C& c, T t, U u) { replace(ALL(c), t, u); }
template<typename C, typename F, typename U> void replace_if(C& c, F f, U u) { (ALL(c), f, u); }
template<typename C> void reverse(C& c) { reverse(ALL(c)); }
template<typename C> void sort(C& c) { sort(ALL(c)); }
template<typename C, typename Pred> void sort(C& c, Pred p) { sort(ALL(c), p); }
#pragma endregion

// ?????°
#pragma region CONST_VAL
constexpr int PI = (2*acos(0.0));
constexpr int EPS = (1e-9);
constexpr int MOD = (int)(1e9+7);
constexpr int INF = 100000000;
#pragma endregion

#define int long long

int come[100100];
signed main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; ++i) {
        int a, b;
        cin >> a >> b;
        come[a]++;
        come[b+1]--;
    }
    come[0]++;
    come[100100-1]--;
    int ans = 0;
    int sum = 0;
    for(int i=0; i<100100; ++i) {
        sum += come[i];
        if(i<=sum) ans = i;
    }
    cout << ans-1 << endl;
    return 0;
}

Measured memory_bytes: 3840
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
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 int P = 1000000007;
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
//g++ -std=c++1z main.cpp
//.\a.exe

int main(void){ios::sync_with_stdio(false);cin.tie(0);
///////////////////////////////////////////////////////
int a,b,c;
cin >> a >> b;
c = a+b;
if(c%2==1){
	cout << "IMPOSSIBLE" << endl;
}
else{
	cout << (a+b)/2 << endl;
}

///////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 256
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <tuple>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;

int main(int argc, const char * argv[]) {
    //    ifstream in("input.txt");
    //    cin.rdbuf(in.rdbuf());
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i, n)
    {
        cin >> a[i];
        a[i] -= i + 1;
    }
    
    sort(a.begin(), a.end());
    
    int b = a[n/2];
    
    ll ans = 0;
    rep(i, n)
    {
        ans += abs(a[i] - b);
    }
    
    cout << ans << endl;
    
    return 0;
}

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

typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	else return gcd(y, x % y);
}

int main() {
	ll a, b, c, d; cin >> a >> b >> c >> d;
	ll ans = 0;

	ll btmp = b - b / c - b / d + b / (c * d / gcd(c, d));
	a--;
	ll atmp = a - a / c - a / d + a / (c * d / gcd(c, d));
	cout << btmp - atmp << endl;

	return 0;
}

Measured memory_bytes: 256
import sys

N = int(input())
A = list(map(int,input().split()))
A_sum = 1

if min(A) == 0:
    print(0)
    sys.exit()

else:
    for i in range(N):
        A_sum = A_sum * A[i]
        
        if A_sum > 1e18:
            print(-1)
            sys.exit()


print(A_sum)

Measured memory_bytes: 21692
#include <iostream>
#include <string>

using namespace std;

class Node{
    public:
        Node():nc(0),id(-1){}
        int nc;
        Node* l;
        Node* r;
        Node* p;
        int id;
};

Node* root;

Node* dfs(Node* node,int id){
     // cout<<"dfs id:"<<node->id<<" nc:"<<node->nc<<endl;
     if(node->id==-1)
        return node;
     
     //cout<<"node-id:"<<node->id<<" id"<<id<<endl;
     if(node->id>id){
       if(node->l==nullptr){
            node->l = new Node();
            node->l->p = node;
     //      cout<<"node-p:"<<node->id<<endl;
            node->nc++;
            return node->l;
        }else{
            return dfs(node->l, id);
        }
      }else{
        if(node->r==nullptr){
           node->r = new Node();
           node->r->p = node;
           node->nc++;
           return node->r;
        }
        return dfs(node->r, id);
      }
}

void insert(int id){
//     cout<<"ins"<<endl;
     Node* leaf = dfs(root,id);
     //cout<<"leaf"<<leaf->id<<" p:"<<leaf->p->id<<endl;
     leaf->id = id;      
     
}

bool pf=true;
void pro(Node* n){
    if(n->id!=-1){
        if(pf||n->id!=root->id)
            cout<<" "<<n->id;
        if(n->id==root->id)
            pf=false;
        if(n->l!=nullptr)
            if(n->l->id!=-1)
                pro(n->l);
        if(n->r!=nullptr){
            if(n->r->id!=-1)
            pro(n->r);
        }
    }
}

bool ifr=true;
void ino(Node* n){
    if(n->id!=-1){
        //cout<<"id:"<<n->id<<endl;
        if(n->l!=nullptr){
            if(n->l->id!=-1)
                ino(n->l);
        }
        if(ifr||n->id!=root->id)
            cout<<" "<<n->id;
        if(n->id==root->id)
            ifr=false;
        if(n->r!=nullptr){
            if(n->r->id!=-1)
                ino(n->r);
        }
    }
}

void print(){
    //cout<<"ino"<<endl;
    ino(root);
    cout<<endl;
    ifr=true;
    //cout<<"pro"<<endl;
    pro(root);
    pf=true;
    cout<<endl;
}

int main(){
    int n, id;
    string cmd;
    bool flag=true;
    root = new Node();
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>cmd;
        if(cmd=="insert"){
            cin>>id;
            if(flag){
                root->id=id;
                root->p = new Node();
                flag=false;
            }
            insert(id);
        }else{
            print();
        }
    }
    delete root;
    return 0;
}

Measured memory_bytes: 24656
#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

int main() {
	
	int N;
	int h[100000];
	cin >> N;
	for (int i = 0; i < N; i++)cin >> h[i];
	int dp[100000] = {};
	if (N == 2) {
		cout << abs(h[0] - h[1]) << endl;
	}
	else {
		dp[1] = abs(h[0] - h[1]);
		for (int i = 2; i < N; i++) {
			dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]));
		}
		cout << dp[N - 1] << endl;
	}
	return 0;
}

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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<ll,int> pii;
typedef vector<ll> VL; const int MD = (int)1e9 + 7;
void dbg(){ cerr << "\n"; } template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T, class T2> void amax(T& a,T2 b){ if(a < b) a = b;}

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	string s;
	cin >>s;
	VI dp(2019);
	ll ans = 0;
	for(auto x: s){
		int d = x -'0';
		VI np(2019);
		rep(j, 2019){
			np[(j*10+d)%2019] += dp[j];
		}
		np[d]++;
		ans += np[0];
		swap(dp, np);
	}
	cout << ans <<"\n";
	return 0;
}


Measured memory_bytes: 3704
#include<stdio.h>
#include<string>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
char in[1024];
vector<int> g[1024];
int bfs[1024];
int main(){
	int a;
	while(scanf("%d",&a),a){
		string str;
		for(int i=0;i<1024;i++)g[i].clear();
		map<string,int> m;
		for(int i=0;i<a;i++){
			scanf("%s",in);
			str=in;
			int from=0;
			int S=0;
			for(int j=0;j<str.size();j++){
				if(str[j]==':'){
					string name=str.substr(from,j-from);
					if(m.count(name)){
						S=m[name];
					}else{
						S=m.size();
						m[name]=S;
					}
					from=j+1;
				}
				else if(str[j]==','||str[j]=='.'){
					string name=str.substr(from,j-from);
					int T=0;
					if(m.count(name)){
						T=m[name];
					}else{
						T=m.size();
						m[name]=T;
					}
					g[S].push_back(T);
					from=j+1;
				}
			}
		}
		for(int i=0;i<1024;i++)bfs[i]=0;
		bfs[0]=1;
		queue<int>Q;
		Q.push(0);
		while(Q.size()){
			int at=Q.front();Q.pop();
	//		printf(" %d\n",at);
			for(int i=0;i<g[at].size();i++){
				if(!bfs[g[at][i]]){
					bfs[g[at][i]]=1;
					Q.push(g[at][i]);
				}
			}
		}
		int ret=0;
		for(int i=0;i<m.size();i++)if(bfs[i]&&!g[i].size())ret++;
		printf("%d\n",ret);
	}
}

Measured memory_bytes: 1260
a,v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())

ab = abs(a-b)
vw = abs(v-w)


if v-w > 0:
    if ab <= vw*t:
        print("YES")
    else:
        print("NO")
else:
    print("NO")


Measured memory_bytes: 9172
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
// nCk を取得
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
 
int main() {
string s;
cin>>s;
ll k=0;
ll g=0;
ll r=0;
for(ll i=0; i<(ll)s.size(); i++){
if(s.at(i)=='C'){
k=i;
r++;
break;}}
for(ll i=s.size()-1; i>k; i--){
if(s.at(i)=='F'){
g=i;
r++;
break;}}
if(r==2) cout<< "Yes" << endl;
else cout << "No" << endl;}




Measured memory_bytes: 3628
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cstring>
#include<functional>

#define vec2c vector<vector<char>>
#define vec2i vector<vector<int>>
#define vecc vector<char>
#define vecs vector<string>
#define veci vector<int>
#define vecd vector<double>
#define rep(i, n) for(int i=0; i < (int)(n); i++)
#define rrep(i, n) for(int i=(int)(n); i>=0;i--)
#define rep1e(i, n) for(int i=1; i <= (int)(n); i++)
#define rep1ne(i, n) for(int i=1; i < (int)(n); i++)

#define MAX 100010

using namespace std;

unsigned digit(unsigned num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main() {

	int N, K;
	string S;

	cin >> N >> K >> S;
	K -= 1;
	if (S[K] == 'A') S[K] = 'a';
	else if (S[K] == 'B') S[K] = 'b';
	else if (S[K] == 'C') S[K] = 'c';

	cout << S << endl;
  return 0;
}

Measured memory_bytes: 256
/*
　　　∫ ∫ ∫
　　　ノヽ
　　（＿　 ）
　（＿　　　 ）
（＿＿＿＿＿＿ ）
　ヽ(´･ω･)ﾉ　
　　 |　 /
　　 UU
*/
#pragma region macro
#include <bits/stdc++.h>
typedef long long int64;
using namespace std;
using P = pair<int64, int64>;
typedef vector<int> vi;
const int MOD = (int)1e9 + 7;
const int64 INF = 1LL << 62;
const int inf = 1<<30;
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; }
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = s; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end() //コンテナじゃないと使えない!!
#define debug(x) cerr << #x << ": " << x << "\n";
#define mp make_pair
#define bn '\n'
template <typename T>
ostream& operator<<(ostream& os, const vector<T> &V){
    int N = V.size();
    REP(i,N){
        os << V[i];
        if (i!=N-1) os << " ";
    }
    os << "\n";
    return os;
}
template <typename T,typename S>
ostream& operator<<(ostream& os, pair<T,S> const&P){
    os << "(";
    os << P.first;
    os << " , ";
    os << P.second;
    os << ")";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, set<T> &S){
    auto it=S.begin();
    while(it!=S.end()){
        os << *it;
        os << " ";
        it++;
    }
    os << "\n";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, deque<T> &q){
    for(auto it=q.begin();it<q.end();it++){
        os<<*it;
        os<<" ";
    }
     os<<endl;
    return os;
}
vector<pair<int,int>> dxdy = {mp(0,1),mp(1,0),mp(-1,0),mp(0,-1)};
#pragma endregion
//fixed<<setprecision(10)<<ans<<endl;

/* 全方位木の練習 */
vector<vector<pair<int,int>>> edge;
vector<int> Dist; //iを根とする部分木でのiからのパス最長

int dfs(int v,int pre){
    int res = 0;
    int to,cost;
    for(auto e:edge[v]){
        tie(to,cost) = e;
        if(to==pre) continue;
        chmax(res, cost+dfs(to, v));
    }   
    Dist[v] = res;
    return res;
}

int ans = 0;
// dist_preはrerooting後のDist[pre]
void dfs_with_rerooting(int v, int pre, int dist_pre){
    int to,cost;

    vector<pair<int,int>> child_dist;
    for(auto e:edge[v]){
        tie(to,cost) = e;
        if(to==pre) child_dist.emplace_back(cost+dist_pre, to);
        else child_dist.emplace_back(cost+Dist[to], to);
    }

    sort(ALL(child_dist), greater<pair<int,int>>());
    child_dist.emplace_back(0,-1); //sizeが1のときにバグらないように
    chmax(ans, child_dist[0].first + child_dist[1].first);

    //再帰で根をくるくるしちゃう
    for(auto e:edge[v]){
        tie(to,cost) = e;
        if(to==pre) continue;
        if(child_dist[0].second == to) dfs_with_rerooting(to, v, child_dist[1].first);
        else dfs_with_rerooting(to, v, child_dist[0].first);
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    edge.resize(N);
    Dist.assign(N,0);

    int a,b,c;
    REP(i,N-1){
        cin >> a >> b >> c;
        edge[a].emplace_back(b,c);
        edge[b].emplace_back(a,c);
    }

    dfs(0,-1);
    dfs_with_rerooting(0,-1,0);

    cout << ans << endl;
}


Measured memory_bytes: 25700
#[allow(unused_imports)]
use std::cmp::{Ordering};

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::max($x, max!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! get { 
    ([$t: ty]) => { 
        { 
            let mut line = String::new(); 
            stdin().read_line(&mut line).unwrap(); 
            line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    };
    ([$t: ty];$n: expr) => {
        (0..$n).map(|_|get!([$t])).collect::<Vec<_>>()
    };
    ($t: ty) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t: ty),*) => {
        { 
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
    ($t: ty; $n: expr) => {
        (0..$n).map(|_|get!($t)).collect::<Vec<_>>()
    };
    ($($t: ty),*; $n: expr) => {
        (0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*).unwrap();
    }
}

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

fn solve() {
    let (w,h) = get!(usize, usize);
    let p = get!(usize; w);
    let q = get!(usize; h);

    let mut vec = Vec::new();
    for e in p {
        vec.push((e, false));
    }
    for e in q {
        vec.push((e, true));
    }

    vec.sort();
    let mut wr = w+1;
    let mut hr = h+1;
    let mut res = 0usize;
    for (e, b) in vec {
        if b {
            res += e*wr;
            hr -= 1;
        } else {
            res += e*hr;
            wr -= 1;
        }
    }
    println!("{}", res);
}


Measured memory_bytes: 16240
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let h = read_vec::<usize>();
    let mut cur = 0;
    let mut ans = 0;
    for i in 1..n {
        if h[i] <= h[i - 1] {
            cur += 1;
        } else {
            cur = 0;
        }
        ans = max(ans, cur);
    }
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4188
#include <iostream>
#include <algorithm>
#include <cmath>
#define REP(i,N) for(int i = 0; i < (N); i++)
using namespace std;

int n;
int s[100];

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

    cin >> n;
    REP(i,n) cin >> s[i];

    int total = 0;
    REP(i,n) total += s[i];

    sort(s,s+n);

    // REP(i,n) cout << s[i] << " ";;

    REP(i,n){
        if( total % 10 != 0)
            break;
        else if(s[i]%10 == 0){
            continue;
        }
        else{
            total -= s[i];
        }
    }

    if (total%10 ==0) cout << 0 << "\n";
    else cout << total << "\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

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

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////

int main() {
	int N;
	string S;
	cin >> N;
	cin >> S;
	int R = 0;
	int B = 0;
	for (int i = 0; i < S.size(); ++i) {
		if (S[i] == 'R') {
			R++;
		}
		else {
			B++;
		}
	}
	if (R > B)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T> ostream& operator<<(ostream& s,const multiset<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1'000'000'007;
const ll inf=1'000'000'000'000'000'00;
const int INF=1'000'000'000;
const double EPS=1e-10;
const double PI=acos(-1);

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll k;
    cin>>k;
    if(k%2==0 || k%5==0){
        cout<<-1<<endl;
        return 0;
    }
    ll pow=1,r=0,ans=0;
    rep(_,1e8){
        ans++;
        r=(r+pow*7)%k;
        if(r==0){
            cout<<ans<<endl;
            return 0;
        }
        pow*=10;
        pow%=k;
    }
    cout<<-1<<endl;
}   

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define dbg(x) cout<< #x << ": " << x << "\n";
using namespace std;
#define inf 1e9+7
#define PI  3.14159265358979323846264338327950L
#define pii pair<ll,ll> 




int  main(){
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	int n;
	cin>>n;
	int arr[n];
	int ans=0;
	for(int i=1; i<=n; ++i){
		cin>>arr[i];
	}
	for(int i=1; i<=n; ++i){
		if(i%2 and arr[i]%2) ans++;
	}
	cout<<ans;
}
    

	




Measured memory_bytes: 3608
import functools

N = int(input())
A = list(map(int,(input().split())))

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

def gcd(nums):
    return functools.reduce(euclid, nums)

print(gcd(A))

Measured memory_bytes: 62704
#include<bits/stdc++.h>
#define lli long long int

using namespace std;
int main()
{
    lli n, mn=LONG_MAX, q[200009], i;scanf("%lld",&n);
    scanf("%lld",&q[0]);
    for(i=1;i<n;i++)
    {
        scanf("%lld",&q[i]);
        q[i]+=q[i-1];
    }
    for(i=0;i<n-1;i++) mn=min(mn, abs(q[n-1]-2*q[i]));
    printf("%lld\n",mn);
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int MOD=1e9+7;
ULL pw(ULL a, ULL n){ ULL b=1; while(n){ if(n&1){ b=(b*a)%MOD; } a=(a*a)%MOD; n>>=1; } return b; }
ULL fct(ULL n){ 
  if(n==1){ return 1; }else{ return (n*fct(n-1))%MOD; }
}
ULL ivf(ULL n, ULL a){ 
 ULL ans=n;
 for(ULL i=1; i<a; i++){ ans=(ans*(n-i))%MOD; }
 return ans;
}

int main(){ 
ULL n, a, b, ans; cin >> n >> a >> b;
ULL nCa=(pw(fct(a), MOD-2)*ivf(n, a))%MOD, nCb=(pw(fct(b), MOD-2)*ivf(n, b))%MOD;
ans=(pw(2, n)+MOD-1)%MOD;
ans=(ans+MOD-nCa)%MOD;
ans=(ans+MOD-nCb)%MOD;
cout << ans << "\n";
}

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

typedef long long int ll;


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

    ll n;
    cin>>n;
    ll arr[n+1];
    for(ll i=0;i<n;i++){
        cin>>arr[i];
    }



    sort(arr,arr+n);

    ll l = 1;
    ll hi = arr[n-1];
    ll ans = 0;
    for(ll i=1;i<arr[n-1]+1;i++)
    {

        ll id = lower_bound(arr,arr+n,i)-arr;
        //cout<<i<<" "<<id<<endl;
        if(id == (n-id)){
            ans++;
        }


    }
    cout<<ans<<endl;

}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    string s;
    cin>>n>>s;
    int ans=0,sum=0;
    for(int i=0;i<n;i++){
        if(s[i]=='I'){
            sum++;
        }if(s[i]=='D'){
            sum--;

        }
        ans=max(ans,sum);
    }

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define T int t;cin>>t;while(t--)
#define f(i,n) for (int i=0;i<n;i++)
#define fa(i,a,b) for (int i=a;i<b;i++)
#define b(i,a,b) for (int i=a;i>=b;i--)
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mp make_pair
#define fi first    
#define se second
#define SZ(x) ((int)(x).size())
#define debug(x) cout<<'>'<<#x<<" = "<<x<<endl;
#define MOD 1000000007
#define ce cout<<"\n"
int main()
{
    int n, i, j=0;
    cin>>n;
    int q[n], p[n], fact[10]={1};
    f(i, n){
        cin>>p[i];
        p[i]-=1;
    }
    f(i, n){
        cin>>q[i];
        q[i]-=1;
    }

    vector<int> vp, vq, ap, aq;
    for(i=0; i<9; i++){
        vp.pb(i);
        vq.pb(i);
        fact[i+1] = fact[i]*(i+1);
    }
    f(i, n)
    {
        j = 0;
        for(auto it=vp.begin(); it!=vp.end(); it++, j++)
        {
            if(*it == p[i])
            {
                ap.pb(j);
                vp.erase(it);
                break;
            }
        }
        j = 0;
        for(auto it=vq.begin(); it!=vq.end(); it++, j++)
        {
            if(*it == q[i])
            {
                aq.pb(j);
                vq.erase(it);
                break;
            }
        }
    }
    int a=0, b=0;
    for(i=ap.size()-1, j=0; i>=0; i--, j++)
    {
        a += ap[i]*fact[j];
    }
    for(i=aq.size()-1, j=0; i>=0; i--, j++)
    {
        b += aq[i]*fact[j];
    }
    cout<<abs(a-b)<<'\n';
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

import static java.lang.System.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long X = sc.nextLong();
        long Y = sc.nextLong();

        long cnt = 0;
        while(X <= Y){
            X *= 2;
            cnt++;
        }

        out.println(cnt);
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
long long inf=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
long long gcd(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd(b,a%b);
  }
}
 
long long lcm(long long x, long long y){
  return (x/gcd(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};

bool prime(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

int main(){
  int n;
  long long a,b;
  cin>>n>>a>>b;
  long long x[n];
  REP(i,n){
    cin>>x[i];
  }
  long long ans=0;
  REP(i,n-1){
    ans += min(a*(x[i+1]-x[i]),b);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<algorithm>
using namespace std;
#define SZ 1024
char p[1010][1010];
int n, m, K, IT[SZ + SZ + 1];
int Max(int b, int e){
	int r = -9999999;
	b += SZ, e += SZ;
	while (b <= e){
		r = max(r, IT[b]);
		r = max(r, IT[e]);
		b = (b + 1) >> 1;
		e = (e - 1) >> 1;
	}
	return r;
}
void Add(int a, int b){
	a += SZ;
	while (a){
		IT[a] = max(IT[a], b);
		a >>= 1;
	}
}
int main(){
	int i, j, ck;
	scanf("%d%d%d", &n, &m, &K);
	for (i = 1; i <= n; i++){
		scanf("%s", p[i] + 1);
	}
	for (i = 1; i < SZ * 2; i++)IT[i] = -9999999;
	for (i = 1; i <= n; i++){
		for (j = 1; j <= m; j++){
			ck = 0;
			if (p[i][j] != '.')continue;
			if (i + j - Max(1, j) > K){
				ck = 1;
				Add(j, i + j);
			}
		}
	}
	if (ck == 0)printf("Chieno\n");
	else printf("Cacao\n");
}


Measured memory_bytes: 2008
def f(N):
    if N==1:
        return [[0]]

    X=f(N-1)
    Y=[]
    for x in X:
        k=max(x)
        for a in range(min(k+2,10)):
            Y.append(x+[a])
    return Y

T={0:"a",1:"b",2:"c",3:"d",4:"e",5:"f",6:"g",7:"h",8:"i",9:"j"}
N=int(input())

for a in f(N):
    S=""
    for x in a:
        S+=T[x]
    print(S)


Measured memory_bytes: 25292
#include<iostream>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=55,P=1e9+7;
int n,ans,w,fc[N],iv[N],vf[N],f[N][N][N][N];
void chk(int&x){x-=P;x+=(x>>31)&P;}
int main(){
	//freopen("1.in","r",stdin);
	scanf("%d",&n);
	f[0][1][0][0]=iv[1]=fc[0]=vf[0]=1;
	FOR(i,2,n) iv[i]=1ll*iv[P%i]*(P-P/i)%P;
	FOR(i,1,n) fc[i]=1ll*fc[i-1]*i%P,vf[i]=1ll*vf[i-1]*iv[i]%P;
	FOR(I,1,n){
		FOR(x,0,n)FOR(y,0,n-x)if(x|y)FOR(z,0,n-x-y)if(w=f[I-1][x][y][z]){
			FOR(i,0,x)FOR(j,0,y)if(!(i&&j)){
				if(i>=j) chk(f[I][i-j][0][z+x+y]+=1ll*w*vf[x-i+j]%P*vf[y-j+i]%P);
				else     chk(f[I][0][j-i][z+x+y]+=1ll*w*vf[x-i+j]%P*vf[y-j+i]%P);
			}
		}
		FOR(x,1,n)FOR(y,1,n-x)FOR(z,0,n-x-y)
			chk(f[I][x][y][z]+=f[I][x-1][y-1][z]); 
		//cout<<f[I][0][0][n]<<'\n';
		chk(ans+=f[I][0][0][n]);
	}
	cout<<1ll*fc[n]*ans%P<<'\n';
}

Measured memory_bytes: 34048
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    string a, b;
    cin >> a >> b;
    long combined_num = stol(a + b);
    if (sqrt(combined_num) == roundl(sqrt(combined_num))) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
*/

#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>
#include <functional>
#include <complex>
#include <list>
#include <cassert>
#include <iomanip>
#include <set>
#include <stack>
#include <bitset>

////多倍長整数, cpp_intで宣言
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;

//#pragma gcc target ("avx2")
//#pragma gcc optimization ("Ofast")
//#pragma gcc optimization ("unroll-loops")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printim(a) printf(a ? "possible\n" : "imposible\n")
#define printdb(a) printf("%.50lf\n", a) //少数出力
#define printLdb(a) printf("%.50Lf\n", a) //少数出力
#define printdbd(a) printf("%.16lf\n", a) //少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str()) //string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2LL) //等差数列の和、初項,末項,項数
#define pb push_back
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI)
#define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L)
#define Please return
#define AC 0
#define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d)) /*(a, b) から (c, d) のマンハッタン距離 */
#define inf numeric_limits<double>::infinity();
#define linf numeric_limits<long double>::infinity()

using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1e9 + 7;
constexpr long double eps = 1e-6;
const long double PI = acosl(-1.0L);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);
	while (c != '\n' && c != -1 && c != ' ') {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

ll LSB(ll n) { return (n & (-n)); }

/*-----------------------------------------ここからコード-----------------------------------------*/



int main() {

	int n;
	scanf("%d", &n);
	printf("%d\n", (n + 999) / 1000 * 1000 - n);

	Please AC;
}

Measured memory_bytes: 3804
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main(void) {
	string s; cin >> s;
	int n = s.size();
	bool x = true;
	for (int i =1; i < n; i++) {
		if (s[i-1] != s[n - i - 1]) {
			x = false;
		}
	}
	if (s[0] == '1'&&s[n - 1] == '0'&&x) {
		vector<int> a;
		for (int i = 0; i < n; i++) {
			if (s[i] == '1') {
				a.emplace_back(i);
			}
		}
		a.emplace_back(n-1);
		for (int i = 0; i < n-1; i++) {
			cout << a[(lower_bound(a.begin(), a.end(), i+1) - a.begin())]+1 << " " << i+1 << endl;
		}
	}
	else {
		cout << -1 << endl;
	}

	return 0;
}


Measured memory_bytes: 2040
from itertools import permutations
n , m = map(int,input().split())
route = [set() for i in range(n+1)]
for i in range(m):
    a , b = map(int,input().split())
    route[a].add(b)
    route[b].add(a)
ans = 0
p=[i + 2 for i in range(n-1)]
kouho = list(permutations(p))

for i in range(len(kouho)):
    now = 1
    flag = True
    for j in kouho[i]:
        if j in route[now]:
            now = j
        else:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Measured memory_bytes: 67732
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);++i)
#define fi first
#define se second
#define INF 1000000009
#define lINF 1000000000000000009
typedef long long ll;

int main() {
  int n;
  cin >> n;
  if(n%2 == 0){
    printf("%.10f\n", (double)1/(double)2);
  }
  else{
    printf("%.10f\n", (double)((n+1)/2)/(double)n);
  }
  return(0);
}


Measured memory_bytes: 256
N = int(input())
V = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
dif = []
for i in range(N):
    dif.append(V[i]-C[i])
ans = 0
for i in range(N):
    if dif[i]>0:
        ans += dif[i]
print(ans)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO.Pipes;
using System.Runtime;

namespace Csharponly
{
    class Program
    {
        static public void Main()
        {
            int[] ABCD = Arrayint();

            string ans = "Yes";
            
            if((ABCD[0] - 1)/ABCD[3] < (ABCD[2] - 1) / ABCD[1])
            {
                ans = "No";
            }

            Console.WriteLine(ans);
            
        }


　　　　//一つの文字列を受け渡す
        static string Onestring()
        {
            return Console.ReadLine();
        }

        //複数の文字列を配列で受け渡す
        //文字列と文字列の間は" "で区切る
        static string[] Arraystring()
        {
            return Console.ReadLine().Split(' ');
        }

        //一つの数字を受け渡す
        static int Oneint()
        {
            return int.Parse(Console.ReadLine());
        }

        //複数の数字を配列で受け渡す
        //数字と数字の間は" "で区切る
        static int[] Arrayint()
        {
            String[] input_line = Console.ReadLine().Split(' ');
            int[] input_num = new int[input_line.Length];
            for (int i = 0; i < input_line.Length; i++)
            {
                input_num[i] = int.Parse(input_line[i]);
            }
            return input_num;
        }
    }
}

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

int main(){
    int k;
    cin >> k;
    int x = 7%k;
    set<int> s;
    int i = 1;
    while (s.count(x) == 0){
        if (x == 0){
            cout << i << endl;
            return 0;
        }
        s.insert(x);
        x = (x*10+7)%k;
        ++i;
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 50512
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <functional>
#include <vector>
#include <queue>
#include <map>

using namespace std;

typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)

int A, B, C;

int main() {
  scanf("%d %d %d", &A, &B, &C);
  int m = max(A, max(B, C));
  int s = m - A + m - B + m - C;
  int c = s / 2;
  if (s % 2 != 0) c += 2;
  printf("%d\n", c);
}


Measured memory_bytes: 256
from collections import Counter
h,w=map(int,input().split())
#a=[list(input()) for i in range(w)]
a=[]
flag=True
for i in range(h):
  a+=list(input())
ca=Counter(a)
if h%2==0 and w%2==0:
  for i in ca:
    if ca[i]%4!=0:
      flag=False
      print('No')
      break
  if flag:
    print('Yes')

elif h%2!=0 and w%2!=0:
  yon=(h-1)*(w-1)
  ni=h*w-yon-1
  iti=1
  for i in ca:
    while ca[i]>0:
      if ca[i]%4==0 and yon>0:
        ca[i]-=4
        yon-=4
      elif ca[i]%2==0 and ni>0:
        ni-=2
        ca[i]-=2
      elif iti>0:
        iti-=1
        ca[i]-=1
      else:
        break
  if yon==0 and ni==0 and iti==0:
    print('Yes')
  else:
    print('No')
else:
  if h%2==0:
    yon=(h)*(w-1)
  else:
    yon=(h-1)*(w)
  ni=h*w-yon
  for i in ca:
    while ca[i]>0:
      if ca[i]%4==0 and yon>0:
        ca[i]-=4
        yon-=4
      elif ca[i]%2==0 and ni>0:
        ni-=2
        ca[i]-=2
      else:
        break
  if yon==0 and ni==0:
    print('Yes')
  else:
    print('No')
  
  

Measured memory_bytes: 9564
import java.util.Scanner;

/**
 * 
 */

/**
 * @author kawakami
 *
 */
class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner as = new Scanner(System.in);
		
		String taro = "";
		String hana = "";
		String str;
		
		int i = 0;
		int num = 0;
		int tpoi = 0;
		int	hpoi = 0;
		
		num = as.nextInt();
		
		for(i=0;i<num;i++){
			
			taro = as.next();
			hana = as.next();
			
			if(hana.compareTo(taro) == 0){
				
				tpoi++;
				hpoi++;
				
			}
			else if(hana.compareTo(taro) < 0){     //??±????????????????????????????????§????????´???
				
				tpoi = tpoi + 3;
				
			}
			else{
				
				hpoi = hpoi + 3;
				
			}
			
		}
		
		str = String.valueOf(tpoi)+" "+String.valueOf(hpoi);
		System.out.println(str);

	}

}

Measured memory_bytes: 29404
A,B,K=map(int,input().split())

def ans120(A:int, B:int, K:int):
    if A>=B:
        n=A
    else:
        n=B
    ans_list=[]
    for i in range(1,n+1):
        if A%i==0 and B%i==0:
            ans_list.append(i)
    return ans_list[-K]

print(ans120(A,B,K))


Measured memory_bytes: 9136
/*C - Poll*/

#include <bits/stdc++.h>

using namespace std;

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

	int tam;
	int mayor = 0;
	string pal;

	cin >> tam;

	map <string, int> dicc;

	for (int i = 0; i < tam ; ++i)
	{
		cin >> pal;

		if(dicc.count(pal))
			dicc[pal]++;
		else
			dicc[pal] = 1;

		if(dicc[pal] > mayor)
			mayor = dicc[pal];
	}

	map <string, int>:: iterator it;
	
	for (it = dicc.begin(); it != dicc.end() ; ++it)
		if (it -> second == mayor)
			cout << it -> first << '\n';
	

	return 0;
}

Measured memory_bytes: 23808