راه‌حل‌های مسابقه الگوریتمی Newbies 2018

سلام!

مسابقات الگوریتمی Newbies زمستون هر سال در دانشگاه شهید بهشتی برگزار میشه. سطح سؤالات این مسابقه به نسبت مسابقات رسمی ACM آسون‌تره ولی سبک سؤالات حفظ شده و شرکت توش برای علاقه‌مندان الگوریتم، بچه‌های المپیادی، دانشجوهای ترم اول و دوم و همه کسانی که می‌خوان در مسابقات ACM-ICPC شرکت کنند، می‌تونه جذاب و چالشی باشه.

همون طور که می‌دونید تصمیم گرفتیم مسابقات سال‌های گذشته Newbies رو به‌صورت آنلاین در کوئرا برگزار کنیم تا فرصتی برای تمرین و رقابت باشه. این هفته مسابقه‌ی الگوریتمی Newbies 2018 در کوئرا برگزار شد. این مسابقه در سال ۲۰۱۸ در دانشگاه شهید بهشتی با تلاش «محمدرضا محسنی»، «محمد نصیری‌فر»، «محمدحسن‌پور»، «عرفان علی‌محمدی»، «سامان خامسیان» و «رضا شیری» طراحی و برگزار شده بود.

راه‌حل‌های سؤالات این مسابقه در ادامه توضیح داده شدند. در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات، سؤالات و ابهام‌های خودتون رو مطرح کنید. اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.

A – AbulHassan’s Quest

اگر b \neq 0 آنگاه:

q = \frac{a-r}{b}

پس کافی است چک کنیم که آیا a-r مضرب b هست یا نه و اگر b = 0 آنگاه کافی است چک کنیم a برابر r است یا خیر.

پیچیدگی زمانی:

\mathcal{O}(T)

// In the name of Allah
#include<bits/stdc++.h>

using namespace std;

int main()
{
	int T;
	cin >> T;
	for(int test = 0; test < T; test++)
	{
		int a, b, r;
		cin >> a >> b >> r;
		if(b == 0)
			cout << (a == r?"Yes\n":"No\n");
		else
			cout << ((a-r)%b == 0?"Yes\n":"No\n");
	}
}

//Thank God

B – Farshad’s Research

در ابتدا اندازه‌ی هر مؤلفه همبندی را بدست می‌آوریم (این کار با dfs ،bfs و یا dsu قابل انجام است). و سپس آن‌ها را مرتب شده در آرایه‌ای مثل V ذخیره می‌کنیم. اگر f(x) را تعداد مؤلفه‌ها با سایز کمتر از x بگیریم آنگاه پاسخ برابر f(r+1)-f(l) خواهد بود. همچنین برای محاسبه f(x) از روش جست‌وجوی دودویی کمک می‌گیریم.

پیچیدگی زمانی:

\mathcal{O}(T \times (N + M \log N + Q \log N))

ما برای سادگی پیاده‌سازی از dsu با پیچیدگی زمانی M \log N استفاده می‌کنیم.

// In the name of Allah
#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	int T;
	cin >> T;
	for(int test = 0; test < T; test++)
	{
		int n, m, q;
		cin >> n >> m >> q;
		int head[n], sz[n];
		for(int i = 0; i < n; i++)
			head[i] = i, sz[i] = 1;
		for(int u, v, i = 0; i < m; i++)
		{
			cin >> u >> v;
			u--, v--;
			while(u != head[u])u = head[u];
			while(v != head[v])v = head[v];
			if(u == v)continue;
			if(sz[v] < sz[u])swap(u, v);
			sz[v] += sz[u];
			head[u] = v;
		}
		vector<int> sizes;
		for(int i = 0; i < n; i++)
			if(i == head[i])
				sizes.push_back(sz[i]);
		sort(sizes.begin(), sizes.end());
		for(int l, r, i = 0; i < q; i++)
		{
			cin >> l >> r;
			l = lower_bound(sizes.begin(), sizes.end(), l)-sizes.begin();
			r = upper_bound(sizes.begin(), sizes.end(), r)-sizes.begin();
			cout << r-l << '\n';
		}
	}
}

//Thank God

C – Shortest but Hardest

ادعا می‌کنیم پاسخ برابر کوچک‌ترین عضو آرایه است (آن را از این به بعد m در نظر بگیرید)! مشخصاً زیردنباله‌ای که تنها از m ساخته شده این خاصیت را دارد. حال ثابت می‌کنیم هر زیردنباله‌ای مانند:

