akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
struct Edge { int dst,w; };
 
const int MAX = 110;
int V,E,sp,ep,iHIT;
vector<Edge> G[MAX];
int maxi[MAX];
 
 
void compute(){
  bool update = true;
  rep(i,V) maxi[i] = 0;
  vector<int> gotoMaxi,candidate;
  gotoMaxi.push_back(sp);
  while( update ) {
    update = false;
    rep(i,(int)gotoMaxi.size()) maxi[gotoMaxi[i]] = iHIT;
    gotoMaxi.clear();
    candidate.clear();

    rep(i,V*3+1) {
      rep(j,V) if( j != ep && maxi[j] ) {
        rep(k,(int)G[j].size()) {
          Edge &e = G[j][k];
          if( maxi[e.dst] < min(maxi[j]+e.w,iHIT) ) {
            update = true;
            maxi[e.dst] = min(maxi[j]+e.w,iHIT);
            if( i == V*3 ) candidate.push_back(e.dst);
          }
        }
      }
    }
    
    //cout<<endl;
    //for(int i=0;i<(int)candidate.size();i++)cout<<candidate[i]<<endl;
    
    int maxValue = 0;
    rep(i,(int)candidate.size()) maxValue = max(maxValue,maxi[candidate[i]]);
    if( maxValue ) rep(i,(int)candidate.size()){
       
        if( maxValue == maxi[candidate[i]] ){
          
          gotoMaxi.push_back(candidate[i]);
        }
      }
    
    
  }
 
  /*
    
  */
 
 
  if( maxi[ep] == 0 ) puts("GAME OVER");
  else                cout << maxi[ep] << endl;
 
}
 
int main(){
  int CNT = 1;
  while( cin >> V >> E, V | E ){
    rep(i,V) G[i].clear();
    rep(i,E){
      int s,t,c;
      cin >> s >> t >> c;
      G[s].push_back((Edge){t,c});      
    }
    cin >> sp >> ep >> iHIT;
    cout << "Case " << CNT++ << ": ";
    compute();
  }
  return 0;
}

Measured memory_bytes: 1276
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);

		String W = sc.next();

		if (W.contains("9")){
			System.out.println("Yes");
		}
		else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++)
    {
        cin >> A.at(i);
    }
    int count=0;
    for(int i=1; i<=N-2; i++)
    {
        if(((A.at(i)-A.at(i-1)<0)&&(A.at(i)-A.at(i+1)>0))||((A.at(i)-A.at(i-1)>0)&&(A.at(i)-A.at(i+1)<0)))
        {
            count++;
        }
    }
    cout << count << endl;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
#define pb push_back
#define mp make_pair

typedef struct data{
	int x;
	int y;
}data;

int ans[21][21];
int h,w;	

int isvalid(int x,int y){
	if(x<h && y<w && x>=0 && y>=0 && ans[x][y])
		return 1;
	return 0;
}

int bfs(data source){
	if(!isvalid(source.x,source.y)){
		return -1;
	}
	int visited[21][21]={0};
	queue <pair<data,int>> q;

	q.push(mp(source,0));
	visited[source.x][source.y]=1;
	int ans=0;
	while(!q.empty()){
		pair<data,int> c = q.front();
		
		data p = c.first;
		int row = p.x;
		int col = p.y;
		int val = c.second;
		q.pop();
		ans=max(ans,val);
		if(isvalid(row+1,col) && !visited[row+1][col]){
			visited[row+1][col]=1;
			data temp;
			temp.x = row+1;
			temp.y = col;
			q.push(mp(temp,val+1));

		}
		if(isvalid(row-1,col) && !visited[row-1][col]){
			visited[row-1][col]=1;
			data temp;
			temp.x = row-1;
			temp.y = col;
			q.push(mp(temp,val+1));
		}
		if(isvalid(row,col+1) && !visited[row][col+1]){
			visited[row][col+1]=1;
			data temp;
			temp.x = row;
			temp.y = col+1;
			q.push(mp(temp,val+1));

		}
		if(isvalid(row,col-1) && !visited[row][col-1]){
			visited[row][col-1]=1;
			data temp;
			temp.x = row;
			temp.y = col-1;
			q.push(mp(temp,val+1));

		}
	}
	return ans;
}

int main()

{
	int i,j;
	scanf("%d%d",&h,&w);
	char a[21][21];
	for(i=0;i<h;i++){
		scanf("%s",a[i]);
		for(j=0;j<w;j++){
			if(a[i][j]=='#'){
				ans[i][j]=0;
			}
			else
				ans[i][j]=1;
		}
	}

	data source;
	int fin=-1;
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			source.x = i;
			source.y = j; 
			int ans1=bfs(source);
				fin=max(fin,ans1);
		}

	}

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

	return 0;
}


Measured memory_bytes: 256
/**
表計算を行う簡単なプログラムを作成します。

表の行数rと列数c、r × c の要素を持つ表を読み込んで、
各行と列の合計を挿入した新しい表を出力するプログラムを作成して下さい。

 */

/*sucannerクラス使うためにインポート*/
import java.util.Scanner;

class Main {
	// プログラムのエントリポイント
	public static void main(String[] args) {
		// 入力ストリームの生成
		Scanner sc = new Scanner(System.in);
		int intR = sc.nextInt();
		int intC = sc.nextInt();

		int Hyou[][] = new int[intR][intC];
		int intYokogoukei = 0;
		int intTategoukei = 0;
		int i = 0;
		int j = 0;
		int intSaigo = 0;
		for (i = 0; i < intR; i++) {

			for (j = 0; j < intC; j++) {
				Hyou[i][j] = sc.nextInt();
				intYokogoukei += Hyou[i][j];
				intSaigo += Hyou[i][j];
				System.out.print(Hyou[i][j] + " ");

			}
			System.out.println(intYokogoukei);
			intYokogoukei = 0;
		}
		for (int k = 0; k < intC; k++) {
			for (int l = 0; l < intR; l++) {
				intTategoukei += Hyou[l][k];

			}
			System.out.print(intTategoukei + " ");
			intTategoukei = 0;
		}
		System.out.println(intSaigo);

	}
}

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

