akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<stdio.h>
#include<fstream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<map>
#include<iomanip>
#include<cassert>
#include<complex>
#include<functional>
#include<list>
#include<cmath>
#include<stack>
#include<assert.h>
#define LL long long
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define F first
#define S second
using namespace std;
int main(){
  int n;
  string a,b,c;
  cin>>n>>a>>b>>c;
  int ans=0;
  for(int i=0;i<n;i++){
  	if(a[i]==b[i]&&b[i]==c[i]);
  	else if(a[i]==b[i]||a[i]==c[i]||b[i]==c[i])
  	  ans++;
  	else
  	  ans+=2;
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=50+10;
const int INF=-0x3f3f3f3f;
int n,m,k,v[maxn];
long long ans=INF,tmp;
vector<int> g;
void fun(int x,int y,int p){
	int l=1,r=n;
	g.clear();
	tmp=0;
	while(x){
		g.push_back(v[l]);
		l++;
		x--; 
	}
	while(y){
		g.push_back(v[r]);
		r--;
		y--;
	}
	sort(g.begin(),g.end(),greater<int>());
	for(int idx=0;idx<g.size()-p;idx++){
		tmp+=g[idx];
	}
	ans=max(ans,tmp);
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&v[i]);
	}
	m=min(n,k);
	for(int i=0;i<=m;i++){
		for(int j=0;i+j<=m;j++){
			for(int p=0;i+j+p<=k;p++){
				if(i+j<p) break;
				else fun(i,j,p);
			}
		}
	}
	printf("%lld",ans);
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<numeric>
#include<map>
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const ll MOD = 1000000007;
 
using namespace std;

int main(){
    int N;  cin >> N;
    vector<ll> v(N);
    cin >> v[0];
    for(int i=1; i<N; i++){
        ll a;  cin >> a;
        v[i] = v[i-1] + a;
    }
    map<ll,ll> mp;
    for(int i=0; i<N; i++)  mp[v[i]]++;
    mp[0]++;
    ll ans = 0;
    for(auto i=mp.begin(); i!=mp.end(); i++){
        ll t = i->second;
        ans += t*(t-1)/2;
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  // 一年の秒数
  string s;
  cin>>s;
  
  int counter=0;
  if(s[0]=='1') ++counter;
  if(s[1]=='1') ++counter;
  if(s[2]=='1') ++counter;
  cout<<counter<<endl;
  
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define loop(k) rep(author_is_masa,k)
#define chmin(a,b) if((a)>(b)) (a)=(b);
#define chmax(a,b) if((a)<(b)) (a)=(b);
#define vi vector<int>
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define pb push_back
#define pf push_front
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/
  while(min(a,b)>0){if(a<b)swap(a,b);a%=b;}return max(a,b);
}
int dx[]={1,0,-1,0,1,-1,-1,1};
int dy[]={0,1,0,-1,1,1,-1,-1};
const int MOD = 1e9+7;
const long long INF = 1e18+10;

/*--------------------------------------------------------------------*/

signed main(){
	int n;cin>>n;
	vi a(n);
	rep(i,n) cin>>a[i];
	int ans=1;
	bool up=0,down=0;
	FOR(i,1,n-1){
		if(up){
			if(a[i-1]>a[i]){
				ans++;
				up=0;
				down=0;
			}

		}else if(down){
			if(a[i-1]<a[i]){
				ans++;
				up=0;
				down=0;
			}

		}else{
			if(a[i-1]<a[i]) up=1;
			if(a[i-1]>a[i]) down=1;
		}

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



Measured memory_bytes: 4044
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i< (int)(b); ++i)
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
typedef long double ld;
using ll=long long;
using namespace std;
const auto mod=1e9+7;
const ld pi = (acos(-1));

ll lcm(ll a, ll b){
    ll g = __gcd(a,b);
    return a/g*b;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  
  ll n; cin >> n;
  vector<ll> t(n);
  rep(i,0,n) cin >> t[i];
  ll ans=1LL;
  rep(i,0,n) {
    ans = lcm(ans,t[i]);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
class Main {
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  while(true) {
   int a = sc.nextInt();
   String op = sc.next();
   int b = sc.nextInt();
   if(op.equals("?")) break;
   switch(op) {
    case "+":
      System.out.println( a + b);
      break;
    case "-":
      System.out.println( a - b);
      break;
    case "/":
      System.out.println( a / b);
      break;
    case "*":
      System.out.println( a * b);
      break;
}
  }
 }
}


Measured memory_bytes: 26352
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define endl '\n'

#define si(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) 
#define rep2(i, n, m) for (ll i = n; i <= (ll)(m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (ll)(m); --i)

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

using ll = long long;
using ld = long double;
using namespace std;

constexpr ll MOD = 1000000007;

signed main()
{
  cout << fixed << setprecision(20);
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, x; cin >> n >> x;
  int mn = MOD, sum = 0;

  rep(i, n) {
    int m; cin >> m;
    sum += m;
    chmin(mn, m);
  }

  int y = x - sum;
  cout << n + (y / mn) << endl;

  return (0);
}


Measured memory_bytes: 3628
# coding: utf-8


def main():
    X, N = map(int, input().split())
    p = list(map(int, input().split()))

    if X not in p:
        return X

    for i in range(1, 100):
        if X-i not in p:
            return X-i
        
        if X+i not in p:
            return X+i


print(main())


Measured memory_bytes: 9196
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e15;
#include "string"

int32_t main() {
	int t=1;
	//cin>>t;
	while(t--) {
		int n , k;
		cin >> n >> k;
		int a[n +1];
		a[0] = 0;
		for(int i =1; i <= n; i++) 
			cin>>a[i];
		int ans = 0;
		for(int i=1;i<=min(n,k);i++){
			vector<int>left;
			for(int l=0;l<=i;l++){
				if(l > 0)
					left.push_back(a[l]);
				vector<int>v = left;
				int c = i - l,r=n;
				while(c > 0){
					v.push_back(a[r]);
					c--;
					r--;
				}
				int rem = k - i,sum = 0;
				sort(v.begin(),v.end());
				for(int j=0;j<v.size();j++){
					if(v[j]<0 && rem>0)
						rem--;
					else
						sum += v[j];
				}
				ans = max(ans,sum);
			}
		}
		cout<<ans<<endl;
	}	
}

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

int main()
{
    int x, y;
    int count = 0;

    cin >> x >> y;
    for (int i = x; i <= y; i++)
    {
        //1桁目=5桁目、2桁目=4桁目
        if(i % 10 == i / 10000 && (i / 10)%10  == (i / 1000)%10){
            count++;
        }
    }

    cout << count;
}

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

h_max = max(hl)
c=0
for i in range(1, h_max+1):
    hit = False
    for j in range(len(hl)):
        if hl[j] >= i: #hit
            if j==len(hl)-1:
                c+=1
            hit=True
        else:
            if hit==True:
                c+=1
            hit=False

print(c)


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;

typedef long long LL;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a))
#define	GE() printf(">----------\n")
#define	IN() freopen("in.txt","r",stdin)
#define	OUT() freopen("out.txt","w",stdout)
const int mod=1000000007;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=1005;

int n, m, r, ans;
int E[maxn][maxn], data[maxn];
map<int, int> vis;
int flag[maxn];

int solve(int pos, int step){
    if(step==r)return 0;
    int u=data[pos];
    flag[u]=1;
    int tans=inf;
    for(int i=0;i<r;i++){
        int v=data[i];
        if(!flag[v]){
            flag[v]=1;
            tans=min(tans, E[u][v]+solve(i, step+1));
            flag[v]=0;
        }
    }
    flag[u]=0;
    return tans;
}

int main()
{
    int n;
    while(~scanf("%d%d%d", &n, &m, &r)){
        vis.clear();
        memset(flag, 0);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                E[i][j]=inf;
                if(i==j)E[i][j]=0;
            }
        }
        for(int i=0;i<r;i++){
            scanf("%d", &data[i]);
            vis[data[i]]++;
        }
        int u, v, cost;
        for(int i=0;i<m;i++){
            scanf("%d%d%d", &u, &v, &cost);
            E[u][v]=E[v][u]=cost;
        }
        for(int k=1;k<=n;k++){
            for( int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    E[i][j]=min(E[i][j], E[i][k]+E[k][j]);
                }
            }
        }
        ans=inf;
        for(int i=0;i<r;i++){
            int res=solve(i, 1);
            ans=min(ans, res);
        }
        printf("%d\n", ans);
    }
    return 0;
}


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

