akhauriyash/Code-Regression huggingface dataset:
import numpy as np

nl = input().split(" ")
apple_aji = []

#欲しかった味の値
for tsumugi in range(int(nl[0])):
  apple_aji.append(int(nl[1]) + tsumugi)
  
apple_abs = np.abs(apple_aji)
apple_abs = apple_abs.tolist()
le_apple = apple_abs.index(min(apple_abs))

apple_aji[le_apple] = 0

aji = 0
for matsuri in range(len(apple_aji)):
  aji += apple_aji[matsuri]

print(aji)


Measured memory_bytes: 12500
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

//#define DEBUG
#ifdef DEBUG
#define debug_printf printf
#else
#define debug_printf 1 ? 0 : printf
#endif

typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pl;

#define FST first
#define SND second

const int MAX_N = 100000;                  // 10^5
// const int MAX_N = 100000;                  // 10^5
// const int MAX_N = 1000000000;              // 10^9
// const ll  MAX_N = 1000000000000000000;     // 10^18
// const int BASE  = 1000000000 + 7;          // 10^9 + 7
// const int INFI  = 1000000000 + 7;          // 10^9 + 7
// const ll INFL  = 1000000000000000000 + 7; // 10^18 + 7

class union_find {
private:
  static const int max_n = MAX_N;
  int par[max_n];
public:
  void init(int n) {
    for (int x = 0; x < n; x++) par[x] = x;
  }
  int find(int x) {
    return (par[x] == x)? x: par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) par[y] = x;
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

int N;
Pi X[MAX_N], Y[MAX_N];

void solve() {
  sort(X, X + N);
  sort(Y, Y + N);

  priority_queue<pair<int, Pi>, vector<pair<int, Pi>>, greater<pair<int, Pi>>> pq;
  for (int i = 0; i < N - 1; i++) {
    pq.push(make_pair(abs(X[i].FST - X[i + 1].FST), Pi(X[i].SND, X[i + 1].SND)));
    pq.push(make_pair(abs(Y[i].FST - Y[i + 1].FST), Pi(Y[i].SND, Y[i + 1].SND)));
  }

  union_find uf;
  uf.init(N);
  ll ans = 0;
  int cnt = 0;
  while(cnt < N && !pq.empty()) {
    auto edge = pq.top(); pq.pop();
    int u = edge.SND.FST, v = edge.SND.SND;
    if (!uf.same(u, v)) {
#ifdef DEBUG
      cout << u << " " << v << " " << edge.FST << endl;
#endif
      uf.unite(u, v);
      ans += edge.FST;
      cnt++;
    }
  }

  cout << ans << endl;
}

int main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    X[i].SND = Y[i].SND = i;
    cin >> X[i].FST >> Y[i].FST;
  }

  solve();

  return 0;
}


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

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

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

    return arr
a,b=map(int,input().split())
g=math.gcd(a,b)

if g==1:
    print(g)
else:
    arr=factorization(g)
    print(len(arr)+1)

Measured memory_bytes: 9296
#include <bits/stdc++.h>
using namespace std;
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;
}
typedef long long int ll;