#define ll long long
const ll Max=100010;
int n,m;
ll num[Max],ans,pre;

int Read()  //读入优化
{
    int i=0,f=1;
    char ch;
    for(ch=getchar();!isdigit(ch) && ch!='-';ch=getchar());
    if(ch=='-')
    {
        f=-1; 
        ch=getchar();
    }
    for(;isdigit(ch);ch=getchar())
        i=(i<<3)+(i<<1)+ch-'0';      //位运算，相当于 i=i*10+c-'0'
    return i*f;
}


int main()
{
	n=Read();m=Read();
	for(ll i=1;i<=n;i++)
		num[i]=Read();
	for(ll i=1;i<=n;i++)
	{
		if(num[i]+pre>m)
			ans+=num[i]+pre-m,pre=num[i]-(num[i]+pre-m);
		else
			pre=num[i];
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,b,c;
  cin>>a>>b>>c;
  if((a==b && a!=c && b!=c) || (b==c && b!=a && c!=a) || (a==c && a!=b && b!=c))
    cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[n-1];
    for (int i=0;i<n;i++){
        int value;
        cin>>value;
        a[i]=value;
    }
    for (int j=0;j<n-1;j++){
        cout<<a[n-j-1]<<" ";
    }
    cout<<a[0]<<endl;
    return 0;
}



Measured memory_bytes: 3072
mod = 998244353
N = int(input())
D = list(map(int, input().split()))
if D[0] !=0:
    print(0)
else:
    cnt = [0]*N
    for i, d in enumerate(D):
        cnt[d]+=1
    cum = 1
    ans = 1
    for i in range(1, N):
        c = cnt[i]
        if c==0:
            break
        ans*=pow(cnt[i-1], c, mod)
        ans%=mod
        cum+=c
    if cum == N:
        print(ans)
    else:
        print(0)


Measured memory_bytes: 53812
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//String s = sc.next();
		//String t = sc.next();
		//String g = sc.next();
		long n = sc.nextLong();
		//long m = sc.nextLong();
		//long k = sc.nextLong();
		//long l = sc.nextLong();
		long count=0;
		long[] array=new long[3];

		/*for(int i=0;i<=3;i++) {
			if(s.substring(i,i+1).equals("+")) {
				count++;
			}else {
				count--;
			}
		}*/
		//Arrays.sort(array);
		if(n%2==0) {
			System.out.println(n*n/4);
		}else {
			System.out.println((n/2)*(n/2+1));
		}
		//System.out.println();
		//System.out.println(Math.abs(array[2]-array[1])+Math.abs(array[1]-array[0]));
	}
}




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

int solve(){
  int n;  cin >> n;
  int a, ans=0, num=1, check=false;
  for(int i=0; i<n; i++)  {
    cin >> a;
    if(a==num)  {
      num++;
      check = true;
    }
    else  ans++;
  }
  cout << (check ? ans : -1) << endl;
}

int main(){
  solve();
  return 0;
}


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

#define REP(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define REPS(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define RREP(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define RREPS(i, n) for (int i = ((int)(n)); i > 0; i--)
#define IREP(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define IREPS(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RVISORT(v) sort(v.begin(), v.end(), greater<int>());
#define ALL(v) v.begin(), v.end()
#define MP(n, m) make_pair(n, m);
#define COUT(d) cout<<std::setprecision(10)<<d<<endl;
#define CIN(n) getline(cin,n);

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using ll = long long;
using ul = unsigned long;

typedef long long ll;

template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }

const int mod=1e9+7;


void printv(VI& v){
  REP(i,v.size()) cout << v[i] << " ";
  cout << endl;
}

int vtotal(VI& v){
  int total=0;
  REP(i,v.size()) total+=v[i];
  return total;
}

int main()
{
  cin.tie( 0 );
  ios::sync_with_stdio( false );
	
  //init(); // mint初期化

  ll n;
  cin>>n;

  ll ans=0;
  REPS(i,n){
    string now=to_string(i);
    if(now.size()%2==1)ans++;
  }

  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int N;
	int i;
	int cnt=0;
	
	scanf("%d",&N);
	
	int A[N];
	int B[N];
	int C[N-1];
	for(i=0;i<N;i++){
		scanf("%d",&A[i]);
	}
	for(i=0;i<N;i++){
		scanf("%d",&B[i]);
	}
	for(i=0;i<N-1;i++){
		scanf("%d",&C[i]);
	}

	for(i=0;i<N-1;i++){
		if((A[i+1]-A[i])==1){
			cnt+=B[A[i]-1];
			cnt+=C[A[i]-1];
		}else{
			cnt+=B[A[i]-1];
		}
	}
	cnt+=B[A[i]-1];

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

	return 0;
}




Measured memory_bytes: 128
#include <iostream>
#include<vector>
#include<algorithm>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include<iomanip>

using namespace std;
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define i64 int64_t
#define tos(x) to_string(x)

