akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<random>
#include<algorithm>
#include<unistd.h>
#define rep(i,n) for(int i = 0 ; i < (n) ; i++)
using namespace std;

int g[50][50]={};
 
 
int main(){
  int N,M;
  cin >> N >> M;

  rep(i,M){
    int a,b;
    cin >> a >>b;
    g[a-1][b-1] = 1;
    g[b-1][a-1] = 1;
  }



  
  int count = 0;
  rep(i,N){
    rep(j,N){
      if(g[i][j] == 0) continue;
      int g_temp[50][50]={0};

      rep(k,N){
        rep(l,N){
            g_temp[k][l] = g[k][l];
        }
      }
      g_temp[i][j] = 0;
      g_temp[j][i] = 0;

      
//    rep(k,N){
//      rep(l,N){
//        cout << g_temp[k][l];
//      }
//      cout <<endl;
//    }
//     cout << endl;
//     cout << endl;
//     rep(k,N){
//       rep(l,N){
//         cout << g[k][l];
//       }
//       cout <<endl;
//     }
//     cout << i << " " << j << endl;




      vector<int> traveled;
      queue<int> q;

      int now = 0;
      rep(k,N) rep(l,N){
        if(g_temp[k][l] == 1){
          now = k;
        }
      }

      traveled.push_back(now);
      while(1){
//        cout << now << endl;

        rep(k,N) if(g_temp[now][k] == 1){
          auto result = find(traveled.begin(),traveled.end(),k);
          if (result == traveled.end() ){
            q.push(k);
            traveled.push_back(k);
          }
        }

        if (int(q.size()) == 0 ) break;
        now = q.front();
        q.pop();
      }
      if(int(traveled.size()) < N){
        ++count;
      }
    }
  }
  cout << count/2 << endl;
}






Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int myposition(const pair<long long int, long long int>& p) {
    long long int x = p.first, y = p.second;
    if (x > 0 && y >= 0) {
        return 1;
        }
        if (x <= 0 && y > 0) {
            return 2;
        }
        if (x < 0 && y <= 0) {
            return 3;
        }
        if (x >= 0 && y < 0) {
            return 4;
        }
        return 0;
}

bool mycompare(const pair<long long int, long long int>& p1,
    const pair<long long int, long long int>& p2) {
    return 1.0 * pow(p1.second, 2) / (pow(p1.first, 2) + pow(p1.second, 2)) < 1.0 * pow(p2.second, 2) / (pow(p2.first, 2) + pow(p2.second, 2));
}

int main() {
    int n;
    cin >> n;
    vector<pair<long long int, long long int>> vp1, vp2, vp3, vp4, vp;
    long long int x, y;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        if (x > 0 && y >= 0) {
            vp1.emplace_back(x, y);
        }
        if (x <= 0 && y > 0) {
            vp2.emplace_back(x, y);
        }
        if (x < 0 && y <= 0) {
            vp3.emplace_back(x, y);
        }
        if (x >= 0 && y < 0) {
            vp4.emplace_back(x, y);
        }
    }
    sort(vp1.begin(), vp1.end(), mycompare);
    sort(vp2.begin(), vp2.end(), mycompare);
    reverse(vp2.begin(), vp2.end());
    sort(vp3.begin(), vp3.end(), mycompare);
    sort(vp4.begin(), vp4.end(), mycompare);
    reverse(vp4.begin(), vp4.end());
    vp.reserve(vp1.size() + vp2.size() + vp3.size() + vp4.size());
    vp.insert(vp.end(), vp1.begin(), vp1.end());
    vp.insert(vp.end(), vp2.begin(), vp2.end());
    vp.insert(vp.end(), vp3.begin(), vp3.end());
    vp.insert(vp.end(), vp4.begin(), vp4.end());
    double res = 0;
    n = vp.size();
    for (int i = 0; i < n; i++) {
        int pos1 = myposition(vp[i]);
        int next_pos1 = (pos1 + 1 == 5 ? 1 : pos1 + 1);
        int next_pos2 = (pos1 + 2 > 4 ? pos1 + 2 - 4 : pos1 + 2);
        int index = (i + 1) % n;
        x = vp[i].first, y = vp[i].second;
        
        res = max(res, pow(x * x + y * y, 0.5));
        while (index != i) {
            int pos2 = myposition(vp[index]);
            long long int c = vp[index].first * vp[i].first + vp[index].second * vp[i].second;
            if ((pos2 == next_pos1) || (pos2 == pos1 && c >= 0) || (pos2 == next_pos2 && c <= 0)) {
                x += vp[index].first;
                y += vp[index].second;
                res = max(res, pow(x * x + y * y, 0.5));
            } else {
                break;
            }
            index = (index + 1) % n;
        }
        res = max(res, pow(x * x + y * y, 0.5));
    }
    cout << setprecision(30) << res << endl;
}









Measured memory_bytes: 4128
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

def gcd(a,b):
    return math.gcd(a,b)

if __name__ == "__main__":
    n,x = I2()
    a = Intl()
    ans = abs(a[0]-x)
    for i in range(1,n):
        ans = gcd(ans,abs(a[i]-x))
    print(ans)


Measured memory_bytes: 19932
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
signed main()
{
   SPEED;
   int n,m;
   cin>>n>>m;
   if(n%2==1)
   {
       int i=1,j=2*m;
       for(int t=0;t<m;t++)
       {
           cout<<i<<" "<<j<<endl;
           ++i;
           --j;
       }
   }
   else
   {
       int i=1,j=n,f=1;
       for(int t=0;t<m;++t)
       {
           if(t>=n/4 && f==1)
           {
               --j;
               f=-1;
           }
           cout<<i<<" "<<j<<endl;
           ++i;
           --j;
       }
   }
}

Measured memory_bytes: 3656
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        HashSet<Integer> a = new HashSet<>();
        HashSet<Integer> b = new HashSet<>();
        for (int i = 0; i < m; i++) {
            int tmpa = sc.nextInt();
            int tmpb = sc.nextInt();
            if(tmpa == 1) {
                a.add(tmpb);
            }
            if(tmpb == n) {
                b.add(tmpa);
            }
        }
        for (int aa : a) {
            if(b.contains(aa)) {
                System.out.println("POSSIBLE");
                return;
            }
        }
        System.out.println("IMPOSSIBLE");
    }
}

