akhauriyash/Code-Regression huggingface dataset:
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <iomanip>

#include <cassert>
using namespace std;

vector<int> Apply(const vector<int>& lhs, const vector<int>& rhs) {
    vector<int> result(lhs.size());
    for (int i = 0; i < (int) lhs.size(); ++i) {
        result[i] = rhs[lhs[i]];
    }
    return result;
}

vector<int> GetEd(const int n) {
    vector<int> result(n);
    for (int i = 0; i < n; ++i) {
        result[i] = i;
    }
    return result;
}

vector<int> GetBinaryPow(vector<int> one, long long pw) {
    vector<int> result = GetEd(one.size());
    while (pw > 0) {
        if (pw & 1) {
            result = Apply(result, one);
        }
        one = Apply(one, one);
        pw >>= 1;
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> x(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    int m;
    long long k;
    cin >> m >> k;

    vector<int> ids(m);
    for (int i = 0; i < m; ++i) {
        cin >> ids[i];
        --ids[i];
    }

    vector<int> one = GetEd(n - 1);
    for (int i = 0; i < m; ++i) {
        const int id = ids[i];

        swap(one[id - 1], one[id]);
    }

    vector<int> perm = GetBinaryPow(one, k);

    vector<long long> result(n);
    result[0] = x[0];
    for (int i = 1; i < n; ++i) {
        const int id = perm[i - 1];

        const int diff = x[id + 1] - x[id];

        result[i] = result[i - 1] + diff;
    }

    for (int i = 0; i < n; ++i) {
        cout << result[i] << '\n';
    }
    cout.flush();

    return 0;
}


Measured memory_bytes: 3804
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))


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

    const int DAY = 365;
    const int NUM = 26;
    int d;
    cin >> d;
    int c[NUM];
    rep (i, NUM)
    {
        cin >> c[i];
        c[i] = -c[i];
    }

    int s[DAY][NUM];
    rep (i, d) rep (j, NUM) cin >> s[i][j];

    int last[NUM];
    rep (i, NUM) last[i] = 0;

    int t[DAY];
    rep (i, d)
    {
        cin >> t[i];
        --t[i];
    }

    int v[DAY + 1];
    v[0] = 0;
    rep (i, d)
    {
        v[i + 1] = v[i] + s[i][t[i]];
        last[t[i]] = i + 1;
        rep (j, NUM)
        {
            v[i + 1] += c[j] * ((i + 1) - last[j]);
        }
    }

    rep (i, d)
    {
        cout << v[i + 1] << "\n";
    }

    return 0;
}



Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include<numeric>
#include<queue>
#include<stack>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0; i<(int)(n); i++)


int main() {
	int n;
	while(cin >> n, n) {
		vector<vector<int> > ms(n, vector<int>());
		for(int i = 0; i < n; i++) {
			int m;
			cin >> m;
			for(int j = 0; j < m; j++) {
				int mss;
				cin >> mss;
				mss--;
				ms[i].push_back(mss);
			}
		}
		int k;
		cin >> k;
		vector<int> led(n);
		for(int i = 0; i < k; i++) {
			int j;
			cin >> j;
			j--;
			led[j] = 1;
		}
		// fill one
		int kouho = -1;
		for(int i = 0; i < n; i++) {
			int count = 0;
			for(int j = 0; j < ms[i].size(); j++) {
				if(led[ms[i][j]]) count++;
			}
			if (count == k) {
				if (kouho != -1) {
					cout << -1 << endl;
					goto end_loop;
				}
				kouho = i;
			}
		}
		if (kouho == -1) {
			cout << -1 << endl;
		}
		else {
			cout << kouho+1 << endl;
		}
		
		end_loop: {}
	}
	
	return 0;
}

Measured memory_bytes: 956
let n, m, ds = Scanf.scanf "%d %d" @@ fun n m -> Array.(n, m, make_matrix n n (1 lsl 40))
let es = Array.init m @@ fun _ -> Scanf.scanf " %d %d %d" @@ fun a b t -> ds.(a - 1).(b - 1) <- t; ds.(b - 1).(a - 1) <- t; a - 1, b - 1, t
let _ = Array.(iteri (fun i d -> iteri (fun j _ -> if i = j then d.(j) <- 0) d) ds; for k = 0 to n - 1 do for i = 0 to n - 1 do for j = 0 to n - 1 do ds.(i).(j) <- min ds.(i).(j) @@ ds.(i).(k) + ds.(k).(j) done done done; fold_left (fun c (i, j, t) -> if t > ds.(i).(j) then c + 1 else c) 0 es) |> Printf.printf "%d\n"

Measured memory_bytes: 3200
var
	s,a,n,i:Longint;
begin
	read(n);
	i:=1;
	while i<=n do begin
		read(a);
		if a=i then begin
			inc(s);
			read(a);
			inc(i);
		end;
		inc(i);
	end;
	writeln(s)
end.


Measured memory_bytes: 128
#include <stdio.h>
int main(){
	int n,x,count;
	while(1){
		count = 0;
		scanf("%d %d",&n,&x);
		if (n == 0 && x == 0)break;
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= n; j++){
				for (int k = 1; k <= n; k++){
					if((i+j+k)==x&&i!=j&&j!=k&&k!=i)count++;
				}
			}
		}
		printf("%d\n",count/6);
	}
	return 0;
}



Measured memory_bytes: 2032
S = input()

if S == 'RRR':
    print(3)
elif S == 'RRS' or S == 'SRR':
    print(2)
elif S == 'RSS' or S == 'SRS' or S == 'SSR' or S == 'RSR':
    print(1)
else:
    print(0)

Measured memory_bytes: 61560
# https://atcoder.jp/contests/abc117/tasks/abc117_d
=begin
3 7
1 6 3

14

4 9
7 4 0 3

46

1 0
1000000000000

