Hướng dẫn giải đề thi UIT Code Contest đợt 17

Bài 1 Trạm vũ trụ ISS

Đề cho góc khuất hai bên bằng nhau ==> tam giác ABC = tam giác ABD, nên từ góc x ta tính được góc ABD (hoặc ABC). Sử dụng định lí sin để tính góc BDA (hoặc BCA).
Sau đó tính được góc A. Sử dụng công thức tính độ dài cung để tính quãng đường mà ISS đi được. Sử dụng công thức t = s/v để tính thời gian quan sát.
Lưu ý: có thể sử dụng hàm sin() và asin() trong thư viện cmath (C++) và chuyển từ góc theo độ thành góc theo radian để tiện xử lí.

Code Mẫu:

#include <iostream>
#include <cmath>
#include <iomanip>
#define R 6400000
#define h 400000
#define v 7706.61
#define PI 3.14159265
using namespace std;

double tinhThoiGian(int goc)
{
double gocRadian = goc * PI / 180;
double gocTrongBu = PI – gocRadian / 2;
double gocTrong2 = asin((R * sin(gocTrongBu)) / (R + h));
double gocQuyDao = (PI – gocTrong2 – gocTrongBu) * 2;
double doDaiCung = R * gocQuyDao;
double thoiGian = doDaiCung / v;
return thoiGian;
}
int main()
{
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}

for (int i = 0; i < n; i++)
{
cout << setprecision(2) << fixed << tinhThoiGian(arr[i]) << ” “;
}

delete[] arr;
return 0;
}

Bài 2 Trò chơi toan tính

Code mẫu:
var a:array[1..1000,1..1001] of double;
n, m, i, j: integer;
f: text;
function Hangkhackhong(i,k: integer): boolean;
var j: integer;
begin
if (k=1) then
begin
j:=1;
while (j<=m) and (round(abs(a[i,j]*10000))/10000=0) do inc(j);
if (j>m) then Hangkhackhong := true
else Hangkhackhong := false;
exit;
end
else
begin
j:=1;
while (j<=m+1) and (round(abs(a[i,j]*10000))/10000=0) do inc(j);
if (j>m+1) then Hangkhackhong := true
else Hangkhackhong := false;
end;
end;
function BacA : integer;
var i, dem: integer;
begin
i:=n;
dem:=0;
while (i<>0) do
begin
if not Hangkhackhong(i,1) then inc(dem);
i:=i-1;
end;
BacA:=dem;
end;
function BacABS : integer;
var i,dem: integer;
begin
i:=n;
dem:=0;
while (i<>0) do
begin
if not Hangkhackhong(i,2) then inc(dem);
i:=i-1;
end;
BacABS:=dem;
end;
procedure PhepKhuGauss;
var i,j,k,max: integer;
t: real;
begin
for i:=1 to n do
begin
max:=i;
for j:=i+1 to n do
if abs(a[j,i])>abs(a[max,i]) then max:=j;
if abs(a[max,i])<>0 then
begin
for k:=i to m+1 do
begin
t:=a[i,k];
a[i,k]:=a[max,k];
a[max,k]:=t;
end;
for j:=i+1 to n do
for k:=m+1 downto i do
a[j,k]:=a[j,k]-a[i,k]*a[j,i]/a[i,i];
end;
end;
end;
begin
readln(n,m);
fillchar(a,sizeof(a),0);
for i:=1 to n do
begin
for j:=1 to m+1 do read(a[i,j]);
readln();
end;
PhepKhuGauss;
if BacA<BacABS then write(0);
if (BacA=BacABS) and (BacA=m) then write(1);
if (BacA=BacABS) and (BacA<m) then write(‘Vo so’);
end.

Bài 3: Đếm cách

Code mẫu:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <sstream>
#include <iostream>
#include <functional>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define forit(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); i++)
#define pb push_back
#define mp make_pair
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef vector <int> vi;
typedef pair <int, int> pii;

int a[11]; // weights
int N;
int prod;

int DP[11][100001*11]; // DP[k][n] is number of ways with k weights of achieving total <= n

#define MOD 1000000007

ll mul_inv(ll a, ll b)
{
ll b0 = b, t, q;
ll x0 = 0, x1 = 1;
if (b == 1) return 1;
while (a > 1) {
q = a / b;
t = b, b = a % b, a = t;
t = x0, x0 = x1 – q * x0, x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}

// Count ways of combining weights to make target of top
ll f(ll top) {
ll total = 0;
int b = top % prod;
ll top2 = top / prod;
// denumerant evaluated at position a.x+b is polynomial of degree at most 10
// so evaluate at 11 points
int last = 10*prod+b; // last location to evaluate
forn(i,last+1)
DP[0][i] = 1; // Consider weight 0 to be of value 1
for(int k=1;k<=N;k++) {
int w=a[k-1];
forn(i,last+1) {
DP[k][i] = (i>=w) ? ((DP[k][i-w] + DP[k-1][i]) % MOD) : DP[k-1][i];
}
}
forn(x,11) {
ll y = DP[N][x*prod+b];
ll den = 1;
forn(i,11) {
if (i==x) continue;
y = y*(((top2-i)+MOD)%MOD)%MOD;
den = den*(((x-i)+MOD)%MOD)%MOD;
}
total = (total + y*mul_inv(den,MOD)%MOD) % MOD;
}
return total;
}

int main(int argc,char *argv[])
{
ll total = 0;
ll L,R;
cin >> N;
prod = 1;
forn(n,N) {
int x,y;
cin >> a[n];
prod *= a[n];
}
cin >> L >> R;
total = (f(R) – f(L-1) + MOD) % MOD;
cout << total << endl;
return 0;
}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *