სტრუქტურები
            სტრუქტურები
წინა თავებში განვიხილეთ მასივები, სადაც ელემენტებში ვინახავდით ერთი და იმავე ტიპის ინფორმაციას. პრაქტიკაში ხშირია შემთხვევა, როცა აუცილებელია სხვადასხვა ტიპის მონაცემთა დაჯგუფება. მაგალითად, ბანკის მეანაბრეთა მონაცემები: სახელი და გვარი (string ტიპის ცვლადი), დაბადების წელი (int ტიპის ცვლადი), ანაბარზე არსებული თანხა (float ან double ტიპის ცვლადი). ცხადია, რომ ამ მონაცემების შენახვა 3 სხვადასხვა მასივშიც შეიძლება, მაგრამ ეს ძალიან გაართულებდა მათ დამუშავებას – რომელიმე მათგანის დასორტირების შემთხვევაში პარალელურად მოგვიწევდა ცვლილებების განხორციელება სამივე მასივში.
ასეთი პრობლემების გადასაწყვეტად პროგრამირების ენებში არსებობს სპეციალური სტრუქტურა,  რომელიც საშუალებას იძლევა ერთად შევინახოთ ინფორმაცია სხვადასხვა ტიპის ცვლადების შესახებ. C/C++–ში ასეთ ბრძანებას წარმოადგენს struct.  იგი წარმოადგენს შაბლონს, რომლის მიხედვითაც პროგრამაში შეიძლება გამოვაცხადოთ ცვლადები და მასივები. struct გასაღები სიტყვის შემდეგ მოდის შაბლონის სახელი და მარცხენა ფიგურული ფრჩხილები, რომელთა შორის ჩამოთვლილია შაბლონის ელემენტთა ტიპები და სახელები:
struct შაბლონის სახელი 
{ 
   int ელემენტის სახელი1 ; 
   float ელემენტის სახელი2; } ცვლადის სახელი; 
} 
ზემოთ მოყვანილი მაგალითის შესაბამისი სტრუქტურა 1000 ადამიანისათვის იქნება:
struct  deposit{ 
   string name; 
   int year; 
   float money; 
  } people[1000]; 

მიმართვა სტრუქტურის ცალკეულ ელემენტებზე შეიძლება ასე განვახორციელოთ:
people[0].year=1983;
people[i].money=3958.73;
struct–ის ერთგვარ გამარტივებულ სახედ შეგვიძლია განვიხილოთ კლასი pair (წყვილი), რომელიც გვხვდება მხოლოდ С++–ის სტანდარტულ ბიბლიოთეკაში და არ ფუნქციონირებს    С–ში. მის გამოსაყენებლად საჭიროა ფაილში ჩავრთოთ ბიბლიოთეკა #include <algorithm>. pair საშუალებას იძლევა ერთმანეთთან დავაკავშიროთ ორი ელემენტი, ამასთან ამ ელემეტებისათვის სახელების დარქმევა საჭირო არ არის, რადგან მათ სტანდარტულად განსაზღვრული აქვთ სახელები   first და second. ჩვენ უნდა მივუთითოთ მხოლოდ იმ ცვლადის ან მასივის სახელი, რომელსაც აქვს  pair  სტრუქტურა და იმ ორი ელემენტის მონაცემთა ტიპი, რომლებიც წყვილში უნდა გაერთიანდნენ. მაგალითად, თუ ჩვენ გვინდა რომ შევქმნათ 10–ელემენტიანი მასივი სახელად book, მთელი რიცხვისა და string ტიპის წყვილით, ინსტრუქციას ექნება სახე:
pair< int, string > book[10];
მიმართვა მასივის ცალკეულ ელემენტებზე მოხდება როგორც book[i].first და book[i].second. მაგალითად, book[i].first=784; ან book[2].second=“Tarzan”;
pair სტრუქტურის მქონე მასივის სორტირება სტანდარტული sort() ბრძანების გამოყენებით ჩვეულებრივი მასივის ანალოგიურად ხდება.  ამ შემთხვევაში sort() ბრძანება მასივს ალაგებს first ელემენტის მნიშვნელობების მიხედვით, ხოლო თუ ეს მნიშვნელობები ტოლია, მაშინ second ელემენტების მიხედვით. struct–ის შემთხვევაში sort() ბრძანების მიერ ელემენტების რიგითობას ყურადღება არ ექცევა და საჭირო ხდება სპეციალური ფუნქციის დაწერა, რომელიც განსაზღვრავს ელემენტთა პრიორიტეტებს სორტირებისას.
 
