akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<utility>
#include<queue>
#include<functional>
#include<cstring>
#include<vector>
#include<climits>
#include<map>
using namespace std;
#define FOR(i,n) for(int i=0;i<(int)n;i++)
#define FORI(i,k,n) for(int i=k;i<(int)n;i++)
typedef pair<int,int> pii;


int main()
{
	while(1)
	{
		int n;
		map<string,int> a;
		
		cin>>n;if(!n)break;
		FOR(i,n)
		{
			string s;int v;
			cin>>s>>v;
			a[s]=v;
		}
		
		int m;
		cin>>m;
		vector<string> r[100];
		FOR(i,m)
		{
			string o;cin>>o;
			int k;cin>>k;
			r[i].push_back(o);
			FOR(j,k)
			{
				string x;cin>>x;
				r[i].push_back(x);
			}
		}
		
		bool ok=true;
		while(ok)
		{
			ok=false;
			FOR(i,m)
			{
				int v=0;
				FORI(j,1,r[i].size())
				{
					v+=a[r[i][j]];
				}
				if(v<a[r[i][0]])
				{
					a[r[i][0]]=v;
					ok=true;
				}
			}
		}
		string f;cin>>f;
		cout<<a[f]<<endl;
		
	}
}

Measured memory_bytes: 3196
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;

class Prog
{
    public Prog() { }
    public static int Main()
    {
        new Prog().calc();
        return 0;
    }

    Scanner cin;

    public void calc()
    {
        cin = new Scanner();
        int N = cin.nextInt();
        int K = cin.nextInt();

        int[] D = new int[K];
        for (int i = 0; i < K; i++)
        {
            D[i] = cin.nextInt();
        }

        for (int n = N; n < 10 * N; n++)
        {
            if (ok(n, D))
            {
                Console.WriteLine(n);
                return;
            }
        }
    }

    bool ok(int n, int[] D)
    {
        string strn = n.ToString();
        for (int i = 0; i < strn.Length; i++)
        {
            int t = int.Parse(strn[i].ToString());
            for (int j = 0; j < D.Length; j++)
            {
                if (t == D[j]) return false;
            }
        }
        return true;
    }
}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

Measured memory_bytes: 6744
N,M=map(int,input().split())
A=[]
B=[]
for i in range(N):
    A.append(input())
for j in range(M):
    B.append(input())
t=0
while t==0:
    for i in range(N-M+1):
        for j in range(len(A[0])-len(B[0])+1):
            m=0
            for h in range(M):
                for k in range(len(B[0])):
                    if B[h][k]==A[h+i][k+j]:
                        m+=1
            if m==M*len(B[0]):
                print('Yes')
                t=1
                break
        if t==1:
            break
    else:
        print('No')
        break


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <math.h>
#include <vector>
#include <queue>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep_1 (i,j,n) for(int i=j;i<n;i++)
typedef long long ll;
typedef long l;
const ll l_INF = 101010101000;
const int INF = 1010101010;
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using pii = pair<int,int>;

int main(){
  int n;
  string s;
  cin>>n;
  int m=n%1000;
  if(m!=0)cout<<1000-m;
  else cout<<0;
}


Measured memory_bytes: 3596
var
	n,m,i,a,b,ans:Longint;
	used:array[1..8]of Boolean;
	c:array[1..8]of Longint;
	G:array[1..8,1..8]of Longint;
procedure f(u,cnt:Longint);
var i:Longint;
begin
	if cnt=n then begin
		inc(ans);
		exit;
	end;
	for i:=1 to c[u] do begin
		if not used[G[u,i]]then begin
			used[G[u,i]]:=True;
			f(G[u,i],cnt+1);
			used[G[u,i]]:=False;
		end;
	end;
end;
begin
	read(n,m);
	ans:=0;
	for i:=1 to m do begin
		read(a,b);
		inc(c[a]);
		inc(c[b]);
		G[a,c[a]]:=b;
		G[b,c[b]]:=a;
	end;
	used[1]:=True;
	f(1,1);
	writeln(ans);
end.

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int n,m,p[1<<17],i,x,y,z,t;
int f(int x){
	if(p[x]==x)return x;
	return p[x]=f(p[x]);
}
int main(){
	cin>>n>>m;
	t=m;
	for(i=1;i<=n;i++)p[i]=i;
	for(i=1;i<=m;i++){
		cin>>x>>y>>z;
		if(f(x)==f(y))t--;
		else p[f(x)]=f(y);
	}
	cout<<n-t;
	return 0;
}


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

def main():
    S = input().strip()
    if S == "Sunny":
        print( "Cloudy" )
    elif S == "Cloudy":
        print( "Rainy" )
    elif S == "Rainy":
        print( "Sunny" )


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, m;
  cin >> n >> m;
  vector<int> k(m), p(m);
  vector<vector<int>> s(m, vector<int>(0));
  for (int i = 0; i < m; i++) {
    cin >> k[i];
    for (int j = 0; j < k[i]; j++) {
      int f;
      cin >> f;
      s[i].push_back(f);
    }
  }
  for (int i = 0; i < m; i++) cin >> p[i];
  
  int cnt, ans = 0;
  vector<int> swit(11, 0);
  for (swit[1] = 0; swit[1] <= 1; swit[1]++) {
  for (swit[2] = 0; swit[2] <= 1; swit[2]++) {
  for (swit[3] = 0; swit[3] <= 1; swit[3]++) {
  for (swit[4] = 0; swit[4] <= 1; swit[4]++) {
  for (swit[5] = 0; swit[5] <= 1; swit[5]++) {
  for (swit[6] = 0; swit[6] <= 1; swit[6]++) {
  for (swit[7] = 0; swit[7] <= 1; swit[7]++) {
  for (swit[8] = 0; swit[8] <= 1; swit[8]++) {
  for (swit[9] = 0; swit[9] <= 1; swit[9]++) {
  for (swit[10] = 0; swit[10] <= 1; swit[10]++) {
    int judge = 0;
    for (int i = n + 1; i <= 10; i++) {
      if (swit[i] != 0) {
        judge = 1;
        break;
      }
    }
    if (judge == 1) continue;
    cnt = 0;
    for (int i = 0; i < m; i++) {
      int sum = 0;
      for (int j = 0; j < k[i]; j++) sum += swit[s[i][j]];
      if (sum % 2 == p[i]) cnt++;
    }
    if (cnt == m) ans++;
  }}}}}}}}}}
  
  cout << ans << endl;
}

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

