akhauriyash/Code-Regression huggingface dataset:
def main():
    inp = input().split(' ')
    n = int(inp[0])
    q = int(inp[1])
    ab = {}
    tree = [0 for i in range(n)]
    for i in range(n-1):
        inp = input().split(' ')
        ab[int(inp[1])] = int(inp[0])
    for i in range(q):
        inp = input().split(' ')
        tree[int(inp[0])-1] += int(inp[1])
    for i in range(n):
        parent = ab.get(i+1)
        if parent is None:
            continue
        else:
            tree[i] += tree[parent-1]
    str_tree = list(map(lambda x: str(x), tree))
    print(' '.join(str_tree))


if __name__ == '__main__':
    main()


Measured memory_bytes: 59668
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
typedef vector<ii> vii;
typedef vector<ll> vll;
random_device device;
mt19937 generator(device());
uniform_int_distribution<int> get_random(0,10);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ii take(ll x)
{
	ii res=ii(0,0);
	while(x%2==0)
	{
		x/=2;
		res.first++;
	}
	while(x%5==0)
	{
		x/=5;
		res.second++;
	}
	return res;
}
map<ii,int> cnt;
int main()
{
	int i,j,k,n;
	scanf("%d",&n);
	long double num;
	ll ans = 0;
	ll x,y,g;
	for(i=0;i<n;i++)
	{
		cin >> num;
		x = llround(num*1e9);
		cnt[take(x)]++;
	}
	for(auto i:cnt)
	{
		for(auto j:cnt)
		{
			if(i.first.first+j.first.first>=18&&i.first.second+j.first.second>=18)
			{
				if(i<j)		ans += 1ll*i.second*j.second;
				if(i==j)	ans += 1ll*(i.second)*(j.second-1)/2;
			}
		}
	}
	printf("%lld",ans);
}


Measured memory_bytes: 3872
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

print(input()[:3])

Measured memory_bytes: 61708
#include <bits/stdc++.h>
#define len(x) (int) (x.size())
using namespace std;
typedef long long ll;

int main(){
    string a;
    cin >> a;

    if(a[a.size()-1] == '2' || a[a.size()-1] == '4' || a[a.size()-1] == '5' || a[a.size()-1] == '7' || a[a.size()-1] == '9') {
        cout << "hon" << '\n';
    }
    else if (a[a.size()-1] == '3') {
        cout << "bon" << '\n';
    }
    else {
        cout << "pon" << '\n';
    }

    return 0;
}

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

using namespace std;

typedef long long LL;
#define N 305

const LL mod=998244353;
LL n,sum,ans,a[N],f[N][N*N];

void upd(LL &x,LL y){x=(x+y%mod+mod)%mod;}

int main(){
	scanf("%lld",&n);
	for (LL i=1;i<=n;++i){scanf("%lld",a+i); sum+=a[i];}
	ans=1; for (LL i=1;i<=n;++i) ans=ans*3%mod;
	f[0][0]=1;
	for (LL i=1;i<=n;++i)
		for (LL j=0;j<=i*300;++j){
			upd(f[i][j],f[i-1][j]*2);
			upd(f[i][j+a[i]],f[i-1][j]);
		}
	for (LL i=(sum+1)/2;i<=n*300;++i) upd(ans,-f[n][i]*3);
	if (sum%2==0){
		memset(f,0,sizeof f);
		f[0][0]=1;
		for (LL i=1;i<=n;++i)
			for (LL j=0;j<=i*300;++j){
				upd(f[i][j],f[i-1][j]);
				upd(f[i][j+a[i]],f[i-1][j]);
			}
		upd(ans,f[n][sum/2]*3);
	}
	printf("%lld\n",ans);
	
	return 0;
}
			

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

typedef signed long long ll;
const ll mod  = 1e9 + 7;

int main() {
    int n;
    ll ans = 1;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        ans = (ans * i) % mod;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
  int n;
  std::cin >> n;
  for (int l = 0; l < n; l++) {
    vector<vector<int> > cards(3, vector<int>(11, 0));
    vector<int> number(10), color(10);
    for (int i = 0; i < 9; i++) std::cin >> number[i];
    for (int i = 0; i < 9; i++) {
      char c;
      std::cin >> c;
      if(c == 'R'){
        cards[0][number[i]]++;
      }else if(c == 'B'){
        cards[1][number[i]]++;
      }else if(c == 'G'){
        cards[2][number[i]]++;
      }
    }
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 9; j++) {
        if(cards[i][j] < 0){
          std::cout << 0 << std::endl;
          i = j = 1e9;
          break;
        }
        cards[i][j] %= 3;
        cards[i][j + 1] -= cards[i][j], cards[i][j + 2] -= cards[i][j];
      }
      if(i == 2)std::cout << 1 << std::endl;
    }
    
  }

  return 0;
}



Measured memory_bytes: 3028
#include<stdio.h>
 
int main(void)
{
  int i, max=0, sum=0, n;
  int l[10];
  scanf("%d", &n);
  scanf("%d %d %d %d %d %d %d %d %d %d", &l[0], &l[1], &l[2], &l[3], &l[4], &l[5], &l[6], &l[7], &l[8], &l[9]);
  for(i=0; i<n; i++){
    sum += l[i];
    if(max < l[i])
      max = l[i];
  }
  if(max < sum - max)
    printf("Yes");
  else
    printf("No");
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main(){
	int n,a[10000],i,x;
	long long sum=0,max=-1000000,min=1000000;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
		if(a[i]>max){
			max=a[i];
		}
		if(a[i]<min){
			min=a[i];
		}
	}
	cout<<min<<" "<<max<<" "<<sum<<endl;
	//What Japanese people!?

	return 0;
}

Measured memory_bytes: 3128
d, g = map(int, input().split())
pc = [list(map(int,input().split())) for _ in range(d)]
ans = g//100 + 1

for i in range(2**d):
    count = 0
    total = 0
    for j in range(d):
        if (i >> j) & 1 == 1:
            count += pc[j][0]
            total += (j+1)*100*pc[j][0] + pc[j][1]

    if total >= g:
        ans = min(ans, count)
    else:
        for k in reversed(range(d)):
            if ((i >> k) & 1) == 0:
                for _ in range(pc[k][0]-1):
                    count += 1
                    total += (k+1)*100
                    if total >= g:
                        ans = min(ans, count)
                        break