ამოცანა 226. დრაკონები
http://codeforces.com/problemset/problem/230A
კირიტო გადავიდა MMORPG–ის მორიგ ეტაპზე. თამაშის გასაგრძელებლად მას სჭირდება ამ ეტაპზე არსებული n დრაკონის დამარცხება. კირიტოსაც და დრაკონებსაც გააჩნიათ ძალა, რომელიც გამოსახება მთელი რიცხვით. ორ მოწინააღმდეგეს შორის იმარჯვებს ის, ვისაც მეტი ძალა აქვს. კირიტოს თავდაპირველი ძალა s–ის ტოლია. თუკი კირიტო ებრძვის i-ურ (1 ≤ i ≤ n) დრაკონს და მისი ძალა არ აღემატება დრაკონის xi ძალას, მაშინ კირიტო იღუპება. თუკი კირიტოს ძალა აღემატება დრაკონის ძალას, მაშინ ის ამარცხებს დრაკონს და იღებს ბონუსს – მისი ძალა იზრდება yi–ით.
კირიტოს შეუძლია დრაკონებთან ბრძოლა ნებისმიერი თანმიმდევრობით. გაარკვიეთ, გადავა თუ არა ის მომდევნო ეტაპზე, ანუ დაამარცხებს თუ არა ყველა დრაკონს ისე, რომ თავად არცერთხელ არ დამარცხდეს.
შესატანი მონაცემები: პირველ სტრიქონში მოცემულია  ორი მთელი რიცხვი: s და n (1≤s≤104, 1≤n≤103). მომდევნო n სტრიქონიდან ყოველი i-ური სტრიქონი შეიცავს ორ მთელ რიცხვს xi და yi (1≤xi≤104, 0≤yi ≤104) – i-ური დრაკონის ძალა და ბონუსი მასზე გამარჯვებისათვის. 
გამოსატანი მონაცემები: ერთადერთ სტრიქონში გამოიტანეთ «YES», თუ კირიტო გადავა მომდევნო ეტაპზე და «NO» – თუკი ვერ გადავა.

შესატანი მონაცემების მაგალითი	           შესაბამისი გამოსატანი მონაცემი
2 2                                                                YES
1 99
100 0	

10 1                                                              NO
100 100
	


ანალიზი. ეტაპის გავლის ნებისმიერ მომენტში კირიტო მოწინააღმდეგედ აირჩევს ყველაზე ნაკლები ძალის მქონე დრაკონს (თუკი მისი დამარცხება არ შეუძლია, სხვებს მითუმეტეს ვერ დაამარცხებს), ამიტომ დრაკონების მონაცემები ჩავწეროთ pair სტრუქტურის მქონე მასივში და დავასორტიროთ. თანმიმდევრულად შევამოწმოთ first ველის მონაცემები და თუ კირიტოს ძალა აღემატება მორიგი დრაკონის ძალას, მაშინ კირიტოს ძალა გავზარდოთ second ველის მნიშვნელობით. თუკი კირიტოს ძალა განსახილველი დრაკონის ძალაზე ნაკლები იქნება, გამოვიტანოთ "NO" და შევწყვიტოთ პროგრამის შესრულება, ხოლო თუ ყველა დრაკონს გაივლის, გამოვიტანოთ "YES".

#include<iostream>
#include<algorithm>
using namespace std;
int a,s,f,g,h,j,k,l,i,n,m;
pair<int,int> d[10002];
main(){
cin>>m>>n;
for(i=0;i<n;i++){
        cin>>d[i].first>>d[i].second;}
sort(d,d+n);
for(i=0;i<n;i++){
       if(d[i].first<m) m=m+d[i].second; else {cout<<"NO";return 0;}}
cout<<"YES";
}



