akhauriyash/Code-Regression huggingface dataset:
#include <string>
#include <vector>
#include <iostream>

using namespace std;

bool compare(string S1, string S2)
{
	if (S1.size() != S2.size()) { return S1.size() > S2.size(); }

	return S1 > S2;
}

int main()
{
	int H, W; char R[71][71];

	while (true)
	{
		scanf("%d", &W);
		scanf("%d", &H);

		if (H == 0 && W == 0) { break; }

		for (int i = 0; i < H; i++)
		{
			scanf("%s", R[i]);
		}

		vector<vector<string> > dp(H, vector<string>(W, ""));

		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				if (isdigit(R[i][j]))
				{
					if (R[i][j] != '0')
					{
						dp[i][j] = R[i][j];
					}

					if (i != 0)
					{
						if (R[i][j] != '0')
						{
							if (compare(dp[i - 1][j] + R[i][j], dp[i][j]))
							{
								dp[i][j] = dp[i - 1][j] + R[i][j];
							}
						}
						else
						{
							if (compare(dp[i - 1][j] + R[i][j], dp[i][j]) && dp[i - 1][j] != "")
							{
								dp[i][j] = dp[i - 1][j] + R[i][j];
							}
						}
					}

					if (j != 0)
					{
						if (R[i][j] != '0')
						{
							if (compare(dp[i][j - 1] + R[i][j], dp[i][j]))
							{
								dp[i][j] = dp[i][j - 1] + R[i][j];
							}
						}
						else
						{
							if (compare(dp[i][j - 1] + R[i][j], dp[i][j]) && dp[i][j - 1] != "")
							{
								dp[i][j] = dp[i][j - 1] + R[i][j];
							}
						}
					}
				}
			}
		}

		string ret = "";

		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				if (compare(dp[i][j], ret))
				{
					ret = dp[i][j];
				}
			}
		}

		printf("%s\n", ret.c_str());
	}

	return 0;
}

Measured memory_bytes: 3252
#include<stdio.h>

int main(void) {

	int n;
	double  x;
	int tmp;
	scanf("%d", &n);
	
	x = n / 1.08;
	//printf("%lf\n", x);

	//整数かどうか
	if (n == (int)((int)(x)*1.08)) {

		printf("%d", (int)x);
	}
	else {
		tmp = (int)(x + 1.0);
		//printf("%d\n", tmp);
		if ((int)(tmp*1.08) == n) {
			printf("%d", tmp);
		}
		else {
			printf(":(");
		}
	}


	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>
#include <set>

using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

const ll MOD = 1000000007;
const ll INF = 1 << 30;
const ll INF2 = 9000000000000000000LL;
const double INF3 = 900000000000000;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define sc second


int main() {
	ll n, a[100010], b[100010], ans;
	P aa[100010];
	cin >> n;
	for (int i = 0;i < n;i++)cin >> a[i];
	for (int i = 0;i < n;i++)cin >> b[i];
	for (int i = 0;i < n;i++) {
		if (i == 0)aa[i] = P(a[i], a[i]);
		else {
			if (a[i] == a[i - 1])aa[i] = P(1, a[i]);
			else aa[i] = P(a[i], a[i]);
		}
	}
	for (int i = n - 1;i >= 0;i--) {
		if (i == n - 1) {
			if (aa[i].fi <= b[n - 1] && b[n - 1] <= aa[i].sc)ans = 1;
			else {
				cout << 0 << endl;
				return 0;
			}
		}
		else {
			if (b[i] != b[i + 1]) {
				if (aa[i].fi <= b[i] && b[i] <= aa[i].sc) {}
				else {
					cout << 0 << endl;
					return 0;
				}
			}
			else {
				ans *= min(b[i], aa[i].sc) - max((ll)aa[i].fi, (ll)1) + 1;
				ans %= MOD;
			}
		}
	}
	cout << ans%MOD << endl;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define endl '\n'
using ll=long long;
 
const int INF=1e9+5;
const ll lim=(ll)3e16;
const int N=1e5+5;
const int mod=1e9+7;
const ll oo=1e18+5;
 
// dp[i] is the number of numbers that sum diggit  
// 10000 number of digits

void add_self(int& a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}

void sub_self(int& a,int b){
	a-=b;
	if(a<0) a+=mod;
}

string k;
int d;

int main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
	cin>>k>>d;
	// cout<<k<<" "<<d<<endl;
	// return 0;
	int len=k.size();
	vector<vector<int>> dp(d,vector<int>(2));
	// dp[sum][pre_small] is the number of ways choose digit that sum of digits is sum and check is true if pre digit is small than k[pre_id]
	// note : avoid cur_num > k
	dp[0][0]=1;
	for(int cur_pos=0;cur_pos<len;++cur_pos){
		vector<vector<int>> cur_dp(d,vector<int>(2));
		for(int sum=0;sum<d;++sum){
			for(int is_smaller=0;is_smaller<2;++is_smaller){
				for(int digit=0;digit<10;++digit){
					if(digit>k[cur_pos]-'0'&&!is_smaller){
						break;
					}
					add_self(cur_dp[(sum+digit)%d][is_smaller||(digit<k[cur_pos]-'0')],dp[sum][is_smaller]);
				}
			}
		}
		dp=cur_dp;
	}
	add_self(dp[0][0],dp[0][1]);
	sub_self(dp[0][0],1);
	cout<<dp[0][0]<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int x,i,sum = 0,average;
	for(i = 0;i<5;i++){
		scanf("%d",&x);
		if(x<40){
			x = 40;
		}
		sum = sum+x; 
	}
	average = sum/5;
	printf("%d\n",average);
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

int main(){
    ll N;
    cin >> N;
    vector<ll> T(N),A(N);
    rep(i,N){
        cin >> T[i] >> A[i];
    }
    ll t=T[0],a=A[0];
    rep(i,N){
        if(T[i] == A[i]){
            a = max(a,t);
            t = max(a,t);
        }else if(T[i] < A[i]){
            //while(true){
                ll tmp = t;
                while(t % T[i] != 0){
                    t++;
                }
                if((t/T[i])*A[i] >= a){
                    a = (t/T[i])*A[i];
                    //break;
                }else{
                    t = tmp;
                    while(a % A[i] != 0){
                        a++;
                    }
                    t = (a/A[i])*T[i];
                    //break;
                }
            //}
        }else{
            //while(true){
                ll tmp = a;
                while(a % A[i] != 0){
                    a++;
                }
                if((a/A[i])*T[i] >= t){
                    t = (a/A[i])*T[i];
                    //break;
                }else{
                    a = tmp;
                    while(t % T[i] != 0){
                        t++;
                    }
                    a = (t/T[i])*A[i];
                    //break;
                }
            //}
        }
        //cout << t << " " << a <<endl;
    }
    cout << a+t << endl;
}



Measured memory_bytes: 256
h, w, n = map(int, input().split())
sr, sc = map(int, input().split())
s = input()
t = input()
p1 = sc - 1
p2 = sc - 1
q1 = sr - 1
q2 = sr - 1
for i in range(n):
    if s[i] == 'R':
        p1 += 1
    elif s[i] == 'L':
        p2 -= 1
    elif s[i] == 'U':
        q1 -= 1
    else:
        q2 += 1
    if p1 >= w or p2 < 0 or q1 < 0 or q2 >= h:
        print('NO')
        exit(0)
    if t[i] == 'R':
        p2 += 1
        if p2 >= w:
            p2 -= 1
    elif t[i] == 'L':
        p1 -= 1
        if p1 < 0:
            p1 += 1
    elif t[i] == 'U':
        q2 -= 1
        if q2 < 0:
            q2 += 1
    else:
        q1 += 1
        if q1 >= h:
            q1 -= 1
print('YES')


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

using ll = long long;

int main() {
	string s;
	cin >> s;

	int idc = 1000, idf = -1;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'C') {
			idc = i;
			break;
		}
	}

	for (int i = s.size() - 1; i >= 0; i--) {
		if (s[i] == 'F') {
			idf = i;
			break;
		}
	}
	
	cout << (idc < idf ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 3636
#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++)
using ll=long long;
using namespace std;


int main()
{
	int ab,bc;
	cin>>ab>>bc;
	cout<<ab*bc/2<<endl;
	return 0;
}


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

int main()
{
	int w,n,b,c,t,i;
	int *a;

	scanf("%d",&w);
	scanf("%d",&n);

	a=(int*)calloc(w,sizeof(int));

	for(i=0;i<w;i++) a[i]=i+1;

	for(i=0;i<n;i++){
		scanf("%d,%d",&b,&c);
		t=a[b-1];
		a[b-1]=a[c-1];
		a[c-1]=t;
	}

	for(i=0;i<w;i++) printf("%d\n",a[i]);
	return 0;
}

Measured memory_bytes: 608
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)







int main() {
    int n, m, x[100000], v[99999], sum = 0;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++){
        scanf("%d", &x[i]);
    }
    sort(x, x + m);
    for(int i = 0; i < m - 1; i++){
        v[i] = x[i + 1] - x[i];
    }
    sort(v, v + m - 1);
    for(int i = m - 1 - n; i >= 0; i--){
        sum += v[i];
    }
    printf("%d\n", sum);
}

