akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(10000000)
input=sys.stdin.readline

n,k = map(int,input().split())

mx=(n-1)*(n-2)//2

if mx < k:print(-1);exit()

ans=[]
for i in range(n-1):
    ans.append((i+1,n))


add=mx-k

edge=[]
for i in range(n-1):
    for j in range(i):
        edge.append((i+1,j+1))
for i in range(add):
    ans.append(edge[i])

print(len(ans))
for i in ans:
    print(*i)

Measured memory_bytes: 4020
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <cmath>
#include <ios>
#include <ctype.h>
#include <stack>
#include <istream>
#include <stdio.h>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <list>
#include <deque>
#include <time.h>
#include <random>
#include <iomanip>
#include <fstream>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define pint pair<int,int>
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
using Graph_weighted = vector<vector<pair<int,int>>>;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
ll ceil(const ll a, const ll b) { return (a + b - 1) / b; }
int main(){
  int n;
  cin >> n;
  vector<int>v(n);
  rep(i,n - 1){
    int tmp;
    cin >> tmp;
    v[tmp - 1]++;
  }
  rep(i,n)cout << v[i] << endl;
  return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }

// ----------------------------------------------------------------------
// ----------------------------------------------------------------------

struct UnionFind {
  vector<int> par, s, e; 
  UnionFind(int N) : par(N), s(N), e(N) { rep(i,N) { par[i] = i; s[i] = 1; e[i] = 0; } }
  int root(int x) { return par[x]==x ? x : par[x] = root(par[x]); }
  int size(int x) { return par[x]==x ? s[x] : s[x] = size(root(x)); }
  int edge(int x) { return par[x]==x ? e[x] : e[x] = edge(root(x)); }
  void unite(int x, int y) { int rx=root(x), ry=root(y); if (rx!=ry) { s[rx] += s[ry]; e[rx] += e[ry]+1; par[ry] = rx; } else e[rx]++; }
  bool same(int x, int y) {  int rx=root(x), ry=root(y); return rx==ry; }
};

// ----------------------------------------------------------------------
// ----------------------------------------------------------------------

vector<ll> zaatsu(vector<ll> &list) {
  map<ll, ll> num; for (auto x: list) num[x]++;
  ll p = 0; for (auto x: num) { num[x.first] = p; p++; }
  vector<ll> result; for (auto x: list) result.push_back(num[x]);
  return result;
}

// ----------------------------------------------------------------------
// ----------------------------------------------------------------------