A_l, A_{l+1}, \dots , A_r

میانگین هندسی بیشتر مساوی m دارد.

\sqrt[r-l+1]{A_l . A_{l+1} . \cdots . A_r} \ge \sqrt[r-l+1]{m . m . \cdots . m} = m

پیچیدگی زمانی:

\mathcal{O}(T \times n)

// In the name of Allah
#include<bits/stdc++.h>

using namespace std;

int main()
{
	int T;
	cin >> T;
	for(int test = 0; test < T; test++)
	{
		int n;
		cin >> n;
		int A[n];
		for(int i = 0; i < n; i++)
			cin >> A[i];
		cout << *min_element(A, A+n) << ".00" << '\n';
	}
}

//Thank God

D – Divisible Strings

برای حل این سؤال حریصانه عمل می‌کنیم. به این شکل که سعی می‌کنیم بزرگترین k را پیدا کنیم به طوری که با حذف برخی از حروف S حاصل k \times T شود و بدین صورت پاسخ برابر |S| - k \times |T| خواهد بود.

پس باید رشته S به S = s_1, s_2, \dots , s_{k*|T|} تبدیل شود به طوری که:

s_1 = T_1, s_2 = T_2, \dots , s_{|T|+1} = T_1, \dots, s_{|T|\times k} = T_{|T|} 

حال از ابتدای S شروع کرده و آنقدر حرف از ابتدا حذف می‌کنیم تا به s_1 برسیم و بعد از آن دوباره آنقدر حرف حذف می‌کنیم تا به s_2 برسیم و…

پیچیدگی زمانی:

\mathcal{O}(T \times (|S| + |T|))

// In the name of Allah
#include<bits/stdc++.h>

using namespace std;

int main()
{
	int T;
	cin >> T;
	getchar();
	for(int test = 0; test < T; test++)
	{
		string s, t;
		getline(cin, s);
		getline(cin, t);
		int ps = 0, pt = 0, k = 0;
		while(ps < s.size())
		{
			if(s[ps] == t[pt])pt++;
			ps++;
			if(pt == t.size())k++, pt = 0;
		}
		cout << s.size()-k*t.size() << '\n';
	}
}

//Thank God

E – Tennis

برای این سؤال کافی است همه حالات جایگذاری ? را امتحان کنید و در هر حالت معتبر برنده را شناسایی کنید.

پیچیدگی زمانی: منظور از MAX_{length} در اینجا همان 11 است.

\mathcal{O}(T \times MAX_{length} \times 3^{MAX_{length}})

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cassert>

using namespace std;

const int NASIRIFAR = 1;
const int MORTEZA = 2;
const int INVALID = 0;

int pw(int a, int b) {
    int ret = 1;
    for(int i = 0 ;i < b;  i++) {
        ret *= a;
    }
    return ret;
}

string renderSequence(string sequence, const vector<char>& assignments) {
    int assignmentPtr = 0;
    for(int i = 0;i < sequence.size(); i++) {
        if(sequence[i] == '?') {
            sequence[i] = assignments[assignmentPtr];
            assignmentPtr++;
        }
    }
    return sequence;
}

enum State {
    toServe,
    ballInAirServe,
    ballInAir,
    groundOnce,
};

const char RACKET = 'R';
const char GROUND = 'G';
const char NET = 'N';

int otherPlayer(int player) {
    if(player == NASIRIFAR) {
        return MORTEZA;
    }
    return NASIRIFAR;
}

int getResult(const string& sequence) {
    int scores[3] = {0};

    int state = toServe;
    int lastHit = 0;

    for(auto event: sequence) {
        if(state == toServe) {
            if(event != RACKET) {
                return INVALID;
            }
            lastHit = NASIRIFAR;
            state = ballInAirServe;
        } else if(state == ballInAirServe) {
            if(event == RACKET) {
                return INVALID;
            } else if(event == NET) {
                scores[otherPlayer(lastHit)] ++;
                state = toServe;
            } else if(event == GROUND){
                state = groundOnce;
            }
        } else if(state == ballInAir) {
            if(event == RACKET) {
                lastHit = otherPlayer(lastHit);
            } else if(event == NET) {
                scores[otherPlayer(lastHit)] ++;
                state = toServe;
            } else if(event == GROUND){
                state = groundOnce;
            }
        } else if (state == groundOnce) {
            if(event == RACKET) {
                lastHit = otherPlayer(lastHit);
                state = ballInAir;
            } else if(event == NET) {
                return INVALID;
            } else if(event == GROUND){
                state = toServe;
                scores[lastHit]++;
            }
        }
    }

    if(state != toServe) {
        return INVALID;
    }

    if(scores[MORTEZA] >= scores[NASIRIFAR]) {
        return MORTEZA;
    }
    return NASIRIFAR;
}