Measured memory_bytes: 1024
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <sstream>
using namespace std;

int main(){
  int x, a;
  cin >> x >> a;
  if (x < a) {
    cout << 0 << endl;
  } else {
    cout << 10 << endl;
  }

  return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

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

  	string s; cin >> s;
    s[3] = '8';
    cout << s << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vll vector<ll>
#define vi vector<int>
#define vvll vector<vll>
#define wh(t) while(t--)
#define fi(n) for(ll i = 0; i < n; i++)
#define fj(n) for(ll j = 0; j < n; j++)
#define fu(i,s,e) for(ll i = s; i <=e; i++)
#define fd(i,s,e) for(ll i = s; i >=e; i--)
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define fr first
#define se second
#define sll stack<ll>
#define qll queue<ll>
using namespace std;
const ll M = 1e9+7;
//const ll M = 998244353;

ll pmp(ll x,ll n){ll a = 1;while(n > 0){if(n & 1) a = (a * x)%M;x = (x * x)%M;n = n>>1;}return a;}

void solve(){
	ll n,m;
	cin >> n >> m;
	ll t;
	cin >> t;
	vpll a(t);
	map<pll,ll> p;
	vpll r(n);
	vpll c(m);
	fi(n){
		r[i].fr = 0;
		r[i].se = i;
	}
	fi(m){
		c[i].fr = 0;
		c[i].se = i;
	}
	fi(t){
		cin >> a[i].fr >> a[i].se;
		--a[i].fr;--a[i].se;
		r[a[i].fr].fr++;
		c[a[i].se].fr++;
		p[a[i]]++;
	}
	sort(r.rbegin(), r.rend());
	sort(c.rbegin(), c.rend());
	vll rr;
	vll cc;
	fi(n)
	if(r[i].fr==r[0].fr) rr.pb(r[i].se);
	else break;
	fi(m)
	if(c[i].fr==c[0].fr) cc.pb(c[i].se);
	else break;
	ll flag = 0;
	for(auto x:rr){
		for(auto y:cc){
			if(p[mp(x,y)]==0){
				flag = 1;
				break;
			}
		}
		if(flag) break;
	}
	cout << r[0].fr+c[0].fr-(1-flag) << endl;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	#ifndef ONLINE_JUDGE
	//freopen("input.txt", "r", stdin);
	#endif
	ll t;
	t = 1;
	//cin >> t;
	wh(t){
		solve();
	}
	cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
	return 0;
}

Measured memory_bytes: 44376
#include<stdio.h>
 #include<vector>
 #include<algorithm>
 using namespace std;
 typedef long long ll;
 int main()
 {
 int a, b, x, y;
 scanf("%d%d%d%d", &a, &b, &x, &y);
 printf("%lf %d\n", double(a)*double(b) / 2, x + x == a&&y + y == b);
return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<stack>
#include<string>
#include<cstdlib>

using namespace std;

int main()
{
	stack<int> S;
	int a, b;
	string s;
	while (cin >> s)
	{
		if (s[0] == '+')
		{
			a = S.top(); S.pop();
			b = S.top(); S.pop();
			S.push(a + b);
			
		}
		else if (s[0] == '-')
		{
			a = S.top(); S.pop();
			b = S.top(); S.pop();
			S.push(b- a);
		}
		else if(s[0]=='*')
		{
			a = S.top(); S.pop();
			b = S.top(); S.pop();
			S.push(a * b);
		}
		else
		{
			S.push(atoi(s.c_str()));
		}
	}

	cout << S.top()<<endl;
	

	return 0;
}


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

namespace
{

}

namespace ABC178
{

  class E
  {
  public:
    E() = default;
    ~E() = default;


    void Run()
    {
      int N = {};
      std::cin >> N;

      long long max_z = LONG_MIN;
      long long min_z = LONG_MAX;
      long long max_w = LONG_MIN;
      long long min_w = LONG_MAX;
      for (int i = 0; i < N; ++i)
      {
        long long x, y;
        std::cin >> x;
        std::cin >> y;

        if (x + y > max_z) max_z = x + y;
        if (x + y < min_z) min_z = x + y;
        if (x - y > max_w) max_w = x - y;
        if (x - y < min_w) min_w = x - y;
      }

       std::cout << std::max(std::abs(max_z - min_z), std::abs(max_w - min_w)) << std::endl;
    }
  };
}
int main()
{

  ABC178::E prob;
  prob.Run();

  return 0;
}




Measured memory_bytes: 3132
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;

struct CHT{
	using D = ll;
	typedef pair<D,D> P;
	vector<P> deq;
	int s,sd,t;
	void init(int N){
		deq.resize(N);
		s=0,sd=0,t=0;
	}
	void add(D a,D b){		//add ax+b     a:(広義)単調減少!!!
		b=-b;
		P p(a,b);
		while(s+1<t&&check(deq[t-2],deq[t-1],p)) t--;
		sd++;
		deq[t++]=p;
	}
	D incr_query(D x){		//x:単調増加の時,これを繰り返し呼ぶ(間にaddが挟まるのはOK)
		x=-x;
		while(s+1<t&&f(deq[s],x)>=f(deq[s+1],x)) s++;
		return -f(deq[s],x);
	}
	D decr_query(D x){		//x:単調減少の時,これを繰り返し呼ぶ(間にaddが挟まるのはOK)
		x=-x;
		if(sd>=t) sd=t-1;
//		while(sd+1<t&&f(deq[sd],x)>=f(deq[sd+1],x)) sd++;
		while(sd>0&&f(deq[sd],x)>f(deq[sd-1],x)) sd--;
		return -f(deq[sd],x);
	}
	D query(D x){
		x=-x;
		int lb=s-1,ub=t-1;
		while(ub-lb>1){
			int m=(lb+ub)/2;
			if(isright(deq[m],deq[m+1],x)) lb=m;
			else ub=m;
		}
		return -f(deq[ub],x);
	}

	bool isright(P& a,P& b,D x){
		return f(a,x)>=f(b,x);
	}
	bool check(P& a,P& b,P& c){
		return (b.fs-a.fs)*(c.sc-b.sc)>=(b.sc-a.sc)*(c.fs-b.fs);
	}
	D f(P &p,int x){
		return p.fs*x+p.sc;
	}
}cht;

ll inf=1e18;
const int MN=300000;
int N;
ll T[MN];

ll le[MN+1],ri[MN+1];

ll notuse[MN];
ll use[MN];

void calc(int L,int R){
	if(L==R) return;
	int m=(L+R)/2;
	
	//L<=j<=m<=p<i<=R
	cht.init(m-L+1);
	for(ll j=L;j<=m;j++) cht.add(-j,le[j]+(j*j-j)/2);
	ll mx=-inf;
	for(ll i=R;i>=m+1;i--){
		ll val=cht.incr_query(i)+(i*i+i)/2+ri[N-i];
		chmax(mx,val);
		chmax(use[i-1],mx);
	}

	//L<=j<=p<m<i<=R
	cht.init(R-m);
	for(ll i=m+1;i<=R;i++) cht.add(-i,ri[N-i]+(i*i+i)/2);
	mx=-inf;
	for(ll j=L;j<m;j++){
		ll val=cht.decr_query(j)+(j*j-j)/2+le[j];
		chmax(mx,val);
		chmax(use[j],mx);
	}

	calc(L,m);
	calc(m+1,R);
}
int main(){
	cin>>N;
	rep(i,N) scanf("%lld",T+i);

	cht.init(N);
	le[0]=0;
	for(ll i=0;i<N;i++){
		cht.add(-i,le[i]+(i*i-i)/2);
		le[i+1]=max(le[i]+T[i],cht.decr_query(i+1)+(i+1)*(i+2)/2);
	}
	cht.init(N);
	ri[0]=0;
	for(ll i=0;i<N;i++){
		cht.add(-i,ri[i]+(i*i-i)/2);
		ri[i+1]=max(ri[i]+T[N-1-i],cht.decr_query(i+1)+(i+1)*(i+2)/2);
	}
	
	rep(i,N) notuse[i]=le[i]+T[i]+ri[N-1-i];

	ll sum=0;
	rep(i,N) sum+=T[i];

	calc(0,N);

//	rep(i,N) printf("use[%d]=%lld\n",i,use[i]);
//	rep(i,N) printf("notuse[%d]=%lld\n",i,notuse[i]);
	

	int M;
	cin>>M;
	rep(i,M){
		int p;
		ll x;
		scanf("%d%lld",&p,&x);
		p--;
		ll ans=max(use[p],notuse[p]-T[p]+x);
		cout<<ans-(sum-T[p]+x)<<endl;
	}
}


Measured memory_bytes: 18944
#include<iostream>
#include<cmath>
#include<string>
#include<list>
#include<vector>
#include<algorithm>
#include <numeric>
#include<queue>
using namespace std;
int main(int argc, char const *argv[])
{
	/*
	cin>>x;
	cout<<x<<endl;
	*/
	int a,b,i,j,n,ans=0;
	cin>>n;
	int v[n],c[n];
	for(i=0;i<n;i++){
		cin>>v[i];
	}
	for(i=0;i<n;i++){
		cin>>c[i];
	}
	for(i=0;i<n;i++){
		if(v[i]-c[i]>0)
			ans+=(v[i]-c[i]);
	}

	cout<<ans<<endl;

}

Measured memory_bytes: 256
-- Structured Program II - Grading

import Control.Applicative

main :: IO ()
main = do
  xs <- map (map read . words) . lines <$> getContents
  mapM_ (putStrLn . calc) $ takeWhile (/= [-1, -1, -1]) xs

calc :: [Int] -> String
calc [-1, _, _] = "F"
calc [_, -1, _] = "F"
calc [m, f, r]
  | total >= 80 = "A"
  | total >= 65 = "B"
  | total >= 50 = "C"
  | total >= 30 = if r >= 50 then "C" else "D"
  | otherwise   = "F"
  where total = m + f



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

using namespace std;

/**templates**/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;

#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define sf(x) scanf("%lf",&x)
#define ss(x) scanf(" %s",x)
#define sc(x) scanf(" %c",&x)
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define aa first
#define bb second
#define sz(x) (ll)(x).size()
#define cas printf("Case %lld: ",++t)
#define casline printf("Case %lld:\n",++t)
//#define cas cout<<"Case "<<++t<<": "
//#define casline cout<<"Case "<<++t<<":"<<endl;
#define distance(x1,y1,x2,y2)((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
#define endl "\n"
#define bug cout<<"bugggggggggggg "<<endl;
#define fast ios_base::sync_with_stdio(0);cin.tie(nullptr); ///no printf/scanf

const ll mod = 1000000007;
const ll inf = 1LL<<62;
const ll mx = 100005;
const double eps = 1e-10;

ll dx[10]={1,0,-1,0};
ll dy[10]={0,-1,0,1};

ll power(ll a,ll b)
{
    if(b==0)return 1;
    ll x=power(a,b/2);
    x=x*x;
    if(b%2)x=x*a;
    return x;
}

ll Set(ll N,ll pos){return N=N | (1LL<<pos);}
ll reset(ll N,ll pos){return N= N & ~(1LL<<pos);}
bool check(ll N,ll pos){return (bool)(N & (1LL<<pos));}

/**
double cosine_rule(double a,double b,double c)
{
    double res=(a*a+b*b-c*c)/(2*a*b);
    res=acos(res);
    return res;
}
*/

int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
//    fast; ///no printf/scanf
    ll tst,a,b,c,k,n,m,res=0,ans=0,t=0;
    sl(a),sl(b),sl(c);
    res=c/a;
    res*=b;
    cout<<res<<endl;


    return 0;
}


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

const int N=1e5+5;

//int a[N],b[N],c[N];

int n;

int mem[N][5];

int h[N][5];

int dp(int i,int last_act){

if (i==n)
    return 0;

    if(mem[i][last_act]!=-1){

        return mem[i][last_act];

    }

    int ans =0;

    for (int j=0;j<3;j++){

        if (j!=last_act){

            ans =max(ans ,h[i][j]+dp(i+1,j));

        }
    }

    return mem[i][last_act]=ans;

}

int main(){

    scanf("%d",&n);

    for (int i=0; i<n;i++){
            for (int j=0;j<3;j++)

        scanf("%d",&h[i][j]);


    }
    memset (mem,-1,sizeof mem);

    int ans =0;

    for (int i=0;i<3;i++){

        ans =max(ans ,h[0][i]+dp(1,i));

    }

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

}


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

#define REP(i, a, b) for ( int i = (a); i < (b); i++ )
#define REVREP(i, a, b) for ( int i = (a); i >= (b); i--)
#define DEBUG_INT(var) printf("the value of "#var" is %d\n", var)
#define PRINT_ARRAY(name, i) printf("the value of "#name"[%d] is %d\n", (i), name[(i)])
#define DEBUG_ARRAY(name, begin, end) REP(i, begin, end) PRINT_ARRAY(name, i)

#define YES puts("YES")
#define NO  puts("NO")
#define Yes puts("Yes")
#define No  puts("No")

using namespace std;

typedef long long ll;

int ans;
int X;
vector<int> v;


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

    v.push_back(1);
    REP(i, 2, 100) {
    	int x = i*i;
    	while (x <= X) {
    		v.push_back(x);
    		x *= i;
    	}
    }

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

    ans = *(upper_bound(v.begin(), v.end(), X) - 1);

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

	return 0;
}