int main()
{


        int N;
        string S;
        cin >> N;
        cin >> S;

        int len = S.length();
        for (int i = 0; i < len; ++i) {

                char c;
                c = S[i] + N;
                if (c >= ('A'+26)) {
                        c = c - 26;
                }
                cout << c;
        }
        cout << endl;








}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int compare_int(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}

int main(void){
    int N,K,*A,*Same,i,j=0,tmp,same=1,kind=1,sum=0;
    scanf("%d %d",&N,&K);
    A = (int*)malloc(sizeof(int)*N);
    Same = (int*)malloc(sizeof(int)*N);
    for(i=0;i<N;i++){
        scanf("%d",&A[i]);
        Same[i] = 0;
    }
    qsort(A,N,sizeof(int),compare_int);
    tmp = A[0];
    for(i=1;i<N;i++){
        if(tmp!=A[i]){
            //printf("i=%d:%d\n",i,A[i]);
            kind++;
            tmp = A[i];
            Same[j] = same;
            same = 1;
            j++;
        }else{
            same++;
        }
        if(i==N-1){
            Same[j] = same;
        }
    }
    for(i=0;i<kind;i++){
        //printf("Same[%d]:%d\n",i,Same[i]);
    }
    
    if(kind<=K) printf("0\n");
    else{
        //printf("kind:%d\n",kind);
        qsort(Same,kind,sizeof(int),compare_int);
        for(j=1,i=kind-j;j<=K;j++,i=kind-j){
            sum += Same[i];
            //printf("Same_%d:%d\n",i,Same[i]);
        }
        printf("%d\n",N-sum);
    }
    
    return 0;
}

Measured memory_bytes: 2556
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
using namespace std;
typedef double  dbl;
typedef long long int lld;
#define PI 3.14159265358979323
#define foi(i,n) for(i = 0; i < n; i+=1)
#define fod(i,n) for(i=n-1; i >=0; i-=1)
#define MAX std::numeric_limits<lld>::max()
#define MIN std::numeric_limits<lld>::min()
#define FastIO  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main ()
{
	FastIO
	lld n, i;
	cin >> n;
	lld count = 0;
	for(i = 1; i <= n; i++){
		lld x = log10(i);
		x+=1;
		if (x%2 != 0)
			count++;
	}
	cout << count;
	return 0;
}

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

using namespace std;

//#define MOD 1e9+7

int main()
{
    long long int n, fact=1;
    cin >> n;

	for(int i=1;i <= n;i++)
	{
		fact=((fact%1000000007)*(i%1000000007))% 1000000007;

	}
	cout << fact <<endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <climits>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <cmath>
#include <regex>
using namespace std;

int main()
{
long long n,a,b;
cin>>n>>a>>b;
if(n==1&&a==b)
{
    cout<<1;
    return 0;
}
if(n<2||a>b)
{
    cout<<0;
    return 0;
}
cout<<(b-a)*(n-2)+1;

}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int N;
    int max=0;
    int i;
    int sum=0;
    int n;
    scanf("%d", &N);
    for(i=0; i<N; i++){
        scanf("%d", &n);
        if(max<n) max=n;
        sum+=n;
    }
    if(sum>2*max) printf("Yes");
    else printf("No");
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define N_MAX 200000


using namespace std;
long long N;
long long A[N_MAX];
int number[N_MAX];

void solve()
{
    memset(number, 0, sizeof(int)*N);
    for(int i=1;i<N;i++)
    {
        number[A[i]-1]++; 
    }
    for(int i=0;i<N;i++){
        cout << number[i] << endl;
    }
    return;
}

int main()
{
    cin >> N;
    A[0] = 0;
    for(int i=1;i<N;i++){
        cin >> A[i];
    }
    solve();
    
    return 0;
}



Measured memory_bytes: 5940
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AthleteProgramming2
{
    
    class Program
    {
        static long Kai(long n)
        {
            if (n == 1)
            {
                return n;
            }else
            {
                return n * Kai(n - 1);
            }
        }

        static void Main()
        {
            long n = long.Parse(Console.ReadLine());
            Console.WriteLine(Kai(n));
        }
    }
}

Measured memory_bytes: 9032
/*
Author:Jenil Mehta
Not yet serious but trying to be serious :)
Coding is lub
*/
 
#include <iostream>
#include <sstream>
#include <cstdio>
#include <climits>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
typedef long long int ll;
ll power(ll a, ll n) {ll p = 1;while (n > 0) {if(n%2) {p = p * a;} n >>= 1; a *= a;} return p;}
ll power(ll a, ll n, ll mod) {ll p = 1;while (n > 0) {if(n%2) {p = p * a; p %= mod;} n >>= 1; a *= a; a %= mod;} return p % mod;}
using namespace std;
ll a[1002];
ll b[1002];
int dp[3000 + 5][3000 + 5];
 
int main() {
   /*
   Jab Bhi Koi Ladaki Dekhun Meraa Dil Divaanaa Bole
Ole Ole Ole, Ole Ole Ole
Gaao Taraanaa Yaaraa Jhum Jhum Ke Haule Haule
Ole Ole Ole, Ole Ole Ole
Mujhako Lubhaati Hai Javaaniya Masti Lutaati Zidagaani Yahaan
Maane Na Kahanaa Paagal Mast Pavan Saa Dil Ye Dole
Ole Ole Ole, Ole Ole Ole
Ole Ole Ole, Ole Ole Ole
Jab Bhi Koi Ladaki Dekhun Meraa Dil Divaanaa Bole
Ole Ole Ole, Ole Ole Ole
Gaao Taraanaa Yaaraa Jhum Jhum Ke Haule Haule
Ole Ole Ole, Ole Ole Ole
   */
    ll n,m;
    cin>>n>>m;
    ll ans;
    ans=(n-1)*n/2+(m-1)*m/2;
    cout<<ans<<endl;
    
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int a,b,c;
    cin>>a>>b>>c;
    cout<<min(c,b/a)<<endl;
}

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  if(a==b) cout << "Yes" << "\n";
  else cout << "No" << "\n";
  return 0;
}


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