using namespace std;
typedef long long ll;


int main()
{
    int h, w;
    cin >> h >> w;
    char g[h][w];
    ll dp[h][w];

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> g[i][j];
            if (g[i][j]=='#')
                dp[i][j] = 0;
        }
    }

    dp[0][0] = 1;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (i==0&&j==0) continue;
            else if (g[i][j]=='#')
                dp[i][j] = 0;
            else if (i!=0&&j!=0)
                dp[i][j] = ((dp[i-1][j]%1000000007) + (dp[i][j-1]%1000000007)) % 1000000007;
            else if (i==0)
                dp[i][j] = dp[i][j-1]%1000000007;
            else if (j==0)
                dp[i][j] = dp[i-1][j]%1000000007;
        }
    }

    cout << dp[h-1][w-1]%1000000007;

    return 0;
}


Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace std;
double algo(int x);
int main(){
int n,k,i,j;
double max_sum=0,cur_sum=0;
cin>>n>>k;
vector<int> v(n,0);
for(i=0;i<n;i++) cin>>v[i];  
  
for(i=0;i<k;i++) max_sum+=v[i];  
cur_sum = max_sum;
for(i=1;i<=n-k;i++){
      cur_sum = cur_sum-v[i-1]+v[i+k-1];
      max_sum = max_sum>cur_sum?max_sum:cur_sum;
  }
  int x = (max_sum+k)/2;
  if(2*x==max_sum+k) cout<<x<<".000000000000";
  else
    cout<<x<<".500000000000";
  
  
  
}

double algo(int x){
  double value=((double)x+1)/2;
  return value;
}  
  


Measured memory_bytes: 1024
from sys import stdin


def main():
    w = next_int()
    h = next_int()
    n = next_int()
    arr = [[1] * w for _ in range(h)]

    for i in range(n):
        xi, yi, a = map(int, input().split())

        for y in range(h):
            for x in range(w):
                if a == 1:
                    if x < xi:
                        arr[y][x] = 0
                if a == 2:
                    if x >= xi:
                        arr[y][x] = 0
                if a == 3:
                    if y < yi:
                        arr[y][x] = 0
                if a == 4:
                    if y >= yi:
                        arr[y][x] = 0

    ans = 0
    for y in range(h):
        ans += sum(arr[y])
    print(ans)


def next_int():
    return int(next_str())


def next_str():
    result = ""
    while True:
        tmp = stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

int main() {
  int n;
  cin >> n;
  vector<double> a(n);
  vector<pair<double, int>> d(n);
  double sum{};
  double avg{};
  REP(i, n) {
    int in;
    cin >> in;
    a[i] = in;
    sum += in;
  }
  avg = sum / n;
  // cout << avg << endl;
  REP(i, n) {
    d[i] = make_pair(a[i] - avg, i);
    if (d[i].first < 0)
      d[i].first *= -1;
    // cout << d[i].first << endl;
  }
  sort(d.begin(), d.end());
  cout << d[0].second << endl;
}