Measured memory_bytes: 72984
s = input()

def kaibun_check(s):
    n = len(s)
    zenhan_s = s[:int((n - 1)/2)]
    zenhan = zenhan_s == zenhan_s[::-1]
    kouhan_s = s[int((n + 1)/2):]
    kouhan = kouhan_s == kouhan_s[::-1]
    return zenhan and kouhan and (s == s[::-1])

print("Yes" if kaibun_check(s) else "No")


Measured memory_bytes: 38256
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define show(x) cout << #x << " = " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int main(){
    int n,a,b;
    cin >> n >> a >> b;
    rep(i,1000){
        if(a+1==b){
            if(i%2==0){
                cout << "Borys" << endl;
            }else{
                cout << "Alice" << endl;
            }
        }
        if(i%2==0){
            a++;
        }else{
            b--;
        }
    }
}

Measured memory_bytes: 256
using System;

namespace Atc_0017
{
    class Program
    {
        static void Main(string[] args)
        {
            var rStr = Console.ReadLine();

            int N = int.Parse(rStr.Split(' ')[0]);
            int K = int.Parse(rStr.Split(' ')[1]);

            bool[] results = new bool[N];

            for (int i = 0; i < K; i++)
            {
                int d = int.Parse(Console.ReadLine());

                var AAs = Console.ReadLine();

                for (int j = 0; j < d; j++)
                {
                    var s = int.Parse(AAs.Split(' ')[j]);
                    results[s - 1] = true;
                }
            }

            int ret = 0;

            for (int i = 0; i < results.Length; i++)
            {
                if (!results[i])
                {
                    ret++;
                }
            }

            Console.WriteLine(ret);
        }
    }
}


Measured memory_bytes: 45624
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

string s;

void solve() {
    rep(i, s.length() - 1) {
        if (s[i] == s[i + 1]) {
            printf("%lli %lli", i + 1, i + 2);
            return;
        }
    }
    rep(i, s.length() - 2) {
        if (s[i] == s[i + 2]) {
            printf("%lli %lli", i + 1, i + 3);
            return;
        }
    }
    printf("%d %d", -1, -1);
}

int main() {
    cin >> s;
    solve();
    return 0;
}

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

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;
const int N = 20+10;

int c[N][N], a[N];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(false); cout.tie(false);
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    ll ans = 0;
    int tmp;
    for(int i = 0; i < n; ++i) cin >> tmp, ans += tmp;
    for(int i = 1; i < n; ++i) cin >> c[i][i+1];
    int last = -1;
    for(int i = 0; i < n; ++i) {
        if(last != -1) ans += c[last][a[i]];
        last = a[i];
    }
    cout << ans << endl;
	return 0;
}


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

const int maxN = 155;

int n, m, mod;
int f[maxN + 1][maxN + 1][maxN + 1], g[maxN + 1][maxN + 1];
int ans;

inline int ADD(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }

inline int solve1()
{
	f[0][0][0] = 1;
	for(int i = 1; i <= m / 2; i++)
	{
		for(int j = 0; j <= i - 1; j++) f[i][0][0] = ADD(f[i][0][0], f[i - 1][0][j]);

		for(int j = 1; j <= i; j++) 
			f[i][0][j] = f[i - 1][0][j - 1];	
	}
	for(int i = m / 2 + 1; i <= n / 2; i++)
	{
		//none
		for(int j = 0; j <= m + 1; j++) 
			for(int k = 0; k <= i - 1; k++)
				f[i][0][0] = ADD(f[i][0][0], f[i - 1][j][k]);
		for(int j = 1; j <= i - m / 2; j++) f[i][0][0] = ADD(f[i][0][0], g[i - 1][j]);
		//left
		g[i][1] = f[i - 1][0][0];
		for(int j = 1; j <= i - 1; j++) g[i][1] = ADD(g[i][1], f[i - 1][0][j]);
		for(int j = 2; j <= i - m / 2; j++) g[i][j] = g[i - 1][j - 1];
		for(int j = 3; j <= m + 1; j++)
			for(int k = 0; k <= i - 1; k++)
				f[i][j][0] = ADD(f[i][j][0], f[i - 1][j - 1][k]);
		//right
		for(int j = 0; j <= m + 1; j++) f[i][0][1] = ADD(f[i][0][1], f[i - 1][j][0]);
		for(int j = 1; j <= i - m / 2 - 1; j++) f[i][0][1] = ADD(f[i][0][1], g[i - 1][j]);
		for(int j = 2; j <= i; j++) 
		{
			f[i][0][j] = f[i - 1][0][j - 1];
			for(int k = 2; k <= m + 1; k++) f[i][0][j] = ADD(f[i][0][j], f[i - 1][k][j - 1]);
		}
		//both
		f[i][2][1] = f[i - 1][0][0];
		for(int j = 1; j <= i - m / 2 - 1; j++) f[i][2][1] = ADD(f[i][2][1], g[i - 1][j]);
		for(int j = 3; j <= m + 1; j++)
		{
			f[i][j][j - 1] = f[i - 1][0][j - 2];
			for(int k = 1; k <= i; k++) f[i][j][k] = ADD(f[i][j][k], f[i - 1][j - 1][k - 1]);
		}
	}
	int last = n - n / 2 + m / 2;
	for(int i = n / 2 + 1; i <= last; i++)
	{
		for(int j = 0; j <= m + 1; j++) 
			for(int k = 0; k <= n / 2; k++)
				f[i][0][0] = ADD(f[i][0][0], f[i - 1][j][k]);
		for(int j = 1; j <= i - m / 2; j++) f[i][0][0] = ADD(f[i][0][0], g[i - 1][j]);

		g[i][1] = f[i - 1][0][0];
		for(int j = 1; j <= i - 1; j++) g[i][1] = ADD(g[i][1], f[i - 1][0][j]);
		for(int j = 2; j <= i - m / 2; j++) g[i][j] = g[i - 1][j - 1];
		for(int j = 3; j <= m + 1; j++)
			for(int k = 0; k <= i - 1; k++)
				f[i][j][0] = ADD(f[i][j][0], f[i - 1][j - 1][k]);
	}
	int ans = f[last][0][0];
	for(int j = 1; j <= n / 2; j++) ans = ADD(ans, f[last][0][j]);
	for(int i = 2; i <= m + 1; i++) 
		for(int j = 0; j <= n / 2; j++) ans = ADD(ans, f[last][i][j]);
	for(int i = 1; i <= n - n / 2; i++) ans = ADD(ans, g[last][i]);
	return ans;
}

