Řešení (Zadání úlohy)
Jelikož na pořadí K, L, M nezáleží můžeme předpokládat, že K ≤ L ≤ M. Potřebujeme alespoň K zaplňěných komor, abychom splnili všechny skeny. My si ukážeme konstrukci pro splnitelné zadání, která má přesně K komor.
Všimneme si, že pokud vidíme zprava L a zepředu M komor, potom zvrchu můžeme vidět nejvíše L*M. Komory zepředu a zboku jinak nezakryjí to co vidíme zvrchu. Tedy pokud K > L*M, řešení neexistuje.
Představíme si, že umisťujeme K komor do obdélníku L*M, ty budou umístěny tak, že zprava jich uvidíme L a zepředu M. Prvních M komor umístíme tak, že v každém řádku a každém řádku bude jedena a v každém sloupci alespoň jedena. (Jedna možnost je ve zdrojovém kódu). Tím splníme požadavek na L a M.
Zbylých K-L bloků umístíme libovolně do neobsazených míst obdélníku. Ty už nám nic nezkazí.
#include <cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> sou[2];
bool verify(vector<int> cis){
if((long long)cis[0]*(long long)cis[1] < (long long)cis[2]) return false;
return true;
}
void build(vector<int> cis){
for(int a = 0; a < cis[0]; a++){
sou[0].push_back(a);
sou[1].push_back(a);
}
for(int b = 0; b < cis[1]-cis[0]; b++){
sou[0].push_back(cis[0]-1);
sou[1].push_back(b+cis[0]);
}
int more = cis[2] - cis[1];
int i = 0, j = 0;
while(more > 0){
if(i == j){
i++;
continue;
}
if(i >= cis[0] || (i >= cis[0]-1 && j>= cis[0]-1)){
i = 0;
j++;
continue;
}
sou[0].push_back(i);
sou[1].push_back(j);
more--;
i++;
}
}
void solve(){
int x,y,z;
scanf("%i%i%i",&x,&y,&z);
vector<int> cis = {x,y,z};
sort(cis.begin(),cis.end());
if(!verify(cis)){
printf("-1\n");
return;
}
for(int a = 0; a < 2; a++) sou[a].clear();
build(cis);
printf("%i\n",(int)sou[0].size());
for(int a = 0; a < sou[0].size(); a++){
printf("%i %i %i\n",sou[0][a],sou[1][a],1);
}
}
int main(){
int t;
scanf("%i",&t);
for(int a = 0; a < t; a++) solve();
return 0;
}