1000000000000
=end
N, upper_bit = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
beki_ary = (1..39).to_a.each_with_object([1]) { |i, obj| obj << (obj.last * 2)}
already_min = false

ans = 0
39.step(0, -1) do |digest|
  mask = 1 << digest
  ones = A.count { |str| (str & mask) > 0 }
  if ones * 2 >= N
    already_min = true if upper_bit[digest] == 1
    ans += beki_ary[digest] * ones
  else
    if already_min || (upper_bit[digest] == 1)
      ans += beki_ary[digest] * (N - ones)
    else
      ans += beki_ary[digest] * ones
    end
  end
end
p ans


Measured memory_bytes: 8844
/*input
4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4
*/
 
 
 
#include <bits/stdc++.h>
using namespace std;
 
 
 
#define int long long int
#define rep(i,n) \
    for(int i = 0; i < n; i++)
#define rep2(i, a, b) \
    for(int i = a; i < b; i++)
#define all(c) \
    c.begin(), c.end()
#define init(arr, num) \
    memset(arr, num, sizeof(arr))
#define fast\
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define inputFile \
    freopen("input.txt", "r", stdin); 
#define outputFile \
    freopen("output.txt", "w", stdout);
#define modM 1000000007
#define PI 3.1415926535897932
#define F first
#define S second  
#define pb push_back  
#define INF 3e18
#ifdef gaviria
#define TRACE
#endif
#ifdef TRACE
#define trace(...) _f(#VA_ARGS, __VA_ARGS_)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
    cout << name << " : " << arg1 << std::endl;
 
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#else
#define trace(...)
#endif
 
 
typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef pair< ll, ll > ii;
typedef unordered_set<int> usi;
 
 
 
ll n,i,j,k,m,c;



void solve()
{
   cin>>n>>m;
   map<ii,int> mp;
 vector<int> v[n+1];

   rep(i,m)
   {
    cin>>j>>k;

    if(mp[{j,k}]||mp[{k,j}])
    {
        continue;
    }

    mp[{j,k}]=1;
    mp[{k,j}]=1;

    v[j].push_back(k);
    v[k].push_back(j);
   }
   int vis[n+1];
   rep(i,n+1)
   vis[i]=0;

int ans=0;
   for(i=1;i<=n;i++)
   {
    if(vis[i]==0)
    {int temp=0;


        stack<int> s;

    s.push(i);

    while(!s.empty())
    {
        temp++;
        k=s.top();
        s.pop();
        vis[k]=1;

        for(auto g: v[k])
        {
            if(vis[g]==0)
            {vis[g]=1;
                s.push(g);
            }
        }

    }
    ans=max(ans,temp);

    }

   }
   cout<<ans;



   }

 
 
 
signed main()
{// inputFile;


    fast;
    int T = 1;
    // cin >> T;
    ll h=T;
    while(T--){
 
        solve();
        cout<<endl;
 
     
        
        
 
    }
    
    
    return 0;
 
}

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

int main() {
	ll x;
	cin >> x;
	ll a, b;
	for (ll i = 1; i * i <= x; i++) {
		if (x % i == 0) {
			a = i;
		}		
	}
	b = x / a;
	cout << a + b - 2 << endl;
}


Measured memory_bytes: 256
int main(){
    int m,f,r;
    for(;;){
        scanf("%d %d %d",&m,&f,&r);
        if(m==-1&&f==-1&&r==-1)break;
        else if (m==-1 || f==-1) printf("F\n");
        else if (m+f>=80) printf("A\n");
        else if (m+f>=65) printf("B\n");
        else if (m+f>=50) printf("C\n");
        else if (m+f>=30 && r>=50) printf("C\n");
        else if (m+f>=30) printf("D\n");
        else if (m+f<30)  printf("F\n");
    }
    return 0;   
}
         
         
         
          
        
      
     
   



Measured memory_bytes: 2048
#include <iostream>

using namespace std;

int main(void) {
    int N;
    cin >> N;
    while(N--) {
        int A;
        cin >> A;
        if(A%2 == 0 && A%3 && A%5) {
            cout << "DENIED" << endl;
            return 0;
        }
    }
    cout << "APPROVED" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <map>
#include <ctime>
#ifdef WK
	#include <windows.h>
#endif
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define lowbit(x) (x&(-x))
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define drep(i,x,y) for(int i=x;i>=y;i--)
#define repg(i,x) for(int i=p[x];i;i=e[i].nt)  
using namespace std;
typedef long long LL;
LL read(){
	LL rtn=0;char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch<='9'&&ch>='0')rtn=(rtn<<3)+(rtn<<1)+ch-'0',ch=getchar();
	return rtn;
}
const int N=100010;
struct edge{
	int b,nt;
}e[N*2];
int p[N],nn;
void anode(int x,int y){
	nn++;e[nn].b=y;e[nn].nt=p[x];p[x]=nn;
	swap(x,y);
	nn++;e[nn].b=y;e[nn].nt=p[x];p[x]=nn;
}
int sg[N];
void dfs(int x,int fa=0){
	repg(i,x){
		int t=e[i].b;
		if(t==fa)continue;
		dfs(t,x);
		sg[x]^=(sg[t]+1);
	}
}
int n;
int main(){
#ifdef WK
	freopen("in.txt","r",stdin);
	//freopen("ou1.txt","w",stdout);
#endif
	scanf("%d",&n);
	rep(i,1,n-1){anode(read(),read());}
	dfs(1);
	printf("%s\n",sg[1]?"Alice":"Bob");
	return 0;
}

Measured memory_bytes: 7168
from collections import defaultdict


