Форум программистов, компьютерный форум CyberForum.ru

Codeforce. Такси. - C++

Восстановить пароль Регистрация
 
AKruglyak
0 / 0 / 0
Регистрация: 18.02.2012
Сообщений: 24
24.03.2012, 17:25     Codeforce. Такси. #1
Имеется следующая задача. Моё решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
using namespace std;
int main(){
    long long n, r, n1=0, n2=0, n3=0, n4=0;
    cin>>n;
    for(long long i=0; i<n; i++){
            r=0;
            cin>>r;
            switch(r){
             case 1: n1++;
              break;
             case 2: n2++;
              break;
             case 3: n3++;
              break;
             case 4: n4++;
              break;          
                      }
            
            }
    if(n1==0 and n2==0 and n3==0)
     cout<<n4;
  
      
    else{
     if(n2%2==0){
        n4+=n2/2;
        n2=0;
     } 
     else{
            n4+=(n2-2)/2;
            n2=1;
     }
     if(n1<=n3){
      n4+=n3;
      n1=0;
      n3=0;
   
      }
     else {
       n4+=n3; 
       n1-=n3;
       n3=0;
   
      }
     if(n2==0 and n1==0)
      n4=n4;
     else{
     if(n2>=n1*2)
        n4++;
     else 
      (n1/4>0)?n4+=n1/4:n4++;
      }
    cout<<n4;
 }
}
Проходит все тесты составленные мной, но выдает неверный ответ в 53 тесте с сайта. При каких исходных данных моё решение выдаст неправильный ответ?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2012, 17:25     Codeforce. Такси.
Посмотрите здесь:

MS Access Такси)
Такси
Проезд в Такси Delphi
C++ В такси одновременно сели три пасажира
Разобраться в задаче с Codeforce C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Duha666
50 / 50 / 5
Регистрация: 10.03.2012
Сообщений: 138
24.03.2012, 17:38     Codeforce. Такси. #2
Тест:
Код
3
2 2 2
Верный ответ: 2. Ответ программы: 1
Вообще, на КФ же есть нормальное активное сообщество. Можно и поспрашивать людей оттуда.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
24.03.2012, 17:40     Codeforce. Такси. #3
AKruglyak, профиль -> попытки -> слева номер решения, там ответы, ваш и системный.
AKruglyak
0 / 0 / 0
Регистрация: 18.02.2012
Сообщений: 24
24.03.2012, 19:59  [ТС]     Codeforce. Такси. #4
Спасибо, после многих нескольких улучшений получилось вот что:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
using namespace std;
int main(){
    long long n, r, n1=0, n2=0, n3=0, n4=0;
    cin>>n;
    for(long long i=0; i<n; i++){
            r=0;
            cin>>r;
            switch(r){
             case 1: n1++;
              break;
             case 2: n2++;
              break;
             case 3: n3++;
              break;
             case 4: n4++;
              break;          
                      }
            
            }
    if(n1==0 and n2==0 and n3==0)
     cout<<n4;
  
      
    else{
     if(n2%2==0){
        n4+=n2/2;
        n2=0;
     } 
     else{
            n4+=n2/2;
            n2=1;
     }
     if(n1<=n3){
      n4+=n3;
      n1=0;
      n3=0;
   
      }
     else {
       n4+=n3; 
       n1-=n3;
       n3=0;
   
      }
     if(n2==0 and n1==0)
      n4=n4;
     else{
     if(n2>n1*2)
        n4++;
     else 
      (n1/4>0)?((n1%4==0)?n4+=n1/4:n4+=n1/4+1):n4++;
      }
     cout<<n4;
           
 
 
     
 }
 
}
Решения стали заходить дальше, но не работают на тестах вида, при чем разница между мои ответом и правильным всегда 1.
100000

4 4 1 4 4 1 4 1 4 4 4 1 4 1 4 4 1 1 4 4 4 1 1 4 4 4 4 4 1 1 4 4 1 4 1 4 4 4 4 4 4 1 1 4 4 1 1 4 1 4 4 1 1 4 1 3 4 4 1 4 4 4 1...

И подобных, где много единиц, при это причина на в большом количестве, так как тест без единиц или там, где их мало проходят на ура. Не могу понять что не так?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
24.03.2012, 22:08     Codeforce. Такси. #5
Интересный сайт =)
Мое решение, проходит все тесты, но, боюсь, не особо читаемое:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
 
int main()
{
    int answer = 0;
    int arr[4] = {};
 
    int n;
    std::cin >> n;
 
    for (int i = 0, x; i < n; ++i)
    {
        std::cin >> x;
 
        if ( x == 4 )
            ++answer;
        else
            ++arr[x];
    }
 
    answer += arr[2] / 2;
    arr[2] %= 2;
 
    int temp = std::min( arr[1], arr[3] );
    answer += temp;
    arr[1] -= temp;
    arr[3] -= temp;
 
    if ( arr[1] == 0 )
    {
        answer += arr[2] + arr[3];
    }
    else
    {
        if ( arr[2] != 0)
        {
            ++answer;
            arr[1] = std::max(arr[1] - 2, 0);
        }
 
        answer += arr[1] / 4 + ( arr[1] % 4 != 0 );
    }
 
    std::cout << answer;
}
Yandex
Объявления
24.03.2012, 22:08     Codeforce. Такси.
Ответ Создать тему
Опции темы

Текущее время: 22:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru