akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;
int main()
{   ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s,t;
    cin>>s>>t;
    
    int cnt=0;
    for(int i=0;i<s.length();i++) if(s[i]!=t[i]) cnt++;
    cout<<cnt;
}


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

template<class t> void vin(vector<t>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main() {
    string s, t;
    cin >> s >> t;
    vector<int> f(26, -1);
    vector<int> g(26, -1);
    rep(i, s.size()) {
        int a = s[i] - 'a';
        int b = t[i] - 'a';
        if (f[a] != -1 or g[b] != -1) {
            if (f[a] != b or g[b] != a) {
                cout << "No" << endl;
                return 0;
            }
        }
        f[a] = b;
        g[b] = a;
    }
    cout << "Yes" << endl;
}


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

#define fi first
#define se second
#define pb push_back
#define int long long
#define all(x) (x).begin(), (x).end()

using LL = long long;
using LD = long double;
using pii = pair<int, int>;
using vii = vector<pii>;

const int INF = 1e18;
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;

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

	int n;
	cin >> n;

	set<int> S;
	vector<int> a(n + 1), pos(n + 1);
	
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pos[a[i]] = i;
	}

	int ans = 0;
	for (int i = n; i >= 1; i--) {
		S.insert(pos[i]);
		int l0 = 0, l1 = 0, r0 = 0, r1 = 0;

		auto it = S.find(pos[i]);
		if (it == S.begin()) {
			l0 = pos[i];
			l1 = 0;	
		} else {
			auto itl1 = prev(it);
			l0 = pos[i] - *itl1;
			if (itl1 == S.begin()) {
				l1 = *itl1;
			} else {
				auto itl2 = prev(itl1);
				l1 =  *itl1 - *itl2;
			}
		}

		if (it == prev(S.end())) {
			r0 = n - pos[i] + 1;
			r1 = 0;	
		} else {
			auto itr1 = next(it);
			r0 = *itr1 - pos[i];
			if (itr1 == prev(S.end())) {
				r1 = n - *itr1 + 1;
			} else {
				auto itr2 = next(itr1);
				r1 = *itr2 - *itr1;
			}
		}

		ans += i * (l0 * r1 + l1 * r0);
	}

	cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
#define P pair<int,int>
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
using namespace std;
const int INF = 1001001001;
const int MOD = 1e9+7;
template<class T> inline bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }

struct mint{ // auto MOD int
  ll x;
  mint(ll x=0) : x((x%MOD+MOD)%MOD){}  //コンストラクタ
  mint operator-() const { return mint(-x); } //符号変換
  mint operator+(const mint &a) const { return mint(*this) += a; } //算術演算子
  mint operator-(const mint &a) const { return mint(*this) -= a; }
  mint operator*(const mint &a) const { return mint(*this) *= a; }
  mint operator/(const mint &a) const { return mint(*this) /= a; }
  mint pow(ll n) const {  //繰り返し累乗
    if(!n) return 1;
    mint a = pow(n>>1);
    a *= a;
    if(n&1) a *= *this;
    return a;
  }
  mint inv() const { return pow(MOD-2); } // for prime mod
  mint& operator+=(const mint a){ if((x+=a.x) >= MOD) x-=MOD;  return *this; } //代入演算子
  mint& operator-=(const mint a){ if((x+=MOD-a.x) >= MOD) x-=MOD;  return *this; }
  mint& operator*=(const mint a){ (x *= a.x) %= MOD;  return *this; }
  mint& operator/=(const mint a){ return (*this) *= a.inv(); }
  friend ostream& operator<<(ostream &stout, const mint &tmp){ stout << tmp.x; return stout; }
};

