ĐÁ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);
}
Các bạn ơi, từ giờ đến khi bắt đầu cuộc thi còn 3 ngày nữa. Mong các bạn sẽ chuẩn bị thật tốt cho cuộc thi. Mình biết rằng tuy thời gian khá gấp những mình vẫn hy vọng rằng các bạn sẽ chuẩn bị thật tốt để đạt được thành tích cao nhất trong cuộc thi này!
Xin chúc tất cả các bạn may mắn!
Ghê quá các pro tin=)))...Mình ủng hộ nhưng mình rút luiii nha=))
Một cuộc thi Tin học, rất đáng được mong chờ đây. Chúc cuộc thi thành công tốt đẹp!
Cuộc thi và giải thưởng hấp dẫn quá, ai kèm 1 : 1 mềnh tin phát :D
Trường mình không có học môn tin thi thố thế nào bây giờ :((
ZỐT NHẤT MÔN TIN HỌC =(((
Em chúc cuộc thi này diễn ra thành công và e cũng xin rút vì e ngu nhất môn tin
kèm em tin đi anh :V
Hay quá bạn mình cũng định ôn thêm về tin học
ok tham gia cũng được
giải thưởng nghe chất qá nhưn mak mik dốt Tin lắm à :( loại ngay từ vòng gửi xe là cái chắc :D
có mấy thanh niên ngu tin mà hack vài giây pay acc facebook luôn :v
Mình ngu Tin quá, ai cho mình ké miếng giỏi để mình tham gia ạ :)))
nếu không có Tin lớp 8 với lớp 11 thì t sẽ suy nghĩ và tham gia =)))
Em chúc cuộc thi diễn ra thành công tốt đẹp ạ
chúc các anh chị thi thật tốt ạ !
a giỏi Tin ko chỉ e vs.
Anh kém tin lắm :v
Chúc mấy bạn thi tốt , mình ở lại cổ vũ , mấy vòng sau mình thêm kiến thức , có cơ hội đồng ý mới vào thi cho chắc
Mỗi 1 kì thi cũng quan trọng lắm chứ đùa , Thi mà rớt thì ..........
Bạn tham gia cho vui nhé
trường toy đang sửa phải qua cơ sở mới ko có phòng tin để thực hành mà phải ngồi nhét lí thuyết vào mồm
tiết sau : thầy hỏi : em nào học bài ròi ?
cả lớp : !!!!! ko ai dơ tay
và câu chuyện cứ tiếp diễn từ HK1 -> HK2
Trường em cũng có khác gì đâu
Đang ôn thi thì thầy nhắn làm bài thi thử 100 câu.
và khi xem kế quả đứa nào cũng 0/100 hết
Cho đến khi học qua zoom .Ông nhắn :''Cho bài không ai ôn hết à , ai đã ôn bài nhưng chưa vào được . Thì giơ tay .
Học sinh ý kiến , thưa thầy bọn em rớt hết lý thuyết rồi ah
Thế thì thi kiểu gì cho đạt , về mỗi đứa ôn tin 3 ngày , xong hết bài mới nghỉ nghe chưa. ..................
like anh Thịnh =)))))
em tham gia cuộc thi nhé Hưng
cái cuộc thi này dùng c++ hoặc pascal đều được nhé em
À, contest kéo dài 5 ngày, vậy chắc ko sao
Sợ kéo dài cỡ 2-3 tiếng thì nát vì có đến 4 Codeforce Rounds trong mấy ngày thi
em đang là đương kim vô địch nha Dương
Anh hy vọng em sẽ bảo vệ thành công ngôi vô địch!
cũng vui đó :))))
Thi ở đâu ạ
Cái link thì đó
Cho em đăng kí với đc ko anh
Bạn tôi tổ chức cuộc thi sao ko nói tôi để tôi hổ trợ bạn củ tôi là information nè
Nguyễn Lê Phước Thịnh CTV