Measured memory_bytes: 256
def main():
    n, a, b, c = list(map(int, input().split()))
    L = [int(input()) for _ in range(n)]
    INF = 1000000
    def dfs(i, la, lb, lc):
        if i == n:
            return abs(la - a) + abs(lb - b) + abs(lc - c) if min(la, lb, lc) > 0 else INF
        res = []
        res.append(dfs(i + 1, la, lb, lc))
        res.append(dfs(i + 1, la + L[i], lb, lc) + 10 if la != 0 else dfs(i + 1, la + L[i], lb, lc))
        res.append(dfs(i + 1, la, lb + L[i], lc) + 10 if lb != 0 else dfs(i + 1, la, lb + L[i], lc))
        res.append(dfs(i + 1, la, lb, lc + L[i]) + 10 if lc != 0 else dfs(i + 1, la, lb, lc + L[i]))
        return min(res)
    print(dfs(0, 0, 0, 0))

if __name__ == '__main__':
    main()

Measured memory_bytes: 9212
x, k, d = list(map(int, input().split()))

sign = 0
if x != 0:
  sign = int(x /abs(x))

if (abs(x) // d) < k:
  tmp = x - sign * d * (abs(x) // d)
  #print(tmp)
  if (k - (abs(x) // d)) % 2 == 0:
    print(abs(tmp))
  else:
    print(min(abs(tmp + d), abs(tmp - d)))
else:
  print(abs(x - sign * d * k))

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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

int main(){
  ll a,b,n;cin>>a>>b>>n;

  ll x = min<ll>(b-1, n);
  cout<<(a*x)/b - a*(x/b)<<endl;

  return 0;
}

Measured memory_bytes: 3636
#include <cstdio>
#include <string>
using namespace std;

int n;
char buf[1000000];

int main() {
  scanf("%d ", &n);
  while (n--) {
    int cnt = 0;
    int score = 0;
    bool runner[4] = {false};

    while (cnt < 3) {
      runner[0] = true;

      scanf("%s", buf);
  
      string s(buf);
      if (s == "HIT") {
        if (runner[3]) score++;
        for (int i=2; i>=0; i--) {
          runner[i+1] = runner[i]; 
        }
      } else if (s == "HOMERUN") {
        for (int i=0; i<4; i++) {
          if (runner[i]) score++;
          runner[i] = false;
        }
      } else if (s == "OUT") {
        cnt++;
      }
    }

    printf("%d\n", score);
  }
}

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

int min_my(int x,int y,int z){
  int answer = x;
  if (x > y){
    answer = y;
    if (y > z){
      answer = z;
    }
  }
  else if (x > z){
    answer = z;
  }
  return answer;
}

int gcd(int a,int b,int c){
  int G = 1;
  for (int i = 1; i <= min_my(a, b, c); i++){
    if (a % i == 0 && b % i == 0 && c % i == 0){
      G = i;
    }
  }
  return G;
}
    
int main(){
  int K;
  cin >> K;
  int sum = 0;
  for (int i = 1; i < K + 1; i++){
    for (int j = 1; j < K + 1; j++){
      for (int k = 1; k < K + 1; k++){
        sum += gcd(i, j, k);
      }
    }
  }
  cout << sum << endl;
  return 0;
}
  


Measured memory_bytes: 3648
#include <stdio.h>

int main(){
  int N, Y, i, j;
  scanf("%d%d", &N, &Y);
  for(i=0; i<=N; i++){
    for(j=0; j<=N-i; j++){
        if(i*10000 + j*5000 + (N-i-j)*1000 == Y){
          printf("%d %d %d", i, j, N-i-j);
          return 0;
        }
    }
  }
  if(i==N+1) printf("%d %d %d", -1, -1, -1);
  return 0;
}

Measured memory_bytes: 128
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
sys.setrecursionlimit(10**6)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


N = z()
S = S()
ans = 0
for i in range(N):
    a = collections.Counter(S[:i])
    b = collections.Counter(S[i:])
    ans = max(len(set(a.keys()) & set(b.keys())), ans)
print(ans)


Measured memory_bytes: 42176
n = int(input())
lst = list(map(int,input().split()))
for i in range(n):
    key = lst[i]
    j = i-1
    while j >= 0 and lst[j] > key:
        lst[j+1] = lst[j]
        j -= 1
    lst[j+1] = key
    print(' '.join(map(str,lst)))

Measured memory_bytes: 7596
#include<stdio.h>

int main()
{
    int a[101], n,i,j,ans=0,keep,p=1;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d",& a[i]);
    for (i = 0; i < n; i++)
    {
        for (j = 1; j < n; j++)
        {
            if (a[j] > a[j - 1])
            {
                keep = a[j];
                a[j] = a[j - 1];
                a[j - 1] = keep;
            }
        }
    }
    for (i = 0; i < n; i++)
    {
        ans += a[i] * p;
        p = p * (-1);
    }
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e17 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

#define int long long

signed main() {
  int h,w;
  cin >> h >> w;

  if (h % 3 == 0 or w % 3 == 0) {
    cout << 0 << endl;
    return 0;
  }

  auto search_height = [=]() {
    int ave = w / 2;
    int res = INF;
    for (int i = 0; i <= h; ++i) {
      int mmin = 10000000;
      int mmax = -1;
      int remain_edge = h - i;
      int sa, sb, sc;
      sa = remain_edge * w;
      sb = ave * i;
      sc = (w - ave) * i;

      mmin = min({sa, sb, sc});
      mmax = max({sa, sb, sc});

      res = min({abs(mmin - mmax), res});

      sa = h * i;
      sb = ave * remain_edge;
      sb = (w - ave) * remain_edge;

      mmin = min({sa, sb, sc});
      mmax = max({sa, sb, sc});

      res = min({abs(mmin - mmax), res});
    }

    return res;
  };

  auto search_width = [=]() {
    int ave = h / 2;
    int res = INF;
    for (int j = 0; j <= w; ++j) {
      int mmin = 10000000;
      int mmax = -1;
      int remain_edge = w - j;
      int sa, sb, sc;
      sa = remain_edge * h;
      sb = ave * j;
      sc = (h - ave) * j;

      mmin = min({sa, sb, sc});
      mmax = max({sa, sb, sc});
      res = min({abs(mmin - mmax), res});

      sa = h * j;
      sb = ave * remain_edge;
      sc = (h - ave) * remain_edge;

      mmin = min({sa, sb, sc});
      mmax = max({sa, sb, sc});
      res = min({abs(mmin - mmax), res});

      // cout << res << endl;
    }

    return res;
  };

  auto three = [=](int x) {
    return x;
  };

  cout << min({search_height(), search_width(), three(h), three(w)}) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string s;
    cin >> s;
    int count = 0;
    string before = "", current = "";
    
    rep(i, sz(s)) {
        current += s[i];
        
        if (before != current) {
            before = current;
            count++;
            current = "";
        }
    }
    
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 720
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
struct Edge {
    int u, v, w;
};
vector<Edge> edges;
void AddEdge(int u, int v, int w) {
    edges.pb({u, v, w});
}
int main() {
    int L;
    cin >> L;
    int t = log2(L);
    int n = t + 1;
    for(int i = 1; i < n; ++i) {
        AddEdge(i, i + 1, 0);
        AddEdge(i, i + 1, (1<<(i-1)));
    }
    int cur = (1<<t);
    int x = L - cur;
    for(int i = 0; i < 20; ++i) {
        if((1<<i) & x) {
            AddEdge(i+1, n, cur);
            cur += (1<<i);
        }
    }
    int m = edges.size();
    printf("%d %d\n", n, m);
    for(Edge e : edges) {
        printf("%d %d %d\n", e.u, e.v, e.w);
    }
    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9)

N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

ds = set(make_divisors(N)) | set(make_divisors(N-1))

def check(n,k):
    if n<k:
        return n==1
    elif n%k==0:
        return check(n//k,k)
    else:
        return check(n%k,k)

ds.remove(1)
cnt = 0
for d in ds:
    # print(d)
    if check(N,d):
        cnt+=1
print(cnt)


Measured memory_bytes: 40812
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <math.h>
#include <time.h>

using namespace std;

void mergeSort(vector<int> &v, long long &count, int start, int end)
{
	if (start == end)
	{
		return;
	}
	int mid = (start + end) / 2;
	mergeSort(v, count, start, mid);
	mergeSort(v, count, mid + 1, end);
	int t1 = start, t2 = mid + 1;
	vector<int> temp;
	while (t1 <= mid || t2 <= end)
	{
		int left = t1 <= mid ? v[t1] : 2001;
		int right = t2 <= end ? v[t2] : 2001;
		if (left <= right)
		{
			temp.push_back(left);
			t1++;
		}
		else
		{
			temp.push_back(right);
			t2++;
			count += (mid + 1) - t1;
		}
	}
	for (int i = start; i <= end; i++)
	{
		v[i] = temp[i - start];
	}
}

int main()
{
	ios::sync_with_stdio(false);
	// (choose 2 from k) * n * (n - 1) / 2 + k * number of inversions in the array (kind of)
	long long n, k;
	cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	long long cnt = 0;
	mergeSort(v, cnt, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		v.push_back(v[i]);
	}
	long long cnt2 = 0;
	mergeSort(v, cnt2, 0, 2 * n - 1);
	long long mod = 1000000007;
	cout << ((k * cnt) % mod + ((k * (k - 1) / 2) % mod) * cnt2) % mod;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
//#include <string.h>
//#include <vector>
//#include <cassert>
#include <algorithm>
//#include <functional>
 
using namespace std;
 
int main() {
	int a, b, c,E, F;
	int K;
	cin >> a >> b >> c;
	cin >> K;
	if (a == b && b == c) {
		for (int i = 0; i < K; i++) {
			a *= 2;
		}	
		cout << a + b + c<< endl;	
	} else {
		int ans = max({a, b, c});
		if (ans == a) {
			E = b;
			F = c;
		} else if (ans == b) {
			E = a;
			F = c;
		} else if (ans == c) {
			E = a;
			F = b;
		}
		for (int j = 0; j < K; j++) {
			ans = ans * 2;
		}
		cout << ans + E + F << endl;
	}
	return 0;
}

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

typedef long long ll;
#define ALL(a) a, a+sizeof(a)/sizeof(a[0])
#define all(a) a.begin(),a.end()
#define MOD 1000000007
using namespace std;
ll gcd(ll n, ll m) {
	if (m == 0) return n;
	return gcd(m, n % m);
}
ll lcm(ll n, ll m) {return m / gcd(n, m) * n;}

int main(void) {
	ll n,x,y,z,ans=0;
	cin >> n;
	vector<ll> a(n), b(n), c(n);
	cin >> x;
	for (ll j = 0; j<x; j++) {
		cin >> a[j];
	}
	cin >> y;
	for (ll j = 0; j < y; j++) {
		cin >> b[j];
	}
	cin >> z;
	for (ll j = 0; j < z; j++) {
		cin >> c[j];
	}
	for (int ci = 0; ci < z; ci++) {
		bool flg1 = false;
		bool flg2 = true;
		for (int bi = 0; bi < y; bi++) {
			if (c[ci] == b[bi]) {
				flg1=true;
			}
		}
		for (int ai = 0; ai < x; ai++) {
			if (c[ci] == a[ai])
				flg2 = false;
		}
		if (flg1 || flg2) ans++;
	}
	cout << ans << endl;
	return 0;
}


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

int main(){
  int h, m, s, X;
  cin >> X ;
  h = X / 3600;
  m = ( X - 3600 * h) / 60;
  s = X - (3600 * h + 60 * m);
  cout << h << ":" << m << ":" << s << endl;
}


Measured memory_bytes: 3112
using System;
using System.Text;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Threading.Tasks;

class Solve
{
	const int mod = 1000000007;
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
		const int c = 400;
		long ansmax = 0;
		long ansmin = 0;
        for(int i = 1; i <= 8; i++)
		{
			int cnt = a.Where(x => (x < i * c) && (x >= (i - 1) * c)).Count();
			if (cnt >= 1)
			{
				ansmax++;
				ansmin++;
			}
		}
		int high = a.Where(x => x >= 3200).Count();
		ansmax += high;
		if (ansmin == 0 && high != 0) { ansmin++; }

		Console.WriteLine($"{ansmin} {ansmax}");
	}
}


Measured memory_bytes: 11348
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i, s, n) for (int i = s; i < (n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
using namespace std;
using ll = long long;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;
const int inf = (1<<29);

int main() {

    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    
    int x3, y3, x4, y4;

    x3 = x2 - (y2 - y1);    
    y3 = y2 + (x2 - x1);    
    x4 = x1 - (y2 - y1);    
    y4 = y1 + (x2 - x1);    

    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;


    return 0;
}

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

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

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

  cout << (int)m.size() << endl;

  return 0;
}


Measured memory_bytes: 256
//BISMILLAHIR RAHMANIR RAHIM
//ALLAH HU AKABR
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  int x,y;
   x=(a+d-1)/d;
   y=(c+b-1)/b;
  if(x>=y)cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
 
#define fi first
#define se second
#define pb emplace_back
#define all(x) x.begin(),x.end()
#define rall(x) (x).rbegin(),(x).rend()
#define re return
#define mp make_pair
#define sz(x) ((int)(x).size())
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repx(i, x, n) for (int i = x; i < (n); i++)
#define repd(i, n, d) for (int i = 0; i < (n); i += d)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepd(i, n, d) for (int i = (n) - 1; i >= 0; i -= d)
#define unq(x); { sort(x.begin(), x.end()); x.resize(unique(x.begin(), x.end()) - x.begin()); }
#define sqr(x) ((x)*(x))
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<string> vs;
typedef vector<ll> vl;
typedef vector<vl> vvl;
 
const int inf = 1e9;
const ll infll = 1e18;
const int base1 = 179;
const int base2 = 653;
const ll mod = 1e9 + 7;
const int maxn = 2e5;
const ld pi = 3.1415926535;
const ld eps = 1e-5;
 
#define DEBUG 1
 
#ifdef DEBUG
    #define deb(x)
    #define debug(x)   cerr << #x << " " << x << endl;
    #define debug_p(x) cerr << #x << " " << x.ff << " " << x.ss << endl;
    #define debug_v(x) {cerr << #x << " "; for (auto i : x) cerr << i << " ";}
    #define debug_vp(x) {cerr << #x << " "; for (auto i : x) cerr << '[' << i.ff << " " << i.ss << ']'; cerr << endl;}
    #define debug_v_v(x) {cerr << #x << "/*\n"; for (auto i : x) { for (auto i2 : i) cerr << i2 << " "; cerr << '\n';} cerr << "*/" << #x << endl;}
#else
    #define deb(x) x
    #define debug(x) 0;
    #define debug_p(x) 0;
    #define debug_v(x) 0;
    #define debug_vp(x) 0;
    #define debug_v_v(x) 0;
#endif
 
void solve() {
	string s;
	cin >> s;

	if(s.size() == 2 && s[ 0 ] == s.back()) {
		cout << 1 << ' ' << 2 << '\n';
		return;
	}

	int l = -1, r = -1;
	rep(i, (int) s.size()) {
		if(i - 1 >= 0 && s[ i ] == s[ i - 1 ]) {
			if(i + 1 < (int) s.size()) l = i - 1, r = i + 1;
			else l = i - 2, r = i;
		}
	}

	rep(i, (int) s.size()) {
		if(i - 2 >= 0 && s[ i ] == s[ i - 2 ]) {
			l = i - 2, r = i;
		}
	}
	if(l == -1) cout << l << ' ' << r << endl;
	else cout << l + 1 << ' ' << r + 1 << endl;
}
 
signed main() {
    // freopen("race.in", "r", stdin);
    // freopen("race.out", "w", stdout);
 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    solve();
}

Measured memory_bytes: 3672
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n;
int sz[maxn + 10], deg[maxn + 10], tot[maxn + 10];
vector<int> g[maxn + 10];
vector<int> a, b, ans;

void dfs(int p, int fa) {
	a.push_back(tot[p]);
	for (auto i: g[p])
		if (sz[i] > 1 && i != fa)
			dfs(i, p);
}

void appendfr() {
	a.push_back(0);
	for (int i = (int)a.size() - 1; i; --i) a[i] = a[i - 1];
	--a[1]; a[0] = 0;
}

void appendbk() {
	--a[(int)a.size() - 1];
	a.push_back(0);
}

void solve() {
	int p = 0, cnt = 0;
	vector<int> now(n);
	for (auto i: a) {
		now[p + i] = ++cnt;
		for (int j = 0; j < i; ++j)
			now[p + j] = ++cnt;
		p += i + 1;
	}
	ans = min(ans, now);
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; ++i) {
		int l, r; scanf("%d%d", &l, &r);
		g[l].push_back(r); g[r].push_back(l);
		++sz[l]; ++sz[r];
	}
	if (n == 2) {
		printf("1 2\n"); return 0;
	}
	for (int i = 1; i <= n; ++i)
			for (auto j: g[i])
				if (sz[j] > 1) {
					if (sz[i] > 1) ++deg[j];
					else ++tot[j];
				}
	for (int i = 1; i <= n; ++i)
		if (sz[i] > 1 && deg[i] > 2) {
			printf("-1"); return 0;
		}
	for (int i = 1; i <= n; ++i)
		if (sz[i] > 1 && deg[i] < 2) {
			dfs(i, 0); break;
		}
	b = a; ans.push_back(1e9);
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j) {
			a = b;
			if (i) appendfr();
			if (j) appendbk();
			solve();
			reverse(a.begin(), a.end());
			solve();
		}
	for (auto i: ans) printf("%d ", i);
}


Measured memory_bytes: 13296
#include <bits/stdc++.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int main(){
  const ll MOD = 998244353;
  int N;
  cin >> N;
  vll D(N);
  rep(i, N)cin >> D[i];
  ll far = *max_element(D.begin(), D.end());
  vll a(far+1, 0);
  rep(i, N)a[D[i]]++;
  ll ans = 1; 
  rep(i, far){
    rep(j, a[i+1]){
      ans *= a[i];
      ans %= MOD;
    }
  }
  if (D[0] != 0 || a[0] != 1) ans = 0;
  cout  << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <string>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s,t;
    cin >> s >> t;

    int ss = s.length();
    int st = t.length();
    int dp[ss + 1][st + 1];

    for (int i = 0; i < ss + 1; i++){
        for (int j = 0; j < st + 1; j++){
            dp[i][j] = 0;
        }
    }
    
    for (int i = ss - 1; i >= 0; i--) {
        for (int j = st - 1; j >= 0; j--) {
            if (s.at(i) == t.at(j)) {
                dp[i][j] = 1 + dp[i + 1][j + 1];
            } else { 
                if (dp[i + 1][j] > dp[i][j + 1]) {
                    dp[i][j] = dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i][j + 1];
                }
            }
        }
    }

    string o = "";
    int i = 0, j = 0;

    while (1){
        if (i >= ss || j >= st){
            break;
        }
        if (s.at(i) == t.at(j)){
            o += s.at(i);
            i++;
            j++;
        } else if (dp[i + 1][j] > dp[i][j + 1]){
            i++;
        } else {
            j++;
        }
    }

    cout << o;
}

Measured memory_bytes: 35456
#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;
  }
  else if (A + B == C + D) {
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" <<endl;
  }
}

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

const int MAX=200000;
bool is_prime[MAX]={true};
vector<int> data;

void sieve(){
	is_prime[0]=is_prime[1]=false;
	for(int i=2;i*i<MAX;i++){
		if(is_prime[i]){
			for(int j=i*2;j<MAX;j+=i){
				is_prime[j]=false;
			}
		}
	}
}
int main(){
	fill(is_prime,is_prime+MAX,true);
	sieve();
	int n,p;
	while(cin>>n>>p &&n!=-1){
		data.clear();
		for(int i=n+1,c=0;c<300;i++){
			if(is_prime[i]){
				c++;
				for(int j=i,d=0;d<300;j++){
					if(is_prime[j]){
						d++;
						data.push_back(i+j);
					}
				}
			}
		}
		sort(data.begin(),data.end());
		cout<<data[p-1]<<endl;
	}

}

Measured memory_bytes: 1876
#include<bits/stdc++.h>
using namespace std;
struct Node{
    Node *parent,*left,*right;
    int key;
};
Node *root=NULL,*NIL=NULL;
void insert(int k){
    Node* x_parent=NIL;//xの親
    Node* x=root;//挿入する場所
    Node* node=NIL;//新しく挿入するノード
    node=(Node*)malloc(sizeof(Node));
    node->key=k;
    node->right=NIL;
    node->left=NIL;
    while(x!=NIL){
        x_parent=x;
        if(node->key<x->key) x=x->left;
        else x=x->right;
    }
    node->parent=x_parent;
    if(x_parent==NIL) root=node;//木が空の場合
    else{
        if(node->key<x_parent->key) x_parent->left=node;
        else x_parent->right=node;
    }
}
void pre(Node* u){
    if(u==NIL) return;
    printf(" %d",u->key);
    pre(u->left);
    pre(u->right);
}
void in(Node* u){
    if(u==NIL) return;
    in(u->left);
    printf(" %d",u->key);
    in(u->right);
}
int main(){
    int m,k;
    scanf("%d",&m);
    string com;
    for(int i=0;i<m;++i){
        cin>>com;
        if(com=="insert"){
            scanf("%d",&k);
            insert(k);
        }else if(com=="print"){
            in(root);
            putchar('\n');
            pre(root);
            putchar('\n');
        }
    }
    return 0;
}

Measured memory_bytes: 26708
import std.algorithm, std.array, std.conv, std.range, std.stdio, std.string;
void main()
{
    auto buf = readln.chomp.split.to!(int[]);
    auto nGames = buf[0], kRestrict = buf[1];
    buf = readln.chomp.split.to!(int[]);
    auto t = (cast(ubyte[])(readln.chomp)).map!(_ => [
            'r': Hand.rock,
            's': Hand.scissors,
            'p': Hand.paper
    ][_]).array;
    solve(nGames, kRestrict, buf, t).writeln;
}
long solve(int nGames, int kRestrict, int[] scores, Hand[] machine)
{
    long ret;
    foreach (i; 0..kRestrict)
    {
        ret += solve1(scores, machine.stride(kRestrict).array);
        machine.popFront;
    }
    return ret;
}
long solve1(int[] scores, Hand[] machine)
{
    // dp[i][j] := max{score; i-th hand = j}
    auto dp = new long[3][machine.length];
    dp[0][] = iota(3).map!(_ => scores.score(_, machine[0])).array[];
    foreach (i; 1..machine.length)
    {
        foreach (j; 0..3)
        {
            foreach (k; 0..3)
                if (j != k)
                    dp[i][j] = max(dp[i][j], dp[i-1][k]);
            dp[i][j] += scores.score(j, machine[i]);
        }
    }
    return dp[machine.length - 1].array.reduce!max;
}
enum Hand
{
    rock, scissors, paper
}
long score(int[] scores, int hand, int machine)
{
    if ((hand + 4 - machine) % 3) return 0;
    return scores[hand];
}
unittest
{
    with (Hand)
    {
        assert (score([8, 7, 6], rock, rock) == 0);
        assert (score([8, 7, 6], rock, scissors) == 8);
        assert (score([8, 7, 6], rock, paper) == 0);
        assert (score([8, 7, 6], scissors, rock) == 0);
        assert (score([8, 7, 6], scissors, scissors) == 0);
        assert (score([8, 7, 6], scissors, paper) == 7);
        assert (score([8, 7, 6], paper, rock) == 6);
        assert (score([8, 7, 6], paper, scissors) == 0);
        assert (score([8, 7, 6], paper, paper) == 0);
    }
}


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

typedef long double ld;
typedef long long ll;

const int Maxd = 19;
const int mult = 1000000000;

int has[Maxd][Maxd];
ll res;

int main()
{
    std::ios_base::sync_with_stdio(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        ld num; cin >> num;
        ll got = ll(num * ld(mult) + 0.5);
        int has2 = 0, has5 = 0;
        while (got % 2 == 0) { got /= 2; has2++; }
        while (got % 5 == 0) { got /= 5; has5++; }
        has2 = min(has2, Maxd - 1);
        has5 = min(has5, Maxd - 1);
        for (int i = 0; i < Maxd; i++) if (has2 + i >= Maxd - 1)
            for (int j = 0; j < Maxd; j++) if (has5 + j >= Maxd - 1)
                res += has[i][j];
        has[has2][has5]++;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3744
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    int n,m;cin>>n>>m;
    vector<int> a(m);
    for(int i=0;i<m;i++) cin>>a[i];

    long long sum=accumulate(a.begin(),a.end(),0LL);
    if(sum>n){
        cout<<-1<<endl;
    }
    else{
        cout<<n-sum<<endl;
    }

    return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N,M,a,b,ans=0;
  cin>>N>>M;
  int Path[N][N];
  int v[N];
  bool exist;
  for(int i=0;i<M;i++){
    for(int j=0;j<M;j++){
      cin>>a>>b;
      Path[a-1][b-1]=1;
      Path[b-1][a-1]=1;
    }
  }
  for(int i=0;i<N;i++){
    v[i]=i;
  }
  do{
    exist=true;
    if(v[0]!=0){
      exist=false;
    }else{
      for(int i=0;i<N-1;i++){
        if(Path[v[i]][v[i+1]]!=1){ 
          exist=false;
          break;
        }
      }
    }
    if(exist){
      ans++;
    }
    }while(next_permutation(v,v+N));
  cout<<ans<<endl;
}

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

int main(int argc, const char * argv[]) {
    // insert code here...
    int N, a, b;
    cin >> N >> a;
    b = N % 500;
    if(a >= b)
    {
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }
    return 0;
}


Measured memory_bytes: 256
// dfs(stack)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
using namespace std;

const int N = 100;
const int WHITE = 0;
const int GRAY = 1;
const int BLACK = 2;

int n, M[N][N];
int color[N], d[N], f[N], tt;
int nt[N];

// uに隣接するvを番号順に取得
int next(int u) {
    for (int v = nt[u]; v < n; v++) {
        nt[u] = v + 1;
        if (M[u][v]) return v;
    }
    return -1;
}

// スタックを用いた深さ優先探索
void dfs_visit(int r) {
    for (int i = 0; i < n; i++)
        nt[i] = 0;

    stack<int> S;
    S.push(r);
    color[r] = GRAY;
    d[r] = ++tt;

    while (!S.empty()) {
        int u = S.top();
        int v = next(u);
        if (v != -1) {
            if (color[v] == WHITE) {
                color[v] = GRAY;
                d[v] = ++tt;
                S.push(v);
            }
        } else {
            S.pop();
            color[v] = BLACK;
            f[u] = ++tt;
        }
    }
}

void dfs() {
    // 初期化
    for (int i = 0; i < n; i++) {
        color[i] = WHITE;
        nt[i] = 0;
    }
    tt = 0;

    // 未訪問のuを始点として深さ優先探索
    for (int u = 0; u < n; u++) {
        if (color[u] == WHITE)
            dfs_visit(u);
    }
    for (int i = 0; i < n; i++) {
        cout << i+1 << " " << d[i] << " " << f[i] << endl;
    }
}

int main() {

    int u, k, v;

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            M[i][j] = 0;
        }
    }
    
    for (int i = 0; i < n; i++) {
        cin >> u >> k;
        u--;
        for (int j = 0; j < k; j++) {
            cin >> v;
            v--;
            M[u][v] = true;
        }
    }
    
    dfs();

    return 0;
}