const int MAX = 1e6+1;
ll fac[MAX],finv[MAX],inv[MAX];
void combinit(){
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for(int i = 2; i < MAX; ++i){
    fac[i] = fac[i-1]*i % MOD;
    inv[i] = MOD-inv[MOD%i] * (MOD/i) % MOD;
    finv[i] = finv[i-1]*inv[i] % MOD;
  }
}
ll com(int n, int k){
  if(n < k) return 0;
  if(n < 0 or k < 0) return 0;
  return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  int n,m; cin >> n >> m;
  if(2 <= abs(n-m)) cout << 0;
  else{
    combinit();
    mint ans = 0;
    if(abs(n-m) == 1) ans = 1;
    else ans = com(max(n,m),min(n,m))*2;
    rep(i,n) ans *= i+1;
    rep(i,m) ans *= i+1;
    cout << ans;
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 27020
package main

import (
  "fmt"
)

func main() {
  var n string; fmt.Scan(&n)
  ans := "No"
  if n[1] == n[2] {
    if n[0] == n[1] || n[2] == n[3] {
      ans = "Yes"
    }
  }
  fmt.Println(ans)
}

Measured memory_bytes: 512
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
using namespace std;

void func(int N,int M){

	double table[N+1][N+1],dp[M+1][N+1];

	for(int i = 0; i <= M; i++){
		for(int k = 0; k <= N; k++)dp[i][k] = 0.0;
	}

	for(int i = 1; i <= N; i++){
		for(int k = 1; k <= N; k++){
			scanf("%lf",&table[i][k]);
		}
	}

	for(int i = 1; i <= N; i++)dp[1][i] = 1.0;

	for(int i = 2; i <= M; i++){
		for(int k = 1; k <= N; k++){
			for(int p = 1; p <= N; p++){
				dp[i][k] = max(dp[i][k],dp[i-1][p]*table[p][k]);
			}
		}
	}

	double ans = -1.0;

	for(int i = 1; i <= N; i++){
		ans = max(ans,dp[M][i]);
	}

	printf("%.2lf\n",ans);

}

int main(){

	int N,M;
	while(true){
		scanf("%d %d",&N,&M);
		if(N == 0 && M == 0)break;

		func(N,M);
	}

    return 0;
}

Measured memory_bytes: 2688
/* おまじない　*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
typedef long long ll;
typedef long double ld;
using namespace std;
const ll MOD=pow(10,9)+7;
const ll INF=(1LL<<62);
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    cout<<fixed;
}
int main(){
    init();

    ld A,B,P,Q,R;cin>>A>>B>>P>>Q>>R;
    if(Q-P>0 && P*A/(Q-P) < B)cout<<A+P*A/(Q-P)<<endl;
    else{
        cout<<B+(P*B-(B-A)*Q)/(R+Q)<<endl;
    }
}


Measured memory_bytes: 3288
#include<bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

int main(){
  int n;
  string s="";
  cin >> n ;
  if (n%10==3){
    s="bon";
  }
  else if (n%10==2|n%10==4|n%10==5|n%10==7|n%10==9){
    s="hon";
  }
  else s="pon";
  
  cout << s << endl;
}

Measured memory_bytes: 3600
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef  unsigned long long int ull;
typedef pair<ll,ll> P;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
ll dp[2000][2000];
int main(){
int h,w;
cin>>h>>w;
ll cnt=0;
V<V<int>> a(h,V<int>(w));
V<V<bool>> used(h,V<bool>(w,true));
ll ans=0;
for(int i=0;i<h;i++)for(int j=0;j<w;j++){cin>>a[i][j];ans|=!(a[i][j]);}
for(int i=0;i<h;i++)dp[i][0]=(a[i][0]==0);
for(int i=0;i<w;i++)dp[0][i]=(a[0][i]==0);
for(int i=1;i<h;i++){
	for(int j=1;j<w;j++){
		if(!a[i][j]){
			dp[i][j]=min({dp[i-1][j-1],dp[i-1][j],dp[i][j-1]})+1;
			chmax(ans,dp[i][j]);
		}
	}
}
cout<<ans*ans<<"\n";
}


Measured memory_bytes: 24716
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int cost[n+1][3];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<3;j++)
        {
            cin>>cost[i][j];
        }
    }
    int dp[n+1][3];
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<3;j++)
        dp[i][j]=0;
    }
    dp[1][0]=cost[1][0];
    dp[1][1]=cost[1][1];
    dp[1][2]=cost[1][2];
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<3;j++)
        {
            int x=max(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3]);
            dp[i][j]=cost[i][j]+x;
        }
    }
    cout<<max(dp[n][0],max(dp[n][2],dp[n][1]))<<"\n";
    return 0;
}

Measured memory_bytes: 2560
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
using namespace std;

int main() {
  int X , ans=0;
  cin >> X;
  ans = X % 10;
  if(ans == 3){
    cout << "bon" << endl;
  }
  else if(ans == 1){
    cout << "pon" << endl;
  }
  else if(ans == 2){
    cout << "hon" << endl;
  }
  else if(ans == 4){
    cout << "hon" << endl;
  }
  else if(ans == 5){
    cout << "hon" << endl;
  }
  else if(ans == 6){
    cout << "pon" << endl;
  }
  else if(ans == 7){
    cout << "hon" << endl;
  }
   else if(ans == 8){
    cout << "pon" << endl;
  }
   else if(ans == 9){
    cout << "hon" << endl;
  }
   else if(ans == 0){
    cout << "pon" << endl;
  }
  
  
  
   

        
  
}


Measured memory_bytes: 3652
import heapq
n, m, s, t = map(int, input().split())
money = 10**15 
graph = [[] for _ in range(n)]

for _ in range(m):
  u, v, a, b = map(int, input().split())
  u -= 1
  v -= 1 
  graph[u] += [[v, a, b]]
  graph[v] += [[u, a, b]]

def dijkstra(s, y):
  dist = [float('inf')]*n 
  dist[s] = 0
  q = [[0, s]]
  heapq.heapify(q)
  while q:
    cost, u = heapq.heappop(q)
    for v, yen, snuuk in graph[u]:
      if y:
        if dist[u] + yen < dist[v]:
          dist[v] = dist[u] + yen 
          heapq.heappush(q, [dist[v], v])
      else:
        if dist[u] + snuuk < dist[v]:
          dist[v] = dist[u] + snuuk 
          heapq.heappush(q, [dist[v], v])
  return dist

y_result = dijkstra(s-1, True)
s_result = dijkstra(t-1, False)

result = [y_result[i]+s_result[i] for i in range(n)]

for i in range(n-1, 0, -1):
  result[i-1] = min(result[i], result[i-1])

for i in range(n):
  print(money-result[i])


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

using namespace std;

using ll = long long;

vector<int> g[150005];
double d[150005];

void dfs1(int cur, int par) {
    int cnt = (int)g[cur].size() - (par != -1);
    if (cnt == 0) return;
    for (int nex : g[cur]) {
        if (nex == par) continue;
        dfs1(nex, cur);
        d[cur] += (d[nex] + 1) / cnt;
    }
}

double ans[150005];

void dfs2(int cur, double d_par, int par) {
    int cnt = g[cur].size();
    for (int nex : g[cur]) {
        if (nex == par) ans[cur] += d_par + 1;
        else ans[cur] += d[nex] + 1;
    }

    for (int nex : g[cur]) {
        if (nex == par) continue;
        dfs2(nex, (cnt > 1 ? (ans[cur] - d[nex] - 1) / (cnt - 1) : 0), cur);
    }
    ans[cur] /= cnt;
}

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

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs1(0, -1);
    dfs2(0, 0, -1);
    for (int i = 0; i < n; i++) {
        cout << setprecision(20) << ans[i] << endl;
    }
    return 0;
}

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

int main() {
    int N; cin >> N;
    bool can = false;
    for(int i = 1; i <= 9; ++i) {
        for(int j = 1; j <= 9; ++j) {
            if(N == i * j) can = true;
        }
    }
    
    if(can) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sz(c)       int(c.size())
#define rep(i,a,b)  for (int i=a; i<(b); ++i)
#define per(i,a,b)  for (int i=(b)-1; i>=(a); --i)
#define fore(c,...) for (auto &__VA_ARGS__:(c))
using namespace std;
using ll = long long;



int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	string s;
	cin>>s;
	cout<<(char)(s[0]+1)<<'\n';
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main()
    {
        var N = int.Parse(ReadLine());
        var uf = new UnionFind(N + N);
        for (int i = 0; i < N - 1; i++)
        {
            var line = ReadLine().Split(' ');
            var u = int.Parse(line[0]) - 1;
            var v = int.Parse(line[1]) - 1;
            var w = int.Parse(line[2]);
            if (w % 2 != 0)
            {
                uf.Unite(u, v + N);
                uf.Unite(u + N, v);
            }
            else
            {
                uf.Unite(u, v);
                uf.Unite(u + N, v + N);
            }
        }
        var ans = new int[N+N];
        for (int i = 0; i < N; i++)
        {
            var a = uf.Root(i);
            var b = uf.Root(i + N);
            if (ans[a] == 0)
            {
                ans[a] = 1;
                ans[b] = -1;
            }
        }

        for (int i = 0; i < N; i++)
        {
            WriteLine(ans[uf.Root(i)] == 1 ? "0" : "1");
        }
    }
}

public class UnionFind
{
    int[] parent;
    int count;
    public int Count => count;

    public UnionFind(int size)
    {
        parent = new int[size];
        for (int i = 0; i < parent.Length; i++)
        {
            parent[i] = -1;
        }
        count = size;
    }

    public int Root(int x) => parent[x] < 0 ? x : parent[x] = Root(parent[x]);

    public bool Same(int x, int y) => Root(x) == Root(y);

    public void Unite(int x, int y)
    {
        x = Root(x);
        y = Root(y);
        if (x == y) return;
        count--;
        if (parent[x] < parent[y])
        {
            parent[x] += parent[y];
            parent[y] = x;
        }
        else
        {
            parent[y] += parent[x];
            parent[x] = y;
        }
    }

    public int Size(int x) => -parent[Root(x)];
}

Measured memory_bytes: 17364
//Atcoder abc 153 e
#include <bits/stdc++.h>
using namespace std;

int main(){
	int h,a;
	cin>>h>>a;
	int ans=0;
	if(h%a==0){
		ans=h/a;
	}
	else if(h%a!=0){
		ans=h/a;
		ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    cout << (n - 1) * n / 2 + (m - 1) * m / 2 << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <limits>

using namespace std;

int main(){
  
  int A[3][3];
  for(int i = 0; i<3; i++ ){
    for(int j = 0; j<3; j++){
      scanf("%d", &A[i][j]);
    }
  }

  int N;
  cin >> N;

  int B[3][3];
  for(int i = 0; i<3; i++ ){
    for(int j = 0; j<3; j++){
      B[i][j]=0;
    }
  } 

  for(int k=0; k<N; k++){
    int b;
    cin >> b;

    for(int i = 0; i<3; i++ ){
      for(int j = 0; j<3; j++){
        if(b == A[i][j]){
          B[i][j] = 1;
        }
      }
    }
  }
  int tate, yoko;
  for(int i=0; i<3; i++){
    tate = 0;
    yoko = 0;
    for(int j=0;j<3;j++){
      if(B[i][j]==1)yoko++;
      if(B[j][i]==1)tate++;
    }
    if (tate==3 || yoko==3){
      cout << "Yes" << endl;
      return 0;
    } 
  }
  int n1=0, n2=0;
  for(int i=0;i<3;i++){
    n1 += B[i][i];
    n2 += B[i][2-i];
  }
  if(n1==3 || n2==3){
    cout << "Yes" << endl;
    return 0;
  }

  cout << "No" << endl;
  return 0;



  cout << (N-1)/2 + 1 << endl;

  return 0;
}

Measured memory_bytes: 256
//Reflection
#include <iostream>
#include <math.h>
#include <iomanip>

using namespace std;

static const double ESP = 1e-10;

bool equals(double a, double b) { return fabs(a - b) < ESP; }

class Point {
public:
    double x, y;

    explicit Point(double x = 0, double y = 0): x(x), y(y) {}

    Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
    Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
    Point operator * (double a) { return Point(a * x, a * y); }
    Point operator / (double a) { return Point(a / x, a / y); }

    double norm() { return x * x + y * y; }
    double abs() { return sqrt(norm()); }

    bool operator < (const Point &p) const {
        return x != p.x ? x < p.x : y < p.y;
    }

    bool operator == (const Point &p) const {
        return fabs(x - p.x) < ESP && fabs(y - p.y) < ESP;
    }
};

typedef Point Vector;

struct Segment {
    Point p1, p2;
    Segment(Point p1, Point p2): p1(p1), p2(p2) {}
};

double dot(Vector a, Vector b) {
    return a.x * b.x + a.y * b.y;
}

double cross(Vector a, Vector b) {
    return a.x * b.y - a.y * b.x;
}

bool isParallel(Vector v1, Vector v2) {
    return equals(cross(v1, v2), 0.0);
}

bool isOrthogonal(Vector v1, Vector v2) {
    return equals(dot(v1, v2), 0.0);
}

Point project(Segment s, Point p) {
    Vector base = s.p2 - s.p1;
    return s.p1 + (base * (dot(base, p - s.p1) / base.norm()));
}

Point reflect(Segment s, Point p) {
    return p + (project(s, p) - p) * 2;
}

int main() {
    int q;
    double x, y, x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2 >> q;
    Point p1 = Point(x1, y1), p2 = Point(x2, y2);
    Segment s = Segment(p1, p2);
    for(int i = 0; i < q; i++) {
        cin >> x >> y;
        Point p = Point(x, y);
        Point x = reflect(s, p);
        cout << setprecision(15) << x.x << " " << x.y << endl;
    }
}


Measured memory_bytes: 3288
N, K = map(int, input().split())

prob = [0] * N

for i in range(1,N+1):
    tmp = i
    for j in range(1,K+1):
        if tmp >= K:
            prob[i-1] = 1
            break
        tmp *= 2
        if tmp >= K:
            prob[i-1] = ((1/2)**j)
            break

ans = 0
tmp = 0

for i in range(N):
    tmp += prob[i]
    ans = 1/N * tmp

print(ans)

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

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

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

            int value;
            cin >> value;
            b.push_back(value);
    }
    for(int i = 0 ; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            int value;
            cin >> value;
            a[i].push_back(value);
        }
    }
    int cc = 0;
    for(int i = 0 ; i < n; i++)
    {
        int p = 0;
        for(int j = 0; j < m; j++)
        {
            p += (a[i][j]*b[j]);
        }
        p += c;
        if(p > 0)
            cc++;
    }
    cout<< cc << "\n";













return 0;}


Measured memory_bytes: 256
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, l[109]; string s[109], t;
int main() {
	int cnt = 0;
	while (cin >> n, n) {
		for (int i = 0; i < n; i++) cin >> s[i] >> l[i];
		cin >> t;
		vector<int> dp1(t.size() + 1);
		for (int i = 1; i <= t.size(); i++) {
			dp1[i] = 0;
			for (int j = 0; j < n; j++) {
				if (s[j].size() <= i && t.substr(i - s[j].size(), s[j].size()) == s[j]) {
					dp1[i] = max(dp1[i], dp1[i - s[j].size()] + l[j]);
				}
			}
		}
		int res = dp1[t.size()];
		vector<vector<int> > dp2(n + 1, vector<int>(res + 1, 999999999));
		dp2[0][0] = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= res; j++) {
				dp2[i][j] = dp2[i - 1][j];
				if (j >= l[i - 1]) dp2[i][j] = min(dp2[i][j], dp2[i][j - l[i - 1]] + (int)s[i - 1].size());
			}
		}
		cout << "Case " << ++cnt << ": " << dp2[n][res] << endl;
	}
	return 0;
}

Measured memory_bytes: 3400
#include <iostream>

using namespace std;

void call(int n){
  int i = 1;
 CHECK_NUM:
  int x = i;
  if ( x % 3 == 0 ){
    cout << " " << i;
    goto END_CHECK_NUM;
  }
 INCLUDE3:
  if ( x % 10 == 3 ){
    cout << " " << i;
    goto END_CHECK_NUM;
  }
  x /= 10;
  if ( x ) goto INCLUDE3;
 END_CHECK_NUM:
  if ( ++i <= n ) goto CHECK_NUM;

  cout << endl;
}

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


Measured memory_bytes: 3092
from collections import defaultdict
n=int(input())
s=list(input())
left=s[:n]
right=list(reversed(s[n:]))

DL=defaultdict(int)
for i in range(2**n):
    red=[]
    blue=[]
    for j in range(n):
        if (i>>j)&1:
            red.append(left[j])
        else:
            blue.append(left[j])
    DL["".join(red),"".join(blue)]+=1

DR=defaultdict(int)
for i in range(2**n):
    red=[]
    blue=[]
    for j in range(n):
        if (i>>j)&1:
            red.append(right[j])
        else:
            blue.append(right[j])
    DR["".join(blue),"".join(red)]+=1

ans=0
for k,v in DL.items():
    if k in DR:
        ans+=v*DR[k]
print(ans)

Measured memory_bytes: 246836
import math
a2e_mod = []
for _ in range(5):
  v = input()
  a2e_mod.append([(v + 9) % 10, v])

a2e_mod.sort(reverse=True)
res = 0
for _, v in a2e_mod[:-1]:
  res += math.ceil(v / 10.0) * 10
print int(res + a2e_mod[-1][-1])

Measured memory_bytes: 2568
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

signed main(){
    int n;
    cin >> n;
    pair<int,int> A[n];
    REP(i,n){
        cin >> A[i].se;
        cin >> A[i].fi;
    }
    sort(A,A+n);
    int su = 0;
    REP(i,n){
        su += A[i].se;
        if(su > A[i].fi){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 3328
//code by parshuram_84
#include<bits/stdc++.h>
#define mod 1000000007
#define pii pair<int,int>
#define pll pair<long long,long long>
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007 //998244353
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define vp vector<pair<long long,long long>>
#define vpp vector<pair<pair<long long,long long>,long long>>
using namespace std;

int main() {
	int a,b,c,d,x=0,j,i;
	cin>>a>>b>>c>>d;
	while(a>0 && c>0)
	{
		c-=b;
		if(c<=0) break;
		a-=d;
		if(a<=0) break;
	}
	if(a<=0) cout<<"No\n";
	else cout<<"Yes\n";
	return 0;
}

Measured memory_bytes: 3636
#include <algorithm>
#include <numeric>
#include <map>
#include <vector>
#include <cmath>
#include <complex>
#include <iostream>
#include <iomanip>

using namespace std;
typedef long long ll;

const int MN = 310;
int data[MN];
int sum[MN];
//sum[i] = [0+1..+i)
ll calc(int l, int r, int m) {
  int s1 = sum[m+1]-sum[l];
  int s2 = sum[r+1]-sum[m+1];
  ll res = 0;
  int c = 0;
  while (s1 || s2) {
	int d1 = s1 % 10;
	int d2 = s2 % 10;
	res += d1*d2+c;
	c = (d1+d2+c)/10;
	s1 /= 10;
	s2 /= 10;
  }
  res += c;
  return res;
}

bool used[MN][MN];
ll dp[MN][MN];
ll solve(int l, int r) {
  //  printf("%d %d", l, r);
  if (r == l) return 0;
  if (used[l][r]) return dp[l][r];
  used[l][r] = true;
  ll res = 1LL<<55;
  for (int m = l; m < r; m++) {
	res = min(res, solve(l, m)+solve(m+1, r)+calc(l, r, m));
	if (!res) {
	  //	  printf("%d %d %d", l, r, m);
	}
  }
  return (dp[l][r] = res);
}

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
	cin >> data[i];
  }
  sum[0] = 0;
  for (int i = 0; i < n; i++) {
	sum[i+1] = sum[i] + data[i];
  }
  cout << solve(0, n-1) << endl;
}

Measured memory_bytes: 2004
#include <stdio.h>
#include <math.h>
#include <string.h>

int mini(int a, int b) {
	if (a < b) {
		return a;
	}
	else {
		return b;
	}
}

int main() {
	int D, i, p[10], c[10], G, min = 1000, sum, count, complete[10], j, rem, quo;

	scanf("%d %d", &D, &G);
	for (i = 0; i < D; i++) {
		scanf("%d %d", &p[i], &c[i]);
	}

	for (i = 0; i < pow(2, D); i++) {
		sum = 0;
		count = 0;
		for (j = 0; j < D; j++) {
			if ((i >> j) % 2 == 1) {
				sum = sum + c[j] + (j + 1) * 100 * p[j];
				count = count + p[j];
				complete[j] = 1;
			}
			else {
				complete[j] = 0;
			}
		}
		if (sum < G) {
			for (j = D - 1; j >= 0; j--) {
				if (complete[j] == 0) {
					if (G <= sum + (j + 1) * 100 * (p[j] - 1)) {
						rem = (G - sum) % ((j + 1) * 100);
						quo = (G - sum) / ((j + 1) * 100);
						if (rem == 0) {
							count = count + quo;
							sum = sum + (j + 1) * 100 * quo;
						}
						else {
							count = count + quo + 1;
							sum = sum + (j + 1) * 100 * (quo + 1);
						}

					}
					break;
				}
			}
		}
		if (sum >= G) {
			min = mini(min, count);
		}
	}

	printf("%d", min);

	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

const char Q = 'Q';
const char _ = '.';
const int offset = 7;

char board[8][9] = {
    "........",
    "........",
    "........",
    "........",
    "........",
    "........",
    "........",
    "........",
};

bool pre_x[8], pre_y[8], diag_L[15], diag_T[15];
int n;

bool solve(int row) {
    if (row == 8)
        return true;
    if (pre_y[row] && solve(row + 1)) {
        return true;
    }
    else {
        for (int i = 0; i < 8; ++i) {
            if (!pre_x[i] && !diag_L[row + i] && !diag_T[i-row+offset]) {
                board[row][i] = Q;
                pre_x[i] = diag_L[row+i] = diag_T[i-row+offset] = true;
                if (solve(row + 1)) {
                    return true;
                }
                else {
                    board[row][i] = _;
                    pre_x[i] = diag_L[row+i]
                             = diag_T[i-row+offset] = false;
                }
            }
        }
    }
    return false;
}

int main(void) {

    scanf("%d", &n);

    for (int i = 0, x, y; i < n; ++i) {
        scanf("%d %d", &y, &x);
        board[y][x] = Q;
        pre_y[y] = pre_x[x] = diag_L[x+y] = diag_T[x-y+offset] = true;
    }

    solve(0);

    for (int i = 0; i < 8; ++i) {
        printf("%s\n", board[i]);
    }

    return 0;
}

Measured memory_bytes: 1168
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			double x = sc.nextDouble();
			double h = sc.nextDouble();
			if(x==0 && h==0)break;
			double c = Math.sqrt(h*h + (x/2)*(x/2));
			double ans = x*x + x*c/2*4;
			System.out.println(ans);
		}
	}
}

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

int main()
{
	int N;
	cin >> N;
	vector<int> a(N);
	bool ok = false;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		if (a[i] & 1) ok = true;
	}
	puts(ok ? "first" : "second");
	return 0;
}


Measured memory_bytes: 640
from functools import reduce
n=int(input())
def sqdivlist(n):
    lista=[]
    for i in range(1,int((n**0.5)//1)+1):
        if n%i==0:
            lista.append(str(i))
    return (lista)
t=len(sqdivlist(n))
u=(sqdivlist(n))
lista2=[]
ans=[]
for j in range(t):
    lista2.append(int(n/int(u[j])))
    ans.append(max(len(str(u[j])),(len(str(lista2[j])))))
print(min(ans))


Measured memory_bytes: 3572
#import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
A = [LI() for _ in range(N)]
m = [[0] * 3 for _ in range(8)]

# + + +
# - - -
A.sort(key=lambda x:x[0]+x[1]+x[2])
for i in range(M):
	for j in range(3):
		m[0][j] += A[i][j]
		m[1][j] += A[N-1-i][j]

# + + -
# - - +
A.sort(key=lambda x:x[0]+x[1]-x[2])
for i in range(M):
	for j in range(3):
		m[2][j] += A[i][j]
		m[3][j] += A[N-1-i][j]

# + - +
# - + -
A.sort(key=lambda x:x[0]-x[1]+x[2])
for i in range(M):
	for j in range(3):
		m[4][j] += A[i][j]
		m[5][j] += A[N-1-i][j]

# + - -
# - + +
A.sort(key=lambda x:x[0]-x[1]-x[2])
for i in range(M):
	for j in range(3):
		m[6][j] += A[i][j]
		m[7][j] += A[N-1-i][j]

print(max([abs(x[0])+abs(x[1])+abs(x[2]) for x in m]))


Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        int x;cin>>x;
        if(x%2==0) 
        {
            if(x%3!=0&&x%5!=0)
            {
                puts("DENIED");
                return 0;
            }
        }
    }
    puts("APPROVED");
    return 0;
}

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

constexpr long double EPS = 1e-15;
const long double PI = acos(-1);
constexpr int inf = 2e9;
constexpr ll INF = 2e18;
constexpr ll MOD = 1e9+7;
constexpr ll MOD1 = 998244353;
typedef pair<ll,ll> P;

//#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

int a[100010];

void solve() {
  int n;
  cin >> n;
  REP(i,n) {cin >> a[i];}
  bool ans = 1;
  for (int i = 1; i < n; i++) {
    if (a[i] == a[i-1]) continue;
    a[i]--;
    if (a[i] < a[i-1]) {
      ans = 0;
      break;
    }
  }
  cout << (ans?"Yes":"No") << endl;
}

int main(int argc, char *argv[]){

  /* Regular */
  int case_num = 1;
  if (argc > 1 && stoi(argv[1])) cin >> case_num;
  REP(case_no, case_num) {
    cerr << endl << "case " << case_no + 1 << endl;
    solve();
  }
  
  // /* AOJ */
  // solve();
  return 0;
}

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

const int INF = 1001001001;

int main() {
  int n,m;
  cin >> n >> m;
  vector<pair<int,int>> key;
  rep(i,m){
    int a,b;
    cin >> a >> b;
    int s = 0;
    rep(j,b){
      int c;
      cin >> c;
      c--;
      s |= 1<<c;
    }
    key.emplace_back(s,a);
  }

  vector<int> dp(1<<n, INF);
  dp[0] = 0;
  rep(s,1<<n) {
    rep(i,m) {
      int t = s | key[i].first;
      int cost = dp[s] + key[i].second;
      dp[t] = min(dp[t], cost);
    }
  }
  int ans = dp.back();
  if(ans == INF) ans = -1;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int i,j,m;
    scanf("%d",&m);
    for(i=1; i<=9; i++)
    {
        for(j=1; j<=9; j++)
        {
            if((i*j)==m)
            {
                printf("Yes\n");
                exit(0);
            }
        }
    }
    printf("No\n");
    return 0;


}


Measured memory_bytes: 256
import sys
s = input()
t = input()

n,m = len(s),len(t)

ans = sys.maxsize


for i in range(n-m + 1):
    remove = 0
    for j in range(m):
        if (t[j]!=s[i+j]):
            remove += 1
    ans = min(remove,ans)
print(ans)


Measured memory_bytes: 8984
#include <bits/stdc++.h>
#define ll long long
#define MODV 998244353
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    ll a, b, c, d;
    cin >> a >> b >> c >> d;

    // dp[i][j]; a行b列から始めて、i行j列まで拡張した場合に考えられる盤面の数
    vvi dp(c+1, vi(d+1, 0));
    dp[a][b] = 1;

    for(ll h=a; h<=c; h++){
        for(ll w=b; w<=d; w++){
            // 縦に広げる操作（選べる箇所がw箇所増える）
            if(h > a){
                dp[h][w] += dp[h-1][w] * w;
                dp[h][w] = (dp[h][w]%MODV+MODV)%MODV;
            }
            // 横に広げる操作（選べる箇所がh箇所増える）
            if(w > b){
                dp[h][w] += dp[h][w-1] * h;
                dp[h][w] = (dp[h][w]%MODV+MODV)%MODV;
            }
            // 操作の順番によって同じ盤面をダブルカウントしているので、その分を取り除く
            //（右上に黒を置かないパターンは重複でカウントしている）
            // 重複が生じるのは、dp[h-1][w-1]の時点で(h-1) * (w-1)通り
            if(h > a && w > b){
                dp[h][w] -= dp[h-1][w-1] * (h-1) * (w-1);
                dp[h][w] = (dp[h][w]%MODV+MODV)%MODV;
            }
        }
    }
    cout << (dp[c][d]%MODV+MODV)%MODV << endl;
}