Measured memory_bytes: 256
from collections import defaultdict
 
N = int(input())	# 使わない
 
# j - i = A[i] + A[j] から、
# i + A[i] = j - A[j] となり、iとjが独立するため、同時並行で処理
L = defaultdict(lambda: 0)
R = defaultdict(lambda: 0)
for i, val in enumerate(map(int, input().split())):
  L[i - val] += 1	# i - val <= j - A[j]
  R[i + val] += 1	# i + val <= i + A[i]
  
cnt = 0
for key, val in L.items():
  if key > 0:
    cnt += L[key] * R[key]
    
print(cnt)

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

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
    ifstream t("/proc/self/status");
    cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) - '0' + ch;
	return sum * fg;
}

typedef long long LL;
typedef long double LD;
typedef pair<int, int> pii;

const int MAXN = (int) 2e5;

int n;

int a[MAXN + 5];

inline void input()
{
	n = read<int>();
	for(int i = 1; i <= n; ++i) a[i] = read<int>();
}

LL prefix[MAXN + 5];

inline LL query(int l, int r) { return prefix[r] - prefix[l - 1]; }

inline void solve()
{
	prefix[0] = 0;
	for(int i = 1; i <= n; ++i) prefix[i] = prefix[i - 1] + a[i];

	int l = 1, r = 3;
	LL ans = LLONG_MAX;
	for(int i = 2; i < n; ++i)
	{
		while(l < i - 1 && abs(query(1, l) - query(l + 1, i)) > abs(query(1, l + 1) - query(l + 2, i))) ++l;
		while(r < n - 1 && abs(query(i + 1, r) - query(r + 1, n)) > abs(query(i + 1, r + 1) - query(r + 2, n))) ++r;
		LL s[4] = {query(1, l), query(l + 1, i), query(i + 1, r), query(r + 1, n)};
		sort(s, s + 4);
		chkmin(ans, s[3] - s[0]);
	}
	printf("%lld\n", ans);
}

