akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <set>

using namespace std;

#define W_MAX 1001

int H, W, A, B;

void print(int x,int y)
{
	int count[W_MAX];
	fill(count, count + W_MAX, 0);

	for (int i = 0; i < x; i++){
		int cnt = 0;
		for (int j = 0; j < y; j++){
			if (cnt >= A){
				printf("1");
				continue;
			}
			if (count[j] < B){
				count[j]++;
				cnt++;
				printf("0");
			}
			else{
				printf("1");
			}
		}
		for (int j = y; j < W; j++){
			if (cnt >= A){
				printf("1");
				continue;
			}
			if (count[j] < (H-B)){
				count[j]++;
				cnt++;
				printf("0");
			}
			else{
				printf("1");
			}
		}
		printf("\n");
	}
	for (int i = x; i < H; i++){
		int cnt = 0;
		for (int j = 0; j < y; j++){
			if (cnt >= (W-A)){
				printf("1");
				continue;
			}
			if (count[j] < B){
				count[j]++;
				cnt++;
				printf("0");
			}
			else{
				printf("1");
			}
		}
		for (int j = y; j < W; j++){
			if (cnt >= (W-A)){
				printf("1");
				continue;
			}
			if (count[j] < (H - B)){
				count[j]++;
				cnt++;
				printf("0");
			}
			else{
				printf("1");
			}
		}
		printf("\n");
	}

	return;
}

void solv()
{
	scanf("%d%d%d%d", &H, &W, &A, &B);

	for (int i = 0; i*2 <= H; i++){
		for (int j = 0; j*2 <= W; j++){
			if (A*i + (W - A)*(H - i) == B*j + (H - B)*(W - j)){
				print(i,j);
				return;
			}
		}
	}

	printf("No");

	return;
}

int main()
{
	FILE *fin = NULL, *fout = NULL;
	//fin = freopen("input.txt", "r", stdin);
	//fout = freopen("output.txt", "w", stdout);

	solv();

	//finalize
	if (NULL != fin) fclose(fin);
	if (NULL != fout) fclose(fout);

	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>

typedef long long ll;
const ll LL_MAX (1LL<<60);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

int main()
{
    ll x1[2], x2[2], x3[2], x4[2];

    cin >> x1[0] >> x1[1] >> x2[0] >> x2[1];

    ll diff_x = x2[0] - x1[0];
    ll diff_y = x2[1] - x1[1];

    x3[0] = x2[0] - diff_y;
    x3[1] = x2[1] + diff_x;

    x4[0] = x1[0] - diff_y;
    x4[1] = x1[1] + diff_x;
    
    
    cout << x3[0] << ' ' << x3[1] << ' ' << x4[0] << ' ' << x4[1] << endl;  

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std;

int main() {
  
  int a,b,c,d,x;
  string s,ss,sss;
  
  int ans = 0;
  string anss = "";
  
  cin >> a >> b;
  
  int ab [] = {0 , 1 , 3 , 1 , 2 , 1 , 2 , 1 , 1 , 2 , 1 , 2 , 1};
  int result3 = std::max({a, b, c});
//--------------------------------------------------------------------------------

//  if(a/10 == 9 || a%10 == 9) anss = "Yes";
//  else anss = "No";
  
  cout << a*a-b << endl;

}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
  val n = readLine()!!.toInt()
  val a = readLine()!!.split(' ').map(String::toInt)
  val b = LongArray(n)
  a.forEach { b[it - 1]++ }
  val c = b.map { it * (it - 1) / 2 }
  val s = c.sum()
  a.forEach {
    val i = it - 1
    val t = (b[i] - 1) * (b[i] - 2) / 2
    println(s - c[i] + t)
  }
}


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

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

int main(){
  int a,b;
  cin>>a>>b;
  cout<<max({a+b,a-b,a*b})<<endl;



  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, begin, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    int A, B, K;
    cin >> A >> B >> K;
    int min;
    if (A > B)
    {
        min = B;
    }
    else
    {
        min = A;
    }
    int count = 0;
    int div = min;
    while (count != K)
    {
        if ((A % div == 0) && (B % div == 0))
        {
            count++;
            if (count == K)
            {
                break;
            }
        }
        div--;
    }
    cout << div << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 4010
int n, a[MAXN], c[MAXN], f[MAXN][MAXN], p[2][MAXN];
int g[2][MAXN][MAXN], h[2][MAXN][MAXN];
char buf[3];
inline void up(int &x, int y) {
	if (y < x) x = y;
}
int main() {
	scanf("%d", &n);
	n <<= 1;
	for (int i = 1; i <= n; i++) {
		scanf("%s%d", buf, a + i);
		p[c[i] = buf[0] == 'B'][a[i]] = i;
	}
	for (int j = 0; j < 2; j++) {
		for (int i = 1; i <= n; i++) {
			for (int k = 1; k <= n; k++) {
				g[j][i][k] = g[j][i - 1][k] + (a[i] == k && c[i] == j);
			}
		}
	}
	for (int j = 0; j < 2; j++) {
		for (int i = 1; i <= n; i++) {
			for (int k = n; k >= 1; k--) {
				g[j][i][k] += g[j][i][k + 1];
			}
		}
	}
	for (int j = 0; j < 2; j++) {
		for (int i = n; i >= 1; i--) {
			for (int k = 1; k <= n; k++) {
				h[j][i][k] = h[j][i][k - 1];
			}
		}
	}
	memset(f, 0x3F, sizeof(f));
	f[0][0] = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k < 2; k++) {
				int pos = p[k][(k ? j : i) + 1];
				int cost = 0;
				cost += g[0][pos - 1][i + 1];
				cost += g[1][pos - 1][j + 1];
				cost += h[0][pos + 1][i - 1];
				cost += h[1][pos + 1][j - 1];
				up(f[i + !k][j + k], f[i][j] + cost);
			}
		}
	}
	printf("%d\n", f[n][n]);
	return 0;
}

Measured memory_bytes: 314240
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    long mod = 1000000009;
    static void Main(string[] args)
    {
        Console.WriteLine(Read.Int()/3);   }
    public static long gcd(long a, long b)
    {
        while (true)
        {
            if (a == 0) { return b; }
            if (b == 0) { return a; }
            if (a > b) { a -= b; }
            else { b -= a; }
        }
    }
    public static long lcm(long a, long b) { return a / gcd(a, b) * b; }
    public static bool IsPrime(int num)
    {
        if (num < 2) return false;
        else if (num == 2) return true;
        else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

        double sqrtNum = Math.Sqrt(num);
        for (int i = 3; i <= sqrtNum; i += 2)
        {
            if (num % i == 0)
            {
                // 素数ではない
                return false;
            }
        }

        // 素数である
        return true;
    }
}
public static class Read
{
    public static void outl(string n = "") { Console.WriteLine(n); return; }
    public static long Long() { return long.Parse(Console.ReadLine()); }
    public static long[] longs() { return Console.ReadLine().Split().Select(long.Parse).ToArray(); }
    public static int Int() { return int.Parse(Console.ReadLine()); }
    public static int[] ints() { return Console.ReadLine().Split().Select(int.Parse).ToArray(); }
    public static string Str() { return Console.ReadLine(); }
    public static string[] Strs() { return Console.ReadLine().Split(); }
}

Measured memory_bytes: 13140
#include<iostream>
using namespace std;
int main() {
    int a,b;
    char op;
    while(1 == 1) {
        cin >> a >> op >> b;
        if(op == '?')break;
        else if(op == '+')cout << a + b << endl;
        else if(op == '-')cout << a - b << endl;
        else if(op == '*')cout << a * b << endl;
        else if(op == '/')cout << a / b << endl;
    }
    return 0;
}


Measured memory_bytes: 3096
#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 d;
    cin >> d;
    vector<int> c(26);
    rep(i, 26) cin >> c[i];
    vector<vector<int>> s(d, vector<int>(26));
    rep(i, d) {
        rep(j, 26) {
            cin >> s[i][j];
        }
    }
    vector<int> t(d);
    rep(i, d) {
        int s_max = 0;
        rep(j, 26) {
            if (s_max < s[i][j]) {
                s_max = s[i][j];
                t[i] = j+1;
            }
        }
        
    }
    rep(i, d) {
        cout << (i+2)%26+1 << endl;
    }
    return 0;
}

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

class Team
{
public:
  int tID, solved, penalty;
  Team(int _tID, int _solved, int _penalty)
    :tID(_tID), solved(_solved), penalty(_penalty) {}
  bool operator <(const Team& obj) const
  {
    if (this->solved == obj.solved) {
      if (this->penalty == obj.penalty)
	return this->tID < obj.tID;
      return this->penalty < obj.penalty;
    }
    return this->solved > obj.solved;
  }
};

int main()
{
  int T, P, R;
  while (cin >> T >> P >> R) {
    if ((T|P|R) == 0)
      break;

    vector<Team> team;
    for (int i = 0; i < T; ++i)
      team.push_back(Team(i, 0, 0));

    vector<vector<int> > log(T, vector<int>(P, 0));
    for (int i = 0; i < R; ++i) {
      int tID, pID, time;
      string message;
      cin >> tID >> pID >> time >> message;
      --tID;
      --pID;
      if (log[tID][pID] == -1)
	continue;

      if (message == "WRONG") {
	++log[tID][pID];
      } else {
	++team[tID].solved;
	team[tID].penalty += time + log[tID][pID]*1200;
	log[tID][pID] = -1;
      }
    }
    sort(team.begin(), team.end());

    for (int i = 0; i < T; ++i)
      cout << team[i].tID+1 << " " << team[i].solved << " " << team[i].penalty << endl;
  }
  return 0;
}

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

const int MAX_N=1e5;

int N;
int A[MAX_N+1];
int X;

int main(){
	cin>>N>>X;
	A[0]=0;
	FOR(i,1,N+1){
		cin>>A[i];
	}
	ll ans=0;
	FOR(i,1,N+1){
		int a=A[i-1]+A[i]-X;
		if (a>0){
			ans+=a;
			A[i]-=a;
		}
	}
	cout<<ans<<endl;
	return 0;
}


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N, M;

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

  std::cin >> N >> M;

  int res = 0;
  res += N * (N - 1) / 2;
  res += M * (M - 1) / 2;

  std::cout << res << std::endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
const int md=998244353;
int n,i,d[100005],c[100005],ans=1;
int pw(int a,int b)
{
	int rtn=1;
	while(b)
	{
		if(b&1)
			rtn=1ll*rtn*a%md;
		a=1ll*a*a%md;
		b>>=1;
	}
	return rtn;
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d",d+i);
	if(d[1]!=0)
	{
		printf("0");
		return 0;
	}
	if(n==1)
	{
		printf("1");
		return 0;
	}
	sort(d+1,d+1+n);
	if(d[2]==0)
	{
		printf("0");
		return 0;
	}
	for(i=1;i<=n;++i)
		c[d[i]]++;
	for(i=1;i<n;++i)
		if(c[i])
			ans=1ll*ans*pw(c[i-1],c[i])%md;
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i = 0; i < n; i++)
typedef long long ll;
// Welcome to my source code!

int lcs(string x, string y) {
    int m = x.size();
    int n = y.size();
    int c[m+1][n+1] = {};
    int maxv = 0;
    x = ' ' + x;
    y = ' ' + y;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[i] == y[j]) {
                c[i][j] = c[i-1][j-1] + 1;
            } else {
                c[i][j] = max(c[i-1][j], c[i][j-1]);
            }
            maxv = max(maxv, c[i][j]);
        }
    }
    return maxv;
}

