akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int mask = (1 << 5) - 1;
const int mod = 1e9 + 7;
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int H, W;
	scanf("%d", &H);
	scanf("%d", &W);

	ll dp[1001];
	dp[0] = 1;
	getchar_unlocked();
	getchar_unlocked();
	rep1(w, W - 1) dp[w] = (getchar_unlocked() == '.' ? dp[w - 1] : 0);
	getchar_unlocked();

	rep1(h, H - 1) {
		dp[0] = (getchar_unlocked() == '.' ? dp[0] : 0);
		rep1(w, W - 1) {
			dp[w] = (getchar_unlocked() == '.' ? dp[w] + dp[w - 1] : 0);
			if (!(h + w & mask)) dp[w] %= mod;
		}
		getchar_unlocked();
	}
	printf("%d", dp[W - 1] % mod);

	Would you please return 0;
}

Measured memory_bytes: 128
n=int(input());l=[[]for _ in[0]*n];c=[1]+[0]*(n-2)+[-1];q=[0,n-1]
for _ in[0]*q[1]:a,b=map(int,input().split());l[a-1]+=[b-1];l[b-1]+=[a-1]
while q:
  p=[]
  for i in q:
    for j in l[i]:
      if c[j]==0:c[j]=c[i];p+=[j]
  q=p
print("FSennunkeec"[sum(c)<1::2])

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

using namespace std;

using ll = long long;

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

    int res = INT_MAX;
    priority_queue<int> que;
    for (int i = 0, a; i < n; ++i) {
        cin >> a;
        que.push(a);
        res = min(res, a);
    }

    while (1 < que.size()) {
        int cur = que.top(); que.pop();
        res = min(res, cur);
        int a = cur - (int)((cur - 1) / que.top()) * que.top();
        if (1 <= cur - que.top() && a < cur)
            que.push(a);
    }

    return min(res, que.top());
}

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

    cout << Solve() << endl;

    return 0;
}


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a;
	int b;
	int k;
	int t;
	cin>>a>>b>>k;
	for(int i=a;i<a+k&&i<b;i++)
	{
		if(i==a)
			cout<<i;
		else
			cout<<endl<<i;
		t=i;
	}
	if(b-k<=t)
	{
		for(int i=t+1;i<=b;i++)
		{
			cout<<endl<<i;
		}
	}
	else
	{
		for(int i=0;i<k;i++)
		{
			cout<<endl<<b-k+i+1;
		}
	}
	return 0;
} 

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
H,W = map(int,input().split())
grid = []
for _ in range(H):
  grid.append(list(input()))

L = [ [0]*W for _ in range(H) ]
R = [ [0]*W for _ in range(H) ]
U = [ [0]*W for _ in range(H) ]
D = [ [0]*W for _ in range(H) ]

for i in range(H):
  for j in range(W):
    if j-1 >= 0:
      L[i][j] = L[i][j-1]
    if i-1 >= 0:
      D[i][j] = D[i-1][j]

    if grid[i][j] == ".":
      L[i][j] += 1
      D[i][j] += 1
    else:
      L[i][j] = 0
      D[i][j] = 0

for i in range(H-1,-1,-1):
  for j in range(W-1,-1,-1):
    if j+1 < W:
      R[i][j] = R[i][j+1] 
    if i+1 < H:
      U[i][j] = U[i+1][j]
    if grid[i][j] == ".":
      R[i][j] += 1
      U[i][j] += 1
    else:
      R[i][j] = 0
      U[i][j] = 0

res = 0
for i in range(H):
  for j in range(W):
    if grid[i][j] == ".":
      res = max(res, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

print(res)

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ALL(a) begin(a),end(a)
#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v) {
  for (T& x: v) s >> x;
  return s;
}
inline void Yes(bool f=true){cout<<(f?"Yes":"No")<<endl;}
inline void YES(bool f=true){cout<<(f?"YES":"NO")<<endl;}
#define ANS(a) cout<<a<<endl

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    int N,K; cin >>N>>K;
    string S; cin >>S;
    S[K-1] = tolower(S[K-1]);
    cout << S << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<string> s(n);
  vector<int> t(n);
  string x;
  for (int i = 0; i < n; i++)
    cin >> s[i] >> t[i];
  cin >> x;
  
  int count = 0;
  bool flag = false;
  for (int i = 0; i < n; i++) {
    if (s[i] == x) {
      flag = true;
      continue;
    }
    if (flag)
      count += t[i];
  }
  
  cout << count << endl;
  
  return 0;
}


Measured memory_bytes: 256
n = int(input())
s1 = input()
s2 = input()

for i in range(1,n+1):
    #print(s1[i-1:],s2[:n-i+1])
    if s1[i-1:] == s2[:n-i+1]:
        #print((s1[:(i-1)]+s2))
        print(len(s1[:(i-1)]+s2))
        exit()
print(len(s1+s2))

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using vi = vector<int64_t>;
using vvi = vector<vi>;
using ll = int64_t;
using P = pair<ll,ll>;
ll INF = 1000000007;
// ll INF = 9223372036854775807;
// ll INF = 998244353;

int main() {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    string s;
    cin >> s;
    if(s.size()==3) reverse(s.begin(), s.end());
    cout << s << endl;
}

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

using namespace std;

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

int main() {
	int n, h = 0;
	cin >> n;
	while (n >= 500)
		n -= 500, h += 1000;
	while (n >= 5)
		n -= 5, h += 5;
	cout << h;
}

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

int64 solve(int N, int K) {
    int64 res = 0;
    for(int b = K + 1; b <= N; ++b) {
        int t = N / b;
        int n = b - K;
        int r = N % b;
        int m = max(0, r - K + 1);
        if(b == N) t = 1, m = 0;
        res += (int64)t * n + m;
    }
    return res;
}