int main() {
	string n;
	cin >> n;
	if ((n[0] == n[1] && n[1] == n[2]) || (n[1] == n[2] && n[2] == n[3])) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#define rep(i, n) for (int i=0; i<n; ++i)
#define FOR(i, a, b) for (int i=a; i<b; ++i)
#define pb(x) push_back(x)
#define ll long long
#define ul unsigned long long
#define dbg(x) cout  << #x << " : " << (x) << endl
#define out(x) cout << (x)
#define outl(x) cout << (x) << endl
#define int(n); int n; cin >> n;
#define long(n); long long n; cin >> n;
#define dbl(f); double f; cin >> f;
#define s(s); string s; cin >> s;
#define into(a, n) for (int i = 0; i < n; ++i) cin >> a[i]
using namespace std;

const int inf =1500000000;

int a[11],b[11],c[11];

bool dfs(int l,char x) {
  if (l>=11) return true;
  if (x=='b') {
    b[l]=a[l];
    rep(i, l) if(b[l]<b[i]) {b[l]=-1; return false;}
  }
  if (x=='c') {
    c[l]=a[l];
    rep(i, l) if(c[l]<c[i]) {c[l]=-1; return false;}
  }
  bool p= dfs(l+1,'b')||dfs(l+1,'c');
  b[l]=-1;c[l]=-1;
  return p;
}

int main () {
  int(n);
  bool flg;
  rep(i, n) {
    flg=false;
    b[0]=-1;c[0]=-1;
    FOR(i, 1, 11) {
      cin>>a[i];
      b[i]=-1; c[i]=-1;
    }
    flg=dfs(1,'b')||dfs(1,'c');
    outl(flg?"YES":"NO");
  }
  return 0;
}

Measured memory_bytes: 1152
import copy

def splitAndPlus(s,len,cursor):

	if len - 1 > cursor :

		s2 = copy.copy(s)
		joined = ''.join([s2.pop(cursor),s2.pop(cursor)])
		nokori = s2
		nokori.insert(cursor,joined)

		return splitAndPlus(s,len,cursor+1) + splitAndPlus(nokori,len-1,cursor)

	else: 
		# print('s is', s,cursor)
		if s is None:
			return 0
		else:	
			numss = [ int(i) for i in s]
			return sum(numss)



inp = input()
s = [inp[i]  for i in range(len(inp))]

print(splitAndPlus(s,len(s),0))



Measured memory_bytes: 3444
#include <stdio.h>

int gcd (int a, int b){
	if (a%b == 0) return b;
	return gcd (b, a%b);
}	

int main(void) {
	int a, b, g, tmp;
	while (scanf ("%d %d", &a, &b) != EOF){
		if (a<b){
			tmp = a;
			a = b;
			b = tmp;
		}
		g = gcd (a, b);
		printf ("%d %d\n", g, a/g*b);
	}
	return 0;
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (a + b > c + d)
    cout << "Left" << endl;
  else if (a + b < c + d)
    cout << "Right" << endl;
  else
    cout << "Balanced" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void printvec(vector<int> vec) {
  int i;
  for (i = 0; i < vec.size() - 1; i++) {
    cout << vec.at(i) << " ";
  }
  cout << vec.at(i) << endl;
}

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

  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }
  printvec(a);

  int v, j;
  for (int i = 1; i < n; i++) {
    v = a.at(i);
    j = i - 1;
    while (j >= 0 && a.at(j) > v) {
      a.at(j + 1) = a.at(j);
      j--;
    }
    a.at(j + 1) = v;
    printvec(a);
  }
}


Measured memory_bytes: 3144
import numpy as np

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
dp = np.array([[0 for j in range(W+1)] for _ in range(N+1)])
for i in range(1, N+1):
    w, v = items[i-1]
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.maximum(dp[i-1, :-w] + v, dp[i-1, w:])
print(dp[N, W])

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

using namespace std;

int main(void){

    int a, b;
    cin >> a >> b;
    
    int count = 0;
    for(int i=a; i<=b; i++) {
        string s = to_string(i);
        string s_rev = s;
        reverse(s_rev.begin(), s_rev.end());
        if(s == s_rev) count++;
    }

    cout << count << endl;

    return 0;
    
}


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

void MatrixChainOrder(int *p,int pLength){
  int i,l,j,k,q,n;
  int m[pLength][pLength];

  n=pLength-1;

  for(i=1;i<=n;i++){
    m[i][i]=0;
  }
  for(l=2;l<=n;l++){
    for(i=1;i<=n-l+1;i++){
      j=i+l-1;
      m[i][j]=INT_MAX;
      for(k=i;k<=j-1;k++){
	q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

	if(m[i][j]<q){
	  m[i][j]=m[i][j];
	}
	else{
	  m[i][j]=q;
	}

      }
    }
  }
  printf("%d\n",m[i][j]);
}

int main(){
  int i,pLength,factor2;
  int *factor;
  
  scanf("%d",&pLength);
  factor=malloc(sizeof(int)*(pLength+2));
  
  for(i=1;i<=pLength;i++){
    if(i<pLength){
      scanf("%d%d",&factor[i],&factor2);
    }
    else if(i==pLength){
      scanf("%d%d",&factor[i],&factor[i+1]);
    }
  }

  MatrixChainOrder(factor,pLength+2);
  
  return 0;
}

Measured memory_bytes: 636
from collections import defaultdict
from heapq import heappush, heappop

v, e, r = map(int, input().split())
E = defaultdict(list)
for i in range(e):
    s, t, d = map(int, input().split())
    E[s].append((t, d))

D = [float("inf")]*v
D[r] = 0

q = []
heappush(q, (r, 0))
while q:
    now, dist = heappop(q)
    if D[now] < dist:
        continue

    for nxt, w in E[now]:
        t = dist + w
        if t < D[nxt]:
            D[nxt] = t
            heappush(q, (nxt, t))

for i in range(v):
    if D[i] == float("inf"):
        print("INF")
    else:
        print(D[i])


