این مسابقه در سال ۲۰۱۳ در «دانشگاه شهید بهشتی» برگزار شده است. تیم طراحان این مسابقه «امین کریمی»، «فتا لواسانی»، «فرزاد شربافیان»، «احسان فرج‌زاده»، «مهرداد عرب‌پور»، «محسن سجادی‌تبار»، «علی طاهری» و «امیرحسین شاپوری» بودند.
با توجه به اینکه در آخرین اتاق موبایل را پیدا می‌کنیم، پس باید N اتاق را بگردیم و N-1 بین اتاق‌ها حرکت کنیم. پس پاسخ برابر N \times t_1 + (N-1)\times t_2\space هست.
پیچیدگی زمانی:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tc, N, t1, t2;
cin >> tc;
while(tc--)
{
cin >> N >> t1 >> t2;
cout << N*t1+(N-1)*t2 << '\n';
}
return 0;
}
کافیست هر بار عدد را به توان دو رسانده و معکوس آن را چاپ کنیم.
پیچیدگی زمانی:
#include <bits/stdc++.h>
using namespace std;
int main()
{
while(true)
{
string s = "";
cin >> s;
if(s == "")break;
string t = to_string(stol(s)*stol(s));
reverse(t.begin(), t.end());
cout << t << '\n';
}
return 0;
}
هنگامی که دو کره با شعاع برابر داریم، هرکدام نیمی از کره دیگر را می‌تواند ببیند. به عبارتی نیمکره‌های بین صفحات عمود بر پاره‌خط واصل دو مرکز کره قابلیت دیده شدن دارند. از آنجا که مختصات کره‌ها دو بعدی هستند یعنی مرکز همه روی صفحه واحد قرار دارد، می‌توان فرض کرد با تعدادی دایره در صفحه مواجه هستیم و حال می‌دانیم:
نسبت محیط پنهان دایره به محیط کل دایره برابر نسبت مساحت پنهان کره به کل کره است
حال کافی است برای هر کره نقاط پنهان روی استوا آن را حساب کرده و جواب را به کمک رابطه بالا محاسبه کنیم. لازم به ذکر است مساحت کره از رابطه زیر بدست می‌آید:
S = 4 \times \pi \times R^2
پیچیدگی زمانی:
\mathcal{O}(T \times N \times N \times \log(N))#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
inline ld front(ld degree){return (degree >= 180? degree-180: degree+180);}
inline ld dis(ld x1, ld y1, ld x2, ld y2){return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}
inline ld rad_to_deg(ld x){return x/2/M_PI*360;}
inline ld Seen(ld x1, ld y1, ld x2, ld y2)
{
if(y1 > y2)
return front(Seen(x2, y2, x1, y1));
ld R = dis(x1, y1, x2, y2), D = dis(x1+R, y1, x2, y2);
return rad_to_deg(asin(D/2/R)*2);
}
inline ld solve()
{
int n;
ld r, ans = 0;
cin >> n >> r;
int x[n], y[n];
for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
vector<ld> seen[n];
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
{
ld degree = Seen(x[i], y[i], x[j], y[j]);
seen[i].push_back(degree);
seen[j].push_back(front(degree));
}
for(int i = 0; i < n; i++)
{
sort(seen[i].begin(), seen[i].end());
ld unvisible_degree = 0;
for(int j = 0; j < n-2; j++)
unvisible_degree += max((ld)0, seen[i][j+1]-seen[i][j]-180);
unvisible_degree += max((ld)0, (-seen[i].back()+360)+seen[i].front()-180);
ans += M_PI*4*r*r*unvisible_degree/360;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int tc;
cin >> tc;
for(int i = 1; i <= tc; i++)
cout << "Case #" << i << ": " << fixed << setprecision(3) << solve() << '\n';
return 0;
}
با توجه به رابطه داده شده، اول p را بدست می‌آوریم. حال با توجه به صورت مسئله، پاسخ قسمت دوم برابر 8 \times p - {h}' \times (b-1) است.
پیچیدگی زمانی:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tc, m, t, b, hp, p;
cin >> tc;
while(tc--)
{
cin >> m >> t >> b;
hp = m/t;
p = ceil(1.0*m*b/t/8);
cout << p << ' ' << 8*p-hp*(b-1) << '\n';
}
return 0;
}
برای حل سؤال کافی است آرایه‌ای از میزان بدهی و طلبکاری هرکس داشته باشید و آن را با پردازش هر خط به‌روزرسانی کنید.
پیچیدگی زمانی:
\mathcal{O}(T \times L \times N \times \log(L\times N))#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define mp make_pair
#define L(s) (int)((s).size())
#define all(c) (c).begin(), (c).end()
void printName(const string & name) {
cout << char(toupper(name[0]));
for (int i = 1; i < L(name); i++)
cout << name[i];
}
void make_valid(string & name) {
for (int i = 0; i < L(name); i++)
if (isalpha(name[i]) && isupper(name[i]))
name[i] = tolower(name[i]);
}
map<string, int> money;
void end_testcase() {
static int tc = 0;
cout << "Case #" << ++tc << ":" << endl;
vector<pair<string, int> > dept, cred;
for (map<string,int>::iterator it = money.begin(); it != money.end(); it++)
if (it->second > 0)
cred.push_back(*it);
else if (it->second < 0)
dept.push_back(*it);
cout << "Debtors:" << endl;
for (int i = 0; i < L(dept); i++) {
printName(dept[i].first);
cout << " owes " << -dept[i].second << " Tomans." << endl;
}
cout << "Creditors:" << endl;
for (int i = 0; i < L(cred); i++) {
printName(cred[i].first);
cout << " paid " << cred[i].second << " Tomans." << endl;
}
money.clear();
}
int main () {
int l;
while (cin >> l) {
while (l--) {
string buyer, temp;
int cost, n;
cin >> buyer >> cost >> n;
make_valid(buyer);
money[buyer] += cost;
cost /= n;
while (n-- && cin >> temp) {
make_valid(temp);
money[temp] -= cost;
}
}
end_testcase();
}
return 0;
}
برای حل این سؤال از روش برنامه‌نویسی پویا استفاده می‌کنیم. dp[i] را این چنین تعریف می‌کنیم: «حداقل میزان خستگی در راه رسیدن به iمین هتل»
مشخصاً dp[n] جواب مسئله است و برای محاسبه dp[i] کافی است روی آخرین هتل متوقف شده قبل از i حالت‌بندی کنیم.
پیچیدگی زمانی:
\mathcal{O}(T \times N^2)راه دیگر این سؤال که به مراتب کندتر از این راه است مشخص کردن زیرمجموعه‌ای از هتل‌هاست که قرار است به استراحت در آن بپردازیم که پیچیدگی زمانی آن
\mathcal{O}(T \times N \times 2^N)#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
int A[n], dp[n+1];
for(int i = 0; i < n; i++)
cin >> A[i];
dp[0] = 0;
for(int i = 1; i <= n; i++)
{
dp[i] = abs(A[i-1]-144);
for(int j = 1; j < i; j++)
dp[i] = min(dp[i],dp[j]+abs(A[i-1]-A[j-1]-144));
}
cout << dp[n] << '\n';
}
return 0;
}
اول ثابت می‌کنیم پاسخ پیشوند یا پسوندی از اعداد است. فرض خلف این است که جواب بازه [L, R] باشد به طوری که L > 1 و R < N. حال ضرب اعداد قبل از L را a و ضرب اعداد بعد از R را b در نظر بگیرید. اگر یکی از این دو مثبت باشد می‌توانستیم بازه با ضرب بزرگ‌تری داشته باشیم و در غیر اینصورت (هر دو منفی باشند) می‌توانستیم بازه [1, N] را خروجی دهیم. پس پاسخ پیشوند یا پسوند دنباله است.
همچنین به‌سادگی می‌تون نشان داد پاسخ بلندترین پیشوند با ضرب اعداد مثبت یا بلندترین پسوند با ضرب اعداد مثبت است.
برای پیاده‌سازی در زبان‌هایی که اعداد محدودیت دارند مانند C++ می‌توان از رابطه زیر استفاده کرد.
a_L \times a_{L+1} \times \dots \times a_R = 10^{\log_{10}(a_L)+\log_{10}(a_{L+1})+\dots+\log_{10}(a_R)}و به‌جای مقایسه ضرب اعداد یک بازه جمع لگاریتم آنها را با هم مقایسه کرد.
راه دیگر هم بهره‌گیری از محدودیت سؤال است که گفته شده از هر ۱۰ عدد متوالی حداقل ۱ عدد منفی است. پس بزرگترین پسوند و پیشوند با ضرب اعداد نامنفی, حداکثر ۱۰ عضو ندارند و خب هرکدام که ضرب اعدادی که ندارند کمتر باشد (از نظر اندازه) پاسخ مسئله است.
پیچیدگی زمانی:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
int A[n];
for(int i = 0; i < n; i++)
cin >> A[i];
if(n == 1)
{
cout << "1 1\n";
continue;
}
bool prefix_negative = false, suffix_negative = false;
double prefix = 0, suffix = 0;
pair<double, int> prefix_max, suffix_max;
for(int i = 0; i < n; i++)
{
prefix_negative ^= (A[i] < 0);
prefix += log2(abs(A[i]));
if(!prefix_negative)
prefix_max = {prefix, i};
}
for(int i = n-1; i >= 0; i--)
{
suffix_negative ^= (A[i] < 0);
suffix += log2(abs(A[i]));
if(!suffix_negative)
suffix_max = {suffix, i};
}
if(suffix_max.first > prefix_max.first)
cout << suffix_max.second+1 << ' ' << n << '\n';
else
cout << 1 << ' ' << prefix_max.second+1 << '\n';
}
return 0;
}
ابتدا ما مسئله را برای d = n حل می‌کنیم. یعنی قیمت‌های اولیه ممکن باتری را حساب می‌کنیم. سپس با داشتن آن بازه قیمتی در هر روزی به‌سادگی قابل محاسبه است.
برای محاسبه کمترین و بیشترین قیمت اولیه ممکن از روش جستوجوی دودویی کمک می‌گیریم. هر بار فرض می‌کنیم اگر قیمت اولیه x باشد، قیمت نهایی بیشتر از p است یا کمتر از آن و بدین طریق کمینه و بیشینه مقدار اولیه ممکن را می‌یابیم.
پیچیدگی زمانی:
\mathcal{O}(T \times N \times \log(P))#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, p, b, d;
vector<ll> rate;
inline ll round(double x, ll b)
{
if(fmod(x,b)*2 >= b)
return x-fmod(x,b)+b+0.00001;
return x-fmod(x,b)+0.00001;
}
inline ll after(ll x, ll cnt = n)
{
for(int i = 0; i < cnt; i++)
if(rate[i+1] > rate[i])
x = round(1.00*x*rate[i+1]/rate[i],b);
return x;
}
inline ll Low()
{
ll mid, l = 0, r = 5000000;
while(l+1 < r)
{
mid = (l+r)/2;
if(after(mid) >= p)r = mid;
else l = mid;
}
return r;
}
inline ll Upp()
{
ll mid, l = 0, r = 5000000;
while(l+1 < r)
{
mid = (l+r)/2;
if(after(mid) <= p)l = mid;
else r = mid;
}
return l;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
while(true)
{
cin >> n >> p >> b >> d;
if(max(max(n,p),max(b,d)) == 0)
break;
rate.resize(n+1);
for(auto &u: rate)
cin >> u;
ll l = Low(), r = Upp();
cout << after(l,n-d) << ' ' << after(r,n-d) << '\n';
}
return 0;
}
گرافی از روی جدول می‌سازیم به‌طوری که رأس‌های آن خانه‌های خالی (شامل تونل) باشند و یال‌ها بین خانه‌های مجاور و سپس با الگوریتم جست‌و‌جو اول سطح(BFS) می‌توان فاصله هر تونل از شیر و مهرداد را پیدا کرد. (توجه کنید گراف شیر کمی متفاوت است چرا که می‌تواند از روی فنس‌ها بپرد و یال‌های بیشتری گرافش دارد.)
پیچیدگی زمانی:
\mathcal{O}(T \times N \times M)#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define pB push_back
#define mP make_pair
#define X first
#define Y second
const int maxn=2*100000+10, MOD=1000*1000*1000+7, INF=1000*1000*1000;
pii dir[]={pii(0, 1), pii(1, 0), pii(0, -1), pii(-1, 0)};
string board[500];
int n, m;
bool inRange(pii cur){
return (cur.X>=0 && cur.X<n && cur.Y>=0 && cur.Y<m);
}
bool canGo(pii cur){
if(inRange(cur)){
char ch=board[cur.X][cur.Y];
if(ch=='M' || ch=='.' || ch=='L' || ch=='O')
return true;
}
return false;
}
pii operator + (const pii a, const pii b){
return pii(a.X+b.X, a.Y+b.Y);
}
int color[555][555];
int curcolor;
vector <pair<pii, int> > BFS(pii start, bool Mehrdad){
queue <pair<pii, int> > Q;
Q.push(mP(start, 0));
curcolor++;
vector <pair <pii, int> > candid;
while(!Q.empty()){
pair<pii, int> temp=Q.front();
Q.pop();
if(board[temp.X.X][temp.X.Y]=='O')
candid.pB(temp);
for(int i=0;i<4;i++){
pii nx(temp.X+dir[i]);
int delta=0;
if(inRange(nx) && board[nx.X][nx.Y]=='+' && !Mehrdad){
nx=nx+dir[i];
delta++;
}
if(canGo(nx) && color[nx.X][nx.Y]!=curcolor){
color[nx.X][nx.Y]=curcolor;
Q.push(mP(nx, temp.Y+1+delta));
}
}
}
return candid;
}
pii getTunnel(vector <pair< pii, int> > M, vector <pair< pii, int> > L){
pii ans(INF, INF);
for(int i=0;i<M.size();i++){
bool flag=false;
for(int j=0;j<L.size();j++){
if(M[i].X==L[j].X){
flag=true;
if(M[i].Y<L[j].Y && M[i].X<ans)
ans=M[i].X;
break;
}
}
if(!flag && M[i].X<ans)
ans=M[i].X;
}
return ans;
}
int main(){
int t, tt=1;
cin >> t;
while(t--){
cin >> n >> m;
for(int i=0;i<n;i++)
cin >> board[i];
pii M, L;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(board[i][j]=='M')
M=pii(i, j);
else if(board[i][j]=='L')
L=pii(i, j);
vector <pair <pii, int> > me, li;
me=BFS(M, true);
li=BFS(L, false);
pii ans=getTunnel(me, li);
cout << "Case " << tt++ << ": ";
if(ans.X!=INF)
cout << ans.X+1 << ' ' << ans.Y+1 << endl;
else
cout << "good bye my dear good friend :(" << endl;
}
return 0;
}
با توجه به اینکه گوشه‌های کیک ساعتگرد داده شده برای این سؤال کافیست یکی یکی نقاط را پیمایش کنیم و بررسی کنیم که هر بار به راست پیچیده‌ایم یا نه (اگر حتی یک مورد هم راستگرد نباشد یعنی کیک خورده شده است!)
برای چک کردن اینکه دو ضلع پشت هم راستگرد هستند یا نه از ضرب خارجی دوبردار و قانون دست راست کمک می‌گیریم. برای جزئیات بیشتر می‌توانید کد راه‌حل را مورد بررسی قرار دهید.
پیچیدگی زمانی:
#include <bits/stdc++.h>
using namespace std;
inline int cross(int x1, int y1, int x2, int y2){return x1*y2-x2*y1;}
inline bool clockwise(int x1, int y1, int x2, int y2, int x3, int y3)
{
return (cross(x3-x2,y3-y2,x2-x1,y2-y1) > 0);
}
inline bool eaten()
{
int M;
cin >> M;
int X[M], Y[M];
for(int i = 0; i < M; i++)
cin >> X[i] >> Y[i];
for(int i = 0; i < M; i++)
if(!clockwise(X[i], Y[i], X[(i+1)%M], Y[(i+1)%M], X[(i+2)%M], Y[(i+2)%M]))
return true;
return false;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int N;
cin >> N;
for(int i = 1; i <= N; i++)
cout << "Case " << i << ": " << (eaten()?"YES":"NO") << '\n';
return 0;
}
امیدورام راه‌حل‌ها مفید بوده باشه. اگر پیشنهاد یا سؤالی داشتین, حتماً در نظرات مطرح بفرمایید. موفق و مؤید باشید.
شایان ضیایی