ამოცანა 227. ისტორია
http://codeforces.com/problemset/problem/137/C
პოლიკარპი კარგი მოსწავლეა, მაგრამ არსებობს საგანი, რომელშიც მას მუდამ პრობლემები აქვს – ისტორია. ყველასათვის ცნობილია, რომ მსოფლიო ისტორიაში მოხდა ზუსტად n მოვლენა: i-ური მოვლენა გრძელდებოდა ai–დან bi–მდე წლამდე (მათი ჩათვლით) და ai < bi. მასწავლებელმა დაავალა პოლიკარპს, რომ ისწავლოს არა მარტო ყოველი მოვლენის  დასაწყისი და დასასრული, არამედ გაარკვიოს შეიცავს თუ არა ეს მოვლენა სხვა მოვლენას თავის შიგნით. მასწავლებლის აზრით,   j–ური მოვლენა შეიცავს თავის შიგნით i–ურ მოვლენას, თუ aj < ai და bi < bj. თქვენი ამოცანა უფრო მარტივია: იპოვეთ იმ მოვლენების რაოდენობა, რომელიც ჩართულია რომელიმე სხვა მოვლენის შიგნით.
შესატანი მონაცემები: პირველ სტრიქონში მოცემულია ერთი მთელი რიცხვი n (1 ≤ n ≤ 105) – მოვლენათა რაოდენობა. მომდევნო n სტრიქონიდან თითოეულში აღწერილია თითო ისტორიული მოვლენა. (i +1)–ე სტრიქონში მოცემულია ორი მთელი რიცხვი ai და bi (1 ≤ ai < bi ≤ 109) – i-ური მოვლენის დასაწყისი და დასასრული. მოვლენათა არცერთი წყვილი არ იწყება და არ მთავრდება ერთსა და იმავე წელს, ანუ ai ≠ aj, ai ≠ bj, bi ≠ aj, bi ≠ bj ყველა i, j (სადაც i ≠ j). მოვლენები მოცემულია რაიმე კანონზომიერების გარეშე.
გამოსატანი მონაცემები: ერთადერთი რიცხვი – ამოცანის პასუხი.

შესატანი მონაცემების მაგალითები             შესაბამისი გამოსატანი მონაცემები
5                                                                        4
1 10
2 9
3 8
4 7
5 6	
5

1 100                                                                   4
2 50
51 99
52 98
10 60	

1                                                                         0
1 1000000000

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct area{
int d;
int f;
}saz;
saz z[100005];
    bool mycompare(area v1,area v2){
        return v1.d < v2.d;
    }
int a,s,n,i,g,h,j,k,l;
main(){
scanf("%d",&n);
if(n==1) {printf("0");return 0;}
for(i=0;i<n;i++){
scanf("%d%d",&z[i].d,&z[i].f);
}
sort(z,z+n,mycompare);a=z[0].f;
for(i=1;i<n;i++){
if(a>z[i].f) k++; else a=z[i].f;
}
printf("%d",k)};

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
long long cur=0,i,j,n,x,y,kol=0;
cin>>n;
pair <int ,int> q[n];
for(i=0;i<n;i++){
   cin>>q[i].first>>q[i].second;
}
sort(q,q+n);
for(i=0;i<n;i++){
	if(q[i].second<cur)kol++; else cur=q[i].second;
}
  cout<<kol;
}




ამოცანა 227. გამარჯვებული
http://codeforces.com/problemset/problem/2/A
ბერლანდიაში პოპულარული ბანქოს თამაშის „ბერლოგინგის“ შემდეგი წესებით ვლინდება: თუკი თამაშის დასრულების მომენტში მხოლოდ ერთ მოთამაშეს აქვს მაქსიმალური რაოდენობის ქულები, ის ცხადდება გამარჯვებულად. სიტუაცია რთულდება, თუ ასეთი მოთამაშე რამდენიმეა. თამაში თითოეულ ფსონზე მოთამაშე იგებს ან აგებს ქულათა გარკვეულ რაოდენობას. თამაში მსვლელობის ჩანაწერში ეს აღინიშნება ფორმატით «name score», სადაც name ამ მოთამაშის სახელია, ხოლო score – მოთამაშის მიერ დაგროვებული ქულების რაოდენობა. თუკი score უარყოფითი რიცხვია, ეს ნიშნავს რომ მოთამაშემ ამ ფსონზე წააგო. თუ რამდენიმე მოთამაშე აგროვებს მაქსიმალურ ქულას (ვთქვათ, ეს ქულაა m), მაშინ გამარჯვებულად ცხადდება ის მოთამაშე, რომელმაც პირველმა (ანუ ყველაზე ადრე) მოაგროვა m ქულა. თამაშის დაწყების წინ თითოეულ მოთამაშეს 0 ქულა აქვს. გარანტირებულია, რომ თამაშის დასრულების მომენტში ერთ მოთამაშეს მაინც აქვს დადებითი ქულა.
შესატანი მონაცემების ფორმატი: პირველ სტრიქონში მოცემულია ერთი მთელი რიცხვი n (1≤n≤1000) – ნათამაშევ ფსონთა რაოდენობა. მომდევნო n სტრიქონიდან თითოეულში ფსონთა შედგები ფორმატით „name score“ ქრონოლოგიური მიმდევრობით, სადაც name არის ლათინური დაბალი რეგისტრის სიმბოლოებისაგან შედგენილი სტრიქონი სიგრძით 1–დან 32–მდე, ხოლო score არის მთელი რიცხვი   –1000..1000 დიაპაზონიდან. 
გამოსატანი მონაცემები: გამოიტანეთ „ბერლოგინგის“ გამარჯვებულის სახელი.

