akhauriyash/Code-Regression huggingface dataset:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <ctime>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int mod = 1000000007;
 
int n;
ll a,b,s[maxn],f[maxn][2];
int A[maxn],B[maxn];
 
void pd(ll&ret,ll val) {
  ret+=val;
  if(ret>=mod)ret-=mod;
}
 
struct BIT {
  ll c[maxn];
  void init() {
    for (int i = 0; i < maxn; i++) c[i] = 0;
  }
  int lowbit(int x) {
    return x&(-x);
  }
  void add(int x, ll y) {
    while(x<maxn) {
      pd(c[x],y);
      x+=lowbit(x);
    }
  }
  ll sum(int x) {
    ll ret=0;
    while(x>0) {
      pd(ret,c[x]);
      x-=lowbit(x);
    }
    return ret;
  }
} bit[2];
 
int bs(int l,int r, ll val) {
  int ret = -1;
  while(l<=r) {
    int m = (l+r)>>1;
    if(s[m]<=val) {
      ret=m;
      l=m+1;
    } else r=m-1;
  }
  return ret;
}
 
int main() {
  //freopen("in.cpp","r",stdin);
  while(cin>>n>>a>>b) {
  n++;
  s[1] = -1000000000000000000LL;
  for(int i=2; i<=n; i++)cin>>s[i];
  s[++n] = 2000000000000000000LL;
  bit[0].init();
  bit[1].init();
  memset(f, 0, sizeof(f));
  s[n + 1] = s[n] - s[1];
  A[1] = B[1] = 1;
  for(int i=2; i<=n; i++) {
    if(i-1>=2&&s[i]>=s[i-1]+a)A[i]=A[i-1];
    else A[i] = i;
    if(s[i]>=s[i-1]+b)B[i]=B[i-1];
    else B[i] = i;
  }
  for(int i=2; i<=n; i++) {
    if(B[i - 1] == 1) {
      pd(f[i][0], 1);
    }
    int l = max(1, B[i - 1] - 1);
    int r = i - 2;
    if (l <= r) {
      int pos = bs(1, i - 2, s[i] - a);
      if (pos != -1 && pos >= l) {
        r = min(r, pos);
        ll tmp = bit[1].sum(r);
        tmp = (tmp + mod - bit[1].sum(l - 1)) % mod;
        pd(f[i][0], tmp);
      }
    }
    bit[0].add(i, f[i][0]);
    l = A[i], r = i;
    if (l == 1) {
      pd(f[i][1], 1);
    }
    int pos = bs(1, i - 1, s[i + 1] - b);
    if (pos != -1 && pos + 1 >= l) {
      r = min(r, pos + 1);
      ll tmp = bit[0].sum(r);
      tmp = (tmp + mod - bit[0].sum(l - 1)) % mod;
      pd(f[i][1], tmp);
    }
    bit[1].add(i, f[i][1]);
  }
  cout<<f[n][1]<<endl;
  }
  return 0;
}


Measured memory_bytes: 4992
import java.util.*;

public class Main {
	public static void main (String[] args){
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		ArrayList<Character> x = new ArrayList<Character>();
		int i, j, count = 0;
		for(i = 0; i < N; i++){
			char input = sc.next().charAt(0);
			x.add(input);
			for(j = 0; j < i; j++){
				if(x.get(j).equals(input)){
					count++;
					break;
				}
			}
		}
		if((N-count) == 3){
			System.out.println("Three");
		}else{
			System.out.println("Four");
		}
	}
}


Measured memory_bytes: 23764
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
  string s;
  cin >> s;
  
  auto ap = s.find("A");
  auto zp = s.rfind("Z");
  
  cout << (zp - ap + 1) << endl;
  
  return 0;
}

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

public class Main{
    
    public static void main(String args[])throws IOException{
       long c1 = 0;
       long c2 = 0;
       long sum1 = 0;
       long sum2 = 0;
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int n = Integer.parseInt(br.readLine());
       StringTokenizer st = new StringTokenizer(br.readLine());
       for(int i=0;i<n;i++){
           long tmp = Integer.parseInt(st.nextToken());
           sum1 += tmp;
           sum2 += tmp;
           if(i%2==0){
               if(sum1<=0){
                   c1 += Math.abs(sum1)+1;
                   sum1 = 1;
               }
               if(sum2>=0){
                   c2 += Math.abs(sum2)+1;
                   sum2 = -1;
               }
           }else{
               if(sum1>=0){
                   c1 += Math.abs(sum1)+1;
                   sum1 = -1;
               }
               if(sum2<=0){
                   c2 += Math.abs(sum2)+1;
                   sum2 = 1;
               }
           }
       }
        System.out.println(Math.min(c1, c2));
    }
     
}



Measured memory_bytes: 35648
#include <bits/stdc++.h>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

#define all(v)   v.begin(), v.end()
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define THINK_TWICE_CODE_ONCE cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define isOdd(n)    (n&1)
#define LLMAX LLONG_MAX
#define LLMIN LLONG_MIN
#define IMN INT_MIN
#define IMX INT_MAX
#define pow(n, m) power((ll)n, (ll)m)
#define numOfDigits(n)  ((n)? (ll)(log10(n)+1) : 1)
#define mem(x, val)    memset(x, val, sizeof(x))
#define MOD 1000000007

typedef long long ll;
typedef long double ld;
typedef double dd;
typedef string str;
typedef pair<int, int> pii;


