akhauriyash/Code-Regression huggingface dataset:
from fractions import gcd
from math import sqrt


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def main():
    A, B = map(int, input().split())
    C = gcd(A, B)
    if (C == 1):
        print(1)
        exit(0)
    arr = factorization(C)
    # print(arr)
    print(len(arr) + 1)


if __name__ == "__main__":
    main()


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

typedef long long ll;

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

    int W, H, x, y;
    cin>>W>>H>>x>>y;

    double ans = (double)W*(double)H;
    ans /= 2;

    cout<<ans<<" ";
    if (x+x == W && y+y == H) cout<<"1"<<endl;
    else cout<<"0"<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    int N; cin >> N;
    vector<int> xs(N); for (auto &xi : xs) cin >> xi;
    vector<int> sorted = xs;
    sort(sorted.begin(), sorted.end());
    for (int i = 1; i <= N; ++i)
    {
        if (xs[i - 1] < sorted[N / 2]) cout << sorted[N / 2] << endl;
        else cout << sorted[N / 2 - 1] << endl;
    }
}


Measured memory_bytes: 3712
from collections import defaultdict
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]

# 数字:(縦, 横)で場所を格納
F = defaultdict()
for i in range(H):
    for j in range(W):
        F[A[i][j]] = (i, j)

# コスト
C = [0] * (H*W)
for i in range(H*W):
    if i >= D:
        C[i] = C[i-D] + abs(F[i+1][0] - F[i-D+1][0]) + abs(F[i+1][1] - F[i-D+1][1])

# クエリを受けとってO(1)で計算
Q = int(input())
for q in range(Q):
    L, R = map(int, input().split())
    print(C[R-1] - C[L-1])


Measured memory_bytes: 23720
#include<bits/stdc++.h>
using namespace std;
int main()
{

    string s;
    cin >> s;
    int arr[26] = {0};
    int c =0;
    for(int i =0;i<s.length();++i)
        arr[s[i]-'a']++;
    //for(int i =0;i<26;++i)
           // cout << arr[i] << " ";
    for(int i =0;i<26;++i)
    {
        if(arr[i]%2 != 0)
        {
            if(arr[i]%2 !=0)
            {
                c = 1;
                break;
            }

        }

    }
    if(c == 0)
        cout << "Yes";
    else
        cout << "No";
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SZ = (2 << 16), LG = 18, INF = 1e9 * 1e6;
ll n, m;
ll grid[LG][LG], inter[SZ], dp[SZ], mx[SZ];

int main() {
	fastInp;

	cin >> n >> m;

	for (int i = 0; i < LG; i++) {
		for (int j = 0; j < LG; j++) grid[i][j] = INF;
	}

	ll sum = 0;
	for (int i = 0; i < m; i++) {
		ll u, v, c;
		cin >> u >> v >> c;
		sum += c;
		u--; v--;
		grid[u][v] = c;
		grid[v][u] = c;
	}

	ll pw = (1ll << n);
	for (int i = 0; i < pw; i++) {
		ll cur = 0;
		for (int j = 0; j < n; j++) {
			for (int k = j + 1; k < n; k++) {
				if (((i >> k) & 1) && ((i >> j) & 1) && grid[k][j] != INF) {
					cur += grid[k][j];
				}
			}
		}

		inter[i] = cur;
	}

	for (int i = 0; i < pw; i++) {
		for (int j = 0; j < LG; j++) dp[i] = -INF;
	}

	for (int i = 0; i < LG; i++) dp[(1ll << i)] = 0;
	dp[1] = 0;
	for (int i = 2; i < pw; i++) {
		for (int j = 0; j < LG; j++) {
			for (int k = 0; k < LG; k++) {
				if (j != k && (i & (1ll << k)) && (i & (1ll << j)) && grid[j][k] != INF) {
					ll msk = i ^ (1ll << j);
					dp[i] = max(dp[i], dp[msk] + grid[k][j]);
				}
			}
		}
	}

	ll ans = -INF;

	for (int i = 0; i < pw; i++) {
		if (!(i & 1)) continue;
		if (!((i >> (n - 1)) & 1)) continue;
		for (int sub = i; true; sub = ((sub - 1) & i)) {
			for (int j = 0; j < LG; j++) {
				if ((i >> j) & 1) {
					ll msk = (i ^ sub);
					if ((msk & 1) && ((msk >> (n - 1)) & 1)) dp[i] = max(dp[i], dp[msk] + inter[sub | (1ll << j)]);
				}
			}
			if (sub == 0) break;
		}
		ans = max(ans, dp[i]);
	}

	cout << sum - ans;

	return 0;
}

Measured memory_bytes: 4116
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
cnt = 0
i = 1
if n == 1:
    print(1)
    quit()
elif n == 2:
    print(2)
    quit()
while True:
    cnt += i
    if cnt >= n:
        break
    i += 1
res = []
while n > 0:
    res.append(i)
    n -= i
    i -= 1
    if n > i:
        continue
    res.append(n)
    break
for i in range(len(res))[::-1]:
    print(res[i])

Measured memory_bytes: 42348
#include <iostream>
#include <string>
using namespace std;
/*long long int kaij(int i,long long int j){
  if(i==1) return j;
  j*=(i-1);
  kaij(i-1,j);
}*/
int main(){
  int n;
  cin >> n;
  string s;
  long long int m=0,a=0,r=0,c=0,h=0,ans=0;
  for(int i=0;i<n;i++){
    cin >> s;
    if(s[0]=='M') m++;
    else if(s[0]=='A') a++;
    else if(s[0]=='R') r++;
    else if(s[0]=='C') c++;
    else if(s[0]=='H') h++;
  }
  ans=(m*a*r)+(m*a*c)+(m*a*h)+(m*r*c)+(m*r*h)+(m*c*h)+(a*r*c)+(a*c*h)+(a*r*h)+(r*c*h);
  cout << ans<<endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
//using static System.Globalization.CultureInfo;

class Program
{ 
    static void Main(string[] args)
    {
        var num = Input.num;
        var ar = Input.ar;
        var ps = Enumerable.Range(0, num).Select(v => new[] { v, 0 }).ToArray();
        for (var i = 0; i < num; i++)
            ps[i][1] = ar[i];
        Array.Sort(ar);
        ps = ps.OrderBy(v => v[1]).ToArray();
        for (var i = 1; i <= num; i++)
            if (i <= num / 2) ps[i - 1][1] = ar[num / 2];
            else ps[i - 1][1] = ar[num / 2-1];
        WriteLine(string.Join("\n", ps.OrderBy(v => v[0]).Select(v => v[1])));
    }
}

public class Input
{
    public static string read => ReadLine();
    public  static int[] ar => Array.ConvertAll(read.Split(' '), int.Parse);
    public  static int num => ToInt32(read);
    public static long[] arL => Array.ConvertAll(read.Split(' '), long.Parse);
    public  static long numL => ToInt64(read);
    public static int[][] twodim(int num)
        => Enumerable.Repeat(0, num).Select(v => ar).ToArray();
    public static long[][] twodimL(int num)
        => Enumerable.Repeat(0, num).Select(v => arL).ToArray();
    public const double eps = 1e-11;
    public  const string Alfa = "abcdefghijklmnopqrstuvwxyz";
    public  const int MOD = 1000000007;
}


Measured memory_bytes: 54620
#include <iostream>
using namespace std;
string s;
int ans;
int main()
{
    cin >> s;
    ans = s.size();
    int len=ans;
    for (int i = 0; i < ans; i++)
        if (s[i] != s[i + 1])
            ans = min(ans, max(len - i - 1, i + 1));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 512
/*Remember: The Struggle is Important*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

#include<bits/stdc++.h>
using namespace std;

#define     int          long long int
#define     ld           long double
#define     fast()       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)       x.begin(),x.end()
#define     mem(a,b)     memset(a,b,sizeof(a))
#define     gcd(a,b)     (__gcd((a),(b)))
#define     lcm(a,b)     (((a)*(b))/gcd((a),(b)))
#define     pb           push_back
#define     ins          insert
#define     pii          pair<int,int>
#define     F            first
#define     S            second
#define     show(x)      for(auto c:x)cout<<c<<" ";cout<<"\n";
#define     show2(x)     for(auto c:x)cout<<c.F<<" "<<c.S<<"\n";

const int inf=1e18,M=1e9+7;
const int N=1;

void solve()
{
    int a,b;
    cin>>a>>b;

    int n;
    cin>>n;

    int mx=max(a,b);
    int ans=n/mx+(n%mx!=0);
    cout<<ans;
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



Measured memory_bytes: 256
K = int(input())
if K % 2 == 0 or K % 5 == 0:
    print(-1)
else:
    mod, modt, ans = 7 % K, 7 % K, 1
    while mod != 0:
        modt = (modt * (10 % K)) % K
        mod, ans = (mod + modt) % K, ans + 1
    print(ans)


Measured memory_bytes: 63284
package main

import (
    "fmt"
)

func main() {
  var a, b int
  fmt.Scan(&a, &b)

  if a < b {
    fmt.Println("a < b")
  }
  if a > b {
    fmt.Println("a > b")
  }
  if a == b {
    fmt.Println("a == b")
  }
}


Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
typedef struct x
{
    long long a,b,c,v;
}x;
long long n;
bool cmp(x tmp1,x tmp2)
{
    return tmp1.v<tmp2.v;
}
void solve()
{
    vector < x > a(n);
    long long i,ans=0,sum=0,ans1=0,ans2=0,tag=0;
    for (i=0;i<n;i++)
        cin>>a[i].a;
    for (i=0;i<n;i++)
        cin>>a[i].b;
    for (i=0;i<n;i++)
    {
        a[i].v=a[i].a-a[i].b;
        if (a[i].v<0)
        {
            ans++;
            sum+=abs(a[i].v);
        }
        ans1+=a[i].a;
        ans2+=a[i].b;
    }
    sort(a.begin(),a.end(),cmp);
    for (i=0;i<n;i++)
        if (a[i].v<0) {tag=1;break;}
    if (!tag) cout<<0;
    else
    {
        if (ans1>=ans2)
        {
            for (i=n-1;i>=0;i--)
            {
                if (a[i].v>0)
                {
                    ans++;
                    if (sum>=a[i].v) sum-=a[i].v;
                    else
                    {
                        sum=0;
                        break;
                    }
                }
                else break;
            }
            cout<<ans;
        }
        else cout<<-1;
    }
    cout<<endl;
}
int main()
{
    while(cin>>n)
        solve();
}

Measured memory_bytes: 3328
#include <iostream>
using namespace std;
int main() {
	int n, i, a[100];
	cin >> n;
	for (i = 0; i < n; i++)cin >> a[i];
	for (i = n - 1; i > 0; i--)cout << a[i] << ' ';
	cout << a[0] << endl;
}

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

#define GO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int

const int maxr = 1e5 + 5;


int32_t main()
{
	GO;
	int x;
	cin >> x;
	for (int i = -1000; i <= 1000; i++) {
		for (int j = -1000; j <= 1000; j++) {
			int a = i * i * i * i * i;
			int b = j * j * j * j * j;
			if (a - b == x) {
				cout << i << " " << j << endl;
				return 0;
			}

		}
	}
	return 0;
}

//!

Measured memory_bytes: 3644
s = input()
t = input()

max_tmp = 0
out = 0


def comp(a, b):
    cnt = 0
    for i in range(len(a)):
        if a[i] == b[i]:
            cnt += 1
    return cnt


for i in range(len(s) - len(t) + 1):
    max_tmp = comp(s[i:i + len(t)], t)
    out = max(out, max_tmp)

print(len(t) - out)

Measured memory_bytes: 9048
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main()
{
    int a,b,c;
    cin >> a >> b >> c;
    int i;
    for(i = 1;i <= b;++i){
        if(a*i%b == c){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

#define MAX 500000
#define INFTY 2000000000

int count;

void merge(int [],int,int,int);
void mergeSort(int [],int,int);

int main(){
  int n,i;
  int S[MAX];

  scanf("%d",&n);
  for(i = 0;i <= n-1;i++){
    scanf("%d",&S[i]);
  }
  
  mergeSort(S,0,n);
  
  for(i = 0;i <= n-1;i++){
    if(i != 0){
      printf(" ");
    }
    printf("%d",S[i]);
  }
  
  printf("\n");
  
  printf("%d\n",count);

  return 0;
}


void merge(int S[],int left,int mid,int right){
  int L[MAX / 2 + 2],R[MAX / 2 + 2];
  int n1,n2,i,j,k;
  
  n1 = mid - left;
  n2 = right - mid;
  /*L[0...n1],R[0...n2]を生成*/
  for(i = 0;i <= n1-1;i++){
    L[i] = S[left + i];
  }
  for(i = 0;i <= n2-1;i++){
    R[i] = S[mid + i];
  }
  L[n1] = INFTY;
  R[n2] = INFTY;
  i = 0;
  j= 0;
  for(k = left;k <= right-1;k++){
    count++;
    if (L[i] <= R[j]){
      S[k] = L[i++];
    }
    else{
      S[k] = R[j++];
    }
  }
}

void mergeSort(int S[],int left,int right){
  if(left + 1 < right){
    int mid = (left + right) / 2;
    mergeSort(S,left,mid);
    mergeSort(S,mid,right);
    merge(S,left,mid,right);
  }
}
  



Measured memory_bytes: 5620
/*input
6
3 2 2 2 2 2
1 2
2 3
1 4
1 5
4 6
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <functional>
#include <cmath>
#include <cstring>
#include <utility>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <list>
#include <cstdlib>
#include <list>
#include <cassert>
#include <ctime>
#include <fstream>
#include <sstream>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define N 100005
// const int INF = 1e18;
struct data {
	int x, y, cost;
	data(int _x = 0, int _y = 0, int _cost = 0): x(_x), y(_y), cost(_cost) {};
	int other(data x, int y) {
		if (x.x == y) return x.y;
		else return x.x;
	}
} E;

int n;
vector<vector<int> > a(N);
vector<data> e;
int c[N];

void quit() {
	cout << "NO" << endl;
	exit(0);
}

void dfs(int u, int p) {
	bool leaf = false; if (a[u].size() == 1) leaf = true;
	if (leaf) {
		if (e[a[u][0]].cost == -1) e[a[u][0]].cost = c[u];
		else if (e[a[u][0]].cost != c[u]) quit();
		if (u != 1)
			return;
	}
	int pos = -1;
	int sum = 0;
	for (int i = 0; i < a[u].size(); i++) {
		int v = E.other(e[a[u][i]], u);
		if (v == p) {
			pos = i;
			continue;
		}
		dfs(v, u);
		sum += e[a[u][i]].cost;
	}
	sum = 2 * c[u] - sum;
	if (sum < 0) quit();
	if (u == 1) {
		if (leaf) {
			if (e[a[u][0]].cost != -1 && sum != e[a[u][0]].cost) quit();
		}
		else {
			if (sum != 0) quit();
		}
		return;
	}
	if (e[a[u][pos]].cost != -1 && sum != e[a[u][pos]].cost) quit();
	e[a[u][pos]].cost = sum;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> c[i];
	for (int i = 1; i <= n - 1; i++) {
		int x, y; cin >> x >> y;
		e.push_back(data(x, y, -1));
		a[x].push_back(i - 1);
		a[y].push_back(i - 1);
	}
	dfs(1, 1);
	for (int i = 1; i <= n; i++) {
		if (a[i].size() == 1) continue;
		int sum = 0;
		for (int j = 0; j < a[i].size(); j++) {
			sum += e[a[i][j]].cost;
		}
		for (int j = 0; j < a[i].size(); j++) if (e[a[i][j]].cost > sum / 2) quit();
	}
	cout << "YES" << endl;
}

Measured memory_bytes: 14004
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a); i<(b);++i)
#define rep(i, n) FOR(i, 0, n)

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

// solve

int main(int argc, char const* argv[])
{
  int n, a, b;
  cin >> n >> a >> b;
  int l = 0, m = 0, k = 0;
  rep(i, n){
    int p;
    cin >> p;
    if(p <= a)l++;
    else if(p <= b)m++;
    else k++;
  }
  cout << min(l, min(m, k)) << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
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; }
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)
//printf("%.10f\n",なんちゃら)

int g[15][15];
const int INF = 1001001001;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//素因数分解
vector<pair<ll, int>>factorize(ll n) {
	vector<pair<ll, int>>res;
	for (ll i = 2;i * i <= n;++i) {
		if (n % i)continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1)res.emplace_back(n, 1);
	return res;
}

int bingo[3][3];
int cnt[2][105];
int h, w;
bool flag[110][110];

int main() {
	string s;
	cin >> s;
	int n = s.length();
	map<char, int>mp;
	rep(i, n) {
		char target = s[i];
		mp[target]++;
	}
	bool flag = true;
	for (auto p : mp) {
		int x = p.second;
		if (x % 2 != 0)flag = false;
	}
	if (flag)puts("Yes");
	else puts("No");
	return 0;
}


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

using namespace std;
using ll = long long;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

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

int n;
int imos[86401];
int main() {
    while (cin >> n, n) {
        memset(imos, 0, sizeof(imos));
        int h1, m1, s1;
        int h2, m2, s2;
        rep(i, n) {
            scanf("%d:%d:%d", &h1, &m1, &s1);
            scanf("%d:%d:%d", &h2, &m2, &s2);
            imos[h1 * 3600 + m1 * 60 + s1]++;
            imos[h2 * 3600 + m2 * 60 + s2]--;
        }
        rep(i, 86401) if (i) imos[i] += imos[i - 1];
        cout << *max_element(imos, imos + 86401) << endl;
    }
    return 0;
}

Measured memory_bytes: 3480
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdio>
#include <stack>

using namespace std;

int a[3];
int k = 0;

int main(){
	for (int i = 0; i < 3; ++i) {
		cin >> a[i];
	}
	cin >> k;
	int ans;

	sort(a, a + 3); // 配列

	for (int j = 1; j < k+1; ++j) {
		if (j == 1) {
			ans = a[2] * 2;
		}
		else {
			ans = ans * 2;
		}
	}

	printf("%d", ans + a[0] + a[1]);

	return 0;
}

Measured memory_bytes: 256
import typing
from typing import Deque, Set, Dict

class Island:
    def __init__(self, id: int) -> None:
        self.id: int = id
        self.connection: List['Island'] = []
        self.parent: 'Island' = None
        self.rank: int = 0
    
    def addConnection(self, other: 'Island') -> None:
        self.connection.append(other)
        other.connection.append(self)

    def setAsRoot(self):
        self.parent = self
    
    def setParent(self, other: 'Island') -> None:
        self.parent = other
        self.rank = other.rank +1

class Islands(Dict[int, Island]):
    def __init__(self, num: int):
        for id in range(1, num+1):
            self[id] = Island(id)

def bfs(root: Island, max_depth: int) -> None:
    root.setAsRoot()
    reserved: Deque[Island] = Deque([root])
    seen: Set[int] = {root.id}
    while len(reserved) != 0:
        current: Island = reserved.popleft()
        if current.rank > max_depth:
            break
        for connected in current.connection:
            if connected.id in seen:
                continue
            connected.setParent(current)
            seen.add(connected.id)
            reserved.append(connected)

def main() -> None:
    with open(0) as f:
        N, M = map(int, f.readline().split())
        ab = [map(int, line.split()) for line in f.readlines()]
    #諸島生成
    islands: Islands = Islands(N)
    #諸島間定期便生成
    for a, b in ab:
        islands[a].addConnection(islands[b])
    #bfs
    bfs(islands[1], 2)
    #出力
    print('POSSIBLE' if islands[N].rank in (1, 2) else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

Measured memory_bytes: 168512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)    for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
#define rrep(i, n)   for(int i=(n-1); i>=0; --i)
#define all(v)       v.begin(), v.end()
#define rall(v)      v.rbegin(), v.rend()
#define int          long long
template<typename T>
using vv  = vector<vector<T>>;
using vi  = vector<int>;
using vvi = vector<vector<int>>;
using P   = pair<int, int>;
using ll  = long long;
constexpr ll INF = 1LL << 60;

template<typename T>
using maxHeap = priority_queue<T>;
template<typename T>
using minHeap = priority_queue<T, vector<T>, greater<T>>;

signed main(){

    int x, n;
    cin >> x  >> n;
    vector<int> p(n);
    rep(i, n){
        cin >> p[i];
    }

    sort(all(p));

    if(n == 0){
        cout << x << endl;
        return 0;
    }

    int ans = 300;
    int z = 300;
    int y = 300;
    REP(i, 0, 150){
        if(binary_search(all(p), i)){
            continue;
        }
        //cout << abs(x - i) << endl;
        if(abs(x - i) < y){
            y = abs(x - i);
            ans = i;
        }
        else if(abs(x - i) == y){
            ans = min(ans, i);
        }
        //cout << "asn :" << ans << endl;
    }   

    cout << ans << endl;

    return 0;
}



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

string T;
int main() {
    
    cin >> T;
    int count = 0;
    for (int i = 0; i < T.length(); i++)
    {
        if (T[i] == '?') T[i] = 'D';
        cout << T[i];

    }
    cout << endl;

    //int ans = 0;
    
    
    //cout << ans << endl; 
    return 0;
}

Measured memory_bytes: 3708
import math

while True:
    n = int(input())
    if n == 0:
        break

    s = list(map(int, input().split()))
    m = sum(s) / n
    x = 0
    for i in range(n):
        x += (s[i] - m) ** 2
    print("{:f}".format(math.sqrt(x / n)))



Measured memory_bytes: 5708
#include <iostream>
#include <stdio.h>       // printf,scanf
#include <stdlib.h>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>  //sort,binarySearch
#include <functional> 
#include <iomanip>    // setprecision
#include <utility>    // c+11 Array
#include <set>
#include <sstream>
#include <map>
#include <bits/stdc++.h>
#define MOD (1e+9)+7
#define PI 3.141592653589793238462643383279
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define pb(x) push_back(x)
#define debug(x) cout << #x << " = " << x << endl;
#define debret(x) debug(x) ; return 0;

using namespace std;

int main(void){

    string str;
    int ans[26] = {};

    cin >> str;

    REP(i,str.size()){
        
        if(str[i] == 'a') ans[0]++;
        if(str[i] == 'b') ans[1]++; 
        if(str[i] == 'c') ans[2]++; 
        if(str[i] == 'd') ans[3]++; 
        if(str[i] == 'e') ans[4]++; 
        if(str[i] == 'f') ans[5]++; 
        if(str[i] == 'g') ans[6]++;
        if(str[i] == 'h') ans[7]++;
        if(str[i] == 'i') ans[8]++;
        if(str[i] == 'j') ans[9]++;
        if(str[i] == 'k') ans[10]++;
        if(str[i] == 'l') ans[11]++;
        if(str[i] == 'm') ans[12]++;
        if(str[i] == 'n') ans[13]++;
        if(str[i] == 'o') ans[14]++;
        if(str[i] == 'p') ans[15]++;
        if(str[i] == 'q') ans[16]++;
        if(str[i] == 'r') ans[17]++;
        if(str[i] == 's') ans[18]++;
        if(str[i] == 't') ans[19]++;
        if(str[i] == 'u') ans[20]++;
        if(str[i] == 'v') ans[21]++;
        if(str[i] == 'w') ans[22]++;
        if(str[i] == 'x') ans[23]++;
        if(str[i] == 'y') ans[24]++;
        if(str[i] == 'z') ans[25]++;
    }
    
    REP(i,26){

        if((ans[i]+1) % 2 == 0){
            cout << "No" << endl;
            return 0;
        }
        
    }
    
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define mod 1000000007
#define mk make_pair
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    double a[n+1][n+1];
    double pb[n+1];
    for(int i=1;i<=n;i++)
    cin>>pb[i];
    pb[0]=0;
    for(int i=0;i<=n;i++)
    {
        a[0][i]=0;
    }a[1][0]=1-pb[1];
     for(int i=2;i<=n;i++)
    {
        a[i][0]=(double)((1-pb[i])*a[i-1][0]);
    }a[1][1]=pb[1];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==1&&j==1)
            continue;
            if(i<j)
            a[i][j]=0;
            else
            {
                double t=(1-pb[i]);
                a[i][j]=(double)(a[i-1][j]*t)+(double)(pb[i]*a[i-1][j-1]);
            }
            //cout<<a[i][j]<<" ";
        }//cout<<endl;
    }double ans=0;
   /* for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {cout<<a[i][j]<<" ";}
        cout<<endl;
    }*/
    for(int i=(n/2)+1;i<=n;i++)
    {
        ans+=a[n][i];
        //cout<<a[n][i]<<" "<<i<<endl;
    }
    cout<<setprecision(9) <<ans;
    return 0;
}

Measured memory_bytes: 70656
def has_duplicates(words):
    return len(words) != len(set(words))

def words(n):
    words = []
    for i in range(n):
        w = input()
        words.append(w)
    return words

def shiritori(shiritori_words):
    ans = []
    word = shiritori_words[0]
    end_word = word[len(word) -1]
    for j in range(1, len(shiritori_words)):
        word = shiritori_words[j]
        first_word = word[0]
        if has_duplicates(shiritori_words) or end_word != first_word:
            ans.append("No")
        else:
            ans.append("Yes")
        end_word = word[len(word) - 1]
    return ans
            
        

n = int(input())
shiritori_words = words(n)
ans = shiritori(shiritori_words)
if "No" in ans:
    print("No")
else:
    print("Yes")

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

#define mp make_pair
#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef pair<ll,ll> pll;

char c; 

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> c;
    if ('A' <= c && c <= 'Z')
        cout << "A\n";
    else
        cout << "a\n";
    return 0;
}