int main() {
    int N, K;
    cin >> N >> K;
    cout << (K == 0 ? (int64)N * N : solve(N, K)) << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cctype>
using namespace std;
 
#define DEBUG(x) cerr << #x << " = " << x << endl
 
typedef string::const_iterator iter;
 
string fstOp, sndOp, thdOp;
 
typedef long long i64;
 
i64 fst(iter& p);
i64 snd(iter& p);
i64 thd(iter& p);
i64 factor(iter& p);
i64 number(iter& p);
 
i64 fst(iter& p) {
	// cerr << "fst(" << *p << ")" << endl;
	i64 r = snd(p);
	while(true) {
		if(*p == '=') break;
		i64 idx = find(fstOp.begin(), fstOp.end(), *p) - fstOp.begin();
		if(idx == fstOp.size()) {
			break;
		}
		char op = fstOp[idx];
		p++;
		i64 res = snd(p);
		if(op == '+') r += res;
		if(op == '-') r -= res;
		if(op == '*') r *= res;
	}
	return r;
}
i64 snd(iter& p) {
	// cerr << "snd(" << *p << ")" << endl;
	i64 r = thd(p);
	while(true) {
		i64 idx = find(sndOp.begin(), sndOp.end(), *p) - sndOp.begin();
		if(idx == sndOp.size()) {
			break;
		}
		char op = sndOp[idx];
		p++;
		i64 res = thd(p);
		if(op == '+') r += res;
		if(op == '-') r -= res;
		if(op == '*') r *= res;
	}
	return r;
}
i64 thd(iter& p) {
	// cerr << "thd(" << *p << ")" << endl;
	i64 r = factor(p);
	while(true) {
		i64 idx = find(thdOp.begin(), thdOp.end(), *p) - thdOp.begin();
		if(idx == thdOp.size()) {
			break;
		}
		char op = thdOp[idx];
		p++;
		i64 res = factor(p);
		if(op == '+') r += res;
		if(op == '-') r -= res;
		if(op == '*') r *= res;
	}
	return r;
}
 
i64 factor(iter& p) {
	if(*p == '(') {
		p++;
		i64 res = fst(p);
		p++;
		return res;
	}
	return number(p);
}
 
i64 number(iter& p) {
	i64 res = 0;
	while(isdigit(*p)) {
		res *= 10;
		res += *p - '0';
		p++;
	}
	return res;
}
 
 
int main() {
	string s; cin >> s;
	s += "=";
	iter it;
 
	i64 maxValue = 1LL << 63;
 
	fstOp = "+"; sndOp = "-"; thdOp = "*";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
	fstOp = "+"; sndOp = "*"; thdOp = "-";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
	fstOp = "-"; sndOp = "+"; thdOp = "*";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
	fstOp = "-"; sndOp = "*"; thdOp = "+";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
	fstOp = "*"; sndOp = "+"; thdOp = "-";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
	fstOp = "*"; sndOp = "-"; thdOp = "+";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
 
	fstOp = "+-*"; sndOp = ""; thdOp = "";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
 
	fstOp = "+"; sndOp = "-*"; thdOp = "";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
	fstOp = "-"; sndOp = "*+"; thdOp = "";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
	fstOp = "*"; sndOp = "+-"; thdOp = "";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
 
	fstOp = "+-"; sndOp = "*"; thdOp = "";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
	fstOp = "-*"; sndOp = "+"; thdOp = "";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
	fstOp = "*+"; sndOp = "-"; thdOp = "";
	it = s.begin();
	maxValue = max(maxValue, fst(it));
 
	cout << maxValue << endl;
}

Measured memory_bytes: 1200
/*																													   
 Templatka c++ Kacper Fis																							   																											   //
*/																													  
																								   
#include <bits/stdc++.h>																							   
																													   
using namespace std; 																								   
																													   
const int INF = 1000000001;																						   
const float PI = 3.14;																								   
typedef long long LL;																								   
																													   
typedef vector<int> vi;																								   
typedef list<int> li;																								   
typedef queue<int> qi; 																								   
typedef pair<int,int> ii; 																							   
typedef map<string,int> msi; //np msi['nazwa'] = 'liczba'															   
typedef vector<ii> vii; //vector par<int>, do tworzenia tablicy dla grafów wagowych #dijkstra #Bellman_Ford			   
typedef priority_queue< ii, vector<ii>, greater<ii> > pq; //kolejka priorytetowa vectorów par(top()=min) #dijkstra	   
																													   																				   
vector<ii>::iterator iter;																							   
																													   																				   
#define print_list(x) for(it = (x).begin(); it != (x).end(); it++) {cout << *it << " ";}							   
#define print_vector(x) for(it2 = (x).begin(); it2 != (x).end(); it2++) {cout << *it2 << " ";}						   
#define search_list(x) for(it = (x).begin(); it != (x).end(); it++)													   
#define search_vector(x) for(it2 = (x).begin(); it2 != (x).end(); it2++);											   
#define pb(x) push_back(x) 																							   
#define pf(x) push_front(x)																							   
#define mp(x, y) make_pair(x, y)                                                                                       
///////////////////////////////////////////////GLOBAL DEFINITIONS////////////////////////////////////////////////////////



///////////////////////////////////////////////////FUNCTIONS/////////////////////////////////////////////////////////////



/////////////////////////////////////////////////////MAIN////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])																					 
{ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);                  												       
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    
	int n;
	string s;
	
	cin >> n >> s;
	
	for(int i = 0; i < s.size(); i++){
		//cout << endl << "to: " << (int)s[i] + n << endl;
		if((int)s[i] + n > 90){
			int roznica = ((int)s[i] + n) - 90;
			//cout << "roznica: " << roznica << endl;
			char c;
			c = (roznica + 64);
			cout << c;
			
		}
		else{
			char c = ((int)s[i] + n);
			cout << c;
		}
	}
	
	
	
	
	
	
	
	return 0;
}


Measured memory_bytes: 256
import sys
Input = sys.stdin.readline

A, B, K = map(int, Input().split())

if K < ((B-A) // 2) + 1:
    for i in range(K):
        print(A+i)
    for i in range(K):
        print(B-K+i+1)
else:
    for n in range(A, B+1):
        print(n)

Measured memory_bytes: 3060
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()

def func(S, index, cnt):
    ans = 0
    if index == 20:
        if cnt == 0:
            return 0
        S_ = list(S)
        for i in range(20):
            if S_[i] != '?':
                continue
            for j in range(10):
                S_[i] = str(j)
                if int(''.join(S_).replace('?', '9')) > N:
                    break
                else:
                    ans += 10 ** S_.count('?')
        ans *= (-1) ** (cnt + 1)
        return ans
    ans += func(S, index + 1, cnt)
    if index <= 16:
        S_ = list(S)
        S_[index] = '5'
        S_[index + 1] = '1'
        S_[index + 3] = '3'
        ans += func(S_, index + 4, cnt + 1)
    return ans

S = ['?'] * 20
print func(S, 0, 0)



Measured memory_bytes: 5088
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr int inf = INT32_MAX/2;
constexpr ll INF = LLONG_MAX/2;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */
 
/* --------------------テンプレート------------------ */
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
/* ----------------------end----------------------- */
 
/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
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 ;
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */

signed main() {
  int n;cin >> n;
  map<int,int> mp;
  rep(i,n) {
	  int a;cin >> a;
	  mp[a]++;
  }
  vector<P> v;
  for(auto p:mp) v.pb({p.first,p.second});
  resort(v);
  //for(auto p:v) cout << p.first << " " << p.second << endl;
  int k=0,l=0;
  rep(i, v.size()) {
	  //cout << "OK" << endl;
	  if(k>0&&l>0) break;
	  if(k==0&&l==0) {
		  if(v[i].second>=4) k=v[i].first,l=v[i].first;
		  else if(v[i].second>=2) k=v[i].first;
	  }
	  else if(k>0) {
		  if(v[i].second>=2) l=v[i].first;
	  }
  }
  cout << k*l << endl;
  return 0;
}

Measured memory_bytes: 11412
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int count = 0;
		for (int i = 0; i < n; i++) {
			int x = sc.nextInt();
			if (a <= x && x < b) {
				count++;
			}
		}
		System.out.println(n - count);
	}
}


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