int main()
{
    THINK_TWICE_CODE_ONCE
    //freopen("test cases\\.txt", "r", stdin) ;
    int a, b, c; cin>>a>>b>>c;
    int arr[] = {a, b, c};
    sort(arr, arr+3);
    if(arr[0]==arr[1] && arr[1]==5 && arr[2]==7)cout<<"YES";
    else cout<<"NO";
	return 0;

}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<long long>;
using pll = pair<long long, long long>;
#define rep(i,n) for(long long i(0);(i)<(n);(i)++)


void solve(long long N, std::vector<long long> A){
    ll s=0, t=0, sum=0, xsum=0;
    ll cnt = 0;
    while(1){
        while(t < N && (sum+A[t])== (xsum^A[t])){
            sum += A[t]; 
            xsum = xsum ^ A[t];
            t++;
        }
        cnt += t-s;
        if(s == N)
            break;
        if(t > s){
            sum -= A[s]; 
            xsum = xsum ^ A[s];
            s++;
        }
        else{//* t==s
            s++; t++;
        }
    }
    cout << cnt << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 1792
#if 0

#endif

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main(){
	set<string> S;
	string cmd;
	string word;
	int n;
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>cmd;
		if(cmd=="insert"){
			cin>>word;
			S.insert(word);
		}else if(cmd=="find"){
			cin>>word;
			if(S.count(word)==1)
				cout<<"yes"<<endl;
			else
				cout<<"no"<<endl;
		}
	}
}

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

int main() {
  int K, N;
  cin >> K >> N;
  int prev, next, first;
  cin >> first;
  next = first;
  int m = 0;
  rep(i, N - 1) {
    prev = next;
    cin >> next;
    m = max(m, next - prev);
  }
  m = max(m, (K + first - next));
  cout << K - m << endl;
}


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

#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 (int i=0    ;i<(n) ;i++)
#define RREP(i,n)     for (int i=(n)-1;i>=0  ;i--)
#define EACH(i,a,b)   for (int i=(a)  ;i<=(b);i++)
#define REACH(i,a,b)  for (int i=(b)  ;i>=(a);i--)
#define ALL(a)        (a).begin(),  (a).end()
#define RALL(a)       (a).rbegin(), (a).rend()

const int MOD = 1e9 + 7;
const int INF = 1 << 29;
const double EPS = 1e-10;

using ll = long long;
using P = pair<int,int>;
template<class T = int> using V = vector<T>;

template<class T> bool inline chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool inline chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T = int> T inline input() { T x; cin >> x; return (x); }
template<class T = int> void inline print(T& x) { cout << x << '\n'; }
#define debug(x) cerr << #x << ": " << x << endl;

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

  int R,G,B,N;
  cin >> R >> G >> B >> N;

  int ans = 0;
  REP(r,3001) {
    REP(g,3001) {
      int bB = N - r*R - g*G;
      if (bB == 0 || bB % B == 0 && 0 <= bB / B && bB / B <= 3000) ans++;
    }
  }

  print(ans);

  return 0;
}


Measured memory_bytes: 3604
#include<iostream>
using namespace std;
long N;
main()
{
	cin>>N;
	N--;
	int k;
	for(k=1;;k++)
	{
		long T=1;
		for(int i=0;i<k;i++)T*=26;
		if(N>=T)N-=T;
		else break;
	}
	string ans(k,' ');
	for(int i=0;i<k;i++)
	{
		long T=1;
		for(int j=i+1;j<k;j++)T*=26;
		int L=N/T;
		ans[i]=L+'a';
		N%=T;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll oo = 0x3f3f3f3f3f3f3f3fLL;
#define sz(c) ll((c).size())
#define all(c) begin(c),end(c)
#define TR(X) ({ if(1) cerr << "Trace: " << (#X) << " = " << (X) << endl; })

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll a; string s; cin >> a >> s;
	cout << (a >= 3200LL ? s : "red") << endl;
}



Measured memory_bytes: 256
n = int(input())
v = list(map(int,input().split()))
v0 = v[0:n-1:2]
v1 = v[1:n:2]
from collections import Counter
V0 = Counter(v0)
V1 = Counter(v1)
if V0.most_common()[0][0] != V1.most_common()[0][0]:
    a = V0.most_common()[0][1]
    b = V1.most_common()[0][1]
else:
    if V0.most_common()[0][1] > V1.most_common()[0][1]:
        if len(V1) > 1:
            a = V0.most_common()[0][1]
            b = V1.most_common()[1][1]
        else:
            a = V0.most_common()[0][1]
            b = 0
    elif V0.most_common()[0][1] < V1.most_common()[0][1]:
        if len(V0) > 1:
            a = V1.most_common()[0][1]
            b = V0.most_common()[1][1]
        else:
            a = 0
            b = V1.most_common()[0][1]
    else:
        if len(V0) == 1 and len(V1) == 1:
            a = 0
            b = V0.most_common()[0][1]
        elif len(V0) == 1:
            a = V0.most_common()[0][1]
            b = V1.most_common()[1][1]
        elif len(V1) == 1:
            a = V0.most_common()[1][1]
            b = V1.most_common()[0][1]
        else:
            a = V0.most_common()[0][1]
            b = max(V0.most_common()[1][1],V1.most_common()[1][1])
print(n-a-b)

Measured memory_bytes: 24668
//50
#include<iostream>
#include<cstdlib>

using namespace std;

int main(){
  for(int a,b,d;cin>>a>>b>>d,a|b|d;){
    int x,y;
    x=y=50000;
    for(int i=0;i<=50000;i++){
      for(int j=-1;j<=1;j+=2){
	int s=abs(a*i+d*j);
	if(s%b==0){
	  int k=s/b;
	  if(i+k<x+y||i+k==x+y&&a*i+b*k<a*x+b*y){
	    x=i;
	    y=k;
	  }
	}
      }
    }
    cout<<x<<' '<<y<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
import java.util.*;

class Main {
  public static void main (String[] args) {
    Scanner scanner = new Scanner(System.in);
    int[] ages = new int[7];
    int c = 0;
    while (scanner.hasNext()) {
      int n = scanner.nextInt();
      if (n == 0) {
        break;
      }
      for (int ii = 0; ii < 7; ii++) {
        ages[ii] = 0;
      }
      for (int ii = 0; ii < n; ii++) {
        int a = scanner.nextInt();
        if (a < 10) {
          c = 0;
        } else if (a < 20) {
          c = 1;
        } else if (a < 30) {
          c = 2;
        } else if (a < 40) {
          c = 3;
        } else if (a < 50) {
          c = 4;
        } else if (a < 60) {
          c = 5;
        } else {
          c = 6;
        }
        ages[c]++;
      }
      for (int ii = 0; ii < 7; ii++) {
        System.out.println(ages[ii]);
      }
    }
  }
}

Measured memory_bytes: 210100
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

int main(){
    cin>>N>>M;
    rep(i,M) cin>>A, N -= A;
    cout<<(N <= 0 ? "Yes" : "No")<<endl;
}

Measured memory_bytes: 256
using System;

public class C
{
    public const int INF = 999999999;
}

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var dp = new int[n, n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i == j) dp[i, j] = 0;
                else dp[i, j] = C.INF;
        for (int i = 0; i < n; i++)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var r = int.Parse(line[0]) - 1;
            var k = int.Parse(line[1]);
            for (int j = 0; j < k; j++)
                dp[r, int.Parse(line[j + 2]) - 1] = 1;
        }
        goWarshall(dp);
        var p = int.Parse(Console.ReadLine().Trim());
        for (int i = 0; i < p; i++)
        {
            string[] line2 = Console.ReadLine().Trim().Split(' ');
            var s = int.Parse(line2[0]);
            var d = int.Parse(line2[1]);
            var v = int.Parse(line2[2]);
            if (dp[s - 1, d - 1] == C.INF | dp[s - 1, d - 1] + 1 > v) Console.WriteLine("NA");
            else Console.WriteLine(dp[s - 1, d - 1] +1);
        }
    }
    public static void goWarshall(int[,] dp)
    {
        var n = dp.GetLength(0);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                        dp[j, k] = Math.Min(dp[j, k], dp[j, i] + dp[i, k]);
    }
}