print(ans)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	string s;
	cin>>s;
	long long int maxl=0;
	long long int cl=0;
	for(long long int i=0;i<s.size();i++){
		if((s[i]=='A'||s[i]=='T'||s[i]=='C'||s[i]=='G')){
			cl++;
			maxl=max(maxl,cl);
		}
		else{
			cl=0;
		}
	}
	cout<<maxl;
	return 0;
}

Measured memory_bytes: 3588
/*
 * atcoder/abc100/c.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }


ll num_2(ll a) {
  ll count = 0;
  while (a%2==0) {
    count++;
    a/=2;
  }
  return count;
}

int N;
void solve() {
  cin >> N;
  ll a;
  ll total = 0;
  loop(n,0,N) {
    cin >> a;
    total += num_2(a);
  }
  cout << total << endl;
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <math.h>
#include <cmath>
#define ll long long
#define lli long long int

using namespace std;
using P = pair<int,int>;


vector<int> enum_div(int n){
  vector<int> ret;
  for(int i = 1 ; i*i <= n ; ++i){
    if(n%i == 0){
      ret.push_back(i);
      if(i != 1 && i*i != n){
        ret.push_back(n/i);
      }
    }
  }
  return ret;
}

int main(){

  int N;
  cin >> N;
  int ans = 0;

  for (int i = 1; i <= N; i++) {
    vector<int> vec(i);
    vec = enum_div(i);
    int size = vec.size()+1;
    if(i%2 != 0 && size == 8) ans++;
  }

  cout << ans << endl;

  return 0;
}

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

set<ll> divs(ll n) {
  set<ll> res;
  for (ll k=1; k*k <=n; k++) {
    if (n%k == 0) {
      res.insert(k);
      res.insert(n/k);
    }
  }
  return res;
}

signed main() {
  ll n;
  vector<ll> ans;
  cin >> n;
  for (auto k : divs(n)) {
    if (k == 1) continue;
    ll t = n;
    while (t % k == 0) t /= k;
    t %= k;
    if (t == 1) ans.push_back(k);
  }
  for (auto k : divs(n-1)) {
    if (k == 1) continue;
    ans.push_back(k);
  }
  cout << ans.size() << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 1e18;
using Graph = vector<vector<int>>;

const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    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;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

signed main() {
  COMinit();
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for( int i = 0; i < N; i++ ) cin >> A[i];
  sort(A.begin(), A.end());

  int min_sum = 0;
  for( int i = 0; i < N; i++ ){
    if( N-i-1 < K-1 ) continue;
    int choice = COM(N-i-1, K-1);
    choice = choice*A[i];
    choice %= MOD;
    min_sum += choice;
    min_sum %= MOD;
  }

  int max_sum = 0;
  for( int i = 0; i < N; i++ ){
    if( i < K-1 ) continue;
    int choice = COM(i, K-1);
    choice = choice*A[i];
    choice %= MOD;
    max_sum += choice;
    max_sum %= MOD;
  }

  int ans = max_sum - min_sum;
  ans %= MOD;
  if( ans < 0 ) ans += MOD;
  cout << ans << endl;


 }

Measured memory_bytes: 15936
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007
using namespace std;



int main(void){
	int n,m;
	cin>>n>>m;
	ll work[n][3][2],score[n],ans=0;
	rep(i,n){
		cin>>work[i][0][0]>>work[i][1][0]>>work[i][2][0];
		work[i][0][1]=-work[i][0][0];
		work[i][1][1]=-work[i][1][0];
		work[i][2][1]=-work[i][2][0];
	}
	rep(i,8){
		rep(j,n){
			score[j]=0;
			if(i%2 == 0)score[j]+=work[j][0][0];
			else score[j]+=work[j][0][1];
			if((i/2)%2 == 0)score[j]+=work[j][1][0];
			else score[j]+=work[j][1][1];
			if((i/4)%2 == 0)score[j]+=work[j][2][0];
			else score[j]+=work[j][2][1];
		}
		sort(score,score+n);
		//rep(j,m)cout<<score[n-1-j]<<" ";
		//cout<<endl;
		ll tmp=0;
		rep(j,m)tmp+=score[n-1-j];
		if(ans < tmp)ans=tmp;
	}

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define increase(a) sort(a.begin(), a.end())
#define decrease(a) sort(a.rbegin(), a.rend())
#define loop(n) for(ll i = 0; i<n; i++)
using namespace std;

int main(){
    ll n; cin>>n;
    ll mat[10][10];
    for(int i = 0; i<10; i++){
        for(int j = 0; j<10; j++) mat[i][j] = 0;
    }

    string s;
    char l_dig, f_dig;
    ll ss;
    for(ll i = 1; i<=n; i++){
        s = to_string(i);
        ss = s.size();
        l_dig = s[ss-1];
        f_dig = s[0];
        mat[l_dig - '0'][f_dig - '0']++;
    }

    ll ans = 0;
    for(int i = 0; i<10; i++){
        for(int j =0; j<10; j++) ans += mat[i][j]*mat[j][i];
    }

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

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

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

using ll = long long;

using namespace std;

int main() {
  in(int, a, b);
  out((a - 1) * (b - 1));
}


Measured memory_bytes: 3640
#include "stdio.h"

int main()
{
  int a, b, c, d;
  scanf("%d", &a);
  if(a <= 81)
  {
      for(b = 0; b < 10; b++)
      {
        for(c = 0; c < 10; c++)
        {
          d = b * c;
          if(d == a)
          {
            printf("Yes");
            return 0;
          }
        }
      }
  }
    printf("No");
    return 0;
}


Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include  <iostream>
#include  <algorithm>
#include  <climits>
#include  <vector>
#include  <string>
#include  <cstring>
#include  <stack>
#include  <queue>
#include  <cmath>
#include  <iomanip>
#include  <set>
#include  <map>
#include  <new>
#include <cstdint>
#include <cctype>
using namespace std;
#define rep(i,n)  for(int i = 0; i < n; i++)
#define lrep(i,n,m)  for(int i = n; i < m; i++)

using ll = long long;
using Vii = vector<vector<int> >;
using Gjudge = vector<vector<bool>>;
using Vi = vector<int>;
using Vl = vector<ll>;
using Vll = vector<vector<ll> >;
using Vs = vector<string>;
using Vb = vector<bool>;
using the = pair<int, int>;
using lthe = pair<ll, ll>;

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

const int Mod = static_cast<int>(1e9 + 7);
const int INF = INT_MAX;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,1,0,-1 };

int main()
{
    double w, h, x, y;
    cin >> w >> h >> x >> y;

    double s = w * h / 2.0;


    if (w / 2 == x && h / 2 == y) {
        cout << fixed << setprecision(8);
        cout << s << " " << 1 << endl;
    }
    else {
        cout << fixed << setprecision(8);
        cout << s << " " << 0 << endl;
    }
}


Measured memory_bytes: 256
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, X = map(int, input().split())
M = [int(input()) for _ in range(N)]

ans = 0
r = X-sum(M)

ans += len(M)
ans += r//min(M)
print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define sz(v)   ((int)(v).size())
#define  all(v)    ((v).begin()),((v).end())
#define  allr(v)    ((v).rbegin()),((v).rend())
#define   pb         push_back
#define   mp         make_pair
#define    Lcm(a,b)  ((a*b)/(__gcd(a,b)))
#define    clr(v,d)      memset( v, d ,sizeof(v))
#define    PI            acos(-1)
typedef  long long     ll ;
typedef  unsigned long long     ull ;
const long double eps= (1e-9);
using namespace std;
using namespace __gnu_pbds;
int dcmp(long double a,long double b){   return fabsl(a-b)<=eps ? 0: (a>b)? 1:-1  ;}
void GO(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int N=200000+9,mod=1e9+7;
map< pair<ll,ll> ,pair<ll,ll> > mb;
ll P[N];
pair<ll,ll> get_slope(ll a,ll b){

  ll gg=__gcd(a,b);
  a/=gg;
  b/=gg;

  if(b<0){
    a*=-1;
    b*=-1;
  }

  return mp(a,b);
}
int main(){
    GO();
    int n;
    cin>>n;
    P[0]=1;
    for(int i=1;i<=n;i++) P[i]=(P[i-1]*2)%mod;
    int Z=0;
    for(int i=0;i<n;i++){
        ll a,b;
        cin>>a>>b;
        if(a==0&&b==0){
            Z++;
            continue;
        }
        pair<ll,ll> p=get_slope(a,b);
        a=p.first;
        b=p.second;
        if(a<=0){
            mb[mp(b,-a)].second++;
        }
        else{
            mb[mp(a,b)].first++;
        }
    }
    ll ans=1;
    for(auto it=mb.begin();it!=mb.end();it++){
        ans*=(((P[(*it).second.first])+(P[(*it).second.second])-1)+mod)%mod;
        ans%=mod;
    }
    cout<<((ans-1+Z)%mod+mod)%mod<<"\n";

}








































Measured memory_bytes: 20772
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

int main() {
    int N,ans=1;   
    cin>>N;
    int H[20];
    cin>>H[0] ;
    int maxheight=H[0];       
    for(int i=1; i<N; i++){
       cin>>H[i];
       maxheight=max(maxheight,H[i]);
       if(maxheight<=H[i])ans++;
    } 
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
import bisect
import collections


def sequence_decomposing(N: int, A: list)->int:
    mins = collections.deque([A[0]])

    for a in A[1:]:
        i = bisect.bisect_left(mins, a)
        if i == 0:
            mins.appendleft(a)
        else:
            mins[i-1] = a

    return len(mins)


if __name__ == "__main__":
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = sequence_decomposing(N, A)
    print(ans)


Measured memory_bytes: 54360
import java.util.Scanner;

public class Main {

	static int mincost(int i, int k, int[] ar, int[] dp) {

		if (i == ar.length - 1)
			return 0;

		if (dp[i] != -1)
			return dp[i];

		int mincost = Integer.MAX_VALUE;
		
		for(int index = i + 1; index <= Math.min(ar.length - 1, i + k); index++)
			mincost = Math.min(mincost, (Math.abs(ar[i] - ar[index]) + mincost(index, k, ar, dp)));

		return dp[i] = mincost;
	}

	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int ar[] = new int[n];
		int dp[] = new int[n];

		for (int i = 0; i < n; i++) {
			ar[i] = sc.nextInt();
			dp[i] = -1;
		}

		System.out.println(mincost(0, k, ar, dp));
		sc.close();
	}

}

Measured memory_bytes: 63024
dice = [int(i) for i in input().split()]
n = int(input())
for _ in range(n):
    face = list(map(int, input().split()))
    if face in [[dice[0], dice[1]], [dice[1], dice[5]], [dice[5], dice[4]], [dice[4], dice[0]]]:
        print(dice[2])
    elif face in [[dice[0], dice[2]], [dice[2], dice[5]], [dice[5], dice[3]], [dice[3], dice[0]]]:
        print(dice[4])
    elif face in [[dice[0], dice[4]], [dice[4], dice[5]], [dice[5], dice[1]], [dice[1], dice[0]]]:
        print(dice[3])
    elif face in [[dice[0], dice[3]], [dice[3], dice[5]], [dice[5], dice[2]], [dice[2], dice[0]]]:
        print(dice[1])
    elif face in [[dice[1], dice[2]], [dice[2], dice[4]], [dice[4], dice[3]], [dice[3], dice[1]]]:
        print(dice[0])
    elif face in [[dice[1], dice[3]], [dice[3], dice[4]], [dice[4], dice[2]], [dice[2], dice[1]]]:
        print(dice[5])



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

int p[30];
string s;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 	
	memset(p, -1, sizeof(p));
	cin >> s;

	for (int i = 0; i < s.size(); i++) {
		if (p[s[i] - 'a'] != -1) {
			int len = i - p[s[i] - 'a'] + 1;
			if (2 * 2 > len) {
				cout << p[s[i] - 'a']+1 << " " << i+1 << '\n';
				return 0;
			}
		}
		p[s[i] - 'a'] = i;
	}
	cout << "-1 -1\n";

	return 0;
}

Measured memory_bytes: 512
# coding: utf-8
# Your code here!
mod=10**9+7

N=int(input())

a,b,c=1,1,1

for _ in range(N):
    a*=10
    a%=mod
    b*=9
    b%=mod
    c*=8
    c%=mod

print((a-2*b+c)%mod)


Measured memory_bytes: 9164
n=int(input())
D={}
for i in range(1,n+1):
    s=(str(i)[0],str(i)[-1])
    if s in D:
        D[s]+=1
    else:
        D[s]=1
ans=0
for i in D:
    t=(i[1],i[0])
    if t in D:
        ans+=D[t]*D[i]
print(ans)


Measured memory_bytes: 40428
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * https://atcoder.jp/contests/abc170/submissions/14453474 を参考に作成
 */