Measured memory_bytes: 3120
Q = int(input())
Pr = [0]*(10**5+1)
Ta = [0]*(10**5+1)
Tb = [0]*(10**5+1)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

for k in range(10**5+1):
    s = 10**5-k
    if s%2==1:
        if Pr[s]==1:
            continue
        div = make_divisors(s)
        if len(div)==2:
            Pr[s]=1
        div = make_divisors((s+1)//2)
        if len(div)==2:
            Pr[(s+1)//2]=1

for k in range(10**5+1):
    if Pr[k]==1 and Pr[(k+1)//2]==1:
        Ta[k]=1

Tb[1]=0
for k in range(3,10**5+1):
    Tb[k]=Ta[k]+Tb[k-2]

for i in range(Q):
    L,R = list(map(int,input().split()))
    if L==1:
        X = 0
    else:
        X = Tb[L-2]
    Y = Tb[R]
    print(Y-X)

Measured memory_bytes: 82000
a, b, c = input().split()
a = int(a)
b = int(b)
c = int(c)

for k in range(a, b * a + 1, a):
    if k % b == c:
        #print (str(k) + ' % ' + str(b) + ' = ' + str(k % b))
        print ('YES')
        break
if k == b * a:
    print ('NO')

Measured memory_bytes: 2940
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const double pi = acos(-1);

int main() {
    string s;
    cin >> s;
    ll n = s.size();

    rep(i, n) {
        if(s[i] == '?') {
            cout << 'D';
        }
        else {
            cout << s[i];
        }
    }
    
    cout << endl;
    re0;
}

Measured memory_bytes: 3756
#include<iostream>
using namespace std;
int main() {
	int a, b[100], c[100],d=0;
	cin >> a;
	for (int i = 0; i < a; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < a; i++) {
		cin >> c[i];
	
		if (b[i] - c[i] > 0)d += b[i] - c[i];
	}
	cout << d << endl;
	return 0;

}

Measured memory_bytes: 256
from functools import lru_cache


n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))


@lru_cache(maxsize=2**12)
def solve(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    ans = solve(i + 1, m) or solve(i + 1, m - A[i])
    return ans


for num in m:
    if solve(0, num):
        print("yes")
    else:
        print("no")



Measured memory_bytes: 7664
N,A=map(int,input().split())
xlist=list(map(int,input().split()))

slist=[0]
for x in xlist:
  slist.append(slist[-1]+x)
#print(slist)

dp=[[[0]*(sum(xlist)+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0]=1
for i in range(1,N+1):
  dp[i][0][0]=1
  for j in range(1,i+1):
    for k in range(1,slist[i]+1):
      dp[i][j][k]=dp[i-1][j][k]
      if k-xlist[i-1]>=0:
        dp[i][j][k]+=dp[i-1][j-1][k-xlist[i-1]]
#print(dp)

answer=0
for j in range(1,N+1):
  if j*A>sum(xlist):
    break
  answer+=dp[N][j][j*A]
  
print(answer)

Measured memory_bytes: 92124
#include<iostream>
#include<vector>

using namespace std;

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

	vector<int> ans(n);

	int d;
	int a;

	for (int i = 0; i < k; i++) {
		cin >> d;
		for (int j = 0; j < d; j++) {
			cin >> a;
			a--;
			ans[a]++;

		}
	}

	int tmp = 0;
	for (int i = 0; i < n; i++) {
		if (ans[i] == 0) tmp++;
	}


	cout << tmp << endl;



	return 0;
}

Measured memory_bytes: 3624
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using static System.Console;
using static System.Convert;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        var num = ToInt32(ReadLine());
        var txys = new int[num][];
        for (var i = 0; i < num; i++)
            txys[i] = Array.ConvertAll(ReadLine().Split(' '), int.Parse);
        var isClear = true;
        if (txys[0][1] + txys[0][2] > txys[0][0]
            ||((txys[0][1]+txys[0][2])%2!=txys[0][0]%2)) { WriteLine("No");return; }
        for (var i = 0; i < num-1; i++)
        {
            var m = Abs(txys[i][1]-txys[i+1][1])+Abs(txys[i+1][2]-txys[i][2]);
            var dift = txys[i + 1][0] - txys[i][0];
            if (m > dift||m%2!=dift%2) { isClear = false;break; }
        }
        WriteLine(isClear ? "Yes" : "No");
    }
}


Measured memory_bytes: 22336
#include <bits/stdc++.h>
using namespace std;
// 居合を終え、青い絵を覆う
int main() {
  char c;
  cin >> c;

  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
    cout << "vowel" << endl;
  } else { 
    cout << "consonant" << endl;
  }

  return 0;
}

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