using namespace std;

const int N = 16;
const int INF = 10000000;

int n, data[N][N+1], dp[2][1<<N], cost[N][1<<N];

int solve(){
  fill(dp[0], dp[2], INF);
  for(int i=0;i<n;i++) dp[0][(1<<i)] = cost[i][0];
  for(int k=0;k<n;k++){
    for(int i=0;i<(1<<n);i++){
      if(dp[k%2][i] == INF) continue;
      dp[(k+1)%2][i] = min(dp[(k+1)%2][i], dp[k%2][i]);
      for(int j=0;j<n;j++){
        if(i & (1<<j)) continue;
        dp[(k+1)%2][i|(1<<j)] = min(dp[(k+1)%2][i|(1<<j)], dp[k%2][i] + cost[j][i]);
      }
    }
  }
  return dp[n%2][(1<<n)-1];
}

main(){
  while(cin >> n && n){
    for(int i=0;i<n;i++) for(int j=0;j<=n;j++) cin >> data[i][j];
    for(int k=0;k<(1<<n);k++){
      for(int i=0;i<n;i++){
        cost[i][k] = data[i][0];
        for(int j=0;j<n;j++) if(k & (1<<j)) cost[i][k] = min(cost[i][k], data[i][j+1]);
      }
    }
    cout << solve() << endl;
  }
}

Measured memory_bytes: 5768
#演習2-16
from bisect import bisect_left, bisect_right #二分探索
from collections import Counter 

def how_many(a, x):
    # リストaのなかでxが何個あるのかを返す関数
    return bisect_right(a, x) - bisect_left(a, x)


def solve(n, m):
    # とく関数
    a = [int(input()) for _ in range(n)]
    b = [int(input()) for _ in range(m)]

    sum_a = [0 for i in range(n + 1)]
    sum_b = [0 for i in range(m + 1)]

    # sum_a[i]=縦の始点からの距離
    # sum_b[i]=横の始点からの距離

    for i in range(n):
        sum_a[i + 1] = sum_a[i] + a[i]

    for i in range(m):
        sum_b[i + 1] = sum_b[i] + b[i]

    all_range_h = []

    all_range_w = []

    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            all_range_h.append(sum_a[j] - sum_a[i])

    for i in range(m + 1):
        for j in range(i + 1, m + 1):
            all_range_w.append(sum_b[j] - sum_b[i])

        # all_range_h=縦の長さでの、ありうる長さの組み合わせ
        # all_range_w=横の長さでの、ありうる長さの組み合わせ

    all_range_w.sort()
    # 縦の長さを決めて、（Lとする）そのとり方がX通りあったとする。この時、横の長さがLとなるものが何個あるのかを考える。これを考える際に二部探索するので予め縦の長さの組み合わせをソートしておく。
    # これをYとしたときX*Yがこの時のありうる総数である。

    ans = 0

    data_h = dict(Counter(all_range_h))

    # data_hに（key=ありうる縦の長さの個数、value=その取り方の総数)を持つ辞書を作る。

    for key in data_h.keys():
        ans += data_h[key] * how_many(all_range_w, key)

    return ans


flag = True

while flag:
    n, m = map(int, input().split())
    # 終わりのサイン:(n,m)=(0,0)
    if n == m == 0:
        flag = False
        break
    else:
        print(solve(n, m))


Measured memory_bytes: 77408
#include<stdio.h>
int main()
{
    int a,b,c,d,e,k = 0;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    scanf("%d", &d);
    scanf("%d", &e);
    scanf("%d", &k);
    if((e-a) > k){
        printf(":("); 

    }
    else{
        printf("Yay!");
    }


    return 0;
}

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



int main() {
    int N;
    string s;
    cin >> N >> s;
    int R[N+1],G[N+1],B[N+1];
    R[0]=0; G[0]=0; B[0]=0;
    for(int i=0;i<N;++i) {
        if(s[i]=='R') {
            R[i+1] = R[i]+1;
            G[i+1] = G[i];
            B[i+1] = B[i];
        }
        else if(s[i]=='G'){
            R[i+1] = R[i];
            G[i+1] = G[i]+1;
            B[i+1] = B[i];
        }
        else if(s[i]=='B') {
            R[i+1] = R[i];
            G[i+1] = G[i];
            B[i+1] = B[i]+1;
        }
    }
    ll ans = 0;
    ll c = 0;
    for(int i=1;i<N-1;++i) {
        if(s[i]=='R') {
            for(int j=1;i-j>=0 && i+j<N;++j) {
            if((s[i-j]=='G' && s[i+j]=='B') || (s[i-j]=='B' && s[i+j]=='G')) ++c;}
            ans += G[i]*(B[N]-B[i+1]);
            ans += B[i]*(G[N]-G[i+1]);
        }
        if(s[i]=='G') {
            for(int j=1;i-j>=0 && i+j<N;++j) {
            if((s[i-j]=='R' && s[i+j]=='B') || (s[i-j]=='B' && s[i+j]=='R')) ++c;}
            ans += B[i]*(R[N]-R[i+1]);
            ans += R[i]*(B[N]-B[i+1]);
        }
        if(s[i]=='B') {
            for(int j=1;i-j>=0 && i+j<N;++j) {
            if((s[i-j]=='R' && s[i+j]=='G') || (s[i-j]=='G' && s[i+j]=='R')) ++c;}
            ans += G[i]*(R[N]-R[i+1]);
            ans += R[i]*(G[N]-G[i+1]);
        }
    }
    cout << ans - c << endl;
}


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