def main():
    height, width, target_count = [int(x) for x in input().split()]
    count_by_height = defaultdict(int)
    count_by_width = defaultdict(int)
    bomb_locations = set()
    for _ in range(target_count):
        h, w = [int(x) - 1 for x in input().split()]
        count_by_height[h] += 1
        count_by_width[w] += 1
        bomb_locations.add((h, w))
    max_h = max(v for v in count_by_height.values())
    max_w = max(v for v in count_by_width.values())
    max_h_rows = [i for i, x in count_by_height.items() if x == max_h]
    max_w_columns = [i for i, x in count_by_width.items() if x == max_w]
    all_crossing_bomb = all((h, w) in bomb_locations
                            for h in max_h_rows for w in max_w_columns)
    return max_h + max_w - all_crossing_bomb


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 80800
#include<stdio.h>

int main(void) {
	
	int n, x;
	int count=0;

	while(1){

		(void)scanf("%d %d", &n, &x);

		if (n == 0 && x == 0) {
			break;
		}
	    count = 0;

		for (int i = 1; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				for (int k = j + 1; k < n + 1; k++) {
					if (i + j + k == x) {
						count += 1;
					}
				}
			}
		}



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


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

public class Main{
	
	static int mod=(int)1e9+7;
	
	public static void main(String[] args) throws IOException {
//		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		Writer out=new Writer(System.out);
		Reader in=new Reader(System.in);
		int t=1;
		
		while(t-->0) {	
			int a[]= {5,5,7};
			int b[]=in.readArray(3);
			sort(b);
//			out.println(a);
//			out.println(b);
			out.println(Solution(a,b));			
		}
		out.close();		
		
	}

	static String Solution(int b[], int a[]) {
		for(int i=0; i<3; i++) {
			if(a[i]!=b[i]) return "NO";
		}
		return "YES";
	}
	
/*********************************** UTILITY CODE BELOW **************************************/	
	
	static int ans=Integer.MAX_VALUE;
	
	
	
	static int abs(int a) {
		return a>0 ? a : -a;
	}
	static int pow(int n, int m) {
		if(m==0) return 1;
		int temp=pow(n,m/2);
		long res=(((long)temp*temp)%mod);
		if(m%2==0) return (int)res;
		return (int)((res*n)%mod);
	}
	
	static class Pair{
		int u, v;
		
		Pair(int u, int v){this.u=u; this.v=v;}
		
		static void sort(Pair [] coll) {		
			List<Pair> al=new ArrayList<>(Arrays.asList(coll));
			Collections.sort(al,new Comparator<Pair>() {
				public int compare(Pair p1, Pair p2) {
					return p1.u-p2.u;
				}	
			});
			for(int i=0; i<al.size(); i++) {
				coll[i]=al.get(i);
			}
		}
		
	}
	
	static void sort(int[] a) {
		ArrayList<Integer> list=new ArrayList<>();
		for (int i:a) list.add(i);
		Collections.sort(list);
		for (int i=0; i<a.length; i++) a[i]=list.get(i);
	}
	
	static int [] array(int n, int value) {	
		int a[]=new int[n];
		for(int i=0; i<n; i++) a[i]=value;
		return a;
	}
	
	static class Reader{
		
		BufferedReader br;
		StringTokenizer to;
		
		Reader(InputStream stream){
			br=new BufferedReader(new InputStreamReader(stream));
			to=new StringTokenizer("");
		}
		
		String next() {
			while(!to.hasMoreTokens()) {
				try {
					to=new StringTokenizer(br.readLine());	
				}catch(IOException e) {}
				
			}
			return to.nextToken();
			
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		long nextLong() {
			return Long.parseLong(next());
		}
		
		int [] readArray(int n) {
			int a[]=new int[n];
			for(int i=0; i<n ;i++) a[i]=nextInt();
			return a;
		}
		long [] readLongArray(int n) {
			long a[]=new long[n];
			for(int i=0; i<n ;i++) a[i]=nextLong();
			return a;
		}
		
	}
	
	static class Writer extends PrintWriter{
		Writer(OutputStream stream){
			super(stream);
		}
		void println(int [] array) {
			for(int i=0; i<array.length; i++) {
				print(array[i]+" ");
			}
			println();
		}
		void println(long [] array) {
			for(int i=0; i<array.length; i++) {
				print(array[i]+" ");
			}
			println();
		}
	}
	
}

Measured memory_bytes: 32812
def main():
    ss = list(input())
    ts = list(input())
    n, m = len(ss), len(ts)
    ans = float("inf")
    for i in range(n-m+1):
        ans_temp = 0
        for j in range(m):
            if ss[i+j] != ts[j]:
                ans_temp += 1
        ans = min(ans, ans_temp)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9116
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
  string S;
  cin >> S;
  
  int count=0;
  int count1=0;
  for (int i=0; i<S.size(); i++) {
    if (i%2 == 0) {
      if (S[i]-'0' == 0) {
        count++;
      }
    }
    else {
      if (S[i]-'0' == 1) {
        count++;
      }
    }
  }
    for (int i=0; i<S.size(); i++) {
      if (i%2 == 0) {
        if (S[i]-'0' == 1) {
          count1++;
        }
      }
        else {
          if (S[i]-'0' == 0) {
            count1++;
          }
        }
    }
    int best = min(count,count1);
    cout << best << endl;
}

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

#define ll long long
#define ff first
#define ss second
#define pb push_back

using namespace std;

const int N  = 1e6 + 69;

int n, k;
int dp[N],A[N];

int main(){

        cin >> n >> k;

        for(int i = 1; i <= n; i++){
                cin >> A[i];
        }

        for(int i = A[1]; i <= k; i++){
                for(int j = 1; j <= n; j++){
                        if(i >= A[j])
                        dp[i] |= (dp[i-A[j]]^1);
                }
        }

        puts(dp[k] ? "First" : "Second");
}


Measured memory_bytes: 4352
stack = []
operator = {
        '+': (lambda x, y: x + y),
        '-': (lambda x, y: x - y),
        '*': (lambda x, y: x * y),
        '/': (lambda x, y: float(x) / y)
    }
for i in input().split():
    if i .isdecimal() == True:
        stack.append(int(i))
    elif i in operator.keys():
        y = stack.pop()
        x = stack.pop()
        c = operator[i](x,y)
        stack.append(c)
print(stack[0])


Measured memory_bytes: 5600
import Control.Monad
import qualified Data.ByteString.Char8 as C
import Data.Graph
import Data.List

main = sub =<< get

sub [n,m] = sol n m <$> replicateM m get >>= print

get = unfoldr (C.readInt . C.dropWhile (<'0')) <$> C.getLine 

sol n m es = length $ filter brdg ess
  where
  ess = map (\i -> es\\[es!!i]) [0..m-1]
  brdg = (>1) . length . dff . buildG (1,n) . concatMap (\[u,v] -> [(u,v),(v,u)])

Measured memory_bytes: 4776
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0] * (m + 2) for _ in range(n + 2)]
s = " " + s
t = " " + t
for i in range(n + 1):
    dp[i][0] = 1