int main() {
    int q;
    string x, y;
    cin >> q;
    REP(i,q) {
        cin >> x >> y;
        cout << lcs(x,y) << endl;
    }
}


Measured memory_bytes: 7080
#include"bits/stdc++.h"

using namespace std;

int main() {
	char s[100];
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		cin >> s[i];
		if (s[i] == '+') {
			cnt++;
		}
		else {
			cnt--;
		}
	}

	cout << cnt << endl;

	return 0;	
}

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

#define ed cout << "\n";
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long
#define ffor(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(i, n) ffor(i, 0, n)
#define All(obj) (obj).begin(), (obj).end()
#define INF ((ll)1e9 + 7)
#define c(a) cout << a << "\n";
using namespace std;
const int N = 100005;

int main()
{
    speed;
    cout << fixed << setprecision(6);
    /*start*/
    int x, y, z;
    cin >> x >> y >> z;
    cout << z << " " << x << " " << y;
    return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define leadinz zero str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
string text="abcdefghijklmnopqrstuvwxyz";
const int maxn=1e6+7;
//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'
ll bin_pow(ll a,ll b)
{
    ll res=1;
    while(b>0){
        if(b&1)res=res*a;
        b>>=1;
        a=a*a;
    }
    return res;
}
bool miller_rabin(ll d,ll n)
{
    ll a=2+rand()%(n-4);
    ll x=bin_pow(a,d);
    if(x==1 || x==n-1)return true;
    while(d!=n-1){
        x=(x*x)%n;
        d*=2;
        if(x==1)return false;
        if(x==n-1)return true;
    }
    return false;
}
bool prime(ll n,ll k)
{
    if(n==1 || n==4)return false;
    if(n<=3)return true;
    ll d=n-1;
    while(d%2==0)d/=2;
    for(int i=0;i<k;i++){
        if(!miller_rabin(d,n))return false;
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    vector<ll>v;
    ll res=n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            while(n%i==0)n/=i;
            v.push_back(i);
        }
    }
    if(n>1)v.push_back(n);
    n=res;
    ll ans=0;
    for(auto x: v){
        ll cnt=1;
        while(n%bin_pow(x,cnt)==0){
            n/=bin_pow(x,cnt);
            ans++;
            cnt++;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3644
#include<iostream>
using namespace std;
int main(){
	int n,r,p,c;
	int t[1000],a[1000],b[1000];
	while(cin>>n>>r,n||r){
		for(int i=0;i<n;i++)
		t[i]=n-i;
		for(int i=0;i<r;i++){
			cin>>p>>c;
			for(int j=0;j<p-1;j++)
			a[j]=t[j];
			for(int j=0;j<c;j++)
			b[j]=t[j+p-1];
			for(int j=0;j<c;j++)
			t[j]=b[j];
			for(int j=0;j<p-1;j++)
			t[j+c]=a[j];
		}
		cout<<t[0]<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
from sys import stdin,stdout
def fn(pos,res,k):
    if pos==n:return (k==0)
    ans=0
    if (pos,res,k) in dp:return dp[pos,res,k]
    cur=ord(s[pos])-48
    if res:
        for d in range(cur+1):
            if d==0:ans+=fn(pos+1,d==cur,k)
            elif d!=0 and k>0:ans+=fn(pos+1,d==cur,k-1)
    else:
        for d in range(10):
            if d == 0:ans += fn(pos + 1,0, k)
            elif d != 0 and k > 0:ans += fn(pos + 1,0, k - 1)
    dp[pos,res,k]=ans
    return ans

#a,b=map(int,stdin.readline().split())
s=input()
n=len(s)
k1=int(stdin.readline())
dp={}
ans=0
for d in range(10):
    if d+48<=ord(s[0]):
        ans+=fn(1,(d==ord(s[0])-48),(k1-(d!=0)))
print(ans)

Measured memory_bytes: 9140
using System;
using System.Linq;

class AtCoder {
  public static void Main() {
    var inputs = Console.ReadLine().Trim().Split().Select(x => int.Parse(x)).ToList();
    var N = inputs[0];
    var R = inputs[1];
    var ans = R;
    if(N < 10) {
      ans += 100 * (10 - N);
    }
    Console.WriteLine(ans);
  }
}

Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
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; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;
void swap(ll *x,ll *y){
  ll tmp;
  tmp = *x;
  *x = *y;
  *y = tmp;
}

int main(){
  string s;
  cin >> s;
  ull n = s.size();
  rep(i,n){
    s[i] = 'x';
  }
  cout << s << endl;
}

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

int main() {
	int a, b;
	cin >> a >> b;
	if(a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0){
		cout << "Possible" << endl;
	}else{
		cout << "Impossible" << endl;
	}
	
 	return 0;
}



Measured memory_bytes: 256
def cin
  gets.split.map(&:to_i)
end

n, k = cin
p = cin.map { |pi| (pi + 1).to_f / 2 }

max = sum = p[0...k].inject(:+)

(k...n).each do |i|
  sum += p[i] - p[i - k]
  max = sum if sum > max
end

puts max

Measured memory_bytes: 16516
#include <bits/stdc++.h>
#define ll long long

using namespace std;
 main()
{
        string s,t;
        int ans=0;
        cin>>s>>t;
        for(int i=0; i<3; i++)if(s[i]!=t[i])ans++;
        cout<<3-ans<<endl;







    return 0;
}


Measured memory_bytes: 256
w, h, n = gets.split.map(&:to_i)
f = h.times.map{Array.new(w, true)}
n.times{
  x, y, a = gets.split.map(&:to_i)
  case a
  when 1 then
    d = Array.new(x, false)
    h.times{|i| f[i][0...x] = d}
  when 2 then
    d = Array.new(w-x, false)
    h.times{|i| f[i][x...w] = d}
  when 3 then
    d = Array.new(w, false)
    (0...y).each{|i| f[i] = d}
  when 4 then
    d = Array.new(w, false)
    (y...h).each{|i| f[i] = d}
  end
}
puts f.map{|d|d.count{|i|i}}.reduce(:+)


Measured memory_bytes: 1916
import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

X = inp()
yen = 100
for i in range(10**4):
    yen += (yen // 100)
    if yen >= X:
        print(i+1)
        break

# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)

Measured memory_bytes: 9188
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_E main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 10;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif

vvi es;
vvi games;

int get_game_id(int i, int j) {
    if (i > j) swap(i,j);
    return games[i][j];
}

vb vis;
vb done;
vi dp;
int M;
int dfs(int n) {
    if (n >= M) return -1;
    // Found a cycle
    if (vis[n]) {
        if (!done[n]) return -1;
        return dp[n];
    }

    vis[n] = true; // visitting
    dp[n] = 1; // day 1

    for (int i : es[n]) {
        int res = dfs(i);
        if (res == -1) return -1;

        dp[n] = max(dp[n], res + 1);
    }

    done[n] = true; // visited

    return dp[n];
}


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

    int N; cin >> N;
    vvi A(N, vi(N-1));
    REP(i,N) {
        REP(j,N-1) {
            cin >> A[i][j];
            A[i][j]--;
        }
    }

    games = vvi(N, vi(N));
    int gm_id = 0;
    REP(i,N) {
        REP(j,N) {
            if (i < j) {
                games[i][j] = gm_id;
                gm_id++;
            }
        }
    }

    M = gm_id;
    vvi prog(N, vi(N));
    set<pii> st;
    es = vvi(M);
    REP(i,N) {
        REP(j,N-1) {
            prog[i][j] = get_game_id(i, A[i][j]);
        }

        REP(j,N-2) {
            int g1 = prog[i][j];
            int g2 = prog[i][j+1];

            if (st.count(pii(g1, g2)) == 0) st.insert(pii(g1, g2));
            else continue;

            es[g1].push_back(g2);
        }
    }

    int ans = 0;
    vis = vb(M, false);
    done = vb(M,false);
    dp = vi(M, -1);
    // dp[i] := Max path length from i

    REP(i, M) {
        int res = dfs(i);

        if (res == -1) {
            ans = -1;
            break;
        }

        ans = max(ans, res);
    }

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 88320
//     THE ONLY WAY IS UP
 
#include<bits/stdc++.h>
 
#define ll              long long int
#define ld              long double
#define f1(i, a, b)     for(ll i = a; i < b; i++)
#define f2(a, b)        for(auto a : b)
#define ar(v, i)        v[i]
#define ar_(v, i, j)    v[i][j]
#define in_(x)          ll x; cin >> x;
#define ino_(type, x)   type x; cin >> x;
#define pb              push_back
#define nl              "\n"
#define tcase(t)        ll t; cin >> t; f1(z, 0, t)
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    in_(n) in_(m)
    ll sum = 0;
    f1(i, 0, m){
        in_(x)
        sum+=x;
    }
    if(sum > n)
        cout << "-1" << nl;
    else
        cout << n - sum << nl;
}

Measured memory_bytes: 3652
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<functional>
#include<map>
#include<cmath>
#include<iomanip>
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

using namespace std;

#define INF 1e9
#define min_3(a, b, c) min(a, min(b, c));
typedef long long ll;

int main()
{
  int n; cin >> n;
  int ans = n;
  vector<int> dp(n + 1, INF);
  
  //dp[n]はn円払う最小手数
  dp[0] = 0;
  for (int  i = 1; i <= n; i++)
  {
    int power = 1;
    while (power <= i)
    {
      dp[i] = min(dp[i], dp[i - power] + 1);
      power *= 6;
    }
  }

  for (int  i = 1; i <= n; i++)
  {
    int power = 1;
    while (power <= i)
    {
      dp[i] = min(dp[i], dp[i - power] + 1);
      power *= 9;
    }
  }

  cout << dp[n] << endl;  
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

void solve(int n, int k) {
    vector<int> v;
    for (int i = 0; i < n; i++) { 
        int x;
        cin >> x;
        v.pb(x);
    }
    sort(v.begin(), v.end());

    int ans = -1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (k >= v[i] + v[j] && k - v[i] - v[j] < k - ans) ans = v[i] + v[j];
        }
    }
    if (ans == -1) cout << "NONE" << endl;
    else cout << ans << endl;
}

int main() {
    cin.tie(0);
    while (1) {
        int n, k;
        cin >> n >> k;
        if (n == 0 && k == 0) break;
        solve(n, k);
    }
    return 0;
}


Measured memory_bytes: 3124
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    l=list(map(int,input().split()))
    l.sort()
    print(sum(l[:2]))

if __name__ == '__main__':
    main()


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

typedef  long long ll;
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//
//
#define int long long

using namespace std;

int ctoi(char c) {
 switch (c) {
 case '0': return 0;
 case '1': return 1;
 case '2': return 2;
 case '3': return 3;
 case '4': return 4;
 case '5': return 5;
 case '6': return 6;
 case '7': return 7;
 case '8': return 8;
 case '9': return 9;
 default: return 0;
 }
}


 ll a,b,c,s,t,i,j,k,x,y,z;
 ll A,B,C,S,T,X,Y,Z;

 ll count;

 long double pi=3.14159265358979323846;

 string N;



signed main(){

	cin>>a;

	x=0;
	REP(i,a+10){
		x=(x*10+7)%a;
		if(x==0){
	cout<<i+1;
	return 0;
	}
   }

   cout<<-1;


	return 0;

}


Measured memory_bytes: 3620
from math import sqrt


def divisors(x):
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            yield i
            if x // i != i:
                yield x // i


n = int(input())

ans = 0
for e in divisors(n):
    if e == 1:
        continue

    r = n
    while r % e == 0:
        r //= e

    if r % e == 1:
        ans += 1

ans += len(list(divisors(n - 1))) - 1

print(ans)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
    ll n;cin>>n;
    vector <ll> vec(n);
    for(int i=0;i<n;i++){
		cin>>vec[i];
    }
    vector <ll> dp(n,INT_MAX);
    dp[0]=0;
    for(int i=1;i<n;i++){
		for(int j=1;j<=2;j++){
			if(i-j>=0){
				dp[i]=min(dp[i],dp[i-j]+abs(vec[i]-vec[i-j]));
			}
		}
    }
    cout<<dp[n-1]<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include <algorithm>
using namespace std;
int N_MAX = 100;
typedef pair<int,int> P;
int main()
{
  int n;
  int h[N_MAX];
  int res=0;
  int t,m;
  int i,j;
  cin >> n;
  for(i=0;i<n;i++)
    cin >> h[i];
  m=*max_element(h,h+n);
  for(j=m;j>0;j--){
    t=0;
    for(i=0;i<n;i++)
      if(h[i]==j){
        t=1;
        h[i]--;
      } else if(t==1&&h[i]<j){
        t=0;
        res++;
      }
    if(t==1)
      res++;
  }
  cout << res << endl;
  return 0;
}

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

typedef long long ll;
#define all(x) (x).begin(),(x).end()
ll MOD = ll(1e8) + 9;

template<typename T>
T mod(T a, T b){
    return (a + b) % b;
}

template<typename T>
T gcd(T a, T b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

// n を素因数分解
map<ll, ll> factor(ll n){
    map<ll, ll> mp;
    for (ll i = 2; i*i <= n; i++) {
        while (n % i == 0) {
            mp[i]++;
            n /= i;
        }
    }

    if (n > 1) {
        mp[n]++;
    }

    return mp;
}

// 文字列に "hoge" が含まれているか
// string str = "hogepiyo";
// if (str.find("hoge") != string::npos) {
//     cout << "文字列が含まれています" << endl;
// }

// char to string
// char c = 'a';
// string str = {c};

void solve(){
    int N, M;
    cin >> N >> M;

    vector<int> num(N, -1);
    for (int i = 0; i < M; i++) {
        int s, c;
        cin >> s >> c;
        s--;
        if (num[s] == -1 || num[s] == c) {
            num[s] = c;
        } else {
            cout << -1 << endl;
            return;
        }
    }

    if (num.size() == 1 && num[0] == -1) {
        cout << 0 << endl;
        return;
    }

    if (num[0] == 0) {
        if (num.size() == 1) {
            cout << 0 << endl;
            return;
        } else {
            cout << -1 << endl;
            return;
        }
    }

    for (int i = 0; i < N; i++) {
        if (i == 0) {
            if (num[0] == -1) cout << 1;
            else cout << num[i];
        } else {
            if (num[i] == -1) cout << 0;
            else cout << num[i];
        }
    }
    cout << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


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

int main() {
    int N, M, X; cin >> N >> M >> X;
    int C[N], A[N][M];
    for (int i = 0; i < N; i++) {
        cin >> C[i];
        for (int j = 0; j < M; j++) cin >> A[i][j];
    }
    int ans = INT_MAX;
    for (int bits = 0; bits < (1 << N); bits++) {
        int p[M] = {};
        int money = 0;
        for (int i = 0; i < N; i++) {
            if (bits & (1 << i)) {
                money += C[i];
                for (int j = 0; j < M; j++) {
                    p[j] += A[i][j];
                }
            }
        }
        bool ok = true;
        for (int j = 0; j < M; j++) ok = ok && (p[j] >= X);
        if (ok) ans = min(money, ans);
    }
    if (ans == INT_MAX) ans = -1;
    cout << ans << endl;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int n;
    string s;
    cin >> n >> s;
    if(n%2==1){
        cout << "No" << endl;
        return 0;
    }
    int x=n/2;
    for(int i=0;i<x;i++){
        if(s[i]!=s[x+i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}



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

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

const ll MOD = (ll) 998244353ll;
const ll MAXN = (ll) 2e5 + 10;
const ll INF = (ll) 2242545357980376863;
const ld EPS = (ld) 1e-8;

ll a[MAXN];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	ll ans = INF;
	for(int i = 0; i + k - 1 < n; i++) ans = min(ans, a[i + k - 1] - a[i]);
	cout << ans;
	return 0;
}


/*

                                 ____              ,----..               ,----..
   ,---,                       ,'  , `.           /   /   \             /   /   \
  '  .' \                   ,-+-,.' _ |          /   .     :           /   .     :
 /  ;    '.              ,-+-. ;   , ||         .   /   ;.  \         .   /   ;.  \
:  :       \            ,--.'|'   |  ;|        .   ;   /  ` ;        .   ;   /  ` ;
:  |   /\   \          |   |  ,', |  ':        ;   |  ; \ ; |        ;   |  ; \ ; |
|  :  ' ;.   :         |   | /  | |  ||        |   :  | ; | '        |   :  | ; | '
|  |  ;/  \   \        '   | :  | :  |,        .   |  ' ' ' :        .   |  ' ' ' :
'  :  | \  \ ,'        ;   . |  ; |--'         '   ;  \; /  |        '   ;  \; /  |
|  |  '  '--'          |   : |  | ,             \   \  ',  /          \   \  ',  /
|  :  :                |   : '  |/               ;   :    /            ;   :    /
|  | ,'                ;   | |`-'                 \   \ .'              \   \ .'
`--''                  |   ;/                      `---`                 `---`
                       '---'

*/



Measured memory_bytes: 1024
N, X, M = map(int,input().split())

def cal(x):
    return pow(x,2,M)

memo = set()
lis = []
while X not in memo:
    memo.add(X)
    lis.append(X)
    X = cal(X)
pos = lis.index(X)

if pos >= N:
    print(sum(lis[:N]))
else:
    print(sum(lis[:pos]) + ((N-pos)//(len(memo)-pos)) * sum(lis[pos:]) + sum(lis[pos:(N-pos)%(len(memo)-pos)+pos]))

Measured memory_bytes: 77284
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define all(v) begin(v), end(v)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int const MOD = 1000000007;

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

signed main() {
    string s;
    while(getline(cin, s)) {
        if(s == ".") break;
        bool ok = true;
        stack<char> st;
        rep(i,0,s.length()) {
            if(s[i] == '(') st.push('(');
            else if(s[i] == '[') st.push('[');
            else if(s[i] == ')') {
                // printf("1: top = %c\n", st.top());
                if(!st.empty() && st.top() == '(') st.pop();
                else ok = false;
            }
            else if(s[i] == ']') {
                // printf("2: top = %c\n", st.top());
                if(!st.empty() && st.top() == '[') st.pop();
                else ok = false;
            }
        }
        if(!ok || !st.empty()) cout << "no" << endl;
        else cout << "yes" << endl;
    }
    return 0;
}

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

int main (){
	int n,nn,i,j,p;
	cin >> n;
	nn=n;
	while(1){
		if(nn==1){
			cout << "No" << endl;
			return 0;
		}
		if((nn%2)==1) break;
		else nn=nn/2;
	}
	cout << "Yes" << endl;
	if(n%2==0) nn=n-2;
	else nn=n-1;
	cout << "1 2" << endl; 
	cout << "2 3" << endl;
	cout << "3 " << 1+n << endl;
	cout << 1+n << " " << 2+n << endl;
	cout << 2+n << " " << 3+n << endl;
	for(i=4;i<=nn;i=i+2){
		cout << "1 " << (i) << endl;
		cout << (i) << " " << (i+1) << endl;
		cout << "1 " << (i+1+n) << endl;
		cout << (i+1+n) << " " << (i+n) << endl;
	}
	if(n%2==0){
		j=1;
		while(1){
			if(n<j){
				j=j/2;
				break;
			}
			j=j*2;
		}
		cout << n << " " << n+j+1 << endl;
		cout << 2*n << " " << n-j << endl;
	}
	return 0;
}

Measured memory_bytes: 2304
#include<bits/stdc++.h>
#define maxn 610
#define ll long long
#define mod 1000000007
using namespace std;
int a[maxn], tp[maxn], used[maxn], f[2][maxn][maxn], p, q, g[maxn][maxn], n, sum;
void get_f()
{
	p = 1; q = 0;
	f[0][0][0] = 1;
	for (int i = 2 * n; i >= 1; i--)
	{
		p ^= 1; q ^= 1;
		int tot = 2 * n;
		for (int j = 0; j <= tot; j++)
			for (int k = 0; k <= tot; k++)
				f[q][j][k] = 0;
		if (used[i] == 2)
		{
			for (int j = 0; j <= tot; j++)
				for (int k = 0; k <= tot; k++)
					f[q][j][k] = f[p][j][k];
			continue;
		}
		for (int j = 0; j <= tot; j++)
			for (int k = 0; k <= tot; k++)
			{
				if (k)
				{
					if (used[i]) f[q][j][k - 1] = (f[q][j][k - 1] + f[p][j][k]) % mod;
					else f[q][j][k - 1] = (f[q][j][k - 1] + f[p][j][k]) % mod;
				}
				if (used[i] == 0 && j) f[q][j - 1][k] = (f[q][j - 1][k] + (ll)f[p][j][k] * j % mod) % mod;
				if (used[i]) f[q][j + 1][k] = (f[q][j + 1][k] + f[p][j][k]) % mod;
				else f[q][j][k + 1] = (f[q][j][k + 1] + f[p][j][k]) % mod;
			}
	}
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= 2 * n; i++)
	{
		scanf("%d", &a[i]);
		if (a[i] != -1) used[a[i]] = 1;
	}
	for (int i = 1; i <= n; i++)
	{
		int t1 = a[2 * i - 1], t2 = a[2 * i];
		if (t1 != -1 && t2 != -1) {used[t1] = used[t2] = 2; continue;}
		if (t1 == -1 && t2 == -1) sum++;
		if (t1 != -1) used[t1] = 1;
		if (t2 != -1) used[t2] = 1;
	}
	get_f();
	int res = f[q][0][0];
	for (int i = 1; i <= sum; i++)
		res = (ll)res * i % mod;
	printf("%d\n", res);
	return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
        return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

int main() {
        constexpr int M = 26;

        string s, t;
        cin >> s >> t;

        const int n = s.length(), m = t.length();

        string ss = " " + s + s;
        auto ta = make_v(2 * n + 1, M, -1);
        vector<int> next(M, -1);

        for (int i = 2 * n; i >= 0; i--) {
                rep (j, M) {
                        ta[i][j] = next[j];
                }
                
                rep (j, M) {
                        if (i > 0 && ss[i] - 'a' == j) {
                                next[j] = i;
                        } else {
                                next[j] = ta[i][j];
                        }
                }
        }

        ll i = 0, c = 0;
        rep (j, m) {
                if (ta[i][t[j] - 'a'] == -1) {
                        cout << -1 << endl;
                        return 0;
                } else {
                        if (ta[i][t[j] - 'a'] > n) {
                                i = ta[i][t[j] - 'a'] - n;
                                c++;
                        } else {
                                i = ta[i][t[j] - 'a']; 
                        }
                }
        }

        cout << n * c + i << endl;

        return 0;
}


Measured memory_bytes: 27264
using System;
using System.Collections;
using System.IO;
using System.Linq;

namespace CompetitiveProgramming
{

  class Solve
  {
    const int INF = (int)(1e9) + 10;

    private void Main()
    {
      int N = int.Parse(Console.ReadLine());
      int K = int.Parse(Console.ReadLine());
      int X = int.Parse(Console.ReadLine());
      int Y = int.Parse(Console.ReadLine());
      if (N > K) 
      {
        Console.WriteLine(K * X + (N - K) * Y);
      }
      else
      {
        Console.WriteLine(N * X);
      }

    }

    public Solve()
    {
      Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
      Main();
      Console.Out.Flush();
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      new Solve();
    }
  }
}

Measured memory_bytes: 2776
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

using Weight=long long;
static const Weight INF=1LL<<57;

struct Edge {
    size_t src, dst;
    Weight weight;
    Edge() {}
    Edge(size_t src, size_t dst, Weight weight=1):
        src(src), dst(dst), weight(weight)
    {}
};

bool operator<(const Edge &e, const Edge &f) {
    if (e.weight != f.weight) {
        return e.weight > f.weight;
    } else {
        return e.src!=f.src? e.src<f.src : e.dst<f.dst;
    }
}

using Edges=vector<Edge>;
using Vertex=vector<Edge>;
using Graph=vector<Vertex>;

void join(Graph &g, size_t s, size_t d, Weight w=1) {
    // non-directed
    g[s].push_back(Edge(s, d, w));
    g[d].push_back(Edge(d, s, w));
}

void connect(Graph &g, size_t s, size_t d, Weight w=1) {
    // directed
    g[s].push_back(Edge(s, d, w));
}

void visit(
    const Graph &g, size_t v, vector<size_t> &ord, vector<size_t> &num,
    size_t k
) {
    if (~num[v]) return;

    num[v] = k;
    for (size_t i=0; i<g[v].size(); ++i)
        visit(g, g[v][i].dst, ord, num, k);

    ord.push_back(v);
}

vector<size_t> get_sccomp_id(const Graph &g) {
    size_t V=g.size();
    vector<size_t> idx(V, -1), ord, dro;
    for (size_t i=0; i<V; ++i)
        visit(g, i, ord, idx, i);

    reverse(ord.begin(), ord.end());
    idx.assign(V, -1);
    Graph h(V);
    for (size_t i=0; i<V; ++i)
        for (const Edge &e: g[i])
            connect(h, e.dst, e.src, e.weight);

    for (size_t i=0; i<V; ++i)
        visit(h, ord[i], dro, idx, i);

    return idx;
}

int main() {
    size_t V, E;
    scanf("%zu %zu", &V, &E);

    Graph g(V);
    for (size_t i=0; i<E; ++i) {
        size_t s, t;
        scanf("%zu %zu", &s, &t);

        connect(g, s, t);
    }

    vector<size_t> sccomp_id=get_sccomp_id(g);

    size_t Q;
    scanf("%zu", &Q);

    for (size_t i=0; i<Q; ++i) {
        size_t u, v;
        scanf("%zu %zu", &u, &v);

        printf("%d\n", sccomp_id[u]==sccomp_id[v]);
    }

    return 0;
}

Measured memory_bytes: 5304
#include<bits/stdc++.h>
#define f first
#define s second
#define inf 999999999999
#define N  500009
#define M  (L+R)/2
#define ll long long
#define pb push_back
using namespace std;
 
ll n,k,ans,len,KL,KR;
string A,L,R;
 
ll check(string x){
	ll pas=0;
	ll nn=x.size();
	for(int i=0;i<nn-1;i++){
		if(x[i]=='R' && x[i+1]=='R')pas++;
	}
	for(int i=nn;i>0;i--){
		if(x[i]=='L' && x[i-1]=='L')pas++;
	}
	return pas;
}
 
vector < pair<ll, pair<ll, ll> > > vL,vR;
 
int main()
{
 
	ios::sync_with_stdio(0);
 
	cin>>n>>k;
	
	cin>>A;
	ans=check(A);
	ans=min(n-1,ans+2*k);

	cout<<ans<<endl;
return 0;
}
 
 

Measured memory_bytes: 512
import sys
readline = sys.stdin.readline

class UF():
    def __init__(self, num):
        self.par = [-1]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            stack = []
            while self.par[x] >= 0:
                stack.append(x)
                x = self.par[x]
            for xi in stack:
                self.par[xi] = x
            return x
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] > self.par[ry]:
                rx, ry = ry, rx
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
        return rx

N, M = map(int, readline().split())
T = UF(N)
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    T.union(a, b)

print(-min(T.par))

Measured memory_bytes: 70828
/*input
1000000
*/


 
#include <bits/stdc++.h>
using namespace std;
 
 
 
#define int long long int
#define rep(i,n) \
    for(int i = 0; i < n; i++)
#define rep2(i, a, b) \
    for(int i = a; i < b; i++)
#define all(c) \
    c.begin(), c.end()
#define init(arr, num) \
    memset(arr, num, sizeof(arr))
#define fast\
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define inputFile \
    freopen("input.txt", "r", stdin); 
#define outputFile \
    freopen("output.txt", "w", stdout);
#define modM 1000000007
#define PI 3.1415926535897932
#define F first
#define S second  
#define pb push_back  
#define INF 3e18
#ifdef gaviria
#define TRACE
#endif
#ifdef TRACE
#define trace(...) _f(#VA_ARGS, __VA_ARGS_)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
    cout << name << " : " << arg1 << std::endl;
 
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#else
#define trace(...)
#endif
 
 
typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef pair< ll, ll > ii;
typedef unordered_set<int> usi;
 
 
 
ll n,i,j,k,m,c;
int countDivisors(int n) 
{ 
    int cnt = 0; 
    for (int i = 1; i <= sqrt(n); i++) { 
        if (n % i == 0) { 
            // If divisors are equal, 
            // count only one 
            if (n / i == i) 
                cnt++; 
  
            else // Otherwise count both 
                cnt = cnt + 2; 
        } 
    } 
    return cnt; 
} 
void solve()
{
  
int count=0;
c=0;
cin>>n;

int ans=0;
      for (int i = 1; i <= n-1; i++) { 
  ans+=n/i;
  if(n%i==0)
    ans--;
    } 
  
       cout<<ans;




  }

 
 
 
signed main()
{// inputFile;


    fast;
    int T = 1;
    // cin >> T;
    ll h=T;
    while(T--){
 
        solve();
        cout<<endl;
 
     
        
        
 
    }
    
    
    return 0;
 
}

Measured memory_bytes: 3692
#include <stdio.h>
int main(void)
{
	

	    int a,b,h=0,i;
 	   scanf("%d",&a);
    	   scanf("%d",&b);
      for(i=0;i<=b-a;i++)
   		 h=h+i;
    
    printf("%d",h-b);
    
    
    return 0;
    
}



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

using namespace std;

int N;
string S;
int c;
int w_c[2];

int main() {
  cin >> N >> S;

  for(int i = 0; i < S.length(); i++) {
    if(c == 0 && S[i] == ')') w_c[1]++;
    else if(c > 0 && S[i] == ')') c--;
    else if(S[i] == '(')c++;
  }
  w_c[0] = c;

  string tmp,tmp2;

  if(w_c[1] > 0) {
    for(int i = 0; i < w_c[1]; i++) tmp.push_back('(');
  }
  if(w_c[0] > 0) {
    for(int i = 0; i < w_c[0]; i++) tmp2.push_back(')');
  }
  cout << tmp + S + tmp2 <<endl;
    
}



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


int main(){
  int N;
  string s;
  cin >> N;
  cin >> s;
  int red = 0, blue = 0;
  for(int i = 0; i < N; i++){
    if(s[i] == 'R'){
      red++;
    }else{
      blue++;
    }
  }
  if(red > blue){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
while 1:
  n,k = map(int,input().split())
  if n == k == 0:
    break
  a = []
  for i in range(n):
    a.append(int(input()))
    c = 0
  for i in range(k):
    c += a[i]
    b = c
  for i in range(k, n):
    c += a[i]
    c -= a[i - k]
    b = max(b,c)
  print(b)


Measured memory_bytes: 9608
import java.util.Scanner;
public class Main {
	static Scanner scan=new Scanner(System.in);
	static long gcd (long a, long b) {return b>0?gcd(b,a%b):a;}
	static long lcm (long a, long b) {return a*b/gcd(a,b);}
	static int max(int a,int b) {return a>b?a:b;}
	static int min(int a,int b) {return a<b?a:b;}
	static long factorial(int i) {return i==1?1:i*factorial(i-1);}
	static int lower_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<=key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static int upper_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static boolean isPrime (int n) {
		if (n==2) return true;
		if (n<2 || n%2==0) return false;
		double d = Math.sqrt(n);
		for (int i=3; i<=d; i+=2)if(n%i==0){return false;}
		return true;
	}
	static int upper_division(int a,int b) {
		if(a%b==0) {
			return a/b;
		}
		else {
			return a/b+1;
		}
	}
	static long lupper_division(long a,long b) {
		if(a%b==0) {
			return a/b;
		}
		else {
			return a/b+1;
		}
	}
	static long lmax(long a,long b) {return Math.max(a, b);}
	static long lmin(long a,long b) {return Math.min(a, b);}
	static int[] setArray(int a) {
		int b[]=new int[a];
		for(int i=0;i<a;i++) {
			b[i]=scan.nextInt();
		}
		return b;
	}
	//Arrays.sort(array, (a, b) -> Integer.compare(a[0], b[0]));
	
	public static void main(String[] args) {
		long a=scan.nextLong();
		long b=scan.nextLong();
		long c=scan.nextInt();
		long d=scan.nextInt();
		long f=lcm(c,d);
		long uo1=((a-1)-((a-1)/c+(a-1)/d-(a-1)/f));
		long uo2=(b-((b)/c+(b)/d-(b)/f));
		System.out.println(uo2-uo1);
	}
}

Measured memory_bytes: 21588
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 * @throws NumberFormatException 
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		
		int count[] = new int[100003];
		
		for(int i = 0; i < n; i++){
			String[] tmpArray = br.readLine().split(" ");
			
			int a = Integer.parseInt(tmpArray[0]);
			int b = Integer.parseInt(tmpArray[1]);
			
			count[a]++;
			count[b + 1]--;
		}
		
		//debug
//		for(int i = 0; i <= 10; i++){
//			System.out.print(count[i]+" ");
//		}
//		System.out.println();
		
		int sum[] = new int[count.length];
		for(int i = 2; i < count.length; i++){
			sum[i] = sum[i - 1] + count[i];
			
//			if(i >= 4950 && i <= 5000) System.out.print("i = "+i+" sum="+sum[i] + " ");
		}
//		System.out.println();
		
		int index = 1;
		int maxValue = 0;
		
		for(int i = 2; i <= n + 1; i++){
//			System.out.println("sum "+sum[i]);
//			result = Math.max(result, sum[i]);
			
			if(maxValue <= sum[i] && sum[i] >= i - 1){
//				System.out.println("update at i = "+i);
				maxValue = i;
				index = i;
			}
		}
		
		System.out.println(index - 1);
	}

}



Measured memory_bytes: 63720