int main() {
    int t;
    cin >> t;
    assert(t <= 50);
    while(t --) {
        string soundsSequence;
        cin >> soundsSequence;

        assert(soundsSequence.size() <= 11);

        vector<char> choices = {RACKET, GROUND, NET};
        
        int numQuestionMarks = count(soundsSequence.begin(), soundsSequence.end(), '?');
        int numAllSequences = pw(3, numQuestionMarks);

        int numMorteza = 0, numNasirifar = 0;

        for(int coding = 0; coding < numAllSequences; coding++) {
            vector<char> assignments;
            int origCoding = coding;
            for(int i = 0 ;i < numQuestionMarks; i++) {
                assignments.push_back(choices[coding%3]);
                coding /= 3;
            }
            coding = origCoding;
            string renderedSequence = renderSequence(soundsSequence, assignments);
            int result = getResult(renderedSequence);
            if(result == NASIRIFAR) {
                numNasirifar++;
            } else if (result == MORTEZA) {
                numMorteza ++;
            }else {
                // invalid sequence
            }
        }
        assert(numMorteza + numNasirifar >= 0);

        if(numMorteza >= numNasirifar) {
            cout << "Morteza to doost dashtani hasti" << endl;
        } else {
            cout << "Nasirifar to doost dashtani hasti" << endl;
        }
    }
    
    return 0;
}

F – Profiling

