Problom 1 Wrong number
Original Problem:
Give you a string, extract all the negative numbers from the string.
e.g. (Source code: THU OJ)
Input:
1
2
3
4
5
6
7
This line contains 1 integer "one".
This line contains no integer.
233, next line is empty.
If you got -123.456, you should output 123 and 456.
Any digit string are considered integers, like 0123456 and 007.
You may also need to consider cases like a0a12a345a6789a.
Output:
1
2
3
4
5
6
7
1
233
123 456 123 456
0123456 007
0 12 345 6789
Solution:
The main idea of the source code:
Find the first number of each string, then find the last number of the string, here we have a total number string.
Decide whether it is the first string, if not so, output a SPACE.
Bugs in the idea of the sorce code:
(1) The source code didn’t initialize the bool-type variable.
(2) The source code mistakes the ASCII code between character and number:
'0'-'9' VS 0-9
My solution
I chose to judge whether the number string is the last one (because I’m accustomed to output a space behind a string [Facepalm])
My source code:
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
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
int main() {
for (string str; getline(cin, str); ) {
bool if_final = true;
size_t length = str.size();
/*********************************************************************************************************************
* Judge whether the character is a number.
* If so, find the last number following it.
* Find out whether it is the last number string by judging whether there is still number behind this string
* If so, it is not the last string, and you need to output a SPACE.
*********************************************************************************************************************/
for(size_t i = 0; i < length; ++i){
if(str[i] >= '0' && str[i] <= '9'){
size_t index = i;
while(str[index] >= '0' && str[index] <= '9'){
putchar(str[index]);
++index;
}
size_t inspect_back = index;
while((str[inspect_back] < '0' || str[inspect_back] > '9') && inspect_back < length - 1){
++inspect_back;
if(str[inspect_back] >= '0' && str[inspect_back] <= '9')
if_final = false;
}
if(!if_final) putchar(' ');
i = index;
if_final = true;
}
}
printf("\n");
}
return 0;
}
Problem 2 Wrong drink
Original problem:
Give you several kinds of wine, the density is $d_i$, the price is $p_i$. Now input a series of densities, the program should output the lowest cost.
(Source code: THU OJ)
Solution:
The idea of the source code is treating pairs ($d_i$, $p_i$) as a point of a 2-dimensional surface, find the convex hull, and pick two wines on the hull.
Bugs in the idea:
(1) The automatically called constructor and destructor: HERE WE HAVE AN EXAMPLE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
class NewClass{
public:
NewClass(){std::cout << "Constructor !" << std::endl; }
~NewClass(){std::cout << "Destructor !" << std::endl; }
};
int main(){
printf("Object:\n");
NewClass cls;
printf("\n");
printf("Pointer:\n");
NewClass* ptr1;
printf("\n");
printf("New a pointer:\n");
NewClass* ptr2 = new NewClass();
printf("\n");
// delete ptr2;
return 0;
}
Output:
1
2
3
4
5
6
7
8
9
10
Object:
Constructor !
Pointer:
New a pointer:
Constructor !
Destructor !
Program ended with exit code: 0
Here we can find that if we just declare a pointer, both the two functions won’t be called automatically.
If you new a pointer, the constructor will be called automatically, while the destructor won’t.
If you declare an object, both the two functions will be called automatically.
Therefore we conclude that the automatically-called mechanism only works for objects. For pointer, sorry, you need to operate them manually.
(2) Special situations
Sometimes the new wine can’t be made: the minimum density is larger than the given density or the maximum density is smaller than given density. We need to deal with them seperately.
My source code:
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <memory>
using namespace std;
// A bottle of wine
typedef pair<int, int> dpair;
// Node
/***********************************************
* Initialized value = 0;
* Counter = 0 <===> Nope or destroyed
* Counter = 1 <===> Created
************************************************/
struct Wine {
int d, p;
Wine* last;
static int counter;
Wine() { ++counter; }
~Wine() { --counter; }
};
int Wine::counter = 0;
/*****************************************************************
* Memory inspector, NO MODIFYING !!!!
* It will be destroyed when the programme ends,
* If counter != 0, it means that the wine is not destructed
*****************************************************************/
struct Checker {
int _;
~Checker() { if (Wine::counter != 0) cout << "你的对象没有正确释放!\n"; }
} _c;
int main() {
ios::sync_with_stdio(0);
int n, m;
vector<dpair> wines;
vector<int> qs;
// Input n,m and the density & price of each bottle of wine
// Create a wine shelf
cin >> n >> m;
for (int i = 0; i < n; ++i) {
int d, p;
cin >> d >> p;
wines.push_back(dpair(d, p));
}
// Sort according to density
sort(wines.begin(), wines.end());
// Create a new list
Wine* phead = nullptr;
Wine* temp = nullptr;
for (int i = 0; i < n; ++i) {
// Read in wine[i], you can say q = the corresponding struct node
auto q = new Wine;
q->d = wines[i].first;
q->p = wines[i].second;
// If two wines have the same value of d, discard the one whose q is bigger
if ( phead && phead->d == q->d) q->~Wine();
// If phead and its tail aren't NULL
while (phead != nullptr && phead->last != nullptr) {
// Compare slope factor, delete the nodes away from the list
// Convert the denominator to double type to avoid singular point
if ((q->p - phead->p) / (double)(q->d - phead->d) <=
(phead->p - phead->last->p) /(double)(phead->d - phead->last->d)){
temp = phead;
phead = phead->last;
temp->~Wine();
}
else break;
}
// If phead isn't NULL or phead doesn't match q
// The first loop go to here
if (!phead || q->d != phead->d) {
q->last = phead;
phead = q;
}
}
// Use vector to search
wines.clear();
for (auto i = phead; i; i = i->last) {
wines.push_back(dpair(i->d, i->p));
}
// Delete the list
for (auto i = phead; i; i = i->last) {
i->~Wine();
}
reverse(wines.begin(), wines.end());
cout.setf(ios::fixed);
for (int i = 0; i < m; ++i) {
int q;
cin >> q;
// Find the point which is the nearest to the the lowest hull
// Here price is initialized to 0
if((wines[0].first > q) || (wines[wines.size() - 1].first < q))
cout << -1 << endl;
else{
auto it = lower_bound(wines.begin(), wines.end(), dpair(q, 0));
auto ib = it - 1;
double res = (it->first - q) / (double)(it->first - ib->first) * ib->second;
res += (q - ib->first) / (double)(it->first - ib->first) * it->second;
cout << setprecision(2) << res << endl;
}
}
}
Acknowledgement:
Thanks for Zhixiao Xiong(熊志潇，未央工-11)’s help, after several days’ debugging, we finally found the reason why the object couldn’t be released correctly.