ĐÁ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);

}