Measured memory_bytes: 3636
from collections import deque
H, W = map(int, input().split())  # H行, W列
CY, CX = map(lambda x: int(x)-1, input().split())  # 魔法使いの初期値
DY, DX = map(lambda x: int(x)-1, input().split())  # 目的地
gridgraph = [input() for _ in range(H)]
# print(gridgraph)

q = deque()
q.append((CY, CX))  # スタート地点
# 各頂点について2*2の幅優先する？
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 上下左右
distant = [[10**10]*W for _ in range(H)]
distant[CY][CX] = 0
warp_y = list(range(-2, 3, 1))
warp_x = list(range(-2, 3, 1))
while len(q):
    cy, cx = q.popleft()  # 現在位置
    for dy, dx in adjacent:
        # 新しい位置
        ny = cy+dy
        nx = cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        # 道の場合
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            # 道の場合はコスト0で移動できる
            distant[ny][nx] = distant[cy][cx]
            q.appendleft((ny, nx))
    # 周囲5*5の道に+1で到達する
    for i in warp_y:
        for j in warp_x:
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            else:
                if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                    distant[target_y][target_x] = distant[cy][cx]+1
                    q.append((target_y, target_x))

if distant[DY][DX] == 10**10:
    print(-1)
else:
    print(distant[DY][DX])