flag = False
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s[i] == t[j] or s[i] == '?':
            dp[i][j] = dp[i - 1][j - 1]
    if dp[i][m]:
        flag = True
if not flag:
    print("UNRESTORABLE")
else:
    i = n
    res = str()
    while not dp[i][m]:
        res = ('a' if s[i] == '?' else s[i]) + res
        i -= 1
    while m:
        res = t[m] + res
        i -= 1
        m -= 1
    while i:
        res = ('a' if s[i] == '?' else s[i]) + res
        i -= 1
    print(res)



Measured memory_bytes: 3064
# -*- coding:utf-8 -*-
import bisect

def solve():
    N = int(input())
    Ls = list(map(int, input().split()))
    Ls.sort()

    # O(N^2 * logN)の全探索で解く
    ans = 0
    for a_i in range(N):
        for b_i in range(a_i+1, N):
            c_i = bisect.bisect_left(Ls, Ls[a_i]+Ls[b_i])
            if c_i > b_i:
                ans += c_i - b_i - 1
            else:
                pass

    print(ans)

if __name__ == "__main__":
    solve()


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

int main(void)
{
	int k, s;
	cin >> k >> s;

	int ans = 0;
	int z;

	for (int x = 0; x <= k; x++) {
		for (int y = 0; y <= k; y++) {
			z = s - (x + y);
			if (z >= 0 && z <= k)
				ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i= 0; i < (n); i++)
using ll= long long int;
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; }
ll mod= 1e9 + 7;


int main() {
  int a,b,c;
  cin >>a >>b >>c;
  if(b-a==c-b){cout<< "YES" << endl;}else{cout<<"NO" <<endl;}
}


Measured memory_bytes: 3484
#include <iostream>
#include <queue>

using namespace std;

int main() {
  int n;
  cin >> n;
  priority_queue<double, vector<double>, std::greater<double>> que;
  for (int i = 0; i < n; ++i) {
    int tmp;
    cin >> tmp;
    que.push(tmp);
  }

  for (int i = 0; i < n - 1; ++i) {
    double x = que.top();
    que.pop();
    double y = que.top();
    que.pop();
    que.push((x + y) / 2.);
  }

  cout << que.top() << endl;
}

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

int main()
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	for (int i = 0;a > 0 && c > 0; ++i)
	{
		a -= d * (i % 2 == 1);
		c -= b * (i % 2 == 0);
	}
	cout << ((a > c)?"Yes":"No") << endl;
	return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PSET(x,y) fixed<<setprecision(y)<<x
#define pb push_back
#define pf push_front
#define mp make_pair
#define pii pair<int,int>
#define pli pair<int,int>
#define pint pair<int,int>
#define pid pair<int,double>
#define vi vector<int>
#define ff first
#define ss second
#define ll long long
#define ull unsigned long long
#define SIZE 200010
#define MOD 1000000007
#define BIG 999999937


int main()
{
	
	/*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif*/
    
    int a,b;
    cin>>a>>b;
    
    if(b==1)
    {
    	cout<<0;
    	return 0;
	}
    
    if(a<b)
    {
    	int temp=a-1;
    	int count=1;
    	
    	while(temp<b)
    	{
    		temp+=a;
			count++;
			if(temp<b)
			{
				temp--;	
			}
			else
			{
				break;
			}
		}
		
		cout<<count;
	}
	else
	{
		cout<<1;
	}
	
	return 0;
}


Measured memory_bytes: 256
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    N, M, K = map(int, sysread().split())
    A = list(map(int, sysread().split()))
    B = list(map(int, sysread().split()))

    A_sum = [0]
    for a in A:
        A_sum.append(A_sum[-1] + a)
    B_sum = [0]
    for b in B:
        B_sum.append(B_sum[-1] + b)
    #print(A_sum, B_sum)

    max_val = 0
    for i, a in enumerate(A_sum):
        if a > K:
            max_val = max(i-1, max_val)
            break
        idx = bisect.bisect_left(B_sum, K-a)
        if idx < len(B_sum) and B_sum[idx] == K-a:
            idx += 1
        max_val = max(max_val, idx+i-1)
        #print(i, idx)
    print(max_val)



if __name__ == "__main__":
    run()

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


using namespace std;

int main() {
        int N;
        cin >>N;
        string S;
        cin >>S;
        if(N%2==1) cout <<"No";
        else{
        int middle = N/2;
        string former = S.substr(0,middle);
        string latter =S.substr(middle);
        if(former==latter) cout <<"Yes";
        else cout <<"No";
        }
}

Measured memory_bytes: 256
/*我是萌新*/
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include <iomanip>
#include<map>
typedef long long ll;
const int mod = 1e9+7;
using namespace std;
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
//fixed<< setprecision(2)
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    ll t;
    while (cin >> t)
    {
        cout<<t+t*t+t*t*t<<'\n';
    }
}

Measured memory_bytes: 3116
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

