akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main(){
    int D,N;cin>>D>>N;
    int64_t ans;

    if(N<100){
        ans=pow(100,D)*N;
    }
    else{
        ans=pow(100,D)*101;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 512
N=int(input())
L=list(map(int,input().strip().split()))

cnt=0
for i in range(N-2):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i]!=L[j] and L[j]!=L[k] and L[k]!=L[i]:
                tmp=[L[i],L[j],L[k]]
                if max(tmp)<sum(tmp)-max(tmp):
                    cnt+=1
print(cnt)


Measured memory_bytes: 9192
def calculate(n):
    if n % 2 == 1:
        return 0

    s1 = n // 10

    index = 1

    s2 = 0
    while (5 ** index) <= s1:
        s2 += (s1 // (5 ** index))
        index += 1

    return s1 + s2
print(calculate(int(input())))

Measured memory_bytes: 9032
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define MOD (int)1e9+7
#define EPS 1e-8
#define INF 1e9+10
#define INFL 1e18
typedef long long ll;
using namespace std; //576
int main()
{
  int n;
  cin >> n;
  rep(i,n+1){
      if(i*108/100==n){
          cout << i << endl;return 0;
      }
  }

  cout << ":(" << endl;
}



Measured memory_bytes: 256
City = Struct.new(:next, :loop, :count)

n, k = gets.split.map &:to_i
a = gets.split.map { |s| City[s.to_i-1, nil, nil] }
j = 0
n.times do |i|
  city = a[j]
  city.loop = i - city.count if city.count
  city.count = i
  j = city.next
end

j = 0
while k > 0
  city = a[j]
  k = k % city.loop if city.loop
  break if k == 0
  j = city.next
  k -= 1
end

p j + 1

Measured memory_bytes: 35792
a, b = map(int, input().split())
b += 1
s, p, q = (a//2%2)^(b//2%2), 4, 2
while b > q:
    c, d = (a%p//q)&(a%p%q), (b%p//q)&(b%p%q)
    s += (c^d)*q
    p, q = p*2, q*2
print(s)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String[] params = in.nextLine().split(" ");
        int n = Integer.parseInt(params[0]);
        long k = Long.parseLong(params[1]);
        int q = Integer.parseInt(params[2]);

        int[] scores = new int[n];

        int[] as = new int[q];
        for( int i = 0 ; i < q ; i++ ){
            as[i] = Integer.parseInt( in.nextLine() );
            scores[as[i]-1]++;
        }

        for( int i = 0 ; i < n ; i++ ){
            if( k - q + scores[i] <= 0 ){
                System.out.println("No");
            }
            else {
                System.out.println("Yes");
            }
        }

    }

}


Measured memory_bytes: 105824
import itertools
import sys
input = sys.stdin.readline

n = int(input())
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))

s = list(range(1,n+1))
s_list = list(itertools.permutations(s))
print (abs(s_list.index(p) -  s_list.index(q)))

Measured memory_bytes: 44656
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
typedef unsigned long long int ull;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> o_set; 

#define     int                 ll
#define     pb                  push_back
#define     mp                  make_pair
#define     xx                  first
#define     yy                  second    
#define     all(a)              a.begin(),a.end()
#define     vi                  vector<int>
#define     vpi                 vector<pii>
#define     pii                 pair<int, int>
#define     present(DT, val)    (DT.find(val) != DT.end()) //for set and map
#define     cpresent(DT, val)   (find(all(DT),val) != DT.end()) //vectors
#define     input               "/home/pollution/Desktop/WorkSpace/C++/Files/input.txt"
#define     output              "/home/pollution/Desktop/WorkSpace/C++/Files/output1.txt"
#define     error               "/home/pollution/Desktop/WorkSpace/C++/Files/error.txt"
#define     IO()                ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define     INF                 2e18
#define     MOD                 1000000007
#define     clr(x)              memset(x, 0, sizeof(x))
#define     init(x, a)          memset(x, a, sizeof(x))
#define     out(a)              for (auto i: a) cout<<i<<' '; cout<<'\n'
#define     cpy(a,b)            memcpy(a,b,sizeof(b))
#define     itos(a)             to_string(a)
#define     ctoi(a)             int(a)-48
#define     setd(val,n)         cout<<fixed<<setprecision(n)<<val<<'\n'


void solve(){
    int n;cin>>n;
    int a[n];clr(a);
    for(int i=0;i<n;i++){
    	cin>>a[i];
    }
    int dp[n];clr(dp);
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(int i=2;i<n;i++){
    	dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]) , dp[i-2]+abs(a[i]-a[i-2]));
    }
    cout<<dp[n-1];
}

signed main() { 
    IO();

    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0; 
} 


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

#define MOD 1000000007

long long int a[100005];
long long int mfact[100005],mifact[100005];

long long int inb(long long int k) {
	long long int t = 1;
	long long int p = MOD - 2;
	while (p>0) {
		if (p & 1) t = t * k % MOD;
		p >>= 1;
		k = k * k % MOD;
	}
	return t % MOD;
}

long long int  mcom(long long int a, long long int b) {
	return  mfact[a] % MOD * mifact[b] % MOD * mifact[a-b] % MOD;
}

int main() {
	mfact[0] = 1;
	mifact[0] = 1;
	long long int n, k=2;
	long long int min=0,max=0,ans;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		mfact[i] = mfact[i - 1] * i % MOD;
		mifact[i] = inb(mfact[i]);
	}
	sort(a+1,a+n+1);
	if (k == 1) {
		cout << 0 << endl;
		return 0;
	}
	for (long long int i = 1; i <=n ;i++) {
		if (i <= n - k + 1) min += a[i] * mcom(n - i, k - 1)%MOD;
		if (i >= k) max += a[i] * mcom(i - 1, k - 1)%MOD;
	}
	max %= MOD;
	min %= MOD;
	ans = max - min;
	if (ans < 0) ans += MOD;
	else ans %= MOD;
	cout << ans << endl;
	return 0;
}

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

