akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

struct Card{
  char suit;
  char value;
};

int main(){
  struct Card C1[101], C2[101],CC;
  int n, i,j,mini,flag=0;
  char ch;

  scanf("%d%c", &n, &ch);
  
  for ( i = 0; i < n; i++ ){
    scanf("%c%c%c", &C1[i].suit, &C1[i].value, &ch);
  }

  for(i=0;i<n;i++) C2[i]=C1[i];

  for(i=0;i<=n-1;i++){
    for(j=n-1;j>=i+1;j--){
      if(C2[j].value < C2[j-1].value){
	CC=C2[j];
	C2[j]=C2[j-1];
	C2[j-1]=CC;
      }
    }
  }
  for(i=0;i<n;i++)
    {
    if(i>0) printf(" ");
    printf("%c%c",C2[i].suit,C2[i].value);
  }
  printf("\n");
  printf("Stable\n");

  for(i=0;i<=n-1;i++){
    mini=i;
    for(j=i;j<=n-1;j++){
      if(C1[j].value < C1[mini].value){
	mini=j;
      }
    }
    CC=C1[i];
    C1[i]=C1[mini];
    C1[mini]=CC;
  }
  for(i=0;i<n;i++)
    {
    if(i>0) printf(" ");
    printf("%c%c",C1[i].suit,C1[i].value);
    if(!(C1[i].suit == C2[i].suit && C1[i].value == C2[i].value)) flag = 1;
  }
  printf("\n");

  if(flag == 1)
    {
    printf("Not stable\n");
    }
  else printf("Stable\n");



  return 0;
}

Measured memory_bytes: 612
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
const int MOD = 1000000007;