inline int solve2(int n)
{
	memset(g, 0, sizeof(g));
	int ans = 1;
	g[0][0] = 1;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j <= min(i - 1, m / 2); j++) g[i][0] = ADD(g[i][0], g[i - 1][j]);
		for(int j = 1; j <= min(i, m / 2); j++)
			g[i][j] = g[i - 1][j - 1], ans = ADD(ans, g[i][j]);
	}
	return ans;
}

int main()
{
	scanf("%d %d %d", &n, &m, &mod);
	if(m & 1) printf("%d", solve1());
	else printf("%d", 1ll * solve2(n / 2) * solve2(n - n / 2) % mod);
	return 0;
}

Measured memory_bytes: 12672
#include<bits/stdc++.h>
using namespace std;
int n, a[500100], f[500100];
char s[500100];

int main() {
	scanf("%d%s", &n, s + 1);
	for(int i = 1; i <= n; i++) {
		a[i] = s[i] - '0';
	} 
	for(int i = 3, lp = 0; i <= n; i++) {
		f[i] = f[i - 1];
		if(a[i] && !a[i - 1] && a[i - 2]) {
			lp = i;
			for(int j = i - 2; a[j] && j >= 1; j--) {
				f[i] = max(f[i], f[j - 1] + i - j - 1);
			}
		}
		if(!a[i]) lp = 0;
		if(a[i] && lp) f[i] = max(f[i], f[lp - 3] + i - lp + 1);
		//printf("%d %d\n", i, f[i]);
	}
	printf("%d\n", f[n]);
}





Measured memory_bytes: 4608
#!/usr/bin/python
# coding: utf-8

# AtCoder Beginner Contest 074
# C - Sugar Water

from sys import stdin

# @param A  水を100 * Aまたは100 * Bだけ増やせる.
# @param B
# @param C  砂糖をCまたはDだけ増やせる.
# @param D
# @param E  水100gに対する最大砂糖量
# @param F  ビーカーの容量
# @return (砂糖水の量, 砂糖の量)

def solve(A, B, C, D, E, F):
  max_concent = (0, 0, 0)  # (濃度, 砂糖水, 砂糖)
  for wa in range(0, F + 1, 100 * A):   # 操作1の水の量
    for w in range(wa, F + 1, 100 * B): # 水の量
      cap = min(F - w, E * w // 100)    # 加えることができる砂糖の量
      for sc in range(0, cap + 1, C):   # 操作3の砂糖の量
        for s in range(sc, cap + 1, D): # 砂糖の量
          concent = 100.0 * s / (s + w) if s > 0 else 0.0  # 濃度
          max_concent = max(max_concent, (concent, s + w, s))
  return max_concent[1:]

A, B, C, D, E, F = [int(w) for w in stdin.readline().split()]
print('%d %d' % solve(A, B, C, D, E, F))

Measured memory_bytes: 2948
#include <iostream>

using namespace std;

int main() {
    int A, B;
    cin >> A >> B;
    for (int i = 1; i <= 2000; i++) {
        if ((int) (i * 0.08) == A && (int) (i * 0.1) == B) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 888
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

using namespace std;

typedef long long ll;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>pb_ds;

#define IN freopen("in.txt","r",stdin)
#define OUT freopen("out.txt","w",stdout)
#define pi pair<int,int>
#define F first
#define S second
#define pb push_back
#define pp pop_back
#define mod 1000000007
#define pai acos(-1)
#define N 1005

int r,c;
int fx[]={-1,1,0,0};
int fy[]={0,0,1,-1};

bool valid(int x,int y){
   return x>=1&&x<=r&&y>=1&&y<=c;
}

int main ()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int n,m,k,sx,sy,dx,dy;
   cin>>n>>m>>k>>sx>>sy>>dx>>dy;
   r=n,c=m;
   char s[n+5][m+5];
   int dis[n+5][m+5];
   for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++){
         cin>>s[i][j];
         dis[i][j]=INT_MAX;
      }
   }
   queue<pi>q;
   if(s[sx][sy]=='.') q.push({sx,sy}),dis[sx][sy]=0;
   while(!q.empty()){
      pi u=q.front();q.pop();
      for(int i=0;i<4;i++){
         for(int j=1;j<=k;j++){
            int nx=u.F+fx[i]*j;
            int ny=u.S+fy[i]*j;
            if(!valid(nx,ny)||s[nx][ny]=='@'||dis[nx][ny]<=dis[u.F][u.S]) break;
            if(dis[nx][ny]>dis[u.F][u.S]+1){
               dis[nx][ny]=dis[u.F][u.S]+1;
               q.push({nx,ny});
            }
         }
      }
   }
   int ans=(dis[dx][dy]==INT_MAX)?-1:dis[dx][dy];
   cout<<ans<<endl;
   return 0;
}



Measured memory_bytes: 9048
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a,b; cin>>a>>b;
  for (int i=0;i*i<=stoi(a+b);i++){
    if(i*i==stoi(a+b)){
    	cout<<"Yes"<<endl;
      	return 0;
    }
  }
  cout<<"No"<<endl;
}