Measured memory_bytes: 73660
A = list()
for _ in range(3):
    A.append(list(map(int, input().split())))

N = int(input())
B = list()
for _ in range(N):
    B.append(int(input()))

flag = [[False] * 3 for i in range(3)]
for b in B:
    for i in range(3):
        for j in range(3):
            if A[i][j] == b:
                flag[i][j] = True
                break

ans = False
for i in range(3):
    if flag[i].count(True) == 3:
        ans = True
    if [f[i] for f in flag].count(True) == 3:
        ans = True
if flag[0][0] == flag[1][1] == flag[2][2] == True or flag[0][2] == flag[1][1] == flag[2][0] == True:
    ans = True

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


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

#define ll long long

int main() {
    std::ios::sync_with_stdio(false);
    using namespace std;
    string A, B;
    cin >> A >> B;

    vector< vector<bool> > C(A.size() + 1);
    for(int i = 0; i < A.size() + 1; i++)
        C[i].resize(B.size() + 1, false);

    array< vector<int>, 2 > D;
    for(auto i : {0, 1})
        D[i].resize(B.size() + 1, 0);

    for(int i = 1; i <= A.size(); i++)
        for(int j = 1; j <= B.size(); j++) {
            if(A[i - 1] == B[j - 1]) {
                D[i % 2][j] = D[(i + 1) % 2][j - 1] + 1;
            } else if(D[(i + 1) % 2][j] > D[i % 2][j - 1]) {
                D[i % 2][j] = D[(i + 1) % 2][j];
                C[i][j] = true;
            } else {
                D[i % 2][j] = D[i % 2][j - 1];
            }
        }

    string result;
    int i = A.size(), j = B.size();
    while(i > 0 && j > 0) {
        if(A[i - 1] == B[j - 1]) {
            result += A[i - 1];
            i--; j--;
        } else if(C[i][j]) {
            i--;
        } else {
            j--;
        }
    }
    reverse(result.begin(), result.end());
    cout << result << "\n";

    return 0;
}