public class Main {

	/** 計算するための最大値 */
	private static final int INF = Integer.MAX_VALUE >> 1;
	/** X,Y座標の差分一覧 */
	private static final int[] DXS = { 1, -1, 0, 0 };
	private static final int[] DYS = { 0, 0, 1, -1 };
	/** 通過可能の文字 */
	private static final char OK = '.';

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int h = scanner.nextInt(), w = scanner.nextInt(), k = scanner.nextInt();
			int x1 = scanner.nextInt() - 1, y1 = scanner.nextInt() - 1;
			int x2 = scanner.nextInt() - 1, y2 = scanner.nextInt() - 1;
			boolean[][] c = new boolean[h][w];
			IntStream.range(0, h).forEach(i -> {
				char[] ci = scanner.next().toCharArray();
				IntStream.range(0, w).forEach(j -> c[i][j] = (ci[j] == OK));
			});
			int[][] dist = new int[h][w];
			IntStream.range(0, h).forEach(i -> Arrays.fill(dist[i], INF));
			boolean[][] visited = new boolean[h][w];
			IntStream.range(0, h).forEach(i -> Arrays.fill(visited[i], false));
			int steps = -1;
			Queue<Data> queue = new ArrayDeque<>();
			queue.add(new Data(x1, y1, 0));
			dist[x1][y1] = 0;
			visited[x1][y1] = true;
			while (!queue.isEmpty()) {
				Data data = queue.poll();
				if ((x2 == data.x) && (y2 == data.y)) {
					steps = data.depth;
					break;
				}
				IntStream.range(0, DXS.length).forEach(i -> {
					for (int j = 1; j <= k; j++) {
						int nX = data.x + DXS[i] * j;
						int nY = data.y + DYS[i] * j;
						int nDepth = data.depth + 1;

						if (!((nX >= 0) && (nX < h) && (nY >= 0) && (nY < w))) {
							break;
						}
						if ((!c[nX][nY]) || (dist[nX][nY] < nDepth)) {
							break;
						}
						if (!visited[nX][nY]) {
							queue.add(new Data(nX, nY, nDepth));
							dist[nX][nY] = nDepth;
							visited[nX][nY] = true;
						}
					}
				});
			}
			System.out.println(steps);
		}
	}

	/**
	 * x,yと深さを格納するクラス
	 */
	private static class Data {
		int x;
		int y;
		int depth;

		public Data(int x, int y, int depth) {
			super();
			this.x = x;
			this.y = y;
			this.depth = depth;
		}
	}
}