Measured memory_bytes: 89304
#include <bits/stdc++.h>
using namespace std;
 
#define   ipr         	pair<int, int>
#define   pb            push_back
#define   ff            first
#define   ss            second
#define   fr(i, j, k)   for (int i = j; i < k; i++)
#define   rf(i, j, k)   for (int i = j; i >= k;i--)
#define   int           long long
#define   ll 			unsigned long long
#define   ld            long double
#define   all(x)        x.begin(), x.end()
#define   rall(x)       x.rbegin(),x.rend()
#define   mp            make_pair
#define   inf           INT_MAX
#define   read_file();	freopen("input.txt", "r", stdin);	freopen("output.txt", "w", stdout);
#define   IOS           std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
const int Maxn  =  10000;
const ld  pi   =  acos(-1);
const int mod =  1000000007;
 
 
template<class T> ostream& operator <<(ostream &out,vector<T> &A){for(auto x:A) out<<x;return out;}
template<class T> ostream& operator <<(ostream &out,set<T> &A){for(auto x:A) out<<x<<" ";return out;}
template <class T1,class T2>T1 powr(T1 a,T2 b){T1 res = 1;fr(i,1,b+1)res = res*a;return res;}
int roundUp(int numToRound, int multiple)
{
 if(multiple == 0)
 {
  return numToRound;
 }

 int roundDown = ( (int) (numToRound) / multiple) * multiple;
 int roundUp = roundDown + multiple; 
 int roundCalc = roundUp;
 return (roundCalc);
}
 

 
int32_t main(){IOS
int n;
cin>>n;
cout<<(n/500)*1000 + ((n%500)/5)*5<<endl;

}