Measured memory_bytes: 148312
#include <stdio.h>

int main(void)
{
	int a, b;
	double f;

	scanf("%d %d", &a, &b);
	if(b == 0)
		return -1;
	printf("%d %d %.5f\n", a / b, a % b, (double)a / b);

	return 0;
}

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

int to[200010];
ll ord[200010];

int main(){
  ll N,K;
  cin >> N >> K;
  REP(i,N) { cin >> to[i]; to[i]--; }

  REP(i,N+1) ord[i] = -1;
  int v = 0;
  ll num = 0;
  ll nmax = 0;
  ll h = 0;
  while(1) {
//    cout << v << " " << num << " " <<  to[v] << endl;
    if ( ord[v] != -1 ) {
      h = ord[v];
      nmax = num - h;
      break;
    }
    ord[v] = num;
    num++;
    v = to[v];
  }
  if (K > h) {
    K -= h;
    K %= nmax;
    K += h;
  }
  REP(i,N) {
    if (ord[i] == K) {
      cout << i+1 << endl;
      break;
    }
  }
}


Measured memory_bytes: 5980
import bisect
ans = 0
N = int(input())
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
lis = factorization(N)
suum = [0]*(10**5)
for k in range(1,10**5):
    suum[k] = suum[k-1]+k
for j in range(len(lis)):
    index = bisect.bisect_right(suum,lis[j][1])
    ans += index
    if lis[j][1] >= 1:
        ans -= 1
if N != 1:
    print(ans)
else:
    print(0)

Measured memory_bytes: 14136
def main():
    n,k = map(int,input().split())
    if k%2==1:
        c = n//k
        print(c**3)
        return
    if k%2==0:
        c = (n-k//2)//k+1
        ans = c**3
        c = n//k
        print(ans + c**3)

if __name__ == "__main__":
    main()


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

int main()
{
	int H, W, N, x, y, tx, ty,res = 0;
	cin >> H >> W >> N;
	cin >> tx >> ty;
	for (int i = 1; i < N; i++) {
		cin >> x >> y;
		if ((x - tx) >= 0) {
			if (y - ty >= 0) {
				res += max(x-tx,y-ty);
			}
			else {
				res += (x - tx - y + ty);
			}
		}
		else {
			if (y - ty >= 0) {
				res += -x + tx+ y - ty;
			}
			else {
				res += max(-x + tx, -y + ty);
			}
		}
		
		tx = x;
		ty = y;
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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;
}

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return (b);
    }
    else
    {
        return (gcd(b, a % b));
    }
}

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}


template <typename T>
T amarinasi(T a,T b){
    if(a%b==0)
{
    return a/b;
}
else if(a%b>0)
{
    return a/b+1;
}
else
{
    return a/b-1;
}
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

//----------------------------------------------------------------

int main(){
ll a,b,c,d;
cin>>a>>b>>c>>d;
ll ans=(b-(b/c+b/d-b/lcm(c,d)))-((a-1)-((a-1)/c+(a-1)/d-(a-1)/lcm(c,d)));
cout<<ans<<endl;
return 0;
}










Measured memory_bytes: 256
import scala.io.StdIn._
object Main extends App {
  val s = readLine

  def dp(rems: Array[Long], d: Char): Array[Long] = {
    val ret = new Array[Long](13)
    val is = if (d == '?') (0 to 9) else Seq((d - '0').toInt)
    for {
      i <- is
      j <- (0 to 12)
    } {
      ret((j * 10 + i) % 13) += rems(j)
      ret((j * 10 + i) % 13) %= 1000000007
    }
    ret
  }

  val init = s.head match {
    case '?' => Array.tabulate(13)(i => if (i < 10) 1L else 0L)
    case d => Array.tabulate(13)(i => if (i == d - '0') 1L else 0L)
  }

  val result = s.tail.foldLeft(init)(dp)
  println(result(5))
}

Measured memory_bytes: 46696
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<int,int>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 1000000000000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
struct edge { int to, cost; };

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}

long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// mod. m での a の逆元 a^{-1} を計算するよ！
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


