akhauriyash/Code-Regression huggingface dataset:
from collections import deque
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

sx, sy, gx, gy = 0, 0, h - 1, w - 1
d = [[float("inf")] * w for _ in range(h)]

que = deque([])
que.append((sx, sy))
d[sx][sy] = 0


def bfs():
    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

##最短距離を格納
bfs = bfs()
cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            cnt += 1
if bfs == float("inf"):
    print(-1)
else:
    print(cnt - (bfs + 1))


Measured memory_bytes: 9516
K, N = map(int, input().split())
A = list(map(int, input().split()))
cost_list = []
for i in range(len(A)-1):
  cost_list.append(A[i+1] - A[i])

cost_list = cost_list + [A[0] + K-A[-1]]

print(sum(cost_list) - max(cost_list))

Measured memory_bytes: 26420
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

bool done[22];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int W, D;
    while (cin >> W >> D) {
    	if (W==0 && D==0) break;
    	vi X(W), Y(D);
    	for (int i = 0; i < W; i++)
    		cin >> X[i];
    	for (int i = 0; i < D; i++)
    		cin >> Y[i];
    	memset(done, false, sizeof(done));
    	int ans = 0;
    	for (int i = 0; i < W; i++) {
    		ans += X[i];
    		for (int j = 0; j < D; j++) {
    			if (!done[j] && X[i] == Y[j]) {
    				done[j] = true;
    				break;
    			}
    		}
    	}
    	for (int i = 0; i < D; i++) {
    		if (!done[i]) ans += Y[i];
    	}
    	cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3100
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)

int main(void){
  int money;
  while(cin>>money){
    if(money==0)break;
    int oturi = 1000-money;
    int ans = 0;
    ans += oturi/500;
    oturi%=500;
    ans += oturi/100;
    oturi%=100;
    ans += oturi/50;
    oturi%=50;
    ans += oturi/10;
    oturi%=10;
    ans += oturi/5;
    oturi%=5;
    ans += oturi;
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <stdio.h>

int main(void){
    int n, d;

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

    int i;
    for(i = 1; i <= n; ++i){
        if((((i - 1) * 2 * d) + 2 * d) + i >= n ) break;
    }

    printf("%d\n", i);

    return 0;
}

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

int main() {
  int N, D;
  cin >> N >> D;
  vector<vector<int>> X(N, vector<int>(D));
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < D; ++j)
      cin >> X[i][j];

  int ans = 0;
  for (int i1 = 0; i1 < N; ++i1) {
    for (int i2 = i1 + 1; i2 < N; ++i2) {
      int dis = 0;
      for (int j = 0; j < D; ++j)
        dis += abs(X[i1][j] - X[i2][j]) * abs(X[i1][j] - X[i2][j]);

      for (int n = 0; n * n <= dis; ++n)
        if (n * n == dis)
          ++ans;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
    #include <algorithm>
    #include <string>
    using namespace std;
     
    int main() {
    	int a,b,c;
    	int i,j,k,n;
    	string s;
    	cin>>s;
    	int panjang=s.length()-1;
    	int jumlah=1;
    	for (i=0;i<panjang;i++)
    	{
    		string potong;
    		potong=s;
    		potong.erase(panjang-i,jumlah);
    		jumlah++;
    		if (potong.length()%2==0)
    		{
    			int panjangpotong=potong.length();
    			int dua=panjangpotong/2;
    			bool cek=true;
    			for (j=0;j<dua;j++)
    			{
    				if (potong[j]!=potong[j+dua])
    				{
    					cek=false;
    					break;
    				}
    			}
    			if (cek)
    			{
    				cout<<panjangpotong<<"\n";
    				return 0;
    			}
    		}
    	}
    	return 0;
    }

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

int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        s[i]+=n;
        if(s[i]>'Z')
        s[i]-=26;
    }
    cout<<s<<endl;
    return 0;
}

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

using namespace std;

#define For(i,a,n)	for(int i = a;i < n;i++)
#define rep(i,n)	For(i,0,n)
#define clr(n)		memset(n,0,sizeof n)
#define all(n)		(n).begin(),(n).end()

int main()
{
	int n, w, d;
	
	while (cin >> n >> w >> d && (n || w || d)){

		vector<int> x, y;
		x.push_back(w), y.push_back(d);

		rep(i, n){
			int p, s;
			cin >> p >> s;
			p--;

			int d[4] = { x[p], y[p], x[p], y[p] };
			int t = -1;

			s = s % (x[p] * 2 + y[p] * 2);
			
			for (int j = 0; j < 4; j++){
				if (s < d[j]){
					t = j; break;
				}
				else{
					s -= d[j];
				}
			}
			int nx1, nx2;
			if (t % 2 == 0){
				nx1 = x[p] - s;
				nx2 = s;

				int ty = y[p];
				x.erase(x.begin() + p);
				y.erase(y.begin() + p);
				x.push_back(min(nx1, nx2));
				x.push_back(max(nx1, nx2));
				y.push_back(ty);
				y.push_back(ty);
			}
			else{
				nx1 = y[p] - s;
				nx2 = s;

				int tx = x[p];
				x.erase(x.begin() + p);
				y.erase(y.begin() + p);
				y.push_back(min(nx1, nx2));
				y.push_back(max(nx1, nx2));
				x.push_back(tx);
				x.push_back(tx);
			}
		}

		vector<int> ans;
		rep(i, x.size()){
			ans.push_back(x[i] * y[i]);
		}
		sort(all(ans));
		rep(i, ans.size()){
			if (i == ans.size() - 1)
				cout << ans[i] << endl;
			else
				cout << ans[i] << " ";
		}
	}
	return 0;
}

Measured memory_bytes: 1220
import sys

a, b = map(int, sys.stdin.readline().split())

def main():
    for i in range(1, 1251):
        if i * 0.1 // 1 == b and i * 0.08 // 1 == a:
            return i
    return -1

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

Measured memory_bytes: 3060
#include<iostream>

using namespace std;

int main(){
  int a,b;
  cin >> a >> b;
  
  if(a>b){
  	cout << a-b << endl;
  }
  else if(a<b){
  	cout << 0 << endl;
  }
  else cout << 0 << endl;
  
  return 0;
  
}

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

  queue<int> q;
  q.push(src);
  vis[src]=1;
  dist[src]=0;
  par[src]=-1;
  int lv=-1;
  while(sz(q)>0){
    int siz=sz(q);
    lv++;
    while(siz--){

        int cur=q.front();
        q.pop();
        dist[cur]=lv;

        for(int i=0;i<sz(v[cur]);i++){
            int nw=v[cur][i];
            if(vis[nw]) continue;
            vis[nw]=1;
            par[nw]=cur;
            q.push(nw);
        }
    }
  }
}

int main(){
    GO();
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }
    bfs(1);

    cout<<"Yes\n";
    for(int i=2;i<=n;i++){
      cout<<par[i]<<"\n";
    }

}










































