ĐÁP ÁN VÒNG 3 CUỘC THI TIN HỌC LẦN 3
Câu 1(2 điểm) Bài làm của bạn Nguyễn Khánh Tài Huy
var a,b,tg1,tg2,UC: longint;
f1,f2: text;
function tguoc(x: longint): longint;
var i,tg: longint;
begin
tg:=0;
for i:=1 to trunc(sqrt(x)) do
if x mod i = 0 then
begin
tg:=tg+i;
tg:=tg+x div i;
if i*i=x then tg:=tg-i;
end;
exit(tg);
end;
function UCLN(a,b: longint): longint;
begin
if a=0 then exit(b)
else UCLN:=UCLN(b mod a,a);
end;
begin
readln(a);
readln(b);
tg1:=tguoc(a);
tg2:=tguoc(b);
if tg1*b=tg2*a then
begin
UC:=ucln(tg1,a);
tg1:=tg1 div UC;
a:=a div UC;
writeln(tg1);
writeln(a);
end
else writeln(-1);
end.
Câu 2(4 điểm) Bài làm của bạn Trần Nguyễn Đăng Dương
#include <bits/stdc++.h>
using namespace std;
#define div 1000000007
#define arrst {{1,1},{1,0}}
long long x;
void power(long long a[2][2], long long n);
void multi(long long a[2][2], long long b[2][2]);
long long fibo(long long n)
{
long long f[2][2]=arrst;
power(f,n-1);
return f[0][0];
}
void power(long long a[2][2], long long n)
{
if ((n==0) || (n==1)) return;
long long b[2][2]=arrst;
power(a,n/2);
multi(a,a);
if (n%2==1)
multi(a,b);
}
void multi(long long a[2][2], long long b[2][2])
{
long long x = (((a[0][0]%div) * (b[0][0]%div))%div + ((a[0][1]%div) * (b[1][0]%div))%div)%div;
long long y = (((a[0][0]%div) * (b[0][1]%div))%div + ((a[0][1]%div) * (b[1][1]%div))%div)%div;
long long z = (((a[1][0]%div) * (b[0][0]%div))%div + ((a[1][1]%div) * (b[1][0]%div))%div)%div;
long long w = (((a[1][0]%div) * (b[0][1]%div))%div + ((a[1][1]%div) * (b[1][1]%div))%div)%div;
a[0][0]=x; a[0][1]=y; a[1][0]=z; a[1][1]=w;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
long long t; cin>>t;
for (long long i=1;i<=t;i++)
{
cin>>x;
cout<<fibo(x)%div<<endl;
}
}
Câu 3(4 điểm) Bài làm của bạn Trần Nguyễn Đăng Dương
#include <bits/stdc++.h>
using namespace std;
struct ii{
long long a; long long b;
};
vector <ii> arr;
long long n,q;
void del(long long numx, long long numy)
{
long long dem=0;
while ((arr[dem].a!=numx) || (arr[dem].b!=numy)) dem++;
arr.erase(arr.begin()+dem);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>n>>q;
for (long long i=1;i<=n;i++)
{
long long x,y; cin>>x>>y;
arr.push_back({x,y});
}
for (long long i=1;i<=q;i++)
{
long long t,x,y; cin>>t>>x>>y;
if (t==1) arr.push_back({x,y});
else if (t==2) del(x,y);
else
{
long long maxx=INT_MIN, maxy=INT_MIN;
for (long long i=0;i<arr.size();i++)
{
if (arr[i].b==y) maxx=max(maxx,abs(arr[i].a-x));
if (arr[i].a==x) maxy=max(maxy,abs(arr[i].b-y));
}
if ((maxx!=INT_MIN) && (maxy!=INT_MIN))
{
cout<<maxx*maxy/2;
if (maxx*maxy%2!=0) cout<<".5";
cout<<endl;
}
else cout<<0<<endl;
}
}
}
Câu 4(5 điểm) Bài làm của bạn Nguyễn Khánh Tài Huy
#include <cstdio>
#include <cstdlib>
#include <numeric>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 16;
const int MAXL = 1 << 20;
const int inf = 1 << 30;
int n;
char str[MAXN][MAXL];
int cnt[MAXN][26];
int dp[1 << MAXN];
int calc_pref(int mask) {
int len = 0;
int tmp[26];
fill(tmp, tmp+26, inf);
for (int i = 0; i < n; ++i)
if (mask&(1 << i))
for (int j = 0; j < 26; ++j)
tmp[j] = min(tmp[j], cnt[i][j]);
for (int i = 0; i < 26; ++i)
len += tmp[i];
return len;
}
int solve(int mask) {
int &ret = dp[mask];
if (ret != -1) return ret;
int pref = calc_pref(mask);
if ((mask&-mask) == mask) return ret = pref;
ret = inf;
for (int i = (mask - 1) & mask; i > 0; i = (i - 1) & mask) {
int curr = solve(i) + solve(mask ^ i) - pref;
ret = min(ret, curr);
}
return ret;
}
int main (void){
memset(dp, -1, sizeof dp);
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%s", str[i]);
for (int i = 0; i < n; ++i)
for (int j = 0; str[i][j]; ++j)
cnt[i][str[i][j] - 'a']++;
printf("%d\n", solve((1 << n)-1) + 1);
return 0;
}
Câu 5(5 điểm) Bài làm của bạn Trần Nguyễn Đăng Dương
#include <bits/stdc++.h>
using namespace std;
vector <bool> sang(1000000000,true);
vector <long long> snt;
void sangnt(long long x)
{
for (long long i=2;i<=x;i++)
{
if (sang[i])
{
snt.push_back(i);
for (long long j=i;j*i<=x;j++) sang[i*j]=false;
}
}
}
void num(long long input)
{
long long step_count = 1;
long long step_limit = 2;
long long adder = 1;
long long x = 0, y = 0;
for (long long n = 2; n != input + 1; n++,step_count++)
{
if (step_count <= .5 * step_limit) x += adder;
else if (step_count <= step_limit) y += adder;
if (step_count == step_limit)
{
adder *= -1;
step_limit += 2;
step_count = 0;
}
}
cout << x << " " << y;
}
int main()
{
long long n; cin>>n;
sangnt(n);
long long l=0;
while (snt[l]!=n) l++;
l++;
num(l);
}
fan cứng nè
chúc cuộc thi thành công nha
Các bạn tham gia cuộc thi nghiêm túc nha! Chúc các bạn làm bài thật tốt!
chúc mừng nhá
cứng với chả mềm :D
cấm xin coin nữa
1 lần nữa:ko còn là j của nhau
nghe ớn v
Chúc cuộc thi thành công tốt đẹp
Những cuộc thi luôn tạo chúng ta các giác mong chờ đúng ko mọi người :3
nhưng vấn đề là có đủ thông minh để đi thi không
ngu mà ik thi thì thôi đó
Chỉ 3 bạn thoi à :((
ừ
:((