//aCbをmod.mで割った余りを求める
ll int c(ll int a, ll int b, ll int m) {
	ll int ans = 1;
	for (ll int i = 0; i < b; i++) {
		ans *= a - i;
		ans %= m;
	}
	for (ll int i = 1; i <= b; i++) {
		ans *= modinv(i, m);
		ans %= m;
	}
	return ans;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}
	int size(int a) {
		return par[root(a)];
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

int main() {
	int n, k;
	cin >> n >> k;
	hei(int) a(n);
	rep(i, 0, n)cin >> a[i];
	sort(a.begin(), a.end());
	int us = 0;
	rep(i,0,k)us += a[i];
	cout << us << endl;
	return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
int main() {double coor[22][2],ans=0;int i=0,N;while (scanf("%lf,%lf",&coor[i][0],&coor[i][1])!=EOF) i++;for (N=0;N<i;N++) ans+=coor[N][0]*coor[(N+1)%i][1]-coor[N][1]*coor[(N+1)%i][0];if (ans<0) ans=-ans;printf("%.6lf\n",ans/2);return 0;}

Measured memory_bytes: 0
N = readline.strip.to_i
P = readline.strip.split().map(&:to_i)

result=0;
P.each_with_index{|p, i|
  
  result+=1 if( i>0 && i<N-1 && ( (P[i-1] < P[i] && P[i] < P[i+1]) || (P[i-1] > P[i] && P[i] > P[i+1]) ) )
}

p result

Measured memory_bytes: 1788
import java.util.Scanner;
import java.util.InputMismatchException;
class Main{
public static void main(String args[]){
 
    Scanner scan = new Scanner(System.in);
    try{
	int W[] = new int[250];
	
	int H[] = new int[250];
   
	int cnt=0;

while(true){
     W[cnt]= scan.nextInt();
     H[cnt]=scan.nextInt();
     
     if ( H[cnt] == 0 && W[cnt]==0 ) break;
     cnt++;

}     


 for ( int p = 0; p < cnt; p++ ){
     for ( int i = 0; i < W[p]; i++ ){
	 for ( int j = 0; j < H[p]; j++ ){
	     if(i==0||i==W[p]-1 ||j==0 ||j==H[p]-1){
		 System.out.print("#");
	     } else {
		 System.out.print(".");
	     }
	 }
System.out.print("\n");
	
     }System.out.print("\n");
 }
 
}catch (InputMismatchException e) {
            System.out.println("try again!!");
        }
 
 
 
 
 
}
}



Measured memory_bytes: 37360
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	final boolean DEBUG = false;

	class PriorityQueue {
		final int MAX_HEAP = 2000000 + 1;
		int[] heap;
		int h, startIndex;
		PriorityQueue() {
			this.heap = new int[MAX_HEAP];
			this.h = 0;
			this.startIndex = 1;
		}
		void insert(int k) {
			h++;
			this.heap[h] = k;
			int i = h;
			while (i > 1 && heap[i] > heap[i / 2]) {
				int tmp = heap[i];
				heap[i] = heap[i / 2];
				heap[i / 2] = tmp;
				i = i / 2;
			}
		}
		void extract() {
			System.out.println(heap[1]);
			heap[1] = heap[h];
			h--;
			maxHeapify(1);
		}
		void maxHeapify(int i) {
			int left = 2 * i;
			int right = 2 * i + 1;
			int largest = 0;
			if (left <= h && heap[left] > heap[i])
				largest = left;
			else
				largest = i;

			if (right <= h && heap[right] > heap[largest])
				largest = right;

			if (largest != i) {
				int tmp = heap[i];
				heap[i] = heap[largest];
				heap[largest] = tmp;
				maxHeapify(largest);
			}
		}
		void buildMaxHeap() {
			for (int i = h / 2; i >= 1; i--)
				maxHeapify(i);
		}
		void printDebug() {
			System.out.print("debug: ");
			for (int i = startIndex; i <= (h % MAX_HEAP); i++)
				System.out.print(heap[i] + " ");
			System.out.println();
		}
	}

	void run() {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		PriorityQueue que = new PriorityQueue();
		while (true) {
			String inst = "";
			try {
				inst = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			int k = 0;
			if (inst.length() > 6 && inst.charAt(6) == ' ') {
				k = Integer.parseInt(inst.substring(7, inst.length()));
				inst = inst.substring(0, 6);
			}
			switch (inst) {
			case "insert":
				if (DEBUG)
					System.out.println("insert " + k);
				que.insert(k);
				break;
			case "extract":
				if (DEBUG)
					System.out.print("expact: ");
				que.extract();
				break;
			case "end":
				return;
			}
			if (DEBUG)
				que.printDebug();
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}



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

using namespace std;

long long gcd(long long a,long long b)
{
    if(!b) return a;
    else return gcd(b,a%b);
}

int main()
{
    long long a,b;
    cin >> a >> b;
    cout << a*b/gcd(a,b) << endl;
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,b) FOR(i,0,b)
using namespace std;
 
int main(void) {
	int count = 1;
	long long int mini, sum;
	long long int q, h, s, d;
	long long int n;
	cin >> q >> h >> s >> d;
	cin >> n;
	if (4 * q > h * 2) {
		count = 2;
		mini = h * 2;
	}
	else {
		count = 1;
		mini = q * 4;
	}
	if (mini > s) {
		count = 3;
		mini = s;
	}
	if (mini * 2 > d) {
		sum = (n / 2)*d + (n % 2)*mini;
		cout << sum << endl;
	}
	else {
		sum = n*mini;
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 256
a, b, k = gets.split(" ").map(&:to_i)

left = [a]
(k-1).times do
  break if b < left[-1] + 1
  left << left[-1] + 1
end

right = [b]
(k-1).times do
  break if right[0] - 1 < a
  right.unshift(right[0] - 1)
end

puts [left + right].flatten.uniq.join("\n")

Measured memory_bytes: 3836
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define rep(i, n) for (i = 0; i < n; i++)
#define rrep(i, n) for (i = n; i >= 0; i--)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)

int main() {
    int n;
    scanf("%d", &n);

    int x = n * 800;
    int y = (n / 15) * 200;

    printf("%d\n", x - y);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define lli long long int
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(lli i=0, i##_len=(lli)(n); i<i##_len; i++)
#define repf(i, n) for(lli i=1, i##_len=(lli)(n+1); i<i##_len; i++)
#define per(i, n) for(lli i=((lli)(n))-1; i>=0; i--)
#define perf(i, n) for(lli i=((lli)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<lli>
#define vvi vector<vector<lli>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    lli a, b; cin >> a >> b;
    if(2*b >= a) cout << "0" << endl;
    else cout << a-b-b << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
A,B = map(int,input().split())

def hoge(N):
  tmp = N//2
  if N%2 == 1:
    tmp+=1
    last=0
  else:
    last=N
  if tmp%2 == 1:
    return last+1
  else:
    return last

print(hoge(A-1) ^ hoge(B))

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

int main()
{
	int n;
	int res = 0;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		res += i;
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
n=int(input())
#n,m,q=map(int,input().split())

use=0b000
count=0
def dfs(cur,use):
    global count
    if cur>n:
        return
    if use==0b111:
        count+=1
    dfs(10*cur+3,use|0b001)
    dfs(10*cur+5,use|0b010)
    dfs(10*cur+7,use|0b100)
dfs(0,0b000)
print(count)

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

typedef long long int lli;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<lli> vli;
typedef priority_queue <int, vector <int>, greater <int> > min_pq;

const int MOD	= 1e9 + 7;

#define fastio			ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define init(a)         memset(a,0,sizeof(a))    
#define pb              push_back  
#define all(a)          a.begin(),a.end()  
#define loop(i,n)       for(int i=0;i<n;i++)  
#define loops(i,s,n)    for(int i=s;i<n;i++)
#define rloop(i,n)      for(int i=n-1;i>=0;i--)
#define rloops(i,s,n)   for(int i=n-1;i>=s;i--)

template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template <typename T> T lcm(T a, T b){return (a*b)/gcd(a,b); }


double tick(){static clock_t oldt,newt=clock();double diff=1.0*(newt-oldt)/CLOCKS_PER_SEC;oldt=newt;return diff;}
//---------------------------------------------------------------------------------------------


int main(){
    fastio;

    

    int h, n;
    cin>>h>>n;

    int a[n];
    loop(i,n){
        cin>>a[i];
    }

    lli s = 0;
    loop(i,n){
        s += a[i];
    }

    if(h <= s){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    

    // cout<<"Execution time : "<<tick()<<"\n";

    return 0;
}

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

int main() {
    int a,b,c,x,y;
    cin>>a>>b>>c>>x>>y;
    ll res,ans=a*x+b*y;
    for (int k=0; k<=2*max(x,y); k+=2) {
        int i=x-k/2;
        int j=y-k/2;
        i=max(i,0),j=max(j,0);
        res=a*i+b*j+c*k;
        ans=min(res,ans);
    }
    cout<<ans<<endl;
}   


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

#define MAX 100005
#define NIL -1

struct Node {
  int parent, child, rightSibling;
};

Node T[MAX];
int n, D[MAX];

void print(int u) {
  int i, c;
  cout << "node " << u << ": ";
  cout << "parent = " << T[u].parent << ", ";
  cout << "depth = " << D[u] << ", ";

  if (T[u].parent == NIL)
    cout << "root, ";
  else if (T[u].child == NIL)
    cout << "leaf, ";
  else
    cout << "internal node, ";

  cout << "[";

  for (i = 0, c = T[u].child; c != NIL; i++, c = T[c].rightSibling) {
    if (i) cout << ", ";
    cout << c;
  }
  cout << "]" << endl;
}

int rec(int u, int p) {
  D[u] = p;
  if (T[u].rightSibling != NIL) rec(T[u].rightSibling, p);
  if (T[u].child != NIL) rec(T[u].child, p + 1);
}

int main() {
  int degree, targetId, inputId, lastId, rootId;

  cin >> n;
  for (int i = 0; i < n; i++) {
    T[i].parent = T[i].child = T[i].rightSibling = NIL;
  }

  for (int i = 0; i < n; i++) {
    cin >> targetId >> degree;
    for (int j = 0; j < degree; j++) {
      cin >> inputId;
      if (j == 0)
        T[targetId].child = inputId;
      else
        T[lastId].rightSibling = inputId;
      lastId = inputId;
      T[inputId].parent = targetId;
    }
  }
  for (int i = 0; i < n; i++) {
    if (T[i].parent == NIL) rootId = i;
  }

  rec(rootId, 0);

  for (int i = 0; i < n; i++) {
    print(i);
  }

  return 0;
}


Measured memory_bytes: 7760
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt();
            int Y = in.nextInt();

            for (int _1e4 = 0; _1e4 <= N; _1e4++) {
                for (int _5e3 = 0; _1e4 + _5e3 <= N; _5e3++) {
                    int _1e3 = N - (_1e4 + _5e3);
                    if (_1e4 * 10000 + _5e3 * 5000 + _1e3 * 1000 == Y) {
                        System.out.println(_1e4 + " " + _5e3 + " " + _1e3);
                        return;
                    }
                }
            }

            System.out.println("-1 -1 -1");
        }
    }
}


Measured memory_bytes: 27276
n = int(input())
ans = [0,0,0,0]
for _ in range(n):
  s = input()
  if s == 'AC':
    ans[0] += 1
  elif s == 'WA':
    ans[1] += 1
  elif s == 'TLE':
    ans[2] += 1
  else:
    ans[3] += 1
print('AC x ' + str(ans[0]))
print('WA x ' + str(ans[1]))
print('TLE x ' + str(ans[2]))
print('RE x ' + str(ans[3]))

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

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

    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v.at(i);
    }

    // 奇数番目と偶数番目に登場する数値で一番多いものを求める
    vector<int> odd(100000);
    vector<int> even(100000);
    for (int i = 0; i < n; i++) {
        if(i%2==0) odd.at(v.at(i) - 1)++;
        else even.at(v.at(i) - 1)++;
    }

    int odd_max = 0;
    int even_max = 0;
    int odd_max_index;
    int even_max_index;
    for (int i = 0; i < 100000; i++) {
        if(odd.at(i) > odd_max) {
            odd_max = odd.at(i);
            odd_max_index = i;
        }
        if(even.at(i) > even_max) {
            even_max = even.at(i);
            even_max_index = i;
        }
    }
    if (odd_max_index != even_max_index){
        cout << n - odd_max - even_max << endl;
        return 0;
    }

    // 2番目に多い数を探す
    int odd_max_sec = 0;
    int even_max_sec = 0;
    for (int i = 0; i < 100000; i++) {
        if(i == odd_max_index) continue;
        if(odd.at(i) > odd_max_sec) {
            odd_max_sec = odd.at(i);
        }
        if(even.at(i) > even_max_sec) {
            even_max_sec = even.at(i);
        }
    }
    
    if (odd_max_sec >= even_max_sec) {
        cout << n - odd_max_sec - even_max << endl;
    } else {
        cout << n - odd_max - even_max_sec << endl;
    }

}

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

const int N = 110;
int a[N];
int n;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	int i;
	for (i = 0; i < n; i++) {
		if (a[i] % 2 == 0) {
			if (a[i] % 3 != 0 && a[i] % 5 != 0) {
				break;
			}
		}
	}

	if (i == n) {
		puts("APPROVED");
	}
	else {
		puts("DENIED");
	}

	return 0;
}

Measured memory_bytes: 256
import itertools

n = int(input())
s1 = list(map(int,input().split()))
s2 = list(map(int,input().split()))
count = 0

for i in itertools.permutations(range(1, n + 1)):
  count += 1
  if i == tuple(s1):
    ans1 = count
  if i == tuple(s2):
    ans2 = count

print(abs(ans1 - ans2))





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

int compare(const void *a, const void *b);

int main(void){
	int i, n, k;
	long x=0;

	scanf("%d%d", &n, &k);
	int *p = (int *)malloc(sizeof(int)*n);
	for(i=0; i<n; i++){
		scanf("%d",p+i);
	}
	qsort(p, n, sizeof(int), compare);
	for(i=k; i<n; i++){
		x += *(p+i);
	}
	free(p);
	printf("%ld\n", x);
	return 0;
}

int compare(const void *a, const void *b){
	int aNum = *(int *)a;
	int bNum = *(int *)b;

	if(aNum > bNum){
		return -1;
	}else if(aNum < bNum){
		return 1;
	}
	return 0;
}

Measured memory_bytes: 3036
import java.util.Arrays;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

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

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

        System.out.println(solve(N, D));

        sc.close();
    }

    static int solve(int N, int[] D) {
        Set<Integer> setD = Arrays.stream(D).boxed().collect(Collectors.toSet());

        for (int i = N;; ++i) {
            if (String.valueOf(i).chars().allMatch(ch -> !setD.contains(ch - '0'))) {
                return i;
            }
        }
    }
}

Measured memory_bytes: 39432
using System;

namespace B
{
    class Program
    {
        static void Main(string[] args)
        {
            string in_d, in_h;
            int result;
            in_d = Console.ReadLine();
            in_h = Console.ReadLine();
            string[] d_array = in_d.Split(' ');
            string[] h_array = in_h.Split(' ');
            result = int.Parse(d_array[0]);
            foreach(string i in h_array)
            {
                result -= int.Parse(i);
            }
            if (result < 0)
                {
                    Console.WriteLine("-1");
                }
            else
            {
                Console.WriteLine(result);
            }
        }
    }
}

Measured memory_bytes: 28464
k = int(input())
A = list(map(int, input().split()))
UP = 2
DOWN = 2 
for a in A[::-1]:
  DOWN = ((DOWN - 1) // a + 1) * a
  UP = UP // a * a + a  - 1
  if UP < DOWN:
    print(-1)
    exit()
print(DOWN, UP)

Measured memory_bytes: 14224
#include <bits/stdc++.h>
#define BASE 1000003
using namespace std;

long mod_fact[BASE];
long mod_inv_fact[BASE];

long mod_pow(long x, int k) {
    long ret = 1;
    while (k > 0) {
        if (k & 1) {
            ret = (ret * x) % BASE;
        }
        k >>= 1;
        x = (x * x) % BASE;
    }
    return ret;
}

inline long mod_inv(long x) {
    return mod_pow(x, BASE - 2);
}

void init() {
    mod_fact[0] = mod_inv_fact[0] = 1;
    for (int i = 1; i < BASE; i++) {
        mod_fact[i] = (mod_fact[i - 1] * i) % BASE;
        mod_inv_fact[i] = mod_inv(mod_fact[i]);
    }
}

long solve() {
    long x, d, n;
    cin >> x >> d >> n;
    if (d == 0) {
        return mod_pow(x, n);
    }
    if (n >= BASE) {
        return 0;
    }
    x = (x * mod_inv(d)) % BASE;
    if (x == 0 || x > (x + n - 1) % BASE) {
        return 0;
    }
    return (mod_pow(d, n) * ((mod_fact[x + n - 1] * mod_inv_fact[x - 1]) % BASE)) % BASE;
}

int main() {
    int q;
    cin >> q;
    init();
    for (int i = 0; i < q; i++) {
        cout << solve() << endl;
    }
    return 0;
}


Measured memory_bytes: 16512
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

use std::cmp::{max, min};

fn main() {
  let a = read::<i64>();
  let b = read::<i64>();
  let c = read::<i64>();

  let ans = c - (a - b);

  if ans > 0 {
    println!("{}", ans)
  } else {
    println!("0")
  }

}



Measured memory_bytes: 4352
from collections import deque
from collections import defaultdict
from collections import Counter

N,M = list(map(int,input().split()))
G = defaultdict(set)

color = [0 for i in range(N+1)]

for _ in range(M):
    A,B = map(int,input().split())
    G[A].add(B)
    G[B].add(A)

color[1] = 1
que = deque([1])
concatenation = False

while len(que):
    p = que.popleft()
    for q in list(G[p]):
        if color[q] == 0:
            color[q] = -color[p]
            que.append(q)
        elif color[q] == color[p]:
            concatenation = True
            break
    
if concatenation:
    print(int(N*(N-1)/2-M))
else:
    B = Counter(color)[1]
    W = Counter(color)[-1]
    print(B*W-M)


Measured memory_bytes: 40540
# -*- coding:utf-8 -*-
n = int(input())

PosList = []
TempSum = 0
ReturnSum = 0

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


for pos in range(1,101):
    TempSum = 0
    for nPos in range(n):
        TempSum += (pos - PosList[nPos])**2
    if pos == 1:
        ReturnSum = TempSum
    elif ReturnSum > TempSum:
        ReturnSum = TempSum
    """
    print("Position = "+str(pos))
    print("TempSum = "+ str(TempSum))
    print("ReturnSum = " + str(ReturnSum))
    print("----------------------------")
    """

print(ReturnSum)

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

int main() {
  string str;
  int q;
  cin >> str >> q;
  for (int i=0; i<q; i++) {
      string mere;
      cin >> mere;
      int a,b;
      cin >> a >> b;
      if (mere=="print") {
          cout << str.substr(a,b-a+1) << endl;
      }
      else if (mere=="replace") {
          string p;
          cin >> p;
          str= str.substr(0,a) + p + str.substr(b+1,str.size()-b+1 ) ;
      }
      else {
          string x=str.substr(a,b-a+1);
          reverse(x.begin(),x.end());
          str= str.substr(0,a) + x + str.substr(b+1,str.size()-b+1 ) ;
      }
  }
}


Measured memory_bytes: 3232
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <sstream>
#include <bitset>
#include <cassert>
#include <fstream>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
#define DBG(X) cout << #X << "=" << (X) << endl;
#else
#define DBG(X)
#endif
 
using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF  = (ll)(2e18);

const ll mod = 1e9 + 7;
const int NIL = -1;
static mt19937 _g(time(nullptr));

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for(auto el: v) cout << el << " "; return os; }

void solve()
{
	int n;
	cin >> n;

	vector<int> p(n);

	for(auto& elem: p)
		cin >> elem;

	int cnt = 0;

	for(int i = 1; i < n - 1; ++i)
		cnt += (p[i] + min({p[i - 1], p[i], p[i + 1]}) + max({p[i - 1], p[i], p[i + 1]}) == p[i - 1] + p[i] + p[i + 1]);

	cout << cnt << endl;
}

int main()
{
	fast_io();
	solve();

	return 0;
}


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

using namespace std;

int main() {
  int n, k;
  cin >> n;
  k = log10(n);

  int odd = 0;
  for (int i = 1; i <= k; i++) {
    if (i%2==0 && i!=k){//odd digit and not top
      odd += (10 * pow(10, i)) -  (1 * pow(10, i));
      //cout << i+1 << " " << odd << endl;
    }if (i%2==0 && i==k) {//odd digit and top
      odd+= n - pow(10, i) + 1;
    }
  }
  if (n >=10){
    odd+=9;
  } else{
    odd+=n;
  }
  cout << odd << endl;
  return 0;
}


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

int main()
{
  int A, B;
  cin >> A >> B;
  const auto plus = A + B;
  const auto minus = A - B;
  const auto times = A*B;
  cout << (plus < minus ? (minus < times ? times : minus) : (plus < times ? times : plus));
  return 0;
}


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

int main(){
 int N;
 cin >> N;
 int t = 0;
 for(int i = 0; i < 26; i++){
     for(int j = 0; j < 16; j++){
         if( 4 * i + 7 * j == N){
             t += 1;
             break;
         }
     }
 }
 if(t != 0){
     cout << "Yes" << endl;
 }else{
     cout << "No" << endl;
 }
}

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

int main() {
  int n;
  cin >> n;
  vector<ll> h(n);
  for (int i = 0; i < n; i++) cin >> h[i];
  
  const ll INF = 1LL << 60;
  vector<ll> dp(n, INF);
  dp[0] = 0;
  for (int i = 1; i < n; i++) {
    dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]));
    if (i > 1) dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]));
  }
  
  cout << dp[n-1] << endl;
}