این سؤال به چند بخش تقسیم می‌شود (اگر موردی در چند بخش بود بخش با اولویت بالاتر مد نظر است) :
1. اگر n < k آنگاه جواب 0 است.
2. اگر n = k آنگاه جواب 1 است.
3. اگر k = 0 آنگاه fib(0) به اندازه fib(2) صدا زده می‌شود پس می‌توانیم k را 2 در نظر بگیریم.
4. به استقرا می‌توان نشان داد جواب fib(n-k) است. پایه برای n = k و n = k+1 مشخص است (در این دو حالت جواب یک است یعنی همان (fib(0) = fib(1) = 1) و گام هم به آسانی اثبات می‌شود.

پیچیدگی زمانی:

\mathcal{O}(MAX_N + T)

// In the name of Allah
#include<bits/stdc++.h>

using namespace std;

const int mod = 1'000'000'007;
const int N = 100'000 + 5;
int fib[N];

int main()
{
	fib[0] = fib[1] = 1;
	for(int i = 2; i < N; i++)
		fib[i] = (fib[i-1]+fib[i-2])%mod;
	int T;
	cin >> T;
	for(int test = 0; test < T; test++)
	{
		int n, k;
		cin >> n >> k;
		if(k == n)
			cout << 1 << '\n';
		else if(k > n or n < 2)
			cout << 0 << '\n';
		else if(k == 0)
			cout << fib[n-2] << '\n';
		else
			cout << fib[n-k] << '\n';
	}
}

//Thank God

G – IMEI

برای بخش اول سؤال کافی است ۸ رقم اول را چاپ کنید و برای بخش دوم ابتدا sumdigits را طبق دستورالعمل حساب می‌کنیم و حال باقی مانده آن بر ۱۰ را s در نظر بگیرید. اگر s = 0 آنگاه checksum = 0 و در غیر اینصورت checksum = 10-s خواهد بود.

پیچیدگی زمانی:

\mathcal{O}(T)

// In the name of Allah
#include<bits/stdc++.h>

using namespace std;

int main()
{
	int T;
	cin >> T;
	for(int test = 0; test < T; test++)
	{
		string n;
		cin >> n;
		for(int i = 0; i < 8; i++)cout << n[i];
		int sum = 0;
		for(int i = 0; i < n.size(); i++)
		{
			if(i%2 == 0)sum += n[i]-'0';
			else sum += (n[i]-'0')*2/10+(n[i]-'0')*2%10;
		}
		sum %= 10;
		cout << ' ' << (sum == 0?sum:10-sum) << '\n';
	}
}

//Thank God

H – Fall in Love

اگر m عدد اول باشد که تنها کافی است بررسی کنیم m بزرگتر از n هست یا نه.
حال فرض می‌کنیم m اول نباشد. پس:

m = \Pi {p_i}^{q_i} (1 \leq p_i \leq \sqrt m, 0 \leq q_i)

حال اگر n! بر هر یک از {p_i}^{q_i} بخش‌پذیر باشد آنگاه n! بر m بخش‌پذیر خواهد بود. تعداد تکرارهای عامل اول p_i در n! به طریق زیر به دست می‌آید (با استقرا روی n می‌توانید ثابت کنید.) :

count_{p_i} = \sum_{k=1}^{\infty} \frac{n}{{p_i}^k}

پس کافی است چک کنیم آیا تعداد تکرارهای عوامل اول m همیشه در n بزرگتر مساوی هست یا نه.

پیچیدگی زمانی: (N را حداکثر m و n در نظر بگیرید که در سؤال 2^{31} است.)

\mathcal{O}(\sqrt N \log\log\sqrt N + T \times \frac{\sqrt N}{\log\sqrt N} \times \log\log N)

که \sqrt N \log\log\sqrt N پیچیدگی زمانی غربال اعداد برای یافتن اعداد اول است و نیز \frac{\sqrt N}{\log\sqrt N} تعداد اعداد اولی هست که می‌توانند عامل اول m در صورتی که m اول نباشد، باشند.

// In the name of Allah
#include<bits/stdc++.h>

using namespace std;

constexpr int N = 2147483647; // 2^31-1
constexpr int SQN = 31622; // sqrt(N)
bitset<SQN> is_prime;
vector<int> primes;

int main()
{
	is_prime.set(), is_prime.reset(0), is_prime.reset(1);
	for(int i = 0; i < SQN; i++)
		if(is_prime[i])
		{
			primes.push_back(i);
			for(int j = i+i; j < SQN; j += i)
				is_prime.reset(j);
		}

	int T;
	cin >> T;
	for(int test = 0; test < T; test++)
	{
		int n, m, m_copy;
		cin >> n >> m, m_copy = m;
		bool divides = true;
		for(auto p: primes)
		{
			if(p*p > m or !divides)break;
			int cnt_p = 0;
			while (m%p == 0) cnt_p++, m /= p;
			int cnt_n_factorial = 0, n_copy = n;
			while(cnt_n_factorial < cnt_p and n_copy > 0)
				n_copy /= p, cnt_n_factorial += n_copy;
			divides &= (cnt_n_factorial >= cnt_p);	
		}
		if(m > 1 and n < m)divides = false;
		cout << m_copy << (divides?" divides ":" does not divide ") << n << "!\n";
	}
}

//Thank God

I – Lightning Strike

برای حل سوال آن را به ۴ بخش تقسیم می‌کنیم. (با فرض داشتن برخورد) برخورد دو توپ پس از برخورد هر کدام به دیوار باشد یا برخورد هر دو قبل از برخورد به دیوار یا یکی قبل از برخورد به دیوار و دیگری پس از برخورد به دیوار(۲ حالت).

حال عملا مساله به این تبدیل می شود که دو توپ دو بعدی با شعاع ها, مکان ها و سرعت های مختلف داریم آیا اینها به هم برخورد می کنند یا نه(توجه کنید باید معتبر بودن جواب هم چک کنیم که مثلا از دیوار توپ رد نشود.) ؟!

برای اینکار از قضیه سرعت نسبی در فیزیک استفاده می کنیم. یعنی می توانیم فرض کنیم یک توپ ثابت است و فقط یک توپ با سرعتی جدید حرکت می کند. حال می خواهیم چک کنیم که آیا با هم برخورد دارند یا خیر.

می‌دانیم مسیر حرکت مرکز توپ تشکیل یک خط(نیم‌خط یا پاره‌خط در واقع) و مرکز توپ دیگر ساکن است. پس می توانیم با استفاده از فرمول فاصله نقطه از خط کمینه فاصله مرکز آن دو را بدست آوریم(از این پس آن را d در نظر می گیریم). حال اگر d \le R_1 + R_2 پس آنگاه آن ها با هم تماس دارند. همچنین بجای فرمول فاصله نقطه از خط می‌توانید از الگوریتم‌هایی مثل search ternary هم استفاده کنید.

پیچیدگی زمانی:

\mathcal{O}(T)

#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-6;

class Vector;

class Point {
public:
    double x, y;

    Point(double x, double y): x(x), y(y) {
    }

    Point() {
    }

    Point translate(const Vector& v) const ;
};

class Vector {
public:
    double x, y;
    Vector(double x, double y): x(x), y(y) {
    }

    Vector() {
    }

    Vector scale(double factor) const;
    Vector normalize() const;
    double cross(const Vector& o) const;
    Vector opposite() const;
    double length() const;
};

ostream& operator<<(ostream& out, const Point& p) {
    out << "(" << p.x<< ", " << p.y << ")";
    return out;
}

ostream& operator<<(ostream& out, const Vector& v) {
    out << "(" << v.x<< ", " << v.y<< ")";
    return out;
}

class Ball {
    public:
    Ball(const Point& pos, const Vector& displacement, double r, double velocity):
        pos(pos), displacement(displacement.normalize()), r(r), velocity(velocity) {
    }
    Point pos;
    Vector displacement;
    double r;
    double velocity;
    Point posAfter(double t) const;
};

class LinearTrajectory {
public:
    double minTime, maxTime;

    Point start;
    Vector displacement;
    double v;

    Point get(double) const;
    
    LinearTrajectory(double minTime, double maxTime, const Point& start, const Vector& displacement, double v): 
        minTime(minTime), maxTime(maxTime), start(start), displacement(displacement.normalize()), v(v) {
    }

    LinearTrajectory() {
    }

};

vector<LinearTrajectory> trajectories(const Ball& b, const vector<Point>& wall);
double findMin(const LinearTrajectory& l1, const LinearTrajectory& l2);
bool segmentInterLine(const Point& s1, const Point& s2, const Point& l1, const Point& l2);
int sgn(double a);
double dist(const Point& p1, const Point& p2);
double eq(double a, double b);
Vector vectorFromTo(const Point& from, const Point& to);

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

    while(n--) {
        vector<Ball> balls;
        vector<Point> wall;


        for(int i = 0 ;i < 2; i++) {
            double x, y, dx, dy;
            cin >> x >> y >> dx >> dy;
            double velocity, r;
            cin >> velocity >> r;
            balls.push_back(Ball(Point(x, y), Vector(dx, dy).normalize(), r, velocity));
        }

        for(int i = 0 ;i < 2 ; i++) {
            double x, y;
            cin >> x >> y;
            wall.push_back(Point(x, y));
        }

        auto traj0 = trajectories(balls[0], wall);
        auto traj1 = trajectories(balls[1], wall);
        bool hit = false;

        for(auto t0: traj0) {
            for(auto t1: traj1) {
                auto minDist = findMin(t0, t1);
                hit |=  minDist < balls[0].r + balls[1].r;
            }
        }

        if(hit) {
            cout << "Lightning strike" <<endl;
        } else {
            cout << "Not even a spark" <<endl;
        }
    }

    return 0;
}

