akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] numbers = new long[n];
        int count2xButNot4x = 0;
        int count4x = 0;
        for (int i = 0; i < n; i++) {
            long num = sc.nextLong();
            if (num % 4 == 0) {
                count4x++;
            } else {
                if (num % 2 == 0) {
                    count2xButNot4x++;
                }
            }
            numbers[i] = num;
        }
        
        boolean pass = false;
        if (count2xButNot4x < 2) {
            if (count4x >= Math.floor((double)n / 2)) {
                pass = true;
            }
        } else {
            if (count4x >= Math.floor((double)(n - count2xButNot4x + 1) / 2)) {
                pass = true;
            }
        }
        
        if (pass) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

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

struct UnionFind{
  vector<long long> par;

  UnionFind(int n){
    par.assign(n,-1);
  }

  void unite(long long x, long long y){
    x=root(x);y=root(y);
    if(x==y) return;

    if(par[x]>par[y]){
      swap(x,y);
    }
    par[x]+=par[y];
    par[y]=x;
  }

  long long root(long long x){
    if(par[x]<0){
      return x;
    }else{
      return par[x]=root(par[x]);
    }
  }

  bool same(long long x, long long y){
    return root(x)==root(y);
  }

  int size(long long x){
    return -par[root(x)];
  }

};