Measured memory_bytes: 60988
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int ll
#define pb push_back
#define setbits(x)          __builtin_popcountll(x)
#define endl "\n"
typedef long long ll;
int ans;
/*int dp[80][3000][40];
int find(int arr[],int n,int pos,int have,int c)
{
    if(pos==n)
    {///ans=max(ans,c);
        return 0;
    }
    if(dp[pos][c][have]!=-1)
       {
           return dp[pos][c][have];
       }
    int res=0;
    for(int i=0;i<=have;i++)
    {
        int a=find(arr,n,pos+1,have-i,c+i*arr[pos])+i*arr[pos];
        res=max(a,res);
    }
    for(int i=0;i<=c/arr[pos];i++)
    {
        int b=find(arr,n,pos+1,have+i,c-i*arr[pos])-i*arr[pos];
        res=max(b,res);
    }
    dp[pos][c][have]=res;
    return res;
}
*/
void solve()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
      /*  for(int i=0;i<n;i++)
        {
            for(int j=0;j<3000;j++)
            {
                for(int k=0;k<40;k++)
                    dp[i][j][k]=-1;
            }
        }
      ans=find(arr,n,0,0,1000);
      */
      int ans=1000;
      for(int i=1;i<n;i++)
      {
          if(arr[i]>arr[i-1])
          {
              int x=ans/arr[i-1];
              ans+=arr[i]*x;
              ans-=arr[i-1]*x;
          }
      }
    cout<<ans<<endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
















    return 0;
}


Measured memory_bytes: 3628
from collections import deque
N = int(input())
G = {i:[] for i in range(1,N+1)}
E = {}
A = []
for _ in range(N-1):
    a,b = map(int,input().split())
    A.append((a,b))
    G[a].append(b)
    G[b].append(a)
    E[(a,b)] = 0
hist = [0 for _ in range(N+1)]
heap = deque([1])
c = 1
for y in G[1]:
    E[(1,y)]=c
    c += 1
K = c-1
hist[1]=1
while heap:
    x = heap.popleft()
    for y in G[x]:
        if hist[y]==0:
            K = max(K,len(G[y]))
            col = [0 for _ in range(min(K,len(G[y]))+1)]
            for z in G[y]:
                if y<z and E[(y,z)]<len(col):
                    col[E[(y,z)]]=1
                elif z<y and E[(z,y)]<len(col):
                    col[E[(z,y)]]=1
            cur = 1
            for z in G[y]:
                if y<z and E[(y,z)]==0:
                    for i in range(cur,K+1):
                        if col[i]==0:
                            E[(y,z)]=i
                            cur = i+1
                            break
                elif z<y and E[(z,y)]==0:
                    for i in range(cur,K+1):
                        if col[i]==0:
                            E[(z,y)]=i
                            cur = i+1
                            break
            heap.append(y)
            hist[y]=1