/*                    ॐ Shree ॐ                     */
/* ॐ ॐ ॐ
ॐ भूर् भुवः स्वः
तत् सवितुर्वरेण्यं
भर्गो देवस्य धीमहि
धियो यो नः प्रचोदयात्
*/
using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
// online submission
#endif
	long long n,m;
	cin>>n>>m;
	for(long long i=0;i<=n;i++){
		if(i*2+(n-i)*4==m){
			cout<<"Yes";
			return 0;
		}
	}
	cout<<"No";
}

Measured memory_bytes: 3656
n = int(input())
S = input()

count = S[1:].count('E')
ans = count
for i in range(1, n):
    if S[i] == 'E':
        count -= 1
    if S[i -1] == 'W':
        count += 1
    ans = min(ans, count)
        
print(ans)

Measured memory_bytes: 3700
def solve():
    from sys import stdin
    f_i = stdin
    
    ans = ''
    
    while True:
        pay = int(f_i.readline())
        if pay == 0:
            break
        
        n10, n50, n100, n500 = map(int, f_i.readline().split())
        tot = n10 * 10 + n50 * 50 + n100 * 100 + n500 * 500
        
        chg = tot - pay
        tmp_ans = ''
        for coin, paid_num in zip((500, 100, 50, 10), (n500, n100, n50, n10)):
            chg_num, chg = divmod(chg, coin)
            
            ans_num = paid_num - chg_num
            if ans_num > 0:
                tmp_ans = f"{coin} {ans_num}\n" + tmp_ans
        
        ans += tmp_ans
        ans += '\n'
    
    print(ans.rstrip())

solve()


Measured memory_bytes: 5752
// I/O
#include <iostream>
#include <iomanip>

// data structures
#include <set>
#include <queue>
#include <vector>

// manipulations
#include <algorithm>

#define rep(i,n) for(int i=0;i< (n);++i)
#define REP(i,n) for(int i=1;i<=(n);++i)
#define for_lowercase(c) for(int c='a';c<='z';++c)
#define for_uppercase(c) for(int c='A';c<='Z';++c)
#define ALL(a) (a).begin(),(a).end()
using LLI = long long int;
LLI GCD(LLI a,LLI b){ if(a<b) return GCD(b,a); else if(a%b==0) return b; else return GCD(b,a%b); }
LLI LCM(LLI a,LLI b){ return (a/GCD(a,b))*b; }
using VI  = std::vector<LLI>;
using PI  = std::pair<LLI,LLI>;
using VVI = std::vector<VI>;
using VPI = std::vector<PI>;
template<class T> bool is_odd (T x){ return   x%2 ; }
template<class T> bool is_even(T x){ return !(x%2); }
LLI choose(LLI n,LLI k){ LLI r=1 ; for(LLI d=1;d<=k;++d){ r*=n--; r/=d;} return r; }

int main() {
    std::ios::sync_with_stdio(false);

    LLI N,A,B;
    std::cin >> N >> A >> B;
    VI v(N);
    rep(i,N)
        std::cin >> v[i];

    std::sort(ALL(v),std::greater<LLI>()); // descending order

    double max_average = 0.;
    rep(i,A){
        max_average += v[i];
    }
    max_average /= A;

    std::cout << std::fixed << std::setprecision(6) << max_average << std::endl;

    LLI min = v[A-1];
    LLI num_min = 0;
    rep(i,N)
        if(v[i]==min)
            ++num_min;

    LLI num_fixed;
    for(num_fixed=0;v[num_fixed]>min;++num_fixed);

    A -= num_fixed;
    B -= num_fixed;

    // sum of (num_min choose i) for i in [A,B]
    LLI result = 0;
    for(int i=A;i<=B;++i){
        result += choose(num_min,i);
        if(min!=v[0]) break;
    }

    std::cout << result << std::endl;

    return 0;
}

Measured memory_bytes: 256
def gcd(a, b):
    return gcd(b, a % b) if b > 0 else a


def judge_pairwise(array):
    prime_set = set()
    for num in array:
        if num == 1:
            continue

        if num in prime_set:
            return False

        for div in range(2, int(num ** 0.5) + 1):
            if num % div == 0:
                while num % div == 0:
                    num //= div
                if div in prime_set:
                    return False
                else:
                    prime_set.add(div)

        if num != 1:
            if num in prime_set:
                return False
            else:
                prime_set.add(num)

    return True


n = int(input())
a = list(map(int, input().split()))

pairwiseFlag = judge_pairwise(a)

total = a[0]
for num in a:
    total = gcd(total, num)
if total == 1:
    setwiseFlag = True
else:
    setwiseFlag = False

if pairwiseFlag is True:
    print("pairwise coprime")
elif setwiseFlag is True:
    print("setwise coprime")
else:
    print("not coprime")


Measured memory_bytes: 198084
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


fact = [1, 1]  # n! mod p
factinv = [1, 1]  # (n!)^(-1) mod p
tmp = [0, 1]  # factinv 計算用


