Finále

C: Nákladní loď

Ř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;
}

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)