akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#define maxn 500009
using namespace std;
const int MOD=998244353;
struct Matrix{
	long long a[2][2];
	Matrix operator *(const Matrix &rhs)const{
		Matrix res;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				res.a[i][j]=0;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++){
					res.a[i][j]+=a[i][k]*rhs.a[k][j];
					res.a[i][j]%=MOD;
				}
		return res;
	}
	void output(){
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++)
				cout<<a[i][j]<<" ";
			puts("");
		}
	}
};
long long mgml(long long a,long long b){
	long long res=1;
	a%=MOD;
	while(b){
		if(b&1)
			res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}
Matrix matrix_mgml(long long b){
	Matrix res;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			if(i==j)
				res.a[i][j]=1;
			else
				res.a[i][j]=0;
	Matrix a;
	a.a[0][0]=a.a[0][1]=a.a[1][0]=1;
	a.a[1][1]=0;
	while(b){
		if(b&1)
			res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
long long fib(long long n){
	if(n==0)
		return 0;
	if(n<=2)
		return 1;
	else{
		Matrix M=matrix_mgml(n-2);
		return (M.a[0][0]+M.a[0][1])%MOD;
	}
}
long long comb(long long n,int m){
	long long ans=1;
	n%=MOD;
	for(int i=0;i<m;i++)
		ans=ans*(n-i)%MOD;
	for(int i=1;i<=m;i++)
		ans=ans*mgml(i,MOD-2)%MOD;
	ans+=MOD;
	ans%=MOD;
	return ans;
}
int main(){
	int n;long long m;
	cin>>n>>m;
	if(n==1){
		cout<<fib(m)<<endl;
	}
	else{
		long long ans=0;
		long long C=comb(m+n-3,n-2);
		for(int i=2;i<=n;i++){
			ans-=fib(2*i-2)*C%MOD;
			ans%=MOD;
			C=C*(n-i)%MOD*mgml(m+n-i-1,MOD-2)%MOD;
		}
		ans=ans+fib(m+2*(n-1))%MOD;
		ans+=MOD;
		ans%=MOD;
		cout<<ans<<endl;
	}
	//system("pause");
	return 0;
}

Measured memory_bytes: 384
import sys
from collections import deque

import numpy as np

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    N = ii()
    H = il()
    c = 0
    queue = deque([H])
    while queue:
        line = queue.popleft()
        a = []
        for x in line:
            if x < 0:
                continue
            if x != 0:
                a.append(x - 1)
            elif a:
                queue.append(a)
                a = []
        if a:
            queue.append(a)
        c += 1
    return c - 1


if __name__ == "__main__":
    print(solve())


Measured memory_bytes: 12480
import std.stdio;

void main() {
    ulong x, a, b;
    readf(" %s %s %s", &x, &a, &b);

    if (b > x + a) {
        writeln("dangerous");
    } else {
        if (b  > a) {
            writeln("safe");
        } else {
            writeln("delicious");
        }
    }
}

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

const double PI=3.14159265358979323846;

int main() {
    int A, B, H, M; cin >> A >> B >> H >> M;
    double t = M * 6.0;
    double s = (H + M / 60.0) * 30.0;
    double kakudo = abs(t - s);
    double c = sqrt(A * A + B * B - 2.0 * A * B * cos(2 * PI * kakudo / 360.0));
    cout << setprecision(20) << c << endl;
}

Measured memory_bytes: 4196
import java.util.Scanner;

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

        int n = Integer.parseInt(sc.next());
        double tmp = 100000.0;

        for (int i = 0; i < n; i++) {
            tmp *= 1.05;
            tmp /= 1000;
            tmp = Math.ceil(tmp);
            tmp *= 1000;
        }

        System.out.println((int)tmp);
    }
}

Measured memory_bytes: 25880
import bisect
N,K= map(int,input().split())
V = list(map(int,input().split()))
sortedV = sorted(V)
rV = V[::-1]

ans = -10**10
for nout in range(K+1):
    nin = K-nout
    if nout >= N:
        cand = sortedV
        ind = bisect.bisect_left(cand,0)
        ind = min(ind,nin)
        ans = max(ans, sum(cand[ind:]))
    else:
        for nleft in range(nout+1):
            nright = nout - nleft
            cand = V[:nleft] + rV[:nright]
            cand.sort()
            ind = bisect.bisect_left(cand,0)
            ind = min(ind,nin)
            ans = max(ans, sum(cand[ind:]))
print(ans)






Measured memory_bytes: 41960
use std::io::{stdout, Write, BufWriter};
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

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

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

fn main() {
    input!{
        n: usize,
    }

    let out = stdout();
    let mut out = BufWriter::new(out.lock());

    writeln!(out, "{}", count(n, 0)).unwrap();
}

fn count(n: usize, x: usize) -> usize{
    if n < x {
        return 0;
    }

    let mut ret = 1;
    for c in "357".chars() {
        if !x.to_string().contains(c) {
            ret = 0;
            break;
        }
    }

    for c in "357".chars() {
        let next = x * 10 + (c as usize - 48);
        ret += count(n, next);
    }

    ret
}

Measured memory_bytes: 4352
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

int H, W, K;
char s[345][345];
int a[345][345];

int main() {

	scanf("%d%d%d", &H, &W, &K);
	rep(i, H) scanf("%s", &s[i]);

	int fh = -1;
	rep(i, H) {
		rep(j, W)
			if (s[i][j] == '#') {
				fh = i;
				break;
			}
		if (fh >= 0) break;
	}


	int id = 1;
	rep(i, H - fh) {
		bool f = false;
		rep(j, W) {
			if (s[i + fh][j] == '#') f = true;
		}
		bool first = true;
		rep(j, W) {
			if (f) {
				if (s[i + fh][j] == '#') {
					if (first) first = false;
					else id++;
				}
				a[i + fh][j] = id;
			}
			else {
				a[i + fh][j] = a[i + fh - 1][j];
			}
		}
		if (f) id++;
	}

	for (int i = fh - 1; i >= 0; --i) {
		rep(j, W)
			a[i][j] = a[i + 1][j];
	}

	rep(i, H) {
		rep(j, W)
			printf("%d ", a[i][j]);
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1280
from numpy import*
from itertools import*
N, K = map(int, input().split())
S=input()
zeros=[0]+[len(list(v)) for k,v in groupby(S) if k=="0"]
ones =[0]+(S[0]=="0")*[0]+[len(list(v)) for k,v in groupby(S) if k=="1"]+(S[-1]=="0")*[0]

#print(zeros,ones)

c_zero= cumsum(zeros)
c_one = cumsum(ones)

#print(c_zero,c_one)

if len(zeros) <= K:
    print(len(S))
else:
    ans = 0
    for i in range( len(zeros)-K ):
        aaa = c_zero[i+K]-c_zero[i] + c_one[i+K+1]-c_one[i]
        ans = max(aaa, ans)
    print(ans)

Measured memory_bytes: 14976
n=int(input())
m=102
chars=['A','T','C','G']
mo=10**9+7
d4=set()
for i in chars:
    for j in chars:
        for k in chars:
            for l in chars:
                d4.add(i+j+k+l)
        
kinsoku4=set()
kinsoku3=['AGC','ACG','GAC']

for y in chars:
    kinsoku4.add('AG'+y+'C')
    kinsoku4.add('A'+y+'GC')
    for z in kinsoku3:
        kinsoku4.add(y+z)
        kinsoku4.add(z+y)

dp=[dict() for i in range(m)]
cnt=[0]*m
for i in d4:
    if i not in kinsoku4:
        dp[4][i]=1

t=1+n
for i in range(4,t):
    for ch in chars:
        for p in dp[i-1].keys():
            if p[1:4]+ch not in kinsoku4:
                if p[1:4]+ch in dp[i]:
                    dp[i][p[1:4]+ch]+=dp[i-1][p]%mo
                else:
                    dp[i][p[1:4]+ch]=dp[i-1][p]%mo
for i in range(t):
    for x in d4:
        if x not in kinsoku4 and x in dp[i]:
            cnt[i]+=dp[i][x]%mo
    cnt[i]%=mo

if n==3:
    ans=61
    print(ans)
else:
    print(cnt[n])


Measured memory_bytes: 42480
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Code author: Saurabh Singhal
Code copy karne vaale tera muh kaala
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/

#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define ppb pop_back

using namespace std;
typedef long long int ll;
typedef vector<int> vi_t;
typedef vector<ll> vll_t;
int t=1;
vll_t a,b;
int  main(){
	// #ifndef ONLINE_JUDGE
 //    // for getting input from input.txt
 //    freopen("input.txt", "r", stdin);
 //    // for writing output to output.txt
 //    freopen("output.txt", "w", stdout);
	// #endif
	int a,b,k;
	cin>>a>>b>>k;
	if(b-a+1<=2*k){
		for(int i=a;i<=b;i++){
			cout<<i<<endl;
		}
	}
	else{
		for(int i=0;i<k;i++){
			cout<<a+i<<endl;
		}
		for(int i=k-1;i>=0;i--){
			cout<<b-i<<endl;
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
ll a[1005];
int main()
{
    ll n;
    set<ll>s;
    cin >> n;
    for(ll i = 0; i < n; i ++)
    {
        cin >> a[i];
        s.insert(a[i]);
    }
    cout << s.size();
}


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

int main(){
  int N;
  cin >> N;
  int num[N];
  int count = -1;
  bool flag =true;
  
  for(int i=0; i<N; i++){
    cin >> num[i];
  }
  
  while(flag){
    for(int i=0; i<N && flag; i++){
      if(num[i]%2 != 0)flag = false;
      num[i] /= 2;
    }
    count++;
  }
  cout << count << endl;
  return 0;
   
}

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

int main() {
  char c;
  cin >> c;

    if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o') {
      cout << "vowel" << endl;
      }
    else {
      cout << "consonant" <<endl;
      }
}

Measured memory_bytes: 256
A=list(map(int,input().split()))
K=int(input())
a=A[0]
b=A[1]
c=A[2]
count=0
while count<=K:
    if a>=b:
        b=b*2
        count=count+1
    else:
        break
if count==K:
    pass
else:
    c=c*(2**(K-count))
if a<b<c:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9136
/*0ms,1360KB*/

#include<cstdio>
#include<cstring>

char grid[105][105], flag;

bool dfs(int i, int j)
{
	if (!grid[i][j] || grid[i][j] != flag) return false;
	grid[i][j] = 0;
	dfs(i - 1, j); dfs(i + 1, j); dfs(i, j - 1); dfs(i, j + 1);
	return true;
}

int main()
{
	int x, y, i, j, cnt;
	while (scanf("%d%d\n", &y, &x), x)
	{
		memset(grid, 0, sizeof(grid));
		cnt = 0;
		for (i = 1; i <= y; ++i)
			gets(grid[i] + 1);
		for (i = 1; i <= y; ++i)
			for (j = 1; j <= x; ++j)
			{
				flag = grid[i][j];
				if (dfs(i, j)) ++cnt;
			}
		printf("%d\n", cnt);
	}
	return 0;
}

Measured memory_bytes: 1360
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int mp[maxn][maxn];
int n,w,h,x,a[100005];
int main(){
    scanf("%d%d",&h,&w);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    x=1;
    for(int i=1;i<=h;i++){
        if(i%2==1){
            for(int j=1;j<=w;j++){
                if(a[x]){
                    mp[i][j]=x;
                    a[x]--;
                }else{
                    while(a[x]==0)x++;
                    mp[i][j]=x;
                    a[x]--;
                }
            }
        }else{
            for(int j=w;j>=1;j--){
                if(a[x]){
                    mp[i][j]=x;
                    a[x]--;
                }else{
                    while(a[x]==0)x++;
                    mp[i][j]=x;
                    a[x]--;
                }
            }
        }
    }
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cout<<mp[i][j]<<" ";
        }
        cout<<endl;
    }
}


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

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M; cin >> N >> M;
  priority_queue<ll, vector<ll>, greater<ll>> A;
  for(int i = 0; i < N; i++){
    int a; cin >> a;
    A.push(a);
  }

  vector<pair<int, int>> CB(M);
  for(int i = 0; i < M; i++){
    int B, C; cin >> B >> C;
    CB[i] = make_pair(C, B);
  }
  sort(CB.begin(), CB.end(), greater<pair<int, int>>());

  for(int i = 0; i < M; i++){
    int B = CB[i].second;
    int C = CB[i].first;
    for(int j = 0; j < B; j++){
      if(A.top() < C){
        A.pop();
        A.push(C);
      }else{
        break;
      }
    }
  }
  ll ans = 0;
  while(!A.empty()){
    ans += A.top();
    A.pop();
  }
  cout << ans << endl;
}


Measured memory_bytes: 1908
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;
	int cnt[][] = new int [11][340];
	boolean used[] = new boolean[10];
	void run() {
		Scanner sc = new Scanner(System.in);
		search(0, 10, 0, used);
		for(;sc.hasNext();) {
			int n = sc.nextInt();
			int s = sc.nextInt();
			if(s > 330 | n > 10) System.out.println(0);
			else System.out.println(cnt[n][s]);
		}
	}
	
	void search(int i, int n, int s, boolean[] used) {
//		System.out.println(s + " " + sum);
		cnt[i][s]++;
		if(i==n) return;
		for(int j=0;j<10;j++) {
			if(!used[j]) {
				used[j] = true;
				search(i+1, n, s+j*(i+1), used);
				used[j] = false;
			}
		}
	}

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

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define Rep(i,s,f) for(int i=(int)s;i<(int)f;i++)
#define INF 1e9
using ll=long long;
using namespace std;


int main()
{
	int N,M;
	cin>>N>>M;
	vector<pair<int,int>> ab(N);
	rep(i,N)
	{
		int a,b;
		cin>>a>>b;
		ab[i]=make_pair(a,b);
	}
	vector<pair<int,int>> cd(M);
	rep(i,M)
	{
		int c,d;
		cin>>c>>d;
		cd[i]=make_pair(c,d);
	}
	rep(i,N)
	{
		int min_v=INF;
		int min_i=-1;
		rep(j,M)
		{
			if(min_v>abs(ab[i].first-cd[j].first)+abs(ab[i].second-cd[j].second))
			{
				min_v=abs(ab[i].first-cd[j].first)+abs(ab[i].second-cd[j].second);
				min_i=j;
			}
		}
		cout<<min_i+1<<endl;
	}
	return 0;
}


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

#include <stdio.h>
//#include <string.h>
#include <string>
/********
*	??????????????????
*********/	
/*********??¢?????´?????????
*	(1)??????????????\???
*	(2)????????????????????????
*********/

int main(void)
{
	string word_T;	//???????????????
	string word_H;	//??±????????????
	int n; 			//n???????????????
	int point_T=0; 	//??????????????????
	int point_H=0; 	//??±???????????????
	
	
		cin >> n;
	
		for (int i=0; i< n; i++ ){
			cin >> word_T >>  word_H ;
		
			if( word_T > word_H  ){						//???????????????
				point_T =point_T + 3 ;
			} else if ( word_T < word_H ){				//??±????????????
				point_H = point_H +3;
			}else if( word_T == word_H ){					//??????
				point_T++ ;
				point_H++ ;
			} else {
			//?????????????????????
			}
		}
		cout << point_T << " "<< point_H << endl;
	
	return 0;
}

Measured memory_bytes: 1208
Sa = input()
Sb = input()
Sc = input()

Ca = 0
Cb = 0
Cc = 0

La = len(Sa)
Lb = len(Sb)
Lc = len(Sc)

def discard(player,Sa,Sb,Sc,Ca,Cb,Cc,La,Lb,Lc):
  if player == "A":
    if La == Ca:
      next_player = "A"
    else:
      next_player = Sa[Ca].upper()
    Ca = Ca + 1
    #print(next_player,Ca)
    return  next_player ,Sa,Sb,Sc,Ca,Cb,Cc,La,Lb,Lc
  elif player == "B":
    if Lb == Cb:
      next_player = "B"
    else:
      next_player = Sb[Cb].upper()
    Cb = Cb + 1
    return  next_player ,Sa,Sb,Sc,Ca,Cb,Cc,La,Lb,Lc
  else:
    if Lc == Cc:
      next_player = "C"
    else:
      next_player = Sc[Cc].upper()
    Cc = Cc + 1
    return  next_player ,Sa,Sb,Sc,Ca,Cb,Cc,La,Lb,Lc

player = "A"
#print(player,Sa,Sb,Sc,Ca,Cb,Cc,La,Lb,Lc)
while (La+1 >Ca) and( Lb+1 > Cb) and (Lc+1 > Cc):
  if (La+1 ==Ca) or (Lb+1 == Cb) or (Lc+1 == Cc):
    break
  condition = discard(player,Sa,Sb,Sc,Ca,Cb,Cc,La,Lb,Lc)
  player = condition[0]
  Ca = condition[4]
  Cb = condition[5]
  Cc = condition[6]
  #print(condition)
  
print(player)

Measured memory_bytes: 3064
#include<stdio.h>

int main(void){
  int N,A[100],swap,i,n,num=0,f=1;
  
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
  while(f){
    f=0;
    for(i=N-1;i>=0;i--){
      if(A[i]<A[i-1]){
	swap=A[i-1];
	A[i-1]=A[i];
	A[i]=swap;
	num++;
	f=1;
      }
   
    }
  } 
  for(n=0;n<N-1;n++){
    printf("%d ",A[n]);
  }
  printf("%d\n%d\n",A[n],num);
  return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
#include<numeric>
#include<set>
#include<math.h>
using namespace std;

// some defines

double rate = 380000.0;

int main(){

    // 浮動小数点で回答する問題にはこれ
    cout << fixed << setprecision(10);

    int N;
    cin >> N;
    double ans = 0.0;
    double x;
    string u;

    for(int i = 0; i < N; i++){
        cin >> x >> u;

        if(u == "JPY") ans += x;
        else ans += rate*x;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
# from collections import defaultdict
# from heapq import heappush, heappop, heapify
# from bisect import bisect_left, insort_left
# from itertools import groupby


class Solution:
    def main(self):
        # N = int(input())
        A, B = list(map(int, input().split()))

        res = 0

        print(max(A-2*B, 0))


if __name__ == '__main__':
    Solution().main()


Measured memory_bytes: 2940
import fractions
A, B, C, D = list(map(int, input().split()))

def f(x, y, z):
    return z // x - (y - 1) // x


print(B - A + 1 - f(C, A, B) - f(D, A, B) + f(int(C * D / fractions.gcd(C, D)),A, B))


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

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

using ll  = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

void func(string s) {
    int len = s.length();
    int cnt = 0;
    rep(i, len) {
        char j = '0' + i % 2;  // 理想形を作る 0101010
        if (s[i] == j) {
            cnt++;
        }
    }
    // 短いほうが正解
    cout << min(cnt, len - cnt) << endl;
}

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

    string s;
    cin >> s;

    func(s);
    return 0;
}


Measured memory_bytes: 512
/*
17/10/2017
*/
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
int main()
{
ll n,x,m;
cin>>n>>x>>m;
ll ans=0;
ll k=x%m;
ans+=k;
n--;
vector<ll> vc;
vc.push_back(ans);
map<ll,ll> mp;
mp[k]=1;
int cnt=0;
while(n>0)
{
k=(k*k)%m;
//cnt++;
//if(k==10000)
//{
//cout<<cnt<<endl;
//}
if(mp.count(k))
{
ll l=n/(vc.size()-mp[k]+1);
if(mp[k]==1)
{
ans+=(vc[vc.size()-1])*l;
}
else
{
ans+=(vc[vc.size()-1]-vc[mp[k]-2])*l;
}
n%=(vc.size()-mp[k]+1);
//cout<<ans<<endl;
break;
}
else
{
n--;
}
ans+=k;
vc.push_back(ans);
mp[k]=vc.size();
}
k=vc[vc.size()-1]-vc[vc.size()-2];
while(n>0)
{
k=(k*k)%m;
ans+=k;
n--;
}
cout<<ans;
}

Measured memory_bytes: 6656
import Control.Applicative
import Control.Monad
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)
import Text.Printf
import Debug.Trace

getInts :: IO [Int]
getInts = map (fst . fromJust . B.readInt) . B.words <$> B.getLine

substr :: Int -> Int -> B.ByteString -> B.ByteString
substr b l s = B.take l $ B.drop b s

main = do
  s <- B.getLine
  let b = fromJust $ 'A' `B.elemIndex` s
  let e = B.length s - (fromJust $ B.elemIndex 'Z' $ B.reverse s)
  print $ e-b


Measured memory_bytes: 1020
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

int *tmp;

void msort(int *a,int n){
  if(n<=1) return;
  int m=n/2;
  msort(a,m);
  msort(a+m,n-m);
  int i=0;
  int j=m;
  int k=0;
  while(i<m && j<n){
    if(a[i]<=a[j]){
      tmp[k++]=a[i++];
    } else {
      tmp[k++]=a[j++];
    }
  }
  while(i<m) tmp[k++]=a[i++];
  for(i=0;i<k;i++) a[i]=tmp[i];
  return;
}

void run(void){
  int n;
  scanf("%d",&n);
  int *a=(int *)malloc(sizeof(int)*n);
  int *b=(int *)malloc(sizeof(int)*n);
  int *c=(int *)malloc(sizeof(int)*n);
  int i;
  for(i=0;i<n;i++) scanf("%d",a+i);
  for(i=0;i<n;i++) scanf("%d",b+i);
  for(i=0;i<n;i++) scanf("%d",c+i);
  tmp=(int *)malloc(sizeof(int)*n);
  msort(a,n);
  msort(b,n);
  msort(c,n);
  int64 *cnt=(int64 *)calloc(n,sizeof(int64));
  int j=0;
  for(i=0;i<n;i++){
    while(j<n && b[i]>=c[j]) j++;
    cnt[i]=n-j;
  }
  for(i=n-1;i>0;i--) cnt[i-1]+=cnt[i];
  int64 sum=0;
  j=0;
  for(i=0;i<n;i++){
    while(j<n && a[i]>=b[j]) j++;
    sum+=cnt[j];
  }
  printf("%lld\n",sum);
}

int main(void){
  run();
  return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int n,a[200001];
struct node
{
    int x,v;
}s[200001];
bool judge(int x)
{
    int cnt=0;
    for(int i=2;i<=n;i++)
        if(a[i]<=a[i-1])
        {
            if(x==1) return false;
            while(cnt&&s[cnt-1].x>a[i])
                cnt--;
            int t=a[i];
            while(t>0&&cnt)
            {
                if(t>s[cnt-1].x) break;
                if(t==s[cnt-1].x)
                {
                    s[cnt-1].v++;
                    if(s[cnt-1].v<x) break;
                    else cnt--;
                }
                t--;
            }
            if(t<=0) return false;
            if(cnt==0||t!=s[cnt-1].x)
                s[cnt].x=t,s[cnt++].v=1;
        }
    return true;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int l=1,r=n,ans;
    while(l<=r)
    {
        int m=l+r>>1;
        if(judge(m)) ans=m,r=m-1;
        else l=m+1;
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 1024
import java.util.*;
import java.io.*;
class Main{

	static int count=0; //number of comparisons
	public static void main(String[]args) throws IOException{
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		//Scanner in=new Scanner(System.in);
		PrintWriter out=new PrintWriter(System.out, true);
		int n=Integer.parseInt(in.readLine());
		String str[]=in.readLine().split(" ");
		int a[]=new int[n];
		for(int i=0;i<n;i++)
			a[i]=Integer.parseInt(str[i]);
		merge_sort(a, 0, n-1);
		for(int i=0;i<n;i++){
			if(i==n-1)
				out.printf(a[i]+"\n");
			else
				out.print(a[i]+" ");
		}
		out.println(count);
	}

	public static void merge_sort(int[] arr, int left, int right){
		if(left<right){
			int m=(left+right)/2;

			merge_sort(arr, left, m);
			merge_sort(arr, m+1, right);

			merge(arr, left, m, right);
		}
	}

	public static void merge(int[] arr, int left, int mid, int right){
		int n1=mid-left+1;
		int n2=right-mid;

		int l[]=new int[n1];
		int r[]=new int[n2];

		for(int i=0;i<n1;i++)
			l[i]=arr[left+i];
		for(int j=0;j<n2;j++)
			r[j]=arr[mid+1+j];

		int i=0, j=0;
		
		int k=left;

		while(i<n1 && j<n2){
			if(l[i]<=r[j]){
				arr[k]=l[i];
				i++;
			}else{
				arr[k]=r[j];
				j++;
			}
			k++;
			count++;
		}

		while(i<n1){
			arr[k]=l[i];
			i++;
			k++;
			count++;
		}
		while(j<n2){
			arr[k]=r[j];
			j++;
			k++;
			count++;
		}
	}
}


Measured memory_bytes: 160352
#include <bits/stdc++.h>
#define foi(i,k,n) for(int i = (int)k; i < (int)n; ++i)
using namespace std;
using ll = long long;
using ii = pair<int,int>;

constexpr int MAXN = 5 + 1e5;

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  ll a,p,q;
  scanf("%lld", &a);
  scanf("%lld.%lld", &p, &q);
  p = p*100+q;
  cout << (a*p)/100 << '\n';
  return 0;
}


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

int main() {
    int x;
    cin >> x;
    if(x == 0) cout << 1 << endl;
    else cout << 0 << endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

int dfs(int i, vector<vector<int>> &g, vector<int> &vis, vector<int> &cc)
{
    vis[i] = true;
    cc.push_back(i);

    int sum = 0;
    for (size_t j = 0; j < g[i].size(); ++j) {
        if (!vis[g[i][j]]) {
            sum += dfs(g[i][j], g, vis, cc);
        }
    }
    return sum + 1;
}

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

    int N, K, L;
    cin >> N >> K >> L;

    vector<vector<int>> road(N), rail(N);
    for (int i = 0; i < K; ++i) {
        int p, q;
        cin >> p >> q;
        road[p-1].push_back(q-1);
        road[q-1].push_back(p-1);
    }
    for (int i = 0; i < L; ++i) {
        int r, s;
        cin >> r >> s;
        rail[r-1].push_back(s-1);
        rail[s-1].push_back(r-1);
    }

    vector<int> vis(N, 0), res(N, -1);
    vector<vector<int>> cc1;
    vector<int> cc1val;
    map<int, int> mcc1, mcc2;
    for (int i = 0; i < N; ++i) {
        if (!vis[i]) {
            cc1.push_back(vector<int>());
            cc1val.push_back(dfs(i, road, vis, cc1[cc1.size()-1]));
            int x = cc1.size() - 1;
            for (size_t j = 0; j < cc1[x].size(); ++j) {
                mcc1[cc1[x][j]] = x;
            }
            sort(cc1[x].begin(), cc1[x].end());
        }
    }

    vis.assign(N, 0);
    vector<vector<int>> cc2;
    vector<int> cc2val;
    for (int i = 0; i < N; ++i) {
        if (!vis[i]) {
            cc2.push_back(vector<int>());
            cc2val.push_back(dfs(i, rail, vis, cc2[cc2.size()-1]));
            int x = cc2.size() - 1;
            for (size_t j = 0; j < cc2[x].size(); ++j) {
                mcc2[cc2[x][j]] = x;
            }
            sort(cc2[x].begin(), cc2[x].end());
        }
    }

    for (int i = 0; i < N; ++i) {
        if (cc1val[mcc1[i]] == 1) {
            res[i] = 1;
        }
    }
    for (int i = 0; i < N; ++i) {
        if (cc2val[mcc2[i]] == 1) {
            res[i] = 1;
        }
    }

    for (int i = 0; i < N; ++i) {
        if (res[i] == -1) {
            vector<int> intersection;
            set_intersection(cc1[mcc1[i]].begin(), cc1[mcc1[i]].end(),
                             cc2[mcc2[i]].begin(), cc2[mcc2[i]].end(),
                             back_inserter(intersection));
            for (size_t j = 0; j < intersection.size(); ++j) {
                res[intersection[j]] = intersection.size();
            }
            if (res[i] == -1) {
                res[i] = 1;
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        cout << res[i] << " ";
    }

    return 0;
}

Measured memory_bytes: 53676
using System;
using System.Collections.Generic;
using System.Linq;

namespace CSharpSample01
{


	class Program
	{
		static void Main(string[] args)
		{
			// スペース区切りの整数の入力
			var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
			var N = input[0];
			var K = input[1];

			var numInput = Console.ReadLine().Split(' ').Select(double.Parse).ToArray();
			var answerList = new List<double>();

			int sum = 0;
			double answer = 0.0;

			for (int i = 0; i < N; i++)
			{
				sum = 0;
				answer = 0.0;

				for (int x = 1; x <= numInput[i]; x++)
				{
					sum += x;
				}
				double test = sum / numInput[i];
				answerList.Add(test);
			}

			double maxValue = 0.0;
			double sumValue = 0.0;
			var count = 0;

			for (int i = 0; i < N; i++)
			{
				if(count >= K)
				{
					sumValue -= answerList[i - K];
				}
				sumValue += answerList[i];

				if(maxValue < sumValue)
				{
					maxValue = sumValue;
				}

				count++;
			}

			Console.WriteLine(maxValue);
		}


	}
}

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

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define rep(i,a,b) for(i=a;i<b;i++)
#define pii pair<ll , ll>
#define all(x) x.begin(),x.end()
#define nl "\n"
#define ump unordered_map
#define mtv(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)

vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out( 
	vector<string> __attribute__ ((unused)) args,
	__attribute__ ((unused)) int idx, 
	__attribute__ ((unused)) int LINE_NUM) { cout << endl; } 
	template <typename Head, typename... Tail>
	void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    stringstream ss; ss << H;
    cout << args[idx] << "- " << ss.str() << ", ";
    debug_out(args, idx + 1, LINE_NUM, T...);
}


const ll N = 3005;
ll grid[N][N],dp[N][N][7];
ll R,C;

ll fun(ll row, ll col, ll cur){
	if(row == R-1 and col == C-1){
		return (cur==3)?0:grid[row][col];
	}
	if(row == R || col == C)return INT_MIN;
	ll ans = 0;
	if(dp[row][col][cur] != -1)return dp[row][col][cur];
	ans = max(fun(row+1,col,0),fun(row,col+1,cur));
	if(cur < 3){
		ans = max({ans, grid[row][col] + fun(row,col+1,cur+1),grid[row][col] + fun(row+1,col,0)});
	}
	return dp[row][col][cur] = ans;
}

void doit(){
	ll n, i, x, y, k;
	cin >> R >> C >> n;
	rep(i,0,n){
		cin >> x >> y >> k;
		grid[x-1][y-1] = k; 
	}
	memset(dp,-1,sizeof(dp));
	cout << fun(0,0,0) << nl;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    // cin >> t;
    for(ll i = 1; i <= t; i++){
        doit();
    }
}


Measured memory_bytes: 568292
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vb=vector<bool>;
using vvb=vector<vb>;
using vc=vector<char>;
using vvc=vector<vc>;
using pii = pair<int,int>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;
using tiii = tuple<int,int,int>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define rep(i, n) for(int i=0;i<(int)n;i++)
#define rep2(i, s, n) for(int i=(s);i<(int)n;i++)
int INF=1e9+7;

int main() {
  int N;
  cin >> N;
  vi A(N);
  rep(i,N) cin >> A[i];
  
  ll ans=0;
  rep(i,N-1) {
    ans+=max(0,A[i]-A[i+1]);
    A[i+1]+=max(0,A[i]-A[i+1]);
  }
  
  cout << ans << endl;
}

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

if n < 10:
    ans = n
elif 10 <= n and n < 100:
    ans = 9
elif 100 <= n and n < 1000:
    ans = 9 + n - 99
elif 1000 <= n and n < 10000:
    ans = 909
elif 10000 <= n and n < 100000:
    ans = 909 + n - 9999
elif n == 100000:
    ans = 90909

print(ans)


Measured memory_bytes: 2940
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include <queue>
#include<cstdio>
#include<algorithm>
#define ls (o << 1)
#define rs (o << 1 | 1)
#define mid ((L + R) >> 1)
using namespace std;
long long n;
int main(){
    while(scanf("%lld",&n) == 1 && n){
        long long ans = n;
        long long tmp = 1;
        for(long long i = 1; i * i <= n * 2; ++i){
            if(n * 2 % i) continue;
            long long ave2 = i;
            long long num = n * 2 / ave2;
            if(i % 2 == 0 && num % 2 == 0) continue;
            //cout << ave2 <<" " <<num << endl;
            long long low = ave2 / 2 - (num + 1) / 2 + 1;
            //cout << low << endl;
            if(low > 0) ans = min(ans, low), tmp = num;
            swap(ave2, num);
            //cout << ave2 <<" " <<num << endl;
            low = ave2 / 2 - (num + 1) / 2 + 1;
            if(low > 0) ans = min(ans, low), tmp = num;
            //cout << low << endl;
        }
        cout << ans <<" "<< tmp << endl;
    }
    return 0;
}



Measured memory_bytes: 3160
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N;
  cin >> N;
  ll ans = 0;
  rep(l,N) {
    ans += ll(l+1)*(N-l);
  }
  rep(i,N-1) {
    int a,b;
    cin >> a >> b;
    a--;b--;
    if(a>b) swap(a,b);
    ans -= ll(a+1)*(N-b);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3628
N = int(input())
c = list(input())
r = c.count("R")
w = c.count("W")
true = []
true += ["R"]*r
true += ["W"]*w
count = 0
for num in range(N):
  if true[num] != c[num]:
    count += 1
print(int(count/2))

Measured memory_bytes: 13584
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n = int(readline())
    a = [int(i) for i in readline().split()]
    j = 1
    for i in a:
        if i == j:
            j += 1
    if j-1 == 0:
        print(-1)
        return
    print(n-(j-1))
if __name__ == '__main__':
    main()


Measured memory_bytes: 20372
function main()
  
  (N,M,X) = map(x -> parse(Int,x), split(readline()))
  A = map(x -> parse(Int,x), split(readline()))
  
  ans1 = 0
  
  for i in X:N
    if in(i,A)
      ans1 += 1
    end
  end
  
  ans2 = 0
  
  for i in X:-1:0
     if in(i,A)
      ans2 += 1
    end
  end
  
  println(min(ans1,ans2))
  
end

main()

Measured memory_bytes: 166940
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<pair<string, int>> rest(N);
    int num[N];
    for (int i = 0; i < N; i++)
    {
        cin >> rest[i].first >> rest[i].second;
        num[i] = i; 
    }
    for (int i = 0; i < N-1; i++)
    {
        for (int j = i+1; j < N; j++)
        {
            if (rest[j].first < rest[i].first)
            {
                pair<string, int> tmp;
                tmp = rest[j];
                rest[j] = rest[i];
                rest[i] = tmp;
                int tmpNum = num[j];
                num[j] = num[i];
                num[i] = tmpNum;
            } else if (rest[j].first == rest[i].first) {
                if (rest[i].second < rest[j].second)
                {
                    pair<string, int> tmp;
                    tmp = rest[j];
                    rest[j] = rest[i];
                    rest[i] = tmp;
                    int tmpNum = num[j];
                    num[j] = num[i];
                    num[i] = tmpNum;
                }
            }
            
        }
        
    }
    
    for (int i = 0; i < N; i++)
    {
        cout << num[i]+1 << endl;
    }
    
    return 0;
}

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

int main(){
  long N, H;
  cin >> N >> H;
  vector<long> A(N);
  vector<long> B(N);
  for(long i=0; i<N; i++){
    cin >> A[i] >> B[i];
  }
  sort(A.begin(),A.end(), greater<int>());
  sort(B.begin(),B.end(), greater<int>());
  long count=0;
  for(int i=0; i<B.size(); i++){
    if(B[i]<=A[0]) break;
    if(H<=B[i]){
      H=0;
      count++; break;
    }
    H-=B[i];
    count++;
  }
  count+=ceil((double)H/A[0]);
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main(){
  int n,t;
  int cost,time;
  int min;
  bool jud = false;
  
  cin >> n >> t;
  
  for(int i=0; i < n ; i++){
    cin >> cost >> time;
    if(i == 0) min = cost;
    
    if(time <= t){
      jud = true;
      if(cost < min) min = cost;
    }
  }
  
  if(jud) cout << min << endl;
  else cout << "TLE" << endl;
  return 0;
}

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

int main(){
	string str,tmp;
	int sum;
	while(1){
		sum = 0;
		cin >> str;
		if( str == "0") break;
		for(int i = 0; i < str.size(); i++){
			tmp = str[i];
			sum += stoi(tmp);
		}
		cout << sum << endl;
	}
	return 0;
}	

Measured memory_bytes: 3132
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>

#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define FOR(i,a,b) for(int i = a;i < b;i++)
#define MEM(a,b) memset(a,b,sizeof(a))
#define ALL(x) (x).begin(),(x).end()
#define LMAX 9223372036854775807
#define LMIN -9223372036854775808

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ull, ull> UP;

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) {}
	void unionSet(int x, int y) {
		x = root(x), y = root(y);
		if (x != y) {
			if (data[y] < data[x])swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	int k = a % b;
	if (k == 1)return 1;
	if (k == 0)return b;
	int ans = gcd(b, k);
	return ans;
}
ll digisum(ll a) {
	int sum = 0;
	while (a) {
		sum += a % 10;
		a /= 10;
	}
	return sum;
}
ll countpow(ll a, ll b) {
	int ans = 0;
	if (b == 0)return -1;
	while (1) {
		if (a % b == 0) {
			a /= b;
			ans++;
		}
		else break;
	}
	return ans;
}
int to_num(char c) {
	if (c >= '0' && c <= '9')return (c - '0');
	else return -1;
}


int main() {
	IOS;
	int cnt = 1;
	int n;
	cin >> n;
	int min, max;
	int is_inc = 0;
	vector<int> v(n);
	REP(i, n)cin >> v[i];
	int prev = v[0], unko = 0;
	FOR(i, 1, n) {
		if (unko == 0 && v[i] > prev)unko = 1;
		else if (unko == 0 && v[i] < prev)unko = 2;
		if (unko == 1 && v[i] < prev) {
			cnt++;
			unko = 0;
		}
		if (unko == 2 && v[i] > prev) {
			cnt++;
			unko = 0;
		}
		prev = v[i];
	}
	cout << cnt << endl;
}



Measured memory_bytes: 640
#include<bits/stdc++.h>
#define YOU setprecision
using namespace std;
int i[11111111];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b,c,d=0,e,f;
  string s;
  cin >>a>>b>>c>>d;
  cout <<(a-c)*(b-d)<<'\n';
  return (0);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;
using Graph = vector<vector<ll>>;
const ll INF = 1LL << 60;
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}
#define tl 1'000'000'007
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REREP(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, a, n) for (ll i = a; i < n; i++)
#define REFOR(i, n, a) for (ll i = n; i >= a; i--)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) //被り削除
#define debug cout << 
int gcd(long long a, long long b) { return b != 0 ? gcd(b, a % b) : a; }
ll factorial(ll n){
   ll ans = 1;
   for(int i = n;i>=1;i--){
     ans *= i;
     ans %= tl;
   }
   return ans;
}
vector<string> split(string str, char del) {
    int first = 0;
    int last = str.find_first_of(del);
 
    vector<string> result;
 
    while (first < str.size()) {
        string subStr(str, first, last - first);
 
        result.push_back(subStr);
 
        first = last + 1;
        last = str.find_first_of(del, first);
 
        if (last == string::npos) {
            last = str.size();
        }
    }
 
    return result;
}
ll calcStr(string s){
    char del = '+';
    ll sum=0;
    for (const auto x : split(s, del)) {
        sum+= stol(x); 
    }
    return sum;
}

//-----------------------------------
int main(){
    init();
    string s;
    cin >> s;
    ll ans= 0;
    ll n= s.size()-1;
    for(int i=0; i<(1<<n); i++){
        // cout << i << 
        ll x=s[0]-'0';
        for(int j=0; j<n; j++){  
            if(i & (1<<j)){ // j が i に入るかどうか
                ans+= x;
                x=0;
            }else{
                x*=10;
            }
            x+= s[j+1]-'0';
        }
        ans+= x;
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;

template<class T>bool chmax(T &a, const T &b) { if( a < b ) { a = b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) { if( b < a ) { a = b; return 1; } return 0;}

#ifdef LOCAL
	#define eprintf(...) printf(__VA_ARGS__)
#else
	#define eprintf(...) 1
#endif

#define ROUNDUP(a, b) 		( ((a) + ((b) - 1) ) / b)
#define SET_ZERO(a)	 		( memset((a), 0, sizeof(a)))
#define SET_NUM_ARRAY(a,b)	( memset((a), b, sizeof(a)))
//#define int long long int //dont forget to change int to signed

const int BIGINT = 1000000007;

int main() {
	int N;
	scanf("%d", &N);
	int a[1009]; SET_ZERO(a);
	for (int i = 2; i <= N; i++) {
		if (a[i] == 0) {
			for (int j = 2; i*j <= N; j++) {
				a[i*j] = 1;
			}
		}
	}
	int b[1009]; SET_ZERO(b);
	for (int i = 2; i <= N; i++) {
		for (int j = 2; j <= i; j++) {
			if (!a[j]) {
				for (int k = i; k >= j && k%j == 0; k/=j) {
					++b[j];
					eprintf("b %d\n", j);
				}
			}
		}
	}

	lli ans = 1;
	for (int i = 2; i <= N; i++) {
		if (b[i] > 0) {
			eprintf("l %d\n", i);
			ans = (ans * (b[i]%BIGINT+1))%BIGINT;
		}
	}
	printf("%lld \n", ans);
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;


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

	int L, R;
	cin >> L >> R;
	int d = R - L;
	int res;
	const int mod = 2019;
	if (d >= mod - 1) res = 0;
	else{
		res = mod;
		FOR(i, L, R) {
			FOR(j, i + 1, R + 1) {
				res = min(res, ((i%mod) * (j%mod)) % mod);
			}
		}
	}
	cout << res << endl;

	return 0;
}


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

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) for(int i = 0; i < (n); ++i)
#define RREP(i, n) for(int i = (n) - 1; i >= 0; --i)
#define ALL(a) begin(a), end(a)

using ll = long long;
using namespace std;

constexpr int INF = 2147483647; // 2 * 1e9
constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

vector<int> e[50];
bool flg[50];

void dfs(int now){
	flg[now] = true;
	for(int &to : e[now]){
		if(flg[to]) continue;
		else{
			dfs(to);
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	int ans = 0;
	cin >> n >> m;
	REP(i, m){
		int a, b;
		cin >> a >> b;
		a--; b--;
		e[a].push_back(b);
		e[b].push_back(a);
	}
//cout << "DEBUG\n";
	REP(i, n){
		for(int j = 0; j < e[i].size(); ++j){
			
			REP(k, n) flg[k] = false;
			int t = e[i].front();
			//cout << i << " " << t << "\n";
			e[i].erase(e[i].begin());
			dfs(0);
			REP(k, n){
				if(!flg[k]){
					ans++;
					break;
				}
			}
			e[i].push_back(t);
		}
	}
	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 256
S = input()
if S == "SUN":
	print(7)
elif S == "SAT":
	print(1)
elif S == "FRI":
	print(2)
elif S == "THU":
	print(3)
elif S == "WED":
	print(4)
elif S == "TUE":
	print(5)
elif S == "MON":
	print(6)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int k; cin >> k;
  if (k == 1) {
    cout << "1\n1\n";
    return 0;
  }
  int n = (k + 3) / 4 * 2;
  VV<> res;
  assign(res, n, n, 0);
  for (int i = 0; i < n; ++i) {
    fill(begin(res[i]), end(res[i]), i);
  }
  for (int i = n; i < k; ++i) {
    for (int j = 1; j < n; j += 2) {
      res[i - n][j] = i;
    }
  }
  cout << n << '\n';
  for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
    cout << res[(i + j) % n][j] + 1 << (j != n - 1 ? ' ' : '\n');
  }
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
#define pb push_back
#define ff first 
#define ss second  
typedef pair<ll,ll> pp;
bool com(pp x,pp y){
    return x.ff<y.ff;
} 

void solve(){
    int n;
    cin>>n;
    int a[n];
    ll ans=0;
    vector<int> d(1e6+7,0);
    for(int i=0;i<n;i++){
        cin>>a[i];
        d[a[i]]++;
    }
    for(int i=0;i<n;i++){
        int x=a[i],y=0;
        for(int j=2;j*j<=x;j++){
            if(x%j==0){
                if(d[x/j]||d[j]){
                    y++;
                    break;
                }
            }
        }
        if(d[x]>1||(d[1]&&x!=1)) y++; 
        if(y) continue;
        ans++;
    }
    cout<<ans;
}
int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0; 
	
}


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

int main(){
  int N,K,X,Y;
  cin>>N>>K>>X>>Y;
  if (N>=K){
  cout<<K*X+(N-K)*Y<<endl;
  } else{
    cout << N*X << endl;
  }
  return 0;
}


Measured memory_bytes: 256