Dreptunghiul ABCD are laturile de lungimi w şi h, numere naturale pare. Acest dreptunghi este desenat pe o foaie de matematică şi este descompus în w ∙ h pătrate de latură 1. Vârfurile A, B, C şi D sunt plasate în colţurile unor pătrate de latură 1. Se alege un punct P din interiorul dreptunghiului ABCD, situat în colţul unui pătrat de latură 1 şi se uneşte prin segmente de dreaptă cu cele patru colţuri ale dreptunghiului. Unele segmente intersectează pătrate de latură 1 în exact două puncte distincte, altele într-un singur punct.
Numim pătrat 2-intersectat, un pătrat de latură 1 intersectat de un segment în exact 2 puncte distincte.
Cerinţă
Se dau două numere naturale w şi h reprezentând lungimile laturilor dreptunghiului ABCD, un număr natural n şi n numere naturale x1, x2,… xn cu propietatea din enunt. Punctul P se plasează, pe rând, în toate punctele interioare dreptunghiului ABCD care sunt colţuri ale unor pătrate de latură 1. Pentru fiecare valoare x[i] (1 ≤ i ≤ n), determinaţi numărul de segmente distincte care trec prin exact x[i] pătrate 2-intersectate.
Date de intrare
Fişierul de intrare intersectii.in conţine pe prima linie trei numere naturale w, h (reprezentând dimensiunile dreptunghiului) şi n. Următoarele n linii conţin câte un număr natural x[i] cu semnificaţia de mai sus.
Date de ieşire
Fişierul de ieşire intersectii.out va conţine n linii. Pe fiecare linie i va fi scris numărul de segmente care trec prin exact x[i] pătrate 2-intersectate, obţinute după plasarea punctului P în fiecare colţ al unui pătrat de latură 1 din interiorul dreptunghiului ABCD.
Restricţii şi precizări:
2 ≤ w , h ≤ 2000 numere naturale pare;2 ≤ n ≤ 100000;- punctul
Pse alege doar în interiorul dreptunghiului; - pentru
40%din teste2 ≤ w, n, h ≤ 500.
Exemple:
intersectii.in
4 6 2 3 5intersectii.out
12 4
Explicatii:
Se pot obţine 12 segmente care trec prin exact 3 pătrate 2-intersectate şi 4 segmente care trec prin exact 3 pătrate 2-intersectate.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Intersectii:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 2048
int W, H, T, N;
int res[maxn], viz[maxn], d[maxn], a[maxn];
int main() {
FILE *f1=fopen("intersectii.in", "r"), *f2=fopen("intersectii.out", "w");
int i, j, p, q, k;
fscanf(f1, "%d %d %d\n", &W, &H, &T);
N = max(W, H) + 1;
for(i=1; i<=N; i++) d[i] = 1;
for(i=2; i<=N; i++) {
if(!viz[i]) {
for(j=i; j<=N; j+=i) {
viz[j] = 1;
d[j] = i;
}
}
}
for(i=1; i<H; i++) {
memset(a, 0, sizeof(a));
for(j=1; j<W; j++) {
if(d[j] == 1 || d[i] == 1) {
a[j] = 1;
}
p = j / d[j];
q = i / a[p];
if(q % d[j] == 0) {
a[j] = d[j] * a[p];
}
else {
a[j] = a[p];
}
if(i == 1) {
p = j;
res[p] += 4;
}
else if(j == 1) {
p = i;
res[p] += 4;
}
else if(i == j) {
p = i;
res[p] += 4;
}
else {
p = i + j - a[j];
res[p] += 4;
}
}
}
while(T--) {
fscanf(f1, "%d\n", &p);
fprintf(f2, "%d\n", res[p]);
}
fclose(f1); fclose(f2);
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1781 Intersectii
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1781 Intersectii de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!