შესატანი მონაცემების მაგალითი	შესაბამისი გამოსატანი მონაცემი
3                                                          andrew
mike 3
andrew 5
mike 2	

3                                                         andrew
andrew 3
andrew 2
mike 5	

ანალიზი. ციკლის ერთი გავლით შეგვიძლია დავთვალოთ ყველა მოთამაშის მიერ დაგროვებული ქულები და ვიპოვოთ მათ შორის მაქსიმალური. თუ რამდენიმე მაქსიმუმი გვაქვს, მონაცემების კიდევ ერთხელ ციკლური გავლით ვიპოვით ვინ მოაგროვა  m ან მეტი ქულა პირველად. ამასთან, რიგში გასათვალისწინებელია, შემთხვევა, როცა რომელიმე მოთამაშემ შეიძლება მოაგროვოს m ან მეტი ქულა, მაგრამ შემდეგ წააგოს და გამარჯვებული ვერ გახდეს.

#include<stdio.h>
#include<string.h>

typedef struct{
  char name[36];
  int score;
  int subscore;
}player;

int main(void){
  player pl[1024];
  int i,j,k,n,now=0,flg,win=0;
  int m=0;
  struct{
    char str[36];
    int sc;
  }input[1024];
  
  scanf("%d%*c",&n);
  for(i=0;i<n;i++){
    scanf("%s %d%*c",input[i].str,&input[i].sc);
    for(j=0,flg=0;j<now;j++){
      if(!strcmp(input[i].str,pl[j].name)){
	flg=1;
	pl[j].score+=input[i].sc;
      }
    }
    if(flg==1) continue;
    strcpy(pl[now].name,input[i].str);
    pl[now].score=input[i].sc;
    pl[now].subscore=0;
    now++;
  }

  for(i=0;i<now;i++)
    if(m<pl[i].score) m=pl[i].score;
  
  for(i=0;i<n;i++){
    for(j=0;j<now;j++){
      if(!strcmp(input[i].str,pl[j].name)){
	pl[j].subscore+=input[i].sc;
	break;
      }
    }
    if(pl[j].subscore>=m && pl[j].score>=m){
      puts(pl[j].name);
      break;
    }
  }
  return 0;
}