vector<LinearTrajectory> trajectories(const Ball& b, const vector<Point>& wall) {
    double st = 0;
    double en = 1e12;

    double lo = st, hi = en;
    for(int i = 0 ;i < 1000; i++) {
        double md = (hi + lo)/2;
        if(segmentInterLine(b.pos, b.posAfter(md), wall[0], wall[1])) {
            hi = md;
        } else {
            lo = md;
        }
    }

    
    double timeOfImpact = (hi + lo)/2;
    Point centerOfBallOnImpact = b.posAfter(timeOfImpact);
    Point pointFromWall = wall[0];
    if(eq(dist(pointFromWall, centerOfBallOnImpact), 0)) {
        pointFromWall = wall[1];
    }

    
    Vector vWall = vectorFromTo(centerOfBallOnImpact, pointFromWall);
    Vector vTraj = vectorFromTo(centerOfBallOnImpact, b.pos);
    
    double sineOfDirections = fabs(vWall.cross(vTraj))/(vWall.length() * vTraj.length());
    double displacementNeededInDirOfTraj = sineOfDirections * b.r;
    Point realCenterOfBall = centerOfBallOnImpact.translate(
            vectorFromTo(centerOfBallOnImpact, b.pos).normalize().scale(displacementNeededInDirOfTraj));
    double cosineOfDirections = sqrt(1 - pow(sineOfDirections, 2));
    double mirrorPointDissplacementFactor = dist(realCenterOfBall, centerOfBallOnImpact) * cosineOfDirections * 2;
    
    Vector maybeDirectionToFindMirrorPoint = vectorFromTo(wall[0], wall[1]).normalize();
    Point maybeMirrorPoint = realCenterOfBall.translate(maybeDirectionToFindMirrorPoint.scale(mirrorPointDissplacementFactor));
    if(!eq(dist(maybeMirrorPoint, centerOfBallOnImpact), dist(realCenterOfBall, centerOfBallOnImpact))) {
        maybeDirectionToFindMirrorPoint = maybeDirectionToFindMirrorPoint.opposite();
        maybeMirrorPoint = realCenterOfBall.translate(maybeDirectionToFindMirrorPoint.scale(mirrorPointDissplacementFactor));
    }

    Vector dMirror = vectorFromTo(centerOfBallOnImpact, maybeMirrorPoint).normalize();

    vector<LinearTrajectory> ret;

    double realTimeOfImpact = dist(realCenterOfBall, b.pos)/b.velocity;

    ret.push_back(LinearTrajectory(0, realTimeOfImpact, b.pos, b.displacement, b.velocity));
    if(timeOfImpact < 1e12 - 1) {
        ret.push_back(LinearTrajectory(realTimeOfImpact, en, realCenterOfBall, dMirror, b.velocity));
    }

    return ret;
}