Measured memory_bytes: 4772
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

N = 10000
def tokey(i, j, k):
    return i*N*N + j*N + k
def dekey(n):
    i = int(n / N / N)
    j = int(n / N) % N
    k = n % N
    return i, j, k

def main():
    X, Y, Z, K = i2nn()
    A = i2nn()
    B = i2nn()
    C = i2nn()
    A.sort()
    A.reverse()
    B.sort()
    B.reverse()
    C.sort()
    C.reverse()
    Q = [(A[0] + B[0] + C[0], 0, 0, 0)]
    loop = 0
    stored = set()
    def next(i, j, k):
        if i >= X or j >= Y or k >= Z:
            return
        key = tokey(i, j, k)
        if key not in stored:
            stored.add(key)
            n = A[i] + B[j] + C[k]
            Q.append((n, i, j, k))
    while True:
        v = max(Q, key=lambda v: v[0])
        Q.remove(v)
        print(v[0])
        loop += 1
        if loop >= K:
            break
        next(v[1]+1, v[2], v[3])
        next(v[1], v[2]+1, v[3])
        next(v[1], v[2], v[3]+1)

main()


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

int main() {
	vector<int> a(5);
	cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
	vector<int> s = { 0, 1, 2, 3, 4 };
	int fans= 999999;
	do {
		int ans = 0;
		for (int i = 0; i < 5; ++i) {
			while (ans % 10 != 0) ans += 1;
			ans += a[s[i]];
		}
		fans= min(fans, ans);
	} while (next_permutation(s.begin(), s.end()));
	cout << fans<< endl;
	return 0;
}


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

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0;
    char now = '#';
    for (int i = 0; i < n; i++){
        if (now != s[i]){
            ans++;
            now = s[i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 512