Measured memory_bytes: 256
// AGC32-A
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
namespace you {
    std::string to_string(char val) {
        return std::string(1, val);
        // return std::string{val};
        // you::to_string(char)
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    int n;
    cin>>n;
    vector<int> num(n+1);
    rep(i,n) cin>>num[i+1];
    deque<int> sosa;
    vector<bool> seen(n+1,false); //trueだともう取り除いてる
    int see=0;
    bool flag=true;
    while(see<n){
        int ind=0; //残っているやつで何番目か
        int del=0; //消せるやつ
        for(int i=1;i<=n;i++){
            if(seen[i]==false) ind+=1;
            else continue;
            if(ind==num[i]) del=i;
        }
        if(del!=0){
            seen[del]=true;
            sosa.push_back(num[del]);
            see+=1;
        }else{
            flag=false;
            break;
        }
    }
    if(flag){
        rep(i,n){
            int a=sosa.back();
            cout<<a<<endl;
            sosa.pop_back();
        }
    }else cout<<-1<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;

int N; char S[303][303];

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%s", S[i]);

	int ans = 0;
	for (int k = 0; k < N; k++) {
		bool g = 1;
		for (int i = 0; i < N; i++) for (int j = i; j < N; j++) if (S[(i + N - k) % N][j] != S[(j+N-k)%N][i]) g = 0;
		if (g) ans += N - k;
		if (k == 0) continue;
		g = 1;
		for (int i = 0; i < N; i++) for (int j = i; j < N; j++) if (S[i][(j + N - k) % N] != S[j][(i+N-k)%N]) g = 0;
		if (g) ans += N - k;
	}
	printf("%d\n", ans);

	return 0;
}

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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vector<int>> mi;
typedef vector<vector<pair<int, int>>> w_graph;
typedef vector<vector<int>> uw_graph;




int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef DEBUG
	freopen("out.txt", "w", stdout);
#endif
	  
   int n, k;
   cin >> n >> k;
   vi a(n);
   for (int i = 0; i < n; i++) cin >> a[i];
   bool dp[2][(int)1e5 + 5];
   dp[0][0] = false;
   dp[1][0] = false;
   
   for (int i = 1; i <= k; i++){
   	  bool ft = true;
   	  for (int j = 0; j < n; j++){
  	  	  if (i >= a[j])
	  	  	 ft &= dp[1][i - a[j]];
   	  }
   	  
   	  dp[0][i] = !ft;
   	  
   	  bool sc = true;
   	  for (int j = 0; j < n; j++){
  	  	  if (i >= a[j])
	  	  	 sc &= dp[0][i - a[j]];
   	  }
   	  
   	  dp[1][i] = !sc;
   }

   cout << (dp[0][k] ? "First" : "Second") << endl;

   return 0;
}


Measured memory_bytes: 512
#include <stdio.h>