int main() {
  int N; cin >> N;
  vector<ll> a(N+1,0); rep(i,N) { cin >> a[i]; a[N] ^= a[i]; }
  vector<ll> b(N+1,0); rep(i,N) { cin >> b[i]; b[N] ^= b[i]; }
  map<ll, ll> ca, cb; rep(i,N+1) { ca[a[i]]++; cb[b[i]]++; }
  bool ok = true; for (auto x: ca) ok &= cb[x.first]==x.second;
  if (!ok) { cout << -1 << endl; return 0; }

  vector<ll> za = zaatsu(a), zb = zaatsu(b);
  // debug(all(za)); debug(all(zb));

  UnionFind uf(N+1);
  rep(i,N+1) if (za[i]!=zb[i]) uf.unite(za[i],zb[i]);
  // rep(i,N+1) cout << i << "->" << uf.root(i) << " " << uf.size(i) << " " << uf.edge(i) << endl;
  ll result = 0;
  rep(i,N) {
    if (i==uf.root(i)) {
      if (i==uf.root(za[N])) {
        if (za[N]==zb[N]) result += uf.edge(i);
        else result += uf.edge(i)-1;
      }
      else if (uf.edge(i)!=0) result += uf.edge(i)+1;
    }
  }
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 22904
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> x(n);
  for(int i=0;i<n;i++){
    cin>>x[i];
  }
  sort(x.begin(),x.end());
  int R=x[n-1]; 
  int L=x[0];
  int ans=1000000000;
  for(int i=L;i<=R;i++){
    int sum=0;
    for(int j=0;j<n;j++){
      sum+=(x[j]-i)*(x[j]-i);
    }
    ans=min(sum,ans);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3628
#include <list>
#include <utility>
#include <cmath>
#include <cstdio>

using namespace std;

typedef list<pair<double, double> > mylist;
typedef mylist::iterator myitr;

double c = cos(M_PI / 3);
double s = sin(M_PI / 3);

void koch(mylist &lst, int order)
{
	if (order > 0) {
		myitr it1 = lst.begin();
		myitr it2 = lst.begin();
		it2++;
		while (it2 != lst.end()) {
			double x0 = (*it1).first;
			double y0 = (*it1).second;
			double x1 = (*it2).first;
			double y1 = (*it2).second;
			double dx = (x1 - x0) / 3;
			double dy = (y1 - y0) / 3;
			lst.insert(it2, make_pair(x0 + dx, y0 + dy));
			lst.insert(it2,	make_pair(x0 + dx + dx * c - dy * s,
						              y0 + dy + dx * s + dy * c));
			lst.insert(it2, make_pair(x1 - dx, y1 - dy));
			it1 = it2;
			it2++;
		}
		koch(lst, order - 1);
	}
}

int main() {
	int n;
	scanf("%d", &n);
	mylist lst;
	lst.push_back(make_pair(0, 0));
	lst.push_back(make_pair(100, 0));
	koch(lst, n);

	myitr it = lst.begin();
	while(it != lst.end()) {
		printf("%.8f %.8f\n", (*it).first, (*it).second);
		it++;
	}

	return 0;
}

Measured memory_bytes: 1268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(ll i = (ll)a; i <= (ll)b; i++)
#define DEC(i, a, b) for(ll i = (ll)a; i >= (ll)b; i--)
typedef pair<ll, ll> pi;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

ll x;

inline ll f(ll a) {
	return a*a*a*a*a;
}

int main() {
	fastio; cin >> x;
	FOR(a, -1000, 1000) FOR(b, -1000, 1000) {
		if (f(a) - f(b) == x) {
			cout << a << " " << b << "\n";
			return 0;
		}
	}
}


Measured memory_bytes: 3612
import java.util.*;
public class Main {
	public static int[] swap(int[] a, int p, int c) {
			int[] tmp = new int[a.length];
			int n = tmp.length;
			int lastA = 0;
			for(int i = 0; i < n - p + 1 - c; i++) {
				tmp[i] = a[i];
			}
			for(int i = 0; i < p - 1; i++) {
				tmp[i + (n - p + 1 - c)] = a[i + (n - p + 1)];
			}
			for(int i = 0; i < c; i++) {
				tmp[i + (n - c)] = a[i + (n - p + 1 - c)];
			}
			return tmp;
			
	}
	
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		while(true) {
			int n = stdIn.nextInt();
			int r = stdIn.nextInt();
			if(n == 0 && r == 0) {
				break;
			}
			
			int[] card = new int[n];
			for(int i = 0; i < n; i++) {
				card[i] = i+1;
			}
		
			for(int i = 0; i < r; i++) {
				int p = stdIn.nextInt();
				int c = stdIn.nextInt();
				card = swap(card,p,c);
				
			}
			System.out.println(card[card.length - 1]);
		}
	}
}

Measured memory_bytes: 28284
import java.util.NoSuchElementException;
import java.util.Scanner;

public class Main {
    private static int INF = 1 << 21;
    private static int WHITE = 0;
    private static int GRAY = 1;
    private static int BLACK = 2;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        try {
            int n = Integer.parseInt(sc.nextLine());
            int[][] m = new int[n][n];
            while (sc.hasNext()) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        int a = sc.nextInt();
                        m[i][j] = a == -1 ? INF : a;
                    }
                }
            }
            int c = prim(n, m);
            System.out.println(c);
        } catch (NoSuchElementException | NumberFormatException e) {
            System.out.println(e);
        }
    }

    private static int prim(int n, int[][] m) {
        int u, minv;
        int[] d = new int[n];
        int[] p = new int[n];
        int[] color = new int[n];

        for (int i = 0; i < n; i++) {
            d[i] = INF;
            p[i] = -1;
            color[i] = WHITE;
        }
        d[0] = 0;
        while (true) {
            minv = INF;
            u = -1;
            for (int i = 0; i < n; i++) {
                if (minv > d[i] && color[i] != BLACK) {
                    u = i;
                    minv = d[i];
                }
            }
            if (u == -1) {
                break;
            }
            color[u] = BLACK;
            for (int v = 0; v < n; v++) {
                if (color[v] != BLACK && m[u][v] != INF) {
                    if (d[v] > m[u][v]) {
                        d[v] = m[u][v];
                        p[v] = u;
                        color[v] = GRAY;
                    }
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (p[i] != -1) {
                sum += m[i][p[i]];
            }
        }
        return sum;
    }
}



Measured memory_bytes: 41656
a,b,k=map(int,input().split())
yakusuu_array=[]
if a==b:
    max_gcd=a
else:
    for l in  reversed(range(min(a,b)+1)):
        if (a%l==0) and (b%l==0):
            max_gcd=l
            break        
if k==1:
    print(max_gcd)
else:
    for i in range(1,max_gcd):
        if max_gcd % i == 0:
            yakusuu_array.append(i)

    #print(max_gcd)
    #print(yakusuu_array)
    print(yakusuu_array[-(k-1)])

Measured memory_bytes: 3064
#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 numOf1s(ll bit){
    int cnt = 0;
    while(bit){
        if(bit & 1 == 1) ++cnt;
        bit = bit >> 1;
    }
    return cnt;
}