map<long long, map<long long, long long>> edge;
map<long long, long long> has_edge;

int main(){
  int n, m;
  cin >> n >> m;
  for (int i=0;i<m;i++) {
    int a,b;
    cin >> a >> b;
    if (edge.find(a) == edge.end()) {
      map <long long, long long> tmp_m;
      edge[a] = tmp_m;
    } 
    if (edge.find(b) == edge.end()) {
      map <long long, long long> tmp_m;
      edge[b] = tmp_m;
    }
    if (edge[a].find(b) == edge[a].end()) {
      edge[a][b] = 0;
    }
    if (edge[b].find(a) == edge[b].end()) {
      edge[b][a] = 0;
    }
    edge[a][b]++;
    edge[b][a]++;
  }
  while (!edge.empty()) {
    long long start_idx = edge.begin()->first;
    long long curr_idx = start_idx;
    while (true) {
      //      cout << curr_idx << endl;
      
      if (edge.find(curr_idx) == edge.end()) {
	if (curr_idx == start_idx) {
	  break;
	} else {
	  cout << "NO" << endl;
	  return(0);
	}
      }
      long long next_idx = edge[curr_idx].begin()->first;
      edge[curr_idx][next_idx]--;
      if (edge[curr_idx][next_idx] == 0) {
	edge[curr_idx].erase(edge[curr_idx].find(next_idx));
      }
      if (edge[curr_idx].empty()) {
	//	cerr << "erase node " << curr_idx << endl;
	edge.erase(edge.find(curr_idx));
      }
      edge[next_idx][curr_idx]--;
      if (edge[next_idx][curr_idx]==0) {
	edge[next_idx].erase(edge[next_idx].find(curr_idx));
      }
      if (edge[next_idx].empty()) {
	//	cerr << "erase node " << next_idx << endl;
	edge.erase(edge.find(next_idx));
      }
      curr_idx = next_idx;
    }
  }
  cout << "YES" << endl;
  return(0);
}


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

int main() {
	string s;
	while(cin >> s, s != "#") {
		const int n = s.size();
		vector<string> ans;
		function<void(string&, char)> dfs = [&] (string& s, char c) {
			if(c < 'a') {
				ans.push_back(s);
				return;
			}
			bool found = false;
			for(int i = 0; i < n; ++i) {
				if(s[i] == c) {
					s[i] = c + 1;
					dfs(s, c - 1);
					s[i] = c;
					found = true;
				} else if(s[i] == c + 1) {
					return;
				}
			}
			dfs(s, c - 1);
		};
		dfs(s, 'y');
		sort(begin(ans), end(ans));
		ans.erase(unique(begin(ans), end(ans)), end(ans));
		cout << ans.size() << endl;
		if(ans.size() <= 10u) {
			for(auto& s : ans) {
				cout << s << endl;
			}
		} else {
			for(int i = 0; i < 5; ++i) {
				cout << ans[i] << endl;
			}
			for(int i = ans.size() - 5; i < (int)ans.size(); ++i) {
				cout << ans[i] << endl;
			}
		}
	}
}


Measured memory_bytes: 4128
#include<iostream> 
#include<string> 
#include<vector> 
#include<algorithm> 
#include<cmath>
using namespace std; 


int main()
{
	string s;
	cin >> s;
	int ans = 0;
	char k = s.at(0);
	for (int i = 1; i < s.size(); i++)
	{
		if (s.at(i) != k)
		{
			k = s.at(i);
			ans++;
		}
		
	}
	cout << ans << endl;
}




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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define endl '\n'

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const ll mod=1000000007;
//head

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
    vll a(n);
    rep(i,0,n) cin >> a[i];
    
    vector<vector<ll>> dp(n+1,vll(2,-(1LL << 30)));
    dp[0][0] = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 2; j++) {
            if(j == 0)
                dp[i+1][0] = max(dp[i][0] + a[i], dp[i][1] - a[i]);
            else dp[i+1][1] = max(dp[i][0] - a[i], dp[i][1] + a[i]);
        }
    }
    cout << dp[n][0] << endl;
    return 0;
}


Measured memory_bytes: 6528
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


DIV=10**9+7

