ĐÁ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);
}
Chúc mừng các em đạt giải nha!
Thịnh lập danh sách trên google sheet or execel rồi gửi thầy Thọ (Ghi tên tài khoản, link tài khoản, tên giải, phần thưởng) nha em!
Chúc mừng các bạn nha! Congratulations!