Measured memory_bytes: 1664
k, x = map(int, input().split())

a = []
for i in range(k):
  a.append(x-i)
for i in range(k-1):
  a.append(x+1+i)
a.sort()
res = ''
for i in range(len(a)):
  res += str(a[i])
  if i != len(a)-1:
    res += (' ')
  
print(res)

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

void solve()
{
    int n, m;
    cin >> n >> m;
    if (n == m)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

int main()
{
    solve();
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
constexpr int MAX = 101;
enum Color { WHITE = 0, GRAY, BLACK};
int n, tt{0};
vv(int, M, MAX, MAX, 0);
vi color(MAX, 0), d(MAX, 0), f(MAX, 0);
inline void dfs_visit(int u) {
	color[u] = GRAY;
	d[u] = ++tt;
	rep(v, 0, n) {
		if(M[u][v] == 0) continue;
		if(color[v] == WHITE) {
			dfs_visit(v);
		}
	}
	color[u] = BLACK;
	f[u] = ++tt;
}
inline void dfs() {
	rep(u, 0, n) {
		if(color[u] == WHITE) dfs_visit(u);
	}
	rep(u, 0, n) {
		cout << u + 1 << " " << d[u] << " " << f[u] << endl;
	}
}
int main() {
	cin >> n;
	int u, k, v;
	rep(i, 0, n) {
		cin >> u >> k;
		--u;
		rep(j, 0, k) {
			cin >> v;
			M[u][--v] = 1;
		}
	}
	dfs();
	return 0;
}

Measured memory_bytes: 3196
# -*- coding: utf-8 -*-

'''
abc : < 1200
arc : < 2800
agc : all
'''

# 入力データ
in_data = int(input())
if in_data < 1200:
	print('ABC')
elif in_data < 2800:
	print('ARC')
else:
	print('AGC')


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
long long inf=(long long)1E17;
//#define i_7 (long long)(1E9+7)
#define i_7 (long long)(1E6+3)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;

//typedef long long ll;
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}

//配列のSIZEは問題ごとに定義する必要がある。
const int SIZE=2'000'010;
long long inv[SIZE+1];//各iの逆元を格納する配列。
long long kai[SIZE+1];//i!のmodを格納する配列。
long long invkai[SIZE+1];//各i!の逆元を格納する配列。
const int MOD=i_7;
void invinit(){//上の配列を初期化する関数。
    inv[1]=1;
    for(int i=2;i<=SIZE;i++){
        inv[i] = MOD - ((MOD/i)*inv[MOD%i])%MOD;
    }
    
    kai[0]=invkai[0]=1;
    for(int i=1;i<=SIZE;i++){
        kai[i]=(kai[i-1]*i)%MOD;
        invkai[i]=(invkai[i-1]*inv[i])%MOD;
    }
}

long long comb(long long a, long long b){
    if(b<0 || a<b){
        return 0;
    }
    return mod(kai[a]*mod(invkai[b]*invkai[a-b]));
}

int main(){
  invinit();
  int q;
  cin>>q;
  long long x[q], d[q], n[q];
  long long ans[q];
  REP(i,q){
    cin>>x[i]>>d[i]>>n[i];
    if(d[i] == 0){
      ans[i] = po(x[i], n[i]);
      continue;
    }
    if(n[i] >= 1'000'003){
      ans[i] = 0;
      continue;
    }
    long long y = mod(x[i] * inv[d[i]]);
    ans[i] = po(d[i], n[i]);
    ans[i] *= kai[y+n[i]-1];
    ans[i] = mod(ans[i]);
    ans[i] *= invkai[y-1];
    ans[i] = mod(ans[i]);
  }
  REP(i,q){
    cout<<ans[i]<<endl;
  } 
  return 0;
}


Measured memory_bytes: 50816
import java.util.Scanner;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if(a>b) System.out.println("a > b");
        if(a<b) System.out.println("a < b");
        if(a==b) System.out.println("a == b");
    }
}


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