#define EPS (1e-7)
#define INF (1 << 30)
#define LLINF (1LL << 60)
#define PI (acos(-1))
#define MOD (1000000007)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> x(n), y(n), h(n);
    for (ll i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i] >> h[i];
    }
    for (ll cx = 0; cx <= 100; cx++)
    {
        for (ll cy = 0; cy <= 100; cy++)
        {
            ll H;
            for (ll i = 0; i < n; i++)
            {
                if (h[i] > 0)
                {
                    H = h[i] + llabs(x[i] - cx) + llabs(y[i] - cy);
                    break;
                }
            }
            bool flg = true;
            for (ll i = 0; i < n; i++)
            {
                if (h[i] != max(H - llabs(x[i] - cx) - llabs(y[i] - cy), 0LL))
                {
                    flg = false;
                }
            }
            if (flg)
            {
                cout << cx << ' ' << cy << ' ' << H << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 256
#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;
int main() {
	int n; cin >> n;
	ll a[100000];
	rep(i, n) {
		cin >> a[i]; a[i]--;
	}
	ll ma = 0; ll sum = 0;
	rep(i, n) {
		ll p = ma + (ll)1;
		ll d = a[i] / p;
		sum += d;
		if (d == 0) {
			ma = max(ma, a[i] + (ll)1);
		}
		ma = max(ma, (ll)1);
	}
	cout << sum << endl;
	return 0;
}

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

using namespace std;

int main(void) {
	int n, k;
	cin >> n >> k;
	int ans = 1;
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			ans *= k;
		}
		else {
			ans *= k - 1;
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll n;
  cin >> n;
  vector<ll> v(n);
  for(int i = 0; i < n; i++){
    cin >> v[i];
    v[i] -= i;
  }
  sort(v.begin(), v.end());
  ll b = v[v.size() / 2];
  ll ans = 0;
  for(ll i: v)ans += abs(i - b);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <stack>
#include <bitset>
#include <utility>
#include<iomanip>
// #include <numeric>
using namespace std;



typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<ll> vint;
typedef vector<vector<ll>> vvint;
typedef vector<string> vstring;
typedef vector<vector<string>> vvstring;
typedef vector<char> vchar;
typedef vector<vector<char>> vvchar;
typedef vector<long double> vdouble;
typedef vector<vector<long double>> vvdouble;
typedef vector<vector<vector<long double>>> vvvdouble;
typedef pair<ll,ll> pint;
typedef vector<pint> vpint;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define INT_MAX 2147483647
#define LLONG_MAX 9223372036854775807
#define vmax(vec) *max_element(vec.begin(), vec.end())
#define vmin(vec) *min_element(vec.begin(), vec.end())
#define vsort(vec) sort(vec.begin(), vec.end())
#define vsortgr(vec) sort(vec.begin(), vec.end(), greater<ll>())
#define DIVIDER 1000000007


//
// struct Node{
//   vint children;
//   ll index;
//   ll prop;
// };



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

// ll X,Y,Z,K;
// ll pmax = 30000000000;
// vint A,B,C;




// int binary_search(int key){
//  //isOKを満たす要素のうち最小のインデックスを返す。（要ソート）
//   int left = -1;
//   int right = N;
//
//   while(right - left > 1){
//     int mid = left + (right - left)/2;
//
//     if(isOK(mid, key)) right=mid;
//     else left=mid;
//   }
//
//   return right;
// }

// ll gcd(ll m, ll n){
//   if(m<n) swap(m,n);
//   if(n==0) return m;
//   return gcd(n, m%n);
// }

// ll get_pow(ll x, ll y){
//   ll ret=0;
//   ll temp = y;
//   while(true){
//     if(x<=temp) break;
//     ret++;
//     temp *= 2;
//   }
//   return ret;
// }






int main() {
  cout<<fixed<<setprecision(10);

  string s;
  cin >> s;

  ll win = 0;
  ll lose = 0;

  string ans;

  rep(i,s.size()){
    if(s[i]=='o') win++;
    else lose++;
  }

  if(15-lose>=8) ans="YES";
  else ans="NO";

  cout << ans << endl;

}

















//


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, start, end) for(int i = start; i < end; i++)
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << (x) << endl;
typedef long long ll;
const int MAX = 999999999;

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

    cout << n / 3 << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
#include<stdlib.h>

#define SZ(v) ((int)v.size())
#define pb push_back
using namespace std;
typedef vector<int> VI;

const int N=200005;
VI li[N],id;
char s[N];
int n,m,L,ec,sum,mark[N];

void markit(){
	if(id.size()&3){
		fprintf(stderr,"SEGMENTION FAULT!");
		exit(1);
	}
	for(int i=0;i<<2<id.size();i++){
		for(int j:{0,1})for(int k:{0,1})mark[id[i<<2|j<<1|k]]=ec+k+1;
		ec+=2;
	}
}
void output(){
	puts("Yes");
	for(int i=0;i<L;i++){
		if(!mark[i])mark[i]=ec<0?-ec:++ec,ec=-ec;
		printf("%d ",mark[i]);
	}
	exit(0);
}

int main(){
	scanf("%d",&n);scanf("%s",s+1);s[0]='1';L=n<<1;
	for(int i=0,j;i<L;i++)if(s[i]=='0'&&s[(i+1)%L]=='1'){
		for(li[m].pb(i),j=(i+1)%L;s[j]=='1';j=(j+1)%L)li[m].pb(j);
		m++;
	}
	if(!m){
		if(~n&1){
			for(int i=0;i<L;i++)id.pb(i);
			markit();output();
		}else puts("No"),exit(0);
	}
	for(int i=0;i<m;i++)sum+=SZ(li[i])-2;
	if(sum&1)puts("No"),exit(0);
	if(sum&2){
		for(int i=0;i<m;i++)if(SZ(li[i])>2)li[m-1].swap(li[i]);
		for(int i=0;i<m-1;i++)if(SZ(li[i])>2){
			VI&a=li[i],&b=li[m-1];
			int la=SZ(a)-1,lb=SZ(b)-1,ea=a[la],eb=b[lb];
			mark[a[la-1]]=mark[b[lb-1]]=++ec;
			a.pop_back();b.pop_back();a.pop_back();b.pop_back();a.push_back(eb);b.push_back(ea);
			sum-=2;
			break;
		}
		if(sum&2)puts("No"),exit(0);
	}
	for(int i=0;i<m;i++){
		mark[li[i][0]]=ec+1+i;
		mark[li[i][SZ(li[i])-1]]=ec+1+(i+1)%m;
		for(int j=1;j<SZ(li[i])-1;j++)id.pb(li[i][j]);
	}
	ec+=m;markit();output();
	return 0;
}

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

#include <set>
#include <map>
#include <iomanip>

using namespace std;

#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define rrep(i, n) for(long long i = (long long)(n - 1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()

using ll = long long;

int main()
{
	map<string, int> mp;
	string s, t;
	int a, b;
	cin >> s >> t >> a >> b;

	mp[s] = a;
	mp[t] = b;

	string u;
	cin >> u;

	mp[u]--;

	cout << mp[s] << " " << mp[t] << endl;


	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n=0,c1=0,c3=0,c2=0;
int a1,a2;
int id(int a ,int b,int c){
    return a+b*a1+c*a2;
}
double pr(double a[],int p ,int q, int r){
    double n1 =n;
    double p1 =p;
    double q1 =q;
    double r1 =r;
    if(a[id(p,q,r)]!=-1)return a[id(p,q,r)];
    if((p==0)&&(q==0)&&(r==1)) return n1;
    double y =p1+q1+r1;
    double x = 0;
    if(p>0) x+=(p1/y)*(pr(a,p-1,q+1,r));
    if(q>0) x+=(q1/y)*(pr(a,p,q-1,r+1));
    if(r>0) x+=(r1/y)*(pr(a,p,q,r-1));
    //cout<<n<<" "<<y<<" "<<p<<" "<<q<<" "<<r<<" "<<x<<endl;
    x=x+n1/y;
    a[id(p,q,r)] = x;
    return x;
}
int main()
{
    scanf("%d",&n);
    c1=0;
    c2=0;
    c3=0;
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        if(x==3)c1++;
        if(x==2)c2++;
        if(x==1)c3++;
    }
    a1= c1+1;
    a2= (c1+1)*(c1+c2+1);
    double a[(c1+c2+c3+1)*(c2+c1+1)*(c1+1)];
    for(int i=0;i<=c1+c2+c3;i++){
        for(int j=0;j<c1+c2+1;j++){
            for(int k=0;k<=c1;k++)
                a[id(k,j,i)]=-1;
        }
    }
    printf("%.10f\n",pr(a,c1,c2,c3));
    return 0;
}


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

int main(){
  long long N, K;
  cin >> N >> K;
  map<int, long long> mp;
  for (int i=0; i<N; i++){
    int a,b;
    cin >> a >> b;
    mp[a] += b;
  }
  long long check = 0;
  for (auto itr = mp.begin(); itr != mp.end(); itr++){
    check += itr->second;
    if (check >= K){
      cout << itr->first << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 4224
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for i in range(N+1)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, '***'))

Measured memory_bytes: 48220
import java.util.Scanner;

public class Main{

 public static void main(String[] args) {
  // TODO 自動生成されたメソッド・スタブ
  Scanner scanner = new Scanner(System.in);

  // 整数nを取得
  int n = scanner.nextInt();
  // System.out.print(" ");

  for (int i = 1; i <= n; i++ ) {
  // 3の倍数
  if (i % 3 == 0) {
   System.out.print(" " + i);
  // 3を含む数字
  } else if (String.valueOf(i).contains("3")) {
   System.out.print(" " + i);
  }
  }
  System.out.println();
 }
}



Measured memory_bytes: 29240
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
	ll N,A,B;
	cin >> N >> A >> B;
	if((B-A)%2==0){
		cout << (B-A)/2;
	}else{
		cout << min(A+(B-A)/2,N-B+1+(B-A-1)/2);
	}
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1000000007; 
const int INF = 1000000000; //1e9
const int NIL = -1;
const long long LINF = 1000000000000000000; // 1e18
const double EPS = 1E-10;

template<class T, class S>
bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S>
bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}



int main(){
    int H, W; std::cin >> H >> W;
    std::vector<int> cnt(26, 0);
    {
        std::string a;
        for(int i(0); i < H; ++i){
            std::cin >> a;
            for(int j(0); j < W; ++j){
                ++cnt[a[j]-'a'];
            }
        }
    }
    int cnt1(0), cnt2(0);
    for(int i(0); i < 26; ++i){
        if(cnt[i] % 2){
            ++cnt1; --cnt[i];
        }
        if(!(cnt[i] % 2) && (cnt[i] % 4)) ++cnt2;
    }
    bool okay(true);
    int lim1((H % 2) & (W % 2)), lim2(0);
    if(H % 2) lim2 += W / 2;
    if(W % 2) lim2 += H / 2;
    if(cnt1 > lim1) okay = false;
    if(cnt2 > lim2) okay = false;
    std::cout << (okay ? "Yes" : "No") << std::endl;
    return 0;
}


Measured memory_bytes: 256
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

# # # # unionfind.py # # # #

# usage: uf = Unionfind(n) ; x = uf.root(y); uf.conn(a,b)

class Unionfind:

  def __init__(s,n):
    s.sz = [1] * n
    s.ances = [i for i in range(n)]

  def root(s,x):
    a = []
    y = x
    while s.ances[y] != y:
      a.append(y)
      y = s.ances[y]
    for z in a:
      s.ances[z] = y
    return y

  def conn(s,x,y):
    i = s.root(x)
    j = s.root(y)
    if i==j:
      return
    #k  = [i,j].min
    k  = j if (s.sz[i]<s.sz[j]) else i
    if k==j:
      s.ances[i] = j
    else:
      s.ances[j] = i
    s.sz[k] = s.sz[i] + s.sz[j]

# # # # end unionfind.py # # # #

n,m = inm()
uf = Unionfind(n)
for i in range(m):
    a,b = inm()
    uf.conn(a-1,b-1)
h = {}
x = 0
for i in range(n):
    r = uf.root(i)
    if r not in h:
        h[r] = 1
    else:
        h[r] += 1
    x = max(x,h[r])
print(x)


Measured memory_bytes: 113824
s = input()
n = len(s)
check = {"A", "C", "G", "T"}
ans = {0}
for i in range(n):
    tmp = s[i]
    if tmp not in check:
        continue
    ans.add(1)
    for j in range(i+1, n):
        if s[j] not in check:
            break
        tmp += s[j]
        ans.add(len(tmp))

print(max(ans))



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

int main(){
  int n;cin >> n;
  vector<int> a(n);rep(i,n)cin >> a[i];
  sort(a.begin(),a.end());
  cout << a[n/2] - a[n/2-1] << endl;
  return 0;
}


Measured memory_bytes: 640
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
  int x[10000];
  int i=0,j,a;
  scanf("%d",&a);
  while(a != 0){
    x[i] = a;
    i++;
    scanf("%d",&a);
  }
  for(j=0;j<i;j++){
    printf("Case %d: %d\n",j+1,x[j]);
  }
  return 0;
}

Measured memory_bytes: 2768
#a[i][j]
def da_generate(h,w,a):
    da = [[0]*w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1,w):
        da[0][i] = da[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j]+cnt_w
    return da

#da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
def da_calc(p,q,x,y,da):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]

n,m,q = map(int,input().split())
lrl = [[0 for i in range(n)] for j in range(n)]
for _ in range(m):
   l,r = map(int,input().split())
   lrl[l-1][r-1] += 1

da = da_generate(n, n, lrl)

for _ in range(q):
   p,q = map(int,input().split())
   p -= 1
   q -= 1
   print(da_calc(p,p,q,q,da))
   

Measured memory_bytes: 17368
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <algorithm>
#include <unordered_map>
#define int                long long
#define pb                 push_back
#define pi                 pair<int,int>
#define vi                 vector<int>
#define all(v)             v.begin(),v.end()
#define MOD                1000000007
#define F                  first
#define S                  second
#define FOR(i,r)           for(int i=0;i<r;i++)
#define REP(i,l,r)         for(int i=l;i<r;i++)
#define RER(i,l,r)         for(int i=l;i>=r;i--)
#define print(v)           for(auto i : v)cout << i << ' ';
#define FASTIO             ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mem(arr,k)         memset(arr,k,sizeof(arr));
#define pii                acos(-1.0)
#define PI                 3.1415926535897932385
#define Sin(a)             sin((pi*a)/180)
#define test()             int x;cin >> x;while(x--)
using namespace std;
set<int>res;
int32_t main(){

	FASTIO;
	queue<int>q;
	REP(i,1,10){
		q.push(i);
	}
	while(!q.empty()){
		int nd = q.front();
		q.pop();
		res.insert(nd);
		if(res.size()>1e5)
			break;
		int last = nd%10;
		if(last-1 >= 0)
			q.push(nd*10+(last-1));
		q.push(nd*10+last);
		if(last+1 <= 9)
			q.push(nd*10+(last+1));
	}
	int k;
	cin >> k;
	k--;
	for(auto i : res){
		if(k==0){
			cout << i << endl;
			return 0;
		}
		k--;
	}
    return 0;

}

Measured memory_bytes: 6656
#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
using namespace std;
const int N=1e6;
const long long mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
vector<int>g[N];
int dp[N][3];
int n,m,s,t;
int main(){
	//freopen("in.txt","r",stdin);
	me(dp,-1);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		sc("%d%d",&u,&v);
		g[u].push_back(v);
	}
	cin>>s>>t;
	queue<pair<int,int> >q;
	q.push({s,0});
	dp[s][0]=0;
	while(!q.empty()){
		int u=q.front().first;
		int x=q.front().second;
		q.pop();
		for(auto v:g[u]){
			int e=(x+1)%3;
			if(dp[v][e]>=0)continue;
			dp[v][e]=dp[u][x]+1;
			q.push({v,e});
		}
	}
	if(dp[t][0]>=0)dp[t][0]/=3;
	o(dp[t][0]);
}