print(K)
for e in A:
    print(E[e])

Measured memory_bytes: 101860
#include <stdio.h>
int main(){
	int k,cnt,a;
	scanf("%d",&k);
	if(k%2==0||k%10==5){printf("-1\n");return 0;}
	a=7,cnt=1;
	while(1){
		if(a%k==0)break;
		a%=k,a=a*10+7,cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}

Measured memory_bytes: 1732
#include "bits/stdc++.h"
#define rep(i,n) for(ll i = 0; i < n; i++)
typedef long long ll;
using namespace std;
#define llMAX numeric_limits<long long>::max()
#define intMAX numeric_limits<int>::max()
#define d_5 100000
#define d9_7 1000000007
#define vll vector<vector<long long>>
#define vl vector<long long>
#define vi vector<int>
#define vii vector<vector<int>>
#define pb push_back
#define pf push_front
#define ld long double
#define ll long long
int main(void){
  ll n;
  cin>>n;
  vl a(n);
  rep(i,n){
    cin>>a[i];
  }
  vll dp=vll(3,vl(n,0));
  dp[0][0]=1;
  vl dp2(n,1);//結び目の個数
  dp2[0]=3;
  ll ans=1;
  if(a[0]!=0){
    cout<<0;
    return 0;
  }
  
  for(ll i=1;i<n;i++){
    ll num=a[i];
    ll cross=0;
    if(dp[0][i-1]==num)cross+=1;;
    if(dp[1][i-1]==num)cross+=1;;
    if(dp[2][i-1]==num)cross+=1;;
    dp2[i]=cross;
    if(cross==0){
      cout<<0<<endl;
      return 0;
    }
    rep(j,3){
      dp[j][i]=dp[j][i-1];
    }
    rep(k,3){
      if(dp[k][i-1]==num){
        dp[k][i]=num+1;
        break;
      }
    }
  }
  rep(i,n){
    ans*=dp2[i];
    ans%=d9_7;
  }
  cout<<ans%d9_7<<endl;
  return 0;
}

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

int main(){
string S;   cin >> S;
vector<int> count(26);
for (int i = 0; i < 26; i++) {
    count[i] = 0;
}
for (int i = 0; i < S.size(); i++) {
    count[S[i] - 'a']++;
    if (count[S[i] - 'a'] == 2) {
        cout << "no" << endl;
        return 0;
    }
}

cout << "yes" << endl;

}

Measured memory_bytes: 256
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    char[] in = sc.next().toCharArray();
    if(in[2] == in[3] && in [4] == in[5]){
      System.out.println("Yes");

    }else{
      System.out.println("No");
    }
  }
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define GET_ARRAY_SIZE(a)   (sizeof(a)/sizeof(a[0]))
#define LL long long
int main(){
    LL n,k,if_ans1 = 0,if_ans2 = 0,for_num = 0,ans = 0;
    cin >> n >> k;
//    cout << n << " " << k << endl;
    if(0 == n%k){
        cout << 0 << endl;
        return 0;
    }
    if_ans1 = n%k;
    if_ans2 = abs(if_ans1 - k);
    if(if_ans1 < if_ans2) ans = if_ans1;
    else ans = if_ans2;
    cout << ans << endl;


/*
    for_num = n/k;
    if(1 <= n%k) for_num = for_num + 1;
    if(0 == n%k){
        cout << 0 << endl;
        return 0;
    }
//    cout << "for_num :" << for_num << endl;
    ans = n;
    for(int i = 0; i < for_num; i++) {
        ans = ans - k;
        ans = abs(ans);
//        cout << "ans :" << ans << endl;
    }
    cout << ans << endl;
/*
    if_ans1 = n;
    if_ans2 = n - k;
    while (if_ans1 >= if_ans2){
//        abs(数値)
        if_ans1 = if_ans2;
        if_ans2 = if_ans2 - k;
        if_ans2 = abs(if_ans2);

        cout << "if_ans1 :" << if_ans1 << endl;
        cout << "if_ans2 :" <<if_ans2 << endl;
        cout << endl;

    }
    cout << if_ans1 << endl;
*/
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
  
#define MIN 1
#define MAX 10000
#define IS_ERR(n) (n < MIN || n > MAX)
  
int main(void)
{
    int a, b, c, i, ans=0;
  
    scanf("%d %d %d", &a, &b, &c);
  
    if(IS_ERR(a) || IS_ERR(b) || IS_ERR(c) || a > b)
    {
        return -1;
    }
  
    for(i=a;i<=b;i++)
    {
        if(c % i == 0)
        {
             ans++;
        }
    }
  
    printf("%d\n", ans);
  
    return 0;
}


Measured memory_bytes: 2124
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int s = sc.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
		    arr[i] = sc.nextInt();
		}
		int right = 0;
		int sum = arr[0];
		int min = Integer.MAX_VALUE;
		for(int left = 0; left < n; left++) {
		    while(right < n && sum < s) {
		        right++;
		        if (right >= n) {
		            break;
		        }
		        sum += arr[right];
		    }
		    if (right >= n) {
		        break;
		    }
		    min = Math.min(min, right - left + 1);
		    sum -= arr[left];
		}
		if (min == Integer.MAX_VALUE) {
		    System.out.println(0);
		} else {
		    System.out.println(min);
		}
	}
}



Measured memory_bytes: 71008
#include <bits/stdc++.h>
 #define rep(i,a,b) for (int i=a;i<b;i++)
 #define rep2(i,a,b) for (int i=a;i>=b;i--)
 #define mod 1000000007
 #define INF  1e9+5
 #define f first
 #define se second
 #define endl '\n'
 #define ll long long
 #define ii pair <int,int>
 #define pll pair <ll,ll>
 #define vi vector <int>
 #define vl vector <ll>
 #define vvi vector < vi >
 #define vii vector < ii >
 #define vvii vector < vii >
 #define vll vector < ll >
 #define mi map<int,int>
 #define mll map<ll,ll>
 #define mci map<char,int>
 #define msi map<string,int>
 #define vb  vector <bool>
 #define pb push_back
 #define mk make_pair
 #define sz(a) a.size()
 #define all(a) a.begin(),a.end()
 #define rall(a) a.rbegin(),a.rend()
 #define int long long int
 #define Anurag_Gupta ios_base::sync_with_stdio(false);