int main(){
    int N; cin >> N;
    vector<vector<P>> vec(N);
    rep(i, N){
        int a; cin >> a;
        rep(j, a){
            int x,y; cin >> x >> y;
            --x;
            vec[i].push_back(P(x,y));
        }
    }

    int result = 0;
    for(ll bit=0; bit < (1<<N); ++bit){
        bool valid = true;
        for(int i=0; i<N; ++i){
            if((bit >> i & 1) != 1) continue;
            for(auto p : vec[i]){
                if(p.second != (bit >> p.first & 1)){
                    valid = false;
                }
            }
        }
        if(valid) result = max(result, numOf1s(bit));
    }
    cout << result << endl;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <boost/range/adaptors.hpp>

using namespace std;

int main() {
  int n;
  std::cin >> n;
  std::vector<int> as(n - 1);
  for (auto& a : as) {
    std::cin >> a;
  }
  int aa;
  std::cin >> aa;
  std::cout << aa;

  auto itr = as.end();
  bool flag = false;
  for (auto const a : boost::adaptors::reverse(as)) {
    if (flag) {
      std::cout << " " << a;
    } else {
      (*(--itr)) = a;
    }
    flag = !flag;
  }
  for (; itr != as.end(); itr++) {
    std::cout << " " << (*itr);
  }
  std::cout << std::endl;
  return 0;
}


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

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N = II()

    ans = 0
    for i in range(1, N+1, 2):
        cnt = 0
        for j in range(1, i+1):
            if i % j == 0:
                cnt += 1
        if cnt == 8:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


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

    #define pb push_back
    #define all(x) x.begin(), x.end()
    #define tmax(a, b, c) max(max(a, b), c)
    #define fio cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
    using namespace std;

    const int INF = 1e9+5;
    const long long LINF = 1e18+5;
    const double eps = 1e-9;
    fstream fin, fout;
    typedef pair<int, int> ii;
    typedef vector<ii> vii;
    typedef long long ll;
    typedef vector<int> vi;
    typedef vector<bool> vb;
    typedef vector<char> vc;
    typedef vector<vector<int> > vvi;
    typedef vector<ll> vll;

    int main(){
    fio;
    int n;
    double t, a; cin >> n >> t >> a;
    int ans;
    double z = 1000;
    for(int i = 1; i <= n; i++){
        int d; cin >> d;
        if( fabs((t - d * 0.006) - a) < z ){
            ans = i;
            z = fabs(t - d * 0.006 - a);
        }
    }
    cout << ans;
    }


Measured memory_bytes: 256
using System;
using System.Linq;

namespace Atcoder
{
    class Program
    {
        public static void Main(string[] args)
        {
            long[] input = Console.ReadLine().Split(" ").Select(i=>long.Parse(i)).ToArray();
            int count = 1;
            foreach (var items in input) 
            {
                if (items == 0)
                    Console.Write(count);
                count++;
            }
            
          
        }
    }
}


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

 
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
	int n;
    cin >> n;
    if(n%10 == 3)
        cout << "bon";
    else if(n%10 == 0||n%10 == 1||n%10 == 6||n%10 == 8)
        cout << "pon";  
    else
        cout << "hon";
    return 0;
}


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

const int M = 1000005;

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i, N) cin >> a[i];
    vector<int> v(M);
    for (auto x : a) {
        if (v[x] != 0) {
            v[x] = 2;
            continue;
        }
        for (int i = 0; i < M; i += x) {
            v[i]++;
        }
    }
    int count = 0;
    for (auto x : a) {
        if (v[x] == 1)
            count++;
    }
    cout << count << endl;
}

Measured memory_bytes: 8020
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int s = sc.nextInt();
    sc.close();
    List<Integer> ls = new ArrayList<>();
    ls.add(s);
    int c = s;
    for (int i = 1; i < 1000000; i++) {
      if (c % 2 == 0) {
        int f1 = c/2;
        if (ls.contains(f1)) {
          System.out.println(ls.size()+1);
          return;
        }
        ls.add(f1);
        c = f1;
      } else {
        int f2 = 3 * c + 1;
        if (ls.contains(f2)) {
          System.out.println(ls.size()+1);
          return;
        }
        ls.add(f2);
        c = f2;
      }
    }
  }
}


Measured memory_bytes: 35820
a = [int(x) for x in input().split()]
weight = a[1]
dp = [0] * weight + [0]
for x in range(a[0]):
    b = [int(x) for x in input().split()]
    for x in range(weight, b[0] - 1, -1):
        dp[x] = max(dp[x], dp[x - b[0]] + b[1])
print(dp[-1])


Measured memory_bytes: 69720
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#include<functional>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define SENTINEL 1000000001

#define min(a,b) ((a)>(b)?(b):(a))
#define max(a,b) ((a)>(b)?(a):(b))

using namespace std;

typedef pair<int, int> pii;

#define NUM 2147483647

int N = 1;
int st[270000];

void init(int first_N) {
	while (N < first_N)N *= 2;
}

void update(int s, int t, int v, int id, int l, int r) {
	if (t < l || s > r)return;
	else if (s <= l && t >= r) {
		st[id] = v;
	}
	else {
		if (st[id] >= 0) {
			st[2 * id + 1] = st[id];
			st[2 * id + 2] = st[id];
			st[id] = -1;
		}
		update(s, t, v, 2 * id + 1, l, (l + r) / 2);
		update(s, t, v, 2 * id + 2, (l + r) / 2 + 1, r);
	}
}

int query(int s, int t, int id, int l, int r) {
	if (t < l || s > r) {
		return NUM;
	}
	else {
		if (st[id] != -1)return st[id];
		else {
			int left = query(s, t, 2 * id + 1, l, (l + r) / 2);
			int right = query(s, t, 2 * id + 2, (l + r) / 2 + 1, r);
			return min(left, right);
		}
	}
}

int main() {
	int first_N, Q;
	scanf("%d %d", &first_N, &Q);

	init(first_N);

	for (int i = 0; i <= 2 * N - 2; i++)st[i] = NUM;

	int command, left, right, value;

	for (int i = 0; i < Q; i++) {
		scanf("%d", &command);

		if (command == 0) {
			scanf("%d %d %d", &left, &right, &value);
			update(left, right, value, 0, 0, N - 1);
		}
		else {
			scanf("%d %d", &left, &right);
			printf("%d\n", query(left, right, 0, 0, N - 1));
		}
	}
}


Measured memory_bytes: 4240
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

#define FOR(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)

using namespace std;
const int MOD = 1e9 + 7;