double findMin(const LinearTrajectory& l1, const LinearTrajectory& l2) {
    double lo = min(l1.minTime, l2.minTime);
    double hi = max(l1.maxTime, l2.maxTime);

    for(int i = 0 ;i< 1000; i++) {
        if(lo > hi) {
            return 1231231231.0;
        }
        double oneThird = lo + (hi - lo)/3;
        double twoThirds = lo + 2*(hi - lo)/3;
        if(dist(l1.get(oneThird), l2.get(oneThird)) < dist(l1.get(twoThirds), l2.get(twoThirds))) {
            hi = twoThirds;
        } else {
            lo = oneThird;
        }
    }
    return dist(l1.get((hi + lo)/2), l2.get((hi + lo)/2));
}

bool segmentInterLine(const Point& s1, const Point& s2, const Point& l1, const Point& l2) {
    return sgn(vectorFromTo(s1, l1).cross(vectorFromTo(s1, l2))) != sgn(vectorFromTo(s2, l1).cross(vectorFromTo(s2, l2)));
}

double dist(const Point& p1, const Point& p2) {
    return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

double eq(double a, double b) {
    return fabs(a - b) < eps;
}

int sgn(double a) {
    if(a < 0) {
        return -1;
    } else if(a > 0) {
        return 1;
    }
    return 0;
}

Vector vectorFromTo(const Point& from, const Point& to) {
    return Vector(to.x - from.x, to.y - from .y);
}

Point Ball::posAfter(double t) const {
    return pos.translate(displacement.scale(t * velocity));
}

Point Point::translate(const Vector& v) const {
    return Point(x + v.x, y + v.y);
}

Vector Vector::scale(double factor) const {
    return Vector(factor * x, factor * y);
}

Point LinearTrajectory::get(double t) const {
    double dt = t - minTime;
    return start.translate(displacement.scale(dt * v));
}

Vector Vector::normalize() const {
    double len = dist(Point(0, 0), Point(x, y));
    return Vector(x/len, y/len);
}

Vector Vector::opposite() const {
    return Vector(-x, -y);
}

double Vector::cross(const Vector& o) const {
    return x * o.y - y * o.x;
}

double Vector::length() const {
    return dist(Point(x, y), Point(0, 0));
}

J – Jitter Minimization

اول آرایه را مرتب می‌کنیم پس از این به بعد داریم:

a_1 < a_2 < \dots < a_{2 \times N} 

حال اگر عددی مثل dis وجود داشته باشد که پاسخ مسئله باشد آنگاه dis برابر a_x - a_1 نیز هست که حتی می‌توان به آسانی نشان داد 2 \leq x \leq N+1. پس به ازای همه حالات ممکن برای dis چک می‌کنیم که آیا معتبر هست یا نه. که این کار را می‌توان حریصانه انجام داد هر بار کوچکترین عضو جفت نشده را در نظر گرفت و با dis به علاوه آن جفت کرد. اگر همچین عضوی وجود نداشت پس آن dis نامعتبر است.

پیچیدگی زمانی:

\mathcal{O}(T \times (N \log N + N \times N \log N))

// In the name of Allah
#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	while(true)
	{
		int N;
		cin >> N;
		if(N == 0) return 0;
		int A[2*N];
		bool paired[2*N];	
		for(int i = 0; i < 2*N; i++)
			cin >> A[i];
		sort(A, A+2*N);
		for(int i = 1; ; i++)
		{
			if(i == N+1)
			{
				cout << "Unreliable Network\n"; 
				break;
			}
			int dis = A[i]-A[0];
			memset(paired, 0, sizeof(paired));
			int p = 0, l = 0;
			while (l < 2*N)
			{
				paired[l] = true;
				auto it = lower_bound(A, A+2*N, dis+A[l]);
				if(it == A+2*N or *it != dis+A[l])break;
				paired[it-A] = true;
				while(l < 2*N and paired[l])l++;
				p++;
			}
			
			if(p == N)
			{
				cout << dis << '\n';
				break;
			}
			
		}
	}	
}