Measured memory_bytes: 11056
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5) #ルートn以上で割れることはない
    data = [i + 1 for i in range(2, n, 2)] #最初から3スタートの奇数にしておく
    while True:
        p = data[0]
        if limit < p: #ここでイコールが入るとlimitが素数の時にlimit^2が残ってダメ。
            return prime + data
        prime.append(p) #ここで一番最初に取り出した素数を加える。
        data = [e for e in data if e % p != 0] #残りでその素数で割れない数字を取得。

MAX = pow(10,5)+10
A = get_sieve_of_eratosthenes(MAX)
A = set(A)
S = [0]
for i in range(1,MAX):
  if i in A and (i+1)%2 == 0 and (i+2)//2 in A:
    temp = S[-1]+1
  else:
    temp = S[-1]
  S.append(temp)
Q = int(input())
for i in range(Q):
  l,r = map(int,input().split())
  ans = S[r]-S[l-1]
  print(ans)

Measured memory_bytes: 12780
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# Copyright  : @Huki_Hara
# Created    : 2015-03-11

for _ in range(int(input())):
    l=[0]
    r=[0]
    c=True
    n=map(int, input().split())
    for i in n:
        if l[-1] > i and r[-1] > i:
            c=False
            break
        if l[-1] < i:
            l.append(i)
        else:
            r.append(i)
    print("YES" if c else "NO" )

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


struct mint {
    long long x;
    static const int MOD = 1000000007;
    mint(long long x=0): x(x%MOD) {}

    void operator=(const long long n) {
        x = n % MOD;
    }
    mint operator+(const mint n) {
        mint ret;
        ret.x = (x + n.x) % MOD;
        return ret;
    }
    mint operator-(const mint n) {
        mint ret;
        ret.x = (x - n.x + MOD) % MOD;
        return ret;
    }
    mint operator*(const mint n) {
        mint ret;
        ret.x = (x * n.x) % MOD;
        return ret;
    }
    mint operator/(const mint n) {
        mint ret;
        ret.x = (x * n.inv().x) % MOD;
        return ret;
    }

    mint inv() const {
        mint ret;
        long long a = x, b = MOD, u = 1, v = 0;
        while(b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= MOD;
        if (u < 0) u += MOD;
        ret.x = u;
        return ret;
    }
};

ostream& operator<<(ostream& os, const mint& n)
{
    os << n.x;
    return os;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int r1, r2, c1, c2;
    cin >> r1 >> c1 >> r2 >> c2;

    mint fact[r2+c2+3] = {1, 1};
    for (int i = 2; i <= r2+c2+2; i++) {
        fact[i] = fact[i-1] * i;
    }

    mint g22 = fact[r2+c2+2]/(fact[r2+1]*fact[c2+1]) - 1;
    mint g12 = fact[r2+c1+1]/(fact[r2+1]*fact[c1]) - 1;
    mint g21 = fact[r1+c2+1]/(fact[r1]*fact[c2+1]) - 1;
    mint g11 = fact[r1+c1]/(fact[r1]*fact[c1]) - 1;

    cout << g22 - g12 - g21 + g11 << endl;

    return 0;
}



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


int main() {


  long N;
	 long K;
    cin >> N >>K;
  
  long ans=0;

  vector<long> bb(N+2);
  vector<long> aa(N+2);
  aa.at(0)=0;
  bb.at(0)=0;
  for(int i=1; i<N+2;i++){
    bb.at(i) = bb.at(i-1)+(i-1);
  }
  
    for(int i=1; i<N+2;i++){
    aa.at(i) = aa.at(i-1)+ N - (i-1);
  }
  for(int j=K;j<N+2;j++){

    ans = ans + 1 + aa.at(j) - bb.at(j);
   
     ans = ans % 1000000007;
    
     
   }
    
  cout << ans << endl;
  return 0;

}

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

int main() {
  int64_t N;
  cin >> N;
  vector<int> prime;
  int64_t n = N;
  for(int64_t i = 2; i*i <= n; i++) {
    int count = 0;
    while(N % i == 0) {
      N /= i;
      count++;
    }
    prime.push_back(count);
  }
  if(N > pow(n, 0.5)) {
    prime.push_back(1);
  }
  int ans = 0;
  for(int i = 0; i < prime.size(); i++) {
    int count = 0;
    int j = 1;
    while(prime.at(i) >= j) {
      prime.at(i) -= j;
      count++;
      j++;
    }
    ans += count;
  }
  cout << ans << endl;
}

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

string s;
int a, b;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> s;
	for(int i=0; i<s.size(); ++i){
		if(s[i] == '0') ++a;
		else ++b;
	}
	cout << 2 * min(a, b) << "\n";
}

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