int main() {
    long long n, m;
    cin >> n >> m;
    vector<long long> x(n);
    FOR(i, 0, n) {
        cin >> x[i];
    }
    vector<long long> y(m);
    FOR(i, 0, m) {
        cin >> y[i];
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    long long accum = 0;
    FOR(i, 0, n - 1) {
        accum = (accum + ((x[i + 1] - x[i]) % MOD)*((i + 1)*(n - i - 1)) % MOD) % MOD;
    }

    long long ans = 0;
    FOR(i, 0, m - 1) {
        long long toadd = (accum*(y[i + 1] - y[i]) % MOD) % MOD;
        toadd = (toadd  *((i + 1)*(m - i - 1)) % MOD) % MOD;
        ans = (ans + toadd) % MOD;
    }
    cout << ans << endl;
    return 0;
}

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

ll Pow(int n) {
	ll res = 1;
	for (int i = 0; i < n; i++) {
		res *= 2;
	}
	return res;
}

ll combi(ll n, ll k) {
	ll res = 1;
	for (ll i = 1; i <= k; i++) {
		res = res * (n - i + 1) / i;
	}
	return res;
}

int main()
{
	int N, P;
	cin >> N >> P;
	int t = 0;
	for (int i = 0, Ai; i < N; i++) {
		cin >> Ai;
		if (Ai & 1) t++;
	}
	ll res = 0;
	if (P) {
		for (int i = 1; i <= t; i += 2) {
			res += combi(t, i);
		}
		res *= Pow(N - t);
	}
	else {
		for (int i = 0; i <= t; i += 2) {
			res += combi(t, i);
		}
		res *= Pow(N - t);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
n, m = gets.split.map(&:to_i)
pp = gets.split.map(&:to_i)

edge = Array.new(n+1) {[]}
m.times do 
    x, y = gets.split.map(&:to_i)
    edge[x] << y
    edge[y] << x
end

visit = Array.new(n+1)
k = 0
1.upto(n) do |i|
    next if visit[i]

    que = [i]
    while now = que.shift
        next if visit[now]
        visit[now] = k
        edge[now].each {|e| que << e}
    end

    k += 1
end

p pp.each_with_index.count {|e, i| visit[i+1] == visit[e]}

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

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

const ll MOD = (ll)1e9 + 7;
const ll MOD2 = 998244353;
const ll LLINF = (ll)1e18;
const ll INTINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max<T>(a,b);}
template <class T> void chmin(T& a, const T b){a=min<T>(a,b);}
void YN(bool flg) {cout << ((flg) ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << ((flg) ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << ((flg) ? "yes" : "no") << endl;}

int main() {
	V<int> c(4,0);
	REP(i,3) {
		int a,b; cin >> a >> b;
		a--,b--;
		c[a]++;
		c[b]++;
	}
	sort(ALL(c));
	YN(c[0]==1&&c[1]==1&&c[2]==2&&c[3]==2);



	return 0;
}


Measured memory_bytes: 256
N,P = map(int,input().split())
# def usage(N):
    # n = N

    # print('# 素因数')
    # fct = factorize(n)
    # print(fct, num(fct))
    #
    # print('# 約数')
    # for div in divisorize(fct):
    #     print(div, num(div))


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


# def divisorize(fct):
#     b, e = fct.pop()  # base, exponent
#     pre_div = divisorize(fct) if fct else [[]]
#     suf_div = [[(b, k)] for k in range(e + 1)]
#     return [pre + suf for pre in pre_div for suf in suf_div]


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

cnt = 1

for (x,y) in factorize(P):
    cnt = cnt * x**(y // N)

print(cnt)

Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 998244353;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;

ll modadd(ll x, ll y) {
    return ((x + y) % mod + mod) % mod;
}

ll modminus(ll x, ll y) {
    return (x - y + mod) % mod;
}

ll multiply(ll x, ll y) {
    return (x % mod) * (y % mod) % mod;
}

ll modpower(ll x, ll y) {
    if (y == 0) {
        return 1;
    } else if (y == 1) {
        return x % mod;
    } else if (y % 2 == 0) {
        ll p = modpower(x, y / 2);
        return p * p % mod;
    } else {
        ll p = modpower (x, y / 2);
        return (p * p) % mod * (x % mod) % mod;
    }
}

ll dp[310][90010];
ll dpb[310][90010];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll a[N];
    ll sum = 0;
    REP(i, 0, N) {
        cin >> a[i];
        sum += a[i];
    }
    dp[0][0] = 1;
    dpb[0][0] = 1;
    REP(i, 0, N) {
        REP(j, 0, 90000) {
            dp[i + 1][j] = modadd(dp[i + 1][j], multiply(dp[i][j], 2));
            dpb[i + 1][j] = modadd(dpb[i + 1][j], dpb[i][j]);
            if (j + a[i] <= 90000) {
                dp[i + 1][j + a[i]] = modadd(dp[i + 1][j + a[i]], dp[i][j]);
                dpb[i + 1][j + a[i]] = modadd(dpb[i + 1][j + a[i]], dpb[i][j]);
            }
        }
    }
    ll dis = 0;
    ll disa = 0;
    REP(i, (sum + 1) / 2, sum) {
        dis = modadd(dis, dp[N][i]);
    }
    dis = multiply(dis, 3);
    if (sum % 2 == 0) {
        disa = dpb[N][sum / 2];
    }
    disa = multiply(disa, 3);
    ll base = modadd(modpower(3, N), -3);
    ll ans = modadd(base, - modadd(dis, - disa));
    cout << ans << endl;
}


Measured memory_bytes: 425600
#include <bits/stdc++.h>
using namespace std;
#define Int int64_t
#define dump(x) cout << (x) << endl
#define fi first
#define se second
Int mod = 1e9+7;
//Int mod = 1e6+3;

int main() {
    Int n, x;
    cin >> n >> x;
    vector<Int> l(n + 1, 0);
    for (Int i = 1; i <= n; i++) cin >> l[i];
    for (Int i = 0; i < n; i++) l[i + 1] += l[i];
    Int cnt = 0;
    for (Int i = 0; i <= n; i++) if (l[i] <= x) cnt++;
    dump(cnt);
    return 0;
}

Measured memory_bytes: 256
#input
N,Y = map(int,input().split())
#A = list(map(int, input().split()))
#print(N,Y)

ans = [-1,-1,-1]
#flag = True
# N = x + y + zを満たす組
for x in range(N+1):
    for y in range(N+1):
        z = N - x - y
        if z >= 0:
            list = [x,y,z]
            if Y == 10000*list[0]+5000*list[1]+1000*list[2]:
                ans = list
                break
print(ans[0],ans[1],ans[2])

Measured memory_bytes: 40940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e6+5;
int main() {
    int n;cin>>n;
    int now;cin>>now;
    ll ans=0;
    for(int i=2;i<=n;i++) {
    	int tem;cin>>tem;
    	if(tem<now) ans+=now-tem;
    	else now=tem;
    }
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;

#define countof(a) (sizeof(a)/sizeof(*a))

#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pi >
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define all(n) n.begin(), n.end()

#define FROMTO(var, from, to) for (register int var = (from), var##down = ((int)(to)) < ((int)(from));var##down ? (var >= (int)(to)) : (var <= (int)(to));var##down ? var-- : var++)
#define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
#define DOWNTO(var, from, to) for (register int var = (from); var >= ((int)to); var--)
#define FOR(var, to)          UPTO(var, 0, (to)-1)
#define DOWN(var, from)       DOWNTO(var, (from)-1, 0)

#define INIT(var, val) FOR(i,countof(var)) var[i] = val
#define INPUT(var) FOR(i,countof(var)) cin >> var[i]
#define INPUT1(var) FOR(i,countof(var)) cin >> var[i], var[i]--

#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)
#define QSORT(v,b) qsort(v,countof(v),sizeof(*v),b)

#define MOD 1000000007
#define INF ((1 << 30)-1)
#define LINF ((1LL << 62)-1)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

struct Comb {
    vector<vector<s64> > data;
    Comb(int n) { // O(n^2)
        data = vector<vector<s64> >(n+1,vector<s64>(n+1,1));
        UPTO(i,1,n) {
            FOR(j,i+1) {
                if (!j || j == i) data[i][j] = 1;
                else data[i][j] = data[i-1][j-1] + data[i-1][j];
            }
        }
    }

    s64 ncr(int n, int r) {
        return data[n][r];
    }
};

static inline int ri() {
  int a;
  scanf("%d", &a);
  return a;
}

int int_less(const void *a, const void *b) {
  return (*((const int*)a) - *((const int*)b));
}
int int_greater(const void *a, const void *b) {
  return (*((const int*)b) - *((const int*)a));
}

int main() {
    int n = ri();
	string a[3];
	FOR(i,3) cin >> a[i];

	int res = 0;
	FOR(i,n) {
		if (a[0][i] != a[1][i] && a[1][i] != a[2][i] && a[0][i] != a[2][i]) {
			res += 2;
		} else if (a[0][i] == a[1][i] && a[1][i] == a[2][i]) {
			res += 0;
		} else res += 1;
	}
	cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

type node struct {
	edge    []int
	dist    [2]int
	Visited [2]bool
}

type graph []node

func DFS(G *graph, s, i int) {
	(*G)[s].Visited[i] = true
	for _, t := range (*G)[s].edge {
		if !(*G)[t].Visited[i] {
			(*G)[t].dist[i] = (*G)[s].dist[i] + 1
			DFS(G, t, i)
		}
	}
}

func main() {
	sc.Split(bufio.ScanWords)

	N := scanInt()
	G := make(graph, N)
	for i := 0; i < N; i++ {
		G[i].edge = make([]int, 0)
	}

	for i := 0; i < N-1; i++ {
		a, b := scanInt()-1, scanInt()-1
		G[a].edge = append(G[a].edge, b)
		G[b].edge = append(G[b].edge, a)
	}
	DFS(&G, 0, 0)
	DFS(&G, N-1, 1)

	cnt := [2]int{0, 0}
	for i := 0; i < N; i++ {
		if G[i].dist[0] <= G[i].dist[1] {
			cnt[0]++
		} else {
			cnt[1]++
		}
	}

	if cnt[0] > cnt[1] {
		fmt.Println("Fennec")
	} else {
		fmt.Println("Snuke")
	}
}


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

int main(){
  int A,B,C,D;

  cin >> A >> B >> C >> D;

  if(A+B > C+D) cout << "Left" <<endl;
  else if(A+B < C+D) cout << "Right" << endl;
  else cout << "Balanced" << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i=0; i<(long long)(n); i++)
#define REP(i, k, n) for(long long i=(long long)(k); i<(long long)(n); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define PQ(T) priority_queue<T>
#define PQS(T) priority_queue<T, vector<T>, greater<T> >
#define deci cout << fixed << setprecision(15);
typedef long long ll;
const ll inf = 1020304050607080910;
const int mod = 1000000007;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
template<class T> bool chmin(T&x,T y){if(x>y){x=y;return true;}return false;}
template<class T> bool chmax(T&x,T y){if(x<y){x=y;return true;}return false;}
ll gcd(ll x,ll y){if(x>y)swap(x, y);while(x!=0){y%=x;swap(x, y);}return y;}
ll mpow(ll x,ll r){if(r==0)return 1;if(r%2==1){return x*mpow(x,r-1)%mod;}else{ll aa=mpow(x,r/2);return aa*aa%mod;}}

int N, M, f, num, s, deg[100000], used[100000];
vector<P> G[100000];

int main(){
	cin >> N >> M;
	rep(i, M){
		int a, b; cin >> a >> b;
		a--; b--;
		G[a].pb(P(b, i)); G[b].pb(P(a, i));
		deg[a]++; deg[b]++;
	}
	rep(i, N){
		if(deg[i] % 2 == 1){ cout << "No" << endl; return 0; }
		if(deg[i] >= 6) f = 1;
		if(deg[i] == 4){ num++; s = i; }
	}
	if(f || num > 2){
		cout << "Yes" << endl;
		return 0;
	}
	if(num < 2){
		cout << "No" << endl;
		return 0;
	}
	rep(i, 2){
		int now = s, cnt = 1, e;
		queue<int> que;
		vector<int> ind(N, 0);
		while(1){
			if(ind[now] != 0){
				M -= cnt - ind[now];
				rep(j, ind[now]-1){
					int aa = que.front(); que.pop();
					used[aa] = 0;
				}
				break;
			}else{
				ind[now] = cnt;
				cnt++;
				rep(j, G[now].size()){
					if(used[G[now][j].second]) continue;
					else{
						que.push(G[now][j].second);
						e = G[now][j].second;
						now = G[now][j].first;
						used[e] = 1;
						break;
					}
				}
			}
		}
	}
	cout << (M?"Yes":"No") << endl;
	return 0;
}


Measured memory_bytes: 9216
#include "stdio.h"
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main(int argc, char const *argv[]){
    int input; 
    int input_order[100];
    stack<int> train_stack;
    vector<int> order;

    while (~scanf("%d", &input)){
        if (input==0){
            cout<<train_stack.top()<<endl;
            train_stack.pop();
        }
        else{
            train_stack.push(input);
        }
    }
    return 0;
}

Measured memory_bytes: 3060
#include <string>
#include <iostream>
using namespace std;
int main(){
	int a, b, c;
	int Count = 0;
	cin >> a >> b >>c;
	if(a == b){
		Count += 1;
	}
	if(b == c){
		Count += 1;
	}
	if(c == a){
		Count += 1;
	}
	if(Count == 3){
		cout << 1 << endl;
	}
	if(Count == 1){
		cout << 2 << endl;
	}
	if(Count == 0){
		cout << 3 << endl;
	}
}

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

int main(){
	int n,i,a,b,j;
	while(cin >> n){
		for(i = 0;i < n;i++){
			cin >> a;
			cout << "Case " << i + 1 << ":" << endl;
			for(j = 0;j < 10;j++){
				a *= a;
				b = a / 100;
				b %= 10000;
				cout << b << endl;
				a = b;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define inf (int)1e18+7
#define mod (int)1e9+7
const int nmax = (int) 1e3 + 10;
         
bool grid[nmax][nmax];
int pr[nmax][nmax]; 

                     
signed main() {

    ios_base :: sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            char ch;
            cin >> ch;
            if ( ch == '.') grid[i][j] = 0;
            else grid[i][j] = 1;
        }
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            if ( i == j && i == 1) {
                pr[i][j] = 1;
                continue;
            } 
            if (grid[i][j]) continue;
            pr[i][j] = (grid[i - 1][j] == 1 ? 0 : pr[i - 1][j]) + (grid[i][j - 1] == 1 ? 0 : pr[i][j - 1]);
            pr[i][j] %= mod;
        }
    }                        

    cout << pr[n][m] << endl;
                                                                                                           

    return 0;
}

Measured memory_bytes: 9216
#include<stdio.h>

	int main(){
		long long int x;
		int n,m,i;
	
		while( scanf("%lld",&n) != EOF){
			m=600/n;
			x=0;
			
			for(i=1;i<=m;i++){
				x=x+(600-((long long)n)*((long long)i))*(600-((long long)n)*((long long)i))*n;
			}
			
			printf("%lld\n",x);
		}
	
	
	return 0;
}

Measured memory_bytes: 596
def solve(n):
    aaa = list(range(1, 2 * n + 1))
    print('?', *aaa[:n])
    l_res = input()
    l = 1
    r = n
    while l < r:
        m = (l + r) // 2
        print('?', *aaa[m:m + n])
        res = input()
        if res == '-1':
            exit()
        if l_res == res:
            l = m + 1
        else:
            r = m

    same_rb1 = aaa[l:l + n - 1]
    same_rb2 = aaa[:l - 1] + aaa[l + n:]
    ans = [''] * (2 * n)
    ans[l - 1] = l_res[0]
    ans[l + n - 1] = 'B' if l_res == 'Red' else 'R'
    for k in range(l - 1):
        print('?', k + 1, *same_rb1)
        res = input()
        ans[k] = res[0]
    for k in range(l + n, 2 * n):
        print('?', k + 1, *same_rb1)
        res = input()
        ans[k] = res[0]
    for k in range(l, l + n - 1):
        print('?', k + 1, *same_rb2)
        res = input()
        ans[k] = res[0]
    return ''.join(ans)


n = int(input())
print('!', solve(n))


Measured memory_bytes: 3532
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <cctype>
#include <fstream>
#include <complex>
#include <cmath>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define ITER(c) __typeof((c).begin())
#define PB(e) push_back(e)
#define FOREACH(i, c) for(ITER(c) i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define PARITY(n) ((n) & 1)

typedef long long ll;
typedef pair<ll, ll> P;
typedef complex<double> xy_t;
const int INF = 1000 * 1000 * 1000 + 7;
const double EPS = 1e-10;

bool ok(const vector<int> &xs, const vector<double> &vs){
  
  // lagrange interpolation
  double fv = 0;
  
  REP(i, xs.size() - 1){
    double t = 1;
    REP(j, xs.size() - 1)if(i != j){
      t *= (double)(xs.back() - xs[j]) / (xs[i] - xs[j]);
    }
    fv += vs[i] * t;
  }

  return abs(fv - vs.back()) < 1e-1;
}

int main(){
  int d;
  while(cin >> d && d){
    vector<double> val(d + 3);
    REP(i, d + 3) cin >> val[i];
    REP(i, d + 3){
      vector<double> vs;
      vector<int> xs;
      
      REP(j, d + 3) if(i != j){
	xs.push_back(j);
	vs.push_back(val[j]);
      }
      
      if(ok(xs, vs)){
	cout << i << endl;
	break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1260
#!/usr/bin/env python
# coding: utf-8

# In[16]:


N = int(input())
AB = []
for _ in range(N):
    AB.append(list(map(int, input().split())))


# In[17]:


x = 0
ans = 0
for i in reversed(range(N)):
    A,B = AB[i]
    b = -(-AB[i][0]//AB[i][1])*AB[i][1]
    if b-A >= x:
        ans += b-A-x
        x = b-A
    else:
        b = -(-(AB[i][0]+x)//AB[i][1])*AB[i][1]
        ans += b-A-x
        x = b-A
print(ans)


# In[ ]:






Measured memory_bytes: 27276
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

struct Dice{
	int me[6];
	Dice(int a[6]){
		for (int i = 0; i < 6; i++){
			me[i] = a[i];
		}
	}

};

int a[6];
string s;

int main(){
	REP(i, 6)cin >> a[i];
	Dice d(a);
	cin >> s;
	REP(i, s.size()){
		if (s[i] == 'N'){
			swap(d.me[0], d.me[1]);
			swap(d.me[1], d.me[5]);
			swap(d.me[5], d.me[4]);
		}
		else if (s[i] == 'E'){
			swap(d.me[0], d.me[3]);
			swap(d.me[3], d.me[5]);
			swap(d.me[5], d.me[2]);
		}
		else if (s[i] == 'W'){
			swap(d.me[0], d.me[2]);
			swap(d.me[2], d.me[5]);
			swap(d.me[5], d.me[3]);
		}
		else{
			swap(d.me[0], d.me[4]);
			swap(d.me[4], d.me[5]);
			swap(d.me[5], d.me[1]);
		}
	}
	cout << d.me[0] << endl;
}

Measured memory_bytes: 1204
#include<stdlib.h>
#include<string.h>
#include<stdio.h>

#define Error(s) {puts(s);exit(0);}
#define INT_MAX (0x3f3f3f3f)

typedef int QueueItem;
typedef struct Node* link;
struct Node {
  QueueItem element;
  link next;
};
link NewNode() {
  link p=(link)malloc(sizeof(Node));
  if(p==NULL)Error("Exhausted memory.");
  p->element=0;
  p->next=NULL;
  return p;
}

typedef struct Queue* queue;
struct Queue {
  link front,rear;
};

queue QueueInit() {
  queue Q=(queue)malloc(sizeof(Queue));
  if(Q==NULL)Error("Exhausted memory.");
  Q->front=Q->rear=0;
  return Q;
}

int QueueEmpty(queue Q) {
  return Q->front==NULL;
}

int QueueFull(queue Q) {
  link p=(link)malloc(sizeof(Node));
  int res=(p==NULL);
  free(p);
  return res;
}

QueueItem QueueFirst(queue Q) {
  if(QueueEmpty(Q))Error("Queue is empty");
  return Q->front->element;
}

void EnterQueue(QueueItem x,queue Q) {
  if(QueueFull(Q))Error("Queue is full");
  link p=NewNode();
  p->element=x;
  p->next=NULL;
  if(QueueEmpty(Q))Q->front=p;
  else Q->rear->next=p;
  Q->rear=p;
}

void DeleteQueue(queue Q) {
  if(QueueEmpty(Q))Error("Queue is empty");
  link p=Q->front;
  Q->front=Q->front->next;
  free(p);
}

int dirx[]={0,0,-1,1};
int diry[]={1,-1,0,0};
int n,m,K;
int **dis;
char **s;
queue queuex,queuey;

void read()
{
  scanf("%d%d%d",&n,&m,&K);
  s=(char**)malloc((n+1)*sizeof(char*));
  int i;
  for(i=1;i<=n;i++)
    s[i]=(char*)malloc((m+2)*sizeof(char));
  for(i=1;i<=n;i++)
    scanf("%s",s[i]+1);
}

void init()
{
  dis=(int**)malloc((n+1)*sizeof(int*));
  int i,j;
  for(i=1;i<=n;i++)
    dis[i]=(int*)malloc((m+1)*sizeof(int));
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      dis[i][j]=INT_MAX;
  queuex=QueueInit();
  queuey=QueueInit();
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      if(s[i][j] == 'S')
      {
        EnterQueue(i,queuex);
        EnterQueue(j,queuey);
        dis[i][j]=0;
      }
}

int min(int x,int y)
{
  return x < y ? x : y;
}

void work()
{
  int ans=INT_MAX;
  while(!QueueEmpty(queuex))
  {
    int x=QueueFirst(queuex);
    int y=QueueFirst(queuey);
    DeleteQueue(queuex);
    DeleteQueue(queuey);
    ans = min(ans,
        1 + (min(min(x - 1, n - x), min(y - 1, m - y)) + K - 1) / K);
    if(dis[x][y] == K) continue;
    // 四种方向的拓展
    int d;
    for(d=0;d<4;d++)
    {
      int nx=x+dirx[d];
      int ny=y+diry[d];
      if(1<=nx && nx<=n && 1<=ny && ny<=m && s[nx][ny]=='.')
        if(dis[nx][ny] > dis[x][y]+1)
        {
          // 更新距离
          dis[nx][ny] = dis[x][y] + 1;
          EnterQueue(nx,queuex);
          EnterQueue(ny,queuey);
        }
    }
  }
  printf("%d\n",ans);
}

int main()
{
  read();
  init();
  work();
  return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define poly vector<ll>
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=42;
char A[N][N];
ll dp1[N][N][N][N],dp2[N][N][N][N];
ll sol2(int a,int b,int c,int d);
ll sol1(int a,int b,int c,int d){
	if(dp1[a][b][c][d]!=-1)return dp1[a][b][c][d];
	ll ans=0;
	For(i,a,b)For(j,c,d)if(A[i][j]){
		ans+=sol2(a,i-1,i+1,b)*sol2(c,j-1,j+1,d);
	}
	return dp1[a][b][c][d]=ans;
}
ll sol2(int a,int b,int c,int d){
	if(a>b&&c>d)return 1;
	if(dp2[a][b][c][d]!=-1)return dp2[a][b][c][d];
	ll ans=0;
	For(i,a,b)For(j,c,d){
		ans+=sol1(a,i,j,d)*sol2(i+1,b,c,j-1);
	}
	return dp2[a][b][c][d]=ans;
}
int main(){
	memset(dp1,-1,sizeof(dp1)); memset(dp2,-1,sizeof(dp2));
	int n=read()*2;
	For(i,1,n)scanf("%s",A[i]+1);
	For(i,1,n)For(j,1,n)A[i][j]-='0';
	//For(i,1,n){For(j,1,n)wri(A[i][j]); puts("");}
	ll ans=0;
	For(i,2,n)if(A[1][i])ans+=sol2(2,i-1,i+1,n);
	cout<<ans<<endl;
}

Measured memory_bytes: 48896
import Control.Monad
import Data.Maybe
import Debug.Trace
import Data.List
import qualified Data.Map.Strict as Map
import qualified Data.IntMap.Strict as IntMap
import qualified Data.Set as Set
import qualified Data.IntSet as IntSet
import Data.Functor
import Data.Array

main :: IO ()
main = do
  n <- readLn
  as <- replicateM n $ readLn :: IO [Int]

  putStrLn $ if solve as then "first" else "second"

solve :: [Int] -> Bool
solve as
  | all (==1) as = True
  | n == 1 = (head as) `mod` 2 == 1
  | otherwise = not $ all (\x -> x `mod` 2 == 0) as 
  where 
    n = length as

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

int main(){

  int x[5],sum=0;
  for(int i = 0; i < 5 ; i++){
    cin >> x[i];
    if(x[i] < 40) sum += 40;
    else sum += x[i];
  }
  cout << sum / 5 << endl;


  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define int long long
int p=1000000007;

signed main() {
	int h,w;
	cin >> h >> w;
	char arr[h][w];
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin >> arr[i][j];
		}
	}
	int dp[h][w];
	dp[0][0]=1;
	for(int i=1;i<w;i++){
		if(arr[0][i]=='#'){
			dp[0][i]=0;
		}
		else{
			dp[0][i]=dp[0][i-1];
		}
	}
	for(int i=1;i<h;i++){
		if(arr[i][0]=='#'){
			dp[i][0]=0;
		}
		else{
			dp[i][0]=dp[i-1][0];
		}
	}
	for(int i=1;i<h;i++){
		for(int j=1;j<w;j++){
			if(arr[i][j]=='#'){
				dp[i][j]=0;
			}
			else{
				dp[i][j]=(dp[i-1][j]+dp[i][j-1])%p;
			}
		}
	}
	cout << dp[h-1][w-1];
	// your code goes here
	return 0;
}

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

int main(){
  int n;
  cin >> n;
  string ans="No";
  rep(i, 9){
    rep(j, 9){
      if((i+1)*(j+1)==n){
        ans="Yes";
        break;
      }
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
using namespace std;


#define li			long long int
#define rep(i,to)	for(int i=0;i<((int)(to));i++)
#define repp(i,start,to)	for(int i=(int)(start);i<((int)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define F first
#define S second
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl

int main(){
	li a[4], b[4];
	while(cin>>a[0]){
		li hit=0, blow=0;
		repp(i,1,4)cin>>a[i];
		rep(i,4)cin>>b[i];
		
		rep(i,4){
			bool found=false;
			rep(j,4){
				if(b[i]==a[j]){
					found=true;
					break;
				}
			}
			if(found){
				if(b[i]==a[i])hit++;
				else blow++;
			}
		}
		cout<<hit<<" "<<blow<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 1156
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 1
#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR
#endif


//改造
typedef long long int ll;
using namespace std;


//ここから編集する
ll mod = 1000000007;


int main() {
    int a,b;
    cin >> a >> b;
    int flag = -2;//0,-1,1
    if(a < 0 && b > 0){
        flag = 0;
    }else if(a > 0 && b > 0){
        flag = 1;
    }else if( a < 0 && b < 0){
        if(abs(a - b + 1) % 2 == 1){
            flag = -1;
        }else{
            flag = 1;
        }
    }
    if(flag == 1){
        cout << "Positive" << endl;
    }else if(flag == -1){
        cout << "Negative" << endl;
    }else if(flag == 0){
        cout << "Zero" << endl;
    }
}


Measured memory_bytes: 256