def mod_invs(n,mod=DIV):
    inv=[0]*(n+1)
    inv[0]=1
    inv[1]=1
    for i in range(2,n+1):
        inv[i] = (-(mod//i)*inv[mod%i]) % mod
    return inv



def main():
    N,M = ints_raw()
    As = [int_raw() for _ in range(M)]
    is_breake = [0]*(N+1)
    for a in As:
        is_breake[a]=1
    memo = [0]*(N+1)

    memo[0]=1
    memo[1]=1 if is_breake[1]==0 else 0
    for n in range(2,N+1):
        if is_breake[n]:
            continue
        else:
            memo[n]=(memo[n-2]+memo[n-1])%DIV
    return memo[-1]

print(main())


Measured memory_bytes: 45148
#include <iostream>
#include <string>
#include <stdio.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    int sum = 0,tmp;
    tmp = n;
    while(tmp > 0) {
        sum += tmp % 10;
        tmp = tmp/10;
    }
    if(n % sum == 0) {
        cout << "Yes";
    }else {
        cout << "No";
    }
    return 0;
}

Measured memory_bytes: 256
N = gets.to_i
T = gets.split.map(&:to_i)
M = gets.to_i

sum = T.inject(:+)

h = Hash.new()
N.times{|i| h[i+1] = T[i] }
p

M.times do |i|
  p, x = gets.split.map(&:to_i)
  puts sum + ( x - h[p] )
end


Measured memory_bytes: 1788
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Runtime.CompilerServices;
using static MyUtil;

class MyUtil
{
    public static int[] ReadIntArray()
    {
	return ReadLine().Split().Select(x => int.Parse(x)).ToArray();
    }
}

class Program
{
    public static void Main()
    {
	int[] tmp = ReadIntArray();
	int a = tmp[0], b = tmp[1], c = tmp[2];

	if (a == b)
	{
	    WriteLine(c);
	}
	else if (b == c)
	{
	    WriteLine(a);
	}
	else
	{
	    WriteLine(b);
	}
    }
}


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

int main(){
	vector<char> grade;
	while(1){
		int m,f,r;
		cin>>m>>f>>r;
		int sum=m+f;
		if(m==-1 && f==-1 && r==-1) break;
		if(m==-1 || f==-1){
			grade.push_back('F');
		}else if(sum>=80){
			grade.push_back('A');
		}else if(65<=sum && sum<80){
			grade.push_back('B');
		}else if(50<=sum && sum<65){
			grade.push_back('C');
		}else if(30<=sum && sum<50){
			if(r>=50){
				grade.push_back('C');
			}else{
				grade.push_back('D');
			}
		}else{
			grade.push_back('F');
		}
	}
	for(int i=0; i<grade.size(); i++){
		cout<<grade[i]<<endl;
	}
	return 0;
}


Measured memory_bytes: 3124
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int x = scanner.nextInt();
		int a = scanner.nextInt();
		int b = scanner.nextInt();

		String selection = "A";
		if (Math.abs(a - x) > Math.abs(b - x)) {
			selection = "B";
		}
		System.out.println(selection);
	}

}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005,inf=0x3f3f3f3f;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int n,cnt[3],b[3];
char ch[N];
struct node{int las,nex,val;}a[N];
bool cmp(int x,int y){return cnt[x]<cnt[y];}
void del(int x){
	int las=a[x].las,nex=a[x].nex;
	a[las].nex=nex;a[nex].las=las;
}
void print(){
	for (int x=a[0].nex;x;x=a[x].nex) putchar(a[x].val+'A');
	putchar('\n');
}
void calc(){
	cnt[0]=cnt[1]=cnt[2]=0;
	for (int x=a[0].nex;x;x=a[x].nex)
	if (a[x].nex&&(a[a[x].nex].val==a[x].val)) del(x);
	else cnt[a[x].val]++;
	b[0]=0;b[1]=1;b[2]=2;
	sort(b,b+3,cmp);

	int now=0,fl=0;
	for (int x=a[0].nex;x;x=a[x].nex)
	if (a[x].val==b[0]) {now+=fl;fl=0;}
	else if (a[x].val==b[1]) fl|=1;
	now+=fl;
	for (int x=a[0].nex;x;x=a[x].nex){
		int lasv=a[a[x].las].val,nexv=a[a[x].nex].val;
		if ((lasv==b[0])&&(nexv==b[0])&&(a[x].val==b[2])&&((--now)<0)) {del(a[x].las);del(x);}
	}
	
	cnt[0]=cnt[1]=cnt[2]=0;
	for (int x=a[0].nex;x;x=a[x].nex) cnt[a[x].val]++;
	for (int x=a[0].nex;x;x=a[x].nex)
	if ((a[x].val==b[2])&&(cnt[b[2]]>cnt[b[1]])&&((!a[x].las)||(a[a[x].las].val^a[a[x].nex].val))){del(x);cnt[b[2]]--;}
	
	for (int x=a[0].nex;x;x=a[x].nex){
		int y=a[x].las;
		if ((cnt[b[1]]>cnt[b[0]])&&((a[x].val^a[y].val)==(b[1]^b[2]))&&((!a[y].las)||(a[a[x].nex].val!=a[a[y].las].val)))
		{del(x);del(y);cnt[b[1]]--;cnt[b[2]]--;}
	}
}
int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	scanf("%s",ch+1);
	n=strlen(ch+1);
	for (int i=1;i<=n;i++) a[i]=(node){i-1,i+1,ch[i]-'A'};
	a[n].nex=0;a[0]=(node){n,1,-1};
	calc();
	print();
	return 0;
}

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

typedef long long ll;
typedef pair<ll, ll> pll;

#define m0(x) memset(x, 0, sizeof(x))
#define all(x) x.begin(), x.end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define asort(x) sort(all(x));
#define dsort(x, t) sort(x.begin(), x.end(), greater<t>());
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define MINS(m, s) m.insert(make_pair(s, 1));
#define MFIN(m, s) m.find(s) != m.end()
#define INF (1 << 29)
const int mod = 1000000007;

int main() {
    int a1, a2, a3;
    cin >> a1 >> a2 >> a3;
    if(a1 + a2 + a3 >= 22) {
        cout << "bust" << endl;
    } else {
        cout << "win" << endl;
    }
    return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <vector>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<map>
#include<math.h>
#include<queue>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1000000007;
const int mod = 1000000007;
const int INF = 1000000001;
const long long LINF = 1e18;
const int MAX = 510000;

int keta(long long int n) {
	int cnt = 1;
	while (n / 10 != 0) {
		n /= 10;
		cnt++;
	}
	return cnt;
}
int m(long long int n) {
	while (n / 10 != 0) {
		n /= 10;
		
	}
	return n;
}
int sum(long long int n) {
	int sum = 0;
	while (n / 10 != 0) {
		sum += n % 10;
		n /= 10;
		
	}
	sum += n % 10;
	return sum;
}
int main() {
	long long int x;
	int ans = 0;
	cin >> x;
	ans = max(9 * (keta(x)-1) + m(x) - 1,sum(x));

	cout << ans << endl;
}


Measured memory_bytes: 3600
N = int(input())
M = 100

ans = 0
dp = [99999] * 100010

dp[0] = 0
for i in range(1,100001):
    power = 1
    while (power <= N):
        dp[i] = min(dp[i], dp[i - power] + 1)
        power *= 6
    power = 1
    while (power <= N):
        dp[i] = min(dp[i], dp[i - power] + 1)
        power *= 9
print(dp[N])

Measured memory_bytes: 8268
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
  string s; cin >> s;
  string ans="";
  for(int i=0; i<s.size(); ++i) {
    char c = s[i];
    if(c=='B' && ans.size()>0) {
      ans.pop_back();
    } else if(c!='B'){
      ans += c;
    }
  }
  cout << ans << endl;

  return 0;
}


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