int main() {
	vector<int> a(6), n(4), o{ 1,1, 2, 2 };
	for (int i = 0; i < 6; i++)
		cin >> a[i];
	sort(a.begin(), a.end());
	for (int i = 0; i < 4; i++)
		n[i] = count(a.begin(), a.end(), i + 1);
	sort(n.begin(), n.end());
	if (n == o)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q;
int cnt[100010];
ll ans;
int main() {
	cin >> n;
	for (int i = 1, a; i <= n; i++) {
		cin >> a;
		ans += a;
		cnt[a]++;
	}
	cin >> q;
	for (int i = 1, b, c; i <= q; i++) {
		cin >> b >> c;
		ans -= 1ll * cnt[b] * b;
		ans += 1ll * cnt[b] * c;
		cnt[c] += cnt[b];
		cnt[b] = 0;
		cout << ans << "\n";
	}
	return 0;
}

Measured memory_bytes: 4008
n = int(input())

A = list(map(int,input().split()))

A.sort()
k = 0
while k<=n-1 and A[k]<0:
    k += 1
if k%2==0:
    print(-sum(A[:k])+sum(A[k:]))
elif k%2==1 and k==n:
    print(-sum(A[:k-1]) + sum(A[k-1:]))
else:
    print(max(-sum(A[:k-1])+sum(A[k-1:]) , -sum(A[:k+1])+sum(A[k+1:])))

Measured memory_bytes: 64752
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>

#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    string s;
    cin >> s;
    string res = "AC";
    if(s.at(0)!='A') res = "WA";
    int orderOfC = -1;
    for(int i=2; i<s.size()-1; i++){
        if(s.at(i)=='C'){
            orderOfC = i;
            break;
        }
    }
    if(orderOfC==-1) res = "WA";
    for(int i=1; i<s.size(); i++){
        if(i==orderOfC) continue;
        if((s.at(i) < 97) || (122 < s.at(i))) res = "WA";
    }
    cout << res << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
 * Lesson5B　以下のような、たてH cm よこ W cm の枠を描くプログラム
##########
#........#
#........#
#........#
#........#
##########

 * @author 前島佑介
 * @version 2014/12/1
 */
class Main {

	// プログラムのエントリポイント
	public static void main(String[] args) {

		try{
			//キーボードからの入力準備
			BufferedReader insBR = new BufferedReader(new InputStreamReader(System.in));

			//入力値を格納する場所を初期化
			String strLine = "";

			//入力値をint型で保存する場所
			ArrayList<String> strArray = new ArrayList<String>();

			//入力値の取得にループさせる
			while(true) {

				//1行読み込む
				strLine = insBR.readLine();

				//入力値が"0 0"だったら
				if(strLine.equals("0 0")) {

					//ループから抜ける
					break;
				}

				//入力値を保存
				strArray.add(strLine);
			}

			//ループさせる
			for(int i = 0; i < strArray.size(); i++) {

				//文字列の分割:入力値を" "で分ける
				//分けた文字列はstrLineAry[0]とstrLineAry[1]に分けられる
				String[] strLineAry = strArray.get(i).split(" ");

				//左の値
				int intNum1 = Integer.parseInt(strLineAry[0]);

				//右の値
				int intNum2 = Integer.parseInt(strLineAry[1]);

				//出力させるメソッド
				SharpPaint(intNum1, intNum2);
			}

		//例外処理
		}catch(IOException e) {

			//例外時の出力
			System.out.println(e);
		}catch(NumberFormatException e) {


			//数値以外の入力値で出力
			System.out.println("数値で入力して下さい");
		}
	}
	/**
	 * たてintNum1の分よこintNum２の分の長方形を描くプログラム
	 * 1 cm × 1cm の長方形を '#'で表す
	 * @param intNum1
	 * @param intNum2
	 */
	public static void SharpPaint(int intNum1, int intNum2) {

		//たての分　ループ
		for(int i = 0; i < intNum1; i++) {

			//よこの分　ループ
			for(int j = 0; j < intNum2; j++) {

				//近くの周りは＃
				if(
						i == 0 ||					//左辺
						j == 0 ||					//上辺
						i == intNum1 - 1 ||			//右辺
						j == intNum2 - 1	) {		//下辺
					//出力
					System.out.print("#");
				} else {
					//出力
					System.out.print(".");
				}
			}
			//改行
			System.out.println("");
		}

		//改行
		System.out.println("");

	}
}

Measured memory_bytes: 25608
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    aset = list(set(A))
    aset.sort()

    ans = [0] * (10 ** 6 + 1)

    for a in aset:
        for i in range(2, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            ans[a * i] += 1

    res = 0
    c = collections.Counter(A)
    for a in A:
        if ans[a] == 0 and c[a] == 1:
            res += 1

    print(res)



if __name__ == '__main__':
    main()


Measured memory_bytes: 126300
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end() 
#define rep(i, K, N)  for(long long int i = K; i < N; i++)
#define ll long long int
#define PP 1000000007
using namespace std;

ll F(ll N, ll a, ll p){
 
    if(a == 0)return 1;
 
    if(a%2 == 0 && a != 0)return (F(N, a/2, p)*F(N, a/2, p))%p;
 
    if(a%2 == 1)return N*F(N, a - 1, p)%p;
 
}

int main() {
ll N , Ans = 0;cin >> N;
bool C = 1;
map<ll, ll> M;

rep(i, 0, N){

  ll a;cin >> a;

  M[a]++;

}
  
//for(auto x : M)cout << x.first << " " << x.second << endl;

if(N%2 != 0){

  if(M[0] == 1){

    for(ll i = 2; i < N; i+=2){

      if(M[i] != 2){C = 0;break;}

    }

  }

  else C = 0;

}

else{

  for(ll i = 1; i < N; i+=2){

    if(M[i] != 2){C = 0;break;}

  }

}

if(C)cout << F(2, N/2, PP);

else cout << 0;

}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int Q;
ll X,D,N;
ll mo=1000003;
const int NUM_=2400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];



ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll comb(ll a,ll b) {
	//cout<<a<<"!"<<b<<endl;
	a=-a;
	ll ret=fact[a+b-1]*factr[b]%mo*factr[a-1]%mo;
	if(b%2) ret=mo-ret;
	return ret%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	
	cin>>Q;
	while(Q--) {
		cin>>X>>D>>N;
		
		if(X==0) {
			cout<<0<<endl;
			continue;
		}
		if(D==0) {
			cout<<modpow(X,N)<<endl;
			continue;
		}
		
		ll k=(mo-X)%mo*modpow(D)%mo;
		//cout<<k<<endl;
		if(k<N) {
			cout<<0<<endl;
			continue;
		}
		//cout<<fact[N]<<" "<<modpow(mo-D,N)<<" "<<comb(-X*modpow(D)%mo,N)<<endl;
		ll ret=fact[N]*modpow(mo-D,N)%mo*comb(-X*modpow(D)%mo,N)%mo;
		cout<<ret<<endl;
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 57088
#include <bits/stdc++.h>
#define debug(a) cout << #a ": " << a << endl
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
const double eps = 1e-6;
ll n, k, a[N];
bool judge(ll mid){
    ll cnt = 0;
    for (int i = 1; i <= n; ++i){
        cnt += (a[i]-1)/mid;
        if (cnt > k) return false;
    }
    return true;
}
int main(void){
    IOS;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    if (n == 1 && k > 2 && a[1] == 1){
        cout << 0 << endl; return 0;
    }
    ll l = 1, r = 1000000000, ans = 0;
    while (l <= r){
        ll mid = (l+r) >> 1;
        if (judge(mid)){
            ans = mid;
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5124
n=int(input())

is_find = False

if n > 81:
    print('No')
else:
    for i in range(9):
        for j in range(9):
            if (i+1)*(j+1) == n:
                is_find = True
                break
        if is_find:
            break
    if is_find:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 3060
from sys import stdin

def f():
     n,m = [int(x) for x in stdin.readline().split()]
     a = [int(x) for x in stdin.readline().split()]
     min_a = min(a)
     a = [(1,i) for i in a]
     b_c = [tuple(map(int,x.split())) for x in stdin.readlines()]
     a += b_c
     a.sort(key=lambda x:x[1])
     ans = 0
     while True:
          if n>a[-1][0]:
               ans += a[-1][0]*a[-1][1]
               n -= a[-1][0]
               a.pop()
          else:
               ans += a[-1][1]*n
               break
     print(ans)
if __name__=='__main__':
     f()

Measured memory_bytes: 35500
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int X = sc.nextInt();
		int N = sc.nextInt();

		Set<Integer> p = new HashSet<>();
		for(int i=0; i<N; i++) {
			p.add(sc.nextInt());
		}

		int ans = -10000;
		for(int i=-200; i<=200; i++) {
			if(p.contains(i)) {
				continue;
			}

			if(ans == -10000) {
				ans = i;
			}else {
				if(Math.abs(i-X) < Math.abs(ans-X)) {
					ans = i;
				}
			}
		}

		System.out.println(ans);
	}

}


Measured memory_bytes: 35884
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int MAXN=105;
char ch[MAXN];
int main()
{
	scanf("%s",ch+1);int len=strlen(ch+1);
	bool tf=true;
	for(int i=1;i<=len;i++)
	{
		if((i&1)&&(ch[i]=='L'))return puts("No"),0;
		else if((!(i&1))&&(ch[i]=='R'))return puts("No"),0;
	}
	puts("Yes");return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define INF 1000000000000000001
#define ll long long
#define pll pair<ll, ll>
using namespace std;



int main()
{
  ll N;
  cin >> N;
  vector<ll> a(N);
  for (ll i = 0; i < N; ++i)
  {
    cin >> a.at(i);
  }
  ll ans = 0;
  ll S = 0;
  for (ll i = 0; i < N; ++i)
  {
    S += a.at(i);
    if (i % 2 == 0)
    {
      if (S > 0)
      {
        continue;
      }
      else
      {
        ans += 1 - S;
        S = 1;
      }
    }
    else
    {
      if (S < 0)
      {
        continue;
      }
      else
      {
        ans += 1 + S;
        S = -1;
      }
    }
  }

  ll ans2 = 0;
  ll S2 = 0;
  for (ll i = 0; i < N; ++i)
  {
    S2 += a.at(i);
    if (i % 2 == 1)
    {
      if (S2 > 0)
      {
        continue;
      }
      else
      {
        ans2 += 1 - S2;
        S2 = 1;
      }
    }
    else
    {
      if (S2 < 0)
      {
        continue;
      }
      else
      {
        ans2 += 1 + S2;
        S2 = -1;
      }
    }
  }
  ans = min(ans, ans2);
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define mp make_pair
#define np next_permutation
#define pb push_back
#define all(x) (x.begin(),x.end())
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)

#define fi first
#define se second 
using namespace std;
const int maxn=1e4+5;
const int maxl=26;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;


int cnt[maxn],ans[maxn];
void solve(){
	rep(i,1,300) cnt[i]++;
	rep(i,2,300){
		for(int j=1;j*i<=300;j++){
			cnt[i*j]++;
		}
	}
	int ccnt=0;ans[0]=0;
	rep(i,1,300) {
		if(cnt[i]==8 and (i&1)){
			ans[i]=++ccnt;
		}
		else ans[i]=ccnt;
	}
	rep(i,1,300) {
//		cout<<"ans["<<i<<"]="<<ans[i]<<endl;
	}
}

int a,b;
int main(){
	ios::sync_with_stdio(false); 
	solve();
	int n;
	while(cin>>n)
		cout<<ans[n]<<endl;
} 

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

using namespace std;

int main(){
	ios::sync_with_stdio(false);
	// freopen("in.txt", "r", stdin);
	string s;
	cin >> s;
	int ans;
	if(s == "SUN") ans = 7;
	if(s == "MON") ans = 6;
	if(s == "TUE") ans = 5;
	if(s == "WED") ans = 4;
	if(s == "THU") ans = 3;
	if(s == "FRI") ans = 2;
	if(s == "SAT") ans = 1;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        k: usize,
        a: [usize; n],
        f: [usize; n],
    }
    let mut a = a;
    let mut f = f;
    a.sort();
    f.sort();
    f.reverse();
    let mut x_min = 0;
    let mut x_max = a[n - 1] * f[0];
    while x_min < x_max {
        let x = (x_max + x_min) / 2;
        // println!("{} {} {}", x, x_min, x_max);
        let mut cost = 0;
        for i in 0..n {
            if a[i] * f[i] > x {
                cost += a[i] - x / f[i]
            }
        }
        if cost <= k {
            x_max = x;
        } else {
            x_min = x + 1;
        }
    }
    println!("{}", x_max);
}


Measured memory_bytes: 10492
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func reverseString(s string) string {
	var t string
	for i := len(s) - 1; i >= 0; i-- {
		t += string(s[i])
	}
	return t
}

func main() {
	sc.Split(bufio.ScanWords)
	n := next()
	if n == reverseString(n) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


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

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fm, to)    for (int i = fm; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 5e3;
const num inf = 0x3f3f3f3f3f3f3f3f;
int n;
num dp[nsz + 5][nsz + 5], ans;
pair<int, int> dat[nsz + 5];

bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.second - b.first < b.second - a.first;
}

void inline upd(num &a, num b) {
	a > b && (a = b);
}

int main() {
	scanf("%d", &n);
	cont (i, n) {
		scanf("%d%d", &dat[i].first, &dat[i].second);
	}
	sort(dat + 1, dat + n + 1, cmp);
	memset(dp, inf, sizeof(dp));
	dp[0][0] = 0;
	cont (i, n) {
		cont (j, i) {
			if (dat[i].first >= dp[i - 1][j - 1]) {
				upd(dp[i][j], dp[i - 1][j - 1] + dat[i].second);
			}
			upd(dp[i][j], dp[i - 1][j]);
		}
	}
	for (int i = n; i >= 1; --i) {
		if (dp[n][i] < inf) {
			ans = i;
			break;
		}
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 195968
#include <bits/stdc++.h>
using namespace std;
#define INF 1001001001001001

struct edge{int to; int cost;};
vector<edge> G[100000];
long long d[100000];

bool bfs(int i) {
    if(d[i] != INF) return true;

    d[i] = 0;
    queue<int> q;
    q.push(i);
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        for(edge e : G[cur]) {
            if(d[e.to] == INF) {
                d[e.to] = d[cur] + e.cost;
                q.push(e.to);
            } else if(d[e.to] != d[cur] + e.cost) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    int N, M;
    cin >> N >> M;
    for(int i=0; i<M; ++i) {
        int L,R,D;
        cin >> L >> R >> D;
        G[L-1].push_back({R-1, D});
        G[R-1].push_back({L-1, -D});
    }

    bool res = true;
    fill(d, d+N, INF);
    for(int i=0; i<N; ++i) {
        if(!bfs(i)) {
            res = false;
            break;
        }
    }
    if(res) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

int main(){
    long long n,min,max,sum =0;
    long long N[10001];
    cin>>n;
    
    cin>>N[0];
    
    max = min = sum = N[0];
    
    for(int i = 1;i<n;i++){
        cin>>N[i];
        
        if(max<N[i])max= N[i];
        if(min>N[i])min = N[i];
        sum += N[i];
    }
    
    cout<<min<<" "<<max<<" "<<sum<<endl;
    
    return 0;
}


Measured memory_bytes: 3172
#include<iostream>
using namespace std;
int main(){
    int a,b,c;
    int i;
    int n=0;
    cin >> a;
    cin >> b;
    cin >> c;
    for(int i=a;i <= b;i++){
        if(c%i == 0){
            n++;
        }
    }
    cout << n << endl;
    return 0;
}


Measured memory_bytes: 3112
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	n := nextInt()
	al := make([]int, 3*n)

	for i := 0; i < 3*n; i++ {
		al[i] = nextInt()
	}
	sort.Ints(al)

	ssum := 0
	for i := 0; i < n; i++ {
		ssum += al[3*n-2-i*2]
	}

	fmt.Println(ssum)

}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // Default=64
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 7212
#include <bits/stdc++.h>
#define lol long long
using namespace std;
int main(){
  lol n,m,ans;
  string s;
  cin>>n>>m;
  if(n%2!=0 && m%2!=0) ans=0;
  else ans=1;
  if(ans==0)
  cout<<"Yes"<<"\n";
  else cout<<"No\n";
  return(0);
}


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

int main() {
    int h, w, k;
    cin >> h >> w >> k;
    vector<vector<char>> s(h, vector<char>(w));
    for (auto& e : s) for (auto& f : e) cin >> f;

    int g = 0, bi = 0;
    vector<vector<int>> ans(h, vector<int>(w));
    vector<bool> emp(h);
    for (int hi = 0; hi < h; hi++) {
        int last = 0;
        for (int wi = 0; wi < w; wi++) {
            if (s[hi][wi] == '.') continue;
            g++;
            fill(begin(ans[hi])+last, begin(ans[hi])+wi+1, g);
            last = wi+1;
        }
        if (last == 0) {
            emp[hi] = true;
        } else {
            bi = hi;
            fill(begin(ans[hi])+last, end(ans[hi]), g);
        }
    }

    for (int i = bi; i-1 >= 0; i--) {
        if (emp[i-1]) ans[i-1] = ans[i];
    }
    for (int i = bi; i+1 < h; i++) {
        if (emp[i+1]) ans[i+1] = ans[i];
    }

    for (auto& e : ans) {
        for (auto& f : e) {
            cout << f << " ";
        }
        
        cout << endl;
    }
}


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

//{ START
using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (a); i > (n); --i)
#define arep(i, x) for (auto &&i : (x))
#define irep(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
#define rirep(i, x) for (auto i = (x).rbegin(); i != (x).rend(); ++i)
//降順はgreater<T>()
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
// gcd lcmはそのままok
#define gcd(a, b) __gcd(a, b)
#define bits(n) (1LL << (n))
#define pcnt(x) __builtin_popcountll(x)
//配列内等要素削除
#define unique(x) (x).erase(unique((x).begin(), (x).end()), (x).end())
#define Fixed(n) fixed << setprecision(n)
//総和
#define sowa(n) (((n) * ((n) + 1)) / 2)
#define pb(x, a) (x).push_back(a)
#define fb(x, a) (x).push_front(a)
#define eb(x, a) (x).emplace_back(a)
#define cauto const auto &
using P = pair<int, int>;
using Graph = vector<vector<P>>;
template <class T>  //昇順
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>  //降順
using max_heap = priority_queue<T>;
template <class A, class B>
using umap = unordered_map<A, B>;
template <class A>
using uset = unordered_set<A>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {  //多次元初期化
  std::fill((T *)array, (T *)(array + N), val);
}
template <class A, class B>
bool chmax(A &a, const B &b) {  //最大値更新 返り値はbool
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class A, class B>
bool chmin(A &a, const B &b) {  //最小値更新 返り値はbool
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
constexpr int INF = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9 + 7;
constexpr int mod2 = 998244353;
//} END

signed main(void) {
  ios_base::sync_with_stdio(false);

  int h, w;
  cin >> h >> w;
  string s;

  rep(i, 0, h) {
    rep(j, 0, w) {
      string s;
      cin >> s;
      if (s == "snuke") cout << (char)('A' + j) << i + 1 << '\n';
    }
  }

  return 0;
}

Measured memory_bytes: 3596
#include<stdio.h>
#include<string.h>

int main(){
const int MAX_V=1000000;
int prime[MAX_V+1];
	int i,k,v,n,p1,q1;
	for(i=2;i<=MAX_V;i++){
		prime[i]=1;
	}
	for(i=2;i*i<=MAX_V;i++){
		if(prime[i]){
			for(k=2*i;k<=MAX_V;k+=i){
				prime[k]=0;
			}
		}
	}
	prime[0]=0;
	prime[1]=0;
	while(1){
		scanf("%d",&v);
		if(v==0)break;
		if(prime[v]==0){
			while(1){
				v--;
				if(prime[v]==1)break;
			}
		}
		p1=v;
		q1=v;
		for(i=v-1;i>0;i--){
			if(prime[i]==1)q1=i;
			if(p1-q1==2){
				printf("%d %d\n",q1,p1);
				break;
			}else{
				p1=q1;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 4504
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
typedef long long ll;

ll tab[20];

ll charcnt(ll n) {
	int a = 0;
	ll tmp = n;
	while(tmp) {
		a++;
		tmp /= 10;
	}
	ll res = tab[a-1];
	ll b = 1;
	for(int i = 0; i < a-1; i++)
		b *= 10;
	b--;

	res += (n/3 + n/5 - b/3 - b/5) * 4;
	res += (n-b - ((n/3 + n/5 - n/15) - (b/3 + b/5 - b/15))) * a;

	return res;
}

int main() {
	ll s;
	cin >> s;

	tab[0] = 0;
	ll tmp = 10;
	for(int i = 1; i < 19; i++) {
		tab[i] = charcnt(tmp-1);
		tmp *= 10;
	}

	ll l, r;
	l = 0; r = 1e17;
//	cout << charcnt(r) << endl;
	while(r - l > 1) {
		ll m = l/2 + r/2 + (l%2 + r%2) / 2;
		ll res = charcnt(m);

		if(res < s) {
			l = m;
		}
		else {
			r = m;
		}
	}
//	cout << l << " " << r << endl;

	if(l == 0)
		l = 1;
	tmp = charcnt(l-1) + 1;
//	cout << tmp << endl;
	string str;
	for(int i = 0; i < 20; i++) {
		if((l+i) % 15 == 0) {
			str += "FizzBuzz";
		}
		else if((l+i) % 5 == 0) {
			str += "Buzz";
		}
		else if((l+i) % 3 == 0) {
			str += "Fizz";
		}
		else {
			stringstream sstr;
			string tmps;
			sstr << l+i;
			sstr >> tmps;
			str += tmps;
		}
	}
//	cout << str << endl;

	cout << string(str.begin() + (s-tmp), str.begin() + (s-tmp+20)) << endl;
}

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

int main()
{
	int n;
	cin >> n;
	int cnt = (n + 3) / 4;
	if ((cnt * 4 - n) <= (cnt / 2))
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 384
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(a,b) memset(a,b,sizeof(a))
#define msn(a,n,b) for(int i=0;i<=n;i++)a[i]=b
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define fi first
#define se second
using namespace std;
mt19937 rng_32(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef double db;
const int mod=1e9+7;
const int seed=233;
const double PI=acos(-1.0);
const double eps=1e-7;
const int inf=0x3f3f3f3f;
const int max_n=100005;
ll ceil(ll x,ll y){if(x==0)return 0;if(y<0)x=-x,y=-y;bool sign=x>0;x=abs(x);return sign?(x+y-1)/y:-x/y;}
ll floor(ll x,ll y){if(x==0)return 0;if(y<0)x=-x,y=-y;bool sign=x>0;x=abs(x);return sign?x/y:-(x+y-1)/y;}
namespace {
    inline int Add(int x,int y){return (x+=y)>=mod?x-mod:x;}
    inline int Sub(int x,int y){return (x-=y)<0?x+mod:x;}
    inline int Mul(int x,int y) {return 1ll*x*y%mod;}
    inline int Pow(int x,int y=mod-2){if(y==0)return 1;int res=1;while(y){if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;}
}
/**********************head************************/
int n,k;
int phi[max_n];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)phi[i]=i;
    for(int i=1;i<=k;i++){
        for(int j=i*2;j<=k;j+=i)phi[j]-=phi[i];
    }
    int ans=0;
    for(int i=1;i<=k;i++)ans=Add(ans,Mul(phi[i],Pow(k/i,n)));
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 4148
import java.util.*;

public class Main{
	public static void main(String[] $){
		Scanner s=new Scanner(System.in);
		HashMap<String,Integer> map=new HashMap<>();
		map.put("#",0);
		for(int n=s.nextInt();n>0;--n)
			map.merge(s.next(),1,Integer::sum);
		for(int m=s.nextInt();m>0;--m)
			map.merge(s.next(),-1,Integer::sum);
		System.out.println(
				map.values().stream()
						.mapToInt(i->i)
						.max().getAsInt());
	}
}


Measured memory_bytes: 27092
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    k=int(input())
    s=str(input())
    if len(s)<=k:
        print(s)
    else:
        print(s[:k]+'...')
    
resolve()

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

#define loop(i, a, b) for (int i = (a); i < (b); i++)
const int MAX = 405;
char grid[MAX][MAX];
int  visited[MAX][MAX];
int h, w;

bool inside(int x, int y)
{
    return 0 <= x && x < h && 0 <= y && y < w;
}

bool check(int x, int y, int a, int b){
    if (!inside(x + a, y + b))
        return false;
    return grid[x][y] != grid[x + a][y + b] && !visited[x + a][y + b];
}

int main()
{
    cin >> h >> w;
    loop(i, 0, h) loop(j, 0, w)
    {
        cin >> grid[i][j];
    }
    long long ans = 0;
    loop(i, 0, h) loop(j, 0, w) {
        if (visited[i][j]) continue;
        queue<pair<int, int>> queue;
        queue.emplace(make_pair(i, j));
        visited[i][j] = 1;
        long long black = 0;
        long long white = 0;
        while(queue.size()){
            pair<int, int> p = queue.front();
            queue.pop();
            if (grid[p.first][p.second] == '#')
                black += 1;
            else 
                white += 1;
            for (int a: {-1, 0, 1}){
                for (int b: {-1, 0, 1}){
                    if(abs(a) == abs(b)) continue;
                    if(check(p.first, p.second, a, b)){
                        queue.emplace(make_pair(p.first + a, p.second + b));
                        visited[p.first + a][p.second + b] = 1;
                    }
                }
            }
        }
        ans += white * black;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 4388
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
int cnt[N],a[N];
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    n=unique(a+1,a+n+1)-a-1;
    int ans=1;
    for(int i=1;i<=n;i++){
        int t=ans;
        (ans+=cnt[a[i]])%=mod;
        (cnt[a[i]]+=t)%=mod;
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define e1 first
#define e2 second
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define eb emplace_back
#define OUT(x) {cout << x; exit(0); }
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long int ll;
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PLL, int> PLLI;
typedef pair <PLL, PLL> PP;
typedef pair <PII, int> PPI;
typedef pair <ll, int> PLI;
typedef unsigned int ui;
const int inf = 1e9+9;
const int mod = 924844033;
#define maxn 1000100
ll tab[maxn];
int main()
{
	ll n;
	cin >> n;
	if (n <= maxn) {
	if (n % 3 != 2) {
		cout << 2 << endl;
		cout << 0 << ' ' << n + 1;
		exit(0);
	}
	else {
		cout << 2 << endl;
		cout << 1 << ' ' << n;
		exit(0);
	}
	}
	else
	{
		int ile = 50;
		FOR(i, 1, ile) tab[i] = i;
		ll ruchy = n;
		ll ileperone = (n / ile);
		FOR(i, 1, ile) tab[i] += ileperone, ruchy -= ileperone;
		FOR(i, 1, ile - ruchy) tab[i]--;
		cout << ile << endl;
		FOR(i, 1, ile) cout << tab[i] << ' ';
	}
}


Measured memory_bytes: 256
n = int(input())
al = list(map(int, input().split()))

def dev_by_2(x, cnt=0):
    if x % 2 == 0:
        x /= 2
        cnt += 1
        return(dev_by_2(x, cnt))
    else:
        return cnt

ans = 1001001001
for a in al:
    ans = min(ans, dev_by_2(a))

print(ans)

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

int main() {
	ll k,s;
	cin >> k >> s;
	ll ans = 0;
	rep(x,k+1) rep(y,k+1) {
		ll z = s-x-y;
		if (z>=0 && z<=k) ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
# -*- coding: UTF-8 -*-
def prime_t(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1
p=[]

for i in range(2,1008):
    if prime_t(i):
        p.append(i)
d={i:0 for i in p}
mod=10**9+7
n=int(input())
tmp=1
ans=1
R=[i for i in range(168)]
for i in range(1,n+1):
    tmp*=i
    for j in R:
        while tmp%p[j]==0:
            d[p[j]]+=1
            tmp//=p[j]
        if tmp<p[j]:
            break
for i in d:
    ans*=(d[i]+1)
    ans%=mod
print(ans)

Measured memory_bytes: 40176
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int a, b;
    cin >> a >> b;
    int c = min(a, b);
    rep(i, max(a, b)) cout << c;
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
import Data.List
import Text.Printf

ans ([0,0]:_) = []
ans x =
  let d = take 5 x
      r = drop 5 x
      a = maximumBy (\(a,b) (c,d)-> compare b d) $ zip ['A','B'..] $ map (\[x,y] -> x + y) d
  in
    a:(ans r)

main = do
  c <- getContents
  let i = map (map read) $ map words $ lines c :: [[Int]]
      o = ans i
  mapM_ (\(a,b) -> printf "%c %d\n" a b) o

Measured memory_bytes: 4280
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, a, b, c, d;
  cin >> N;
  a = N / 1000;
  b = (N - 1000 * a) / 100;
  c = (N - 1000 * a -100 * b) / 10;
  d = N % 10;
  if (((a == b) && (b == c)) || ((b == c) && (c == d)) ) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>ordered_set;
*/
/////////////////// TYPES & MACROS ///////////////////////////////
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define vv vector
#define exist(s,e) (s.find(e)!=s.end())
using ll=long long int; using dd=double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
typedef vector<int> vi;
const ll INFLL=(ll)2e18, MOD=1'000'000'007;
const int INF=0x3f3fffff ;
/////////////////// DEBUG /////////////////////////////////////////
#define D(x) cerr<<#x<<" is: "<<x<<'\n';
#define DD(x,y) cerr<<"("<<#x<<","<<#y<<") are: "<<x<<" "<<y<<'\n';
/////////////////// VARIABLES & FUNCTIONS//////////////////////////
vector<vector<int>> adj,dp; vector<int> vis;
int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1},dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};
inline ll mexp(ll x,ll n,ll m){ll res=1;while(n){if(n&1)res=(res*x)%m;n>>=1;x=((x%m)*(x%m))%m;}return res;}
bool ispow2(ll x){ return x && (!(x&(x-1)));}
ll gcd(ll x, ll y){ pll p{x,y}; while(p.ss) p={p.ss,p.ff%p.ss}; return p.ff;}


/////////////////// MAIN STARTS //////////////////////////////////
int main(){
  ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
  cout<<fixed;cerr<<fixed; cout<<setprecision(10); cerr<<setprecision(3);
  random_device rd; mt19937 genr(rd());

#ifdef DEBUG
  auto tStart = chrono::system_clock::now();
  //freopen("op.txt","w",stdout);
#endif

int n; cin>>n;
ll ans=0;
for (int i=0;i<n;i++){
  int t; cin>>t;
  ans+=t-1;
}
cout<<ans<<"\n";

#ifdef DEBUG
  auto diff=chrono::system_clock::now()-tStart;
	cerr<<"\nExecution time: "<<chrono::duration<dd,milli>(diff).count()<<" ms.\n";
#endif
return 0;
}


Measured memory_bytes: 256