const int Nmax=200010;

int main() {
	int N;
  	bool flag=false;
	cin >> N;
	int index[10]={};
	if((N%1000)/100 == (N%100)/10){
		index[N / 1000]++;
  		N %= 1000;
  		index[N / 100]++;
  		N %= 100;
  		index[N / 10]++;
  		N %= 10;
  		index[N]++;
  		for(int i=0;i < 10;i++)
      		if(index[i] >= 3) flag = true;
    }
	
	if(flag) cout << "Yes" << endl;
  	else cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string n;
	cin>>n;
	if(n[0]==n[1]&&n[1]==n[2])
	{
		cout<<"Yes"<<endl;
		return 0;
	}
	else
	if(n[1]==n[2]&&n[2]==n[3])
	{
		cout<<"Yes"<<endl;
		return 0;
	}
	cout<<"No"<<endl;
	return 0;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    string S; cin >> S;
    ll ans = 0;
    rep(i, S.size()){if (S[i] == '+'){ans++;}else{ans--;}}
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3560
#include<stdio.h>

int main() {
  int n,R[200000],minv,maxv,j;
   while(1) {
  scanf("%d",&n);
    if(2 <= n || n <= 200000) break;
   }
  for(j = 0;j < n;j++) {
    scanf("%d",&R[j]);
    if(1 > R[j] || R[j] > 1000*1000*1000) j=j-1;
  }
  maxv = R[1]-R[0];
  minv = R[0];
  
  for(j=1;j<=n-1;j++) {
    if(maxv > R[j]-minv) maxv = maxv;
    else maxv = R[j]-minv;
    if(minv < R[j]) minv =minv;
    else minv = R[j];
  }
  printf("%d\n",maxv);
  return 0;
}

Measured memory_bytes: 1376
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#undef max
#undef min

int dp[11][100001] = { 0 };
int knapsack(int maxWeight, std::vector<int> cost, std::vector<int> benefit) {
    if (cost.size() != benefit.size()) return 0;
    std::memset(dp, 0, sizeof(dp));
    int maxBenefit = maxWeight;
    for (int i = 0; i <= 100000; i++) {
        dp[0][i] = i;
    }
    for (int i = 0; i < cost.size(); i++) {
        for (int j = 0; j <= maxWeight; j++) {
            if (cost[i] > j) dp[i + 1][j] = dp[i][j];
            else {
                dp[i + 1][j] = std::max(dp[i][j], dp[i+1][j - cost[i]] + benefit[i]);
                maxBenefit = std::max(maxBenefit, dp[i + 1][j]);
            }
        }
    }
    return maxBenefit;
}

int main() {
    int n, d, x;
    std::vector<std::vector<int>> p;

    std::cin >> n >> d >> x;
    for (int i = 0; i < d; i++) {
        p.push_back(std::vector<int>());
        for (int j = 0; j < n; j++) {
            int a;
            std::cin >> a;
            p.back().push_back(a);
        }
    }

    for (int i = 0; i < d - 1; i++) {
        x = knapsack(x, p[i], p[i+1]);
    }
    std::cout << x << std::endl;
    return 0;
}


Measured memory_bytes: 7436
#include<iostream>
int T[10];
int ans;

void method(int num,int A,int B){
  if(num==10){
    ++ans;
    return;
  }
  if(T[num]>A){
    method(num+1,T[num],B);
  }
  if(T[num]>B){
    method(num+1,A,T[num]);
  }
}
int main(){
  int n;

  std::cin >> n;

  for(int i=0;i<n;i++){
    for(int j=0;j<10;j++){
      std::cin >> T[j];
    }
    ans = 0;
    method(0,0,0);
    std::cout << ((!ans)? "NO" : "YES") << std::endl;
  }
}

Measured memory_bytes: 3048
# coding: utf-8

# In[4]:


import numpy as np


# In[6]:


N, D = map(int, input().split())
X_list = []
Y_list = []
for i in range(N):
    xi,yi = map(int, input().split())
    X_list.append(xi)
    Y_list.append(yi)
X = np.array(X_list)
Y = np.array(Y_list)


# In[18]:


distance_array = np.sqrt( X**2 + Y**2 )
N_near = len( np.where(distance_array<=D)[0] )
print(N_near)



Measured memory_bytes: 49400
#include <bits/stdc++.h>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)

using namespace std;
int R, N, A[100];

int main(void){
	//IO("test.in", "test.out");
	R = INT_MAX;
	scanf("%d", &N);
	for(int i = 0; i < N; i++) scanf("%d", &A[i]);
	for(int i = -100; i <= 100; i++){
		int s = 0;
		for(int j = 0; j < N; j++) s += (A[j] - i) * (A[j] - i);
		if(s < R) R = s;
	}
	printf("%d\n", R);
}

Measured memory_bytes: 256
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-11;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 11100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	inline long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ

int main(){
	int a;
	long long b;scanf("%d%lld",&a,&b);
	int ret=0;
	for(int i=0;i<a;i++){
		long long x,y;scanf("%lld%lld",&x,&y);
		if(x*x+y*y<=b*b)ret++;
	}
	printf("%d\n",ret);
}

Measured memory_bytes: 1732