using namespace std;
int main() {
	int N;
	cin >> N;
	
	vector<long long> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

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


	long long X = 0, Y = 0;
	int i = N-1;
	while (i > -1) {
		if (A[i] == A[i - 1]){
			if (X == 0) {
				X = A[i];
				i = i - 2;
			}
			else {
				Y = A[i];
				break;
			}
		}
		else {
			i--;
		}
	}

	cout << X*Y;

	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int main(){
    int n,t;
    cin>>n>>t;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans=0,mx=-2e9,mn=2e9;
    for(int i=0;i<n;i++){
        if(mx<a[i]-mn){
            mx=a[i]-mn;
            ans=1;
        }
        else if(mx==a[i]-mn){
            ans++;
        }
        mn=min(mn,a[i]);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 640
n, k = map(int, input().split())
A = list(map(int, input().split()))
for i in range(k):
  C = [0]*(n+1)
  for j in range(n):
    C[max(0, j-A[j])] += 1
    C[min(n-1, j+A[j])+1] -= 1
  v = 1
  for j in range(n):
    C[j+1]=C[j+1]+C[j]
    if C[j]!=n:
      v = 0
  if v:
    break
  A = C
C = [str(c) for c in C[:-1]]
print(' '.join(C))

Measured memory_bytes: 161528
import numpy as np
N, x = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
cumsum = A.cumsum()

if cumsum[-1] < x:
    print(N - 1)
    exit()

ans = 0
for i in range(N):
    if cumsum[i] <= x:
        ans = i + 1
print(ans)


Measured memory_bytes: 12396
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>
#include <cstring>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
#include <stack>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>

/* ---------- Constants  */
const double PI = 3.141592653589793238462643383279;
const ll MOD = 1e9 + 7;
const int INF = 1LL << 55;

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */
signed main() {
    int N;
    cin >> N;
    int zero_n = 0;
    int two_n = 0;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        if (a % 4 == 0) two_n++;
        else if (a % 2 != 0) zero_n++;
    }
    cout << (two_n >= zero_n || (two_n + zero_n == N && two_n >= zero_n - 1) ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int N,A[100],flag,count=0;
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    flag = 1;
    while(flag){
        flag = 0;
        for(int j=N-1;j>=1;j--){
            if(A[j]<A[j-1]){
                swap(A[j],A[j-1]);
                count++;
                flag = 1;
            }
        }
    }
    for(int i=0;i<N;i++){
        cout << A[i];
        if(i!=N-1)  cout << " ";
    }
    cout << "\n" << count << "\n";
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);

int main(){
    fastIO;
    int N;
    cin >> N;
    vector<long long> x(N+1,0);
    vector<long long> y(N+1,0);
    vector<long long> t(N+1,0);
    for(int i=1; i<N+1; i++){
        cin >> t[i] >> x[i] >> y[i];
        int dt = abs(t[i]-t[i-1]);
        int dx = abs(x[i]-x[i-1]);
        int dy = abs(y[i]-y[i-1]);
        if(dt%2!=(dy+dx)%2 || dt < dx+dy){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 5528
#include <algorithm>
#include <array>
#include <bitset>
#include <functional>
#include <iostream>
#include <memory>
#include <set>
#include <string>
#include <vector>

using namespace std;

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

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n - i; j++) {
			if (i * 10000 + j * 5000 + (n - i - j) * 1000 == y) {
				cout << i << " " << j << " " << (n - i - j) << endl;
				return 0;
			}
		}
	}
	cout << "-1 -1 -1" << endl;
	return 0;
}


Measured memory_bytes: 768
#include <stdio.h>
int main(void){
    int i,j;            //  ループ文に使用
    int x,y,z;
    int count,count2;   //  カウント用に使用
    char s[256];        //  文字列
    
    count = 0;
    count2 = 0;
    
    //  入力処理
    
    scanf("%d %d %d",&x,&y,&z);
    
    //  計算処理
    
    x = x - y;
    z = z - x;
    if (z < 0){
        z = 0;
    }
    //  出力処理
    
    printf("%d",z);
    
    
}


Measured memory_bytes: 128
#include<iostream>
using namespace std;
int n,m,a[105],sum[10],ts[10];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=10;++j)
        ts[(sum[j]+a[i])%10]=max(ts[(sum[j]+a[i])%10],sum[j]+a[i]);
        for(int j=0;j<=10;++j)
        sum[j]=ts[j];
    }
    for(int i=1;i<=9;++i)
        if (m<sum[i]) m=sum[i];
    cout<<m<<endl;
    return 0;
}

Measured memory_bytes: 256
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,D,A = LI()
    X = []; XH = []
    for _ in range(N):
        x,h = LI()
        X.append(x); XH.append((x,h))
    XH.sort()
    X.sort()
    down = [0] * (N+1)


    p = 0
    ans = 0
    for i in range(N):
        if p < XH[i][1]:
            b = -(-(XH[i][1]-p)//A)
            ans += b
            p += b * A
            down[bisect.bisect(X,X[i]+2*D)-1] += b*A
        p -= down[i]
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 78808
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a,b,c;
	cin>>a>>b>>c;
	cout<<a*b/2<<endl;
}

