fork(1) download
copy 
  1. #include <stdio.h>
  2.  
  3. #define maxn 100000
  4.  
  5. int gcd(int x,int y){// semmi trükk
  6.     if(y==0)return x;
  7.     return gcd(y,x%y);
  8. }
  9.  
  10. // Mindig az elejéről vagy a végéről kapcsolunk le vagont, ezért minden
  11. // mozgatás után egymásutáni vagonok vannak a pályán: a[i],a[i+1],..,a[j]
  12. // A megoldás nyilván gcd(a[i],a[i+1],..,a[j]), ahol i-edik az első,
  13. // j-edik az utolsó vagon ami a pályán van. Illetve 0 a válasz, ha üres a vonat.
  14.  
  15. // Legyen őrszem egy index i és j között, ha minden
  16. // t<orszem-re  bal[t]=gcd(a[t],..,a[orszem-1]) és
  17. // u>=orszem-re jobb[u]=gcd(a[orszem],..,a[u]) ismert, akkor
  18. // gcd(a[i],...,a[j])=gcd(bal[i],jobb[j])
  19. // Azaz némi számolás után csak egyetlen gcd-t számolunk ki. De!
  20. // Ha az őrszemet lekpcsolnánk akkor egy új őrszemet választunk:
  21. // őrszem=(vonat_eleje+vonat_vege)/2.
  22. // És pont ezt az algoritmust fogja a kód használni.
  23.  
  24. // Futásidőről:
  25. // Az algoritmus (legfeljebb) 3*N darab lnko-t számít ki, bizonyítás:
  26. // - Ha nincs új őrszem választása, akkor (legfeljebb) 2 lnko számítása kell,
  27. //   sőt, ha nem vagont kapcsolnak le, akkor (legfeljebb) 1 lnko-t számítunk
  28. // - Ha új őrszem kell, akkor L hosszú vagonnál L darab lnko-t számítunk ki
  29. //   a bal[] és jobb[] tömb felépítéséhez, DE a kővetkező őrszem kiválasztásáig
  30. //   (vagy amíg el nem érjük az N mozgatást) (L-1)/2 olyan lépés is lesz a 
  31. //   későbbiekben, amikor lekapcsolnak egy vagont, és akkor csak (legfeljebb)
  32. //   1 darab lnko-t számítunk ki. Így ezen L/2 lépésre, ha szétosztjuk az extra
  33. //   L darab lnko-t, akkor minden lépésben legfeljebb 3 darab lnko-t számítunk ki.
  34. // Mivel ez akkor is igaz, amikor nincs új őrszem választása, ezért N mozgatás
  35. // esetén így (legfeljebb) 3*N darab lnko-t kell kiszámítanunk.
  36.  
  37.  
  38. int main(void){
  39.  
  40.     int i,j,n,bal[maxn],jobb[maxn],a[maxn];
  41.     int mozgatas,megoldas;
  42.     int orszem=0;
  43.     int vonat_eleje=0;
  44.     int vonat_vege=-1;
  45.     int vonat_hossz;
  46.  
  47.     scanf("%d",&n);
  48.     for(i=0;i<n;i++){
  49.         scanf("%d",&mozgatas);
  50. 	if(mozgatas==0){
  51. 	   vonat_vege++;
  52. 	   scanf("%d",&a[vonat_vege]);
  53. 	   if(orszem<vonat_vege)jobb[vonat_vege]=gcd(jobb[vonat_vege-1],a[vonat_vege]);
  54. 	   else                 jobb[vonat_vege]=a[vonat_vege];
  55. 	   // bal[]-hoz tartozó vonatok: a(eleje)..a(orszem-1)
  56. 	   // jobb[]-hoz tartozó vonatok: a(orszem)..a(vege)
  57. 	}
  58. 	else if(mozgatas==1)vonat_vege--;// utolso vagon lekapcsolasa
  59. 	else vonat_eleje++;// elso vagon lekapcsolasa
  60.  
  61. 	if(vonat_eleje>=orszem||orszem>vonat_vege){// uj orszem kell!!!!!
  62. 	   orszem=(vonat_eleje+vonat_vege)/2;// a kozepso vagon lesz az orszem
  63. 	   if(orszem>0){
  64. 	      bal[orszem-1]=a[orszem-1];
  65. 	      for(j=orszem-2;j>=vonat_eleje;j--)bal[j]=gcd(a[j],bal[j+1]);
  66. 	   }
  67. 	   jobb[orszem]=a[orszem];
  68. 	   for(j=orszem+1;j<=vonat_vege;j++)jobb[j]=gcd(a[j],jobb[j-1]);
  69. 	}
  70.  
  71. 	vonat_hossz=vonat_vege-vonat_eleje+1;// vonat hossza
  72.  
  73. 	// a megoldas kiszamolasa, trivi esetek ellenorzese eloszor
  74.         if(vonat_hossz==0)megoldas=0;// ures vonat, ekkor 0 a valasz
  75. 	else if(vonat_hossz==1)megoldas=a[vonat_vege];// 1 vagon van
  76. 	else if(vonat_eleje<orszem)megoldas=gcd(bal[vonat_eleje],jobb[vonat_vege]);// altalanos eset
  77. 	else megoldas=jobb[vonat_vege];// orszemtol balra nincs vagon
  78. 	printf("%d\n",megoldas);
  79.     }
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0s 3220KB
comments (?)
stdin
copy 
8
0 10
0 6
0 21
2
1
0 18
2
1
stdout
copy 
10
2
1
3
6
6
18
0
https://ideone.com/A8poMH
language:
C (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!