ამოცანა 229. ფოტოგრაფი
http://codeforces.com/problemset/problem/203/C
ვალერი დიდხანს ოცნებობდა ფოტოგრაფობაზე და ამიტომ იყიდა ახალი ფოტოაპარატი. მისთვის შეკვეთების რაოდენობა დღითი დღე იზრდებოდა და ერთ მშვენიერ დღეს მას დასჭირდა პროგრამა, რომელიც გაარკვევს, თუ რა მაქსიმალური რაოდენობის ადამიანის  მომსახურება შეუძლია. ფოტოაპარატის მეხსიერება d მეგაბაიტია და მას შეუძლია გადაიღოს მაღალი და დაბალი ხარისხის სურათები. დაბალი ხარისხის სურათი ფოტოაპარატში იკავებს a მეგაბაიტ ინფორმაციას, ხოლო მაღალი ხარისხის – b მეგაბაიტს. i–ური კლიენტი ითხოვს, რომ მისთვის xi ცალი დაბალი ხარისხის ფოტოგრაფია და yi ცალი მაღალი ხარისხის ფოტოგრაფია. კლიენტი კმაყოფილია მხოლოდ მაშინ, თუ მისი შეკვეთა მთლიანად შესრულდა. ვალერის სურს, რაც შეიძლება მეტი კლიენტი ჰყავდეს კმაყოფილი. დაბალი ხარისხის სურათის შესანახავად ფოტოაპარატში თავისუფალი უნდა იყოს არანაკლებ a მეგაბაიტისა, ხოლო მაღალი ხარისხის სურათის შესანახავად – არანაკლებ b მეგაბაიტისა. თავდაპირველად ფოტოაპარატის მეხსიერება ცარიელია. ვალერი არ შლის ფოტოაპარატიდან არცერთ სურათს, ამიტომ მისი მეხსიერება ნელ–ნელა ივსება.
გამოთვალეთ, რა მაქსიმალური რაოდენობის კლიენტის მომსახურება შეუძლია ვალერის და გამოიტანეთ ამ კლიენტების ნომრები.
შესატანი მონაცემები: პირველ სტრიქონში მოცემულია  ორი მთელი რიცხვი:  n და d (1≤n≤105, 1≤d≤109) – კლიენტების რაოდენობა და ფოტოაპარატის მეხსიერების მოცულობა. მეორე სტრიქონში მოცემულია  ორი მთელი რიცხვი:  a და b (1≤a≤b≤104) —  შესაბამისად დაბალი და მაღალი ხარისხის სურათის ზომა. მომდევნო n სტრიქონიდან თითოეულში აღწერილია შეკვეთები. i–ურ სტრიქონში მოცემულია ორი მთელი რიცხვი: xi და yi (0≤xi,yi≤105) – i–ური კლიენტის მიერ შეკვეთილი დაბალი და მაღალი ხარისხის სურათების რაოდენობა.
გამოსატანი მონაცემები: პირველ სტრიქონში სტრიქონში ამოცანის პასუხი – რა მაქსიმალური რაოდენობის კლიენტის მომსახურება შეუძლია ვალერის. მეორე სტრიქონში გამოიტანეთ ამ კლიენტების ნომრები. ყველა ნომერი განსხვავებული უნდა იყოს. თუ პასუხი რამდენიმეა – გამოიტანეთ ნებისმიერი.

შესატანი მონაცემების მაგალითი	შესაბამისი გამოსატანი მონაცემი
3 10                                                        2
2 3                                                          3 2
1 4
2 1
1 0	


3 6                                                           1
6 6                                                           2 
1 1
1 0
1 0	



ანალიზი. ცხადია, რომ ვალერი უფრო მეტ კლიენტს მოემსახურება, თუკი ამოარჩევს ჯამურად ნაკლები მეხსიერების მომთხოვნ შეკვეთებს. ე.ი. ჩვენ უნდა დავთვალოთ თითოეული კლიენტის სურათებისათვის საჭირო ჯამური მეხსიერება, დავალაგოთ ეს მონაცემი ზრდადობით და თანმიმდევრობით შევასრულოთ შეკვეთები ვიდრე მეხსიერება გვეყოფა. ერთადერთი პრობლემა აქ არის ის, რომ დალაგებისას დაიკარგება კლიენტთა თავდაპირველი ნომრები. ეს რომ არ მოხდეს, გამოვიყენოთ pair სტრუქტურა. first ველში შევინახოთ კლიენტის სურათებისათვის საჭირო მეხსიერების სიდიდე (რის მიხედვითაც შემდეგ უნდა დავალაგოთ), ხოლო second ველში დავიმახსოვროთ კლიენტის ნომრები, რომელთაც გამოვიტანთ პასუხად.

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a,s,f,g,h,j,k,l,i,n,i1;
pair <int,int>d[100002];
main(){
cin>>n>>k;
cin>>g>>h;
for(i=0;i<n;i++){
cin>>j>>l;
d[i].first=j*g+h*l;
d[i].second=i+1;}
sort(d,d+n);
for(i=0;i<n;i++){
k=k-d[i].first;
if(k<0) {cout<<i<<endl;break;}}
if(i==n) {cout<<i<<endl;}
for(i1=0;i1<i;i1++){
cout<<d[i1].second<<" ";}
}