int main(){
    int x[5];

    for(int i = 0; i < 5; i++)
        cin >> x[i];

    int ans = 0;
    for(int i = 0; i < 5; i++){
        if(x[i] == 0)
            ans = i + 1;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  int a, b, c;
  cin >> a >> b >> c;

  if (a == b && b == c){
    cout << 1 << endl;
  }else if(a == b || b == c || c == a){
    cout << 2 << endl;
  }else{
    cout << 3 << endl;
  }
}


Measured memory_bytes: 3620
n = 0

def format_input(filename = None):
	global n
	if filename == None:
		n = int(input())

	elif filename == '__random__':
		from random import randint as rng
		n = rng(1, 10**6)
		print(n)

def get_answer():
	fizzbuzz = ((n // 15) * (n // 15 + 1)) // 2 * 15
	fizz = ((n // 3) * (n // 3 + 1)) // 2 * 3 - fizzbuzz
	buzz = ((n // 5) * (n // 5 + 1)) // 2 * 5 - fizzbuzz
	answer = (n * (n + 1)) // 2 - fizz - buzz - fizzbuzz
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)


Measured memory_bytes: 9200
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define REP(X, Y, Z) for (ll(X) = (Y); (X) < (Z); (X)++)
#define REV(X, Y, Z) for (ll(X) = (Y); (X) > (Z); (X)--)

using namespace std;
using ll = long long;
using dll = deque<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using usll = unordered_set<ll>;
using umll = unordered_map<ll, ll>;
using sll = stack<int>;
using vll = vector<ll>;
using vvll = vector<vll>;

constexpr ll kMod = 1e9 + 7;

ll gcd(ll a, ll b) {
  if (a < b) {
    return gcd(b, a);
  }
  ll c = a % b;
  while (c != 0) {
    a = b;
    b = c;
    c = a % b;
  }
  return b;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

int main() {
  init();

  ll X, Y;
  cin >> X >> Y;
  ll ans = 0;
  while (X <= Y) {
    X *= 2;
    ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 384
S = list(input())
N = len(S)

def check(st):
    rev = st[::-1]

    if rev == st:
        return True
    else:
        return False

if check(S) and check(S[0:(N-1)//2]) and check(S[(N+3)//2 -1:N]):
    print("Yes")
else:
    print("No")
    

Measured memory_bytes: 2940
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define node(a,b,c)   mp(mp(a,b),c)

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=100005;
 main()

{
    fast
    int x;
    cin>>x;
    if(x==2)
    {
        cout<<"2 2"<<endl;
        cout<<"1 2 0"<<endl;
        cout<<"1 2 1"<<endl;
        return 0;
    }
    x--;
    int cur=0;
    while(1)
    {
        int val=(1LL<<(cur+1));
        if(val<=x)cur++;
        else break;
    }
    vector<pair<pi,int>>vec;
    f(i,1,cur)
    {
        vec.pb(node(i,i+1,0));
        int val=(1LL<<(i-1));
        vec.pb(node(i,i+1,val));
    }
    int now=(1LL<<cur);
    int baki=x-(now-1);
    int n=cur+1;
    while(1)
    {
        for(int i=n-1;i>=1;i--)
        {
            int rgt=now+(1LL<<(i-1))-1;
            if(rgt<=x)
            {
               vec.pb(node(i,n,now));
               now=rgt+1;
               break;
            }
        }
        if(now>x)break;
    }
    cout<<cur+1<<" "<<vec.size()<<endl;
    for(auto z:vec)
    {
        cout<<z.fi.fi<<" "<<z.fi.si<<" "<<z.si<<endl;
    }
    return 0;

}





































Measured memory_bytes: 3580
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vs){
  for (const T& v : vs) os << v << " ";
  return os;
}

int main() {
  int N, K; cin >> N >> K;
  vector<int> A(N); cin >> A;
  vector<bool> dp(K + 1, false);
  for (int i = 1; i <= K; ++i) {
    for (int j : A) {
      if (i - j < 0) break;
      dp[i] = dp[i] || !dp[i-j];
    }
  }
  if (dp[K]) cout << "First" << endl;
  else       cout << "Second" << endl;
}


Measured memory_bytes: 3640
// warm heart, wagging tail,and a smile just for you!
//                                                                     ███████████
//                                                                   ███╬╬╬╬╬╬╬╬╬╬███
//                                                                ███╬╬╬╬╬████╬╬╬╬╬╬███
//                                            ███████████       ██╬╬╬╬╬████╬╬████╬╬╬╬╬██
//                                      █████████╬╬╬╬╬████████████╬╬╬╬╬██╬╬╬╬╬╬███╬╬╬╬╬██
//                               ████████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬██╬╬╬╬╬╬╬██
//                             ████╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬╬╬╬╬╬██
//                           ███╬╬╬█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬███╬╬╬╬╬╬╬█████
//                         ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬████████╬╬╬╬╬██
//                       ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬╬╬╬╬███
//                     ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬██
//                 ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬████
//     █████████████╬╬╬╬╬╬╬╬██╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬██████
//   ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬██████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████╬╬╬╬╬╬╬███████████╬╬╬╬╬╬╬╬██╬╬╬██╬╬╬██
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬█╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬██
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬▓▓▓▓▓▓╬╬╬████╬╬████╬╬╬╬╬╬╬▓▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬███
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬█████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████████
//   ███╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
//       ██████████████  ████╬╬╬╬╬╬███████████████████████████╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████
//                         ███████                           █████  ███████████████████
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<vector<P> > Graph;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

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

  int n;
  cin >> n;

  vec a(n);
  REP(i,n) cin >> a[i];
  
  vec x(n),y(n);
  x[0] = a[0], y[n-1] = a[n-1];
  REP(i,n-1) x[i+1] = __gcd(x[i],a[i+1]);
  RREP(i,n-1) y[i] = __gcd(a[i],y[i+1]);

  int ans = max(x[n-2],y[1]);
  FOR(i,1,n-1) ans = max(ans,__gcd(x[i-1],y[i+1]));

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 2560
def BubbleSort(C, N):

    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j][1] < C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]
    return C

def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j][1] < C[minj][1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C

def isStable(C1, C2, N):
    if C1 != C2:
        return "Not stable"
    return "Stable"

Num = int(input())
Cards = [x for x in input().split()]
card1 = BubbleSort(list(Cards), Num)
card2 = SelectionSort(list(Cards), Num)

print(" ".join(card1))
print(isStable(card1, card1, Num))
print(" ".join(card2))
print(isStable(card1, card2, Num))



Measured memory_bytes: 5612
//AtCoder 
#include <bits/stdc++.h>
using namespace std;
using lli=int64_t;
 
int main() {
#if LOCAL&01
  	std::ifstream in("input.txt");
  	std::cin.rdbuf(in.rdbuf());
#endif
    int N,K;
    cin>>N>>K;
 
    auto calc = [&](lli num){
        lli cnt=1;
        while(num<K){
            num *= 2;
            cnt *= 2;
        }
        return (double)1/(double)cnt;
    };
   
    double t=0.0;
    double tmp = (double)1/(double)N;
    for (int i=1;i<=N;++i) {
        if (i>=K) {
            break;
        } else {
            t += (double)calc(i);
        }
    }
    //t /= (double)N;
    //t += double(max(N-K+1,0))/(double)N;
    t += (double)(max(N-K+1,0));
    t /= (double)N;
    cout<<fixed<<std::setprecision(10)<<t<<endl;
    return 0;
}

Measured memory_bytes: 256
"""everything has a cost!"""

from math import *
import random, functools, collections, sys

__author__ = 'p7x'


# sys.stdin = open('in.txt', 'r')
# sys.stdout = open('out.txt', 'w')
# sys.stderr = open('err.txt', 'w')


if __name__ == '__main__':
    n = int(input())
    print(int(1000*ceil(n/1000)-n))


Measured memory_bytes: 76744
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
char str[600][600];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
long double ijk[600][600];
long double ijk2[600][600];
long double eps=1e-10L;
pair<long double,pair<int,int> > v[1000000];
int t[600][600];
int main(){
	int a,b;
	scanf("%d%d",&b,&a);
	for(int i=0;i<a;i++)scanf("%s",str[i]);
	for(int i=0;i<a;i++)for(int j=0;j<b;j++)
		ijk[i][j]=ijk2[i][j]=1e20L;
	int sr,sc,gr,gc;
	queue<pair<int,int> > Q;
	int cnt=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(str[i][j]=='s'){sr=i;sc=j;}
			if(str[i][j]=='g'){
				gr=i;gc=j;
				ijk[i][j]=0;
				Q.push(make_pair(i,j));
			}
		}
	}
	for(int i=0;i<a;i++)for(int j=0;j<b;j++)if(str[i][j]!='#'&&str[i][j]!='*'&&str[i][j]!='g')cnt++;
	while(Q.size()){
		int row=Q.front().first;
		int col=Q.front().second;Q.pop();
		for(int i=0;i<4;i++){
			if(0<=row+dx[i]&&row+dx[i]<a&&0<=col+dy[i]&&col+dy[i]<b&&str[row+dx[i]][col+dy[i]]!='#'&&str[row+dx[i]][col+dy[i]]!='*'&&ijk[row+dx[i]][col+dy[i]]>eps+ijk[row][col]+1){
				ijk[row+dx[i]][col+dy[i]]=ijk[row][col]+1;
				Q.push(make_pair(row+dx[i],col+dy[i]));
			}
		}
	}
	for(int i=0;i<a;i++)for(int j=0;j<b;j++){
		if(str[i][j]=='*'){
			ijk2[i][j]=0;
			Q.push(make_pair(i,j));
		}
	}
	while(Q.size()){
		int row=Q.front().first;
		int col=Q.front().second;Q.pop();
		for(int i=0;i<4;i++){
			if(0<=row+dx[i]&&row+dx[i]<a&&0<=col+dy[i]&&col+dy[i]<b&&str[row+dx[i]][col+dy[i]]!='#'&&str[row+dx[i]][col+dy[i]]!='*'&&ijk2[row+dx[i]][col+dy[i]]>eps+ijk2[row][col]+1){
				ijk2[row+dx[i]][col+dy[i]]=ijk2[row][col]+1;
				Q.push(make_pair(row+dx[i],col+dy[i]));
			}
		}
	}
	int sz=0;
	
	long double L=0;
	long double R=0;
	int n=0;
	int m=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(str[i][j]=='s'||str[i][j]=='.'){
				if(ijk[i][j]<1e10L&&ijk2[i][j]<1e10L)
					v[sz++]=make_pair(ijk[i][j]-ijk2[i][j],make_pair(i,j));
				else if(ijk[i][j]<1e10L){
					n++;
					L+=ijk[i][j];
				}
				else if(ijk2[i][j]<1e10L){
					m++;
					R+=ijk2[i][j];
				}
			}
		}
	}
	std::sort(v,v+sz);
	for(int i=0;i<a;i++)for(int j=0;j<b;j++){
		if(ijk[i][j]<1e10L&&ijk2[i][j]<1e10L)
		if(str[i][j]=='s'||str[i][j]=='.')R+=ijk2[i][j];
	}
	long double ret=ijk[sr][sc];
//	for(int i=0;i<a;i++)for(int j=0;j<b;j++)
	//	printf("%d %d: %Lf %Lf\n",i,j,ijk[i][j],ijk2[i][j]);
	for(int i=0;i<=sz;i++){
		if(t[sr][sc]){
			break;
		}
		if(n+i){
		//	printf("%d: %Lf\n",i,ijk2[sr][sc]+R/(sz-i)*((long double)sz/i-1)+L/(n+i));
			ret=min(ret,ijk2[sr][sc]+R/(m+sz-i)*((long double)(sz+m+n)/(n+i)-1)+L/(n+i));
		}
		if(i<sz){
			t[v[i].second.first][v[i].second.second]=1;
			L+=ijk[v[i].second.first][v[i].second.second];
			R-=ijk2[v[i].second.first][v[i].second.second];
		}
	}
	printf("%.12Lf\n",ret);
}

Measured memory_bytes: 44272
/* 根つき木　*/
#include <stdio.h>

#define MAX 100005     /*　最大ノード数　*/
#define NIL -1

typedef struct{

  int l;             /* 一番左の子ども　*/
  int r;             /* すぐ右隣の兄弟　*/
  int p;
}Node;

Node T[MAX];         /*　根つき木　*/
int n;               /* ノード数　*/
int depth[MAX];      /* 各ノードの深さ　*/

/*　関数プロトタイプ宣言　*/
void GetDepth(int, int);
void print(int);

int main()
{
  int i, j, d, v, c, l, root;

  scanf("%d", &n);

  /* 根付き木をNILで初期化　*/
  for( i = 0; i<n; i++ )
    {
      T[i].l = NIL;
      T[i].r = NIL;
      T[i].p = NIL;
    }

  /* 根付き木の各ノードを読み込み　*/
  for( i = 0; i<n; i++ )
    {
      scanf("%d%d", &v, &d);
      for( j = 0; j<d; j++ )
	{
	  scanf("%d", &c);
	  if( j == 0 )
	    T[v].l = c;     /* 一番左の子ノードの場合　*/
	  else
	    T[l].r = c;     /*　それ以外の子ノードの場合　*/
	  
	  l = c;
	  T[c].p = v;       /* そのノードのparentを設定　*/
	}
    }

  /* ルートノードを求める　*/
  for( i = 0; i<n; i++ )
    {
      if( T[i].p == NIL )
	{
	  root = i;
	  break;
	}
    }

  /*　各ノードの深さを求める　*/
  GetDepth(root, 0);

  /*　根付きノードの情報を表示*/
  for( i = 0; i<n; i++ )
    print(i);
  
  return 0;
}

/*　各ノードの深さを再帰的に求める関数　
    引数：　u -> その時着目しているノードの番号　　p ->　その時着目しているノードの深さ　*/
void GetDepth(int u, int p)
{
  depth[u] = p;
  
  if( T[u].r != NIL )
    GetDepth(T[u].r, p);          /*　右隣の兄弟ノードに同じ深さを設定　*/
  if( T[u].l != NIL )
    GetDepth(T[u].l, p+1);        /* そのノードの一番左の子ノードの深さを求める*/
}

/*　ノードT[u]の情報を出力する関数　*/
void print(int u)
{
  int c;

  printf("node %d: parent = %d, depth = %d, ", u, T[u].p, depth[u]);
  
  if( T[u].p == NIL )
    printf("root, ");
  else if( T[u].l == NIL )
    printf("leaf, ");
  else
    printf("internal node, ");

  /* ノードT[u]の子どもを表示　*/
  c = T[u].l;
  printf("[");
  while( c != NIL )
    {
      printf("%d", c);
      if( T[c].r != NIL )
	printf(", ");
      c = T[c].r;
    }
  printf("]\n");
}



Measured memory_bytes: 6368
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main(void) {
  ios::sync_with_stdio(false);
  int A, B, Q;
  cin >> A >> B >> Q;
  vector<int64_t> S(A);
  rep(i, A) cin >> S[i];
  vector<int64_t> T(B);
  rep(i, B) cin >> T[i];

  rep(i, Q) {
    int64_t x;
    cin >> x;
    auto sitr = lower_bound(S.begin(), S.end(), x);
    auto titr = lower_bound(T.begin(), T.end(), x);

    // sitr -> titr or titr -> sitr
    int64_t dist0 = 1e10 * 4;
    if(sitr != S.end() && titr != T.end()) {
      dist0 = max(*sitr, *titr) - x;
    }

    // sitr -> tir-1
    int64_t dist1 = 1e10 * 4;
    if (sitr != S.end() && titr != T.begin()) {
      --titr;
      int64_t dist1a = (*sitr - x) + (*sitr - *titr);
      int64_t dist1b = (x - *titr) + (*sitr - *titr);
      dist1 = min(dist1a, dist1b);
      ++titr;
    }

    // sitr-1 -> titr
    int64_t dist2 = 1e10 * 4;
    if (sitr != S.begin() && titr != T.end()) {
      --sitr;
      int64_t dist2a = (*titr - x) + (*titr - *sitr);
      int64_t dist2b = (x - *sitr) + (*titr - *sitr);
      dist2 = min(dist2a, dist2b);
      ++sitr;
    }

    // sitr -1 -> titr-1
    int64_t dist3 = 1e10 * 4;
    if (sitr != S.begin() && titr != T.begin()) {
      --sitr;
      --titr;
      dist3 = x - min(*sitr, *titr);
    }

    int64_t answer = min(min(dist0, dist1), min(dist2, dist3));
    cout << answer << endl;
  }
  return 0;
}


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

using namespace std;
string input_s;
int c_char[29];
int H,W;
int main() {
	int c_one=0;
	int c_two=0;
	cin >> H >> W;
	if(H%2==1&&W%2==1) c_one++;
	if(H%2==1) c_two+=W/2;
	if(W%2==1) c_two+=H/2;
	for(int i=0;i<H;i++) {
		cin >> input_s;
		for(int j=0;j<W;j++) c_char[(int)(input_s[j]-'a')]++;
	}
	for(int i=0;i<26;i++) {
		if(c_char[i]%2) {
			c_one--;
			c_char[i]--;
		}
	}
	for(int i=0;i<26;i++) {
		if(c_char[i]%4==2) c_two--;
	}
	if(c_one>=0&&c_two>=0) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
//"I'll live the focused life, because it's the best kind there is" - Winifred Gallagher
#include<bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << ": " << a << endl

int32_t main(){
	//freopen("input.txt","r",stdin);
	int n, m; cin>>n>>m;
	if(n > m){
		for(int i =0; i<n; ++i) cout<<m;
	}
	else{
		for(int i =0; i<m; i++) cout<<n;
	}
	
	return 0;
}



Measured memory_bytes: 256
#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()
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; }
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 a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    
    int k;
    cin >> k;
    
    cout << a[k-1] << endl;
    


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

Measured memory_bytes: 256
using System;
using static System.Console;
using static System.Math;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace atcoder
{
    class Program
    {
        //メイン関数
        static void Main(string[] args)
        {
            string N = Read();
            bool check = false;

            if (int.Parse(N.Substring(0, 1)) == 9 || int.Parse(N.Substring(1, 1)) == 9) WriteLine("Yes");
            else WriteLine("No");
            
        }

        //メインじゃない関数
        private static string Read() { return ReadLine(); }
        private static int ReadI() { return int.Parse(ReadLine()); }
    }
}


Measured memory_bytes: 13140
n = gets.to_i
min = last = gets.to_i
profits = []
(n-1).times{
  current = gets.to_i
  profits<<(current-min) if (current > last) || (profits.bsearch{|i| i >= 0} == nil)
  min = current if (current < min)
  last = current
}
puts profits.max

Measured memory_bytes: 9744
s = list(input())
s = [int(i) for i in s]
for i in range(0, 8):
    t = str(s[0])
    a = s[0]
    c = format(i, '03b')
    for j in range(3):
        if c[j] == "0":
            a -= s[j+1]
            t += "-"+str(s[j+1])
        else:
            a += s[j+1]
            t += "+"+str(s[j+1])
    if a == 7:
        print(t+"=7")
        break

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	while(a>=0&&c>=0){
		c-=b;
		if(c<=0){
			cout<<"Yes";
			return 0;
		}
		a-=d;
		if(a<=0){
			cout<<"No";
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define M (long long)1000000007
using namespace std;
ll dp1[100005],dp2[100005];
vector<ll> adj[100005];
void dfs(ll V,ll pV){
	ll prod1=1;int prod2=1;
	for(auto x:adj[V]){
		if(x==pV)continue;
		dfs(x,V);
		prod1=(prod1*(dp1[x]+dp2[x]))%M;
		prod2=(prod2*dp1[x])%M;
		
	}
	dp1[V]=prod1;
	dp2[V]=prod2;
}
int main() {
     ll n,a,b;
     cin>>n;
     for(ll i=0;i<n-1;i++){
     	cin>>a>>b;
     	adj[a].pb(b);
     	adj[b].pb(a);
     }
     dfs(1,0);
     cout<<(dp1[1]+dp2[1])%M<<endl;
	return 0;
}

Measured memory_bytes: 14208
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long sum[100010] = {};
vector<long long> vec;
int main(){
	long long i,n,m,v,p,ans = 0;
	cin >> n >> m >> v >> p;
	for(i=0;i<n;i++){
		long long a; cin >> a;
		vec.push_back(a);
	}
	if(p==n){
		cout << n << endl;
		return 0;
	}
	sort(vec.begin(),vec.end());
	for(i=1;i<=n;i++){
		sum[i] = sum[i - 1] + vec[i - 1];
	}
	int posi = upper_bound(vec.begin(),vec.end(),vec[0] + m) - vec.begin();
	for(i=n - p + 1;i<=posi;i++){
		long long vv = max(v - (n - i) - 1,0LL);
		long long x = sum[i] - sum[1];
		if((vec[0] + m)*(i - 1)>= x + m*vv){
			cout << n << endl;
			return 0;
		}
	}
	int l = 0,r = n - 1;
	while(r - l>1){
		int mid = (l + r)/2;
		int pos = upper_bound(vec.begin(),vec.end(),vec[mid] + m) - vec.begin();
		if(mid>=n - p){
			r = mid;
			continue;
		}
		bool flag = false;
		for(i=n - p + 1;i<=pos;i++){
			long long vv = max(v - (n - i) - (mid + 1),0LL);
			long long x = sum[i] - sum[mid + 1];
			if((vec[mid] + m)*(i - mid - 1)>= x + m*vv){
				flag = true;
				break;
			}
		}
		if(flag) r = mid;
		else l = mid;
	}
	for(i=0;i<n;i++){
		if(vec[i]>=vec[r]){
			ans++;
		}
	}
	cout << ans << endl;
}

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

#define REP(i,s,n) for(int i=s; i<n; ++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

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

int main(){

	int n;
	cin >> n;
	vector<ll> t(n);
	rep(i, n) cin >> t[i];
	sort(t.begin(), t.end());

	if(n == 1){
		cout << t[0] << endl;
		return 0;
	}

	ll ans = 0;
	for(int i = n - 1; i > 0; i -= 2){
		if(i == 1){
			ans += t[1];
			break;
		}
		if(i == 2){
			ans += (t[2]+t[1]+t[0]);
			break;
		}
		ans += min(t[i] + t[0] + t[i-1] + t[0], t[1] + t[0] + t[i] + t[1]);
	}

	cout << ans << endl;


	return 0;
}



Measured memory_bytes: 3160
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using P   = pair<ll, ll>;
using mat = vector<vector<ll>>;

void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

const ll INF = 1e16;
const ll MOD = 1e9 + 7;
const ld EPS = 1e-12;

template <typename T>
void dump(T x) { cout << x << endl; }
void dumpf(ld x, int t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
inline ll mod(ll a, ll b) {
	if (a > 0) return a % b;
	if (a % b == 0) return 0;
	ll x = -a / b + 1;
	a += x * b;
	return a % b;
}
ll powm(ll a, ll b, ll c) {
	if (b == 0)
		return 1;
	else if (b % 2 == 0) {
		ll d = powm(a, b / 2, c);
		return (d * d) % c;
	} else
		return (a * powm(a, b - 1, c)) % c;
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

//ll dx[4] = {1, 0, -1, 0};
//ll dy[4] = {0, 1, 0, -1};

int main() {
	IOS;
	ll m, k;
	cin >> m >> k;
	int n = 1;
	for (int i = 0; i < m; i++) {
		n *= 2;
	}
	if ((m == 0 || m == 1) && k != 0 || k >= n) {
		dump(-1);
		return 0;
	}
	if (m == 0) {
		cout << "0 0" << endl;
		return 0;
	}
	if (m == 1) {
		cout << "0 0 1 1" << endl;
		return 0;
	}
	vector<ll> a(n);
	for (int i = 0; i < n; i++) {
		a[i] = i;
	}
	for (int i = 0; i < n; i++) {
		if (i != k) cout << i << " ";
	}
	cout << k << " ";
	for (int i = n - 1; i >= 0; i--) {
		if (i != k) cout << i << " ";
	}
	cout << k << endl;
	return 0;
}

Measured memory_bytes: 2816
S = input()

def stringDevider(S):    
    odd_letters = [S[l] for l in range(len(S)) if l % 2 == 0] 
    even_letters = [S[l] for l in range(len(S)) if l % 2 == 1] 
    
    return odd_letters, even_letters

odd_letters, even_letters = stringDevider(S)

if 'L' not in odd_letters and 'R' not in even_letters:
    print('Yes')
else :
    print('No')

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

int main()
{
    int x,counta,countb;
    cin>>x;
    
    if((x/500)!=0)
    {
        counta=(x/500);
         x=x%500;
        if((x/5)!=0)
        countb=(x/5);
    
    
    cout<<((1000*counta)+(5*countb));
    }
     else
    {
        
        if((x/5)!=0)
        countb=(x/5);
    
    cout<<(5*countb);
    }
    return 0;
}

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

using namespace std;

using int64 = long long;

constexpr int64 P = 1000000007;

// Verified: ABC133E, ABC132D, ABC130E
struct FiniteField {
 private:
  int64 x;
 public:
  FiniteField(int64 x) : x(x) {}
  FiniteField() : x(0) {}
  int64 Value() { return x; }
  inline FiniteField operator+(FiniteField o) {
    FiniteField r(*this); r += o; return r;
  }
  inline FiniteField operator-(FiniteField o) {
    FiniteField r(*this); r -= o; return r;
  }
  inline FiniteField operator* (FiniteField o) {
    FiniteField r(*this); r *= o; return r;
  }
  inline FiniteField operator/ (FiniteField o) {
    FiniteField r(*this); r /= o; return r;
  }
  inline void operator+= (FiniteField o) { x = (x + o.x) % P; }
  inline void operator-= (FiniteField o) { x = (x + P - o.x) % P; }
  inline void operator*= (FiniteField o) { x = (x * o.x) % P; }
  void operator/=(FiniteField o) {
    int64 p = P - 2; while (p) { if (p % 2) { *this *= o; } o *= o; p /= 2; }
  }
};

vector<FiniteField> MakeFactorialTable(int n) {
  vector<FiniteField> values(n + 1);
  values[0] = 1;
  for (int i = 1; i <= n; i++) {
    values[i] = values[i - 1] * i;
  }
  return values;
}

vector<vector<FiniteField>> MakeStirlingNumberSecondTable(int n, int k) {
  vector<vector<FiniteField>> table(n + 1, vector<FiniteField>(k + 1));
  table[1][1] = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= min(k, i); j++) {
      table[i][j] = table[i - 1][j] * j + table[i - 1][j - 1];
    }
  }
  return table;
};

FiniteField Power(FiniteField x, int p) {
  if (p < 0) return FiniteField(1) / Power(x, -p);
  FiniteField value = 1;
  while (p) {
    if (p % 2) value *= x;
    x *= x;
    p /= 2;
  }
  return value;
}

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

  int n, k;
  cin >> n >> k;

  if (n < k) {
    cout << 0 << endl;
    return 0;
  }

  auto factorials = MakeFactorialTable(k + 1);
  FiniteField value = 0;
  for (int i = 0; i <= k; i++) {
    value += Power(i, n) * Power(P - 1, k - i)
        / factorials[i] / factorials[k - i];
  }
  cout << value.Value() << endl;
}



Measured memory_bytes: 3180
#include<bits/stdc++.h>
using namespace std;
int main (void){
  int a,b,N,M;
  int road[55] = {};
  cin >> N >> M;
  
  for(int i = 0; i < M; i++){
    cin >> a >> b;
    a--;
    b--;
    road[a]++;
    road[b]++;
  }
  for(int i = 0; i < N; i++){
    cout << road[i] << '\n';
  }
  return 0;
}

Measured memory_bytes: 3592
using System;
using System.Collections.Generic;
using System.Linq;

public class Hello
{
    public static void Main()
    {
        var dic = new Dictionary<int, uint>();

        Console.ReadLine();
        for (int c = Console.Read(); c != -1; c = Console.Read())
        {
            if (c < 'a' || c > 'z')
                continue;
            uint count;
            dic.TryGetValue(c, out count);
            dic[c] = count + 1;
        }

        Console.WriteLine(
                (dic.Values.Aggregate(1ul, (s, v) => (s * (v + 1)) % 1000000007ul) - 1)
                    % (1000000007ul)
            );
    }
}


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

namespace C___Coloring_Colorfully
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Array.ConvertAll(Console.ReadLine().ToArray(), x => int.Parse(x.ToString()));
            var zero_one = Enumerable.Range(1, S.Count()).Select(x => x % 2).ToArray();
            var one_zero = Enumerable.Range(0, S.Count()).Select(x => x % 2).ToArray();
            int cnt1 = 0, cnt2 = 0;

            for (int i = 0; i < S.Length; i++)
            {
                if ((S[i] ^ zero_one[i]) == 1)
                    cnt1++;
                if ((S[i] ^ one_zero[i]) == 1)
                    cnt2++;
            }

            Console.WriteLine(Math.Min(cnt1, cnt2));
        }
    }
}


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

int a[100000];
int main() {
	int n, s; scanf("%d%d", &n, &s);
	rep(i, n)scanf("%d", &a[i]);
	int g = 0, sum = 0, Min = INT_MAX;
	rep(i, n) {
		while (g < n&&sum < s)sum += a[g], g++;
		if (sum >= s)Min = min(Min, g - i);
		sum -= a[i];
	}
	if (Min == INT_MAX)puts("0");
	else printf("%d\n", Min);
}

Measured memory_bytes: 3596
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var a, b string
	var an, bn int
	fmt.Scan(&a, &b)
	if len(a) > len(b) {
		fmt.Println("GREATER")
		return
	}
	if len(a) < len(b) {
		fmt.Println("LESS")
		return
	}
	for i := range a {
		an, _ = strconv.Atoi(string(a[i]))
		bn, _ = strconv.Atoi(string(b[i]))
		if an > bn {
			fmt.Println("GREATER")
			return
		}
		if an < bn {
			fmt.Println("LESS")
			return
		}
	}
	fmt.Println("EQUAL")
}


Measured memory_bytes: 512
import Data.Char
import Data.List

fukugou :: Int -> [String] -> String
fukugou n x
  | or $ map (flip isInfixOf (concat $ map (map (chr . sub n . ord)) x)) ["this", "the", "that"] = unwords $ map (map (chr . sub n . ord)) x
  | otherwise = fukugou (n+1) x
    where sub n	x
            | x - n < 97 = 26 - n + x
            |	otherwise = x - n

solve :: [[String]] -> [String]
solve [] = []
solve (x:xs)
  | f x == [] = fukugou 0 x : solve xs
  | otherwise =	period (fukugou 0 x) (f x) : solve xs
    where f x = elemIndices '.' (unwords x)
          period xs [] = xs
          period xs (n:nx) = period (take n xs ++ "." ++ drop (n+1) xs) nx

main = getContents >>= mapM_ putStrLn . solve . map words . lines

Measured memory_bytes: 3996
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,k = map(int,ipt().split())
    x1,y1,x2,y2 = map(int,ipt().split())
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
    ms = [input()+"@" for _ in range(h)]
    ms.append("@"*(w+1))
    hq = []
    al = [[10**18]*w for _ in range(h)]
    al[x1][y1] = 0
    dr = [(0,1),(1,0),(0,-1),(-1,0)]
    hpq.heappush(hq,(0,x1,y1))
    while hq:
        c,x,y = hpq.heappop(hq)
        cn = c+1
        if x == x2 and y == y2:
            print(c)
            exit()
        for dx,dy in dr:
            xx = x
            yy = y
            for i in range(k):
                xx += dx
                yy += dy
                if ms[xx][yy] == ".":
                    if al[xx][yy] > cn:
                        al[xx][yy] = cn
                        hpq.heappush(hq,(cn,xx,yy))
                    elif al[xx][yy] == cn:
                        continue
                    else:
                        break
                else:
                    break
    print(-1)

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 132968