//Thank God

K – Traffic Lights

برای حل سؤال از روش برنامه‌نویسی پویا استفاده می‌کنیم.

ما dp[i][0] را که (1 \leq i \leq n) را تعداد بیشینه روز‌های انتخابی بین روز ۱ تا i در حالتی که آخرین روز سبز انتخاب کرده باشیم، در نظر می‌گیریم. dp[i][1] برای زرد و dp[i][2] برای قرمز به طور مشابه تعریف می‌شود. پاسخ مسئله برابر بیشینه dp[n][x] خواهد بود که 0 \leq x \leq 2.
برای پایه قرار می‌دهیم dp[0][0] = dp[0][1] = dp[0][2] = 0 و نیز برای به‌روز‌رسانی دیپی اگر مثلاً روز iـام سبز باشد داریم:

dp[i][0] = max(dp[i-1][0], dp[i-1][2])+1

و نیز اگر روز iـام سبز نباشد داریم:

dp[i][0] = dp[i-1][0]

و به طور مشابه برای زرد وقرمز نیز چنین است.

پیچیدگی زمانی:

\mathcal{O}(T \times N)

// In the name of Allah
#include<bits/stdc++.h>

using namespace std;

int main()
{
	int T;
	cin >> T;
	for(int test = 0; test < T; test++)
	{
		int n;
		cin >> n;
		string s;
		cin >> s;
		int dp[n+1][3];
		dp[0][0] = dp[0][1] = dp[0][2] = 0;
		for(int i = 0; i < n; i++)
		{	
			dp[i+1][0] = dp[i][0];
			dp[i+1][1] = dp[i][1];
			dp[i+1][2] = dp[i][2];
			if(s[i] == 'G')dp[i+1][0] = max(dp[i][0],dp[i][2])+1;
			else if(s[i] == 'Y')dp[i+1][1] = max(dp[i][0],dp[i][1])+1;
			else dp[i+1][2] = max(dp[i][1],dp[i][2])+1;
		}
		cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << '\n';
	}
}

//Thank God

L – Your House Have Ant

نکته سؤال این است که می‌توانید فرض کنید راهرو تنگی وجود ندارد و مورچه‌ها آزادانه در جهت دلخواه حرکت می‌کنند! پس صرفاً کافیست به ازای هر مورچه مسافتی را که باید طی کند تا از تونل خارج شون را با هم جمع کنید.

پیچیدگی زمانی:

\mathcal{O}(T \times |S|)

#include <bits/stdc++.h>

using namespace std;

int t;
string s;

int main()
{
	cin >> t;
	while (t--)
	{
		cin >> s;
		int ans = 0;
		int l = s.size();
		for (int i = 0; i < l; i++)
			if (s[i] == '<')
				ans += i;
			else if (s[i] == '>')
				ans += l - i - 1;
		cout << ans << endl;
	}
	return 0;
}

M – Concert

در ابتدا فرض می‌کنیم جواب -1 نباشد (حالتی که جواب -1 است به سادگی به دست می‌آید).
حال می‌دانیم جواب مسئله(K_مین عدد اول‌دوست) در مبنای ۳ کمتر از M = 30 > \frac{log(10^{13})}{log(3)} رقم دارد و همچنین جمع ارقام آن کمتر از S \le 2 \times M = 30 خواهد بود.
حال به کمک رابطه بازگشتی جواب را محاسبه می‌کنیم. برای اینکار به تابع

 f(K, CntDigits, Before) 