Measured memory_bytes: 256
#include<stdio.h>

void swap(int* a,int x,int y){
	int c;
	c=a[x];
	a[x]=a[y];
	a[y]=c;
	return;
}


int main(){
	int a[4]={0,0,0,0};
	int i,j,k;
	int c;
	for(i=10;i--;){
		scanf("%d",&a[3]);
		if(a[3]>a[2]){
			swap(a,0,1);
			swap(a,1,2);
			swap(a,2,3);
		}else if(a[3]>a[1]){
			swap(a,0,1);
			swap(a,1,3);
		}else if(a[3]>a[0]){
			swap(a,0,3);
		}
	}
	
	for(i=3;i--;){
		printf("%d\n",a[i]);
	}
	return 0;
}

Measured memory_bytes: 600
def pre_cmb(N, MOD):
    FACT = [1, 1]  # 階乗
    INV = [0, 1]  # 各iの逆元
    FACTINV = [1, 1]  # 階乗の逆元

    for i in range(2, N + 1):
        FACT.append((FACT[-1] * i) % MOD)
        INV.append(pow(i,MOD-2,MOD))
        FACTINV.append((FACTINV[-1] * INV[-1]) % MOD)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):
    FACT, FACTINV = PRELIST
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    return FACT[N] * FACTINV[R] * FACTINV[N-R] % MOD