Measured memory_bytes: 9324
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <queue>
#include <list>
#include <string>
using namespace std;

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

int main()
{
  int N,K;
  char S[10];
  cin >> N;
  for(int i=0;i<N;i++){
    cin >> S[i];
  }
  cin >> K;
  for(int i=0;i<N;i++){
    if(S[K-1] != S[i]){
      S[i] = '*';
    }
  }
  for(int i=0;i<N;i++){
  cout << S[i];
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back
ll n, a , b , c , d ;
string s ;

ll check ( ll x  , ll y ) {
    ll ans = 1 ,i ;
    for ( i = x-1 ; i <=y-1 ;i++ ) {
        if (s[i]=='#' and s[i+1]=='#' )
            ans = 0 ;
    }
    if (s[y-1]=='#') ans = 0 ;
    return ans ;

}

int main() {

    cin >> n >> a>> b >> c >> d >> s ;
    ll ans = 1 ;
    if (c==d) ans = 0;
    else if (c<d) {
       ll x = check(a,c) ;
       ll y = check(b,d) ;
       ans = x & y ;
    }
    else {
            ans = 0 ;
        for (ll i = b-1 ; i<=min(d-1,n-2) ;i++)  {
            if (s[i]=='.' and s[i-1]=='.' and s[i+1]=='.') {
                ans =1 ;
            }
        }
        ans = ans & check(a,c) ;
        ans = ans & check(b,d) ;
    }
    cout << (ans==1 ?  "Yes\n" : "No\n" ) ;

}


Measured memory_bytes: 644
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
#define cMaxLimit 260
#define UNDEFINED -2000000001

typedef struct { int key, parent, leftChild, rightChild; } Node;
stringstream ans1, ans2;

void print(Node node[], int maxNum)
{
	for (int i = 1; i <= maxNum; i++)
	{
		ans1 << "node " << i << ": ";
		ans1 << "key = " << node[i].key << ", ";
		if (node[i].parent != UNDEFINED) ans1 << "parent key = " << node[i].parent << ", ";
		if (node[i].leftChild != UNDEFINED) ans1 << "left key = " << node[i].leftChild << ", ";
		if (node[i].rightChild != UNDEFINED) ans1 << "right key = " << node[i].rightChild << ", ";
		ans1 << endl;
	}
}

int main()
{
	int nodeMaxNum; cin >> nodeMaxNum;
	Node node[cMaxLimit + 1]; // ????????????????????????1-???????????????????????????
	for (int i = 1; i <= nodeMaxNum; i++)
	{
		int key; cin >> key;
		node[i].key = key;
		node[i].leftChild = UNDEFINED;
		node[i].rightChild = UNDEFINED;
		node[i].parent = UNDEFINED;
	}
	for (int i = 1; i <= nodeMaxNum; i++)
	{
	   ans2 << "node " << i << ": ";
	   ans2 << "key = " << node[i].key << ", ";
	   if (i / 2 >= 1) ans2 << "parent key = " << node[i / 2].key << ", ";
	   if (i * 2 <= nodeMaxNum) ans2 << "left key = " << node[i * 2].key << ", ";
	   if (i * 2 + 1 <= nodeMaxNum) ans2 << "right key = " << node[i * 2 + 1].key << ", ";
	   ans2 << endl;
	}
	for (int i = 1; i <= nodeMaxNum; i++)
	{
		if (i / 2 >= 1) node[i].parent = node[i / 2].key;
		if (i * 2 <= nodeMaxNum) node[i].leftChild = node[i * 2].key;
		if (i * 2 + 1 <= nodeMaxNum) node[i].rightChild = node[i * 2 + 1].key;
	}
	print(node, nodeMaxNum);
	cout << ans1.str();
	return 0;
}

Measured memory_bytes: 3252
from collections import defaultdict
def debug(*args): print(*args, file=sys.stderr)
N=int(input())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
for a in A:
    dd[a]+=1
#print(dd)
B=sorted(A,reverse=True)
ans=0
for x in B:
    #print(x)
    if dd.get(x,-1)==0:
        continue
    s=len(bin(x))-3
    if x==1<<s:
        t=dd.get(x,-1)
        if t!=-1:
            ans+=t//2
            dd[x]-=(t//2)*2
            #print(ans)
            #print(dd)
    else:
        s+=1
        #print((1<<s)-x)
        t=dd.get((1<<s)-x,-1)
        if t>=1:
            ans+=1
            dd[x]-=1
            dd[(1<<s)-x]-=1
            #print(ans)
            #print(dd)
print(ans)



Measured memory_bytes: 112468
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=1e9;
int cnt;
int ans[10][10];
int fld[10][10];
int X,Y;
int B[15],K[15],Bx[15],By[15],N;
vector<int> V[15];
bool pos(int x,int y){
      return 0<=x&&x<X&&0<=y&&y<Y;
}
bool ok(int x,int y,int w,int h,int n){
      REP(i,w)REP(j,h)if(!pos(x+i,y+j)||(fld[x+i][y+j]!=0&&fld[x+i][y+j]!=n)){
            //cout<<i<<" "<<j<<"no"<<endl;
            return false;
      }
      return true;
}
void rec(int n){
      if(n==N){
            REP(i,X)REP(j,Y)ans[i][j]=fld[i][j];
            cnt++;
            return;
      }
      int sx,sy;
      //cout<<n<<" "<<B[n]<<endl;
      //REP(i,Y)REP(j,X)printf("%d%c",fld[j][i],j==X-1?'\n':' ');
      REP(i,X)REP(j,Y)if(fld[i][j]==B[n]){sx=i;sy=j;};
      //cout<<sx<<" "<<sy<<endl;
      REP(i,V[n].size()){
            //cout<<V[n][i]<<endl;
            for(int x=sx-V[n][i]+1;x<=sx;x++){
                  for(int y=sy-K[n]/V[n][i]+1;y<=sy;y++){
                        if(ok(x,y,V[n][i],K[n]/V[n][i],B[n])){
                              REP(j,V[n][i])REP(k,K[n]/V[n][i])fld[x+j][y+k]=B[n];
                              rec(n+1);
                              REP(j,V[n][i])REP(k,K[n]/V[n][i]){
                                    if(x+j==Bx[n]&&y+k==By[n])continue;
                                    else fld[x+j][y+k]=0;
                              }
                        }
                  }
            }
      }
      return;
}
int main(){
      while(cin>>X>>Y>>N&&(X||Y||N)){
            REP(i,15)V[i].clear();
            cnt=0;
            REP(i,N){
                  cin>>B[i]>>K[i];
                  for(int j=1;j*j<=K[i];j++){
                        if(K[i]%j==0){
                              V[i].PB(j);
                              if(K[i]/j!=j)V[i].PB(K[i]/j);
                        }
                  }
            }
            REP(i,Y)REP(j,X){
                  cin>>fld[j][i];
                  if(fld[j][i]!=0){
                        REP(k,N)if(B[k]==fld[j][i]){
                              Bx[k]=j;By[k]=i;
                        }
                  }
            }
            rec(0);
            if(cnt==1){
                  REP(i,Y)REP(j,X)printf("%d%c",ans[j][i],j==X-1?'\n':' ');
            }else{
                  cout<<"NA"<<endl;
            }
      }
}

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

using namespace std;
typedef long long llong;

#define MAX 200001
const llong mod = 1000000000 + 7;

int main()
{
  char S[MAX];
  int U[2019];

  scanf("%s", S);

  U[0] = 1;

  int current = 0;
  int ans = 0;
  int len = strlen(S);
  int T[MAX];
  T[0] = 1;
  for (int i = 1; i < len; i++)
  {
    T[i] = (T[i - 1] * 10) % 2019;
  }

  for (int i = 0; i < len; i++)
  {
    current = (current + (S[len - 1 - i] - '0') * T[i]) % 2019;
    ans += U[current];
    U[current]++;
  }

  printf("%d", ans);

  return 0;
}

Measured memory_bytes: 2692
A, B, C, D = map(int, input().split())

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(x, y):
    return (x * y) // gcd(x, y)

A_C = A // C
A_D = A // D
A_CD = A // lcm(C, D)

B_C = B // C
B_D = B // D
B_CD = B // lcm(C, D)

A_e = A - (A_C + A_D - A_CD)
B_e = B - (B_C + B_D - B_CD)

if A % C == 0 or A % D == 0:
    ans = B_e - A_e
else:
    ans = B_e - A_e + 1
print(ans)

Measured memory_bytes: 3064
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
d = [list(map(int,input().split())) for i in range(m)]
#1から直で行ける
from_one_to = []
#nに直で行く
to_n_from = []
for i,j in d:
    if i==1:
        from_one_to.append(j)
    if j==n:
        to_n_from.append(i)
if len(set(from_one_to) & set(to_n_from)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


Measured memory_bytes: 61024
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
n=I()
a=S()
b=S()
c=S()
ans=0
for i in range(n):
    if a[i]==b[i] and b[i]==c[i]:
        ans+=0
    elif a[i]==b[i] or b[i]==c[i] or a[i]==c[i]:
        ans+=1
    else:
        ans+=2
print(ans)

Measured memory_bytes: 3064
#include <stdio.h>
int main(void){
	int a, b;

	scanf("%d %d", &a, &b);

	int max = a + b;

	if( a - b > max ){
		max = a - b;
    }
	if( a * b > max ){
		max = a * b;
	}
    printf("%d", max);
	return 0;
}

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

int main() {
    int n, u, k, tmp;
    cin >> n;
    int M[n][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;
        for (int j=0; j<k; j++) {
            cin >> tmp;
            M[u-1][tmp-1] = 1;
        }
    }

    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cout << M[i][j];
            if (j<n-1) {
                cout << ' ';
            } else {
                cout << endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3160
#define _USE_MATH_DEFINES
#include<iostream>
#include<fstream>
#include<cstdlib> 
#include<string>
#include<math.h>
#include<bitset>
#include<algorithm>
#include<vector>
#include<set>
#include<stack>
#include<queue>
using namespace std;


int main(){

	unsigned long long n,p[20000],a[20000],b[20000],ab[20000];

	cin>>n;
	for(int i=0;i<n;i++){
		cin >> p[i];
		a[i]=50000*i;
		b[i]=1000000000-50000*i;
	}

	for(int i=0;i<n;i++){
		a[p[i]-1]+=(i+1);
	}

	for(int i=0;i<n;i++){
		cout << a[i] << ' ';
	}
	cout << endl;

	for(int i=0;i<n;i++){
		cout << b[i] << ' ';
	}
	cout << endl;

	//while(1);

}


Measured memory_bytes: 1152
#入力
lst = input().split()

a = lst[0]
b = lst[1]

#出力
if a == 'H': #Aは正直
   if b == 'H': #Tは正直:真
      print('H')
   elif b == 'D': #Tは嘘:真
      print('D')
elif a == 'D': #Aは嘘
   if b == 'H': #Tは正直:偽
      print('D')
   elif b == 'D': #Tは嘘:偽
      print('H')

Measured memory_bytes: 8864
/*
ID: amagica1
TASK: ariprog
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
#define INF INT_MAX
#define NINF -INF
#define mp make_pair
#define endl '\n'
#define boost() cin.tie(0); cin.sync_with_stdio(0)
#define For(i, a, b) for(int i=a; i<b; i++)
#define FOR(i, a, b) for(int i=a; i<=b; i++)
#define Rev(i, a, b) for(int i=a; i>b; i--)
#define REV(i, a, b) for(int i=a; i>=b; i--)
typedef long long ll;
typedef long double ld;
typedef int64_t l;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
const ll MOD = 1e9 + 7;
const int MAXN = 200005;
ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}
mt19937 rng;
int randint(int a, int b){ return uniform_int_distribution<int>(a, b)(rng);}
int main() {
    //-----------FILE------------//
    //freopen("airprog.in", "r", stdin);
    //freopen("airprog.out", "w", stdout);
    //----------------------------//
    ll a, b, k;
    cin >> a >> b >> k;
    a -= k;
    if(a < 0) b -= abs(a);
    a = max(0LL, a);
    b = max(0LL, b);
    cout << a << " " << b << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	vector<int> a(n-1);
	for (int i = 0; i < n-1; ++i)
	{
		cin >> a.at(i);
	}
	sort(a.begin(),a.end());
	vector<int> b(n);
	for (int i = 0; i < n-1; ++i)
	{
		b.at(a.at(i)-1)++;
	}
	for (int i = 0; i < n; ++i)
	{
		cout << b.at(i) << endl;
	}

}


Measured memory_bytes: 4792
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using ii=pair<ll,ll>;
using vi=vector<ll>;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (ll)1e18
#define all(x) (x).begin(),(x).end()
#define print(a); for(auto x:a)cout<<x<<" "; cout<<"\n";
#define mset(a); memset(a,0,sizeof(a));

bool comp(ii a,ii b){
    return a.se>b.se;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,m;cin>>n>>m;
    ll a[n];
    ll sum=0;
    for(ll i=0;i<n;i++){
        cin>>a[i];sum+=a[i];
    }
    vector<ii>v(m);
    for(ll i=0;i<m;i++){
        cin>>v[i].fi>>v[i].se;
    }
    sort(a,a+n);
    sort(all(v),comp);
    ll cnt=0;
    bool state=0;
    for(ll i=0;i<m;i++){
        for(ll j=cnt;j<min(cnt+v[i].fi,n);j++){
            if(a[j]<v[i].se){
                sum+=(v[i].se-a[j]);
            }else{
                state=1;break;
            }
        }
        cnt=min(cnt+v[i].fi,n);
        if(state||cnt==n)break;
    }
    cout<<sum<<"\n";
}


Measured memory_bytes: 5568
#include<stdio.h>

int main(void){

int N, i, k;
int H[20];
int count = 1;
int defference[20];
int c = 0;

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

for(k = 1; k < N; k++){
    c = 0;
    for(i = 0; i < k; i++){
        defference[i] = H[k] - H[i];
        if(defference[i] < 0){
            c = 1;
        }
    }
    if(c == 0){
      count += 1;

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

return 0;
}


Measured memory_bytes: 128
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String args[]) {
		FastScanner scanner = new FastScanner();
		int n=scanner.nextInt();
		sieve(55555);
		int cnt=0;
		StringBuilder sb=new StringBuilder();
		for(int i=2;i<=55555;i++){
			if(is_prime[i]&&i%5==1){
				sb.append(i+" ");
				cnt++;
			}
			if(cnt==n){
				System.out.println(sb);
				return;
			}
		}
	}
	
	static boolean[] is_prime;
	static private void sieve(int n) {
		is_prime = new boolean[n + 1];
		for (int i = 2; i <= n; i++) {
			is_prime[i] = true;
		}
		for (int i = 2; i <= n; i++) {
			if (is_prime[i]) {
				for (int j = i + i; j <= n; j += i) {
					is_prime[j] = false;
				}
			}
		}
	}
	
}
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}


Measured memory_bytes: 21332
#include <bits/stdc++.h>
using namespace std;
using ll= long long;
using vi= vector<int>;
using vvi= vector<vi>;
using vd= vector<double>;
using vvd= vector<vd>;
using vc= vector<char>;
using vb= vector<bool>;
using vl= vector<ll>;
#define rep(i,x,n) for(int i=x; i<n; i++)
#define all(x) x.begin(), x.end()

int main(){
  int n;
  bool bingo=false;
  vector<vector<int>> a(3,vector<int>(3));
  rep(i,0,3){
    rep(j,0,3){
      cin >> a[i][j];
    }
  }
  cin >> n;
  vi b(n);
  rep(i,0,n){
    cin >> b[i];
  }
  vector<vector<bool>> c(3,vector<bool>(3,false));

  rep(i,0,n){
    rep(j,0,3){
      rep(k,0,3){
        if(b[i]==a[j][k]){
          c[j][k]=true;
        }
      }
    }
  }
  for(int i=0; i<3; i++){
    if(c[i][0] && c[i][1] && c[i][2]){
      bingo=true;
    }
    if(c[0][i] && c[1][i] && c[2][i]){
      bingo=true;
    }
  }
  if(c[0][0] && c[1][1] && c[2][2])
    bingo= true;
  if(c[0][2] && c[1][1] && c[2][0])
    bingo= true;

  if(bingo){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


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

int H, W;
char a[110][110];
bool f1[110], f2[110];
vector<vector<char>> ans;

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> H >> W;
    rep(i, H) rep(j, W) cin >> a[i][j];
    rep(i, H) f1[i] = true;
    rep(i, H) rep(j, W) f1[i] &= (a[i][j]=='.');
    rep(i, W) f2[i] = true;
    rep(i, W) rep(j, H) f2[i] &= (a[j][i]=='.');
    
    rep(i, H) {
        if (f1[i]) continue;
        vector<char> v;
        rep(j, W) {
            if (f2[j]) continue;
            v.pb(a[i][j]);
        }
        ans.pb(v);
    }
    rep(i, ans.size()) {
        rep(j, ans[0].size()) cout << ans[i][j];
        cout << endl;
    }
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
Sone=0
Stwo=sum(A)
D=sum(A)
for i in range(N):
  Sone+=A[i]
  Stwo-=A[i]
  D=min(D,abs(Sone-Stwo))
print(D)

Measured memory_bytes: 3060
#include<cstdio>
#define min(a,b) (a<b?a:b)
int n,m,a[6666666],ans=0x3f3f3f3f;
int main(){
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i]+m;
	for(int i=1;i<=n;i++)ans=min(ans,a[i+n-1]-a[i]);
	printf("%d",ans);
}

Measured memory_bytes: 1664
#include<iostream>
#include<cmath>
#include<iomanip>
#define MAX 100001
#define EPS (1e-2)
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29) 
using namespace std;
double dp[MAX][10];
double pr[MAX];
double f[10];
int main()
{
  int n;
  
  f[0] = 1;
  REP(i,1,10)f[i] = f[i-1]/2;
  rep(i,MAX)rep(j,10)dp[i][j] = 0;
  dp[0][0] =  1;
  double sum = 0;

  REP(i,0,MAX-1)
    {
      rep(j,min(i+1,10))
	{
	  if(dp[i][j] == 0)continue;
	  if(j == 0)
	    {//前回失敗した
	      dp[i+1][j+1] += dp[i][j];
	      sum += dp[i][j];
	      continue; 
	    }
	  //前回失敗したとかそーでもない
	  dp[i+1][0]   += dp[i][j] * (1 - f[j]);
	  dp[i+1][j+1] += dp[i][j] * f[j];
	  sum += dp[i][j] * f[j];
	}      
      pr[i] = sum;
    }

  while(cin >> n,n)cout << setiosflags(ios::fixed) << setprecision(100008) << pr[n-1] << endl;  
    
  
  return 0;
}

Measured memory_bytes: 10544
import java.io.PrintWriter

fun main(args: Array<String>) {
  val pw = PrintWriter(System.out)
  val (H, W, A, B) = readLine()!!.split(" ").map{ it.toInt() };
  for (i in 0 until H) {
    for (j in 0 until W)
      pw.print(if ((i < B).xor(j < A)) 1 else 0);
    pw.println();
  }
  pw.close();
}

Measured memory_bytes: 47440
sx, sy, tx, ty = map(int, input().split())

A = "L"
for i in range(ty-sy+1):
    A += "U"
for i in range(tx-sx+1):
    A += "R"
for i in range(ty-sy+1):
    A += "D"
for i in range(tx-sx):
    A += "L"
for i in range(ty-sy):
    A += "U"
for i in range(tx-sx+1):
    A += "R"
for i in range(ty-sy+1):
    A += "D"
for i in range(tx-sx+1):
    A += "L"
A += "U"

print(A)


Measured memory_bytes: 9108
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const ll mod = 1000000007;
const ll INF = mod * mod;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
typedef vector<int> vec;
typedef vector<string> svec;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
//#define int long long

void solve() {
    ll a, b, x; cin >> a >> b >> x;
    cout << b / x - a / x + (a % x == 0 ? 1LL : 0) << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
square = []
s1= a[0]
c = 0
result = 0
for i in range(1, n):
    s2 = a[i]
    if s1 == s2:
        c += 1
        if c % 2 == 1:
            square.append(s1)
            if len(square) == 2:
                result = square[0] * square[1]
                break
    else:
        s1 = a[i]
        c = 0
print(result)

Measured memory_bytes: 14244
N, K = map(int,input().split())
A = list(map(int,input().split()))

import collections

cA = collections.Counter(A)

sorted_ls = sorted(list(cA.values()))
sum_ls = sum(sorted_ls)


if len(sorted_ls)>K:
  print(sum(sorted_ls[:len(sorted_ls)-K]))
else:
  print(0)

Measured memory_bytes: 34956
N, K = map(int, input().split())
A = tuple(map(int, input().split()))
import itertools
import numpy as np
ans_cnt = np.Inf
for now in itertools.combinations(range(1,N), K-1):
    height = A[0]
    cnt = 0
    for i in range(1,len(A)):
        if i in now:
            if A[i] > height:
                height = A[i]
            else:
                height += 1
                cnt += height - A[i]
        else:
            height = max(height, A[i])
    ans_cnt = min(cnt, ans_cnt)
print(ans_cnt)

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

int main() {
  int n;
  cin >> n;
  vector<ll> v({3});
  for (int i = 0; i < n; i++) {
    v.push_back(2 * v[i] + 1);
  }
  cout << v[n] - 1 << endl;

  return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let mut str: String = read();
    let mut flag = true;
    for i in 0..str.len()/2{
        let ch2 = &str[i*2..i*2+2];
        if ch2 != "hi" {
            flag = false;
            break;
        }     }
    if str.len() %2 != 0 {
        flag = false;
    } 
    if flag {
        println!("Yes");    
    } else {
        println!("No");
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define push_back pb
typedef long long int ll;
typedef long int li;

using namespace std;

int main()
{
	int a[3];
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	cout<<abs(a[2]-a[1])+abs(a[1]-a[0])<<endl;
	return 0;
}

Measured memory_bytes: 256
// atcoder/abc151/A/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  char c;
  while (cin >> c) {
    ++c;
    cout << c << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

const int mod = 1e9 + 7;
int n, dp[100010][2];
vector<vi> e;
void rec(int c, int p){
	dp[c][1] = 1;
	dp[c][0] = 1;
	for(int i : e[c]) if(i != p){
		rec(i, c);
		dp[c][1] = dp[c][1] * (ll)dp[i][0] % mod;
		dp[c][0] = dp[c][0] * (ll)(dp[i][0] + dp[i][1]) % mod;
	}
}
int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	cin >> n; e.resize(n);
	rep(i, n - 1){
		int a, b; cin >> a >> b; a--; b--;
		e[a].pb(b);
		e[b].pb(a);
	}
	rec(0, 0);
	cout << (dp[0][0] + dp[0][1]) % mod << endl;
	return 0;
}

Measured memory_bytes: 13440
#include <iostream>
#include <utility>
#include <algorithm>

#define l first
#define r second

const int MAXN = (int)1e5;

std::pair<int, int> a[MAXN];

int solve(int n) {
  std::sort(a, a + n, [](const auto& u, const auto& v) {
    return u.r < v.r; 
  });
  int ans = 1;
  int cur_r = a[0].r;
  for (int i = 1; i < n; ++i) {
    if (a[i].l < cur_r) continue;
    ++ans;
    cur_r = a[i].r;
  }
  return ans;
}

int main() {
  int n;
  std::cin >> n;
  for (int i = 0, u, v; i < n; ++i) {
    std::cin >> u >> v;
    a[i].l = u - v;
    a[i].r = u + v;
  }
  std::cout << solve(n) << std::endl;
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const long double EPS = 1e-9;
const ll mod = 1e9 + 7;
const ll INF = 1e9;

#define rep(i, n) for(ll i = 0; i < n ; i++ )
#define For(i, a, b) for(ll i = (a); i < (b) ; i++ )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

const ll MAX_N = 100000;

int main(void){
    ll a,b,c,d;
    string s,t;

    cin >> a >> b;//>> c >> d;
    //cin >> s >> t;
    if (a%3==0||b%3==0||(a+b)%3==0) cout << "Possible";
    else cout << "Impossible";

    return 0;
}

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

using namespace std;

typedef pair<string,int> P;

int main(){
	queue<P> que;
	P task;
	int n,q,time=0;
	cin >> n >> q;
	for(int i=0;i < n;i++){
		cin >> task.first >> task.second;
		que.push(task);
	}
	
	while(!que.empty()){
		task = que.front();que.pop();
		if(task.second>q){
			time += q;
			task.second -= q;
			que.push(task);
		}else{
			time += task.second;
			cout << task.first << " " << time << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 6332
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int i=(m);(i)<(n);(i)++)
typedef long long ll;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
  	int n;
    string str;
  	cin >> n;
    cin >> str;
    vector<int> sumE(n+1,0);
    vector<int> sumW(n+1,0);

    rep(i,n){
        if(str[i]=='E'){
            sumE[i+1]=sumE[i]+1;
            sumW[i+1]=sumW[i];
        }
        if(str[i]=='W'){
            sumW[i+1]=sumW[i]+1;
            sumE[i+1]=sumE[i];
        }        
    }

    int ans = 1e9;

    for(int i=1; i<=n;i++){
        if(i==n){
            ans = min(ans,sumW[n-1]);
        }else{
            ans = min(ans,sumW[i-1]+sumE[n]-sumE[i]);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) (x).begin(),(x).end()
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> P;
typedef map<int,int> mp;
 
const int MOD = 1e9 + 7;
 
 
int main() {
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
    int n;
    string s;
    cin >> n >> s;
 
    int ans = 0;
    rep(i, n-2){
        if(s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C' ){
            ans++;
        }
    }
 
    cout << ans << endl;
 
 
    return 0;
}

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

int main(int argc, char const* argv[])
{
  while (true) {
    int n;
    std::cin >> n;
    if (n == 0) {
      break;
    }
    int pt_a = 0, pt_b = 0;
    for (int i = 0; i < n; ++i) {
      int a, b;
      std::cin >> a >> b;
      if (a == b) {
        pt_a += a;
        pt_b += b;
      } else if (a < b) {
        pt_b += a + b;
      } else {
        pt_a += a + b;
      }
    }
    std::cout << pt_a << " " << pt_b << std::endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>
int main(void){
  int a = 0;
  int b = 0;
  int c = 0;
  int tmp = 0;
  
  scanf("%d%d%d",&a,&b,&c);
  
  tmp = a + b + c;
  
  if (tmp >= 22){
    printf("bust");
  } else {
    printf("win");
  }
  
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
#define ll long long int
int main(){
    ll a;
    cin>>a;
    ll arr[3][a], dp[3][a];
    for (ll i=0; i<a; i++){
        for (ll j=0; j<3; j++){
            cin>>arr[j][i];
            dp[j][i]=0;
        }
    }
    dp[0][0]=arr[0][0], dp[1][0]=arr[1][0], dp[2][0]=arr[2][0];
    for (ll i=0; i<a-1; i++){
        for (ll j=0; j<3; j++){
            for (ll k=0; k<3; k++){
                if (k==j) continue;
                dp[k][i+1]=max(dp[k][i+1], dp[j][i]+arr[k][i+1]);
            }
        }
    }
    cout<<max(dp[0][a-1], max(dp[1][a-1], dp[2][a-1]))<<endl;
}

Measured memory_bytes: 4992
#define _USE_MATH_DEFINES
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<math.h>
 
using namespace std;
 
 
// this class works only if mod is prime number and mod is so big number .
class mll
{
  public:
    mll(int _data=0,int mod = 1000000007):data(_data),MOD(mod){
    };
    ~mll(){};
    long long data;
    long long MOD ;
    //  overload
    mll  operator + (mll obj){
      return (this->data+obj.data)%this->MOD;
    }
    mll  operator - (mll obj){
      return (this->data-obj.data)%this->MOD;
    }
    mll  operator * (mll obj){
      return (this->data*obj.data)%this->MOD;
    }
    mll  operator / (mll obj){
      long long div_buf[65]={1,obj.data%this->MOD};
      for(int i=2;i<=64;i++){
        div_buf[i]=(div_buf[i-1]*div_buf[i-1])%this->MOD;
      }
      mll bmod2(1);
      //calc b^(MOD-2)
      for(int i = 0;i<64;i++){
        if(((this->MOD-2)>>i)%2){
          bmod2 = bmod2*div_buf[i+1];
        }
      }
      return bmod2*(*this);
 
    }
    //  overload for long long
    mll  operator + (long long  obj){
      return (this->data+obj)%this->MOD;
    }
    mll  operator - (long long  obj){
      return (this->data-obj)%this->MOD;
    }
    mll  operator * (long long  obj){
      return (this->data*obj)%this->MOD;
    }
    mll  operator / (long long  obj){
      long long div_buf[65]={1,obj%this->MOD};
      for(int i=2;i<=64;i++){
        div_buf[i]=(div_buf[i-1]*div_buf[i-1])%this->MOD;
      }
      mll bmod2(1);
      //calc b^(MOD-2)
      for(int i = 0;i<64;i++){
        if(((this->MOD-2)>>i)%2){
          bmod2 = bmod2*div_buf[i+1];
        }
      }
      return bmod2*(*this);
    }
 
    // for iostream
 
    friend istream& operator >> (istream &in,mll &dt);
    friend ostream& operator << (ostream &out,mll &dt);
  private:
};
 
istream& operator >> (istream &in,mll &dt){
  in >> dt.data;
  return in;
}
ostream& operator << (ostream &out,mll &dt){
  out << dt.data;
  return out;
}
 
mll combMOD(mll n,mll r)
{
  mll ans(1);
  for(long long i=0;i<r.data;i++){
    mll buf(1+i);
    ans = ans*(n-i);
    ans = ans/buf;
  }
  return ans;
}
int main(){
  mll h,w,a,b;
  cin >> h >> w >> a >>b;
  mll sh = h-a-1;
  mll sw = b-1;
  mll scmb,lcmb;
  scmb = combMOD(sh+sw,sh);
  lcmb = combMOD(a-1+w-b,a-1);
  mll ans(0);
  for(int i=1;i<=(w-b).data;i++){
    scmb = scmb*(sh+sw+i);
    scmb = scmb/(sw+i);
    lcmb = lcmb*(w-b-i+1);
    lcmb = lcmb/(w-b+a-1-i+1);
    ans = ans+ scmb*lcmb;
  }
  cout <<ans << endl;
}

Measured memory_bytes: 256