int main()
{
  string A,B;
  int C=0;
  cin >> A >> B;
  A = A + B;
  REP(i,A.size()){
    C *= 10;
    C += A[i]-'0';
  }
  for(int i=1;i<=C;i++){
    if(i*i == C){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}



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

using ll = long long;
using namespace std;
using pii = pair<int, int>;

int INF = 1000000000;
int n, x;
std::vector<std::vector<pii>> g;
priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;
std::vector<int> dist;
std::vector<bool> used;

int main() {
    std::cin >> n;
    dist.assign(n, INF);
    used.assign(n, false);
    g.assign(n, std::vector<pii>(0));
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            std::cin >> x;
            if (x == -1) {
                continue;
            }
            g[i].push_back(make_pair(x, k));
        }
    }
    pq.push(std::make_pair(0, 0));
    used[0] = true;
    dist[0] = 0;
    while (!pq.empty()) {
        auto e = pq.top();
        pq.pop();
        used[e.second] = true;
        for (int i = 0; i < g[e.second].size(); i++) {
            if (used[g[e.second][i].second] == false && dist[g[e.second][i].second] > g[e.second][i].first) {
                dist[g[e.second][i].second] = g[e.second][i].first;
                pq.push(g[e.second][i]);
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < dist.size(); i++) {
        ans += dist[i];
    }
    std::cout << ans << std::endl;
}



Measured memory_bytes: 3216
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<cstdio>
#define MAXA 100000
#define MAX 2000000000
#define s(i) scanf("%d", &(i))
#define p(i) printf("%d", (i))
#define ps() printf(" ") 
#define rer(i,j,k) for((i)=(j);(i)<(k);++(i))
#define ret(i,j,k) for((i)=(j);(i)>(k);--(i))
using namespace std;
int A[MAXA] = {0}, B[MAXA] = {0}; 
int main(){
	int i, n;
	long long sum = 0;
	cin >> n;
	rer(i,0,n+1){
		cin >> A[i];
	}
	rer(i,0,n){
		cin >> B[i];
	}
	rer(i,0,n){
		if(B[i] < A[i]){
			sum += B[i];
		}else if(B[i] >= A[i]){
			sum += A[i];
			if(A[i+1] >= (B[i] - A[i])){
				sum += (B[i] - A[i]);
				A[i+1] -= (B[i] - A[i]);
			}else{
				sum += A[i+1];
				A[i+1] = 0;
			}
			
		}
	}
	cout << sum << endl;;
	return 0;
} 


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)
#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a)  (a).rbegin(),(a).rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int MOD = 1000000007;
const double PI = acos(-1); //3.14~
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int A = 1, G = 2, C = 3, T = 4;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main()
{
    int N; cin >> N;
    auto dp = make_vec<ll>(N + 1, 5, 5, 5);
    dp[0][0][0][0] = 1;
    rep(n, N)
    {
        rep(i, 5) // i 3文字前
        {
            rep(j, 5) // j　2文字前
            {
                rep(k, 5) //k 1文字前
                {
                    Rep(l, 1, 5) //l 選ぶ文字 dammyは無し
                    {
                        if (i == A && j == G && l == C) continue; //AG*C
                        if (i == A && k == G && l == C) continue; //A*GC
                        if (j == A && k == G && l == C) continue; //AGC
                        if (j == G && k == A && l == C) continue; //GAC
                        if (j == A && k == C && l == G) continue; //ACG
                        dp[n + 1][j][k][l] += dp[n][i][j][k];
                        dp[n + 1][j][k][l] %= MOD;
                    }
                }
            }
        }
    }
    ll ans = 0;
    Rep(i, 1, 5)
    {
        Rep(j, 1, 5)
        {
            Rep(k, 1, 5)
            {
                ans += dp[N][i][j][k];
                ans %= MOD;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>
#include <algorithm>

#define rep(i,st,ed) for (int i=st;i<=ed;++i)

typedef long long LL;

int main(void) {
	LL n,k; scanf("%lld%lld",&n,&k);
	LL t1=n/k;
	if (k&1) printf("%lld\n", t1*t1*t1);
	else {
		LL t2=((n-k/2)/k)+1;
		if (n%k>=k/2) t2=t1+1;
		else t2=t1;
		printf("%lld\n", t1*t1*t1+t2*t2*t2);
	}
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define int long long
#define DEBUG(x) // cerr << #x << " = " << x << endl
constexpr int MOD = 1000000007;
int dp[4001][2001];
int comb(int n, int k) {
    if(k < 0 || k > n) return 0;
    if(n == 0) return 1;
    if(dp[n][k] > 0) return dp[n][k];
    return dp[n][k] = (comb(n-1, k-1) + comb(n-1, k)) % MOD;
}
int mchoose(int n, int m) {
  return comb(n + m - 1, m - 1);
}
signed main() {
  memset(dp, 0, sizeof(dp));
  int N, K; cin >> N >> K;
  for (int i = 1; i <= K; i++) {
    int ans = 0;
    int t = comb(K - 1, i - 1);
    if (i == 1) {
      ans = t * mchoose(N - K, 2);
      ans %= MOD;
    } else {
      for (int j = i - 1; j <= N - K; j++) {
        int t2 = t;
        int p;
        p = mchoose(N - K - j, 2);
        DEBUG(p);
        t2 *= p;
        t2 %= MOD;
        p = comb(j - 1, i - 1 - 1);
        DEBUG(p);
        t2 *= p;
        t2 %= MOD;
        ans += t2;
        ans %= MOD;
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 62848
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            boolean[] used = new boolean[14];
            boolean ans = false;
            for (int i = 0; i < 6; i++) {
                used[sc.nextInt()] = true;
            }
            if (used[1] == used[13])
                ans = !used[1];
            else {
                int[] r = { 6, 8 };
                boolean t = false;
                for (;;) {
                    int a = t == used[1] ? 1 : 0;
                    int b = (a + 1) % 2;
                    if (used[r[a]] ^ t)
                        r[a] += a == 1 ? 1 : -1;
                    else if (used[r[b]] ^ t)
                        r[b] += b == 1 ? 1 : -1;
                    if (r[1] == 13 || r[0] == 1) {
                        ans = used[1] ^ r[1] == 13;
                        break;
                    }
                    t = !t;
                }
            }
            System.out.println(ans ? "yes" : "no");
        }
    }
}


Measured memory_bytes: 28492
#include <bits/stdc++.h>
#define ll long long
#define arena ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;

int main() 
{
    ll n;
    cin>>n;
    ll arr[n];
    for(ll i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    ll flag=0;
    for(ll i=0;i<n;i++)
    {
        if(arr[i]%2==0)
        {
        if(arr[i]%3!=0&&arr[i]%5!=0)
        {
            flag=1;
            break;
        }
        }
    }
    if(flag==1)
    {
        cout<<"DENIED";
        return 0;
    }
    
    cout<<"APPROVED";
}

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

int main(){
	int n,m;
	cin>>n>>m;
	vector<vector<int>> edge(n,vector<int>(n,1e8));
	for(int i=0;i<m;i++){
		long long int a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		edge[a][b]=c;
		edge[b][a]=c;
	}
	vector<vector<int>> d=edge;
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	int res=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(edge[i][j]!=1e8){
				if(d[i][j]<edge[i][j]){
					res++;		
				}
			}
		}
	}
	cout<<res/2<<endl;
	return 0;
}


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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
 
  if (A + B > C + D) {
    cout << "Left" << endl;
  }
  if (A + B < C + D) {
    cout << "Right" << endl;
  }
  if (A + B == C + D) {
    cout << "Balanced" << endl;
  }
}

Measured memory_bytes: 3632
inf = 1e10
n,m = map(int,raw_input().split())
edge = [map(int,raw_input().split()) for i in range(m)]
d = [inf]*n
d[0] = 0
while 1:
	update = False
	for i in range(m):
		a,b,c = edge[i]
		if d[a] != inf and d[b] > d[a] - c:
			d[b] = d[a] - c
			update = True
	if not update: break
print abs(d[n-1])

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

int main() {
    int N;cin>>N;
    int mini=N+1;
    int ans=0;
    for (int i = 0; i < N; i++){
        int P;cin>>P;
        if(P<=mini)ans++;
        mini=min(mini,P);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3604
#include <stdio.h>
#include <limits.h>

int main(void) {
    long long l, r, i, j, min = LLONG_MAX;
    scanf("%lld%lld", &l, &r);
    if ( l / 2019 == r / 2019 ) {
        for ( i = l; i <= r -1; i++ ) {
            for ( j = i + 1; j <= r; j++ ) {
                if ( (i * j) % 2019 < min ) {
                    min = (i * j) % 2019;
                }
            }
        }
        printf("%lld\n", min);
    }
    else {
        if ( r / 2019 - l / 2019 > 1 ) {
            printf("0\n");
        }
        else {
            if ( l % 2019 == 0 || r % 2019 == 0 ) {
                printf("0\n");
            }
            else {
                for ( i = l; i <= r -1; i++ ) {
                    for ( j = i + 1; j <= r; j++ ) {
                        if ( (i * j) % 2019 < min ) {
                            min = (i * j) % 2019;
                        }
                    }
                }
                printf("%lld\n", min);
            }
        }
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define vec vector
#define rep(i,n) for (int i=0; i<(n); i++)
#define reps(i,s,n) for (int i=(s); i<(n); i++)
#define rep1(i,n) for (int i=1; i<=(n); i++)
#define repr(i,s,n) for (int i=(s)-1; i>=(n); i--)
#define print(a) cout << a << endl
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()


int main() {
  int D,T,S;
  cin >> D >> T >> S;
  print(((S*T>=D)?"Yes":"No"));
  return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <sstream>
#include <numeric>
#define INF 2000000000
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define sym cout<<"---------"<<endl;
#define ll long long
#define PL pair<long long, long long>
#define P pair<int,int>
#define mk make_pair
#define en endl
#define WHITE 0
#define BLACK 2
#define GRAY 1
#define RE return 0
#define int ll

signed main(){
  int n,k;
  cin>>n>>k;
  
  int ans=0;
  for(int i=1; i<=n; i++){
    int amari_=i%k;
    int amari=k-amari_;
    if(amari*2%k!=0) continue;
    else{
      ans++;
      ans+=(i-1)/k*3;
      ans+=(n-i)/k*3;
      ans+=(n-i)/k*((i-1)/k)*6;
    }
  }
  cout<<ans<<en;
}



Measured memory_bytes: 256
n=input()
a=[int(i) for i in input().split()]
a.sort(reverse=True)


x1=0
x2=0
i0=0
for i in a:
  if i==i0 and x1==0 and x2==0:
    x1=i
    i0=0
  elif i==i0 and x2==0:
    x2=i
    i0=0
  else:
    i0=i
print(x1*x2)

Measured memory_bytes: 14244
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------

int main(void){
    string s, t;
    cin >> s >> t;

    cout << t + s << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(),(x).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> P;


template<typename T>
void dump(T *arr, int h, int w){
	rep(i,h){
		rep(j,w) cout << arr[i][j] << "\t";
		cout << "\n";
	}
}

template<typename T>
void dump(T *arr, int a){
	rep(i,a) cout << arr[i] << "\t";
	cout << "\n";
}

const int INF = 1e9;
const int MOD = 1e9+7;

bool compare(P a, P b){
	if(a.second != b.second) return a.second > b.second;
	else	return a.first > b.first;
}

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

	int n,m;
	cin >> n >> m;

	vector<P> p;
	int a,b;
	rep(i,n){
		cin >> a >> b;
		if(a > m) continue;
		p.push_back(P(a,b));
	}
	sort(p.begin(), p.end());
	
	priority_queue<int> que;
	int ind=0;
	int ans=0;
	repi(i,1,m+1){
		while(ind < p.size() && p[ind].first <= i){
			que.push(p[ind++].second);
		}
		if(!que.empty()){
			ans += que.top();
			que.pop();
		}
	}
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 1908
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(20000000)


def main():
  N = int(input())
  G = [[] for _ in range(N+1)]
  for i in range(N-1):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))

  color = [-1]*(N+1)
  color[1] = 0
  # S = [1]
  # while len(S):
  #   now = S[-1]
  #   for next_, w in G[now]:
  #     if color[next_] != -1:
  #       continue
  #     S.append(next_)
  #     color[next_] = (w % 2) ^ color[now]
  #     break
  #   else:
  #     S.pop()

  def dfs(now):
    for next_, w in G[now]:
      if color[next_] == -1:
        color[next_] = (w % 2) ^ color[now]
        dfs(next_)
  dfs(1)

  for i in range(1, N+1):
    print(color[i])


if(__name__ == '__main__'):
  main()


Measured memory_bytes: 184032
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod2 1000000007
#define mod 998244353
#define pi 3.141592653589793
#define all(v) v.begin(),v.end()


ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t%mod;
    }
    return n*rep_jijo(n,x-1)%mod;
}

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
   mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
}c(210000);

int main(){
    ll n,m,k;
    cin >> n >> m >> k;
    mint ans=0;
    mint now=m;
    for(ll x=n-1;x>=0;x--){
        mint tim=now*c(n-1,x);
        if(x<=k) ans+=tim;
        now*=m-1;
    }
    cout << ans.x << endl;

    return 0;
}



Measured memory_bytes: 6692
import std.stdio, std.string, std.conv, std.algorithm, std.numeric;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;

void main() {
    while (true) {
        int n;
        scan(n);

        if (n == 0) return;

        auto a = new int[](n);
        iota(n).each!(i => scan(a[i]));

        a.sort();
        int ans = a[1 .. $-1].sum / (n - 2);
        writeln(ans);
    }
}



void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

Measured memory_bytes: 2448
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <limits>

using Graph_t = std::vector<std::unordered_map<size_t, size_t>>;

constexpr size_t INF = std::numeric_limits<size_t>::max() / 2;

std::vector<size_t> calc_fare(Graph_t const& g, size_t start) {
  std::vector<size_t> ret(g.size(), INF);
  using P = std::pair<size_t, size_t>;
  std::priority_queue<P, std::vector<P>, std::greater<P>> que;

  ret[start] = 0;
  que.emplace(0, start);

  while (! que.empty()) {
    size_t fare, u;
    std::tie(fare, u) = que.top();
    que.pop();

    if (fare > ret[u]) continue;

    for (auto const& p: g[u]) {
      size_t v, f;
      std::tie(v, f) = p;
      auto new_f = fare + f;

      if (new_f<ret[v]) {
        ret[v] = new_f;
        que.emplace(new_f, v);
      }
    }
  }

  return ret;
}

int main() {
  size_t n, m, s, t;
  std::cin >> n >> m >> s >> t;
  s--; t--;

  Graph_t g_y(n);
  Graph_t g_s(n);

  for (size_t i=0; i<m; i++) {
    size_t u, v, a, b;
    std::cin >> u >> v >> a >> b;
    u--; v--;
    g_y[u].emplace(v, a);
    g_s[u].emplace(v, b);
    g_y[v].emplace(u, a);
    g_s[v].emplace(u, b);
  }

  auto f_y = calc_fare(g_y, s);
  auto f_s = calc_fare(g_s, t);

  std::vector<size_t> anss(n);
  auto f_min = f_y[n-1] + f_s[n-1];
  for (ssize_t i=n-1; i>=0; i--) {
    f_min = std::min(f_min, f_y[i] + f_s[i]);
    anss[i] = 1'000'000'000'000'000 - f_min;
  }

  for (auto ans : anss) {
    std::cout << ans << '\n';
  }

  return 0;
}


Measured memory_bytes: 36992
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=1000000007;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };


int main() {
	int n,a;
	cin>>n>>a;
	cout<<n*n-a<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
using Real = mp::number<mp::cpp_dec_float<1024>>;

int main()
{
	unsigned int N;
	unsigned int count=0;
	unsigned int sq_count=0;
	cin >> N;
	
	for(int a=1;a<N;a++)
	{
		count+=(N-1)/a;
	}
	cout << count << endl;
}

Measured memory_bytes: 3608
#include <stdio.h>

int main() {
    int N, X, i, result  = 0;
    int L[100];
    int D[100];

    scanf("%d",&N);
    scanf("%d",&X);

    for(i = 0; i < N; i++){
        scanf("%d",&L[i]);
    }

    for(i = 0; i < N+1; i++){
        if(i == 0){
            D[i] = 0;
        }else{
            D[i] = D[i-1] + L[i-1];
        }
        if(D[i] <= X){
            result++;
        }
    }

    printf("%d\n",result);

    return 0;
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main(){
  int n,a[1000000],cnt=0,m=0,g[1000000];
  cin>>n;
  for(int i=0;i<n;i++)cin>>a[i];
  for(int i=1;i<=n;i=3*i+1)g[m]=i,m++;
  for(int i=m-1;i>=0;i--){
    for(int j=g[i];j<n;j++){
      int v=a[j],k=j-g[i];
      while(k>=0&&a[k]>v){
	a[k+g[i]]=a[k];
	k=k-g[i];
	cnt++;
      }
      a[k+g[i]]=v;
    }
  }
  cout<<m<<endl;
  for(int i=m-1;i>=0;i--){
    cout<<g[i];
    i==0?cout<<endl:cout<<" ";
  }
  cout<<cnt<<endl;
  for(int i=0;i<n;i++)cout<<a[i]<<endl;
  return 0;
}

Measured memory_bytes: 7008
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100005

int N;
int A[NUM],B[NUM];

int calc(int table[NUM]){

	int ret = 0;
	int x,y,z;

	//★★2番目の不等号を修正するように考える★★

	for(int i = 0; i <= N-3; i++){

		x = table[i];
		y = table[i+1];
		z = table[i+2];

		if(x < y && y < z){

			ret++;

			if(i+3 <= N-1 && y > table[i+3]){

				swap(table[i+2],table[i+3]); //より下りやすくなる

			}else{

				swap(table[i+1],table[i+2]);
			}

		}else if(x > y && y > z){

			ret++;

			if(i+3 <= N-1 && y < table[i+3]){

				swap(table[i+2],table[i+3]); //より上りやすくなる

			}else{

				swap(table[i+1],table[i+2]);
			}
		}
	}

	return ret;
}

int main(){

	scanf("%d",&N);

	for(int i = 0; i < N; i++){

		scanf("%d",&A[i]);
		B[i] = A[i];
	}

	swap(B[0],B[1]);

	int ans_A = calc(A);
	int ans_B = calc(B)+1; //最初のswapの分

	printf("%d\n",min(ans_A,ans_B));

	return 0;
}



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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

//status unsolved
int main(){
    long long n,k;
    cin>>n>>k;
    double ans=0;
    double sum[n+1];
    sum[0]=0;

    rep(i,n){
    double  p;
    cin>>p;
    ans=(p+1)/2;
    sum[i+1]=sum[i]+ans;
    }
    ans=-1;

    for(int i=0;i+k<=n;i++){
        ans=max(ans,sum[i+k]-sum[i]);
    }
    printf("%.6lf",ans);
    return 0;

}
/*


*/


Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>

using namespace std;

int main() {

  int a, c;int b;
  //cin >> a >> b;// >> c; //>> b >> c;
  double ans, ra, rb;
  string FatString;
  cin >> FatString;
  cout << char(FatString[0] - 'a' + 'A');
  cin >> FatString;
  cout << char(FatString[0] - 'a' + 'A');
  cin >> FatString;
  cout << char(FatString[0] - 'a' + 'A');
  return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
bool dp[51][900][900];
int T[50];
int S[50];
signed main() {
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  REP(i,N) cin >> T[i];
  S[0] = T[0];
  for(int i = 1; i < N; ++i) S[i] = S[i - 1] + T[i];
  memset(dp, 0, sizeof(dp));
  dp[0][T[0]][0] = true;
  dp[0][0][T[0]] = true;
  for(int i = 1; i < N; ++i) {
    REP(a,900) REP(b,900) {
      if(dp[i - 1][a][b]) {
        if(S[i] - a - b < 900) dp[i][a][b] = true;
        if(a + T[i] < 900) dp[i][a + T[i]][b] = true;
        if(b + T[i] < 900) dp[i][a][b + T[i]] = true;
      }
    }
  }
  int ans = (int)1e9;
  REP(a,900) REP(b,900) {
    if(dp[N - 1][a][b]) {
      ans = min(ans, max({a, b, S[N - 1] - a - b}));
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 43536
a,b,c,d=map(int,input().split())
aoki=c
taka=a
data=0
for i in range(10000):
    if i%2==0:
        aoki-=b
        if aoki<=0:
            data=i
            break
    else:
        taka-=d
        if taka<=0:
            data=i
            break
            
if data%2==0:
    print("Yes")
else:
    print("No")
    
    
    

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

int main() {

	int s;
	int a;

	cin >> s;

	a = s % 10;

	if (a == 2 || a == 4 || a == 5 || a == 7 || a == 9) {
		cout << "hon" << "\n";
	}
	else if (a == 3) {
		cout << "bon" << "\n";
	}
	else {
		cout << "pon" << "\n";
	}

}

Measured memory_bytes: 3536
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
using P=pair<int,int>;
int main() {
    string t;cin>>t;
    for(int i=0;i<t.size();i++){
        if(t.at(i)=='?'){
            t.at(i)='D';
        }
    }
    int ans=0;
    rep(i,t.size()){
        cout<<t.at(i);
    }
    cout<<endl;

}

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

//wierd debugging stuff
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << "\n" ; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
//end of weird debugging stuff
using ll = long long;
using ld = long double;
using vi = vector<int>;
using ii = pair<int,int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
 
#define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define fo(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define foe(i,x) for(auto& i: x)
#define ar array
#define pb push_back
#define vt vector

template<class T> bool umin(T& a,const T& b){return b<a?a=b,1:0;}
template<class T> bool umax(T& a,const T& b){return b>a?a=b,1:0;}

template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class T> void read(T& x) {
	cin >> x;
}
void read(double& d) {
	string t;
	read(t);
	d=stod(t);
}
void read(long double& d) {
	string t;
	read(t);
	d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
	read(h);
	read(t...);
}
template<class A> void read(vt<A>& x) {
	foe(a, x)
		read(a);
}

// no change 
const ll MOD = 1e9+7;  
int n,k;
void Titan(){
	read(n,k);
	int ans = 0;
	while(n){
		n/=k;
		ans++;
	}
	cout << ans ;
	
}

int main() {
	FASTER;
	int T = 1;
	//cin >> T;		//cmt if one test case
    fo(T)Titan();
}


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

#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;

int main(){
  int n, k;
  cin >> n >> k;
  vector<pair<int, int>> a(n);
  rep(i,n) cin >> a[i].first >> a[i].second;
  sort(a.begin(), a.end(), [](pair<int,int> x, pair<int,int> y){
    return x.second>y.second;
  });
  vector<pair<int,int>> take(k);
  map<int,int> num;
  int i=0;
  ll sum=0, var=0;
  while(i<k){
    take[i] = a[i];
    sum += a[i].second;
    if(!num[a[i].first]){
      var++;
    }
    num[a[i].first]++;
    i++;
  }
  priority_queue<ll> ans;
  ans.push(sum+var*var);
  int j=k-1;
  while(i<n){
    if(!num[a[i].first]){
      while(j>=0 && num[take[j].first]==1)
        j--;
      if(j<0)
        break;
      sum = sum-take[j].second+a[i].second;
      var++;
      ans.push(sum+var*var);
      num[take[j].first]--;
      num[a[i].first]++;
      take[j] = a[i];
      j--;
    }
    i++;
  }
  cout << ans.top() << endl;
  return 0;
}

Measured memory_bytes: 4736
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define ll unsigned long long
using namespace std;
int main(){
    string s;cin>>s;
    string ans[3] = {"Sunny","Cloudy","Rainy"};
    if(s[0]=='S')cout<<ans[1]<<endl;
    else if(s[0]=='C')cout<<ans[2]<<endl;
    else cout<<ans[0]<<endl;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
 
/* 
The read function reads a string according to each one. 
*/
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}


//main function
fn main() {
    let a:i64 = read();
    let b:i64 = read();
    let min_8:i64;
    let max_8:i64;
    let min_10:i64 = b*10;
    let max_10:i64 = (b+1)*10-1;
    if a%2==0{
	min_8 = a*25/2;
	max_8 = (a+1)*25/2;
    }else {
	min_8 = a*25/2+1;
	max_8 = (a+1)*25/2-1;
    }

    if max_8 < min_10 || max_10 < min_8 {
	println!("-1");
	return;
    }

    if min_10 < min_8 {
	println!("{}",min_8);
    }else{
	println!("{}",min_10);
    }
}


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

int main()
{
	int n;
	cin >> n;
	char s[n];
	cin >> s;
	
	int countAll[26];
	for(int i = 0; i < 26; i++)
		countAll[i] = 0;
	for(int i = 0; i < n; i++){
		countAll[s[i]-97]++;
	}
	
	int ans = 0;
	for(int i = 1; i < n; i++){
		int countFront[26];
		for(int j = 0;j < 26; j++)
			countFront[j] = 0;
		int ansCand = 0;
		for(int j = 0; j < i; j++){
			countFront[s[j]-97]++;
		}
		for(int k = 0; k < 26; k++){
			if(countAll[k] > countFront[k] && countFront[k] != 0){
				ansCand++;
			}
		}
		ans = max(ans,ansCand);
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#define MOD 1000000007
#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
//#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

const double PI=3.14159265358979; 
vector<complex<double>> DFT(vector<complex<double>> A){
    int N=A.size();
    if(N==1)return A;
    vector<complex<double>> A0(N/2),A1(N/2),iA0,iA1,iA(N);
    for(int i=0;i<N;i++){
        if(i%2==0){
            A0[i/2]=A[i];
        }else{
            A1[i/2]=A[i];
        }
    }
    iA0=DFT(A0);
    iA1=DFT(A1);
    
    for(int i=0;i<N;i++){
        complex<double> ith_zeta = complex<double>(cos(2*PI*i/N),sin(2*PI*i/N));
        iA[i]=(iA0[i%(N/2)]+ ith_zeta*iA1[i%(N/2)]);
    }
    return iA;
}
 
vector<complex<double>> iDFT(vector<complex<double>> iA){
    int N=iA.size();
    vector<complex<double>> A,dA,rA;
    dA=DFT(iA);
    for(int i=0;i<N;i++){
        rA.push_back(dA[(N-i)%N]);
        A.push_back(rA[i]/complex<double>(N,0));
    }
    return A;
}
 
vector<complex<double>> convolution(vector<complex<double>> A,vector<complex<double>> B){
    int deg = A.size() + B.size() -1;
    int N=1;
    while(N<deg){N<<=1;}
    A.resize(N);B.resize(N);
    vector<complex<double>> C(N),iC(N),iA,iB;
    iA=DFT(A);iB=DFT(B);
    for(int i=0;i<N;i++){
        iC[i]=iA[i]*iB[i];
    }
    C=iDFT(iC);
    return C;
}

signed main(void){
    int N,M,a,Amax=0;
    vector<int> A;
    cin >> N >> M;
    REP(i,N){
        cin >> a;
        Amax=max(Amax,a);
        A.push_back(a);
    }
    
    vector<complex<double>> B,C;
    B.resize(Amax+1,0.0);
    REP(i,N){
        B[A[i]]+=1.0;
    }
    C=convolution(B,B);
    
    /*REP(i,C.size()){
        if(C[i]==0)continue;
        cout <<i MM C[i] << endl;
    }*/
    
    int Ans=0;
    int now=0;
    RREP(i,C.size()){
        int d=(C[i].real()+0.1);
        if(M-now>=d){
            Ans+=d*i;
            now+=d;
        }else{
            Ans+=(M-now)*i;
            break;
        }
    }
    cout << Ans << endl;
    return 0;
}



Measured memory_bytes: 61964
def main():
    S = input()
    L = len(S)

    def check(s):
        return s == s[::-1]

    cond = check(S)
    cond = cond and check(S[:L // 2])
    cond = cond and check(S[(L + 1) // 2:])

    print('Yes' if cond else 'No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9056
#include<bits/stdc++.h>
using namespace std;
#define int long long
int pre[50],in[50],post[50];
int n,pos,idx;
void dfs(int l,int r){
  if(l>=r) return;
  int root=pre[pos++];
  int m=-1;
  for(int i=l;i<r;i++)
    if(in[i]==root) m=i;
  dfs(l,m);
  dfs(m+1,r);
  post[idx++]=root;
}
signed main(){
  cin>>n;
  for(int i=0;i<n;i++) cin>>pre[i];
  for(int i=0;i<n;i++) cin>>in[i];
  pos=idx=0;
  dfs(0,n);
  for(int i=0;i<n;i++)
    cout<<post[i]<<" \n"[i==n-1];
  return 0;
}

Measured memory_bytes: 3100
s = list(input())
start = 0
end = 0
for i in range(len(s)):
    if s[i] == "A":
        start = i
        break
for j in range(len(s)):
    if s[-j-1] == "Z":
        end = -j-1
        break
if end == -1:
    print(len(s[start:]))
else:
    print(len(s[start:end+1]))

Measured memory_bytes: 6180
#include<bits/stdc++.h>
using namespace std;
int to(string s,char c){
	bool flag = true;
	for(int i=0; i<s.length(); i++)
		if(s[i] != c)
			flag = false;
	if(flag)return 0;
	string s2;
	for(int i=1; i<s.length(); i++)
		if(s[i] == c || s[i-1] == c)
			s2 += c;
		else
			s2 += s[i];
	return to(s2,c)+1;
}
int main(){
	string s;
	cin >> s;
	int mask = 0;
	for(int i=0; i<s.length(); i++)
		mask |= 1<<(s[i]-'a');
	int res = 111;
	for(int i=0; i<26; i++)if(mask&(1<<i))
		res = min(res, to(s,i+'a'));
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;


using Graph = vector<vector<int>>;//グラフ型
void dfs(const Graph& G, int v/*根*/, vector<bool>& seen) {
	seen[v] = true;  //vを訪問済にする
	for (auto next_v : G[v]) { //訪問済にしたvとつながっている場所を順番に探す
		if (seen[next_v]) continue; //もし探索済みならスルー
		dfs(G, next_v, seen); //再帰的に探索
	}
}

void bfs(const Graph& G, queue<int>& que/*発見したが訪問はしていない*/, vector<int>& dist/*開始地点からの距離*/) {

	while (!que.empty()) {
		int v = que.front();//queのうち先頭のものからスタート
		que.pop();//先頭を削除

		for (int nv : G[v]) {//vとつながっている点を列挙
			if (dist[nv] != -1) continue;//発見済(=距離が格納されている)であればスルー
			dist[nv] = dist[v] + 1;//vとつながっている点に距離の情報を追加
			que.push(nv);//vとつながっている点を発見済にする
		}
	}
}

template<typename T>
T gcd(T a, T b) {
	if (a % b == 0) {
		return(b);
	}
	else {
		return(gcd(b, a % b));
	}
}

template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}


template<typename T>
bool same(T x_b, T x_e, T y_b, T y_e) {
	for (auto i = x_b, j = y_b; i != x_e && j != y_e; ++i, ++j) {
		if (*i != *j) {
			return false;
		}
	}
	return true;
}


int main(void) {
	double n;
	cin >> n;
	double ans = n * 2 * acos(-1);
	cout << ans;
}

/*
9   3**2 1
27  3**3 2
81  3**4 3

11121213131415161516
3234566667

	
	*/


Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
const ll INF = 1e9+100;
const ll MOD = 1e9+7;
const double EPS  = 1e-10;
const bool debug = 0;
//---------------------------//

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

ll to_ll(string s) {
	ll res;
	stringstream ss(s);
	ss >> res;
	return res;
}

string s;

int main(){
	cin >> s;
	
	int lp = s.size();
	if (s.find('(') != string::npos) lp = s.find('(');
	
	int pc = s.find('.');
	ll q = 1;
	while (pc + 1 < lp) { // .1( -> 1.(
		q *= 10;
		swap(s[pc], s[pc + 1]);
		pc++;
	}
	
	ll u, d;
	if (s.find('(') == string::npos) {
		string str = s.substr(0, pc);
		u = to_ll(str);
		d = q;
	}
	else {
		string B = s.substr(lp + 1, s.size() - 2 - lp);
		ll b = to_ll(B);
		ll a = to_ll(s.substr(0, pc));
		
		u = a * (ll)pow(10, B.size()) + b - a;
		d = q * (ll)pow(10, B.size()) - q;
	}
	
	ll g = gcd(u, d);
	u /= g; d /= g;
	printf("%lld/%lld\n", u, d);
	
	return 0;
}

Measured memory_bytes: 3400
#pragma GCC optimize("O3")

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
tree<int,int,greater<int>,rb_tree_tag,tree_order_statistics_node_update> map_t;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); ++i)
#define sz(x) (int)x.size()
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define REV(x) reverse(x.begin(),x.end())
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
const ll INF=1e15;
int n;
ll a,b;
ll sum;
ll X;
vector<ll> on;
ll f(ll m){
    ll cur = sum;
    for(ll i = 0; i < sz(on); ++i){
        if((m >> i) & 1) cur |= (1LL << on[i]);
    }
    return (cur >= b ? cur - b : -1);
}

int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    vector<ll> arr(n);
    F0R(i,n)
        cin >> arr[i];
    a=arr[0];
    b=arr[1];
    ll xsum=0;
    FOR(i,2,n)
        xsum^=arr[i];
    ll tot=arr[0]+arr[1];
    if(tot-xsum<0) {
        cout << -1;
        return 0;
    }
    tot-=xsum;
    if((tot&(xsum<<1LL))!=0) {
        cout << -1;
        return 0;
    }
    if(tot%2) {
        cout << -1;
        return 0;
    }
    X=xsum;
    sum=(tot>>1);
    for(ll i = 0; i < 60; ++i){
        if((X >> i) & 1) on.push_back(i);
    }
    // for(auto i : on) cout << i << " ";
    // cout << "\n";
    ll l = 0, r = (1LL << sz(on)) - 1, res = -1;
    if(sum == 0) l++, r--;
    while(l <= r){
        ll m = l + (r - l)/2, cur = f(m);
        if(cur != -1){
            res = cur;
            r = m - 1;
        }
        else l = m + 1;
    }
    cout << res;
    /* ll best=INF;
    if(xsum==0 && (tot>>1LL)>=arr[1]) {
        best=(tot>>1LL)-arr[1];
        cout << best;
        return 0;
    }
    ll val=0;
    for(ll i=58; ~i; i--) {
        if(((xsum>>i)&1LL)==0)
            continue;
        if(val+(1LL<<i)+(tot>>1LL)>=arr[1] && val+(1LL<<i)+(tot>>1LL)!=arr[0]+arr[1])
            best=min(best,val+(1LL<<i)+(tot>>1LL)-arr[1]);
        else
            val+=(1LL<<i);
    }
    if(best==INF) {
        cout << -1;
        return 0;
    }
    cout << best; */

    return 0;
}


Measured memory_bytes: 3648
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
static const int MAX_N = 10000;
static const int MAX_M = 20000;
static const int INF = 1 << 30;
struct edge{int to, weight;};
 
int N, M;
int u[MAX_M], v[MAX_M], d[MAX_M], c[MAX_M];
vector<edge> G[MAX_N];
int dist[MAX_N];
int mincost[MAX_N];
 
void dijkstra(int s){
    priority_queue<P, vector<P>, greater<P> > pqa;
    pqa.push(P(0, s));
    fill(dist, dist + N, INF);
    dist[s] = 0;
    while(!pqa.empty()){
        P p = pqa.top(); pqa.pop();
        int v = p.second;
        if(dist[v] < p.first) continue;
        for(int i = 0; i < G[v].size(); i++){
            if(dist[G[v][i].to] <= dist[v] + G[v][i].weight) continue;
            dist[G[v][i].to] = dist[v] + G[v][i].weight;
            pqa.push(P(dist[G[v][i].to], G[v][i].to));
        }
    }
}
 
int main(){
    for(;;){
        scanf("%d %d", &N, &M);
        if(N == 0 && M == 0) break;
        for(int i = 0; i < M; i++){
            scanf("%d %d %d %d", &u[i], &v[i], &d[i], &c[i]);
            u[i]--; v[i]--;
            G[u[i]].push_back((edge){v[i], d[i]});
            G[v[i]].push_back((edge){u[i], d[i]});
        }
        dijkstra(0);
        fill(mincost, mincost + N, INF);
        mincost[0] = 0;
        for(int i = 0; i < M; i++){
            if(dist[u[i]] + d[i] == dist[v[i]]) mincost[v[i]] = min(mincost[v[i]], c[i]);
            if(dist[v[i]] + d[i] == dist[u[i]]) mincost[u[i]] = min(mincost[u[i]], c[i]);
        }
        int res = 0;
        for(int i = 0; i < N; i++) res += mincost[i];
        printf("%d\n", res);
        for(int i = 0; i < N; i++) G[i].clear();
    }
    return 0;
}


Measured memory_bytes: 4488
#133_B
n,d=map(int,input().split())
x=[list(map(int,input().split())) for _ in range(n)]

ans=0
for i in range(n-1):
    for j in range(i+1,n):
        dist=sum([(x[i][k]-x[j][k])**2 for k in range(d)])
        if (dist**.5).is_integer():
            ans+=1
            
print(ans)

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int  long long int
#define pb push_back
#define fe first
#define lb lower_bound 
#define ub upper_bound
#define pii pair<pair<int,int>,pair<int,int> >
#define se second
#define endl "\n"
#define pi pair<int, int>
#define mi          map<int,int>
#define mii         map<pi,int>
#define vi vector<int> 
#define vvi vector<vi>
#define bs   binary_search
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b) for(int i=a;i<=b;i++)	
#define all(c) (c).begin(),(c).end()
#define sz(x)       (int)x.size() 
#define PI 3.14159265358979323846

 const int N=2e3+5;

 int mod= 1e9+7;
 int dx[4]={0,0,+1,-1};
 int dy[4]={+1,-1,0,0};  
 
 
int po(int a, int b) {
	a %= mod;
	int res = 1;
	while (b > 0) {
		if (b & 1)
			res = (res * a) % mod;
		a =(a*a) % mod;
		b >>= 1;
	}
	 return res;	
   }
  

 void solve() {
  	    int n;
  	    cin>>n;
  	   
  	   for(int i=-200;i<=200;i++) {
		     for(int j=-200;j<=200;j++) {
				    int nx1=pow(i,5);
				    int nx2=pow(j,5);
				    //~ cout<<nx1<<" "<<nx2<<endl;
				    if(nx1-nx2==n ) {
						    //~ cout<<1<<endl;
						    cout<<i<<" "<<j<<endl;
						    return;						    
						}
				    if(nx2-nx1==n) {
						//~ cout<<nx2-nx1<<" "<<n<<endl; 
						//~ cout<<2<<endl;
						   cout<<j<<" " <<i<<endl;
						   return;
						}		
				 }
		   }
						   
 }

    
int32_t main() {
	cool;
	int t=1;

	//cin>>t;
	while(t--)
	solve();


return 0;	   
}


Measured memory_bytes: 4072
#include<bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)

using namespace std;
typedef long long ll;
using Graph =vector<int>;
typedef pair<int,int> P;
const ll MAX_N=131072;
const ll INF=1000000;
vector<int> G[1000010];
int main(){
  int N;ll x;cin>>N>>x;
  ll a;cin>>a;
  ll b=0;
  ll res=0;
  res+=max((ll)0,b+a-x);
  rep(i,N-1){
    b=a-(max((ll)0,b+a-x));
    cin>>a;
    res+=max((ll)0,b+a-x);
  }
  cout<<res<<endl;
}


Measured memory_bytes: 23680
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 132913423039
typedef long long ll;
const ll mod=1e9+7;
const ll N=1e5+5;
const int max_=1e5+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x)          { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    swap(n,m);
    swap(n,k);
    cout<<n<<" "<<m<<" "<<k<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int sortplus(int x[],int y[],int l){
	int i,j,k,a;
	for(i=1;i<=l;i++){
		for(j=l;j>=i+1;j--){
			if(x[j-1]<x[j]){
				k=x[j];
				a=y[j];
				x[j]=x[j-1];
				y[j]=y[j-1];
				x[j-1]=k;
				y[j-1]=a;
			}
		}
	}
	return 0;
}

int main(void){
	int c[128]={0},n[128]={0},k,t,i,yk=0,ans=0;
	scanf("%d%d",&k,&t);
	for(i=1;i<=t;i++){
		n[i]=i;
		scanf("%d",&c[i]);
	}
	for(i=1;i<=k;i++){
		sortplus(c,n,t);
		if(n[1]!=yk){
			c[1]--;yk=n[1];
		}
		else if(c[2]>0){
			c[2]--;yk=n[2];
		}
		else{
			c[1]--;ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256