Show all threads Hide all threads Show all messages Hide all messages |
anyone in O(1) extra space? | Aayush Chaturvedi | 1319. Hotel | 24 Feb 2023 23:41 | 2 |
Is there a O(1) extra space solution? I tried looking up for patterns but it didn't help. Can we have a function f such that matrix[i][j] = f(i, j, n) for all valid i and j? Still takes more space than some O(N^2) solution i've found for some reasons. I am not really familiar with cpp compiler optimizations, so that might be linked ! #include <iostream> int main(int argc, char* argv[]) { int size; if (argc != 2) { scanf("%d",&size); } else { size = std::atoi(argv[1]); } int halfSquare = (size * size) / 2; int half = size / 2; int previousY0 = halfSquare - (half) - size; int previous; for (int y = 0; y < size; y++) { previous = previousY0 + (size + 1 - y); printf("\n%d ", previous); for (int x = 1; x < size; x++) { previous = previous - (size - 1 - std::max(std::abs(x - y), 1) + (x >= y)); printf("%d ", previous); } previousY0 = previousY0 + (size + 1 - y); } return 0; } |
I have optimized the problem,but it took me more time! | 我是中国人 | 1319. Hotel | 6 Apr 2022 10:47 | 3 |
........................... |
Hotel - Trivago | n000 | 1319. Hotel | 7 Jan 2020 02:09 | 1 |
|
O(1)? Python как ускорить? | CGCG | 1319. Hotel | 20 Dec 2019 02:50 | 1 |
Считаем кол-во клеток ( квадрат + 2 треугольника сверху и снизу ) 156 мс, как ускорить программу? сократить формулу? найти более легкую закономерность? n = int(input()) def tr(size): ans = 0 for i in range(1, size+1): ans += i return ans for j in range(n): print() for i in range(n): if i >= j: print((n-i-1)*j + tr(j) + tr(n-i-2) + 1 + j + (n-i-1), end = ' ') else: print(n*n - (i+1)*(n-j) - tr(n-j-1) - tr(i-1) + 1, end = ' ') |
Accepted in c++ | WENXIANG LU | 1319. Hotel | 15 Jul 2017 13:53 | 3 |
#include <iostream> int main() { int N; std:: cin >> N; /* dynamic memory allocation */ int ** p = new int * [N]; for (int i = 0; i < N; i++) p[i] = new int [N]; /* initialize upper triangle matrix */ p[0][N-1] = 1; int m, n; int ct = 1, value = 2, iter = 1, row = 0, column = N - 2; while (ct <= N - 1) { n = column, m = row; for (int i = 0; i <= iter; i++) { p[m++][n++] = value; value++; }
iter++; ct++; column--; } /* initialize the lower triangle matrix */ row = 1; column = 0, iter = N - 2; while (ct > 1) { n = column, m = row; for (int i = 0; i <= iter; i++) { p[m++][n++] = value; value++; } iter--; ct--; row++; } /* display matrix */ for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) std::cout << p[i][j] << " "; std::cout << std::endl; }
/* release memory */ for (int i = 0; i < N; i++) delete[] p[i]; delete[] p; return 0; } We do not give a fuck. remove the code. |
What's in test #4? Please, help | Sapunovnik | 1319. Hotel | 10 Jun 2017 15:16 | 1 |
Hi. My solution works on my computer but there is not. What's wrong with my code? #include <iostream> using namespace std; int main() { int n, c = 1; int pix[100][100]; for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < n; ++j ) { pix[i][j] = 0; } } cin >> n; for ( int i = 0; i < n; ++i ) { for ( int j = (n - 1); j >= 0; --j ) { if ( pix[i][j] > 0 ) continue; int ii = i, jj = j; while ( ii < n && jj < n ) { pix[ii][jj] = c; ii++; jj++; c++; } } } for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < n; ++j ) { cout << pix[i][j] << " "; } cout << endl; } return 0; } Edited by author 10.06.2017 15:16 Edited by author 10.06.2017 15:16 Edited by author 10.06.2017 15:17 |
hint | Mostafa Tantawy | 1319. Hotel | 29 Apr 2017 21:48 | 1 |
hint Mostafa Tantawy 29 Apr 2017 21:48 divide the matrex into three divisions >> above the diagonal >>> the diagonal>>under the diagonal simulate more than matrix for insure your answer |
why is Wrong answer? (use Visual C++ 2013) | Huyen Pham | 1319. Hotel | 22 Dec 2015 10:02 | 1 |
Running in my computer is OK,use use Visual C++ 2010. But in here (use Visual C++ 2013) is wrong answer. I don't understand. Help me, please! #include <iostream> using namespace std; int main(){ int a[100][100]; int n, x=0; cout<<"\Input n: "; cin>>n; for(int j=n-1,i=0;j>=0;j--){ int h=i,k=j; while(k<n) a[h++][k++]=++x; } for(int i=1,j=0;i<n;i++){ int h=i,k=j; while(h<n) a[h++][k++]=++x; } for(int i=0; i<n ;i++){ for(int j=0; j<n ;j++){ cout.width(4); cout<<a[i][j]; } cout<<endl; } cin.ignore(80,'\n'); cin.get(); return 0; } |
C# Accepted | anete.anetes | 1319. Hotel | 17 Mar 2015 14:10 | 1 |
using System.IO; using System; class Program { static void Main() { int size = Int32.Parse(Console.ReadLine()); int[,] arr=new int[size,size]; int count=1; for(int x=size;x>=0;x--) { int y=0; int xx=x; bool exc=false; while(!exc) { try { arr[xx,y]=count; count++; xx++; y++; } catch { exc=true; break; } } }
for(int y=1;y<=size-1;y++) { int x=0; int yy=y; bool exc=false; while(!exc) { try { arr[x,yy]=count; count++; x++; yy++; } catch { exc=true; break; } } }
for(int x=0;x<size;x++) { for(int y=0;y<size;y++) { Console.Write(arr[y,x]+" "); } Console.WriteLine(); }
} } |
Format of output | Aleksandar Bukva | 1319. Hotel | 4 Oct 2014 06:03 | 1 |
What is the format of output, blank spaces before number? |
hint for some one that want to think more... | mhg | 1319. Hotel | 26 Sep 2014 21:48 | 1 |
hi,i know! there are some solution in this discussion that is a dangerous thing for someone that want to think more... so i say something about this problem for only hint.. for solving this problem this is better to check 2 or 3 example then consider a general case with n as input then try to simulate the answer and in the final step code it. be successful... |
nothing | Ouch | 1319. Hotel | 31 Oct 2013 23:15 | 1 |
Edited by author 02.11.2013 13:47 |
WA 4 Help!! | Alexandr-pro | 1319. Hotel | 8 Oct 2013 06:52 | 1 |
var i,j,n:word; a:array[1..100] of word; begin readln(n); a[1]:=1; for i:=2 to n do a[i]:=a[i-1]+i-1; for j:=n downto 1 do begin for i:=n downto 1 do write(a[i]:3); for i:=1 to n-1 do a[i]:=a[i+1]+1; a[n]:=a[n]+j; writeln; end; end. |
AC Python 3.3 | lomobit | 1319. Hotel | 28 Jul 2013 00:16 | 1 |
num = int(input()) arr = [] for i in range(num): arr.append([]) for j in range(num): arr[i].append([])
check = 1 for i in range(num-1,-1,-1): x = 0 y = i while y != num: arr[x][y] = check check += 1 y += 1 x += 1 for i in range(1,num,1): x = i y = 0 while x != num: arr[x][y] = check check += 1 y += 1 x += 1 string = '' for i in range(num): for j in range(num): string += (str(arr[i][j]) + ' ') print(string) string = '' |
asdasdasd | ranc_dm | 1319. Hotel | 16 May 2013 22:06 | 1 |
Edited by author 31.05.2013 05:43 |
What can be the reason of Crash (access violation)? On my computer it works great. | vpro | 1319. Hotel | 20 Jun 2012 20:12 | 1 |
The same trouble was with problem 1313. |
what the first test? | ejjjik | 1319. Hotel | 29 Dec 2011 13:25 | 1 |
#include <iostream> #include <iomanip> //#include <conio.h> using namespace std; #define size 105 int main() { //const int size = 105; int mas[size][size]; int xSize; cout << "Input array size: "; cin >> xSize; if ( xSize <= 100 && xSize >=1 ) { //заполняемые элементы int ch = 1; // правая половина + диагональ; top right corner + main diagonal for ( int f = 0; f < xSize; f++ ) {
for( int i = 0, j = xSize - 1, d = f; d >= 0; i++, d-- ) { mas[ i ][ j - d ] = ch++; }
} // левая половина; left down corner for ( int f = 1; f < xSize; f++ ) {
for( int i = f, j = 0, d = 0; i < xSize; i++, d++ ) { mas[ i ][ j + d ] = ch++; }
} //output array for ( int i = 0; i < xSize; i++ ) { for ( int j = 0; j < xSize; j++ ) { cout << setw(4) << mas[i][j]; } cout << endl;
} } //_getch(); return 0; } |
It is possible to write the output to one line. | Zefick | 1319. Hotel | 9 Dec 2011 11:24 | 1 |
|
This is my very simple solution in Pacal! | NikolaV994 | 1319. Hotel | 26 Nov 2011 22:05 | 1 |
program Project2; var a:array[1..100,1..100] of integer; k,p,n,i,j,s:integer; begin readln(n); k:=0; p:=n-1; for s:=1 to (n*2-1) do begin for i:=1 to n do for j:=1 to n do if j-i=p then begin k:=k+1; a[i,j]:=k end; p:=p-1 end; for i:=1 to n do begin for j:=1 to n do begin write(a[i,j]); write(' ') end; writeln end; end. |
here is the mathematic method | esger | 1319. Hotel | 10 Oct 2011 08:33 | 3 |
#include<iostream.h> int i,j; long a[101][101],n; int main(){ cin>>n; for(i=1;i<n+1;i++) { a[i][n]=i*(i+1)/2; } for(i=1;i<n;i++) { for(j=n-1;j>=i;j--) { a[i][j]=a[i][j+1]+n-j+i-1; } } for(i=2;i<n+1;i++) { for(j=i-1;j>0;j--) { a[i][j]=a[i][j+1]+n+j-i; } } for(i=1;i<n+1;i++) { for(j=1;j<n+1;j++) cout<<a[i][j]<<" "; cout<<"\n"; } return 0; } This method is easy but very interesting! Nice, but there's no need in arrays if you're trying to use some math. My solution uses just seven integers and that's enough. |