Measured memory_bytes: 38528
#include <bits/stdc++.h>
using namespace std;
int n,num[101],used[10],size,flg[101];
string str[13];
int B[10];

int nxp(int idx,int i,int sum){
  if(sum<0||i==size) return sum==0;
  if(idx==n) return nxp(0,i+1,sum);
  
  int f=idx? -1:1,ch=str[idx][i],res=0;
  if(num[ch]!=-1) return nxp(idx+1,i,sum+f*(B[size-i-1]*num[ch]));
  for(int j=0;j<10;j++){
    if(used[j]||(!j&&flg[ch]))continue;
    used[j]=1,num[ch]=j;
    res+=nxp(idx+1,i,sum+f*(B[size-i-1]*j));
    used[j]=0,num[ch]=-1;
  }
  return res;
}
  
int solve(){
  str[0]='0'+str[0];
  size=str[0].size();
  for(int i=1;i<n;i++){
    if(size<str[i].size()) return 0;
    while(size>str[i].size()) str[i]='0'+str[i];
  }
  return nxp(0,0,0); 
}


int main(){
  B[0]=1;
  for(int i=1;i<10;i++)B[i]=B[i-1]*10;
  memset(num,-1,sizeof(num));
  num['0']=0;
  
  while(cin>>n,n){
    memset(flg,0,sizeof(flg));
    for(int i=0;i<n;i++){
      cin>>str[i];
      if(str[i].size()>1)flg[str[i][0]]=1;
    }
    swap(str[0],str[n-1]);
    cout <<solve()<<endl;
  }
  return 0;
}

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    long long m=1000;
    long long k=0;
    cin>>n;
    vector<long long>a(n);
    for(int i=0;i<n;i++){
        cin>>a.at(i);
    }
    for(int i=0;i<n-1;i++){
        if(a.at(i)<a.at(i+1)){
            k+=m/a.at(i);
            m%=a.at(i);
        }else{
            m+=a.at(i)*k;
            k=0;           
        }
    }
    if(k!=0){
        m+=a.at(n-1)*k;
    }
    cout<<m;
    
}

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