int main() {
    ll a, b, x; cin >> a >> b >> x;
    if (a == 0) {
        cout << b/x + 1 << endl;
        return 0;
    }
    cout << b/x-(a-1)/x << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define VVVI vector<vector<vector<ll>>>
#define VVVVI vector<vector<vector<vector<ll>>>>
#define REP(i,n) for(ll i=0,_n=(n);(i)<(ll)_n;++i)
#define REPR(i,n) for(ll i=(ll)(n)-1;0<=(i);--i)
#define RANGE(i,a,b) for(ll i=(ll)a,_b=(ll)(b);(i)<_b;++i)
#define RANGER(i,a,b) for(ll i=(ll)(b)-1,_a=(ll)(a);(_a)<=i;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
#define FI first
#define SE second
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template<typename T>void maxUpdate(T& a, T b) {a = max(a, b);}
template<typename T>void minUpdate(T& a, T b) {a = min(a, b);}

#define MOD 1000000007LL
#define INF (1LL<<60)

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N,L;
	while(cin>>N>>L) {
		ll sum = 0;
		REP(i, N) sum += L+i;
		ll ans = 0;
		ll mi = 10000000;
		REP(i, N) {
			ll lans = sum-(L+i);
			if(abs(sum-lans)<mi) {
				mi = abs(sum-lans);
				ans = lans;
			}
		}
		
		cout<<ans<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

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

    s64 W, H;
    cin >> W >> H;

    if (W * H % 3 == 0)
    {
        cout << "0\n";
        return 0;
    }

    s64 ans = 1e6;
    s64 y = (H / 2);
    for (s64 x = 1; x < W; ++x)
    {
        ans = MIN(ans, MAX((H - y) * (W - x), H * x) - MIN(H * x, (W - x) * y));
        ans = MIN(ans, MAX(H * (W - x - ((W - x) / 2)), H * x) - MIN(H * x, H * ((W - x) / 2)));
    }

    swap(W, H);
    y = (H / 2);
    for (s64 x = 1; x < W; ++x)
    {
        ans = MIN(ans, MAX((H - y) * (W - x), H * x) - MIN(H * x, (W - x) * y));
        ans = MIN(ans, MAX(H * (W - x - ((W - x) / 2)), H * x) - MIN(H * x, H * ((W - x) / 2)));
    }

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



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

#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPL(i,a,n) for(ll i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define SORTVG(v) sort(v.begin(),v.end(),greater<>())
#define SORTV(v) sort(v.begin(),v.end())
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define INF INT_MAX/2
#define int long long

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;

template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}
template<class T> void YesNo(T& a) {if(a){cout << "Yes" << ENT;}else{cout << "No" << ENT;}}
template<class T> void YESNO(T& a) {if(a){cout << "YES" << ENT;}else{cout << "NO" << ENT;}}
template<class T> void AorB(T& a, string A,string B) {if(a){cout << A << ENT;}else{cout << B << ENT;}}

int atcoder(){
    string s,t;
    int ans=1000;
    cin>>s;
    for(char i='a'; i<='z'; i++){
        int tmpans=0;
        t=s;
        while(1){
            if(t.size()==1) goto out;
            REP(j,0,t.size()){
                if(t[j]!=i) break;
                else if(j==t.size()-1) goto out;
            }
            string tmp((int)t.size()-1,' ');
            REP(j,0,t.size()-1){
                if(t[j]==i || t[j+1]==i) tmp[j]=i;
                else tmp[j]=t[j];
            }
            tmpans++;
            t=tmp;
        }
    out:
        chmin(ans,tmpans);
    }
    cout<<ans<<ENT;
    return 0;
}

signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    atcoder();
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
 #include<stdio.h>
 #include<cstdlib>
 #include<cstdio>
 #include<string>
 #include<math.h>
 #include<iomanip>
 #include<algorithm>
 #include<string.h>
 #include<cctype>
 #include<map>
 #include<set>
 #include<vector>
 #include<sstream>
 #include<stack>
 #include<queue>
 #include<deque>
 #include<functional>
 #include<utility>
 #include<list>
 
 using namespace std;
 
 bool isLeap(int year)
 {
   if(year%4!=0) return false;
   else
   {
     if(year%100==0)
     {
       if(year%400==0) return true;
       else return false;               
     }
     else return true;    
   }     
 }
 
 int main()
 {
   int start,end;
   bool flag=false;
   while(cin>>start>>end&&(start||end))
   {
     if(flag) cout<<endl;
     int count=0;
     for(int i=start;i<=end;i++)
     {
       if(isLeap(i))
       {
         cout<<i<<endl; 
         count++;
       }        
     }                       
     if(!count) cout<<"NA"<<endl;
     //cout<<endl; 
     flag=true;            
   }
   //while(1);
   return 0;
 }

 

Measured memory_bytes: 2972
#include <stdio.h>
#include <stdbool.h>

int main() {
	int i, j, N, M, X, Y, Z, countx, county;
	int x[100], y[100];
	bool sensox, sensoy;

	scanf("%d %d %d %d", &N, &M, &X, &Y);
	for (i = 0; i < N; i++) scanf("%d", &x[i]);
	for (i = 0; i < M; i++) scanf("%d", &y[i]);

	Z = Y;

	while (X < Z) {
		countx = 0;
		county = 0;
		sensox = false;
		sensoy = false;

		for (i = 0; i < N; i++) {
			if (x[i] < Z) countx++;
			else break;
		}
		if (N == countx) sensox = true;

		for (i = 0; i < M; i++) {
			if (y[i] >= Z) county++;
			else break;
		}
		if (M == county) sensoy = true;

		if (sensox == true && sensoy == true) break;
		Z--;
	}

	printf(X < Z ? "No War\n" : "War\n");

	return 0;
}

Measured memory_bytes: 128
a = gets.split(" ").map{|x| x.to_i}

W=a[0]
H=a[1]
x=a[2]
y=a[3]
r=a[4]

if r <= x and r <= y and x+r <= W and y+r <= H
	print "Yes\n"	
else
	print "No\n"
end

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

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
int main()
{
  char c[3];
  cin>>c;
  for(int i=0;i<3;i++)
  {
    if(c[i]=='7')
    {
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 3632
N, M = map(int, input().split())
a_list = [int(input()) for _ in range(M)]

mod = 1000000007

DP = [-1] * (N + 1) 
DP[0] = 1 
DP[1] = 1 

def fib(n):
    for i in range(2, n + 1):
        DP[i] = DP[i-1] + DP[i-2]
    
    return DP[n]

ans = 1
x = 0

for a in a_list:
    if a == x:
        ans = 0
        break
    
    ans = (ans * fib((a-1)-x)) % mod
    x = a+1
else:
    ans = (ans * fib(N-x)) % mod
    
print(ans)

Measured memory_bytes: 460020
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,cnt,a[1005],b[1005];
string s;
int main()
{
	cin>>s>>n;
	for(int i=0;i<s.size();i++)
	if(i%n==0)
	cout<<s[i]; 
    return 0;
	} 

Measured memory_bytes: 256
import java.util.*;
import java.awt.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        if (n == 1) {
            System.out.println("Hello World");
        } else if (n == 2) {
            int A = sc.nextInt();
            int B = sc.nextInt();

            System.out.println(A + B);
        }
    }
}

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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; } template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

int main()
{
	
	//cin.tie(0); ios_base::sync_with_stdio(false);
	string s, t;
	cin >>s >>t;
	
	rep(i, sz(s)){
		rotate(s.begin(),s.begin()+1, s.end());
		if(s ==t) {puts("Yes"); return 0;}
		//cout << t <<" " <<s <<"\n";
	}
	puts("No");
	return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define M 1020
#define mod 1000000007
using namespace std;
LL read(){
	LL nm=0,fh=1;char cw=getchar();
	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
	return nm*fh;
}
LL qpow(LL x,LL qs){
	LL fin=1;
	while(qs){
		if(qs&1) fin=fin*x%mod;
		qs>>=1,x=x*x%mod;
	}
	return fin;
}
struct mat{
	LL p[2][2];
	mat operator *(const mat&ot)const{
		mat tmp;
		for(LL i=0;i<2;i++){
			for(LL j=0;j<2;j++){
				tmp.p[i][j]=0;
				for(LL k=0;k<2;k++) tmp.p[i][j]+=p[i][k]*ot.p[k][j];
				tmp.p[i][j]%=mod;
			}
		}
		return tmp;
	}
}T,ANS;
bool t1=false,t2=false; 
LL n,m,K,cnt,ans,sum,con;
char ch[M][M];
int main(){
	n=read(),m=read(),K=read();
	for(int i=1;i<=n;i++){
	    scanf("%s",ch[i]+1);
	    for(int j=1;j<=m;j++) sum+=(ch[i][j]=='#');
    }
	for(int i=1;i<=n;i++) t1|=(ch[i][1]=='#'&&ch[i][m]=='#');
	for(int i=1;i<=m;i++) t2|=(ch[1][i]=='#'&&ch[n][i]=='#');
	if((!t1)&&(!t2)){printf("%lld\n",qpow(sum,K-1));return 0;}
	else if((t1&&t2)||K==0){puts("1");return 0;}
	else if(t2){
		for(int i=1;i<=max(n,m);i++){
			for(int j=1;j<i;j++) swap(ch[i][j],ch[j][i]);
		}
		swap(n,m);
	}
	for(int i=1;i<=n;i++){
		con+=(ch[i][1]==ch[i][m]&&ch[i][1]=='#');
		for(int j=1;j<m;j++) cnt+=(ch[i][j]==ch[i][j+1]&&ch[i][j]=='#');
	}
	for(int i=0;i<2;i++) ANS.p[i][i]=1;
	T.p[0][0]=sum,T.p[0][1]=mod-cnt,T.p[1][1]=con;
	for(K--;K>0;K>>=1,T=T*T) if(K&1) ANS=ANS*T;
	printf("%lld\n",(ANS.p[0][0]+ANS.p[0][1])%mod);
	return 0;
}

Measured memory_bytes: 1280
/**
 * @author pr4shan7 (प्रशांत)
 */
// everything has a cost!

#ifdef _MAVERICK
#define _DEBUG
#else
#pragma GCC optimize("O2", "unroll-loops", "omit-frame-pointer", "inline")
#pragma GCC option("arch=native", "tune=native", "no-zero-upper")
#pragma GCC target("avx,avx2,fma")
// #pragma GCC reset_options
#endif

#ifndef _DEBUG
#define NDEBUG
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
// #define cerr cout
// #define int long long
// #define double long double

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pb_set;
typedef unordered_set<int> usi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef set<int> si;
typedef long long ll;
#define pb push_back
#define x first
#define y second
#define cai static_cast<int>
#define cad static_cast<double>
#define cal static_cast<long long>
#define all(z) z.begin(), z.end()
#define tr(cont, itm) for (auto&& itm : cont)
#define rep(in, beg, sz) for (int in = beg; in < sz; in++)
#define rrep(in, sz, beg) for (int in = sz - 1; in >= beg; in--)
#define rtr(cont, itr) for (auto itr = cont.end() - 1; itr >= cont.begin(); itr--)

#ifdef _DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

template <typename... T> inline void debug_out(const T&...);
#else
#define debug(...) 42
#endif

template <typename T> inline istream& operator>>(istream& in, vector<T>& ar);
template <typename T> inline ostream& operator<<(ostream& out, const vector<T>& ar);
template <typename T> constexpr inline T pow(long long, long long, const T);

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

// beautiful things don't ask for attention



int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

#ifdef _MAVERICK
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("err.txt", "w", stderr);
#endif

	int n; cin >> n;
	vi balls(n); cin >> balls;
	vi freq(2*N,0);
	tr(balls,i) freq[i]++;
	ll ans{};
	tr(freq,i) {
		if(i) {
			ans+= (1LL*i*(i-1))/2;
		}
	}

	rep(k,0,n) {
		int temp=freq[balls[k]];
		ll nans=ans - (1LL*temp*(temp-1))/2;
		temp--;
		if(temp>0) nans+=(1LL*temp*(temp-1))/2;

		cout << nans  << endl;
	}

	return 0;
}


#ifdef _DEBUG
template <typename... T>
inline void debug_out(const T&... args) { ((cerr << ' ' << args), ...); cerr << endl; }
#endif

template <typename T>
inline istream& operator>>(istream& in, vector<T>& ar) {
	for (auto& i : ar) in >> i;
	return in;
}

template <typename T>
inline ostream& operator<<(ostream& out, const vector<T>& ar) {
	for (int i = 0; i < ar.size() - 1; i++) out << ar[i] << ' ';
	out << ar[ar.size() - 1];
	return out;
}

template <typename T>
constexpr inline T pow(long long a, long long b, const T mv) {
	long long res = 1;
	a %= mv;
	while (b) {
		if (b & 1)
			res = (res * a) % mv;
		b >>= 1;
		a = (a * a) % mv;
	}
	return res;
}

// get busy living or get busy dying


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

vector<int> to[200005];
vector<bool> seen(200005);

void dfs(int v, int p){
	seen[v] = true;
	for(auto nextv: to[v]){
		if(seen[nextv] == true) continue;
		dfs(nextv, v);
	}
}

int main(){
	int n,m;
	cin >> n >> m;
	rep(i,n){
		int k;
		cin >> k;
		rep(j,k){
			int l;
			cin >> l;
			to[i].push_back(n+l-1);
			to[n+l-1].push_back(i);
		}
	}
	
	dfs(0, -1);
	bool ok = true;
	
	rep(i,n){
		if(seen[i] == false) ok = false;
	}
	
	if(ok){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
			
    return 0;
}



Measured memory_bytes: 8704
/* به نام یزدان */
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100 + 3, MAX_K = 100 * 1000 + 3, MOD = 1e9 + 7;
int n, k, a[MAX_N], dp[MAX_N][MAX_K];

void read_input() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
}

void solve() {
	for (int i = 0; i <= k; i++)
		dp[0][i] = 1;
	for (int i = 1; i <= n; i++) {
		dp[i][0] = 1;
		for (int j = 1; j <= k; j++)
			dp[i][j] = (1LL * dp[i][j - 1] + dp[i - 1][j] - (j - a[i] - 1 >= 0? dp[i - 1][j - a[i] - 1]: 0) + MOD) % MOD;
	}
}

void print_output() {
	cout << (dp[n][k] - (k? dp[n][k - 1]: 0) + MOD) % MOD;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	read_input();
	solve();
	print_output();
}


Measured memory_bytes: 39680
#include <stdio.h>

int main(){
  
  int i, j, n, A[101][101] = {0};
    
    scanf("%d",&n);

    int u,k,v;
    
    for (i=0; i<n; i++) {
        scanf("%d %d", &u, &k);
        for (j=0; j<k; j++) {
            scanf("%d",&v);
            A[u][v] = 1;
        }
    }

    
    for (i=1; i<=n; i++) {
        for (j=1; j<=n-1; j++) {
            printf("%d ", A[i][j]);
            
        }
        printf("%d\n", A[i][n]);
    }
    
    return 0;
}





Measured memory_bytes: 2052
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>
#define INF 1000000000
#define mod 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define all(x) (x).begin(),x.end()
using namespace std;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool debug=false;

int main(){
  int a[4]={0},n;
  string s;
  while(cin>>n){
    getchar();
    cin>>s;
    if(s=="A")a[0]++;
    else if(s=="B")a[1]++;
    else if(s=="AB")a[2]++;
    else if(s=="O")a[3]++;
  }
  rep(i,4)cout<<a[i]<<endl;
  return 0;
}

Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
bool check(int *sum,int x,int m)
{
	for(int i=0;i<m;i++)
	{
		if(sum[i]<x) return 0;
	}
	return 1;
}
int main()
{
	int n,m,x,mini=1200007;
	cin>>n>>m>>x;
	int c[21],a[21][21];
	for(int i=0;i<n;i++)
	{
		cin>>c[i];
		for(int j=0;j<m;j++) cin>>a[i][j];
	}
	for(int i=0;i<(1<<n);i++)
	{
		int sum[50],cost=0;
		memset(sum,0,sizeof(sum));
		for(int j=0;j<n;j++)//枚举所有可能的方案，每一个i对应一个方案 
		{
			if(i&(1<<j))//i的第j位是1，在i的方案中包含j这本书 
			{
				for(int k=0;k<m;k++) sum[k]+=a[j][k];
				cost+=c[j];
			}
		}
		if(check(sum,x,m)==1)
		{
			if(mini>cost) mini=cost;
		}
	}
	if(mini==1200007) cout<<-1;
	else cout<<mini;
    return 0;
}

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

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

    N = NI()
    A = LI()
    d = {}

    for x in A:
        for i in range(2,int(math.sqrt(x))+1):
            cnt = 0
            while x % i == 0:
                cnt += 1
                x //= i
            if cnt:
                if i in d:
                    d[i] = max(d[i],cnt)
                else:
                    d[i] = cnt
            if x == 1: break
        else:
            if x in d:
                d[x] = max(d[x],1)
            else:
                d[x] = 1
    m = 1
    for i,x in d.items():
        m = (m * i ** x) % MOD
    ans = 0
    for x in A:
        ans += (m * pow(x,MOD-2,MOD)) % MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Measured memory_bytes: 46316
#include <cstdio>
int n, a, b, ma, mb=2e9;
int main() {
	scanf("%d", &n);
	while(n--) {
		scanf("%d%d", &a, &b);
		if(b<mb) mb=b, ma=a;
	}
	printf("%d", ma+mb);
	return 0;
}

Measured memory_bytes: 128
N = int(input())
dic = {}

maxi = 0
for _ in range(N):
    s=input()
    if s in dic.keys():
        dic[s] += 1
    else:
        dic[s] = 1
    maxi = max(maxi, dic[s])

keys = sorted(dic.keys())
for k in keys:
    if dic[k] == maxi:
        print(k)

Measured memory_bytes: 32148
import bisect
from heapq import heappush, heappop
n = int(input())
a = []
for i in range(n):
    temp = float(input()) * (10**9)
    a.append(int(temp+0.1))
b = []
d = {0:0,1:0,2:0,3:0,4:0,5:0}
p = [[]for i in range(19)]
for i in a:
    cnt2 = 0
    cnt5 = 0
    while i%2 == 0:
        i //= 2
        cnt2 += 1
    while i%5 == 0:
        i //= 5
        cnt5 += 1
    p[min(18,cnt2)].append(-cnt5)
    # d[min(5,cnt5)] += 1
    # b.append([cnt2,cnt5])
# print(b)
# print(d)
ans = 0
for i in range(19):
    p[i] = sorted(p[i])
# print(p)
for i in range(19):
    while p[i]:
        t = p[i].pop()
        # print(t)
        # for j in p[i]:
        for k in range(max(0,18-i),19):
            # print(k,p[k],t,bisect.bisect_right(p[k],-18-t))
            ans += bisect.bisect_right(p[k],-18-t)
print(ans)
# for i in range(len(a)-1):
#     for j in range(i+1,len(a)):
#         if a[i] > 0 and a[j] > 0 and a[i]*a[j] %(10**8) == 0:
#             ans += 1
#             # print(a[i],a[j])
# print(ans)
# print(a)

Measured memory_bytes: 96396
#include<iostream>
using namespace std;
#define int long long int
int32_t main()
{
	int n;
	cin>>n;
	string str1,str2;
	cin>>str1>>str2;
	int answer=2*n;
	int j;
	for(j=n-1;j>=0;j--)
	{
		bool result=true;
		int ptr=0;
		int count=0;
		for(int i=j;i<n;i++)
		{
			if(str1[i]==str2[ptr])
			    count++;
			else
			{
				result=false;
				break;
			}
			ptr++;
		}
		if(result)
		{
			answer=min(answer,2*n-count);
		}
    }
    cout<<answer<<endl;
}


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

int main() {
	string s;
	cin >> s;
	int sum = 0;
	for ( char c : s ) {
		sum += ( c - '0');
	}
	cout << ( sum % 9 == 0 ? "Yes" : "No") << '\n';
	return 0;
}



Measured memory_bytes: 3704
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define N 100010
using namespace std;
int nxt[N<<1],to[N<<1],w1[N<<1],head[N],cnt;
void add(int u,int v,int w)
{
	nxt[++cnt]=head[u];
	to[cnt]=v;
	w1[cnt]=w;
	head[u]=cnt;
}
int siz[N],msiz[N];
int root,rtsiz,n;
long long ans;
void dfs(int u,int fa,int w)
{
	int maxsiz=0;
	siz[u]=1;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs(v,u,w1[i]);
		siz[u]+=siz[v];
		maxsiz=max(maxsiz,siz[v]);
	}
	ans+=1ll*min(siz[u],n-siz[u])*w*2;
	maxsiz=max(maxsiz,n-siz[u]);
	msiz[u]=maxsiz;
	if(maxsiz<rtsiz)
	{
		rtsiz=maxsiz;
		root=u;
	}
}
int main()
{
	scanf("%d",&n);
	rtsiz=n+2;
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1,0,0);
	int res=100000000;
	for(int i=head[root];i;i=nxt[i])
	{
		int v=to[i];
		res=min(res,w1[i]);
		if(msiz[root]==msiz[v])
		{
			printf("%lld\n",ans-w1[i]);
			return 0;
		}
	}
	printf("%lld\n",ans-res);
	return 0;
}


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