نیاز داریم که برای ما محاسبه کند که K_مین عدد شبه‌اول‌دوست که حداکثر CntDigits رقم در مبنای ۳ دارد، کدام است. به عددی شبه‌اول‌دوست می‌گوییم که جمع ارقامش به‌علاوه Before عددی اول شود. توجه کنید که اگر Before = 0 آنگاه ما K_مین عدد اول‌دوست را خواهیم داشت. پس f(K, M, 0) جواب مسئله خواهد بود.

همچنین ما برای حل مسئله به

cnt[i][j] (0 \leq i \leq M, 0 \leq j \leq S) 

که تعداد اعداد حداکثر i رقمی (قاعدتاً در مبنای ۳) با جمع ارقام j را می‌شمارد، نیاز داریم که طریق به دست آوردن آن به شرح زیر است:

cnt[0][0] = 1, cnt[i][j] = cnt[i-1][j] + cnt[i-1][j-1] + cnt[i-1][j-2]

برای محاسبه f(K, CntDigits, Before) ما هر بار تلاش می‌کنیم مقدار باارزش‌ترین رقم جواب را مشخص کنیم. به طور دقیق‌تر فرض کنید تعداد اعداد شبه‌اول‌دوست در حالی که پرارزش‌ترین رقم 0 است x, 1 است y و 2 است z باشد. حال اگر 0 \le K \le x آنگاه پرارزش‌ترین رقم 0 و اگر x < K \le x+y پر‌ارزش‌ترین رقم 1 و اگر x+y < K \le x+y+z پر‌ارزش‌ترین رقم 3 خواهد بود (درغیر این‌صورت جواب -1 است).

برای اینکه بدانیم چند عدد شبه‌اول‌دوست با پرارزش‌ترین رقم w داریم کافی است عبارت زیر را حساب کنیم:

 \sum_{p_i \in P} cnt[CntDigits-1][p_i-w-before] 

که منظور از P مجموعه اعداد اول بین 0 تا S است.

حال جواب بدین شکل بدست می‌آید:

w=0: f(K, CntDigits, before) = f(K, CntDigits-1,before)

w=1: f(K, CntDigits, before) = 3^{CntDigits-1}+f(K-x, CntDigits-1,before+1)

w=2: f(K, CntDigits, before) = 2*3^{CntDigits-1}+f(K-x-y, CntDigits-1,before+2)

پیچیدگی زمانی:

\mathcal{O}(\log {MAX_N}^2 + T \times \log MAX_N \times \frac{\log {MAX_N}}{\log \log MAX_N})

که \log {MAX_N}^2 برای محاسبه cnt[i][j] و \frac{\log {MAX_N}}{\log \log MAX_N}) نماینده تعداد اعداد اول 1 تا \log MAX_N است.

// In the name of Allah
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N = 30; // N = MAX_DIGIT_IN_BASE_3
vector<ll> primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
ll dp[N][N*2], n, k, ans;

ll Find(ll k, ll digit, ll before)
{
	if(digit == -1)
		return 0;
	ll last_sum = 0, sum = 0;
	for(ll d = 0; d < 3; d++)
	{
		for(auto p: primes)if(p >= d+before)
			sum += dp[digit][p-d-before];
		if(sum >= k)
			return d*pow(3, digit)+Find(k-last_sum, digit-1, before+d);
		last_sum = sum;
	}
	return -1LL;
}

int main()
{
	memset(dp, 0, sizeof(dp));
	dp[1][0] = dp[1][1] = dp[1][2] = 1;
	for(int i = 0; i < N; i++)dp[i][0] = 1;
	for(int i = 0; i < N; i++)dp[i][1] = i;
	for(int i = 2; i < N; i++)
		for(int j = 2; j < 2*N; j++)
			dp[i][j] = dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2];
	
	int T;
	cin >> T;
	for(int test = 0; test < T; test++)
	{
		cin >> n >> k;
		ans = Find(k, N-1, 0);
		if(ans > n)
			ans = -1;
		cout << ans << '\n';
	}
}

//Thank God

امیدورام راه‌حل‌ها مفید بوده باشه. اگر پیشنهاد یا سؤالی داشتین، حتماً در نظرات مطرح بفرمایید.