int main(){
  long long n,m,ans=0;
  cin >> n >> m;
  UnionFind uf(n);
  long long p[n],x[m],y[m];
  for(int i=0;i<n;i++){
    cin >> p[i];
    p[i]--;
  }
  for(int i=0;i<m;i++){
    cin >> x[i] >> y[i];
    x[i]--;y[i]--;
    uf.unite(x[i],y[i]);
  }
  for(int i=0;i<n;i++){
    if(uf.same(i,p[i])){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3328
import collections
n=int(input())
a=list(map(int,input().split()))
b=collections.deque()

for i,x in enumerate(a):
    if i%2==1:
        b.appendleft(x)
    else:
        b.append(x)
if n%2==1:
    for i in list(b)[::-1]:
        print(i)
else:
    for i in b:
        print(i)

Measured memory_bytes: 25532
#include<bits/stdc++.h>
#define LL long long
#define db double

using namespace std;
const int N=400+10;
LL rd()
{
    LL x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*w;
}
int p[N],hd,tl,nt;

int main()
{
	LL rs=rd()+1;
	hd=201,tl=200,nt=0;
	int w=50;
	while(!(rs>>w&1)) --w;
	for(int i=w-1;~i;--i)
	{
		++nt,p[++tl]=nt;
		if(rs>>i&1) ++nt,p[--hd]=nt;
	}
	printf("%d\n",(nt<<1));
	for(int i=1;i<=nt;++i) printf("%d ",i);
	for(int i=hd;i<=tl;++i) printf("%d ",p[i]);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
     int n,a=0,w=0,t=0,r=0;
     cin>>n;
     for(int i=1;i<=n;i++)
     {
          string s;
          cin>>s;

          if(s=="AC") a++;
          if(s=="WA") w++;
          if(s=="TLE") t++;
          if(s=="RE") r++;
     }

     cout<<"AC x "<<a<<endl;
      cout<<"WA x "<<w<<endl;
       cout<<"TLE x "<<t<<endl;
        cout<<"RE x "<<r<<endl;


     return 0;
}


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

int main()
{
    char a[10] = {'w','a','k','s','t','n','h','m','y','r'};
    char b[5] = {'a','i','u','e','o'};
    int c[128];
    c['T'] = 0;
    c['L'] = 1;
    c['U'] = 2;
    c['R'] = 3;
    c['D'] = 4;

    string s;

    cin >> s;

    for( int i = 0; i < s.size(); i += 2 )
    {
        if( s[i] == '1' )
            cout << b[c[s[i+1]]];
        else if( s[i] == '0' && s[i+1] == 'U' )
            cout << "nn";
        else
            cout << a[s[i]-'0'] << b[c[s[i+1]]];
    }
    cout << endl;

    return 0;

}


Measured memory_bytes: 3232
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
	"unsafe"
)

func main() {
	N := sc.nextInt()
	S := sc.next()
	SArr := strings.Split(S, "")
	// ansArr := make([]string, N)
	ans := 0
	var prev string
	for i := 0; i < N; i++ {
		if SArr[i] == prev {
			continue
		}
		prev = SArr[i]
		// ansArr[i] = SArr[i]
		ans++
	}
	fmt.Println(ans)
}

var (
	sc scanner
)

func init() {
	sc = scanner{
		buf: make([]string, 0, 0),
		cur: 0,
		r:   bufio.NewReader(os.Stdin),
	}
}

type scanner struct {
	buf []string
	cur int
	r   *bufio.Reader
}

func (s *scanner) readln() {
	rbuf := make([]byte, 0, 0)
	for {
		line, prefix, err := s.r.ReadLine()
		if err != nil {
			panic(err)
		}
		rbuf = append(rbuf, line...)
		if prefix == false {
			break
		}
	}
	s.cur = 0
	s.buf = strings.Split(*(*string)(unsafe.Pointer(&rbuf)), " ")
}
func (s *scanner) isFull() bool {
	if s.cur == len(s.buf) {
		return true
	}
	return false
}
func (s *scanner) resetCur() {
	s.cur = 0
}
func (s *scanner) next() string {
	if s.cur == 0 {
		s.readln()
	}
	res := s.buf[s.cur]
	s.cur++
	if s.isFull() {
		s.resetCur()
	}
	return res
}
func (s *scanner) nexts() []string {
	s.readln()
	s.resetCur()
	return s.buf
}
func (s *scanner) nextInt() int {
	if s.cur == 0 {
		s.readln()
	}
	res, _ := strconv.Atoi(s.buf[s.cur])
	s.cur++
	if s.isFull() {
		s.resetCur()
	}
	return res
}
func (s *scanner) nextInts() []int {
	s.readln()
	res := make([]int, len(s.buf))
	for i := range s.buf {
		res[i], _ = strconv.Atoi(s.buf[i])
	}
	s.resetCur()
	return res
}
func (s *scanner) nextFloat() float64 {
	if s.cur == 0 {
		s.readln()
	}
	res, _ := strconv.ParseFloat(s.buf[s.cur],
		64)
	s.cur++
	if s.isFull() {
		s.resetCur()
	}
	return res
}
func (s *scanner) nextFloats() []float64 {
	s.readln()
	res := make([]float64, len(s.buf))
	for i := range s.buf {
		res[i], _ = strconv.ParseFloat(s.buf[i],
			64)
	}
	s.resetCur()
	return res
}
func digits(x int) int {
	return len(strconv.Itoa(x))
}
func powInt(x, p int) (result int) {
	result = 1
	for i := 0; i < p; i++ {
		result *= x
	}
	return
}
func max(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}
func min(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}
func abs(x int) int {
	return int(math.Abs(float64(x)))
}
func varDump(value ...interface{}) {
	for _, v := range value {
		fmt.Fprintf(os.Stderr, "%#v\n", v)
	}
}
func yes() {
	fmt.Println("Yes")
}
func no() {
	fmt.Println("No")
}

// Pair a
type Pair struct {
	first  int
	second int
}

// Queue a
type Queue struct {
	v []Pair
}

// Push for queue
func (q *Queue) Push(v Pair) {
	q.v = append(q.v, v)
}

// Pop for queue
func (q *Queue) Pop() Pair {
	r := q.v[0]
	q.v = q.v[1:]
	return r
}

// Front for queue
func (q Queue) Front() Pair {
	return q.v[0]
}

// Empty return true if empty
func (q Queue) Empty() bool {
	return len(q.v) == 0
}


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

int main() {
  string s;
  cin >> s;
  
  vector<ll> ans(s.length(), 0);
  s += 'R';

  ll cnt = 0;
  char prev = 'R';

  for (ll i = 0; i < s.length(); i++) {
    if (prev == s[i]) cnt++;
    if (prev == 'L' && s[i] == 'R') {
      ans[i - cnt - 1] += cnt / 2;
      ans[i - cnt]     += (cnt + 1) / 2;
      cnt = 1;
    }
    else if (prev == 'R' && s[i] == 'L') {
      ans[i - 1] = (cnt + 1) / 2;
      ans[i]     = cnt / 2;
      cnt = 1;
    }
    prev = s[i];
  }

  for (ll i : ans) {
    cout << i << " ";
  }
  cout << endl;
}


Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>

int main(void) {
	// in
	int n;
	std::cin >> n;
	std::vector<int> w(n);
	for(int i = 0; i < n; ++i) std::cin >> w[i];
	
	// calc s1, s2
	int s1, s2;
	int diff_min = 114514;
	for(int i = 0; i <= n; ++i) {
		s1 = std::accumulate(w.begin(), w.begin() + i, 0);
		s2 = std::accumulate(w.begin() + i, w.end(), 0);
		diff_min = (diff_min < std::abs(s1 - s2) ? diff_min : std::abs(s1 - s2));
	}

	std::cout << diff_min << std::endl;

	return 0;
}


Measured memory_bytes: 256
import sys
N = int(sys.stdin.readline().rstrip())
S = list(map(str, sys.stdin.readline().rstrip()))

left = [None] * N
right = [None] * N
tmp_white,tmp_black = 0,0
for i in range(N):
	if S[i] == '#':
		tmp_black += 1
	left[i] = tmp_black

for i in range(N):
	if S[-(i+1)] == '.':
		tmp_white += 1
	right[-(i+1)] = tmp_white

ans = min(left[-1], right[0])

for i in range(1,N):
	ans = min(ans, left[i-1] + right[i])

print(ans)

Measured memory_bytes: 14368
#include<iostream>
#include<vector>
using namespace std;
int n,a,b;
int main(){
  while(1){
    cin>>n>>a>>b;
    if(n==0&&a==0&&b==0)break;
    vector<bool> t(n+1);
    t[0]=true;
    int ans=-1;
    for(int i=0;i<=n;i++){
      ans+=t[i];
      if(t[i]&&i+a<=n)t[i+a]=true;
      if(t[i]&&i+b<=n)t[i+b]=true;
    }
    cout<<n-ans<<endl;
  }
  return 0;
}

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

int main() {
  int N;
  cin >> N;
  int result = 0;
  vector<int> num(N);
  for (int i = 0; i < N; i++)
  {
    cin >> num.at(i);
  }
  
  for (int i = 0; i < N; i++)
  {
    for (int j = i + 1; j < N; j++)
    {
      result += num.at(i) * num.at(j);
    }
  }
  cout << result << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdbool.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define rep(i,n) for(int i=0; i <(n); i++)

int main(){
  int n,m;
  scanf("%d%d",&n,&m);
  printf("%d\n",(n-1)*(m-1));
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
bool ask(int a,int b){
	cout<<"? "<<a<<" "<<b<<endl;
	string str;
	cin>>str;
	return str=="Y";
}
int main(){
	int n,a,b,i,j,k,lol;
	stack<int> st;
	cin>>a>>b;
	if(a<=b){
		cout<<"Impossible"<<endl;
		return 0;
	}
	n=a+b;
	for(i=0;i<n;i++){
		if(st.empty()){
			st.push(i);
			continue;
		}
		if(ask(i,st.top())){
			st.push(i);
		}else{
			st.pop();
		}
	}
	while(!st.empty()){
		lol=st.top();
		st.pop();
	}
	string ans(n,'0');
	for(i=0;i<n;i++){
		if(ask(lol,i)) ans[i]='1';
	}
	cout<<"! "<<ans<<endl;
}

Measured memory_bytes: 848
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    u,v,w = map(int,(input().split()))
    tree[u-1].append((v-1,w))
    tree[v-1].append((u-1,w))
color = [-1]*N
black = 0
white = 1
color[0] = white
def dfs(cur,parent):
    li = tree[cur]
    for chi,dis in li:
        if chi == parent:
            continue
        if dis % 2 == 0:
            color[chi] = color[cur]
            dfs(chi,cur)
        else:
            if color[cur] == black:
                color[chi] = white
            else:
                color[chi] = black
            dfs(chi,cur)
dfs(0,-1)
for i in color:
    print(i)

Measured memory_bytes: 89260
from collections import defaultdict

d = defaultdict(list)

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

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

for i in range(M):
    a, b = list(map(int, input().split()))
    d[a-1].append(b-1)
    d[b-1].append(a-1)

ans = 0
for i in range(N):
    ng = 0

    if(i not in d):
        ans += 1
        continue

    for j in d[i]:
        if(H[i] <= H[j]): ng = 1
    if(ng != 1):
        ans += 1

print(ans)

Measured memory_bytes: 34416
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;

int main(){
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    vector<int> arrx(n), arry(m);
    rep(i,n){
        cin >> arrx[i];
    }
    
    rep(i,m){
        cin >> arry[i];
    }

    sort(arrx.begin(),arrx.end());
    sort(arry.begin(),arry.end());
    int Xmin = arrx[0],Xmax = arrx[arrx.size() - 1];
    int Ymin = arry[0],Ymax = arry[arry.size() - 1];
    //cout << Xmin << "," << Xmax << endl;
    //cout << Ymin << "," << Ymax << endl;
    reps(i,x+1,y){
        if(Xmax < i && i <= Ymin){
                cout << "No War" << endl;
                return 0;
        }
    }

/*
    if(Xmax < Ymin){
        //区間 Xmax + 1, YminまでにX < Z <= Yを満たす数があるか？
        reps(i,Xmax+1,Ymin+1){
            cout << "ch:" << i << endl;
            if(x < i && i <= y){
                //cout << i << endl;
                cout << "No war" << endl;
                return 0;
            }
        }
    }
*/

    cout << "War" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline int rd(char c[]){
  int i, sz=0;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
char C[3][5];
int main(){
  int i;
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<3;Lj4PdHRW++){
      rd(C[Lj4PdHRW]);
    }
  }
  for(i=0;i<3;i++){
    C[0][i] = C[i][i];
  }
  wt_L(C[0]);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190721-1

// --- original code ---
// char C[3][5];
// {
//   rd(C(3));
//   rep(i,3) C[0][i] = C[i][i];
//   wt(C[0]);
// }


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

int main() {
  string S;
  cin >> S;
  long long ans = 0;
  for (int bit = 0; bit < 1 << (S.size() - 1); bit++) {
    int s = 0;
    for (int i = 0; i < S.size() - 1; i++) {
      if (bit & 1 << i) {
        ans += stoll(S.substr(s, i - s + 1));
        s = i + 1;
      }
    }
    ans += stoll(S.substr(s, S.size() - s));
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import fractions

a, b, c, d = map(int, input().split())

mc = b // c
md = b // d
mcd = b // ((c * d) // (fractions.gcd(c, d)))

mb = b - mc - md + mcd

amc = (a - 1) // c
amd = (a - 1) // d
amcd = (a - 1) // ((c * d) // fractions.gcd(c, d))

ma = (a - 1) - amc - amd + amcd

print(int(mb - ma))


Measured memory_bytes: 5076
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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


ans = INF
for a in A:
    cnt = 0
    while True:
        q, mod = divmod(a, 2)
        if mod != 0:
            break
        cnt += 1
        a = q
    ans = min(ans, cnt)
print(ans)


Measured memory_bytes: 9128
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long i64;

int n;
i64 k;
vector<i64> a;

int ope(int a,int b)
{
	return a + b;
}
struct Segment
{
	vector<int> node;
	int n;
	
	int init = 0;

	Segment(const vector<int>& vec)
	{
		int sz = vec.size();
		n = 1;
		while(n < sz) n <<= 1;

		node.resize(2 * n - 1,init);
		
		for(int i = 0;i < sz;i++)
		{
			node[n - i + 1] = vec[i];
		}
		for(int i = n - 2;i >= 0;i--)
		{
			node[i] = ope(node[i * 2 + 1] , node[i * 2 + 2]);

		}
	}

	void update(int i)
	{
		i += n - 1;

		node[i]++;

		while(i > 0)
		{
			i = (i - 1) / 2;
			node[i] = ope(node[i * 2 + 1],node[i * 2 + 2]);
		}
	}

	int get_inter(int a,int b,int k = 0,int l = 0,int r = -1)
	{
		if(r < 0) r = n;

		if(a <= l && r <= b) return node[k];

		if(r <= a || b <= l) return init;

		int lv = get_inter(a,b,2 *k + 1 ,l ,(l + r) / 2);
		int rv = get_inter(a,b,2 * k + 2,(l + r) / 2,r);

		return ope(lv,rv);
	}
};

vector<i64> vec;



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

	a.assign(n,0);

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

	vec.push_back(a[0]);
	
	for(int i = 1;i < n;i++)
	{
		a[i] += a[i - 1];
		vec.push_back(a[i]);
	}

	sort(vec.begin(),vec.end());

	i64 res = 0;
	i64 now = 0;

	Segment seg(vector<int>(n + 1,0));
	for(int i = 0;i < n;i++)
	{
		int ite = lower_bound(vec.begin(),vec.end(),now) - vec.begin();
		res += n - ite - seg.get_inter(ite,n + 1);
		now = a[i];
		ite = lower_bound(vec.begin(),vec.end(),now) - vec.begin();
		seg.update(ite);
	}

	cout << res << endl;
}




Measured memory_bytes: 6256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isIn(x,y,h,w) (x >= 0 && x < h && y >= 0 && y < w)
#define int long long
#define debug(var) cout << "[" << #var << "] " << var << endl
//using ll = long long;

const int INF=1e+18;
const double EPS=1e-9;
const int MOD=998244353;

signed main() {
    int n;
    cin >> n;
    switch (n % 10)
    {
        case 0:
            cout << "pon";
            break;
        case 1:
            cout << "pon";
            break;
        case 2:
            cout << "hon";
            break;
        case 3:
            cout << "bon";
            break;
        case 4:
            cout << "hon";
            break;
        case 5:
            cout << "hon";
            break;
        case 6:
            cout << "pon";
            break;
        case 7:
            cout << "hon";
            break;
        case 8:
            cout << "pon";
            break;
        case 9:
            cout << "hon";
            break;
        default:
            break;
    }

}

Measured memory_bytes: 3676
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include <functional>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(var,init,end) for(int var=init;var<end;var++)
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

int main() {
	vector<int> abc(3);
	FOR(i, 0, 3) {
		cin >> abc[i];
	}
	sort(abc.begin(), abc.end(), std::greater<int>());

	cout << (abc[0] * 10 + abc[1] + abc[2]);

	return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scanner = new Scanner(System.in);
		char[] charSet = scanner.nextLine().toCharArray();
		int len = charSet.length;

		List<Character> zeroStart = new ArrayList<Character>();
		List<Character> oneStart = new ArrayList<Character>();
		int zcnt = 0;
		int ocnt = 0;
		for(int i = 0; i < len; i++){
			zeroStart.add(Integer.toString(i%2).toCharArray()[0]);
			oneStart.add(Integer.toString((i+1)%2).toCharArray()[0]);

			if(!zeroStart.get(i).equals(charSet[i])){
				zcnt++;
			}else{
				ocnt++;
			}
		}
		int min = Math.min(zcnt, ocnt);


		System.out.println(min);
		scanner.close();
	}

}


Measured memory_bytes: 43980
//containing t test cases
#include<bits/stdc++.h>
#define pb push_back
#define mod 1000000007
#define mkp make_pair
#define fi first
#define se second
#define ll long long
#define scan(n) ll a[n]; for(ll i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(ll i=x;i<y;i++)
//#define int long long
using namespace std;
typedef vector<int>vi ;
typedef vector<ll>vll ;
typedef vector<vector<ll> >vvl ; 
typedef pair<ll,ll> pll ;
typedef vector<pair<ll,ll> > vpll;
/*vi adj[200005];
ll vis[200005];
ll parent[200005];
ll level[200005];
ll arr[200005];
ll size[200005];*/
//endl mut bhool!!
int main()
{
	fast;
	int test=1;
	//cin>>test;
	while(test--)
	{
		ll x;
		cin>>x;
		ll p=100;
		if(p>=x)
		{
			cout<<"0";
			return 0;
		}
		ll i=0;
		ll z;
		while(p<x)
		{
			i++;
			z=p/100;
			p+=z;
			if(p>=x)
			{
				cout<<i;
				return 0;
			}
		}
	}
	return 0;
}
/*
cout<<"YES"<<endl;
cout<<"NO"<<endl;
*/



Measured memory_bytes: 3636
// #pragma GCC target("avx2")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	if(a<0LL)return 0;
	if(b<0LL)return 0;
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
// ここから編集しろ

int p[110000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",p+i);
	for(int i=0;i<a;i++)p[i]-=i;
	std::sort(p,p+a);
	long long ret=0;
	for(int i=0;i<a;i++){
		ret+=ABS(p[i]-p[a/2]);
	}
	printf("%lld\n",ret);
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
typedef long long ll;
#pragma GCC optimize(3)
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > >
template<class T> inline T min(T &x,const T &y){return x>y?y:x;}
template<class T> inline T max(T &x,const T &y){return x<y?y:x;}
int read()
{
    int x=0,f=1;	char c=getchar();
    while(c<'0'||c>'9')	{if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9')	{x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct ios
{
    inline char gc()
    {
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template <typename _Tp> inline ios & operator >> (_Tp&x)
    {
        static char ch,sgn; ch = gc(), sgn = 0;
        for(;!isdigit(ch);ch=gc())
        {   
            if(ch==-1)return *this;sgn|=ch=='-';
        }
        for(x=0;isdigit(ch);ch=gc())x=(((x<<2)+x)<<1)+(ch^'0');
        sgn&&(x=-x); return *this;
    }
}io;
const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;
/** keep hungry and keep calm! **/

/**
1 2 3 4 5
共有10种情况
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
暴力枚举每一种情况 
**/
ll n,a[6],ans;
string s[200000];
int main()
{
    n = read();
    for(int i=1;i<=n;i++) cin >> s[i];
    for(int i=1;i<=n;i++)
	{
        if(s[i][0] == 'M') ++a[1];
        if(s[i][0] == 'A') ++a[2];
        if(s[i][0] == 'R') ++a[3];
        if(s[i][0] == 'C') ++a[4];
        if(s[i][0] == 'H') ++a[5];
    }
    ans += a[1]*a[2]*a[3];
    ans += a[1]*a[2]*a[4];
    ans += a[1]*a[2]*a[5];
    ans += a[1]*a[3]*a[4];
    ans += a[1]*a[3]*a[5];
    ans += a[1]*a[4]*a[5];
    ans += a[2]*a[3]*a[4];
    ans += a[2]*a[3]*a[5];
    ans += a[3]*a[4]*a[5];
    ans += a[2]*a[4]*a[5];
    printf("%lld\n",ans);
    return 0;
}

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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 x;
    cin >> x;
    int32 ans = 0;
    ans += x / 500 * 1000;
    x %= 500;
    ans += x / 5 * 5;
    ANS(ans);
    return 0;
}

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

int main(){
	int i,n,b,mint,x,y;
	int minm=32767,tmint;
	long long a[2][1000];
	cin>>n>>mint;
	int n1=0;
	for (i=0;i<n;i++){
		cin>>x>>y;
		if (y<=mint){
			a[0][n1]=x;
			a[1][n1]=y;
			n1++;
		}
	}
	for (i=0;i<n1;i++){
		if (a[0][i]< minm){
			minm=a[0][i];
		}
	}
	if (n1 != 0){
		cout<<minm;
		
	}else{
		cout<<"TLE";
	}
}

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

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n,a,b,fl=0,i;
	cin>>n;
	cin>>a>>b;
	for(i=a;i<=b;i++) {
		if(i%n==0) {
			cout<<"OK";
			fl=1;
			break;
		}
	}
	if(fl==0) cout<<"NG";
}

Measured memory_bytes: 3636
#include<stdio.h>
int main()
{
    int a,b;
    scanf("%d %d", &a, &b);
    if((a+b) % 2 == 0){
        printf("%d", (a+b)/2);
    }else{
        printf("IMPOSSIBLE");
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 128
#if loc||local
#define _GLIBCXX_DEBUG
#endif

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

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = __int128_t;
using pll = pair<ll,ll>;
constexpr ll INF = 1LL<<60;
constexpr ll MOD = 1e9+7;
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(a>b){a=b;return 1;}return 0;}
#if loc||local
template<class T>void dump(T&& t){cerr<<t<<endl;}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){cerr<<h<<", ";dump(forward<Ts>(t)...);}
#else
void dump(){}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){}
#endif
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T> ostream &operator<<(ostream& os,vector<T>const& v){for(auto const& vi:v)os<<vi<<" ";return os;}
template<class T,class U> ostream &operator<<(ostream& os,pair<T,U>const& p){os<<p.first<<","<<p.second;return os;}
template<class T>vector<T> vec(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto vec(size_t a, Ts... ts){return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...));}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
signed main(){

  int64_t _x,_k,_d;
  cin>>_x>>_k>>_d;
  ll x=_x,k=_k,d=_d;

  ll ax = abs(x);
  if(ax>k*d){
    ax -= k*d;
    cout<< ax <<endl;
    return 0;
  }

  ll xd = ax/d;
  k -= xd;
  ax -= xd*d;

  cout<<(k&1?abs(ax-d):ax)<<endl;

}


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


int main()
{
    int n,k,a[2005];
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i) scanf("%d",a+i);
    sort(a+1,a+n+1);
    for(int i=1;i<=k;++i) a[i]+=a[i-1];
    cout<<a[k];
}

Measured memory_bytes: 3704
#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>;

int main() {
    int n;
    cin >> n;
    vector<P> a(n);
    rep(i, n) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a.begin(), a.end());

    rep(i, n) {
        cout << a[i].second + 1 << ' ';
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    int n,i;
    cin>>n;
    vector<ll> a(n),b(n),c(n);
    for (i=0;i<n;i++)
        cin>>a[i];
    for (i=0;i<n;i++)
        cin>>b[i];
    for (i=0;i<n;i++)
        cin>>c[i];
    sort(a.begin(),a.end());
    sort(c.begin(),c.end());
    ll ans=0;
    for (i=0;i<n;i++)
        ans+=(lower_bound(a.begin(),a.end(),b[i])-a.begin())*(n-(upper_bound(c.begin(),c.end(),b[i])-c.begin()));
    cout<<ans<<endl;
}

Measured memory_bytes: 2560
#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 1010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,m,b[N],cnt=0;
ll a[N*N],c[N*N],ans;
int main()
{
/*#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	const char LL[]="%I64d\n";
#else
	const char LL[]="%lld\n";
#endif*/
	n=read(),m=read();
	for (int i=1;i<=n;i++) b[i]=read();
	for (int i=1;i<=n;i++)
	{
		a[++cnt]=b[i];
		for (int j=i+1;j<=n;j++)
		cnt++,a[cnt]=a[cnt-1]+b[j];
	}
	n=cnt;
	for (int j=40;~j;j--)
	{
		int s=0;
		for (int i=1;i<=n;i++)
		if (a[i]&(1ll<<j)) c[++s]=a[i];
		if (s>=m)
		{
			ans+=1ll<<j;n=s;
			for (int i=1;i<=s;i++) a[i]=c[i];
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 7296
// Problem : E - Logs
// Contest : AtCoder - AtCoder Beginner Contest 174
// URL : https://atcoder.jp/contests/abc174/tasks/abc174_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long
#define db double
#define mod 1000000007
#define pb push_back
#define pp pair<int,int>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repe(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=b;i>=a;i--)
#define maxn 200005
#define ss second
#define ff first
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
int inv(int a, int b){
 return 1<a ? b - inv(b%a,a)*b/a : 1;
}
int n,k;
int a[maxn];
int check(int x)
{
	int c=k;
	for(int i=0;i<n;i++)
	{
		int ct = a[i]/x;
		if(a[i]%x == 0)
			ct--;
		if(ct > c)
		return 0;
		c-=ct;
	}
	return 1;
}
void solve()
{
	cin >> n >> k;
	rep(i,0,n)
		cin >> a[i];
	int start=1,end=(int)(1e9);
	int ans;
	while(start <= end)
	{
		int mid=(start+end)/2;
		if(check(mid))
		{
			ans = mid;
			end = mid-1;
		}
		else start = mid+1;
	}	
	cout << ans;
}
signed main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}


Measured memory_bytes: 5160
from itertools import combinations
mod=10**9+7
def solve(n,k,a):
  if min(a)>0:
    ans=1
    a.sort(reverse=1)
    for i in a[:k]:
      ans*=i
      ans%=mod
    return ans
  if max(a)<0:
    if k%2==0:
      a.sort()
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
    else:
      a.sort(reverse=1)
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
  if n==k:
    ans=1
    for i in a:
      ans*=i
      ans%=mod
    return ans
  if k==1:
    return max(a)
  if n-k==1:
    ans=1
    if a.count(0)>1:return 0
    p=[]
    m=[]
    for i in a:
      if i>0:p.append(i)
      elif i<0:m.append(i)
    if 0 in a:
      if len(m)%2==0:
        for i in a:
          if i==0:continue
          ans=(ans*i)%mod
      else:ans=0
    else:
      if len(m)%2==0:
        for i in sorted(p)[1:]+m:ans=(ans*i)%mod
      else:
        for i in p+sorted(m)[:-1]:ans=(ans*i)%mod
    return ans


  ans=1
  p=[]
  m=[]
  for i in a:
    if i<0:m.append(i)
    elif i>=0:p.append(i)
  p.sort()
  m.sort(reverse=1)

  while k>1:
    if k<=5:
      if len(p)>=10:p=p[-10:]
      if len(m)>=10:m=m[-10:]
      ans*=solve2(len(p)+len(m),k,m+p)
      ans%=mod
      k=0
      break
    if len(p)<2:
      ans*=m.pop()*m.pop()
      k-=2
    elif len(m)<2:
      ans*=p.pop()*p.pop()
      k-=2
    elif m[-1]*m[-2]>p[-1]*p[-2]:
      ans*=m.pop()*m.pop()
      k-=2
    else:
      ans*=p.pop()*p.pop()
      k-=2
    ans%=mod
  if k:
    ans*=p.pop()
  return ans

def solve2(n,k,a):
  ans=-10**20
  for c in combinations(range(n),k):
    anss=1
    for i in c:anss*=a[i]
    ans=max(ans,anss)
  return ans%mod

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


Measured memory_bytes: 109032
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針

int main(){
    ll N, T;
    cin >> N >> T;
    ll t[N];
    FOR(i, 0, N) cin >> t[i];
    ll start = t[0], end = start + T, ans = 0;
    FOR(i, 1, N){
        if(end <= t[i]){
            ans += end - start;
            start = t[i];
            end = start + T;
        }
        //被ってる
        else{
            end = t[i] + T;
        }
    }
    ans += end - start;
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;;
#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef long long ll;
typedef long double ld;
typedef vector<ll> vl;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;

ll divi(ll x){
  vector<ll> v;
  for(ll i = 2; i*i<=x; i++){
    if(x%i==0){
      v.push_back(i);
      if(i*i!=x)v.push_back(x/i);
    }
  }
  return v.size()+1ll;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll k;cin >> k;
  if(k==2){
    cout << 1 << endl;
    return 0;
  }
  ll ans = divi(k-1);
  vector<ll> v;
  for(ll i = 2; i*i<=k; i++){
    if(k%i==0){
      v.push_back(i);
      if(i*i!=k)v.push_back(k/i);
    }
  }
  
  v.push_back(k);
  rep(i,v.size()){
    ll x = v[i];
    ll tmp = k;
    while(tmp%x==0)tmp/=x;
    if(tmp%x==1)ans++;
  }
  cout << ans << endl;
  

}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include<cstdio>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<queue>
using namespace std;
int main() {
	int n,m;
	int dp1[1005] = {0}, dp2[1005] = {0};
	int fa[1005] = {0};
	int wed[1005] = { 0 };
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> fa[i];
	}
	for (int j = 1; j <= m; j++) {
		cin >> wed[j];
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < i; j++) {
			if (dp2[j] > dp1[j]||dp2[j]==0) {
				dp2[j] = dp1[j];
			}
			if (dp2[j + 1] > dp1[j]+fa[j+1]*wed[i] || dp2[j + 1] == 0) {
				dp2[j + 1] = dp1[j] + fa[j + 1] * wed[i];
			}
		}
		for (int j = 0; j <= i; j++) {
			dp1[j] = dp2[j];
			dp2[j] = 0;
		}
	}
	cout << dp1[n] << endl;
	return 0;
}

Measured memory_bytes: 3100
import math
L = 10**6 + 1

N = int(input())
A = list(map(int, input().split()))
memo = [0] * L
flag = 0 # 0をpairwise coprime

for a in A:
    memo[a] += 1

for i in range(2, L): # すべてでgcdが1ということは、対象の数字ごとのステップに数字がないことと同じ
    if sum(memo[i::i]) > 1: # memo[i] + memo[2i] +... + memo[ni] memo[i]の倍数があれば sum は 2 以上になる
        flag = 1
        break

g = 0
for i in range(N):
    g = math.gcd(g, A[i])

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)

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

int main(){
    string S;
    cin >> S;
    
    string ans = "AC";
    
    if(S.at(0) != 'A'){
        ans = "WA";
    }
    
    int cnt = 0;
    for(int i = 1;i < S.size();i++){
        if(isupper(S.at(i))){
            if(i == 1 || i == S.size() - 1||S.at(i) !='C'){
                ans = "WA";
            }
            cnt++;
        }
    }
    
    if(cnt != 1){
        ans = "WA";
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<cmath>
#define pb push_back
#define ld long double
#define mp make_pair
#define vl vector<ll> 
#define vd vector<double>
#define vld vector<long double>
#define ll long long int
#define pl pair<ll, ll>
#define all(a) a.begin(), a.end()
#define forr(i, n) for(ll i=0; i<n; i++) 
#define forr1(i, n) for(ll i=1; i<=n; i++)
using namespace std;
const ld PI =3.1415926535897923846;
const ll MOD = 1e9+7;
void solve()
{
    string str;
    cin>>str;
    ll n=str.length();
    ll num=2019;
    vl a(num);
    ll ans=0;
    ll pow_of_ten=1;
    ll suf=0;
    a[0]++;
    for(ll i=n-1; i>=0; i--)
    {
        ll dig=str[i]-'0';
        suf=((dig*pow_of_ten)+suf)%num;
        pow_of_ten=pow_of_ten*10%num;
        ans+=a[suf];
        a[suf]++;
    }
    cout<<ans;
}
int main()
{
    ll test=1;
    //cin>>test;
    while(test--)
        solve();
}

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

ll gcd(ll a, ll b) {
  return b?gcd(b,a%b):a;
}

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

int main(){
  ll n,ans;cin>>n>>ans;
  REP(i,n-1){
    ll temp;cin>>temp;
    ans=lcm(ans,temp);
  }

  cout<<ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
ll MOD = 1e9 + 7;

int main() {
    int n, k;
    ll R, S, P;
    string t;
    cin >> n >> k >> R >> S >> P >> t;
    int r = 0, s = 0, p = 0;
    for (int i = 0; i < n; i++) {
        if (i >= k) {
            if (t[i] == t[i - k]) t[i] = 'x';
        }
        if (t[i] == 'r') r++;
        if (t[i] == 's') s++;
        if (t[i] == 'p') p++;
    }
    cout << r * P + s * R + p * S << endl;
    return 0;
}

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

int main()
{
    int n,k;
    cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++) cin>>arr[i];
    bool dp[k+1];
    dp[0]=false;
    for(int i=1;i<=k;i++){
   dp[i]=false;
   for(int j=0;j<n;j++) if(i-arr[j]>=0 && dp[i-arr[j]]==false) {
       dp[i]=true;
       break;
   }
}
if(dp[k]==true) cout<<"First";
else cout<<"Second";
    

    return 0;
}


Measured memory_bytes: 384
#include <cstdio>
#include <cstring>

const int N = 100000 + 10;

int n, m;
char s[N], t[N];
int x[N], y[N];

int main() {
  scanf(" %s %s", s + 1, t + 1);
  n = strlen(s + 1);
  m = strlen(t + 1);
  for (int i = 1; i <= n; ++i) x[i] = x[i - 1] + s[i] - 'A' + 1;
  for (int i = 1; i <= m; ++i) y[i] = y[i - 1] + t[i] - 'A' + 1;
  int q;
  for (scanf("%d", &q); q--;) {
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    int u = (x[b] - x[a - 1]) % 3, v = (y[d] - y[c - 1]) % 3;
    puts(u == v ? "YES" : "NO");
  }
  return 0;
}


Measured memory_bytes: 1408
/*
 * written by Yaqi Zhang
 * University of Wisconsin-Madison
 * 2020
 */

#include<algorithm>
#include<cstring>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stdio.h>
#include<vector>

#define INF 0x3f3f3f3f

using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 4000
    int n;
    cin >> n;
    string s;
    cin >> s;
    // 1 <= i < j < k <= N
    // j - i != k - j
    // triplets ...
    // RGB
    // subsequence
    // RRGB: RGB
    vector<vector<int>> idxes(3);
    for(int i = 0; i < n; ++i) {
        if(s[i] == 'R') idxes[0].push_back(i);
        else if(s[i] == 'G') idxes[1].push_back(i);
        else idxes[2].push_back(i);
    }
    long long ans = 0LL;
    for(int i = 0; i < 3; ++i) {
        int jj = (i + 1) % 3;
        int kk = 3 - i - jj;
        vector<int> js = {jj, kk};
        for(int j : js) {
            int k = 3 - i - j;
            for(int ia = 0; ia < (int) idxes[i].size(); ++ia) {
                int a = idxes[i][ia];
                auto itb = lower_bound(idxes[j].begin(), idxes[j].end(), a);
                int start_b = itb - idxes[j].begin();
                for(int ib = start_b; ib < (int) idxes[j].size(); ++ib) {
                    int b = idxes[j][ib];
                    auto itc = lower_bound(idxes[k].begin(), idxes[k].end(), b);
                    // need to know if exit ib - ia == ic - ib
                    ans += idxes[k].end() - itc;
                    auto it = lower_bound(itc, idxes[k].end(), 2 * b - a);
                    if (it != idxes[k].end() && (*it) == 2 * b - a) ans -= 1;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;

}



Measured memory_bytes: 3652
def inc3(i):
    if i - (i // 10)*10 == 3:
        return(True)
    elif i//10==0:
        return(False)
    else:    
        return(inc3(i//10))

n = int(input())
for i in range(1,n+1):
    if i%3==0 or inc3(i):
        print(" " + str(i),end="")
print()


Measured memory_bytes: 5872
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <sstream>
#include <cassert>
using namespace std;

struct Score {
    int student_number;
    int score;
    Score() {
        score = 0;
    }
    bool operator>(const Score& o) const {
        return score == o.score ? student_number < o.student_number : score > o.score;
    }
};

int calc_score(istringstream& is) {
    vector< pair<int, int> > frame(12); // フレームごとの投球情報. 1-indexed

    int score = 0;

    int bonus_spare = 0;
    int bonus_strike = 0;
    int pin;
    int cur_frame = 1;
    int cur_pin = 0;
    bool first_bowl = true;
    while (is >> pin) {
        if (cur_frame != 11) score += pin;
        if (bonus_spare) {
            score += pin * bonus_spare;
            bonus_spare = bonus_strike;
            bonus_strike = 0;
        } 
//        cout << score << ' ';

        if (cur_frame == 11) {
            if (first_bowl) {
                frame[cur_frame].first = pin;
                first_bowl = false;
            } else {
                frame[cur_frame].second = pin;
            }
            continue;
        }

        if (pin == 10) {
            if (first_bowl) {
                frame[cur_frame].first = 10;
                frame[cur_frame].second = -1; // 投球がなかったことのフラグ
                cur_frame++;
                bonus_spare++;
                bonus_strike++;
                first_bowl = true;
            } else {
                frame[cur_frame].second = 10;
                cur_frame++;
                bonus_spare++;
                first_bowl = true;
            }
            continue;
        } 

        if (first_bowl) {
            frame[cur_frame].first = pin;
            first_bowl = false;
        } else {
            frame[cur_frame].second = pin;
            if (frame[cur_frame].first + frame[cur_frame].second >= 10) 
                bonus_spare++;
            first_bowl = true;
            cur_frame++;
        }
    }
    return score;
}

int main() {
    int n;
    while (cin >> n, n != 0) {
        cin.ignore(1);
        vector<Score> info(n);
        for (int i = 0; i < n; i++) {
            Score score;
            string s; getline(cin, s);
            istringstream is(s);
            is >> score.student_number;
            score.score = calc_score(is);
            info[i] = score;
        }
        sort(info.begin(), info.end(), greater<Score>());
        for (int i = 0; i < info.size(); i++) {
            cout << info[i].student_number << ' ' << info[i].score << endl;
        }
    }
    return 0;
}

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

int main(){
  int H1,M1,H2,M2,K;
  cin >> H1 >> M1 >> H2 >> M2 >> K;
  int S=60*H1+M1,T=60*H2+M2;
  cout << T-S-K << endl;
}

Measured memory_bytes: 3628
#include<stdio.h>
#define N 250


int main(){

  int T[N],i,n;

  scanf("%d",&n);

  for(i=1;i<=n;i++)scanf("%d",&T[i]);

  for(i=1;i<=n;i++){
    printf("node %d: key = %d, ",i,T[i]);
    if(i!=1)printf("parent key = %d, ",T[i/2]);
    if(2*i<=n) printf("left key = %d, ",T[2*i]);
    if(2*i+1<=n) printf("right key = %d, ",T[2*i+1]);

    printf("\n");
  }

  return 0;
}

Measured memory_bytes: 600
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);
		int Max = 3000;
		int[][] idata = new int[Max][2];
		String[] sdata = new String[2]; // 入力されたデータを半角区切りで分けて受け取るための配列
		String input = ""; // 入力されたデータを取る変数;
		int n = 0; // 入力されたデータの組数
		boolean inputjudge = true; // 入力された値が範囲内に収まっているかをチェックするための変数
		int temp = 0; // ２つの整数の順番を変える際に、片方の変数を一時的に格納しておくための変数

		for (int i = 0; i < idata.length; i++) {
			input = sc.nextLine();
			sdata = input.split(" ");
			if (sdata[0].equals("0") && sdata[1].equals("0")) {
				break;
			}
			idata[i][0] = Integer.parseInt(sdata[0]);
			idata[i][1] = Integer.parseInt(sdata[1]);

			if ((idata[i][0] >= 0 && idata[i][0] <= 10000)
					&& (idata[i][1] >= 0 && idata[i][1] <= 10000)) {
				n++; // 組数を1つカウントする
				if (idata[i][0] > idata[i][1]) { // 要素の順番を変更
					temp = idata[i][0];
					idata[i][0] = idata[i][1];
					idata[i][1] = temp;
				}
			} else {
				inputjudge = false;
				break;
			}

		}
		if (inputjudge == true) {

			for (int i = 0; i < n; i++) {
				System.out.println(idata[i][0] + " " + idata[i][1]);

			}
		}

	}

}



Measured memory_bytes: 36064