Measured memory_bytes: 256
buils = [
    [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
    [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
    [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
    [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]]

n = int(input())

for i in range(n):
    BFRV = input().split()
    b = int(BFRV[0])
    f = int(BFRV[1])
    r = int(BFRV[2])
    v = int(BFRV[3])
    
    buils[b-1][f-1][r-1] = buils[b-1][f-1][r-1] + v

for b in range(4):
    for f in range(3):
        for r in range(10):
            print(" ", end="")
            print(buils[b][f][r], end="")
        print("")
    if b != 3:
        print("####################")

Measured memory_bytes: 7764
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
using namespace std;

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 long long INF = 1LL << 60;
int main()
{
	int n;
	int res = 0;
	cin >> n;
	vector<int> a(n+1);
	vector<int> na(n + 1);
	for (int i = 1;i <= n;i++) {
		cin >> a[i];
	}
	na[0] = 0;
	na[1] = 1;
	for (int i = 1; i <= n;) {
		na[a[i]]++;
		if (na[a[i]] >= 2) {
			res = -1;
			break;
		}
		i = a[i];
		if (i == 2) {
			break;
		}
	}
	if (res == -1) {
		cout << res << endl;
		return 0;
	}
	for (int i = 1;i < n + 1;i++) {
		res += na[i];
	}
	cout << res-1 << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")

using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 18; // segment tree size
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f; // memset(dp, 0x3f, sizeof(dp)), 2*INF < INT_MAX
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10; // double EPS

// a종류 토핑이 1개 이하인 경우의 수->그 중 b 종류가 1개인 경우의 수-> nCa * aCb * partitionv(a, b) * 2 ^ (2 ^ (n - a) - 1)
// partitionv(a, b) = sigma k, 1~b partition(b, k) * (2^(n-a))^k
// ans = sigma a, sigma b, sigma k, nCa * aCb * partition(b, k) * (2^(n-a))^k * 2 ^ (2^(n-a) - 1) 
ll mypow(ll a, ll b, ll m) {
	ll rv = 1;
	while (b) {
		if (b % 2) rv = rv*a%m;
		a = a*a%m;
		b /= 2;
	}
	return rv;
}

ll Co[3050][3050];
ll part[3050][3050];
int main() {
	ll N, M, i, j, k;
	scanf("%lld %lld", &N, &M);

	for (i = 0; i <= 3000; i++) {
		Co[i][0] = Co[i][i] = 1;
		for (j = 1; j < i; j++) Co[i][j] = (Co[i - 1][j - 1] + Co[i - 1][j]) % M;
	}
	part[0][0] = 1;
	for (i = 1; i <= 3000; i++) {
		for (j = 0; j <= i; j++) {
			part[i][j] = part[i - 1][j] * (j + 1);
			if (j) part[i][j] += part[i - 1][j - 1];
			part[i][j] %= M;
		}
	}

	ll ans = 0;
	for (ll a = 0; a <= N; a++) {
		ll tv1 = mypow(2, (N - a), M);
		ll tv = mypow(2, mypow(2, N - a, M - 1), M) % M;
		for (ll k = 0; k <= a; k++) {
			ll v = Co[N][a];
			v = v * part[a][k] % M;
			v = v * tv % M;
			if (a % 2) v = M - v;

			ans = (ans + v) % M;
			tv = (tv * tv1) % M;
		}
	}
	return !printf("%lld\n", ans);
}

Measured memory_bytes: 142720
#include<iostream>
#include<algorithm>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define SQ(n) ((n)*(n))
const int inf=1<<28;

int n,m,code[16],in[20000];
int dp[2][256];

int func(int n)
{
	if(n<0)return 0;
	return min(255,n);
}

int main(){
	while(cin>>n>>m,n)
	{
		rep(i,m)cin>>code[i];
		rep(i,n)cin>>in[i];
		
		fill_n(dp[0],256,inf);
		dp[0][128]=0;
		
		int cur=0,next=1;
		for(int i=1;i<=n;i++)
		{
			fill_n(dp[next],256,inf);
			rep(j,256)rep(k,m)dp[next][func(j+code[k])]=min(
				dp[next][func(j+code[k])],dp[cur][j]+
				SQ(func(j+code[k])-in[i-1])
			);
			swap(cur,next);
		}
		
		cout<<*min_element(dp[cur],dp[cur]+256)<<endl;
	}
	return 0;
}

Measured memory_bytes: 960
R, G, B, N = map(int, input().split())

ans = 0
for r in range(0, N // R + 1):
    _g = N - R * r
    for g in range(0, _g // G + 1):
        _b = N - R * r - G * g
        if _b % B == 0:
            ans += 1
print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
inline int_fast64_t read(){int_fast64_t x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;}
int N, ans = 0;
void dfs(int_fast64_t x, bool a, bool b, bool c) {
    if (x > N) return;
    if (a && b && c) ans++;
    dfs(x*10+3, true, b, c);
    dfs(x*10+5, a, true, c);
    dfs(x*10+7, a, b, true);
}
void Main() {
    N = read();
    dfs(0, false, false, false);
    printf("%d\n", ans);
}
int main() {cin.tie(nullptr);ios::sync_with_stdio(false);Main();return 0;}


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

int main() {
  string s;
  int k;
  cin >> s >> k;
  int n = s.size();
  if(n == 1){
    int rest = k % 26;
    int g = s[0] - 'a';
    g += rest;
    g %= 26;
    s[0] = g + 'a';
    cout << s << endl;
    return 0;
  }
  rep(i, n){
    int a = s[i] - 'a';
    if(a == 0)continue;
    if(26 - a <= k){
      s[i] = 'a';
      k -= 26 - a;
    }
  }
  string tmp = "";
  rep(i,n){
    tmp += 'a';
  }
  if(s == tmp){
    int rest = k % 26;
    int g = s[n-1] - 'a';
    g += rest;
    g %= 26;
    s[n-1] = g + 'a';
    cout << s << endl;
    return 0;
  }
  for (int i = n - 1; i >= 0; i--){
    if(s[i] == 'a')continue;
    int j = s[i] - 'a';
    j += k;
    s[i] = j + 'a';
    break;
  }
  cout << s << endl;
}

Measured memory_bytes: 3764
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
  ll N;
  cin>>N;
  for(ll i=1;i<120;i++){
    for(ll j=0;j<120;j++){
      if(i*i*i*i*i-j*j*j*j*j==N){cout<<i<<" "<<j<<endl;return 0;}
      if(i*i*i*i*i+j*j*j*j*j==N){cout<<i<<" "<<-1*j<<endl;return 0;}
    }
  }
}

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

bool uru(int y){
  if(!(y%400))return true;
  if(!(y%100))return false;
  if(!(y%4))return true;
  return false;
}

int day(int y, int m, int d){
  int res = 0;
  int month[] = {31,0,31,30,31,30,31,31,30,31,30};

  for(int i=0;i<y;i++){
    if(uru(i))res += 366;
    else res += 365;
  }

  for(int i=0;i<m-1;i++)res += month[i];
  if(m>2){
    if(uru(y))res += 29;
    else res += 28;
  }

  res += d;
  return res;
}

  

int main(){
  int y1,y2,m1,m2,d1,d2;

  while(1){
    cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2;
    if(y1<0 || m1<0 || d1<0 || y2<0 || m2<0 || d2<0)break;

    int s1,s2;
    s1 = day(y1,m1,d1);
    s2 = day(y2,m2,d2);
    cout << s2 - s1 << endl;
  }
}

Measured memory_bytes: 0
#include<iostream>
#include<cmath>
#include<algorithm>
#include <cassert>
#include<string>
#include<vector>
#include<map>
#include <utility>
#include <math.h>
using namespace std;
int a = 0, b = 0, c = 0, d = 0, e[100010] = {}, f[100010];
double syo = 0, su = 0;
long long   mur=0, kmr=0, yju=0, counto[5003],counto1[5003];
char fir='z',sec='z',mado[5010];
string rik,tok[25003];
bool mazi[110], gi[110],zi,manji;
pair<int, int>n[110];
vector<int> aa[50] = {}, cc;
vector<string> bb;
map<int, int>pos;
int gcd(int a,int b) {
	int d;
	if (a > b) {
		int t = b;
		b = a;
		a = t;
	}
	while ((d = b % a) != 0) {
		b = a;
		a = d;
	}
	return a;
}
int main() 
{
	cin >> a;
	cin >> b;
	if (b % 2 == 1) {
		for (int i = 1; i <= a; i++) {
			if (i%b == 0) {
				mur++;
			}
		}
		cout << mur * mur*mur << endl;
		return 0;
	}
	else {
		for (int i = 1; i <= a; i++) {
			if (i%b == 0) {
				mur++;
			}
			else if((i%b)==(b/2)){
				kmr++;
			}
		}
		//cout << mur << ' ' << kmr << endl;
		cout << mur * mur*mur + kmr * kmr*kmr << endl;
	}
	return 0;
}

Measured memory_bytes: 512
N=int(input())
def dnum(n):
  ret=0
  for i in range(1,n+1):
    if n%i==0:
      ret+=1
  return ret

ans=0

for i in range(1,N+1):
  if i%2==1 and dnum(i)==8:
    ans+=1

print(ans)


Measured memory_bytes: 2940
N= int(input())
A = list(map(int,input().split()))
B = [0] * N

for i in A:
    B[i-1] +=1

B_sum = 0
for i in B:
    B_sum += i * (i-1) //2

for i in range(N):
    print(B_sum-B[A[i]-1]+1)

Measured memory_bytes: 26140
#include <bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> a;
int f(int p) {
	if (a[p].empty()) return 0;
	vector<int> b;
	for (auto x : a[p]) {
		b.push_back(f(x));
	}
	sort(b.rbegin(), b.rend());
	int r = -1;
	for (int i = 0; i < (int)b.size(); ++ i) {
		//cout << "*" << b[i] + i + 1 << endl;
		r = max(r, b[i] + i + 1);
	}
	//cout << r << endl;
	return r;
}
int main() {
	cin >> N;
	a.resize(N+1);
	for (int i = 2; i <= N; ++ i) {
		int x;
		cin >> x;
		a[x].push_back(i);
	}
	cout << f(1) << endl;
}


Measured memory_bytes: 15104
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int a, b;
  cin >> a >> b;
  a--;
  int r = (b - 1 + a - 1) / a;
  cout << r;
}
#endif


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

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define M 998244353

#define ll long long
#define ld long double
#define vi vector<ll>
#define pi pair<ll, ll>
#define vii vector<pi>
#define vvi vector<vi>
#define pb push_back
#define endl "\n"

#define REP(i, s, e) for (ll i = s; i < e; i++)
#define RREP(i, s, e) for (ll i = s; i > e; i--)

#define all(v) v.begin(), v.end()
#define part(v, s, e) v.begin() + s, v.begin() + e
#define print(v) for (auto i: v) cout << i << " ";

int main() {
    fast;
    string s;
    cin >> s;
    ll c  = 0;
    REP(i, 0, s.size())
        if (s[i] == 'o')
            c++;
    if (15 - s.size() + c >= 8)
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}


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

using namespace std;

int main(){
    double x,ans = 0.0;
    string s;
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> x >> s;
        if(s == "JPY") ans+=x;
        else ans += x*380000.0;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256