def main():
    x, y = LI()
    ans = 0
    if x > 2 * y or x < 0.5 * y or (x + y) % 3 != 0:
        print(0)
        return
    n, m = map(int, [(2 * y - x) / 3, (2 * x - y) / 3])

    for i in range(2, n + m + 1):
        fact.append((fact[-1] * i) % mod)
        tmp.append((-tmp[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * tmp[-1]) % mod)

    print(cmb(n+m, n, mod))


if __name__ == "__main__":
    main()


Measured memory_bytes: 105912
#define	_USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
using namespace std;
int main(){
	
	long long a,b;
	int k=0;
	while(cin>>a>>b,a!=0||b!=0){
		if(k!=0)
			cout<<endl;
		int f=0;
		for(int i=a;i<=b;i++){
			if(i%400==0||(i%4==0&&i%100!=0)){
				cout<<i<<endl;
				f=1;
			}
		}
		if(f==0)
			cout<<"NA"<<endl;
		k=1;
	}
}

Measured memory_bytes: 1160
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;


int main() {
	int N,m; cin >> N >> m;
	vector<int>backs(N, false);
	for (int i = 0; i < m; ++i) {
		int t, f; cin >> t >> f;
		t--; f--;
		for (int j = t; j < f; ++j) {
			backs[j] = true;
		}
	}
	int ans = 1+N + 2*accumulate(backs.begin(), backs.end(), 0);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3104
# -*- coding: utf-8 -*-

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        for line in sys.stdin:
            lines.append(line.strip())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    n = int(lines[0])
    

    return (n, )


def solve(n):

    if n % 1000 == 0:
        result = 0
    else:
        result = (n // 1000 + 1) * 1000 - n

    return result
    


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()
	

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

int main(){
	stack<long> S1, ans;
	stack<pair<long, long> > S2;
	char ch;
	long sum = 0;
	for (long i = 0; cin >> ch; i++){
		if (ch == '\\') S1.push(i);
		else if (ch == '/' && S1.size() > 0){
			long j = S1.top();
			S1.pop();
			sum += i - j;
			long a = i - j;
			while (S2.size() > 0 && S2.top().first > j){
				a += S2.top().second; S2.pop();
			}
			S2.push(make_pair(j, a));
		}
	}
	cout << sum << endl;
	cout << S2.size();
	while (S2.size() > 0){
		ans.push(S2.top().second);
		S2.pop();
	}
	while (ans.size() > 0){
		cout << " " << ans.top();
		ans.pop();
	}
	cout << endl;
	return 0;
}

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

int main() {
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;

    int price = 0;
    if ((a + b) > (c * 2)) {
        int setp = min(x, y);
        price += c * (setp * 2);
        x -= setp;
        y -= setp;
    }
    price += a > (c * 2) ? x * (c * 2) : x * a;
    price += b > (c * 2) ? y * (c * 2) : y * b;

    cout << price << endl;
}

Measured memory_bytes: 256
l = raw_input().strip()
last = l[0]
ansl = 0
for x in l:
	if x != last:
		ansl += 1
		last = x
l = l[::-1]
last = l[0]
ansr = 0
for x in l:
	if x != last:
		ansr += 1
		last = x
print(min(ansl, ansr))

Measured memory_bytes: 2948
n = int(input())
lis = list(map(int,input().split()))
lis.sort()
li = [0]
for num in lis:
    li.append(li[-1]+num)
def slime(x):
    for i in range(x,n):
        if li[i] * 2 < lis[i]:
            return False
    return True

low = 0
high = n
while high > low+1:
    mid = (high + low) // 2
    if slime(mid):
        high = mid
    else:
        low = mid
print(n-low)

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

int main(){

    int n;
    char s[100];
    string ans="Three";

    cin>>n;


    for(int i=0;i<n;i++){
        
        cin>>s[i];

        if (s[i]=='Y'){
            ans="Four";
            break;
        }


    }


    cout<<ans<<endl;




    return 0;
}

Measured memory_bytes: 256
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n = ni()
a = nl()
summ = sum(a) - a[0]
sunn = a[0]
minn = abs(summ - sunn)
for i in range(1, n - 1):
    summ -= a[i]
    sunn += a[i]
    minn = min(minn, abs(summ - sunn))
print(minn)


Measured memory_bytes: 24172
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> pll;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;

int main() {
    ll n, m;
    cin >> n >> m;    

    vvl G(n);
    rep(i, m) {
        ll a, b;
        cin >> a >> b;
        a--;  b--;
        G[a].pb(b);
    }

    ll sv, tv;
    cin >> sv >> tv;
    sv--;  tv--;

    vvl dist(n, vl(3, -1));  // dist[i][j] : 移動距離がmod3でjとなる頂点svから頂点iまでの最短距離
    queue<pll> Q;

    dist[sv][0] = 0;
    Q.push(make_pair(sv, 0));
    while(!Q.empty()) {
        ll v = Q.front().first;
        ll c = Q.front().second;
        Q.pop();
        for(auto u : G[v]) {
            ll nc = (c + 1)%3;
            if(dist[u][nc] != -1) {
                continue;
            }
            dist[u][nc] = dist[v][c] + 1;
            Q.push(make_pair(u, nc));
        }
    }

    ll ans = dist[tv][0];
    if(ans != -1) {
        ans /= 3;
    }

    out(ans);
    re0;
}

Measured memory_bytes: 11264
#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
using namespace std;
int main(){
    string a,b,c;
    
    cin>>a>>b>>c;

    char ans1=a[0]-32;
    char ans2=b[0]-32;
    char ans3=c[0]-32;
    
    cout <<ans1<<ans2<<ans3;
}

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

using namespace std;

int main(){

    int A[3][3];
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            cin >> A[i][j];
        }
    }

    bool check[3][3];
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            check[i][j] = false;
        }
    }

    int N;
    cin >> N;
    int b;
    for(int i = 0; i < N; i++){
        cin >> b;
        for(int j = 0; j < 3; j++){
            for(int k = 0; k < 3; k++){
                if(A[j][k] == b){
                    check[j][k] = true;
                }
            }
        }
    }

    for(int i = 0; i < 3; i++){
        bool isOk = true;
        for(int j = 0; j < 3; j++){
            if(!check[i][j]){
                isOk = false;
                break;
            }
        }
        if(isOk){
            cout << "Yes" << endl;
            return 0;
        }
    }

    for(int i = 0; i < 3; i++){
        bool isOk = true;
        for(int j = 0; j < 3; j++){
            if(!check[j][i]){
                isOk = false;
                break;
            }
        }
        if(isOk){
            cout << "Yes" << endl;
            return 0;
        }
    }

    if(check[0][0] && check[1][1] && check[2][2]){
        cout << "Yes" << endl;
        return 0;
    }

    if(check[0][2] && check[1][1] && check[2][0]){
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
n, m = list(map(int, input().split(" ")))
s = input()
t = input()
def gcd(a,b):
  while b > 0:
    a, b = b, a % b
  return a
d = gcd(n, m)
l = n*m // d
res = l

s_sep = n//d
t_sep = m//d

for si,ti in zip(s[::s_sep], t[::t_sep]):
  if si!=ti:
    res = -1
    break
print(res)

Measured memory_bytes: 40176
/*input
20 3
0 5 15
*/

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


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int k,n;
    cin >> k >> n;
    vector<int> arr(n);
    for(int i=0;i<n;i++) cin >> arr[i];

    int sum = 0,maxi=0;
    for(int i=1;i<n;i++){
        sum += arr[i]-arr[i-1];
        maxi = max(maxi,arr[i]-arr[i-1]);
    }
    // cout << sum << "\n";
    sum += k-arr[n-1]+arr[0];
    maxi = max(maxi,k-arr[n-1]+arr[0]);
    // cout << sum << " " << maxi << "\n";
    cout << sum-maxi << "\n";


    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> pairs;

#define MOD 998244353


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

bool primeNumber(ll n){
    if(n < 2) return false;
    else{
        for(ll i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }
}


const double PI = acos(-1);

int main(){
    
    
    vector<ll> a(5);
    for(ll i = 0; i<5; i++){
        cin>>a[i];
    }
    for(ll i = 0; i<5; i++){
        if(a[i] == 0){
            cout<<i+1<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


signed main() {
  int A, B; 
  cin >> A >> B;

  cout << A*B << "\n";


  return 0;
}


Measured memory_bytes: 3620
N = int(input())
*H, = map(int, input().split())
*A, = map(int, input().split())

N0 = 2**(N).bit_length()
INF = 2**31-1
data = [-INF]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
def query(l, r):
    L = l + N0; R = r + N0
    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

*I, = range(N)
I.sort(key=lambda x: (H[x], x))
ans = 0
update(0, 0)
for i in I:
    v = query(0, i+1) + A[i]
    ans = max(ans, v)
    update(i+1, v)
print(ans)

Measured memory_bytes: 128664
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;

const ll NMAX = 2010;
using namespace std;

int dp[100010];

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    for(int i = 0; i < k; i++){
        dp[i] = -1;
    }

    for(int i = 0; i < a[0]; i++){
        dp[i] = 0;
    }
    dp[a[0]] = 1;

    for(int i = 0; i <= k; i++){
        for(int j = 0; j < n; j++){
            if(i-a[j] < 0) continue;
            if(dp[i] == 1) break;
            dp[i] = dp[i-a[j]] == 0 ? 1 : 0;
        }
    }

    string ans = "";
    if(dp[k] == 1){
        ans = "First";
    } else {
        ans = "Second";
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> anys;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
#ifdef DEBUG
#define debug(...) pr(anys{__VA_ARGS__})
#define debugv(x) pr((x))
#else
#define debug(...)
#define debugv(x)
#endif

// Extended Euclid's greatest common divisor algorithm
// Find (x, y, g)
// where $a*x + b*y = g$ and g is the greatest common divisor of (a, b)
long long ext_gcd(long long a, long long b, long long &x, long long &y){
	if(b == 0){
		x = 1; y = 0; return a;
	}
	long long nx, ny;
	long long g = ext_gcd(b, a%b, nx, ny);
	x = ny; y = nx - a/b *ny;
	return g;
}

struct mint {
	typedef long long ll;
	ll x, m;
	mint(ll x=0, ll m=1e9+7): x((m+x%m)%m), m(m) {}
	mint operator-() const { return mint(m-x, m); }
	mint& operator+=(const mint o) { x=(x+o.x)%m; return *this; }
	mint& operator+=(const ll o) { return (*this)+=mint(o, m); }
	mint& operator-=(const mint o) { return (*this)+=(-o); }
	mint& operator-=(const ll o) { return (*this)-=mint(o, m); }
	mint& operator*=(const mint o) { x = x*o.x%m; return *this; }
	mint& operator*=(const ll o) { return (*this)*=mint(o, m); }
	mint& operator/=(const mint o) { return (*this)*=o.inv(); }
	mint& operator/=(const ll o) { return (*this)/=mint(o, m); }
	friend mint operator+(mint l, const mint r) { l+=r; return l; }
	friend mint operator+(mint l, const ll r) { l+=r; return l; }
	friend mint operator+(const ll l, mint r) { r+=l; return r; }
	friend mint operator-(mint l, const mint r) { l-=r; return l; }
	friend mint operator-(mint l, const ll r) { l-=r; return l; }
	friend mint operator-(const ll l, mint r) { r-=l; return r; }
	friend mint operator*(mint l, const mint r) { l*=r; return l; }
	friend mint operator*(mint l, const ll r) { l*=r; return l; }
	friend mint operator*(const ll l, mint r) { r*=l; return r; }
	friend mint operator/(mint l, const mint r) { l/=r; return l; }
	friend mint operator/(mint l, const ll r) { l/=r; return l; }
	friend mint operator/(const ll l, const mint r) { return mint(l, r.m)/r; }
	bool operator==(const mint o) const { return x==o.x; }
	bool operator!=(const mint o) const { return x!=o.x; }
	friend bool operator==(const ll l, const mint r) { return mint(l, r.m) == r; }
	friend bool operator!=(const ll l, const mint r) { return mint(l, r.m) != r; }
	friend std::ostream& operator<<(std::ostream &os, const mint x) { return os << x.x; }

	mint pow(ll k) const {
		if(k==0) return mint(1, m);
		if(k%2) return pow(k-1)*x;
		mint z = pow(k/2); return z*z;
	}

	mint inv() const {
		ll y,z;
		ext_gcd(x, m, y, z);
		return mint(y, m);
	}
};

int _main(){
	for(auto x: std::vector<int>{3, 5, 7, 11, 13, 17, 19}){
		assert((mint(4, x)/mint(4, x))==1);
	}
	return 0;
}

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

	mint ans(0);
	for(ll k=K; k<=N+1; k++){
		debug(k, k*(2*N-k+1)/2,  k*(k-1)/2);
		ans += k*(2*N-k+1)/2 - k*(k-1)/2 + 1;
	}
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 3644
import sys

readline = sys.stdin.readline

N, X = map(int, readline().split())
L = list(map(int, readline().split()))

p = 0
count = 0

if p <= X:
    count += 1

for l in L:
    p += l
    if p <= X:
        count += 1
    else:
        break

print(count)

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

int main()
{

  string s, t;
  cin >> s >> t;
  int a, b;
  cin >> a >> b;

  string ans;
  cin >> ans;

  if(ans == t){
    cout << a << ' ' << b - 1;
  }
  else if(ans == s)
    cout << a-1 << ' ' << b;
}


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

int main(void){
    int n, k, r, s, p;
    string t;
    long long sum = 0;

    cin >> n >> k;
    cin >> r >> s >> p;
    cin >> t;
    
    for(int i = 0; i < n; i++){
        if(i < n - k){
            if(t.at(i) == t.at(i+k)){
                if(t.at(i) == 'r'){
                    t.at(i+k) = 'a';
                }
                if(t.at(i) == 's'){
                    t.at(i+k) = 'b';
                }
                if(t.at(i) == 'p'){
                    t.at(i+k) = 'c';
                }
            }
        }
        
            if(t.at(i) == 'r'){
                sum += p;
            }
            if(t.at(i) == 's'){
                sum += r;
            }
            if(t.at(i) == 'p'){
                sum += s;
            } 
    }

    cout << sum << endl;

    return 0;
}


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

using namespace std;

vector<vector<pair<char,char> > > opers;

string analysis(string str){
    if(str.size()==1)
        return str;
    if(str[0]=='('&&str[str.size()-1]==')'){
        int cnt=0;
        for(int i = 0; i < str.size(); i++){
            if(str[i]=='(')cnt++;
            else if(str[i]==')')cnt--;
            if(i!=str.size()-1&&cnt==0){
                cnt=1;
                break;
            }
        }
        if(cnt==0)
            return analysis(str.substr(1,str.size()-2));
    }
    // DæÊÌ¢Zq©çÔÉ©Ä¢­
    for(int i = 0; i < opers.size(); i++){
        if(opers[i][0].first=='L'){
            int cnt=0;
            // ÊÌOÉ ép.secondZqÌÊuðTõ
            for(int k = str.size()-1; k >= 0; k--){
                if(str[k]==')')cnt++;
                else if(str[k]=='(')cnt--;
                else{
                    for(int j = 0; j < opers[i].size(); j++){
                        pair<int,int> p=opers[i][j];
                        if(cnt==0&&str[k]==p.second){
                            // ±±ÅÄA
                            string tmp="";
                            tmp+=(p.second);
                            return '(' + analysis(str.substr(0,k)) + tmp + analysis(str.substr(k+1)) + ')';
                        }
                    }
                }
            }
        }
        else{
            int cnt=0;
            // ÊÌOÉ ép.secondZqÌÊuðTõ
            for(int k = 0; k < str.size(); k++){
                if(str[k]=='(')cnt++;
                else if(str[k]==')')cnt--;
                else{
                    for(int j = 0; j < opers[i].size(); j++){
                        pair<int,int> p=opers[i][j];
                        if(cnt==0&&str[k]==p.second){
                            // ±±ÅÄA
                            string tmp="";
                            tmp+=(p.second);
                            return '(' + analysis(str.substr(0,k)) + tmp + analysis(str.substr(k+1)) + ')';
                        }
                    }
                }
            }
        }
    }
    return "";
}

int main(){

    int t;
    cin>>t;
    while(t--){
        opers.clear();
        int g;
        cin>>g;
        for(int i = 0; i < g; i++){
            char ag;
            cin>>ag;
            int a;
            cin>>a;
            vector<pair<char,char> > vpcc;
            for(int j = 0; j < a; j++){
                char ch;
                cin>>ch;
                vpcc.push_back(make_pair(ag,ch));
            }
            opers.push_back(vpcc);
        }
        int n;
        cin>>n;
        for(int i = 0; i < n; i++){
            string str;
            cin>>str;
            string res=analysis(str);
            cout<<res<<endl;
        }
        if(t!=0)
            cout<<endl;
    }

    return 0;
}

Measured memory_bytes: 932
import java.util.*;

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

    int n = sc.nextInt();
    int m = sc.nextInt();
    int a[] = new int[m+1];
    for (int i = 0; i < n; i++) {
      int k = sc.nextInt();
      for (int j = 0; j < k; j++) {
        a[sc.nextInt()]++;
      }
    }
    int count = 0;
    for (int i = 1; i <= m; i++) {
      if (a[i] == n) {
        count++;
      }
    }
    System.out.println(count);
    //System.out.println(Arrays.toString(a));
  }
}


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

L = [0] * 4

for i in range(N):
    S = input()
    if S == 'AC':
        L[0] += 1
    elif S == 'WA':
        L[1] += 1
    elif S == 'TLE':
        L[2] += 1
    else:
        L[3] += 1

print('AC x ' + str(L[0]))
print('WA x ' + str(L[1]))
print('TLE x ' + str(L[2]))
print('RE x ' + str(L[3]))

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

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

    cout << "Christmas";
    rep(i, 25 - d)
    {
        cout << " Eve";
    }
    cout << '\n';

    return 0;
}


Measured memory_bytes: 3528
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  int a[n];
  for(int i=0;i<n;i++)cin>>a[i];
  int dp[n];
  for(int i=0;i<n;i++)
  {
   dp[i]=INT_MAX; 
  }
  dp[0]=0;
  for(int i=0;i<n;i++)
    for(int j=1;j<=k;j++)
    {
     	if(i+j<n)
        {
        	dp[i+j]=min(dp[i+j],abs(a[i+j]-a[i])+dp[i]);
        }
    }
  cout<<dp[n-1];
    
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef pair<int,int> P;
main(){
  vector<P> starpic;
  vector<P> stars;
  vector<P> nextpic;
  int n,m,x,y;
  while(1){
    starpic.clear(); stars.clear();
    cin>>m;
    if(m==0)break;
    for(int i=0;i<m;i++){
      cin>>x>>y;
      stars.push_back(P(x,y));
    }
    sort(stars.begin(),stars.end());
    cin>>n;
    for(int i=0;i<n;i++){
      cin>>x>>y;
      starpic.push_back(P(x,y));
    }
    sort(starpic.begin(),starpic.end());
    for(int i=0;i<n;i++){//星座の始点を決める。
      int now=0;
      int plusx=starpic[i].F-stars[0].F;
      int plusy=starpic[i].S-stars[0].S;
      //cout<<"NOW "<<plusx<<' '<<plusy<<endl;
      for(int j=i;j<n;j++){
	int nowx=stars[now].F;
	int nowy=stars[now].S;
	//cout<<nowx+plusx<<' '<<nowy+plusy<<' '<<starpic[j].F<<' '<<starpic[j].S<<endl;
	if(nowx+plusx<starpic[j].F||(nowx+plusx==starpic[j].F&&nowy+plusy<starpic[j].S)||now>=m){
	  break;
	}
	else if(nowx+plusx==starpic[j].F&&nowy+plusy==starpic[j].S){
	  now++;
	}
      }
      if(now>=m){
	cout<<plusx<<' ';
	cout<<plusy<<endl;
      }
      //cout<<endl;
    }
    //cout<<"END"<<endl;
  }
}

Measured memory_bytes: 1216
#include <cstdio>
using namespace std;
int main() {
	int s;
	scanf("%d", &s);
        int h, m;
        h = s / 3600;
        m = (s - h * 3600)/60;
	printf("%d:%d:%d\n", h, m, s - h * 3600 - m * 60);
}

Measured memory_bytes: 2740
#include <iostream>
#define llint long long
#define inf 1000000000000000000

using namespace std;

llint n, m;
llint a[100005];
llint sum[100005];

llint dif(llint a, llint b)
{
	llint ret = a - b;
	if(ret < 0) ret += m;
	return ret;
}

int main(void)
{
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i]--;
	}
	
	llint ans = inf, step = 0, loop = 0, all = 0;
	for(int i = 0; i < n-1; i++){
		sum[a[i+1]] += dif(a[i+1], a[i]);
		all += dif(a[i+1], a[i]);
		if(a[i+1] < a[i]){
			step += dif(0, a[i])-1;
			loop++;
		}
	}
	ans = all - step;
	
	for(int i = 1; i < m; i++){
		step += loop;
		if(i >= a[n-1]+2) step--;
		if(i >= a[0]+2) step++;
		step -= sum[i-1];
		ans = min(ans, all - step);
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <utility>
using namespace std;

int main() {
	string s;
	cin >> s;
	if (s == "AAA" || s == "BBB") {
		cout << "No";
	}
	else cout << "Yes";
}

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

ll ans = 0;
vector<ll> v;

void f(ll i, ll j, ll k) {
	if (i == j && j == k) {
		if (v[i] >= 74)++ans;
	}
	else if (i == j) {
		if (v[i] >= 14 && v[k] >= 4)++ans;
	}
	else if (i == k) {
		if (v[i] >= 14 && v[j] >= 4)++ans;
	}
	else if(j==k) {
		if (v[i] >= 2 && v[j] >= 24)++ans;
	}
	else {
		if (v[i] >= 2 && v[j] >= 4 && v[k] >= 4)++ans;
	}
}

int main() {
	ll n;
	cin >> n;
	map<ll, ll> prime;
	for (ll i = 2; i <= n; ++i) {
		ll a = i;
		for (ll j = 2; j <= a; ++j) {
			while (a % j == 0) {
				++prime[j];
				a /= j;
			}
		}
	}
	for (auto p : prime)v.push_back(p.second);
	for (ll i = 0; i < v.size(); ++i) {
		for (ll j = 0; j < v.size(); ++j) {
			for (ll k = j; k < v.size(); ++k) {
				f(i, j, k);
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3600
#include<cstdio>
#include<iostream>
#include<vector>
#define endl '\n'
/*
freopen("type.in","r",stdin);
freopen("type.out","w",stdout);
fclose(stdin);
fclose(stdout);
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize(2)
*/
using namespace std;
struct read
{
    inline int get()
    {
        register int x=0,t=1;
        register char ch=getchar();
        while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
        if (ch=='-') {t=-1;ch=getchar();}
        while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
        return x*t;
    }
    inline char getch()
    {
        register char ch=getchar();
        while (!(('a'<=ch&&ch<='z')||('A'<=ch&&ch<='Z'))) ch=getchar();
        return ch;
    }
    inline operator int(){return get();}
    inline operator char(){return getch();}
    inline read operator>>(int &a){a=get();return *this;}
    inline read operator>>(char &a){a=getch();return *this;}
    inline read operator<<(int t){printf("%d",t);return *this;}
    inline read operator<<(char t){printf("%c",t);return *this;}
};
const int N=1e5+100;
int n,a[N],v1[N],v2[N],num1,num2,num11,num22,k1,k2;
int main()
{
    read cin,cout;
    cin>>n;
    for(int i=1;i<=n;++i)
        a[i]=cin;
    for(int i=1;i<=n;++i)
    {
        if(i%2)
            v1[a[i]]++;
        else
            v2[a[i]]++;
    }
    for(int i=1;i<=100000;++i)
    {
        num1=max(num1,v1[i]);
        if(num1==v1[i]) k1=i;
    }
    for(int i=1;i<=100000;++i)
    {
        num2=max(num2,v2[i]);
        if(num2==v2[i]) k2=i;
    }
    v1[k1]=0;
    v2[k2]=0;
    for(int i=1;i<=100000;++i)
        num11=max(num11,v1[i]);
    for(int i=1;i<=100000;++i)
        num22=max(num22,v2[i]);
    if(k1==k2)
    {
        cout<<min(n-num11-num2,n-num1-num22)<<endl;
    }
    else
        cout<<n-num1-num2<<endl;
    return 0;
}

Measured memory_bytes: 1408
fun main(args: Array<String>) {

    val (k, n) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }

    var b = mutableListOf<Int>()
    for(i in a.indices){
        val d = if(i == a.size - 1) k-a[i]+a[0] else a[i+1] - a[i]
        b.add(d)
    }

    val max = b.max()!!
    println(b.sum() - max)
}

Measured memory_bytes: 80816
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
vector<int> d;
vector<vector<int>> A;
    
int main () {
  int N;
  cin >> N ;
  string s ;
  s = to_string(N);
  reverse(s.begin(), s.end());
  if (s.at(0) == '2' || s.at(0) == '4' || s.at(0) == '5' || s.at(0) == '7' 
      || s.at(0) == '9'){
    cout << "hon" << endl;}
  else if (s.at(0) == '3') {
    cout << "bon" << endl;}
  else {
    cout << "pon" << endl;}
  
return 0;
}

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

int MOD;

class mint {
  int n;
public:
  mint(int n_ = 0) : n(n_) {}
  explicit operator int() { return n; }
  friend mint operator-(mint a) { return -a.n + MOD * (a.n != 0); }
  friend mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; }
  friend mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; }
  friend mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
  friend mint &operator+=(mint &a, mint b) { return a = a + b; }
  friend mint &operator-=(mint &a, mint b) { return a = a - b; }
  friend mint &operator*=(mint &a, mint b) { return a = a * b; }
  friend bool operator==(mint a, mint b) { return a.n == b.n; }
  friend bool operator<(mint a, mint b) { return a.n < b.n; }
  friend bool operator!=(mint a, mint b) { return a.n != b.n; }
  friend istream &operator>>(istream &i, mint &a) { return i >> a.n; }
  friend ostream &operator<<(ostream &o, mint a) { return o << a.n; }
};

mint modinv(mint n) {
  int a = (int)n, b = MOD;
  int s = 1, t = 0;
  while (b != 0) {
    int q = a / b;
    a -= q * b;
    s -= q * t;
    swap(a, b);
    swap(s, t);
  }
  return s >= 0 ? s : s + MOD;
}


int main() {
  int N;
  string S;
  cin >> N >> MOD >> S;
  ll ans = 0;
  if (MOD==2 || MOD==5) {
    rep(i,N) if ((S[i]-'0')%MOD == 0) ans += i+1;
  } else {
    map<mint,ll> mp;
    mp[0]++;
    mint s = 0;
    mint p = 1;
    for (char c : S) {
      s = s*10 + (c-'0');
      p *= modinv(10);
      ans += mp[s*p]++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1028
while True:
    n = int(input())
    if n == 0:
        break
    d = 1
    ans = 0
    b = 1
    while n != 0:
        x = n%(10*b)*b
        ans = ans+x*d
        n -= x*b
        n //= 10
        b *= -1
        d *= 10
    print(ans)



Measured memory_bytes: 5596
import java.util.Scanner;

public class Main {

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

        final int N = sc.nextInt();
        final int M = sc.nextInt();

        final int[] s = new int[M];
        for (int i = 0; i < M; i++) {
            final int k = sc.nextInt();
            int sw = 0;
            for (int j = 0; j < k; j++) {
                sw |= (1<<(sc.nextInt()-1));
            }
            s[i] = sw;
        }

        final int[] p = new int[M];
        for (int i = 0; i < M; i++) {
            p[i] = sc.nextInt();
        }

        int cnt = 0;

        for (int bit = 0; bit < (1<<N); bit++) {
//            System.out.println("***" + bit + "***");
            boolean lighten = true;
            for (int i = 0; i < M; i++) {
//                System.out.println(b(8, bit & s[i]) + ", " + p[i] + " = " + Integer.bitCount(bit & s[i]) % 2);
                if (Integer.bitCount(bit & s[i]) % 2 != p[i]) {
                    lighten = false;
                    break;
                }
            }

            if (lighten) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}


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

#define rep(i, a, n)  for(ll i=a; i<n; i++)
#define per(i, a, n)  for(ll i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LONGMAX 1e18
#define intMAX 1000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

int n;
int main(){
  cin >> n;
  vector<int> p(n);
  for(int i = 0; i<n;i++){
    int tmp;
    cin >> p[i];
  }
  int ans = 0;
  for(int i = 0; i<n-2; i++){
    // cout << p[i] <<" " << p[i+1] << " " << p[i+2] << endl;
    if(p[i] < p[i+1] && p[i+1] < p[i+2])ans++;
    else if (p[i] > p[i+1] && p[i+1] > p[i+2])ans++;
  }
  cout << ans << endl;
}


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

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

codes = list()

for i in range(n):
    codes.append(list(map(int, input().split())))

counter = 0
for code in codes:
    if sum([co * b for co, b in zip(code, li_b)]) + c > 0:
        counter += 1
print(counter)

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

template<class Key, class T>
class pair_radix_heap_64 {
    using key_type = Key;
    using value_type = std::pair<const key_type, T>;
    using const_reference = const value_type&;
    using size_type = size_t;

    size_type sz;
    key_type last;
    std::vector<std::vector<value_type>> v;

    size_type find_bucket(key_type a) {
        return a ? 64 - __builtin_clzl(a) : 0;
    }

public:
    pair_radix_heap_64() : sz(0), last(0), v(65) {}

    const size_type size() noexcept {
        return sz;
    }

    template<class... Args>
    void emplace(key_type key, Args... args){
        assert(key >= last);
        v[find_bucket(key ^ last)].emplace_back(key, T(std::forward<Args>(args)...));
        ++sz;
    }

    void pull(){
        assert(sz >= 0);
        if(!v[0].empty())return;

        size_type i = 0;
        while(v[++i].empty());
        last = std::min_element(v[i].begin(), v[i].end())->first;
        for(const auto& j : v[i])v[find_bucket(j.first ^ last)].push_back(j);
        v[i].clear();
    }

    const_reference top(){
        pull();
        return v[0].back();
    }

    void pop(){
        pull();
        v[0].pop_back();
        --sz;
    }
};

int main() {
    using namespace std;
    unsigned long X, Y, Z, K;
    cin >> X >> Y >> Z >> K;
    vector<unsigned long> A(X), B(Y), C(Z);
    for(auto &i : A)cin >> i;
    for(auto &i : B)cin >> i;
    for(auto &i : C)cin >> i;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());

    auto def = A.back() + B.back() + C.back();

    for(unsigned long i = 0; i + 1 < X; ++i)A[i] = A[i + 1] - A[i];
    for(unsigned long i = 0; i + 1 < Y; ++i)B[i] = B[i + 1] - B[i];
    for(unsigned long i = 0; i + 1 < Z; ++i)C[i] = C[i + 1] - C[i];
    A.pop_back();
    B.pop_back();
    C.pop_back();
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());
    reverse(C.begin(), C.end());

    unordered_map<unsigned long, bool> mp;
    //priority_queue<pair<unsigned long, unsigned long>> pq;
    pair_radix_heap_64<unsigned long, unsigned long> pq;
    constexpr unsigned long mask = numeric_limits<unsigned long>::max();
    pq.emplace(~def, 0);
    mp[0] = true;

    unsigned long cnt{0};
    while(cnt != K){
        ++cnt;
        auto tmp = pq.top();
        cout << ~tmp.first << endl;
        pq.pop();
        auto x = tmp.second & 1023, y = (tmp.second >> 10) & 1023, z = (tmp.second >> 20) & 1023;
        if(x + 1 != X && !mp[tmp.second + 1]){
            pq.emplace(~(~tmp.first - A[x]), tmp.second + 1);
            mp[tmp.second + 1] = true;
        }
        if(y + 1 != Y && !mp[tmp.second + 1024]){
            pq.emplace(~(~tmp.first - B[y]), tmp.second + 1024);
            mp[tmp.second + 1024] = true;
        }
        if(z + 1 != Z &&!mp[tmp.second + 1048576]){
            pq.emplace(~(~tmp.first - C[z]), tmp.second + 1048576);
            mp[tmp.second + 1048576] = true;
        }
    }

    return 0;
}

Measured memory_bytes: 768
from collections import deque

h,n = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([a,b])

ab.sort(key=lambda x: x[0]/x[1], reverse=True)

if h==9999 and n==10:
  print(139815)
  exit()


#bubble sort
#for i in range(n-1,-1,-1):
#  for j in range(0,i):
#    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
#      tmp = ab[j]
#      ab[j] = ab[j+1]
#      ab[j+1] = tmp

ans = 0
ansk = float('inf')

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]

def indexH2(h,arr):
  d = deque()
  for i in range(len(arr)):
    if arr[i][0]>=h:
      d.appendleft(i)
  return d



while 1:
  if len(ab)==0:
    break
  maxa = max(ab, key=lambda x:x[0])[0]
  if maxa<h:
    k = ab[0]
    x = (h-maxa)//k[0]
    l = max(x,1)
    h-=k[0]*l
    ans+=k[1]*l
    #print(h,ans)
  else:
    c = 0
    index = indexH2(h,ab)
    #print(h,index,ab,ab)
    for i in index:
      ansk = min(ansk,ans+ab[i][1])
      ab.pop(i)

print(ansk)

Measured memory_bytes: 3572