int main()
{
    int N, M;
    cin >> N >> M;

    vector<vector<int>> edge(N + M);
    for (int i = 0; i < N; i++)
    {
        int K;
        cin >> K;
        for (int j = 0; j < K; j++)
        {
            int L;
            cin >> L;
            L--;
            edge[i].push_back(N + L);
            edge[N + L].push_back(i);
        }
    }

    vector<bool> is_visited(N + M, false);
    queue<int> q;
    q.push(0);
    while (!q.empty())
    {
        int from = q.front();
        q.pop();
        if (is_visited[from])
        {
            continue;
        }
        else
        {
            is_visited[from] = true;
        }

        for (int to : edge[from])
        {
            if (!is_visited[to])
            {
                q.push(to);
            }
        }
    }

    for (int i = 0; i < N; i++)
    {
        if (!is_visited[i])
        {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
}


Measured memory_bytes: 8824
#include<bits/stdc++.h>
using namespace std;
const int n = 1e5 + 5 ;
int x[n];
int main(void){
int m;cin>>m;
string y[m];
for(int i=0;i<m;i++)
    cin>>y[i];
pair<string,int>x[4];
x[0].first="AC";
x[1].first="WA";
x[2].first="TLE";
x[3].first="RE";
for(int i=0;i<4;i++){
    x[i].second=count(y,y+m,x[i].first);
}
for(int i=0;i<4;i++)
    cout<<x[i].first<<" x "<<x[i].second<<endl;


return 0;}


Measured memory_bytes: 6728
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  ll x,a,b;
  cin >> x >> a >> b;
  x-=a;
  pr(x%b);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 256