int main() {
  int M_1, D_1, M_2, D_2;
  cin >> M_1 >> D_1 >> M_2 >> D_2;

  if (M_1 != M_2) {
    cout << 1 << endl;
  } else {
    cout << 0 << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <fstream>
#include <queue>
#include <math.h>
#include <set>
#include <stdlib.h>
#include <time.h>
#include <list>

#define For(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  For(i,0,n)

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
#define chk(a) rep(i, a.size()) cout << a[i] << " "
#define SORT(c) sort((c).begin(),(c).end())
#define ll long long
#define vi(m,a) vector<int> m(a)
#define vti(m,a,i) vector<vector<int>> m(a,vector<int>(i))
#define ALL(it,a) for(auto it = a.begin(); it!=a.end(); it++)
#define Fe(it,a) for(auto &it : a)
#define all(a) begin(a),end(a)


using namespace std;
typedef pair<int, int> pii;
#define WARU 1000000007;

int main(void) {
	ll a, b; cin >> a >> b;
	if (a *b <= 0) {
		cout << "Zero" << endl;
	}
	else if (a > 0) {
		cout << "Positive" << endl;
	}
	else {
		if ((b - a) % 2 == 1) {
			cout << "Positive" << endl;
		}
		else {
			cout << "Negative" << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 256
n, k = list(map(int, input().split()))
v = list(map(int, input().split()))
ans = 0

from heapq import heappush, heappop
for i in range(1, k+1):
  for j in range(1, i+1):
    for k in range(0, j+1):
      minus = []
      l = min(n, k)
      r = min(n-l, j-l)
      cur = 0
      for ll in range(l):
        cur += v[ll]
        if v[ll]<0:
          heappush(minus, v[ll])
      for rr in range(r):
        cur += v[n-rr-1]
        if v[n-rr-1]<0:
          heappush(minus, v[n-rr-1])
      rm = i-l-r
      while rm>0 and len(minus)>=rm:
        rm -= 1
        t = heappop(minus)
        cur -= t
      ans = max(ans, cur)
print(ans)

Measured memory_bytes: 63836
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
void dfs(int now,int parent,int d,vector<vector<pair<int,int> > > &children,vector<int> &ans) {
    ans.at(now)=d;
    rep(i,children.at(now).size()) {
        if(children.at(now).at(i).first==parent) continue;
        dfs(children.at(now).at(i).first,now,d+children.at(now).at(i).second,children,ans);
    }
}

int main() {
    int n;
    cin>>n;
    vector<vector<pair<int,int> > >children(n);
    rep(i,n-1){
        int u,v,w;
        cin>>u>>v>>w;
        u--;v--;w%=2;
        children.at(u).push_back(make_pair(v,w));
        children.at(v).push_back(make_pair(u,w));
    }
    vector<int>ans(n);
    dfs(0,-1,0,children,ans);
    rep(i,n) cout<<ans.at(i)%2<<endl;
}


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

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

    sort(d, d+N);

    int n=0,m=0;
    for(int i=0; i<N; i++){
        if(d[i] != m){
            n++;
            m = d[i];
        }
    }

    cout << n << endl;
}


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

int main()
{
    int a[10005];
    int i,j,k,l=0,m,n;

    cin>>n;
    cin>>m;

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

    if(j>=0)
    {
        cout<<j<<endl;
    }
    else{
        cout<<"-1"<<endl;
    }
    return 0;
}


Measured memory_bytes: 3684
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmpArray = br.readLine().split(" ");
		int n = Integer.parseInt(tmpArray[0]);
		int m = Integer.parseInt(tmpArray[1]);
		
		int[] input = new int[n];
		tmpArray = br.readLine().split(" ");
		for(int i = 0; i < n; i++){
			input[i] = Integer.parseInt(tmpArray[i]);
		}
		
		Arrays.sort(input);
		int G = GCD(input);
		//System.out.println(G);
		
		//kが最大値以下かつGで割り切れればOK
		if(m <= input[input.length - 1] && m % G == 0){
			System.out.println("POSSIBLE");
		}
		else{
			System.out.println("IMPOSSIBLE");
		}

	}
		
	
	static int GCD (int[] array){
		//int[] copyArray = Arrays.copyOf(array, array.length);
		
		int result = array[0];
		for(int i = 0; i < array.length - 1 ; i++){
			result = GCD(result, array[i + 1]);
		}
		
		return result;
	}
	
	static int GCD (int a, int b){
		
		while(a != b){
			//System.out.println(a+" "+b);
			if(b > a){
				int tmp = a;
				a = b;
				b = tmp;
			}
			if(a%b == 0) {
				//System.out.println("result "+b);
				return b;
			}
			a = a%b;
		}
		//System.out.println("result "+a);

		return a;
	}

}


Measured memory_bytes: 35796
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    from fractions import gcd
    n = int(input())
    A = readInts()
    left = [0] * (n+1)
    right = [0] * (n+1)
    for i in range(1,n):
        left[i] = gcd(left[i-1],A[i-1])
    for i in range(n-2,-1,-1):
        right[i] = gcd(right[i+1],A[i+1])
    # 全部で探索してみるべ
    res = 0
    for i in range(n):
        l = left[i]
        r = right[i]
        res = max(res,gcd(l,r))
    print(res)
if __name__ == '__main__':
  main()


Measured memory_bytes: 16128
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

template <class T>
class UnionFindTree
{
private:
    const int n;
    vector<pair<int, T> > parent; // 親ノード
    vector<int> rank;             // 木の高さの上限

    pair<int, T> find(int x){
        if(parent[x].first == x){
            return parent[x];
        }else{
            pair<int, T> p = find(parent[x].first);
            p.second += parent[x].second;
            return parent[x] = p;
        }
    }
public:
    UnionFindTree(int n) : n(n){ // コンストラクタ
        parent.resize(n);
        for(int i=0; i<n; ++i)
            parent[i] = make_pair(i, 0);
        rank.assign(n, 0);
    }
    bool unite(int a, int b, T diff){ // aとbのグループを併合
        pair<int, T> x = find(a);
        pair<int, T> y = find(b);
        a = x.first;
        b = y.first;
        if(a != b){
            if(rank[a] < rank[b]){
                parent[a] = make_pair(b, y.second - x.second + diff);
            }else{
                parent[b] = make_pair(a, x.second - y.second - diff);
                if(rank[a] == rank[b])
                    ++ rank[a];
            }
            return true;
        }
        else{
            return x.second - y.second == diff;
        }
    }
    pair<bool, T> getDiff(int a, int b){ // aとbの値の差を調べる
        pair<int, T> x = find(a);
        pair<int, T> y = find(b);
        if(x.first == y.first)
            return make_pair(true, x.second - y.second);
        else
            return make_pair(false, 0);
    }
};

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

    UnionFindTree<int> uft(n);
    for(int i=0; i<m; ++i){
        int l, r, d;
        cin >> l >> r >> d;
        -- l;
        -- r;
        if(!uft.unite(l, r, d)){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}


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

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		in.close();
		int mod = 1000000007;
		List<Integer> list = new ArrayList<>();
		for(int i=2;i*i<=m;i++) {
			int count = 0;
			while(m%i==0) {
				m /= i;
				count++;
			}
			if(count!=0) {
				list.add(count);
			}
		}
		if(m>1) list.add(1);
		long ans = 1;
		for(int q : list) {
			ans = (ans * comb(n+q-1,q,mod)) % mod;
		}
		System.out.println(ans);
		

	}
	
	//return pCq % r
	public static long comb(int p,int q,int mod) {
		long[] array = new long[q];
		for(int i=0;i<q;i++) {
			array[i] = p - i;
		}
		List<Integer> list = new ArrayList<>();
		for(int num=2;num<=q;num++) {
			int x = num;
			for(int i=2;i*i<=x;i++) {
				while(x%i==0) {
					x /= i;
					list.add(i);
				}
			}
			if(x>1) list.add(x);
		}
		
		for(int num : list) {
			for(int i=0;i<q;i++) {
				if(array[i]%num==0) {
					array[i] /= num;
					break;
				}
			}
		}
		
		long ans = array[0] % mod;
		for(int i=1;i<q;i++) {
			ans = (ans * (array[i] % mod))%mod;
		}
		return ans;	
	}

}


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

    int h,w;
    cin>>h>>w;
    vector<string>grid(h);
    for(int i=0;i<h;i++) cin>>grid[i];

    queue<pair<int,int>>q;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++) {
            check[i][j]=-1;
            if(grid[i][j]=='#'){
             q.push({i,j});
             check[i][j]=0;
            }
        }
    }
    int cnt=0;
    while(!q.empty())
    {
        int n=q.size();
       // cerr<<q.size()<<endl;
        for(int i=0;i<n;i++){
        int y=q.front().first;
        int x=q.front().second;
        q.pop();
        for(int dx=-1;dx<=1;dx++){
            for(int dy=-1;dy<=1;dy++){
                if( 0<=y+dy && y+dy<h && 0<=x+dx && x+dx<w &&  dx*dx+dy*dy==1 && check[y+dy][x+dx]==-1){
                    q.push({y+dy,x+dx});
                    check[y+dy][x+dx]=0;
                }
            }
        }
    }
    cnt++;
    }
    cout<<cnt-1<<endl;
    return 0;
}

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