#define IIIT_ALLD    cin.tie(NULL);cout.tie(NULL);
using namespace std;
vi fact(1000007);
inline int mdpower(int a,int b)
{
    int res =1;
    while(b)
    {
        if(b&1) res = (res%mod*a%mod)%mod;
        b/=2;
        a = (a%mod*a%mod)%mod;
    }
    return res;
}
inline int power(int a,int b)
{
    int res =1;
    while(b)
    {
        if(b&1) res = (res*a);
        b/=2;
        a = a*a;
    }
    return res;
}

inline void factorial()
{
    fact[0]=1;
    for(int i=1;i<1000007;i++)
        fact[i] = (fact[i-1]%mod*i%mod)%mod;
}

inline int inverse(int a)
{
    return mdpower(a,mod-2);
}
int n;
vector<double>v;
double dp[3000][3000];
double solve(int idx,int hd,int ta)
{
	
	if(dp[hd][ta]!=1.0) return dp[hd][ta];
	if(ta==0 and idx==1) return dp[hd][ta]=v[idx-1];
	if(hd==0 and idx==1) return dp[hd][ta]=(1-v[idx-1]);
	if(hd==0)
		return dp[hd][ta]=(1-v[idx-1])*solve(idx-1,hd,ta-1);
	if(ta==0)
		return dp[hd][ta]=v[idx-1]*solve(idx-1,hd-1,ta);

	return dp[hd][ta]=v[idx-1]*solve(idx-1,hd-1,ta)+(1-v[idx-1])*solve(idx-1,hd,ta-1);

}
 signed main()
 {
     Anurag_Gupta
     IIIT_ALLD
     
   
         cin>>n;
        for(int i=0;i<3000;i++)
        	for(int j=0;j<3000;j++)dp[i][j]=1.0;
         for(int i=0;i<n;i++)
         {
         	double x;
         	cin>>x;
         	v.pb(x);
         }
         double ans=0;
         for(int i=0;i<=n;i++){

         	double x = solve(n,i,n-i);
         	if(i>n-i)
         		ans+=x;
         }
         printf("%.9lf",ans);


 }


Measured memory_bytes: 78720
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>

using namespace std;
const int INF = 1<<30;
typedef long long int ll;

int main(){
	ll a, b, c;cin>>a>>b>>c;
	if((a%2)*(b%2)*(c%2)==0){cout << 0 << endl;return 0;}
	if(a>b)swap(a, b);
	if(b>c)swap(b, c);
	cout << a*b << endl;
}


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

using namespace std;

struct Item
{
  uint64_t id, x, pref, year;
  
  Item(uint64_t id = 0, uint64_t pref = 0, uint64_t year = 0) 
    : id(id), pref(pref), year(year), x(0) {}
  
  string to_string() const {
    stringstream ss;
    ss << setw(6) << setfill('0') << pref;
    ss << setw(6) << setfill('0') << x;
    return ss.str();
  }
  
  bool operator<(const Item &item) const {
    return year < item.year;
  }
};

int main()
{
  uint64_t N, M;
  cin >> N >> M;
  
  vector< vector<Item> > items(N);
  for (uint64_t m = 0; m < M; ++m) {
    uint64_t P, Y;
    cin >> P >> Y;
    
    items[P - 1].emplace_back(m, P, Y);
  }
  
  for (uint64_t n = 0; n < N; ++n) {
    sort(items[n].begin(), items[n].end());
    
    for (uint64_t x = 0; x < items[n].size(); ++x) {
      items[n][x].x = x + 1;
    }
  }
  
  vector<string> postal_codes(M);
  for (uint64_t n = 0; n < N; ++n) {
    for (uint64_t x = 0; x < items[n].size(); ++x) {
      postal_codes[ items[n][x].id ] = items[n][x].to_string();
    }
  }
  
  for (uint64_t m = 0; m < M; ++m) {
    cout << postal_codes[m] << endl;
  }
  
  return 0;
}

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