int main(void)
 {

	int a,b,c;
	int num1, num2 =0;

	scanf("%d %d %d", &a, &b, &c);
	for(num1 =a;num1<=b;num1++){



		if(c%num1==0){

			num2++;

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

	return 0;

}

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

int main(){
  string s;cin >> s;
  ll cnt = 0;
  rep(i,s.size()) cnt += s.at(i)-'0';
  if( cnt%9 == 0 )
    cout << "Yes" << endl;
  else 
    cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3760
#include <stdio.h>
int main(){
  int n,s,i,min=1000,max=3,sum=0,ave;
  while(1){
    scanf("%d",&n);
    if(n==0){
      break;
    }
    for(i=0;i<n;i++){
      scanf("%d",&s);
      if(s<min){
    min=s;
      } 
      if(s>max){
    max=s;
      }
      sum=sum+s;
    }
    sum=sum-max-min;
    ave=sum/(n-2);
    printf("%d\n",ave);
    sum=0;
    min=1000;
    max=3;
  }
  return 0;
}

Measured memory_bytes: 1024
#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 md = (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(){
	int a,b;
	string s;
	cin >>a >>b;
	if(a >8 || b>8) puts(":(");
	else puts("Yay!");;
	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<numeric>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
int abc[300000];
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	int X = 0, Y = 0, A = 0, B = 0, C = 0;
	while ((ct = getchar_unlocked()) >= '0') X = X * 10 + ct - '0';
	while ((ct = getchar_unlocked()) >= '0') Y = Y * 10 + ct - '0';
	while ((ct = getchar_unlocked()) >= '0') A = A * 10 + ct - '0';
	while ((ct = getchar_unlocked()) >= '0') B = B * 10 + ct - '0';
	while ((ct = getchar_unlocked()) >= '0') C = C * 10 + ct - '0';

	auto a = abc;
	auto b = abc + A;
	auto c = abc + A + B;

	int k = 0;
	int M = A + B + C;
	while (k < M) {
		int yoyuu = (cm - (ci - cn)) / 11;
		chmin(yoyuu, M - k);
		if (yoyuu > 100) {
			rep(i, yoyuu) {
				while ((ct = *ci++) >= '0') abc[k] = abc[k] * 10 + ct - '0';
				k++;
			}
		}
		else {
			auto tmp = ci;
			while (k < M) {
				abc[k++] = getint();
				if (tmp - ci < 0) break;
				tmp = ci;
			}
		}
	}

	nth_element(a, b - X, b);
	nth_element(b, c - Y, c);
	if (X + Y > B) memcpy(b, b - X, (B - Y) * sizeof(int));
	else memcpy(c - X - Y, b - X, X * sizeof(int));
	nth_element(c - X - Y, c + C - X - Y, c + C);

	ll kotae = accumulate(c + C - X - Y, c + C, 0ll);
	//for (auto kari = c + C - X - Y; kari < c + C; kari++) kotae += *kari;
	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n;
double dp[305][305][305];
bool chk[305][305][305];
double go(int x,int y,int z) {
	if(!x&&!y&&!z) return 0;
	double& ret=dp[x][y][z];
	if(chk[x][y][z]) return ret;
	chk[x][y][z]=1;
	double t=0;
	if(x) t+=1.0*x/n*(go(x-1,y,z)+1);
	if(y) t+=1.0*y/n*(go(x+1,y-1,z)+1);
	if(z) t+=1.0*z/n*(go(x,y+1,z-1)+1);
	int w=n-x-y-z;
	if(!w) return ret=t;
	return ret=(1+t)/(1-1.0*w/n)-1;
}
int main() {
	int x=0,y=0,z=0;
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++) {
		int u;
		scanf("%d",&u);
		if(u==1)x++;
		else if(u==2)y++;
		else if(u==3)z++;
	}
	printf("%.10f",go(x,y,z));
	return 0;
}

Measured memory_bytes: 246016
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5005;
const int mod = 1e9 + 7;

int n, E;
int fa[N], siz[N];
int fir[N], nex[N << 1], arr[N << 1];
LL g[N], tmp[N][2], f[N][N][2];

inline void Add_Edge(int x, int y) {
	nex[++E] = fir[x];
	fir[x] = E; arr[E] = y;
}

void Solve(int x) {
	siz[x] = f[x][1][0] = 1;
	for (int i = fir[x]; i; i = nex[i]) {
		if (arr[i] == fa[x]) continue;
		fa[arr[i]] = x;
		Solve(arr[i]);
		for (int j = 1; j <= siz[x] + siz[arr[i]]; ++j) tmp[j][0] = tmp[j][1] = 0;
		for (int j = 1; j <= siz[x]; ++j) {
			for (int k = 1; k <= siz[arr[i]]; ++k) {
				for (int l = 0; l < 2; ++l) {
					tmp[j + k][l] += f[arr[i]][k][0] * f[x][j][l];
					tmp[j + k][l] += f[arr[i]][k][1] * f[x][j][l ^ 1];
					tmp[j][l] += f[arr[i]][k][0] * f[x][j][l ^ 1] % mod * g[k];
					tmp[j][l] += f[arr[i]][k][1] * f[x][j][l] % mod * g[k];
					tmp[j][l] %= mod;
					tmp[j + k][l] %= mod;
				}
			}
		}
		for (int j = 1; j <= siz[x] + siz[arr[i]]; ++j) {
			f[x][j][0] = tmp[j][0];
			f[x][j][1] = tmp[j][1];
		}
		siz[x] += siz[arr[i]];
	}
}

int main() {
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int x, y; scanf("%d%d", &x, &y);
		Add_Edge(x, y); Add_Edge(y, x);
	}
	g[0] = 1;
	for (int i = 1; i <= n; ++i) {
		if (i & 1) g[i] = 0;
		else g[i] = g[i - 2] * (i - 1) % mod;
	}
	LL ans = 0;
	Solve(1);
	for (int i = 1; i <= n; ++i) {
		ans += f[1][i][0] * g[i];
		ans -= f[1][i][1] * g[i];
		ans %= mod;
	}
	cout << (ans + mod) % mod << endl;
	return 0;
}


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

int main() {
 
  int A,B;
  cin >> A >> B;
  
  vector<int> N(5);
  
  int ans=0;
  for(int i=A; i<B+1; i++){
    int t=i;
    for(int j=0; j<5; j++){
      N.at(j) = t % 10;
      t/=10;
    }
    
    if(N.at(0) == N.at(4) && N.at(1) == N.at(3)){
      ans++;
    }
  }
  
 cout << ans << endl;
  
}


Measured memory_bytes: 3584
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

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

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> myds;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define F first
#define S second
#define vec(x) vector<x> 
#define pi(x,y) pair<x,y>
#define pqq(x) priority_queue<x> 
#define min_heap(x) priority_queue<x, vector<x>, greater<x> >
#define all(x) x.begin(),x.end()
#define rep(i,x,y) for(int i=x;i<y;i++)
#define repd(i,x,y,k) for(int i=x;i<y;i+=k)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define rev(x) reverse(all(x))
#define uniq(x) x.resize(distance(x.begin(),unique(all(x))))
#define full(x,a) memset(x,a,sizeof(x))
#define lcm(x,y) ((x*y)/__gcd(x,y))
#define mod 1000000007
#define bitcount __builtin_popcountll
#define pb push_back
#define indexof order_of_key
#define valueat find_by_order

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int dxx[8]={0,0,1,-1,-1,-1,1,1};
int dyy[8]={1,-1,0,0,-1,1,1,-1};

int gcdextended(int a,int b,int &x,int &y){if(!a){x=0,y=1;return b;}int x1,y1;int ans=gcdextended(b%a,a,x1,y1);x=y1-(b/a)*x1;y=x1;return ans;}
int inv(int a){int x,y;int ans=gcdextended(a,mod,x,y);return(x%mod+mod)%mod;}
int nCr(int n,int k){int res=1;k=(k>n-k)?n-k:k;rep(i,0,k){res*=(n-i);res/=(i+1);}return res;}
int POW(int x,int y){int res=1;x=x%mod;while(y>0){if(y&1)res=(res%mod*x)%mod;y=y>>1;x=(x*x)%mod;}return res;}
//void seive(){prime[0]=0;prime[1]=0;rep(i,2,10002)prime[i]=1;for(int i=2;i*i<=10000;i++){if(prime[i]){for(int j=i*i;j<=10000;j+=i)prime[j]=0;}}} 

const int N = 100005;

int n1,n2,m;
int a[N],b[N];
int ans=INT_MAX;

void input(){
    cin>>n1>>n2>>m;
    rep(i,1,n1+1)
        cin>>a[i];
    rep(i,1,n2+1)
        cin>>b[i];
    ans=*min_element(a+1,a+n1+1)+*min_element(b+1,b+n2+1);
}

void solve(){
    rep(i,0,m){
        int x,y,c;
        cin>>x>>y>>c;
        ans=min(ans,a[x]+b[y]-c);
    }
    cout<<ans<<endl;
}

main(){
    fastio;
    int t=1;
    while(t--){
        input();
        solve();
    }
}

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

long long gcd(long long a, long long b){
    if(a < b){
        swap(a, b);
    }
    long long r = a % b;
    while(r){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

int main(){
    long long k;
    cin >> k;

    long long ans = 0;
    for(long long h = 1; h <= k; h++){
        for(long long i = 1; i <= k; i++){
            long long tmp = gcd(h, i);
            for(long long j = 1; j <= k; j++){
                ans += gcd(tmp, j);
            }
        }
    }

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

Measured memory_bytes: 3624
N, D = gets.split.map(&:to_i)
Xs = Array.new(N)
Ys = Array.new(N)
As = Array.new(N)
D2 = D ** 2
counter = 0
N.times do |i|
  Xs[i], Ys[i] = gets.split.map(&:to_i)
  d2 = Xs[i] ** 2 + Ys[i] ** 2
  counter += 1  if d2 <= D2
end

puts counter


Measured memory_bytes: 19180
#include <iostream>
#include <iomanip>
#include <vector>
typedef long long ll;
using namespace std;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> A(n, vector<int>(n, -1));
    repi(i, n, 0)
    {
        int a;
        cin >> a;
        repi(j, a, 0)
        {
            int x, y;
            cin >> x >> y;
            --x;
            A[i][x] = y;
        }
    }
    int ans = 0;
    for (int bit = 0; bit < (1 << n); bit++)
    {
        vector<int> d(n);
        repi(i, n, 0)
        {
            if (bit & (1 << i))
            {
                d[i] = 1;
            }
        }
        bool ok = true;
        repi(j, n, 0)
        {
            if (d[j])
            {
                repi(k, n, 0)
                {
                    if (A[j][k] == -1)
                        continue;
                    if (A[j][k] != d[k])
                        ok = false;
                }
            }
        }

        if (ok)
            ans = max(ans, __builtin_popcount(bit));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
def rec(x,y,t):
    global ans
    if t >= ans: return
    if field[y][x] == 3: ans = min(ans,t)
    for dx,dy in zip([1,0,-1,0],[0,1,0,-1]):
        nx,ny = x+dx,y+dy
        while 0 <= nx < W and 0 <= ny < H:
            if field[ny][nx] == 3:
                rec(nx,ny,t+1)
            if field[ny][nx] == 1:
                if abs(nx-x)+abs(ny-y) == 1: break
                field[ny][nx] = 0
                rec(nx-dx,ny-dy,t+1)
                field[ny][nx] = 1
                break
            nx += dx; ny += dy

while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    field = [map(int,raw_input().split()) for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if field[y][x] == 2: sx,sy = x,y
    ans = 11
    rec(sx,sy,0)
    print ans if ans <= 10 else -1

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

#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define ll long long
#define MOD 1000000007
#define N 106

using namespace std;

ll n, ans;

struct Node {

    ll x, y, z;

} node[N];

double res;

void search(ll, ll, ll);
bool cmp(Node, Node);

int main() {

    scanf ("%d", &n);

    rep (i, 1, n) scanf("%lld%lld", &node[i].x, &node[i].y);

    rep (i, 1, 1000) {
        srand(56527);
        rep (k, 1, n) node[k].z = rand();
        sort(node + 1, node + n + 1, cmp);
        search(1, 0, 0);
    }

    res = sqrt(ans);

    printf("%.13lf\n", res);

    return 0;
}

void search(ll j, ll u, ll v) {
    if (j > n) {
        ans = max(ans, u * u + v * v);
        return;
    }
    if (j <= 10 || u * u + v * v <=
            (u + node[j].x) * (u + node[j].x) + (v + node[j].y) * (v + node[j].y))
        search(j + 1, u + node[j].x, v + node[j].y);
    if (j <= 10 ||
            u * u + v * v > (u + node[j].x) * (u + node[j].x) + (v + node[j].y) * (v + node[j].y))
        search(j + 1, u, v);
}

bool cmp(Node u, Node v) { return u.z < v.z; }


Measured memory_bytes: 384
# スペース区切りの整数の入力
a, b, c, d = map(int, input().split())
i = 0

if abs(a - b) <= d and abs(b - c) <= d:
    i += 1

if abs(a - c) <= d:
    i += 1

# 出力
if i == 0:
    print("No")
else: 
    print("Yes")

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

int main(){
    ll h, w;
    cin >> h>>w;
    if(h==1||w==1){
        cout << 1 << endl;
        return 0;
    }
    if (h * w % 2 == 0){
        cout << h * w / 2 << endl;
    }
    else{
        cout << h * w / 2 + 1 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
//	freopen("text.out","w",stdout);
	long long a,b;
	scanf("%lld %lld",&a,&b);
	if((a+b)/2.0==(a+b)/2)
	printf("%lld",(a+b)/2);
	else
	printf("IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import heapq

N, D, A = map(int, readline().split())
m = map(int,read().split())
XH = list(zip(m,m))
heapq.heapify(XH)
width = 2*D

ans = 0
while len(XH) != 0:
  xh_min = heapq.heappop(XH)
  # left + D の位置で攻撃する
  left = xh_min[0]
  right = left + width
  nAttack = (xh_min[1] + A - 1) // A
  damage = nAttack * A
    
  target = []
  while len(XH) != 0:
    xh = heapq.heappop(XH)
    if xh[0] <= right:
      if xh[1] > damage:
        target.append(xh)
    else:
      heapq.heappush(XH, xh)
      break
  if len(XH) == 0:
    maxH = xh_min[1]
    if len(target):
      maxH = max(xh_min[1], max([t[1] for t in target]))
    nAttack = (maxH + A - 1) // A
    ans += nAttack
  else:
    ans += nAttack
    for t in target:
      heapq.heappush(XH, (t[0], t[1] - damage))
  
print(ans)


Measured memory_bytes: 113396
#include <bits/stdc++.h>
#define cinf(n,x,y) for(int i=0;i<(n);i++) cin >> x[i]>>y[i];
typedef long long int ll;
using namespace std;

int main(){
	ll n; cin >>n;
	vector<ll>t(n),a(n);
	cinf(n,t,a);
	ll ansa=1;ll ansb=1;
	for(int i=0;i<n;i++){
		ll x=max((ansa+t[i]-1)/t[i],(ansb+a[i]-1)/a[i]);
		ansa=x*t[i];ansb=x*a[i];
	}
	cout <<ansa+ansb <<endl;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF=1e9;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
 
int main(){
  string s;
  cin>>s;
  vector<int> a(len(s)+1,0);
  rep(i,len(s)){
    if(s[i]=='<'){
      a[i+1]=a[i]+1;
    }
  }
  for(int i=len(s)-1;i>=0;i--){
    if(s[i]=='>'){
      a[i]=max(a[i+1]+1,a[i]);
    }
  }
  ll ans=0;
  rep(i,len(s)+1){
    ans+=a[i];
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 5720
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

int N;
string S;

const long long int MOD = 1000000007;

int main() {
  cin >> N >> S;

  unordered_map<char, int> map;
  for (int i = 0; i < N; i++) {
    if (map.find(S[i]) == map.end()) {
      map[S[i]] = 1;
    } else {
      map[S[i]]++;
    }
  }

  long long int res = 1;
  for (auto it = map.begin(); it != map.end(); it++)
    res = (res * (it->second + 1)) % MOD;
  res--;
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 3704
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
int a[100010],cnt[100010][2];
int w[2][2],p[2][2];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int u1=0,u2=0;
	for(int i=1;i<=n;i++)cnt[a[i]][i%2]++;
	for(int i=1;i<=n;i++)
	{
		if(p[i%2][0]<cnt[a[i]][i%2])
		{
			w[i%2][1]=w[i%2][0],p[i%2][1]=p[i%2][0];
			w[i%2][0]=a[i],p[i%2][0]=cnt[a[i]][i%2];
		}
		else if(p[i%2][1]<cnt[a[i]][i%2] && a[i]!=w[i%2][0])w[i%2][1]=a[i],p[i%2][1]=cnt[a[i]][i%2];
	}
	int ans=0;
	if(w[0][0]==w[1][0])ans=min(n/2-p[0][0]+n/2-p[1][1],n/2-p[0][1]+n/2-p[1][0]);
	else ans=n/2-p[0][0]+n/2-p[1][0];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1280
#![allow(unused)]

//
// Based on EbTech's Scanner https://stackoverflow.com/q/56449027
//
struct Scanner<'a, R: std::io::BufRead> {
    reader: R,
    buf: String,
    iter: std::str::SplitWhitespace<'a>,
}

impl<'a, R: std::io::BufRead> Scanner<'a, R> {
    fn new(reader: R) -> Self {
        Self { reader, buf: String::new(), iter: "".split_whitespace() }
    }

    fn get_str(&mut self) -> &str {
        if let Some(t) = self.iter.next() {
            return t;
        }
        self.buf.clear();
        self.reader.read_line(&mut self.buf).expect("I/O error");
        self.iter = unsafe { std::mem::transmute(self.buf.split_whitespace()) };
        self.get_str()
    }

    fn get<T: std::str::FromStr>(&mut self) -> T {
        self.get_str().parse().ok().expect("Parse error")
    }
}

fn main() {
    let stdin = std::io::stdin();
    solve(Scanner::new(stdin.lock()));
}

const M: i64 = 998244353;

fn mod_inverse(mut a: i64, m: i64) -> i64 {
    use std::mem::swap;

    let mut b = m;
    let mut u = 1;
    let mut v = 0;

    while b > 0 {
        let mut t = a / b;
        a -= t * b;
        swap(&mut a, &mut b);
        u -= t * v;
        swap(&mut u, &mut v);
    }

    u %= m;
    return if u < 0 { u + m } else { u };
}

fn solve<R: std::io::BufRead>(mut sc: Scanner<R>) {
    let n: i64 = sc.get();
    let m: i64 = sc.get();
    let k: i64 = sc.get();

    if m == 1 {
        println!("{}", if k == n - 1 { 1 } else { 0 });
    } else {
        let m_minus_1_inv = mod_inverse(m - 1, M);
        let ans = (0..=k)
            .scan(
                (0..(n - 1)).fold(m, |a, _| a * (m - 1) % M),
                |a, i| {
                    let a_ = *a;
                    *a = *a * m_minus_1_inv % M
                            * (n - (i + 1)) % M
                            * mod_inverse(i + 1, M) % M;
                    Some(a_)
                })
            .fold(0, |a, x| (a + x) % M);
        println!("{}", ans);
    }
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using pii = pair<int, int>;

void Main(){
	int n; 
	cin >> n;
	vector<string> s(n);
	set<string> st;
  	rep(i,n) {
      string s;
      cin >> s;
      st.insert(s);
    }
    cout << st.size() << endl; 

	return;
}

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


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

int main() {
  int N;
  cin >> N;
  vector<int> mochi(N);
  int tall = 0;
  for (int i = 0; i < N; i++) {
    cin >> mochi.at(i);
    int m = mochi.at(i);
    bool isUniq = true;
    for (int j = 0; j < i ; j++) {
      int mm = mochi.at(j);
      if (m == mm) {
        isUniq = false;
      }
    }
    if (isUniq) {
      tall++;
    }
  }
  cout << tall << endl;
}


Measured memory_bytes: 256
import math


def cosin_fomula(a, b, cos:float):
    c = a**2 + b**2 - 2*a*b*cos
    return math.sqrt(c)


A, B, H, M = map(int, input().split())

short_m = 360 / 60
long_m = 360 / (12 * 60)

all_minute = H * 60 + M

degree_short = (short_m * all_minute) % 360
degree_long = (long_m * all_minute) % 360
degree_between = abs(degree_short - degree_long)
cos = math.cos(math.radians(degree_between))
print(cosin_fomula(A, B, cos))


Measured memory_bytes: 9464
#include<stdio.h>

int main(){
    int m,f,r;
    int i=0;
    char seiseki[50];
    
    while(1){
        scanf("%d %d %d",&m,&f,&r);
        if(m==-1 && f==-1 && r==-1)break;

        if(m==-1 || f==-1)seiseki[i]='F';

        else if(m+f>=80)seiseki[i]='A';
        else if(m+f>=65 && m+f<80)seiseki[i]='B';
        else if((m+f>=50 && m+f<65) || (m+f>=30 && m+f<50)&&r>=50)seiseki[i]='C';
        else if(m+f>=30 && m+f<50)seiseki[i]='D';
        else if(m+f<30)seiseki[i]='F';
        i++;
    }
    for(int j=0; j<i; j++)printf("%c\n",seiseki[j]);
    return 0;
}


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

int main(){
  int N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
  int NA, NC;
  NA = (N + A - 1) / A;
  NC = (N + C - 1) / C;
  int ans;
  if(NA*B <= NC*D){
    cout << NA*B << endl;
  }else{
    cout <<  NC*D << endl;
  }
}



Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int k;
	string s;
	cin>>k>>s;
	if(s.length()<=k)
		cout<<s<<"\n";
	else
		cout<<s.substr(0,k)<<"...\n";
}

Measured memory_bytes: 3652
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<climits>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<map>

using namespace std;

int main(){
	int d,n;
	cin>>d>>n;
	if(n==100)
		n=101;
	cout<<n*(int)pow(100,d);
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
template <class T> inline bool chmin(T& a, T b) {
  if(a > b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  int N;
  cin >> N;
  vector<ll> bs(N, 0);
  ll a;
  for(ll i = 1; i <= N; ++i) {
    cin >> a;
    bs[i - 1] = a - i;
  }
  sort(bs.begin(), bs.end());
  ll b = bs[N / 2];
  ll ans = 0;
  for(int i = 0; i < bs.size(); ++i) {
    ans += abs(bs[i] - b);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
N = int(input())
list = []
for i in range(N):
    L = input().split()
    list.append([i+1, L[0], int(L[1])])

list.sort(key = lambda x:x[2], reverse=True)
list.sort(key = lambda x:x[1])

for k in range(N):
    print(list[k][0])

Measured memory_bytes: 3060
/* 
 * File:   main.c
 * Author: s1252007
 *
 * Created on July 30, 2018, 8:22 PM
 */

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INF 100000000
#define NIL -1

/*
 * 
 */

int M[MAX][MAX], d[MAX], pi[MAX], color[MAX];
int n, u, r, mincost;
int sum = 0;

int prim(int r);

int main(int argc, char** argv) {
    int temp;
    scanf("%d", &n);
    
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
        {
            scanf("%d", &temp);
            if (temp == NIL) M[i][j] = INF;
            else M[i][j] = temp;
        }
    
    
    printf("%d\n", prim(0));

    return (EXIT_SUCCESS);
}

int prim(int r)
{
    for (int i = 0; i < n; ++i)
    {
        d[i] = INF;
        pi[i] = NIL;
        color[i] = WHITE;
    }
    
    d[r] = 0;
    
    while (1)
    {
        mincost = INF;
        for (int i = 0; i < n; ++i)
        {
            if (color[i] != BLACK && d[i] < mincost)
            {
                mincost = d[i];
                u = i;
            }
        }
        
        if (mincost == INF) break;
        color[u] = BLACK;
        
        for (int v = 0; v < n; ++v)
        {
            if (color[v] != BLACK && M[u][v] != INF)
            {
                if (M[u][v] < d[v])
                {
                    pi[v] = u;
                    d[v] = M[u][v];
                    color[v] = GRAY;
                }
            }
        }
    }
    
    for (int ix = 0; ix < n; ++ix) if (pi[ix] != NIL) sum += M[ix][pi[ix]];
    
    return sum;
}





Measured memory_bytes: 2088
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.IntStream;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), m = scanner.nextInt();
			// パスの一覧
			@SuppressWarnings("unchecked")
			Set<Integer>[] paths = new Set[n];
			IntStream.range(0, n).forEach(i -> paths[i] = new HashSet<>());
			IntStream.range(0, m).forEach(i -> {
				int a = scanner.nextInt() - 1, b = scanner.nextInt() - 1;
				paths[a].add(b);
				paths[b].add(a);
			});
			System.out.println(getResult(0, paths, ~(0xFFFF_FFFF << n), new HashMap<>()));
		}
	}

	/**
	 * @param startNode アクセス始点
	 * @param paths
	 * @param status    グラフのアクセス済ステータス（nビット目が1＝まだアクセスしていない）
	 * @param map
	 * @return アクセスのパスの数
	 */
	private static int getResult(int startNode, Set<Integer>[] paths, int status, Map<List<Integer>, Integer> map) {
		// 現在のノードが最後のノードの場合
		if (0 == (status & (~(1 << startNode)))) {
			return 1;
		}
		List<Integer> key = Arrays.asList(startNode, status);
		Integer result = map.get(key);
		if (null == result) {
			result = 0;
			// 現在のノードをアクセス済にする
			status &= ~(1 << startNode);
			for (Integer nextNode : paths[startNode]) {
				if ((status & (1 << nextNode)) > 0) {
					result += getResult(nextNode, paths, status, map);
				}
			}
			map.put(key, result);
		}
		return result;
	}
}


Measured memory_bytes: 36464
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T> using vec = std::vector<T>;
using namespace std;

int main() {
  ll N, A;
  cin >> N;
  bitset<1000000001> s;
  REP(i, N) {
    cin >> A;
    s[A] = ~s[A];
  }
  cout << s.count() << endl;
  return 0;
}


Measured memory_bytes: 125660
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define INF 1LL << 60
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i, m) for (long long i = 0; i < m; i++)
#define FOR(i, n, m) for (long long i = n; i < m; i++)
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef long double ld;

int main(){
  int n, m;
  cin >> n >> m;
  pair<P, int> p[m];
  int d[n][n];
  REP(i, n){
    REP(j, n) d[i][j] = 1000000;
  }
  REP(i, m){
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    p[i] = {{a, b}, c};
    d[a][b] = c;
    d[b][a] = c;
  }
  REP(k, n){
    REP(i, n){
      REP(j, n){
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
  int ans = 0;
  REP(i, m){
    if(d[p[i].first.first][p[i].first.second] != p[i].second) ans++;
  }
  cout << ans << endl;
	return 0;
}


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

int n;
double ans=0;

int main(){
    cin >> n;
    int v[n];
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    sort(v, v+n);
    ans = (v[0]+v[1])/2.0;
    for(int i=2; i<n; i++){
        ans=(ans+v[i])/2.0;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
/*
input
atcoder beginner contest

*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a,b;
	cin>>a>>b;
	if(a.size()>b.size())
	cout<<"GREATER\n";
	else if(a.size()<b.size())
		cout<<"LESS\n";
	else 
	{
    if(a>b)
	cout<<"GREATER\n";
	else if(a<b)
		cout<<"LESS\n";
	else cout<<"EQUAL\n";
	}
	return 0;
}

Measured memory_bytes: 256