ĐÁ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);
}
Trong tình huống đó em sẽ cảm thấy hơi buồn, vì bạn đó không thẳng thắn trao đổi về những khuyết điểm của em mà thay vào đó lại đi nói xấu. Trong hoàn cảnh như vậy, em sẽ đọc kĩ để thấy những điểm yếu, điểm sai của bản thân để khắc phục. Nếu là những tin nhắn ác ý nhằm bôi xấu bản thân, thì em sẽ không quan tâm đến những lời nói đó để bản thân không phải buồn hay phiền vì những lời nói đó. Và em sẽ nhắn lại với người bạn đã chụp màn hình đó lời cảm ơn, vì đã giúp bản thân thấy được những điều thiếu sót mà cá nhân không nhận ra. Có thể trong hoàn cảnh này, một số bạn sẽ tức giận, hoặc có thể là nói xấu ngược lại người bạn đã nói xấu mình, điều đó là không nên. Nếu có thấy được những khuyết điểm của nhau, hay điểm yếu thì hãy thẳng thắn chia sẻ với đối phương, đừng lấy nó làm nội dung của một cuộc trò chuyện vì nó sẽ hạ thấp bản thân mình.
Trong tình huống đó em sẽ cảm thấy hơi buồn, vì bạn đó không thẳng thắn trao đổi về những khuyết điểm của em mà thay vào đó lại đi nói xấu. Trong hoàn cảnh như vậy, em sẽ đọc kĩ để thấy những điểm yếu, điểm sai của bản thân để khắc phục. Nếu là những tin nhắn ác ý nhằm bôi xấu bản thân, thì em sẽ không quan tâm đến những lời nói đó để bản thân không phải buồn hay phiền vì những lời nói đó. Và em sẽ nhắn lại với người bạn đã chụp màn hình đó lời cảm ơn, vì đã giúp bản thân thấy được những điều thiếu sót mà cá nhân không nhận ra. Có thể trong hoàn cảnh này, một số bạn sẽ tức giận, hoặc có thể là nói xấu ngược lại người bạn đã nói xấu mình, điều đó là không nên. Nếu có thấy được những khuyết điểm của nhau, hay điểm yếu thì hãy thẳng thắn chia sẻ với đối phương, đừng lấy nó làm nội dung của một cuộc trò chuyện vì nó sẽ hạ thấp bản thân mình.