int main() {
  int A,B,M;
  cin>>A>>B>>M;
  vector<int>a(A);
  vector<int>b(B);
  for(int i=0;i<A;i++) cin>>a[i];
  for(int i=0;i<B;i++) cin>>b[i];
  vector<vector<int>>data(M,vector<int>(3));
  for(int i=0;i<M;i++) cin>>data[i][0]>>data[i][1]>>data[i][2];
  int ans=a[0]+b[0];
  for(int i=0;i<M;i++){
    int x=a[data[i][0]-1]+b[data[i][1]-1]-data[i][2];
      ans=min(ans,x);
  }
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  ans=min(ans,a[0]+b[0]);
  cout<<ans<<endl;
}


Measured memory_bytes: 8576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{  ll n,ans=1;
   ll len=0;
   cin>>n;
   for(int i=1;i<=n;i++)
   {  ll x;
      cin>>x;
      if(x==0)
      {  printf("0");
         return 0;
      }
      if(ans!=-1)ans=ans*x;
      while(x/2)
      {  x=x/2;
         len++;
      }
     // cout<<len<<endl;
      if(len>=60||ans<0||ans>1000000000000000000)ans=-1;
   }
   cout<<ans;

    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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 ll;
typedef pair<ll, ll> p;

int n;
// iは嘘か本当か
vector<vector<p>> v;
int res = 0;

int check(vector<int> state){
  int count = 0;
  int n = int(state.size());

  for(int s = 0; s < n; s++){
    if(state[s] == 0) continue;
    bool flag = false;
    for(auto a : v[s]){
      int man = a.first;
      int tf = a.second;
      if(tf != state[man]) return 0;
    }
    if(!flag) count++;
  }
  chmax(res, count);
  // cout << count << endl;
  return 1;
}

void dfs(int step, vector<int> state){
  if(step == n){
    // print(state);
    check(state);
    return;
  }
  dfs(step+1, state);
  state[step] = 1;
  dfs(step+1, state);
}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  v = vector<vector<p>> (n, vector<p>());
  rep(i, n){
    int a = 0;
    cin >> a;
    rep(j, a){
      int tmp1, tmp2;
      cin >> tmp1 >> tmp2;
      tmp1--;
      v[i].push_back({tmp1, tmp2});
    }
  }
  dfs(0, vector<int> (n));
  cout << res << endl;

}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
using namespace std;
int main(){
int a[5];
for(int i=0;i<5;i++){
scanf("%d",&a[i]);
}
sort(a,a+5);
printf("%d %d %d %d %d\n",a[4],a[3],a[2],a[1],a[0]);
}

Measured memory_bytes: 2788