const int maxn = 1000010;
#define ll long long
int a[maxn];
int n;
ll ans = 0ll;
int main()
{
	cin >> n;
	for (int i = 1; i <= n;i++)
	{
		cin >> a[i];
	}
	ll sum = 0ll;
	ll xo = 0;
	int l = 1;
	int r = 0;
	ll cnt = 0;
	while (1)
	{
		while (r < n && sum + a[r + 1] == (xo ^ a[r + 1]))
		{
			r++;
			sum += a[r];
			xo ^= a[r];
		}
		cnt = r - l + 1;
		ans += cnt;
		sum -= a[l];
		xo ^= a[l++];
		if (l == n + 1)
		{
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

int main() {
  int flag=0;
  ll sum;
  string input="";
  char target;

  cin >> input;

  sort(input.begin(), input.end());

  target = input.at(0);
  sum = 0;

  for (int i=0; i<input.size(); i++)
  {
    sum++;
    if(i+1==input.size() || input.at(i+1) != target)
    {
      if(sum%2 != 0) flag=1;
      if(i+1!=input.size()) target = input.at(i+1);
      sum=0;
    }
  }

  switch (flag)
  {
  case 0:
    cout << "Yes" << endl;
    break;
  case 1:
    cout << "No" << endl;
    break;
  }

}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 1000000000
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


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

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  int N, C, D[33][33], c[1111][1111], M[3][33];

  std::cin >> N >> C;

  for (int i = 0; i < C; i ++)
    for (int j = 0; j < C; j ++)
      std::cin >> D[i][j];

  for (int i = 0; i < N; i ++)
    for (int j = 0; j < N; j ++)
      std::cin >> c[i][j];

  memset(M, 0, sizeof(M));
  
  for (int i = 0; i < N + N - 1; i ++) {
    int y = i, x = 0;

    for ( ; y >= N; y --, x ++)
      ;

    for (int j = 0; j < C; j ++) {
      int s = 0;
      
      for (int yy = y, xx = x; yy >= 0 && xx < N; yy --, xx ++)
        s += D[c[yy][xx] - 1][j];

      M[i % 3][j] += s;
    }
  }

  int Sm = INF;

  for (int i = 0; i < C; i ++)
    for (int j = 0; j < C; j ++)
      for (int k = 0; k < C; k ++)
        if (i != j && j != k && k != i)
          Sm = std::min(M[0][i] + M[1][j] + M[2][k], Sm);

  std::cout << Sm << std::endl;
  
  return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;

int main() {
	ll n, a,pos=0,index=0;
	ll k;
	cin >> n >> k;
	set<int>cycle;
	vector<int>city;
	vi tere;
	rep(i, n) {
		cin >> a;
		city.push_back(--a);
	}
	pos = 0;
	for (int s:city) {
		cycle.insert(pos);
		tere.push_back(pos);
		pos = city[pos];
		if (cycle.count(pos))break;
	}
	for (int s : tere) {
		if (s == pos) break;
		else index++;
	}
	if (k <= index) {
		cout << tere[k] + 1 << endl;
	}
	else {
		k -= index;
		cout << tere[index + (k % (tere.size() - index))] + 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 14008
import sys
sys.setrecursionlimit(10**8)

N = int(input())

vertex = [{} for _ in range(N)]

for i in range(N-1):
    a,b,c = map(int,input().split())
    vertex[a-1][b-1] = c
    vertex[b-1][a-1] = c

Q,K = map(int,input().split())

d = [0 for i in range(N)]

def dfs(v1,v2):
    d[v2] = d[v1] + vertex[v1][v2]
    for v in vertex[v2]:
        if v == v1:
            continue
        dfs(v2,v)

for v in vertex[K-1].keys():
    dfs(K-1,v)

for q in range(Q):
    x,y = map(int,input().split())
    print(d[x-1] + d[y-1])


Measured memory_bytes: 162592
import java.util.*;
    public class Main {
     
    	public static void main(String[] args) {
    			
    		Scanner scan =new Scanner(System.in);
    		
    		int a=Integer.parseInt(scan.next());
    		int b=Integer.parseInt(scan.next());
    		if (a%2!=0&&b%2!=0) {
    			System.out.print("Yes");
    		}else {
    			System.out.print("No");
    		}
   
     
    }
    }
// end 

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

#define pb push_back
#define ll long long
#define maxn 200005
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define ms1(i) memset(i,-1,sizeof(i));
#define F first
#define S second
const int mod = 1e9+7;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int cur = 1;
    f(n){
        int add;
        cin >> add;
        if(add == cur){
            cur++;
        }
    }
    if(cur == 1){
        cout << -1 << '\n';
    }
    else{
        cout << n - cur + 1 << '\n';
    }
}

Measured memory_bytes: 256
#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(){
	string s;
	cin >> s;
	bool f = true;
	if(s.size() >= 4){
		if(s.at(0) != 'Y') f = false;
		if(s.at(1) != 'A') f = false;
		if(s.at(2) != 'K') f = false;
		if(s.at(3) != 'I') f = false;
	}else{
		f = false;
	}
	if(f == true){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int N,S;
int dp[(1<<10)][331];
int solve(int st,int s,int no){
  if(s>S) return 0;
  if(no==N+1){
    if(s==S) return 1;
    return 0;
  }
  if(dp[st][s]!=-1) return dp[st][s];
  int ret=0;
  for(int i=0;i<10;i++){
    if(!(st & (1<<i))){
      ret+=solve(st | (1<<i),s+no*i,no+1);  
    }
  }
  return dp[st][s]=ret;
}
int main(){
  while(~scanf("%d %d",&N,&S)){
    memset(dp,-1,sizeof(dp));
    printf("%d\n",solve(0,0,1));
  }
}

Measured memory_bytes: 2520
#include <bits/stdc++.h>
using namespace std;
int main() {
  vector<int> vct;
  vct.push_back(0);
  vct.push_back(0);
  vct.push_back(0);
  string s;
  cin >> s;
  bool flag=false;
  int ans = 0;
  int cnt = 0;
  for (int i = 0; i < 3; ++i) {
    if (s[i] == 'R') {
      ++cnt;
      flag=true;
    } else {
      cnt = 0;
      flag=false;
    }
    ans = max(ans, cnt);
  }

  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N=2e5+9;
const int mod=1e9+7;

ll add(ll a, ll b){
    return ((a%mod)+(b%mod))%mod;
}
ll mul(ll a, ll b){
    return ((a%mod)*(b%mod))%mod;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  /*/  ll n,x,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        ll con=(n-i);
        if(i==n)con=n-1;
        ans=add(ans,mul(con,x));
    }
    cout<<ans;*/

    double d,t,s;
    cin>>d>>t>>s;
    double ned=d/s;
    if(ned<=t)cout<<"Yes";
    else cout<<"No";

  


    


    

}

Measured memory_bytes: 3736
import java.util.*;
/**
 * @author afterCmidday
 *
 */
class Main {
 
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO 自動生成されたメソッド・スタブ
        final double eps = 1e-10;
        int n;
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 0;i < n;i++){
            double x1 = scan.nextDouble(), y1 = scan.nextDouble(), x2 = scan.nextDouble(), y2 = scan.nextDouble();
            double a = x2 - x1, b = y2 - y1;
            double x3 = scan.nextDouble(), y3 = scan.nextDouble(), x4 = scan.nextDouble(), y4 = scan.nextDouble();
            double c = x4 - x3, d = y4 - y3;
            double e = a * d - b * c;
            if(Math.abs(e) < eps){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
        }
 
    }
 
}


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

int main(){
    int n,k;
    cin>>n>>k;
    vector<int>a(n);
    rep(i,n)cin>>a[i];
    int x=min(n,k),mx=0;
    for(int i=0; i<=x; ++i){
        for(int j=0; j<=x-i; ++j){
            int sum=0;
            vector<int>ans;
            rep(l,i){
                ans.push_back(a[l]);
            }
            for(int l=n-1; l>n-1-j; --l){
                ans.push_back(a[l]);
            }
            sort(ans.begin(),ans.end());
            int y=k-i-j;
            rep(l,y){
                if(l>=ans.size())break;
                if(ans[l]<0)ans[l]=0;
            }
            rep(l,ans.size())sum+=ans[l];
            mx=max(mx,sum);
        }
    }
    cout<<mx<<endl;
}


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

using namespace std;

struct Edge {
	int to, cap, rev;
};

vector< vector<Edge> > G;
vector<bool> used;
int dfs(int s, int t, int f) {
	if (s == t) return f;
	used[s] = true;

	for (int i = 0; i < G[s].size(); ++i) {
		Edge& e = G[s][i];
		if (!used[e.to] && e.cap > 0) {
			int d = dfs(e.to, t, min(e.cap, f));
			if (d > 0) {
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s, int t) {
	int res = 0;
	while (1) {
		int N = G.size();
		used = vector<bool>(G.size(), false);
		int flow = dfs(s, t, 1e9);
		if (flow > 0) {
			res += flow;
		}
		else {
			break;
		}
	}
	return res;
}
void add_edge(int u, int v, int cap) {
	G[u].push_back((Edge){v, cap, (int)G[v].size()});
	G[v].push_back((Edge){u, cap, (int)G[u].size()-1});
}

typedef pair<int, int> P;

int main() {
	int N, M; cin >> N >> M;
	G.resize(N);
	vector<P> edges;
	map<P, int> tbl;
	for (int i = 0; i < M; ++i) {
		int a, b; cin >> a >> b; --a, --b;
		edges.push_back( P(a, b) );
		tbl[edges[i]] = i;
	}
	for (int i = 0; i < M; ++i) {
		int u = edges[i].first, v = edges[i].second;
		add_edge(u, v, 1);
	}
	int S, T; cin >> S >> T; --S, --T;
	cout << max_flow(S, T) << endl;

	vector<int> ans;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < G[i].size(); ++j) {
			Edge& e = G[i][j];
			if (e.cap == 0) {
				if (tbl.find(P(e.to, i)) != tbl.end()) {
					ans.push_back(tbl[P(e.to, i)]+1);
				}
			}
		}
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); ++i) {
		cout << ans[i] << endl;
	}
}

Measured memory_bytes: 3304
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	if (a >= 13) printf("%d\n", b);
	else if (a >= 6 && a <= 12) printf("%d\n", b / 2);
	else printf("0\n");
	return 0;
}

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

struct die{
  int t[6];
  void ra(){
    int tmp=t[0];
    t[0]=t[2];
    t[2]=t[5];
    t[5]=t[3];
    t[3]=tmp;
  }
  void rb(){
    int tmp=t[1];
    t[1]=t[2];
    t[2]=t[4];
    t[4]=t[3];
    t[3]=tmp;
  }
  void rc(){
    int tmp=t[0];
    t[0]=t[4];
    t[4]=t[5];
    t[5]=t[1];
    t[1]=tmp;
  }
};

vector<die> calc(die d){
  vector<die> res;
  for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
      res.push_back(d);
      d.rc();
    }
    d.ra();
  }
  d.rb();
  for(int i=0;i<4;i++){
    res.push_back(d);
    d.rc();
  }
  d.rb();d.rb();
  for(int i=0;i<4;i++){
    res.push_back(d);
    d.rc();
  }
  return res;
}

int n,cnt,ans;
die A[4];
map<string,int> mp;
vector<die> B[4];

void check(){
  int cnt=0;
  for(int i=0;i<6;i++){
    int maxm=0;
    map<int,int> mp;
    for(int j=0;j<n;j++){
      int num=A[j].t[i];
      mp[num]++;
      maxm=max(maxm,mp[num]);
    }
    cnt+=(n-maxm);
  }
  ans=min(ans,cnt);
}

void solve(int x){
  if(x==n){
    check(); 
  }else{
    for(int i=0;i<24;i++){
      A[x]=B[x][i];
      solve(x+1);
    }
  }
}

int main(){
  while(1){
    cin>>n;
    if(n==0)break;
    cnt=0;
    mp.clear();
    string str;
    for(int i=0;i<n;i++){
      for(int j=0;j<6;j++){
	cin>>str;
	if(mp[str]==0){
	  cnt++;
	  mp[str]=cnt;
	}
	A[i].t[j]=mp[str];
      }
      B[i]=calc(A[i]);
    }
    
    ans=(1<<24);
    solve(0);
    cout<<ans<<endl;
  }
  return 0;
}

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

class Program
{
    static void Main(string[] args)
    {
        var hwk = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var h = hwk[0];
        var w = hwk[1];
        var k = hwk[2];

        // 黒をTrue
        var board = new bool[h][].Select(t => t = new bool[w]).ToArray();

        for (int i = 0; i < h; i++)
        {
            var line = Console.ReadLine();
            for(int j = 0; j < w; j++)
            {
                if (line[j] == '#') board[i][j] = true;
            }
        }

        long ans = 0;

        // bit全探索
        foreach(var item in BitFullSearch(h + w))
        {
            var tate = item.Take(h).ToArray();
            var yoko = item.Skip(h).ToArray();
            bool[][] newBorad = new bool[h][].Select(t => t = new bool[w]).ToArray();

            for(int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++) newBorad[i][j] = board[i][j];
            }

            for (int i = 0; i < tate.Length; i++)
            {
                if(tate[i])
                    for (int j = 0; j < w; j++) newBorad[i][j] = false;
            }
            for (int i = 0; i < yoko.Length; i++)
            {
                if(yoko[i])
                    for (int j = 0; j < h; j++) newBorad[j][i] = false;
            }

            if (newBorad.Sum(aa => aa.Count(bb => bb)) == k) ans++;
        }

        Console.WriteLine(ans);
    }

    public static IEnumerable<bool[]> BitFullSearch(int n)
    {
        if (n <= 0)
        {
            yield return new bool[] { };
            yield break;
        }

        for (int i = 0; i < Math.Pow(2, n); i++)
        {
            var array = new bool[n];
            for (int j = 0; j < n; j++)
            {
                var targetBit = (i >> j) & 1;
                if (targetBit == 1) array[j] = true;
            }

            yield return array;
        }
    }
}

Measured memory_bytes: 31996