ĐÁ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);
}
Bản thân mình cũng học chuyên Tin nhưng lại không mạnh về Pascal, thôi thì xem những bạn khác trổ tài vậy :3
anh không mạnh về Pascal thì anh làm c++ cũng được mà
Nghe hay quá cảm ơn đã nới cho tớ biết thi thử lun nếu cậu cũng thi thì chúc cậu thi tốt nhé !! Tick mình nhé hihihi
thôi, ngu tin lắm
tôi chưa qua nổi cấp 2
tạm thời xếp lại :v
Oh thế á, chắc anh chưa đọc kĩ đề :3
Nếu anh có thể làm được bằng c++ thì anh cứ làm
Em sẽ chấm theo đúng như cách khi chấm bài làm bằng Pascal
dùng C++ cũng được anh ạ
P/s: Các bạn lưu ý chỉ được sử dụng 1 trong hai ngôn ngữ lập trình là Pascal hoặc C++ thôi. Không sử dụng ngôn ngữ lập trình nào khác hai ngôn ngữ lập trình này.
ok
chịu òi ngu Tin quá
Ủa môn tin học này có dành cho cấp 2 ko
hmu ngu cả pascal lẫn C++ thì làm kiểu j hỏ
hiện giờ chưa giỏi tin nhưng mà có giỏi cũng chịu , báo lỗi mạng mãi nè
Zậy thì idol hóng cùng tui luôn :3
em ghét nhất môn tin ! đến tiết tin cả lớp em đều chán !
Tuy em ko được nhưng chúc các anh/chị thu tốt
em đợi hóng kết quả 24/24
Anh chuyên nhiều nhỉ? Chuyên Anh, chuyên Toán, chuyên Tin. Đôi khi em thấy anh chuyên Văn nữa vì viết Văn rất là màu mè ._.
( Đồng thời còn chuyên thả thính =))) và chuyên yêu me :v )
từ lp 6 trờ lên bn
Nếu sử dụng thuật toán không phải là tối ưu nhất thì có bị trừ điểm không ạ?
Mk mới lm xong. Mà cx khó thật !!!
ủa mà ông thịnh ở chỗ nào trong khánh hòa thế
Ngoại trừ bài cuối dạng khá khó (mất 1 bảng trắng để nháp) thì 4 bài còn lại khá dễ
Bài 4 brute-force cũng dưới 1 giây được
Thành ra cuối cùng thi Code Golf (viết code ngắn nhất có thể) với một bạn khác, vì thế nên code mình viết sẽ khá khó đọc, sorry ae
cái bài cuối em làm không tốt
chỉ chạy được 1/10 test à
ông sài c++14 hay c++ 17 vậy vì tôi sài hàm trong c++ 17Nguyễn Lê Phước Thịnh CTV
c++ 17 nha ông
Mình ngu code lắm thi không lại mọi người.
mình cũng ngu tin lắm với cả lớp 6 chưa học c++ và pascal
Mình làm trong pascal xong mình copy paste qua phần nộp bài của mình được không
đúng rồi đó
nhưng mà bạn lưu ý làm hết 5 bài trong 1 khung trắng xong rồi nộp nhé, tại vì chỉ cho phép nộp duy nhất 1 lần thôi