n, m, k = map(int, input().split())
mod = 998244353

prelist = pre_cmb(n, mod)

cnt = 0
for i in range(k + 1):
    cnt += (m * pow(m - 1, n - i - 1, mod) * cmb(n - 1, i, mod, prelist)) % mod

print(cnt % mod)


Measured memory_bytes: 117948
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using Pair = pair<int, int>;
using Vec = vector<int>;
using Graph = vector<Vec>;

int		main(void)
{
	string s;
	cin >> s;
	bool f = true;
	int len = s.length();
	for (int i = 0; i < len; i++)
	{
		if (i % 2 == 0 && s[i] == 'L')
			f = false;
		else if (i % 2 == 1 && s[i] == 'R')
			f = false;
	}
	cout << (f ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

int main()
{
	int a, b;
	cin >> a >> b;
	if(a == 1)
		a += 13;
	if(b == 1)
		b += 13;

	if(a < b)
		cout << "Bob" << endl;
	else if(a == b)
		cout << "Draw" << endl;
	else
		cout << "Alice" << endl;

	return 0;
}

Measured memory_bytes: 764
from collections import deque
N = int(input())
A = [int(i) for i in input().split()]
lenA = len(A)

B = deque()
for i in range(N):
    if lenA % 2 == 0:
        if i % 2 == 0:
            B.append(A[i])
        else:
            B.appendleft(A[i])
    else:
        if i % 2 == 0:
            B.appendleft(A[i])
        else:
            B.append(A[i])
            
print(' '.join(map(str, B)))

Measured memory_bytes: 29124
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int h, w;
    cin >> h >> w;
    vector<vector<int>> c(10, vector<int>(10));
    vector<vector<int>> mg(10, vector<int>(10));
    for(int i = 0; i < 10; i++)
    {
        for(int j = 0; j < 10; j++)
        {
            cin >> c[i][j];
            mg[i][j] = 100000;
        }
    }
    vector<int> num(10);
    for(int i = 0; i < 10; i++)
    {
        num[i] = i;
    }
    do
    {
        int start = num[0];
        if(start == 1) continue;
        int magic = 0;
        int now = start;
        for(int i = 1; i < 10; i++)
        {
            int cand = num[i];
            if(cand != 1)
            {
                magic += c[now][cand];
                now = cand;
            }
            if(cand == 1)
            {
                magic += c[now][1];
                mg[start][1] = min(mg[start][1], magic);
                break;
            }
        }
    }
    while(next_permutation(num.begin(), num.end()));
  
    int ans = 0;
    for(int i = 0; i < h*w; i++)
    {
        int x;
        cin >> x;
        if(x == 1 || x == -1) continue;
        ans += mg[x][1];
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define pb push_back
#define xx first
#define yy second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define repp(i,k,n) for(int i=k;i<n;i++)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> iv;
typedef pair<int,int> iip;
typedef map<int,int> mii;
template <typename T>
void dbg(T t){cerr<<t<<endl ;}
template<typename T, typename... Args>
void dbg(T t, Args... args) {cerr << t <<" ";dbg(args...) ;}
set<int> g[200005];

int main(){
	int n,m,a,b;
	cin>>n>>m;
	rep(i,m){
		cin>>a>>b;a--;b--;
		g[a].insert(b);
		g[b].insert(a);
	}
	bool ok = false;
	for(auto c:g[0]){
		if(c==n-1) ok = true;
		else{
			for(auto k:g[c]){
				if(k==n-1)ok=true;
			}
		}

	}

	cout<<((ok)?"POSSIBLE":"IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 28416
#include <bits/stdc++.h>
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; }
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1}; // 移動方向

int n;
int num[4];

void input(){
    cin >> n;
    for(int i=0;i<4;i++){
        int tmp = pow(10, i);
        num[i] = (n / tmp) % 10;
    }
    reverse(num, num+4);
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    input(); 
    /*0なら-、1なら+, 3bit*/
    vector<char> op;
    for(int bit = 0; bit < (1<<3); bit++){
        int sum = num[0];
        op = {};
        for(int i = 0; i < 3; i++){
            if (bit & (1<<i)) sum += num[i+1], op.push_back('+');
            else sum -= num[i+1], op.push_back('-'); 
        }
        if (sum == 7) break;
    }
    cout << num[0] << op[0] << num[1] << op[1] << num[2] << op[2] << num[3] << "=7" << endl;
    return 0;
}

Measured memory_bytes: 256
import math
n, m = map(int,input().split())
mod = (10**9)+7
mul = 0 if abs(n-m)>1 else 2 if n==m else 1
a = min(n,m)
A = math.factorial(a)
B = A
if mul==1:
  B*=max(n,m)
print(A*B*mul%mod)

Measured memory_bytes: 5184
(defun solve (n strings)
  (declare (ignore n))
  (let ((map (make-hash-table :test 'equal))
        (results '()))
    (loop with max-count = 0
          for string in strings
          do (setf max-count
                   (max max-count (incf (gethash string map 0))))
          finally (maphash (lambda (string count)
                             (when (= count max-count)
                               (push string results)))
                           map))
    (sort results #'string<)))

#-swank
(let* ((n (read))
       (strings (loop repeat n collect (read-line))))
  (format t "~{~A~%~}" (solve n strings)))


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

int main(){
    int N; cin >> N;
    string ret = "";
    while(true){
        int temp = N % (-2);
        bool neg = temp < 0;
        if (temp == 0)
            ret = "0" + ret;
        else
            ret = "1" + ret;
        bool sign = N>0;
        N = N / (-2) - (neg ? 1 : 0) * (sign ? 1 : -1);
        if (N == 0)
            break;
    }
    cout << ret << endl;
    return 0;
}

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

using namespace std;

// Problem https://atcoder.jp/contests/abc098/tasks/arc098_a
// C++ 3rd Try
long int solver(long int MEMBERS,string POSITIONINF){
    long int result;
    result = MEMBERS;
    // EとWを0,1で各専用ベクトルに納める
    vector<long int> EMembers(MEMBERS,0);
    vector<long int> WMembers(MEMBERS,0);

    for(long int j = 0;j<MEMBERS;j++){
        if(POSITIONINF[j]=='E'){
            EMembers[j] = 1;
        }
        else if(POSITIONINF[j]=='W'){
            WMembers[j] = 1;
        }            
    }
    vector<long int> accEMEM(MEMBERS+1,0);
    vector<long int> accWMEM(MEMBERS+1,0);
    // E,Wの累積和を作成
    for(long int j=0;j<MEMBERS;j++){
        accEMEM[j+1] = accEMEM[j]+EMembers[j];
        accWMEM[j+1] = accWMEM[j]+WMembers[j];
    }
    // 各人間がリーダーの時のE,Wが向く方向を求める
    for(long int j=0;j<MEMBERS;j++){
        long int switchMember = 0;
        switchMember = accWMEM[j]+accEMEM[MEMBERS]-accEMEM[j+1];
        result = min(result,switchMember);
    }
    return result;
}


int main(void){
    long int answer=0;
    long int N;
    cin >> N;
    string S;
    cin >> S;
    answer = solver(N,S);
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 10372
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, m, a = 0;
  long long count = 0;
  cin >> n >> m;
  vector<vector<int>> data1(n, vector<int>(m,0));
  vector<int> data2(m,0);
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> data1.at(i).at(j);
    }
  }
  for(int i = 0; i < m; i++){
    cin >> data2.at(i);
  }  
  
   for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      count += data1.at(i).at(j) * data2.at(j);
    }
    cout << count << endl;
    count = 0;
  }
  
  
}


Measured memory_bytes: 3164
#include <iostream>
#include <math.h>
#include <string>
using namespace std ;

string yorn(bool a){ if(a) return "Yes" ; return "No" ;}

int main(){
    string a,b ; 
    cin >> a >> b ;
    int n = stoi(a+b) ;
    cout << yorn(sqrt(n)==(int)sqrt(n)) << endl ;
}


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

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
int A[111];

void MAIN() {
    scanf("%d", &N);
    REP (i, N) scanf("%d", A+i);

    int sum = 0;
    REP (i, N) sum += A[i];
    int id = 0, dist = 1<<29;
    REP (i, N) {
	int d = abs(sum - A[i] * N);
	if (d < dist) {
	    id = i;
	    dist = d;
	}
    }
    printf("%d\n", id);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



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


int main(){
  int r;
  cin >> r;
  if(r<1200){
    cout << "ABC" << endl;
  }else if(r>=1200 && r<2800){
    cout << "ARC" << endl;
  }else{
    cout << "AGC" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+1;
const ll mod = 1e9+7;
ll fact[N];
ll inv(ll a, ll p=mod-2) {
	if(p==0) return 1;
	ll b = inv(a, p/2);
	if(p%2==0) {
		return b*b%mod;
	}
	else {
		return b*b%mod*a%mod;
	}
}
ll C(int n, int k) {
	if(k>n) {
		return 0;
	}
	return fact[n]*inv(fact[k]*fact[n-k]%mod)%mod;
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, k;
	cin>>n>>k;
	fact[0]=1;
	for(ll i=1; i<=n; ++i) {
		fact[i]=fact[i-1]*i%mod;
	}
	vector<ll> a(n);
	for(int i=0; i<n; ++i) {
		cin>>a[i];
	}
	sort(a.begin(), a.end());
	reverse(a.begin(), a.end());
	ll ans=0;
	for(int i=0; i<n; ++i) {
		ll val = a[i] * C(n-i-1, k-1) % mod;
		ans += val;
		ans%=mod;
	}
	for(int i=1; i<=n; ++i) {
		ll val = a[n-i] * C(n-i, k-1) % mod;
		ans -= val;
		ans+=mod;
		ans%=mod;
	}
	cout<<ans<<'\n';
}


Measured memory_bytes: 1792
n,a=int(input()),sorted(list(map(int,input().split())))
q,p=b,c=a[0],a[-1]
d=a[1:-1]
for i in d:
  if i<0:p-=i
  else:q-=i
print(p-q)
for i in d:
  if i<0:print(c,i);c-=i
  else:print(b,i);b-=i
print(c,b)


Measured memory_bytes: 63564
N = int(input())

flag = 0
count = 0

for _ in range(N):
    a, b = map(int, input().split(" "))

    if a == b:
        count += 1
    else:
        count = 0

    if count == 3:
        flag = 1

if flag:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9128
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n + 1);
    set<int> s;
    for (int i = 1; i <= n; ++i) scanf("%d", &a.at(i));
    for (int i = n; i >= 1; --i) {
        int cnt = 0;
        for (int j = i * 2; j <= n; j += i) if (s.find(j) != s.end()) ++cnt;
        if (cnt % 2 != a.at(i)) s.insert(i);
    }
    printf("%d\n", int(s.size()));
    for (auto i = s.begin(); i != s.end();) {
        printf("%d", *i);
        printf("%c", ++i == s.end() ? '\n' : ' ');
    }
    return 0;
}


Measured memory_bytes: 7808
#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 51
using namespace std;
int n, C[N_];
long long S[N_], X, DD;
vector<int>E[N_];
void DFS(int a) {
	C[a] = 1;
	for (auto &x : E[a]) {
		DFS(x);
		S[a] += S[x];
		C[a] += C[x];
	}
}
struct point {
	long long f, c, s;
	bool operator <(const point &p)const {
		return s * p.c < p.s*c;
	}
}w[N_], A[N_];
long long D1[5100], D2[5100];
int main() {
	int i, a, j, k;
	scanf("%d%lld%lld", &n, &X, &DD);
	for (i = 1; i <= n; i++) {
		scanf("%lld", &S[i]);
		if (i != 1) {
			scanf("%d", &a);
			E[a].push_back(i);
		}
	}
	DFS(1);
	for (i = 1; i <= n; i++) {
		w[i] = {DD, C[i], S[i]};
	}
	w[1].f = 2e9;
	sort(w + 1, w + n + 1);
	long long T = X;
	long long s = 0;
	for (i = 1; i <= n; i++) {
		int t = min(w[i].f, T / w[i].s);
		s += t * w[i].c;
		T -= t * w[i].s;
		A[i] = { w[i].f - t, w[i].c, w[i].s };
		w[i].f = t;
	}
	for (i = 1; i <= 5000; i++)D2[i] = 1e18;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= 50; j++) {
			if (j <= w[i].f) {
				for (k = 5000; k >= w[i].c; k--) {
					D1[k] = max(D1[k], D1[k - w[i].c] + w[i].s);
				}
			}
			if (j <= A[i].f) {
				for (k = 5000; k >= w[i].c; k--) {
					D2[k] = min(D2[k], D2[k - w[i].c] + w[i].s);
				}
			}
		}
	}
	for (i = 4999; i >= 0; i--) {
		D2[i] = min(D2[i], D2[i + 1]);
	}
	for (i = 1; i <= 5000; i++)D1[i] = max(D1[i], D1[i - 1]);
	long long res = s;
	for (i = 0; i < 5000; i++) {
		for (j = i + 1; j <= 5000; j++) {
			if (D2[j] - D1[i] <= T) {
				res = max(res, s + j - i);
			}
		}
	}
	printf("%lld\n", res);
	
}

Measured memory_bytes: 384
import math
def main():
	A, B, H, M = map(float, input().split())
	R = H/12 + M*0.5/360
	r = M/60
	cos = math.cos((R-r)*2*math.pi)
	C = math.sqrt(A*A + B*B - 2*A*B*cos)
	print(C)

if __name__ == '__main__':
	main()

Measured memory_bytes: 9392
/*
 * Created by Dipta Das on 26-06-2019
 * Title: 
 * Problem Link: 
 * Editorial: 
 * Source Code: 
 * Comments: 
*/

#include <bits/stdc++.h>
#include <stdio.h>
#define fin freopen("input", "r", stdin)
#define whatis(x) cerr << #x << ": " << x << endl;

using namespace std;
using ll = long long;

int INF = 1e9 + 10;

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

    int n, k;
    cin >> n >> k;
    vector<int> height(n);
    for (int &i : height) cin >> i;
    vector<int> dp(n, INF);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= k; ++j) {
            dp[i+j] = min (dp[i+j], dp[i] + abs (height[i+j] - height[i]));
        }
    }

    cout << dp[n-1] << endl;
    


    return 0;
}



Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String ... args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] v = new int[n];
		for (int i = 0; i < n; i++) {
			v[i] = sc.nextInt();
		}
		int[] c = new int[n];
		for (int i = 0; i < n; i++) {
			c[i] = sc.nextInt();
		}
		int max = 0;
		for (int i = 0; i < n; i++) {
			if (v[i] > c[i]) {
				max += v[i] - c[i];
			}
		}
		System.out.println(max);
	}
}


Measured memory_bytes: 22996
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

#define fs first
#define sc second

int main() {
    ll N;
    int K;
    cin >> N >> K;

    int ans = 0;
    ll x = 1;
    while(true) {
        if(x <= N) {
            x *= K;
            ans++;
        } else {
            break;
        }
    }

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


Measured memory_bytes: 256
sx,sy,tx,ty=map(int,input().split())
string="U"*(ty-sy)+"R"*(tx-sx)+"D"*(ty-sy)+"L"*(tx-sx+1)+"U"*(ty-sy+1)+"R"*(tx-sx+1)+"D"+"R"+"D"*(ty-sy+1)+"L"*(tx-sx+1)+"U"
print(string)

Measured memory_bytes: 3060
s=input()
n=len(s)
ss=s[:n//2]
sss=s[n//2+1:]
f1=all(i==j for i,j in zip(s,s[::-1]))
f2=all(i==j for i,j in zip(ss,ss[::-1]))
f3=all(i==j for i,j in zip(sss,sss[::-1]))
if f1 and f2 and f3:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int n, W;
    cin >> n >> W;
    vector<ll> w(n), v(n);
    REP(i,n) cin >> w[i] >> v[i];

    vector<vector<ll>> dp(n+1,vector<ll>(W+1));
    ll ans = 0;
    REP(i,n) {
        REP(j,W+1){
            if (j - w[i] >= 0) {
                dp[i+1][j] = max(dp[i][j-w[i]]+v[i],dp[i][j]);
            } else {
                dp[i+1][j] = dp[i][j];
            }
        }
        //cerr << ans << endl;
    }

    cout << dp[n][W] << '\n';


    return 0;
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
using namespace std;
const int maxp = 10100;
const int maxn = 200100;
map<char, int> digits;
int cnt[maxp], n, mod;
int u[maxn];
string str;

int main() {
	cin>>n>>mod;
	cin>>str;

	if(mod == 2 || mod == 5) {
		ll result = 0LL;
		for(int i=n-1;i>=0;i--) {
			for(char j='0';j<='8';j++) {
				if(int(j-'0') % mod == 0) result += 1LL * cnt[j];
			}
			
			if(int(str[i]-'0') % mod == 0) result++;
			cnt[str[i]]++;
		}
		cout<<result;
		return 0;
	}

	ll result = 0LL;
	cnt[0] = 1;
	int pow10 = 1;
	for(int i=n-1;i>=0;i--) {
		u[i] = (pow10 * int(str[i] - '0') + u[i+1]) % mod;

		result += 1LL * cnt[u[i]];
		cnt[u[i]]++;
		pow10 *= 10; pow10 %= mod;
	} cout<<result;
} 

Measured memory_bytes: 1412