int main()
{
//#ifndef ONLINE_JUDGE
//	freopen("D.in", "r", stdin);
//	freopen("D.out", "w", stdout);
//#endif

	input();
	solve();

	return 0;
}



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

int main() {
  int n, k, d, a;
  scanf("%d %d", &n, &k);
  set<int> s;
  for(int i = 0; i < k; i++) {
    scanf("%d", &d);
    for(int j = 0; j < d; j++) {
      scanf("%d", &a);
      s.insert(a);
    }
  }
  printf("%d\n", n - s.size());
}

Measured memory_bytes: 3792
import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args){
	try{
	    BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
	    String st = s.readLine();
	    for(int i=st.length()-1; i>=0; i--)
		System.out.print(st.charAt(i));
	    System.out.println();
	}catch(Exception e){
	    System.out.println("Error");
	}
    }
}

Measured memory_bytes: 9336
N=int(input())
dp=[[0 for i in range(N+1)] for i in range(3)]

for j in range(N):
    abc=list(map(int,input().split()))
    for i in range(3):
        if j==0:
            dp[i][j]=abc[i]
        else:
            dp[i][j]=max([dp[k][j-1]+abc[i] for k in range(3) if k!=i])
print(max([dp[i][N-1] for i in range(3)]))

Measured memory_bytes: 14960
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  int N;
  cin >> N;
  vector<int> s(N);
  int sum = 0;
  rep(i, N) {
    cin >> s[i];
    sum += s[i];
  }
  sort(all(s));

  if (sum % 10 != 0) {
    cout << sum << endl;
    return 0;
  } else {
    rep(i, N) {
      if (s[i] % 10 != 0) {
        cout << sum - s[i] << endl;
        return 0;
      }
    }
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, A, B;
  double C, D;
  cin >> N;
 
  A = N / 10;
  B = N % 1000;
  C = A / 111.0;
  D = B / 111.0;
  
  if (C==1 || C==2 || C==3 || C==4 || C==5 || C==6 || C==7 || C==8 || C==9){
    cout << "Yes" << endl;
  }
  else if (D==0 || D==1 || D==2 || D==3 || D==4 || D==5 || D==6 || D==7 || D==8 || D==9){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <cstring>
using namespace std;
long long a[200000];
vector <int> edges[200000];
int ans[200000];
bool used[200000];
vector <int> dp;

void dfs(int cur){
  used[cur] = true;
  long long prev;
  int prev_ind;
  auto it = lower_bound(dp.begin(), dp.end(), a[cur]);
  if(it != dp.end()){
    prev = *it;
    prev_ind = it - dp.begin();
    *it = a[cur];
  } else {
    prev = -1;
    prev_ind = dp.size();
    dp.push_back(a[cur]);
  }
  ans[cur] = dp.size();

  for(int i = 0 ; i < edges[cur].size(); i++){
    int next = edges[cur][i];
    if(!used[next]){
      dfs(next);
    }
  }

  if(prev >= 0){
    dp[prev_ind] = prev;
  } else {
    dp.pop_back();
  }
}

int main(){
  int N;
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> a[i];
  }

  for(int i = 0; i < N - 1; i++){
    int u;
    int v;
    cin >> u >> v;
    edges[u - 1].push_back(v - 1);
    edges[v - 1].push_back(u - 1);
  }

  dfs(0);

  for(int i = 0; i < N; i++){
    cout << ans[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 28544
<?php
$A[0] = trim(fgets(STDIN));
$A[1] = trim(fgets(STDIN));
$A[2] = trim(fgets(STDIN));
$A[3] = trim(fgets(STDIN));
$A[4] = trim(fgets(STDIN));
$result=0;;
for($i = 0; $i <= 4; $i++){
  $res = $A[$i]%10;
  if($res==0){
    $res=10;
  }
  $a1[$i] = $res;
}
$min = min($a1);
foreach($A as $v){
  $aa = ceil(($v/10))*10;
  $result+=$aa;
}
$result-= 10-$min;
print($result);

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


ll K;
vector<ll> A;

int main(){
    cin >> K;
    A.resize(K);
    rep(i, 0, K) cin >> A[i];

    if(A[K-1] != 2){
        cout << -1 << endl;
        return 0;
    }

    // min
    ll mn = 2, mx = 2;
    for(ll i = K-1; i >= 0; i--){
        
        ll tmn, tmx;
        
        if(mn % A[i] != 0 && mn + A[i] - mn % A[i] > mx){
            cout << -1 << endl;
            return 0;
        }

        tmn = (ll)((mn+A[i]-1)/A[i])*A[i];
        tmx = (ll)(mx/A[i])*A[i]+A[i]-1;

        mn = tmn; mx = tmx;
    }

    cout << mn << " " << mx << endl;
    return 0;
}

Measured memory_bytes: 1024
N = int(input())
Axyss = []
for i in range(N):
  A = int(input())
  xys = []
  for j in range(A):
    x, y = map(int, input().split())
    x = x-1
    xys.append((x, y))
  Axyss.append((A, xys))
r = 0
for n in range(2**N):
  ss = [0]*N
  for i in range(N):
    if n&(1<<i) != 0:
      ss[i] = 1
  c = ss.count(1)
  if c <= r:
    continue
  ok = True
  for i in range(N):
    s = ss[i]
    A, xys = Axyss[i]
    for x, y in xys:
      if s == 1 and ss[x] != y:
        ok = False
        break
  if ok:
    r = max(r, c)
print(r)


Measured memory_bytes: 3064
s = gets.chomp
s = s.reverse()
pre = -1
for i in 0..(s.length)
  k =  s.slice(pre+1..i)
  if k == 'maerd' or k == 'esare' or k == 'remaerd' or k == 'resare'
    pre	= i
  end
end
if (pre == s.length - 1)
  puts("YES")
else
  puts("NO")
end


Measured memory_bytes: 63216
n, m = map(int,input().split())
h = list(map(int,input().split()))
l =[0]*(n+1)

for i in range(m):
    a,b = map(int,input().split())
    if h[a-1]>h[b-1]:
        l[b]=1
    elif h[a-1]<h[b-1]:
        l[a]=1
    else:
        l[a], l[b]=1,1

print(n-sum(l))

Measured memory_bytes: 85064
import java.util.*;

public class Main {

    static final int MOD = 1000000007;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        for(int i=1;i<=n;i+=2){
            if(div(i)==8)ans++;
        }
        System.out.println(ans);
    }
    private static int div(int n){
        int ans = 0;
        for(int i=1;i<=n;i++){
            if(n%i==0)ans++;
        }
        return ans;
    }


}


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

#define ll long long
#define ii pair <int, int>
#define endl "\n"

ll maxi(ll a, ll b){
	return ((a > b) ? a : b); 
}

ll mini(ll a, ll b){
	return ((a < b) ? a : b);
}

int main ()
{
	
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #define int ll

    int n, w;
    cin >> n >> w;

    vector <int> weight(n, 0);
    vector <int> value(n, 0);
    int sum = 0;

    for (int i=0; i<n; i++){
    	cin >> weight[i] >> value[i];
    	sum += value[i];
    }


    vector <int> dp(sum + 1, 9e18);//dp[i] denotes the minimum weight necessary to have value of i
    dp[0] = 0;
    for (int i=0; i<n; i++){
    	for (int j = sum - value[i]; j >= 0; j--){
    		dp[j + value[i]] = mini(dp[j + value[i]], dp[j] + weight[i]);
    	}
    }
    int ans = 0;
    for (int i=0; i <= sum; i++){
    	if (dp[i] <= w)
    		ans = maxi(ans, i);
    }
    cout << ans << endl;

    
    
	return 0;
}

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

#define INF INT_MAX

using namespace std;

typedef long long ll;
typedef pair<string,int> pii;

int main(void){
 	cin.tie(0);
    ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector< pii > sp;
	vector< pii > index;
	for(int i = 0;i < N;i++){
		int p;
		string s;
		cin >> s >> p;
		sp.push_back(pii(s,100-p));
		index.push_back(pii(s,100-p));
	}
	sort(sp.begin(),sp.end());
	for(int i = 0;i < N;i++){
		for(int j = 0;j < N;j++){
			if(sp[i].first==index[j].first && sp[i].second == index[j].second){
				cout << j+1 << endl;
				break;
			}

		}
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

const int INF = 100000000;
#define P(x) (x) * (x)

int dp[20050][260];

int main(void)
{
	int n, m;
	while (cin >> n >> m, n && m){
		int c[20];
		int x[20050];
		for (int i = 0; i < m; i++){
			cin >> c[i];
		}
		for (int i = 0; i < n; i++){
			cin >> x[i];
		}

		// memset(dp, INF, sizeof(dp));
		for (int i = 0; i < 20050; i++){
			for (int j = 0; j < 260; j++){
				dp[i][j] = INF;
			}
		}

		dp[0][128] = 0;
		for (int i = 0; i < n; i++){
			for (int j = 0; j < 256; j++){
				if (dp[i][j] == INF) continue;
				for (int k = 0; k < m; k++){
					int now = j + c[k];
					if (now < 0) now = 0;
					if (255 < now) now = 255;
					dp[i + 1][now] = min(dp[i + 1][now], dp[i][j] + P(x[i] - now));
					// cout << P(c[i + 1] - now) << " ";
					// printf("dp[%d][%d] = %d\n", i+1, now, dp[i+1][now]);
				}
				// puts("");
			}
		}

		int ret = INF;
		for (int i = 0; i < 256; i++){
			ret = min(ret, dp[n][i]);
		}

		cout << ret << endl;
	}
}

Measured memory_bytes: 21600
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Tasks
{
    public class D
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var N = Scanner.Scan<int>();
            var answer = 0L;
            var C = new int[10, 10];
            for (var i = 1; i <= N; i++)
            {
                if (i % 10 == 0) continue;
                var r = i % 10;
                var l = 0;
                var tmp = i;
                while (tmp > 0)
                {
                    l = tmp;
                    tmp /= 10;
                }
                C[l, r]++;
            }
            for (var i = 0; i < 10; i++)
            {
                for (var j = 0; j < 10; j++)
                {
                    answer += C[i, j] * C[j, i];
                }
            }

            Console.WriteLine(answer);
        }

        public static class Scanner
        {
            private static Queue<string> queue = new Queue<string>();
            public static T Next<T>()
            {
                if (!queue.Any()) foreach (var item in Console.ReadLine().Trim().Split(" ")) queue.Enqueue(item);
                return (T)Convert.ChangeType(queue.Dequeue(), typeof(T));
            }
            public static T Scan<T>() => Next<T>();
            public static (T1, T2) Scan<T1, T2>() => (Next<T1>(), Next<T2>());
            public static (T1, T2, T3) Scan<T1, T2, T3>() => (Next<T1>(), Next<T2>(), Next<T3>());
            public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() => (Next<T1>(), Next<T2>(), Next<T3>(), Next<T4>());
            public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() => (Next<T1>(), Next<T2>(), Next<T3>(), Next<T4>(), Next<T5>());
            public static IEnumerable<T> ScanEnumerable<T>() => Console.ReadLine().Trim().Split(" ").Select(x => (T)Convert.ChangeType(x, typeof(T)));
        }
    }
}


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

int main(){
  string N;
  cin >>N;
  if( ((N.at(0)==N.at(1))&&(N.at(1)==N.at(2))) ||((N.at(1)==N.at(2))&&(N.at(2)==N.at(3)))){
    cout<<"Yes"<<endl;
    return 0;
  }
      
      cout<<"No"<<endl;

  return 0;
}


Measured memory_bytes: 256
function Main(input) {
    input = input.split("\n");
    x = parseInt(input[0], 10);
    if (x>=30) {
        console.log("Yes\n");
    } else {
        console.log("No\n");
    }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));//おまじない

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

using namespace std;

int main()
{
  uint64_t N, M;
  cin >> N >> M;
  
  vector<uint64_t> A(N);
  for (uint64_t n = 0; n < N; ++n) {
    cin >> A[n];
  }
  
  priority_queue<uint64_t> q;
  for (uint64_t n = 0; n < N; ++n) {
    q.emplace(A[n]);
  }
  
  for (uint64_t m = 0; m < M; ++m) {
    uint64_t a = q.top(); q.pop();
    q.emplace(a >> 1);
  }
  
  uint64_t S = 0;
  while (!q.empty()) {
    uint64_t a = q.top(); q.pop();
    S += a;
  }
  cout << S << endl;
  
  return 0;
}

Measured memory_bytes: 2168
import math

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

a_list=[]
b_list=[]
for i in range(N): # N < 10**5
  a,b = map(int, input().split())
  a_list.append(a)
  b_list.append(b)

atack_damage = max(a_list)
b_list.sort(reverse=True)
#print("b_list",b_list)

throw_damage_list = []

for i in range(N):
  if b_list[i] > atack_damage:
    throw_damage_list.append(b_list[i])
  else:
    break

throw_total_damage = sum(throw_damage_list)
#print("投げダメージ:",throw_damage_list)

if throw_total_damage >= H:
  for i in range(N):
    H -= b_list[i]
    if H <= 0:
      print(i+1)
      break
else:
  H -= throw_total_damage
  #print("残り",H)
  #print("通常攻撃",atack_damage)
  print(len(throw_damage_list) + math.ceil(H/atack_damage))

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

signed main(){
    int n; cin>>n;
    vector<int> h(n,0);  rep(i,n) cin>>h.at(i);
    vector<int> dp(n,0);
    rep(i,n){
        if(i==0) continue;
        else if(i==1) dp.at(i)=abs(h.at(i)-h.at(i-1));
        else{
            dp.at(i)=min(abs(h.at(i)-h.at(i-2))+dp.at(i-2),abs(h.at(i)-h.at(i-1))+dp.at(i-1));
        }
    }
    cout<<dp.back()<<endl;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;

//約数の個数
long long calc(long long N,long long M) {
	long long ret = 1;
	for (long long i = 2; i*i <= N; i++) {
		int m = 0;
		while (N%i == 0) { // 素数で割り切れなくなるまで割っていく
			m++;//割った個数を配列に足す
			N /= i;
		}
		if (0 != m) {
			for (int j = 0;j<m/M;++j) {
				ret *= i;
			}
		}
		if (1 == N) {
			break;
		}
	}
	if (1 != N) {
		for (int j = 0; j < 1 / M; ++j) {
			ret *= N;
		}
	}
	return ret;
}


int main() {
	long long N, P;
	cin >> N >> P;
	long long ans = calc(P,N);
	cout << ans <<  endl;
	return 0;
}


Measured memory_bytes: 3636
n, k = map(int, input().split())
s = input()

tmp = 0
for i in range(len(s)):
    if i == 0:
        if s[i] == 'R' and s[i+1] == 'R':
            tmp += 1
    elif i == len(s) - 1:
        if s[i] == 'L' and s[i- 1] == 'L':
            tmp += 1
    else:
        if s[i] == 'R' and s[i+1] == 'R':
            tmp += 1
        elif s[i] == 'L' and s[i- 1] == 'L':
            tmp += 1

print(min(tmp + 2 * k, n-1))


Measured memory_bytes: 39920
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define MOD 1e9 + 7

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

    string s,t;
    bool o = false;
    int id;

    cin >> s >> t;
    
    if(s.length()<t.length()){ cout << "UNRESTORABLE"; return 0; }

    for(int i = 0;i <= s.length()-t.length();i++)
    {
        bool ok = true;
        for(int j = 0;j < t.length();j++)
        {
            if(s[i+j]==t[j]) continue;
            if(s[i+j]=='?') continue;
            ok = false;
            break;
        }
        if(ok){ o = true; id = i; }
    }

    if(!o) cout << "UNRESTORABLE";
    else
    {
        for(int i = 0;i < id;i++)
        {
            if(s[i]=='?') cout << 'a';
            else cout << s[i];
        }
        for(int i = 0;i < t.length();i++) cout << t[i];
        for(int i = id+t.length();i < s.length();i++)
        {
            if(s[i]=='?') cout << 'a';
            else cout << s[i];
        }
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
const int Q = 1e9 + 7;


inline void add(int &A , int B) {
    A += B;
    if (A >= Q) A -= Q;
}


map< pair<vector<bool>,bool> , int> h[2];

char str[N];

int main() {
    cin >> str;
    int cur = 0 , nxt = 1;
    h[cur][make_pair(vector<bool>(), false)] = 1;

    for (int i = 0 ; str[i] ; ++ i) {
        h[nxt].clear();
        int L = str[i] - '0' , R = str[i] - '0';
        if (str[i] == '?') L = 0 , R = 1;
        // cout << L << ' ' << R << endl;
        for (auto it : h[cur]) {
            //int s = it.first.first.size() + 1;
            for (int j = L ; j <= R ; ++ j) {
                vector<bool> p = it.first.first;
                p.emplace_back(j);
                int s = p.size();
                if (s >= 3 && !(p[s - 3] == 1 && p[s - 2] == 0 && j == 0)) {
                    int q = j + p[s - 3] + p[s - 2];
                    p.pop_back();
                    p.pop_back();
                    p.pop_back();
                    p.push_back(q >= 2);
                    s -= 2;
                }
                add(h[nxt][make_pair(p , it.first.second || (s > 1 && p[0] == 1 && p[1] == 1))] , it.second);
            }
        }
        swap(cur , nxt);
    }
    int res = 0;
    for (auto &it : h[cur]) {

        /*vector<bool> p = it.first.first;
        for (int i = 0 ; i < p.size() ; ++ i) {
            cout << p[i] << ' ';
            } cout << "|  " << it.first.second << ' ' << it.second << endl;*/


        if (it.first.second || it.first.first.size() == 1 && it.first.first[0]) {
            add(res , it.second);
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <numeric>
#include <iomanip>

int main(void) {
	int a, b;

	std::cin >> a >> b;

	std::vector<std::string> v(a);

	for (size_t i = 0; i < a; i++) {
		std::cin >> v[i];
	}

	std::vector<int> x(b), y(a);

	for (size_t i = 0; i < a; i++) {
		if (std::count(v[i].begin(), v[i].end(), '#') != 0) {
			y[i] = 1;
		}
	}

	for (size_t i = 0; i < b; i++) {
		int count = 0;
		for (size_t j = 0; j < a; j++) {
			if (v[j][i] == '#') {
				count++;
			}
		}

		if (count != 0) {
			x[i] = 1;
		}
	}

	for (size_t i = 0; i < a; i++) {
		for (size_t j = 0; j < b; j++) {
			if (y[i] != 0 && x[j] != 0) {
				std::cout << v[i][j];
			}
		}
		if (y[i] != 0)
		std::cout << std::endl;
	}

	return 0;
}

Measured memory_bytes: 256
n = int(input())
m = ["M", "A", "R", "C", "H"]
s = {}
for _ in range(n):
    s_ = input()[0]
    if s_ not in m: continue
    else:
        if s_ not in s.keys():
            s[s_] = 0
        s[s_] += 1
if len(list(s.keys())) <= 2:
    print(0)
    exit()
l = list(s.values())
n = len(l)
a = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            a += l[i] * l[j] * l[k]
print(a)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
const ll MAX = 1001001;
const ll MOD = 1000000007;
ll fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long COM(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main()
{
    ll n;
    cin >> n;
    COMinit();
    ll ans = 0;
    rep2(i, 1, n / 3 + 1)
    {
        ll co = n - i * 3;
        ans = (ans + COM(co + i - 1, i - 1)) % MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 27132
#include<iostream>
using namespace std;
#include<cstdio>
#include<algorithm>
#include<set>
#include<iterator>

struct evp
{
	int y, x_l, x_r;
	int kind;
	bool operator < (const evp &E) const
	{
		if(y != E.y) return y < E.y;
		return kind < E.kind;
	}
};

evp init(int co_y, int co_x_l, int co_x_r, int kd)
{
	evp E;
	E.y = co_y, E.x_l = co_x_l, E.x_r = co_x_r, E.kind = kd;
	return E;
}

int main()
{
	int i, n;
	int x1, y1, x2, y2;
	scanf("%d", &n);
	evp *MG;
	MG = new evp [2 * n];
	int ev_n = 0;

	for(i = 0; i < n; i++){
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		if(y1 != y2){
			if(y1 > y2) swap(y1, y2);
			MG[ev_n] = init(y1, x1, -1, 0);
			MG[ev_n + 1] = init(y2, x2, -1, 2);
			ev_n += 2;
		}else{
			if(x1 > x2) swap(x1, x2);
			MG[ev_n] = init(y1, x1, x2, 1);
			ev_n++;
		}
	}
	sort(MG, MG + ev_n);

	set<int> A;
	int count = 0;

	for(i = 0; i < ev_n; i++){
		switch(MG[i].kind){
			case 0:
				A.insert(MG[i].x_l);
				break;
			case 2:
				A.erase(MG[i].x_l);
				break;
			case 1:
				count += distance(A.lower_bound(MG[i].x_l), A.upper_bound(MG[i].x_r));
				break;
		}
	}
	printf("%d\n", count);
	return 0;
}

Measured memory_bytes: 7064
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}


void MAIN() {
    int N, K;
    scanf("%d%d", &K, &N);

    VI ans;
    if (K == 1) {
	ans.assign((N+1)/2, 1);
    } else if (K % 2) {
	ans.assign(N, (K+1)/2);
	REP (i, N/2) {
	    for (int j=N; j--;) {
		if (ans[j]) {
		    ans[j]--;
		    if (ans[j]) {
			j++;
			while (j<N) {
			    ans[j] = K;
			    j++;
			}
		    }
		    break;
		}
	    }
	}
	while (ans.back() == 0) ans.pop_back();
    } else {
	ans.resize(N);
	ans[0] = K/2;
	for (int i=1; i<N; i++) ans[i] = K;
    }
    rprintf("%d", ans.begin(), ans.end());
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 3456
import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		char c[] = sc.nextLine().toCharArray();
		for(int i = 0; i < Math.pow(2, 3); i++) {
			int c_num[] = {Character.getNumericValue(c[1]), Character.getNumericValue(c[2]), Character.getNumericValue(c[3])};			
			String answer[] = new String[3];
			for(int j = 0; j < 3; j++) {
				if((1 & i >> j) == 1) {
					c_num[j] = -c_num[j];
				}
			}
			if(Character.getNumericValue(c[0]) + c_num[0] + c_num[1] + c_num[2] == 7) {
				for(int k = 0; k < 3; k++) {
					if(c_num[k] >= 0) {
						answer[k] = "+" + c_num[k];
					} else {
						answer[k] = String.valueOf(c_num[k]);
					}
				}
				System.out.println(c[0] + answer[0] + answer[1] + answer[2] + "=7");
				break;
			}
		}
	}
}

Measured memory_bytes: 21844
/*
 *  Lang    : C++
 *  Author  : little_angel
 */
#include <bits/stdc++.h>

using namespace std;
#define int long long
int n;
long double dp[301][301][301];
long double p[301][301][301];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int x, a[] = {0, 0, 0};
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        a[x - 1]++;
    }
    p[a[0]][a[1]][a[2]] = 1;
    for (int three = n; three >= 0; --three) {
        for (int two = n; two >= 0; --two) {
            for (int one = n; one >= 0; --one) {
                if (one + two + three > n || (!one && !two && !three))continue;

                long double p_waste = (long double) (n - (one + two + three)) / n;
                long double ev_waste = p_waste / (1 - p_waste) + 1;
                dp[one][two][three] += ev_waste * p[one][two][three];

                if (one)dp[one - 1][two][three] += dp[one][two][three] * (double) one / (one + two + three);
                if (two)dp[one + 1][two - 1][three] += dp[one][two][three] * (double) two / (one + two + three);
                if (three)dp[one][two + 1][three - 1] += dp[one][two][three] * (double) three / (one + two + three);

                if (one)p[one - 1][two][three] += p[one][two][three] * (double) one / (one + two + three);
                if (two)p[one + 1][two - 1][three] += p[one][two][three] * (double) two / (one + two + three);
                if (three)p[one][two + 1][three - 1] += p[one][two][three] * (double) three / (one + two + three);
            }
        }
    }

    cout << setprecision(10) << dp[0][0][0] << endl;
}

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

int main(int argc, char **argv) {
  int n, k;
  scanf("%d%d", &n, &k);
  if (k >= n) printf("1\n");
  else {
    printf("%d\n", 1 + (n - k + (k - 1) - 1) / (k - 1));
  }
  return 0;
}

Measured memory_bytes: 256