using namespace std;

int main(){
long N;
cin>>N;
vector<long> v(N);
for (auto &&x : v)
{
    cin>>x;
}
long ans=0;

sort(v.begin(),v.end());

for (long i = 0; i < N-2; i++)
{
    for (long k = i+1; k < N-1; k++)
    {
        for (long m = k+1; m < N; m++)
        {
            if(v[i]<v[k]+v[m]&&v[k]<v[i]+v[m]&&v[m]<v[i]+v[k]){
                ans++;
            }else{
                break;
            }
        }
        
    }
    
}
cout<<ans<<endl;
    

}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {

	int MOD = 1_000_000_007;
	int INF = Integer.MAX_VALUE / 3;
	int ALPH = 26;
	
	void solve() {
		char[] s = in.nextToken().toCharArray();
		int n =s.length;
		int[] dp = new int[n];
		int[] last = new int[ALPH];
		int[] lastPos = new int[ALPH];
		Arrays.fill(lastPos, n);
		int[] next = new int[n];
		int[] nextChar = new int[n];
		
		for (int i = n - 1; i >= 0; i--) {
			int code = s[i] - 'a';
			dp[i] = INF;
			for (int j = 0; j < ALPH; j++) {
				if (last[j] + 1 < dp[i]) {
					dp[i] = last[j] + 1;
					next[i] = lastPos[j];
					nextChar[i] = j;
				}
			}
			last[code] = dp[i];
			lastPos[code] = i;
		}
		
		int best = -1, bestPos = -1;
		for (int i = 0; i < ALPH; i++) {
			if (best == -1 || last[i] < last[best]) {
				best = i;
				bestPos = lastPos[best];
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append((char) (best + 'a'));
		while (bestPos < n) {
			sb.append((char) (nextChar[bestPos] + 'a'));
			bestPos = next[bestPos];
		}
		out.println(sb.toString());
	}

	FastScanner in;
	PrintWriter out;

	void run() {
		in = new FastScanner();
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public FastScanner(String s) {
			try {
				br = new BufferedReader(new FileReader(s));
			} catch (FileNotFoundException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}

		public String nextToken() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
				}
			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextToken());
		}

		public long nextLong() {
			return Long.parseLong(nextToken());
		}

		public double nextDouble() {
			return Double.parseDouble(nextToken());
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}


Measured memory_bytes: 27604
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef list<ll> listl;
typedef string str;

#define min(A, B) min(static_cast<ll>(A), static_cast<ll>(B))
#define max(A, B) max(static_cast<ll>(A), static_cast<ll>(B))

#define rep(i, max) for(ll i = 0, i_max = max; i < i_max; i++)

void in(ll& I)
{
	cin >> I;
}

void in(vl& I)
{
	for (auto& i : I)
	{
		cin >> i;
	}
}

void in(listl& I)
{
	for (auto& i : I)
	{
		cin >> i;
	}
}

void in(str& s)
{
	cin >> s;
}

void out(ll& O)
{
	cout << O;
}

void out(ll O)
{
	cout << O;
}

void out(vl& O)
{
	for (auto& o : O)
	{
		cout << o;
	}
}

bool comp(pair<ll, ll> lh, pair<ll, ll> rh)
{
	return lh.second < rh.second;
}

void OutResult(bool b, str True, str False)
{
	if (b)
	{
		cout << True.c_str();
	}
	else
	{
		cout << False.c_str();
	}
}

int main()
{
	ll N;
	in(N);

	list<pair<ll, ll>> L;

	for (int i = 0; i < N; i++)
	{
		ll A, B;
		in(A);
		in(B);
		L.push_back(make_pair(A, B));
	}

	L.sort(comp);

	bool b = true;

	ll Time = 0;

	for (auto& l : L)
	{
		if (l.second < Time + l.first)
		{
			b = false;
			break;
		}
		Time += l.first;
	}

	OutResult(b, "Yes", "No");

	return 0;
}

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

int distt[301];
int dists[301];

int main() {
	int N, s, t;
	cin >> N >> s >> t;
	vector<pair<int, int>> K;
	cout << "? " << s << " " << t << endl;
	cin >> distt[s];
	dists[t] = distt[s];
	for(int n = 1; n <= N; n++) {
		if (n == s or n == t) continue;
		cout << "? " << s << " " << n << endl;
		cin >> dists[n];
		cout << "? " << t << " " << n << endl;
		cin >> distt[n];
		if (distt[n] + dists[n] == distt[s]){
			K.push_back(make_pair(dists[n], n));
		}
	}
	sort(K.begin(), K.end());
	vector<int> ans;
	ans.push_back(s);
	for(int i = 0; i < K.size(); i++) {
		int q = (int)ans.size();
		q -= 1;
		int p = K[i].second;
		cout << "? " << ans[q] << " " << p << endl;
		int an;
		cin >> an;
		if (dists[ans[q]] + an + distt[p] == distt[s]) {
			ans.push_back(p);
		}
	}
	ans.push_back(t);
	cout << "! ";
	for(int i = 0; i < ans.size(); i++) {
		if (i + 1==ans.size()) cout << ans[i] << endl;
		else cout << ans[i] << " ";
	}
}


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

using namespace std;

int main() {
  int a, b, m;
  cin >> a >> b >> m;
  vector<int> ref(a), ran(b);
  for (int i=0; i<a; ++i) cin >> ref.at(i);
  for (int i=0; i<b; ++i) cin >> ran.at(i);
  int min_ref = 1e9, min_ran = 1e9;
  for (int i=0; i<a; ++i) if (ref.at(i) < min_ref) min_ref = ref.at(i);
  for (int i=0; i<b; ++i) if (ran.at(i) < min_ran) min_ran = ran.at(i);
  
  int res = min_ref + min_ran;
  for (int i=0; i<m; ++i) {
    int x, y, c;
    cin >> x >> y >> c;
    int tmp = ref.at(x-1) + ran.at(y-1) - c;
    if (tmp < res) res = tmp;
  }
  
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<cmath>
#include<vector>
#define N 999999

using namespace std;

vector<int> MakePrimeNumber(void);

int main(){
  int i, j, a, d, n, count;
  vector<int> data;

  data = MakePrimeNumber();

  while(1){
    cin >> a >> d >> n;
    if(a == 0 && d == 0 && n == 0) break;

    i = a;
    j = 0;
    count = 0;
    while(1){
      if(i == data[j]){
	++count;
	if(count == n) break;
	i += d;
	++j;
      }else if(i < data[j]){
	i += d;
      }else{
	++j;
      }
    }

    cout << i << endl;
  }
  return 0;
}

vector<int> MakePrimeNumber(void){
  int i, j, k;
  vector<int> data;

  data.push_back(2);
  data.push_back(3);
  for(i=5; i<=N; i+=2){
    for(j=1, k=0; data[j]<=sqrt(i); ++j){
      if(i%data[j] == 0){
        k = 1;
        break;
      }
    }
    if(k == 0) data.push_back(i);
  }
  return data;
}

Measured memory_bytes: 1344
import std.stdio;
import std.conv;
import std.array;
import std.string;

uint[] readArray(uint n) {
	auto a = new uint[n];

	foreach (ref e;a) {
		uint u;
		readf(" %s", &u);
		e = u;
	}

	return a;
}

void main() {
	auto nk = readln.chomp.split(" ");
	auto n = nk[0].to!uint;
	auto k = nk[1].to!uint;

	auto p = readArray(n);
	uint sum = 0;

	foreach (e;p[0..k]) {
		sum += e;
	}
	auto max = sum;
	sum -= p[0];

	for (uint i = 1;i + k <= p.length;++i) {
		sum += p[i + k - 1];

		if (sum > max) {
			max = sum;
		}

		sum -= p[i];
	}

	writefln("%.12f", (cast(real)max + k) / 2);
}


Measured memory_bytes: 2812
#include<iostream>
using namespace std;
int main()
{
    int h,w;
    cin >> h >> w;
    while(h!=0)
    {
        int i,j;
        for(i=0;i<h;i++)
        {
            for(j=0;j<w;j++)
            {
                if((i%2==0&&j%2==0||i%2==1&&j%2==1))
                cout << "#";
                else cout << ".";
            }
            cout << endl;
        }
        cout << endl;
        cin >> h >> w;
    }
    return 0;
}


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

int main(){
	int n,i,j,cnt;
	char str[100000],str2[100000];
	for(j = 0;j < 10000;j++) str2[j] = 0;
	while(1){
		cnt = 1;
		scanf("%d",&n);
		if(!n) break;
		scanf("%s",str);
		for(i = 0;i < n;i++){
			for(j = 0;str[j] != 0;j++){
				if(str[j] == str[j + 1]) cnt++;
				else{
					sprintf(str2,"%s%d%c",str2,cnt,str[j]);
					cnt = 1;
				}
			}
			strcpy(str,str2);
			for(j = 0;j < 10000;j++) str2[j] = 0;
		}
		printf("%s\n",str);
	}
	return 0;
}

Measured memory_bytes: 712
#include<iostream>
#include<cmath>
using namespace std;
int main() {
	int N = 0;
	cin >> N;
	int check = 0;
	while (1) {
		if (pow(2, check) > N) {
			check--;
			break;
		}
		check++;
	}
	cout << pow(2, check) << endl;
	return 0;
}

Measured memory_bytes: 4200
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

const ll mod = 1e9 + 7;
#define INF 1e16

struct edge{ll to,cost;};
 
void dijkstra(vector<vector<edge> > &graph, VL &d, VL &way, ll s){
    ll n = graph.size();
    fill(ALL(d), INF);
    fill(ALL(way), 0);
    d[s] = 0;
    way[s] = 1;
    priority_queue<PL, vector<PL>, greater<PL> > q;
    q.push(PL(0, s));
    while (!q.empty()){
        PL a = q.top();
        q.pop();
        ll now = a.second;
        if(d[now] < a.first) continue;
        REP(i,graph[now].size()){
            edge e = graph[now][i];
            ll next = e.to;
            if (d[next] == d[now] + e.cost){
                way[next] = (way[next] + way[now]) % mod;
            }
            if (d[next] > d[now] + e.cost){
                way[next] = way[now];
                d[next] = d[now] + e.cost;
                q.push(make_pair(d[next], next));
            }
        }
    }
}

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

    vector<vector<edge> > graph(n);
    REP(_,m){
        ll u, v, d;
        scanf("%lld %lld %lld", &u, &v, &d);
        u--;v--;
        graph[u].push_back((edge){v, d});
        graph[v].push_back((edge){u, d});
    }

    VL d1(n), way1(n), d2(n), way2(n);
    dijkstra(graph, d1, way1, s);
    dijkstra(graph, d2, way2, t);

    // REP(i,n){
    //     cout << d1[i] << " " << way1[i] << "   " << d2[i] << " " << way2[i] << endl;
    // }

    ll dmin = d1[t];
    ll ans = (way1[t] * way1[t]) % mod;

    REP(i,n){
        if (2 * d1[i] < dmin){
            for (edge e : graph[i]){
                ll next = e.to;
                if (2 * d2[next] < dmin && d1[i] + d2[next] + e.cost == dmin){
                    ll tmp = (way1[i] * way2[next]) % mod;
                    tmp = (tmp * tmp) % mod;
                    ans = (ans - tmp + mod) % mod;
                }
            }
        }
        if (2 * d1[i] == dmin){
            if (d1[i] + d2[i] == dmin){
                ll tmp = (way1[i] * way2[i]) % mod;
                tmp = (tmp * tmp) % mod;
                ans = (ans - tmp + mod) % mod;
            }
        }
    }

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


Measured memory_bytes: 18772